Expert · Module 25 · Lesson 5 of 5
Memory reclamation
A lock-free structure can outlive the thread that is reading it: another thread removes a node while the reader is descheduled, and freeing it then is a use-after-free. Hazard pointers, epochs, RCU and garbage collection each answer when a free is safe.
By the end you can
- Explain why a lock-free structure cannot free a node the moment it unlinks it
- Trace a retire under hazard pointers and say when the node is actually freed
- Compare hazard pointers, epoch-based reclamation, RCU and garbage collection by cost
Builds on A lock-free stack, Lock-free queues and the ABA problem.
01 · A question first
A thread reads a pointer into a lock-free list, then the operating system takes its core away for a few minutes. Meanwhile another thread removes that node and would normally free it. When the first thread wakes and follows the pointer, that memory belongs to something else. Who is allowed to call free?
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
- The reader that outlives the node
- Remove first, free later
- Hazard pointers
- Epoch-based reclamation
- RCU in the kernel
- Garbage collection as the language-level answer
- Choosing a scheme
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Something wrong with this lesson? Report a problem