Cairn
data structures · concurrency · O(1) amortized per enqueue/dequeue barring CAS retries, O(n) space, lock-free (not wait-free, not starvation-free)

↩ back to Concurrency

Michael-Scott Queue

The Treiber Stack showed what a lock-free structure buys on top of hardware compare-and-swap: no lock, one shared pointer, one CAS per operation. A FIFO queue needs two ends — enqueue works at the tail, dequeue works at the head — and that's exactly the complication a stack never has to face: two pointers racing independently means one of them can legitimately fall behind the other's own idea of where the queue really ends. Maged Michael and Michael Scott published the standard solution to this in 1996, and it's the textbook second lock-free structure taught right after Treiber's stack for exactly that reason: same CAS primitive, same retry-on-failure loop shape, but a genuinely new hazard neither a single-pointer structure nor a busy-wait algorithm on this site has any analogue for.

Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that a lagging tail is real and recoverable, and exactly what breaks if the recovery step is dropped — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.

Try it

Pick a scenario (how many enqueue/dequeue operations each of two threads runs) and a dequeue variant — Correct (helps advance a lagging tail) is the real Michael-Scott algorithm; Naive (head == tail always means empty) skips the one check that makes it work — then either step through by hand with Step T0 / Step T1, or press Explore all schedules to search every reachable interleaving at once. Try the Minimal (T0: enqueue · T1: dequeue) scenario with the Naive variant first — it reports a phantom empty queue in as little as 4 moves. Switch to Correct with the same scenario and it vanishes completely, at every one of the same states.

Pick a scenario and dequeue variant, then step each thread by hand.

Why it works

The queue is a singly-linked list that always holds at least one node, even when logically empty: a permanent dummy node that head points to. Real values live in the nodes after the dummy — head.next is the first real item, if any. Two shared pointers, head and tail, are each updated with their own CAS, independently of each other. enqueue(v) allocates a new node, reads tail and that node's own next, and if next is null — tail really is pointing at the last node — tries to link the new node on with one CAS (CAS(tail.next, null, newNode)). Either way, right after that loop exits, it makes one further, un-retried attempt to swing tail itself forward to the node it just linked. dequeue() reads head, tail, and head.next; if there's a real next node, it reads that node's value, then tries to swing head onto it with one CAS — the old head node (the previous dummy) is retired, and the node that just got read becomes the new dummy, its own value field never looked at again.

The genuinely new piece, with nothing like it on either of this site's other lock-based Concurrency pages or on the Treiber Stack: what does enqueue's own retry loop do when it reads tail and finds tail.next is not null? That means some earlier enqueue already linked a node on, but hasn't yet run its own follow-up tail-swing — tail is pointing one node behind the real end of the list. The textbook answer isn't "wait for that other thread to finish": it's "fix it yourself, then retry." Any thread — enqueuing or dequeuing — that finds a lagging tail performs the exact same CAS (CAS(tail, staleTail, staleTail.next)) that thread was eventually going to run anyway, then loops back around. Nobody waits on anybody else's progress; whoever notices the gap first just closes it. This is what a lock-free structure needs to guarantee that some thread always makes progress even though no thread is ever required to finish what it started before another thread builds on top of it.

dequeue needs the identical check for a different reason. head === tail is ambiguous by construction: it's true both when the queue is genuinely empty (dummy has no real node after it) and for the brief window right after an enqueue has linked a new node but hasn't swung tail onto it yet — in that second case head.next is already the real new node. Reporting "empty" is only correct in the first case. The Pitfalls section below exists entirely because that distinction is easy to get wrong without touching a single line of the actual linking logic.

Reference implementation

Pseudocode compareAndSwap(ref, expected, next) stands for the real hardware primitive, same as on the Treiber Stack's own page: atomically check whether ref still equals expected, and if so set it to next, reporting success or failure as one indivisible step.

// queue starts with one permanent dummy node; head = tail = dummy

function enqueue(value) {
  const node = { value: value, next: null };
  while (true) {
    const tail1 = tail;         // read
    const next1 = tail1.next;   // read
    if (next1 === null) {
      // tail really points at the last node — try to link on
      if (compareAndSwap(tail1, 'next', null, node)) break; // linked; exit retry loop
    } else {
      // tail is lagging behind the real last node — help advance it, then retry
      compareAndSwap('tail', tail1, next1);
    }
  }
  compareAndSwap('tail', tail1, node); // one more, un-retried: swing tail onto the new node
}

function dequeue() {
  while (true) {
    const head1 = head;         // read
    const tail1 = tail;         // read
    const next1 = head1.next;   // read
    if (head1 === tail1) {
      if (next1 === null) return EMPTY;      // genuinely empty
      compareAndSwap('tail', tail1, next1);  // tail lagging — help, then retry
      continue;
    }
    const value = next1.value;
    if (compareAndSwap('head', head1, next1)) return value; // old head1 retired, next1 is the new dummy
  }
}

