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.
|
A starvation problem can be hard to spot if you're developing on a VM that uses preemptive thread scheduling. Just because the problem doesn't arise on your machine doesn't mean it won't arise on your customers' machines if their VMs use cooperative thread scheduling. Most current virtual machines use preemptive thread scheduling, but some older virtual machines are cooperatively scheduled. | |
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.
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.
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.
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.
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. We can use join( ) to fix up Example 5-4. Example 5-4s problem was that the main( ) method tended to outpace the threads whose results the main( ) method was using. It's straightforward to fix this by joining to each thread before trying to use its result. Example 5-13 demonstrates.
Example 5-13. Avoid a race condition by joining to the thread that has a result you need
import java.io.*;
public class JoinDigestUserInterface {
public static void main(String[] args) {
ReturnDigest[] digestThreads = new ReturnDigest[args.length];
for (int i = 0; i < args.length; i++) {
// Calculate the digest
File f = new File(args[i]);
digestThreads[i] = new ReturnDigest(f);
digestThreads[i].start( );
}
for (int i = 0; i < args.length; i++) {
try { digestThreads[i].join( );
// Now print the result
StringBuffer result = new StringBuffer(args[i]);
result.append(": ");
byte[] digest = digestThreads[i].getDigest( );
for (int j = 0; j < digest.length; j++) {
result.append(digest[j] + " ");
} System.out.println(result);
}
catch (InterruptedException ex) {
System.err.println("Thread Interrupted before completion");
} } }
}
Since Example 5-13 joins to threads in the same order as the threads are started, this fix also has the side effect of printing the output in the same order as the arguments used to construct the threads, rather than in the order the threads finish. This modification doesn't make the program any slower, but it may occasionally be an issue if you want to get the output of a thread as soon as it's done, without waiting for other unrelated threads to finish first.
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( )
These must be invoked on the object the thread was waiting on, not generally on the Thread itself. Before notifying an object, a thread must first obtain the lock on the object using a synchronized method or block. The notify( ) method selects one thread more or less at random from the list of threads waiting on the object and wakes it up. The notifyAll() method wakes up every thread waiting on the given object. Once a waiting thread is notified, it attempts to regain the lock of the object it was waiting on. If it succeeds, execution resumes with the statement immediately following the invocation of wait(). If it fails, it blocks on the object until its lock becomes available; then execution resumes with the statement immediately following the invocation of wait( ). For example, suppose one thread is reading a JAR archive from a network connection. The first entry in the archive is the manifest file. Another thread might be interested in the contents of the manifest file even before the rest of the archive is available. The interested thread could create a custom ManifestFile object, pass a reference to this object to the thread that would read the JAR archive, and wait on it. The thread reading the archive would first fill the ManifestFile with entries from the stream, then notify the ManifestFile, then continue reading the rest of the JAR archive. When the reader thread notified the ManifestFile, the original thread would wake up and do whatever it planned to do with the now fully prepared ManifestFile object. The first thread works something like this:
ManifestFile m = new ManifestFile( );
JarThread t = new JarThread(m, in);
synchronized (m) {
t.start( );
try {
m.wait( );
// work with the manifest file...
}
catch (InterruptedException ex) {
// handle exception...
}
}
The JarThread class works like this:
ManifestFile theManifest;
InputStream in;
public JarThread(Manifest m, InputStream in) {
theManifest = m;
this.in= in;
}
public void run( ) {
synchronized (theManifest) {
// read the manifest from the stream in...
theManifest.notify( );
}
// read the rest of the stream...
}
Waiting and notification are more commonly used when multiple threads want to wait on the same object. For example, one thread may be reading a web server log file in which each line contains one entry to be processed. Each line is placed in a java.util.List as it's read. Several threads wait on the List to process entries as they're added. Every time an entry is added, the waiting threads are notified using the notifyAll() method. If more than one thread is waiting on an object, notifyAll( ) is preferred, since there's no way to select which thread to notify. When all threads waiting on one object are notified, all will wake up and try to get the lock on the object. However, only one can succeed immediately. That one continues; the rest are blocked until the first one releases the lock. If several threads are all waiting on the same object, a significant amount of time may pass before the last one gets its turn at the lock on the object and continues. It's entirely possible that the object on which the thread was waiting will once again have been placed in an unacceptable state during this time. Thus, you'll generally put the call to wait( ) in a loop that checks the current state of the object. Do not assume that just because the thread was notified, the object is now in the correct state. Check it explicitly if you can't guarantee that once the object reaches a correct state it will never again reach an incorrect state. For example, this is how the client threads waiting on the log file entries might look:
private List entries;
public void processEntry( ) {
synchronized (entries) { // must synchronize on the object we wait on
while (entries.size( ) == 0) {
try {
entries.wait( );
// We stopped waiting because entries.size( ) became non-zero
// However we don't know that it's still non-zero so we
// pass through the loop again to test its state now.
}
catch (InterruptedException ex) {
// If interrupted, the last entry has been processed so return;
} }
String entry = (String) entries.remove(entries.size( )-1);
// process this entry...
}
}
The code reading the log file and adding entries to the vector might look something like this:
public void readLogFile( ) {
String entry;
while (true) {
entry = log.getNextEntry( );
if (entry == null) {
// There are no more entries to add to the vector so
// we have to interrupt all threads that are still waiting.
// Otherwise, they'll wait forever.
for (int i = 0; i < threads.length; i++) threads[i].interrupt( );
break;
}
synchronized (entries) {
entries.add(0, entry);
entries.notifyAll( );
}
}
}
Priority-based preemption
Since threads are preemptive between priorities, you do not need to worry about giving up time to higher-priority threads. A high-priority thread will preempt lower-priority threads when it's ready to run. However, when the high-priority thread finishes running or blocks, it generally won't be the same low-priority thread that runs next. Instead, most non-real-time VMs use a round-robin scheduler so that the lower-priority thread that has been waiting longest will run next. For example, suppose there are three threads with priority 5 named A, B, and C running in a cooperatively scheduled virtual machine. None of them will yield or block. Thread A starts running first. It runs for a while and is then preempted by thread D, which has priority 6. A stops running. Eventually, thread D blocks, and the thread scheduler looks for the next highest-priority thread to run. It finds three: A, B, and C. Thread A has already had some time to run, so the thread scheduler picks B (or perhaps C; this doesn't have to go in alphabetical order). B runs for a while when thread D suddenly unblocks. Thread D still has higher priority so the virtual machine pauses thread B and lets D run for a while. Eventually, D blocks again, and the thread scheduler looks for another thread to run. Again, it finds A, B, and C, but at this point, A has had some time and B has had some time, but C hasn't had any. So the thread scheduler picks thread C to run. Thread C runs until it is once again preempted by thread D. When thread D blocks again, the thread scheduler finds three threads ready to run. Of the three, however, A ran the longest ago, so the scheduler picks thread A. From this point forward, every time D preempts and blocks and the scheduler needs a new thread to run, it will run the threads A, B, and C in that order, circling back around to A after C. If you'd rather avoid explicit yielding, you can use a higher-priority thread to force the lower-priority threads to give up time to each other. In essence, you can use a high-priority thread scheduler of your own devising to make all threading preemptive. The trick is to run a high-priority thread that does nothing but sleep and wake up periodically, say every 100 milliseconds. This will split the lower-priority threads into 100-millisecond time slices. It isn't necessary for the thread that's doing the splitting to know anything about the threads it's preempting. It's simply enough that it exists and is running. Example 5-14 demonstrates with a TimeSlicer class that allows you to guarantee preemption of threads with priorities less than a fixed value every timeslice milliseconds.
Example 5-14. A thread that forces preemptive scheduling for lower-priority threads
public class TimeSlicer extends Thread {
private long timeslice;
public TimeSlicer(long milliseconds, int priority) {
this.timeslice = milliseconds;
this.setPriority(priority);
// If this is the last thread left, it should not
// stop the VM from exiting
this.setDaemon(true);
}
// Use maximum priority
public TimeSlicer(long milliseconds) {
this(milliseconds, 10);
}
// Use maximum priority and 100ms timeslices
public TimeSlicer( ) {
this(100, 10);
}
public void run( ) {
while (true) {
try {
Thread.sleep(timeslice);
}
catch (InterruptedException ex) {
}
}
}
}
Finish
The final way a thread can give up control of the CPU in an orderly fashion is by finishing. When the run() method returns, the thread dies and other threads can take over. In network apps, this tends to occur with threads that wrap a single blocking operation, such as downloading a file from a server, so that the rest of the app won't be blocked. Otherwise, if your run( ) method is so simple that it always finishes quickly enough without blocking, there's a very real question of whether you should spawn a thread at all. There's a nontrivial amount of overhead for the virtual machine in setting up and tearing down threads. If a thread is finishing in a small fraction of a second anyway, chances are it would finish even faster if you used a simple method call rather than a separate thread.