the Michael-Scott lock-free queue
/ MY-kuhl SKOT /
A stack only ever touches one end, which is why the Treiber stack needs just one atomic pointer. A queue is harder: it is first-in-first-out, so you add at one end (the tail) and remove at the other (the head), and now two pointers must be kept consistent at the same time under concurrent access. The Michael-Scott queue, published by Maged Michael and Michael Scott in 1996, is the classic, widely used lock-free solution to this, and it underlies many production concurrent queues (including Java's ConcurrentLinkedQueue).
Its two ideas are worth understanding. First, a sentinel (dummy) node always sits at the head, so the queue is never truly empty in pointer terms and enqueue and dequeue never have to special-case an empty queue against each other. Second, and cleverly, an enqueue takes two steps that cannot be made atomic together — link the new node onto the last node, then swing tail to point at it — and the algorithm survives a thread pausing between them by having every other thread HELP: if any thread notices that tail has fallen behind (its next pointer is not null), it first advances tail with a CAS before doing its own work. So a half-finished enqueue is always completed by whoever arrives next, and the structure is never left in a broken state.
This helping is exactly the cooperative-completion technique, and it is what makes the queue lock-free rather than merely obstruction-free: no thread's pause can wedge the queue, because the next thread tidies up. The same caveats as the Treiber stack apply, though — the dequeue path reads node fields that another thread might free, so a correct implementation pairs the MS queue with hazard pointers or epoch-based reclamation. It is a beautiful, much-studied algorithm, and also a standing reminder of how much care a correct lock-free queue actually demands.
/* Enqueue: link then swing tail; any thread will help finish a lagging tail. */ for (;;) { Node *t = tail, *next = t->next; if (next == NULL) { if (CAS(&t->next, NULL, n)) { CAS(&tail, t, n); return; } /* done */ } else { CAS(&tail, t, next); /* help: tail lagged behind, push it forward */ } }
The else branch is the helping step: whoever finds tail lagging advances it, so a stalled enqueuer can never wedge the queue.
The sentinel node and the help-the-lagging-tail step are what make it lock-free; without safe reclamation (hazard pointers or epochs) the dequeue path is still a use-after-free.