Threads II

Race Conditions

In general, parallel programming is fraught with peril! If you're not careful, you can end up with bugs whose occurrence 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 a single Queue, "Q", that is shared by two threads. Both threads call enqueue 1,000 times, and after the second thread dies, the main thread then counts that there were indeed 1,000 items enqueued by each thread.

Ex0.java
public class Ex0 {
  public static class QThread extends Thread {
    Queue Q;
    public QThread(Queue Q) {
      this.Q = Q;
    }

    public void run() {
      for( int i = 0; i < 1000; i++ )
        Q.enqueue("b" + i);
    }
  }

  public static void main(String[] args) {
    Queue  Q = new Queue();
    Thread t = new QThread(Q);

    t.start();

    while (Q.empty()) {}

    for( int i = 0; i < 1000; i++ ) {
      Q.enqueue("a" + i);
    }

    while( t.isAlive() ) {}
    int a = 0, b = 0;

    while( !Q.empty() ) {
      if( Q.dequeue().charAt(0) == 'a' )
        a++;
      else
        b++;
    }
    System.out.println("a=" + a + " b=" + b);
  }
}
Queue.java
public class Queue {
  public void enqueue(String s) {
    if( head == null ) {
      head = tail = new Node(s, null);
    } else {
      tail.next = new Node(s, null);
      tail = tail.next;
    }
  }

  public String dequeue() {
    Node t = head;

    head = head.next;

    if( head == null ) {
      tail = null;
    }
    return t.data;
  }

  public boolean empty() {
    return head == null;
  }

  private class Node {
    public String data;
    public Node next;
    public Node(String d, Node n) {
      data = d;
      next = n;
    }
  }
  private Node head = null, tail = null;
}

So what happens when I run this?

You may see the program crash ...

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 2 (run)
tail.next = new Node(s,null);

tail = tail.next;
Thread 1 (main)
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!

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!

You mays see the program stuck in an infinite loop

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 possibility 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.

Queue.java
public class Queue {
  public synchronized void enqueue(String s) {
    if( head == null ) {
      head = tail = new Node(s, null);
    } else {
      tail.next = new Node(s, null);
      tail      = tail.next;
    }
  }

  public synchronized String dequeue() {
    Node t = head;

    head = head.next;

    if( head == null ) {
      tail = null;
    }
    return t.data;
  }

  public boolean empty() {
    return head == null;
  }

  private class Node {
    public String data;
    public Node   next;
    public Node(String d, Node n) {
      data = d;
      next = n;
    }
  }
  private volatile Node head = null, tail = null;
}

A Race Condition Example: Counting

Here is anothing example, slightly contrived, but that illustrates further how synchronized works. Imagine you need to process a lot of data files, and you realize that you could parrallelize the processing by assigning a new thread to each data file. Instead of one main thread looping over all the files, launch all the threads at the same time.

The program below takes file paths as arguments, and creates a CountThread for each one. The threads share a single SafeCounter object which simply counts how many lines are in the files. Each thread increments the counter. This is a classic race condition. There is a single value int to update as the counter that is shared across all threads. As the threads grab the value, in between reading its value and then sending the ++ updated value, another thread might read the value as well and miss the new update.

Try running this on a couple large files, and remove the synchronized keyword from the methods. You'll see different counts output from different runs. With the synchronized keyword, it will always be the same (correct) value.

SafeCounter.java
public class SafeCounter {
    private int value = 0;
    public synchronized void increment() {
        value++;
    }
    public synchronized int getValue() {
        return value;
    }
            }
CountThread.java
public class CountThread extends Thread {
  String filename;
  SafeCounter counter;

  public CountThread(String filename, SafeCounter counter) {
    this.filename = filename;
    this.counter = counter;
  }

  public void run() {
    try {
      Scanner scan = new Scanner(new File(filename));
      while( scan.hasNextLine() ) {
        scan.nextLine();
        counter.increment();
      }
      scan.close();
    } catch( Exception ex ) {
      ex.printStackTrace();
    }
  }
}  
CountFiles.java
/**
 * Counts the lines in the given files. Sums all counts up.
 * One thread per given filename command-line argument.
 */
public class CountFiles {

  public static void main(String[] args) {
    SafeCounter counter = new SafeCounter();

    CountThread[] threads = new CountThread[args.length];
    for( int xx = 0; xx < args.length; xx++ )
      threads[xx] = new CountThread(args[xx], counter);

    for( int xx = 0; xx < args.length; xx++ )
      threads[xx].start();

    try {
      for( int xx = 0; xx < args.length; xx++ )
        threads[xx].join();
    } catch( Exception ex ) {
      ex.printStackTrace();
    }

    System.out.println("Final count = " + counter.getValue());
  }
}

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 possibility 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 get added to the event queue? 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:

final JTextField tfp = tf;
java.awt.EventQueue.invokeLater(
   new Runnable() {
     public void run() { tfp.setText("0.0"); }
   }
);

The "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".

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!