AlgoInsight

Free lesson · Concurrency Interview Mastery

Designing a Thread-Safe Blocking Queue

Hard10 min readconcurrencymultithreadinginterview-prep

A blocking queue is the bounded buffer from Module 8, packaged as a reusable data structure - put blocks when the queue is full, take blocks when it's empty, and everything is thread-safe and FIFO. It's the single most-used concurrent data structure in practice: every thread pool's task queue, every producer-consumer pipeline, every hand-off between threads is a blocking queue. Designing one is a focused exercise in condition-variable coordination - using two conditions (notFull, notEmpty) so producers and consumers wait and wake each other correctly - and it introduces a key concurrency-engineering trick: the two-lock design that lets put and take proceed concurrently by separating the head and tail of the queue. We'll build the single-lock version first, then the two-lock refinement, and pin down the condition-variable discipline that makes it correct.

Requirements and API

A bounded, thread-safe FIFO queue:

interface BlockingQueue<E>:
    put(item: E)        # add to tail; BLOCKS if the queue is full
    take() -> E         # remove from head; BLOCKS if the queue is empty
    # optional: offer(item, timeout), poll(timeout), size()

The requirements:

This is the canonical producer-consumer buffer, now as a first-class data structure with proper blocking.

The single-lock design: one lock, two conditions

The straightforward design uses a single lock plus two condition variables - notFull (producers wait here when full) and notEmpty (consumers wait here when empty):

items   = array of capacity        # circular buffer
count   = 0                        # current number of items
head, tail = 0, 0
lock    = ReentrantLock()
notFull  = lock.newCondition()     # signaled when an item is removed (space available)
notEmpty = lock.newCondition()     # signaled when an item is added (item available)

function put(item):
    lock.lock()
    try:
        while count == capacity:       # WHILE-loop predicate (not if!)
            notFull.await()            # wait for space (releases lock while waiting)
        items[tail] = item
        tail = (tail + 1) % capacity
        count += 1
        notEmpty.signal()              # wake a waiting consumer
    finally:
        lock.unlock()

function take():
    lock.lock()
    try:
        while count == 0:              # WHILE-loop predicate
            notEmpty.await()           # wait for an item
        item = items[head]
        head = (head + 1) % capacity
        count -= 1
        notFull.signal()               # wake a waiting producer
        return item
    finally:
        lock.unlock()

The mechanism is the bounded-buffer logic with condition variables. A put acquires the lock and checks count == capacity in a while loop - if full, it awaits on notFull, which atomically releases the lock and sleeps until signaled. When space appears (a consumer removed an item and signaled notFull), the producer wakes, re-checks the predicate (hence the while, not if - handling spurious wakeups and the possibility that another producer grabbed the space first), and proceeds to enqueue. After enqueuing, it signals notEmpty to wake any consumer waiting for an item. take is the mirror image: wait on notEmpty while empty, dequeue, signal notFull. The two conditions are essential - a single condition would force producers and consumers to wait on the same queue and risk waking the wrong kind of thread (a producer waking another producer when an item, not space, became available). Separate notFull/notEmpty conditions wake exactly the right waiters.

flowchart TD
    PUT["put(item)"] --> PL["lock"]
    PL --> PFULL{"count == capacity?"}
    PFULL -->|"yes (while)"| PWAIT["notFull.await()<br/>(release lock + sleep)"]
    PWAIT --> PFULL
    PFULL -->|no| PENQ["enqueue at tail; count++"]
    PENQ --> PSIG["notEmpty.signal()"] --> PUL["unlock"]
    TAKE["take()"] --> TL["lock"]
    TL --> TEMPTY{"count == 0?"}
    TEMPTY -->|"yes (while)"| TWAIT["notEmpty.await()<br/>(release lock + sleep)"]
    TWAIT --> TEMPTY
    TEMPTY -->|no| TDEQ["dequeue at head; count--"]
    TDEQ --> TSIG["notFull.signal()"] --> TUL["unlock"]
    note["TWO conditions: notFull (producers wait), notEmpty (consumers wait).<br/>WHILE-loop predicates (spurious wakeups). put signals notEmpty; take signals notFull."]

