Problem 14 Advanced Synchronization in Multi-Buffered Master-Worker Thread Pools

The right primitive turns this into three lines

A master produces items and workers consume them through a bounded buffer: producers must block when it's full, consumers must block when it's empty. The clean classic uses two counting semaphores — empty (slots free, starts at capacity) and full (items ready, starts at 0) — plus a mutex to protect the buffer structure itself. The earlier version mixed prose about "condition variables" with semaphore code, left a semaphore that was never acquired, and busy-spun a worker — all symptoms of not letting one primitive own the blocking.

Correct Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

class BoundedBuffer<T> {
    private final Queue<T> buf = new ArrayDeque<>();
    private final Semaphore empty, full;
    private final ReentrantLock mutex = new ReentrantLock();
    BoundedBuffer(int capacity) { empty = new Semaphore(capacity); full = new Semaphore(0); }

    public void put(T x) throws InterruptedException {
        empty.acquire();                 // blocks if buffer full
        mutex.lock();
        try { buf.add(x); } finally { mutex.unlock(); }
        full.release();                  // one more item to consume
    }
    public T take() throws InterruptedException {
        full.acquire();                  // blocks if buffer empty
        mutex.lock();
        T x;
        try { x = buf.poll(); } finally { mutex.unlock(); }
        empty.release();                 // one more free slot
        return x;
    }
}

Acquire the counting semaphore before the mutex, never the reverse — holding the mutex while blocking on a full/empty semaphore would deadlock the whole buffer.

Correct Go — the buffer IS a channel

Go folds all three objects into one: a buffered channel already blocks the sender when full and the receiver when empty, with the synchronization built in. This is the idiomatic answer and why Go concurrency is so terse here.

buf := make(chan T, capacity)   // bounded buffer
// producer:  buf <- x          // blocks when full
// consumer:  x := <-buf        // blocks when empty
// shut down: close(buf); for x := range buf { ... }   // drains then ends

Pitfalls

• Busy-spinning ("while empty: keep checking") burns a core and adds latency — let the semaphore / channel block the thread so the scheduler can run someone useful.
• Lock ordering: counting semaphore first, mutex second. The mutex is held only for the O(1) enqueue/dequeue.
• A semaphore that's created but never acquired (the old bug) does nothing — every primitive must be on the actual blocking path.
• When NOT to hand-roll it: in real Java, reach for ArrayBlockingQueue / LinkedBlockingQueue — they are this exact structure, tested. Roll your own only to learn the primitive, or when you need a predicate the JDK queues don't offer (priority, multi-condition). ConcurrentLinkedQueue is unbounded, so it gives up the back-pressure that is the whole point here — use it only when memory is not the risk.

Takeaways

• Bounded buffer = empty + full semaphores + a short mutex; producers/consumers block, never spin.
• In Go a buffered channel is the bounded buffer — capacity, blocking, and safety in one.
• Acquire the counting semaphore before the mutex; hold the mutex only for the enqueue/dequeue.

---

Re-authored for correctness for this guide (the prior version had prose/code mismatch, a dead semaphore, and a busy-spin). Classic producer-consumer (Dijkstra). See also: Semaphore, Condition Variables, Mutex Lock.

Sizing the buffer: the latency–memory–throughput triangle

The capacity C is not a free parameter — it trades three things against each other. An item can sit behind up to C−1 others, so when the buffer runs near-full the time an item waits before a worker picks it up is roughly C / μ, where μ is the aggregate consumer rate; by Little's law the average occupancy L = λ·W ties arrival rate, wait, and depth together.

• Larger C absorbs bursts — the producer stalls less, so throughput under bursty load is higher — but costs more memory (C × item size) and adds queueing latency (an item waits behind more predecessors).
• Smaller C (down to 1) couples producer and consumer tightly: lowest latency and memory, but any rate mismatch stalls the producer immediately, so throughput collapses under bursts.

Concrete break-even: if consumers drain at μ and producers can burst at λpeak for a duration t, size C ≥ (λpeak − μ)·t to ride out the burst without ever blocking (that is exactly the net items accumulated during the burst). Below that the producer blocks for the overflow; above it you are only buying latency and memory for no throughput gain.

When producers outrun workers: block, drop, or OOM

A bounded buffer is backpressure by construction: when it is full, put() blocks on the empty semaphore, and that stall propagates upstream until the producer slows to the consumer's pace. Memory stays capped at C. The alternatives make the opposite trade:

• Unbounded queue (LinkedBlockingQueue with no cap, ConcurrentLinkedQueue): the producer never blocks, so a producer that persistently outruns consumers grows the queue without bound → GC pressure, then OOM. This is the classic "we removed the limit to stop the producer stalling" latent crash — use only when you can prove consumers always keep up.
• Bounded + rejection (e.g. ThreadPoolExecutor's RejectedExecutionHandler: abort, discard-oldest, or caller-runs): when the producer cannot block — a request handler that must stay responsive — you shed load instead. CallerRunsPolicy is implicit backpressure (the submitter runs the task, slowing itself); the discard policies are explicit loss.

Decision: block when the producer can afford to slow down and you need zero loss (batch / ETL); reject or drop when the producer must stay live and the data is lossy-tolerant (metrics, logs); never unbounded unless the consumer provably never falls behind.

Shutting down N workers cleanly: the poison pill

Closing a shared buffer to many workers has a trap: enqueue one sentinel and only one worker sees it — the other N−1 block forever on the empty buffer. So the producer enqueues one poison per worker after the last real item:

static final Object POISON = new Object();

// producer, after the last real item:
for (int w = 0; w < N_WORKERS; w++) buffer.put(POISON);

// each worker:
while (true) {
    T x = buffer.take();
    if (x == POISON) break;      // one poison per worker → each stops exactly once
    process(x);
}

If the producer does not know N_WORKERS, use the cascade: a worker that takes the poison re-inserts it before exiting (buffer.put(POISON); break;), so it propagates worker to worker. In Go you get this for free — close(jobs) after the producers finish, and every range over the channel exits cleanly; the channel close is the multi-worker poison pill.

I'm working on the problem **Problem 14 Advanced Synchronization in Multi-Buffered Master-Worker Thread Pools** (Concurrency). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Problem 14 Advanced Synchronization in Multi-Buffered Master-Worker Thread Pools** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Problem 14 Advanced Synchronization in Multi-Buffered Master-Worker Thread Pools**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Problem 14 Advanced Synchronization in Multi-Buffered Master-Worker Thread Pools**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.