Expert · Module 25 · Lesson 4 of 5

Lock-free queues and the ABA problem

A queue has two live ends, so it needs a dummy node, two CASes per operation and a rule for finishing work another thread left half-done. Then the ABA problem: a CAS that compares values can succeed on a node that left and came back.

ProAbout 15 minutes

By the end you can

Explain why an enqueue needs two CASes and how helping keeps the tail consistent
Trace an ABA interleaving and name the step where the CAS succeeds for the wrong reason
Compare versioned pointers, reclamation schemes and garbage collection as ABA fixes

Builds on A lock-free stack, Queues and ring buffers, Nodes and pointers.

01 · A question first

The stack needed one CAS because one pointer was the whole structure. A queue has two ends, updated by different threads, and between a thread's read and its swap the value it plans to match may go away and come back, bit for bit. What is a CAS actually comparing?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Two ends, and both move
The Michael-Scott queue
The helping argument
What a CAS compares
The five steps that corrupt the stack
Fixes: versioned pointers and reclamation
What garbage collection fixes
Pseudocode & Multi-Language Implementations (C++, Java, Python)

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeDesign circular queueImplement a fixed-size queue on a ring buffer, with every operation in O(1) and correct full and empty checks.Practice · easy · LeetCodeImplement queue using stacksBuild a FIFO queue from two LIFO stacks, and show that each operation is O(1) amortized.

Asked in interviews

Explain the Michael-Scott lock-free queue and the ABA problem: how can a CAS succeed when the pointer address matches yet corrupt the queue?

Something wrong with this lesson? Report a problem