Why does pthread_cond_wait have spurious wakeups

cpthreads

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?

Best Answer

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_call_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.

Related Solutions

With arrays, why is it the case that a[5] == 5[a]

The C standard defines the [] operator as follows:

a[b] == *(a + b)

Therefore a[5] will evaluate to:

*(a + 5)

and 5[a] will evaluate to:

*(5 + a)

a is a pointer to the first element of the array. a[5] is the value that's 5 elements further from a, which is the same as *(a + 5), and from elementary school math we know those are equal (addition is commutative).

What does “static” mean in C

A static variable inside a function keeps its value between invocations.
A static global variable or a function is "seen" only in the file it's declared in

(1) is the more foreign topic if you're a newbie, so here's an example:

#include <stdio.h>

void foo()
{
    int a = 10;
    static int sa = 10;

    a += 5;
    sa += 5;

    printf("a = %d, sa = %d\n", a, sa);
}


int main()
{
    int i;

    for (i = 0; i < 10; ++i)
        foo();
}

This prints:

a = 15, sa = 15
a = 15, sa = 20
a = 15, sa = 25
a = 15, sa = 30
a = 15, sa = 35
a = 15, sa = 40
a = 15, sa = 45
a = 15, sa = 50
a = 15, sa = 55
a = 15, sa = 60

This is useful for cases where a function needs to keep some state between invocations, and you don't want to use global variables. Beware, however, this feature should be used very sparingly - it makes your code not thread-safe and harder to understand.

(2) Is used widely as an "access control" feature. If you have a .c file implementing some functionality, it usually exposes only a few "public" functions to users. The rest of its functions should be made static, so that the user won't be able to access them. This is encapsulation, a good practice.

Quoting Wikipedia:

In the C programming language, static is used with global variables and functions to set their scope to the containing file. In local variables, static is used to store the variable in the statically allocated memory instead of the automatically allocated memory. While the language does not dictate the implementation of either type of memory, statically allocated memory is typically reserved in data segment of the program at compile time, while the automatically allocated memory is normally implemented as a transient call stack.

And to answer your second question, it's not like in C#.

In C++, however, static is also used to define class attributes (shared between all objects of the same class) and methods. In C there are no classes, so this feature is irrelevant.

Best Answer

Related Solutions

With arrays, why is it the case that a[5] == 5[a]

What does “static” mean in C

Related Topic