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

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)

Performance Characteristics

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.