Condition Variables and the Lost Wakeup Problem

A thread wants to wait until a queue is non-empty. The obvious code reads the queue length, finds it zero, and calls a sleep function. The producer, running in between, pushes an item and signals the sleeping thread, which has not yet gone to sleep and therefore misses the signal. The consumer then sleeps with work available, and the producer has nothing left to signal. This is the lost wakeup, and it is the reason the condition variable interface is shaped the way it is: the check and the sleep must happen while holding the same lock the producer takes to change the predicate.

The window between testing and sleeping

Every sleep interface has the same structure underneath. The caller tells the scheduler it is waiting on some address or queue, the scheduler removes it from the run queue, and later something marks it runnable. If the signal arrives between the test and the scheduler’s act of removing the thread, the signal finds no waiter and is dropped. On Linux the classic demonstration uses signals rather than threads: a process checks a flag, then calls pause(), and a SIGUSR1 delivered between the check and the call is handled before the sleep begins, so the process sleeps with the condition already satisfied. The standard remedy is to block the signal, test the flag, and then suspend with sigsuspend, which installs the old mask and sleeps in one indivisible step. Condition variables are the thread-level version of the same remedy.

The naive fix, a global “wait until signalled” flag, fails for a different reason: with two waiters, one signal wakes both or wakes the wrong one, and with one waiter the flag has to be cleared atomically with the sleep. Trying to build the pair out of a mutex and a sleep primitive leads back to the same race one level down.

The mutex is part of the interface, not an accessory

POSIX defines the wait as pthread_cond_wait(cond, mutex), taking both objects, and the specification is precise about what happens: the mutex is released atomically with respect to the wait, and reacquired before the call returns. The atomicity is the entire point. The predicate is protected by the mutex, so a producer that wants to change it must hold the mutex, and therefore cannot run between the consumer’s test and the consumer’s registration as a waiter.

The sequence inside the implementation is:

1. The waiter holds the mutex and has already evaluated the predicate as false.
2. It appends itself to the condition variable’s waiter list.
3. It releases the mutex.
4. It blocks.

Steps 2 and 3 are one indivisible operation from the point of view of any other thread holding the mutex. A signaller must hold the mutex to change the predicate, so it either runs entirely before step 1, in which case the waiter’s test sees the change and does not wait, or entirely after step 3, in which case the waiter is already on the list and the signal finds it. There is no third ordering.

#include <pthread.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  cv = PTHREAD_COND_INITIALIZER;
static struct item *head;

struct item *pop_waiting(void)
{
    pthread_mutex_lock(&m);
    while (head == NULL)                    /* always a loop, never an if */
        pthread_cond_wait(&cv, &m);         /* releases m, sleeps, reacquires */
    struct item *it = head;
    head = it->next;
    pthread_mutex_unlock(&m);
    return it;
}

void push(struct item *it)
{
    pthread_mutex_lock(&m);
    it->next = head;
    head = it;
    pthread_cond_signal(&cv);               /* one waiter may proceed */
    pthread_mutex_unlock(&m);
}

The release of the mutex inside pthread_cond_wait and the reacquisition before returning are both mandatory. A variant that returned with the mutex still released would let the caller inspect the predicate without protection; a variant that kept the mutex while sleeping would deadlock the producer.

Why the wait is a loop

The while is not defensive style. Three distinct events can end a wait without the predicate being true.

Spurious wakeups are permitted by POSIX. An implementation may return from the wait for reasons internal to itself, and a correct program must tolerate it. The permission keeps the implementation free of any obligation to match signals to returns one for one: a wakeup can be consumed early, and the broadcast path does not have to identify exactly which waiters had their predicates become true.

pthread_cond_signal unblocks at least one waiter, not exactly one, and an implementation may wake more; pthread_cond_broadcast wakes all of them. Even with signal, a wakeup intended for a specific thread cannot be directed, so the woken thread may find the item already taken by a third thread that never slept.

