Circular Buffer – Part I

A circular buffer is an object used to ‘buffer’ data between Producer and Consumer. If the consumer is faster than the consumer, perhaps an intermediate object like a circular buffer would not be needed. If such condition cannot be guaranteed, then a circular buffer might be what the doctor ordered.

When I decided to write about this subject, I quickly went and designed and implemented a complete solution in C. Last night I decided that was not a good idea. Instead let’s start very simple with the basics and gradually increase the complexity of the solution as requirements evolve. I believe that is one of the main ideas for Agile. If you are an experienced software developer then you would immediately see the need for additional functionality in the initial implementation. In addition, depending on what the requirements are, several additional features might be required. I am not planning on spending a few days on this topic so I will try to get multiple implementations to some degree of functionality.

In practice I have used circular buffers in several projects. Most of them ran under real-time operating systems. They were used for keyboard input, serial, parallel and Ethernet ports. I have also implemented circular buffers in other operating systems.

So why would you need a circular buffer? The basic idea is to buffer data between a producer and a consumer. This is illustrated in the following diagram:

The idea behind the buffer (in this case a circular buffer) is to allow the producer and consumer to execute at their own pace. If there is an impedance mismatch between them, one would have to slow down to match the rate of the other. For example, if the producer is a user typing on the keyboard of a computer and the consumer is an application that needs to perform a set of time consuming operations, the user may type ahead and the keystrokes would not be lost. Most users type a few words in a sentence and then momentarily stop to think about the next one. That allows for the consumer to process and display the contents of the buffer and then wait for additional input from the user. A different example might be sending and receiving data over a serial or parallel interface. Yet another example might be sending and receiving data over a network connection.

I always like to start by generating a test for the software. The implementation of the circular buffer can then be started. During testing the initial behavior may be corrected, additional feature may be needed and in some cases some might be removed.

Following is Java code to test the CircularBuffer class to be developed using the Eclipse IDE:

package john.circular.buffer;

import java.util.Random;

public class Solution {

/**

* Test code.

* @param args

*/

public static void main(String[] args) {

// **** ****

final int TOTAL_ITERATIONS = 10;

final int TURNS = 3;

final int MAX_VALUE = 100;

// **** initialize a (pseudo) random number generator ****

Random rand = new Random(System.currentTimeMillis());

// **** ****

int val;

// **** instantiate a circular buffer ****

CircularBuffer cb = new CircularBuffer();

// **** loop putting and getting data from the circular buffer ****

for (int i = 0; i < TOTAL_ITERATIONS; i++) {

// **** decide who runs ****

int t = rand.nextInt(TURNS);

// **** producer ****

if ((t % TURNS) != 0) {

val = 1 + rand.nextInt(MAX_VALUE);

System.out.println(“<<< put val: ” + val);

cb.Put(val);

}

// **** consumer ****

else {

val = cb.Get();

System.out.println(“<<< get val: ” + val);

}

}

}

}

The test code instantiates the circular buffer to be tested. It then loops a few times performing one operation on the circular buffer per pass. In this case the random value in t will favor the producer because rand() % 3 produces 0, 1, 2. We could switch the “! =” to “==” in order to switch frequencies.

Following is a screen capture after a simple shell of the CircularBuffer class has been created:

<<< put val: 14

<<< put val: 35

<<< put val: 15

<<< get val: 0

<<< put val: 1

<<< put val: 59

<<< get val: 0

<<< get val: 0

<<< put val: 40

<<< put val: 32

<<< get val: 0

<<< put val: 45

<<< put val: 75

As expected, there is more Producer than Consumer operations.

Following is the shell code for the CircularBuffer class:

package john.circular.buffer;

public class CircularBuffer {

// **** ****

public final int BUFFER_SIZE = 8;

// **** members ****

private int[] arr;

int head;

int tail;

// **** constructor ****

public CircularBuffer() {

}

// **** methods ****

public void Put(int val) {

}

public int Get() {

return 0;

}

}

For the CircularBuffer class we envision an array of integers of some size (e.g., 8) to be used to hold the values generated by the producer. To keep track we will use the head index. To pull values we will use the tail index. We need to define a relationship between them to make sure we are able to determine when the buffer is full and when is empty.

Let’s take the updated class for a run:

<<< put val: 95

<<< get val: 95

<<< put val: 88

<<< put val: 88

<<< put val: 11

<<< get val: 88

<<< put val: 77

<<< put val: 100

<<< put val: 47

<<< put val: 100

<<< put val: 90

<<< get val: 47

<<< get val: 100

<<< put val: 55

<<< put val: 96

<<< put val: 1

<<< put val: 91

<<< put val: 51

<<< get val: 91

<<< put val: 45

Obviously something is not implemented yet. We are putting (overriding) values and not checking if the buffer is full. We need to check if the buffer is full. We probably need to check if the buffer is empty. We could delay that implementation for later but let’s get it done now.

Let’s try again:

<<< put val: 7

<<< put val: 75

<<< put val: 17

<<< put val: 10

<<< EXCEPTION buffer full

