Mastering Lock-Free Queue: Theory and Implementation

1. Introduction and Core Concepts

A lock-free queue is a concurrent FIFO data structure that guarantees system-wide progress without using mutual exclusion locks. Unlike a traditional queue protected by a mutex, where a thread holding the lock can block all other threads if it is preempted, descheduled, or crashes, a lock-free queue ensures that at least one thread always makes progress even when multiple threads contend for enqueue and dequeue operations. This property is crucial for building highly scalable, low-latency systems on modern multi-core processors.

The term "lock-free" is often misunderstood. It does not mean wait-free or non-blocking in the informal sense; it has a precise definition in concurrent programming theory. A data structure is lock-free if, when multiple threads operate on it concurrently, at least one operation completes in a finite number of steps. This is weaker than wait-freedom, which guarantees that every thread completes in a finite number of steps, but significantly stronger than blocking synchronization. A lock-free queue therefore tolerates thread delays and failures gracefully, avoids deadlock, livelock, and priority inversion, and reduces context switching overhead.

Why does the lock-free queue matter today? As core counts scale from 4 to 64 and beyond, lock contention becomes a primary bottleneck. In high-throughput domains such as network packet processing, trading engines, game engines, and operating system kernels, a single contended lock can collapse scalability. The lock-free queue, most famously the Michael and Scott queue introduced in 1996, has become the foundational building block for work-stealing schedulers, inter-thread message passing, event loops, and asynchronous I/O pipelines. Understanding its theory and implementation is essential for any engineer working on concurrent systems.

What Makes a Queue Lock-Free?

A standard queue supports two primary operations: enqueue at the tail and dequeue from the head. In a lock-based implementation, both operations are wrapped in a critical section. In a lock-free implementation, these operations are implemented using atomic hardware primitives such as Compare-And-Swap (CAS), Load-Linked/Store-Conditional (LL/SC), or Fetch-And-Add (FAA). Instead of blocking, a thread attempts to atomically update a pointer; if it fails due to contention, it simply retries. This optimistic concurrency control is the heart of lock-freedom.

To achieve this, lock-free queues typically use a singly linked list with a dummy sentinel node. Two shared atomic pointers, head and tail, point to the first and last nodes. Enqueuers append a new node after the tail using CAS, and dequeuers advance the head pointer using CAS. Because these two operations act on different ends of the queue, they can often proceed in parallel without interfering, which is a key source of performance.

Progress Guarantees Explained

It is helpful to place lock-free queues in the hierarchy of non-blocking progress guarantees. Blocking queues provide no guarantee: a thread holding a lock can stall the entire system. Lock-free queues guarantee system-wide progress. Wait-free queues guarantee per-thread progress. Obstruction-free queues guarantee progress only when a thread runs in isolation. For most practical systems, lock-free is the sweet spot: it provides strong enough guarantees to avoid catastrophic stalls while being simpler and faster than wait-free alternatives, which often require more complex helping mechanisms and higher overhead.

2. How It Works

The canonical lock-free queue is the Michael-Scott queue (MS-Queue). It solves a deceptively difficult problem: how to allow multiple producers and multiple consumers to concurrently modify head and tail without locks, while maintaining FIFO order and avoiding lost updates. The design relies on three key ideas: an invariant with a dummy node, atomic tail chasing, and careful ordering of pointer updates.

The queue is represented as a linked list where head always points to a dummy node whose value is irrelevant. The first real element is head.next. The tail points to the last node, or sometimes to the second-to-last node if it has fallen behind. This dummy node eliminates special cases for empty queues and allows enqueue and dequeue to be decoupled. An empty queue is one where head == tail and head.next == None.

Enqueue proceeds in two steps. First, the thread reads the current tail and its next pointer. If tail is consistent and next is None, it tries to CAS tail.next from None to the new node. If successful, the new node is now logically in the queue. Second, it tries to CAS tail from the old tail to the new node. If this second CAS fails, it does not matter for correctness; another thread will help advance the tail. This helping mechanism is what keeps the structure lock-free. A thread that sees tail.next != None knows another enqueue is in progress and will try to swing tail forward before retrying its own operation.

