Condition Variables

01 Introduction

Lesson 6.5 introduced the condition variable as the mechanism a monitor uses to wait for a condition. This lesson examines the condition variable in its own right, as a primitive that can be used directly with a mutex. The condition variable is not an alternative to the lock; it is a companion to it. The lock provides mutual exclusion — one thread at a time inside the critical section. The condition variable provides waiting — a way for a thread to leave the critical section, sleep until a condition becomes true, and then re-enter it.

Why is a separate primitive needed? Consider what happens if a thread wants to wait for a condition while holding a lock. If it simply spins in a loop inside the critical section, checking the condition repeatedly, then it holds the lock the entire time and no other thread can change the state to make the condition true. The thread deadlocks itself. If it releases the lock and then spins, another thread can change the state, but the waiting thread is burning CPU cycles and — worse — it is not holding the lock, so the check it just did may be stale by the time it acquires the lock again. Neither approach works.

The condition variable solves the problem by providing a single atomic operation, wait, that releases the lock and blocks in one indivisible step. When the thread is later woken by a signal, it re-acquires the lock before returning. From the thread's point of view, it acquired the lock, tested the condition, waited, and then woke up still holding the lock — with the condition possibly true, possibly false, and the lock correctly held either way. The atomicity of the release-and-block and the re-acquire is what makes the abstraction work.

This lesson presents the condition variable in full detail. It defines the three operations — wait, signal, and broadcast — and explains why each is necessary. It presents the loop-around-wait pattern, which is the canonical way to use a condition variable correctly, and explains why the loop is required by Mesa semantics and spurious wakeups. It presents the POSIX interface, pthread_cond_t, with its wait, timedwait, signal, and broadcast operations. It shows the producer–consumer, reader–writer, and barrier solutions built on condition variables, and it examines the pitfalls that make this primitive easy to misuse.

02 Learning objectives

This lesson contributes to U6.3, U6.4, and U6.5, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

• OSTEP — Chapter 30, Condition Variables. The clearest available treatment of the condition variable as a primitive. OSTEP builds up from the problem to the interface, and its discussion of the producer–consumer and its variants is the basis for the worked example in this lesson.
• Operating System Concepts — Chapter 6, Section 6.7, Monitors. The condition variable as part of the monitor abstraction, with the producer–consumer example.
• Butenhof, D. R. — Programming with POSIX Threads, Chapter 4, Condition Variables. The definitive reference for the POSIX condition variable. Read the sections on the "wait" semantics, the "signal" semantics, and the "waiting for the state to change" pattern.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.3.7, Monitors. The condition variable in the historical context of the monitor.
• Linux man pages: man 3 pthread_cond_init, man 3 pthread_cond_wait, man 3 pthread_cond_timedwait, man 3 pthread_cond_signal, man 3 pthread_cond_broadcast, man 3 pthread_cond_destroy.

04 Core content

4.1 The condition variable abstraction

A condition variable is an object associated with a particular condition on shared state. It provides three operations:

wait(c, m)

Atomically release the mutex m and block the calling thread on the condition variable c. When the thread is woken by a signal or broadcast, it re-acquires m before returning from wait. The release of the mutex and the block are one indivisible operation; the re-acquisition is also part of the operation and happens before wait returns.

signal(c)

Wake one thread waiting on c, if any. If no thread is waiting, the signal has no effect — it is lost. This is different from a semaphore's post, which increments a value that a later wait finds.

broadcast(c) (or notify_all)

Wake all threads waiting on c, if any. Each of them re-checks its condition after re-acquiring the mutex.

The condition variable has no value. It is a queue of waiting threads, nothing more. The condition it is associated with is a property of the shared state that the mutex protects; the condition variable is only the mechanism for waiting until that property changes.

This absence of state is the essential distinction between a condition variable and a semaphore. A semaphore's value is the number of pending signals. A condition variable's signal is not "remembered": if no thread is waiting at the moment of the signal, the signal disappears. The consequence is that a condition variable must be used with a mutex that protects a state variable indicating whether the condition holds. The thread that signals changes the state before signalling; the thread that waits checks the state after waking.

4.2 Why a mutex is required

A condition variable is always used with a mutex. The mutex serves two purposes.

