178

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?

Jonathan M Davis
  • 37,181
  • 17
  • 72
  • 102
  • 6
    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. – cHao Dec 21 '11 at 18:34
  • 1
    @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. – Steve Jessop Dec 21 '11 at 19:09
  • 5
    A related article on Wikipedia: [Spurious wakeup](http://en.wikipedia.org/wiki/Spurious_wakeup) – Palec Jan 07 '15 at 22:51
  • 5
    Useful [Vladimir Prus: Spurious Wakeups](http://blog.vladimirprus.com/2005/07/spurious-wakeups.html). – iammilind Aug 03 '15 at 11:24
  • 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? – curiousguy Jun 22 '19 at 21:09
  • Related: [Software Engineering - Spurious wakeups explanation sounds like a bug that just isn't worth fixing, is that right?](https://softwareengineering.stackexchange.com/questions/186842) – Flow Apr 22 '20 at 10:00

5 Answers5

140

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.

mateusazis
  • 43
  • 4
acm
  • 12,183
  • 5
  • 39
  • 68
  • 33
    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'. – Martin James Dec 22 '11 at 11:07
  • 6
    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. – CubicleSoft May 23 '16 at 09:40
  • 1
    @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. – CubicleSoft May 23 '16 at 09:42
  • The condition/predicate can become false just after you have checked it. – Yola Nov 23 '16 at 10:22
  • 3
    @Yola 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`. – a3f Dec 13 '16 at 19:51
  • 1
    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? – Quuxplusone Jul 04 '17 at 01:20
  • 2
    @Quuxplusone - 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. – acm Jul 04 '17 at 19:24
  • 2
    @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 ; kill -18 ` 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. – Quuxplusone Jul 05 '17 at 06:27
  • 2
    @Quuxplusone 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. – acm Jul 05 '17 at 17:21
  • 1
    If your code is written well, spurious wakeups are not a problem. If it's written badly, it will crash with or without them. – ed22 Nov 24 '19 at 08:55
  • 1
    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. – Josh Jan 18 '21 at 17:17
  • 1
    @Josh - 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. – acm Jan 18 '21 at 20:59
  • 1
    @Quuxplusone “*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. – Holger Jun 17 '21 at 16:21
84

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. 
/------------------[ David.Buten...@compaq.com ]------------------\ 
| 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 ]-----/
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • 54
    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. – Bogdan Ionitza Jan 10 '19 at 12:26
7

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.

Jingguo Yao
  • 7,320
  • 6
  • 50
  • 63
  • 2
    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". – Quuxplusone Jul 04 '17 at 01:16
7

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.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
1

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.

Flow
  • 23,572
  • 15
  • 99
  • 156