Sunday, June 30, 2013

Rude Awakenings

Here's a piece of esoterica. The java.util.concurrent.locks.Condition mentions that "a Condition should always be waited upon in a loop, testing the state predicate that is being waited for." This can be because of spurious wake-ups. But what are these?

"On some implementations, a thread waiting on a condition variable may be woken up even though no other thread actually signalled the condition variable. Such spurious wake-ups are a (rare) consequence of the technique required for efficient implementation on some multiprocessor systems, and are explicitly permitted by SUSv3".
Linux Programming Interface, Michael Kerrisk

(SUS is the Single Unix Specification.)

"If the state [of the task] is set to TASK_INTERRUPTIBLE, a signal wakes the process up. This is called a spurious wake up (a wake-up not caused by the occurrence of the event)"
- Linux Kernel Development, Rob Love

Even if we didn't have this rare edge case, we should still spin on the condition that put a thread into a waiting state. If we take the code in the Condition JavaDoc, make the BoundedBuffer only have a capacity of 1 and then have multiple threads adding and removing objects from it, you'll see many occasions where the thread woke up erroneously (about 1% of the time when I measured it). This is (probably) due to some other thread changing the state of the BoundedBuffer after the waiting thread was signalled to wake but before it actually got chance to run.

This is not limited to Linux. "There is no guarantee around when a thread that has been awakened will become scheduled. Condition variables are not fair. It's possible - and even likely - that another thread will acquire the associated lock and make the condition false again before the awakened thread has a chance to reacquire the lock and return to the critical region." - Concurrent Programming On Windows, Joe Duffy [1]

One final aside: when awaiting on a Condition, the calling thread is added to a linked list stored in the Condition. If the signal method is called before this event, the thread will never know of it. That is to say, signal events are not stored for later.

[1] Quoted in a comment in Stack Overflow.

No comments:

Post a Comment