Barging is the third case and the most interesting. The signaller still holds the mutex when it calls pthread_cond_signal. The woken thread must reacquire the mutex before returning, and between the signal and the acquisition, a new thread can arrive and take the mutex, consume the item, and leave. The woken thread then acquires the mutex and finds nothing. The implementation chose this design because releasing the mutex inside signal would break the atomicity the interface is built on: the signaller’s predicate update and its signal must be ordered with respect to the waiter’s registration.

Because of barging, a condition variable is best understood as a hint that the predicate may now be true, not as a token that grants access. The predicate is the truth; the condition variable only avoids polling.

Signal, broadcast, and the cost of choosing wrong

The choice between the two wake operations is a correctness decision first and a performance decision second.

pthread_cond_broadcast is always safe when the predicate change may enable more than one waiter, or when different waiters wait for different predicates on the same condition variable. It is also the required choice when the predicate is a state change rather than a count of available resources, since the implementation cannot know which waiter’s predicate is now satisfiable. The cost is a thundering herd: every waiter wakes, contends for the mutex, and all but one find the predicate still false and go back to sleep. With many waiters the wakeups themselves are wasted work and the mutex becomes a bottleneck.

pthread_cond_signal is safe only when all waiters wait for the same predicate and one unit of the resource satisfies exactly one of them. A queue with one item per push qualifies. A barrier, a reader-writer transition, or a “flush completed” event does not.

A common structure that avoids the dilemma is one condition variable per predicate, or per direction of a queue. A bounded queue needs two: not-empty for consumers and not-full for producers, each signalled only by the side that can make it true. With one shared condition variable, a producer’s push might wake another producer, which finds the queue still full and sleeps again while a consumer that could have run is not woken.

Timed waits, cancellation, and the errors that are not errors

pthread_cond_timedwait takes an absolute deadline on the CLOCK_REALTIME clock by default, which means a change to the system clock can shorten or extend the wait. The pthread_condattr_setclock call can select a monotonic clock for a condition variable created with matching attributes; code that measures timeouts for anything other than wall-clock deadlines should use it. The return value ETIMEDOUT says the deadline passed, not that the predicate is false, so the loop condition is unchanged.

A thread cancelled while inside pthread_cond_wait reacquires the mutex before the cancellation is acted on, which is what lets a cleanup handler unlock it. The reacquisition happens whether the cancellation arrives while the thread is asleep or while it is waiting to reacquire the mutex after a wake, so a cleanup handler can rely on the mutex being held at the point it runs; what it cannot rely on is the predicate, which may be false. POSIX distinguishes deferred cancellation, which is the default and acts only at cancellation points such as the wait, from asynchronous cancellation, which can act anywhere and makes any cleanup logic unreliable.

Futex-based implementations on Linux add a wrinkle visible in the return value: pthread_cond_wait may return zero after a wakeup that was not a signal, and may return zero after a signal that raced with a broadcast. The predicate loop absorbs all of it.

The ordering that the mutex does not supply

A condition variable orders the predicate check against the signal, and nothing more. It does not order the contents of the data structure against the consumer’s read of them in any way beyond the mutex’s own acquire and release semantics. Since both sides take the mutex, the necessary ordering is present, but it comes from the mutex, not from the condition variable. A design that reads shared data after waking without holding the mutex has no ordering at all, which is the subject of acquire and release ordering.

The other limit is scope. A condition variable lives in memory shared by the waiting threads. Threads in different processes can share one only if it is placed in a mapping created with MAP_SHARED and initialized with a process-shared attribute; a condition variable in ordinary private memory works only within one address space. Waiting across a process boundary without shared memory requires the kernel to hold the queue, which is what futex wait and wake provides on Linux.

Finally, the pattern does not compose into a priority-aware wait. A signaller wakes whichever waiter the implementation chooses, with no regard to scheduling class, so a low-priority thread can take the resource ahead of a high-priority one that has been waiting longer. Fixing that requires the mutex to carry priority information, as described in priority inversion and inheritance.