vault

The Treiber Stack and Michael-Scott Queue

16 min read

The Treiber Stack and Michael-Scott Queue

These are the two canonical lock-free data structures — the ones every treatment of non-blocking programming walks first, because between them they teach the whole craft. The Treiber stack (R. Kent Treiber, IBM 1986) is a singly linked list with an atomic head: push and pop are each a single compare-and-swap (CAS) loop, which makes it the simplest lock-free structure that exists and the textbook home of The ABA Problem. The Michael–Scott queue (Maged Michael & Michael Scott, PODC 1996) is the standard lock-free FIFO: a singly linked list with separate Head and Tail pointers, a dummy sentinel node that removes the empty/single-element special cases, and the famous “help advance the tail” step by which any thread finishes another thread’s half-done enqueue (Michael & Scott 1996). Both are non-blocking: a stalled thread can never prevent others from completing — the property that makes them robust to preemption, page faults, and cache misses where a lock would freeze the whole structure.

This note is the theory: the structures walked node by node, why each CAS is placed where it is, and why both need ABA defenses and safe memory reclamation to be correct. The precise progress vocabulary is in Lock-Free Wait-Free and Obstruction-Free; the atomic primitive is in Compare-and-Swap and Load-Linked Store-Conditional; the reclamation schemes are Hazard Pointers and Epoch-Based Reclamation.

Mental Model — One CAS Point vs Two

The essential design difference: a stack mutates at one end, so it has a single contended pointer (head) and every operation is one CAS. A FIFO queue mutates at two ends — enqueue at the tail, dequeue at the head — so a naive single-pointer scheme cannot atomically keep the list consistent while both ends move. Michael & Scott’s insight is to (a) keep a dummy node so the list is never empty and Head/Tail never go NULL, and (b) split an enqueue into two CAS steps — link the new node, then swing the tail — and let any thread perform the second step on behalf of a straggler. That “any thread can finish it” is what keeps the queue non-blocking despite the two-step update.

flowchart LR
    subgraph Stack["Treiber stack — one CAS point"]
      H1["head"] --> A1["A"] --> B1["B"] --> C1["C"]
    end
    subgraph Queue["Michael-Scott queue — dummy + Head/Tail"]
      HH["Head"] --> D0["dummy"]
      D0 --> X1["x1"] --> X2["x2"]
      TT["Tail"] --> X2
    end

What it shows and the insight to take: the stack (top) is a single chain with one atomic entry point — trivially simple, one CAS per op. The queue (bottom) always has a dummy node at the front that Head points to; the real front element is dummy->next, and Tail points at the last node — or lags one behind it during the window between an enqueue’s two CASes. The takeaway: the dummy node is not decoration — it is what lets Head and Tail never alias dangerously and never fall off the end, collapsing a swarm of empty/one-element edge cases into the common path.

The Treiber Stack

Structure and operations

The stack is a singly linked list of nodes, each with a value and a next pointer, plus a shared atomic head. It first appeared in R. Kent Treiber’s 1986 IBM Almaden technical report Systems Programming: Coping with Parallelism (report RJ 5118), which studied shared-data hazards on the IBM System/370 and its compare and swap instruction (Treiber stack, Wikipedia; referenced as [21] in Michael & Scott 1996).

Uncertain

Verify: Treiber’s original report number (RJ 5118), year (1986), and exact title Systems Programming: Coping with Parallelism, plus whether Treiber’s original stack used a version/modification counter in the head word. Reason: the primary IBM report was unreachable during research (server refused the connection); details here are from Wikipedia and Michael & Scott’s citation of [21]. To resolve: retrieve the IBM report RJ 5118 PDF from IBM Research and read the stack routine directly. #uncertain

struct Node { Value value; Node* next; };
_Atomic(Node*) head;   // shared
 
void push(Value v) {
    Node* n = new Node{v, NULL};
    Node* old;
    do {
        old  = atomic_load(&head);   // (1) snapshot current top
        n->next = old;               // (2) point new node at it
    } while (!CAS(&head, old, n));   // (3) install n as top iff head still == old
}
 