• It protects the shared state. The condition is a property of some shared variable — a count, a flag, a queue's length — that can be read and written by multiple threads. The mutex ensures that these accesses are mutually exclusive, so that the condition check and the state change are consistent.
• It makes the check-and-wait sequence atomic. A thread that checks the condition and then calls wait must not have another thread change the state between the check and the wait. The mutex ensures this: the check happens inside the critical section, and the wait releases the mutex only as part of the atomic release-and-block operation.

The wait operation's atomicity is the key. It does two things — release the mutex, and add the thread to the wait queue — as one indivisible step. If the release and the block were separate, a signal could arrive between them and be lost, because the signalling thread would see an empty queue and return without waking anyone, and then the waiting thread would block forever. The atomic release-and-block eliminates this race.

For the same reason, the wait operation re-acquires the mutex before returning. When a waiting thread is woken by a signal, it must not simply resume with the mutex released — the state it is about to read may not be consistent, and the thread needs the same mutual exclusion it had before. The re-acquisition guarantees that the woken thread holds the mutex as soon as wait returns.

4.3 The loop-around-wait pattern

The canonical way to use a condition variable is the loop-around-wait pattern:

lock(mutex);
while (!condition) {
    wait(cond, mutex);
}
/* The condition is true. Use the state. */
unlock(mutex);

The while loop is essential, and it is the most important rule of condition variable programming. There are three reasons a single if is not sufficient.

• Mesa semantics. The signal wakes a thread but does not transfer control to it immediately. Between the signal and the woken thread's re-acquisition of the mutex, other threads may enter the critical section and change the state, so the condition may no longer be true. The woken thread must re-check the condition before proceeding.
• Spurious wakeups. A condition variable is permitted to wake a waiting thread without any signal or broadcast having occurred. This is allowed by POSIX and by every condition variable implementation, for reasons that range from implementation details of the underlying wait mechanism to the handling of signals. A while loop handles spurious wakeups correctly: the thread re-checks the condition, finds it still false, and waits again.
• Multiple waiters. When several threads are waiting on the same condition and a broadcast wakes them all, only one may be able to proceed. The others re-check, find the condition false, and wait again. Without a while loop, every woken thread would proceed, and several would operate on invalid state.

4.4 Signal versus broadcast

The condition variable provides two wakeup operations, and the choice between them affects both correctness and performance.

In the producer–consumer problem, one inserted item allows exactly one consumer to remove it, so signal is correct and more efficient. In the dining philosophers problem, a philosopher putting down their forks may allow either of two neighbours to pick up a fork — and the signaller does not know which of them will succeed — so broadcast is the appropriate choice.

A broadcast is always safe: it wakes more threads than necessary, but each re-checks its condition and goes back to sleep if the condition is still false. Its cost is the wasted wakeups. Each wakeup involves a context switch and a re-acquisition of the mutex, and on a system with many waiters this can dominate the useful work. The rule is to use signal when the condition is specific and to reserve broadcast for the cases where the condition is general.

4.5 The POSIX interface

The POSIX condition variable is pthread_cond_t, declared in <pthread.h>. Its operations are:

int pthread_cond_init(pthread_cond_t *cond,
                      const pthread_condattr_t *attr);
int pthread_cond_destroy(pthread_cond_t *cond);

int pthread_cond_wait(pthread_cond_t *cond,
                      pthread_mutex_t *mutex);
int pthread_cond_timedwait(pthread_cond_t *cond,
                           pthread_mutex_t *mutex,
                           const struct timespec *abstime);

int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);

The interface has several features worth noting.

• The mutex is an argument to wait. pthread_cond_wait takes both the condition variable and the mutex. This is what allows the function to release the mutex and block on the condition variable in one atomic step. The caller must hold the mutex when calling wait; if it does not, the behaviour is undefined.
• pthread_cond_timedwait. The timed variant takes an absolute time (not a relative duration) at which the wait should time out. If the timeout elapses before a signal, the function returns ETIMEDOUT and the caller must re-check the condition — the wait may have returned for a timeout rather than a signal.
• Return value. All POSIX condition variable functions return an error code directly, as with the rest of pthreads. They do not set errno.
• Process-shared attribute. By default, a condition variable is shared only between threads of the same process. Setting PTHREAD_PROCESS_SHARED allows it to be shared between processes that share memory.
• Clock attribute. A condition variable can be configured to use CLOCK_MONOTONIC or CLOCK_REALTIME for its timed wait. The default on most systems is CLOCK_REALTIME, which is subject to adjustments for daylight saving and for time synchronization; CLOCK_MONOTONIC is preferable for measuring intervals.

