Producer-Consumer / Bounded Buffer

Language-specific mechanics: Concurrency Language Manual →

The problem

One or more producer threads generate items and place them into a shared buffer; one or more consumer threads remove items from that buffer and process them. The buffer has finite capacity N (hence "bounded buffer" — the version with an unbounded buffer is a strictly easier special case). Three constraints have to hold simultaneously:

A producer must never write into a full buffer (no overflow / no overwriting unread data).
A consumer must never read from an empty buffer (no underflow / no reading garbage).
Concurrent producers and concurrent consumers must not corrupt the buffer's internal bookkeeping (the read/write index, the count) by racing on it.

This is the same structural problem as an OS pipe, a bounded work queue feeding a thread pool, a network socket's receive buffer, or a logging library's async appender — which is exactly why it's one of the most-asked concurrency problems at the senior+ level: it's not an academic toy, it's the shape of half of all real inter-thread hand-off code.

Why one semaphore isn't enough

A first instinct is "use a mutex to protect the buffer, done." That handles constraint 3 but not 1 or 2 — mutual exclusion tells you only one thread touches the buffer at a time, it says nothing about what a thread should do when the buffer is in the wrong state for it. A producer holding the mutex on a full buffer still has nowhere to put its item; spinning while holding the mutex would deadlock every consumer trying to drain it.

The classical solution uses three synchronization objects together, each with a distinct job:

Object	Type	Initial value	Job
`mutex`	binary semaphore / lock	1	Protects the buffer's shared state (index, count, slots) during the actual read/write
`empty`	counting semaphore	`N`	Counts available empty slots; producers wait on it before writing
`full`	counting semaphore	`0`	Counts available filled slots; consumers wait on it before reading

producer():                          consumer():
    loop:                                loop:
        item = produce_item()                full.wait()      # block until >=1 item exists
        empty.wait()      # block until >=1 slot free          mutex.wait()
        mutex.wait()                          item = remove_from_buffer()
        add_to_buffer(item)                   mutex.signal()
        mutex.signal()                        empty.signal()   # a slot just freed up
        full.signal()     # an item just appeared            consume_item(item)

Notice the symmetry: empty and full are two views of the same finite capacity (empty + full == N, modulo the moment mid-transfer), and each side of the buffer waits on the semaphore that the other side signals. A producer never touches full except to signal it; a consumer never touches empty except to signal it. That cross-signaling is precisely the "semaphore has no ownership" property from the previous subtopic in action — the thread that calls full.wait() is never the thread that will eventually call full.signal() for that particular slot.

Why the ordering of wait() calls matters

The counting semaphore (empty/full) is always acquired before the mutex, never after. This ordering is load-bearing, not stylistic — swap it and you can deadlock:

Imagine a producer acquires mutex first, then calls empty.wait() and blocks because the buffer is full. It's now holding mutex while waiting. No consumer can acquire mutex to drain the buffer and signal empty, because the producer is holding it hostage while asleep. That's a deadlock caused purely by getting the acquisition order backwards — the general lesson (never block on a resource-counting wait while holding a mutex you need to release progress) reappears constantly in real systems and is worth stating explicitly if you're asked to explain the "why this order" question live.

Multiple producers, multiple consumers

The two-semaphore-plus-mutex solution above is already correct for multiple producers and multiple consumers, not just one of each — that's a common point of confusion. empty and full correctly count capacity regardless of how many threads are racing to wait() on them, and mutex serializes the actual buffer mutation regardless of how many producers or consumers exist. No structural change is required; you just spin up more producer/consumer threads against the same three objects. This is worth saying out loud in an interview, since candidates sometimes assume (incorrectly) that "multiple producers" needs a fundamentally different design.

Finite buffer vs. the simpler infinite-buffer version

Downey's Little Book of Semaphores deliberately introduces this problem in two stages: first with an unbounded buffer (§4.1, where only mutex and full — no empty — are needed, since there's no upper bound to enforce), then generalizes to the finite-capacity version (§4.1.4) that needs all three objects above. If you're ever asked "what if the buffer has unlimited size," recognize it as the strictly easier sub-problem — you only need to prevent underflow, not overflow, so empty drops out entirely.

Blocking vs. non-blocking variants

The pure semaphore solution above always blocks the calling thread when the buffer is full/empty. Real systems often want alternatives:

Bounded with timeout — tryAcquire(timeout) on empty/full instead of an unconditional wait(), returning a "buffer full, rejected" signal instead of blocking forever. This is exactly what backpressure policies in real thread pools and queues implement (see Thread Pools & Executors later in this roadmap).
Drop-oldest / drop-newest on overflow instead of blocking the producer — trades correctness-under-load for latency, appropriate for things like metrics or non-critical logs where losing data is preferable to blocking the producer.

Neither variant changes the core two-semaphore structure; they change what happens on the "would block" branch.

Pitfalls and interview gotchas

Forgetting the mutex is still needed even with empty/full in place. The counting semaphores prevent overflow/underflow, but two producers can still race on writing to the same buffer slot or corrupting the shared index without a mutex around the actual mutation — all three objects are required together, not as alternatives to each other.
Acquiring mutex before the counting semaphore. As shown above, this creates a real deadlock, not just a theoretical one — it's one of the most common bugs candidates introduce live when asked to write this from memory under interview pressure.
Using a single semaphore for both empty and full. They must be independent counters — conflating them (e.g. trying to reuse one semaphore's complement) breaks the moment you have more than one producer or consumer thread racing on the same counter.
Ignoring spurious-wakeup-adjacent bugs when reimplementing with condition variables instead of semaphores. If you solve this with a monitor/condition-variable style instead (see Condition Variables & Monitors, next topic), you must re-check the buffer's state in a while loop after waking, not an if — semaphores sidestep this specific bug because their counter is authoritative, but the analogous condition-variable solution does not get that for free.
Not handling InterruptedException/cancellation correctly in real code. Java's Semaphore.acquire() throws InterruptedException; swallowing it silently (instead of restoring the interrupt flag or propagating) is a very common real-world bug that also shows up in interview code review rounds.

The canonical shape: empty (counting, starts at capacity) and full (counting, starts at 0) are always waited on before mutex — see the theory above for why reversing that order deadlocks.

type BoundedBuffer struct {
    buf   []any
    mu    sync.Mutex
    empty chan struct{} // counting, starts at capacity
    full  chan struct{} // counting, starts at 0
}

func NewBoundedBuffer(capacity int) *BoundedBuffer {
    b := &BoundedBuffer{
        empty: make(chan struct{}, capacity),
        full:  make(chan struct{}, capacity),
    }
    for i := 0; i < capacity; i++ {
        b.empty <- struct{}{} // pre-fill empty-slot tokens
    }
    return b
}

func (b *BoundedBuffer) Put(item any) {
    <-b.empty // wait for a free slot BEFORE taking the mutex
    b.mu.Lock()
    b.buf = append(b.buf, item)
    b.mu.Unlock()
    b.full <- struct{}{}
}

func (b *BoundedBuffer) Take() any {
    <-b.full
    b.mu.Lock()
    item := b.buf[0]
    b.buf = b.buf[1:]
    b.mu.Unlock()
    b.empty <- struct{}{}
    return item
}

Buffered channels play the two counting semaphores; acquire is a receive of a token, release is a send. Wait on empty/full before the mutex — reversing that order deadlocks, same as the textbook. Idiomatic Go usually skips this construction and just uses make(chan T, capacity) as the buffer itself.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Design Bounded Blocking QueueMediumPremium!!!3/535m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Puzzle: Producer-Consumer With a Finite Buffer (Little Book of Semaphores §4.1.4)The Little Book of Semaphores~3/525m
Implement Producer-Consumer With Multiple Producers and Multiple Consumers (Java)GeeksforGeeks!3/530m