The Role of Compare-And-Swap (CAS)

Compare-And-Swap is an atomic instruction provided by modern CPUs (e.g., CMPXCHG on x86, CAS on ARM). It atomically performs: if *addr == expected then *addr = new and return true else return false. CAS is the universal primitive for building lock-free structures because it allows a thread to detect interference. If two threads try to enqueue simultaneously, only one CAS on tail.next will succeed; the other will observe the failure and retry. This retry loop is often called a spin or CAS loop.

However, CAS alone introduces the infamous ABA problem. A thread reads value A, is preempted, another thread changes the value from A to B and back to A, and the first thread's CAS incorrectly succeeds despite the intervening modification. In a queue, this can cause a dequeued node that was freed and reallocated to be mistaken for the same node, leading to corruption. Real implementations solve ABA with tagged pointers, version counters, or hazard pointers.

Dequeue and Helping

Dequeue is slightly more complex. A thread reads head, tail, and head.next. If head == tail, the queue might be empty or tail might be lagging. If head.next is None, the queue is empty and the operation returns failure. Otherwise, if head == tail but head.next != None, tail is behind and the thread helps advance tail with CAS before retrying. If the queue is non-empty, the thread attempts to CAS head from old head to head.next. On success, it has logically removed the old dummy node, and the new head's value is the dequeued result. The old dummy node can then be reclaimed safely, subject to memory reclamation constraints.

This helping pattern ensures lock-freedom: no thread can block another indefinitely. If a thread stalls after linking a node but before swinging tail, any other thread that observes the intermediate state will complete the tail update for it, allowing progress to continue.

3. Implementation

Python does not expose true lock-free primitives at the language level due to the Global Interpreter Lock (GIL) in CPython, but we can simulate the logic accurately using atomic references and illustrate the exact algorithm that would be used in C++, Java, or Rust. The following examples capture the essential CAS loops, ABA mitigation, and memory ordering concepts. In production, you would implement this in a language with hardware atomics and use libraries like Atomics in Java or std::atomic in C++.

We first build a minimal AtomicReference abstraction to simulate CAS semantics. In a real system this would be a single hardware instruction, not a lock. We use a lock here only to emulate atomicity for educational purposes in Python.

import threading
import time
from typing import Optional, Any

class AtomicReference:
    """Simulates a hardware atomic pointer with CAS."""
    def __init__(self, value: Any):
        self._value = value
        self._lock = threading.Lock()

    def get(self) -> Any:
        with self._lock:
            return self._value

    def compare_and_set(self, expected: Any, new: Any) -> bool:
        """Atomic CAS: if current == expected, set to new and return True."""
        with self._lock:
            if self._value is expected:
                self._value = new
                return True
            return False

class Node:
    def __init__(self, value: Any = None):
        self.value = value
        self.next: Optional[AtomicReference] = None
        # For ABA prevention, add a version tag in real implementations
        self.tag = 0

    def __repr__(self):
        return f"Node({self.value})"

With atomic references in place, we can implement the core Michael-Scott lock-free queue. Note the two-step enqueue and the helping behavior for both enqueue and dequeue. All shared state (head and tail) is accessed only through atomic operations.

