Q199FreeComputer Architecture
Build a bounded one-producer, one-consumer queue
Interview prompt
Question
Implement a fixed-capacity queue for one producer thread and one consumer thread. try_push returns false when full, and try_pop returns false when empty. Do not use a mutex or overwrite unread data. For this exercise Capacity is a positive power of two no larger than 2^63, and the target provides lock-free 64-bit atomics.
Candidate starting point
Implementation scaffold
#include <array>
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <limits>
template <std::size_t Capacity>
class SpscQueue {
static_assert(std::atomic<std::uint64_t>::is_always_lock_free,
"Target must provide lock-free 64-bit atomics");
static_assert(Capacity > 0, "Capacity must be positive");
static_assert((Capacity & (Capacity - 1)) == 0,
"Capacity must be a power of two");
static_assert(Capacity <= (std::uint64_t{1} << 63),
"Capacity must not exceed half the sequence space");
static constexpr std::size_t slot(std::uint64_t sequence) noexcept {
return static_cast<std::size_t>(sequence) & (Capacity - 1);
}
public:
bool try_push(std::uint64_t value) {
const std::uint64_t tail = tail_.load(std::memory_order_relaxed);
const std::uint64_t head = head_.load(std::memory_order_acquire);
// Implement here: apply the full/empty test and publish the slot/index with the required ordering.
}
bool try_pop(std::uint64_t& value) {
const std::uint64_t head = head_.load(std::memory_order_relaxed);
const std::uint64_t tail = tail_.load(std::memory_order_acquire);
// Implement here: apply the full/empty test and publish the slot/index with the required ordering.
}
private:
std::array<std::uint64_t, Capacity> slots_{};
alignas(64) std::atomic<std::uint64_t> head_{0};
alignas(64) std::atomic<std::uint64_t> tail_{0};
};
// Implement here: explain full, empty, modulo wrap and the acquire/release publication choices.
Reviewed example
Trace one case
Input
Capacity=2; push(10), push(20), push(30), pop(x), push(30), pop(x), pop(x)Expected output
true, true, false, x=10, true, x=20, x=30The third push cannot overwrite unread value 10; after one pop releases that slot, value 30 can reuse it safely.
What to cover
Requirements
- Support exactly one producer and one consumer.
- Use fixed storage and atomic indices without a lock or allocation after construction.
- Publish a slot only after its value is written and free it only after its value is read.
- Explain full, empty, wraparound, and the memory-order choices.