In this lesson:
- the producer/consumer problem a ring buffer solves
- head and tail indices wrapping a fixed array, O(1) push and pop
- the full-vs-empty ambiguity and the two ways to resolve it
- the power-of-two masking trick
- why single-producer/single-consumer ring buffers can be lock-free
A ring buffer (a.k.a. circular buffer or FIFO) is the most-used data structure in embedded firmware, own this one cold.
The problem: a producer faster than the consumer
A UART receive ISR fires on every incoming byte; your main loop processes them in bursts. You need a queue that:
- holds bytes in arrival order (FIFO, first in, first out),
- uses fixed memory (no heap),
- never moves existing data (an O(n) shift on every byte would be fatal at 1 Mbaud),
- lets the ISR write while the main loop reads.
A ring buffer is a fixed array plus two indices, head (where the producer writes next) and tail (where the consumer reads next), that wrap around to 0 when they pass the end. The array is logically a circle.
capacity 8, after writing A,B,C and reading A:
index: 0 1 2 3 4 5 6 7
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑ ↑
tail head (A already consumed; B,C pending)
(read) (write)When head reaches the end it wraps to 0 and keeps going, the data never shifts, only the indices move.
O(1) push and pop
#define CAP 8
typedef struct {
uint8_t buf[CAP];
volatile uint16_t head; // next write slot (producer)
volatile uint16_t tail; // next read slot (consumer)
} Ring;
bool ring_push(Ring *r, uint8_t b) { // producer (e.g. ISR)
uint16_t next = (r->head + 1) % CAP;
if (next == r->tail) return false; // full — drop (or overwrite)
r->buf[r->head] = b;
r->head = next; // publish AFTER writing data
return true;
}
bool ring_pop(Ring *r, uint8_t *out) { // consumer (e.g. main loop)
if (r->tail == r->head) return false; // empty
*out = r->buf[r->tail];
r->tail = (r->tail + 1) % CAP;
return true;
}Every operation is O(1): a couple of index updates and one byte move, no scanning, no shifting, regardless of how full the buffer is. Space is O(CAP), fixed at compile time.
The full-vs-empty ambiguity
Here's the classic trap. The buffer is empty when head == tail. But if you fill all CAP slots, head wraps right back to tail, so head == tail also looks full. The two states are indistinguishable. Two standard fixes:
1. Sacrifice one slot (used above). Declare "full" when advancing head would hit tail ((head+1) % CAP == tail). The buffer holds at most CAP-1 items, and head == tail now unambiguously means empty. Simple, no extra state, costs one slot.
2. Keep a count. Track count of items alongside head/tail. count == 0 is empty, count == CAP is full; you can use all CAP slots. Costs a counter that both sides modify, which reintroduces a shared variable that needs care under concurrency (see below).
Sacrifice-one-slot: Count:
full when (head+1)%CAP == tail full when count == CAP
uses CAP-1 slots uses all CAP slots
no shared counter shared counter (sync needed)For single-producer/single-consumer, the sacrifice-one-slot approach is popular precisely because it avoids a counter both sides touch.
The power-of-two trick
% (modulo) can be a slow division on MCUs without a hardware divider (e.g. Cortex-M0). If CAP is a power of two, the wrap becomes a cheap bitwise AND:
// CAP must be a power of two, e.g. 8, 16, 256
r->head = (r->head + 1) & (CAP - 1); // & 7 instead of % 8x % 8 and x & 7 are equal for non-negative x, but the AND is one cycle. This is why production ring buffers almost always use power-of-two capacities.
Lock-free for single producer + single consumer (SPSC)
The reason ring buffers are the ISR data structure: with exactly one producer and one consumer, you need no lock. The producer only writes head and reads tail; the consumer only writes tail and reads head. Neither modifies the other's index.
The one rule: publish the index after the data. Write buf[head], then advance head, so the consumer never sees an advanced head pointing at a slot that isn't filled yet. Mark head/tail volatile (recall the C module) so the compiler doesn't cache them across the ISR boundary. On multi-core or weakly-ordered CPUs you additionally need a memory barrier; on a single-core Cortex-M, volatile plus correct ordering is the common (if subtle) idiom.
If you have multiple producers or consumers, this breaks, then you need a critical section (the RAII guard from the C++ module) or atomic operations around the index updates.
Overflow policy: drop vs overwrite
When the buffer is full, you choose:
- Drop the new item (return false), used for lossless data like received commands; the producer or protocol handles backpressure.
- Overwrite the oldest (advance tail too), used for "latest wins" data like a sensor stream where stale samples are worthless.
Decide deliberately; a silent wrong choice either loses fresh data or corrupts ordering.
Gotchas
- Full/empty ambiguity.
head == tailis both, resolve with sacrifice-one-slot or a count. Forgetting this corrupts the buffer when it fills. - Publish index after data. Advance
headonly after writing the slot; otherwise the consumer can read an unwritten slot. Order matters even single-threaded against an ISR. volatileon head/tail for ISR sharing. Without it the compiler may cache an index and the consumer spins on a stale value (the polling-loop bug from the C module).- SPSC only is lock-free. Multiple producers/consumers racing on the same index need a critical section or atomics, the no-lock property is specific to one-producer/one-consumer.
- Modulo cost. Use power-of-two capacity + AND mask on divider-less cores;
% CAPcan be a costly division.
TL;DR
- A ring buffer is a fixed array with wrapping
head(write) andtail(read) indices, a FIFO with O(1) push/pop, O(CAP) fixed space, and no data shifting or heap. head == tailmeans empty and would-be full; resolve the ambiguity by sacrificing one slot or keeping a count.- Use a power-of-two capacity so wrapping is a one-cycle
& (CAP-1)instead of a% CAPdivision. - For one producer + one consumer it's lock-free: each side owns one index, just publish the index after the data and mark indices
volatile. - Choose an overflow policy deliberately: drop new items (lossless) or overwrite oldest (latest-wins).