Java 101: Understanding Java threads, Part 3: Thread scheduling and wait/notify

Learn about the mechanisms that help you set and manage thread priority

This month, I continue my four-part introduction to Java threads by focusing on thread scheduling, the wait/notify mechanism, and thread interruption. You'll investigate how either a JVM or an operating-system thread scheduler chooses the next thread for execution. As you'll discover, priority is important to a thread scheduler's choice. You'll examine how a thread waits until it receives notification from another thread before it continues execution and learn how to use the wait/notify mechanism for coordinating the execution of two threads in a producer-consumer relationship. Finally, you'll learn how to prematurely awaken either a sleeping or a waiting thread for thread termination or other tasks. I'll also teach you how a thread that is neither sleeping nor waiting detects an interruption request from another thread.

Note that this article (part of the JavaWorld archives) was updated with new code listings and downloadable source code in May 2013.

Thread scheduling

In an idealized world, all program threads would have their own processors on which to run. Until the time comes when computers have thousands or millions of processors, threads often must share one or more processors. Either the JVM or the underlying platform's operating system deciphers how to share the processor resource among threads—a task known as thread scheduling. That portion of the JVM or operating system that performs thread scheduling is a thread scheduler.

Note: To simplify my thread scheduling discussion, I focus on thread scheduling in the context of a single processor. You can extrapolate this discussion to multiple processors; I leave that task to you.

Remember two important points about thread scheduling:

  1. Java does not force a VM to schedule threads in a specific manner or contain a thread scheduler. That implies platform-dependent thread scheduling. Therefore, you must exercise care when writing a Java program whose behavior depends on how threads are scheduled and must operate consistently across different platforms.
  2. Fortunately, when writing Java programs, you need to think about how Java schedules threads only when at least one of your program's threads heavily uses the processor for long time periods and intermediate results of that thread's execution prove important. For example, an applet contains a thread that dynamically creates an image. Periodically, you want the painting thread to draw that image's current contents so the user can see how the image progresses. To ensure that the calculation thread does not monopolize the processor, consider thread scheduling.

Examine a program that creates two processor-intensive threads:

Listing 1. SchedDemo.java

// SchedDemo.java
class SchedDemo
{
   public static void main (String [] args)
   {
      new CalcThread ("CalcThread A").start ();
      new CalcThread ("CalcThread B").start ();
   }
}
class CalcThread extends Thread
{
   CalcThread (String name)
   {
      // Pass name to Thread layer.
      super (name);
   }
   double calcPI ()
   {
      boolean negative = true;
      double pi = 0.0;
      for (int i = 3; i < 100000; i += 2)
      {
           if (negative)
               pi -= (1.0 / i);
           else
               pi += (1.0 / i);
           negative = !negative;
      }
      pi += 1.0;
      pi *= 4.0;
      return pi;
   }
   public void run ()
   {
      for (int i = 0; i < 5; i++)
         System.out.println (getName () + ": " + calcPI ());           
   }
}

SchedDemo creates two threads that each calculate the value of pi (five times) and print each result. Depending upon how your JVM implementation schedules threads, you might see output resembling the following:

CalcThread A: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread B: 3.1415726535897894

According to the above output, the thread scheduler shares the processor between both threads. However, you could see output similar to this:

CalcThread A: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread A: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread B: 3.1415726535897894
CalcThread B: 3.1415726535897894

The above output shows the thread scheduler favoring one thread over another. The two outputs above illustrate two general categories of thread schedulers: green and native. I'll explore their behavioral differences in upcoming sections. While discussing each category, I refer to thread states, of which there are four:

  1. Initial state: A program has created a thread's thread object, but the thread does not yet exist because the thread object's start() method has not yet been called.
  2. Runnable state: This is a thread's default state. After the call to start() completes, a thread becomes runnable whether or not that thread is running, that is, using the processor. Although many threads might be runnable, only one currently runs. Thread schedulers determine which runnable thread to assign to the processor.
  3. Blocked state: When a thread executes the sleep(), wait(), or join() methods, when a thread attempts to read data not yet available from a network, and when a thread waits to acquire a lock, that thread is in the blocked state: it is neither running nor in a position to run. (You can probably think of other times when a thread would wait for something to happen.) When a blocked thread unblocks, that thread moves to the runnable state.
  4. Terminating state: Once execution leaves a thread's run() method, that thread is in the terminating state. In other words, the thread ceases to exist.

How does the thread scheduler choose which runnable thread to run? I begin answering that question while discussing green thread scheduling. I finish the answer while discussing native thread scheduling.

Green thread scheduling

