Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Concurrency and liveness
Page 10 of 29

Condition Variables and Semaphores

Predicate-based waiting, atomic sleep handoff, Mesa semantics, counting permits, and bounded-buffer protocols.

Lesson briefConcurrency and liveness · 6 h · 4 outcomes

Required knowledge

  • Interleavings and atomicity
  • Locks, atomics, and memory ordering
  • Processes, threads, and scheduler states

Learning outcomes

  • Derive a condition-variable wait loop from a shared predicate and explain why releasing the mutex and blocking must form one protocol.
  • Trace signal, broadcast, spurious wakeup, timeout, and competing-consumer executions under Mesa semantics.
  • Implement and verify a bounded-buffer protocol with counting semaphores, including permits reserved by in-flight operations.
  • Choose among a condition variable, semaphore, event counter, and direct handoff from the state that must persist.

Assessment target

Given an unseen wait protocol, identify its predicate and mutex, construct a lost-wakeup or stale-predicate schedule if one exists, repair it, and verify safety and progress for both condition-variable and semaphore formulations.

Scope boundary

  • Language-runtime async/await, distributed notifications, and real-time semaphore protocols require separate treatment.
  • This lesson specifies POSIX-style and xv6-style mechanisms; platform APIs with different contracts must be read from their own standards.

A consumer checks an empty queue, releases its mutex, and prepares to sleep. In that gap a producer enqueues work and sends a notification. No waiter is registered, so the notification changes nothing. The consumer then sleeps forever beside a non-empty queue.

Mutual exclusion protected the queue while code was running. It did not solve waiting until a state becomes true. That requires an atomic handoff from “I hold the mutex and the predicate is false” to “I am registered as a waiter and no longer hold the mutex.”

A condition variable is not the condition

Definition 3.3.1Condition predicate

A condition predicate P(S)P(S) is a Boolean expression over shared state SS evaluated while holding the mutex that protects every field on which PP depends. A condition variable is a wait set used to block and make waiters eligible; it does not store the truth of PP

For a bounded queue, a consumer’s predicate may be count > 0; a producer’s may be count < capacity. The queue fields are durable program state. A notification is only a scheduling hint that some waiter should re-evaluate state.

