Why does java.util.concurrent.ArrayBlockingQueue use 'while' loops instead of 'if' around calls to await()?

Question

I have been playing with my own version of this, using 'if', and all seems to be working fine. Of course this will break down horribly if signalAll() is used instead of signal(), but if only one thread at a time is notified, how can this go wrong?

Their code here - check out the put() and take() methods; a simpler and more-to-the-point implementation can be seen at the top of the JavaDoc for Condition.

Relevant portion of my implementation below.

public Object get()
{
    lock.lock();
    try 
    {
        if( items.size() < 1 )
            hasItems.await();
        Object poppedValue = items.getLast();
        items.removeLast();
        hasSpace.signal();
        return poppedValue; 
    } catch (InterruptedException e) {
        e.printStackTrace();
        return null;
    } 
    finally
    {
        lock.unlock();
    }
}

public void put(Object item)
{
    lock.lock();
    try 
    {
        if( items.size() >= capacity )
            hasSpace.await();
        items.addFirst(item);
        hasItems.signal();
        return;
    } catch (InterruptedException e) {
        e.printStackTrace();
    } 
    finally
    {
        lock.unlock();
    }
}

P.S. I know that generally, particularly in lib classes like this, one should let the exceptions percolate up.

Answer 1

Perhaps missing your point, but the original code uses a while instead of if because there maybe multiple thread listening/consuming the queue...

Answer 2

To protect against spurious wake ups. There is no guarantee made to you by the JVM that the only possible reason the thread will ever start running again is because you called signal in the way you intended. Sometimes it will just get started accidentally and go (Spurious wake up). So you have to keep waiting again if the condition you want to run on isn't actually true.

This is explained in the javadoc for the wait method: http://java.sun.com/javase/6/docs/api/java/lang/Object.html#wait%28long%29

And mentioned in the docs for await: http://java.sun.com/javase/6/docs/api/java/util/concurrent/locks/Condition.html#await%28%29

The lock associated with this Condition is atomically released and the current thread becomes disabled for thread scheduling purposes and lies dormant until one of four things happens:

• Some other thread invokes the signal() method for this Condition and the current thread happens to be chosen as the thread to be awakened; or

• Some other thread invokes the signalAll() method for this Condition; or

• Some other thread interrupts the current thread, and interruption of thread suspension is supported; or

* A "spurious wakeup" occurs.

Some implementations of the Condition interface may suppress spurious wakeups, but relying on that would hence be relying on an implementation detail and makes your code unportable.

Answer 3

I believe this is the classic thread race condition in producer/consumer models and not spurious wakeups. I've written some sample code and more documentation which demonstrates the issue:

http://256.com/gray/docs/misc/producer_consumer_race_conditions/

The race is as follows:

1. thread #1, a consumer, is waiting in the while loop for there to be items in the queue
2. thread #2, a producer, locks on the queue
3. thread #3, a consumer, finishes consuming the last item, calls get(), locks on the queue, and has to wait for #2 to unlock
4. thread #2, adds an item into the queue and notifies everyone that there is an item there
5. thread #1 is awoken and goes to lock the queue, has to wait for #2 to unlock
6. thread #2 unlocks
7. thread #3 is ahead of thread #1 waiting for the lock so it locks the queue first, goes into the while loop and dequeues the item that #1 was notified for, and then unlocks
8. thread #1 now is able to lock, loops around back to the while test to see if there are items in the queue, finds out that there are none, and then goes back to waiting.

If it was just an if statement, thread #1 would find no items in the queue and NPE or something.

This is a classic issue that trips up a lot of reentrant programmers. The initial versions of the O'Reilly pthreads bible, for example, had example code without the while loop and had to be republished.

Answer 4

Another problem with your implementation is a potentially lost "signal". if you look closely at the jdk impls which handle InterruptedException, some of them signal before returning. this is because a thread could be chosen to be signalled and then end up getting interrupted, in which case that signal would be lost. thus, when interrupted, the jdk impls re-signal before bailing out. since this thread may or may not have actually been receiving a signal, this may also cause a "spurious wakeup" (as previously mentioned).