Java exercises
Answers can be found here.
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
- 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:
The airport IT department, developing the application
Main3
, does not have access toJDisplay2
, but only to the interface and an object file. Thus they have to solve the problem without modifyingJDisplay2
. One way to do this is to identify the critical sections inMain3
and protect them using a semaphore. Do this! You should use an instance ofjava.util.concurrent.Semaphore
for this purpose. (java.util.concurrent
is a new package from Java 1.5.) Note that the methodacquire()
may throw anInterruptedException
, so you will have to use atry
/catch
construction. Test your program again to see that it seems to behave correctly. We say "seems", since you should now have an initial feeling for the difficulties in testing a concurrent program.The IT department has also complained to the display manufacturer, requesting a thread safe implementation of
JDisplay2
. Fulfill this request. It is easy: just add the modifiersynchronized
to the header of each method. We will explain this later in the course, but for the moment you should just check that your initialMain3
(without the semaphore) together with your thread safeJDisplay2
gives a correct program. As a final remark, we just note that it is an important but non-trivial design decision whether to make a class thread safe. For multi-threaded use it is essential, but it does imply a performance penalty. An example of a large library that is not thread safe is the Swing library for GUI's. One possibility, used in the Collections framework, is to provide both unsynchronized base implementations and synchronized wrapper classes. You may want to think of still another fix to the original program: instead of using semaphores, the IT department could have produced a simple synchronized wrapper class forJDisplay2.java
.
Introduction to resource and barrier synchronization
In this exercise 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:
Ball.java
An instance of this class is a ball, that lives in a BallWorld. The class is a subclass of
Thread
and its run is an infinite loop where the ball repeatedly makes a move that updates its position, calls forces the world to repaint and sleeps for a short while (30 ms). The ball also has the ability to draw itself, given a graphics context. Furthermore, upon creation (i.e. in its constructor), the ball registers itself with the world it lives in by calling the world'saddBall
method.BallWorld.java
An instance of this is a world, that may contain several balls, stored in an
ArrayList
. A world is a subclass ofJPanel
, theSwing
class used as a drawing surface. Consequently, the world can draw itself, which it does in thepaintComponent
method by asking all its contained balls to draw themselves. The details ofSwing
painting are of less importance to the exercises, but the serious Java programmer must know more, in particular about the reasons for the complications inBallWorld.addBall
.Balls.java
This class contains the main method, which creates a world and a couple of balls and adds the world to a
Swing
window.
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.
Problem 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.
Problem 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.
Problem 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.
Problem 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.
Sieves and Bridges
Java Problem: 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 a zip file ex3-java. 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?