Implement Condition Variable from Scratch

Topic Overview

Waiting for a Condition

Condition variables let threads sleep until a predicate becomes true. A mutex protects the predicate; wait() atomically releases the mutex and sleeps, reacquiring on wakeup. Spurious wakeups mean you always re-check the predicate in a loop.

Classic Producer/Consumer

Pattern:

• Lock mutex
• while (!ready) cond_wait(&cv, &mutex);
• Consume item
• Unlock mutex

For example, a queue depth predicate count > 0 blocks consumers until a producer post() increments count and signals the CV.

Why This Matters in Production

This exact wait/signal pattern is what powers pthread_cond_wait in glibc, Java's Object.wait()/notify(), and every bounded producer-consumer queue in real message brokers like RabbitMQ's internal worker pools. The 'always recheck in a while loop, never an if' rule you'll apply here guards against spurious wakeups, a documented POSIX behavior that has caused real intermittent bugs in code that assumed a single wakeup always means the condition holds.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement cond_wait and cond_signal using futex-backed queues or pthread equivalents from scratch. The task asks for a bounded buffer demo proving that waiters sleep instead of spinning.

Your Task

Build a bounded buffer from one mutex and two condition variables, not_full and not_empty. Use it to show the two classic condition-variable lessons. First, a woken thread must re-check its condition in a while loop, because another thread may have run between the signal and the wakeup, and wakeups can be spurious. Second, signal wakes one waiter while broadcast wakes them all. Each command runs atomically under the mutex, except that cond_wait releases it. Woken threads run only when told to.

Input

cCopy
Loading…

Rules

• A thread that must wait joins the back of that condition variable's queue. signal wakes the first waiter, and broadcast wakes every waiter, in queue order.
• With while, a thread that runs after waking re-checks. If the condition is still false, that is a wasted wakeup, and it waits again (at the back of the queue).
• With if, a woken thread proceeds without checking. A get from an empty buffer prints BUG: buffer empty, read garbage. A put into a full buffer prints BUG: buffer full, X overwrites the newest item, and X replaces the newest slot. Each counts as a bug, and the get or put still counts as done.
• A thread that is waiting or woken cannot start a new operation: busy (waiting) / busy (woken, needs run). Other errors are not woken, not waiting, missing item and unknown operation.

Output

cCopy
Loading…

Each command line is echoed before its result. notify with signal|broadcast is printed for wake. The final statistics line is always printed. Spurious wakeups are not counted as wakeups.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Give each condition variable its own FIFO of waiting threads. cond_wait = release the mutex, then join the queue, as one atomic step.
2. Make the re-check the only difference between while and if, so you can compare the two behaviours directly.

Hidden tests cover producers blocking on a full buffer, broadcast waking several consumers of which only one succeeds, the if bug on both the producer and the consumer side, spurious wakeups under while, busy threads, and misuse of run and spurious.