If the details of thread scheduling seem somewhat esoteric, here’s the good news: most of the time, all the scheduling details in this chapter have no practical impact on your Java program. This is true, in general, of threaded programs under any operating system and with any threading library, but it’s particularly true in the case of Java programs.
In a Java program, a thread is most often created because the
programmer wants to call a method that may block—-usually a
read() method on a slow InputStream (such as a
SocketInputStream), or the Thread.sleep() method
to emulate a periodic timer, or the wait()
method to wait for a particular event. As a result, threads in the
Java virtual machine tend to oscillate between the blocked and
runnable states quite often. And as long as every thread in the Java
virtual machine blocks periodically, they will all get an opportunity
to run: each thread becomes the currently running thread, blocks,
exits the blocked state, is placed on the end of the list for its
priority, and moves up through the list as other threads go through
the same cycle.
Even in those cases where all the threads in the virtual machine do not periodically block, it’s usually possible to ignore the issue of scheduling altogether. A Java program usually performs a specific task, and often the completion of that task is all that matters. A Java program that is charged with calculating and displaying four convolutions of a GIF image has to wait for all four convoluted images to be complete before it displays the final image. It’s more convenient to program this so that each convolution is performed in a separate thread, but it will take the same amount of time to calculate all four convolutions whether each thread calculates its image sequentially or whether there’s some sort of round-robin scheduling among the four threads. When the task of our Java program is divided into separate subtasks and each subtask is written as a separate thread, we can often ignore the scheduling of those separate threads because, in the end, all we care about is the completed task.
So when do we care about the scheduling mechanism of these threads? When all of these normal cases do not apply; specifically, when:
There are one or more CPU-intensive threads in the program
and either
Intermediate results of the calculations are interesting (e.g., if we wanted to see one of the four convolved GIF images as soon as possible)
or
The threads are not performing a joint task; they’re providing separate tasks that should, in fairness, either employ a round-robin scheduling paradigm (e.g., a server program that is acting on requests on behalf of several different users) or employ a sequential scheduling paradigm (e.g., a server that processes user requests on a first-come, first-served basis).
We’ll look at these cases in more depth as we discuss the various mechanisms to achieve them.
Many developers are surprised to learn that equal-priority Java threads are not automatically timesliced by a round-robin scheduler. Part of this surprise stems from the tendency to think of threads within a program as equivalent in theory to processes in an operating system: it has long been ingrained in our psyches that a timesliced scheduler is the fairest mechanism to deal with multiple processes. And, in an interactive user environment, that’s usually the case.
There are, however, occasions when a round-robin scheduler is not the fairest scheduling algorithm available and the programmer is required to make sure that no timeslicing of threads occurs. Consider the case of a calculation server that accepts connections from multiple clients simultaneously and runs each client in a separate thread. This is an elegant server architecture, but the question of the best scheduling mechanism to employ with this architecture turns out to be a profound one.
Let’s take the case of a CalcServer that performs some sort of complex, analytic calculation for each of the clients that connects to it; assume that the calculation requires some 5 seconds for each client. When five clients connect to the server at roughly the same time, the CalcServer starts five separate threads. If those threads are subject to timeslicing, it takes about 25 seconds for all threads to reach the end of their calculation, and because the CPU has been equitably shared, each thread reaches the end of its individual calculation at this 25-second mark. So each client receives an answer after 25 seconds.
If no round-robin scheduling is in effect in our CalcServer, however, then we have a different case: the clients still connect at the same time, but one client (somewhat arbitrarily) gets the opportunity to run its calculation to conclusion; the first client gets an answer in just 5 seconds instead of 25 seconds. Then the second client’s calculation begins; the second client gets its answer after 10 seconds have passed, and so on. Only the fifth client has to wait the entire 25 seconds for an answer.
Which of these scheduling modes is the “fairest”? The answer to that depends on what happens during the 5 seconds the server calculates on behalf of the client. If the server provides just a single answer to the client, clearly the non-timesliced version is “fairest”: on average, each client has to wait 15 seconds for an answer versus 25 seconds for the timesliced version. If, instead, the server provides five answers to the client—one for every second of calculation—then the timesliced version is “fairest”: each client has one answer after 5 seconds, whereas in the non-timesliced version, the fifth client won’t have its first answer until 21 seconds have passed.
In other words, this is once again the “intermediate results” requirement: if intermediate results are important to us, a round-robin scheduler provides the fairest results to all the threads. But if all we care about is the final answer, a round-robin scheduler on a single-CPU machine is not appropriate: in the best of cases, it doesn’t provide any benefits, and in cases like our CalcServer calculator, it actually decreases throughput in the system.
This situation becomes more complicated on a system with multiple CPUs. If there are four CPUs available to run our five threads, then on a system that does not perform round-robin scheduling, the average client will receive an answer after 6 seconds: the first four will receive an answer after 5 seconds, and the last will receive one after 10 seconds. On the other hand, if round-robin scheduling is involved, the average answer will be received in 6.2 seconds. However, the distribution of those answers will all be very close to 6.2 seconds: in fact, we can essentially say that each client will get an answer in 6.2 seconds. So even though the average calculation time with round-robin scheduling is slightly greater, it may be perceived to be fairer. And in this case if all we care about is the final answer from all five threads, then round-robin scheduling will be faster: 6.2 seconds versus 10 seconds.