Lock-Free Structures — Queues, Stacks & ABA
Lock-free structures use CAS so some thread always makes progress. The teaching cases are the Treiber stack, the Michael-Scott queue, and an SPSC ring. ABA and reclamation are the part people skip.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What does a Treiber push CAS?
Answer
It sets the new node's next to the observed head, then CASes the head from that observed value to the new node.
L2
Why is that lock-free and not wait-free?
Answer
A failed CAS means another push or pop succeeded, so the system progresses. One thread can lose every attempt.
L3
What is ABA?
Answer
The bits you CAS on change from A to B and back to A. The compare succeeds. The structure those bits now name is not the one you observed.
L4
Name three mitigations.
Answer
A tagged pointer or version, hazard pointers, and epoch or RCU-style deferred free. A garbage collector removes explicit free and does not remove every logical ABA on indexes.
L5
Why is an SPSC ring easier?
Answer
One producer owns the write index and one consumer owns the read index. A release store and an acquire load are enough. No CAS, if it really is one and one.
L6
What does a Michael-Scott queue add?
Answer
A sentinel, a CAS on the tail's next pointer, a swing of the tail, and helping so a stalled enqueuer does not block the system. Reclamation is still required.
L7
When do you refuse to hand-roll this?
Answer
Almost always in application code. Use ConcurrentLinkedQueue, Crossbeam, Folly, or a mutex. Hand-roll only when you can name the paper and the reclamation scheme.
Failure modes
Freelist ABA
A pop observes head A and next B, pauses, and later CASes A to B after A was reused and B was freed.
Fake MPMC
Several producers CAS a shared write index on a ring that was proved for one producer. Slots tear or are skipped.
Free immediately after pop
Another thread still holds the raw pointer. The next allocate reuses it. Hazard pointers and epochs exist for this gap.
Lock-free claim with a locked allocator
The structure CAS is lock-free and the node allocator takes a global mutex. A stall in allocate blocks everyone.
Misconceptions
Java ConcurrentLinkedQueue has the C++ freelist ABA bug.
The garbage collector will not recycle an object's identity while it is reachable. C++ freelists do. Index-based structures can still have a logical ABA.
A lock-free queue is wait-free.
CAS loops can starve one thread. Wait-free queues exist and are a different, heavier design.
Hazard pointers and epochs are the same.
A hazard pointer publishes 'I am using this address.' An epoch defers all frees until every thread has passed a quiescent point. Batching and latency differ.
Interviewer traps
Writing a full Michael-Scott proof when the question was ABA.
Tell the pop, reuse, CAS story. Then name the tag, the hazard pointer, or the epoch.
Answering with a distributed lock or a lease.
This is process-local memory. Reclamation is not a fencing token.
Design scenario
Same prompt for every reader.
Requirements
The pipeline must not drop or duplicate slots. The freelist must not hand out a buffer a thread still reads. A stalled worker must not block the pipeline forever if you claim the pipeline is lock-free.
Traffic / scale
The pipeline is steady and one-to-one. The freelist is bursty and shared by all workers.
Latency
The pipeline should be a couple of index releases, not a CAS on a hot head. Freelist pops must stay correct if a worker pauses for a scheduler quantum.
Consistency
A popped buffer is not reused until every reader has dropped it. A ring slot is not written until the consumer has released it.
Availability
A dead consumer fills the ring and the producer observes full. That is backpressure, not corruption. A dead worker must not pin a mutex inside the pipeline.
Failure assumptions
- Buffer addresses are recycled.
- A thread can pause between load and CAS.
- The pipeline might later grow a second producer.
Constraints
- Do not use the SPSC ring once there are two producers.
- Do not free a node on pop without a reclamation scheme.
Prompt
A service has a pipeline stage with one producer and one consumer, and a separate freelist of buffers shared by many worker threads. Someone proposes one lock-free MPMC queue for both.
API
Which path is push/pop with a tag, and which path is a ring index?
Data
What is packed into the head word, and what does the consumer store with release?
Architecture
What library do you take if a second producer appears, instead of editing the ring?
Queue you should actually ship
Prefer
SPSC ring, or a library, or a mutex
One producer and one consumer get a ring and two indexes. Everyone else gets ConcurrentLinkedQueue, Crossbeam, Folly, or a mutex around a deque.
- The ring's proof is release and acquire, not a novel CAS.
- A library already paid for helping and reclamation.
- A mutex is allowed to be the right answer.
Alternative
A whiteboard MPMC with a freelist
Head and tail CAS, immediate free on pop, and a comment that says lock-free. The first reuse corrupts the structure.
- ABA needs an era, not another test on x86.
- A stalled thread must not be holding a lock you denied having.
- Two producers on an SPSC ring are not a small patch.
From a stack sketch to something you can free
The CAS is the small part. The era and the free are the algorithm.
- 1
CAS the head, and retry when it moved
Push links the new node to the observed head. Pop swings the head to next. Failure means another operation won. - 2
Assume the address comes back
A freelist will pop A, pop B, and push A again. Your paused CAS still names A. - 3
Put an era in the word
A tag, a hazard pointer the reader publishes, or an epoch that defers the free. Pick one you can implement. - 4
Prefer a topology that needs none of that
SPSC uses indexes and release/acquire. If you might add a producer, do not start with that ring.
Overview
Lock-free here means some thread completes an operation in finite steps even if another thread stalls in the middle of its own operation. Nobody holds a mutual-exclusion lock across the update. The usual teaching structures are the Treiber stack, the Michael-Scott queue, and a single-producer single-consumer ring. The hard parts are ABA, how you free memory, and knowing when a sharded mutex would have been shorter and faster. That last decision is the next page.
Treiber stack
Each node holds a value and a next pointer. The head is an atomic pointer.
Push. Allocate the node. Loop: load the head, store it into the new node's next, CAS the head from that loaded value to the new node. On failure, the head moved. Load again.
Pop. Loop: load the head. If it is null, the stack is empty. Otherwise CAS the head from that node to its next, and return the value.
A failed CAS means another push or pop succeeded. That is the lock-free argument. It is not wait-free: one thread can starve. The empty check must use the same load you CAS on. A separate emptiness flag is a second word and a second bug.
ABA
- Thread P loads head = A, and A.next is B.
- P is preempted.
- Other threads pop A, pop B, and push A again because the allocator reused the node. The head word is A again. A.next might now be C, and B might be free.
- P wakes and CASes the head from A to B. The bits of A match. The CAS succeeds. The stack now points at recycled memory.
ABA means the same bit pattern in a different era. Pointer equality is not identity once you free.
Flow
- 1
P loads head A
- nextP is preempted
- 2
P is preempted
- nextOthers pop A and reuse it
- 3
Others pop A and reuse it
- nextP CAS still sees bits of A
- 4
P CAS still sees bits of A
- nextTag, hazard pointer, or epoch
- 5
Tag, hazard pointer, or epoch
Lesson map
Lock-Free Structures — Queues, Stacks & ABA
Lock-free structures use CAS so some thread always makes progress. The teaching cases are the Treiber stack, the Michael-Scott queue, and an SPSC ring. ABA and reclamation are the part people skip.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["P loads head A"] b["P is preempted"] c["Others pop A and reuse it"] d["P CAS still sees bits of A"] a -->|P loads head A to P is preempted| b b -->|P is preempted to Others pop A and reuse it| c c -->|Others pop A and reuse it| d
Mitigations
| Technique | Idea | Cost |
|---|---|---|
| Tagged pointer | CAS a pointer plus a version that increments on every swing | Needs a wide CAS or spare bits in the pointer |
| Hazard pointer | A reader publishes the address it is using so reclaimers skip it | Bookkeeping on the read path |
| Epoch / RCU-style | Defer the free until every thread has passed a quiescent point | Batch latency. A stuck thread holds the epoch |
| Garbage collector | No explicit free of a reachable object | Pauses. Indexes and slots can still repeat |
| Never reuse | Bump an arena and do not recycle addresses | Memory grows without a bound |
Hazard pointers protect specific addresses a thread has declared. Epochs batch frees and are often faster, and a thread that never checks in pins the garbage. A JVM or Go garbage collector removes the C++ use-after-free version of ABA. It does not stop a logical ABA on a slot index you recycle yourself.
SPSC ring
One producer, one consumer, a fixed buffer, a write index, and a read index.
- The producer writes the slot, then release-stores the write index.
- The consumer acquire-loads the write index, reads the slots that are now published, then release-stores the read index so the producer can reuse them.
- Capacity is a power of two so masking is a bit operation.
- If it is truly one producer and one consumer, you do not need a CAS. Each index has a single writer.
The moment a second producer appears, this proof is gone. Do not "upgrade" it with a casual CAS on the write index. Take a real MPMC algorithm or a mutex.
Flow
- 1
Producer writes the slot
- nextRelease-store the write index
- 2
Release-store the write index
- nextConsumer acquire-loads the index
- 3
Consumer acquire-loads the index
- nextConsumer reads the slot
- 4
Consumer reads the slot
Michael-Scott, at sketch depth
An MPMC queue keeps a sentinel node. Enqueue CASes the tail node's next pointer from null to the new node, then swings the tail forward. A thread that finds the swing unfinished helps finish it, which is what keeps a stalled enqueuer from blocking the others. Dequeue CASes the head forward. The paper is the proof. Production code should be ConcurrentLinkedQueue, Crossbeam, Folly, or Boost.Lockfree, not a transcription from memory. Reclamation is still your problem in C++.
Sandbox
The ring below is single-threaded so the index rule is visible: you cannot push into a full ring, and pop returns items in order. The TypeScript snippet shows a version tag rejecting a recycled index that a naive compare would accept.
ExpectedTwo pushes then two pops return a then b, and the third pop is empty.
Press Run. Snippets must be self-contained — no network, files, or native modules.
ExpectedThe index matches and the packed word does not, so the tagged CAS fails.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Lock-free MPMC versus a mutex deque
| Lock-free MPMC | Mutex and a deque | |
|---|---|---|
| A thread dies mid-operation | Others can still finish, if you really hold no lock | Waiters block until the holder returns or the process restarts |
| Reclamation | Your problem in C++ | The lock covers the nodes |
| Fairness | Usually barging | A fair mutex is available |
| Review | Easy to get subtly wrong | Boring, which is the point |
| Hot line | CAS traffic | Park, which is often cheaper |
Interview Q&A
Does Java's ConcurrentLinkedQueue suffer freelist ABA?
Answer
Not in the C++ sense. The collector does not reuse an object identity while a thread can still load it. The algorithm still depends on careful orders. A C++ freelist that recycles addresses is where the classic ABA bug lives. A recycled slot index can still ABA even in a garbage-collected language.
Is a lock-free stack wait-free?
Answer
Usually no. The CAS can fail for an arbitrary number of attempts while other threads succeed. Wait-free stacks and queues exist and are specialized. Do not claim the Treiber loop is one of them.
Why prefer SPSC when the topology allows it?
Answer
One writer per index, a release store after the payload, an acquire load before the read. No CAS, a short proof, and good cache behavior for a pipeline stage. The proof dies as soon as a second producer writes the same index.
Hazard pointer versus epoch?
Answer
A hazard pointer is a published address the reclaimer must not free. An epoch defers every free until all threads have reached a quiescent state. Epochs batch well. A thread that never quiesces pins memory. Hazard pointers bound that differently and cost more on the read side.
Why help in the Michael-Scott enqueue?
Answer
If the thread that CASed the next pointer stalls before swinging the tail, other threads must be able to swing it. Otherwise the stalled thread has blocked the queue without holding a lock you can see. Helping is the lock-free part, not a courtesy.
Can the allocator break the lock-free claim?
Answer
Yes. If allocating a node takes a global lock, a stalled allocator stalls every push. The stack CAS being lock-free does not make the operation lock-free. Account for the allocator or use a structure that preallocates.
What memory order is on the head?
Answer
The CAS that publishes a node is typically a release on success so the node's fields are visible. The load that will dereference next is an acquire. Relaxed is wrong on that pointer. The order menu is the memory ordering page. The bug if you skip it is a popped node whose value is stale.
When is the right answer a mutex?
Answer
When you need several fields to change together, when you need fairness, when the contention is high, or when nobody on the team can review reclamation. The next page is that decision. Shipping a named library is also a fine answer.
Pitfalls
- Freeing a node as soon as the pop CAS succeeds, while another thread may have loaded it.
- Using an SPSC ring for a thread pool.
- Treating a version counter that can wrap onto the same tag as infinite protection. Wide tags matter.
- Calling a locked
std::dequeembarrassing when it meets the latency budget. - Drawing a distributed lease as the ABA fix. Different cluster.
Draw a two-node stack, pause a pop that has loaded head A, and reuse A before the CAS. Say what pointer the CAS installs. Then add a 16-bit tag and show the compare failing. If you freed B in the middle, say who was still allowed to read it.
Go Deeper
- Treiber's stack (1986) is the usual citation. Michael and Scott's 1996 queue paper is the public PDF: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.
- ConcurrentLinkedQueue and Crossbeam for the versions you should call instead of retyping.
- Maged Michael's hazard pointers, and epoch or RCU chapters in Paul McKenney's Is Parallel Programming Hard, And, If So, What Can You Do About It? The book is public. Read the reclamation chapter before you invent a scheme.
- The acquire and release pair those pointers need is Preshing's acquire and release note.
Next: When locks win.