The following solution to the single producer single consumer problem uses semaphores for synchronization:
#define BUFFSIZE 100
buffer buf[BUFFSIZE];
int first = last = 0;
semaphore b_full = 0;
semaphore b_empty = BUFFSIZE;
void producer() {
while(1) {
produce an item p;
P(b_empty);
buf[last] = p;
last = (last+1) % BUFFSIZE;
V(b_full);
}
}
void consumer() {
while(1) {
P(b_full);
c = buf[first];
first = (first+1) % BUFFSIZE;
V(b_empty);
consume item c;
}
}
A. Complete the dotted part of the above solution.
B. Using another semaphore variable, insert one line statement each immediately after p1, immediately before p2, immediately before c1 and immediately before c2 so that the program works correctly for multiple producers and consumers.
Which of the following correctly completes part A (filling in the producer and consumer code shown above, where the dotted lines represent missing synchronization)?
A. The code as given is already complete; b_full and b_empty suffice for mutual exclusion.
B. A mutex semaphore (initialized to 1) is needed: P(mutex) before accessing buf[] and V(mutex) after, in both producer and consumer.
C. Only the producer needs a mutex semaphore; the consumer does not.
D. A condition variable replaces the semaphores b_full and b_empty.
GATE 2002 · Operating System · Process Synchronization · medium
Answer: Part A: The given code is complete for single producer-consumer — b_full and b_empty are sufficient. Part B: Add semaphore mutex=1. In producer: P(mutex) immediately after P(b_empty), V(mutex) immediately before V(b_full). In consumer: P(mutex) immediately after P(b_full), V(mutex) immediately before V(b_empty). This ensures correct mutual exclusion on the shared buffer for multiple producers and consumers. (Option B)
Analyze the single producer-consumer solution: With exactly one producer and one consumer: b_empty prevents producer overflow (blocks when full), b_full prevents consumer underflow (blocks when empty). The indices 'first' and 'last' are only modified by one process each, so no race condition exists. The given code is complete for the single case.
Identify race condition with multiple producers/consumers: With multiple producers: P1 and P2 both execute P(b_empty) successfully (b_empty >= 2). Then both read 'last=5', both write to buf[5], and both compute last=(5+1)%100=6. Result: buf[6] is skipped, buf[5] is overwritten, and one item is lost. Similarly, multiple consumers can both read 'first=3', fetch buf[3], and both advance first to 4 — one consumer gets garbage data.
Add mutex for Part B — multiple producers and consumers: Modified producer:
P(b_empty); // point p1
P(mutex); // ADD: immediately after p1
buf[last] = p;
last = (last+1) % BUFFSIZE;
V(mutex); // ADD: immediately before p2
V(b_full); // point p2
Modified consumer:
P(b_full); // point c1
P(mutex); // ADD: immediately after c1
c = buf[first];
first = (first+1) % BUFFSIZE;
V(mutex); // ADD: immediately before c2
V(b_empty); // point c2
Note: mutex is acquired AFTER b_empty/b_full to avoid deadlock. If mutex were acquired first, a producer holding mutex could block on P(b_empty) while a consumer waiting for mutex is also blocked — deadlock.