The idea: a queue with no lock
A queue shared by many threads is usually a linked list behind a mutex. While one thread holds the lock, every other thread waits, and if the holder is descheduled they all wait longer. The Michael–Scott queue (1996) needs no lock at all. Every change is one compare-and-swap (CAS) on one pointer, and a thread that stops halfway never stops anyone else.
The list always starts with a dummy node. Head points at the dummy, and the first value is in Head->next. Tail points at the last node, or at the node just before it while an enqueue is half done. Because of the dummy, an empty queue is still one node, so enqueuers (who work at Tail) and dequeuers (who work at Head) never touch the same pointer.
Enqueue: link, then swing the tail
E1 node = alloc(); node->value = v; node->next = NULL
E2 t = Tail
E3 next = t->next; if (t != Tail) goto E2
E4 if (next != NULL) { CAS(&Tail, t, next); goto E2 }
E5 if (!CAS(&t->next, NULL, node)) goto E2
E6 CAS(&Tail, t, node)
The new node is private until E5. That CAS sets t->next only if it is still NULL, so of two threads that read the same tail, exactly one wins. The loser sees a failed CAS and starts again from E2 (Demo: two enqueues race for tail->next). E5 is the moment the value is in the queue: the linearization point. E6 then moves Tail forward. It may fail, and that is fine.
Helping: why a stalled thread blocks nobody
Suppose T1 has done E5 and is then preempted before E6. Tail points at the second-to-last node. With a lock, T2 would have to wait for T1. Here T2 reads Tail, sees that Tail->next is not NULL, and does T1's E6 for it (line E4), then carries on with its own enqueue. When T1 wakes up, its E6 CAS fails because Tail has already moved (Demo: T1 stalls, T2 helps swing Tail).
A dequeuer helps too. If Head == Tail but the dummy has a successor, a node is linked and Tail lags. The dequeuer swings Tail first (line D5), so that Head never moves past Tail (Demo: dequeue helps a lagging tail). This is what makes the queue lock-free: at every moment some thread can finish its operation, whatever the others are doing.
Dequeue: move Head, the old dummy goes away
D1 h = Head
D2 t = Tail
D3 next = h->next; if (h != Head) goto D1
D4 if (next == NULL) return EMPTY
D5 if (h == t) { CAS(&Tail, t, next); goto D1 }
D6 v = next->value
D7 if (!CAS(&Head, h, next)) goto D1
D8 free(h); return v
The value lives in next, not in the dummy. One CAS moves Head from the dummy to next, and next becomes the new dummy. The old dummy is out of the list and can be freed. v is read at D6, before the CAS, because after the CAS another thread may dequeue and free next at once. The checks t != Tail and h != Head throw away a pair of reads that did not happen at the same moment.
The ABA problem
CAS checks that a word still holds the same value. It cannot see that the word changed and changed back. With pointers that is dangerous: if a node is freed and alloc() hands the same address out again, a stale pointer looks valid.
On the canvas the free list is LIFO, like many real allocators, so a freed address is the next one handed out. T1 stalls before D7 with h = @1, next = @2, v = 10. T2 dequeues and enqueues twice, and the addresses come back in the same places: Head is @1 again and @1->next is @2. T1's CAS succeeds. It returns 10, which T2 already returned, and makes @2, which holds 30, the new dummy. 30 is gone (Demo: ABA, free at once (bug)).
Three ways out: tags, hazard pointers, GC
| How it stops ABA | Cost | |
|---|---|---|
| Tagged pointers | Each pointer word carries a counter, and every successful CAS adds 1. CAS compares pointer and tag, so @1 ·0 no longer matches @1 ·2. This is the original paper's fix. | needs a double-width CAS (cmpxchg16b) or spare pointer bits; freed nodes must stay readable memory (a type-stable free list) |
| Hazard pointers | Before using a node, a thread publishes its address in a hazard pointer. retire(h) frees a node only when no hazard pointer names it, so an address in use is never reused. | a store and re-check per pointer read; a scan of all hazard pointers per batch of retires |
| Garbage collector | The code never frees. The GC reclaims a node only when nothing refers to it, and T1's local h is a reference. | needs a GC; this is why Java's ConcurrentLinkedQueue needs no tags |
Run the same script with each fix. With tags, T1's CAS fails (tag 0 vs 2) and it retries and dequeues 30. With hazard pointers, @1 and @2 stay retired (yellow) while T1's hp0 and hp1 name them, so 20 and 30 go into new slots, T1's CAS fails, and the retired nodes are freed at a later scan. With a GC the outcome is the same, and no code frees anything. In every case each value comes out exactly once. Read-copy-update solves the same "when is it safe to free?" question with grace periods.
Lock-free, not wait-free
A failed CAS means another thread's CAS succeeded, so the system as a whole always makes progress. One unlucky thread can still lose the race again and again, so the queue is lock-free but not wait-free. In practice the retry loop is short. The algorithm is behind Java's java.util.concurrent.ConcurrentLinkedQueue, and the same CAS-on-a-bin idea appears in ConcurrentHashMap. Compare a plain, single-threaded linked-list queue, and a lock-based bounded buffer where producers and consumers sleep instead of retrying.
What the page leaves out
Each line runs as one atomic step, so memory ordering (acquire/release fences, and why node->value must be visible before E5) is not shown. In the paper every pointer is tagged; here the tags are shown only in tagged mode. Hazard pointers really need a store, a fence and a re-read of Head to validate; the page does that in one step. Real hazard-pointer code scans only when the retired list is long, epoch-based reclamation is not shown, and the queue has no size bound. The 6-slot memory is tiny on purpose, so a freed address comes back quickly.
See where this page fits on the Concurrency mind map.