int queue_take(queue *q, item *out) {
    int rc = pthread_mutex_lock(&q->mutex);
    if (rc != 0) return rc;

    while (q->count == 0 && !q->closed) {
        rc = pthread_cond_wait(&q->not_empty, &q->mutex);
        if (rc != 0) {
            pthread_mutex_unlock(&q->mutex);
            return rc;
        }
    }

    if (q->count == 0 && q->closed) {
        pthread_mutex_unlock(&q->mutex);
        return QUEUE_CLOSED;
    }

    *out = q->slots[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->count -= 1;
    pthread_cond_signal(&q->not_full);
    return pthread_mutex_unlock(&q->mutex);
}

The wait operation atomically releases the mutex and blocks with respect to another thread acquiring that mutex and signaling the condition. Before returning, it reacquires the mutex. The loop re-evaluates the predicate after reacquisition.

Retrieval. Why does pthread_cond_wait require the caller to pass the mutex rather than asking the caller to unlock immediately before waiting?

AnswerExpand

Separate unlock and wait operations create an observable gap. A producer can acquire the mutex, make the predicate true, signal when no waiter is registered, and finish before the consumer blocks. The combined wait protocol closes that gap: once another thread can acquire the predicate mutex, the waiter is treated as blocked for a subsequent signal.

Wakeup means “compete again,” not “proceed”

Most practical condition-variable APIs use Mesa-style semantics: signaling makes a waiter ready, but the signaler keeps running until it releases the mutex. By the time a waiter reacquires, another thread may have consumed the resource. Implementations may also permit wakeups even when no program-level event made the predicate true.

Code
hide footbox
participant "consumer A" as A
participant "predicate mutex" as M
participant "producer" as P
participant "consumer B" as B
A -> M : wait(not_empty)\nrelease and block
B -> M : wait(not_empty)\nrelease and block
P -> M : lock; enqueue X; broadcast
P -> M : unlock
M -> A : reacquire; predicate true
A -> M : dequeue X; unlock
M -> B : reacquire; predicate now false
B -> M : wait again
note over A,B
The while-loop is required even though B was notified.
end note
consumer Apredicate mutexproducerconsumer Bconsumer Apredicate mutexproducerconsumer Bwait(not_empty)release and blockwait(not_empty)release and blocklock; enqueue X;broadcastunlockreacquire; predicatetruedequeue X; unlockreacquire; predicatenow falsewait againThe while-loop is required eventhough B was notified.

Prediction — fix an invariant in writing before moving the trace. In the broadcast schedule, which event makes an if (count == 0) wait(...) consumer unsafe: the broadcast, consumer A’s dequeue, or consumer B’s wakeup?

Interactive exploration

Place a context switch inside a condition-variable protocol

Compare the atomic wait protocol with a lost-wakeup gap and an if-check that fails under Mesa semantics. The buffer predicate—not the notification—is the source of truth.

Event 1 of 6
Trace event: 1 of 6
Producer
ready
Consumer A
ready
Bounded buffermutex: free
empty
Initial state

The predicate buffer.length > 0 is false.

wakeup state: none

Place a context switch inside a condition-variable protocol
Producer
done
Consumer A
sleeping
Bounded buffermutex: free
X
Consumer finally sleeps

Liveness fails: the consumer can sleep forever beside available work.

wakeup state: lost

Static state: a signal occurs between an unlocked emptiness check and sleep. The notification is lost, leaving the consumer asleep while data is available.

Transfer. The queue can be closed. A close operation sets closed = true and no further producer may enqueue. Should close signal one waiter or broadcast? What predicates do waiting producers and consumers use?

Transfer solutionExpand

Close changes a state relevant to every waiter, so it normally broadcasts on each condition wait set. A consumer waits while count == 0 && !closed; after wakeup, count > 0 permits draining existing work, while count == 0 && closed returns end-of-stream. A producer waits while count == capacity && !closed; any observation of closed rejects the enqueue. Both predicates and the close transition use the same queue mutex.

Consumer A’s dequeue is the event that makes the predicate false before B reacquires. Broadcast is legal; B’s wakeup is not permission to skip the predicate.

Signal one waiter when one unit of progress became possible. Broadcast when a transition can satisfy several different predicates, when all waiters must observe shutdown/configuration change, or when the implementation cannot identify the relevant waiter. Broadcast can create a thundering herd: many threads wake, contend for one mutex, discover false predicates, and sleep again. That is a performance failure, not permission to weaken the loop.

Condition Variable Mesa Semantics Matrix

0 / 4 answered

Under Mesa semantics, a producer thread signals not_empty and releases the mutex. Evaluate each statement regarding why waiters must loop on wait():

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Testing the condition predicate in an if statement is safe provided the producer signals rather than broadcasts.
2
Operating systems and threading runtimes may permit spurious wakeups even when no thread signaled the variable.
3
Signaling under Mesa semantics immediately yields CPU execution and transfers the lock directly to the waiter.
4
Another thread can acquire the mutex and consume the resource before the woken waiter reacquires the lock.

Predicate updates define the notification protocol

The safe sequence is derived from state ownership:

  1. lock the predicate mutex;
  2. change the fields on which the predicate depends;
  3. signal or broadcast as required by the transition;
  4. unlock, publishing the new state to a waiter that later acquires.

POSIX does not make “signal only while holding the mutex” a universal syntactic law. Some programs can signal after unlocking without losing correctness because the predicate remains authoritative and all state transitions are synchronized. Holding the mutex through the state change and notification is easier to audit: the waiter cannot interleave between publication and notification, and the review can connect one transition to one wake decision.

Counterexample: notifications as remembered events. A thread calls signal before any waiter exists. A later waiter does not consume a stored signal; condition variables do not generally count notifications. If the application requires one future operation to consume one earlier permit, represent that fact in state—a counter, queue entry, generation number, latch, or semaphore.

Application: generation wait. A configuration service increments generation after each reload. A worker holds seen. Its predicate is generation != seen || shutting_down; after waking it copies the current generation to seen. A bare boolean changed can merge several reloads, which may be correct for “refresh to latest” but wrong if each reload requires one audit action. The state representation decides the semantics.

Timeouts add another state transition. A timed wait returning does not establish that the predicate is false or true; reacquire the mutex and test it. When elapsed duration matters, use a monotonic clock-capable API so wall-clock adjustment does not change the deadline semantics.

Semaphores store permits

Definition 3.3.2Counting semaphore

A counting semaphore has a nonnegative logical permit count. wait/P consumes one permit or blocks until one can be consumed. post/V adds one permit and may wake a waiter. The operation that changes the count and chooses whether to block is atomic with respect to other semaphore operations.

A semaphore post before a wait is remembered as a permit. That makes a semaphore suitable for a pool of interchangeable resources or queued units of availability. A condition variable is suitable when a thread must re-evaluate an arbitrary predicate over separately protected state.

MechanismPersistent stateOwnership on releaseNatural question
mutexlocked/unlocked plus ownerowner releaseswho may mutate this invariant?
condition variableno application truth valuenonewhen should waiters recheck P(S)P(S)
counting semaphorepermit countusually no mutex-style ownerhow many units may proceed?
event/generation countermonotonically changing valueapplication-definedhas state advanced since my observation?

A binary semaphore can have values 0/1, but that does not automatically make it a mutex. Mutex ownership enables errors such as non-owner unlock to be rejected or defined; mutex protocols often carry priority inheritance and memory synchronization semantics. A semaphore can be posted by a different thread and often represents handoff rather than ownership.

Derive the bounded-buffer semaphore protocol

Let capacity be NN Initialize:

empty = N      // permits to reserve an empty slot
full  = 0      // permits to reserve a filled slot
mutex = 1      // exclusive queue metadata access

Producer:

P(empty)
P(mutex)
enqueue(item)
V(mutex)
V(full)

Consumer:

P(full)
P(mutex)
item = dequeue()
V(mutex)
V(empty)

Taking empty before mutex prevents a producer from sleeping for capacity while holding the metadata lock needed by a consumer. The consumer follows the symmetric order.

At quiescent points, empty + full == N. During concurrent operations that equality omits reservations. A stronger accounting invariant is

empty+full+Rp+Rc=N,empty + full + R_p + R_c = N,

where RpR_p counts producers that consumed an empty permit but have not posted a full permit, and RcR_c counts consumers that consumed a full permit but have not posted an empty permit. Queue occupancy and permit counts are related by the protocol phase, not by one unconditional two-variable equation.

Worked trace, N=2N=2 Start empty=2, full=0. Producers A and B each perform P(empty), so empty=0, R_p=2. A acquires mutex, enqueues X, releases, and posts full: full=1, R_p=1. A consumer consumes that full permit (full=0, R_c=1) before B has enqueued. It may dequeue only after acquiring mutex; B’s reserved slot does not count as a filled item. The mutex and phase ordering preserve representation safety while permits limit capacity.

Counterexample: take the mutex first. With a full buffer, a producer acquires mutex then blocks in P(empty). A consumer can consume a full permit but blocks trying to acquire mutex, so it cannot dequeue and post empty. The system deadlocks. This schedule is one reason resource-acquisition order belongs in the protocol proof.

xv6 sleep and wakeup expose the same handoff

xv6 kernel code waits on a channel, an arbitrary identifier associated with a predicate. sleep(chan, lock) acquires the process lock before releasing the caller’s condition lock, records the channel and sleeping state, and enters the scheduler. The overlapping lock ownership prevents a concurrent wakeup(chan) from passing between predicate inspection and visible sleep registration.

The channel is not the predicate and wakeup is not a stored permit. Callers inspect their condition in a loop under the condition lock. wakeup makes matching sleepers runnable; by the time one runs, another process may have changed the condition.

Code
start
:caller holds condition lock C;
:predicate is false;
:sleep(channel, C) acquires process lock P;
:sleep releases C;
:record channel and SLEEPING under P;
:scheduler releases P after switch;
:wakeup checks matching sleepers under each P;
:awakened caller reacquires C;
:caller rechecks predicate;
stop
caller holds condition lock Cpredicate is falsesleep(channel, C) acquiresprocess lock Psleep releases Crecord channel and SLEEPINGunder Pscheduler releases P after switchwakeup checks matchingsleepers under each Pawakened caller reacquires Ccaller rechecks predicate

Holding C while entering sleep forever would block the producer that needs C to make the predicate true. Releasing C before the sleep protocol owns P would reopen the lost-wakeup gap. The handoff must ensure the waiter owns one lock or the other across the vulnerable interval.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 3.3.1: Lost-Wakeup Race Condition When Releasing Mutex Before Sleeping

Descriptionapplication

Explain why an implementation of cond_wait(cv, mutex) that executes mutex_unlock(mutex) and then separately executes thread_sleep(cv) possesses a fatal lost-wakeup race condition. Trace the exact interleaving with a concurrent signaler.

HintExpand

Trace what happens if a signal arrives between mutex_unlock and thread_sleep.

Worked solutionExpand

If unlocking and sleeping are not atomic:

  1. Waiter acquires mutex, tests condition count == 0, and decides to sleep.
  2. Waiter executes mutex_unlock(mutex).
  3. Before the waiter executes thread_sleep(cv), a context switch occurs.
  4. Producer acquires mutex, inserts an item into the queue, executes cond_signal(cv), and releases mutex.
  5. Because the waiter is not yet enqueued on cv’s wait set, the signal is lost into the void.
  6. Waiter resumes and executes thread_sleep(cv), blocking indefinitely even though the queue is non-empty. cond_wait must atomically release the mutex and enroll the thread into the wait queue.

Exercise 3.3.2: Mesa Semantics and Spurious Wakeup Invariants

Verificationapplication

Contrast Hoare monitor semantics with Mesa monitor semantics. Explain why Mesa semantics require condition wait calls to be placed inside a while (!predicate) loop rather than an if (!predicate) block.

HintExpand

Analyze whether signaling hands off lock ownership immediately or merely marks the waiter runnable.

Worked solutionExpand

Under Hoare semantics, signaling immediately transfers the monitor lock and CPU execution directly to the awakened waiter; thus, the predicate is guaranteed to remain true when the waiter resumes. Under Mesa semantics, cond_signal merely transitions a waiting thread from sleeping to runnable; the signaler retains the lock until it explicitly releases it. Between the signal and the moment the awakened waiter reacquires the lock, a third intervening thread can execute, acquire the lock, and invalidate the predicate. Furthermore, POSIX permits spurious wakeups (e.g., due to kernel interrupt signals). Wrapping pthread_cond_wait inside a while loop ensures the predicate is perpetually verified under mutual exclusion before proceeding.

Exercise 3.3.3: Bounded Buffer Synchronization Using Counting Semaphores

Constructiontransfer

Write the pseudocode for a concurrent bounded FIFO queue of capacity NN using counting semaphores empty_slots, full_items, and a binary semaphore mutex. Explain why sem_wait(&empty_slots) must precede sem_wait(&mutex).

HintExpand

Inverting the semaphore acquisition order creates an instant deadlock when the queue is full.

Worked solutionExpand
semaphore empty_slots = N;
semaphore full_items = 0;
semaphore mutex = 1;

void enqueue(item):
    sem_wait(&empty_slots);  // wait for space
    sem_wait(&mutex);        // acquire buffer access
    buffer[tail] = item;
    tail = (tail + 1) % N;
    sem_post(&mutex);
    sem_post(&full_items);

item dequeue():
    sem_wait(&full_items);   // wait for an item
    sem_wait(&mutex);        // acquire buffer access
    item = buffer[head];
    head = (head + 1) % N;
    sem_post(&mutex);
    sem_post(&empty_slots);
    return item;

If a producer executes sem_wait(&mutex) before sem_wait(&empty_slots) when the buffer is completely full (empty_slots == 0), the producer acquires mutex and then blocks on empty_slots. A consumer attempting to dequeue blocks immediately on mutex, creating an instant deadlock where the consumer cannot free a slot and the producer will never release the mutex.

Exercise 3.3.4: Thundering Herd Performance Degradation vs Targeted Signaling

Descriptiontransfer

Explain the performance phenomenon known as the “thundering herd” problem when pthread_cond_broadcast() is invoked on a condition variable with 100 waiting worker threads, only one of which can successfully claim the newly available work item.

HintExpand

Trace the lock contention and context-switching overhead among the 99 unsuccessful waiters.

Worked solutionExpand

When a producer broadcasts on a condition variable with 100 waiting threads, the kernel wakes all 100 threads, placing them on the runnable queue. However, all 100 threads immediately contend for the single mutex protecting the queue. One winner acquires the lock, drains the work item, and releases the lock. The remaining 99 threads sequentially acquire the lock, recheck their while (count == 0) loop, observe the predicate is false, and re-enter cond_wait(). This results in 99 redundant context switches, severe CPU cache-line bouncing, and high scheduling latency with zero forward progress. Targeted cond_signal() should be preferred when exactly one waiter can make progress.

Exercise 3.3.5: Designing Graceful Queue Shutdown and Waiter Cancellation

Constructionsynthesis

Design a thread-safe multi-producer multi-consumer work queue supporting a close() operation that gracefully unblocks all current and future waiting consumers with an END_OF_STREAM status without leaking memory or dropping enqueued items.

HintExpand

Add a closed boolean flag under the mutex and broadcast to all waiters upon shutdown.

Worked solutionExpand
  1. Shared state: Add bool closed = false under the queue mutex, alongside cond_var not_empty and cond_var not_full.
  2. Enqueue: Producers wait while (count == N && !closed). If closed, enqueue immediately returns -ESHUTDOWN.
  3. Dequeue: Consumers wait while (count == 0 && !closed). Upon waking:
    • If count > 0: dequeue item and return success (draining pre-existing work).
    • If count == 0 && closed: return -EPIPE / END_OF_STREAM.
  4. Close operation:
    void queue_close(struct Queue *q) {
        pthread_mutex_lock(&q->mutex);
        q->closed = true;
        pthread_cond_broadcast(&q->not_empty);
        pthread_cond_broadcast(&q->not_full);
        pthread_mutex_unlock(&q->mutex);
    }
    Broadcasting ensures every blocked consumer and producer awakens, observes closed == true, and exits without blocking forever.

References & Further Reading