class MichaelScottQueue:
    """Lock-free queue (Michael & Scott, 1996) - Python simulation."""
    def __init__(self):
        dummy = Node()  # sentinel node
        dummy.next = AtomicReference(None)
        self.head = AtomicReference(dummy)
        self.tail = AtomicReference(dummy)

    def enqueue(self, value: Any) -> None:
        new_node = Node(value)
        new_node.next = AtomicReference(None)
        while True:
            tail = self.tail.get()
            tail_next = tail.next.get()
            # Check consistency - is tail still the same?
            if tail is self.tail.get():
                if tail_next is None:
                    # Tail is at the end, try to link new node
                    if tail.next.compare_and_set(None, new_node):
                        # Linking succeeded, try to swing tail (may fail, that's ok)
                        self.tail.compare_and_set(tail, new_node)
                        return
                else:
                    # Tail is lagging, help advance it
                    self.tail.compare_and_set(tail, tail_next)

    def dequeue(self) -> Optional[Any]:
        while True:
            head = self.head.get()
            tail = self.tail.get()
            head_next = head.next.get()
            if head is self.head.get():  # consistency check
                if head is tail:
                    if head_next is None:
                        return None  # empty
                    # Queue in intermediate state, help advance tail
                    self.tail.compare_and_set(tail, head_next)
                else:
                    # Read value before CAS, otherwise another dequeue might free it
                    value = head_next.value
                    if self.head.compare_and_set(head, head_next):
                        # Success - old dummy can be reclaimed (hazard pointers needed in C++)
                        return value

    def is_empty(self) -> bool:
        head = self.head.get()
        return head.next.get() is None

    def peek(self) -> Optional[Any]:
        head_next = self.head.get().next.get()
        return head_next.value if head_next is not None else None

To address the ABA problem, production implementations add a monotonic counter to each pointer. In Python we can illustrate the concept with a tagged pointer. The tag is incremented on every CAS, so even if a pointer cycles back to the same address, the tag will differ and the CAS will fail.

class TaggedPointer:
    """ABA prevention via version counter (a.k.a. stamped reference)."""
    def __init__(self, ptr, tag=0):
        self.ptr = ptr
        self.tag = tag

class ABASafeAtomicReference:
    def __init__(self, value):
        self._ptr = TaggedPointer(value, 0)
        self._lock = threading.Lock()

    def get(self) -> TaggedPointer:
        with self._lock:
            return TaggedPointer(self._ptr.ptr, self._ptr.tag)

    def compare_and_set(self, expected: TaggedPointer, new_ptr) -> bool:
        with self._lock:
            if self._ptr.ptr is expected.ptr and self._ptr.tag == expected.tag:
                self._ptr = TaggedPointer(new_ptr, expected.tag + 1)
                return True
            return False

# Usage in queue would be:
# head = ABASafeAtomicReference(dummy_tagged)
# On dequeue: head.compare_and_set(old_tagged, next_node)
# Tag increment ensures ABA is detected even if node address is reused.

Finally, here is a concurrent test harness that demonstrates correct FIFO behavior under contention. While CPython's GIL serializes execution, this harness validates logical correctness and can be adapted to Jython, PyPy, or translated to a true parallel language.

def test_lock_free_queue_concurrent():
    q = MichaelScottQueue()
    results = []
    results_lock = threading.Lock()

    def producer(start, count):
        for i in range(start, start + count):
            q.enqueue(i)

    def consumer(total_to_consume):
        consumed = 0
        while consumed < total_to_consume:
            val = q.dequeue()
            if val is not None:
                with results_lock:
                    results.append(val)
                consumed += 1
            else:
                # Back-off to reduce contention - exponential or yield in real code
                time.sleep(0.0001)

    # 2 producers, 2 consumers, 1000 items total
    threads = []
    threads.append(threading.Thread(target=producer, args=(0, 500)))
    threads.append(threading.Thread(target=producer, args=(500, 500)))
    threads.append(threading.Thread(target=consumer, args=(500,)))
    threads.append(threading.Thread(target=consumer, args=(500,)))

    for t in threads:
        t.start()
    for t in threads:
        t.join()

    # Verify all items present and FIFO per producer not globally guaranteed
    # but no items lost or duplicated
    assert len(results) == 1000
    assert sorted(results) == list(range(1000))
    print(f"SUCCESS: Consumed {len(results)} items, no loss/duplication")
    print(f"Queue empty? {q.is_empty()}")

# Run the test
test_lock_free_queue_concurrent()

4. Step-by-Step Example

