Shared variables and critical sections

Problem 1: A shared counter

In this problem we will consider the following Java program:

class Counter implements Runnable {

  private int counter = 0;
  private final int rounds = 100000;

  public void run () {
//    try {
      for(int i = 0; i < rounds; i++) {
        counter++;
      }
//    } catch (InterruptedException e) {
//      System.out.println ("Interrupted!");
//    }
  }

  public static void main (String[] args) {
    try {
      Counter c = new Counter ();

      // Create two threads that run our run () method.
      Thread t1 = new Thread (c, "thread1");
      Thread t2 = new Thread (c, "thread2");

      t1.start (); t2.start ();

      // Wait for the threads to finish.
      t1.join (); t2.join ();

      // Print the counter
      System.out.println(c.counter);
    } catch (InterruptedException e) {
      System.out.println ("Interrupted!");
    }
  }
}

The main method creates a Counter object and runs two threads on it, both running its run() method, which updates the shared counter. After both threads have updated the counter 100000 times, they finish and its value is printed. The expected output is 200000. Compile and run the program.

The results that you get may depend on the hardware, operating system and the version of the Java environment. If you are running it on a multi-core machine, it is quite likely that at least some of the runs will give different results than 200000.

The reason for this is that incrementing the counter is in fact not one basic operation, but two. Code counter++ gets compiled into something like this:

int tmp = counter;
counter = tmp + 1;

So while one thread is about to write the new value to the shared counter variable the other one might update it several times (or even very many times) in the mean time. The Java standard does not guarantee that the threads will run synchronized in any way. And in fact they often are completely unsynchronized and execute in a very surprising order. Whenever a particular order of executing code in different threads causes the program to make an error, we call it a race condition. In this case it's a race condition between two threads reading and updating the same counter.

How to fix this problem? One possible way is to restrict the way in which operations of the two threads may be ordered. In particular, we don't want one thread to read and change the counter when the other one has read it but not updated it yet.

In short, we want to make sure that at most one thread at a time is executing the code that reads and updates the counter. This property is called mutual exclusion and one way to achieve it is to use the synchronized keyword in Java. Replace the line counter++ with this code:

synchronized (this) {
          counter++;
}

What we have added is a synchronized block, which makes sure that no other synchronized block from the same object (this) executes at the same time. In our case, this means that the other thread, which tries to enters the synchronized block on the same Counter object, will have to wait until the first thread leaves the block.

Recompile and run the example, and now the printed value should always be 200000. We haven't changed the actual operations performed by the program, but by controling the order in which operations are performed we made sure that the result will be correct.

Now comes the main part of the exercise. Your job will be to find out what could be the least value of the counter reported by the original, unsynchronized, program. You will also have to demonstrate that happening. But instead of running the program 1000000000 times and hoping to get the very unlikely result you will be able to pause the threads in strategic moments to get a good chance of getting the results.

Start by taking the original program (without the synchronized block) and replace counter++ with

int tmp = counter;
counter = tmp + 1;

Now you will add a number of lines like this to the loop:

if (id== ?? && i== ??) Thread.sleep(??)

Each line will delay one thread on a specific iteration of the loop by a specific number of milliseconds. To be able to tell which thread you are in, you have to add this code to the beginning of the run() method:

int id;
String name = Thread.currentThread().getName();
if (name.equals("thread1")) id = 1;
else id = 2;

Note that in normal programs you should identify threads by using your own data (for example integers) as identifiers. Thread.getName() is good for debugging. Also, because Thread.sleep() is interruptible, it may throw a InterruptedException, which we have to catch here. This exception is used to for safe thread cancellation, and we will not deal with this topic in this exercise. Instead, we will just catch it and ignore it. For that, you need to uncomment the try-catch block in the run() method.

class Counter implements Runnable {

  private int counter = 0;
  private final int rounds = 100000;

  public void run () {
    try {
      int id;
      String name = Thread.currentThread().getName();
      if (name.equals("thread1")) id = 1;
      else id = 2;
      for(int i = 0; i < rounds; i++) {
        // Delay here?
        int tmp = counter;
        // Perhaps here?
        counter = tmp + 1;
        // Or here?
      }
    } catch (InterruptedException e) {
      System.out.println ("Interrupted!");
    }
  }

  public static void main (String[] args) {
    try {
      Counter c = new Counter ();

      // Create two threads that run our run () method.
      Thread t1 = new Thread (c, "thread1");
      Thread t2 = new Thread (c, "thread2");

      t1.start (); t2.start ();

      // Wait for the threads to finish.
      t1.join (); t2.join ();

      // Print the counter
      System.out.println(c.counter);

    } catch (InterruptedException e) {
      System.out.println ("Interrupted!");
    }
  }
}

