A hierarchy of promises
Concurrent algorithms differ in what progress they promise under contention. The hierarchy, from weakest to strongest, is:
- Blocking: a thread may wait indefinitely, for example holding a mutex. A stalled holder can stop everyone.
- Obstruction free: a thread completes in bounded steps if it runs alone with no interference. Concurrent threads may livelock, repeatedly undoing each other.
- Lock free: at least one thread always makes progress, so the system as a whole never stalls, though an individual thread may starve.
- Wait free: every thread finishes in a bounded number of its own steps, with no starvation at all.
How they relate
Each level implies the ones below it: wait free is also lock free, and lock free is also obstruction free. The stronger the guarantee, the harder and usually slower the implementation.
Choosing a level
Most production lock free libraries target lock free, the sweet spot of robustness against stalled threads with manageable complexity. Wait free is reserved for hard real time needs, and obstruction free appears in transactional memory where a contention manager resolves livelock.
Key idea
Progress guarantees rise from blocking to obstruction free to lock free to wait free, each stronger property implying the weaker ones while costing more complexity and overhead.