Consider the following solution to the producer-consumer synchronization…
2018
Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is 𝑁. Three semaphores empty, full and mutex are defined with respective initial values of 0, 𝑁 and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full 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 empty or full. The valid semaphore operations are: wait() and signal().
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
Attempted by 153 students.
Show answer & explanation
Correct answer: C
Interpretation of semaphores and initial values: The problem statement gives initial values empty = 0 and full = N. With those values, the semaphore named full actually counts free buffer slots (N free at start) and the semaphore named empty counts filled items (0 at start). We must map the placeholders so the producer waits for a free slot then increments the filled count, and the consumer waits for a filled item then increments the free-slot count.
Correct assignment: P = full, Q = empty, R = empty, S = full.
Producer sequence:
wait(full) -> wait(mutex) -> add item to buffer -> signal(mutex) -> signal(empty).
Explanation: wait(full) ensures a free slot exists (full starts at N). After producing we signal(empty) to indicate one more filled item is available for consumers.
Consumer sequence:
wait(empty) -> wait(mutex) -> remove item from buffer -> signal(mutex) -> signal(full).
Explanation: wait(empty) blocks until a produced item exists (empty starts at 0). After consuming we signal(full) to show one more free slot is available for the producer.
Why this works:
Preserves counts: filled and free-slot counts are updated in complementary pairs (producer increments filled, consumer increments free).
Prevents overflow/underflow: producers only proceed when a free slot exists; consumers only proceed when an item exists.
Mutual exclusion: mutex ensures single-thread access to buffer modifications.
Why the other assignments fail:
P = full, Q = full, R = empty, S = empty: The producer signals the free-slot semaphore after producing instead of signaling the filled-item semaphore, so the filled-item count is not incremented properly and the buffer invariants break (possible overflow or blocked consumers).
P = empty, Q = empty, R = full, S = full: The producer waits on the filled-item semaphore (initially zero) and blocks immediately, while the consumer can proceed because it waits on the free-slot semaphore (initially N). That allows the consumer to attempt to consume from an empty buffer (underflow).
P = empty, Q = full, R = full, S = empty: Again the producer waits on the filled-item semaphore and will block at start; the consumer can run prematurely and try to consume nothing, causing incorrect behavior.
A video solution is available for this question — log in and enroll to watch it.