Free lesson · Concurrency Interview Mastery

Exercise: Design a Thread-Safe Blocking Queue

Hard6 min readconcurrencymultithreadinginterview-prep

This exercise builds the single-lock blocking queue, refines to the two-lock design, and diagnoses the if-vs-while and wrong-condition bugs. Reason each through before the solution - the goal is to wield two conditions correctly with while-loop predicates, and to see how separate head/tail locks enable concurrent put and take.

Important: Two anchors: use two conditions (notFull, notEmpty) and re-check the predicate in a while loop (spurious wakeups and lost races), and separating the head lock from the tail lock lets put and take run concurrently (they touch different ends), at the cost of careful cross-lock signaling.

Part 1 - Single-lock, two-condition queue

Your task: Implement put and take with one lock and two conditions on a bounded circular buffer. Why two conditions, and why a while loop?

lock, notFull = lock.newCondition(), notEmpty = lock.newCondition(), circular items, count. 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 so producers and consumers wake the right kind of waiter; while because waits can wake spuriously and another thread may take the space/item first. </details>

Part 2 - Two-lock design

Your task: Refine to separate putLock (tail) and takeLock (head) so put and take run concurrently. What's the tricky part?

Linked queue; putLock guards the tail + notFull, takeLock guards the head + notEmpty, count = AtomicInteger. put/take operate on different ends under different locks → concurrent. Tricky part: the shared count (atomic) and cross-lock signaling - put signals notEmpty (under takeLock) only when the queue was empty (c == 0); take signals notFull only when it was full. Signal across locks only on the empty↔non-empty / full↔non-full transitions. </details>

Part 3 - Find the bugs

// Bug A - if instead of while:
function take():
    lock.lock()
    try:
        if count == 0:                  // <-- if, not while
            notEmpty.await()
        item = dequeue(); count -= 1
        notFull.signal()
        return item
    finally: lock.unlock()

// Bug B - one condition:
condition = lock.newCondition()         // <-- single condition for both
function put(x):  lock; while full: condition.await(); enqueue; condition.signal(); unlock
function take():  lock; while empty: condition.await(); dequeue; condition.signal(); unlock

Your task: Identify the predicate bug in A and the signaling bug in B.

