Bounded Blocking Queue

Overview

Implement a fixed-capacity queue shared between producer and consumer threads. Producers call put to add items; consumers call take to remove them. When the queue is full, put must block until space frees up; when the queue is empty, take must block until an item arrives.

The core problem is coordinating threads around shared state without busy-waiting. A plain lock gives mutual exclusion, but on its own it cannot make a thread wait for a condition. That needs a condition variable: a thread releases the lock and sleeps until another thread signals that the state it was waiting for may now hold. The design has to wake the right threads and re-check the condition after waking, because a wakeup does not guarantee the condition is still true (spurious wakeups).

Interfaces

A generic BoundedBlockingQueue, plus a driver that runs producers and consumers:

class BoundedBlockingQueue<T> {
    BoundedBlockingQueue(int capacity);

    // Add item; block while the queue is full.
    void put(T item) throws InterruptedException;

    // Remove and return the oldest item; block while the queue is empty.
    T take() throws InterruptedException;

    int size();
}

// Spawn the threads, run them to completion, return the total items consumed.
static long runProducerConsumer(int numProducers,
                                int numConsumers,
                                int itemsPerProducer) throws InterruptedException;

Guard the buffer with a single lock and use two conditions — "not full" and "not empty". put waits on "not full" and signals "not empty"; take waits on "not empty" and signals "not full". Always wait inside a while loop, not an if, so the condition is re-checked after every wakeup.

Inputs and outputs

• Input: the queue capacity (1–10000), the number of producer and consumer threads, and how many items each producer emits.
• Output: every produced item is taken exactly once, no item is lost or duplicated, and the program terminates with no thread left blocked forever.

Requirements

• put blocks while full and take blocks while empty — no busy-waiting.
• Items come out in FIFO order relative to a single producer.
• All access to the shared buffer happens under the lock.
• Signal the matching condition after every state change so waiters wake up.
• The system must not deadlock: producers and consumers always make progress.

Examples

BoundedBlockingQueue<Integer> q = new BoundedBlockingQueue<>(2);

q.put(1);          // queue: [1]
q.put(2);          // queue: [1, 2]
// q.put(3)        // would block here — queue is full

q.take();          // returns 1, queue: [2]
q.put(3);          // unblocks: queue: [2, 3]

A consumer that calls take on an empty queue parks until a producer adds an item; it never spins or returns a null/placeholder.

Follow-ups

• What does ArrayBlockingQueue give you that a hand-rolled queue doesn't — and what design decisions does it quietly make for you?

• A consumer shouldn't always wait forever. How would you add a poll(timeout) that gives up after a bounded wait?

• How do you shut the whole system down so every consumer exits cleanly and no producer is left blocked?

• And more...