Why does pthread_cond_wait have spurious wakeups?

Question

To quote the man page:

When using condition variables there is always a Boolean predicate involving shared variables associated with each condition wait that is true if the thread should proceed. Spurious wakeups from the pthread_cond_timedwait() or pthread_cond_wait() functions may occur. Since the return from pthread_cond_timedwait() or pthread_cond_wait() does not imply anything about the value of this predicate, the predicate should be re-evaluated upon such return.

So, pthread_cond_wait can return even if you haven't signaled it. At first glance at least, that seems pretty atrocious. It would be like a function which randomly returned the wrong value or randomly returned before it actually reached a proper return statement. It seems like a major bug. But the fact that they chose to document this in the man page rather than fix it would seem to indicate that there is a legitimate reason why pthread_cond_wait ends up waking up spuriously. Presumably, there's something intrinsic about how it works that makes it so that that can't be helped. The question is what.

Why does pthread_cond_wait return spuriously? Why can't it guarantee that it's only going to wake up when it's been properly signaled? Can anyone explain the reason for its spurious behavior?

Estren

I'd imagine it has something to do with returning whenever the process catches a signal. Most *nixes don't restart a blocking call after a signal interrupts it; they just set/return an error code that says a signal occurred. – Ridgeway

@cHao: although note that because condition variables have other reasons for spurious wake-ups anyway, handling a signal isn't an error for pthread_cond_(timed)wait: "If a signal is delivered ... the thread resumes waiting for the condition variable as if it was not interrupted, or it shall return zero due to spurious wakeup". Other blocking functions indicate EINTR when interrupted by a signal (e.g. read), or are required to resume (e.g. pthread_mutex_lock). So if there were no other reasons for spurious wake-up, pthread_cond_wait could have been defined like either of those. – Getupandgo

A related article on Wikipedia: Spurious wakeup – Poacher

Useful Vladimir Prus: Spurious Wakeups. – Enroll

Many functions can not do fully their job completely (interrupted I/O) and observing functions can receive non event like a change to a directory where the change was cancelled or reverted back. What's the problem? – Bordy

Related: Software Engineering - Spurious wakeups explanation sounds like a bug that just isn't worth fixing, is that right? – Trejo

Answer 1

The following explanation is given by David R. Butenhof in "Programming with POSIX Threads" (p. 80):

Spurious wakeups may sound strange, but on some multiprocessor systems, making condition wakeup completely predictable might substantially slow all condition variable operations.

In the following comp.programming.threads discussion, he expands on the thinking behind the design:

Patrick Doyle wrote: 
> In article , Tom Payne   wrote: 
> >Kaz Kylheku  wrote: 
> >: It is so because implementations can sometimes not avoid inserting 
> >: these spurious wakeups; it might be costly to prevent them. 

> >But why?  Why is this so difficult?  For example, are we talking about 
> >situations where a wait times out just as a signal arrives? 

> You know, I wonder if the designers of pthreads used logic like this: 
> users of condition variables have to check the condition on exit anyway, 
> so we will not be placing any additional burden on them if we allow 
> spurious wakeups; and since it is conceivable that allowing spurious 
> wakeups could make an implementation faster, it can only help if we 
> allow them. 

> They may not have had any particular implementation in mind. 

You're actually not far off at all, except you didn't push it far enough. 

The intent was to force correct/robust code by requiring predicate loops. This was 
driven by the provably correct academic contingent among the "core threadies" in 
the working group, though I don't think anyone really disagreed with the intent 
once they understood what it meant. 

