Before reading this chapter, you should be familiar with how to program
using Java threads-how to implement Runnable and subclass Thread, how to
start and stop threads, and how to wait for a thread to end. If you need an
introduction to Java threads, take time now to read through Chapter
6, "Effective Use of Threads."
When you begin exploring Java's multithreading capabilities, you will
discover that there is more to learn about concurrency than knowing how to use
the Thread
class API. Some of the questions you might encounter include:
This chapter takes a detailed look at concurrent programming in Java. It
covers the essential information you need in order to write thread-safe
classes: why thread-safety is an issue and how to use the synchronized
keyword to enforce one-at-a-time access to an object. The chapter then
elaborates on monitors, the concept behind Java's implementation of concurrent
programming. This is followed up with a section on how to use monitors to
coordinate the activities of your threads. As the theme of this book implies,
special tips, techniques and pitfalls are discussed throughout this chapter.
Note |
Concurrent programming
is at first an unfamiliar concept for most Java programmers, a concept that
requires a period of adjustment. The transition from nonconcurrent
programming to concurrent programming is similar in many ways to the
transition from writing procedural programs to writing object-oriented
programs: difficult, frustrating at times, but in the end rewarding. If at
first you do not understand the material in this chapter, give the material
time to sink in-try running the examples on your own computer. |
One of the most powerful features of the Java programming language is the
ability to run multiple threads of control. Performing multiple tasks at the
same time seems natural from the human perspective-for example, simultaneously
downloading a file from the Internet, performing a spreadsheet recalculation,
or printing a document. From a programmer's point of view, however, managing
concurrency is not as natural as it seems. Concurrency requires the programmer
to take special precautions to ensure that Java objects are accessed in a
thread-safe manner.
"What is unsafe about running multiple threads?" There is
nothing obvious about threads that makes threaded programs unsafe;
nevertheless, threaded programs can be subject to hazardous situations unless
you take appropriate measures to make them safe.
The following is an example of how a threaded program may be unsafe:
public class Counter {
private int count = 0;
public int incr() {
int n = count;
count = n + 1;
return n;
}
}
As Java classes go, the Counter
class is simple, having only one attribute and one method. As its name implies,
the Counter
class is used to count things, such as the number of times a button is pressed
or the number of times the user visits a particular Web site. The incr() method is
the heart of the class, returning and incrementing the current value of the
counter. However, The incr()
method has a problem; it is a potential source of unpredictable behavior in a
multithreaded environment.
Consider a situation in which a Java program has two runnable threads, both
of which are about to execute this line of code (affecting the same Counter object):
int cnt = counter.incr();
The programmer is not able to predict nor control the order in which these
two threads are run. The operating system (or Java virtual machine) has full
authority over thread scheduling. Consequently, there are no guarantees about
which thread will receive CPU time, when the threads will execute, or how long
each thread will be allowed to execute. Either thread may be interrupted by a
context switch to a different thread at any time. Alternately, both threads may
run concurrently on separate processors of a multiprocessor machine.
Table 7.1 describes one possible sequence of execution of the two threads.
In this scenario, the first thread is allowed to run until it completes its
call to counter.incr();
then the second thread does the same. There are no surprises in this scenario.
The first thread increments the Counter value to 1, and the second thread increments the
value to 2.
Table 7.1. Counter
Scenario One.
Thread 1 |
Thread 2 |
Count |
cnt
= counter.incr(); |
--- |
0 |
n
= count; // 0 |
--- |
0 |
count
= n + 1; // 1 |
--- |
1 |
return
n; // 0 |
--- |
1 |
--- |
cnt
= counter.incr(); |
1 |
--- |
n
= count; // 1 |
1 |
--- |
count
= n + 1; // 2 |
2 |
--- |
return
n; // 1 |
2 |
Table 7.2 describes a somewhat different sequence of execution. In this
case, the first thread is interrupted by a context switch during execution of
the incr()
method. The first thread remains temporarily suspended, and the second thread
is allowed to proceed. The second thread executes its call to the incr() method,
incrementing the Counter
value to 1.
When the first thread resumes, a problem becomes evident. The Counter's value
is not updated to the value 2,
as you would expect, but is instead set again to the value 1.
Table 7.2. Counter
Scenario Two.
Thread 1 |
Thread 2 |
Count |
cnt
= counter.incr(); |
--- |
0 |
n
= count; // 0 |
--- |
0 |
--- |
cnt
= counter.incr(); |
0 |
--- |
n
= count; // 0 |
0 |
--- |
count
= n + 1; // 1 |
1 |
--- |
return
n; // 0 |
1 |
count
= n + 1; // 1 |
--- |
1 |
return
n; // 0 |
--- |
1 |
By examining Thread 1 in Table 7.2, you will see an interesting sequence of
operations. Upon entering the incr() method, the value of the count attribute
(0) is
stored in a local variable, n.
The thread is then suspended for a period of time while a different thread
executes. (It is important to note that the count attribute is modified by the
second thread during this time.) When Thread 1 resumes, it stores the value n + 1 (1) back to the count attribute.
Unfortunately, this is no longer a correct value for the counter, as the
counter was already incremented to 1 by Thread 2.
The problem outlined by the scenario in Table 7.2 is called a race
condition-the outcome of the program was affected by the order in which the
program's threads were allocated CPU time. It is usually considered
inappropriate to allow race conditions to affect the results of a program.
Consider a medical device that monitors a patient's blood pressure. If this
device were affected by race conditions in its software, it might report an
incorrect reading to the physician. The physician would be basing medical
decisions on incorrect patient information-a bad situation for the patient,
doctor, insurance company, and software vendor!
All multithreaded programs, even Java programs, can suffer from race
conditions. Fortunately, Java provides the programmer with the necessary tools
to manage concurrency-monitors.
Many texts on computer science and operating systems deal with the issue of
concurrent programming. Concurrency has been the subject of much research over
the years, and many concurrency control solutions have been proposed and
implemented. These solutions include:
Java implements a variant of the monitor approach to concurrency.
The concept of a monitor was introduced by C.A.R. Hoare in a 1974
paper published in the Communications of the ACM. Hoare described a
special-purpose object, called a monitor, which applies the principle of mutual
exclusion to groups of procedures (mutual exclusion is a fancy way of
saying "one thread at a time"). In Hoare's model, each group of
procedures requiring mutual exclusion is placed under the control of a monitor.
At runtime, the monitor allows only one thread at a time to execute a procedure
controlled by the monitor. If another thread tries to call a procedure
controlled by the monitor, that thread is suspended until the first thread
completes its call.
Java monitors remain true to Hoare's original concepts, with a few minor
variations (which will not be discussed here). Monitors in Java enforce
mutually exclusive access to methods, or more specifically, mutually exclusive
access to synchronized
methods.
When a Java synchronized
method is invoked, a complicated process begins. First, the virtual machine
locates the monitor associated with the object on which the method is being
invoked (for example, if you are calling obj.method(), the VM finds obj's monitor).
Every Java object can have an associated monitor, although for
performance reasons, the 1.0 VM creates and caches monitors only when
necessary. Once the monitor is located, the VM attempts to assign ownership of
the monitor to the thread invoking the synchronized method. If the monitor is unowned,
ownership is assigned to the calling thread, which is then allowed to proceed
with the method call. However, if the monitor is already owned by another
thread, the monitor cannot be assigned to the calling thread. The calling
thread will be put on hold until the monitor becomes available. When assignment
of the monitor becomes possible, the calling thread is assigned ownership and
will then proceed with the method call.
Metaphorically, a Java monitor acts as an object's gatekeeper. When a synchronized
method is called, the gatekeeper allows the calling thread to pass and then
closes the gate. While the thread is still in the synchronized method, subsequent synchronized
method calls on that object from other threads are blocked. Those threads line
up outside the gate, waiting for the first thread to leave. When the first
thread exits the synchronized
method, the gatekeeper opens the gate, allowing a single waiting thread to
proceed with its synchronized
method call. The process repeats.
In plain English, a Java monitor enforces a one-at-a-time approach to
concurrency. This is also known as serialization (not to be confused
with "object serialization", the Java library for reading and writing
objects on a stream).
Note |
Programmers already familiar
with multithreaded programming in a different language often confuse monitors
with critical sections. Java monitors are not like traditional critical sections.
Declaring a method synchronized
does not imply that only one thread may execute that method at a time, as
would be the case with a critical section. It implies that only one thread
may invoke that method (or any synchronized method) on a particular object at any
given time. Java monitors are associated with objects, not with blocks of
code. Two threads may concurrently execute the same synchronized method,
provided that the method is invoked on different objects (that is, a.method() and
b.method(),
where a != b).
|
To demonstrate how monitors operate, let's rewrite the Counter example
to take advantage of monitors, using the synchronized keyword:
public class Counter2 {
private int count = 0;
public synchronized int incr() {
int n = count;
count = n + 1;
return n;
}
}
Note that the incr()
method has not been rewritten-the method is identical to its previous listing
of the Counter
class, except that the incr()
method has been declared synchronized.
What would happen if this new Counter2 class were used in the scenario presented
in Table 7.2 (the race condition)? The outcome of the same sequence of context
switches would not be the same-having a synchronized method prevents the race
condition. The revised scenario is listed in Table 7.3.
Table 7.3. Counter
Scenario Two, revised.
Thread 1 |
Thread 2 |
Count |
cnt
= counter.incr(); |
--- |
0 |
(acquires
the monitor) |
--- |
0 |
n
= count; // 0 |
--- |
0 |
--- |
cnt
= counter.incr(); |
0 |
--- |
(can't
acquire monitor) |
0 |
count
= n + 1; // 1 |
---(blocked)
|
1 |
return
n; // 0 |
---(blocked)
|
1 |
(releases
the monitor) |
---(blocked)
|
1 |
--- |
(acquires
the monitor) |
1 |
--- |
n
= count; // 1 |
1 |
--- |
count
= n + 1; // 2 |
2 |
--- |
return
n; // 1 |
2 |
--- |
(releases
the monitor) |
2 |
In Table 7.3, the sequence of operations begins the same as the earlier
scenario. Thread 1 starts executing the incr() method of the Counter2 object,
but it is interrupted by a context switch. In this example, however, when
Thread 2 attempts to execute the incr() method on the same Counter2 object,
the thread is blocked. Thread 2 is unable to acquire ownership of the counter
object's monitor; the monitor is already owned by Thread 1. Thread 2 is
suspended until the monitor becomes available. When Thread 1 releases the
monitor, Thread 2 is able to acquire the monitor and continue running,
completing its call to the method.
The synchronized
keyword is Java's single solution to the concurrency control problem. As
you saw in the Counter
example, the potential race condition was eliminated by adding the synchronized
modifier to the incr()
method. All accesses to the incr()
method of a counter were serialized by the addition of the synchronized
keyword. Generally speaking, the synchronized modifier should be applied to any
method that modifies an object's attributes. It would be a very difficult task
to examine a class's methods by visually scanning for thread-safety problems.
It is much easier to mark all object-modifying methods as synchronized and
be done with it.
Note |
You might be wondering when
you will see an actual monitor object. Anecdotal information has been
presented about monitors, but you probably want to see some official
documentation about what a monitor is and how you access it. Unfortunately,
that is not possible. Java monitors have no official standing in the language
specification, and their implementation is not directly visible to the
programmer. Monitors are not Java objects-they have no attributes or methods.
Monitors are a concept beneath Java's implementation of threading and
concurrency. It may be possible to access a Java monitor at the native code
level, but this is not recommended (and it is beyond the scope of this
chapter). |
Java monitors are used only in conjunction with the synchronized
keyword. Methods that are not declared synchronized do not attempt to acquire
ownership of an object's monitor before executing-they ignore monitors
entirely. At any given moment, one thread (at most) may be executing a synchronized
method on an object, but an arbitrary number of threads may be executing non-synchronized
methods. This can lead to some surprising situations if you are not careful in
deciding which methods need to be synchronized. Consider the following Account class:
class Account {
private int balance;
public Account(int balance) {
this.balance = balance;
}
public synchronized void transfer(int amount, Account
destination) {
this.withdraw(amount);
Thread.yield(); // force a
context switch
destination.deposit(amount);
}
public synchronized void withdraw(int amount) {
if (amount > balance) {
throw new RuntimeException("No
overdraft protection!");
}
balance -= amount;
}
public synchronized void deposit(int amount) {
balance += amount;
}
public int getBalance() {
return balance;
}
}
The attribute-modifying methods of the Account class are declared synchronized. It
appears that this class has no problem with race conditions, but it does!
To understand the race condition the Account class is subject to, consider how
a bank deals with accounts. To a bank, the correctness of its accounts is of
the utmost importance-a bank that makes accounting errors or reports incorrect
information would not have happy customers. In order to avoid reporting
incorrect information, a bank would likely disable "inquiries" on an
account while a transaction involving the account is in progress. This prevents
the customer from viewing a partially complete transaction. The Account class getBalance()
method is not synchronized,
and this can lead to some problems.
Consider two Account
objects, and two different threads are performing actions on these accounts.
One thread is performing a balance transfer from one account to the other. The
second thread is performing a balance inquiry. This code demonstrates the
suggested activity:
public class XferTest implements Runnable {
public static void main(String[] args) {
XferTest xfer = new XferTest();
xfer.a = new Account(100);
xfer.b = new Account(100);
xfer.amount = 50;
Thread t = new Thread(xfer);
t.start();
Thread.yield(); // force a
context switch
System.out.println("Inquiry: Account a has :
$" + xfer.a.getBalance());
System.out.println("Inquiry: Account b has :
$" + xfer.b.getBalance());
}
public Account a = null;
public Account b = null;
public int amount = 0;
public void run() {
System.out.println("Before xfer: a has :
$" + a.getBalance());
System.out.println("Before xfer: b has :
$" + b.getBalance());
a.transfer(amount, b);
System.out.println("After xfer: a has :
$" + a.getBalance());
System.out.println("After xfer: b has :
$" + b.getis assigned to the higher priority thread. However, the Win32
1.0 virtual machine uses the Win32 thread scheduling algorithms.
In the 1.0
virtual machine, it is not possible to specify an order for assigning ownership
of a monitor when multiple threads are waiting. You should avoid writing code
that depends on this kind of ordering.
It is not
possible to use synchronized methods on some types of objects. Java
arrays, for instance, can declare no methods at all, much less synchronized
methods. To get around this restriction, Java has a second syntactic convention
that enables you to interact with an object's monitor. The synchronized
statement is defined to have the following syntax:
synchronized ( Expression ) Statement
Executing a synchronized
statement has the same effect as calling a synchronized method-a monitor's
ownership will be acquired before the block of code is executed. In the case of
a synchronized statement, the object whose monitor is up for grabs is
the object resulting from Expression (which must be an object type, not
an elemental type).
One of the
most important uses of the synchronized statement involves serializing
access to array objects. The following example demonstrates how to use the synchronized
statement to provide thread-safe access to an array:
void safe_lshift(byte[] array, int
count) {
synchronized(array) {
System.arraycopy(array,
count, array, 0, array.size - count);
}
}
Prior to
modifying the array in this example, the virtual machine assigns ownership of array's
monitor to the executing thread. Other threads trying to acquire array's
monitor will be forced to wait until the array copy has been completed. Of
course, accesses to the array that are not guarded by a synchronized
statement will not be blocked, so be careful.
The synchronized
statement is also useful when modifying an object without going through synchronized
methods. This situation can arise if you modify an object's public attributes
or call a method that is not declared synchronized (but should be).
Here's an example:
void call_method(SomeClass obj) {
synchronized(obj) {
obj.method_that_should_be_synchronized_but_isnt();
}
}
Note |
The synchronized statement
makes it possible to use monitors with all Java objects. However, code may be
confusing if the synchronized
statement is used where a synchronized
method would have sufficed. Adding the synchronized modifier at the method
level broadcasts exactly what happens when the method is called. |
Exceptions
create a special problem for monitors. The Java virtual machine must handle
monitors very carefully in the presence of exceptions. Consider the following
code:
public synchronized void foo() throws
Exception {
...
throw new Exception();
....
}
While inside
the method, the thread executing foo() owns the monitor (which should
be released when the method exits normally). If foo()ONT>
exits because an exception is thrown, what happens to the monitor? Is the
monitor released, or does the abnormal exit of this method cause the monitor
ownership to be retained?
The Java virtual machine has
the responsibility of unwinding the thread's stack as it passes an exception up
the stack. Unwinding the stack involves cleanup at each stack frame, to
include releasing any monitors held in that stack frame. If you find a
situation where this is not the case, please report that situation to Sun!
There is debate within the
Java community about the potential danger of declaring attributes to be public. When
concurrency is considered, it becomes apparent that public attributes can lead to
thread-unsafe code. Here's why: public attributes can be accessed by any thread
without the benefit of protection by a synchronized method. When you declare an
attribute public,
you are relinquishing control over updates to that attribute, and any
programmer using your code has a license to access (and update) public
attributes directly.
Note |
Java programmers frequently
define immutable symbolic constants as public final class attributes.
Attributes declared this way do not have thread-safety issues (race
conditions involve only objects whose value is not constant). |
In general, it is not a good
idea to declare (non-final)
attributes to be public.
Not only can it introduce thread-safety problems, but it can make your code
difficult to modify and support as time goes by.
By now, you should be able to
write thread-safe code using the synchronized keyword. When should you really use synchronized?
Are there situations when you should not use synchronized? Are there drawbacks to
using synchronized?
The most common reason
developers don't use synchronized
is that they write single-threaded, single-purpose code. For example, CPU-bound
tasks do not benefit much from multithreading. A compiler does not perform much
better if it is threaded. The Java compiler from Sun does not contain many synchronized
methods. For the most part, it assumes that it is executing in its own thread
of control, without having to share its resources with other threads.
Another common reason for
avoiding synchronized
methods is that they do not perform as well as non-synchronized methods. In simple
tests, synchronized
methods have been shown to be three to four times slower than their non-synchronized
counterparts (in the 1.0.1 JDK from Sun). This doesn't mean your entire
application will be three or four times slower, but it is a performance issue
none the less. Some programs demand that every ounce of performance be squeezed
out of the runtime system. In this situation, it might be appropriate to avoid
the performance overhead associated with synchronized methods.
Although Java is currently
not suitable for real-time software development, another possible reason to
avoid using synchronized
methods is to prevent nondeterministic blocking situations. If multiple threads
compete for the same resource, one or more threads may be unable to execute for
an excessive amount of time. Although this is acceptable for most types of
applications, it is not acceptable for applications that must respond to events
within real-time constraints.
Sometimes referred to as a deadly
embrace, a deadlock is one of the worst situations that can happen
in a multithreaded environment. Java programs are not immune to deadlocks, and
programmers must take care to avoid them.
A deadlock is a situation
that causes two or more threads to hang, unable to proceed. In the
simplest case, you have two threads, each trying to acquire a monitor already
owned by the other thread. Each thread goes to sleep, waiting for the desired
monitor to become available, but it will never become available. The first
thread waits for the monitor owned by the second thread, and the second thread
waits for the monitor owned by the first thread. Because each thread is
waiting, each will never release its monitor to the other thread.
This sample application
should give you an understanding of how a deadlock happens:
public class Deadlock implements Runnable {
public static void main(String[] args) {
Deadlock d1 = new
Deadlock();
Deadlock d2 = new
Deadlock();
Thread t1 = new Thread(d1);
Thread t2 = new Thread(d2);
d1.grabIt = d2;
d2.grabIt = d1;
t1.start();
t2.start();
try { t1.join(); t2.join();
} catch(InterruptedException e) { }
System.exit(0);
}
Deadlock grabIt;
public synchronized void run() {
try { Thread.sleep(2000); }
catch(InterruptedException e) { }
grabIt.sync_method();
}
public synchronized void sync_method() {
try { Thread.sleep(2000); }
catch(InterruptedException e) { }
System.out.println("in
sync_method");
}
}
In this class, the main() method
launches two threads, each of which invokes the synchronized run() method on a Deadlock object.
When the first thread wakes up, it attempts to call the sync_method() of
the other Deadlock
object. Obviously, the Deadlock's
monitor is owned by the second thread; so, the first thread begins waiting for
the monitor. When the second thread wakes up, it tries to call the sync_method() of
the first Deadlock
object. Because that Deadlock's
monitor is already owned by the first thread, the second thread begins waiting.
The threads are waiting for each other, and neither will ever wake up.
Note |
If you run the Deadlock
application, you will notice that it never exits. That is understandable;
after all, that is what a Deadlock is. How can you tell what is really going
on inside the virtual machine? There is a trick you can use with the Solaris
JDK to display the status of all threads and monitors: press Ctrl+\ in the
terminal window where the Java application is running. This sends the virtual
machine a signal to dump the state of the VM. Here is a partial listing of
the monitor table dumped several seconds after launching Deadlock: Deadlock@EE300840/EE334C20 (key=0xee300840):
monitor owner: "Thread-5" |
There are numerous algorithms
available for preventing and detecting deadlock situations, but those
algorithms are beyond the scope of this chapter (many database and operating
system texts cover deadlock detection algorithms in detail). Unfortunately, the
Java virtual machine itself does not perform any deadlock detection or
notification. There is nothing that would prevent the virtual machine from
doing so, however, so this could be added to versions of the virtual machine in
the future.
It is worth mentioning that
the volatile
keyword is supported as a variable modifier in Java. The language specification
states that the volatile
qualifier instructs the compiler to generate loads and stores on each access to
the attribute, rather than caching the value in a register. The intent of the volatile keyword
is to provide thread-safe access to an attribute, but the virtual machine falls
short of this goal.
In the 1.0 JDK virtual
machine, the volatile
keyword is ignored. It is unclear whether volatile has been abandoned in favor of
monitors and synchronized
methods or whether the keyword was included solely for C and C++ compatibility.
Regardless, volatile
is useless-use synchronized
methods rather than volatile.
After learning how synchronized
methods are used to make Java programs thread-safe, you might wonder what the
big deal is about monitors. They are just object locks, right? Not true!
Monitors are more than locks; monitors also can be used to coordinate multiple
threads by using the wait()
and notify()
methods available in every Java object.
What is thread
coordination? In a Java program, threads are often interdependent-one
thread may depend on another thread to complete an operation or to service a
request. For example, a spreadsheet program may run an extensive recalculation
as a separate thread. If a user-interface (UI) thread attempts to update the
spreadsheet's display, the UI thread should coordinate with the recalculation
thread, starting the screen update only when the recalculation thread has
successfully completed.
There are many other
situations in which it is useful to coordinate two or more threads. The
following list identifies only some of the possibilities:
·
Shared buffers are often used to communicate
data between threads. In this scenario, there is usually one thread writing to
a shared buffer (the writer) and one thread reading from the buffer (the
reader). When the reader attempts to read from the buffer, it should coordinate
with the writer thread, retrieving data from the shared buffer only after it
has been put there by the writer thread. If the buffer is empty, the reader
waits for the data (without continuously polling!). The writer notifies the
reader thread when it has completed filling the buffer, so that the reader can
continue.
·
If an application must be very responsive to user
input, but needs to perform an intensive numerical analysis occasionally, it is
a good idea to run the numerical analysis in a separate low-priority thread.
Any higher-priority thread that needs to obtain the results of the analysis
waits for the low-priority thread to complete; the low-priority thread should
notify all interested threads when it is done.
·
A thread could be constructed in such a way that it
performs processing only in response to asynchronous events delivered by other
threads. When no events are available, the waiting thread is suspended (a
thread with nothing to do should not consume CPU time). The threads sending
events to the waiting thread should invoke a mechanism to notify the waiting
thread that an event has occurred.
It is no accident that the
previous examples repeatedly use the words "wait" and
"notify." These words express the two concepts central to thread
coordination: a thread waits for some condition event to occur, and you notify
a waiting thread that a condition or event has occurred. The words wait and
notify are also used in Java as the names of the methods you will call to
coordinate threads (wait()
and notify(),
in class Object).
As noted earlier in the
chapter (in the section titled Monitors), every Java object has an associated
monitor. That fact turns out to be useful at this point, because monitors are
also used to implement Java's thread coordination primitives. Although monitors
are not directly visible to the programmer, an API is provided in class Object to enable
you to interact with an object's monitor. This API consists of two methods: wait() and notify().
Threads are usually
coordinated using a concept known as a condition, or condition
variable. A condition is a state or an event that a thread can not
proceed without-the thread must wait for the condition to become true before
continuing. In Java, this pattern is usually expressed:
while ( ! the_condition_I_am_waiting_for ) {
wait();
}
First, you check to see if
the desired condition is already true. If it is true, there is no need to wait.
If the condition is not yet true, then call the wait() method. When wait() ends,
recheck the condition to make sure that it is now true.
Invoking the wait() method on
an object pauses the current thread until a different thread calls notify() on the
object, to inform the waiting thread of a condition change. While stopped
inside wait(),
the thread is considered not runnable, and will not be assigned to a CPU
for execution until it is awakened by a call to notify() from a different thread.
(The notify()
method must be called from a different thread; the waiting thread is not
running, and thus is not capable of calling notify().) A call to notify() will
inform a single waiting thread that a condition of the object has changed,
ending its call to wait().
There are two additional
varieties of the wait()
method. The first version takes a single parameter-a timeout value (in
milliseconds). The second version has two parameters-again, a timeout value (in
milliseconds and nanoseconds). These methods are used when you do not
want to wait indefinitely for an event. If you want to abandon the wait after a
fixed period of time, you should use either of the following:
·
wait(long
milliseconds);
·
wait(long
milliseconds, int nanoseconds);
Unfortunately, these methods
do not provide a means to determine how the wait() was ended-whether a notify()
occurred or whether it timed out. This is not a big problem, however, because
you can recheck the wait condition and the system time to determine which event
has occurred.
Note |
The 1.0 JDK implementation
from JavaSoft does not provide a full implementation for wait(long milliseconds,
int nanoseconds). This method currently rounds the nanoseconds
parameter to the nearest millisecond. JavaSoft has not stated whether they
plan to change the behavior of this method in the future. |
The wait() and notify() methods
must be invoked either within a synchronized method or within a synchronized
statement. This requirement will be discussed in further detail in the section Monitor
Ownership, later in this chapter.
A classic example of thread
coordination used in many computer science texts is the bounded buffer
problem. This problem involves using a fixed-size memory buffer to communicate
between two processes or threads. (In many operating systems, interprocess
communication buffers are allocated with a fixed size and are not allowed to
grow or shrink.) To solve this problem, you must coordinate the reader and
writer threads so that the following are true:
·
The writer thread can continuously write to a buffer
until the buffer becomes full, at which time the writer thread is suspended.
·
When the reader thread removes items from the full
buffer, the writer thread is notified of the buffer's changed condition and is
activated and allowed to resume writing.
·
The reader can continuously read from the buffer until
it becomes empty, at which time the reader thread is suspended.
·
When the writer adds items to the empty buffer, the
reader thread is notified of the buffer's changed condition and is activated
and allowed to resume reading.
The following class listings
demonstrate a Java implementation of the bounded buffer problem. There are
three main classes in this example: the Producer, the Consumer, and
the Buffer.
Let's start with the Producer:
public class Producer implements Runnable {
private Buffer buffer;
public Producer(Buffer b) {
buffer = b;
}
public void run() {
for (int i=0; i<250; i++) {
buffer.put((char)('A'
+ (i%26)));
}
}
}
The Producer class
implements the Runnable
interface (which should give you a hint that it will be used as the main method
in a thread). When the Producer's run() method is invoked, 250 characters are written in
rapid succession to a Buffer.
If the Buffer
is not capable of storing all 250 characters, the Buffer's put() method is
called upon to perform the appropriate thread coordination (which you'll see in
a moment).
The Consumer class
is as simple as the Producer:
public class Consumer implements Runnable {
private Buffer buffer;
public Consumer(Buffer b) {
buffer = b;
}
public void run() {
for (int i=0; i<250;
i++) {
System.out.println(buffer.get());
}
}
}
The Consumer is also
a Runnable.
Its run()
method greedily reads 250 characters from a Buffer. If the Consumer tries
to read characters from an empty Buffer, the Buffer's get() method is responsible for
coordinating with the Consumer
thread acting on the buffer.
The Buffer class has
been mentioned a number of times already. Two of its methods, put(char) and get(), have been
introduced. Here is a listing of the Buffer class in its entirety:
public class Buffer {
private char[] buf; // buffer storage
private int last; // last occupied
position
public Buffer(int sz) {
buf = new char[sz];
last = 0;
}
public boolean isFull() { return (last ==
buf.length); }
public boolean isEmpty() { return (last ==
0); }
public synchronized void put(char c) {
while(isFull()) {
try { wait(); }
catch(InterruptedException e) { }
}
buf[last++] = c;
notify();
}
public synchronized char get() {
while(isEmpty()) {
try { wait(); }
catch(InterruptedException e) { }
}
char c = buf[0];
System.arraycopy(buf, 1,
buf, 0, --last);
notify();
return c;
}
}
Note |
When you first begin using wait() and notify(), you
might notice a contradiction. You've already learned that to call wait() or notify(), you
must first acquire ownership of the object's monitor. If you acquire the
monitor in one thread and then call wait(), how will a different thread
acquire the monitor in order to notify() the first thread? Isn't the monitor still
owned by the first thread while it is wait()ing, preventing the second
thread from acquiring the monitor? The answer to this paradox is
in the implementation of the wait() method; wait() temporarily releases ownership
of the monitor when it is called, and obtains ownership of the monitor again
before it returns. By releasing the monitor, the wait() method allows other
threads to acquire the monitor (and maybe call notify()). |
The Buffer class is
just that-a storage buffer. You can put() items into the buffer (in this
case, characters), and you can get() items out of the buffer.
Note the use of wait() and notify() in
these methods. In the put()
method, a wait()
is performed while the Buffer
is full; no more items can be added to the buffer while it is full. At the end
of the get()
method, the call to notify()
ensures that any thread waiting in the put() method will be activated and
allowed to continue adding an item to the Buffer.
Note |
Java provides two classes that
are similar to the Buffer
class presented in this example. These classes, java.io.PipedOutputStream and java.io.PipedInputStream,
are useful in communicating streams of data between threads. If you unpack
the src.zip
file shipped with the 1.0 JDK, you can examine these classes and see how they
handle interthread coordination. |
The wait() and notify() methods
greatly simplify the task of coordinating multiple threads in a concurrent Java
program. However, in order to make full use of these methods, there are a few
additional details you should understand. The following sections present more
detailed material about thread coordination in Java.
The wait() and notify() methods
have one major restriction that you must observe: you may call these methods
only when the current thread owns the monitor of the object. Most frequently, wait() and notify() are
invoked from within a synchronized
method, as in the following:
public synchronized void method() {
...
while (!condition) {
wait();
}
...
}
In this case, the synchronized
modifier guarantees that the thread invoking the wait() call already owns the
monitor when it calls wait().
If you attempt to call wait() or notify() without
first acquiring ownership of the object's monitor (for example, from a non-synchronized
method), the virtual machine will throw an IllegalMonitorStateException. The
following code example demonstrates what happens when you call wait() without
first acquiring ownership of the monitor:
public class NonOwnerTest {
public static void main(String[] args) {
NonOwnerTest not = new
NonOwnerTest();
not.method();
}
public void method() {
try { wait(); } catch(InterruptedException
e) { }
}
}
If you run this Java
application, the following text is printed to the terminal:
java.lang.IllegalMonitorStateException: current
thread not owner
at
java.lang.Object.wait(Object.java)
at NonOwnerTest.method(NonOwnerTest.java:10)
at
NonOwnerTest.main(NonOwnerTest.java:5)
When you invoke the wait() method on
an object, you must own the object's monitor in order to avoid this exception.
Unfortunately, JavaSoft's
documentation of the wait()
and notify()
methods contains a confusing error with respect to monitor ownership. The 1.0
JDK API documentation for the wait() method-in the Object class-contains a factual
error, stating that "The method wait() can only be called from
within a synchronized
method." (The notify()
and notifyAll() documentation
contain similar misstatements.) The documentation continues with a discussion
of exceptions for the wait()
method: "Throws: IllegalMonitorStateException-If
the current thread is not the owner of the Object's monitor." The former
quotation is incorrect in that it is overly restrictive. The second quotation
is correct. Only monitor ownership is required, not a synchronized
method.
To demonstrate that monitor
ownership is the only requirement for calling wait() and notify(), look at this example
class:
public class NonOwnerTest2 {
public static void main(String[] args) {
NonOwnerTest2 not2 = new
NonOwnerTest2();
not2.syncmethod();
}
public synchronized void syncmethod() {
method();
}
private void method() {
try { wait(10); }
catch(InterruptedException e) { }
}
}
In this example, wait(10); is
invoked within a non-synchronized
method, without any problems at runtime. At startup, main() calls syncmethod() on
a NonOwnerTest2
object, which implicitly assigns ownership of the monitor to the current
thread. syncmethod()
then calls method(),
a non-synchronized
method that performs the wait().
When you run this application, no exception is thrown, and the application exits
after a ten-millisecond wait.
You might argue that the
previous example does not justify nit-picking Java's API documentation. After
all, the example still uses a synchronized method. wait() is called in a method that
is called by a synchronized
method, so the wait()
could be considered to be "within" the synchronized method. But synchronized
methods are not the only way to acquire a monitor in Java, however.
Recall the synchronized(obj)
statement, presented earlier in the chapter. The synchronized() statement can be
used to acquire monitor ownership, just like a synchronized method.
The synchronized()
statement can be useful in some situations related to thread coordination. For
example, let's take a look at a variation of the Counter class, presented earlier
in the chapter. The NotifyCounter
class notifies a waiting thread when the counter reaches a specific value. Here
is the code:
public class NotifyCounter {
private int count = -1;
private int notifyCount = -1;
public synchronized int incr() {
if (++count == notifyCount)
{ notify(); }
return (count);
}
public synchronized void notifyAt(int i) {
notifyCount = i;
}
}
This Counter class
will call notify()
when the counter reaches a programmer-specified value, but the class does not
contain code that calls the wait()
method. How is a thread to be notified? By calling wait() on the NotifyCounter
object itself, as in the following application:
import NotifyCounter;
public class NotifyCounterTest implements Runnable {
public static void main(String[] args) {
NotifyCounterTest nct = new NotifyCounterTest();
nct.counter = new NotifyCounter();
synchronized(nct.counter) {
(new Thread(nct)).start();
nct.counter.notifyAt(25);
try {
nct.counter.wait();
// wait here
System.out.println("NotifyCounter
reached 25");
} catch (InterruptedException e) { }
}
}
private NotifyCounter counter = null;
public void run() {
for (int i=0; i<50; i++) {
int n = counter.incr();
System.out.println("counter:
" + n);
}
}
}
It is possible for multiple
threads to be wait()ing
on the same object. This might happen if multiple threads are waiting for the
same event, or if many threads are competing for a single system resource. For
example, recall the Buffer
class described earlier in this section. The Buffer was operated on by a single Producer and a
single Consumer.
What would happen if there were multiple Producers? If the Buffer filled,
different Producers
might attempt to put()
items into the buffer; both would block inside the put() method, waiting for a Consumer to come
along and free up space in the Buffer.
When you call notify(), there
may be zero, one, or more threads blocked in a wait() on the monitor. If there are no
threads waiting, the call to notify() is a no-op-it will not affect any
other threads. If there is a single thread in wait(), that thread will be notified and
will begin waiting for the monitor to be released by the thread that called notify(). If two
or more threads are in a wait(),
the virtual machine will pick a single waiting thread and will notify that
thread.
How does the virtual machine
pick a waiting thread if multiple threads are wait()ing on the same monitor? As with
threads waiting to enter a synchronized
method, the behavior of the virtual machine is not specified. Current
implementations of the virtual machine, however, are well-defined. The Solaris
1.0 JDK virtual machine will select the highest-priority thread and will notify
that thread. If more than one waiting thread has the same high priority, the
thread that executed wait()
first will be notified. Windows 95 and Windows NT are a little more complicated-the
Win32 system handles the prioritization of the notification.
Although it may be possible
to predict which thread will be notified, this behavior should not be trusted.
JavaSoft has left the behavior unspecified to allow for change in future implementations.
The only behavior you can reliably depend on is that exactly one waiting thread
will be notified when you call notify()-that is, if there are any waiting threads.
In some situations, you may
wish to notify every thread currently wait()ing on an object. The Object API
provides a method to do this: notifyAll(). Whereas the notify() method wakes a single
waiting thread, the notifyAll()
method will wake every thread currently stopped in a wait() on the
object.
When would you want to use notifyAll()? As
an example, consider the java.awt.MediaTracker
class. This class is used to track the status of images that are being loaded
over the network. Multiple threads may wait() on the same MediaTracker
object, waiting for all the images to be loaded. When the MediaTracker
detects that all images have been loaded, notifyAll() is called to inform every
waiting thread that the images have been loaded. notifyAll() is used because the MediaTracker
does not know how many threads are waiting; if notify() were used, some of the waiting
threads might not receive notification that transfer was completed. These
threads would continue waiting, probably hanging the entire applet.
An example presented earlier
in this chapter could also benefit from the use of notifyAll(). The Buffer class
used the notify()
method to send a notification to a single thread waiting on an empty or a full
buffer. There was no guarantee that only a single thread was waiting, however;
multiple threads may have been waiting for the same condition. Here is a
modified version of the Buffer
class (named Buffer2)
that uses notifyAll():
public class Buffer2 {
private char[]
buf; //
storage
private int last =
0; //
last occupied position
private int writers_waiting = 0; // # of threads
waiting in put()
private int readers_waiting = 0; // # of threads
waiting in get()
public Buffer2(int sz) {
buf = new char[sz];
}
public boolean isFull() { return (last ==
buf.length); }
public boolean isEmpty() { return (last ==
0); }
public synchronized void put(char c) {
while(isFull()) {
try
{ writers_waiting++; wait(); }
catch (InterruptedException
e) { }
finally {
writers_waiting--; }
}
buf[last++] = c;
if (readers_waiting > 0)
{
notifyAll();
}
}
public synchronized char get() {
while(isEmpty()) {
try
{ readers_waiting++; wait(); }
catch (InterruptedException
e) { }
finally {
readers_waiting--; }
}
char c = buf[0];
System.arraycopy(buf, 1,
buf, 0, --last);
if (writers_waiting > 0)
{
notifyAll();
}
return c;
}
}
The get() and put() methods
have been made more intelligent. They now check to see whether any notification
is necessary and then use notifyAll()
to broadcast an event to all waiting threads.
Throughout this chapter, the
examples have contained a reference to the exception class InterruptedException.
If you examine the declaration of the wait() methods in Object, you will
see why:
public final void wait() throws InterruptedException
The wait() method
declares that it might throw an InterruptedException. The documentation for wait() states:
"Throws: InterruptedException-Another
thread has interrupted this thread."
What does this mean? A
different thread has interrupted this thread. How? This is not made clear by
the documentation. In fact, this is not made clear by examining the source code
for Object.
The wait()
method does not throw an InterruptedException,
nor does any other code in the 1.0 JDK.
The InterruptedException
is part of JavaSoft's future plan for the language. This exception is intended
to be used by the Thread
method interrupt().
In future versions of the language, it will be possible to throw an InterruptedException
in a different thread by calling the interrupt() method on its Thread object.
If the thread happens to be blocked inside a wait(), the wait() will be ended, and the InterruptedException
will be thrown.
Monitors are the only form of
concurrency control directly available in Java. However, monitors are a
powerful enough concept to enable the expression of other types of concurrency
control in user-defined classes. Mutexes, condition variables, and critical
sections can all be expressed as Java classes-implemented using monitors.
The following is an example
of a Mutex
class, implemented in Java using monitors:
public class Mutex {
private Thread owner = null;
private int wait_count = 0;
public synchronized boolean lock(int millis) throws
InterruptedException {
if (owner ==
Thread.currentThread()) { return true; }
while (owner != null) {
try
{ wait_count++; wait(millis); }
finally {
wait_count--; }
if (millis != 0
&& owner != null) {
return
false; // timed out
}
}
owner =
Thread.currentThread();
return true;
}
public synchronized boolean lock() throws InterruptedException
{
return lock(0);
}
public synchronized void unlock() {
if (owner != Thread.currentThread())
{
throw new
RuntimeException("thread not Mutex owner");
}
owner = null;
if (wait_count > 0) {
notify();
}
}
}
If you are familiar with
mutexes, you undoubtedly see how easily this concept is expressed in Java. It
is an academic exercise (left to the reader) to use this Mutex class to
implement condition variables, critical sections, and so forth.
A lot of information is
presented in this chapter! By now, you probably feel like a concurrency and
synchronization guru. You've learned the following:
·
Why thread-safety can be a problem when programming
with multiple threads
·
How to make classes thread-safe using synchronized
methods and the synchronized
statement
·
Many details about how monitors work in Java (probably
more than you wanted to know!)
·
Some situations when you might not want to use synchronized
methods
·
How Monitors, used in incorrect ways, can cause your
application to freeze-a situation known as a deadlock
·
How to coordinate threads using the wait() and notify() methods
·
When and why to use notifyAll()
· How to implement other forms of concurrency control using Java monitors