The Michael-Scott Queue: A Lock-Free FIFO

The Problem: Locks Block, Non-Blocking Doesn't

A lock-based queue is correct but fragile under scheduling. If the thread holding the queue's mutex is preempted, page-faulted, or simply descheduled mid-critical-section, every other thread that wants the queue stalls until that one thread is rescheduled — unbounded, at the whim of the OS scheduler. On an oversubscribed machine (more threads than cores) this convoying can dominate runtime.

A lock-free data structure eliminates that failure mode by construction. Its guarantee: in any finite window of execution, at least one thread completes an operation, regardless of delays, preemption, or crashes of the others. No thread holds exclusive ownership; instead, threads race to apply their change with an atomic compare-and-swap (CAS), which atomically writes a memory word only if it still holds an expected value. A losing thread simply re-reads and retries. The Michael-Scott queue (M&S), from their 1996 PODC paper "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms," is the canonical FIFO built this way, and it is simple enough to be practical — the reason it shipped into real runtimes rather than staying a proof.

Anatomy: A Sentinel and Two Pointers

The queue is a singly linked list of nodes, each holding a value and a next pointer, plus two shared pointers: Head and Tail. The decisive design choice is a dummy sentinel node: the list always contains at least one node, and Head always points at it. The sentinel carries no live value; the first real element is the sentinel's successor.

• Empty queue: Head == Tail, both pointing at the sentinel, and sentinel.next == null. There is no null-pointer special case for the empty state — emptiness is uniform.
• Enqueue appends at the tail end and advances Tail.
• Dequeue reads the value out of the sentinel's successor, makes that successor the new sentinel by advancing Head, and frees the old sentinel.

Why a sentinel? Without it, an empty queue would need Head == Tail == null, and a concurrent enqueue and dequeue on a one-element queue would fight over the same pointer, forcing awkward special cases. The sentinel decouples the two ends: an enqueuer only ever touches Tail and the last node's next; a dequeuer only ever touches Head. They can run genuinely in parallel.

Enqueue: Two CAS Steps and "Helping"

Enqueue is the subtle half, because appending a node and advancing Tail cannot be done in one atomic step. M&S split it into two CAS operations and make the intermediate state safe for everyone to observe:

enqueue(Q, value):
  node = new Node(value, next=null)
  loop:
    tail = Q.Tail
    next = tail.next
    if tail == Q.Tail:            // Tail still consistent?
      if next == null:            // tail is really the last node
        if CAS(&tail.next, null, node):   // STEP 1: link node
          break                   // success -> leave loop
      else:                       // Tail is lagging; HELP it
        CAS(&Q.Tail, tail, next)  // swing Tail forward, then retry
  CAS(&Q.Tail, tail, node)        // STEP 2: swing Tail to node

Step 1 links the new node by CAS-ing the last node's next from null to the new node. Step 2 swings Tail to point at it. Between the two steps the queue is in a legal but "unfinished" state: the node is already in the list, but Tail still points one node back, so Tail.next != null.

This is where helping makes the structure lock-free. Any thread that observes a lagging Tail (its next is non-null) does not wait for the original enqueuer to wake up and finish; it performs the pending Step 2 itself via CAS(&Q.Tail, tail, next), then retries its own operation. So even if the enqueuer is descheduled for a millisecond right after Step 1, the queue keeps making progress — the second CAS is idempotent and can be completed by whoever gets there first. That final CAS(&Q.Tail, tail, node) after the loop may harmlessly fail if a helper already advanced Tail; failure is fine.

Dequeue: Read Before You Swing

dequeue(Q):
  loop:
    head = Q.Head
    tail = Q.Tail
    next = head.next
    if head == Q.Head:            // Head still consistent?
      if head == tail:           // empty, or Tail lagging
        if next == null:
          return EMPTY           // truly empty
        CAS(&Q.Tail, tail, next) // help advance a lagging Tail
      else:
        value = next.value       // read value BEFORE the CAS
        if CAS(&Q.Head, head, next):  // swing Head; next is new sentinel
          break
  free(head)                     // reclaim old sentinel
  return value

Dequeue reads the value out of the sentinel's successor (next.value), then advances Head to that successor with a single CAS. The successor becomes the new sentinel and the old sentinel is freed. Two ordering details are load-bearing. First, the value is read before the CAS on Head: once Head advances, another thread may dequeue that node and free it, so reading afterward would be a use-after-free. Second, the dequeuer also participates in helping: if it finds Head == Tail but next != null, that means an enqueuer finished Step 1 but not Step 2, so the dequeuer advances Tail before retrying — otherwise a stuck-half-way enqueue could make a non-empty queue look permanently empty.

