GATE Overflow Test Series | Mock GATE | Test 4 | Question: 50

Question

Consider the following synchronization solution for Producer-Consumer problem. Here, counter is a shared variable initialized to 0, buffer is the shared memory region and increment and decrement operations take place atomically.

Consumer process
item nextConsumed;
while (1) {
    while (counter == 0);
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}
Producer process
item nextProduced;
while (1) {
    while (counter == BUFFER_SIZE);
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

Which of the following is correct?

• A. Race condition may be possible.
• B. The solution works fine for Producer Consumer problem.
• C. Progress is violating.
• D. Buffer overflow is possible.

Comments

@gatecse Sir, let there be 2 producer processes initially when counter = 0. Let the first producer process be pre-empted after the line

$buffer[in] = nextProduced;$

Now if the second producer process also runs till this particular line, won’t it overwrite the item produced by the first process, since we haven’t incremented the buffer index variable $’in’$ yet? If so can we call it a correct solution?

Please check

---

Yes. As we aren’t using semaphores.

---

@rohith8194, Producer consumer problem has only one producer and one consumer.

---

@gatecse Sir, in the question only when the Buffer is entirely full can the consumer start consuming and on the other hand when the Buffer becomes empty can the producer start producing. So when the Buffer is non empty or non full the consumer or the producer are blocked, isn’t this violating Progress?

Answer 1

As both the increment and decrement operations are atomic the given solution works correctly. This is because the only time both Producer and Consumer access the same memory region is when the buffer is either full or empty (when in = out). But when buffer is empty, only producer can proceed and when buffer is full, only consumer can proceed.

Comments

key in this question lies on the word atomic.

i missed that.

---

@gatecse please explain option C..I think progress is violating.

if we take initial case ,since  counter =0,Consumer is struck at while loop and therefore unable to consume or enter in Critical section.Then how it is guaranteed here?

---

@spike500 then it will not be progress right?

I think progress will violated if one Producer is not able to produce, because another Producer is not producing, or if one consumer is not able to consume because other consumer isn’t consuming.

---

say buffer is empty initially , consumer waits in the while loop .

Producer start producing and continues to do so until buffer is full then waits in the while loop .

both stuck in while loop right ?

This  problem is unlike standard producer and consumer problem where busy waiting is not there , consumer will sleep if buffer is empty and as soon as producer produces an item , it will give a wakeup call to the consumer.

kindly clarify