Why do condition variables sometimes erroneously wake up?

Question

I've known for eons that the way you use a condition variable is

lock
while not task_done
  wait on condition variable
unlock

Because sometimes condition variables will spontaneously wake. But I've never understood why that's the case. In the past I've read it's expensive to make a condition variable that doesn't have that behavior, but nothing more than that.

So... why do you need to worry about falsely being woken up when waiting on a condition variable?

Nonmetallic

Answer 1

It isn't that the condition variable will erroneously wake up; the condition variable will only wake up if it has been signalled from another thread. However, it is possible that by the time the thread has been re-scheduled for execution, some other thread has already managed to nab the resource on which you were waiting, and so it is necessary to double-check. For example, if a group of threads x,y,z are waiting on some resource R that w was previously holding, and x,y,z,w communicate through a condition variable... suppose w is done with R and signals x,y,z. So, x,y, and z will all be taken off of the wait queue and placed in the runqueue to be scheduled for execution. Suppose x is scheduled first... so then it acquires R, and then it might be put to sleep, and then y might be scheduled, and so when y is running, the resource R on which y was previously waiting is still not available, so it is necessary for y to go to sleep again. Then z wakes up, and z also finds that R is still in use, so z needs to go back to sleep again, etc.

If you have exactly two threads, and the condition variable is shared between just the two of them, there are sometimes situations where it is ok to not perform that check. However, if you want to make your application dynamic and capable of scaling up to an arbitrary number of threads, then it's good to be in the habit (not to mention much simpler and less worrisome) to do that extra check as it is required in most situations.

Dunham

It's never okay to not perform the check. There is no guarantee, even with only two threads, that the condition will be true when the thread wakes up. – Paintbrush

@Nick, that is not so. If the condition is that the other thread has released the mutex associated with the condition variable (so that essentially you are alternating execution between the two threads, back and forth), then it is safe, because you cannot wakeup and reacquire the lock until the other thread has released it. Of course that isn't all that useful. – Dunham

I think you are trying to force a point that shouldnt be made. There really isnt any GOOD reason why you shouldnt recheck the the predicate. Even if the condition is shared with only two threads, there are no garuntees that the thread that is waiting wont be spuriously woken. – Objectivity

@John, I am not suggesting that one shouldn't check; to the contrary, I have stated that it makes sense to always check. However, to be technically precise, there are certain cases where the check is unnecessary. – Dunham

I think we are disagreeing for different reasons. I agree that under a normal circustance, if you have two threads that share a common condition then then you can get away with not rechecking. But when spurious wake ups can occur then there are no cases where it is unnecessary – Objectivity

Answer 2

Threads can wake up without being signaled. This is called a spurious wakeup. However, just precisely why they occur is a question that seems to be mired in superstition and uncertainty. Reasons I have seen include being a side effect of the way threading implementations work, or being intentionally added to force programmers to properly use loops instead of conditionals around wait.

Paintbrush

LOL - "being intentionally added to force programmers to properly use loops instead of conditionals around wait" - oh wait, you are kidding, right? :-) You're not! It was Apple, wasn't it?!! – Ample

@Bert F: Actually I've often wished for a version of Linux that would exercise every way that POSIX can screw with a program. Sockets would return readable from select and then have nothing to read. write would return partial results 50% of the time. condition variables would spontaneously wake. Etc. – Legge