Producer and Consumer Problems with Threads

A notification sent between a thread's check of a condition and its call to wait() is lost, and the waiting thread can wait forever. This is a race condition.

Programming

The Patient Waiter Picture

A common way to think about wait() and notify() is as a simple waiting arrangement. One thread waits, and some other thread will eventually call notify() to wake it up, so the waiting thread only has to sit and be patient. This picture feels reasonable, but it quietly assumes that the notification arrives after the wait has started. That assumption is wrong in general, and this article takes it apart.

The problem is a race condition. A race condition is a situation where two or more threads access shared data and the outcome depends on the order in which they execute. The threads in this article are a producer, which creates a result, and a consumer, which uses it. Whether the handoff between them works depends on how their steps interleave, and some interleavings leave the consumer waiting forever.

Predicting the Early Notification

Before reading the trace, try the question yourself. The consumer has checked that the shared result is still empty and has not yet called wait(). What do you think happens if the producer now stores the result and calls notify() before the consumer gets to wait()?

What do you think happens?

What happens if notify() runs after the consumer's check but before its wait() call?

The consumer wakes up immediately because notify() was already sent
The notification is lost and the consumer can wait forever
The producer waits until the consumer calls wait()

Reveal answer

Answer:

The notification is lost and the consumer can wait forever.

A notification sent between the consumer's check of the condition and its call to wait() is lost. Nothing is waiting when notify() runs, so the later wait() has no notification to respond to. The source describes this as a kind of deadlock in which the waiting thread waits forever. The fault is in the unprotected gap between the check and the wait, not in wait() or notify() themselves.

The Single-Item Handoff Setup

To make the idea concrete, the source uses a simplified producer and consumer problem in which only one item is produced and consumed. Three pieces are involved. A shared variable named sharedResult carries the result from the producer to the consumer. When the result is ready, the producer sets sharedResult to a non-null value. The consumer checks whether the result is ready by testing whether sharedResult is null. A separate variable named lock is used for synchronization.

The source's structure places the work and the coordination in different places. The producer computes its result outside the synchronized statement. Then, inside the synchronized statement, it stores the result in sharedResult and calls notify(). The consumer enters a synchronized statement, loops while sharedResult is still null, and calls wait() inside that loop. Once the result is available, the consumer copies the value out and uses it after leaving the synchronized block. The calls that generate and use the result sit outside the synchronized code, so they can run in parallel with other threads that also synchronize on the lock.

java

class Handoff {
    private static final Object lock = new Object();
    private static String sharedResult = null;

    static void produce(String value) {
        // the value is computed before this point, outside the synchronized block
        synchronized (lock) {
            sharedResult = value;
            lock.notify();
        }
    }

    static String consume() {
        String value;
        synchronized (lock) {
            while (sharedResult == null) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    // the source's simplified version leaves this catch block empty
                }
            }
            value = sharedResult;
        }
        // the value is used here, after the lock has been released
        return value;
    }
}

class Handoff {
    private static final Object lock = new Object();
    private static String sharedResult = null;

    static void produce(String value) {
        // the value is computed before this point, outside the synchronized block
        synchronized (lock) {
            sharedResult = value;
            lock.notify();
        }
    }

    static String consume() {
        String value;
        synchronized (lock) {
            while (sharedResult == null) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    // the source's simplified version leaves this catch block empty
                }
            }
            value = sharedResult;
        }
        // the value is used here, after the lock has been released
        return value;
    }
}

Notes on the code

sharedResult is the shared variable that carries the result
lock is the synchronization object used for both wait() and notify()
The producer's notify() happens inside the same lock as the consumer's check and wait
The while loop re-tests the condition every time the consumer wakes up

Tracing the Lost Notification

The following diagram is not a trace of any particular run. It shows one order of steps that breaks the handoff. The consumer checks sharedResult and finds it null. Before the consumer reaches wait(), the producer sets sharedResult and calls notify(). No thread is waiting at that moment, so the notification has nothing to wake. When the consumer then calls wait(), it has no notification left to receive.

In what order do the two threads' steps interleave, and at which exact point does notify() get sent before the waiter has started waiting?

The consumer in this order is waiting for a notification that will never come, because notify() has already been called. The threads are not doing anything wrong individually. The error lies in the gap between the check and the wait, where nothing protects the state from change. The fix is to make the check and the wait happen inside the same lock, so the producer cannot slip its notify() into that gap.

Why Both Calls Use the Same Lock

The fix the source proposes is to enclose both threads' code in synchronized statements, and to synchronize on the same object that is used for the calls to wait() and notify(). Java makes this a requirement. A thread can legally call obj.wait() or obj.notify() only if it holds the synchronization lock associated with obj. Calling either method without the lock throws IllegalMonitorStateException.

