Circular buffer

From Wikipedia, the free encyclopedia

A circular buffer is a method of using memory within a computer program.

While the term "circular" is figurative, it alludes to the rotation through the buffer of the positions where the next data will be read and written. When moving through the buffer, the writer moves forward one step each time it writes, and when it passes the end of the buffer it starts again at the beginning. The reader moves through the buffer in the same way. As long as the reader is as fast as or faster than the writer (which is usually the case), the buffer acts as a queue of the next data to be processed. If the writer is faster than the reader, the buffer can fill up.

The term ring buffer is also often used to describe a circular buffer; this term is somewhat more common in multimedia development and informal discussion.

1 Implementation
2 Alternative approach
3 Typical Applications
- 3.1 Multimedia
4 See also
5 External links

[edit] Implementation

A circular buffer requires storage space for the data of whatever size is desired and feasible, pointers to the current locations for reading and writing, and a method for determining when the buffer is empty or full. The processes of writing and reading also need to know how big the buffer is.

[edit] Buffer Space

The data storage for the buffer must be able to hold at least one unit of data, and should (if possible) be large enough to hold as much data as the data source will produce while the user of the data is either working with the data or is otherwise not reading it.

The units of data in the buffer can be anything, but are most often the smallest unit of data that the system can process efficiently.

[edit] Read and Write Pointers

The two pointers indicate where in memory the next data should be read or written. Each time data is read, the read pointer moves forward, going back to the beginning after reading the last thing in the buffer. Each time data is written, the write pointer moves forward, going back to the beginning after writing to the last position in the buffer. Depending on how the implementation handles writing to a full buffer, the writing process may also need to move the read pointer to make room for more incoming data.

[edit] Empty and Full Buffers

If the read and write pointers point to the same spot in the buffer, that might mean that there is no data in the buffer (nothing has yet been written to the spot we next want to read from) or that the buffer is full (the next place we want to write already has in it data we have not yet read). There are two ways to make the distinction.

Do not allow the write pointer to catch up to the read pointer. Consider the buffer full when there is only one element between the write pointer and the read pointer. This results in at least one element always being "wasted", but is computationally fast.
Maintain a separate indication of whether there is data in the buffer. This can be the number of elements in the buffer, or a simple flag that is set to "Yes" each time data is written and "No" when the read pointer catches up to the write pointer.

[edit] How to Write to a Full Buffer

If the data source produces more data than can fit in the buffer, there are four choices:

If possible, tell the data source to wait until there is room in the buffer.
If the latest data is the most important, write over the oldest data that has not been read, and move the read pointer to the position of the oldest remaining data.
If the oldest data is the most important, ignore new data from the source until there is room again in the buffer.
Grow the buffer so it can handle more elements. This involves allocating a new buffer, copying the data and releasing the old buffer.

[edit] How Full is the Buffer

If the implementation maintains a count of the number of elements in the buffer, that count can be checked at any time the information is necessary. Otherwise, the difference between the write pointer and the read pointer can provide that information. Assuming that the position of both pointers can be expressed as numbers and each element in the buffer increases the pointer's position by 1, the amount of data waiting in the buffer is given by

$(w+n-r)\mod n$ ,

where

w represents the position of the write pointer;
r represents the position of the read pointer;
n is the size of the buffer.

(If n is a power of 2, the calculation can be simplified to a bit-wise AND of $(w - r)$ with $(n - 1)$ .)

If the result is zero, the process may need to check the indicator to see whether the buffer is empty or full.

[edit] Sharing the Buffer

The processes that read and write the data do not need to be able to communicate outside the buffer itself as long as there is an agreed method for losing data that does not fit in the buffer and the pointers to the reading and writing positions cannot be changed by both processes at exactly the same time

[edit] Alternative approach

If the size of circular buffer is a power of 2 (..., 32, 64, 128, ..., 4096, 8192, ...) The implementation can use one pointer to the beginning of buffer and 2 free-running index variables. The address of first and last positions on the buffer are calculated by masking out of the high-order bits in these variables. Now the emptiness of the buffer is known when (last - first) == 0 and the buffer is full when (last - first) == (buffer_size - 1). This also simplifies some other operations on the ring buffer. Linux kernel (2.6.10-), Solaris and Xen have this kind of ring buffer in use.

[edit] Typical Applications

[edit] Multimedia

In multimedia applications, circular buffers are often used to decouple a fixed-rate output stage from a variable-rate input stage. For example, consider a streaming receiver whose purpose is to receive audio data over a network connection, and then pass it on to a DAC connected to a speaker. In such an application, the sampling rate of the DAC will be fixed (or as close to fixed as possible); the consumption rate of the data will be close to constant. The primary limitation of the output device is likely to be a device driver that requires blocks of a particular minimum, or perhaps a fixed, size (such as for DMA applications). However, in many such schemes, the audio source is a "push-type" source-- our application cannot request blocks of audio data at any particular rate, it can only request the live stream, then accept blocks as they are sent to it. Further, network dynamics will have a large impact on the size of the blocks and the frequency of delivery; in particular, the supply rate will vary as available bandwidth between the source and the receiver fluctuates.

A modern approach to this problem is to use a circular buffer and two threads: one thread reads data as it becomes available, another thread wakes up as the output driver indicates the need for another block of data (or polls and delivers another block when a need is detected).

Note that this technique can also be used when connecting an ADC directly to a DAC (line in to line out, as for DSP effects); some buffering is required because the clocks for the DAC and ADC will gradually drift relative to each other.