Lock-free queues — SPSC, MPSC, and when to use each

Why lock-free

A mutex is a valid synchronisation tool. But it has a hard cost: if one thread is preempted while holding a lock, every other thread blocks until the scheduler wakes it back up. On a latency-sensitive pipeline — audio, network packet processing, game engine tick — this jitter is unacceptable.

Lock-free queues avoid this by using atomic operations that always make progress without a kernel lock. The tradeoff: correctness requires careful memory ordering, and implementation mistakes are silent, rare, and catastrophic.

This article covers two patterns: SPSC (single-producer, single-consumer), which is the simplest and fastest, and MPSC (multi-producer, single-consumer), which covers most real-world multi-threaded pipelines.

SPSC — the simplest lock-free queue

SPSC has one invariant: only one thread writes (producer) and only one thread reads (consumer). This constraint unlocks a very efficient ring-buffer design.

Design

head ──────────────────────────────────┐
     [ _ ][ A ][ B ][ C ][ _ ][ _ ][ _ ]
               ↑                    ↑
            tail                  capacity

• tail is owned by the producer — only the producer writes it
• head is owned by the consumer — only the consumer writes it
• The queue is empty when head == tail
• The queue is full when (tail + 1) % capacity == head

Because ownership is exclusive, we only need atomic reads of the other side’s index — no compare-and-swap, no spinlock.

Implementation

 1template <typename T, size_t Capacity>
 2class SpscQueue {
 3    static_assert((Capacity & (Capacity - 1)) == 0,
 4                  "Capacity must be a power of two");
 5public:
 6    bool push(const T& item) {
 7        const size_t tail = tail_.load(std::memory_order_relaxed);
 8        const size_t next = (tail + 1) & (Capacity - 1);
 9
10        // Stale read is fine — if head moved forward, we just see fewer slots
11        if (next == head_.load(std::memory_order_acquire))
12            return false;  // full
13
14        buffer_[tail] = item;
15        tail_.store(next, std::memory_order_release);
16        return true;
17    }
18
19    bool pop(T& item) {
20        const size_t head = head_.load(std::memory_order_relaxed);
21
22        if (head == tail_.load(std::memory_order_acquire))
23            return false;  // empty
24
25        item = buffer_[head];
26        head_.store((head + 1) & (Capacity - 1), std::memory_order_release);
27        return true;
28    }
29
30private:
31    alignas(64) std::atomic<size_t> head_{0};
32    alignas(64) std::atomic<size_t> tail_{0};
33    T buffer_[Capacity];
34};

Memory ordering explained

The push path:

1. tail_.load(relaxed) — producer reads its own index; no sync needed
2. head_.load(acquire) — acquire pairs with the consumer’s release store of head_, ensuring we see all writes the consumer made before advancing head_
3. buffer_[tail] = item — write the data
4. tail_.store(release) — release ensures the data write is visible before the index advances; the consumer’s acquire load of tail_ will see both

Without these orderings, the compiler or CPU could reorder the data write after the index store — the consumer would read the index, see a new item, and read uninitialised memory.

False sharing

alignas(64) on each atomic prevents false sharing — the CPU cache line is typically 64 bytes. If head_ and tail_ shared a cache line, the producer writing tail_ would invalidate the cache line in the consumer’s L1 cache, and vice versa. Separating them costs 64 bytes of memory and buys significant throughput on multi-core systems.

MPSC — multiple producers, one consumer

MPSC is needed when several threads (worker pool, I/O threads, interrupt handlers) feed a single processing thread. A classic example: a logger that receives messages from many threads and writes them on a dedicated I/O thread.

Design

The challenge: multiple producers race to claim a slot. We need an atomic compare-and-swap (CAS) to resolve the race.

