2

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!

enter image description here

enter image description here

user3343396
  • 191
  • 1
    You completely changed your question. The code you are now showing is doing something completely different from the one on the original question. The edit function should only be used to make the question more precise/ avoid misunderstandings/ format it nicer etc, not for asking a different follow up question. Please reroll your question to the original one and post the new one as a new question. Also, you didn't state what you actually want to know in the edited question – NeitherNor Jul 10 '20 at 13:31
  • 1
    Above this comment section and below the body of your question, you find the history of the question. Use it to get the source of the original question. If you want, after having posted the new question, you can put a comment with the link to your new question below my answer in order to ask me for help with the new one – NeitherNor Jul 10 '20 at 13:46
  • Done. posted a new one here https://math.stackexchange.com/questions/3752219/bounded-buffer-problem-why-can-only-fill-up-n-1-buffer – user3343396 Jul 10 '20 at 13:53

1 Answers1

3

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.

NeitherNor
  • 1,210