Synchronizing Thread

The examples in this chapter so far have contained independent, asynchronous threads. Each thread contained all the data and methods required for its execution and didn't require any outside resources or methods. Also, the threads in those examples ran at their own pace without concern for the state or activities of any other concurrently running threads.

However, in many interesting situations, separate, concurrently running threads do share data and must consider the state and activities of other threads. In one such set of programming situations, called producer/consumer scenarios, the producer generates a stream of data that a consumer uses.

For example, imagine an application in which one thread (the producer) writes data to a file while a second thread (the consumer) reads data from the same file. Or, as you type characters on the keyboard, the producer thread places mouse events in an event queue and the consumer thread reads the events from the same queue. Both of these examples use concurrent threads that share a common resource: The first shares a file, and the second shares an event queue. Because the threads share a common resource, they must be synchronized.

This section teaches you about thread synchronization through a simple producer/consumer example.

Producer/Consumer Example

The Producer.java generates an integer between 0 and 9 (inclusive), stores it in a CubbyHole object, and prints the generated number. [1] To make the synchronization problem more interesting, the Producer sleeps for a random amount of time between 0 and 100 milliseconds before repeating the number-generating cycle:

[1] Producer.java, Cubbyhole.java, and Consumer.java are included on the CD and are available online. See Code Samples (page 310).

public class Producer extends Thread { 
 private CubbyHole cubbyhole; 
 private int number; 

 public Producer(CubbyHole c, int number) { 
 cubbyhole = c; 
 this.number = number; 
 } 

 public void run() { 
 for (int i = 0; i < 10; i++) { 
 cubbyhole.put(i); 
 System.out.println("Producer #" + this.number + " put: " + i); 
 try { 
 sleep((int)(Math.random() * 100)); 
 } catch (InterruptedException e) { } 
 } 
 } 
} 

The Consumer.java, being ravenous, consumes all integers from the CubbyHole (the exact same object into which the Producer put the integers) as quickly as they become available:

public class Consumer extends Thread { 
 private CubbyHole cubbyhole; 
 private int number; 

 public Consumer(CubbyHole c, int number) { 
 cubbyhole = c; 
 this.number = number; 
 } 

 public void run() { 
 int value = 0; 
 for (int i = 0; i < 10; i++) { 
 value = cubbyhole.get(); 
 System.out.println("Consumer #" + this.number 
 + " got: " + value); 
 } 
 } 
} 

The Producer and Consumer in this example share data through a common CubbyHole object. Also, although the Consumer ideally will get each value produced once and only once, neither the Producer nor the Consumer makes any effort whatsoever to ensure that that happens. The synchronization between these two threads occurs at a lower level, within the get and put methods of the CubbyHole object. However, assume for a moment that these two threads make no arrangements for synchronization, and let's discuss the potential problems that might arise from this.

One problem arises when the Producer is quicker than the Consumer and generates two numbers before the Consumer has a chance to consume the first one. In this situation, the Consumer misses a number. Part of the output might look like this:

Another problem might arise when the Consumer is quicker than the Producer and consumes the same value twice. In this situation, the Consumer might produce output that looks like this:

Either way, the result is wrong because the Consumer should get each integer produced by the Producer exactly once. A problem such as this is called a race condition. Race conditions arise from multiple, asynchronously executing threads trying to access a single object at the same time and getting the wrong result.

Race conditions in the producer/consumer example are prevented by having the storage of a new integer into the CubbyHole by the Producer be synchronized with the retrieval of an integer from the CubbyHole by the Consumer. The activities of the Producer and the Consumer must be synchronized in two ways. First, the two threads must not simultaneously access the CubbyHole. A thread can prevent this from happening by locking an object. When an object is locked by one thread and another thread tries to call a synchronized method on the same object, the second thread will block until the object is unlocked.

Second, the two threads must do some simple coordination. That is, the Producer must have a way to indicate to the Consumer that the value is ready, and the Consumer must have a way to indicate that the value has been retrieved. The Thread class provides a collection of methodswait, notify, and notifyAllto help threads wait for a condition and notify other threads when that condition changes.

Locking an Object

Within a program, the code segments that access the same object from separate, concurrent threads are called critical sections. A critical section can be a block or a method and is identified with the synchronized keyword. The Java platform then associates a lock with every object that has synchronized code.

In the producer/consumer example, the put and get methods of CubbyHole.java are the critical sections. The Consumer should not access the CubbyHole when the Producer is changing it, and the Producer should not modify it when the Consumer is getting the value. So put and get in the CubbyHole class should be marked with the synchronized keyword.

Here's a code skeleton for the CubbyHole class:

public class CubbyHole { 
 private int contents; 
 private boolean available = false; 

 public synchronized int get() { 
 ... 
 } 

 public synchronized void put(int value) { 
 ... 
 } 
} 

