Untangling Java concurrency

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

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

1 2 3 4 Page 2
Page 2 of 4

A JVM's thread scheduler usually solves the priority inversion problem through priority inheritance: The thread scheduler silently raises the priority of the thread holding the lock when a higher-priority thread requests the lock. As a result, both the thread holding the lock and the thread waiting for the lock temporarily have equal priorities. Using the previous example, the priority 3 thread (holding the lock) would temporarily become a priority 9 thread as soon as the priority 9 thread attempts to acquire the lock and is blocked. As a result, the priority 9 thread (holding the lock) would become the currently running thread (even when the priority 4 thread unblocks). The priority 9 thread would finish its execution and release the lock, allowing the waiting priority 9 thread to acquire the lock and continue execution. The priority 4 thread would lack the chance to become the currently running thread. Once the thread with its silently raised priority releases the lock, the thread scheduler restores the thread's priority to its original priority. Therefore, the thread scheduler would restore the priority 9 thread previously holding the lock to priority 3, once it releases the lock. Thus, priority inheritance ensures that a lower-priority thread holding a lock is not preempted by a thread whose priority exceeds the lock-holding thread's priority but is less than the priority of the thread waiting for the lock to release.

Native thread scheduling

Most JVMs rely on the underlying operating system (such as Linux or Microsoft Windows XP) to provide a thread scheduler. When an operating system handles thread scheduling, the threads are native threads. As with green thread scheduling, priority proves important to native thread scheduling: higher-priority threads typically preempt lower-priority threads. But native thread schedulers often introduce an additional detail: time-slicing.

Note: Some green thread schedulers also support time-slicing. And many native thread schedulers support priority inheritance. As a result, green thread schedulers and native thread schedulers normally differ only in their thread scheduler's source: JVM or operating system.

Native thread schedulers typically introduce time-slicing to prevent processor starvation of equal-priority threads. The idea is to give each equal-priority thread the same amount of time, known as a quantum. A timer tracks each quantum's remaining time and alerts the thread scheduler when the quantum expires. The thread scheduler then schedules another equal-priority thread to run, unless a higher-priority thread unblocks.

Time-slicing complicates the writing of those platform-independent multithreaded programs that depend on consistent thread scheduling, because not all thread schedulers implement time-slicing. Without time-slicing, an equal-priority runnable thread will keep running (assuming it is the currently running thread) until that thread terminates, blocks, or is replaced by a higher-priority thread. Thus, the thread scheduler fails to give all equal-priority runnable threads the chance to run. Though complicated, time-slicing does not prevent you from writing platform-independent multithreaded programs. The setPriority(int priority) and yield() methods influence thread scheduling so a program behaves fairly consistently (as far as thread scheduling is concerned) across platforms.

Note: To prevent lower-priority threads from starving, some thread schedulers, such as Windows schedulers, give temporary priority boosts to threads that have not run in a long time. When the thread runs, that priority boost decays. Thread schedulers still give higher-priority threads preference over lower-priority threads, but at least all threads receive a chance to run.

Schedule with the setPriority(int priority) method

Enough theory! Let's learn how to influence thread scheduling at the source code level. One way is to use Thread's void setPriority(int priority); method. When called, setPriority(int priority) sets the priority of a thread associated with the specified thread object (as in thd.setPriority (7);), to priority. If priority is not within the range of priorities that Thread's MIN_PRIORITY and MAX_PRIORITY constants specify, setPriority(int priority) throws an IllegalArgumentException object.

