Producer-consumer algorithm to use full buffer

Question

I was reading Galvin OS book about producer consumer problem and came through this piece of code.

Global definitions

#define BUFFER_SIZE 10
typedef struct {
    . . .
} item;

int in  = 0;
int out = 0;

Producer

while (((in + 1) % BUFFER_SIZE) == out)
    ; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE ;

Consumer

while (in == out)
    ; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;

Now this is what Galvin book says:

This scheme allows at most BUFFER_SIZE − 1 items in the buffer at the same time. We leave it as an exercise for you to provide a solution in which BUFFER_SIZE items can be in the buffer at the same time.

This is what I came up with. Is this correct?

Producer

buffer[in] = next_produced;  //JUST MOVED THIS LINE!
while (((in + 1) % BUFFER_SIZE ) == out)
    ; /* do nothing */
in = (in + 1) % BUFFER_SIZE;

Consumer

while (in == out)
    ; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;

I think this solves, but is this correct? Any other better solution possible?

Answer 1

In the original piece of code, when in == out it could mean the buffer is empty OR full. So to avoid such an ambiguity, the original code do not allow buffer to full, always leaving at least one empty item.

I am not sure you are solving this problem with your change: you will be able to put BUFFER_SIZE items, but you will not be able to consume them. So, literally you solved it, but it will not function properly.

Basically, to solve this problem, you should have an extra piece of information, so you can distinct between an empty buffer and full. There are a variety solutions for that, the most obvious is to add an extra flag.

The most elegant IMO is to use in and out counters as is, wrapping them only to access the buffer, so:

• when in == out -- the buffer is empty
• when abs(in - out) == BUFFER_SIZE -- the buffer is full
• to access the buffer we should use buffer[in % BUFFER_SIZE] or buffer[out % BUFFER_SIZE]

We leave it as an exercise for you to provide a complete solution ;)