notify() instead of notifyAll() for blocking queue

Question

I am trying to find out whether it is possible to have a multiple producer / multiple consumer queue where I can use notify() instead of notifyAll(). For example, in the implementation below (source: here) you cannot just simply switch the notifyAll() for notify(). It is not totally obvious why you cannot switch so I will leave it as an teaser to whoever wants to help me out understanding this problem.

So the code below is broken:

public class BlockingQueue {

  private Object lock = new Object();

  private List queue = new LinkedList();
  private int  limit = 10;

  public BlockingQueue(int limit){
    this.limit = limit;
  }


  public void enqueue(Object item)
  throws InterruptedException  {
   synchronized(lock) {
    while(this.queue.size() == this.limit) {
      lock.wait();
    }
    if(this.queue.size() == 0) {
      lock.notify();
    }
    this.queue.add(item);
   }
  }


  public Object dequeue()
  throws InterruptedException{
   synchronized(lock) {
    while(this.queue.size() == 0){
      lock.wait();
    }
    if(this.queue.size() == this.limit){
      lock.notify();
    }

    return this.queue.remove(0);
  }
 }
}

Answer 1

The following steps lead us to deadlock. Let's set limit to 1 to keep the example brief.

• E1 enqueues an item.
• E2 attempts enqueue - checks wait loop - already full - waits

• E3 attempts enqueue - checks wait loop - already full - waits

• D1 attempts dequeue - and is executing synchronized block

• D2 attempts dequeue - blocks on entry to the (synchronized) block - due to D1

• D3 attempts dequeue - blocks on entry to the (synchronized) block - due to D1

• D1 is executing enqueue - gets the item, calls notify, exits method

• The notify happens to wake up E2 (i.e. "any waiting thread")
• BUT, D2 enters sync block before E2 can (E2 must reacquire the lock), so E2 blocks on entry to the enqueue sync block
• D2 checks wait loop, no more items in queue, so waits

• D3 enters block after D2, but before E2, checks wait loop, no more items in queue, so waits

• Now there is E3, D2, and D3 waiting!

• Finally E2 acquires the lock, enqueues an item, calls notify, exits method

• E2's notification wakes E3 (remember any thread can be woken)

• E3 checks the wait loop condition, there is already an item in the queue, so waits.
• NO MORE THREADS TO CALL NOTIFY and THREE THREADS PERMANENTLY SUSPENDED!

SOLUTION: Replace notify with notifyAll

Answer 2

Whatever your design, know that notify() wakes up a random thread currently waiting on the lock object, and notifyAll() wakes up all such threads (in random order).

As long as your waiting threads are coded to handle the type of wake up you give them, there'll be no problem.

One is not better then the other: In some situations notify() is the best choice, in others notifyAll() - it depends on the problem being tackled.

Answer 3

Move notify out of conditional statements in both methods (that conditions are no longer needed), and everything should work correctly.

And, in the original source the methods were synchronized. Why did you changed this to synchronized(lock)? Just to forget to change wait to lock.wait()?