Bounded buffer problem - Why producer can only fill up n–1 buffer?

Question

I read a lecture about synchronization.

In this lecture there were 2 slides about the bounded buffer problem (see below).

My question is about the sentence marked in yellow, why it's true that producer can only fill up to n-1 buffer cells? thanks!

Answer 1

That's easiest to see when you put n=1. Then, in+1 mod n = out is always true, as is in=out.. thus, even though our buffer could store 1 element, only n-1=0 are filled at any time. The underlying problem is that the "natural" encoding for buffer empty (out=in) is the same as for buffer completely full (in=out). We thus have to stop filling the buffer already one element before it's full in order to reestablish a 1 to 1 mapping.

Edit: the variable $in$ denotes the next position the producer would like to store an element, the variable $out$ the next position the consumer wants to read. Consider first the case when the buffer is completely empty: the consumer wants to read position $out$ and it has already read the element currently saved in $out$. Thus it is completely fine for the producer to store a value in $in=out$. However, if the buffer is completely full, the consumer still wants to read the position $out$. However, it did not yet read the element currently stored in $out$. Thus, it is not ok for the producer to overwrite the element $in=out$. How does the producer now figure out which case holds, i.e. if the buffer is completely full or empty. Since both cases are encoded by $in=out$, it cannot. Thus, if we would allow the buffer to become full, the producer would not be allowed to overwrite $in=out$ since this might lead to the overriding of a not yet read element. This would however result in a dead lock if the buffer is empty. To avoid this dead lock, we must forbid the buffer to ever become completely full in order for the producer to be allowed to store a value in $in=out$ without risking to override a not yet read value.