Introduction

Circular buffer queues are common in high-throughput systems because they use fixed memory and predictable indexing. The difficult part is not the ring structure itself but the progress guarantee: depending on the producer and consumer pattern, a queue may be wait-free, lock-free, or only obstruction-free.

Progress Guarantees in Plain Terms

These terms sound similar, but they are not interchangeable.

• wait-free means every operation finishes in a bounded number of steps
• lock-free means the system as a whole keeps making progress, even if individual threads retry
• obstruction-free means an operation finishes only if it eventually runs without interference

A circular buffer queue can satisfy different guarantees depending on whether it is:

• single-producer single-consumer, often written as SPSC
• multi-producer single-consumer, often written as MPSC
• multi-producer multi-consumer, often written as MPMC

An SPSC ring buffer is relatively simple and can often be made wait-free. Once you allow multiple writers or multiple readers, atomic coordination becomes more expensive and most practical designs are merely lock-free.

Why SPSC Is Simpler

With one producer and one consumer, each side owns one index:

• the producer updates the tail
• the consumer updates the head

Each thread reads the other index to detect full or empty conditions, but it does not contend on the index it owns. That significantly reduces synchronization complexity.

Here is a minimal SPSC queue in C++:

1#include <array>
2#include <atomic>
3#include <cstddef>
4#include <optional>
5
6template <typename T, std::size_t Capacity>
7class SpscQueue {
8public:
9    bool push(const T& value) {
10        auto tail = tail_.load(std::memory_order_relaxed);
11        auto next = (tail + 1) % Capacity;
12
13        if (next == head_.load(std::memory_order_acquire)) {
14            return false;
15        }
16
17        buffer_[tail] = value;
18        tail_.store(next, std::memory_order_release);
19        return true;
20    }
21
22    std::optional<T> pop() {
23        auto head = head_.load(std::memory_order_relaxed);
24
25        if (head == tail_.load(std::memory_order_acquire)) {
26            return std::nullopt;
27        }
28
29        T value = buffer_[head];
30        head_.store((head + 1) % Capacity, std::memory_order_release);
31        return value;
32    }
33
34private:
35    std::array<T, Capacity> buffer_{};
36    std::atomic<std::size_t> head_{0};
37    std::atomic<std::size_t> tail_{0};
38};

Assuming bounded atomic operations and fixed capacity, push and pop do a constant amount of work with no compare-and-swap retry loop. That is why SPSC queues are often described as wait-free.

Why MPMC Usually Drops to Lock-Free

In an MPMC queue, multiple producers may race to claim the same slot and multiple consumers may race to remove the same element. The implementation normally needs compare-and-swap loops or sequence counters to avoid corruption.

That makes a strong difference in progress guarantees. A thread can be delayed indefinitely by repeated contention, even though the queue as a whole still moves forward. This is lock-free behavior, not wait-free behavior.

A sketch of a claim loop looks like this:

1std::size_t pos = tail.load(std::memory_order_relaxed);
2while (!tail.compare_exchange_weak(
3    pos,
4    pos + 1,
5    std::memory_order_acq_rel,
6    std::memory_order_relaxed)) {
7}

The loop is still non-blocking because no mutex is held, but one unlucky thread may spin many times while another succeeds. That violates the per-thread completion guarantee required for wait-freedom.

Circular Buffers Also Need Slot State

A ring buffer is not just head and tail math. In a contended queue, wraparound means slot reuse, so each slot must have some notion of generation or state. Otherwise a consumer can mistake old data for new data after indices wrap.

Practical MPMC ring buffers often use:

• per-slot sequence numbers
• ticket-based ownership
• separate reservation and commit phases

That is why a correct MPMC queue is much more complex than an SPSC example lifted from a textbook.

Choosing the Right Guarantee

If your workload is audio streaming, telemetry ingestion, or one-thread-to-one-thread handoff, SPSC is often ideal. It is fast, cache-friendly, and easier to prove correct.

If you truly need many producers and consumers, accept that lock-free may be the right engineering target. Lock-free can still deliver excellent throughput and avoid deadlock, but it does not promise fairness or bounded latency for every thread.

Wait-free designs exist for more complex cases, but they are usually harder to implement, harder to verify, and sometimes slower in practice because the extra bookkeeping is expensive.

Common Pitfalls

The first mistake is calling a queue "lock-free" just because it does not use std::mutex. A busy-spin algorithm can still be incorrect or only obstruction-free.

Another mistake is ignoring memory ordering. A queue may appear correct on one machine and fail on another if writes to the buffer are not properly ordered before publication of the tail index.

Wraparound bugs are also common. If full and empty states are distinguished only by head == tail, capacity handling must leave one slot unused or track additional state.

Finally, many articles generalize from SPSC to MPMC too casually. An SPSC ring buffer is not evidence that the same design remains wait-free under contention.

Summary

• A circular buffer can have different progress guarantees depending on the concurrency model.
• SPSC queues are often wait-free because each side owns one index.
• MPMC queues usually rely on retry loops and are typically lock-free, not wait-free.
• Correct ring buffers need memory-ordering discipline and careful slot reuse handling.
• "No locks" is not the same thing as a strong progress guarantee.