Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 30, Arpaci-Dusseau & Arpaci-Dusseau

Condition Variables

Locks alone are not enough. Often a thread must wait until some condition is true (child finished, buffer not empty, enough free memory). Spinning wastes CPU.

Crux: how should a thread wait for a condition?

Condition variables​

A condition variable is an explicit queue: threads wait when state is wrong; another thread that changes state signals (or broadcasts) to wake waiters. Roots: Dijkstra’s private semaphores [D68]; Hoare’s monitors [H74].

pthread_cond_wait(&c, &mutex);   // must hold mutex
pthread_cond_signal(&c);

wait atomically releases the mutex and sleeps; on wake it re-acquires the mutex before returning. That pairing prevents lost wakeups around “check then sleep.”

Always hold the lock while signaling

And you must hold it when calling wait. Hold the lock for both and you stay safe.

Example: join​

Shared done, a mutex, and a CV (Fig 30.3):

  • thr_join: lock; while done==0 wait; unlock
  • thr_exit: lock; done=1; signal; unlock

Covers both orders: parent waits first, or child finishes before parent joins (signal with empty wait queue is fine — done records the fact).

Broken without done: child signals before parent waits → parent waits forever.
Broken without the lock around check/wait: parent can miss the signal between checking done and waiting.

Quiz

Rank the sequence

1 / 1

Order the steps of thr_exit (child) signaling thr_join (parent) when the parent waits first.

OrderDrag the handle to rearrange — top should be first.

  1. 1Child sets done = 1
  2. 2Parent locks mutex and checks while(done==0)
  3. 3Parent wakes, re-acquires mutex, and returns
  4. 4Parent calls wait, atomically releasing the mutex and sleeping
  5. 5Child signals the condition variable

Drag items into the correct order (or use ↑↓), then check.

Producer / consumer (bounded buffer)​

Producers put items; consumers take them. Shared buffer needs a mutex and waiting for empty/full [D72]. Web servers, pipes (grep | wc), work queues — same pattern.

Broken: one CV + if​

With Mesa semantics [LR80], signal is a hint, not a promise the condition still holds when you run. Another consumer can sneak in after you were signaled. Fix: while (not if) around the wait. Always.

Still broken: one CV + while​

A consumer that empties the buffer may wake another consumer instead of the producer → everyone asleep (Fig 30.9).

Correct: two CVs + while​

  • Producers: while (full) wait(empty); put; signal(fill)
  • Consumers: while (empty) wait(fill); get; signal(empty)

Multi-slot buffer: wait while count==MAX / count==0; circular fill_ptr / use_ptr (Figs 30.11–30.12).

Quiz

Rank the sequence

1 / 1

Order a producer's steps in the correct two-CV, while-loop bounded buffer solution.

OrderDrag the handle to rearrange — top should be first.

  1. 1Signal the fill condition variable
  2. 2Unlock the mutex
  3. 3Lock the mutex
  4. 4Put the item into the buffer
  5. 5While the buffer is full, wait on the empty condition variable

Drag items into the correct order (or use ↑↓), then check.

Use while (not if) for conditions

Also handles spurious wakeups in some libraries [L11].

Covering conditions​

Memory allocator: waiters need different sizes. signal may wake the wrong thread. broadcast wakes all; each rechecks with while — a covering condition [LR80]. Cost: extra wakeups. If you “need” broadcast but think you shouldn’t, you may have a bug — unless the wake set is truly ambiguous.

Interactive​

Try: join · Mesa while≠if · two CVs · broadcast covering.

Check your understanding​

Quiz

Condition variables

1 / 6

pthread_cond_wait assumes…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: producer/consumer variants​

Use the OSTEP CV homework (main-two-cvs-while.c and broken variants).

Lab

Homework: threads-cv producer/consumer

0/5 started

Loading lab…

Summary​

RuleWhy
Hold lock for wait/signalAvoid lost wakeups
State + CVSignal alone is not memory
while not ifMesa + spurious wakeups
Two CVs for PCDirected wakeups
Broadcast when unsureCovering conditions

Previous: Lock-based Concurrent Data Structures

Next: Semaphores — locks and waiting in one primitive.

Further Reading​