Expert · Module 25 · Lesson 3 of 5
A lock-free stack
The Treiber stack links a node's next field and then CASes the head, for both push and pop. This lesson verifies every pointer through both operations, shows why the classic pop turns unsafe once a node can be freed, and states the progress guarantees exactly.
By the end you can
- Trace a push and a pop on a Treiber stack and check every pointer after each CAS
- Explain why the classic pop stops being safe once a node can be freed or reused
- Tell lock-free, obstruction-free and wait-free apart, and say when lock-free matters
Builds on Nodes and pointers, Stacks and the LIFO rule, Data races and locks.
01 · A question first
A stack has one pointer to change, so it looks like the easiest structure to make lock-free: one CAS to push, one to pop. The catch is in the pop, which reads through a pointer to a node another thread may have already removed. What exactly goes wrong at that moment?
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
- One pointer, and it is always the top
- Push: link first, swing second
- Pop: read two values, swap once
- The step that stops being safe
- Progress guarantees, stated exactly
- Why lock-free matters when threads stall
- What pushing a node requires
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem