Sieves and Bridges

There are two exercises this week, one for Java and one for JR. Each one practices a different skill (synchronous message passing and dynamic process creation in JR, and monitor-based synchronisation in Java, respectively).

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?

JR Problem: Dynamic Sieves

Asynchronous and synchronous message passing can be used to calculate a sequence of prime numbers by the sieve of Eratosthenes, in which filter processes are created that filters out non prime numbers. The filters are chained together and connected to a producer that produces the initial input sequence. Your task is to write a version that dynamically creates new sieving processes so as to be able to produce an arbitrary number of primes (in theory :-) ). To start with, you may want to read previous term materials (Lectures 6 and 7) to find an introduction to the Sieve of Eratosthenes and for skeleton JR.

This can be seen as a test of your overall JR language skills and your understanding of the problem. In particular you will need to dynamically create ops (channels) and pass references to them (capabilities) to achieve this.

Can you find a way to terminate the pipeline after a desired number of primes generated? For example sending a special value at the end. If you feel you don't know how to handle termination properly - just forget it ever existed, JR will automatically terminate once all processes stopped/deadlocked.

Implement a solution which works using synchronous message passing (call). Test the implementation using both synchronous and asynchronous message passing; only minimal code changes should be needed. Does it work? Are there any noticeable differences in execution time? Can you explain your results?

Practical note: for large number of generated primes it might be necessary to run the program by explicity running java inside the jrGen and supply stack size using -Xss option, for example java -Xss48k Sieve