Spin Buffers

Ring Buffers

The most common way to implement the shared buffer is a Ring buffer (Listing One) with a certain size (SIZE). With Ring buffers, you maintain two pointers—one to read (m_rptr) and one to write (m_wptr). The producer inserts a new item into the buffer at m_wptr, then increments it by 1; for instance, (m_wptr+1)%size. Similarly, the consumer inserts a read from m_rptr, then increments it by 1. If the special condition m_rptr == m_wptr is True, the buffer is empty.

One thing you should avoid is letting the read pointer get ahead of the write pointer. To ensure this doesn't happen, you could maintain the current size (m_size) so that the read pointer is not incremented. In this case, m_size is 0 (buffer is empty, nothing to read) and the write pointer should not be incremented if m_size is equal to the buffer size (buffer is full, write fails).

Let's package all this into a class and provide access to methods put and get. Note that I try to have the smallest amount of synchronized code; namely, the method updateSize(). In most cases, this is okay because it is straightforward. But if you are producing a high-performance application, you need to take a closer look at the producer-consumer patterns in the applications. For example, I work on game server engines that require more than 100,000 messages be processed every second, then broadcast back to the clients.

Spin Buffers

Spin buffers contain three internal "ordered" buffers (see Figure 2), but expose a simple API similar to Ring buffers. The buffers are ordered as 0, 1, and 2. The buffer of 0 is 1, then the buffer of 1 is 2, and finally, the buffer of 2 is 0. Two pointers are maintained—one that points to a buffer that a reader reads from, and another that a writer writes to. Referring to Figure 2, at any time there can be an assigned read buffer (R), an assigned write buffer (w), and free one (f). The buffers can be implemented as fixed-sized arrays.

Figure 2: Spin buffers contain three internal "ordered" buffers.

The put method is as follows:

1. Put the item into the write buffer.
2. If the next buffer is free, make the free buffer become the write buffer, and the current write buffer becomes free.

The get method is as follows:

1. Read the item from the read buffer.
2. If the current read buffer is empty and the next buffer is free, make the next buffer the read buffer, and the current read buffer becomes free.

Listing Two is the Spin buffer implementation in Java (it should be straightforward to write it in other programming languages).