The Bounded Blocking Queue

The bounded blocking queue is one of the most-asked concurrency problems in interviews, and for a sneaky reason: a correct single-threaded queue is trivial, but a correct concurrent, blocking one forces you to understand locks, waiting, and signalling down to the last line.

In this post we build it twice — first with the low-level synchronized + wait/notify primitives, then with the more expressive ReentrantLock + Condition — and cover the theory you need to explain every line in a round.

The problem

Build a queue with a fixed capacity N. If it's full, put blocks until space frees up. If it's empty, take blocks until an item arrives.

This is the producer–consumer problem in its purest form. Producers add items; consumers remove them. The queue is the buffer between them, and its two blocking rules are what make it interesting:

• Full → block the producer. A producer that arrives when the queue is full must wait — not fail, not drop the item — until a consumer makes room.
• Empty → block the consumer. A consumer that arrives when the queue is empty must wait until a producer supplies an item.

Java ships a ready-made BlockingQueue, but the whole point of the exercise is to build the blocking yourself — which forces you to understand locks, waiting, and signalling. We'll build it twice: first with the low-level synchronized + wait/notify primitives, then with the more expressive ReentrantLock + Condition. But first, the theory that makes both make sense.

Threads, waiting, and sleeping

Creating a thread

There's one idiom to remember, and it's the modern one: a lambda passed to Thread.

new Thread(() -> {
    // code the thread runs
}).start();

A Runnable is a functional interface with one method, so a lambda is a Runnable. You wrap it in a Thread and call start().

start vs join

Two methods cover almost everything: start() launches a thread; join() waits for one to finish.

start() is "fire and forget" — it launches the thread and immediately moves to the next line without waiting. join() is the opposite: the calling thread pauses until the joined thread completes. You use join() when the main thread needs to wait for all its workers before continuing — for example, to print a result after all the work is done.

wait vs sleep — a favourite interview question

Both pause a thread, but the difference is the lock, and it's the whole point.

Locks and the monitor

Every object in Java has an invisible built-in lock called its monitor. synchronized(obj) means: acquire obj's monitor on the way in, release it on the way out. Only one thread can hold a given object's monitor at a time — so if two threads reach synchronized(obj) for the same obj, one enters and the other waits.

The object itself does nothing special — it's a shared token that threads compete for. Think of a single key on a hook: to enter the room (the critical section) you must take the key; only one key exists, so only one person is inside at a time; you hang it back when you leave.

A subtle point that matters later: a lock is about ownership, not execution. If the OS pauses a thread while it holds the lock, it still owns the lock — another thread can run but cannot enter the critical section until the owner resumes and exits. However threads interleave, only one is ever inside the block.

wait, notify, and the wait-set

A thread that holds the lock but can't proceed yet — a consumer on an empty queue — shouldn't spin, burning CPU checking the same condition. Instead it calls wait(): it goes to sleep, using no CPU, until another thread wakes it.

The threads asleep on an object's monitor sit in its wait-set — a waiting room. Two calls wake them:

• notify() — wakes one arbitrary thread from the wait-set.
• notifyAll() — wakes all threads in the wait-set.

A woken thread doesn't resume instantly — it must first re-acquire the lock (only one at a time), then continue from just after its wait() call. This "wake, re-acquire, re-check" cycle is why the next section exists.

Why while, not if

This is the single most-probed detail in the entire problem. Guard every wait() with while, never if.

The rule: when a thread wakes from wait(), the condition it waited for may no longer be true — so it must re-check. An if checks once, before sleeping, and never again; the woken thread falls straight through. A while re-checks on every wake and only proceeds when the condition actually holds.

The scenario that breaks if

Queue empty, four consumers all asleep in wait(). A producer adds one item and calls notifyAll(). All four wake and compete for the lock:

• Consumer 1 gets the lock, takes the item. Queue is empty again. Releases the lock.
• Consumer 2 gets the lock next. With if, it does not re-check — it runs poll() on a now-empty queue → gets null. Bug.
• Consumers 3 and 4: same — they poll an empty queue.

With while, consumers 2, 3, and 4 loop back, re-check "is it empty?", find it is, and go back to sleep. Only the one consumer that can actually proceed does.

Building it with synchronized

Now the theory pays off. A plain ArrayDeque holds the items (only BlockingQueue is off-limits — a regular queue for storage is fine, and ArrayDeque is the array-backed, allocation-light choice). We wrap it in synchronized + wait/notifyAll to provide the blocking.

class BoundedBlockingQueue {
    private final Queue<Message> q = new ArrayDeque<>();
    private final int capacity;

    BoundedBlockingQueue(int capacity) {
        this.capacity = capacity;
    }

    void put(Message msg) throws InterruptedException {
        synchronized (this) {
            while (q.size() >= capacity) {   // full -> block the producer
                wait();
            }
            q.offer(msg);                    // add first...
            notifyAll();                     // ...then wake consumers
        }
    }

