1. Problem It Solves
One thread produces data and another consumes it in FIFO order. A single-producer/single-consumer (SPSC) ring buffer can use fixed storage and two atomic indices; synchronization must cover both publishing an element and allowing its slot to be reused.
2. Prerequisites
std::atomic, acquire/release memory order, and happens-before: the ordering that makes earlier work safe to observe in another thread.Object lifetime, move constructors, and destructors.
Exactly one thread may push and exactly one may pop; these two roles may run concurrently.
3. Core Idea
Reserve one empty slot in an array of N slots (N > 1): head == tail means empty; next(head) == tail means full. Usable capacity is N - 1.
Only the producer changes head; only the consumer changes tail. The producer constructs an element, then release-stores head; the consumer acquire-loads head before accessing it. The consumer destroys the element, then release-stores tail; the producer acquire-loads tail before reusing the slot. Both synchronization directions protect data and lifetime; see acquire/release ordering.
4. Minimal Syntax
The publication step inside try_push is:
slots_[current].emplace(std::move(value));
head_.store(following, std::memory_order_release);It runs only after an acquire-load of tail_ establishes available space. slots_ is an array of std::optional<T>; an empty slot contains no live T.
5. How It Works
The producer reads its own index with
relaxed, computes the next index, and acquire-loads the consumer's index. It returnsfalseif full; otherwise it constructs the element before publishing the newhead.The consumer reads
tailwithrelaxedand acquire-loadshead. It returnsstd::nulloptif empty; otherwise it moves the element into the result, resets the slot, then publishes the newtail.Indices stay in
[0, N). The sample usesindex + 1 == N ? 0 : index + 1; it relies on neither signed overflow nor a power-of-twoN.The sample requires non-throwing move construction and destruction of
T. Thetry_push(T value)parameter is created before entering the body: an lvalue copy may throw, and passing an rvalue may change the source even if the queue returnsfalse.Destroy the queue only after both roles stop accessing it. Any still-engaged optionals destroy their remaining elements.
6. Common Mistakes
Publishing
headbefore constructingT, ortailbefore finishing with and destroying the element.Making all atomics
relaxed; atomic indices alone do not publish the slot data.Adding a second producer or consumer without changing the algorithm.
Calling the whole operation lock-free just because no mutex is visible. Index atomics must be lock-free on the target, and
Toperations must not lock or block.noexceptdoes not establish that.
7. When to Use It
Use this design when producer/consumer counts are fixed and a full queue has a clear policy: retry, drop, or apply backpressure. It is not directly suitable for MPSC/MPMC. Measure latency and cache contention before adding optimizations such as separating indices onto different cache lines.
8. Simple Example
The C++20 sample uses SpscRing<int, 4>: four physical slots hold at most three integers. It pushes 40 and 2, then pops them in that order.
This only demonstrates sequential behavior; it does not prove concurrent safety. Validation needs empty/full boundaries, minimum capacity, repeated wraparound, and two-thread sequence transfers that detect loss, duplication, and reordering. Use suitable sanitizers to find races or memory errors; a clean run does not replace the synchronization argument.
Complete sample code
Source file
dailycppinterview/254_bounded-lock-free-spsc-ring-buffer/main.cpp
// Real-World C++ Interviews Q254: How would you design and validate a bounded lock-free SPSC
// ring buffer, including full/empty states, object lifetime, wraparound, and acquire-release
// ordering?
// Key: With exactly one producer and one consumer, let the producer own head and the consumer
// own tail. One simple representation reserves a slot: head equal to tail means empty, while
// advancing head to tail means full, so physical size N stores at most N-1 elements. The
// producer constructs a free slot before a release-store to head; the consumer acquire-loads
// head before reading that object, destroys it, then release-stores tail so the producer's
// acquire-load can safely reuse the slot. Index arithmetic must wrap without overflow
// assumptions, and T's construction, move, and destruction contracts must be handled. Test
// capacity boundaries, many wraparounds, long stress runs, and sanitizer-supported misuse; also
// verify that the index atomics are lock-free on the target. The design is not MPSC or MPMC.
#include <array>
#include <atomic>
#include <cstddef>
#include <iostream>
#include <optional>
#include <type_traits>
#include <utility>
template<class T, std::size_t N>
requires (N > 1 && std::is_nothrow_move_constructible_v<T> &&
std::is_nothrow_destructible_v<T>)
class SpscRing {
public:
static constexpr std::size_t capacity = N - 1;
static constexpr bool always_lock_free =
std::atomic<std::size_t>::is_always_lock_free;
bool try_push(T value) noexcept {
const std::size_t current = head_.load(std::memory_order_relaxed);
const std::size_t following = next(current);
if (following == tail_.load(std::memory_order_acquire)) return false;
slots_[current].emplace(std::move(value));
head_.store(following, std::memory_order_release);
return true;
}
std::optional<T> try_pop() noexcept {
const std::size_t current = tail_.load(std::memory_order_relaxed);
if (current == head_.load(std::memory_order_acquire)) return std::nullopt;
std::optional<T> result{std::in_place, std::move(*slots_[current])};
slots_[current].reset();
tail_.store(next(current), std::memory_order_release);
return result;
}
private:
static constexpr std::size_t next(std::size_t index) noexcept {
return index + 1 == N ? 0 : index + 1;
}
std::array<std::optional<T>, N> slots_{};
std::atomic<std::size_t> head_{};
std::atomic<std::size_t> tail_{};
};
int main() {
SpscRing<int, 4> queue;
queue.try_push(40);
queue.try_push(2);
while (const auto value = queue.try_pop()) {
std::cout << *value << std::endl;
}
}
9. Key Takeaways
The sample's always_lock_free reports a property of the index atomics; it does not enforce target support. Assess the design using its happens-before argument, the contract of T, and testing on the target.
10. Self-Check Question
Full question: How would you design and validate a bounded lock-free SPSC ring buffer, including full/empty states, object lifetime, wraparound, and acquire-release ordering?
With N = 4, why can the queue hold only three elements? What does the release/acquire pair on tail protect? If T has a non-throwing move constructor that takes a mutex, is the entire try_push operation lock-free?