Sketch how a producer–consumer bounded buffer is built out of semaphores. Which semaphores do you need, what does each one count, and why does the order of the acquire calls matter?
answer
- empty starts at capacity, full starts at 0, plus a lock
- producer: acquire empty → lock → enqueue → unlock → release full
- consumer mirrors it, releasing empty
- counting semaphore BEFORE the lock, always
- lock-then-block = deadlock on an empty buffer
basics
~20 sUse three: an "empty slots" semaphore starting at capacity, a "filled slots" semaphore starting at zero, and a mutual-exclusion semaphore or lock for the buffer itself. Producers acquire empty then the lock; consumers acquire filled then the lock. Acquiring the lock first deadlocks.
solid answer
~60 sThree primitives. `empty` is a counting semaphore initialised to the buffer capacity — it counts free slots. `full` is a counting semaphore initialised to zero — it counts items available. A separate mutex (or a binary semaphore) protects the buffer's internal structure, because with capacity > 1 several producers could otherwise write concurrently. ``` produce(x): empty.acquire(); lock(); enqueue(x); unlock(); full.release() consume(): full.acquire(); lock(); x=dequeue(); unlock(); empty.release(); return x ``` The two counting semaphores do the blocking — a producer sleeps when the buffer is full, a consumer sleeps when it is empty — and they hand permits *to the other side*, which is precisely the ownerless signalling a mutex cannot express. Order matters: acquire the counting semaphore **before** the lock. If a consumer took the lock first and then blocked on `full`, it would sleep holding the lock, so no producer could ever enqueue and release a permit — a textbook deadlock. Release the lock before releasing the counting semaphore, so the woken thread does not immediately block on a held lock.
code
text · 11 linesempty = Semaphore(CAPACITY) # free slots
full = Semaphore(0) # available items
mutex = Lock()
produce(x): consume():
empty.acquire() full.acquire()
mutex.lock() mutex.lock()
enqueue(x) x = dequeue()
mutex.unlock() mutex.unlock()
full.release() empty.release()
return xgo deeper
Name the three objects and their initial values, and be able to write the two five-line procedures in the right order.
Explain why the mutex is needed only when capacity exceeds one, and trace the deadlock interleaving that results from locking before acquiring.
Cover fairness and starvation, timeouts and load shedding instead of unbounded blocking, and the release-after-unlock detail that avoids a wasted wake-up.
Position it against the monitor/condition-variable formulation and against a lock-free ring buffer, and treat the buffer's capacity as a backpressure policy decision rather than an arbitrary constant.
## The problem A bounded buffer (bounded queue) is shared by producers, which add items, and consumers, which remove them. Capacity is fixed. Three things must hold: 1. A producer must wait while the buffer is full. 2. A consumer must wait while the buffer is empty. 3. The buffer's internal state (indices, links, count) must not be mutated by two threads at once. Those are three different obligations, and the classic solution uses three different objects — conflating them is the usual source of bugs. ## The three primitives - **`empty`** — a counting semaphore initialised to `capacity`. Its permits represent *free slots*. A producer consumes one to reserve space; a consumer produces one when it frees a slot. - **`full`** — a counting semaphore initialised to `0`. Its permits represent *items ready to take*. A producer produces one after enqueuing; a consumer consumes one to claim an item. - **`mutex`** — a mutual-exclusion lock over the buffer's data structure. Needed whenever capacity > 1, because reserving a slot does not tell you *which* slot, and two producers still race on the write index. Notice the invariant this creates: `empty.permits + full.permits + in_flight_operations == capacity`. The two semaphores split the capacity between "space available" and "data available", and no thread can consume a unit that does not exist. ## The algorithm ``` produce(item): empty.acquire() # wait for a free slot, then claim it mutex.lock() enqueue(item) mutex.unlock() full.release() # publish: one more item available consume(): full.acquire() # wait for an item, then claim it mutex.lock() item = dequeue() mutex.unlock() empty.release() # publish: one more free slot return item ``` Each side acquires from one semaphore and releases to the other. This cross-release is the defining move: the permit changes hands between threads, which only an ownerless primitive can do. It is also why the counting semaphores are not "locks with a number" — they are message channels carrying a unit of capacity or a unit of data. ## Why acquire order is not negotiable Swap the first two lines of `consume`: ``` mutex.lock() full.acquire() # BUG ``` On an empty buffer the consumer blocks inside `full.acquire()` **while holding the mutex**. A producer then arrives, successfully acquires `empty`, and blocks on `mutex.lock()`. Neither can proceed: the consumer waits for a permit only the producer can create, and the producer waits for a lock only the consumer can drop. That is a circular wait — a deadlock — and it is deterministic as soon as the buffer runs dry, which in practice means it shows up under load and not in tests. The general rule this instantiates: **never block on a condition while holding a lock that the thread satisfying the condition must take.** Blocking-with-a-lock-held is a resource-ordering violation. ## Why release order matters less but still matters Releasing the counting semaphore *after* unlocking is preferred. If you released `full` while still holding the mutex, a woken consumer would immediately block on the mutex you have not yet dropped, costing an extra sleep/wake round trip. This is the semaphore analogue of the "hurry-up-and-wait" problem; it is a performance issue, not a correctness one. ## Common variants and their costs - **Capacity 1.** With a single slot the mutex can be dropped: `empty` and `full` alternate strictly, so at most one thread is inside at a time. Do not generalise this shortcut — it fails immediately at capacity 2. - **Separate producer and consumer locks.** With a linked-node queue, producers touch only the tail and consumers only the head, so two mutexes reduce contention. You must still handle the boundary case where head and tail meet. - **Fairness.** Unfair semaphores let a barging producer take the slot a queued producer has been waiting for. Under sustained saturation that queued thread can starve. Choose a fair semaphore when you need a latency bound, and accept the throughput cost. - **Timeouts.** Real systems use a bounded acquire (`try_acquire(timeout)`) so a producer facing a permanently full buffer can shed load rather than block forever. That turns a hang into a visible rejection, which is nearly always the better failure. ## Why not do this with monitors instead? You can — a monitor with two condition variables (`notFull`, `notEmpty`) and a predicate loop is the other classic solution, and it is what most standard-library blocking queues use, because predicates compose better than counters when the wait condition is more than "a unit exists". The semaphore version is worth knowing because it shows the counting invariant explicitly and needs no predicate re-check loop: a permit *is* the proof that a slot exists. ## What interviewers listen for The three-object decomposition, the cross-release, the deadlock caused by inverting acquire order, and the honest statement that the mutex is required only because capacity > 1 makes slot selection racy.
- Can you drop the mutex if the buffer has capacity 1?Yes. With one slot the `empty` and `full` semaphores force strict alternation, so at most one thread is ever inside the buffer and there is no slot-selection race. The shortcut disappears at capacity 2, where two producers can hold two `empty` permits simultaneously and race on the write index, so treat it as a special case, not a pattern.
- How would you stop a producer blocking forever when consumers have stalled?Use a bounded acquire with a timeout, or a non-blocking try-acquire, so the producer can reject or shed the item instead of parking indefinitely. That converts an invisible hang into a measurable rejection rate and a backpressure signal upstream. You then need a policy for the rejected item — drop, spill, or propagate the failure — which is a product decision, not a concurrency one.
- How does the semaphore solution compare with a monitor using two condition variables?They solve the same problem; the semaphore version encodes the count as permits, so no predicate re-check loop is needed, while the monitor version re-tests a predicate in a loop under one lock. Monitors scale better when the wait condition is richer than "a unit exists" — for example waiting on capacity *and* a shutdown flag — because predicates compose and permit counters do not.
A car park with a ticket machine (free-space tickets) and a valet desk (one car through the barrier at a time). You take a space ticket before queueing at the barrier; queueing at the barrier first and then waiting for a space would block everyone leaving.
saying these in an interview costs you the question
- Using a single semaphore and expecting it to handle both full and empty conditions
- Taking the mutex before the counting semaphore, then blocking while holding it
- Omitting the mutex at capacities greater than one
- Believing the producer should release the same semaphore it acquired
- Assuming waiting producers are served in arrival order without asking for fairness