Producer-Consumer — Decoupling Work With a Bounded Queue

An online judge receives code submissions in bursts: when a contest starts, hundreds arrive within a minute. Each one takes seconds to compile and run. The web server that receives the submissions should not have to wait for the judge, and the judge should not receive work faster than it can handle it.

The producer-consumer pattern puts a buffer between the two sides. Producers add work to it, consumers take work from it, and each side runs at its own pace. This lesson first builds a buffer with a size limit by hand, to show how it works, and then uses BlockingQueue, the ready-made version you should use in real code.

💡 The core idea.

A buffer separates producers from consumers: it absorbs bursts of work, and each side can be scaled up independently.
The buffer must be bounded, meaning it has a maximum size. When it is full, a producer must wait, be turned away, or throw work away. Slowing producers down this way is called back-pressure, and which option to use is a design decision.
Use a BlockingQueue (in Python, queue.Queue) rather than writing wait/notify code by hand, and stop the consumers by sending each one a poison pill: a special item that means "no more work".

This builds on Locks & Semaphores. How wait and notify work in Java, including what goes wrong when you use if instead of while, is covered in the Java guide's Concurrency: Coordination. Every output below was produced by running the code on Java 21 and Python 3.11.

You'll be able to: explain what a buffer between producers and consumers gives you; build a bounded buffer on a monitor and say why each wait is in a while loop; replace it with a BlockingQueue; choose between blocking, rejecting and dropping when the queue is full; shut down a pool of consumers with poison pills; pick a queue type and a capacity.

📘 How to read the Intuition boxes. Each one is built in three moves:

The mechanism — what the queue and its waiting threads do.
A concrete bite — a specific, runnable program where the mechanism produces a surprise.
The earned rule — the decision heuristic, now justified rather than asserted, plus its cost.

Why put a buffer between them?
A bounded buffer on a monitor
BlockingQueue: the buffer done for you
When the queue is full: back-pressure
Choosing a queue
Mental-model summary
Gotcha checklist
Check yourself
Sources

1. Why put a buffer between them?

Without a buffer, a producer hands work directly to a consumer and waits for it to finish. The web server would keep every user's request open while the judge compiles their code. A buffer changes three things:

Independence. The producer can carry on as soon as the work is in the queue. Producers and consumers don't know about each other, only about the queue.
Absorbing bursts. The first minute of a contest fills the queue, and the judges work through it over the next few minutes.
Separate scaling. Add consumers when the queue keeps growing; add producers when it stays empty.

A coffee machine and a customer are the smallest example: a buffer that holds one cup. The machine must not pour into a cup that is already full, and the customer must wait while the cup is empty. Every buffer follows the same two rules: don't add when it is full, and don't take when it is empty.

2. A bounded buffer on a monitor

Building a buffer by hand shows what every blocking queue does inside. Here, a fast producer places orders into a buffer that holds two, and a slower kitchen takes them out:

Output:

orders handled, in order: [1, 2, 3, 4, 5, 6]
most orders ever waiting: 2

Analysis. All six orders were handled, in the order they were placed, and the buffer never held more than two. The producer was faster, so it often found the buffer full and waited inside put(). Each take() made room and woke the producer up. Python's threading.Condition is a lock with wait and notify methods, the same pair a Java monitor provides [4].

Intuition. Mechanism. wait() releases the monitor and sleeps until another thread calls notify or notifyAll on the same object. Before returning, it takes the monitor back [1]. Both put and take hold the monitor while they check and change items, so checking and changing happen as one atomic step.

Concrete bite. Each wait() sits inside a while loop, not an if. A thread can wake up while the condition is still false: another consumer may have taken the item first, notifyAll wakes up every waiting thread, and the JVM even allows spurious wake-ups, where a thread wakes with no notify at all [1]. The loop checks the condition again after every wake-up. With if, a consumer that woke up too early would call remove() on an empty queue. The Java guide's Concurrency: Coordination, section 1 runs that failure.