    Message take() throws InterruptedException {
        synchronized (this) {
            while (q.isEmpty()) {            // empty -> block the consumer
                wait();
            }
            Message msg = q.poll();          // remove first...
            notifyAll();                     // ...then wake producers
            return msg;                      // hand the item back
        }
    }
}

Three things carry the correctness, and each maps to a theory section above:

• while, not if, on both guards — woken threads re-check the condition.
• Modify, then notify. Add the item before notifyAll(), so a woken consumer finds it there. Notifying before the change wastes the wakeup.
• notifyAll(), not notify() — the next section explains why this specific choice is forced here.

notify vs notifyAll — the lost wakeup

Why notifyAll() and not the cheaper notify()? Because in this design, producers and consumers wait on the same monitor for different reasons — and notify() wakes one arbitrary thread, which might be the wrong kind.

Suppose the wait-set holds both a blocked producer (waiting for space) and blocked consumers (waiting for items). A consumer removes an item, opening a slot, and calls notify(). If notify() happens to wake another consumer instead of the producer, that consumer re-checks, finds nothing useful for it, and goes back to sleep — while the producer that could have used the new slot stays asleep. The signal was consumed by the wrong thread. Under the wrong interleaving, work stalls with progress available: a lost wakeup, and possibly deadlock.

Those wasted wakeups are the one blemish on the synchronized version: adding an item wakes everyone, though only consumers can act. With a single wait-set there's no way to wake just the consumers. Fixing that is exactly what Condition is for — but first, the lock it lives on.

synchronized vs ReentrantLock

Both give mutual exclusion — one thread in the critical section at a time — and both are reentrant (a thread holding the lock can re-acquire it without deadlocking itself). So why reach for ReentrantLock? For the flexibility it adds.

Locks and Conditions

Keep three things distinct, because they're easy to blur:

There is one lock guarding the whole queue — one gate, shared by put and take, since both touch the same data. A Condition is a different thing: not a lock, but a waiting room created from the lock. You can make several.

ReentrantLock lock = new ReentrantLock();      // ONE lock
Condition notFull  = lock.newCondition();      // room: "waiting for space"
Condition notEmpty = lock.newCondition();      // room: "waiting for an item"

The Condition operations mirror wait/notify exactly — same behaviour, just per-room:

The crossover

The one new idea: you await on your own condition, but signal the other one. A producer waits on notFull (it needs space) and, after adding an item, signals notEmpty to wake a consumer (there's now something to take). A consumer waits on notEmpty and, after removing an item, signals notFull to wake a producer (there's now room). You wake the side that your action just unblocked.

Building it with ReentrantLock

Same logic as before — same while guards, same modify-then-signal order — now with targeted signalling and manual locking.

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

class BoundedBlockingQueue {
    private final Queue<Message> q = new ArrayDeque<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull  = lock.newCondition();   // producers wait
    private final Condition notEmpty = lock.newCondition();   // consumers wait

    BoundedBlockingQueue(int capacity) {
        this.capacity = capacity;
    }

    void put(Message msg) throws InterruptedException {
        lock.lock();                            // acquire BEFORE the try
        try {
            while (q.size() >= capacity) {
                notFull.await();                // wait on my own condition
            }
            q.offer(msg);
            notEmpty.signal();                  // wake a consumer (the other side)
        } finally {
            lock.unlock();                      // always release, on every path
        }
    }

    Message take() throws InterruptedException {
        lock.lock();
        try {
            while (q.isEmpty()) {
                notEmpty.await();
            }
            Message msg = q.poll();
            notFull.signal();                   // wake a producer
            return msg;                         // finally still runs before return
        } finally {
            lock.unlock();
        }
    }
}

The mandatory pattern

lock.lock();
try {
    // everything done while holding the lock
} finally {
    lock.unlock();
}

And because producers and consumers now wait in separate rooms, signal() (wake one) is enough and precise — a notEmpty.signal() can only wake a consumer, so there's no wrong-thread risk and no wasted wakeups. The lost-wakeup problem from the synchronized version is gone by construction.

Running it

To see it work, fire several producers and consumers at a small-capacity queue. Balanced counts (equal puts and takes) ensure every thread completes and the program terminates.

class Message {
    int id; String content;
    Message(int id, String content) { this.id = id; this.content = content; }
}

public static void main(String[] args) throws InterruptedException {
    BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // small -> we see blocking
    List<Thread> threads = new ArrayList<>();

    for (int p = 0; p < 4; p++) {
        final int id = p;                              // snapshot for the lambda
        Thread t = new Thread(() -> {
            try { queue.put(new Message(id, "MC" + id)); }
            catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });
        threads.add(t); t.start();
    }
    for (int c = 0; c < 4; c++) {
        Thread t = new Thread(() -> {
            try { queue.take(); }
            catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });
        threads.add(t); t.start();
    }

    for (Thread t : threads) t.join();               // wait for all to finish
    System.out.println("All done.");
}

