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 (the high-priority callback stuck waiting on a lock a low-priority thread holds) 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, a fixed array used as a circular queue, 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

A producer writes a slot, then bumps an index; the consumer sees the new index but reads the slot's old contents. Whether that can happen is decided by the memory ordering on the index. 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 (a store tagged memory_order_release) synchronizes-with, that is, forms an ordering edge with, an acquire load (tagged memory_order_acquire) 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

Two workers try to take the next job at the same instant. With no lock, something has to decide which one gets it and tell the other to try again. 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

The audio thread's command queue has exactly one writer, the game thread, and one reader, the callback. Single-producer, single-consumer (SPSC: one thread pushes, one thread pops) 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 is the x86 line size; Apple Silicon lines are 128 bytes, so pad to 128 when shipping there.
    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

A job queue has every worker pushing and popping, so no index has a single owner. Many producers and many consumers can't each own an index, so you need an atomic read-modify-write: read, compute and write back as one indivisible step, as CAS does. Dmitry Vyukov's bounded MPMC (multi-producer, multi-consumer) 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

A lock-free stack can pass its tests for weeks before a crash dump shows its top pointing into freed memory. ABA is the classic lock-free trap behind that. 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, a CAS over two adjacent words such as x86's CMPXCHG16B) 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

A queue runs for months on PC and PS5, then corrupts data on the first Switch build. The most dangerous thing about lock-free code is that a wrong version often passes every test on your desktop. x86's memory model (its rules for how one thread's memory operations can appear reordered to another) is TSO, total store order, and it's 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, meaning the hardware may reorder independent loads and stores unless told not to: those reorderings really happen. The Cambridge lowering table makes it concrete: an acquire/release on x86 compiles to a plain MOV, while on AArch64, the 64-bit Arm instruction set, it needs LDAR/STLR instructions^[6]. So a missing acquire/release can stay invisible on your dev box and corrupt state on a Switch, a phone, or Apple Silicon: the bug was always there, and the weaker hardware exposes it.

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

You've profiled a queue, the lock shows up, and you're about to write your own lock-free version. 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, whose owner pushes and pops one end while idle threads steal from the other^[13], weak-memory-correct, used under Rayon)^[9][14]. The code in this tutorial is for understanding; ship the library.

09Pitfalls

A lock-free queue that passes its tests can still starve a thread, corrupt data on Arm, or run slower than the mutex it replaced. The usual causes:

10What's next

Next in the series: 3D Math for Games. The concurrency foundation is done, and the series moves to the math every system after it uses: vectors, matrices and quaternions, then IEEE-754 floating point, then the runtime spine (the game loop, the platform window, input) before the renderer.

This page fills the last gap in that foundation, alongside the Memory Model, Allocators, and Job Systems. The Audio tutorial reuses this SPSC ring to hand play commands to the audio callback. 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. doi.org; PDF (archived). 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".