An example should make this clearer. Let’s look at the following (incomplete) code example:

public class SchedulingExample implements Runnable {
    public static void main(String args[]) {
        Thread calcThread = new Thread(this);
        calcThread.setPriority(4);
        calcThread.start();

        AsyncReadSocket reader;
        reader = new AsyncReadSocket(new Socket(host, port));
        reader.setPriority(6);
        reader.start();

        doDefault();
    }

    public void run() {
        doCalc();
    }
}

This Java program has three threads: first, there’s the default thread executing the main() method, which, after creating the other threads, is going to execute the doDefault() method. Second, there’s the calculation thread (calcThread) that is going to execute the doCalc() method. And third, there’s the reader AsyncReadSocket thread (from Chapter 3) that’s reading a socket.

In the following discussion, we assume the threads we created are the only threads in the Java virtual machine, but as we already know, there are many other threads that have been created on our behalf. For simplicity, we’ll ignore those threads, since, for the most part, they’ll remain in the blocked state and won’t affect this discussion. Figure 6.1 shows the transition of the threads in our example between their various states.

Figure 6-1. Thread state diagram

We start at time T1 with our single default thread executing the main() method. The initial thread has a priority of 5 and is the only active thread in the Java virtual machine. So the default thread is in the runnable state and is also the currently running thread. At time T2, the default thread creates the calcThread, gives it a priority of 4, and calls its start() method. Now there are two threads in the runnable state, but the default thread is still the currently running thread because it has a higher priority than calcThread . calcThread is in the runnable state, but it is waiting for the CPU.

The default thread continues execution: it creates the reader thread, gives it a priority of 6, and then calls the thread’s start() method. After the default thread calls the reader thread’s start() method, the reader thread enters the runnable state. Because reader has a higher priority than the default thread, reader becomes the currently running thread (at the expense of the default thread, which will no longer be running even though it’s in the runnable state). These changes in the states of the threads are shown at time T3 in the diagram.

Now the reader thread executes the readChar() method on its socket. If no data is available, the reader thread enters the blocked state (shown at time T4). When this happens, the default thread begins execution from the point at which it was previously interrupted (in fact, the default thread will be completely unaware that it had been interrupted). The default thread continues to be the currently running thread until data becomes available to satisfy the readChar() method. When this data becomes available (at time T5), the Java virtual machine changes the state of the reader thread to the runnable state. When the Java virtual machine changes the state, it notices that this thread now has the highest priority of all the runnable threads, so it interrupts the default thread and makes the reader thread the currently running thread.

Meanwhile, calcThread has been patiently waiting for its chance to run, and it must continue to wait until both the default thread and the reader thread are blocked or have exited (or until some thread raises the priority of calcThread). calcThread is in danger of never becoming the currently running thread at all, a concept known as CPU starvation. In general, it is the responsibility of Java developers to ensure that none of the threads in their Java programs starve; the Java virtual machine never adjusts any thread’s priority to compensate for that thread’s lack of availability to the CPU (though some underlying operating systems may do so).

In most Java programs, we’ll have multiple threads of the same priority; we need to expand our discussion to take this into account. What follows is a description of what happens at a conceptual level within the Java virtual machine. Once again, our intent here is to provide an illustration of how the thread scheduling within the Java virtual machine works, not to provide a blueprint of how any particular Java virtual machine is actually implemented.

We can conceive that the Java virtual machine keeps track of all the threads in a Java program by means of linked lists; every thread in the Java virtual machine is on a list that represents the state of that thread. A thread can have any one of eleven priorities, so we conceive of fourteen linked lists: one for all threads in the initial state, one for all threads in the blocked state, one for all threads in the exiting state, and one for each priority level. The list of threads at a given priority level represents only those threads that are currently in the runnable state: a thread in the runnable state at priority 7 will be on the priority 7 list, but when the thread blocks, it moves to the blocked linked list.

For simplicity, we conceive of these threads as being on an ordered list; in reality, they may be held in simple pools. Keeping the threads in a linked list implies that there is an order by which the threads will be selected to become the currently running thread, and while that is a useful way of thinking about the process, it is not necessarily the way an implementation may work.

