Lock Free Queue
Lock-Free Queues are the concurrent data structures that allow multiple threads to enqueue and dequeue elements simultaneously without using locks or blocking — using atomic compare-and-swap (CAS) operations to resolve contention, providing guaranteed system-wide progress (at least one thread makes progress in any finite number of steps), and achieving significantly lower tail latency than lock-based queues under high contention.
Lock-Free vs. Wait-Free vs. Lock-Based
| Property | Lock-Based | Lock-Free | Wait-Free |
|---|---|---|---|
| Progress | Blocking (priority inversion) | System-wide (some thread progresses) | Per-thread (every thread progresses) |
| Tail latency | Unbounded (lock holder preempted) | Bounded per-operation retries | Bounded per-thread |
| Throughput | Good (low contention) | Great (moderate contention) | Lower (overhead of helping) |
| Complexity | Simple | Complex | Very complex |
Michael-Scott Lock-Free Queue (MPMC)
- Classic lock-free FIFO queue using linked list + CAS.
- Enqueue:
1. Allocate new node.
2. CAS tail→next from NULL to new node. (If fail, retry — another thread enqueued.)
3. CAS tail from old tail to new node.
- Dequeue:
1. Read head→next.
2. CAS head from current to head→next. (If fail, retry.)
3. Return dequeued value.
- ABA problem: Solved with tagged pointers (version counter) or hazard pointers.
Lock-Free Ring Buffer (SPSC)
- Single-Producer Single-Consumer: simplest and fastest lock-free queue.
- Fixed-size circular buffer. Producer writes at `write_idx`, consumer reads at `read_idx`.
- Only atomic load/store needed (no CAS) — because only one thread modifies each index.
struct SPSCQueue {
std::atomic<size_t> write_idx{0};
std::atomic<size_t> read_idx{0};
T buffer[SIZE];
bool push(T val) {
auto w = write_idx.load(relaxed);
if ((w + 1) % SIZE == read_idx.load(acquire)) return false; // full
buffer[w] = val;
write_idx.store((w + 1) % SIZE, release);
return true;
}
};MPMC Ring Buffer
- Multiple producers, multiple consumers.
- Each slot has a sequence number that tracks state (empty/full/in-progress).
- CAS on sequence number to claim slot for write or read.
- Higher throughput than linked-list queue (no allocation, cache-friendly).
Memory Reclamation (The Hard Part)
| Technique | How | Tradeoff |
|---|---|---|
| Hazard Pointers | Each thread publishes pointers it's using | Per-thread overhead, bounded memory |
| RCU (Read-Copy-Update) | Defer freeing until all readers done | Fast reads, deferred reclamation |
| Epoch-Based Reclamation | Threads advance through epochs | Simple, but unbounded if thread stalls |
| Reference Counting | Atomic ref count per node | Simple, but contended counter |
Performance Characteristics
| Queue Type | Throughput (ops/sec) | Latency (p99) |
|---|---|---|
| `std::mutex` + `std::queue` | ~10-50M | 1-100 μs |
| SPSC ring buffer | ~100-500M | < 100 ns |
| MPMC lock-free (Michael-Scott) | ~20-100M | 100-500 ns |
| MPMC bounded (ring) | ~50-200M | 50-200 ns |
Lock-free queues are essential building blocks for high-performance concurrent systems — from inter-thread communication in real-time systems to message passing in actor frameworks to I/O event dispatches, they provide the low-latency, non-blocking communication channels that modern parallel software depends on.