GATE 2018 CS Q.40: solution and answer

GATE 2018 · CSQ.40 · 2 marks · MCQ

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is $N$ . Three semaphores $e m pt y$ , $f u l l$ and mutex are defined with respective initial values of 0, $N$ and 1. Semaphore $e m pt y$ denotes the number of available slots in the buffer, for the consumer to read from. Semaphore $f u l l$ denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either $e m pt y$ or $f u l l$ . The valid semaphore operations are: wait() and signal().

Producer:

do{
    wait(P);
    wait(mutex);
    //Add item to buffer
    signal(mutex);
    signal(Q);
}while(1);

Consumer:

do{
    wait(R);
    wait(mutex);
    //Consume item from buffer
    signal(mutex);
    signal(S);
}while(1);

Which one of the following assignments to P, Q, R and S will yield the correct solution?

(A)
P: full, Q: full, R: empty, S: empty
(B)
P: empty, Q: empty, R: full, S: full
(C)
P: full, Q: empty, R: empty, S: full
(D)
P: empty, Q: full, R: full, S: empty

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct assignment is P: full, Q: empty, R: empty, S: full, which is option (C).

Official answer: CSource: Official answer key, GATE 2018 CS (IIT Guwahati)

Read the meanings from the question: $f u l l$ (initial value $N$ ) counts the slots the producer may write into, and $e m pt y$ (initial value $0$ ) counts the filled slots the consumer may read from. mutex (initial value 1) gives mutual exclusion on the buffer.
The producer must first wait for a writable slot, so it waits on the semaphore that counts writable slots: P $= f u l l$ .
After adding an item, the producer makes one more item available for reading, so it signals the semaphore that counts readable items: Q $= e m pt y$ .
The consumer must first wait for an item to read, so it waits on the readable-items semaphore: R $= e m pt y$ .
After consuming, the consumer frees a slot for the producer, so it signals the writable-slots semaphore: S $= f u l l$ .
Check with the initial values. $e m pt y = 0$ makes the consumer block while the buffer is empty. $f u l l = N$ lets the producer write $N$ items and then block when the buffer is full.
Check the other options. In (A) the producer both waits on and signals $f u l l$ , so nothing ever signals $e m pt y$ and the consumer blocks forever on $e m pt y = 0$ . In (B) the producer waits on $e m pt y = 0$ and blocks, while the consumer waits on $f u l l = N$ and reads $N$ items from an empty buffer. In (D) the producer waits on $e m pt y = 0$ and blocks, while the consumer waits on $f u l l = N$ and reads from an empty buffer. So only (C) is correct: P: $f u l l$ , Q: $e m pt y$ , R: $e m pt y$ , S: $f u l l$ .

KEY IDEA

Each side waits on the semaphore that counts what it needs (producer: free slots; consumer: filled slots) and signals the semaphore that counts what it has just created for the other side.

WATCH OUT FOR

Reading the names literally and taking $e m pt y$ to be the producer's semaphore. Here the question defines $e m pt y$ as the count of filled slots for the consumer and $f u l l$ as the count of free slots for the producer, so the names are swapped from the usual textbook version.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 7 Synchronisation questions, with notes

GATE 2018 CS Q.40: solution and answer

Answer and solution

More Synchronisation questions