How threads help each other
summary
Explains the 1996 Michael‑Scott queue implementation used in C++ and Java, the actual node layout and the two-pointer update (head and tail) sequence, and why it works: threads use compare-and-swap (CAS) on atomic references and threads help each other by fixing a partially-updated tail so the queue recovers instead of deadlocking. Demonstrates lock‑free progress (not wait‑free), the retry storm when many producers contend, and that the helper trick keeps correctness while avoiding global locks.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 3:29Non-blocking synchronization
- 10:55Memory models and shared memory
- 21:51Lock problems and critical sections
- 26:28Atomic operations and CAS
- 34:22Lock-free stack
- 39:19Michael-Scott queue
- 47:35Locks vs lock-free
- 50:00Queue modifications and use
- 52:45Performance and recommendations
related talks
01h 00mIntro to Concurrent Programming 1/3: Classic Stack and Queue Algorithms
51mFrom Linux Threads To ForkJoinPool
01h 04mBack to Basics: Concurrency
01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)
47m“Multithreading is the answer. What is the question? (part 1 of 2)”
01h 08mThinking Outside the Synchronisation Quadrant
01h 08mBetter Code: Concurrency
01h 05mAn Interesting Lock-free Queue - Part 2 of N