2.2. Data Transfer and Flow Control

The last section just scratched the surface on the ring buffer and gave a functional overview of how to use it. In this section, we will discuss how it works in a bit more detail in hopes to remove some of its mystery. In what follows, we'll describe a single producer, single consumer ring buffer first and then generalize to a single producer multi-consumer ring buffer.

Suppose we have a chunk of memory which is shareable between processes and within which we are going to use modulo addressing. Using modulo addressing means that if we have a pointer sequentially accessing this memory, when the pointer would run off the end of this memory region instead it returns to the beginning.

You can therefore think of this memory as an 'endless' ring of addresses. A ring buffer.

For a ring buffer to be useful as a mechanism for exchanging data we need a bit more information. Specifically, we need a put pointer and a get pointer. As we will see we also need some concept of flow control.

Here's how this all works. Define the ring buffer as being empty if the put and get pointers are equal. Define the ring buffer as full if advancing the put pointer one storage unit would make it equal to the get pointer (we don't want an ambiguity between full and empty ring buffers). A producer will ensure it has space in the ring buffer for whatever data it wants to put by calculating the modulo distance between the put and get pointers. When space becomes available (producers wait if necessary for space), data are transferred to the ring buffer starting at the location indicated by the put pointer (using modulo addressing again). When the data are transferred, the put pointer is advanced to point to the location just following the message.

Similarly, a consumer that wants to get data from the ring ensures there is enough data to get by waiting until the distance between the put and get pointers is at least the size of the data transfer it wants to perform. Once there is sufficient data in the ring buffer it transfers the data out of the ring and, when the data have been read, updates the get pointer so that it points to the next unread unit of memory.

This business of the produceer waiting for space to be available and the consumer waiting for data to be available is called flow control.

In a data acquisition system, we usually want to have several consumers. This can be accomodated by having more than one get pointer. This slightly complicates the flow control logic of the producer. Now the producer must consider the free space to be the minimum distance between the the put pointer and all of the get pointers.

The result of this is that ring buffers are a very low overhead mechanism to transfer data between processes in a single shared memory computer system. Messages can be atomically put without any requirement to negotiate locks. Furthermore, since data are in shared memory, it's not necessary to transfer buffers to kernel space and then back out to application space. For more information about ring buffers see http://en.wikipedia.org/wiki/Circular_buffer

Finally, the data transferred through the ring buffer is just a stream of bytes, in practice and in the NSCL Ring buffer Data Acquisition system, we send messages that have structure. The messages have a structure defined later in Chapter 3.