5.5.2 Preemption

Every virtual machine has a thread scheduler that determines which thread to run at any given time. There are two kinds of thread scheduling: preemptive and cooperative. A preemptive thread scheduler determines when a thread has had its fair share of CPU time, pauses that thread, and then hands off control of the CPU to a different thread. A cooperative thread scheduler waits for the running thread to pause itself before handing off control of the CPU to a different thread. A virtual machine that uses cooperative thread scheduling is much more susceptible to thread starvation than a virtual machine that uses preemptive thread scheduling, since one high-priority, uncooperative thread can hog an entire CPU.

All Java virtual machines are guaranteed to use preemptive thread scheduling between priorities. That is, if a lower-priority thread is running when a higher-priority thread becomes able to run, the virtual machine will sooner or later (and probably sooner) pause the lower-priority thread to allow the higher-priority thread to run. The higher-priority thread preempts the lower-priority thread.

The situation when multiple threads of the same priority are able to run is trickier. A preemptive thread scheduler will occasionally pause one of the threads to allow the next one in line to get some CPU time. However, a cooperative thread scheduler will not. It will wait for the running thread to explicitly give up control or come to a stopping point. If the running thread never gives up control and never comes to a stopping point and if no higher-priority threads preempt the running thread, all other threads will starve. This is a bad thing. It's important to make sure all your threads periodically pause themselves so that other threads have an opportunity to run.

There are 10 ways a thread can pause in favor of other threads or indicate that it is ready to pause. These are:

• It can block on I/O.

• It can block on a synchronized object.

• It can yield.

• It can go to sleep.

• It can join another thread.

• It can wait on an object.

• It can finish.

• It can be preempted by a higher-priority thread.

• It can be suspended.

• It can stop.

You should inspect every run( ) method you write to make sure that one of these conditions will occur with reasonable frequency. The last two possibilities are deprecated because they have the potential to leave objects in inconsistent states, so let's look at the other eight ways a thread can be a cooperative citizen of the virtual machine.

5.5.2.1 Blocking

Blocking occurs any time a thread has to stop and wait for a resource it doesn't have. The most common way a thread in a network program will voluntarily give up control of the CPU is by blocking on I/O. Since CPUs are much faster than networks and disks, a network program will often block while waiting for data to arrive from the network or be sent out to the network. Even though it may block for only a few milliseconds, this is enough time for other threads to do significant work.

Threads can also block when they enter a synchronized method or block. If the thread does not already possess the lock for the object being synchronized on and some other thread does possess that lock, the thread will pause until the lock is released. If the lock is never released, the thread is permanently stopped.

Neither blocking on I/O nor blocking on a lock will release any locks the thread already possesses. For I/O blocks, this is not such a big deal, since eventually the I/O will either unblock and the thread will continue or an IOException will be thrown and the thread will then exit the synchronized block or method and release its locks. However, a thread blocking on a lock that it doesn't possess will never give up its own locks. If one thread is waiting for a lock that a second thread owns and the second thread is waiting for a lock that the first thread owns, deadlock results.

5.5.2.2 Yielding

The second way for a thread to give up control is to explicitly yield. A thread does this by invoking the static Thread.yield() method:

public static void yield( )

This signals the virtual machine that it can run another thread if one is ready to run. Some virtual machines, particularly on real-time operating systems, may ignore this hint.

Before yielding, a thread should make sure that it or its associated Runnable object is in a consistent state that can be used by other objects. Yielding does not release any locks the thread holds. Therefore, ideally, a thread should not be synchronized on anything when it yields. If the only other threads waiting to run when a thread yields are blocked because they need the synchronized resources that the yielding thread possesses, then the other threads won't be able to run. Instead, control will return to the only thread that can run, the one that just yielded, which pretty much defeats the purpose of yielding.

Making a thread yield is quite simple in practice. If the thread's run( ) method simply consists of an infinite loop, just put a call to Thread.yield( ) at the end of the loop. For example:

public void run( ) {
while (true) {
// Do the thread's work...
Thread.yield( );
}
}

