Vladimir Prus


vladimirprus.com

Wednesday, July 06, 2005

Spurious wakeups

One of the two basic synchronisation primitives in multithreaded programming is called "condition variables". Here's a small example:

bool something_happened;
boost:::mutex m;
boost:::condition c;
void thread1()
{
     boost::mutex::scoped lock(m);
     while(!something_happened)
     {
        c.wait(m);
     }
}
void thread2()
{
      // do lots of work
      boost::mutex::scoped lock(m);
      something_happened = true;
      c.notify()
}

Here, the call to "c.wait()" unlocks the mutex (allowing the other thread to eventually lock it), and suspends the calling thread. When another thread calls 'notify', the first thread wakes up, locks the mutex again (implicitly, inside 'wait'), sees that variable is set to 'true' and goes on.

But why do we need the while loop, can't we write:

if (!something_happened)
    c.wait(m);

We can't. And the killer reason is that 'wait' can return without any 'notify' call. That's called spurious wakeup and is explicitly allowed by POSIX. Essentially, return from 'wait' only indicates that the shared data might have changed, so that data must be evaluated again.

Okay, so why this is not fixed yet? The first reason is that nobody wants to fix it. Wrapping call to 'wait' in a loop is very desired for several other reasons. But those reasons require explanation, while spurious wakeup is a hammer that can be applied to any first year student without fail.

The second reason is that fixing this is supposed to be hard. Most sources I've seen say that fixing that would require very large overhead on certain architectures. Strangely, no details were ever given, which made me wonder if avoiding spurious wakeups is simple, but all the threading experts secretly decided to tell everybody it's hard.

After asking on comp.programming.thread, I at least know the reason for Linux (thanks to Ben Hutchings). Internally, wait is implemented as a call to the 'futex' system call. Each blocking system call on Linux returns abruptly when the process receives a signal -- because calling signal handler from kernel call is tricky. What if the signal handler calls some other system function? And a new signal arrives? It's easy to run out of kernel stack for a process. Exactly because each system call can be interrupted, when glibc calls any blocking function, like 'read', it does it in a loop, and if 'read' returns EINTR, calls 'read' again.

Can the same trick be used to conditions? No, because the moment we return from 'futex' call, another thread can send us notification. And since we're not waiting inside 'futex', we'll miss the notification. So, we need to return to the caller, and have it reevaluate the predicate. If another thread indeed set it to true, we'll break out of the loop.

So much for spurious wakeups on Linux. But I'm still very interested to know what the original reasons were.

9 comments:

r.o.e said...

Thanks for this post.

I've been hunting the world to find the answer while I am learning boost.thread and am wondering the why-while-instead-of-if pattern. Luckily I came to here.

It's a pity this is not in the boost.thread FAQ.

jon wayne said...
This comment has been removed by a blog administrator.
Anonymous said...

Is there a program in C to simulate spurious wakeup?

Vladimir Prus said...

Sending a signal should be sufficient to wake up a waiting thread spuriously.

Christian said...

This is fantastic!

Anonymous said...

Sending a signal should be sufficient to wake up a waiting thread spuriously.

Have you got this to work in practice? I was unable to.

AlphaStream said...

Thanks for the post! 10 years later it's still educative.

Study Crap said...

I was having this terrible "THOUGHT WORM" about this 'spurious wakeup' for long time .
Searched so much to conclude the real reason for this 'while' loop .
After reading this now i am putting the nagging irritations of this issue to rest .
Thanks for letting me find the peace :) :) .

Johannes Schaub said...
This comment has been removed by the author.