Lock-Free Stacks, Queues, and Ring Buffers

From a single word to a whole data structure

Guide 2 left you with one primitive and its one famous bug: compare-and-swap atomically updates a single machine word, and the CAS retry loop turns that into 'read the current value, compute a new one, swap it in only if nobody changed it underneath me, else try again'. That is enough to bump a counter. But a stack or a queue is not one word — it is a web of nodes linked by pointers, and CAS can only swing one pointer at a time. The whole craft of lock-free data structures is arranging the layout so that the one CAS you are allowed each step lands on exactly the pointer that publishes your change atomically, making the structure go from a valid old state to a valid new state with no broken intermediate that another thread could trip over.

We will build three structures of rising difficulty. A stack has one mutable pointer — the top — so a single CAS suffices and the code is short enough to hold in your head. A queue has two ends, head and tail, that must stay consistent, so it needs a cleverer dance and the helping idea. A ring buffer in its easiest single-producer single-consumer form needs no CAS at all — just two indices and the right acquire/release ordering — which makes it the fastest and the one you will reach for most. Watching them in order shows how the difficulty scales with the number of mutable pointers, and where each structure hits the wall that the next two guides exist to break.

The Treiber stack: one pointer, one CAS

The Treiber stack (R. Kent Treiber, IBM, 1986) is the friendly first lock-free structure because it has exactly one mutable thing: an atomic pointer `top` to the head node, and every node holds a `next` pointer. To push a new node n, you read the current top, point n->next at it, then CAS top from that old value to n. If the CAS fails, someone pushed or popped in between, so you re-read top, re-link n->next, and retry — a textbook retry loop. To pop, you read top, read its next, then CAS top from the node to that next; on success the old top is yours to return. One CAS publishes the entire change because the stack's whole identity lives in that one pointer.

// push(n)                                  // pop() -> node or NULL
do {                                        do {
    old = top.load(acquire);                    old = top.load(acquire);
    n->next = old;                              if (old == NULL) return NULL;
} while (!top.compare_exchange_weak(             next = old->next;     // <-- ABA reads here
            old, n, release, relaxed));     } while (!top.compare_exchange_weak(
                                                        old, next, acquire, relaxed));
// success: n is the new top                 // success: 'old' is unlinked, return it

Two details make it correct rather than merely plausible, and both are payoffs from earlier rungs. The memory ordering is not decoration: the push uses release on its successful CAS so that the writes filling the new node are sealed behind it, and the pop uses acquire so the popping thread actually sees that node's contents — this is the same publish/subscribe handshake from the memory-model rung, now load-bearing inside a real structure. Get the ordering wrong and the node's data appears half-written on the other core. The CAS being lock-free is the other payoff: a failed CAS means some thread made progress (it changed top), so the system as a whole never stalls, even though your particular thread may loop.

The Michael-Scott queue: two ends and the helping trick

A FIFO queue is harder because it has two pointers that must agree: `head` (where you dequeue) and `tail` (where you enqueue). You cannot move both with one CAS, so a naive design has a window where head and tail disagree and another thread sees a broken queue. The Michael-Scott queue (Maged Michael and Michael Scott, 1996) is the answer that shipped — it lives inside `java.util.concurrent` and countless C libraries. Its first idea is a permanent dummy node: the queue is never truly empty, so head and tail always point at real nodes and the empty case stops being a special, fragile branch.

The clever part is enqueue, which it splits into two CAS steps and makes safe with helping. Step one: CAS the last node's `next` pointer from NULL to your new node — this is the real, linearizing publish, the instant your node joins the queue. Step two: CAS `tail` forward from the old last node to your new node. Between these two steps the queue is in a legal but 'lagging' state: the node is linked in, but `tail` still points one short. The breakthrough is that any thread which notices tail is lagging finishes the job for whoever fell behind — it does the step-two CAS itself before proceeding. Because everyone helps, no thread's stall can block the queue, and a thread that dies between step one and step two leaves a state others repair automatically.

1. Read tail, then read tail->next. If next is non-NULL, tail is lagging — help by CAS-ing tail forward to next, then restart. (This is the helping step that repairs a half-finished enqueue.)
2. If next is NULL, the read tail really is the last node. CAS its next from NULL to your new node. If this fails, someone beat you; restart the whole loop.
3. On success your node is now linked in — that link is the linearization point, the moment the enqueue 'officially' happened. Then do a best-effort CAS to swing tail forward; if it fails, fine, the next thread will help.

Dequeue mirrors this: read head, read head->next (the first real element behind the dummy), copy out its value, then CAS head forward to that next, retiring the old dummy. The MS-queue is genuinely lock-free at both ends, and helping is what buys that guarantee — it converts 'I must wait for the slow thread to finish' into 'I finish the slow thread's leftover myself'. But notice the same shadow: dequeue unlinks a node that another thread may still be reading through its own stale `head`. Two CAS-driven ends did not make the reclamation problem go away; they doubled it.

The SPSC ring buffer: no CAS, just two indices

Now the surprise: the fastest lock-free queue often uses no CAS at all. A single-producer single-consumer ring buffer is a fixed array of N slots plus two indices: a `head` only the consumer advances and a `tail` only the producer advances. Because exactly one thread writes each index, there is no read-modify-write contest over it — no CAS, no retry loop, no ABA. The producer writes a slot then advances tail; the consumer reads a slot then advances head. The array is treated as a circle: index N wraps to 0, usually via `& (N-1)` when N is a power of two, so the wrap is a cheap mask instead of a divide.

What replaces CAS is ordering. The producer must finish writing the slot before it publishes the new tail, and the consumer must read the new tail before it reads the slot — otherwise the consumer reads a slot the producer has not filled yet. That is precisely an acquire/release handshake: the producer does a release store on tail (sealing the slot write behind it), the consumer does an acquire load on tail (so seeing the new tail guarantees seeing the slot). The structure is empty when head equals tail and full when advancing tail would collide with head. This is the same happens-before machinery from the memory-model rung, now the entire synchronization mechanism — no lock, no CAS, just two one-way fences.

What 'correct' means here, and what still leaks

How do we even claim these are correct when operations from different threads interleave in countless ways? The standard is linearizability: every operation appears to take effect instantaneously at some single point between its call and its return, and the resulting sequence is a legal history of an ordinary, single-threaded stack or queue. That is why we kept naming the linearization point — the CAS that swings top, the CAS that links the queue node, the release-store on tail. Pin down that one instant for every operation and a tangle of concurrent calls becomes equivalent to one tidy sequential order, which is exactly the mental model you already have for a normal data structure. Linearizability is the contract that lets you reason about these without tracking every interleaving by hand.

But honesty matters more than a clean ending. Two of these three structures are correct only with a reclamation strategy we have deliberately not supplied. The Treiber stack's pop and the MS-queue's dequeue both unlink a node that another thread may still be reading — free it too early and you get use-after-free or revive the ABA problem; never free it and you get an unbounded memory leak. The bounded ring buffer dodges this entirely by never allocating, which is a large part of why it is the easiest and fastest, and a hint that bounding your memory is one of the strongest tools you have. For the unbounded structures, *when can I free this node?* is the unanswered question, and it is genuinely hard.

So that is the honest shape of this rung. You can now build the three workhorses — and you have seen the same crack run through two of them. The next guide picks up exactly that crack: hazard pointers and epoch-based reclamation, two ways to answer *when is it safe to free a node?* without a lock. The last guide then pushes to RCU and the brutal reason all of this is so easy to get subtly, silently wrong. The data structures were the easy half; safe reclamation is the half that humbles experts.