This gives other threads of the same priority the opportunity to run.

If each iteration of the loop takes a significant amount of time, you may want to intersperse more calls to Thread.yield() in the rest of the code. This precaution should have minimal effect in the event that yielding isn't necessary.

5.5.2.3 Sleeping

Sleeping is a more powerful form of yielding. Whereas yielding indicates only that a thread is willing to pause and let other equal-priority threads have a turn, a thread that goes to sleep will pause whether any other thread is ready to run or not. This gives an opportunity to run not only to other threads of the same priority but also to threads of lower priorities . However, a thread that goes to sleep does hold onto all the locks it's grabbed. Consequently, other threads that need the same locks will be blocked even if the CPU is available. Therefore, try to avoid having threads sleeping inside a synchronized method or block.

Sometimes sleeping is useful even if you don't need to yield to other threads. Putting a thread to sleep for a specified period of time lets you write code that executes once every second, every minute, every 10 minutes, and so forth. For instance, if you wrote a network monitor program that retrieved a page from a web server every five minutes and emailed the webmaster if the server had crashed, you could implement it as a thread that slept for five minutes between retrievals.

A thread goes to sleep by invoking one of two overloaded static Thread.sleep( ) methods. The first takes the number of milliseconds to sleep as an argument. The second takes both the number of milliseconds and the number of nanoseconds:

public static void sleep(long milliseconds) throws InterruptedException
public static void sleep(long milliseconds, int nanoseconds)
throws  InterruptedException

While most modern computer clocks have at least close-to-millisecond accuracy, nanosecond accuracy is rarer. There's no guarantee that you can actually time the sleep to within a nanosecond or even within a millisecond on any particular virtual machine. If the local hardware can't support that level of accuracy, the sleep time is simply rounded to the nearest value that can be measured. For example:

public void run( ) {
while (true) {
if (!getPage("http://www.cafeaulait.org/")) {
mailError("elharo@metalab.unc.edu");
}
try {
Thread.sleep(300000); // 300,000 milliseconds == 5 minutes
}
catch (InterruptedException ex) {
break;
}
}
}

The thread is not absolutely guaranteed to sleep as long as it wants to. On occasion, the thread may not be woken up until some time after its requested wake-up call, simply because the VM is busy doing other things. It is also possible that some other thread will do something to wake up the sleeping thread before its time. Generally, this is accomplished by invoking the sleeping thread's interrupt( ) method.

public void interrupt( )

This is one of those cases where the distinction between the thread and the Thread object is important. Just because the thread is sleeping doesn't mean that other threads that are awake can't work with the corresponding Thread object through its methods and fields. In particular, another thread can invoke the sleeping Thread object's interrupt( ) method, which the sleeping thread experiences as an InterruptedException. From that point forward, the thread is awake and executes as normal, at least until it goes to sleep again. In the previous example, an InterruptedException is used to terminate a thread that would otherwise run forever. When the InterruptedException is thrown, the infinite loop is broken, the run( ) method finishes, and the thread dies. The user interface thread can invoke this thread's interrupt( ) method when the user selects Exit from a menu or otherwise indicates that he wants the program to quit.

5.5.2.4 Joining threads

It's not uncommon for one thread to need the result of another thread. For example, a web browser loading an HTML page in one thread might spawn a separate thread to retrieve every image embedded in the page. If the IMG elements don't have HEIGHT and WIDTH attributes, the main thread might have to wait for all the images to load before it can finish by displaying the page. Java provides three join( ) methods to allow one thread to wait for another thread to finish before continuing. These are:

public final void join( ) throws InterruptedException
public final void join(long milliseconds) throws InterruptedException
public final void join(long milliseconds, int nanoseconds)
throws InterruptedException

The first variant waits indefinitely for the joined thread to finish. The second two variants wait for the specified amount of time, after which they continue even if the joined thread has not finished. As with the sleep() method, nanosecond accuracy is not guaranteed.

