14

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.

Gray
  • 115,027
  • 24
  • 293
  • 354
kenny_k
  • 3,831
  • 5
  • 30
  • 41
  • The selected answer is a valid answer and I can testify from painful personal experience that spurious wake-ups do happen and must be protected against. But I think the answer from Gray is also valid since there would be synchronization problems with an `if` instead of a `while` even on a system without spurious wake-ups. – toto2 Nov 22 '11 at 15:02
  • 1
    I continue to be annoyed by the accepted answer. Although spurious wakeups do occur the reason why `while` loops are used is because of race conditions. This is well documented: http://sarveshspn.blogspot.com/2012/01/producer-consumer-using-while-loop.html – Gray Apr 10 '12 at 14:17

5 Answers5

21

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.

Affe
  • 47,174
  • 11
  • 83
  • 83
  • Perfect, thanks! Not sure if the Java 5 ReentrantLock.newCondition() implementation suppresses them or not, but I absolutely see your point about portability. – kenny_k Jun 02 '10 at 19:10
  • 6
    I know this is a popular answer but I feel strongly it is not the right one. Spurious wakeups I'm sure do happen but the reason why whiles are used is because of race conditions _not_ spurious wakeups. See my answer below or the page I put up about this: http://256.com/gray/docs/misc/producer_consumer_race_conditions/ – Gray Jun 15 '10 at 16:14
  • Agreed that a loop is also the solution to two threads interleaving on lock acquisition at the entrance to put() and take(). The would be concurrent Java programmer still needs to understand the JVM's inability to guarantee the semantics of wait(). Even purpose built custom implementations where one internally managed thread is the consumer, still need loops even though such a race condition is impossible. Likewise alternate ways to prevent interleaving on the lock acquisition will not be acceptable in Java without also having the loop anyway. – Affe Jun 15 '10 at 17:39
  • that answer is not exactly correct: read above: race conditions + previous (or any other) unpark. – bestsss Oct 09 '11 at 09:59
  • New URL for web page about this: http://256stuff.com/gray/docs/misc/producer_consumer_race_conditions – Gray Jul 11 '16 at 18:22
15

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

They use while instead of if to protect against the classic thread race conditions in producer/consumer models and to protect against the much more rare case of spurious wakeups.

When (for example) multiple consumers are waiting for a particular condition (like a queue is empty) and the condition gets notified, there is a chance that another thread may lock first and "steal" the item added to the queue. The while loop is necessary for the thread to make sure that the queue has an item before it tries to de-queue it.

Sample Code

I've written some sample code and more documentation which demonstrates the race condition.

Description of the Race Condition

Looking at your specific code, the race is as follows:

  1. thread #1, a consumer, is in await() in the while loop, waiting 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 (it is NOT waiting on hasItems but it is waiting to get the lock)
  4. thread #2, adds an item into the queue and calls hasItems.signal() to notify someone 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. If it was just an if statement, it would go forward and try to dequeue from an empty list which would throw ArrayIndexOutOfBoundsException or something.

The reason why the while statement is necessary is to handle these race conditions. In step 8 above, with a while, thread #1 would instead loop around back to the test to see if there are items in the queue, finds out that there are none, and then goes back to waiting.

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.

With some thread systems, it is easier for the system to awaken all conditions instead of the specific condition that has been signaled so a "spurious wakeup" can occur. The while loops protect against this as well.