bool pop(Value* out) {
    Node* old;
    Node* next;
    do {
        old = atomic_load(&head);    // (1) snapshot top = A
        if (old == NULL) return false;   // empty
        next = old->next;            // (2) read A->next = B  (BEFORE the CAS — the ABA window)
    } while (!CAS(&head, old, next));// (3) swing head A -> B iff head still == A
    *out = old->value;
    // reclaim old  <-- unsafe without a reclamation scheme
    return true;
}

Line by line. push builds a node, snapshots the old top, links its next to that snapshot, and CASes itself in; if a concurrent push/pop moved head in between, the CAS fails and the loop retries with a fresh snapshot — no lock, no blocking. pop snapshots head into old, reads old->next into next, and CASes head from old to next. The correctness of push is airtight: even under contention it only ever links a new node atop whatever the current top is. pop is where the danger lives, for two reasons that must be handled separately.

Why the Treiber stack is the home of ABA

First, the classic ABA: pop reads next = old->next = B before the CAS. If, between that read and the CAS, other threads pop A, pop B, free(B), and then push a recycled node at address A again, the CAS CAS(&head, A, B) succeeds (head is bit-for-bit A) and installs the freed pointer B as the new top — corruption (ABA problem, Wikipedia). Treiber’s own environment addressed this with a modification counter packed alongside the pointer (System/370 offered a double-width compare — compare double and swap), the same versioned-pointer trick the queue below uses.

Second, and independent of ABA, is plain use-after-free: even with a version counter on head, if a thread reads old->next while another thread has already freed old, the read faults. So the Treiber stack is only correct in the abstract; a real implementation must add a version counter (defends the head slot) and a memory-reclamation discipline (defends the node body). A hazard pointer approach needs exactly one hazard pointer per thread for the Treiber stack — the thread publishes old before dereferencing old->next, so old cannot be freed underneath it (Michael 2004). In a garbage-collected runtime both problems dissolve, because the node’s address is never recycled while any reference (even a racing stale one) exists.

Michael & Scott note in passing that Treiber’s stack is “simple and efficient,” and they in fact reuse it to implement the non-blocking free list behind their queue (Michael & Scott 1996 §2) — the Treiber stack is the workhorse allocator inside the more famous queue.

The Michael-Scott Queue

Structure

A singly linked list with a ⟨pointer, count⟩ pair for Head and Tail and for each node’s next; the count is the modification counter that suppresses ABA (increment on every successful CAS). Head always points to a dummy node — the first node in the list, whose value is ignored; the real front element is Head->next. Tail points to the last or the second-to-last node — it is allowed to lag by one during an in-progress enqueue. The paper’s exact declarations:

structure pointer_t { ptr: pointer to node_t, count: unsigned integer }
structure node_t    { value: data type, next: pointer_t }
structure queue_t   { Head: pointer_t, Tail: pointer_t }

initialize(Q):
    node = new_node()          # a dummy node
    node->next.ptr = NULL
    Q->Head = Q->Tail = node   # both point at the dummy

Enqueue — link, then swing (and help)

The paper’s enqueue, line labels E1–E17 (Michael & Scott 1996, Figure 1):

enqueue(Q, value):
E1:  node = new_node()
E2:  node->value = value
E3:  node->next.ptr = NULL
E4:  loop
E5:      tail = Q->Tail                                   # read Tail (ptr+count together)
E6:      next = tail.ptr->next                            # read tail's next (ptr+count together)
E7:      if tail == Q->Tail                               # is our snapshot still consistent?
E8:          if next.ptr == NULL                          # was Tail really pointing at the last node?
E9:              if CAS(&tail.ptr->next, next, <node, next.count+1>)  # try to LINK node at the end
E10:                 break                                # success — leave the loop
E11:              endif
E12:          else                                        # Tail was lagging (points to 2nd-to-last)
E13:              CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)       # HELP: advance Tail forward
E14:          endif
E15:      endif
E16:  endloop
E17: CAS(&Q->Tail, tail, <node, tail.count+1>)            # try to swing Tail to the node we just linked

