Implement SPSC Lock-Free Queue (Single Producer Single Consumer)

Single Producer, Single Consumer Rings

When only one thread produces and one consumes, a ring buffer with atomic head and tail needs no CAS on both sides. Linux kfifo, Disruptor, and game engine job queues use this pattern for millions of events per second.

Cache-Friendly Ring Layout

Producer writes slot at tail % cap, then publishes tail. Consumer reads at head % cap, then publishes head. Power-of-two capacity makes modulo a bitmask.

cCopy
Loading…

• Leave one empty slot to distinguish full vs empty
• False sharing if head and tail share a cache line; pad them
• Batch dequeue amortizes atomic stores
• Wait-free on the hot path when roles are fixed

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement an SPSC ring buffer with release/acquire ordering. This exercise asks you to pass a stress test with one producer and one consumer thread.