Run it and you'll see all items produced and consumed exactly once, in an unpredictable order (proof of real concurrency), the queue never exceeding capacity 2, and a clean exit after join(). To watch the blocking, drop capacity to 1 and add a print just before each wait()/await() — you'll see producers park when full and wake as consumers drain.

The complete program

Here is the whole thing in one file — the ReentrantLock version, a Message, and a main that prints what each thread does so you can watch the interleaving. Save it as BoundedBlockingQueueDemo.java and run it with a single command (JDK 11+).

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

class Message {
    final int id;
    final String content;
    Message(int id, String content) { this.id = id; this.content = content; }
}

class BoundedBlockingQueue {
    private final Queue<Message> q = new ArrayDeque<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull  = lock.newCondition();   // producers wait here
    private final Condition notEmpty = lock.newCondition();   // consumers wait here

    BoundedBlockingQueue(int capacity) { this.capacity = capacity; }

    void put(Message msg) throws InterruptedException {
        lock.lock();
        try {
            while (q.size() >= capacity) notFull.await();
            q.offer(msg);
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    Message take() throws InterruptedException {
        lock.lock();
        try {
            while (q.isEmpty()) notEmpty.await();
            Message msg = q.poll();
            notFull.signal();
            return msg;
        } finally {
            lock.unlock();
        }
    }
}

public class BoundedBlockingQueueDemo {
    public static void main(String[] args) throws InterruptedException {
        BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // small -> blocking is visible
        List<Thread> threads = new ArrayList<>();

        for (int p = 0; p < 4; p++) {
            final int id = p;
            Thread t = new Thread(() -> {
                try {
                    queue.put(new Message(id, "MC" + id));
                    System.out.println("produced  MC" + id);
                } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            });
            threads.add(t);
            t.start();
        }
        for (int c = 0; c < 4; c++) {
            Thread t = new Thread(() -> {
                try {
                    Message m = queue.take();
                    System.out.println("consumed  " + m.content);
                } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            });
            threads.add(t);
            t.start();
        }

        for (Thread t : threads) t.join();
        System.out.println("All done - queue never exceeded capacity 2.");
    }
}

Run it:

java BoundedBlockingQueueDemo.java

One run prints something like the following. The order changes on every run — that unpredictability is the proof that the threads really are running concurrently — but every message is produced and consumed exactly once, and the program always exits cleanly:

produced  MC1
produced  MC3
consumed  MC1
consumed  MC3
produced  MC2
produced  MC0
consumed  MC2
consumed  MC0
All done - queue never exceeded capacity 2.

Revision cheat sheet

The night before a concurrency round, read only this.

Threads

• new Thread(() -> {...}).start() — start() launches concurrently; run() does not (runs inline). join() waits for a thread to finish. No close()/end() — a thread ends when run() returns.
• wait vs sleep: wait() releases the lock and waits for a condition (until notified); sleep() keeps the lock and pauses for a set time (wakes itself).

Locks & waiting

• Every object has a monitor (lock). synchronized(obj) = one thread holds obj's monitor at a time. Which object you lock decides who competes.
• wait() releases the lock as it sleeps — so many threads can wait at once, and another thread can enter to change the condition.
• Woken threads must re-acquire the lock and re-check — one at a time.

The two rules that carry the problem

• while, not if, around every wait()/await(): many are woken, only some can proceed, so each must re-verify (plus spurious wakeups exist).
• notifyAll(), not notify(), on a shared monitor with different waiter types: notify() may wake the wrong kind and lose the signal (deadlock). notify() is only safe when all waiters are interchangeable.

synchronized → ReentrantLock

• Both: mutual exclusion, reentrant. synchronized auto-unlocks (safe, less code); ReentrantLock is manual — always lock() → try { } finally { unlock() }, or you deadlock on exception.
• The reason to switch: multiple wait-sets. One lock, many Conditions (lock.newCondition()).
• Lock = who executes. Condition = whether the state is ready. await/signal/signalAll mirror wait/notify/notifyAll.
• Crossover: await on your own condition, signal the other. Producer waits notFull, signals notEmpty; consumer waits notEmpty, signals notFull. With separate conditions, signal() (wake one) is precise — no wasted wakeups.

The shape of both solutions

• put: lock → while full, wait → offer → signal consumers → unlock.
• take: lock → while empty, wait → poll → signal producers → return → unlock.
• Storage is a plain ArrayDeque (only BlockingQueue is banned). take() must return the removed item.

Both implementations are complete and correct, and every line traces back to a principle above. If you spot an error or a cleaner framing, I'd like to hear it — that's how the next detail gets sharpened.