This flowchart shows a single-lock blocking queue. A put operation acquires the lock, then checks in a while loop whether the queue is full. If full, it awaits on the notFull condition, which atomically releases the lock and sleeps until signaled. When woken, it re-checks the predicate in the loop - using while, not if, to handle spurious wakeups and the case where another producer took the space. Once there is room, it enqueues at the tail, increments the count, and signals the notEmpty condition to wake a waiting consumer, then unlocks. A take operation mirrors this: it waits on notEmpty while the queue is empty, then dequeues from the head, signals notFull to wake a waiting producer, and unlocks. Two separate conditions are essential: notFull for producers waiting on space and notEmpty for consumers waiting on items, so that signaling wakes exactly the right kind of waiter.

The two-lock design: concurrent put and take

The single-lock version has a limitation: put and take use the same lock, so a producer and a consumer can't operate simultaneously even though they touch different ends of the queue (tail vs. head). The two-lock design (Java's LinkedBlockingQueue) fixes this by using a linked-node queue with separate locks for the head and the tail:

# Linked queue with a putLock (guards tail) and a takeLock (guards head)
putLock  = ReentrantLock(); notFull  = putLock.newCondition()
takeLock = ReentrantLock(); notEmpty = takeLock.newCondition()
count    = AtomicInteger(0)            # shared count, updated atomically

function put(item):
    putLock.lock()
    try:
        while count.get() == capacity: notFull.await()
        enqueue(item)                  # link at tail (only putLock needed)
        c = count.getAndIncrement()
        if c + 1 < capacity: notFull.signal()      # still room -> wake another producer
    finally: putLock.unlock()
    if c == 0: signalNotEmpty()        # queue WAS empty -> a consumer may be waiting

function take():
    takeLock.lock()
    try:
        while count.get() == 0: notEmpty.await()
        item = dequeue()               # unlink at head (only takeLock needed)
        c = count.getAndDecrement()
        if c > 1: notEmpty.signal()                # still items -> wake another consumer
        return item
    finally: takeLock.unlock()
    if c == capacity: signalNotFull()  # queue WAS full -> a producer may be waiting

The insight: a linked queue has a head (where take removes) and a tail (where put adds), and as long as the queue isn't empty, these are different nodes - so put (modifying the tail) and take (modifying the head) can proceed concurrently under separate locks. putLock guards the tail and the notFull condition; takeLock guards the head and the notEmpty condition. A producer and a consumer can run at the same time, roughly doubling throughput under balanced producer/consumer load. The subtlety is the shared count: both put and take modify it (it's an AtomicInteger for safe cross-lock updates), and the cross-condition signaling is careful - when put makes the queue non-empty (was empty, c == 0), it must signal notEmpty (held by takeLock), acquiring takeLock briefly to do so; symmetrically take signals notFull when it frees space in a full queue. This cross-lock coordination is the price of the extra concurrency, and getting it exactly right (signaling only when transitioning across the empty/full boundary) is the delicate part.

Important: A blocking queue is the bounded buffer as a data structure: put blocks when full, take blocks when empty, FIFO. Single-lock design: one lock + two conditions - notFull (producers wait) and notEmpty (consumers wait); put waits on notFull in a while loop (spurious wakeups, Module 6), enqueues, signals notEmpty; take mirrors it. Two conditions wake exactly the right waiter. Two-lock design (LinkedBlockingQueue): a linked queue with separate putLock (tail) and takeLock (head), so put and take run concurrently (different ends), with a shared AtomicInteger count and careful cross-lock signaling only on the empty→non-empty and full→non-full transitions. Single-lock is simpler; two-lock roughly doubles throughput under balanced load. while-loop predicates and the two-condition (or two-lock) structure are the standout points.