Walk-through. Lines E1–E3 build the node. The loop reads a consistent snapshot of the tail: E5 reads Tail, E6 reads that node’s next, and E7 re-reads Tail to confirm it hasn’t moved since E5 — this “read, read, re-check” is Michael & Scott’s lightweight substitute for a full snapshot (they only need to re-verify one shared variable, simpler than Prakash et al.’s two-variable snapshot). Then the fork at E8:

  • If next.ptr == NULL (E8), Tail genuinely points at the last node, so E9 attempts the real work: CAS the last node’s next from NULL to our new node. This is the linearization point of the enqueue — the instant the item joins the queue. On success, E10 breaks out.
  • If next.ptr != NULL (E12), then Tail is lagging — some other enqueuer linked a node at E9 but has not yet swung Tail (its E17 hasn’t run). Rather than wait, this thread helps: E13 CASes Tail forward to next.ptr. This is the celebrated helping step; it is what keeps the queue non-blocking despite the two-phase update, because no enqueue depends on any particular thread performing the tail swing — anyone can.

After breaking out, E17 tries to swing Tail to the node we just linked. Note it is a plain CAS whose failure is ignored: if it fails, it is only because another thread already advanced Tail for us (via its own E13 help step), which is exactly the outcome we wanted. The enqueue is already linearized at E9; E17 is cleanup.

Dequeue — read value, then swing Head

The dequeue, labels D1–D20:

dequeue(Q, pvalue):
D1:  loop
D2:      head = Q->Head                                   # read Head
D3:      tail = Q->Tail                                   # read Tail
D4:      next = head.ptr->next                            # read Head's next
D5:      if head == Q->Head                               # consistent snapshot?
D6:          if head.ptr == tail.ptr                      # empty, or Tail lagging?
D7:              if next.ptr == NULL                      # queue empty
D8:                  return FALSE
D9:              endif
D10:             CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)   # HELP: advance a lagging Tail
D11:         else                                         # queue non-empty, Tail fine
D12:             *pvalue = next.ptr->value                # READ VALUE *before* the CAS
D13:             if CAS(&Q->Head, head, <next.ptr, head.count+1>) # swing Head to next
D14:                 break
D15:             endif
D16:         endif
D17:     endif
D18: endloop
D19: free(head.ptr)                                       # free the OLD dummy node
D20: return TRUE

Walk-through. D2–D4 snapshot Head, Tail, and Head->next, and D5 re-checks Head for consistency. Then D6 asks whether Head and Tail point at the same node. If they do, either the queue is empty (D7: next.ptr == NULL → return FALSE at D8) or the queue has one element but Tail is lagging behind Head — in which case the dequeuer helps advance Tail at D10 before retrying, so a stalled enqueuer cannot block dequeues. If Head != Tail (D11), there is a real element to remove: the front value is in Head->next->value (recall the front element is after the dummy).

The single most important line is D12: read next.ptr->value before the CAS at D13. The paper’s own comment is emphatic — if you CAS Head first, another dequeue could free the node before you read its value (Michael & Scott 1996, Figure 1). After a successful D13, Head swings to next.ptr — which now becomes the new dummy — and the old dummy (head.ptr) is freed at D19. Because Head moved off it and, by construction, Tail never lags behind Head, the old dummy has no live pointer into it, so freeing it is safe. This “dequeue turns the removed front into the new dummy” is the elegant trick that makes the sentinel self-perpetuating.

Why it is correct — and why it still needs reclamation

Michael & Scott prove safety via five invariants that hold by induction assuming ABA never occurs: the list stays connected; nodes are only inserted after the last node; nodes are only deleted from the front; Head always points at the first node; Tail always points at a node in the list (§3.1). They prove linearizability by naming the exact take-effect point of each operation: an enqueue linearizes when the new node is linked (E9), a dequeue when Head swings (D13) (§3.2; on linearizability see Linearizability as a Correctness Condition). And they prove non-blocking liveness: a thread loops more than a bounded number of times only if some other thread completed an operation — so the system as a whole always makes progress (§3.3).

That proof rests on the ABA-never-occurs assumption, which the algorithm secures with its ⟨ptr, count⟩ versioned pointers — every CAS installs count+1, so an A→B→A on any pointer is caught by the changed counter. Implementing that needs a double-width CAS (to swap pointer and counter atomically) or array indices sharing a word with a counter (§1). Separately, the queue still needs safe reclamation for the node bodies: a dequeuer reads next.ptr->value (D12) that another thread might free; hazard pointers solve this with two hazard pointers per thread (guarding Head and its next) (Michael 2004). The two defenses are orthogonal: the counter protects the slots, reclamation protects the nodes.

The two-lock queue — the blocking cousin

