Barrier Free Synchronization
Non-Blocking Synchronization refers to concurrent algorithms and data structures that guarantee system-wide progress without using locks (mutexes), classified by their progress guarantees into wait-free, lock-free, and obstruction-free categories — providing immunity to priority inversion, deadlock, and convoying that plague lock-based designs.
Lock-based synchronization has fundamental problems: priority inversion (a high-priority thread waits for a low-priority thread holding a lock), convoying (all threads queue behind one slow lock-holder), deadlock (circular lock dependencies), and inability to compose (combining two lock-based data structures into a larger atomic operation is generally unsafe). Non-blocking algorithms eliminate these issues.
Progress Guarantee Hierarchy:
| Guarantee | Definition | Strength | Practical |
|---|---|---|---|
| Wait-free | Every thread completes in bounded steps | Strongest | Hard to achieve |
| Lock-free | At least one thread makes progress | Strong | Practical choice |
| Obstruction-free | A thread in isolation completes | Weakest | Easy to achieve |
Lock-Free Algorithm Design: Most practical non-blocking algorithms are lock-free. The core technique is CAS (Compare-And-Swap) loops: read current state, compute desired new state, atomically swap if state hasn't changed. Example — lock-free stack push:
Repeat: read top -> new_node->next = top -> CAS(&top, top, new_node) until success.
If CAS fails (another thread modified top), retry with the new value. Lock-free guarantee: if CAS fails, some other thread's CAS succeeded — global progress is assured.
The ABA Problem: CAS can be fooled if a value changes from A to B and back to A between read and CAS. Solution: tagged pointers (combine version counter with pointer — CAS succeeds only if both match), hazard pointers (defer reclamation of nodes until no thread holds a reference), or epoch-based reclamation (batch reclamation in epochs).
Memory Reclamation: The hardest problem in lock-free programming — when can freed memory be safely reused? Without a lock protecting the data structure, a thread might hold a reference to a node being freed. Solutions:
- Hazard pointers: Each thread publishes pointers to nodes it's currently accessing. Memory can be freed only when no hazard pointer references it. O(1) overhead per access, O(N*M) scan on reclamation.
- Epoch-Based Reclamation (EBR): Threads advance through numbered epochs. Memory freed in epoch E can be reclaimed once all threads have passed epoch E+2. Simple and fast but assumes threads don't stall (a stalled thread blocks reclamation).
- Reference counting: Atomic reference counts on each node. When count reaches zero, free. Overhead: 2 atomic operations per access (increment/decrement).
Wait-Free Algorithms: Guarantee bounded completion for every thread. Typically use helping mechanisms — if a thread detects another thread is mid-operation, it helps complete that operation before proceeding with its own. Universal constructions exist (wait-free simulation of any sequential data structure) but are generally too slow for production use.
Non-blocking synchronization represents the theoretical ideal for concurrent programming — eliminating all blocking-related pathologies at the cost of algorithm complexity, and is essential for real-time systems, kernel-level code, and high-performance concurrent data structures where lock contention would be unacceptable.