Non-blocking data structures
In Chapter 4 we studied the implementation of a synchronized queue. We used mutexes and condition variables as synchronization primitives. Data structures synchronized with locks are called blocking data structures because threads are blocked (by the operating system), waiting until the locks become available.
Data structures that don’t use locks are called non-blocking data structures. Most (but not all) of them are lock-free.
A data structure or algorithm is considered lock-free if each synchronized action completes in a finite number of steps, not allowing indefinite waiting for a condition to become true or false.
The types of lock-free data structures are the following:
- Obstruction-free: A thread will complete its operation in a bounded number of steps if all other threads are suspended
- Lock-free: A thread will complete its operation in a bounded number of steps while multiple threads are working on the data structure ...
