A progress condition specifies what an operation can guarantee about completion while concurrent threads interfere, block, or receive unfavorable scheduling. The guarantee matters because blocking can produce high and unpredictable tail latency in low-latency systems. section 8.5.1
Common progress conditions form a spectrum of increasingly strong guarantees:
- Blocking gives a thread no progress guarantee; it may remain suspended indefinitely, for example while another thread holds a mutex or deadlocks. section 8.5.1
- Starvation-free guarantees eventual progress, but potentially after significant delays that remain unsuitable for highly predictable latency. section 8.5.1
- Obstruction-free guarantees completion within finite time when an operation runs in isolation, but contention can cause interference and livelock. section 8.5.1
- Lock-free and wait-free synchronization provide stronger alternatives to traditional mutual exclusion; wait-free structures target predictable low latency, multicore scalability, and fault tolerance. section 8.5.1 section 8.7
Mutex contention
Thread 1 holds a mutex while executing a long critical section. Thread 2 waits; if Thread 1 deadlocks, Thread 2 may never advance. Even after release, another thread may acquire the mutex first, extending the wait. A fair queue-based lock can provide stronger progress behavior than a plain mutex. section 8.5.1
Figure 8.3 The relationship between different wait-free and lock-free progress conditions
Use the relationship diagram to compare the relative strength of wait-free and lock-free progress conditions. section 8.5.1
