Wait-free synchronization guarantees that every participating thread or process completes its operation within a finite number of steps, regardless of concurrent interference. Unlike lock-free synchronization, which guarantees progress for only some thread, wait-free synchronization guarantees progress for each operation. section 8.5
Use it when shared data must be accessed concurrently and mutexes or spinlocks impose unacceptable latency. It fits low-level components such as request processing and job queues, where isolating complexity can protect latency-sensitive application paths. section 8.0
Wait-free designs trade implementation complexity for several operational properties:
- Predictable low latency by avoiding blocking and waiting. section 8.5
- Multicore scalability by avoiding lock-contention bottlenecks. section 8.5
- Immunity to deadlocks and reduced exposure to priority inversion. section 8.5
- Resistance to one thread’s failure or suspension preventing other threads from progressing. section 8.5
Implementation relies on atomic operations and memory barriers, while primitive choice depends on the number of processes requiring consensus. Atomic registers support one process; test-and-set, fetch-and-add, queues, and stacks support two; compare-and-swap and queues with peek have unlimited consensus numbers and can implement other objects wait-free. section 8.5.2 section 8.7
Table 8.1 Consensus numbers of wait-free primitives that you’ll typically use. The consensus number represents the maximum number of threads or processes a primitive can guarantee consensus for.
| Wait-free primitive |
Consensus number |
|---|---|
| Atomic registers |
1 |
| Test-and-set |
2 |
| Fetch-and-add |
2 |
| Queues |
2 |
| Stacks |
2 |
| Queues with peek |
∞ |
| Compare-and-swap (CAS) |
∞ |
Compare consensus numbers before selecting a wait-free primitive for the required process count. section 8.5.2
Traditional locks can suffer inefficiency, priority inversion, deadlocks, and convoying, where delayed lock holders queue other threads, increasing tail latency and reducing throughput. Wait-free synchronization addresses these blocking-related costs but remains complex to implement. section 8.2.3 section 8.7