Gray
  • 115,027
  • 24
  • 293
  • 354
  • Hmmm, I don't think this can happen in my implementation, as thread 2 (step 4. in your description) only notifies a single thread that there is an item in the queue, rather than everyone, so only one thread will wake up, and so one thread can't get "ahead" of another. Didn't know about the O'Reilly book, that's quite amusing :) – kenny_k Jun 02 '10 at 19:31
  • 3
    Your code still will exhibit the issue if a previous consumer is calling the get method and entering the while loop at the right time. This is _not_ about notifying multiple consumers. I suspect that a large number of the "spurious wakeup"s that people get are this sort of race condition (which is not spurious) as opposed to some OS/hardware signal issue. – Gray Jun 02 '10 at 21:37
  • Sorry if I'm being obtuse, but I'm afraid I don't see how this can happen (aside from a "spurious wakeup"), if only one consumer is awakened for a single item being placed on the queue. I believe I am correct in saying that only a single thread will perform the check at a time (the lock.lock() line that precedes it should guarantee this), so I am not sure what you mean by "entering the while loop ['if'?] at the right time". Please correct me if I am wrong. – kenny_k Jun 02 '10 at 23:03
  • It _can_ happen. Follow my enumeration above carefully. Again, it's not about 2 comsumers being awoken but about 1 being awoken and 1 calling get at the wrong time. – Gray Jun 03 '10 at 15:56
  • @theFunkyEngineer, besides races, anyone is free to call unpark and screwing the logic up and yes races a major one. – bestsss Oct 09 '11 at 10:01
  • @Gray: I think your reasoning depends on an implementation detail: In step #5 thread #1 is moved from the condition wait queue to the lock wait queue. An implementation _might choose_ to put thread #1 not at the end of the lock queue but at the very start - before thread #3. The justification could be that the waiting time of the condition queue is "credited" for the lock queue.
    I cannot find an official stipulation in the JavaDoc of `Condition` or `Lock` mandating one behaviour or the other. So we are back to square one: Use `while`, don't assume any implementation -for whatever reason.
    – A.H. Oct 17 '11 at 20:55
  • @A.H. there is info in Lock and AbstractQueuedSynchronizer (which is what impl. most of the blocking primitives in concurrent), the thread goes by the end. I have my own StackQueuedSynchronizer which is awfully unfair. Look `Object.notify()` *...for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object.* The steps above are more or less what happens in reality. But again, anyone is free to awake a thread by calling LockSupport.unpark, hence `while` is necessary (I mean truly simplistic reason) – bestsss Oct 17 '11 at 21:38
  • @bestsss The stuff in `AbstractQueuedSynchronizer` is an implementation detail. If/When Oracle decides to change the behaviour in the way I have outlined they could without breaking any written/promissed contract and eliminate _one_ (but not the only) source of "sourious wakeups". – A.H. Oct 18 '11 at 10:13
  • @A.H. Read the usage part of AbstractQueuedSynchronizer, it's well described and refers to *fair* or not. – bestsss Oct 18 '11 at 10:28
  • 1
    It's an implementation detail sure but it's also what happens typically. I deal with realities more than academics. Did you try the test application I posted? I doubt you'll find a JVM that won't exhibit that behavior. – Gray Oct 18 '11 at 12:45
  • 2
    Just a comment to clarify the answer, although it is quite clear already. Threads #1 and #3 are both consumers, but they are not symmetrical: #1 is in `await` state, but #3 is waiting for the lock at the very beginning of `get`. So when the producer sends a `signal`, __only__ #1 can be waken up, but it might be #3 that gets the lock first. If this happens, #3 processed the item first and #1 has nothing to process when it does get the lock. – toto2 Nov 22 '11 at 14:59
3

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).

james
  • 468
  • 2
  • 3
  • You are absolutely correct, thanks for pointing that out. Reading the code for ConditionObject, (which provides ReentrantLock.newCondition) shows that signal() just moves the thread from the wait queue of the condition to the wait queue of the conditions's lock - and if it's interrupted while trying to acquire that - goodbye signal. Unless, of course, some crazy person had the thread re-broadcast it ;) – kenny_k Jun 02 '10 at 22:24
0

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

Chris Kimpton
  • 5,546
  • 6
  • 45
  • 72
  • Right, so suppose the program starts, and several threads call get(), and are all put in the WAITING state. Then a producer thread calls put() - and awakens a single consumer thread by calling hasItems.signal(); the rest of the consumer threads remain as they were, until another producer thread awakens one of them again. Or am I missing something? – kenny_k Jun 02 '10 at 18:56
0

The main reason for this is that when a thread is notified it can't act right away, it has to acquire the lock first. And there is no guarantee it will be the next thread to get the lock.

When a thread receives a notification while waiting, it does not have the lock. (It released the lock when it started waiting.) Before it can leave the wait method it has to reacquire the lock. It has no priority over any other thread contending for the lock, it is entirely likely some other thread may get there first.

Whatever those intervening threads do could change the state of the object being accessed, possibly making the notification irrelevant. So once the notified thread has successfully reacquired the lock, it needs to check the condition again in order to verify that the condition that it was notified about is still actually true. The while loop is there so that the thread can check the condition again once it has the lock.

In addition to that there are other reasons to use a while loop for check that the condition you're waiting for is present:

  • It's not valid to infer from your thread having stopped waiting that it necessarily must have gotten notified; this is the "spurious wakeup".

  • Also if there are multiple things that a notification could mean, then you'd want to check the condition again in order to make sure the event you're interested in was what you were woken up for.

Nathan Hughes
  • 94,330
  • 19
  • 181
  • 276