Let’s revisit our last example and this time change the priority of calcThread so that it is now the same as the default thread. If these two threads have the same priority, then our state diagram might look like Figure 6.2. Note that in the figure, we now start at time T2, since that’s when things become interesting.

Figure 6-2. Thread state diagram for equal-priority threads

The difference now is that the default thread and calcThread have the same priority, so that when the reader thread blocks, the Java virtual machine does something different to select the currently running thread. In this example, we’re concerned with only three of Java’s internal lists: the list of priority 5 threads (the default thread and calcThread), the list of priority 6 threads (the reader thread), and the list of blocked threads. As the Java virtual machine enters time T2, when calcThread is started, those lists look like this:^[8]

               PRIORITY 5:  Default -> calcThread -> NULL
PRIORITY 6:  NULL
   BLOCKED:  NULL

So the Java virtual machine selects the default thread to be the currently running thread since it is at the head of the non-empty list that has the highest priority. The Java virtual machine also alters the priority 5 list so that as it exits time T2; that list appears as:

               PRIORITY 5:  calcThread -> Default -> NULL

At time T3, the default thread starts the reader thread, which will preempt the default thread. The Java virtual machine’s internal lists now look like this:

               PRIORITY 5:  calcThread -> Default -> NULL
PRIORITY 6:  reader -> NULL
   BLOCKED:  NULL

At T4 when the reader thread enters the blocked state, the Java virtual machine searches for a non-empty priority list and finds one at priority 5; the first thread in that list (calcThread) becomes the currently running thread and gets moved to the end of the list. So exiting time T4, the internal lists now look like this:

               PRIORITY 5:  Default -> calcThread -> NULL
PRIORITY 6:  NULL
   BLOCKED:  reader -> NULL

And so we continue: every time the reader thread enters the blocked state, the default thread and calcThread change positions on the priority 5 list, and they alternate becoming the currently running thread.

In this example, we’ve posited the notion that when a thread is made the currently runnable thread, it is moved to the end of the list. As a result, every time the reader thread blocks, a different thread from the priority 5 list will become the currently running thread. While this is by far the most common implementation of the Java virtual machine, it is not a requirement: we know of one particular real-time operating system in which threads that are interrupted are not reordered as they are in this discussion. On that implementation (and any like it), the calcThread and reader thread would execute alternately and the default thread would starve.

In a typical priority-based threading system, something unusual occurs when a thread attempts to acquire a lock that is held by a lower-priority thread: because the higher-priority thread becomes blocked, it temporarily runs with an effective priority of the lower-priority thread. Say that we have a thread with a priority of 8 that wants to acquire a lock that is held by a thread with a priority of 2. Because the priority 8 thread is waiting for the priority 2 thread to release the lock, it ends up running with an effective priority of 2. This is known as priority inversion.

Priority inversion is often solved by priority inheritance. With priority inheritance, a thread that holds a lock that is wanted by a thread with a higher priority will have its priority temporarily and silently raised; its new priority becomes the same as the priority of the thread that it is causing to block. When the thread releases the lock, its priority is lowered to its original value.

Let’s look at an example. Say that we have three threads: Thread2, Thread5, and Thread8, which have priorities, respectively, of 2, 5, and 8. We’ll start at the point where Thread2 is the currently running thread, and the other threads are therefore blocked:

               PRIORITY 2:  Thread2 -> NULL
PRIORITY 5:  NULL
PRIORITY 8:  NULL
   BLOCKED:  Thread5 -> Thread8 -> NULL

At this point in time, Thread2 has obtained a lock, but since no other thread wants the lock, its priority is not changed. Now, say that Thread5 unblocks; it will become the currently running thread:

               PRIORITY 2:  Thread2 -> NULL
PRIORITY 5:  Thread5 -> NULL
PRIORITY 8:  NULL
   BLOCKED:  Thread8 -> NULL

Now, when Thread8 unblocks it will become the currently running thread. If it then attempts to acquire the lock held by Thread2, it will again block, but the priority of Thread2 will be adjusted to 8:

               PRIORITY 2:  NULL
