Consider the procedure below for the Producer-Consumer problem which uses semaphores:
semaphore n = 0; semaphore s = 1;
void producer()
{
while(true)
{
produce();
semWait(s);
addToBuffer();
semSignal(s);
semSignal(n);
}
}
void consumer()
{
while(true)
{
semWait(s);
semWait(n);
removeFromBuffer();
semSignal(s);
consume();
}
}
Which one of the following is TRUE?
View worked solution
Answer: C
To analyze the behavior of the given Producer-Consumer implementation, let us look at the semaphores used:
s = 1: A binary semaphore (mutex) used to ensure mutual exclusion when accessing the shared buffer.n = 0: A counting semaphore representing the number of items currently in the buffer.
Deadlock Analysis
Consider the scenario where the buffer is initially empty () and the consumer process executes first:
- The consumer executes
semWait(s). Since , the consumer successfully acquires the mutex, and becomes . - The consumer then executes
semWait(n). Since the buffer is empty (), the consumer is blocked on semaphore . Crucially, the consumer is still holding the mutex . - The producer process now attempts to run. It executes
produce()and then callssemWait(s). - Since (held by the consumer), the producer blocks on semaphore .
At this point:
- The consumer is waiting for the producer to signal (via
semSignal(n)). - The producer is waiting for the consumer to release (via
semSignal(s)).
This circular wait results in a deadlock.
Evaluating the Options
- Option A is incorrect: If the producer runs first, it successfully adds an item and signals . The consumer can then successfully consume it.
- Option B is incorrect: If the producer continuously produces items ahead of the consumer, the consumer can remove multiple items without deadlocking, as long as the buffer never becomes empty when the consumer acquires .
- Option C is correct: As demonstrated in our trace, if the consumer acquires when the buffer is empty (), a deadlock occurs.
- Option D is incorrect: Simply changing the initial value of to does not prevent deadlock. The correct solution is to swap the order of the wait operations in the consumer to:
semWait(n); semWait(s);
Free practice · Your answers on this page are not saved.