Featured White Papers

• Measuring Risk to Improve Java Software Quality
• Do You Really Get Classloaders?
• Pragmatic Continuous Delivery with Jenkins, Nexus, and LiveRebel
• Your Next Java Web App: Less XML, No Long Restarts, Fewer Hassles
• Coding with JRebel, Java Forever Changed
• 2012 Developer Productivity Report: Java Tools, Tech, Devs, and Data

Sponsored Links

• Graph databases are 1000x faster than relational.

  Learn More!

• Career opportunities at Harman- Careers That'll Rock Your Socks Off.

  Learn More!

• Developer-friendly Java PDF libraries by Qoppa Software

  Live Demos

• Stop blaming your app! Diagnose Java performance issues.

  Free tool >

• UrbanCode: Go From Continuous Integration to
  Continuous Delivery

  Learn More!

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

Programming Java threads in the real world, Part 2

The perils of race conditions, deadlock, and other threading problems

By Allen Holub, JavaWorld.com, 10/01/98

Page 3 of 7

Working with wait() and notify()

The following code demonstrates a blocking queue used for one thread to notify another when some event occurs. (We'll see a more realistic version of these in a future article, but for now I want to keep things simple.) The basic notion is that a thread that tries to dequeue from an empty queue will block until some other thread puts something in the queue.

class Notifying_queue 
{
    private static final queue_size = 10;
    private Object[]  queue = new Object[ queue_size ];
    private int       head  = 0;
    private int       tail  = 0;
    public void synchronized enqueue( Object item )
    {
        queue[++head %= queue_size ]= item; 
        this.notify();                  // The "this" is there only to
    }                                   // improve readability.
    public Object synchronized dequeue( )
    {
        try
        {   if( head == tail ) // <=== This is a bug
                this.wait();
        }
        catch( InterruptedException e )
        {
            // If we get here, we were not actually notified.
            // returning null doesn't indicate that the
            // queue is empty, only that the waiting was
            // abandoned.
            return null;
        }
        return queue[++tail %= queue_size ]; 
    }
}

Starting with an empty queue, let's follow the sequence of operations in play if one thread does a dequeue and then another (at some later time) enqueues an item.

1. The dequeueing thread calls dequeue(), entering the monitor (and locking out other threads) until the monitor is released. The thread tests for an empty queue (head==tailwait(). (I'll explain why this is a bug in a moment.)
   
   
2. The wait() releases the lock. (The current thread temporarily leaves the monitor.) It then blocks on a second synchronization object called a condition variable. (The basic notion of a condition variable is that a thread blocks until some condition becomes true. In the case of Java's built-in condition variable, the thread will wait until the notified condition is set to true by some other thread calling notify.) It's important to realize that the waiting thread has released the monitor at this juncture.
   
   
3. A second thread now comes along and enqueues an object, eventually calling notify(), thereby releasing the waiting (dequeueing) thread.
   
   
4. The dequeueing thread now has to wait to reacquire the monitor before wait() can return, so it blocks again, this time on the lock associated with the monitor.
   
   
5. The en queueing thread returns from the enqueue() method releasing the monitor.
   
   
6. The dequeueing thread acquires the monitor, wait() returns, an object is dequeued, and dequeue() returns, releasing the monitor.

Race conditions following a wait()
Now, what sorts of problems can arise? The main ones are unexpected race conditions. First, what if you replaced the notify() call with a call to notifyAll()? Imagine that several threads were simultaneously trying to dequeue something from the same, empty, queue. All of these threads are blocked on a single condition variable, waiting for an enqueue operation to be executed. When enqueue() sets the condition to true by calling notifyAll(), the threads are all released from the wait (moved from a suspended to a runnable state). The released threads all try to acquire the monitor at once, but only one would "win" and get the enqueued object. The problem is that the others would then get the monitor too, in some undefined sequence, after the winning thread had dequeued the object and returned from dequeue(). Since these other threads don't retest for an empty queue, they will dequeue garbage. (Looking at the code, the dequeue() method will advance the tail pointer to the next slot, the contents of which are undefined since the queue is empty.)