Progress without locks
Non blocking algorithms avoid mutexes so that no thread can block all others by sleeping or being preempted while holding a lock. They come in strength levels defined by what progress they guarantee.
Lock free
A lock free algorithm guarantees that as long as threads keep taking steps, some thread makes progress. The whole system never stalls. The usual implementation is a CAS retry loop: if a thread CAS fails, it failed because another thread succeeded, so the system advanced. An individual thread, however, can be unlucky and retry forever while others keep winning, so lock free does not rule out starvation.
Wait free
A wait free algorithm is stronger: every thread completes its operation in a bounded number of its own steps, regardless of what other threads do. No thread can be starved. This eliminates worst case latency, which matters for real time systems, but wait free designs are typically more complex and use helping schemes where threads finish each others work.
The hierarchy
- Obstruction free, weakest, progress when one thread runs alone
- Lock free, the system as a whole always progresses
- Wait free, strongest, every thread progresses in bounded steps
Key idea
Lock free guarantees the system always progresses, wait free guarantees every thread progresses in bounded steps and cannot starve.