Why are only BUFFER_SIZE-1 items allowed in buffer in Producer-Consumer paradigm using shared memory?

Question

Here is an excerpt from the book "Operating System Concepts" 7th Edition Galvin,Gagne Chapter 3 from the hard-copy itself :

---

The following variables reside in a region of memory shared by the producer and consumer processes:

#define BUFFER_SIZE 10

typedef struct {
 . . .
} item;

item buffer[ BUFFER_SIZE ];
int in = 0;
int out = 0;

The shared buffer is implemented as a circular array with two logical pointers: in and out.The variable in points to the next free position in the buffer;out points to the first full position in the buffer.The buffer is empty when in==out; the buffer is full when ((in+1)%BUFFER_SIZE)==out.

This scheme allows at most BUFFER_SIZE-1 items in the buffer at the same time.

---

I have highlighted my confusion in bold.Here's a link to an online slide of that chapter (but it has edited a few lines of the book).Go to the section "Producer-Consumer Example Using Shared Memory"

http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/3_Processes.html

Why can there be BUFFER_SIZE-1 items in the buffer? If we start from buffer[0] to buffer[BUFFERSIZE-1], doesn't it equal BUFFER_SIZE number of items? Does the author mean to say that the index of the buffer can't exceed BUFFER_SIZE-1?But then, he has clearly written the number of items can't exceed BUFFER_SIZE-1 at the same time. Please explain the whole thing.

Grassi

It is to facilitate his algorithm that when the head and tail of the circular buffer are residing on the same node (regardless of which node it is) the buffer is "empty". Therefore there will always be one node that cannot hold data. I've seen this before in other implementations, though this one is a bit baroque. – Inferential

Answer 1

When you have ring buffer, you typically have 2 pointers or offsets, which signify start and end of the data in the buffer. Typical convention to tell if buffer is empty when start == end.

This convention leads to BUFFER_SIZE - 1 limitation on total numbers of items in ring buffer. If we were to allow to fill it to BUFFER_SIZE, this would mean that start == end, and thus would be impossible to tell if buffer is completely empty or completely full.

If you create one more variable that keeps number of items in the buffer, this would be possible to tell apart and allow to fill buffer to the max. But it is easier to not do that and simply reduce max number of items by 1.

Taxi

@Taxi Why can't we use (in+2)%(BUFFER_SIZE+1)==out?That way we can full the buffer to the max and still tell when it is full? – Scrounge

@Inferential Check out if you have anything to say about my comment above. – Scrounge

If in and out are ringbuffer offsets, they both must be from 0 to BUFFER_SIZE-1. With that, (in-out)%BUFFER_SIZE is number of elements currently in rungbuffer (0 if in==out). But, if number of elements is BUFFER_SIZE, (in-out)%BUFFER_SIZE is also 0. Your expression does not hold true if in==out (or when buffer is empty). – Taxi

@Rüppell'sVulture I've started typing up a response several times, but in the end mvp's answer is honestly the best explanation. in == out must signify exclusively one of the two possible conditions of "full" or "empty". If the latter, it means there must be a blank element at all times. If the former, you must account for "empty" some other way (an additional member that is a counter is the usual mechanism). Drawing it on paper really helps. – Inferential

@Taxi Thanks for following up your answer.It helped. – Scrounge

@Inferential Thanks to you too,you've always been nice and helpful. – Scrounge

@Taxi how would I code the version with a maximum limit of BUFFER_SIZE? I don't understand the need of an extra variable. – Gillies

@mozart: without extra variable it is impossible to tell if in==out means that buffer is completely empty or if buffer is completely full. So, this variable is needed for single purpose to tell this condition apart. However, it is much easier to simply increase BUFFER_SIZE by 1 and not use such variable in first place. – Taxi

Sometimes access to a ring buffer is controlled by a pair of semaphores. In that case, it is not necessary to check whether the buffer is full, or check whether it is empty, and the buffer may contain BUFFER_SIZE items. The counters in the semaphores provide extra information so that in**==**out is not needed to signify exclusively one of the two possible conditions of "full" or "empty". – Mousse