Let us walk through a concrete execution with two producer threads (P1, P2) and one consumer thread (C1) operating on a queue that initially contains [10, 20] with a dummy node D. The initial state is: head -> D -> 10 -> 20, tail -> 20. We will trace how enqueue(30) and dequeue() interleave without locks.

Step 1: P1 begins enqueue(30). It reads tail = 20 and tail.next = None. It prepares new node N30 with next = None. Before it can execute CAS, it is preempted by the scheduler.

Step 2: P2 begins enqueue(40). It also reads tail = 20 and tail.next = None (same snapshot as P1). It tries CAS(tail.next, None, N40). This succeeds, so the list is now D -> 10 -> 20 -> 40. P2 then tries CAS(tail, 20, 40) which succeeds, so tail now points to 40. P2 completes. The queue is D -> 10 -> 20 -> 40.

Step 3: P1 resumes. Its earlier CAS(tail.next, None, N30) will now fail because tail is no longer 20, or more precisely tail.next is no longer None (it is 40). P1's consistency check detects tail is not the same as tail.get(), so it loops. On retry, it reads tail = 40, tail.next = None, and CAS(tail.next, None, N30) succeeds. List becomes D -> 10 -> 20 -> 40 -> 30. It then swings tail to 30. Queue is now D -> 10 -> 20 -> 40 -> 30. Note the order is FIFO by successful link time, not by thread start time.

Dequeue Interleaving

Step 4: C1 begins dequeue(). It reads head = D, tail = 30, head.next = 10. Since head != tail, it attempts CAS(head, D, 10). If no other consumer interferes, this succeeds. The new head becomes the node containing 10, which now serves as the new dummy. The old dummy D is logically removed and can be reclaimed. The returned value is 10. The queue is now 10(dummy) -> 20 -> 40 -> 30.

Step 5: Consider the helping scenario. Suppose P1 had linked N30 but stalled before swinging tail, leaving tail pointing to 40 while tail.next points to 30. C1 or another producer that observes tail.next != None will execute CAS(tail, 40, 30) to help. This ensures tail never stays behind indefinitely, which could otherwise cause subsequent enqueues to repeatedly fail their first CAS and degrade performance.

This walkthrough highlights why the dummy node is essential. Without it, dequeue would need to handle the case where head is None atomically with enqueue updating head, creating a race. The dummy ensures head and tail are never None and that enqueue and dequeue operate on different nodes in the common case, enabling true concurrency.

5. Complexity Analysis

Complexity analysis for lock-free data structures must distinguish between the cost of a single operation in isolation and the cost under contention. In the absence of contention, both enqueue and dequeue perform a constant number of atomic operations and pointer dereferences. Under contention, a thread may need to retry its CAS loop multiple times, but the system as a whole still makes progress.

Time complexity is typically described as O(1) expected time per operation, with the understanding that worst-case time for an individual thread is unbounded in theory (it could starve if it always loses the CAS race), though this is rare in practice with fair scheduling. Space complexity is O(n) where n is the number of elements currently in the queue plus at most one dummy node. However, memory reclamation adds subtlety: nodes that have been dequeued cannot be immediately freed if other threads might still hold references to them, leading to transient extra memory usage.

It is also important to analyze contention overhead. Each failed CAS is wasted work. Under high contention, the number of retries scales with the number of threads. Techniques like exponential backoff, where a thread sleeps briefly after a failed CAS, can reduce cache coherence traffic and improve throughput, though they increase latency for the individual thread.

Where k is the number of contending threads. Note that "worst case" here refers to a single thread's latency, not system throughput. System throughput remains lock-free: in any infinite execution, infinitely many operations complete. This is a critical distinction from blocking queues where a single stalled thread can halt all progress.

Amortized and Cache Considerations

