Lock-free Queues & Memory Ordering

01Why lock-free

Two concrete cases pull an engine toward lock-free queues, and one honest reason to think twice.

• The job pool. Every worker pulls tasks from a shared queue. Put a mutex on it and the workers serialize on that one lock exactly when you wanted them parallel (the scaling problem from the Job Systems tutorial).
• The audio thread. The audio callback runs under a hard deadline. If it takes a mutex and a lower-priority thread holds it, priority inversion can stall the callback past its deadline and the sound glitches. The control thread hands parameters to the audio thread through a lock-free ring instead^[11].
• The counterpoint. Lock-free is genuinely hard to get right and harder to test. Often a mutex plus a ring buffer is fast enough. Reach for lock-free when you can prove the lock is the bottleneck, and prefer it for progress and tail-latency, not raw throughput.

02The memory model in one screen

The Memory Model tutorial builds this in full; here is the working subset. Two ideas, kept separate: atomicity (an operation happens all-or-nothing) and ordering (which writes another thread is guaranteed to see, and when).

• relaxed: atomic, but no ordering. Fine for a counter nobody synchronizes on.
• acquire / release: a release store synchronizes-with an acquire load that reads its value, so everything the writer did before the release becomes visible to the reader after the acquire^[3][4]. This is the pair lock-free queues are built on.
• seq_cst: a single total order over all seq_cst operations, on top of acquire/release. The safe default, the most expensive.

03CAS and the progress taxonomy

Compare-and-swap (CAS) is the universal building block: atomically write a new value only if the location still holds the expected one. Loops of CAS are how multiple threads agree without a lock. But "lock-free" is a precise progress guarantee, and three levels get conflated.

04SPSC: reach for this first

Single-producer, single-consumer is the queue to reach for first, and it needs no CAS at all. The reason: each index has exactly one writer. The producer owns the write index, the consumer owns the read index, so no two threads ever contend to modify the same atomic.

Correctness comes from one acquire/release pair per direction. The producer writes the slot, then does a release store of the write index to publish it; the consumer does an acquire load of the write index before reading the slot. Each side reads its own index with relaxed, because nothing else writes it. Boost documents its spsc_queue as "a wait-free single-producer/single-consumer queue"^[15], and moodycamel's reader-writer queue makes the same claim: wait-free, no CAS loop, not counting the allocation when enqueue grows the queue^[10].

#include <atomic>
#include <cstddef>
#include <type_traits>

template <typename T, size_t Capacity>
class SpscRing {
    static_assert(Capacity > 0 && (Capacity & (Capacity - 1)) == 0,
                  "the & (Capacity - 1) mask needs a power-of-two Capacity");
    static_assert(std::is_trivially_copyable_v<T>,
                  "slots stay live between reuses; pop copies out and never destroys");
    // 64 assumes the line size; portable code uses std::hardware_destructive_interference_size (128 on Apple Silicon).
    alignas(64) std::atomic<size_t> writeIndex{0};   // producer writes, consumer reads
    alignas(64) std::atomic<size_t> readIndex{0};    // own cache line each: no false sharing
    alignas(64) T storage[Capacity];
public:
    bool push(const T& value) {                          // producer thread only
        size_t writePos = writeIndex.load(std::memory_order_relaxed);  // we own it
        size_t readPos = readIndex.load(std::memory_order_acquire);    // pairs with consumer release
        if (writePos - readPos == Capacity) return false;              // full
        storage[writePos & (Capacity - 1)] = value;
        writeIndex.store(writePos + 1, std::memory_order_release);     // publish
        return true;
    }
    bool pop(T& out) {                                     // consumer thread only
        size_t readPos = readIndex.load(std::memory_order_relaxed);    // we own it
        size_t writePos = writeIndex.load(std::memory_order_acquire);  // pairs with producer release
        if (writePos == readPos) return false;                         // empty
        out = storage[readPos & (Capacity - 1)];
        readIndex.store(readPos + 1, std::memory_order_release);       // free the slot
        return true;
    }
};

use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicUsize, Ordering};

