Lock-Free Queue: The Michael-Scott Algorithm
What you'll learn: How the classic Michael-Scott algorithm implements a lock-free queue using two pointers and CAS operations for concurrent enqueue and dequeue.
The Core Challenge
Unlike a lock-free stack (which has a single top pointer), a queue needs both a head (dequeue end) and a tail (enqueue end). The Michael-Scott algorithm, published in 1996, became the standard solution for lock-free queues by carefully coordinating these two pointers using compare-and-swap (CAS) operations.
How It Works
The algorithm maintains separate head and tail pointers to linked nodes. Here's the key insight:
Enqueue tries to CAS a new node onto tail->next, then swings the tail pointer forward. If another thread beats you to updating tail, that's fine—you help move it along.
Dequeue advances the head pointer forward, effectively "removing" the front node. The tricky part: head always points to a dummy node, so the actual data is in head->next.
Why the Dummy Node?
This prevents a race where enqueue and dequeue try to modify the same pointer simultaneously. The dummy creates separation—enqueue works at tail, dequeue at head, and they only "collide" when the queue has 0-1 elements.
Handling the Tail Lag
The tail pointer may lag behind the actual last node temporarily. Threads detect this (tail->next != null) and help update tail before inserting. This cooperation prevents indefinite blocking even when threads are delayed.
Key Takeaway: The Michael-Scott algorithm achieves lock-free queue operations by using separate head and tail CAS operations, a dummy node for separation, and cooperative tail-pointer updates to handle concurrent enqueues and dequeues without blocking.