Using Condition Queues

Condition queues make it easier to build efficient and responsive state-dependent classes, but they are still easy to use incorrectly; there are a lot of rules regarding their proper use that are not enforced by the compiler or platform. (This is one of the reasons to build on top of classes like LinkedBlockingQueue, CountDown-Latch, Semaphore, and FutureTask when you can; if you can get away with it, it is a lot easier.)

14.2.1. The Condition Predicate

The key to using condition queues correctly is identifying the condition predicates that the object may wait for. It is the condition predicate that causes much of the confusion surrounding wait and notify, because it has no instantiation in the API and nothing in either the language specification or the JVM implementation ensures its correct use. In fact, it is not mentioned directly at all in the language specification or the Javadoc. But without it, condition waits would not work.

The condition predicate is the precondition that makes an operation state-dependent in the first place. In a bounded buffer, take can proceed only if the buffer is not empty; otherwise it must wait. For take, the condition predicate is "the buffer is not empty", which take must test for before proceeding. Similarly, the condition predicate for put is "the buffer is not full". Condition predicates are expressions constructed from the state variables of the class; BaseBoundedBuffer tests for "buffer not empty" by comparing count to zero, and tests for "buffer not full" by comparing count to the buffer size.

Document the condition predicate(s) associated with a condition queue and the operations that wait on them.

There is an important three-way relationship in a condition wait involving locking, the wait method, and a condition predicate. The condition predicate involves state variables, and the state variables are guarded by a lock, so before testing the condition predicate, we must hold that lock. The lock object and the condition queue object (the object on which wait and notify are invoked) must also be the same object.

In BoundedBuffer, the buffer state is guarded by the buffer lock and the buffer object is used as the condition queue. The take method acquires the buffer lock and then tests the condition predicate (that the buffer is nonempty). If the buffer is indeed nonempty, it removes the first element, which it can do because it still holds the lock guarding the buffer state.

If the condition predicate is not true (the buffer is empty), take must wait until another thread puts an object in the buffer. It does this by calling wait on the buffer's intrinsic condition queue, which requires holding the lock on the condition queue object. As careful design would have it, take already holds that lock, which it needed to test the condition predicate (and if the condition predicate was true, to modify the buffer state in the same atomic operation). The wait method releases the lock, blocks the current thread, and waits until the specified timeout expires, the thread is interrupted, or the thread is awakened by a notification. After the thread wakes up, wait reacquires the lock before returning. A thread waking up from wait gets no special priority in reacquiring the lock; it contends for the lock just like any other thread attempting to enter a synchronized block.

Every call to wait is implicitly associated with a specific condition predicate. When calling wait regarding a particular condition predicate, the caller must already hold the lock associated with the condition queue, and that lock must also guard the state variables from which the condition predicate is composed.

 

14.2.2. Waking Up Too Soon

As if the three-way relationship among the lock, the condition predicate, and the condition queue were not complicated enough, that wait returns does not necessarily mean that the condition predicate the thread is waiting for has become true.

A single intrinsic condition queue may be used with more than one condition predicate. When your thread is awakened because someone called notifyAll, that doesn't mean that the condition predicate you were waiting for is now true. (This is like having your toaster and coffee maker share a single bell; when it rings, you still have to look to see which device raised the signal.)[7] Additionally, wait is even allowed to return "spuriously"not in response to any thread calling notify.[8]

[7] This situation actually describes Tim's kitchen pretty well; so many devices beep that when you hear one, you have to inspect the toaster, the microwave, the coffee maker, and several others to determine the cause of the signal.

[8] To push the breakfast analogy way too far, this is like a toaster with a loose connection that makes the bell go off when the toast is ready but also sometimes when it is not ready.

When control re-enters the code calling wait, it has reacquired the lock associated with the condition queue. Is the condition predicate now true? Maybe. It might have been true at the time the notifying thread called notifyAll, but could have become false again by the time you reacquire the lock. Other threads may have acquired the lock and changed the object's state between when your thread was awakened and when wait reacquired the lock. Or maybe it hasn't been true at all since you called wait. You don't know why another thread called notify or notifyAll; maybe it was because another condition predicate associated with the same condition queue became true. Multiple condition predicates per condition queue are quite commonBoundedBuffer uses the same condition queue for both the "not full" and "not empty" predicates.[9]