The simplest correct approach is a linked-list MPSC (Michael-Scott queue simplified for single consumer):

 1template <typename T>
 2class MpscQueue {
 3    struct Node {
 4        T data;
 5        std::atomic<Node*> next{nullptr};
 6    };
 7
 8public:
 9    MpscQueue() {
10        // Sentinel node — head always points to a dummy
11        Node* dummy = new Node{};
12        head_.store(dummy, std::memory_order_relaxed);
13        tail_ = dummy;
14    }
15
16    // Called by producers (any thread)
17    void push(T item) {
18        Node* node = new Node{std::move(item)};
19        // Atomically swap the head, link new node to previous head
20        Node* prev = head_.exchange(node, std::memory_order_acq_rel);
21        prev->next.store(node, std::memory_order_release);
22    }
23
24    // Called by consumer (single thread only)
25    bool pop(T& item) {
26        Node* tail = tail_;
27        Node* next = tail->next.load(std::memory_order_acquire);
28        if (!next) return false;  // empty
29
30        item = std::move(next->data);
31        tail_ = next;
32        delete tail;  // delete old sentinel
33        return true;
34    }
35
36    ~MpscQueue() {
37        T discard;
38        while (pop(discard)) {}
39        delete tail_;
40    }
41
42private:
43    alignas(64) std::atomic<Node*> head_;
44    alignas(64) Node* tail_;   // consumer-only, no atomic needed
45};

The exchange trick

head_.exchange(node, acq_rel) atomically swaps the head pointer and returns the old head. Multiple producers can race here and each one wins exactly one slot — the order is determined by the exchange sequence. The prev->next.store(release) then links the chain from the consumer’s perspective.

The consumer walks tail_->next to dequeue — it sees nodes in LIFO order from the exchange perspective, which becomes FIFO when traversed from tail_ forward.

Memory allocation

The linked-list MPSC allocates a node per push — a new call per message. This can be expensive. For high-throughput systems, use a node pool:

1// Pre-allocate fixed pool, acquire/release nodes lock-free
2// Out of scope here — topic for the allocators article

For low-throughput logging or event dispatch, the allocation cost is negligible.

SPSC vs MPSC — when to use which

The rule: if you can guarantee exactly one writer, use SPSC — it’s faster and simpler. If writers are dynamic or you can’t enforce the count, use MPSC.

Never use an SPSC queue with multiple producers. The race on tail_ will corrupt the index silently. The bug will reproduce once in 10 million operations, under specific cache conditions, and only in release builds.

Benchmarking

Rough throughput on a modern x86 (Ryzen 5800X, single socket):

The SPSC advantage comes from no CAS, no contention on any cache line between threads (with proper alignment), and the ring buffer’s cache-friendly access pattern.

On embedded targets

On Cortex-M (ARM), the memory model is weaker than x86. On single-core MCUs (which is the majority of embedded targets), you don’t need atomics at all for SPSC — a volatile index and a barrier around the data copy is sufficient.

On multi-core Cortex-A, you need the same orderings as on x86, but the instruction set makes them explicit (ldar/stlr for acquire/release).

For bare-metal SPSC between an ISR and a main loop on a single-core Cortex-M:

1// ISR writes to tail, main loop reads tail
2// Only need to prevent compiler reordering — __DMB() or atomic_signal_fence
3void ISR_handler() {
4    buffer[tail_] = new_sample;
5    std::atomic_signal_fence(std::memory_order_release);  // compiler barrier only
6    tail_ = (tail_ + 1) & MASK;
7}

atomic_signal_fence is a compiler barrier without a hardware instruction — correct when the only concern is compiler reordering within a single core.

What can go wrong

ABA problem (MPSC): if you recycle nodes and a producer and consumer race on the same address, the CAS might succeed on a recycled node. The linked-list design above doesn’t have this problem because the sentinel node isn’t recycled.

Memory reclamation: the consumer deletes the old sentinel in pop(). If a producer holds a pointer to a node that the consumer just deleted — in theory impossible in MPSC because the producer exchange completes before the consumer advances — but tricky if you extend the design.

Capacity vs power of two: the SPSC ring uses & (Capacity - 1) instead of % Capacity for the modulo — this requires power-of-two capacity but avoids a division on every push/pop.

Summary

• SPSC: ring buffer, two atomic indices, exclusive ownership per side, acquire/release ordering. ~600 M ops/s.
• MPSC: linked list, atomic exchange on head, single-consumer tail. ~150 M ops/s. No dynamic producer count limit.
• Memory ordering is not optional — get it wrong and the queue works correctly 99.9999% of the time, then silently corrupts data.
• Always align producer and consumer state to separate cache lines.

What’s next

• Memory allocators: pool, arena, and avoiding heap fragmentation — replacing new inside MPSC
• Cache-friendly data structures: AoS vs SoA — applying the same cache-line thinking to bulk data
• FreeRTOS task and queue design — RTOS-provided queues vs lock-free tradeoffs