Java Network Programming (3rd ed) [Electronic resources] نسخه متنی

5.5 Thread Scheduling

When multiple threads are running at
the same time (more properly, when multiple threads are available to
be run at the same time), you have to consider issues of thread
scheduling. You need to make sure that all important threads get at
least some time to run and that the more important threads get more
time. Furthermore, you want to ensure that the threads execute in a
reasonable order. If your web server has 10 queued requests, each of
which requires 5 seconds to process, you don't want
to process them in series. If you do, the first request will finish
in 5 seconds but the second will take 10, the third 15, and so on
until the last request, which will have to wait almost a minute to be
serviced. By that point, the user has likely gone to another page. By
running threads in parallel, you might be able to process all 10
requests in only 10 seconds total. The reason this strategy works is
that there's a lot of dead time in servicing a
typical web request, time in which the thread is simply waiting for
the network to catch up with the CPUtime the
VM's thread scheduler can put to good use by other
threads. However, CPU-bound threads (as opposed to the I/O-bound
threads more common in network programs) may never reach a point
where they have to wait for more input. It is possible for such a
thread to starve all other threads by taking all the available CPU
resources. With a little thought, you can avoid this problem. In
fact, starvation is a considerably easier problem to avoid than
either mis-synchronization or deadlock.

5.5.1 Priorities

Not
all threads are created equal. Each thread has a priority, specified
as an integer from 1 to 10. When multiple threads are able to run,
the VM will generally run only the highest-priority thread, although
that's not a hard-and-fast rule. In Java, 10 is the
highest priority and 1 is the lowest. The default priority is 5, and
this is the priority that your threads will have unless you
deliberately set them otherwise.

This is exact opposite of the normal Unix way of prioritizing processes, in which the higher the priority number of a process, the less CPU time the process gets.

These three priorities (1, 5, and 10) are often specified as the
three named constants Thread.MIN_PRIORITY,
Thread.NORM_PRIORITY, and
Thread.MAX_PRIORITY:

public static final int MIN_PRIORITY  = 1;
public static final int NORM_PRIORITY = 5;
public static final int MAX_PRIORITY  = 10;

Sometimes you want to give one thread more time than another. Threads
that interact with the user should get very high priorities so that
perceived responsiveness will be very quick. On the other hand,
threads that calculate in the background should get low priorities.
Tasks that will complete quickly should have high priorities. Tasks
that take a long time should have low priorities so that they
won't get in the way of other tasks. The priority of
a thread can be changed using the setPriority( )
method:

public final void setPriority(int newPriority)

Attempting to exceed the maximum priority or set a nonpositive
priority throws an IllegalArgumentException.

The getPriority( ) method returns the current
priority of the thread:

public final int getPriority( )

For instance, in Example 5-11, you might want to give higher
priorities to the threads that do the calculating than the main
program that spawns the threads. This is easily achieved by changing
the calculateDigest( ) method to set the priority
of each spawned thread to 8:

  public void calculateDigest( ) {
ListCallbackDigest cb = new ListCallbackDigest(input);
cb.addDigestListener(this);
Thread t = new Thread(cb);
t.setPriority(8);
t.start( ); 
}

In general, though, try to avoid using too high a priority for
threads, since you run the risk of starving other, lower-priority
threads.

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.

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.

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.

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.

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( )

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( );
}
}
}

5.5.2.6 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) {
}
}
}
}

5.5.2.7 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 applications, 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 application
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.