We followed that intent with several levels of justification. The first was that 
"religiously" using a loop protects the application against its own imperfect 
coding practices. The second was that it wasn't difficult to abstractly imagine 
machines and implementation code that could exploit this requirement to improve 
the performance of average condition wait operations through optimizing the 
synchronization mechanisms. 
/------------------[ [email protected] ]------------------\ 
| Compaq Computer Corporation              POSIX Thread Architect | 
|     My book: http://www.awl.com/cseng/titles/0-201-63392-2/     | 
\-----[ http://home.earthlink.net/~anneart/family/dave.html ]-----/ 

Lorica

basically this says nothing. No explanation is given here other than the initial thought that "it may make things faster" but nobody knows how or if it does at all. – Snowinsummer

Has anyone figured out a source that explains why this might make things faster? Sure, "mathematically" having more freedom means it can't be any slower, but is anyone utilising this? – Ginoginsberg

Answer 2

There are at least two things 'spurious wakeup' could mean:

• A thread blocked in pthread_cond_wait can return from the call even though no call to pthread_cond_signal or pthread_cond_broadcast on the condition occurred.
• A thread blocked in pthread_cond_wait returns because of a call to pthread_cond_signal or pthread_cond_broadcast, however after reacquiring the mutex the underlying predicate is found to no longer be true.

But the latter case can occur even if the condition variable implementation does not allow the former case. Consider a producer consumer queue, and three threads.

• Thread 1 has just dequeued an element and released the mutex, and the queue is now empty. The thread is doing whatever it does with the element it acquired on some CPU.
• Thread 2 attempts to dequeue an element, but finds the queue to be empty when checked under the mutex, calls pthread_cond_wait, and blocks in the call awaiting signal/broadcast.
• Thread 3 obtains the mutex, inserts a new element into the queue, notifies the condition variable, and releases the lock.
• In response to the notification from thread 3, thread 2, which was waiting on the condition, is scheduled to run.
• However before thread 2 manages to get on the CPU and grab the queue lock, thread 1 completes its current task, and returns to the queue for more work. It obtains the queue lock, checks the predicate, and finds that there is work in the queue. It proceeds to dequeue the item that thread 3 inserted, releases the lock, and does whatever it does with the item that thread 3 enqueued.
• Thread 2 now gets on a CPU and obtains the lock, but when it checks the predicate, it finds that the queue is empty. Thread 1 'stole' the item, so the wakeup appears to be spurious. Thread 2 needs to wait on the condition again.

So since you already always need to check the predicate under a loop, it makes no difference if the underlying condition variables can have other sorts of spurious wakeups.

Backing

yes. Essentialy, this is what happens when an event is used instead of a synchronization mechanism with a count. Sadly, it appears that POSIX semaphores, (on Linux anyway), are subject to spurius wakeups as well. I just find it a bit strange that a fundamental functionality failure of synchronization primitives is just accepted as 'normal' and has to be worked around at user-level :( Presumably, developers would be up-in-arms if a system call was documented with a 'Spurious segfault' section or, perhaps 'Spurious connecting to the wrong URL' or 'Spurious opening of the wrong file'. – Giesser

The more common scenario of a "spurious wakeup" is most likely the side-effect of a call to pthread_cond_broadcast(). Let's say you have a pool of 5 threads, two wake up to the broadcast and do the work. The other three wake up and find the work has been done. Multi-processor systems can also result in a conditional signal waking up multiple threads by accident. The code just checks the predicate again, sees an invalid state, and goes back to sleep. In either case, checking the predicate solves the problem. IMO, in general, users shouldn't use raw POSIX mutexes and conditionals. – Gaines

@MartinJames - How about the classic "spurious" EINTR? I will agree that constantly testing for EINTR in a loop is a tad annoying and makes code rather ugly but developers do it anyway to avoid random breakages. – Gaines

The condition/predicate can become false just after you have checked it. – Acidosis

@Acidosis No it can't, because you are supposed to lock a mutex around the pthread_cond_signal/broadcast and you won't be able to do so, until the mutex is unlocked by calling pthread_cond_wait. – Jonjona

This answer's example is very realistic and I agree that checking predicates is a good idea. However, couldn't it be fixed equally soundly by taking the problematic step "thread 1 completes its current task, and returns to the queue for more work" and replacing it with "thread 1 completes its current task, and goes back to waiting on the condition variable"? That would eliminate the failure mode described in the answer, and I'm pretty sure it would make the code correct, in the absence of spurious wakeups. Is there any actual implementation that produces spurious wakeups in practice? – Mise

@Mise - No, that doesn't work, for two reasons. First, condition variables are not level triggered - they are edge triggered. So if thread 1 started unconditionally waiting after thread 3 called notify, it won't be woken up from the wait to process the item thread 3 enqueued. And even if the prior reason somehow didn't apply, you don't want to introduce the latency of waiting and awaking just to dequeue the next work item if it is already present. The "item already present" case should be your fast path. You only want to enter the condvar wait path (slow path) if there is nothing to do. – Backing

@acm: My "fix" assumes that there are only as many notifies, in total, as there are threads coming in to grab work items. For example if we're using this merely to indicate "hey thread B, thread A is done and ready for you to start working!" Agreed it's not a performant (or maybe even correct/useful) idea for work queues in general. But since yesterday I've found a way to get spurious wakeups on Linux: kill -19 <pid>; kill -18 <pid> will spurious-wakeup all futexes in the target process. So it's moot; spurious wakeups are indeed real and therefore the loop is 100% needed even in my case. – Mise

@Mise Yup, no getting around the loop. This in fact is why the C++ std::condition_variable allows you to pass in a lambda to describe the predicate. That entry point will automatically evaluate the lambda in a loop until the predicate is met. That way, you can't use it wrong. – Backing

If your code is written well, spurious wakeups are not a problem. If it's written badly, it will crash with or without them. – Vainglory

Thanks for the answer. But is this really a "spurious" wakeup? The above scenario is just a normal course of execution when contending for a lock. The source of the wakeup is not false, fake, unknown, mysterious, or otherwise spurious; another thread simply grabbed the lock first. – Manzanilla

@Manzanilla - That's a reasonable way to look at it, but my essential point was that since this normal course of execution can (and therefore does) happen, you must recheck the predicate anyway. Therefore it doesn't matter whether there may be other, and perhaps genuinely spurious, causes of wakeup; you must act as if there are. And, since the user of the condvar must act as if spurious wakeups are a real possibility, an implementation is free to in fact allow or cause them, should doing so prove advantageous. Whether any do is a separate question, but the answer seems effectively irrelevant. – Backing

@Mise “My ‘fix’ assumes that there are only as many notifies, in total, as there are threads coming in to grab work items.” That’s not how it works. Imagine a queue that can take up to at least three elements, implementing the necessary wait and notify and three producers and consumers. Then, you can have a sequence “pop, push, pop, push, pop, push”, having every consumer needing to wait for the “non-empty” condition and every producer notifying. But what about “push, push, push, pop, pop, pop”. Now, only one thread signals “non-empty”, so waiting without pre-checking would deadlock. – Thoughtless

@Thoughtless There is another "fix" where a consumer "pre-decreases" the counter representing the number of work items available, even if that makes it go negative. A producer notifies iff the counter was negative before the producer increases it. This way another consumer not waiting on the condvar couldn't grab the work item because the counter would still be 0. I believe this would be a correct implementation of a semaphore if spurious wakeups did not exist. – Benildis

Answer 3

Section "Multiple Awakenings by Condition Signal" in pthread_cond_signal has an example implementation of pthread_cond_wait and pthread_cond_signal which involves spurious wakekups.

Gwin

I think this answer is wrong, as far as it goes. The sample implementation on that page has an implementation of "notify one" which is equivalent to "notify all"; but it doesn't seem to generate actually spurious wakeups. The only way for a thread to wake up is by some other thread invoking "notify all", or by some other thread invoking the-thing-labeled-"notify one"-which-is-really-"notify all". – Mise

@Mise 1. The example is from the "POSIX Programmer's Manual" which is probably right about what it says. The able_to_run(sleeper); which wakes up the head element of cond->waiter queue. value == cond->value fails, so the interrupted thread which has not been put into the queue (i.e. not runs cond->waiter = me;) also wakes up after pthread_mutex_unlock(cond->mutex); /* 12 */. Then spurious wakeups occur. – Diacritic

Answer 4

While I don't think it was considered at the time of design, here is an actual technical reason: In combination with thread cancellation, there are conditions under which taking the option to wake "spuriously" may be absolutely necessary, at least unless you're willing to impose very very strong constraints on what sort of implementation strategies are possible.

The key problem is that, if a thread acts on cancellation while blocked in pthread_cond_wait, the side effects must be as if it did not consume any signal on the condition variable. However, it's difficult (and highly constraining) to ensure that you have not already consumed a signal when you begin acting on cancellation, and at this stage it may be impossible to "re-post" the signal to the condition variable, since you may be in a situation where the caller of pthread_cond_signal is already justified to have destroyed the condvar and freed the memory in which it resided.

The allowance for spurious wake gives you an easy out. Instead of continuing to act on cancellation when it arrives while blocked on a condition variable, if you may have already consumed a signal (or if you want to be lazy, no matter what), you can declare a spurious wake to have happened instead, and return with success. This does not interfere at all with the operation of cancellation, because a correct caller will simply act on the pending cancellation the next time it loops and calls pthread_cond_wait again.

Araxes

Answer 5

I think a major cause of spurious wakeups is EINTR.

EINTR Interrupted function call (POSIX.1-2001); see signal(7).

^{source: https://man7.org/linux/man-pages/man3/errno.3.html}

Basically the system call that is invoked by e.g., pthread_cond_wait(), for example futex(2), may return with EINTR. This typically happens if a system call, which blocked in the kernel, was interrupted by a POSIX signal (see signal(7)). Refer to "What is the rationale behind EINTR?" on unix.stackexchange.com why (some) operating systems return EINTR if a system call was interrupted after a POSIX signal was delivered and handled by the system-call issuing thread.

I assume there is a potential race condition once the low-level operating system primitive, used to implement, e.g., pthread_cond_wait() returns EINTR. The implementation of pthread_cond_wait() may not simply re-issue the system call, as the condition may now hold. If the condition is not re-evaluated after EINTR, then this could easily lead to a deadlock where the application makes no further progress.

Trejo

Answer 6

The acm's example is similar to "Figure 30.9" in ostep threads-cv book where the problem is that the scheduler will make the wake-up thread run after another scheduled consumer.

But "also handles the case where spurious wakeups occur" in ostep threads-cv p14 says it is not totally same as the spurious wakeup. From man 3 pthread_cond_broadcast, the definition of spurious wakeup "more than one thread can return" is not reflected in the acm's example (i.e. "Thread 2 needs to wait on the condition again" implies only one thread is wake-up), so ostep thinks it is not one spurious wakeup.

---

Details about the man 3 pthread_cond_broadcast's example which can be complement of Jingguo Yao's answer. Also see my comment above in the Jingguo Yao's answer.

IMHO, this example implementation may be just for representation which seems to be weird because it will continue running after being interrupted and cond->value changed instead of waiting.

As NPE's answer says, the implementation is chosen purposefully for simplification. IMHO this is due to taking Mesa style in account which is also said in OSTEP book. "Mesa style" implies using the while to recheck the condition after wakeup, so it is maybe redundant to avoid spurious wakeups inside the pthread_cond_wait and pthread_cond_signal. "users of condition variables have to check the condition on exit anyway" in the NPE's answer also implies the while() outside the pthread_cond_wait which is thought as one convention of using the pthread_cond_wait.

Diacritic