Prompt and context
Implement a fixed-capacity queue with one writer and one reader. push fails when full and pop fails when empty. The interviewer wants you to exploit the SPSC constraint, then explain indexes, visibility, reclamation, and boundary tests instead of copying a multi-producer queue.
What the interviewer is testing
The core is concurrency invariants and trade-offs. The producer must write only its tail and the consumer only its head; each reads the other index and uses atomics to establish “write the data, then publish the index” happens-before. cppreference documents the synchronization relationship between a release store and an acquire load; Java VarHandle similarly distinguishes acquire, release, and volatile access modes.
Clarifying questions to ask first
Clarify whether elements are copied or moved, whether overwriting old data is allowed, whether capacity is chosen at runtime, whether blocking APIs are required, whether there is exactly one producer and consumer, and how destruction or exceptions are handled. If the constraint becomes MPSC or MPMC, this algorithm cannot be reused unchanged.
A 30-second answer framework
Say: “I maintain monotonically increasing head and tail counters and map them to slots with modulo. The producer reads its local tail and the consumer’s published head, checks space, writes the slot, then release-publishes the new tail. The consumer acquire-loads tail, checks non-empty, moves the element, then release-publishes the new head. Modulo handles non-power-of-two capacities; tests cover wraparound, full/empty boundaries, and visibility.”
Step-by-step deep analysis
1. State the invariants
Use tail - head as the number of occupied entries, assuming sufficiently wide unsigned counters with natural wraparound. The producer must never let the difference exceed capacity; the consumer must never read outside head != tail. Each slot is written by the producer once before it is consumed.
2. Separate local and shared indexes
The producer frequently updates tail, and the consumer frequently updates head; each can keep its own index in a normal local variable. Reading the other index across threads uses acquire, while publishing your own new index uses release, avoiding a write race on the same counter.
3. Publish in the push order
The producer loads the consumer’s head and checks tail - head < capacity. It writes buffer[tail % capacity], then release-stores the new tail. The consumer may read that slot only after an acquire load observes the new tail.
4. Reclaim in the pop order
The consumer loads the producer’s published tail and checks head != tail. After moving the slot value, it release-stores the new head. The producer may reuse that slot only after an acquire load observes the new head.
5. Handle capacity and wraparound
A power-of-two capacity can use a bit mask, but the implementation must state its overflow and width assumptions. For an ordinary capacity, % capacity is easier to verify. For long-running counters, use a wide unsigned type and compare differences rather than truncating indexes into a small integer.
6. Define failure, lifetime, and tests
Return false when full and empty when empty; do not spin. If writing an element fails, do not publish tail; moving or destroying an element requires an explicit type constraint or recovery rule. Test capacity one, capacity plus one, repeated wraparound, mismatched producer and consumer speeds, full/empty edges, and remaining elements at shutdown.
High-quality sample answer
push(x):
t = tail.load(relaxed)
h = head.load(acquire)
if t - h == capacity: return false
buffer[t % capacity] = x
tail.store(t + 1, release)
return true
pop():
h = head.load(relaxed)
t = tail.load(acquire)
if h == t: return empty
x = move(buffer[h % capacity])
head.store(h + 1, release)
return xhead and tail are atomic counters; the producer writes only tail, and the consumer writes only head. The ordinary buffer write happens before the release publication of tail, so the consumer’s acquire load makes the element visible. The reverse release of head lets the producer safely reuse the slot. Use modulo for a non-power-of-two capacity and a mask only with the extra power-of-two and overflow assumptions. This version is SPSC, not a general multi-writer or multi-reader queue.
Common mistakes and improvements
- Both threads write one index: State SPSC ownership and switch to a dedicated MPSC/MPMC algorithm when the constraint changes.
- Publishing before writing the element: Write the slot first and release-publish the index last.
- Using relaxed everywhere: Relaxed gives atomicity, not publication of ordinary data; cross-thread indexes need acquire/release.
- Assuming every capacity is a power of two: Use modulo for ordinary capacities instead of an unverified mask.
Follow-up questions and responses
Why can local index reads use relaxed?
The producer modifies only its tail and the consumer only its head, so local reads do not synchronize with the other thread. Reading the other index still needs acquire because it also provides visibility.
When can a reference-valued slot be reused?
Only after the consumer finishes moving or destroying the value and release-publishes the new head. The producer acquire-loads that value before overwriting the slot; seeing the consumer begin is not enough.
How would you extend it to multiple producers?
Multiple producers cannot write the same tail directly. You need CAS-based sequence reservation, per-slot sequence numbers, or a lock, and must re-prove reservation, publication, and reclamation order. Do not present the SPSC code as a general queue.
How do you know the optimization is faster?
Compare throughput, p99 latency, context switches, and cache misses under equal element size, thread affinity, batch size, and load. If the producer frequently catches the consumer, capacity, batching, or backpressure may matter more than weakening memory ordering.