Beyond Semaphores: Condition Variables and Lock-Free Ring Buffers

Moving from kernel-blocking semaphores to pthread condition variables for MPMC thread pools and wait-free C11 atomic ring buffers for low-latency SPSC pipelines.

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:

  1. 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.
  2. Sub-Microsecond Latency (Zero Kernel Traps): Contended semaphore operations trap into the OS kernel (futex on 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <pthread.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define QUEUE_CAPACITY 64

typedef struct {
    int32_t         slots[QUEUE_CAPACITY];
    size_t          write_idx;
    size_t          read_idx;
    size_t          count;
    bool            closed;
    pthread_mutex_t lock;
    pthread_cond_t  can_push;
    pthread_cond_t  can_pop;
} MpmcQueue;

void mpmc_init(MpmcQueue *q) {
    *q = (MpmcQueue){0};
    pthread_mutex_init(&q->lock, nullptr);
    pthread_cond_init(&q->can_push, nullptr);
    pthread_cond_init(&q->can_pop, nullptr);
}

bool mpmc_push(MpmcQueue *q, int32_t item) {
    pthread_mutex_lock(&q->lock);

    while (q->count == QUEUE_CAPACITY && !q->closed) {
        pthread_cond_wait(&q->can_push, &q->lock);
    }
    if (q->closed) {
        pthread_mutex_unlock(&q->lock);
        return false;
    }

    q->slots[q->write_idx] = item;
    q->write_idx           = (q->write_idx + 1) % QUEUE_CAPACITY;
    q->count++;

    pthread_cond_signal(&q->can_pop);
    pthread_mutex_unlock(&q->lock);
    return true;
}

bool mpmc_pop(MpmcQueue *q, int32_t *out) {
    pthread_mutex_lock(&q->lock);

    while (q->count == 0 && !q->closed) {
        pthread_cond_wait(&q->can_pop, &q->lock);
    }
    if (q->count == 0) { // Queue is both empty and closed
        pthread_mutex_unlock(&q->lock);
        return false;
    }

    *out        = q->slots[q->read_idx];
    q->read_idx = (q->read_idx + 1) % QUEUE_CAPACITY;
    q->count--;

    pthread_cond_signal(&q->can_push);
    pthread_mutex_unlock(&q->lock);
    return true;
}

void mpmc_close(MpmcQueue *q) {
    pthread_mutex_lock(&q->lock);
    q->closed = true;
    pthread_cond_broadcast(&q->can_push);
    pthread_cond_broadcast(&q->can_pop);
    pthread_mutex_unlock(&q->lock);
}

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:

  1. 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-locks q->lock, a freshly scheduled Consumer B can acquire q->lock first and steal the item. When Consumer A returns from pthread_cond_wait, q->count is 0 again.
  2. Spurious Wakeups: On Linux (futex) and other POSIX kernels, hardware interrupts or signal delivery can wake a waiting thread even when no thread called signal or broadcast.

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:

1
2
ring->slots[w & MASK] = item; // (1) Write payload to slot
ring->write_idx = w + 1;      // (2) Publish new write_idx

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_idx guarantees that the payload write to slots[w & MASK] is globally visible before the updated write_idx becomes visible.
  • A Load-Acquire on write_idx by the consumer guarantees that once it sees the new write_idx, its subsequent read of slots[r & MASK] will observe the written payload.

Cache-Aligned C11 Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define SPSC_CAPACITY 1024U
#define SPSC_MASK     (SPSC_CAPACITY - 1U)

_Static_assert((SPSC_CAPACITY & SPSC_MASK) == 0, "SPSC_CAPACITY must be a power of 2");

typedef struct {
    // Isolate producer-owned, consumer-owned, and read-mostly data on 64-byte cache lines
    _Alignas(64) _Atomic uint64_t write_idx;
    _Alignas(64) uint64_t         cached_read_idx; // Producer-local shadow copy

    _Alignas(64) _Atomic uint64_t read_idx;
    _Alignas(64) uint64_t         cached_write_idx; // Consumer-local shadow copy

    _Alignas(64) int32_t          slots[SPSC_CAPACITY];
} SpscRing;

static inline bool spsc_push(SpscRing *r, int32_t item) {
    const uint64_t w = atomic_load_explicit(&r->write_idx, memory_order_relaxed);

    if (w - r->cached_read_idx == SPSC_CAPACITY) {
        // Only reload the consumer's atomic read_idx when our cached view looks full
        r->cached_read_idx = atomic_load_explicit(&r->read_idx, memory_order_acquire);
        if (w - r->cached_read_idx == SPSC_CAPACITY) {
            return false; // Ring is genuinely full
        }
    }

    r->slots[w & SPSC_MASK] = item;
    atomic_store_explicit(&r->write_idx, w + 1, memory_order_release);
    return true;
}

static inline bool spsc_pop(SpscRing *r, int32_t *out) {
    const uint64_t rd = atomic_load_explicit(&r->read_idx, memory_order_relaxed);

    if (rd == r->cached_write_idx) {
        // Only reload the producer's atomic write_idx when our cached view looks empty
        r->cached_write_idx = atomic_load_explicit(&r->write_idx, memory_order_acquire);
        if (rd == r->cached_write_idx) {
            return false; // Ring is genuinely empty
        }
    }

    *out = r->slots[rd & SPSC_MASK];
    atomic_store_explicit(&r->read_idx, rd + 1, memory_order_release);
    return true;
}

Two Microarchitectural Optimizations

  1. Eliminating False Sharing (_Alignas(64)): CPU caches coherence protocols (MESI/MOESI) operate on 64-byte cache lines. If write_idx and read_idx shared 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.
  2. 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 observed read_idx locally on the producer’s cache line, the producer only performs an acquire load across cores when its local bound w - cached_read_idx == SPSC_CAPACITY is reached—reducing cross-core coherence traffic by up to $1024\times$.