The reference lock free queue
The Michael Scott queue is the standard non blocking FIFO queue. It uses a singly linked list with a sentinel node, a head pointer for dequeue, and a tail pointer for enqueue. Every mutation is driven by compare and swap rather than locks.
A two step enqueue
Enqueue is subtle because linking a node and moving the tail cannot be one atomic step:
- Read the tail and its next field
- If next is null, compare and swap the new node into that next slot
- Then attempt a second compare and swap to advance tail to the new node
The second step may be left undone if the thread stalls right after linking, so the tail can temporarily lag behind the true last node.
Cooperative helping
Other threads handle the lagging tail with helping. When any thread observes that tail's next is not null, it knows tail is behind and advances it on the original thread's behalf before doing its own work. This cooperation guarantees the structure stays consistent even if a thread pauses mid enqueue, giving the queue its lock free progress property.
Key idea
The Michael Scott queue links nodes and advances the tail in two compare and swap steps, with threads helping a lagging tail to preserve lock free consistency.