[9] It is actually possible for threads to be waiting for both "not full" and "not empty" at the same time! This can happen when the number of producers/consumers exceeds the buffer capacity.

For all these reasons, when you wake up from wait you must test the condition predicate again, and go back to waiting (or fail) if it is not yet true. Since you can wake up repeatedly without your condition predicate being true, you must therefore always call wait from within a loop, testing the condition predicate in each iteration. The canonical form for a condition wait is shown in Listing 14.7.

Listing 14.7. Canonical Form for State-dependent Methods.

void stateDependentMethod() throws InterruptedException {
 // condition predicate must be guarded by lock
 synchronized(lock) {
 while (!conditionPredicate())
 lock.wait();
 // object is now in desired state
 }
}

When using condition waits (Object.wait or Condition.await):

• Always have a condition predicatesome test of object state that must hold before proceeding;
• Always test the condition predicate before calling wait, and again after returning from wait;
• Always call wait in a loop;
• Ensure that the state variables making up the condition predicate are guarded by the lock associated with the condition queue;
• Hold the lock associated with the the condition queue when calling wait, notify, or notifyAll; and
• Do not release the lock after checking the condition predicate but before acting on it.

 

14.2.3. Missed Signals

Chapter 10 discussed liveness failures such as deadlock and livelock. Another form of liveness failure is missed signals. A missed signal occurs when a thread must wait for a specific condition that is already true, but fails to check the condition predicate before waiting. Now the thread is waiting to be notified of an event that has already occurred. This is like starting the toast, going out to get the newspaper, having the bell go off while you are outside, and then sitting down at the kitchen table waiting for the toast bell. You could wait a long timepotentially forever.[10] Unlike the marmalade for your toast, notification is not "sticky"if thread A notifies on a condition queue and thread B subsequently waits on that same condition queue, B does not immediately wake upanother notification is required to wake B. Missed signals are the result of coding errors like those warned against in the list above, such as failing to test the condition predicate before calling wait. If you structure your condition waits as in Listing 14.7, you will not have problems with missed signals.

[10] In order to emerge from this wait, someone else would have to make toast, but this will just make matters worse; when the bell rings, you will then have a disagreement about toast ownership.

14.2.4. Notification

So far, we've described half of what goes on in a condition wait: waiting. The other half is notification. In a bounded buffer, take blocks if called when the buffer is empty. In order for take to unblock when the buffer becomes nonempty, we must ensure that every code path in which the buffer could become nonempty performs a notification. In BoundedBuffer, there is only one such placeafter a put. So put calls notifyAll after successfully adding an object to the buffer. Similarly, take calls notifyAll after removing an element to indicate that the buffer may no longer be full, in case any threads are waiting on the "not full" condition.

Whenever you wait on a condition, make sure that someone will perform a notification whenever the condition predicate becomes true.

There are two notification methods in the condition queue APInotify and notifyAll. To call either, you must hold the lock associated with the condition queue object. Calling notify causes the JVM to select one thread waiting on that condition queue to wake up; calling notifyAll wakes up all the threads waiting on that condition queue. Because you must hold the lock on the condition queue object when calling notify or notifyAll, and waiting threads cannot return from wait without reacquiring the lock, the notifying thread should release the lock quickly to ensure that the waiting threads are unblocked as soon as possible.

Because multiple threads could be waiting on the same condition queue for different condition predicates, using notify instead of notifyAll can be dangerous, primarily because single notification is prone to a problem akin to missed signals.

