Concurrent Queue with Atomic Indices

The Problem: Data Races on Simple Integers

Imagine our producer and consumer threads running on different CPU cores.

• The producer thread reads head and writes to tail.
• The consumer thread reads tail and writes to head.

What happens when, for example, the producer is in the middle of writing a new 64-bit value to the tail index, and the consumer thread tries to read it? Or what if the producer reads head, calculates that there's space, but before it can write, the consumer reads an element and updates head? These scenarios are called data races, and they lead to undefined behavior: corrupted data, incorrect state, and crashes.

A simple increment like tail++ isn't a single, indivisible operation. At the machine level, it's a sequence:

1. Read the current value of tail from memory into a register.
2. Modify the value in the register (add 1).
3. Write the new value from the register back to memory.

If a thread is interrupted by the OS between these steps, another thread can read a stale value, leading to chaos. Let's see a practical demonstration of exactly this problem.

The Solution: std::atomic

To prevent data races, we need operations that are atomic. An atomic operation is one that executes as a single, indivisible transaction. Other threads will see the state of the system either as it was before the operation or as it was after it, but never in a partially-completed intermediate state.

C++11 introduced the std::atomic template in the <atomic> header to provide this guarantee.

To fix our ring buffer, we simply change the type of our head and tail indices from size_t to std::atomic<size_t>.

#include <atomic> // Don't forget to include the header!

template <typename T>
class SPSCQueue {
private:
    // ... buffer, capacity, mask from previous lesson ...

    // The key change: our indices are now atomic!
    std::atomic<size_t> head_ = 0;
    std::atomic<size_t> tail_ = 0;

public:
    // ...
};

This simple change is profound. Now, any operation on head_ or tail_ is guaranteed to be atomic. A tail_.fetch_add(1) operation (which is what tail_++ does for atomics) is no longer a separable read-modify-write sequence; it is a single, uninterruptible hardware instruction.

The article "Lock-free SPSC Queue" shows this exact modification.

Atomicity is Not Enough: Memory Ordering

Making the index updates atomic solves the problem of torn reads and interrupted increments. However, there's a more subtle issue: memory visibility and ordering.

Consider the producer's logic:

1. Write data to buffer_[i].
2. Increment tail to publish that the new data is available.

A smart compiler or an out-of-order CPU might decide it's more efficient to reorder these operations, incrementing tail before the data is actually written to the buffer. If this happens, the consumer could see the updated tail index, try to read the data, and get garbage because the data hasn't been written yet.

This is where memory ordering comes in. Atomic operations can be given memory ordering constraints that tell the compiler and CPU which kinds of reordering are forbidden.

By default, all std::atomic operations use the strongest memory order: std::memory_order_seq_cst (sequential consistency). This ordering does two crucial things:

1. It ensures all threads agree on a single global sequence of atomic operations.
2. It acts as a full memory barrier (or "fence"), preventing any memory reads or writes from being moved across the atomic operation.

In our push example, the tail_.store(new_value) with default sequential consistency guarantees that the write to the buffer_ happens before the new tail value becomes visible to any other thread. This correctly synchronizes the producer and consumer.

Let's return to Charles Frasch's talk, where he explains this with excellent timeline diagrams.

Conclusion

In this lesson, we made the critical transition from a conceptual, single-threaded design to a correct, concurrent one. You've now taken the most important step in building the "spine" of our telemetry profiler.

Key Takeaways:

• Accessing shared non-atomic variables (like our head and tail indices) from multiple threads leads to data races and undefined behavior.
• std::atomic<T> provides indivisible, uninterruptible operations on a variable of type T, preventing these races.
• To make our ring buffer thread-safe, we must declare our head and tail indices as std::atomic<size_t>.
• By default, std::atomic operations use sequentially consistent memory ordering, which acts as a memory fence. This guarantees that writes to our data buffer become visible to the consumer thread before the corresponding index update does, ensuring correctness.

What's Next?

We've made our indices atomic and learned that the default memory ordering provides the correctness we need. However, sequential consistency is the strictest (and potentially most expensive) ordering. For a high-performance data structure like this, we can often achieve the same correctness with more relaxed, and therefore faster, memory orders.

In the next lesson, "Implement the non-blocking push operation, applying memory_order_release to publish data," we will begin writing the final code for our push method. We'll move beyond the default ordering and explicitly use std::memory_order_release and std::memory_order_acquire—a common and highly efficient pattern for producer-consumer scenarios.