Buffering

Why buffering matters

I/O devices and the CPU operate at vastly different speeds. A programme may write a few bytes at a time (e.g., fprintf for each field of a record), but the disk or network prefers large, block-aligned transfers. Buffering smooths out the speed mismatch by accumulating small writes into larger blocks and pre-reading large blocks to satisfy small reads.

Additionally, buffering can relax the synchronisation constraints between processes: a process writing to a pipe need not wait for the reader to consume every byte; the pipe buffer absorbs the mismatch.

Single buffering

A single buffer is allocated in kernel space for the device. When a user process issues a read():

1. The kernel initiates a device read into the kernel buffer.
2. The user process blocks.
3. When the device completes, the kernel copies data from the kernel buffer to the user buffer.
4. The process is unblocked.

While the user process is processing the data, the device is idle — it cannot start the next read because the buffer is still being read from. With single buffering, the device and CPU proceed sequentially, never overlapping.

Throughput: For buffer size $B$ and transfer time $T$, the effective throughput is $\frac{B}{T + T_\text{copy} + T_\text{process}}$. Device idle time is $T_\text{copy} + T_\text{process}$.

Double buffering (ping-pong)

Two buffers alternate: while data from buffer A is being copied to user space (and processed), the device can fill buffer B with the next block. When both sides are ready, they swap roles.

Throughput: The device and CPU now overlap. Throughput approaches $\frac{B}{\max(T_\text{device}, T_\text{copy} + T_\text{process})}$. The device is idle only if the CPU+copy time exceeds the device transfer time.

This is the standard approach for block devices (disk controllers use double buffers, or scatter-gather lists which generalise the concept to multiple non-contiguous buffers).

Circular buffering

A fixed-size ring buffer with a producer (device) and consumer (user process), each advancing a pointer:

• Producer writes to buffer[in] and increments in.
• Consumer reads from buffer[out] and increments out.
• The buffer is empty when in == out.
• The buffer is full when (in + 1) % N == out (one slot is sacrificed to disambiguate full from empty).

Circular buffering provides greater elasticity than double buffering: the device and process can proceed at their natural rates as long as the average rates match, with the buffer absorbing transient bursts.

Buffering and pipes

A UNIX pipe is effectively a circular buffer maintained by the kernel (64 KB default on Linux). The write end is the producer; the read end is the consumer. When the buffer is full, write() blocks (back-pressure). When empty, read() blocks. This is exactly the producer-consumer synchronisation problem, solved by the kernel.

Tripos context (2020 Q4)

An exam question asks about buffering in I/O subsystems: the different types (single, double, circular), the throughput implications, and the trade-off between buffer memory usage and device utilisation. Key points for the mark scheme:

• Single buffering serialises device and CPU.
• Double buffering allows overlap.
• Circular buffering provides elasticity for bursty traffic.
• Larger buffers increase the elasticity but consume more kernel memory.

Summary

• Buffering bridges speed mismatches between CPU and I/O devices.
• Single buffering is simple but serialised.
• Double buffering overlaps I/O and processing.
• Circular buffering provides elasticity for variable-rate producers and consumers.
• Pipes are kernel-managed circular buffers that also provide flow control.