Intro to Concurrent Programming 1/3: Classic Stack and Queue Algorithms
summary
Covers lock-free implementations of a linked-list stack and the Michael-Scott queue, using CAS-based push/pop loops, the universal-copy-on-write construction for conceptual lock-freedom, and a dummy head node with separate head/tail pointers for the queue. Shows how failing CAS implies system-wide progress, explains helping (one thread advancing tail for another), and notes practical tradeoffs such as lack of wait-freedom and the common optimization of volatile reads versus extra CAS.
AI-written summary · about
chapters (8)
- 0:00Concurrent programming intro
- 4:21Locks and coarse sync
- 10:00Lock-free counter with CAS
- 19:03Lock-free stack algorithm
- 28:54Correctness in concurrent data structures
- 37:35Top operation and wait-free
- 40:30Michael-Scott queue overview
- 57:35Summary and assignments
related talks
01h 05mAn Interesting Lock-free Queue - Part 2 of N
54mHow threads help each other
01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)
01h 08mBetter Code: Concurrency
01h 07mBuilding Robust Inter-Process Queues in C++
01h 04mBack to Basics: Concurrency
01h 35mThinking Outside the Synchronisation Quadrant
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II