Lab 11: Concurrency

The goal of this lab is to practice synchronizing among concurrent activities.

1. Introduction and set up

You will be working with a train simulation. There are two trains running on elliptical tracks that meet at four points. In the code as you get it, they will (almost certainly) crash at the crossings. You need to modify the code so that they do not crash.

Clone the repository for this lab to get started.

hg clone /cslab/class/csci245/lab11

2. Threads and synchronization in Java

We'll start by looking at the programs in the example directory. In class, we learned that a thread is an independently running entity, as if it has its very own processor. Within a Java program, you create a thread as an instance of the class Thread, passing it an instance of some class that implements the interface Runnable. When you call the thread's start() method, it starts running.

Take a look at Example1, compile it, and run it. You can run it with an integer argument if you try a different number of threads. Notice how it creates instances of RunPrinter and passes those to the constructor for Thread. There is no synchronization done in this version; so you should see the letters mixed together, and you'll see a different mix each time you run it.

The simple construct provided by Java is the ability to have a block of code marked as synchronized with respect to a particular object. What that looks like is

    synchronized(obj) {
        statements;
    }

For all synchronized blocks using the same object, Java enforces mutual exclusion—that is, it ensures that at most one of those blocks executes at any given time. We usually describe this by saying that the first thread that executes one of these blocks locks the object. If another thread attempts to lock the object, it will be forced to wait until the first one unlocks it by completing the statements.

Example2 introduces a String object on which to synchronize. (Using a String here is pretty lame, but this is a simple example.) Notice how the inner for loop is synchronized. Predict what will be different about the output of this program, then run it several times.

Example3 synchronizes the outer loop. Again, predict what you'll see, then run the program a few times to check. Be sure that you understand why some things change, and others don't.

Finally, look at Example4. Identify the object used for synchronization. Predict the output, and then check you prediction.

3. The trains

Now turn your attention to the trains subdirectory. Open the files Train.java, Track.java, and TrackPosition.java. (You will not be able to easily use Eclipse for this, because you have been provided a bunch of classes with the compiled version only, which Eclipse doesn't approve of.)

Try running the program as it is and confirm that the trains crash. The main method is in the class trains/Trains, and it will run repeatably with no additional command line arguments.

The tracks are drawn in red, with the crossing locations in a lighter color. The trains are drawn in blue and green. You might notice that the trains are of different lengths, and they move at different average speeds. It might not be quite as obvious that the two tracks are not exactly the same length.

The program runs each train as its own thread. Your job is to fix the Train so that the trains no longer crash. All the coding you need to do is in Train.java. All you need to know about the rest of the code you can learn by looking at the interfaces Track.java and TrackPosition.java. The other thing you need to know is how to synchronize between threads, which was demonstrated above.

In this program, some of the code that you don't see does the creation of a thread for each of the trains, and the class Train provides the instance of Runnable. So all of the interesting action happens in the method run().

The difficulty comes when two trains try to occupy the same TrackPosition where the tracks cross.

In Java, you would usually try to design a class so that its methods will be automatically synchronized as necessary. (In fact, the concrete classes for the simulation, such as those representing the tracks, have already been written in this way.) But in this problem, we have deliberately exposed the possibility of a train trying to go() into a position that is already occupied by another train.

To keep more than one train from go()-ing into a single position on the track, you will need to think about

1. what to lock,
2. when to lock it, and
3. how long to keep it locked.

Be sure to include comments in your code that describe your reasoning.1

4. Other testing

If you run the program with an extra argument, as in

java trains/Trains random

5. Handing in

Be sure that you have everything committed to your Mercurial repository. Then, from your lab11 directory, turn it in with

/cslab/class/csci245/bin/handin lab11 .hg heap/*.java

Be sure that both partners have a copy of the code before you leave.