Managing State Dependence

In a single-threaded program, if a state-based precondition (like "the connection pool is nonempty") does not hold when a method is called, it will never become true. Therefore, classes in sequential programs can be coded to fail when their preconditions do not hold. But in a concurrent program, state-based conditions can change through the actions of other threads: a pool that was empty a few instructions ago can become nonempty because another thread returned an element. State-dependent methods on concurrent objects can sometimes get away with failing when their preconditions are not met, but there is often a better alternative: wait for the precondition to become true.

State-dependent operations that block until the operation can proceed are more convenient and less error-prone than those that simply fail. The built-in condition queue mechanism enables threads to block until an object has entered a state that allows progress and to wake blocked threads when they may be able to make further progress. We cover the details of condition queues in Section 14.2, but to motivate the value of an efficient condition wait mechanism, we first show how state dependence might be (painfully) tackled using polling and sleeping.

A blocking state-dependent action takes the form shown in Listing 14.1. The pattern of locking is somewhat unusual in that the lock is released and reacquired in the middle of the operation. The state variables that make up the precondition must be guarded by the object's lock, so that they can remain constant while the precondition is tested. But if the precondition does not hold, the lock must be released so another thread can modify the object stateotherwise the precondition will never become true. The lock must then be reacquired before testing the precondition again.

Listing 14.1. Structure of Blocking State-dependent Actions.