BoundedBuffer provides a good illustration of why notifyAll should be preferred to single notify in most cases. The condition queue is used for two different condition predicates: "not full" and "not empty". Suppose thread A waits on a condition queue for predicate PA, while thread B waits on the same condition queue for predicate PB. Now, suppose PB becomes true and thread C performs a single notify: the JVM will wake up one thread of its own choosing. If A is chosen, it will wake up, see that PA is not yet true, and go back to waiting. Meanwhile, B, which could now make progress, does not wake up. This is not exactly a missed signalit's more of a "hijacked signal"but the problem is the same: a thread is waiting for a signal that has (or should have) already occurred.

Single notify can be used instead of notifyAll only when both of the following conditions hold:

Uniform waiters. Only one condition predicate is associated with the condition queue, and each thread executes the same logic upon returning from wait; and

One-in, one-out. A notification on the condition variable enables at most one thread to proceed.

BoundedBuffer meets the one-in, one-out requirement, but does not meet the uniform waiters requirement because waiting threads might be waiting for either the "not full" and "not empty" condition. A "starting gate" latch like that used in TestHarness on page 96, in which a single event releases a set of threads, does not meet the one-in, one-out requirement because opening the starting gate lets multiple threads proceed.

Most classes don't meet these requirements, so the prevailing wisdom is to use notifyAll in preference to single notify. While this may be inefficient, it is much easier to ensure that your classes behave correctly when using notifyAll instead of notify.

This "prevailing wisdom" makes some people uncomfortable, and for good reason. Using notifyAll when only one thread can make progress is inefficientsometimes a little, sometimes grossly so. If ten threads are waiting on a condition queue, calling notifyAll causes each of them to wake up and contend for the lock; then most or all of them will go right back to sleep. This means a lot of context switches and a lot of contended lock acquisitions for each event that enables (maybe) a single thread to make progress. (In the worst case, using notify-All results in O(n2) wakeups where n would suffice.) This is another situation where performance concerns support one approach and safety concerns support the other.

The notification done by put and take in BoundedBuffer is conservative: a notification is performed every time an object is put into or removed from the buffer. This could be optimized by observing that a thread can be released from a wait only if the buffer goes from empty to not empty or from full to not full, and notifying only if a put or take effected one of these state transitions. This is called conditional notification. While conditional notification can improve performance, it is tricky to get right (and also complicates the implementation of subclasses) and so should be used carefully. Listing 14.8 illustrates using conditional notification in BoundedBuffer.put.

Single notification and conditional notification are optimizations. As always, follow the principle "First make it right, and then make it fastif it is not already fast enough" when using these optimizations; it is easy to introduce strange liveness failures by applying them incorrectly.

Listing 14.8. Using Conditional Notification in BoundedBuffer.put.

public synchronized void put(V v) throws InterruptedException {
 while (isFull())
 wait();
 boolean wasEmpty = isEmpty();
 doPut(v);
 if (wasEmpty)
 notifyAll();
}

14.2.5. Example: A Gate Class

The starting gate latch in TestHarness on page 96 was constructed with an initial count of one, creating a binary latch: one with two states, the initial state and the terminal state. The latch prevents threads from passing the starting gate until it is opened, at which point all the threads can pass through. While this latching mechanism is often exactly what is needed, sometimes it is a drawback that a gate constructed in this manner cannot be reclosed once opened.

It is easy to develop a recloseable ThreadGate class using condition waits, as shown in Listing 14.9. ThreadGate lets the gate be opened and closed, providing an await method that blocks until the gate is opened. The open method uses notifyAll because the semantics of this class fail the "one-in, one-out" test for single notification.

The condition predicate used by await is more complicated than simply testing isOpen. This is needed because if N threads are waiting at the gate at the time it is opened, they should all be allowed to proceed. But, if the gate is opened and closed in rapid succession, all threads might not be released if await examines only isOpen: by the time all the threads receive the notification, reacquire the lock, and emerge from wait, the gate may have closed again. So THReadGate uses a somewhat more complicated condition predicate: every time the gate is closed, a "generation" counter is incremented, and a thread may pass await if the gate is open now or if the gate has opened since this thread arrived at the gate.

Since ThreadGate only supports waiting for the gate to open, it performs notification only in open; to support both "wait for open" and "wait for close" operations, it would have to notify in both open and close. This illustrates why state-dependent classes can be fragile to maintainthe addition of a new statedependent operation may require modifying many code paths that modify the object state so that the appropriate notifications can be performed.

