Blocking queue in Java

Question

I am reading a book titled "Beginning Algorithms", that has examples in Java. In the chapter about queues, it explains the "blocking queue", and ... even when my background is C# and not Java, something looks funny to me.

This is part of the code ( I have omitted non relevant parts ):

public void enqueue(Object value){
    synchronized(_mutex){
        while(size == _max_size){
            waitForNotification();
        }
        _queue.enqueue(value);
        _mutex.notifyAll();
    }
}

private void waitForNotification(){
    try {
        _mutex.wait();
    } catch( InterruptedException e){
        // Ignore
    }
}

public Object dequeue() throws EmptyQueueException {
    synchronized(_mutex){
        while(isEmpty()){
            waitForNotification();
        }
        Object value = _queue.dequeue();
        _mutex.notifyAll();
        return value;
    }
}

I see two major problems.

First, if the queue is full, 5 threads are waiting to add items, and other thread dequeue 1 item, the other 5 will be released, will check at the same time that "size() == _max_size" is not true anymore and they will try to call "_queue.enqueue" 5 times, overflowing the queue.

Second, similarly the same happens with "dequeue". If several threads are blocked trying to dequeue items because the queue is empty, adding one, will cause all of them to check that the queue is not empty anymore, and all of them will try to dequeue, getting null or an exception I guess.

Am I right? I C# there is a "Monitor.Pulse" that only releases one blocked thread, would that be the solution?

Cheers.

Even though all five of your hypothetical threads might be woken after notifyAll(), only a single thread will acquire _mutex and enter the synchronized block. The rest will go back to sleep (edit: still waiting to enter the synchronized block) — wobbals, Apr 20 '13 at 22:37
Looks like your (magic number of) 5 threads are using the same queue, so the implementation is saying to make the other objects to wait while one thread is adding or removing an element in the queue. — Luiggi Mendoza, Apr 20 '13 at 22:37
If 5 threads are blocked in "_mutex.wait()" , they are already inside the synchronized block, if I call "_mutex.notifyAll()", only one awakes? — vtortola, Apr 20 '13 at 22:43

score 1 · Accepted Answer · edited May 23 '17 at 12:12

1

You are disregarding the synchronized statement. This allows only one thread to acquire the _mutex. Consequently, only that one thread will be able to check the value of size because the while statement is within the synchronized block.

As described in this thread, the wait() method actually releases the _mutex object and waits for a call to notify(), or notifyAll() in this case. Furthermore, notifyAll() will only grant the lock on _mutex to one of the waiting threads.

edited May 23 '17 at 12:12

Community

1
1

answered Apr 20 '13 at 22:44

Zoltán

21,321
14
93
134

I see. So even when a thread is blocked in ".wait()", the synchronized statement is still blocking others from get into the "while", right? – vtortola Apr 20 '13 at 22:46
Thanks. That brought me to question the difference between "notify" and "notifyAll", but I already got the answer in SO. Cheers. – vtortola Apr 20 '13 at 23:10

Blocking queue in Java

1 Answers1