The joining thread (that is, the one that invokes the join() method) waits for the joined thread (that is, the one whose join( ) method is invoked) to finish. For instance, consider this code fragment. We want to find the minimum, maximum, and median of a random array of doubles. It's quicker to do this with a sorted array. We spawn a new thread to sort the array, then join to that thread to await its results. Only when it's done do we read out the desired values.

double[] array = new double[10000];                         // 1
for (int i = 0; i < array.length; i++) {                  // 2
array[i] = Math.random( );                                // 3
}                                                           // 4
SortThread t = new SortThread(array);                       // 5
t.start( );                                                 // 6
try {                                                       // 7
t.join( );                                                // 8
System.out.println("Minimum: " + array[0]);               // 9
System.out.println("Median: " + array[array.length/2]);   // 10
System.out.println("Maximum: " + array[array.length-1]);  // 11
}                                                           // 12
catch (InterruptedException ex) {                           // 13
}                                                           // 14

First lines 1 through 4 execute, filling the array with random numbers. Then line 5 creates a new SortThread. Line 6 starts the thread that will sort the array. Before we can find the minimum, median, and maximum of the array, we need to wait for the sorting thread to finish. Therefore, line 8 joins the current thread to the sorting thread. At this point, the thread executing these lines of code stops in its tracks. It waits for the sorting thread to finish running. The minimum, median, and maximum are not retrieved in lines 9 through 10 until the sorting thread has finished running and died. Notice that at no point is there a reference to the thread that pauses. It's not the Thread object on which the join() method is invoked; it's not passed as an argument to that method. It exists implicitly only as the current thread. If this is within the normal flow of control of the main( ) method of the program, there may not be any Thread variable anywhere that points to this thread.

A thread that's joined to another thread can be interrupted just like a sleeping thread if some other thread invokes its interrupt( ) method. The thread experiences this invocation as an InterruptedException. From that point forward, it executes as normal, starting from the catch block that caught the exception. In the preceding example, if the thread is interrupted, it skips over the calculation of the minimum, median, and maximum because they won't be available if the sorting thread was interrupted before it could finish.

5.5.2.5 Waiting on an object

A thread can wait on an object it has locked. While waiting, it releases the lock on the object and pauses until it is notified by some other thread. Another thread changes the object in some way, notifies the thread waiting on that object, and then continues. This differs from joining in that neither the waiting nor the notifying thread has to finish before the other thread can continue. Waiting is used to pause execution until an object or resource reaches a certain state. Joining is used to pause execution until a thread finishes.

Waiting on an object is one of the lesser-known ways a thread can pause. That's because it doesn't involve any methods in the Thread class. Instead, to wait on a particular object, the thread that wants to pause must first obtain the lock on the object using synchronized and then invoke one of the object's three overloaded wait( ) methods:

public final void wait( ) throws InterruptedException 

public final void wait(long milliseconds) throws InterruptedException 

public final void wait(long milliseconds, int nanoseconds) 

throws InterruptedException

These methods are not in the Thread class; rather, they are in the java.lang.Object class. Consequently, they can be invoked on any object of any class. When one of these methods is invoked, the thread that invoked it releases the lock on the object it's waiting on (though not any locks it possesses on other objects) and goes to sleep. It remains asleep until one of three things happens:

• The timeout expires.

• The thread is interrupted.

• The object is notified.

The timeout is the same as for the sleep( ) and join( ) methods; that is, the thread wakes up after the specified amount of time has passed (within the limits of the local hardware clock accuracy). When the timeout expires, execution of the thread resumes with the statement immediately following the invocation of wait(). However, if the thread can't immediately regain the lock on the object it was waiting on, it may still be blocked for some time.

Interruption works the same way as sleep( ) and join( ): some other thread invokes the thread's interrupt( ) method. This causes an InterruptedException, and execution resumes in the catch block that catches the exception. The thread regains the lock on the object it was waiting on before the exception is thrown, however, so the thread may still be blocked for some time after the interrupt( ) method is invoked.

The third possibility, notification, is new. Notification occurs when some other thread invokes the notify( ) or notifyAll( ) method on the object on which the thread is waiting. Both of these methods are in the java.lang.Object class:

public final void notify( )
public final void notifyAll( )