October 20, 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 »

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

First, a few quick definitions. A queue is a container object that supports two basic methods:
get()
and
put()
. Objects are put into the queue, and they are retrieved at a later time with get. A queue is different from a stack in that it implements first-in-first-out (FIFO) semantics. That is, if you put several objects into a queue, the first one that is retrieved with
get
will be the first one that was put in with
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
. The processing threads take the objects off the queue with
get
, one at a time, and process them in turn.

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

Continuing to use our chat example, we ask the following question: "What does a writer thread do when a queue is empty?" At any given moment, there may be no messages to process. In this case, what happens when the writer thread calls the queue's
get
method?

One solution is to have the queue return

null
. Semantically, this return value means "nothing in the queue right now." Well, what does the writer thread do at this point? It could call the
get
method again, and then again and again, until the queue returned a message. This is called polling or busywaiting (depending on who you ask), and it can be a tremendous waste of CPU resources.

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

get
method will return something. This solves the problem of wasting raw CPU power, but it still isn't perfect. If the thread sleeps five seconds, an object might become available only one second into that sleep. If the thread waits only one second, an object might become available only one-tenth of a second into that sleep. In general, the thread might be wasting time sleeping when there is an object available, even if the sleep is very short. (If the sleep is extremely short, then you're really just busywaiting again.)

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
. The advantage of this is that the thread can be awakened the moment that an object is available.

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

Using
wait
involves a good deal of programming logic. The thread calling
get
has to put itself into a wait state if there aren't any objects available. Meanwhile, some other thread has to be around to wake the waiting thread as soon as an object becomes available.

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
inside the
get
method itself. Thus, the
get
method is responsible for putting the calling thread into a wait state if there aren't any objects available in the queue. At some later point, an object will become available, and the
get
method returns this object.

This is elegant because the semantics of the

get
call are very simple: you call
get
, and later, you get an object back. This is really as simple as a method like this can be. The fact that the call to
get
might actually involve going into a suspended state for an arbitrary length of time doesn't really affect the semantics; it only affects the time the call takes. One call to
get
might return an object immediately, while another call might wait an hour. But in both cases, all that the calling code needs to do is assume that an object will be returned.

Who does the
notify
?

We've left something out, however. Previously, I mentioned that once a thread has gone into a wait state, it needs to be
notify
'd, or awakened, by some other thread. In the blocking queue, which thread is responsible for this task?

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

notify
inside the
put
method of the blocking queue. The effect is that any time some other thread puts an object into the queue, any threads waiting for an object will be awakened.

This takes care of the

notify
rather nicely: the waiting threads are only woken up when an object has just been placed on the queue. And we don't need a special thread to do it.







Page 1 of 2



Comment and Contribute

 


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

 

 


Sitemap | Contact Us

Rocket Fuel