Circular Buffer Problem

A classic problem in operating system is to handle the producer and consumer scenario. Producer will keep producing new data and consumer will consume that data. To do so say the producer and consumer process share the same memory. Lets say the size of that memory shared is fixed or bounded. Can you implement a logic to produce a data to that buffer when space is available. Similarly consumer can read only when data is available and the buffer is not empty.

This can be achieved by a circular bounded buffer shared between the producer and consumer.

/* the size of the bounded shared buffer */
#define BUFFER_SIZE 10

/* Each elements of the buffer */
typedef struct element {
	int i;//some data is present

/* The shared buffer, each index is of the type element */
element data_buffer[BUFFER_SIZE];

Let us come with the logic

Other than sharing the data_buffer, the producer and consumer must share the index where to produce data and from where to consume it.

Let’s define that

/* Add element in position "in" and move to next */
int in = 0; 

/* remove element from position "out" and move to next */
int out = 0;

Now how to know when the buffer is FULL so any element can’t be added. Similarly how to know when buffer is empty when element can be read or consumed. Let’s define the rules

/* if in == out, buffer is empty */

/* if (in + 1)%BUFFER_SIZE == out buffer is full */

Okay now lets write the pseudo code of the producer

/* producer */

while(TRUE) {

        /* keep waiting as buffer is full*/
	while((in + 1)%BUFFER_SIZE == out);
	data_buffer[in] = data_produced;
	in = (in+1)%BUFFER_SIZE;


The consumer pseudo code

/* consumer */

while(TRUE) {

        /* keep waiting as buffer is empty, nothing to consume */
	while(in == out);
	data_consumed = data_buffer[out];
	out = (out + 1)%BUFFER_SIZE;


I hope the above logic is self explanatory. I have a question for you, how many elements will make the buffer full in the above logic ?

Linux Kernel Barriers

Sometimes you need to have the memory read (load) and write operation (store) to be executed in certain order. But it may be that complier (or processor) can reorder reads and writes for performance reason.

It is possible to instruct the compiler not to reorder read or write at a given point. These instructions are called barriers.

Let us take a simple example

x = 1;
y = 2;

On some processors “y” may store new value first before “x”. That is second store instruction above gets executed before 1st store instruction.

But this reorder will never happen if the instructions are related, for example

x = 1;
y = x;

A mb() call provides both read and write barrier. No load and store will get reordered across this barrier.

Thus the below instructions will not reorder now

x = 1;
mb(); /* barrier */
y = 2;

Further Read