Blocking Queues

Imagine a consumer thread that needs work items from a shared queue. Sometimes the queue has items in it, and sometimes it has nothing at all. A consumer that asks for an item from an empty queue has to be handled somehow. This article follows one consumer thread and one queue through that moment, and shows how a blocking queue keeps the consumer from either giving up or spinning in a loop.

When several threads work on the same data, one common arrangement is to have some threads produce work and other threads consume it. A queue sits between them. Producers add items at one end and consumers remove items from the other. The queue must be synchronized so that two threads never corrupt it by touching it at the same moment, but synchronization alone does not solve everything.

Consider what a consumer should do when the queue has nothing in it. A simple design would have the consumer check the queue, see that it is empty, and then either give up or spin around checking again. Neither option is satisfying. Giving up loses the work the consumer was meant to do, and repeated checking wastes processor time. What is really wanted is for the consumer to pause until something arrives. The same problem appears on the other side: a producer facing a full, limited-size queue should be able to pause until room opens up.

A blocking queue needs a way to hold a thread in a waiting state until some event happens. That event is usually caused by a different thread, for example a producer adding an item to the queue. So the problem involves at least two threads: one that waits, and one whose action wakes it up. Java provides wait() and notify() for this handoff. Both are instance methods of class Object, so any object can coordinate two threads.

The rule is simple. A thread that calls wait() on an object sleeps until another thread calls notify() on that same object. The object is the meeting point. If the two threads call wait() and notify() on different objects, they never meet and the waiting thread is not woken by that call.

Read the diagram as the life of Thread A. Thread A does not wait in every case. It waits only when a check finds that the result is not yet available. If the result already exists, the condition is false, the call to wait() is skipped, and Thread A moves straight on to using the result. When wait() is reached, Thread A stops running and stays in the waiting state until Thread B calls notify() on the same object. Only then does Thread A resume, continuing with the line after the wait. Thread B is the one running at step 2, and its notify() is what ends Thread A's pause.

The handoff depends on timing. A notify() call only reaches a thread that is already waiting on the same object. The source states that calling notify() when no thread is waiting is not an error and has no effect. Nothing is stored for later. The signal is simply gone.

A thread that is suspended while it waits for something to happen is said to be blocked. Blocking is a pause in the thread's own progress. The thread does not finish its call and move on. It stays in the middle of the call until the condition it is waiting for is met, and then it continues from that point.

The diagram shows the two possible paths. If an item is already present, the thread takes it and keeps going without ever pausing. If the queue is empty, the thread moves into the blocked state. It stays there until an item is placed in the queue, and at that moment it resumes and receives the item. The thread does not need to poll the queue to find out when work has arrived. The waiting is part of the take() call itself.

Blocking applies in both directions. On the consumer side, take() on an empty queue blocks the caller until an item appears. On the producer side, put(item) on a limited-capacity queue that is already full blocks the caller until a space opens. The same queue can therefore hold back consumers when it is empty and hold back producers when it is full, without any extra logic written by the programmer around the queue.

Java provides two classes that implement blocking queues: LinkedBlockingQueue and ArrayBlockingQueue. Both are parameterized types, so you specify the type of item the queue will hold. Both are defined in the package java.util.concurrent, and both implement an interface called BlockingQueue. Because they share that interface, the blocking operations behave the same way on either class, while the capacity rules differ.

Read the comparison from top to bottom and the pattern is clear. A bounded queue gives producers a signal of pressure, either by pausing them through put() or by raising an exception through add(). An unbounded queue removes that signal, which is why it demands a separate safeguard against unchecked growth. In both cases, a consumer that calls take() on an empty queue waits.

The source names four operations that are enough for most purposes. take() and put(item) are the blocking pair: one waits for items, the other waits for room. add(item) is the non-blocking counterpart of put(item). The source recommends put(item) for limited-capacity queues and add(item) for unlimited ones, because add(item) cannot wait for room that will never be needed. clear() is not part of the blocking pair described in the source, so it is not the tool for producer or consumer handoff. The source does not detail its behavior further, so the choice in a handoff rests on take, put, and add.

Choosing between the classes is a decision about where back-pressure comes from. A bounded ArrayBlockingQueue lets the queue itself slow producers down when consumers fall behind. An unbounded LinkedBlockingQueue lets producers keep going, which avoids blocking them, but then the queue can keep growing if consumers are slower than producers. A practical rule follows: if you want a natural limit on how far producers can run ahead of consumers, choose a bounded queue and use put(item). If producers must never pause and you have a separate way to bound the queue's size, choose an unbounded queue. In either case, consumers should use take(), which waits for work without polling.