How do you solve the producer-consumer problem using semaphores?
Use three semaphores: empty (counts free slots, starts at N), full (counts filled slots, starts at 0) and mutex (starts at 1). Producers wait on empty, consumers wait on full, and mutex guards the buffer.
Explain it simply
A shared bounded buffer is like a tiffin rack with N slots. The cook (producer) must not add when it is full; the eater (consumer) must not take when it is empty; and the two must not grab the same slot at once.
Three semaphores handle those three rules:
empty = N: free slots. The producer waits when this is 0.full = 0: filled slots. The consumer waits when this is 0.mutex = 1: only one process touches the buffer at a time.
Example
semaphore empty = N, full = 0, mutex = 1
producer: consumer:
produce item wait(full)
wait(empty) wait(mutex)
wait(mutex) item = remove from buffer
insert item signal(mutex)
signal(mutex) signal(empty)
signal(full) consume itemOrder matters. If the producer did wait(mutex) before wait(empty) and the buffer were full, it would hold the mutex while sleeping. The consumer could then never get the mutex to remove an item, so both would be stuck forever: a deadlock.
Always wait on the counting semaphore first, take the mutex second, and release in reverse order.
What to say in the interview
"I use empty (N), full (0) and mutex (1). The producer does wait(empty), wait(mutex), insert, signal(mutex), signal(full); the consumer mirrors it with full and empty. The counting waits must come before the mutex wait, or the pair can deadlock."
Common mistakes
- Swapping the order of the wait calls, which deadlocks when the buffer is full or empty.