Bounded Buffer
A bounded buffer is a fixed-capacity producer/consumer queue. It needs two counting semaphores: full counts items available to consume, empty counts free slots available to produce. Producers P(empty) before adding; consumers P(full) before taking.
Why two semaphores?
Because blocking can happen on either side: a producer waits when the buffer is full, a consumer waits when it’s empty. One counter can’t track both, you need one that decrements as items accumulate (
empty) and one that decrements as items are consumed (full).
CS343 canonical form (Buhr §6.4.2.2)
Producer loops indefinitely, emits a stopping value on shutdown; consumer breaks out of its for(;;) on seeing that sentinel. The final full.V() after the loop ensures a waiting consumer gets unstuck even if the buffer was empty at shutdown.
uSemaphore full(0), empty(QueueSize);
int queue[QueueSize], front = 0, back = 0;
void Producer::main() {
for ( ;; ) {
// produce an item
empty.P(); // wait for a free slot
// add element to buffer (queue[back] = item; back = (back+1)%QueueSize)
full.V();
}
// produce a stopping value
full.V(); // ensure consumer wakes up
}
void Consumer::main() {
for ( ;; ) {
full.P(); // wait for an item
// remove element from buffer
if ( /* stopping value ? */ ) break;
// process or consume the item
empty.V();
}
}Counter semantics, full and empty are mirror images
At any time full.counter() + empty.counter() == QueueSize (modulo blocked waiters). When the queue holds 0 items, full is 0 and empty is at max; adding an item ticks full up by one and empty down by one.
queue content: 34 13 9 10 -3
full empty
0 5
1 4
2 3
3 2
4 1
5 0
Negative values of counter() indicate blocked tasks.
Multi-producer / multi-consumer
Add a mutex semaphore around the index updates, the full/empty pair only coordinates counts, not the array indices. For multiple producers updating back, you need mutex on the producer side; symmetric for consumers.
uSemaphore full(0), empty(QueueSize), pmut(1), cmut(1);
// producer: empty.P(); pmut.P(); <insert>; pmut.V(); full.V();
// consumer: full.P(); cmut.P(); <remove>; cmut.V(); empty.V();