Where Counting Semaphores Hit Their Limits
Counting semaphores are a natural fit when synchronization reduces to a single integer counter (such as available buffer slots). However, two common engineering requirements quickly push beyond what semaphores express cleanly:
- Compound State Predicates and Graceful Shutdown: In a Multi-Producer / Multi-Consumer (MPMC) thread pool, a worker thread typically waits for
(count > 0 || shutdown_requested). Encoding compound boolean predicates across separate counting semaphores without race conditions or “poison-pill” dummy messages is brittle. - Sub-Microsecond Latency (Zero Kernel Traps): Contended semaphore operations trap into the OS kernel (
futexon Linux), costing thousands of clock cycles. In real-time audio, high-frequency telemetry, or network packet rings, a Single-Producer / Single-Consumer (SPSC) channel should transfer data across cores in a few nanoseconds without locks or system calls.
Let’s build the idiomatic C solution for each regime: Monitors with POSIX Condition Variables for MPMC thread pools, and a Wait-Free Atomic Ring Buffer using C11 acquire-release memory ordering.
1. MPMC Thread Queues with Condition Variables
A Monitor pairs a mutex (pthread_mutex_t), shared state variables, and one or more Condition Variables (pthread_cond_t). Unlike a semaphore, a condition variable holds no counter; it is a kernel wait-queue that lets threads sleep until an arbitrary predicate protected by the mutex becomes true.
| |
Why the while Loop Around pthread_cond_wait Is Mandatory
Calling pthread_cond_wait(&q->can_pop, &q->lock) atomically unlocks q->lock and puts the calling thread to sleep; when signaled, it re-acquires q->lock before returning. Re-testing the predicate in a while loop—never an if—is required for two reasons:
- Mesa Semantics (Intercepted Wakeups): Between the instant a producer calls
pthread_cond_signal(&q->can_pop)and the instant sleeping Consumer A wakes up and re-locksq->lock, a freshly scheduled Consumer B can acquireq->lockfirst and steal the item. When Consumer A returns frompthread_cond_wait,q->countis0again. - Spurious Wakeups: On Linux (
futex) and other POSIX kernels, hardware interrupts or signal delivery can wake a waiting thread even when no thread calledsignalorbroadcast.
Notice how cleanly mpmc_close() shuts down an entire thread pool: setting q->closed = true and broadcasting wakes all blocked producers and consumers simultaneously, allowing consumers to drain any remaining items (q->count > 0) before exiting.
2. Wait-Free SPSC Ring Buffer with C11 Atomics
Now consider the Single-Producer / Single-Consumer (SPSC) case. Look closely at data ownership:
- Only the producer ever modifies
write_idx. - Only the consumer ever modifies
read_idx.
If we drop the shared count variable—which forced both threads to mutate the same integer—no variable is written by more than one thread.
Instead of wrapping indices early, let write_idx and read_idx be monotonically increasing uint64_t counters, and require RING_CAPACITY to be a power of two ($2^k$). We index the array via bitwise masking (idx & (RING_CAPACITY - 1)), and the exact number of items in flight is simply write_idx - read_idx:
- Empty:
write_idx == read_idx - Full:
write_idx - read_idx == RING_CAPACITY
(Unlike the classic modulo approach, monotonic counters use all $2^k$ slots without wasting an element to distinguish full from empty).
The Hardware Reordering Hazard and Acquire-Release Pairing
Even with single-writer ownership, plain C variables break on multi-core CPUs. Suppose the producer executes:
| |
Without memory ordering constraints, both the compiler and weakly ordered CPUs (such as ARM64 / Apple Silicon) can reorder (2) ahead of (1) as seen by another core. The consumer observes the incremented write_idx, reads ring->slots[r & MASK], and gets stale, uninitialized memory!
C11 <stdatomic.h> solves this without expensive full memory barriers (memory_order_seq_cst) by pairing memory_order_release stores with memory_order_acquire loads:
- A Store-Release on
write_idxguarantees that the payload write toslots[w & MASK]is globally visible before the updatedwrite_idxbecomes visible. - A Load-Acquire on
write_idxby the consumer guarantees that once it sees the newwrite_idx, its subsequent read ofslots[r & MASK]will observe the written payload.
Cache-Aligned C11 Implementation
| |
Two Microarchitectural Optimizations
- Eliminating False Sharing (
_Alignas(64)): CPU caches coherence protocols (MESI/MOESI) operate on 64-byte cache lines. Ifwrite_idxandread_idxshared the same 64-byte line, every store by the producer would invalidate the consumer’s L1 cache line and vice versa. Aligning each atomic index to 64 bytes eliminates cross-core cache-line ping-ponging. - Shadow Index Caching (
cached_read_idx/cached_write_idx): Even with separate cache lines, reading the remote core’s atomic index on every push or pop triggers cross-core cache traffic whenever the remote core updates its counter. By caching the last observedread_idxlocally on the producer’s cache line, the producer only performs anacquireload across cores when its local boundw - cached_read_idx == SPSC_CAPACITYis reached—reducing cross-core coherence traffic by up to $1024\times$.