From a hardware perspective, the dominant cost is not instruction count but cache coherence. Each successful CAS invalidates the cache line holding head or tail in other cores, forcing a round-trip to the coherence protocol. Enqueue and dequeue touching different cache lines (tail vs head) is why the Michael-Scott queue scales well for single-producer-single-consumer or when producers and consumers are balanced. When many threads hammer the same end, the cache line bounces and throughput plateaus. This is why more advanced designs like the LCRQ (Linked Concurrent Ring Queue) or elimination techniques are used for extreme contention.

6. Variations and Optimizations

The basic Michael-Scott queue is a solid foundation, but numerous variations optimize for specific workloads, contention levels, or progress guarantees. Understanding these helps you choose the right implementation for your system.

The Bounded MPMC Array Queue, often called the Vyukov queue or Lamport queue for SPSC, uses a fixed-size ring buffer instead of a linked list. It stores elements in an array and uses sequence numbers or head/tail indices updated with CAS or FAA. This eliminates per-element allocation, improves cache locality, and simplifies memory reclamation. It is ideal when maximum size is known and allocation overhead must be avoided, such as in network drivers or real-time audio processing. The trade-off is that enqueue blocks or fails when full, and it requires careful handling of wrap-around.

Batching and flat combining are optimizations for high contention. Instead of each thread performing its own CAS, threads combine their operations: one thread becomes the combiner and applies a batch of enqueues/dequeues while others wait. This converts many contended CAS operations into a single bulk update, dramatically improving throughput at the cost of increased latency for individual operations. LMAX Disruptor takes a different approach: it uses a single writer principle and sequence barriers to achieve wait-free progress for consumers without CAS at all.

Wait-Free and Hybrid Approaches

Wait-free queues, such as the Kogan-Petrank queue, guarantee that every thread finishes in a bounded number of steps by using helping with operation descriptors. Each thread publishes its operation, and other threads help complete it before proceeding. This eliminates starvation but adds overhead: every operation must allocate a descriptor and threads must scan for pending operations. For most applications, lock-free is sufficient, but wait-free is valuable in hard real-time systems where thread starvation is unacceptable.

Memory reclamation is the most complex optimization area. In garbage-collected languages like Java or Go, reclamation is automatic. In C/C++, you must use Hazard Pointers, Epoch-Based Reclamation (EBR), or Quiescent-State-Based Reclamation (QSBR). Hazard pointers let a reader announce which nodes it is accessing, preventing reclamation. EBR divides execution into epochs and defers reclamation until all threads have passed through a quiescent state. Choosing the wrong scheme can lead to use-after-free or unbounded memory growth.

ABA Mitigation Strategies

Beyond tagged pointers, modern CPUs offer Double-Wide CAS (DWCAS) that atomically updates a pointer and counter together (e.g., CMPXCHG16B on x86-64). Some designs use hazard pointers to ensure a node is never reused while any thread might still reference it, which sidesteps ABA entirely. In Rust, the crossbeam crate provides epoch-based reclamation that makes ABA-safe queues ergonomic and safe.

7. Real-World Applications

Lock-free queues are ubiquitous in infrastructure software where latency and scalability are paramount. They are rarely visible to end users but form the backbone of high-performance systems.

In web servers and event loops, lock-free queues decouple I/O threads from worker threads. For example, Netty, Node.js's libuv, and Nginx use MPMC queues to pass accepted connections or completed I/O events to a thread pool without blocking the event loop. This ensures that a slow request handler does not stall the acceptor thread, maintaining high connection rates under load.

In databases and storage engines, write-ahead log (WAL) buffers and transaction commit queues are often lock-free. Systems like RocksDB, ScyllaDB, and Kafka use lock-free queues to pipeline log appends: multiple writer threads enqueue log records, and a single flush thread dequeues them in batches to disk. This reduces lock contention on the hot WAL path and improves tail latency for writes.

Operating system kernels and networking stacks use lock-free queues for inter-core communication. The Linux kernel's io_uring, DPDK, and high-frequency trading platforms use bounded lock-free ring buffers to pass packets between cores at millions of operations per second, bypassing the kernel's locking overhead entirely. Similarly, GPU command queues and task schedulers in game engines (e.g., Intel TBB, Unreal Engine) use work-stealing deques, which are specialized lock-free queues, to balance load across cores.

