Thread-Safe Queue Design

A bounded blocking queue built from a lock and two condition variables, traced and tested with real threads; then the two-lock and lock-free designs behind Java's queues and the ABA problem.

Overview

A thread-safe queue is the part of a system where producers hand work to consumers: a thread pool's task queue, a log writer's buffer, the stage between a network reader and a parser. It has to do two things a plain queue does not. It must survive several threads pushing and popping at once, and it must make a consumer wait when there is nothing to take and a producer wait when there is no room.

The interview usually starts with the bounded blocking queue, because it exercises the exact skills a concurrency question tests: a lock, a condition variable, the loop around the wait, and a test with real threads. From there it goes to the designs behind library queues: one lock, two locks, or no lock at all.

What goes wrong without a lock

A single pop is several steps: read the head, read the item, move the head. Two consumers interleaving those steps can both take the same item, or one can move the head past an item nobody took.

1 — reads head, sees item 1 — [1, 2, 3]
2 — reads head, sees item 1 — [1, 2, 3]
3 — takes item 1, moves head — [2, 3]
4 — takes item 1 again, moves head — [3]
result — got 1 — got 1 — item 2 was never delivered

The fix is to make the whole operation one indivisible step from every other thread's point of view. A lock does that by letting one thread at a time run the steps; a lock-free design does it with a single atomic compare-and-swap.

The bounded blocking queue

A single lock protects the buffer, and two condition variables share that lock: not_empty, which consumers wait on, and not_full, which producers wait on. A put appends and wakes one consumer; a get removes and wakes one producer.

A trace with capacity 2, one producer P and one consumer C.

1 — P — put(a) — [a] — signals not_empty; nobody waiting
2 — P — put(b) — [a, b] — full now
3 — P — put(c) — [a, b] — full: P waits on not_full, releasing the lock
4 — C — get() — [b] — returns a; signals not_full: P wakes
5 — P — (resumes) rechecks: not full — [b, c] — appends c; signals not_empty
6 — C — get() — [c] — returns b
7 — C — get() — [] — returns c
8 — C — get() — [] — empty: C waits on not_empty

Step 5 is why the wait sits in a loop: when P wakes, it must check 'still full?' again, because another producer could have filled the slot first, and because a wait may return without any signal at all. Both Python's threading docs and Java's Condition docs say to always wait in a loop for this reason.

wait_for is the loop: it re-tests the predicate after every wakeup and returns False on timeout. The stop marker is the standard way to end consumers that block on get; the main thread puts one per consumer after the producers are done.

Choosing a library queue

Interviewers expect you to know what the standard libraries give you and how each is built.

Java ArrayBlockingQueue — Yes, fixed at construction — Yes — An array, one lock, two conditions — The 'classic bounded buffer'; an optional fairness mode grants waiting threads FIFO order, at a cost in throughput
Java LinkedBlockingQueue — Optional; default Integer.MAX_VALUE — Yes — Linked nodes, a put lock and a take lock, an atomic count — Typically higher throughput than array-based queues but less predictable
Java ConcurrentLinkedQueue — No — No — Linked nodes, compare-and-swap — Based on Michael and Scott's non-blocking algorithm; size() walks the list and may be inaccurate
Python queue.Queue(maxsize) — If maxsize > 0 — Yes; put/get take block and timeout and raise Full/Empty — A lock and conditions — Adds task_done() and join() for waiting until all items are processed
Python queue.SimpleQueue — No — get blocks; put never does — A reentrant C implementation — Safe to use from destructors and weakref callbacks

Two locks instead of one

With one lock, a producer and a consumer block each other even though they touch opposite ends of the list. Michael and Scott's two-lock queue keeps a dummy node at the head so that an enqueue touches only the tail and a dequeue touches only the head; each end gets its own lock, and one enqueue and one dequeue can run at the same time. Java's LinkedBlockingQueue is a variant of it, with the element count kept as an atomic so most operations need only their own lock.

What you will be able to do

Implement a bounded blocking queue with a lock and two condition variables, and test it with real threads.
Explain why the wait is a loop and what a spurious wakeup is.
Pick between array-based, linked, one-lock, two-lock and lock-free queues, and name the Java and Python classes.
Describe the ABA problem and how counters, hazard pointers and garbage collection avoid it.
Design backpressure: what happens when the queue is full.

Interview questions

Implement a bounded blocking queue where producers block when it is full and consumers block when it is empty.
What is the ABA problem in lock-free data structures, and how is it avoided?
What is the difference between ArrayBlockingQueue and LinkedBlockingQueue in Java?
What should happen when the queue is full? Design the backpressure.
Design a work-stealing queue for a thread pool.