Trade-offs and connections

A thorough answer weighs the designs. Single-lock (array-backed, ArrayBlockingQueue) is simpler and has predictable memory (fixed array), but serializes put and take. Two-lock (linked, LinkedBlockingQueue) allows concurrent put/take for higher throughput, at the cost of per-node allocation and trickier cross-lock signaling. Fairness: the lock can be fair (FIFO waiter ordering) or not - fair locks prevent waiter starvation but reduce throughput. The while-loop predicate is non-negotiable: condition waits can wake spuriously (Module 6), and even a correct signal may race with another thread that consumes the space/item first, so the predicate must be re-checked in a loop, never with a bare if. Connection to the bounded buffer: this is the Module 8 bounded buffer, which is why the structure is familiar - the new content here is the data-structure packaging, the two-condition discipline, and the two-lock concurrency trick. For an unbounded queue, drop the notFull condition (put never blocks); for a SynchronousQueue (zero capacity, direct hand-off), every put waits for a take. The design lesson: one lock + two conditions is the clean baseline; the two-lock split is the throughput optimization; while-loop predicates are mandatory. One more practical note worth raising: the choice between the array-backed single-lock queue and the linked two-lock queue isn't only about throughput - the array version pre-allocates a fixed buffer (predictable, bounded memory, cache-friendly contiguous storage, no per-item allocation), while the linked version allocates a node per item (more GC pressure, pointer-chasing) but allows the concurrent put/take. So under low-to-moderate contention or where memory predictability matters, the simpler single-lock array queue is often the better engineering choice despite its lower theoretical concurrency; the two-lock linked queue earns its complexity only when producer/consumer throughput is genuinely the bottleneck. Matching the implementation to the actual contention and memory profile - rather than reflexively reaching for the "more concurrent" design - is the kind of judgment that distinguishes someone who understands these structures from someone who has merely memorized them.

A worked scenario: producers and consumers blocking

Tracing a capacity-2 single-lock queue shows the blocking and signaling. Start empty (count=0):

Consumer C1 take(): lock; count==0 -> notEmpty.await() (releases lock, SLEEPS)
Producer P1 put(a): lock; count(0)<2 -> enqueue a; count=1; notEmpty.signal(); unlock
   -> C1 wakes, re-acquires lock, RE-CHECKS count==0? no (count=1) -> proceeds
C1 (resumes): dequeue a; count=0; notFull.signal(); unlock; returns a
Producer P2 put(b): lock; enqueue b; count=1; notEmpty.signal(); unlock
Producer P3 put(c): lock; enqueue c; count=2; notEmpty.signal(); unlock   [FULL]
Producer P4 put(d): lock; count==2 -> notFull.await() (releases lock, SLEEPS)
Consumer C2 take(): lock; dequeue b; count=1; notFull.signal(); unlock; returns b
   -> P4 wakes, re-checks count==2? no (count=1) -> enqueue d; count=2; notEmpty.signal(); unlock

Follow the blocking and the re-checks. C1 arrives first to an empty queue and blocks on notEmpty; when P1 enqueues and signals, C1 wakes, re-checks the predicate (count == 0? now no), and proceeds - the re-check is what the while loop provides. Later, when the queue is full (count=2), P4 blocks on notFull; when C2 dequeues and signals notFull, P4 wakes, re-checks count == capacity (now false), and enqueues. Notice each operation signals the opposite condition (put→notEmpty, take→notFull), so producers wake consumers and vice versa - and the re-check after every wakeup guards against both spurious wakeups and the case where another thread of the same kind grabbed the slot first. The blocking is genuine (the threads sleep, consuming no CPU, until signaled), and the FIFO order is preserved by the circular buffer's head/tail advancement.

