The Ring Buffer

A producer may generate events faster than a consumer can process them. An unbounded queue handles the difference by increasing memory usage.

A ring buffer uses a fixed allocation and requires an explicit policy for handling a full queue.

A ring buffer is an ordinary array with a tail for the next write and a head for the next read. Both begin at slot 0.

That is the whole representation: one allocation and two integers. Elements stay together in memory, with no linked nodes or per-item bookkeeping.

To push an item, write it to the slot at the tail index and then increment the tail.

The operation does not shift existing elements or allocate memory. It runs in O(1) time and is suitable for latency-sensitive code such as interrupt handlers.

To pop an item, read the slot at the head index and then increment the head. The range between the head and tail represents the current queue contents.

A popped slot does not need to be physically cleared. Its value remains in memory until a later push overwrites it, while the indices determine whether the slot is logically occupied.

After an index reaches the final slot, its next position is slot 0: next = (i + 1) % capacity.

The array remains contiguous in memory, while modulo arithmetic treats its endpoints as adjacent. Freed slots can therefore be reused without resizing the array.

If wrapped head and tail indices are equal, the buffer may be either empty or full. Additional state is required to distinguish the two cases.

Common approaches store an explicit item count, reserve one unused slot, or use monotonically increasing indices and apply modulo only during array access. In the last approach, tail − head gives the item count.

A full buffer may overwrite its oldest entry instead of blocking or rejecting a push. In this mode, the new item replaces the item at the head and both indices advance.

The buffer then retains the most recent N events. This policy is common in flight recorders, kernel logs, and diagnostic traces.

When capacity is a power of two, modulo can be replaced with a bit mask: (i + 1) & (capacity − 1).

This reduces index wrapping to a bitwise operation and allows monotonically increasing unsigned indices to wrap correctly across integer overflow.

With one producer and one consumer, the ring buffer has a property most queues lack: each index has exactly one writer. The producer alone moves the tail; the consumer alone moves the head. Neither thread ever writes to the other's index.

That ownership split makes the single-producer single-consumer queue lock-free with only memory-ordering fences: the producer writes the element first and publishes the new tail second, so the consumer can never observe an index that points at unwritten data. This is the queue inside audio callbacks and network drivers, where taking a mutex is not an option.

When a fixed-capacity buffer fills, the producer must block, drop the new item, or overwrite an old item. Capacity should account for expected workload bursts.

A bounded queue can provide backpressure instead of increasing memory use. Operations remain O(1), with no allocation after initialization.

Linux uses rings for its kernel log and exposes kfifo as a reusable primitive. io_uring shares submission and completion rings between user space and the kernel. Network cards use descriptor rings to hand packets to drivers running at a different pace.

Audio pipelines use single-producer, single-consumer rings between real-time and ordinary threads. The LMAX Disruptor applies the same shape to trading, while Rust’s VecDeque turns it into a growable deque.

A ring buffer uses head and tail indices to reuse a fixed array. Push and pop operations run in constant time without shifting elements.

Its fixed capacity makes memory use predictable and requires the application to define how overload is handled.