Consider the procedure below for the Producer-Consumer problem which uses…
2014
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);
}
}
{
while(true)
{
semWait(s);
semWait(n);
removeFromBuffer();
semSignal(s);
consume();
}
}
Which one of the following is TRUE?
- A.
The producer will be able to add an item to the buffer, but the consumer can never consume it
- B.
The consumer will remove no more than one item from the buffer.
- C.
Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
- D.
The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.
Attempted by 109 students.
Show answer & explanation
Correct answer: C
Explanation of the bug and why deadlock occurs:
Initial state: item-count semaphore n = 0 (no items), mutex semaphore s = 1 (free). The consumer calls semWait(s) before semWait(n). Consider the consumer running first when the buffer is empty:
Consumer executes semWait(s): mutex s becomes 0 and consumer holds the mutex.
Consumer executes semWait(n): because n = 0, the consumer blocks waiting for an item, but it still holds the mutex s.
Producer tries to add an item and calls semWait(s) to acquire the mutex, but s = 0 so the producer blocks.
Both threads are blocked: consumer waiting for item-count n, producer waiting for mutex s. No one can proceed to signal n, so deadlock occurs.
Key fix: ensure the consumer waits on the item-count semaphore before acquiring the mutex.
Correct consumer order: semWait(n); semWait(s); removeFromBuffer(); semSignal(s); consume().
Producer remains: produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n).
With this ordering the consumer blocks on the item-count semaphore without holding the mutex, so the producer can still add an item and signal n, avoiding deadlock.
Note: The item-count semaphore should start at 0 (no items). Changing it to 1 would hide the bug by allowing a spurious initial consumption but is incorrect logically because it misrepresents the buffer state.
A video solution is available for this question — log in and enroll to watch it.