Java: Why wait must be called in a synchronized block

Let's look at an example of what issues we would run into if wait() could be called outside of a synchronized block.

Suppose we were to implement a blocking queue.

A first attempt (without synchronization) could look something along the lines below

class BlockingQueue {
    Queue<String> buffer = new LinkedList<String>();
    
    public void give(String data) {
        buffer.add(data);
        notify();  // Since someone may be waiting in take
    }
    
    public String take() throws InterruptedException {
        while (buffer.isEmpty())  // Avoid "if" due to spurious wakeups
            wait();
        return buffer.remove();
    }
}

This is what could potentially happen:

  1. A consumer thread calls take() and sees that the buffer.isEmpty().

  2. Before the consumer thread goes on to call wait(), a producer thread comes along and invokes a full give(), that is, buffer.add(data); notify();

  3. The consumer thread will now call wait() (and miss the notify() that was just called).

  4. If unlucky, there will be no more calls to give and the consumer is stuck in wait indefinitely, even though there's data available to be consumed.

Once you understand the issue, the solution is obvious: Use synchronized to make sure notify is never called between isEmpty and wait.

Without going into details: This synchronization issue is universal. Wait / notify always boils down to communicating something, and inter-thread communication without synchronization is almost always broken.

Put Formally

Here is a more formal description given by Chris Smith.

[…] You need an absolute guarantee that the waiter and the notifier agree about the state of the predicate. The waiter checks the state of the predicate at some point slightly BEFORE it goes to sleep, but it depends for correctness on the predicate being true WHEN it goes to sleep. There's a period of vulnerability between those two events, which can break the program. […]

The predicate that the producer and consumer need to agree upon is in the above example buffer.isEmpty(). And the agreement is resolved by ensuring that the wait and notify are performed in synchronized blocks.

Comments (4)

User avatar

Hi, I have a question. If a consumer thread calls take() and go into synchronized block (assumed there is an synchronized object) then wait(), how would the producer thread call give(), which is protected by the same synchronized object? Is this another deadlock?

by Chen Wei |  Reply
User avatar

Good question. The answer can be found in the javadoc of the Object.wait method:

"[...] The thread releases ownership of this monitor and waits until another thread notifies threads waiting on this object's monitor to wake up either through a call to the notify method or the notifyAll method. [...]"

So the producer calling give() is allowed in, because while inside the Object.wait method, the monitor is temporarily released.

by Andreas Lundblad |  Reply
User avatar

Point #4 says -

"If unlucky, there will be no more calls to give and the consumer is stuck in wait indefinitely, even though there’s data available to be consumed."

Any example for the unlucky situation??

by Dinesh Ranawat |  Reply
User avatar

Here's an example of such unlucky situation:

Suppose you have an algorithm that may have at most 1 pending outstanding task at any given time. If one task gets "stuck in the queue" indefinitely because a notify() was missed by the consumer, then the producer can't enqueue more tasks, and the algorithm as a whole will get stuck.

by Andreas Lundblad |  Reply

Add comment