October 31, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Working with the blocking queue

  • September 10, 1998
  • By Greg Travis
  • Send Email »
  • More Articles »

Part 2 of 2

Multiple
get
'ers

Things get a bit more complicated if we have multiple threads taking objects from our queue. However, the elegant semantics of the
wait
and
notify
methods take care of most of this for us. There's no problem, in terms of the threading implementation, with having multiple threads in
wait
state, waiting for the same event.

However, there is one potential issue. Suppose two threads are in a
wait
state, waiting to taken an object off the queue. Another thread comes along and places an object on the queue. Which of the waiting threads gets the object?

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

notify
-- really, a
notifyAll
-- event happens, all the waiting threads wake up. However, because of the synchronization blocks we've wrapped around the
get
and put calls, only one of these threads actually gets to run. Which one is implementation-dependent and, in general, entirely unpredictable. We can only be sure that one of the threads will get to run.

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
, so it's best to get familiar with it.

And, again, this logic is all hidden inside the

get
call of the blocking queue. Once you have it working, you can forget about it.

The code

Speaking of getting the blocking queue code working, here's a working implementation, along with a test program. The code in Queue.java implements all the logic of the blocking queue, while QT.java contains a simple test program.

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

The blocking queue is simple and useful. There are some potential problems that might happen, especially in complex or high-traffic systems.

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
method returns a
null
. This makes the semantics of
get
slightly more complicated -- since a
null
return value is now possible -- but if the application requires it, there may be no way around it.

Summary

The blocking queue may not be right for all applications, but it is remarkably effective given the simplicity of its implementation. The blocking queue should be handy in the toolbox of any Java programmer who wants to write a multithreaded program.

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.






Page 2 of 2



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel