Working with the blocking queue

Java’s threading implementation is one of the most elegant out there. The quality of its design has introduced countless programmers — some of them learning programming for the very first time — to multi-threaded programming.

Java’s threading implementation is also very simple. Following the “less is more” design principle, the designers included only those features that were necessary to get the job done elegantly.

In this article, we introduce a basic threading construct called the blocking queue. The beauty of Java’s threading implementation is this element can be easily written in Java.

Queues

get()

put()

get

put

What is a queue for? Well, in a multithreaded program, we might have one thread responsible for processing a certain object. Other threads “send” objects to these processing threads by placing them on the queue with

put

get

The chat server is the classic example used to demonstrate multithreading concepts in Java. In a chat server, we might have a small, finite pool of threads that is responsible for sending messages out to the chat clients. These threads are called “writer threads.” Meanwhile, another small finite pool of threads are reading messages from chat clients. These are called “reader threads.”

The reader threads take incoming messages and place them on the main message queue. The writer threads take the messages off of the queue, one at a time, and send them out to the appropriate clients.

Using a queue effectively decouples the reading process from the writing process. This is useful because network connections vary widely in their efficiency: some connections are very fast and some are slow. Often, a connection might “go dead” for a long time. If a single thread was responsible for both reading a message and sending it out to other clients, then any outgoing connection might block that thread. While that thread is blocked, it wouldn’t be able to spend time reading new messages from clients.

Blocking queues

get

One solution is to have the queue return

null

get

Another possibility would be to go to sleep for a short while, and then, after waking up, check again to see if the

get

Java provides a solution to this problem. Instead of polling or sleeping, the writer thread can wait for an object to become available. A wait is like a sleep, in that the thread suspends its execution for a time. However, unlike sleep, which suspends execution for a fixed length of time, a wait suspends execution until another thread does a

notify

This solves our waste problems: we’re not polling, and we’re not going to run the risk of being suspended for too long. Instead, the writer thread suspends its execution until the very moment that an object is available.

Hiding the details

wait

get

The blocking queue hides all this detail by putting all of the wait and notify logic inside the queue object itself. That way, this logic doesn’t need to be inside the writer thread or any other object that might want to use the queue.

The idea is to do the

wait

get

get

get

This is elegant because the semantics of the

get

get

get

get

Who does the

notify

?

notify

We don’t need to create an extra thread for this purpose. Instead, we simply put a

notify

put

This takes care of the

notify

Part 2 of 2

Multiple

get

‘ers

wait

notify

wait

However, there is one potential issue. Suppose two threads are in a

wait

The answer is: whichever thread grabs it first. When a

notify

notifyAll

get

Okay, but what about the second thread? The first thread woke up, took the object and left the queue empty again. When the second thread, having just been woken up, gets a chance to run, the queue will probably still be empty.

The only answer is the straightforward one: check the queue, and if there isn’t an object, on it, go back into a wait state. This might seem awkward, and, in reality, it does waste some CPU time, but very little. And there really isn’t any other way, given Java’s synchronization primitives. This technique is used in almost every situation involving multiple threads and

wait

notify

And, again, this logic is all hidden inside the

get

The code

The test program is a command-line program, and works as follows. You specify a number of threads on the command-line:

> java QT 5

The QT object creates five threads that all attempt to get objects from the blocking queue it contains. Each time an object is returned from the blocking queue, the receiving thread prints the object out and goes back to waiting for another one.

Meanwhile, the main thread waits for you to type some text and press <RETURN>. When you press <RETURN>, the text you typed is put into the blocking queue. Thus, you can put objects into the queue as fast as you can type them in. Meanwhile, the various threads are printing the objects out. Each thread announces its thread ID when it prints out an object, so you can see that different threads are receiving the objects.

(Note: This code is written for Java 1.0.2 for maximum portability. Later Java implementations might complain about deprecated methods when this code is compiled.)

Queue.java

import java.util.*;

public class Queue
{
  // Internal storage for the queue'd objects
  private Vector vec = new Vector();

  synchronized public void put( Object o ) {
    // Add the element
    vec.addElement( o );

    // There might be threads waiting for the new object --
    // give them a chance to get it
    notifyAll();
  }

  synchronized public Object get() {
    while (true) {
      if (vec.size()>0) {
        // There's an available object!
        Object o = vec.elementAt( 0 );

        // Remove it from our internal list, so someone else
        // doesn't get it.
        vec.removeElementAt( 0 );

        // Return the object
        return o;
      } else {
        // There aren't any objects available.  Do a wait(),
        // and when we wake up, check again to see if there
        // are any.
        try { wait(); } catch( InterruptedException ie ) {}
      }
    }
  }
}

QT.java

import java.io.*;

public class QT implements Runnable
{
  // The blocking queue we are testing.
  private Queue q = new Queue();

  // Create the specified number of object-getting threads.
  public QT( int nThreads ) {
    for (int i=0; i<nThreads; ++i)
      new Thread( this ).start();
  }

  // Each thread does this: get an object, and print it out.
  // Over and over.
  public void run() {
    while (true) {
      String s = (String)q.get();
      System.out.println( "Thread "+Thread.currentThread()+": "+s );
    }
  }

  // Place a text string into the queue.
  public void put( String s ) {
    q.put( s );
  }

  static public void main( String args[] ) throws Exception {
    // Check command-line parameters
    if (args.length<1) throw new Exception( "Usage: QT <numthreads>" );

    // Create the QT object and its threads
    QT qt = new QT( new Integer( args[0] ).intValue() );

    // Main thread: read string; put string in queue; repeat.
    DataInputStream din = new DataInputStream( System.in );
    String s = null;
    while ((s=din.readLine())!=null) {
      qt.put( s );
      Thread.yield();
    }
  }
}

Problems

Deadlock: Deadlock is a problem in any multithreaded program, and there’s no simple solution for it. When using a blocking queue, deadlock can happen if one thread is waiting for an object while another thread — the one that can supply that object — is waiting for an object that can only be supplied by the first thread. Such a situation can simply be described as bad design.

Waiting Forever: Even without deadlock, it’s possible for a thread to wait for an object that is never going to come. One modification that might take care of this is to modify the queue code to have a timeout, so that a thread will wait only a certain amount of time before the

get

null

get

null

Summary

Greg Travis is a freelance programmer living in New York City. His interest in computers can probably be traced back to the episode of “The Bionic Woman” where Jamie runs around trying to escape a building whose lights and doors are controlled by an evil artificial intelligence which mocks her through loudspeakers. He’s a devout believer in the idea that when a computer program works, it’s a complete coincidence. He can be reached at mito@panix.com.