14.2.6. Subclass Safety Issues

Using conditional or single notification introduces constraints that can complicate subclassing [CPJ 3.3.3.3]. If you want to support subclassing at all, you must structure your class so subclasses can add the appropriate notification on behalf of the base class if it is subclassed in a way that violates one of the requirements for single or conditional notification.

Listing 14.9. Recloseable Gate Using Wait and Notifyall.

@ThreadSafe
public class ThreadGate {
 // CONDITION-PREDICATE: opened-since(n) (isOpen || generation>n)
 @GuardedBy("this") private boolean isOpen;
 @GuardedBy("this") private int generation;

 public synchronized void close() {
 isOpen = false;
 }

 public synchronized void open() {
 ++generation;
 isOpen = true;
 notifyAll();
 }

 // BLOCKS-UNTIL: opened-since(generation on entry)
 public synchronized void await() throws InterruptedException {
 int arrivalGeneration = generation;
 while (!isOpen && arrivalGeneration == generation)
 wait();
 }
}

A state-dependent class should either fully expose (and document) its waiting and notification protocols to subclasses, or prevent subclasses from participating in them at all. (This is an extension of "design and document for inheritance, or else prohibit it" [EJ Item 15].) At the very least, designing a state-dependent class for inheritance requires exposing the condition queues and locks and documenting the condition predicates and synchronization policy; it may also require exposing the underlying state variables. (The worst thing a state-dependent class can do is expose its state to subclasses but not document its protocols for waiting and notification; this is like a class exposing its state variables but not documenting its invariants.)

One option for doing this is to effectively prohibit subclassing, either by making the class final or by hiding the condition queues, locks, and state variables from subclasses. Otherwise, if the subclass does something to undermine the way the base class uses notify, it needs to be able to repair the damage. Consider an unbounded blocking stack in which the pop operation blocks if the stack is empty but the push operation can always proceed. This meets the requirements for single notification. If this class uses single notification and a subclass adds a blocking "pop two consecutive elements" method, there are now two classes of waiters: those waiting to pop one element and those waiting to pop two. But if the base class exposes the condition queue and documents its protocols for using it, the subclass can override the push method to perform a notifyAll, restoring safety.

14.2.7. Encapsulating Condition Queues

It is generally best to encapsulate the condition queue so that it is not accessible outside the class hierarchy in which it is used. Otherwise, callers might be tempted to think they understand your protocols for waiting and notification and use them in a manner inconsistent with your design. (It is impossible to enforce the uniform waiters requirement for single notification unless the condition queue object is inaccessible to code you do not control; if alien code mistakenly waits on your condition queue, this could subvert your notification protocol and cause a hijacked signal.)

Unfortunately, this adviceto encapsulate objects used as condition queuesis not consistent with the most common design pattern for thread-safe classes, in which an object's intrinsic lock is used to guard its state. BoundedBuffer illustrates this common idiom, where the buffer object itself is the lock and condition queue. However, BoundedBuffer could be easily restructured to use a private lock object and condition queue; the only difference would be that it would no longer support any form of client-side locking.

14.2.8. Entry and Exit Protocols

Wellings (Wellings, 2004) characterizes the proper use of wait and notify in terms of entry and exit protocols. For each state-dependent operation and for each operation that modifies state on which another operation has a state dependency, you should define and document an entry and exit protocol. The entry protocol is the operation's condition predicate; the exit protocol involves examining any state variables that have been changed by the operation to see if they might have caused some other condition predicate to become true, and if so, notifying on the associated condition queue.

AbstractQueuedSynchronizer, upon which most of the state-dependent classes in java.util.concurrent are built (see Section 14.4), exploits the concept of exit protocol. Rather than letting synchronizer classes perform their own notification, it instead requires synchronizer methods to return a value indicating whether its action might have unblocked one or more waiting threads. This explicit API requirement makes it harder to "forget" to notify on some state transitions.