Exercises

This page contains several exercises to practice concurrent programming, get to know Java and Erlang, and prepare yourselves for the assignments. We also provide some exercises using the language Promela and the related tool Spin, which can be used to simulate and formally verify that certain concurrency-related properties are satisfied by models of your programs. None of the exercises are mandatory.

Java exercises

Solutions to the Java exercises can be found here

Exercise 1: A shared counter

In this problem we 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 controlling 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 a huge number of 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();
id = name.equals("thread1") ? 1 : 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();
      id = name.equals("thread1") ? 1 : 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.

Exercise 2: A split-flap display

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

Split-flap display

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.

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

unzip displayJava.zip

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’s conventions, 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.

The 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:

Exercise on barrier synchronization

In these exercises you will practice creating threads and using semaphores to synchronize their behaviour. We will start from a program that opens a window in which a couple of “balls” start moving, bouncing against the walls.

Download the program to your working directory and unzip the file. You will find three classes:

Please note that the (concurent) control flow in this example is rather subtle. The moving of balls and repainting is initiated independently by each of the balls, as each of them is running a separate thread of control. Because of that, different balls may execute doMove() and world.repaint() concurrently. Calling world.repaint() concurrently is OK, as stated in the Swing documentation. But calling repaint() also triggers calling the draw() method of all the balls registered with the world. This is again OK, because both draw() and doMove() methods are synchronized, which means that they will not be called concurrently for a given object.

As you can see, this very simple program already has complicated concurrency. It is acceptable to have a design like this for simple programs, but for anything larger its concurrent behaviour must be designed in a structurred way, or else it will be extremely complicated.

Now back to the exercise. Compile and run the program:

javac *.java
java Balls

Look at the classes and make sure that you understand them.

Exercise 3.1: Killing the balls

Your first task is to add still another thread to your program that kills the balls at random times (i.e. with short random delays in between). But the balls should be killed in random order. Killing a ball means that its run method must terminate. This should be achieved by making the loop terminate normally and NOT by calling the deprecated method to stop a thread. Further, the ball must be removed from the world (in a thread-safe way similar to addBalls). After this has been done the garbage collector in the run-time system will eventually reclaim the space allocated for the ball object.

To solve the problem you can make use of a semaphore that the balls try to acquire in order to “get permission to die”. The semaphore is initially zero and then released a number of times in a thread started in main. Note that it is very useful to try to acquire the semaphore, using its tryAcquire method.

Implement this and test your program. Make sure that you understand how the design makes the killing order unpredictable. If you want, you can change the behaviour of the program further so that killed balls are reborn after some (random) time.

Exercise 3.2: Freezing the balls

Now return to the original version of the program (make a new directory and download the program again).

You must now modify the program to achieve the following behaviour: When a bouncing ball after one of its moves finds itself in the diagonal area of the world (i.e. where x is very close to y), it will “freeze”, i.e. stop moving. Note that a ball may jump over the diagonal area in one move; this will not cause it to freeze. When all balls have frozen at the diagonal, they will all wake up and continue bouncing until they freeze again on the diagonal. This bouncing/freezing continues forever.

You should recognize this as a form of barrier synchronization that can be achieved using N + 1 semaphores: one common barrier semaphore, which ball threads release when they reach the synchronization point, and an array of “continue” semaphores, indexed by thread, which threads acquire in order to continue beyond the barrier.

A special barrier synchronization process is also needed, which repeatedly acquire the barrier semaphore N times, followed by releasing all the continue semaphores.

Exercise 3.3: Freezing revisited

The package java.util.concurrent includes the class CyclicBarrier, which provides more convenient means to achieve barrier synchronization. Rewrite the program from the previous exercise using this class instead of semaphores.

Exercise 4: Your own CyclicBarrier

Now for a harder exercise: implement the body of your own class CyclicBarrier which provides similar features as the Java class of the same name. But we are content with a simpler version with the following spec:

public class CyclicBarrier {

   public CyclicBarrier(int parties);

   public void await();
}

The parameter parties is the number of threads that need to reach the barrier before they are all allowed to continue. Write the whole class and then use it to solve the ball-freezing problem again.

Hint: We cannot follow the array-of-semaphores approach directly, since that would require await to have a parameter i indicating the index of the semaphore on which to block. Instead, one could try to use a single semaphore on which all processes block and an integer variable counting how many processes have reached the barrier. But this integer variable is shared, so we need to protect updates to it using a second, mutex semaphor. We cannot use the Java synchronized locking instead of the mutex semaphore. Why?

Note that, however, trying to simply complete this idea, you will get a faulty solution that does not prevent a quick process from “stealing” a release from a slower process. You can fix this by using different semaphores for different cycles of the barrier.

To test your implementation, modify the bouncing balls program to use your new class.

Exercise 5: The single-lane bridge

A bridge over a river contains only a single lane, but cars enter from both direction. Consequently, some kind of synchronisation is needed to keep cars from colliding. To illustrate the problem we provide you with a malfunctioning solution, in which no synchronisation is performed. Your task is to add synchronisation to the cars. For fun we have included a compiled graphical interface.

The unsafe solution can be downloaded as ex3-java.zip. Compile and execute it. The GUI should be self-explanatory; using the two buttons you can add cars entering from the right or the left, respectively. You will see the cars colliding on the bridge.

As usual, you do not need to understand the graphics code in order to solve the problem. All you need to know is that cars going from left to right call the method controller.enterLeft() when they approach the bridge (to ask for permission) and call the method controller.leaveRight() when they leave. Cars in the other direction call enterRight and leaveLeft instead. Here, controller is an instance of the class TrafficController, which is responsible for synchronisation. As you can see, the supplied class has empty implementations of all four methods. Your task is to change this class into a monitor that coordinates cars so that they do not collide.

We recommend that you use the simple monitor mechanisms in class Object and not the more sophisticated tools in java.util.concurrent for this exercise.

There are many possible solutions this exercise - how many ways of synchronising the cars can you find? What are the differences between the ways? Is your implementation fair or could starvation occur?

Erlang exercises

The solutions to the Erlang exercises can be found here.

General syntax

Simple message passing

> Pid = spawn(foo, avg_server, [0]).
Current average is 0
> Pid ! 10.
Current average is 5.0
> Pid ! 10.
Current average is 7.5
> Pid ! 10.
Current average is 8.75
> Pid = spawn(foo, avg_server, []).
> Pid ! 5.
The average of [5] is 5.0
> Pid ! 10.
The average of [5,10] is 7.5
> Pid ! 20.
The average of [5,10,20] is 11.666666666666666
> Pid ! 50.
The average of [5,10,20,50] is 21.25
new_queue()      % returns a process ID to a queue server
push(Pid, Value) % add Value to end of queue
pop(Pid)         % pop first item from front of queue. If queue is empty, this should block@

Here is an example of these functions in use, again assuming you have put your code in a module foo:

> Pid = foo:new_queue().
> foo:push(Pid, "hello").
> foo:push(Pid, {tuple}).
> foo:pop(Pid).
"hello"
> foo:push(Pid, 333).
> foo:pop(Pid).
{tuple}
> foo:pop(Pid).
333
> spawn(fun() -> X = foo:pop(Pid), io:fwrite("I finally got: ~p~n", [X]) end).
% ... pause ...
> foo:push([4,4]).
I finally got: [4,4]

Semaphores in Erlang

(This exercise is from the exam 2015-10)

During the course, we have seen different kind of primitives for concurrent programming: semaphores, monitors, message passing, etc. In fact, we mentioned that these primitives are equally expressive, i.e., what you can do with semaphores, you can do with monitors, what you can do with monitors, you can do with semaphores, and so on. In this exercise, we are going to show that message passing is able to encode semaphores.

Q1: implement the following Erlang module.

-module(sem).
-export([createSem/1, acquire/1, release/1]).

createSem(InitialValue) -> ...
acquire(Semaphore) -> ...
release(Semaphore) -> ...

Erlang’s processes can, for instance, use this module in the following manner:

Mutex = createSem(0),
acquire(Mutex),
%% critical section
release(Mutex),
%% rest of the program
.

Acquiring or releasing a semaphore should not delay acquiring or releasing another one—every semaphore minds its own business.

Q2: write some code to test your implementation. It should spawn a bunch of processes, each of which uses the semaphore to control access to some shared resource. Use it to convince yourself that two processes are not able to obtain the semaphone simultaneously.

Elevator

(This exercise is from the exam 2016-03)

You are developing a networking module for an application. The main operation of the module is send(H, Msg), which takes a handle and a message, and sends them over the network. Here is the code of the module, which implements this operaion.

-module(network).

-export([start/0, send/2]).

start() -> spawn(fun () -> loop () end).

request(Pid, Data) ->
  Ref = make_ref(),
  Pid!{request, self(), Ref, Data},
  receive
    {result, Ref, Result} -> Result
  end.

send(Pid, Msg) ->
  request(Pid, {send, Msg}).

loop() ->
  receive
    {request, Pid, Ref, {send, Msg}} ->
      net_io:transmit([Msg]),
      Pid ! {result, Ref, ok},
      loop()
  end.

The function start() starts a new instance of the service and returns a handle to it. The function send(H, Msg) sends a message using the low-level net_io:transmit() function and returns ok. The net_io:transmit() function takes a list of messages to send at once. For simpicity we assume that net_io:transmit() does not take any additional argument to specify the end point.

Q1: Since sending a single message at a time has a large overhead, your team decides that calling send() should not send each message at once, but wait until ten messages are accumulated and send all of them with a single call to net_io:transmit(). Change the network module to provide the described behaviour.

Q2: Buffering of messages comes with its own disadvantages. In the scheme implemented in the previous task a single message might be delayed for an arbitrary amount of time if requests to send further messages arrive much later. To mitigate that, the network module should be modified so that no message is kept in the buffer for more than 100 ms. Thus, whenever the buffer contains a message that is 100 ms old all messages should be sent off without waiting for the remaining messages to fill the buffer. Implement the behaviour described above by modifying the network module.

Promela exercises

You can use the web interface for Spin, and you can download the Promela exercises in PDF format, along with a small errata.

Menu