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.**