Note: The blocking queue is worth recognizing as the most used concurrent data structure in real systems - and seeing how it ties the whole course together. It is the bounded buffer (Module 8) made concrete; it is the task queue inside every thread pool (Module 7); it is the inter-stage buffer in every pipeline; it is the per-subscriber inbox in the pub-sub system (Module 9). When you call ExecutorService.submit, the task lands in a blocking queue that worker threads take from. When you wire two concurrent components together, a blocking queue between them provides both the hand-off and the backpressure (full→block) or the buffering. This ubiquity is why understanding its internals matters even though you'll almost always use the library implementation (ArrayBlockingQueue, LinkedBlockingQueue): knowing that the single-lock version serializes put/take while the two-lock version parallelizes them lets you choose the right one (single-lock for simplicity and predictable memory; two-lock for throughput under balanced producer/consumer load); knowing the while-loop and two-condition discipline lets you reason about correctness and debug subtle stalls; and knowing it's "just" a bounded buffer with proper blocking demystifies an enormous swath of concurrent infrastructure. The transferable lesson: the highest-leverage concurrent data structure to understand cold is the one you use constantly, and for most engineers that's the blocking queue - master its two designs and their trade-offs, and a large fraction of real concurrent systems becomes legible.

The interview angle

Interview: "Design a blocking queue" is a common concurrent-data-structure question (and a natural follow-up to the bounded buffer). The expected core: a lock + two conditions (notFull, notEmpty), put/take with while-loop predicates, signaling the opposite condition. Distinguishing points: (1) two conditions (not one) so the right waiters wake, and why a single condition is wrong (could wake a producer when an item, not space, is available); (2) while not if for the predicate - spurious wakeups and lost races - the classic bug; (3) the two-lock design (putLock/takeLock, separate head/tail) for concurrent put/take, with shared AtomicInteger count and careful cross-lock signaling - the depth signal; (4) connecting it to the bounded buffer / producer-consumer; (5) variants (unbounded, synchronous, fairness). Follow-ups push on the two-lock signaling and the while-loop necessity. The two-condition structure, the while-loop discipline, and the two-lock optimization are the standout signals.

Quick reference

The single most-used concurrent data structure in practice - the bounded buffer packaged as a reusable type, with proper blocking semantics built on two condition variables, and a two-lock variant that lets enqueue and dequeue run concurrently:

BLOCKING QUEUE: bounded FIFO; put BLOCKS when full, take BLOCKS when empty; thread-safe
  = the bounded buffer (Module 8) as a reusable data structure

SINGLE-LOCK DESIGN (one lock + TWO conditions):
  notFull (producers wait), notEmpty (consumers wait)
  put(x):  lock; while count==capacity: notFull.await(); enqueue; count++;
           notEmpty.signal(); unlock
  take():  lock; while count==0: notEmpty.await(); dequeue; count--;
           notFull.signal(); unlock
  -> TWO conditions wake exactly the right waiter; WHILE-loop predicate (spurious wakeups!)

TWO-LOCK DESIGN (LinkedBlockingQueue - concurrent put + take):
  putLock guards TAIL + notFull;  takeLock guards HEAD + notEmpty;  count = AtomicInteger
  -> put (tail) and take (head) run CONCURRENTLY (different ends) -> ~2x throughput
  -> cross-lock signaling ONLY on transitions: put signals notEmpty when WAS empty (c==0);
     take signals notFull when WAS full (c==capacity)

KEY POINTS:
  - WHILE not IF on the predicate (spurious wakeups + lost races) -- non-negotiable
  - TWO conditions (not one) -> wake the right kind of waiter
  - single-lock (array) simpler; two-lock (linked) higher concurrency
  variants: unbounded (no notFull), synchronous (0 capacity), fair vs unfair lock

The blocking queue showcased condition-variable coordination and the two-lock trick. The next structure trades exactness for space - a concurrent Bloom filter - where the probabilistic, append-only nature enables a remarkably lock-free design.

Back to Concurrency Interview Mastery