The method declarations for both put and get contain the synchronized keyword, so the system associates a unique lock with every instance of CubbyHole. Whenever control enters a synchronized method, the thread that called the method locks the object whose method has been called. Other threads cannot call a synchronized method on the same object until the object is unlocked.

Thus, when it calls CubbyHole's put method, the Producer locks the CubbyHole, thereby preventing the Consumer from calling the CubbyHole's get method:

public synchronized void put(int value) { 
 //CubbyHole locked by the Producer 
 ... 
 //CubbyHole unlocked by the Producer 
} 

When the put method returns, the Producer unlocks the CubbyHole.

Similarly, when the Consumer calls CubbyHole's get method, it locks the CubbyHole, thereby preventing the Producer from calling put:

public synchronized int get() { 
 //CubbyHole locked by the Consumer 
 ... 
 //CubbyHole unlocked by the Consumer 
} 

The acquisition and release of a lock is done automatically and atomically by the Java runtime environment. This ensures that race conditions cannot occur in the underlying implementation of the threads, thus ensuring data integrity.

Synchronization isn't the whole story. The two threads must also be able to notify each other when they've done their jobs. Learn more about that after a brief foray into reentrant locks.

The same thread can call a synchronized method on an object for which it already holds the lock, thereby reacquiring the lock. The Java runtime environment allows a thread to reacquire a lock because the locks are reentrant. Reentrant locks are important because they eliminate the possibility of a single thread's deadlocking itself on a lock that it already holds.

Consider this class:

public class Reentrant { 
 public synchronized void a() { 
 b(); 
 System.out.println("here I am, in a()"); 
 } 
 public synchronized void b() { 
 System.out.println("here I am, in b()"); 
 } 
} 

Reentrant contains two synchronized methods: a and b. The first, a, calls the other, b. When control enters method a, the current thread acquires the lock for the Reentrant object. Now a calls b; because b is also synchronized, the thread attempts to acquire the same lock again. Because the Java platform supports reentrant locks, this works. In platforms that don't support reentrant locks, this sequence of method calls causes deadlock. The current thread can acquire the Reentrant object's lock again, and both a and b execute to conclusion, as is evidenced by the output:

here I am, in b() 
here I am, in a() 

Using the notifyAll and wait Methods

Let's investigate how the code in CubbyHole's put and get methods helps the Producer and the Consumer coordinate their activities. The CubbyHole stores its value in a private member variable called contents. CubbyHole has another private member variable, available, that is a boolean. The available variable is true when the value has been put but not yet gotten and is false when the value has been gotten but not yet put. Here's one possible implementation for the put and get methods:

public synchronized int get() { //won't work! 
 if (available == true) { 
 available = false; 
 return contents; 
 } 
} 
public synchronized int put(int value) { //won't work! 
 if (available == false) { 
 available = true; 
 contents = value; 
 } 
} 

As implemented, these two methods won't work. Look at the get method. What happens if the Producer hasn't put anything in the CubbyHole and available isn't true? The get method does nothing. Similarly, if the Producer calls put before the Consumer got the value, put doesn't do anything.

You really want the Consumer to wait until the Producer puts something in the CubbyHole and the Producer to notify the Consumer when it's done so. Similarly, the Producer should wait until the Consumer takes a value (and notifies the Producer of its activities) before replacing it with a new value. The two threads must coordinate more fully and can use Object's wait and notifyAll methods to do so.

Here are the new get and put implementations that wait on and notify each other of their activities:

public synchronized int get() { 
 while (available == false) { 
 try { 
 //wait for Producer to put value 
 wait(); 
 } catch (InterruptedException e) { } 
 } 
 available = false; 
 //notify Producer that value has been retrieved 
 notifyAll(); 
 return contents; 
} 

public synchronized void put(int value) { 
 while (available == true) { 
 try { 
 //wait for Consumer to get value 
 wait(); 
 } catch (InterruptedException e) { } 
 } 
 contents = value; 
 available = true; 
 //notify Consumer that value has been set 
 notifyAll(); 
} 

The code in the get method loops until the Producer has produced a new value. Each time through the loop, get calls the wait method. The wait method relinquishes the lock held by the Consumer on the CubbyHole (thereby allowing the Producer to get the lock and update the CubbyHole) and then waits for notification from the Producer. When it puts something in the CubbyHole, the Producer notifies the Consumer by calling notifyAll. The Consumer then comes out of the wait state, available is now true, the loop exits, and the get method returns the value in the CubbyHole.

The put method works in a similar fashion. It waits for the Consumer thread to consume the current value before allowing the Producer to produce a new one.

The notifyAll method wakes up all threads waiting on the object in question (in this case, the CubbyHole). The awakened threads compete for the lock. One thread gets it, and the others go back to waiting. The Object class also defines the notify method, which arbitrarily wakes up one of the threads waiting on this object.

The Object class contains three versions of the wait method:

