ConcurrentQueue Lock-Free Algorithm in C

The ConcurrentQueue<T> in .NET provides a high-throughput, thread-safe, first-in-first-out (FIFO) collection without relying on traditional mutual-exclusion locks. Modern implementations in .NET achieve this lock-free behavior by utilizing a linked list of fixed-size ring-buffer segments, coordinating concurrent enqueues and dequeues through low-level atomic CPU instructions like Interlocked.CompareExchange. This article details the underlying architecture of ConcurrentQueue<T>, how it evolved from the classic Michael-Scott queue, and the specific mechanics governing its lock-free operations.

Transition from Michael-Scott to Segmented Ring Buffers

Early versions of ConcurrentQueue<T> in .NET Framework were directly based on the standard Michael & Scott (1996) lock-free queue algorithm. That algorithm uses a singly linked list where every enqueued item requires allocating a new node, and operations coordinate head and tail updates via Compare-And-Swap (CAS) instructions. While mathematically sound and lock-free, this approach created substantial garbage collection (GC) pressure and poor cache locality due to frequent individual node allocations.

Starting in .NET Core and continuing in modern .NET, the implementation was redesigned into an array-based segmented architecture. Instead of allocating a node per element, ConcurrentQueue<T> organizes data into a linked list of bounded arrays, known as segments. Each segment acts as a fixed-size circular buffer (typically 32 elements). This hybrid model preserves lock-free guarantees while significantly reducing allocations, maximizing CPU cache line utilization, and mitigating cache contention.

Core Architecture: Segments and Slots

A ConcurrentQueue<T> maintains a reference to a head segment (where consumers read) and a tail segment (where producers write). Each segment contains an array of Slot structures alongside two primary 32-bit integer counters: _headAndTail or individual head and tail positions tracking the segment's logical range.

Each slot inside a segment holds:

  1. The Item (T): The actual payload stored in the queue.
  2. A Sequence Number (int): A monotonically increasing state tracker used to validate slot ownership and prevent read/write hazards.

Because the capacity of each segment is a power of two (such as 32), indexing into the array uses a fast bitwise AND operation (index & (Capacity - 1)) instead of an expensive modulo operation.

The Lock-Free Enqueue Pattern

The enqueue algorithm reserves a slot in the current tail segment using an atomic fetch-and-add pattern rather than acquiring a lock:

  1. Reserve Index: The producer thread atomically increments the segment's tail counter using Interlocked.Increment or Interlocked.Add.
  2. Capacity Validation: The thread checks whether the returned index falls within the segment's boundaries.
    • If the index is within range, the thread owns that specific slot.
    • If the index exceeds the segment's capacity, the thread detects that the segment is full. It then ensures a new segment is allocated, links it to the chain using Interlocked.CompareExchange, and attempts the enqueue in the new segment.
  3. State Verification and Slot Write: The thread inspects the sequence number of the assigned slot. The sequence number acts as a barrier:
    • When a slot is ready to be written, its sequence number matches the expected turn for that index.
    • The thread writes the element T to the slot.
    • The thread uses a volatile or atomic write to increment the slot's sequence number, signaling to consumers that the slot now contains valid, fully published data.

The Lock-Free Dequeue Pattern

The dequeue operation mirrors the producer flow but reads from the head segment:

  1. Reserve Index: The consumer thread atomically increments the segment's head counter using Interlocked.Increment.
  2. Boundary and Availability Check: The consumer compares the reserved head index against the segment's tail.
    • If the head index has caught up to or surpassed the tail, the segment is empty (or the entire queue is empty), and the operation fails or transitions to the next segment.
  3. Spinning for In-Flight Writes: If the head index is valid, the consumer checks the slot's sequence number. If a producer has reserved the slot but has not finished writing the value, the consumer briefly spins until the sequence number confirms the write is complete.
  4. Data Extraction and Cleanup: Once the sequence number indicates the slot is populated:
    • The consumer extracts the item T.
    • The slot reference is reset to default(T) to avoid memory leaks (loitering objects under the GC).
    • The sequence number is updated to indicate the slot has been consumed.
  5. Segment Disposal: When a segment's head counter reaches its capacity, the segment is completely drained. The consumer advances the queue's global head reference to the next segment, allowing the exhausted segment to be collected by the GC or returned to an internal object pool.

Synchronization and Race Condition Mitigation

The pattern eliminates several common concurrency pitfalls through hardware-level primitives:

  • Preventing the ABA Problem: By relying on monotonically increasing sequence numbers and index ranges rather than recycling raw node pointers, the implementation avoids the classic ABA hazard common to pointer-based CAS queues.
  • Cache Line Padding: Internal fields susceptible to frequent simultaneous modification (such as separate head and tail counters) are padded with empty bytes. This prevents false sharing, ensuring that writes to the tail by producers do not invalidate the CPU cache line holding the head counter used by consumers.
  • Memory Barriers: Modern .NET relies on the acquire/release semantics inherent in operations like Volatile.Write and Interlocked methods to enforce memory ordering. This guarantees that an enqueued payload is completely written to main memory before its corresponding sequence flag signals that the item is readable.