The same paper offers a two-lock queue for machines without a universal atomic like CAS. It keeps the dummy node but guards Head with an H_lock and Tail with a T_lock, so one enqueue and one dequeue can proceed concurrently — enqueuers touch only Tail, dequeuers only Head, and the dummy is what keeps those two disjoint (no deadlock from cross-ordering) (Michael & Scott 1996, Figure 2). It is blocking (a preempted lock-holder stalls its end) but far simpler and, on a busy queue, beats a single global lock. It is the right default when you only have test-and-set.

Failure Modes and Common Misunderstandings

Forgetting to read the value before swinging Head. Reordering D12 after D13 is the single most common hand-rolled bug: the node can be freed by a racing dequeue between the CAS and the read, yielding garbage or a fault. The value read must precede the head CAS.

Assuming Tail always points at the last node. It does not — it may lag by one during the window between an enqueue’s E9 and E17. Code that dereferences Tail->next assuming NULL will misbehave; that is exactly why enqueue checks next.ptr == NULL at E8 and helps at E13.

Dropping the version counter on a non-GC platform. Without it, ABA silently corrupts under contention + allocator reuse. The bug is rare, non-deterministic, and load-dependent — the worst kind.

Believing lock-free means faster. On an uncontended queue a single lock is often faster (no CAS retries, better cache behavior). Lock-free wins under contention and, decisively, under multiprogramming — where a preempted lock-holder freezes a blocking queue but merely gets “helped past” in the non-blocking one, which is the whole point of Michael & Scott’s multiprogrammed experiments (§4).

Treiber stack contention collapse. All pushes and pops hammer one head word; under high concurrency the CAS retry rate explodes and throughput collapses. The fix is not a better CAS but a different structure — see the elimination-backoff stack below.

Alternatives and When to Choose Them

  • Treiber stack vs a lock-guarded stack: prefer Treiber when you need non-blocking progress and contention is low-to-moderate; add an elimination-backoff array (Hendler, Shavit & Yerushalmi 2004) when contention is high — pairs of a concurrent push and pop can “cancel out” on a side array without ever touching the central stack, restoring scalability the bare Treiber stack loses.
  • Michael–Scott queue vs the two-lock queue: MS queue for multiprogrammed or preemption-prone environments and machines with CAS; two-lock queue for machines with only test-and-set, or when simplicity outweighs the last drop of contention performance (§4).
  • MS queue vs bounded array queues (e.g. LMAX Disruptor-style ring buffers): a linked MS queue is unbounded and allocation-heavy; a preallocated ring buffer avoids per-op allocation and reclamation entirely but must handle full/empty and is bounded. Choose the ring buffer when the capacity is known and allocation churn matters.
  • MS queue vs message passing: if you can restructure to avoid a shared queue at all (e.g. per-worker queues with work-stealing, or CSP channels), you often sidestep the whole reclamation problem — see Shared Memory versus Message Passing.

Production Notes

The Michael–Scott queue is one of the most widely deployed concurrent algorithms in existence. Java’s java.util.concurrent.ConcurrentLinkedQueue (Doug Lea) is a Michael–Scott queue adapted for a garbage-collected runtime: GC removes ABA-by-recycling, so the counted pointers are dropped, and Lea adds lagged head/tail updates and lazySet writes to cut cache traffic (openjdk source). In C++, boost::lockfree::queue is a Michael–Scott queue with a freelist and tagged pointers for ABA; and the reclamation machinery this class of structure needs is now standardized as std::hazard_pointer in C++26 (cppreference).

The original evaluation is worth internalizing: on a 12-processor SGI Challenge multiprocessor, the new lock-free queue consistently beat every prior alternative (Prakash et al.’s non-blocking queue, Valois’s queue, Mellor-Crummey’s blocking queue, and a single lock), across both dedicated and multiprogrammed runs, over one million enqueue/dequeue pairs (§4). The multiprogrammed result is the durable lesson: when you oversubscribe processors — twice as many processes as CPUs — the blocking queues degrade sharply because a preempted lock-holder stalls everyone, while the non-blocking queue’s helping mechanism lets other threads simply route around the stalled one. That robustness to unpredictable delay, not raw single-thread speed, is the real reason non-blocking structures earn their complexity.

See Also

Graph View

Backlinks