Wait for a predicate, not a notification

Prerequisites: Threads, shared state, and mutual exclusion.

Learning objectives

• Explain the atomic release-and-wait operation.
• Use a loop to recheck a shared predicate.
• Trace a lost-wakeup failure and a correct protocol.

The shared state defines whether progress is possible

A mutex allows one thread at a time to manipulate a protected invariant. A condition variable lets a thread sleep while waiting for a predicate about that shared state. The predicate might be “the queue is nonempty” or “space is available.” A notification does not store the data and should not be treated as a durable permission token.

For a bounded queue, protect both the queue contents and its size with one mutex. A consumer acquires that mutex and checks whether the queue is empty. If it is empty, the consumer waits on the condition variable using an operation that atomically releases the mutex and begins waiting. Before that wait returns, it reacquires the mutex.

PSEUDOCODE: consumer
lock(mutex)
while queue is empty:
    wait(not_empty, mutex)
item = remove_front(queue)
notify(not_full)
unlock(mutex)
return item

A producer uses the symmetric protocol: wait while the queue is full, insert an item while holding the mutex, and notify a consumer. Both sides must follow the same protection discipline.

Why the check belongs in a loop

Suppose two consumers are waiting. A producer inserts one item and a consumer wakes. Before it reacquires the mutex, another eligible consumer may acquire the mutex and remove the item. A wakeup therefore does not prove that the predicate is still true when the awakened thread runs. Some condition-variable interfaces also permit spurious wakeups. The loop handles both by rechecking the actual state under protection.

Using a separate unlock followed by an ordinary sleep introduces a different failure. A producer can insert and notify during the gap after the consumer releases the lock but before it begins sleeping. The consumer then sleeps even though work exists, possibly forever if no further notification arrives. Atomic release-and-wait closes that gap relative to the coordinated protocol.

State the invariant and the shutdown rule

For capacity k, the queue invariant is 0 <= size <= k, with every queue mutation under the mutex. Notification policy should wake enough eligible waiters without assuming fairness that the primitive does not guarantee. A program that can stop also needs a closed or cancelled predicate, so waiting threads can terminate when no future item or space will arrive.

A semaphore has different semantics because it maintains a count. A mutex is about exclusive access. A condition variable is about waiting for a state change. Choosing among them starts by identifying what information must persist and which invariant needs protection, rather than replacing one primitive’s name with another.

Primary reading

• Condition Variables (Arpaci-Dusseau and Arpaci-Dusseau, OSTEP).

Practice problem

A consumer checks an empty queue under a lock, unlocks, and then calls an unrelated sleep operation. A producer inserts one item and signals between the unlock and sleep. Explain the failure. Rewrite the protocol in words using a condition variable, and explain why an if-statement is still insufficient after fixing the atomic wait.

Worked solution

The producer’s notification occurs before the consumer is registered as waiting. The consumer then sleeps despite the queue containing an item, and no future producer may arrive to wake it. The corrected consumer acquires the mutex, repeatedly checks the empty predicate, and uses the condition variable’s atomic release-and-wait operation when empty. On return it holds the mutex again and rechecks before removing an item. Replacing the loop with one if-statement remains unsafe because another consumer can remove the item before this consumer reacquires the lock, or the interface can wake without the predicate becoming true. The shared queue state is authoritative. A notification only provides a reason to check that state again.

Check your understanding

What must a condition wait do atomically for this protocol?

• Release the mutex and register the thread as waiting.
• Delete all queue items.
• Increment the CPU frequency.
• Guarantee that the predicate stays true forever.

Explanation

Atomic release-and-wait prevents the gap that can lose a notification relative to the predicate check.

Why recheck the predicate after waking?

• Because the mutex cannot be reacquired.
• Because shared state may have changed before the waiter regains the mutex.
• Because every notification is an error.
• Because the queue must always remain empty.

Explanation

Wakeup is not a reservation of the desired state.

Primary reading

• Condition Variables: Arpaci-Dusseau and Arpaci-Dusseau, OSTEP

Open the study and save your work →