Find out what is the least number the program could report and demonstrate this by inserting delays.

Here are conclusions that we would like to draw from the above exercise. First, we demonstrated that even simple data manipulation can give corrupted results if it is performed by many threads concurrently without proper synchronization. Data corruption is a common problem with buggy concurrent code. Secondly, sometimes concurrent programs can give very unexpected results if a very specific (and unlikely) ordering of concurrent actions takes place. We were able to fix the concurrency problem by restricting different possible orderings of actions performed by different threads using synchronization.

Problem 2: An information display

In this example we will consider a display of the kind commonly found in airports, where information about upcoming flights is given:

We will study the programming of such a display in Java. This will enable us to study simple situations where concurrent threads interfere in their use of a shared data structure. The Java exercise should also be possible to do on any platform, given that Java 1.5 is available.

First download the file displayJava.zip to a suitable working directory. Then decompress:

$ unzip displayJava.zip 
Archive:  displayJava.zip
   creating: java/
  inflating: java/HighLevelDisplay.java     
  inflating: java/HWDisplay.java     
  inflating: java/JDisplay.java      
  inflating: java/JDisplay2.java     
  inflating: java/Main1.java         
  inflating: java/Main2.java         
  inflating: java/Main3.java         
$ ls java
HWDisplay.java          JDisplay2.java          Main3.java
HighLevelDisplay.java   Main1.java
JDisplay.java           Main2.java

Unfortunately, we do not have access to a real 10 square meter hardware display, so we have here instead a complete Java implementation, where the display is visualized using the Java Swing library. However, we should think of this as a simulation of the programming of a hardware device in the following way.

The hardware is accessed using the following simple API, found in the file HWDisplay.java:

public interface HWDisplay {
    public int getRows();
    public int getCols();
    public void write(int row, int col, char c);
}

The two first methods return the number of rows and columns, respectively, in the display (presumably the device comes in different sizes). The third is used to write one character in the specified row and column. Following Java practice, we start counting rows and columns from 0.

The file JDisplay.java contains an implementation of this API using Swing. You do not need to look into this file for this exercise. It contains a lot of low-level detail specific to Java's GUI libraries, which are not essential for this course. Instead, look at Main1.java for a simple main program that writes an A and a B at different positions in the display, then waits for three seconds and finally removes the A. After that, the program just waits for further input and you have to kill it using Ctrl-C. To see this in action, do as follows:

$ javac *.java
$ java Main1

You may note the convenient function nap for future use.

However, it is clear that the interface HWDisplay is much too low-level for actually programming the display. Therefore, the manufacturer provides also HighLevelDisplay.java, which is much more convenient to use:

public interface HighLevelDisplay {

    public void clear();
    public void addRow(String str);
    public void deleteRow(int row);

}

The method clear removes all text from the display. addRow(str) adds the string str as the new last row, after the last existing line. Finally, deleteRow(r) deletes row r, shifting all rows below up one slot. Also, the intention is that one can add rows also when the display is fully used; this row will not be visible on screen until enough rows above has been deleted. Finally, the last visible change is highlighted by flashing a few times. All this should of course be more fully documented, preferrably using javadoc, but we have intentionally left this out so as not to clutter the code.

he display manufacturer also provides an implementation of this interface in the file JDisplay2.java. You should study and understand this class, but first you may want to run a simple demo:

$ java Main2

We will not have time to try to think of a full-fledged program for the airport administration using this API, but just note that it is conceivable that the display will be accessed from a multi-threaded program, with several airport officials concurrently updating the display. To test the class JDisplay2 under such conditions, your task now is to write a simple multi-threaded program. A skeleton is found in the file Main3.java, which shows the structure of a simple main program that creates a display d and starts two threads, one executing the static procedure addProc(d), the other executing deleteProc(d). You must complete the bodies of these two procedures. Fill addProc with a sequence of addRow commands, interspersed with suitable naps. Similarly, fill deleteProc with calls to deleteRow(0). To allow for a not too boring simulation, naps should be in the order of seconds (or fractions of seconds) and not minutes as in a real airport.

If you do this and run your program, you will probably see some un-intended behaviour. You should make sure that you understand how these problems can occur. In fact, the class JDisplay2 is not thread safe; it does not guarantee correct behaviour when its methods are accessed by concurrent threads.

We will now fix this problem in two different ways: