Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Design

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).


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.