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.
| Thread 1 | Thread 2 | |
| cnt = counter.incr(); | ||
| n = count; // 0 | ||
| count = n + 1; // 1 | ||
| return n; // 0 | ||
| cnt = counter.incr(); | ||
| n = count; // 1 | ||
| count = n + 1; // 2 | ||
| return n; // 1 |
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.
| Thread 1 | Thread 2 | |
| cnt = counter.incr(); | ||
| n = count; // 0 | ||
| cnt = counter.incr(); | ||
| n = count; // 0 | ||
| count = n + 1; // 1 | ||
| return n; // 0 | ||
| count = n + 1; // 1 | ||
| return n; // 0 |
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.
| Thread 1 | Thread 2 | |
| cnt = counter.incr(); | ||
| (acquires the monitor) | ||
| n = count; // 0 | ||
| cnt = counter.incr(); | ||
| (can't acquire monitor) | ||
| count = n + 1; // 1 | ---(blocked) | |
| return n; // 0 | ---(blocked) | |
| (releases the monitor) | ---(blocked) | |
| (acquires the monitor) | ||
| n = count; // 1 | ||
| count = n + 1; // 2 | ||
| return n; // 1 | ||
| (releases the monitor) |
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.getBalance());
}
}
In this example, two Accounts are created, each with a $100 balance. A transfer is then initiated to move $50 from one account to the other. The "transfer" is not an operation that should affect the total balance of the two accounts; that is, the sum of the balance of the two accounts should remain constant at $200. If the balance inquiry is performed at just the right time, however, it is possible that the total amount of funds in these accounts could be reported incorrectly. For example, if this program is run using the 1.0 Java Development Kit (JDK) for Solaris, the following output is printed:
Before xfer: a has : $100
Before xfer: b has : $100
Inquiry: Account a has : $50
Inquiry: Account b has : $100
After xfer: a has : $50
After xfer: b has : $150
The Inquiry reports that the first account contains $50 and the second account contains $100. That's not $200! What happened to the other $50? Nothing has "happened" to the money, except that it is in the process of being transferred to the second account when the balance inquiry scans the accounts. The getBalance() method is not synchronized, so there is no problem executing this method on accounts that are involved in the balance transfer. This could leave some customer wondering why the accounts are $50 short.
If the getBalance() method is declared synchronized, the application has a different result. The balance inquiry is blocked until the balance transfer is complete. Here is the modified program's output:
Before xfer: a has : $100
Before xfer: b has : $100
Inquiry: Account a has : $50
Inquiry: Account b has : $150
After xfer: a has : $50
After xfer: b has : $150
Monitors sound pretty simple. You add the synchronized modifier to your methods, and that's all there is to it? Well, not quite. Monitors themselves may be simple, but taken together with the rest of the programming environment, there are many issues you should understand in order to use monitors optimally. This section is dedicated to presenting those tips and techniques you must master to become expert in concurrent Java programming.
Methods that are declared synchronized will attempt to acquire ownership of the target object's monitor. But what about methods that do not have an associated instance (static methods)?
The language specification is fairly clear, if brief, about static synchronized methods. When a static synchronized method is called, the monitor acquired is said to be a per-class monitor-that is, there is one monitor for each class that regulates access to all static methods of that class. Only one static synchronized method in a class may be active at a given moment.
The 1.0 Java virtual machine takes this a step further. The monitor used to regulate access to a class's static synchronized methods is the same monitor that is associated with the java.lang.Class instance of that class. Run the following test to demonstrate this behavior:
public class ClassMonitorTest implements Runnable {
public static void main(String[] args) {
new Thread(new ClassMonitorTest()).start();
static_method();
}
public void run() {
synchronized(getClass()) {
System.out.println("in run()");
try { Thread.sleep(5000); } catch (InterruptedException e) { }
}
}
public static synchronized void static_method() {
System.out.println("in static_method()");
try { Thread.sleep(5000); } catch (InterruptedException e) { }
}
}
When running this application under Solaris or Win32, you will clearly see that "in static_method()" is printed on the terminal, and then there is about a five-second pause. Then "in run()" is displayed. The monitor used for the static synchronized method is the same monitor associated with the Class object. Whether this behavior can be relied on for future implementations of the JVM is unknown. What is certain, however, is that two static synchronized methods defined in the same class will both refer to and compete for the same monitor.
What happens if a synchronized method calls itself recursively? Or if a synchronized method calls another synchronized method on the same object? A programmer not intimately familiar with Java monitors might assume that this would be a fatal situation, because a synchronized method "can be entered only once." However, this is not the case.
The behavior of a monitor, expressed earlier in this chapter,
can be stated again as follows: to enter a synchronized
method, the thread must first acquire ownership of the target
object's monitor. If a thread is recursively calling a synchronized
method, it already owns the monitor (because it is in the
middle of executing a synchronized
method). When the virtual machine tries to assign ownership of
the monitor, it finds that the thread already owns the monitor
and immediately allows that thread to proceed.
| Note |
A consequence of "recursive synchronized method call" is that it forces the virtual machine to count the number of times a thread has entered a particular monitor. Each time the thread enters the synchronized method, a counter within the monitor is incremented. Each time the thread leaves a synchronized method, the counter is decremented. Only when the counter reaches zero is the monitor released! |
A competitive situation arises when two or more threads are blocked, waiting to acquire the same monitor. Suppose a thread owns an object's monitor (it is executing a synchronized method on that object). If another thread attempts to call a synchronized method on that object, that thread will be suspended, pending the release of the monitor. If yet another thread attempts to call a synchronized method on the object, it will also be suspended. When the monitor becomes available, there are two threads waiting to acquire it.
When two or more threads are waiting to acquire the same monitor, the virtual machine must choose exactly one of the threads and assign ownership of the monitor to that thread. There are no guarantees about how the VM will make this decision. The language specification states only that one thread will acquire the monitor, but it does not specify how the VM will make the decision. In the Solaris 1.0 virtual machine, the decision is based on thread priority (first come, first serve when the priorities are equal). Monitor ownership is 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:
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:
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 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: