Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build a Blocking Queue

Build a Blocking Queue

You've already built a bounded producer–consumer buffer — one lock, two condition variables, correct under contention. A blocking queue is the general abstraction that buffer is one instance of: the thing ArrayBlockingQueue, LinkedBlockingQueue, and every language's "safe work queue" actually are. This lab pushes past the single-lock design into the one real engineering question a senior interviewer will ask next: your buffer works, but it doesn't scale — why not, and what do you do about it? The answer (splitting one lock into two) is exactly how the JDK's own LinkedBlockingQueue beats ArrayBlockingQueue under many-thread contention, and getting the split wrong reproduces a real, shipped-in-production failure mode: a permanently hung consumer with data sitting right there in the queue. Do the Bounded Producer–Consumer lab first if you haven't — this one assumes you already own the single-lock mechanism and is about to make you outgrow it.

1. The trap

You wire your single-lock bounded buffer into a real system: a thread pool with 32 worker threads calling take() and an ingest layer with several threads calling put(). It's correct — no corruption, no busy-wait — but under load, throughput plateaus far below what the hardware should give you. Profile it and the picture is obvious: every single put() and every single take() serialize through the same lock, even though a producer only ever touches the tail and a consumer only ever touches the head — two ends of the queue that, physically, almost never overlap. You've built a highway with two lanes and put one shared toll booth in the middle that every car from both lanes has to stop at. This is exactly why the JDK ships two blocking queue implementations, not one: ArrayBlockingQueue (single lock, what you built in the last lab) and LinkedBlockingQueue (two locks) — and why interviewers who've shipped concurrent systems will ask "how would you make this scale to more threads?" right after you get the basic version working.

There's a second, independent trap hiding in the API shape itself. If put() and take() are your only operations, any caller on a request path that calls queue.put(job) unconditionally is one dead or slow consumer away from that request thread blocking forever. That's not hypothetical — "downstream queue backs up, every request-handling thread ends up parked in put(), the thread pool exhausts, the whole service goes unresponsive" is a real, repeating production incident shape. A queue that only offers unconditional blocking is a queue that's one bad day away from a cascading outage. You need a way to say "wait, but not forever."

2. Scope it like a senior

Same discipline as the last lab, with the questions that actually differ this time:

3. Reason to the design

Attempt 0 — just split the single lock you already have. Your existing design is an array-backed ring buffer under one ReentrantLock. The obvious first idea: keep the array, but guard the head index with one lock and the tail index with another. Try to reason through put() under this scheme and it falls apart immediately — in a ring buffer, the tail index can wrap around and land in the same region of the array the head is reading from. The head and tail aren't just conceptually related, they're reading and writing the same backing array, so a "tail-only" lock can't actually protect the tail's writes from a concurrent head read near the wraparound boundary. Two locks on one shared array buys you nothing but a false sense of safety.

Attempt 1 — change the data structure, not just the locking. A linked list of nodes has a real seam: the head pointer and the tail pointer reference genuinely different memory (except for the single-node case). Enqueuing at the tail allocates a new node and links it after the current tail; dequeuing at the head unlinks the current head's successor. These two operations touch disjoint node references almost all of the time. Now a separate putLock (guards the tail pointer) and a separate takeLock (guards the head pointer) actually protect what they claim to protect. This is why LinkedBlockingQueue is linked, not array-backed — the data structure is chosen because it admits a clean two-lock split, not for any other reason.

The new problem this creates: how does either side know the size? With one lock, "is it full" and "is it empty" were trivial — you held the only lock that could change them. With two locks, a producer holding only putLock needs to know if the queue is empty (to decide whether to wake a consumer) without ever taking takeLock for the common case, and vice versa. The fix is a single AtomicInteger count shared by both sides, updated with atomic getAndIncrement/getAndDecrement — a small piece of genuinely shared, lock-free state that both locks' critical sections can read cheaply, so 99% of a put() or take() never has to touch the other side's lock at all.

The one moment the two sides MUST talk to each other. If the queue is empty and a producer adds the first item, no consumer waiting on takeLock's notEmpty condition can ever find out — producers don't hold that lock, so they can't call notEmpty.signal() without briefly acquiring takeLock too. This has to happen exactly on the empty→non-empty transition (count goes 0→1) and the full→non-full transition (count goes capacity→capacity-1) — every other put/take can stay entirely on its own side. Get this cross-lock signal right and you have real two-lock throughput. Drop it, even by one line, and you get a permanent hang — that's Movement 5.

4. Build it — milestones

Attempt each milestone before reading the reference implementation. The reveal is positioned after the tests on purpose.

Reference implementation — Java (linked, two-lock, ArrayBlockingQueue's sibling LinkedBlockingQueue)

This is the real mechanism inside java.util.concurrent.LinkedBlockingQueue, written out so you own every line. The comments mark the two lines that are the entire lesson: the atomic count read/write, and the cross-lock signal that only fires on a transition.

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/** Separate locks for the head (takers) and the tail (putters), joined only
 *  when the queue crosses empty<->non-empty or full<->non-full, so a
 *  producer and a consumer touching opposite ends never fight over one lock. */
public final class TwoLockBlockingQueue<T> {
    private static final class Node<T> {
        T item;
        Node<T> next;
        Node(T item) { this.item = item; }
    }

    private final int capacity;
    private final AtomicInteger count = new AtomicInteger(0);   // shared, lock-free size

    private Node<T> head;   // dummy; head.next is the real first node
    private Node<T> tail;

    private final ReentrantLock putLock = new ReentrantLock();
    private final Condition notFull = putLock.newCondition();

    private final ReentrantLock takeLock = new ReentrantLock();
    private final Condition notEmpty = takeLock.newCondition();

    public TwoLockBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        head = tail = new Node<>(null);
    }

    private void enqueue(Node<T> node) { tail.next = node; tail = node; }

    private T dequeue() {
        Node<T> first = head.next;
        head.next = head;          // help GC
        head = first;
        T item = first.item;
        first.item = null;
        return item;
    }

    /** Wake ONE waiting taker. Only called on the empty -> non-empty transition. */
    private void signalNotEmpty() {
        takeLock.lock();
        try { notEmpty.signal(); } finally { takeLock.unlock(); }
    }

    /** Wake ONE waiting putter. Only called on the full -> non-full transition. */
    private void signalNotFull() {
        putLock.lock();
        try { notFull.signal(); } finally { putLock.unlock(); }
    }

    public void put(T item) throws InterruptedException {
        if (item == null) throw new NullPointerException();
        int c;
        Node<T> node = new Node<>(item);
        putLock.lockInterruptibly();
        try {
            while (count.get() == capacity) {          // while, not if -- same rule as always
                notFull.await();
            }
            enqueue(node);
            c = count.getAndIncrement();                 // c = count BEFORE this put
            if (c + 1 < capacity) notFull.signal();       // still room -- wake next producer, same lock
        } finally {
            putLock.unlock();
        }
        // THE line that must not be dropped -- Movement 5 shows what happens without it.
        if (c == 0) signalNotEmpty();
    }

    public T take() throws InterruptedException {
        T item;
        int c;
        takeLock.lockInterruptibly();
        try {
            while (count.get() == 0) {
                notEmpty.await();
            }
            item = dequeue();
            c = count.getAndDecrement();                 // c = count BEFORE this take
            if (c > 1) notEmpty.signal();                 // more left -- wake next consumer, same lock
        } finally {
            takeLock.unlock();
        }
        if (c == capacity) signalNotFull();               // full -- non-full: wake a producer
        return item;
    }

    /** M3: bounded wait instead of blocking forever. */
    public boolean offer(T item, long timeout, TimeUnit unit) throws InterruptedException {
        if (item == null) throw new NullPointerException();
        long nanos = unit.toNanos(timeout);
        int c = -1;
        putLock.lockInterruptibly();
        try {
            while (count.get() == capacity) {
                if (nanos <= 0L) return false;
                nanos = notFull.awaitNanos(nanos);
            }
            enqueue(new Node<>(item));
            c = count.getAndIncrement();
            if (c + 1 < capacity) notFull.signal();
        } finally {
            putLock.unlock();
        }
        if (c == 0) signalNotEmpty();
        return true;
    }

    public T poll(long timeout, TimeUnit unit) throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        T item = null;
        int c = -1;
        takeLock.lockInterruptibly();
        try {
            while (count.get() == 0) {
                if (nanos <= 0L) return null;
                nanos = notEmpty.awaitNanos(nanos);
            }
            item = dequeue();
            c = count.getAndDecrement();
            if (c > 1) notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        if (c == capacity) signalNotFull();
        return item;
    }

    public int size() { return count.get(); }
}

Compiled and executed with javac/java before publishing — no warnings, no errors.

Reference implementation — Go (channel idiom AND a two-lock sync.Cond idiom)

First, the idiomatic Go answer — a buffered channel's send/receive blocking is the queue, and the runtime owns the wake-up protocol so you can't get the loop wrong:

package blockingqueue

import (
    "context"
    "errors"
)

// ChanQueue is a bounded blocking queue built directly on a buffered
// channel -- send/receive blocking on the channel IS the queue. No lock,
// no condition variable, and the runtime can never get the wake-up wrong.
type ChanQueue[T any] struct {
    ch chan T
}

func NewChanQueue[T any](capacity int) *ChanQueue[T] {
    return &ChanQueue[T]{ch: make(chan T, capacity)}
}

// Put blocks until there is room.
func (q *ChanQueue[T]) Put(item T) { q.ch <- item }

// Take blocks until an item is available.
func (q *ChanQueue[T]) Take() T { return <-q.ch }

var ErrTimeout = errors.New("blockingqueue: timed out")

// Offer is Put with a deadline -- select gives this for free, no manual
// awaitNanos-style bookkeeping needed.
func (q *ChanQueue[T]) Offer(ctx context.Context, item T) error {
    select {
    case q.ch <- item:
        return nil
    case <-ctx.Done():
        return ErrTimeout
    }
}

// Poll is Take with a deadline.
func (q *ChanQueue[T]) Poll(ctx context.Context) (T, error) {
    var zero T
    select {
    case v := <-q.ch:
        return v, nil
    case <-ctx.Done():
        return zero, ErrTimeout
    }
}

func (q *ChanQueue[T]) Len() int { return len(q.ch) }

Second, the manual idiom — a two-lock sync.Cond design that mirrors the Java LinkedBlockingQueue mechanism line for line, for the case where you need Java-style tunable wake behavior rather than the channel runtime's built-in one:

package blockingqueue

import (
    "sync"
    "sync/atomic"
)

type node[T any] struct {
    item T
    next *node[T]
}

// TwoLockQueue mirrors java.util.concurrent.LinkedBlockingQueue: a separate
// lock for the head (takers) and the tail (putters), joined only when the
// queue crosses empty<->non-empty or full<->non-full.
type TwoLockQueue[T any] struct {
    capacity int
    count    atomic.Int64

    putMu   sync.Mutex
    notFull *sync.Cond
    tail    *node[T]

    takeMu   sync.Mutex
    notEmpty *sync.Cond
    head     *node[T]
}

func NewTwoLockQueue[T any](capacity int) *TwoLockQueue[T] {
    q := &TwoLockQueue[T]{capacity: capacity}
    dummy := &node[T]{}
    q.head = dummy
    q.tail = dummy
    q.notFull = sync.NewCond(&q.putMu)
    q.notEmpty = sync.NewCond(&q.takeMu)
    return q
}

func (q *TwoLockQueue[T]) signalNotEmpty() {
    q.takeMu.Lock()
    q.notEmpty.Signal()
    q.takeMu.Unlock()
}

func (q *TwoLockQueue[T]) signalNotFull() {
    q.putMu.Lock()
    q.notFull.Signal()
    q.putMu.Unlock()
}

func (q *TwoLockQueue[T]) Put(item T) {
    n := &node[T]{item: item}
    var c int64

    q.putMu.Lock()
    for q.count.Load() == int64(q.capacity) { // for, not if -- must recheck after Wait
        q.notFull.Wait()
    }
    q.tail.next = n
    q.tail = n
    c = q.count.Add(1) - 1 // c = count BEFORE this put (mirrors getAndIncrement)
    if c+1 < int64(q.capacity) {
        q.notFull.Signal()
    }
    q.putMu.Unlock()

    // THE line that must not be dropped -- Movement 5 shows what happens without it.
    if c == 0 {
        q.signalNotEmpty()
    }
}

func (q *TwoLockQueue[T]) Take() T {
    var item T
    var c int64

    q.takeMu.Lock()
    for q.count.Load() == 0 {
        q.notEmpty.Wait()
    }
    first := q.head.next
    item = first.item
    var zero T
    first.item = zero
    q.head = first
    c = q.count.Add(-1) + 1 // c = count BEFORE this take (mirrors getAndDecrement)
    if c > 1 {
        q.notEmpty.Signal()
    }
    q.takeMu.Unlock()

    if c == int64(q.capacity) {
        q.signalNotFull()
    }
    return item
}

func (q *TwoLockQueue[T]) Len() int { return int(q.count.Load()) }

Both files build clean under go build ./... and go vet ./..., and both were exercised end to end (including under go test -race) before writing this page. Note what's missing from the sync.Cond version: a timeout. Go's sync.Cond gives you Wait/Signal/Broadcast and nothing else — there's no awaitNanos equivalent. A production Go offer/poll with a deadline on this design needs a second goroutine racing a timer against the wait, which is exactly why idiomatic Go reaches for the channel version the moment timeouts matter.

5. Break it — the test that fails

Delete exactly one thing from put(): the cross-lock signal on the empty→non-empty transition. Everything else stays identical — the while/for loop is still there, count is still atomic, the item is still genuinely enqueued. Scenario: a consumer is already parked in take() on an empty queue; a producer calls put() exactly once.

// Java -- BuggyTwoLockBlockingQueue.put(), the ONLY change from the correct version:
public void put(T item) throws InterruptedException {
    putLock.lockInterruptibly();
    try {
        while (count.get() == capacity) notFull.await();
        enqueue(new Node<>(item));
        int c = count.getAndIncrement();
        if (c + 1 < capacity) notFull.signal();
        // BUG: no "if (c == 0) signalNotEmpty()" here. A waiting taker on an
        // empty queue is NEVER told the queue is no longer empty.
    } finally {
        putLock.unlock();
    }
}

Run it (consumer parks first, then the producer puts one item):

[BUGGY]   queue.size() after put = 1
[BUGGY]   consumer still blocked after 2s? true
[BUGGY]   item ever received by consumer? null
[BUGGY]   BUG REPRODUCED: item is in the queue, consumer is parked forever.

Read that output carefully: size() == 1. The item is really there. Nothing is corrupted — count is correct, the linked list is correct, a second take() call would succeed immediately. The bug isn't a data-structure bug at all — it's a communication bug. The consumer parked in notEmpty.await() is waiting on takeLock's condition, and nothing on the put side ever acquired takeLock to signal it. This is the two-lock design's characteristic failure mode: unlike the single-lock buffer's if-vs-while bug (which corrupts an invariant and is loud), the missing cross-lock signal produces total silence — a permanent hang with perfectly correct internal state, the kind of bug that looks like "the consumer thread must be stuck on something else" in a stack dump, not "the queue is broken."

The Go version reproduces identically and deterministically under go test -race:

// $ go test -race -run TestMissingSignalHangsForever -v
=== RUN   TestMissingSignalHangsForever
    blockingqueue_test.go:28: BUG REPRODUCED: item is in the queue (Len()=1) but the consumer is parked forever
--- PASS: TestMissingSignalHangsForever (1.10s)

The fix is putting the one deleted line back: if (c == 0) signalNotEmpty(); in Java, if c == 0 { q.signalNotEmpty() } in Go. Re-running the identical scenario against the correct queue:

[CORRECT] queue.size() after take = 0
[CORRECT] consumer still blocked?  false
[CORRECT] item received by consumer = job-1
[CORRECT] woke and delivered in ~3ms (well under the 2s window)

// Go: blockingqueue_test.go:56: CORRECT: consumer received "job-1" after 58.542µs (Len()=0)

The entire lesson of this lab in one sentence: splitting a lock buys you throughput, but every transition boundary the split creates is a place where a signal can silently fail to cross — and unlike a corrupted counter, a missing signal doesn't announce itself. It just waits, forever, for a wake-up that was never coming.

6. Optimise — with trade-offs

DesignThroughput under high fan-outComplexityOrderingUse when
Array-backed, single lock (ArrayBlockingQueue, the sibling lab)Moderate — put/take always contend on one lockLowest — one lock, two conditions, doneStrict FIFOLow-to-moderate thread counts on each side; simplicity and a smaller memory footprint (no per-node allocation) matter more than peak throughput
Linked, two-lock (LinkedBlockingQueue, this lab)High — put and take rarely contend at allModerate — two locks, a shared atomic counter, and one delicate cross-lock signal to get rightStrict FIFOMany producer and consumer threads sharing one queue (thread pools, work queues) where the single lock has been profiled as the bottleneck
SynchronousQueue (zero-capacity handoff)High for direct handoff patterns, but no buffering at all — every put waits for a matching takeModerate — a genuinely different rendezvous algorithm, not "capacity=1"N/A — pairs producer and consumer 1:1Direct thread-to-thread handoff where buffering would hide back-pressure you want to feel immediately — e.g. Executors.newCachedThreadPool()'s internal work queue
Go buffered channelHigh, comparable to the two-lock designLowest of the "real" designs — the runtime owns the wait/notify protocol entirelyStrict FIFOAny Go program; prefer it over hand-rolled sync.Cond unless you need a wait condition select can't express (see the drilling section)
Heap-ordered / DelayQueue (M4 variant)Lower — every op touches a heap (O(log n)) instead of O(1) list append/removalHighest — take() must recompute and re-arm its wait on every wake, not just check a booleanBy priority or deadline, not arrival orderScheduled/delayed work (retry backoff, timer wheels, "run this at time T") where FIFO isn't the right order at all

The real judgment call: don't reach for two locks by default. A single lock is simpler, has less to get wrong, and is fast enough for the overwhelming majority of real workloads — the JDK ships ArrayBlockingQueue as the "just works" default for exactly this reason. Split the lock only after you've profiled contention on the single lock as the actual bottleneck, because the two-lock design trades a simple, hard-to-misuse mechanism for a faster one with a sharp, silent edge: the cross-lock signal you just watched fail in Movement 5. And don't confuse "bounded queue with capacity 1" with SynchronousQueue — the former buffers one item and lets a producer return before any consumer has acted; the latter is a true rendezvous where put() doesn't return until a take() has taken the exact item, a different guarantee entirely.

7. Defend under drilling

8. You can now defend

Re-authored/Deepened for this guide. Reference code compiled and executed (javac/java; go build, go vet, go test -race) before publishing; the break-it test reproduces the missing cross-lock-signal hang deterministically on every run. See also: the Bounded Producer–Consumer lab (the single-lock design this one generalizes) and Condition Variables — wait, notify & the while-loop trap.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build a Blocking Queue? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build a Blocking Queue** (Hands-On Builds) and want to truly understand it. Explain Build a Blocking Queue from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build a Blocking Queue** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build a Blocking Queue** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build a Blocking Queue** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Build a Thread PoolBuild a Concurrent LRU Cache →