Even in managed languages, lock-free queues are critical. Java's ConcurrentLinkedQueue, C++'s boost::lockfree::queue, and Rust's crossbeam-queue are direct implementations of the Michael-Scott algorithm and are used extensively in microservices and data pipelines. Choosing a lock-free queue in these contexts is not premature optimization; it is often the default for any cross-thread channel that must remain responsive under load.

8. Comparison with Alternatives

Selecting a queue implementation requires trading off throughput, latency, progress guarantees, implementation complexity, and memory overhead. A lock-free queue is not always the best choice; simpler alternatives may be faster under low contention or easier to reason about.

A mutex-based queue is the simplest and often fastest when contention is low. It has minimal overhead for a single thread and is easy to implement correctly. However, under contention it suffers from context switches, convoying, and vulnerability to thread preemption. A lock-free queue outperforms it when more than a few threads contend, but may be slightly slower in the uncontended case due to CAS loop overhead.

A wait-free queue provides the strongest guarantee but is more complex and often slower due to helping overhead. A lock-free stack is similar in implementation but has different semantics (LIFO) and suffers from higher contention because all operations hit the same top pointer, whereas a queue's head and tail can be updated independently.

The key takeaway is to match the structure to the workload. For single-producer-single-consumer (SPSC) with a known bound, a ring buffer is almost always superior: it is wait-free, cache-friendly, and allocation-free. For general MPMC with unpredictable load and where allocation is acceptable, the lock-free queue is the workhorse. For hard real-time, consider wait-free. For low contention or when simplicity is paramount, a well-tuned mutex queue with a spin-then-block strategy may be perfectly adequate and far easier to maintain.

9. Common Mistakes and Best Practices

Implementing lock-free queues correctly is notoriously difficult. Even experts publish buggy algorithms that fail under rare interleavings. The most common pitfalls stem from memory ordering, reclamation, and subtle race conditions.

The first major mistake is ignoring memory ordering. On x86, the memory model is relatively strong (TSO), so many buggy implementations appear to work. On ARM or RISC-V, which have weaker models, missing a memory fence can cause a thread to see tail.next updated before tail itself, or to read a stale value. In C++ this means using std::memory_order_acquire for loads and std::memory_order_release for stores, with CAS using acq_rel. In Java, volatile and VarHandle provide the needed ordering. Never assume sequential consistency without explicitly requesting it.

The second mistake is unsafe memory reclamation leading to use-after-free and ABA. A classic bug is freeing a dequeued node immediately and then reusing it for a new enqueue while another thread still holds a reference to the old node. In C++ this manifests as a segfault or silent corruption. The fix is to use a proper reclamation scheme: hazard pointers, epoch-based reclamation, or rely on a garbage collector. Never call free() or delete directly after dequeue in a lock-free structure.

A third mistake is busy-spinning without backoff. A tight CAS retry loop under high contention generates massive coherence traffic and wastes CPU. Best practice is to add a backoff strategy: after a failed CAS, execute a pause instruction (e.g., _mm_pause on x86), yield, or exponentially increase a delay. Some implementations use a bounded number of spins before falling back to a different strategy. This dramatically improves throughput and power efficiency.

Best Practices Checklist

