An Interesting Lock-free Queue - Part 2 of N
summary
Detailed walkthrough of a lock-free, mostly-contiguous circular queue that handles integers and aims to be multi-producer, multi-consumer and growing and shrinking. Shows CAS loops, uses per-slot generation tags and relaxed atomics for head/tail as hints, explains when acquire/release are needed, and enumerates failure modes (empty/full, wraparound, ABA). Includes invariant-based reasoning and planned design to allocate bigger buffers with reference counts. Slides, code and materials are on the CppCon2017 GitHub.
AI-written summary · about
chapters (6)
- 0:00Start
- 2:54Rules of Lock Free Coding
- 7:00False Sharing
- 19:51Why Do You Need a Head and Tail Pointer
- 42:11Updating Generation and Tail
- 57:00Proof by Induction
related talks
01h 00mIntro to Concurrent Programming 1/3: Classic Stack and Queue Algorithms
01h 32mLock-free programming with modern C++
01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II
01h 02mIntro to Concurrent Programming 2/3: Modern Queues and Flat Combining
01h 07mBuilding Robust Inter-Process Queues in C++
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
01h 03mSafety: off --- How not to shoot yourself in the foot with C++ atomics