How wait() Hands Off the Lock

There is an apparent contradiction in the handoff. The consumer's wait() does not finish until the producer's notify() runs, yet both calls sit inside synchronized statements on the same object. Shouldn't that make it impossible for both to be running at the same time? The answer is that wait() is a special case. When a thread calls lock.wait(), it gives up the lock it holds on the synchronization object. That gives another thread the chance to enter the synchronized block that contains notify(). After the second thread leaves that block, the lock is returned to the waiting consumer so that it can continue.

What state is the waiting thread in after wait() is called, who holds the lock at that moment, and how does control pass to the thread that calls notify()?

The Shared Variable as the Handoff Path

With the lock in place, the path of a single item becomes clear. The producer's computation happens first, outside any lock. The result then enters the synchronized block, where it is stored in sharedResult. The consumer copies the value out of sharedResult while it holds the lock, and it uses the value only after the lock has been released. Only the storing and copying steps are protected, because those are the steps that touch the shared state.

How does a produced item move from the producer into the shared variable and then out to the consumer, and which step is protected by the lock?

Why the Wait Belongs in a Loop

The wait() method can throw an InterruptedException, so it should be called inside a try statement that handles that exception. In the consumer code, the wait() call is wrapped in try and catch. The more important structure, however, is the loop around the try. The consumer re-tests the condition sharedResult == null every time it wakes up, rather than assuming that waking up means the result is ready.

After the consumer wakes, it does not go straight to the use step. It checks the condition again. If sharedResult is still null, the consumer goes back to waiting. If it is no longer null, the consumer copies the value and leaves the block. The recheck is what makes the handoff robust, because the consumer proceeds only when the state it needs actually exists.

Common mistake
Checking the condition outside the lock and then calling wait() inside it
What it looks like
```
if (sharedResult == null) { lock.wait(); } written with no synchronized block around the check
```
Why it fails
A notify() can run between the check and the wait, and the notification is lost, so the thread can wait forever.
Do this instead
Put the check and the wait inside the same synchronized block on the same lock.
Common mistake
Waiting and notifying on different lock objects
What it looks like
The consumer calls waitLock.wait() while the producer calls notifyLock.notify()
Why it fails
A thread can call wait() or notify() legally only while holding the lock on the object it uses, and a notification on one object does not reach a waiter on another.
Do this instead
Use one shared lock object for the check, the wait, the store, and the notify.
Common mistake
Using an if statement instead of a while loop around wait()
What it looks like
```
if (sharedResult == null) { wait(); } followed by using sharedResult
```
Why it fails
Waking up does not guarantee that the condition is true, so the thread may proceed too early.
Do this instead
Re-test the condition in a while loop every time the thread wakes.
Common mistake
Ignoring InterruptedException, which wait() can throw and which must be handled in a try statement

Stepping Through the Consumer's Decisions

Worked example

Following the consumer through one handoff

The consumer enters the synchronized block first and finds sharedResult is null. The producer later stores a value and calls notify(). Trace what the consumer does at each step.

1
Enter the synchronized block
The consumer holds the lock on lock and tests sharedResult == null, which is true.
2
Call wait()
wait() releases the lock, so the producer can enter its synchronized block and store the value.
3
Producer notifies and exits
The producer sets sharedResult, calls notify(), and leaves its block, which returns the lock to the consumer.
4
Re-test the condition
The consumer wakes inside the loop and checks sharedResult == null again. It is now false, so the loop ends.
5
Copy and use the value
The consumer copies the value while still holding the lock, leaves the block, and then uses the value.

Result

The consumer receives the item only after the condition is confirmed true, and the notification was not lost because the check and the wait were protected by the same lock.

Trying the Handoff Yourself

MEDIUM

A colleague writes a consumer that checks sharedResult == null outside any synchronized block, and then calls lock.wait() inside a synchronized block that begins after that check. Explain whether a notify() from the producer could be lost in this arrangement, and describe the change that closes the gap.

Hints

Think about which steps can be interleaved with the producer's steps when the check and the wait are not protected together.
The source's fix moves the check inside the same synchronized block as the wait, and uses one shared lock.

Your attempt (not saved)

Key Takeaways

A notification sent between a thread's check of a condition and its call to wait() is lost, and the waiting thread can wait forever. This is a race condition.
wait() and notify() must be called while holding the lock on the same object. Calling either without that lock throws IllegalMonitorStateException.
wait() releases the lock it holds, which lets the producer enter its synchronized block, call notify(), and leave, after which the lock returns to the waiting consumer.
A robust handoff keeps the check and the wait in one synchronized block on one lock, wraps wait() in a try statement, and re-tests the condition in a loop each time the thread wakes.