// CAPACITY is a power of two; one writer per index means no CAS.
pub struct SpscRing<T: Copy, const CAPACITY: usize> {
    write_index: AtomicUsize,           // producer writes, consumer reads
    read_index: AtomicUsize,            // production: pad each onto its own cache line (crossbeam's CachePadded)
    storage: [UnsafeCell<T>; CAPACITY], // UnsafeCell: slots are written through &self
}

// Sound to share across threads because the unsafe blocks below never touch
// the same slot concurrently; the contract is one producer thread, one consumer.
unsafe impl<T: Copy + Send, const CAPACITY: usize> Sync for SpscRing<T, CAPACITY> {}

impl<T: Copy, const CAPACITY: usize> SpscRing<T, CAPACITY> {
    pub fn push(&self, value: T) -> Result<(), T> {         // producer only
        const { assert!(CAPACITY.is_power_of_two()) }       // the & (CAPACITY - 1) mask depends on it
        let write_pos = self.write_index.load(Ordering::Relaxed);   // we own it
        let read_pos = self.read_index.load(Ordering::Acquire);     // pairs with consumer release
        if write_pos - read_pos == CAPACITY { return Err(value); }  // full
        // Sound: this slot is outside the live range [read_pos, write_pos),
        // and only this producer thread ever writes slots.
        unsafe { *self.storage[write_pos & (CAPACITY - 1)].get() = value; }
        self.write_index.store(write_pos + 1, Ordering::Release);   // publish
        Ok(())
    }
    pub fn pop(&self) -> Option<T> {                        // consumer only
        let read_pos = self.read_index.load(Ordering::Relaxed);     // we own it
        let write_pos = self.write_index.load(Ordering::Acquire);   // pairs with producer release
        if write_pos == read_pos { return None; }                    // empty
        // Sound: the acquire above saw the producer's release, so the slot's
        // write happened-before this read, and the producer will not reuse
        // the slot until read_index moves past it.
        let value = unsafe { *self.storage[read_pos & (CAPACITY - 1)].get() };
        self.read_index.store(read_pos + 1, Ordering::Release);     // free the slot
        Some(value)
    }
}

The widget runs it. The producer and consumer indices chase around the ring; no lock is ever held, and neither index is ever touched by two threads:

05Bounded MPMC: Vyukov

Many producers and many consumers can't each own an index, so you need an atomic read-modify-write. Dmitry Vyukov's bounded MPMC queue, built on CAS, is a common choice, and the Job Systems tutorial uses it^[5].

It's a fixed array of cells, each holding a payload plus an atomic sequence number, with two position counters. To enqueue: load the enqueue position, index the cell, and compare its sequence to the position. If they're equal the cell is free, so CAS the position forward and, on success, write the payload and release-store the cell's sequence to mark it ready. Dequeue mirrors this. The cell sequence is loaded with acquire and stored with release; the position counters use relaxed CAS.

06The ABA problem

ABA is the classic lock-free trap. A CAS reads value A; another thread changes the location A → B → A (often by freeing a node and the allocator handing the same address back); the original CAS then succeeds because the bits match, even though the "A" is now a different object or freed memory: a false-positive CAS.

Three families of fix, and the trap inside the first one:

• Tagged / versioned pointers: pack a counter into spare pointer bits (or use double-width CAS) so A-then-A still differs by the tag.
• Hazard pointers: readers publish what they're dereferencing; a writer won't free anything a hazard slot names.
• Epoch-based reclamation: retire freed nodes into epoch buckets and free only after every thread has moved on. Rust's crossbeam-epoch ships this^[9].

Step through it. Thread A reads the top, pauses; thread B pops two nodes, frees them, and pushes a new node at the recycled address; A resumes and its CAS wrongly succeeds. Turn on tags: the CAS fails, and one more step runs the retry:

07x86 vs ARM: the latent bug

The most dangerous thing about lock-free code is that a wrong version often passes every test on your desktop. x86's memory model (TSO) is strong: in hardware, a plain load is already an acquire and a plain store already a release^[7][8]. So relaxed where you needed acquire/release usually goes unpunished, but it is not correct: the hardware supplies the ordering, and the compiler is still free to reorder your other loads and stores around a relaxed atomic.

