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?