Not all operating systems, the ancient Microsoft Windows 3.1 perating system, for example, support threads. For such systems, Sun Microsystems can design a JVM that divides its sole thread of execution into multiple threads. The JVM (not the underlying platform's operating system) supplies the threading logic and contains the thread scheduler. JVM threads are green threads, or user threads.

A JVM's thread scheduler schedules green threads according to priority—a thread's relative importance, which you express as an integer from a well-defined range of values. Typically, a JVM's thread scheduler chooses the highest-priority thread and allows that thread to run until it either terminates or blocks. At that time, the thread scheduler chooses a thread of the next highest priority. That thread (usually) runs until it terminates or blocks. If, while a thread runs, a thread of higher priority unblocks (perhaps the higher-priority thread's sleep time expired), the thread scheduler preempts, or interrupts, the lower-priority thread and assigns the unblocked higher-priority thread to the processor.

Note: A runnable thread with the highest priority will not always run. Here's the Java Language Specification's take on priority:

Every thread has a priority. When there is competition for processing resources, 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.

That admission says much about the implementation of green thread JVMs. Those JVMs cannot afford to let threads block because that would tie up the JVM's sole thread of execution. Therefore, when a thread must block, such as when that thread is reading data slow to arrive from a file, the JVM might stop the thread's execution and use a polling mechanism to determine when data arrives. While the thread remains stopped, the JVM's thread scheduler might schedule a lower-priority thread to run. Suppose data arrives while the lower-priority thread is running. Although the higher-priority thread should run as soon as data arrives, that doesn't happen until the JVM next polls the operating system and discovers the arrival. Hence, the lower-priority thread runs even though the higher-priority thread should run. ou need to worry about this situation only when you need real-time behavior from Java. But then Java is not a real-time operating system, so why worry?

To understand which runnable green thread becomes the currently running green thread, consider the following. Suppose your application consists of three threads: the main thread that runs the main() method, a calculation thread, and a thread that reads keyboard input. When there is no keyboard input, the reading thread blocks. Assume the reading thread has the highest priority and the calculation thread has the lowest priority. (For simplicity's sake, also assume that no other internal JVM threads are available.) Figure 1 illustrates the execution of these three threads.

Figure 1. Thread-scheduling diagram for different priority threads

At time T0, the main thread starts running. At time T1, the main thread starts the calculation thread. Because the calculation thread has a lower priority than the main thread, the calculation thread waits for the processor. At time T2, the main thread starts the reading thread. Because the reading thread has a higher priority than the main thread, the main thread waits for the processor while the reading thread runs. At time T3, the reading thread blocks and the main thread runs. At time T4, the reading thread unblocks and runs; the main thread waits. Finally, at time T5, the reading thread blocks and the main thread runs. This alternation in execution between the reading and main threads continues as long as the program runs. The calculation thread never runs because it has the lowest priority and thus starves for processor attention, a situation known as processor starvation.

We can alter this scenario by giving the calculation thread the same priority as the main thread. Figure 2 shows the result, beginning with time T2. (Prior to T2, Figure 2 is identical to Figure 1.)

Figure 2. Thread-scheduling diagram for equal priority main and calculation threads, and a different priority reading thread

At time T2, the reading thread runs while the main and calculation threads wait for the processor. At time T3, the reading thread blocks and the calculation thread runs, because the main thread ran just before the reading thread. At time T4, the reading thread unblocks and runs; the main and calculation threads wait. At time T5, the reading thread blocks and the main thread runs, because the calculation thread ran just before the reading thread. This alternation in execution between the main and calculation threads continues as long as the program runs and depends on the higher-priority thread running and blocking.

We must consider one last item in green thread scheduling. What happens when a lower-priority thread holds a lock that a higher-priority thread requires? The higher-priority thread blocks because it cannot get the lock, which implies that the higher-priority thread effectively has the same priority as the lower-priority thread. For example, a priority 6 thread attempts to acquire a lock that a priority 3 thread holds. Because the priority 6 thread must wait until it can acquire the lock, the priority 6 thread ends up with a 3 priority—a phenomenon known as priority inversion.

Priority inversion can greatly delay the execution of a higher-priority thread. For example, suppose you have three threads with priorities of 3, 4, and 9. Priority 3 thread is running and the other threads are blocked. Assume that the priority 3 thread grabs a lock, and the priority 4 thread unblocks. The priority 4 thread becomes the currently running thread. Because the priority 9 thread requires the lock, it continues to wait until the priority 3 thread releases the lock. However, the priority 3 thread cannot release the lock until the priority 4 thread blocks or terminates. As a result, the priority 9 thread delays its execution.

1 2 3 4 Page
Recommended
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more