The demo above runs this exact shape as a step-by-step state machine, with every read, every local computation, and every CAS as its own independently interleavable move. The Naive dequeue variant changes exactly one thing: it collapses the entire if (head1 === tail1) branch straight to return EMPTY, deleting both the next1 === null check and the help-and-retry step — the one-line "simplification" that looks harmless until a visitor steps through the exact schedule in Pitfalls below.

Pitfalls

The correct algorithm never reports a phantom empty queue — exhaustively confirmed, 0 occurrences across every scenario tried, including ones that race an enqueue against a dequeue on purpose. The naive variant does, and the shortest reproducing schedule needs only two threads doing one operation each:

scenariodequeue variantreachable statesphantom-empty statesshortest schedule
T0: enqueue · T1: dequeueCorrect200—
T0: enqueue · T1: dequeueNaive1824 moves
T0: enqueue, enqueue · T1: dequeue, dequeueCorrect950—
T0: enqueue, enqueue · T1: dequeue, dequeueNaive106314 moves
T0: dequeue · T1: dequeue (queue starts empty)Correct90—
T0: dequeue · T1: dequeue (queue starts empty)Naive90—

The minimal reproduction (Minimal scenario, Naive variant, starting from an empty queue): T0 calls enqueue(X) and reads tail1 = the dummy, next1 = null — tail genuinely points at the last (and only) node, so T0's CAS links X on: dummy.next = X. T0 has not yet run its own follow-up tail-swing. T1 now calls dequeue(): reads head1 = the dummy, tail1 = the dummy (unchanged — T0 hasn't swung it), next1 = head1.next = X. head1 === tail1 is true, so the naive variant returns EMPTY immediately — without ever looking at next1, which is X, not null. Four moves total: T0's read, T0's link CAS, T1's read, T1's wrong return. The correct variant, given the identical schedule up to that point, takes the next1 !== null branch instead: helps swing tail onto X, loops back, rereads (now head1 !== tail1), and dequeues X correctly. The Larger scenario (one more enqueue/dequeue round trip on each side) finds the identical shortest schedule length (4 moves) but many more total occurrences — 31 of 106 reachable states, not just 2 of 18 — because more in-flight operations give more chances for some dequeue to land in the gap between a link and its tail-swing.

Two things worth being precise about, because it's tempting to overstate this into "the naive version loses data." First, no value is ever permanently lost or duplicated by the naive variant — confirmed separately by tracking every value ever enqueued against every value either still reachable in the list or already returned by a completed dequeue, at every fully- finished state reachable in either scenario above: 0 mismatches, in both the correct and the naive version. X in the trace above is still sitting right there in the queue after T1's wrong answer, perfectly intact, available to the next dequeue that comes along (if one does). The bug is narrower and in some ways stranger than data loss: one specific call lied about the queue's state at the exact moment it was asked, a correctness violation even though nothing downstream necessarily notices. Second, the Dequeue only scenario above — two threads, both dequeuing, nothing ever enqueued — comes back with 0 phantom-empty states under either variant: with no enqueue in flight, next1 is genuinely always null whenever head1 === tail1, so the naive shortcut happens to give the right answer by accident. The bug needs a real race between a linking enqueue and a reading dequeue to ever surface — concurrent dequeues on a truly empty queue can't trigger it no matter how many are tried.

This queue's two independently-CAS'd pointers face the identical ABA hazard the Treiber Stack's own page demonstrates exhaustively under a recycling node allocator — a stale CAS can't tell a freed-and-reused node identity from the original, regardless of whether there's one shared pointer or two. Nothing about compare-and-swap's identity-based comparison changes between the two structures; that mechanism isn't re-derived separately here. What's new on this page is the lagging- tail hazard above, which has no Treiber Stack analogue at all — a single-pointer structure has nothing that can "lag behind" its own other half, because it doesn't have another half.

Complexity

Time: O(1) for the read-compute-CAS body of either operation, with no bound on how many times that body retries under contention — the same lock-free guarantee as the Treiber Stack: some thread's attempt always eventually succeeds, not necessarily this one's. Space: O(n) for n live elements, plus the one permanent dummy node — a cost no singly-linked queue avoids, lock-free or not. Six of this site's ten other Concurrency entries guarantee bounded waiting for every process (see the Safety vs. Liveness guide); this page, the Treiber Stack, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List all give that up in exchange for never blocking anything, a trade Busy-Waiting vs. Blocking measures the cost of directly.

The extra pointer changes the constant, not the complexity class: every enqueue that finds the tail already current pays one CAS, same as a Treiber Stack push; one that finds it lagging pays a second CAS to help, then retries — a real but bounded amount of extra work per occurrence, not a new growth rate. Measured against a single global spinlock protecting the equivalent plain operations, same two-worker SharedArrayBuffer setup and discipline as the Treiber Stack's own benchmark: at low contention the lock-free queue's two-CAS enqueue path makes it consistently the slower of the two, by a similar margin to the stack's own single-worker result; under real contention (two workers oversubscribing this VM's 2 cores) the direction flips the same way, for the same reason — a spinlock held across a preemption stalls every other thread until the scheduler returns, while nothing here ever holds anything a preemption could strand.