Bounded buffers such as ArrayBlockingQueue are commonly used in producer-consumer designs. A bounded buffer provides put and take operations, each of which has preconditions: you cannot take an element from an empty buffer, nor put an element into a full buffer. State dependent operations can deal with precondition failure by throwing an exception or returning an error status (making it the caller's problem), or by blocking until the object transitions to the right state.

We're going to develop several implementations of a bounded buffer that take different approaches to handling precondition failure. Each extends BaseBoundedBuffer in Listing 14.2, which implements a classic array-based circular buffer where the buffer state variables (buf, head, tail, and count) are guarded by the buffer's intrinsic lock. It provides synchronized doPut and doTake methods that are used by subclasses to implement the put and take operations; the underlying state is hidden from the subclasses.

14.1.1. Example: Propagating Precondition Failure to Callers

GrumpyBoundedBuffer in Listing 14.3 is a crude first attempt at implementing a bounded buffer. The put and take methods are synchronized to ensure exclusive access to the buffer state, since both employ check-then-act logic in accessing the buffer.

While this approach is easy enough to implement, it is annoying to use. Exceptions are supposed to be for exceptional conditions [EJ Item 39]. "Buffer is full" is not an exceptional condition for a bounded buffer any more than "red" is an exceptional condition for a traffic signal. The simplification in implementing the buffer (forcing the caller to manage the state dependence) is more than made up for by the substantial complication in using it, since now the caller must be prepared to catch exceptions and possibly retry for every buffer operation.[1] A well-structured call to take is shown in Listing 14.4not very pretty, especially if put and take are called throughout the program.

[1] Pushing the state dependence back to the caller also makes it nearly impossible to do things like preserve FIFO ordering; by forcing the caller to retry, you lose the information of who arrived first.

Listing 14.2. Base Class for Bounded Buffer Implementations.

Listing 14.3. Bounded Buffer that Balks When Preconditions are Not Met.

Listing 14.4. Client Logic for Calling GrumpyBoundedBuffer.

A variant of this approach is to return an error value when the buffer is in the wrong state. This is a minor improvement in that it doesn't abuse the exception mechanism by throwing an exception that really means "sorry, try again", but it does not address the fundamental problem: that callers must deal with precondition failures themselves.[2]

[2] Queue offers both of these optionspoll returns null if the queue is empty, and remove throws an exceptionbut Queue is not intended for use in producer-consumer designs. BlockingQueue, whose operations block until the queue is in the right state to proceed, is a better choice when producers and consumers will execute concurrently.

The client code in Listing 14.4 is not the only way to implement the retry logic. The caller could retry the take immediately, without sleepingan approach known as busy waiting or spin waiting. This could consume quite a lot of CPU time if the buffer state does not change for a while. On the other hand, if the caller decides to sleep so as not to consume so much CPU time, it could easily "oversleep" if the buffer state changes shortly after the call to sleep. So the client code is left with the choice between the poor CPU usage of spinning and the poor responsiveness of sleeping. (Somewhere between busy waiting and sleeping would be calling Thread.yield in each iteration, which is a hint to the scheduler that this would be a reasonable time to let another thread run. If you are waiting for another thread to do something, that something might happen faster if you yield the processor rather than consuming your full scheduling quantum.)

14.1.2. Example: Crude Blocking by Polling and Sleeping

SleepyBoundedBuffer in Listing 14.5 attempts to spare callers the inconvenience of implementing the retry logic on each call by encapsulating the same crude "poll and sleep" retry mechanism within the put and take operations. If the buffer is empty, take sleeps until another thread puts some data into the buffer; if the buffer is full, put sleeps until another thread makes room by removing some data. This approach encapsulates precondition management and simplifies using the bufferdefinitely a step in the right direction.

The implementation of SleepyBoundedBuffer is more complicated than the previous attempt.[3] The buffer code must test the appropriate state condition with the buffer lock held, because the variables that represent the state condition are guarded by the buffer lock. If the test fails, the executing thread sleeps for a while, first releasing the lock so other threads can access the buffer.[4] Once the thread wakes up, it reacquires the lock and tries again, alternating between sleeping and testing the state condition until the operation can proceed.

[3] We will spare you the details of Snow White's other five bounded buffer implementations, especially SneezyBoundedBuffer.

[4] It is usually a bad idea for a thread to go to sleep or otherwise block with a lock held, but in this case is even worse because the desired condition (buffer is full/empty) can never become true if the lock is not released!

From the perspective of the caller, this works nicelyif the operation can proceed immediately, it does, and otherwise it blocksand the caller need not deal with the mechanics of failure and retry. Choosing the sleep granularity is a tradeoff between responsiveness and CPU usage; the smaller the sleep granularity, the more responsive, but also the more CPU resources consumed. Figure 14.1 shows how sleep granularity can affect responsiveness: there may be a delay between when buffer space becomes available and when the thread wakes up and checks again.

Figure 14.1. Thread Oversleeping Because the Condition Became True Just After It Went to Sleep.

Listing 14.5. Bounded Buffer Using Crude Blocking.

SleepyBoundedBuffer also creates another requirement for the callerdealing with InterruptedException. When a method blocks waiting for a condition to become true, the polite thing to do is to provide a cancellation mechanism (see Chapter 7). Like most well-behaved blocking library methods, SleepyBounded-Buffer supports cancellation through interruption, returning early and throwing InterruptedException if interrupted.

These attempts to synthesize a blocking operation from polling and sleeping were fairly painful. It would be nice to have a way of suspending a thread but ensuring that it is awakened promptly when a certain condition (such as the buffer being no longer full) becomes true. This is exactly what condition queues do.

14.1.3. Condition Queues to the Rescue

Condition queues are like the "toast is ready" bell on your toaster. If you are listening for it, you are notified promptly when your toast is ready and can drop what you are doing (or not, maybe you want to finish the newspaper first) and get your toast. If you are not listening for it (perhaps you went outside to get the newspaper), you could miss the notification, but on return to the kitchen you can observe the state of the toaster and either retrieve the toast if it is finished or start listening for the bell again if it is not.

A condition queue gets its name because it gives a group of threadscalled the wait seta way to wait for a specific condition to become true. Unlike typical queues in which the elements are data items, the elements of a condition queue are the threads waiting for the condition.

Just as each Java object can act as a lock, each object can also act as a condition queue, and the wait, notify, and notifyAll methods in Object constitute the API for intrinsic condition queues. An object's intrinsic lock and its intrinsic condition queue are related: in order to call any of the condition queue methods on object X, you must hold the lock on X. This is because the mechanism for waiting for state-based conditions is necessarily tightly bound to the mechanism for preserving state consistency: you cannot wait for a condition unless you can examine the state, and you cannot release another thread from a condition wait unless you can modify the state.

Object.wait atomically releases the lock and asks the OS to suspend the current thread, allowing other threads to acquire the lock and therefore modify the object state. Upon waking, it reacquires the lock before returning. Intuitively, calling wait means "I want to go to sleep, but wake me when something interesting happens", and calling the notification methods means "something interesting happened".

BoundedBuffer in Listing 14.6 implements a bounded buffer using wait and notifyAll. This is simpler than the sleeping version, and is both more efficient (waking up less frequently if the buffer state does not change) and more responsive (waking up promptly when an interesting state change happens). This is a big improvement, but note that the introduction of condition queues didn't change the semantics compared to the sleeping version. It is simply an optimization in several dimensions: CPU efficiency, context-switch overhead, and responsiveness. Condition queues don't let you do anything you can't do with sleeping and polling[5], but they make it a lot easier and more efficient to express and manage state dependence.

[5] This is notquite true; a fair condition queue can guarantee the relative order in which threads are released from the wait set. Intrinsic condition queues, like intrinsic locks, do not offer fair queueing; explicit Conditions offer a choice of fair or nonfair queueing.

Listing 14.6. Bounded Buffer Using Condition Queues.

BoundedBuffer is finally good enough to useit is easy to use and manages state dependence sensibly.[6] A production version should also include timed versions of put and take, so that blocking operations can time out if they cannot complete within a time budget. The timed version of Object.wait makes this easy to implement.

[6] ConditionBoundedBuffer in Section 14.3 is even better: it is more efficient because it can use single notification instead of notifyAll.