wait()	Waits indefinitely for notification. (This method was used in the producer/consumer example.)
wait(long timeout )	Waits for notification or until the timeout period has elapsed. The timeout argument is specified in milliseconds.
wait(long timeout , int nanos )	Waits for notification or until timeout milliseconds plus nanos nanoseconds have elapsed.

Note

Besides using these timed wait methods to synchronize threads, you also can use them in place of sleep. Both wait and sleep delay for the requested amount of time. You can easily wake up wait with a notify, but a sleeping thread cannot be awakened prematurely. This doesn't matter too much for threads that don't sleep for long, but it could be important for threads that sleep for minutes at a time.

 

Running the Producer/Consumer Example

Here's a small standalone application, called ProducerConsumerDemo, [1] that creates a CubbyHole object, a Producer, and a Consumer and then starts both the Producer and the Consumer:

[1] ProducerConsumerDemo.java is included on the CD and is available online. See Code Samples (page 310).

public class ProducerConsumerDemo { 
 public static void main(String[] args) { 
 CubbyHole c = new CubbyHole(); 
 Producer p1 = new Producer(c, 1); 
 Consumer c1 = new Consumer(c, 1); 

 p1.start(); 
 c1.start(); 
 } 
} 

Here's the output of ProducerConsumerDemo:

Producer #1 put: 0 
Consumer #1 got: 0 
Producer #1 put: 1 
Consumer #1 got: 1 
Producer #1 put: 2 
Consumer #1 got: 2 
Producer #1 put: 3 
Consumer #1 got: 3 
Producer #1 put: 4 
Consumer #1 got: 4 
Producer #1 put: 5 
Consumer #1 got: 5 
Producer #1 put: 6 
Consumer #1 got: 6 
Producer #1 put: 7 
Consumer #1 got: 7 
Producer #1 put: 8 
Consumer #1 got: 8 
Producer #1 put: 9 
Consumer #1 got: 9 

Avoiding Starvation and Deadlock

If you write a program in which several concurrent threads are competing for resources, you must take precautions to ensure fairness. A system is fair when each thread gets enough access to limited resources to make reasonable progress. A fair system prevents starvation and deadlock. Starvation occurs when one or more threads in your program are blocked from gaining access to a resource and, as a result, cannot make progress. Deadlock, the ultimate form of starvation, occurs when two or more threads are waiting on a condition that cannot be satisfied. Deadlock most often occurs when two (or more) threads are each waiting for the other(s) to do something.

http://java.sun.com/docs/books/tutorial/essential/threads/deadlock.html

The story of the dining philosophers is often used to illustrate various problems that can occur when many synchronized threads are competing for limited resources. The story goes like this. Five philosophers are sitting at a round table. In front of each philosopher is a bowl of rice. Between each pair of philosophers is one chopstick. Before taking a bite of rice, an individual philosopher must have two chopsticks: one taken from the left and one taken from the right. The philosophers must find a way to share chopsticks so that they all get to eat.

The dining philosophers algorithm implemented by the following applet works like this. Duke always reaches for the chopstick on his right first. If the chopstick is there, Duke takes it and raises his right hand. Next, Duke tries for the left chopstick. If the chopstick is available, Duke picks it up and raises his other hand. Now that Duke has both chopsticks, he takes a bite of rice and says, "Mmm!" He then puts both chopsticks down, thereby allowing either of his two neighbors to get the chopsticks. Duke then starts all over again by trying for the right chopstick. Between each attempt to grab a chopstick, Duke pauses for a random period of time.

The slider at the bottom of the applet controls the amount of time that each philosopher waits before attempting to pick up a chopstick. When the slider is set to 0, the philosophers don't waitthey just graband the applet often ends up in deadlockthat is, all the philosophers are frozen with their right hands in the air. Why? Because each immediately has one chop-stick and is waiting on a condition that cannot be satisfied. That is, each is waiting for the chopstick on the left, which is held by the philosopher to the left.

When you move the slider so that the waiting period is longer, the applet may proceed for a while without deadlocking. However, deadlock is always possible with this particular implementation of the dining philosophers problem because it is possible for all five philosophers to be holding their right chopsticks. Rather than rely on luck to prevent deadlock, you must either explicitly prevent it or detect it.

For most programmers, the better choice is to prevent deadlock rather than to try to detect it. The simplest approach to preventing deadlock is to impose ordering on the condition variables. In the dining philosopher applet, no ordering is imposed on the condition variables because the philosophers and the chopsticks are arranged in a circle. All chopsticks are equal.

However, you can change the rules in the applet by numbering the chopsticks 1 through 5 and insisting that the philosophers pick up first the chopstick that has the lower number. The philosopher who is sitting between chopsticks 1 and 2 and the philosopher who is sitting between chopsticks 1 and 5 must now reach for the same chopstick first (chopstick 1) rather than picking up the one on the right. Whoever gets chopstick 1 first is then free to take another chopstick. Whoever doesn't get chopstick 1 must now wait for the first philosopher to release it. Deadlock is not possible.