Bug A: with if, a thread woken from await proceeds without re-checking count == 0. It can wake spuriously, or another consumer may have taken the only item between the signal and this thread re-acquiring the lock - so it dequeues from an empty queue (corruption/error). Fix: while count == 0. Bug B: a single condition means put and take both wait on and signal the same condition, so signal() may wake the wrong kind of waiter - e.g., after a put, the signal could wake another blocked producer (who still can't proceed if full) instead of a waiting consumer, leading to missed wakeups / stalls. Fix: two conditions (notFull, notEmpty); or use signalAll (wasteful). Two conditions wake the right waiters precisely. </details>

Solution

Part 1 - Single-lock, two-condition queue

items = array(capacity); count = 0; head = 0; tail = 0
lock = ReentrantLock(); notFull = lock.newCondition(); notEmpty = lock.newCondition()

function put(item):
    lock.lock()
    try:
        while count == capacity:           # WHILE
            notFull.await()
        items[tail] = item; tail = (tail + 1) % capacity; count += 1
        notEmpty.signal()                  # wake a consumer
    finally: lock.unlock()

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

Two conditions (notFull, notEmpty) let producers and consumers wait separately, so signaling wakes exactly the right kind of waiter: put signals notEmpty (waking a consumer who can now take), take signals notFull (waking a producer who can now put). while loop because await can return spuriously (Module 6) and, more importantly, between the signal and the woken thread re-acquiring the lock, another thread may have consumed the space/item - so the predicate must be re-verified, not assumed. The circular buffer gives O(1) enqueue/dequeue with fixed memory.

Part 2 - Two-lock design

putLock = ReentrantLock(); notFull = putLock.newCondition()
takeLock = ReentrantLock(); notEmpty = takeLock.newCondition()
count = AtomicInteger(0)        # shared, atomic

function put(item):
    putLock.lock()
    try:
        while count.get() == capacity: notFull.await()
        enqueueAtTail(item)                       # only the tail -> only putLock
        c = count.getAndIncrement()
        if c + 1 < capacity: notFull.signal()     # room remains -> wake another producer
    finally: putLock.unlock()
    if c == 0: signalNotEmpty()                   # WAS empty -> wake a consumer (acquire takeLock)

function take():
    takeLock.lock()
    try:
        while count.get() == 0: notEmpty.await()
        item = dequeueAtHead()                     # only the head -> only takeLock
        c = count.getAndDecrement()
        if c > 1: notEmpty.signal()                # items remain -> wake another consumer
        return item
    finally: takeLock.unlock()
    if c == capacity: signalNotFull()             # WAS full -> wake a producer (acquire putLock)

A linked queue has a head (take end) and a tail (put end); when non-empty these are different nodes, so put (tail) and take (head) can run concurrently under separate putLock/takeLock - roughly doubling throughput under balanced load. The tricky part is the shared count (an AtomicInteger, since both locks touch it) and the cross-lock signaling: put only needs to wake a consumer when the queue transitions from empty (c == 0), and take only wakes a producer when it transitions from full - signaling across the other lock only on these boundary transitions, to avoid unnecessary cross-lock contention. Getting that boundary signaling exactly right is the delicate part of the two-lock design.

Part 3 - The bugs

Bug A - if instead of while. After notEmpty.await() returns, the code proceeds directly to dequeue without re-checking count == 0. Two failure modes: (1) spurious wakeup - await can return without a signal (Module 6), so count may still be 0, and the thread dequeues from an empty queue. (2) lost race - even with a real signal, between the signal and this thread re-acquiring the lock, another consumer may have taken the only item, so count is 0 again when this thread proceeds. Either way, dequeuing an empty queue corrupts state or returns garbage. The fix is while count == 0 - re-check the predicate after every wakeup and wait again if it's still unsatisfied. This is the canonical condition-variable bug, and the reason "always wait in a while loop" is an iron rule.

Bug B - a single condition. With one shared condition, both producers (waiting for space) and consumers (waiting for items) sleep on the same condition queue, and a signal() wakes an arbitrary one. After a put enqueues and signals, the signal might wake another blocked producer (who, if the queue is now full again or was woken for the wrong reason, just goes back to sleep) instead of a waiting consumer - so the consumer that should have been woken isn't, and may stall indefinitely (a lost wakeup). The fix is two conditions: put signals notEmpty (only consumers wait there) and take signals notFull (only producers wait there), so each signal targets exactly the right kind of waiter. (Using signalAll on a single condition also avoids the lost wakeup but wakes everyone wastefully, causing a thundering herd.) Two conditions are the precise, efficient solution.

Both bugs reinforce the discipline: re-check predicates in a while loop (Bug A), and use two conditions to wake the correct waiters (Bug B).

Common mistakes

Warning: Watch for: (1) if instead of while on the predicate - spurious wakeups and lost races dequeue/enqueue incorrectly; always loop. (2) A single condition - signals wake the wrong waiter (lost wakeups); use notFull + notEmpty. (3) Signaling under no lock / wrong lock - condition signal/await must be under the owning lock. (4) Two-lock: forgetting boundary signaling - must signal across locks on empty↔non-empty / full↔non-full transitions. (5) Non-atomic shared count in the two-lock design - both locks touch it; use AtomicInteger. (6) Busy-waiting instead of await - wastes CPU.

Why this exercise matters for interviews

Interview: The blocking queue is a common data-structure question and a natural extension of the bounded buffer. Part 1 (single-lock, two conditions) tests the core condition-variable discipline: two conditions for the right waiters, while-loop predicates. Part 2 (two-lock) is the depth signal - separate head/tail locks for concurrent put/take, with shared atomic count and boundary cross-lock signaling. Part 3 (bugs) targets the two signature errors: if vs. while (the canonical condition bug) and single-vs-two conditions (lost wakeups). The throughline interviewers reward: two conditions, while-loop predicates, the two-lock concurrency optimization, and connecting it to the bounded buffer / producer-consumer. The if-vs-while reasoning and the two-lock design are what most distinguish a strong answer.

Back to Concurrency Interview Mastery