Note: If you call setPriority(int priority) with a priority value that exceeds the maximum allowed priority for the respective thread's thread group, this method silently lowers the priority value to match the thread group's maximum priority. (I'll discuss thread groups next month.)

When you must determine a thread's current priority, call Thread's int getPriority() method, via that thread's thread object. The getPriority() method returns a value between MIN_PRIORITY (1) and MAX_PRIORITY (10). One of those values might be 5—the value that assigns to the NORM_PRIORITY constant, which represents a thread's default priority.

The setPriority(int priority) method proves useful in preventing processor starvation. For example, suppose your program consists of a thread that blocks and a calculation thread that doesn't block. By assigning a higher priority to the thread that blocks, you ensure the calculation thread will not starve the blocking thread. Because the blocking thread periodically blocks, the calculation thread will not starve. Of course, we assume the thread scheduler does not support time-slicing. If the thread scheduler does supports time-slicing, you will probably see no difference between calls to setPriority(int priority) and no calls to that method, depending on what the affected threads are doing. However, you will at least ensure that your code ports across thread schedulers. To demonstrate setPriority(int priority), I wrote PriorityDemo:

Listing 2. PriorityDemo.java

// PriorityDemo.java
class PriorityDemo
{
   public static void main (String [] args)
   {
      BlockingThread bt = new BlockingThread ();
      bt.setPriority (Thread.NORM_PRIORITY + 1);
      CalculatingThread ct = new CalculatingThread ();
      bt.start ();
      ct.start ();
      try
      {
          Thread.sleep (10000);
      }
      catch (InterruptedException e)
      {
      }
      bt.setFinished (true);
      ct.setFinished (true);
   }
}
class BlockingThread extends Thread
{
   private boolean finished = false;
   public void run ()
   {
      while (!finished)
      {
         try
         {
            int i;
            do
            {
               i = System.in.read ();
               System.out.print (i + " ");
            }
            while (i != '\n');
            System.out.print ('\n');
         }
         catch (java.io.IOException e)
         {
         }
      }
   }
   public void setFinished (boolean f)
   {
      finished = f;
   }
}
class CalculatingThread extends Thread
{
   private boolean finished = false;
   public void run ()
   {
      int sum = 0;
      while (!finished)
         sum++;
   }
   public void setFinished (boolean f)
   {
      finished = f;
   }
}

PriorityDemo has a blocking thread and a calculating thread in addition to the main thread. Suppose you ran this program on a platform where the thread scheduler did not support time-slicing. What would happen? Consider two scenarios:

  1. Assume no bt.setPriority (Thread.NORM_PRIORITY + 1); method call: The main thread runs until it sleeps. At that point, assume the thread scheduler starts the blocking thread. That thread runs until it calls System.in.read(), which causes the blocking thread to block. The thread scheduler then assigns the calculating thread to the processor (assuming the main thread has not yet unblocked from its sleep). Because the blocking, main, and calculating threads all have the same priority, the calculating thread continues to run in an infinite loop.
  2. Assume bt.setPriority (Thread.NORM_PRIORITY + 1); method call: The blocking thread gets the processor once it unblocks. Then assume that the thread scheduler arbitrarily chooses either the calculating thread or the main thread (assuming the main thread has unblocked from its sleep) when the blocking thread blocks upon its next call to System.in.read(). As a result, the program should eventually end. If the thread scheduler always picks the calculating thread over the main thread, consider boosting the main thread's priority to ensure eventual termination.

If you run PriorityDemo with time-slicing, you have the following two scenarios:

  1. Assume no bt.setPriority (Thread.NORM_PRIORITY + 1); method call: Time-slicing ensures that all equal-priority threads have a chance to run. The program eventually terminates.
  2. Assume bt.setPriority (Thread.NORM_PRIORITY + 1); method call: The blocking thread will run more often because of its higher priority. But because it blocks periodically, the blocking thread does not cause significant disruption to the calculation and main threads. The program eventually terminates.

Schedule with the yield() method

Many developers prefer the alternative to the setPriority(int priority) method, Thread's static void yield();, because of its simplicity. When the currently running thread calls Thread.yield ();, the thread scheduler keeps the currently running thread in the runnable state, but (usually) picks another thread of equal priority to be the currently running thread, unless a higher-priority thread has just been made runnable, in which case the higher-priority thread becomes the currently running thread. If you have no higher-priority thread and no other equal-priority threads, the thread scheduler immediately reschedules the thread calling yield() as the currently running thread. Furthermore, when the thread scheduler picks an equal-priority thread, the picked thread might be the thread that called yield()—which means that yield() accomplishes nothing except delay. This behavior typically happens under a time-slicing thread scheduler. Listing 3 demonstrates the yield() method:

Listing 3. YieldDemo.java

// YieldDemo.java
class YieldDemo extends Thread
{
   static boolean finished = false;
   static int sum = 0;
   public static void main (String [] args)
   {
      new YieldDemo ().start ();
      for (int i = 1; i <= 50000; i++)
      {
           sum++;
           if (args.length == 0)
              Thread.yield ();
      }
      finished = true;
   }
   public void run ()
   {
      while (!finished)
         System.out.println ("sum = " + sum);
   }
}

From a logical perspective, YieldDemo's main thread starts a new thread (of the same NORM_PRIORITY priority) that repeatedly outputs the value of instance field sum until the value of instance field finished is true. After starting that thread, the main thread enters a loop that repeatedly increments sum's value. If no arguments pass to YieldDemo on the command line, the main thread calls Thread.yield (); after each increment. Otherwise, no call is made to that method. Once the loop ends, the main thread assigns true to finished, so the other thread will terminate. After that, the main thread terminates.

Now that you know what YieldDemo should accomplish, what kind of behavior can you expect? That answer depends on whether the thread scheduler uses time-slicing and whether calls are made to yield(). We have four scenarios to consider:

  1. No time-slicing and no yield() calls: The main thread runs to completion. The thread scheduler won't schedule the output thread once the main thread exits. Therefore, you see no output.
  2. No time-slicing and yield() calls: After the first yield() call, the output thread runs forever because finished contains false. You should see the same sum value printed repeatedly in an endless loop (because the main thread does not run and increment sum). To counteract this problem, the output thread should also call yield() during each while loop iteration.
  3. Time-slicing and no yield() calls: Both threads have approximately equal amounts of time to run. However, you will probably see very few lines of output because each System.out.println ("sum =" + sum); method call occupies a greater portion of a quantum than a sum++; statement. (Many processor cycles are required to send output to the standard output device, while (relatively) few processor cycles are necessary for incrementing an integer variable.) Because the main thread accomplishes more work by the end of a quantum than the output thread and because that activity brings the program closer to the end, you observe fewer lines of output.
  4. Time-slicing and yield() calls: Because the main thread yields each time it increments sum, the main thread completes less work during a quantum. Because of that, and because the output thread receives additional quantums, you see many more output lines.

Note: Should you call setPriority(int priority) or yield()? Both methods affect threads similarly. However, setPriority(int priority) offers flexibility, whereas yield() offers simplicity. Also, yield() might immediately reschedule the yielding thread, which accomplishes nothing. I prefer setPriority(int priority), but you must make your own choice.

The wait/notify mechanism

As you learned last month, each object's associated lock and waiting area allow the JVM to synchronize access to critical code sections. For example: When thread X tries to acquire a lock before entering a synchronized context guarding a critical code section from concurrent thread access, and thread Y is executing within that context (and holding the lock), the JVM places X in a waiting area. When Y exits the synchronized context (and releases the lock), the JVM removes X from the waiting area, assigns the lock to X, and allows that thread to enter the synchronized context. In addition to its use in synchronization, the waiting area serves a second purpose: it is part of the wait/notify mechanism, the mechanism that coordinates multiple threads' activities.

The idea behind the wait/notify mechanism is this: A thread forces itself to wait for some kind of condition, a prerequisite for continued execution, to exist before it continues. The waiting thread assumes that some other thread will create that condition and then notify the waiting thread to continue execution. Typically, a thread examines the contents of a condition variable—a Boolean variable that determines whether a thread will wait—to confirm that a condition does not exist. If a condition does not exist, the thread waits in an object's waiting area. Later, another thread will set the condition by modifying the condition variable's contents and then notifying the waiting thread that the condition now exists and the waiting thread can continue execution.

Tip:Think of a condition as the reason one thread waits and another thread notifies the waiting thread.

1 2 3 4 Page 2
Page 2 of 4