Two-Phase Syncronization in Java

It's often the case that two threads need to synchronize with each one another before performing a task. For example:

  1. In a query/response-style dialog. You want to call a method that asks the user for some bit of information and then waits for the user's response before returning.
  2. A thread-pool-class constructor creates the auxiliary threads that comprise the pool. The pool object needs to wait for all the auxiliary threads to be running before the constructor can return (otherwise the pool size will be too low).
  3. You're using an event-based parser like SAX (which sends you events when it recognizes XML elements). The incoming XML file contains large elements (that represent images, for example). You want to process these elements sequentially by calling get_next_element(), which returns the next element from the XML stream, and you want SAX to be running in the background on one thread and your call to get_next_element() to be on a second thread. (This strategy of suspending a thread between calls is sometimes called a "co-routine.")

Understanding the Problem

The synchronization requirements in these tasks are all structurally very similar, but implementation isn't straightforward. I'll use the first example to demonstrate the solution (since it's easy). Consider the following code: 

package com.holub.ui;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

/** Use this class to make a simple query of the user. A
 *  one-line dialog pops up, centered on the screen, asking
 *  the user a question. The user types in a response and hits Enter.
 *  The dialog shuts down. Use it like this:
 *  
 *  String answer = SimpleQuery.ask( "The question" );
 *  

 *  SimpleQuery.ask() doesn't return until the
 *  user types an answer and the dialog shuts down.
 */

class Query
{   static String ask( String query )
    {
        Object user_input_complete = new Object();

        final JFrame     frame  = new JFrame( "Query" );
        final JTextField answer = new JTextField();

        frame. getContentPane().setLayout(new FlowLayout());
        frame. getContentPane().add( new JLabel(query) );
        frame. getContentPane().add( answer );
        answer.setPreferredSize( new Dimension(200,20) );

        // Add an action listener that notifies us when the
        // data entry is complete.

        answer.addActionListener
        (   new ActionListener()
            {   public void actionPerformed( ActionEvent e )
                {   synchronized( user_input_complete )
                    {   frame.dispose();
                        user_input_complete.notify();
                    }
                }
            }
        );

        //...

        frame.pack();
        frame.show();

        // Wait to be notified by the action listener before
        // reading the data.

        synchronized( user_input_complete )
        {   try
            {   user_input_complete.wait();
            }
            catch(InterruptedException e){/*won't happen*/}
        }

        return answer.getText();
    }

    public static void main(String[] args)
    {   String reply = Query.ask("How are you?");
        System.out.println( reply );
    }
}

Seems straightforward. You create a synchronization object (user_input_complete), wait for it to be notified inside the ask() method, and notify it in the action handler for the text control. You might be tempted to do the same thing in all of the earlier examples.

Understanding the Solution

Unfortunately, the foregoing strategy doesn't work. Consider the situation where the thread that calls ask() get's preempted between the calls to show() and wait(). Swing runs on its own thread, so the fact that the thread that calls ask() is suspended is immaterial. The Swing subsystem displays the window, the user enters some text, the ActionListener object disposes the frame and issues the notify(), and *then* your calling thread wakes up and waits. The wait() call is executed *after* the notify() is executed. Since the window that issues the notify() is long gone when ask() gets around to waiting, ask() waits forever.

Now consider the other examples I mentioned earlier. The thread-pool constructor creates the auxiliary threads. These threads increment a counter in their run() methods, and when some thread that the counter has reached the maximum-thread count, it notifies the thread-pool object that all the threads are running. What if thread on which the thread-pool constructor is preempted after all the auxiliary threads are created but before it waits? Same problem as before, it could miss the notification. In the SAX example, the following loop is used to process elements: 

Parser.start();

while( ... )
{
    MyElement e = Parser.get_next_element();
    process_element( e );
}
There's a wait() inside get_next_element() that matches a notify() that's issued by some SAX event handler. There are two problems, here. First, if the code is preempted between the start() and get_next_element() calls, the parser will be issuing notify() calls that will be ignored because nobody's waiting. Second, the same thing can happen if process_element() takes more time to process the element than it does for the parser to parse the element. The notify() is issued as soon as the element is recognized, but the code that uses the element is still processing the last one and hasn't gotten around to waiting for the next one, yet.

So, how do we solve these problems? With a two-phase synchronization. The following code demonstrates the process. (I've stripped it down considerably; get the complete code from the subscribers-only part of the web site at /subscribers/) 

//...
class Query
{   static String ask( String query )
    {
        final Object user_input_complete    = new Object();
        final Object container_initializing = new Object();

        //...
        final JTextField answer = new JTextField();

        answer.addActionListener
        (   new ActionListener()
            {   public void actionPerformed( ActionEvent e )
                {   synchronized( container_initializing )
                    {   synchronized( user_input_complete )
                        {   frame.dispose();
                            user_input_complete.notify();
                        }
                    }
                }
            }
        );

        //...

        synchronized( user_input_complete )
        {   synchronized( container_initializing )
            {   frame.pack();   // In the general case, the
                frame.show();   // start() call goes here.
            }

            try
            {   user_input_complete.wait();
            }
            catch(InterruptedException e){/*Won't happen*/}
        }
        return answer.getText();
    }
}

I've used two locks (user_input_complete and container_initializing) to implement a simple handshake. The ask() method acquires both locks (order is important), pops up the window, and then releases only one of them (container_initializing). The code then waits to be notified that the user input is complete, as before. Meanwhile, on the Swing thread, the ActionListerner object also acquires both locks.

Now, let's consider our earlier scenario. It's no big deal if the the thread on which ask() is running is preempted before it's acquired both locks because the window won't be displayed yet. What if it's preempted after the show, but before it's released container_initializing? The window will be displayed, and the user may well have entered input, but the Swing thread will be suspended in actionPeformed(), waiting to synchronize on container_initializing, effectively shutting down the Swing thread until ask() releases the lock by exiting the synchronized block.

What if the preemption occurs after container_initializing is released? actionPerformed() is still blocked, because it has to acquire user_input_complete() to issue the notify. The ask() thread has that lock, however, and the lock isn't released until the wait() is issued.

The net effect is that it's now impossible for actionPerformed() (running on the Swing thread) to notify the user_input_complete object until the thread on which ask() is running is waiting for the notification to come. It's no longer possible to miss the notification. Note that the lock on which we're waiting (user_input_complete) has to be acquired first, because we need to be holding that lock when the second lock (container_initializing) is released.

You can use the same technique to solve the other problems discussed earlier.

The main "gotcha" is the order of acquisition. As I mentioned earlier, when two threads acquire a set of locks, the locks must be acquired in the same order on both threads to avoid deadlock. (Find an article on sequence-related deadlock at /publications/other/deadlock.html.) This acquisition-in-the-same-order rule is irrelvant here because it's essential that the creating thread acquire both locks before it can allow the created thread to run. (The Swing/AWT event thread is effectively "created" when you issue the pack()/show().)

A Generalized Solution

As is often the case with boilerplate code, it's often best to hide it in a class to make programming easier. The following Gate class hides all the synchronization discussed earlier: 

class Gate
{   private Object wait_lock = new Object();
    private Object init_lock = new Object();

    public void am_complete()
    {   synchronized( init_lock )
        {   synchronized( wait_lock )
            {   wait_lock.notify();
            }
        }
    }

    /** Run the code in the initializations object, then wait
     *  for an am_complete() message. This method assures that
     *  you can't miss the notification because of a preemption
     *  that occurs just after initializations are performed.
     */
    public boolean create_and_wait( Runnable initializations )
    {   synchronized(wait_lock)
        {   synchronized(init_lock)      { initializations.run();}
            try                          {  wait_lock.wait();    }
            catch(InterruptedException e){  return false;        }
            return true;
        }
    }
}
Using that class, you can simplify the earlier Query as follows: 
//...
class Query
{   static String ask( String query )
    {
        Gate gate = new Gate();

        //...
        final JTextField answer = new JTextField();

        answer.addActionListener
        (   new ActionListener()
            {   public void actionPerformed( ActionEvent e )
                {   frame.dispose();
                    gate.am_complete();
                }
            }
        );
        //...
        gate.create_and_wait
        (   new Runable(){ public static void Run()
            {   frame.pack();   // In the general case, the
                frame.show();   // start() call goes here.
            }}
        );

        return answer.getText();
    }
}

Source Code and References

Get the complete source code for the Swing example I've used here from the subscibers-only page on www.holub.com. Execute the example code with java -jar handshake.jar.

Threading is always nasty stuff, and most Java programmers don't know nearly enough about it. The easiest way to learn more about threads is to have me come in and present my one-day "Taming Java Threads" class. Lacking that, here are a few good books on the subject:

Allen Holub, Taming Java Threads. Find the code for the book on my web site (). You'll also find the original JavaWorld articles (on which the book is based) on the web site.

Doug Lea, Concurrent Programming in Java(TM): Design Principles and Pattern (2nd Ed.).

Scott Oaks and Henry Wong, Java Threads (2nd Ed.)

The Swing/AWT event thread is active as soon as a setVisible(...), show(), or pack() message is sent to a component. There's an article on the topic at http://java.sun.com/products/jfc/tsc/articles/threads/threads1.html.