Why It Is Correct and Lock-Free

Linearizability. Every operation appears to take effect atomically at one instant. For enqueue that instant is the successful Step-1 CAS that links the node; for a successful dequeue it is the CAS that swings Head; for an empty-return it is the read of next == null under a consistent Head. Because those points fall in a total order consistent with real time, the queue behaves exactly as a sequential FIFO would — the strongest correctness condition for concurrent objects.

Invariants that always hold: Head is never null; the list from Head is always reachable and acyclic; Tail always points at a node in the list (possibly one short of the true last node, never past it); and the sentinel's successor, when present, is the oldest live element. The consistency check tail == Q.Tail (and head == Q.Head) before acting is what makes the multi-word read look atomic: if the snapshot changed under the thread's feet, it discards the attempt.

Progress. The structure is lock-free but not wait-free. A CAS only fails when some other thread's CAS succeeded — meaning the system as a whole advanced. So the collection never stalls. But a single unlucky thread can be starved: it may lose the CAS race arbitrarily many times while others keep winning, so there is no per-thread bound on retries. Wait-free queues exist (Kogan & Petrank, 2011) but pay for the stronger guarantee with helping descriptors and more overhead; M&S deliberately chose the cheaper lock-free tier.

The ABA Problem and Memory Reclamation

The one classic hazard is the ABA problem. A dequeuer snapshots Head = A, gets preempted; meanwhile A is dequeued and freed, then the allocator hands the same address back for a brand-new node that is enqueued and happens to sit at Head again. The stalled thread wakes, sees Head still equals the pointer A, and its CAS succeeds by accident — corrupting the list, because the meaning of that address changed. CAS compares bits, not identity.

M&S's original fix is tagged (versioned) pointers: each Head/Tail is a pointer plus a monotonically increasing counter, updated together by a double-width CAS (on x86, CMPXCHG16B for 128-bit, historically CMPXCHG8B). Because the counter advances on every modification, an ABA'd pointer carries a stale tag and the CAS correctly fails. The other production-grade fix is hazard pointers (Michael, 2004): a thread publishes the address it is about to dereference, and no node may be freed while any hazard pointer references it — solving both ABA and safe memory reclamation in non-garbage-collected languages. Managed runtimes get this for free: Java's ConcurrentLinkedQueue needs no tags because the garbage collector guarantees a node is never freed while any thread still holds a reference, so an address can never be recycled underneath a live CAS.

Real Systems, Performance, and Descendants

The MS queue is one of the most widely deployed concurrent algorithms in existence. Doug Lea's java.util.concurrent.ConcurrentLinkedQueue is a direct descendant, with one shrewd optimization: it lets Tail lag by up to one node on purpose, advancing it only every other enqueue, which roughly halves the CAS traffic on the Tail hotspot at the cost of a slightly longer helping walk. C++ programmers reach for boost::lockfree::queue, which implements the MS algorithm with tagged pointers; the .NET ConcurrentQueue and many game engines and trading systems use the same lineage.

How it is measured. The 1996 paper benchmarked on a 12-processor SGI Challenge and showed the non-blocking queue matching the two-lock queue when threads ≤ processors, and dramatically beating all lock-based variants once the system was multiprogrammed — exactly the preemption scenario locks handle worst. Uncontended, each operation is a couple of CAS instructions (tens of cycles); the real cost under load is cache-line ping-pong, because every enqueuer contends on the single Tail line and every dequeuer on the single Head line.

That single-hotspot design is also the MS queue's ceiling. High-throughput descendants attack the contention differently: the LCRQ (Morrison & Afek, 2013) links array segments so most operations are a local fetch-and-add rather than a contended CAS; bounded ring buffers (Vyukov-style MPMC queues, LMAX Disruptor) trade unbounded capacity for cache-friendly array layout; and elimination or flat-combining layers absorb bursts. Yet for an unbounded, general-purpose, node-based FIFO, the Michael-Scott queue remains the reference design and the one every concurrency course teaches first.

The lock-free MS queue against blocking queues and its lock-free stack cousin

Queue design	Synchronization	Progress under preemption	Concurrent enq + deq	Needs ABA-safe reclamation
Single-lock queue	One mutex around both ends	Blocks (preempted holder stalls all)	No	No
Two-lock queue (M&S 1996)	Separate head lock + tail lock	Blocks (per-end)	Yes (one enqueuer + one dequeuer)	No
Michael-Scott lock-free queue	CAS on Head, Tail, and next	Lock-free: system always progresses	Yes (many threads)	Yes (tags / hazard pointers / GC)
Treiber stack (LIFO cousin)	CAS on a single top pointer	Lock-free	N/A (LIFO, one hotspot)	Yes