• Always use a dummy sentinel node to avoid special cases for empty queues and to decouple head and tail.
• Validate the consistency snapshot: re-read head/tail after reading next to ensure they have not changed before attempting CAS.
• Handle the lagging tail case explicitly: if tail.next != None, help advance tail before retrying.
• Use tagged pointers or hazard pointers to prevent ABA; test on weak memory architectures, not just x86.
• Separate reclamation from logical removal: retire nodes to a garbage list and reclaim only when no thread can access them.
• Prefer bounded array queues when allocation rate is high or when you need better cache locality.
• Benchmark under contention: measure throughput with 1, 2, 4, 8, 16 threads, not just single-threaded latency.
• Consider using mature libraries (Java's ConcurrentLinkedQueue, Rust's crossbeam, C++'s moodycamel::ConcurrentQueue) instead of rolling your own for production.

Testing lock-free code requires specialized techniques. Stress tests with many threads and random delays, combined with model checkers like CDSChecker or Relacy, can uncover races that unit tests miss. Linearizability checkers can verify that every concurrent execution is equivalent to some sequential FIFO order. Invest in these tools early, as bugs in lock-free code are often heisenbugs that appear only under specific schedules.

10. Interview Questions

Lock-free queues are a favorite topic in senior systems and concurrency interviews because they test understanding of atomics, progress guarantees, and practical trade-offs. Here are common questions and how to approach them.

Q1: What is the difference between blocking, lock-free, and wait-free?

Answer: Blocking means a thread can be delayed indefinitely by another thread holding a lock (e.g., mutex queue). Lock-free guarantees that at least one thread makes progress in a finite number of steps, so the system as a whole never stalls even if threads are preempted. Wait-free is stronger: every thread completes in a bounded number of steps, guaranteeing per-thread starvation freedom. Example: Michael-Scott queue is lock-free but not wait-free, because a thread could theoretically starve if it always loses CAS races. Emphasize that lock-free avoids deadlock and priority inversion but does not guarantee fairness.

Q2: Implement a lock-free queue's enqueue using CAS. How do you handle the case where tail is falling behind?

Answer: Describe the two-step enqueue: read tail and tail.next, if tail.next is None try CAS(tail.next, None, newNode), then CAS(tail, oldTail, newNode). If tail.next != None, it means another thread has already linked a node but not yet swung tail, so you help by doing CAS(tail, oldTail, tail.next) before retrying. This helping ensures lock-freedom. Mention the need for a dummy node and the consistency check (re-read tail after reading next). Provide pseudocode and note the ABA problem and its mitigation with tags.

Q3: What is the ABA problem and how would you solve it in a lock-free queue?

Answer: ABA occurs when a thread reads A, another thread changes A -> B -> A, and the first thread's CAS succeeds incorrectly. In a queue, a node could be dequeued, freed, reallocated, and enqueued again, causing a CAS on head or tail to succeed when it should fail. Solutions: tagged pointers (pointer + monotonic counter with DWCAS), hazard pointers (prevent reuse while referenced), or epoch-based reclamation (defer freeing until safe). In garbage-collected languages, GC solves it automatically. Mention that x86_64 CMPXCHG16B can atomically update pointer+counter.

Q4: When would you choose a lock-free queue over a mutex-based queue or a bounded ring buffer?

Answer: Choose lock-free queue for MPMC workloads with moderate to high contention where blocking would hurt tail latency, e.g., task pools, log pipelines. Choose mutex queue when contention is low, simplicity is key, or you need condition variables for blocking. Choose bounded SPSC ring buffer when you have single producer/consumer, need zero allocation, bounded memory, and best cache performance (e.g., audio, network drivers). Discuss trade-offs: lock-free has higher uncontended overhead and complex reclamation, but scales better; ring buffer is fastest for SPSC but blocks when full.

Q5: Why can't you simply free a node immediately after dequeue in C++?

Answer: Because another thread might still hold a reference to that node. For example, a thread that read head before the dequeue may still be about to read head.next. If you free the node, that thread will dereference freed memory. Safe reclamation requires hazard pointers, epoch reclamation, or RCU to ensure no thread holds a reference before freeing. This is why lock-free memory management is the hardest part, often more complex than the algorithm itself. Mention that this is not an issue in Java/Go due to GC.

Mastering these answers, along with the ability to sketch the Michael-Scott algorithm and discuss memory ordering, will demonstrate deep systems knowledge. Interviewers often follow up by asking you to reason about a specific interleaving or to compare throughput graphs, so practice walking through concurrent executions step by step as shown in Section 4.