4.6 Producer–consumer with condition variables

The bounded-buffer producer–consumer problem is solved with one mutex and two condition variables:

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  not_full  = PTHREAD_COND_INITIALIZER;
pthread_cond_t  not_empty = PTHREAD_COND_INITIALIZER;

int buffer[N];
int in = 0, out = 0, count = 0;

void insert(int item) {
    pthread_mutex_lock(&mutex);
    while (count == N)
        pthread_cond_wait(&not_full, &mutex);
    buffer[in] = item;
    in = (in + 1) % N;
    count++;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&mutex);
}

int remove(void) {
    pthread_mutex_lock(&mutex);
    while (count == 0)
        pthread_cond_wait(&not_empty, &mutex);
    int item = buffer[out];
    out = (out + 1) % N;
    count--;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&mutex);
    return item;
}

The structure is the classic monitor pattern. The mutex protects the buffer's state; the two condition variables handle the two conditions — "buffer is not full" and "buffer is not empty". The insert procedure waits on not_full until there is a free slot, inserts the item, and signals not_empty to wake a waiting consumer. The remove procedure is the mirror image.

The two condition variables are necessary because the conditions they represent are different. A single condition variable would not distinguish between a producer waiting for a free slot and a consumer waiting for an item; a signal on the shared variable might wake the wrong kind of thread. The two variables keep the waiters separate and allow a targeted signal.

4.7 Reader–writer with condition variables

The reader–writer problem can also be solved with condition variables. The following solution gives writers priority, to avoid the writer-starvation problem of the reader-preferring semaphore solution from Lesson 6.4.

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  can_read  = PTHREAD_COND_INITIALIZER;
pthread_cond_t  can_write = PTHREAD_COND_INITIALIZER;

int readers = 0;
int writers = 0;
int waiting_writers = 0;

void reader_enter(void) {
    pthread_mutex_lock(&mutex);
    while (writers > 0 || waiting_writers > 0)
        pthread_cond_wait(&can_read, &mutex);
    readers++;
    pthread_mutex_unlock(&mutex);
}

void reader_exit(void) {
    pthread_mutex_lock(&mutex);
    readers--;
    if (readers == 0)
        pthread_cond_signal(&can_write);
    pthread_mutex_unlock(&mutex);
}

void writer_enter(void) {
    pthread_mutex_lock(&mutex);
    waiting_writers++;
    while (readers > 0 || writers > 0)
        pthread_cond_wait(&can_write, &mutex);
    waiting_writers--;
    writers++;
    pthread_mutex_unlock(&mutex);
}

void writer_exit(void) {
    pthread_mutex_lock(&mutex);
    writers--;
    if (waiting_writers > 0)
        pthread_cond_signal(&can_write);
    else
        pthread_cond_broadcast(&can_read);
    pthread_mutex_unlock(&mutex);
}

The solution uses the waiting_writers counter to give writers priority: a reader that arrives while a writer is waiting must wait, even if no writer is currently active. This prevents the writer from being starved by a continuous stream of readers. When a writer exits, it signals another waiting writer if there is one, or broadcasts to the readers if there is not.

The final broadcast to the readers is necessary because the condition that has become true — no writers active — may allow more than one reader to proceed. A signal would wake only one reader, which is correct but would require the woken reader to signal the next reader when it exits, and so on. The broadcast wakes all of them at once, which is simpler.

4.8 Barrier with condition variables

A barrier is a rendezvous point at which a fixed number of threads must arrive before any of them can proceed. It is useful for iterative algorithms — numerical simulations that advance in time steps, for example — where every thread must finish one phase before any begins the next.

A barrier can be built from a mutex, a condition variable, a count, and a generation number:

typedef struct {
    pthread_mutex_t mutex;
    pthread_cond_t  cond;
    int             count;        /* threads still to arrive */
    int             generation;   /* to distinguish successive uses */
    int             total;        /* total number of threads */
} barrier_t;

void barrier_wait(barrier_t *b) {
    pthread_mutex_lock(&b->mutex);
    int gen = b->generation;
    b->count--;
    if (b->count == 0) {
        /* Last to arrive: release everyone */
        b->generation++;
        b->count = b->total;
        pthread_cond_broadcast(&b->cond);
    } else {
        while (gen == b->generation)
            pthread_cond_wait(&b->cond, &b->mutex);
    }
    pthread_mutex_unlock(&b->mutex);
}