ARM and POWER are weak: those reorderings really happen. The Cambridge lowering table makes it concrete: an acquire/release on x86 compiles to a plain MOV, while on AArch64 it needs LDAR/STLR instructions^[6]. So a missing acquire/release is invisible on your dev box and corrupts state on a Switch, a phone, or Apple Silicon. It's a bug, not a timing fluke.

Run the message-passing test: writer sets data = 42 then sets a flag; reader waits on the flag then reads data. Toggle the ordering and the hardware model:

08When not to go lock-free

The strongest practical advice in this tutorial: most of the time, don't hand-roll it. Lock-free correctness is subtle on weak hardware, hard to test because races hide, and easy to get wrong in reclamation.

The expert consensus is to use a proven implementation. The C++ Core Guidelines say not to use lock-free programming "unless you absolutely have to"; the alternative CP.100 lists is lock-free structures "implemented by others as part of some library"^[12]. In practice: in C++ reach for moodycamel::ConcurrentQueue (MPMC) or ReaderWriterQueue (SPSC, wait-free)^[10]; in Rust reach for crossbeam's ArrayQueue (bounded MPMC), SegQueue (unbounded), and crossbeam-deque (the Chase-Lev work-stealing deque^[13], weak-memory-correct, used under Rayon)^[9][14]. The code in this tutorial is for understanding; ship the library.

09Pitfalls

10What's next

That fills the last gap in the concurrency foundation, alongside the Memory Model, Allocators, and Job Systems. The lock-free ring here is exactly what feeds the audio thread later. With the foundations done, the series turns to the renderer: The GPU & Graphics Pipeline, then your first triangle in Vulkan. The full path is on the series hub.

1. Jeff Preshing. "An Introduction to Lock-Free Programming." preshing.com. Lock-free as system-wide progress; the "lock" means lock-up, not mutex.
2. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann. The obstruction-free / lock-free / wait-free progress hierarchy and the ABA problem.
3. Jeff Preshing. "Acquire and Release Semantics." preshing.com. The synchronizes-with edge a release store forms with an acquire load that reads it.
4. cppreference. std::memory_order. en.cppreference.com. The exact relaxed / acquire / release / seq_cst semantics.
5. Dmitry Vyukov. "Bounded MPMC queue." 1024cores. The per-cell sequence-number design, the orderings, and the "not lockfree in the official meaning" caveat.
6. Cambridge Computer Lab. "C/C++11 mappings to processors." cl.cam.ac.uk. The instruction lowering per ordering per ISA: x86 MOV vs AArch64 LDAR/STLR.
7. Peter Sewell et al. "x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors." cl.cam.ac.uk. The formal x86 store-buffer model (loads acquire, stores release, for free).
8. The Rustonomicon. "Atomics." doc.rust-lang.org. Acquire/release pairing in Rust, "often totally free" on strongly-ordered platforms.
9. crossbeam (Rust). github.com/crossbeam-rs/crossbeam. Epoch-based reclamation, ArrayQueue/SegQueue, and the Chase-Lev crossbeam-deque.
10. Cameron Desrochers. moodycamel ConcurrentQueue and ReaderWriterQueue. github.com/cameron314/readerwriterqueue. The lock-free MPMC queue and the wait-free SPSC ReaderWriterQueue.
11. Ross Bencina. "Real-time audio programming 101: time waits for nothing." rossbencina.com. Why the audio callback must not lock, and the lock-free ring pattern.
12. C++ Core Guidelines, Concurrency (CP.100–CP.101). isocpp.github.io. CP.100: don't use lock-free programming unless you absolutely have to; its listed alternative is a library implementation.
13. David Chase and Yossi Lev. "Dynamic Circular Work-Stealing Deque." SPAA 2005. vanderbilt.edu. The work-stealing deque behind job systems.
14. Nhat Minh Lê et al. "Correct and Efficient Work-Stealing for Weak Memory Models." PPoPP 2013. fzn.fr. The acquire/release fixes that make Chase-Lev correct on ARM/POWER.
15. Boost.Lockfree documentation. boost.org. Describes spsc_queue as "a wait-free single-producer/single-consumer queue".