Table of Contents

Thread Scheduling in Java


The Use of Schedulers

As discussed earlier, threads are a common feature of newer operating systems and a convenient way to write programs. In general the implementation details of threads should not be a concern, however we need an understanding of how the thread scheduler defines the behaviour of the threads in the program.

We need a thread scheduler because only a single thread can execute at a time on a CPU, so we need some sort of algorithm to control the order in which threads get access to the CPU. Even on a multi-processor this is an issue because there could be more threads than there are processors. While the details of the scheduler implementation is by its very nature very specific to the OS and hardware that it runs on, a multi-platform language like Java must provide a definition of how the thread scheduler behaves which holds for all platforms.

The scheduler must be able to initiate a context switch which is the removal of a thread from the CPU and its replacement by another thread. It needs to do this in some organized fashion, which is hopefully fair. By fairness we mean that threads should all occaisionally get their own turn on the CPU so that there is no risk of starvation. Fairness, does not mean that all threads need an equal amount of time on the CPU. Normally threads are assigned a priority value which gives a value to how urgenty the thread needs a time-slice on the CPU. However, even the low priority threads must get an occaisional chance on the CPU - otherwise they are "starving". As we shall see, Java does not do a very good job at ensuring fairness to its threads.

The Java Scheduler

The Java thread scheduler is very simple. All threads have a priority value which can be changed dynamically by calls to the threads setPriority() method.

A "runnable" thread is a thread that is able to run - it is not, for example, waiting on I/O or a condition variable. In Java the "runnable" thread with the highest priority is always running. This means that if a thread with higher priority becomes runnable, it will immediately pre-empt the lower priority thread.

The behaviour of the thread scheduler with regard to more than one thread running at the same highest priority is not defined. In some systems it may use round-robin time-slicing to give all such threads equal time, while in other systems it may let the first thread to run continually, at the expense of the other threads.

The yield() method is provided to allow threads to voluntarily give up the CPU periodically to let other threads run. Because some systems may not use round-robin scheduling, all Java programs must use calls to "yeild()" or else they may not behave properly on some systems.

Problems with the Java Scheduler

This scheme is fairly easy to implement, in particular on systems that do not themselves provide threads as a operating system primitive. This partly makes sense with the design goals of keeping Java simple and small. However this design has sacrificed ease of programming by not ensuring thread fairness.

Java threads are not fair for two reasons:

First I discuss this second problem. As an analogy, consider Windows 3.1. It was a multi-tasking system that had a similar scheduler to this Java design. Programmers had to voluntarily give up the CPU in order to allow different processes a chance to use the system. This resulted in poor multi-tasking performance and even the chance that one program could hang the whole system by never giving up its control. Windows 95 has rectified this situation by providing a pre-emptive scheduler. Now multi-tasking performance is much better, and programs are easier to write. Unfortunately by requiring the use of the "yield()" method, Java follows the Windows 3.1 scheme. Even worse its behaviour is inconsistent from platform to platform so a program must be very carefully written.

Currently Java has mostly been used to implement small simple applications, and for these the limitations of the thread scheduler can be easily worked around with intelligent programming. However when people try to implement large, complex systems with code coming from different programmers, the problems of making sure that all the threads are getting enough time on the CPU may become more of a problem. A single thread that fails to call "yeild()" and runs at a high priority could cause the whole application to fail. A thread with a low priority value may never execute.

The White Paper from Sun has only the following to say about the short comings of the scheduler:

"Other benefits of multithreading are better interactive responsiveness and real-time behavior. This is limited, however, by the underlying platform: stand-alone Java runtime environments have good real-time behavior. Running on top of other systems like Unix, Windows, the Macintosh, or Windows NT limits the real-time responsiveness to that of the underlying system."

This blames the underlying OS for Java's behaviour. However Java should be responsible for ensuring a consistent behaviour on all systems that it supports. This is possible, as I outline in the next section.

Suggested Changes - A Good Scheduler

Thread-scheduling is practically the same as process scheduling on a multi-tasking system. Systems like UNIX have been able to provide quite robust and practical multitasking for many years - the science is not new or radical. Current systems, for example Windows NT, have extended this system to the robust and practical scheduling of threads within each process. As mentioned, all of the current or next-wave operating systems will have this same functionality. It is therefore logical that Java should be changed to take advantage of these intelligent algorithms.

A thread scheduler could ensure good behaviour for its threads by guaranteeing that threads will be pre-empted off the CPU after some fixed time quanta and that the algorithm that chooses which thread executes next will make a good choice that will prevent starvation.

The choice of which thread to execute is the source of most of the complexity in these algorithms. Threads are meant to have different behaviour - some work in the background doing CPU intensive calculations, some wait around doing nothing while waiting for network communication, others serve the user by reading input and updating the screen. By their very nature these threads need to be given CPU time in a more sophisticated manner than just allowing them all equal time. A common way to ensure some fair behaviour, is to allow low-priority threads to "age", meaning that their priority gets larger until they are the highest priority thread and are allowed to execute, after which they are given their original low-priority again.

The best thing about these systems is that, although they are significantly more complicated than the current Java scheme, their implementation details are not of a concern to the programmer. The programmer's task is easier than the current scheme because there is no need to call "yeild()" or ensure that the priority values are perfect to allow the code to work. The threads in the system will work in a fair manner automatically - the setting of priority values is just a optimization technique to fine-tune performance. This is a much more desirable system for the Java threads.

Implementation for Java

To give Java a sophisticated thread scheduler on top of an operating system that has a good thread scheduler for its threads would not be difficult at all. Java could just map its threads to the operating system threads and then let the OS scheduler do the work.

This is a more difficult problem on a operating system that is not multi-threaded. In this case the Java code would have to implement its own scheduler. We know that this is possible because we could implement one ourselves in Java. We know that a high priority thread can pre-empt a lower priority thread, so we can have a controlling thread at the highest priority that wakes up every time quantum, and sets the priority of the other threads so that the correct thread will execute next. Although it is possible to program such a class, it should be built into the system to save the programmer the extra work, to make Java programs run consistently, and for efficiency.

With this extra work Java could have consistent multi-threaded behaviour on all platforms, without the need for yields() and other gymnastics.

Conclusion

Java's usefulness as a concurrent language is risked by having such a weak thread scheduling scheme. It would be much better if a system that matches more with the schemes that modern operating systems provide is implemented so that the programmer needs to do less work to ensure that programs run properly.
Table of Contents Top of this Page Next Chapter