The generation counter distinguishes one use of the barrier from the next. A thread that waits on the barrier records the current generation and waits until the generation changes. The last thread to arrive increments the generation and broadcasts, releasing all the waiters. Without the generation counter, a thread that arrives at the barrier a second time might be confused with a thread from the previous use — a classic bug in naive barrier implementations.

4.9 Condition variables versus semaphores

Both a condition variable and a semaphore can be used to wait for an event. They are not interchangeable, and choosing the wrong one makes a program either harder to understand or incorrect.

The essential distinction is the state. A semaphore has state in its value, so a post before a wait is not lost. A condition variable has no state, so its use must be paired with a shared variable that does. The while loop that re-checks the condition is the price of this absence of state: every wakeup must be verified against the state variable, because the signal itself carries no information about whether the condition is true.

The general guidance is: use a condition variable when the problem is to wait for a condition on state protected by a mutex. Use a semaphore when the problem is to count resources or to signal a one-shot event. The producer–consumer problem can be solved with either; the condition variable solution is more natural in a lock-based design, and the semaphore solution is more natural in a design without an explicit lock.

4.10 Common pitfalls

05 Worked example

The following example traces the producer–consumer solution through a sequence of operations, showing the state of the mutex, the two condition variables, and the buffer at each step. It also demonstrates the failure mode of the if-instead-of-while bug.

int remove_buggy(void) {
    pthread_mutex_lock(&mutex);
    if (count == 0)
        pthread_cond_wait(&not_empty, &mutex);
    /* BUG: count may still be 0 */
    int item = buffer[out];
    out = (out + 1) % N;
    count--;            /* count goes negative */
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&mutex);
    return item;
}

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• A condition variable is an object used together with a mutex to allow a thread to wait for a condition to become true. It has three operations: wait, signal, and broadcast.
• wait(c, m) atomically releases the mutex m, blocks the calling thread on c, and re-acquires m before returning when the thread is woken. The atomicity of the release-and-block and the re-acquire is what makes the primitive work.
• A condition variable has no memory: a signal that arrives when no thread is waiting is lost. This is why it must be used with a state variable that indicates whether the condition holds, and why every wait must be wrapped in a loop that re-checks the state.
• The loop-around-wait pattern is essential: the wait must be inside a while loop that re-checks the condition after every wakeup. This is required by Mesa semantics, by spurious wakeups, and by the possibility of multiple waiters.
• signal wakes one waiter and is appropriate when the condition allows exactly one thread to proceed. broadcast wakes all waiters and is required when the condition may allow more than one to proceed, or when the signaller does not know which can proceed.
• The POSIX interface is pthread_cond_t with pthread_cond_init, pthread_cond_wait, pthread_cond_timedwait, pthread_cond_signal, pthread_cond_broadcast, and pthread_cond_destroy. The mutex is passed to wait as an argument.
• The producer–consumer problem is solved with one mutex and two condition variables: not_full for producers and not_empty for consumers. Two condition variables are necessary to target the signal to the right kind of waiter.
• The reader–writer problem can be solved with condition variables and a waiting_writers counter, which gives writers priority and prevents writer starvation.
• A barrier can be built from a mutex, a condition variable, a count, and a generation counter. The generation counter is essential for a reusable barrier, because it distinguishes one use of the barrier from the next.
• The essential distinction between a condition variable and a semaphore is state: a semaphore has state in its value, so a post before a wait is remembered; a condition variable has no state, so every wait must re-check an external state variable. Use a condition variable when the problem is to wait for a condition on state protected by a mutex; use a semaphore when the problem is to count resources or signal a one-shot event.

11 References

• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 30. Available online at ostep.org.
• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 6, Section 6.7.
• Butenhof, D. R. Programming with POSIX Threads, Chapter 4. The definitive reference for the POSIX condition variable.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.3.7.
• Hoare, C. A. R. Monitors: An Operating System Structuring Concept. Communications of the ACM, 1974.
• Lampson, B. W., & Redell, D. D. Experience with Processes and Monitors in Mesa. Communications of the ACM, 1980. The paper that introduced Mesa semantics.
• Love, R. Linux System Programming, 2nd ed., Chapter 10.
• Linux man-pages: man 3 pthread_cond_init, man 3 pthread_cond_wait, man 3 pthread_cond_timedwait, man 3 pthread_cond_signal, man 3 pthread_cond_broadcast, man 3 pthread_cond_destroy.