<<< put val: 39

<<< EXCEPTION buffer full

<<< put val: 24

<<< EXCEPTION buffer full

<<< get val: 7

<<< get val: 75

<<< get val: 17

<<< EXCEPTION buffer empty

<<< EXCEPTION buffer empty

<<< put val: 13

<<< put val: 34

<<< get val: 13

<<< put val: 94

<<< put val: 11

<<< put val: 75

<<< EXCEPTION buffer full

<<< put val: 33

<<< EXCEPTION buffer full

<<< put val: 41

<<< EXCEPTION buffer full

<<< put val: 55

<<< EXCEPTION buffer full

The updated code for the test software follows:

package john.circular.buffer;

import java.util.Random;

public class Solution {

/**

* Test code.

*/

public static void main(String[] args) {

// **** ****

final int TOTAL_ITERATIONS = 20;

final int TURNS = 3;

final int MAX_VALUE = 100;

// **** initialize a (pseudo) random number generator ****

Random rand = new Random(System.currentTimeMillis());

// **** ****

int val;

// **** instantiate a circular buffer ****

CircularBuffer cb = new CircularBuffer();

// **** loop putting and getting data from the circular buffer ****

for (int i = 0; i < TOTAL_ITERATIONS; i++) {

// **** decide who runs ****

int t = rand.nextInt(TURNS);

// **** producer ****

if ((t % TURNS) != 0) {

val = 1 + rand.nextInt(MAX_VALUE);

System.out.println(“<<< put val: ” + val);

try {

cb.Put(val);

} catch (Exception ex) {

System.out.println(“<<< ” + ex.getMessage());

}

}

// **** consumer ****

else {

try {

val = cb.Get();

System.out.println(“<<< get val: ” + val);

} catch (Exception ex) {

System.out.println(“<<< ” + ex.getMessage());

}

}

}

}

}

A run for an active (if ((t % TURNS) != 0)) Producer follows:

<<< put val: 84

<<< get val: 84

<<< EXCEPTION buffer empty

<<< put val: 75

<<< put val: 84

<<< put val: 9

<<< get val: 75

<<< put val: 88

<<< put val: 11

<<< EXCEPTION buffer full

<<< get val: 84

<<< put val: 6

<<< put val: 19

<<< EXCEPTION buffer full

<<< put val: 34

<<< EXCEPTION buffer full

<<< put val: 43

<<< EXCEPTION buffer full

<<< put val: 77

<<< EXCEPTION buffer full

<<< get val: 9

<<< get val: 88

<<< put val: 47

<<< put val: 89

<<< put val: 25

<<< EXCEPTION buffer full

A run for an active (if ((t % TURNS) == 0)) Consumer follows:

<<< put val: 74

<<< get val: 74

<<< EXCEPTION buffer empty

<<< EXCEPTION buffer empty

<<< put val: 34

<<< put val: 85

<<< get val: 34

<<< get val: 85

<<< EXCEPTION buffer empty

<<< EXCEPTION buffer empty

<<< EXCEPTION buffer empty

<<< put val: 52

<<< put val: 47

<<< get val: 52

<<< put val: 30

<<< get val: 47

<<< put val: 45

<<< put val: 91

<<< get val: 30

<<< get val: 45

The final (for now ;o) code for the CircularBuffer class follows:

package john.circular.buffer;

public class CircularBuffer {

// **** ****

public final int BUFFER_SIZE = 4;

// **** members ****

private int[] arr;

private int head;

private int tail;

// **** constructor ****

public CircularBuffer() {

this.arr  = new int[BUFFER_SIZE];

this.head = 0;

this.tail = 0;

}

// **** methods ****

public void Put(int val) throws Exception {

// **** check if the buffer is full ****

if (IsFull()) {

throw new Exception(“EXCEPTION buffer full”);

}

// **** increment the head ****

this.head++;

if (this.head >= BUFFER_SIZE) {

this.head = 0;

}

// *** insert the element into the array ****

this.arr[this.head] = val;

}

public int Get() throws Exception {

// **** check if the buffer is not empty ****

if (IsEmpty()) {

throw new Exception(“EXCEPTION buffer empty”);

}

// **** increment the tail ****

this.tail++;

if (this.tail >= BUFFER_SIZE) {

this.tail = 0;

}

// **** remove the element from the array ****

int val = this.arr[this.tail];

this.arr[this.tail] = 0;

return val;

}

public Boolean IsEmpty() {

return (this.head == this.tail);

}

public Boolean IsFull() {

if (tail == 0) {

if (head >= (BUFFER_SIZE – 1)) {

return true;

} else {

return false;

}

} else {

if ((head + 1) == tail) {

return true;

} else {

return false;

}

}

}

}

All works so far because the producer and consumer are synchronized (run of the same main()). If they would be running on separate threads or there are multiple Producers and Consumers things would turn chaotic.

Also note that the returned values are cleared from the buffer. For security and / or privacy reasons, is not a good idea to leave stale data in the circular buffer.

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. I will not disclose your name unless you allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.