IC211: Threads II

Race Conditions

In general, parallel programming is fraught with peril! If you're not careful, you can end up with bugs whose occurence or precise behavior depends on the exact order in which the instructions of each thread are executed relative to one another. This kind of bug is called a race condition.

To see a nice example of how this might happen, let's turn back to our old friend the Queue class. The following program has single Queue, "Q", that is shared by two threads. Both threads call enqueue 1,000 times, after the second thread dies, the main thread then counts that there were indeed 1,000 items enqueued by each thread.

So what happens when I run this?

You may see the program crash ... You mays see the program stuck in an infinte loop

When I run this ... it crashes. Why? Well there are a couple of possible race conditions here. The one that just happened to me went something like this: Things were OK for a while, each thread enqueuing values, but then we had a bad interleaving of execution of instructions. It probably happened like is shown in the following table:

Thread 1 (main)

Thread 2 (run)


tail.next = new Node(s,null); 

tail = tail.next; 
       ---------
     this causes the problem
     because Thread 2 has just
     set tail to point to a
     Node whose "next" is null!

tail.next = new Node(s,null); 

tail = tail.next;

This isn't the only way things could go wrong, in fact. It's possible for the two threads to execute in such a way that neither thread crashes, but one of the values is lost!

When I run this it gets stuck in an infinite loop. Why? Well, the lines

    Thread t = new QThread(Q);
    t.start();
    while(Q.empty())
      ;

start up a new thread and then wait until the new thread actually gets something enqueued in Q to continue. The problem is that the Java compiler / VM perform certain optimizations. In this case, one or the other of them may decide that recomputing Q.empty() is a pointless waste of time, since the call "Q.empty()" doesn't actually change any fields, and nothing else happens in the loop, and thus either Q.empty() gives true every time or false every time - why recompute it? And so it is transformed to


    Thread t = new QThread(Q);
    t.start();
    boolean tmp = Q.empty();
    while(tmp)
      ;

... and we get our infinite loop. The problem is that the compiler/JVM is not taking into account the possiblity that there may be other threads changing Q.head and Q.tail, and thus the result of Q.empty() may indeed change. To fix this, we can add the modifier volatile to Q.head and Q.tail

  private volatile Node head = null, tail = null;

which tells the compiler/JVM that, as it does its optimizing, it cannot assume that other threads won't be modifying these fields. This fixes the infinite loop.

Synchronization in general, and the synchronized keyword in particular

While for the most part we want threads to process independently, in parallel, what we just saw is that there are times when we need to coordinate, or synchronize the execution of separate threads in order to avoid race conditions. To the previous example, we need to ensure that the two threads don't simultaneously execute enqueue's - they need to take turns.

Perhaps the simplest of the many mechanisms Java provides for synchronizing the execution of threads are synchronized methods. Declaring one or more methods in a class with the synchronized modifier causes the Java virtual machine to ensure that no two threads execute overlapping calls of synchronized methods on the same object. It does this by temporarily delaying threads as needed. To be clear, suppose we have a class Foo:

public class Foo
{
  ...
  public sychronized void bar()
  {
    ...
  }
  ...
}

If var1 and var2 are references to distinct objects of type Foo then Thread x could call var1.bar() and Thread y could call var2.bar(), and the two methods could execute simulaneously. However, if both Threads called var1.bar() at the same time (note: we calling bar() on the same object this time!), then one Thread would execute bar() while the other Thread was delayed, and only after the first thread had completed its call to bar() could the second thread start executing its call.

So, to fix our bug, all we need to do is declare enqueue (and dequeue, though it doesn't really matter in our test program) with the synchronized modifier.

Synchronization with the Event Dispatch Thread

Whenever we have two or more threads reading-from/writing-to the same object, we have to worry about the possiblity of race conditions. But isn't that, in fact, what we've been doing with GUIs? The Event Dispatch Thread manipulates all of the JFrame, JButtons, JLabels and so on, but in several of our programs the main thread has manipulated these as well, and so have other threads we've spawned. So should we be worried? The short answer is ... yes. These Swing classes are not "thread safe", meaning they do not employ synchronized methods or other mechanisms to ensure that race conditions don't arise when multiple threads are involved. So, we have kind of been playing with fire.

The way one is supposed to update Swing objects is to use the "event queue". The event queue, like our Queue with synchronized methods, is threadsafe. Multiple threads can safely add items to it. What kind of items? Runnable items. These items will be dequeued and their run() methods called, but they will be executed in the Event Dispatch Thread. If you do everything related to a GUI component this way, the component is only ever modified in the Event Dispatch Thread, so there is no concurrency, and thus no race conditions. When you have an action you'd like to take in order to update a GUI component, instead of executing the action directly in whatever thread you are in, you should enqueue a Runnable object with the "invokeLater" method.

For example, suppose have a JTextField tf and you want to set its text to "0.0". Instead of executing the statement

tf.setText("0.0");

you should create the class

public class MyRunnable implements Runnable
{
  private JTextField t;
  public void MyRunnable(JTextField t) { this.t = t; }
  public void run() { t.setText("0.0"); }
}

and then, where you would have had tf.setText("0.0"); you would write

java.awt.EventQueue.invokeLater(new myRunnable(tf));

This way, when the Event Dispatch Thread has a spare moment, it will dequeue this MyRunnable object and call its run() method, which will cause it to set tf's text to "0.0".

This idiom causes a proliferation of classes, which is a bit ugly and awkward, so Java allows you to define and instantiate a class "inline", using what are called anonymous classes. Using this mechanism, we can set our text with the following:

	                                               overriding 'run' method
final JTextField tfp = tf;                       .------------------------------------.
java.awt.EventQueue.invokeLater(new Runnable() { public void run() { tfp.setText("0.0"); } } );
                                    \______________________________________________________/
                                          anonymous class derived from Runnable

The "final" in final JTextField tfp is there because of a technicality, which is that any local variable you reference from within the anonymous class has to be "final". Note that this doesn't mean that the JTextField object can't be modified. It means that the reference tfp can't be changed to point to another object.

Because it rapidly involves a lot of anonymous classes, which we're not going to cover in-depth, we'll mostly stick to "playing with fire" in our simple GUIs for this class, and access GUI elements from outside the Event Dispatch Thread. Let's just hope we don't get burned!