Introduction to resource and barrier synchronization

We will start from a program that opens a window in which a couple of "balls" start moving, bouncing against the walls.

Java version

• 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 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's addBall method.
• BallWorld.java.
  An instance of this is a world, that may contain several balls, stored in an ArrayList. A world is a subclass of JPanel, the Swing class used as a drawing surface. Consequently, the world can draw itself, which it does in the paintComponent method by asking all its contained balls to draw themselves. The details of Swing painting are of less importance to the exercises, but the serious Java programmer must know more, in particular about the reasons for the complications in BallWorld.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. It also creates a thread which repeatedly asks the world to draw itself by calling the window's repaint method.

javac *.java
java Balls

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 inbetween). 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. But don't spend all time on this exercise. You should also have some time both for the next Java exercise and the MPD versions.

Freezing the balls

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 semaphors. See slide 36 of lecture 6 for details.

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.

MPD version

The window handling and graphics routines are of course different; you should NOT try to learn to do GUI programming in MPD unless you are particularly interested. In this course you will not be asked to do any such programming. Now you will solve the same two problems as in Java. However, we propose that you start with the second problem.

Freezing the balls

If you have solved the Java version of this problem, an MPD version using semaphores should be straightforward. Do it anyhow! You might need the try_p() (see below).

Now for a harder exercise: Implement the body of a resource 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:

resource cyclicBarrier

  op await()

body cyclicBarrier(int parties) separate

body cyclicBarrier

  sem barrier = 0
  sem mutex = 1

  int arrived = 0

  proc await() {
    P(mutex)
    arrived++
    ...
  }

end

Note that, however, trying to complete this, you will get a faulty solution that does not prevent a quick process from "stealing" a V from a slower process. Optionally, you can fix this by using two barrier semaphores that are used in alternating turns. But, as we warned above, this is a bit tricky.

To test your implementation, modify the bouncing balls program to use this resource. Note that you must update the Makefile, since your MPD program now contains two more files, cyclicBarrier.spec.mpd and cyclicBarrier.body.mpd. This is done using mpdm:

mpdm coords.mpd colors.mpd ball.spec.mpd ball.body.mpd ballWorld.mpd cyclicBarrier.spec.mpd cyclicBarrier.body.mpd 
balls.mpd mpdwin.o -lX11

Killing the balls

If you have time, here is a final exercise. The task is to do the ball killing program in MPD.

Here you would also want semaphores with an operation similar to tryAcquire from the Java class. Such an operation is not available for MPD:s built-in semaphores. Therefore we provide you with an alternative semaphore resource. This is a formulation of a semaphore in MPD, which is not compatible with the native semaphores. Thus, you cannot use the P and V primitives.

To use the semaphores of this resource, write

import semaphore                          # import the package
...
cap semaphore mutex = create semaphore(1) # create a new semaphore
...
mutex.p()                                 # works as P
... Critical Section 
mutex.v()                                 # works as V

The resource also contains a non-blocking operation try_p() which is the correspondence to tryAcquire. It tries to acquire the semaphore but instead of blocking it returns immediately with return value true if the semaphore was acquired and false if it was not. (If you look into the file semaphore.mpd, it will be difficult to understand for the moment. Everything will be explained in a few weeks! For now, you should rely on your understanding of the concept of semaphores and trust that the required behaviour is implemented.)

mpdm coords.mpd colors.mpd ball.spec.mpd ball.body.mpd ballWorld.mpd semaphore.mpd balls.mpd mpdwin.o -lX11