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);
  }
 }
}

So, in addition for us trying to help you solve your problem, we also have to answer a riddle? — Isaac
– Isaac, Commented Dec 8, 2012 at 5:41
I am just trying to make it more interesting, that's all. I edit the question so I make that clear. — chrisapotek
– chrisapotek, Commented Dec 8, 2012 at 5:43

xagyg · Accepted Answer · 2012-12-08 08:47:19Z

10

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

answered Dec 8, 2012 at 8:47

xagyg

9,7822 gold badges34 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

chrisapotek Over a year ago

So it is impossible to have a blocking queue (multiple consumers and producers) with notify() ?

xagyg Over a year ago

@chrisapotek That is correct. You can only use notify in cases where only one "type" of thread is involved.

chrisapotek Over a year ago

Just wanted to know if it was possible somehow to use notify().

xagyg Over a year ago

@chrisapotek No problem. As mentioned, it's not possible. Using notify may happen to work (even most of the time), but there is always a chance it could get into the deadlocked state. The example you give is a fairly standard bounded buffer scenario and the general pattern with these is always to use a notifyAll. All patterns like readers/writers, producers/consumers etc. must use notifyAll to avoid deadlock.

Martin James Over a year ago

OK, what's wrong with a semaphore instead? Waking a dozen threads for one object, then having 11 of them block again almost immediately, does not seem sane to me..

|

Bohemian · Accepted Answer · 2012-12-08 05:51:56Z

0

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.

answered Dec 8, 2012 at 5:51

Bohemian♦

427k103 gold badges603 silver badges750 bronze badges

1 Comment

chrisapotek Over a year ago

I wanted to use notify() for a blocking queue, but if you use notify() in the code above it can break the queue. Do you see the situation where it breaks? Is it impossible to use notify() with this type of queue?

Alexei Kaigorodov · Accepted Answer · 2012-12-08 06:21:39Z

0

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()?

answered Dec 8, 2012 at 6:21

Alexei Kaigorodov

13.6k1 gold badge24 silver badges38 bronze badges

1 Comment

chrisapotek Over a year ago

Yes. To protect the lock. If you don't protect the lock it is a good idea to use notifyAll(). FIXED. Thx.

Collectives™ on Stack Overflow

notify() instead of notifyAll() for blocking queue

3 Answers 3

7 Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related