Introduction to Lock/Wait Free Algorithms - Defining and Understanding the Terms
summary
Defines compare-and-swap as the common atomic primitive and gives a concrete claim: lock‑free means for every subset of threads at least one thread can make progress, while wait‑free means every scheduled thread completes in a bounded number of steps (the bound may include the number of threads). Shows why a reader-writer lock is not lock‑free, why wait‑free is costly and complex, and when each guarantee (e.g. self‑driving latency) actually matters.
AI-written summary · about
chapters (8)
- 0:00Lock/wait-free intro
- 1:56Why lock-free matters
- 4:01Sync primitives limits
- 6:33Lock-free defined
- 8:42Wait-free defined
- 13:03Need wait-free?
- 15:31CAS in lock-free code
- 17:37Work transfer in wait-free
related talks
01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)
39mLive Lock-Free or Deadlock (Practical Lock-free Programming)
52mNonblocking algorithms/ CAS/Atomics
01h 12mThe speed of concurrency (is lock-free faster?)
01h 06mLocks are tricky — let's understand them by building one
01h 38mLock-free Programming is Dead - Long Live Lock-free Programming!
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II
01h 00mConcurrency in C++20: A Deep Dive