GATE CS 2014 Set 2 Q.41 (CS Q.31): Process Synchronization and Concurrency

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?

The producer will be able to add an item to the buffer, but the consumer can never consume it.

The consumer will remove no more than one item from the buffer.

Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.

The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

Official answer and solution

Official answer: C
From: Official GATE 2014 answer key

Solution

Trace semaphore acquisitions in producer and consumer to check for inversion of wait operations leading to deadlock.

Semaphore Roles:
- Semaphore $s$ (initialized to 1) provides mutual exclusion on the shared buffer.
- Semaphore $n$ (initialized to 0) counts the number of available items in the buffer.

Consumer Execution Order:

In the consumer code:

semWait(s); // acquires mutual exclusion lock
semWait(n); // waits for an item to become available

Deadlock Scenario:
- Suppose the buffer is initially empty ( $n = 0$ ) and the consumer executes first.
- The consumer calls semWait(s), successfully decrementing $s$ from 1 to 0 and acquiring the lock.
- The consumer next calls semWait(n). Because $n = 0$ , the consumer is put to sleep waiting for an item.
- However, the consumer still holds semaphore $s = 0$ .
- When the producer later attempts to add an item, its first instruction is semWait(s). Since $s = 0$ , the producer blocks waiting for $s$ .
- Both processes are now permanently blocked waiting for each other, creating a classic deadlock.
Conclusion:
Deadlock occurs if the consumer succeeds in acquiring semaphore $s$ when the buffer is empty, matching option (C).

Final answer

Common trap

Overlooking that holding the mutual exclusion semaphore s while blocking on resource semaphore n prevents the producer from ever generating the resource.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 41 of 65, printed as CS Q.31
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source