PRIORITY 5:  Thread5 -> NULL
PRIORITY 8:  Thread2 -> NULL
   BLOCKED:  Thread8 -> NULL

So Thread2 will be selected as the currently running thread, even though its programmed priority is lower than another runnable thread. When Thread2 releases its lock, its priority will be changed back to 2, and Thread8 will unblock (since the lock it was waiting for is no longer held):

               PRIORITY 2:  Thread2 -> NULL
PRIORITY 5:  Thread5 -> NULL
PRIORITY 8:  Thread8-> NULL
   BLOCKED:  NULL

And, predictably, Thread8 will become the currently running thread.

The goal of priority inheritance is to allow the high-priority thread to run as soon as possible. If the inheritance did not occur in the above example, then Thread8 would have to wait until Thread5 blocked or exited before Thread2 could run and give up its lock. This would give Thread8 (temporarily) an equivalent priority of 2. Priority inheritance changes that scenario in favor of the higher-priority thread.

Priority inheritance is a common, but not mandatory, feature of Java virtual machines.

In our previous example, there was never a time when the calcThread and the default thread switched places on their priority queue without the reader thread intervening. Stated another way, the calcThread never preempts the default thread, and vice versa. This is confusing to many people, who assume that preemptive means that threads of the same priority will timeslice—that is, that they will periodically preempt each other.

The case in which threads of the same priority preempt each other is referred to as round-robin scheduling and is one of the more contentious aspects of Java thread scheduling. Nothing in the Java language specification requires a virtual machine to employ round-robin scheduling, but nothing prevents a virtual machine from implementing it either. Because of their ties to the operating system, many implementations of the virtual machine do employ round-robin scheduling, but many—especially on non-Windows platforms—do not.

This introduces a level of non-deterministic behavior into our discussion. On a platform that performs round-robin scheduling, threads of equal priority will periodically yield to each other. This process follows the same ideas we outlined above: the thread is selected to run and moves to the end of its priority queue. The presence of round-robin scheduling, however, means that periodically an internal timer will go off, which will interrupt the currently running thread and cause the next thread on the priority queue to become the currently running thread. But on a platform without round-robin scheduling, the currently running thread will continue to run until it blocks or until a higher-priority thread is able to run.

The absence or presence of priority inheritance or of round-robin scheduling among threads of equal priority is only one difference that exists between the scheduling of threads on different implementations of the Java virtual machine. These differences exist because the Java language specification has very little to say about thread scheduling, and different implementations have therefore leveraged the features of the host platform to provide support for Java threads.

In the very early days of Java, priority-based thread scheduling was thought to be absolute: the highest-priority runnable thread would always be the currently running thread. Many Java programming books (including the first release of this book) based their discussions of thread programming on that premise. The new version of the Java specification, however, says only this about thread scheduling: “Threads with higher priority are generally executed in preference to threads with lower priority. Such preference is not, however, a guarantee that the highest priority thread will always be running, and thread priorities cannot be used to reliably implement mutual exclusion.”^[9]

This clarification is an admission of how things work in the real world. Some operating systems cannot tell exactly when a blocked thread becomes runnable, and so there may be a small amount of time between when a high-priority blocked thread becomes runnable and when it actually becomes the currently running thread. In practice, that difference is rarely important, because you can’t predict absolutely when a thread will become unblocked anyway. If there’s a slight delay between when data arrives on a socket and when the thread reading the socket is unblocked, your program won’t know; it will simply assume that the data was delayed slightly longer than it was. Java is not, after all, a real-time operating system.

More important, however, is that many implementations of the Java virtual machine now allow Java threads to be scheduled directly by the operating system rather than by the virtual machine itself. And while operating systems can generally follow the principle of priority-based scheduling that we’ve outlined here, they usually add some additional complexity to thread scheduling that affects the simple notion that we’ve outlined.

Hence, understanding how Java threads are ultimately scheduled requires an understanding of the particular virtual machine involved. There are two basic variations here:

Later in this chapter, we’ll discuss the implementations of these thread models on several platforms and the subtle differences between these implementations with respect to thread scheduling.