For a semaphore s we define the following inits initial valu

For a semaphore s, we define the following: init[s]::= initial value of s start_P[s] ::= the number of times P(s) has been started end_P[s] ::= the number of times P(s) has been completed end_V[s] ::= the number of times V(s) has been completed A useful invariant is: end_P[s] = min(start_P[s], init[s] + end_V[s]) Now consider the abstract version of the bounded buffer problem: empty, full, mutex: semaphore = (N, 0, 1); Producer: while(1) { P(empty); get buffer from freelist; …. produce put buffer on fullist; V(full) } Consumer: while(1) { P(full); get buffer from fullist; …. produce put buffer on freelist; V(empty) }

Prove that 0 end_P[empty] – end_P[full] N

Solution

The given problem describes two processes, the producer and the consumer, who share a common, buffer. The producer\'s job is to generate data, put it into the buffer, and start again. At the same time, the consumer is consuming the data from the buffer one at a time. The producer will not add data into the buffer if it is full and that the consumer will not try to remove data from an empty buffer.

The given problem does not have any synchronization issue. Number of times the consumer remove data from the buffer will be equal to number of times producer puts it in the buffer. So end_P[empty] = end_P[full]

end_P[empty] -end_P[full]=0

0 0 N