8 Wait-free synchronization
This chapter motivates wait-free synchronization as a practical path to predictable low latency when multiple threads must share data. It begins by noting that eliminating redundant work and exploiting CPU parallelism are not always sufficient; shared state still demands coordination. The focus is to understand traditional mutual exclusion, the atomic and memory-ordering foundations beneath all concurrency, and how to assemble these into wait-free data structures suitable for latency-sensitive, low-level components such as queues and request pipelines.
The text reviews mutual exclusion mechanisms—mutexes, read-write locks, and spinlocks—explaining critical sections and why contention, OS blocking, and spinning can inflate latency. It highlights core pathologies of lock-based designs: inefficiency under contention, priority inversion, convoying, and deadlocks, illustrated by simple counters and ABBA-style lock ordering pitfalls. From there, it introduces atomics as the hardware primitives underpinning synchronization (loads/stores, fetch-and-modify, and compare-and-exchange) and shows how even a spinlock can be built from them. Because modern CPUs and compilers reorder memory operations, the chapter details memory barriers/fences and their higher-level acquire/release/SeqCst/relaxed semantics, along with compiler fences, and demonstrates how pairing release on writes with acquire on corresponding reads preserves invariants without resorting to locks.
Wait-free synchronization is then defined and contrasted with lock-free and other progress conditions, emphasizing its benefits for low latency: bounded progress for every thread, scalability, deadlock immunity, and resilience to priority inversions. The chapter clarifies the hierarchy of progress guarantees (blocking, starvation-free, obstruction-free, lock-free, and the various wait-free forms) and warns that blocking memory allocation can undermine these guarantees. It introduces the notion of consensus numbers, noting that primitives like compare-and-swap are universal, and surveys wait-free queues, stacks, and linked lists, including the challenges of safe memory reclamation (reference counting, hazard pointers, epoch schemes, or GC). A practical single-producer, single-consumer bounded queue is constructed using atomic indices and acquire/release ordering to guarantee correctness without locks, demonstrating a dramatic drop in operation latency compared to a mutex-based design and illustrating how careful use of atomics and memory barriers yields predictable, low-latency concurrency.
Categories of memory barriers. Memory barriers are needed between two instructions that perform a load (read) or a store (write) to memory. In many programming languages today, memory barriers are abstracted as acquire and release barriers. Acquire barriers contain both load/load and load/store memory barriers release barriers contain both load/store and store/store memory barriers.
Example usage of acquire/release memory barriers to ensure ordering between writes to two variables, data and flag, where it’s critical that the write to data is visible when the write to flag becomes visible. In this example specifically, the flag indicates that some operation is done, where the result of the operation is store in data. If we allow the write to flag to be visible before the write to flag, the process can read invalid or stale data from data.
The relationship between different wait-free and lock-free progress conditions.
Summary
- Wait-free synchronization is an alternative to traditional mutual exclusion for reducing latency in concurrent systems.
- Mutual exclusion is traditionally implemented using mutexes, spinlocks, and read-write locks, but they have various problems for low latency apps, including inefficiency, priority inversion, convoying, and deadlocks.
- Atomic operations and memory barriers are important in implementing wait-free concurrent data structures.
- Wait-free has various progress conditions in concurrent programming, including blocking, starvation-free, obstruction-free, lock-free, and wait-free.
- Wait-free data structures are presented as a solution for predictable low latency, multicore scalability, and fault tolerance in concurrent systems.
- A practical example of building a wait-free single-producer, single-consumer (SPSC) queue is provided, demonstrating the use of atomics and memory barriers.
- Wait-free can have significant performance improvements over traditional mutex-based implementation.
Latency ebook for free