💡 Earned rule. If you write a wait yourself, write it as while (!condition) wait(); inside the lock, and use notifyAll() when producers and consumers wait on the same monitor.

The cost of writing this coordination by hand is that every one of these details must be right. That is why the next section replaces it with a library class.

3. `BlockingQueue`: the buffer done for you

java.util.concurrent.BlockingQueue is a thread-safe queue whose put() waits while it is full and whose take() waits while it is empty [2]. Python's queue.Queue(maxsize=…) works the same way [3]. Here is the online judge with one fast producer, two slow judges, and room for three submissions to wait in the queue:

Output (illustrative — the blocked time is rounded and can vary slightly):

judged 8 of 8 submissions
producer spent ~200 ms blocked on a full queue, instead of ~0 ms

Analysis. All eight submissions were judged. The producer could not get far ahead of the judges: once three submissions were waiting, put() made it wait until a judge took one. That waiting is back-pressure: the slow side automatically slows the fast side down, and memory use stays limited.

To shut down, the producer added one POISON submission for each judge, and each judge stops when it takes one. A poison pill is just a value that the consumers recognise as "no more work". It goes into the queue behind all the real work, so nothing already queued is lost.

Intuition. Mechanism. The queue contains the lock, the two conditions ("not full" and "not empty") and the while loops from section 2. So the producer and consumer code needs no locking of its own.

Concrete bite: one pill per consumer. With two judges and only one pill, the first judge to take it stops, and the second waits in take() forever, so the program never ends. Send exactly as many pills as there are consumers, or use an executor's shutdown() (Thread Pools & Executors), which uses the same pattern with a queue built in.

💡 Earned rule. For producer-consumer inside one process, use a BlockingQueue with a size limit (in Python, queue.Queue(maxsize=…)). Stop the consumers with one poison pill each, or let an executor manage the queue.

The cost is choosing a capacity (section 5). The benefit is coordination code you don't have to write, test or debug yourself.

4. When the queue is full: back-pressure

If producers stay faster than consumers for long enough, the queue fills up. Then something has to give, and what gives should be decided in the design:

Policy	Java	Python	Effect
Block the producer	`put(e)`	`put(item)`	the producer slows down to the consumers' pace
Wait a while, then reject	`offer(e, timeout, unit)` returns `false`	`put(item, timeout=…)` raises `queue.Full`	the caller can tell the user "busy, please retry"
Reject at once	`offer(e)` returns `false`	`put_nowait(item)` raises `queue.Full`	fails immediately
Drop	`offer` and ignore the result, or remove the oldest item first	—	keeps only recent data, such as metrics samples

Making a web request wait for minutes is rarely acceptable, so the judge's web front end should reject submissions instead. Here, every judge is busy and the queue has two places left:

Output:

alice: queued
bob: queued
carol: server busy, please retry
dave: server busy, please retry
queued: [alice's submission, bob's submission]

Analysis. Alice and Bob filled the two places. Carol and Dave each waited 100 ms for space, found none, and were told to retry. Their requests did not hold up a web server thread until a judge became free.

Intuition. Mechanism. A bounded queue turns overload into a visible signal: a full queue. An unbounded queue hides the overload. A LinkedBlockingQueue created without a capacity accepts everything, and under constant overload it grows until the process runs out of memory. That is the same failure as newFixedThreadPool's queue in Thread Pools & Executors, section 5.

Concrete bite. "Let's just make the queue very big" only moves the problem. If a queue holds a million submissions and the judges need an hour to work through them, every new user waits an hour. Rejecting early is kinder to the user.

💡 Earned rule. For each producer, decide what happens when the queue is full: block for background producers, wait briefly and then reject for user-facing ones, and drop only data that is allowed to be lost. Never leave a queue without a size limit by accident.

Rejecting costs a "busy" path in the client, and retries that wait before trying again. Not deciding costs an outage.

5. Choosing a queue

