Concurrency and synchronization form the architectural core of multi-threaded systems programming, high-performance database engines, and distributed operating systems. As modern multi-core CPUs execute instructions out-of-order and cache memory hierarchically across L1/L2/L3 caches, coordinating concurrent threads requires precise synchronization primitives to prevent data races, deadlocks, and stale memory visibility anomalies.
This guide details synchronization primitives (Mutexes, Read-Write Locks, Semaphores, and Condition Variables), non-blocking lock-free atomics (Compare-and-Swap CAS), hardware memory models (Acquire-Release, Sequential Consistency, and Memory Barriers), and lock contention mitigations.
+-----------------------------------------------------------------------------------------+
| SYNCHRONIZATION PRIMITIVES MATRIX |
+-----------------------------------------------------------------------------------------+
| Primitive | Blocking / Non-Blocking | Optimal Use Case | Overhead / Latency | Fairness / Ordering |
+--------------------+-------------------------+---------------------+---------------------+---------------------+
| Mutex (std::mutex) | Blocking (Futex/Sleep) | High-contention | High (Context switch| OS Scheduler |
| | | complex invariants | ~ 1,500 - 3,000 ns)| dependent |
+--------------------+-------------------------+---------------------+---------------------+---------------------+
| Spinlock | Non-blocking (Busy-wait)| Ultra-short hold | Low (< 10 ns) if | Unfair (CPU cache |
| | | times (< 100 ns) | uncontended; burns | line bouncing) |
+--------------------+-------------------------+---------------------+---------------------+---------------------+
| Read-Write Lock | Blocking (Shared/Excl) | Read-heavy (95%+ R) | Moderate (Atomic | Reader/Writer |
| (rwlock) | | multi-reader access | refcount overhead) | preference modes |
+--------------------+-------------------------+---------------------+---------------------+---------------------+
| Semaphore | Blocking / Signaling | Resource pooling & | Moderate (Counter | FIFO queue options |
| (Counting) | | rate limiting | decrement/signal) | |
+--------------------+-------------------------+---------------------+---------------------+---------------------+
| Lock-Free Atomics | Non-blocking (Hardware) | Single-word state, | Lowest (< 5 ns) via | Lock-free / |
| (std::atomic, CAS) | | queues, counters | CMPXCHG hardware | Wait-free bounds |
+-----------------------------------------------------------------------------------------+
Coffman Deadlock Conditions:
1. Mutual Exclusion: At least one resource held in a non-shareable mode.
2. Hold and Wait: A thread holding resources requests new resources.
3. No Preemption: Resources cannot be forcibly confiscated from a thread.
4. Circular Wait: A closed chain of threads exists where T1 waits for T2, and T2 waits for T1.
To eliminate Circular Wait, systems enforce a global Lock Hierarchy: if a thread must acquire both Lock A and Lock B, it must always acquire Lock A before Lock B, regardless of execution path.
// C++11 std::lock: Deadlock-Free Multi-Lock Acquisition
std::unique_lock<std::mutex> lockA(mutexA, std::defer_lock);
std::unique_lock<std::mutex> lockB(mutexB, std::defer_lock);
std::lock(lockA, lockB); // Uses deadlock avoidance algorithm (Resource Ordering)
Lock-free data structures guarantee that at least one concurrent thread makes forward progress in a finite number of steps, eliminating context-switch overhead and thread priority inversion.
The core hardware instruction powering lock-free algorithms is Compare-and-Swap (CAS) (CMPXCHG on x86, LDREX/STREX on ARM):
CAS Atomic Logic:
bool CAS(int* address, int expected_value, int new_value) {
if (*address == expected_value) {
*address = new_value;
return true; // Success!
}
return false; // Value changed concurrently by another thread
}
// Lock-Free Atomic Counter Increment Loop
void atomic_increment(std::atomic<int>& counter) {
int current = counter.load(std::memory_order_relaxed);
while (!counter.compare_exchange_weak(current, current + 1,
std::memory_order_release,
std::memory_order_relaxed)) {
// Spin loop: 'current' is automatically updated with fresh value on failure
}
}
If Thread 1 reads pointer A, and Thread 2 changes A \to B \to A before Thread 1's CAS executes, the CAS succeeds even though intermediate state was modified.
Modern multi-core processors reorder memory read/write instructions to maximize pipeline utilization. Memory models define visibility guarantees across threads:
+---------------------------+-----------------------------------+------------------------+
| Memory Order Mode | CPU Barrier Behavior | Performance / Safety |
+---------------------------+-----------------------------------+------------------------+
| `memory_order_relaxed` | Guarantees atomic read/write only;| Maximum performance; |
| | no synchronization or ordering | zero barrier overhead |
| `memory_order_acquire` | Prevents reads/writes from moving | High performance; used |
| | before this load operation | on mutex acquire/read |
| `memory_order_release` | Prevents reads/writes from moving | High performance; used |
| | after this store operation | on mutex release/write |
| `memory_order_seq_cst` | Total global sequential ordering; | Safe default; emits full|
| | strict memory fence barriers | CPU hardware fences |
+---------------------------+-----------------------------------+------------------------+