Loading page…
Master the fundamental concepts of lock-free & wait-free programming through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksWhen 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.
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.
cLoading…
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.
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.
A single-producer, single-consumer ring buffer needs no CAS at all. The producer only writes tail, the consumer only writes head, and each reads the other's index to check for space. Correctness depends on order: the producer must write the slot before publishing the new tail (a release store), and the consumer must read the slot only after seeing that tail (an acquire load). Simulate the queue step by step, including wrap-around, full and empty, and the stale reads that appear when the producer publishes too early.
cLoading…
head and tail are unbounded counters. A slot is index & (C - 1), and the buffer starts full of zeros.
| Side | Step 0 | Step 1 | Step 2 |
|---|---|---|---|
| push V | read head. If tail - head == C, full: the push fails and is done. Remember slot = tail | write buf[slot] = V | tail = tail + 1 |
| pop | read tail. If head == tail, empty, done | v = buf[head] | head = head + 1 |
In broken order, the producer's steps 1 and 2 are swapped. A pop's value is correct only if it equals the next value the producer has finished pushing (in push order). Otherwise it is a stale read.
cLoading…
A stale read when some finished value was expected says (expected the next pushed value). order prints producer order: write slot, then publish tail or producer order: publish tail BEFORE writing the slot (missing release). Other messages: P: finished / C: finished, schedule: use P or C, and capacity: power of two, 1..64.
Input:
cLoading…
Output:
cLoading…
tail - head == C, and no slot has to be wasted.Hidden tests cover wrap-around over several laps, a capacity of 1, a full queue that frees up, the broken order where the consumer is lucky (it reads after the write), the broken order with a stale read of an old value, and invalid capacities.