Queue	Bounded?	Order	Fits
`ArrayBlockingQueue`	yes, fixed at creation	FIFO	the default bounded buffer
`LinkedBlockingQueue`	optional (no limit by default)	FIFO	always pass a capacity; uses separate locks for put and take
`PriorityBlockingQueue`	no	by priority	for example, paid users' submissions first; add a limit yourself
`SynchronousQueue`	stores nothing at all	direct hand-off	each `put` waits for a matching `take`
`DelayQueue`	no	by when each item's delay ends	retries and timeouts that become ready later

Python's queue module offers Queue (FIFO), LifoQueue and PriorityQueue, and each one takes a maxsize limit.

How big should the queue be? Size it by how long users can be made to wait, not by how much memory you have. If two judges together finish about 20 submissions a minute, and users will accept a 3-minute wait, a capacity of around 60 is right. Beyond that, reject submissions and let users retry, or add more judges.

Between separate processes or machines, the same pattern uses a message broker (Kafka, RabbitMQ, SQS) instead of a queue in memory. The broker keeps messages safe if a process crashes, and lets producers and consumers run on different machines. The choices about what to do when the queue is full stay the same.

6. Mental-model summary

Principle	Consequence
A buffer separates producers from consumers	Bursts are absorbed; each side scales independently
Don't add when full, don't take when empty	`put` waits on "not full", `take` waits on "not empty"
Waits go inside `while` loops	A thread can wake up while the condition is still false; always check again
`BlockingQueue` / `queue.Queue` contain the lock, the conditions and the loops	Producer and consumer code needs no locking of its own
A bounded queue creates back-pressure	Memory use stays limited; the fast side slows down or is told "busy"
When the queue is full: block, wait and then reject, or drop	Choose for each producer; user-facing code should not wait long
One poison pill per consumer	Fewer pills leave consumers waiting forever
Size the queue by acceptable waiting time	A huge queue only hides overload

7. Gotcha checklist

Symptom	Likely cause	Fix
`NoSuchElementException` from a hand-written buffer	`if` instead of `while` around `wait()`	`while (empty) wait();`
Hand-written buffer hangs with items waiting	`notify()` woke a thread of the wrong kind	`notifyAll()`, or a `BlockingQueue`
`IllegalMonitorStateException` from `wait()`	called without holding that object's monitor	call it inside `synchronized` on the same object
Memory grows steadily under load	an unbounded queue (`LinkedBlockingQueue()` with no capacity)	give it a capacity and a full-queue policy
Request threads hang when the system is busy	user-facing producers use blocking `put()`	`offer(timeout)` / `put(timeout=…)`, then reject
The program never exits after the work is done	fewer poison pills than consumers	one pill per consumer, or an executor's `shutdown()`
Work disappears silently	`offer()` returned `false` and nobody checked	handle the `false` (or `queue.Full`)

✅ Check yourself

One check per objective. Answer before you open anything.

The 🧪 box below: four judges instead of two; a queue of capacity 1; and one poison pill for two judges.

Four judges empty the queue twice as fast, so the producer finds it full less often: in our run its blocked time fell from about 200 ms to about 100 ms. All 8 are still judged.
With capacity 1, at most one submission waits, so the producer blocks more: about 300 ms in our run. The result is the same 8 of 8.
With one pill and two judges, one judge exits and the other waits in take() forever, so join() never returns and the program hangs.

📚 Sources

java.lang.Object, Java SE 21 API (wait(), notify(), notifyAll(), spurious wake-ups) — https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Object.html
java.util.concurrent.BlockingQueue, Java SE 21 API — https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/BlockingQueue.html
Python 3 documentation, queue — A synchronized queue class — https://docs.python.org/3/library/queue.html
Python 3 documentation, threading — Condition objects — https://docs.python.org/3/library/threading.html#condition-objects

🧪 Predict, then check.

In section 3, set judges = 4. Predict how long the producer is blocked.
In section 3, set the queue capacity to 1. Predict the number judged and whether the producer waits more or less.
In section 3, send one poison pill instead of one per judge. Predict what the program does.

Your Turn

Before you move on, check your understanding with the coach — explain the idea, apply it, weigh the trade-offs, then defend your reasoning.