|
|
|
|
|
02152 Concurrent Systems Fall 2008 |
Mandatory Assignment 1: Car Control |
| Home | Plan | Material |
To demonstrate ability to solve and implement non-trivial synchronization problems using both semaphores and Java monitors.
Following a long tradition of Concurrent Programming, the problem is cast in a made-up setting:
At a playground, 8 pedal-driven cars are available for the children to use. Each car must follow a given track circling around a hut on the ground. Some of the cars go one way round, some the other way (rounding a shed in the corner). Unfortunately, the alley behind the hut has one lane only. Each car has to pass a special gate on the track, where it may be stopped if needed. A special 9-th car (Car no. 0) is available for the youngest children. It follows its own tiny track that does not intersect the other ones. Those toddlers really go incredibly fast! Everything usually goes fine although the cars bump into each other from time to time. When the cars meet front-to-front in the alley, the children sort it out their own way...
One day it is decided to upgrade the cars to battery driven ones. Since these are very expensive, a control system should ensure that they do not bump into each other anymore. And now the playground attendants also get ideas about new functionalities...
You have been engaged to implement this control system.
[All files mentioned below have been packed into mandat1.jar, see later.]
Your are given a Java-class Cars.java that provides a graphical user interface (GUI) illustrating the state of the playground and the cars. The GUI also allows for starting and stopping the cars and activating a barrier (described later).
You must provide (several versions of) a Java class CarControl that runs and controls the cars. A prototype of the class (with auxiliary classes) is given here.
The means of interaction between the graphics and the control parts is given by two interfaces. The CarDisplayI.java provides methods for the control part to move the cars around and to display various messages. The CarControlI.java defines the methods by which the GUI requests change of the control.
The playground is structured as a 11 rows times 12 columns matrix of fields using (row,col)-indexing starting with (0,0) at the left-most field of the the top row. To communicate such matrix positions, an auxiliary class Pos.java is used by the interfaces.
Your class CarControl must have the form:
public class CarControl implements CarControlI {
public CarControl(CarDisplayI cd) { ... }
...
}
The program is run by the command
which will create the GUI and make a single instance of your class, passing it an implementation of CarDisplayI. The CarControlI-methods of your class will then be called when the various buttons are activated in the GUI.
For testing purposes, a special test class must be provided as described later.
Even though you may feel tempted to improve upon the graphics, you are not supposed to make any changes to any classes in the Cars.java file. Correspondingly, your CarControl is only allowed to access the information provided by Cars.java through the CarDisplayI interface.
You will have to change the contents of the CarControl class as well as other auxiliary classes in the CarControl.java file.
You are, however, not allowed to change the track or the direction of any car (determined by the function nextPos()). You may change the colour and speed of the cars except for Car no. 0 that should remain ultra-fast.
In the first three problem steps (see below), you should assume that you are in an environment where the only synchronization mechanism available is that of semaphores. For this, you must use the provided class Semaphore.java that implements a classical, weakly-fair Dijkstra semaphore.
The given Semaphore class should not be changed.
In the following, EXTRA marks optional elaborate topics some of which are required for groups of 3 persons (see "Group Work" later).
Step 1,3,4 and 5 should be solved in proper order. Step 2 may be solved after Step 1, but independently of the rest.
Analyze, solve and implement the following control problems:
You can check that bumping does not take place by setting the mark called "Keep crash".
It is recommended to implement the alley synchronization by an instance of a class of the form:
class Alley{
public void enter(int no)
public void leave(int no)
}
Here enter(i) is to be called by car no. i in order to get access to the alley and leave(i) is to be called when car no. i leaves the alley. The car number may be used to determine the direction of the car.
It is acceptable that the cars no. 1 and 2 may experience a slight delay when entering the alley. You should not try to optimize this in this step.
The attendants' coffee room is situated in the hut towards the alley, so to let them have some calm coffee breaks, it has been made possible to apply speed reduction in the alley (by setting the mark called "Slowdown").
You should discuss to which extent the cars may experience starvation in your solution, both with and without the alley speed reduction. However, you are not requested to make a fair solution (preventing starvation) in this step.
Use SPIN to demonstrate that your solution to the alley synchronization problem is correct.
Make a Promela model of your system which reflects the synchronization done at the entry and exit points of the alley. The model should not deal with details of the field synchronization used to avoid bumping. Use macros/inlines to define the semaphore operations and to mimic the structure of your solution.
State and verify relevant safety and liveness properties. Give priority to safety. If the properties do not hold, comment on this.
Every day, the children start to argue because some of them make more rounds than the others. To solve this problem, the playground attendants suggest that the cars stop at a barrier line until all have made a round, before starting a new one. It should be possible to turn stopping at the barrier on and off as needed.
Analyze, solve, and implement such a basic on/off barrier. The barrier must work independently of the gates, i.e. when the bar is active, all cars must be waited for, even if some cars have been temporarily stopped at the gate.
It is recommended to represent the barrier as an instance of a class of the form:
class Barrier {
public void sync() { ... } // Wait for others to arrive (if barrier active)
public void on() { ... } // Activate barrier
public void off() { ... } // Deactivate barrier
}
Initially, the barrier should be inactive. In this state, cars should just pass the barrier. When the barrier is active, cars arriving at the barrier must wait in front of it until all cars have arrived. Whenever this happens, all cars are released. If any cars are waiting at the barrier when it is deactivated, they must be released.
The barrier should be able to deal properly with the special car no. 0 which after being released may get back to the barrier again in almost no time.
As in Step 1, the only synchronization mechanism allowed is the given Semaphore class.
EXTRA (A) Verify your barrier solution using SPIN.
[Note that it is not trivial to state the required properties of an on/off barrier in a formal way. You may restrict your verification to the case where the barrier is assumed to be permanently activated.]
EXTRA (B) Generalize the functionality of the basic barrier to allow for a variable threshold of cars that must be present before the cars are released. As for the basic barrier, cars must pass through when inactive. When the barrier is active, cars arriving at the barrier must wait until a number of cars corresponding to the last set threshold value, k, have arrived. Whenever the number of waiting cars reaches k (or happens to exceed k after decreasing the threshold), all waiting cars must be released. If any cars are waiting at the barrier when it is deactivated, they must be released. The value of the threshold is not affected by the barrier being turned on/off.
From now on, you are allowed to use Java monitors. Discuss for which of the synchronization issues solved so far (field, alley, barrier), a monitor solution would seem more convenient.
Implement the alley synchronization and the on/off barrier as a monitors.
EXTRA (C) Implement the alley synchronization monitor such that it is fair (i.e. prevents starvation).
EXTRA (D) Optimize the alley synchronization such that cars no. 1 and 2 may enter the alley as soon as possible.[Hard.]
Now, the attendants would like to be able to immediately remove a car for service (wherever it is) and restore it later. The car should be restored at its gate position.
For a solution to the previous steps, using either semaphores, monitors or a mixture of these, carefully analyze, solve and implement such a facility under the assumption that the barrier is not used.
In the GUI, a removal of a car is requested by [SHIFT+Click] at the gate and restoration by [CTRL+Click] at the gate.
EXTRA (E) Provide a solution that also works when the barrier is used such that:
(If your also did the EXTRA (C), this extension may assume that the threshold functionality is not used, ie. remains at 9.)
Although subtle concurrent programming bugs, e.g. race conditions, cannot be expected to be discovered by even intensive program execution, testing is still useful for discovering more mundane programming errors and to demonstrate functionality.
In the given system, the GUI allows for manual functional testing. However, in order to repeat tests or to make more precise stimulation of the system than manually possible, a testing facility has been built into the user interface.
This is simply a means for activating a sequential thread that may "press the buttons" of the interface. More precisely, it may call the same abstract event methods as the GUI does. This interface is given by CarTestingI.java. An object implementing this is passed to the test together with a test number.
The interface allows for controlling the speed of the cars in order to demonstrate particular scenarios.
Your test class file must be called CarTest.java and must have the form:
public class CarTest extends Thread {
public CarTest(CarTestingI ct, int no) { ... }
...
}
A prototype test class is given here.
Only one test thread will be activated at a time. The manual stimuli may still be applied when a test is going on, being interleaved with the automatic ones.
For each test case, you should document (in the code) what the test demonstrates and what the resulting behaviour should be.
You may provide a test class for each version of your control class. In the report you should give an overall description of the manual and/or automated testing you have conducted at the various steps.
You may refer to particular tests that will demonstrate a certain behaviours, but you should not expect tests to be tried out as part of the evaluation.
The assignment is intended to be solved and reported in 20-25 hours each for a group of 2-3 (well-prepared) students. For evaluation criteria, see below.
Groups of two are not required to do any of the EXTRA s, whereas groups of three students must do at least two of the EXTRA topics.
On the groups page, you can find information on forming and registering your group.
Please read the general report requirements carefully. Especially note the paragraphs on declaration of work distribution and on use of other work.
Although you should in general not include larger pieces of program code in the actual report text, some of the code of interest in this assignment will be small synchronization classes that may be fully included in the main text. No debug code should appear in the proper report though.
For this assignment, emphasis is put on correctness of solutions. For those steps that are not verified by SPIN, you are are encouraged to formulate (formally or informally) safety and liveness properties, state invariants, and provide abstract solutions using coarse-grained atomic actions, wherever you find it relevant and helpful for the presentation.
It is recommended that the report deals with the steps in order. For each step, the nature of the problem should analyzed, alternative solution principles discussed and the implementation described. The correctness of the solution should be argued/verified.
The main report text (not including appendices) should not exceed 12 (2 students) or 15 (3 students) pages. The report should be ended by a conclusion on your experiences.
The report must include appendices with easily navigable printouts of the files CarControl.java and CarTest.java (as well as any auxiliary file you may have added) for each version of your system.
Each group must hand in one paper copy of the report no later than
in the boxes at the West entrance of Building 322.
The report must be signed by all group members.
The program files for this assignment must be delivered electronically as well (also before the deadline). Details of this will appear on the update page.
This assignment will - together with the second mandatory assignment and the written exam - contribute to the overall mark given for the course. Together, the two assignments will count approximately the same as the written exam.
You will receive some feedback for this assignment, but no definite mark will be given.
High scores will be given only to work that is both fully functional and correct as well as concisely analyzed and described using the terminology introduced in the course. It should be possible to understand the work from the report proper without having to resolve issues by code inspection.
Emphasis is put on the concurrent programming issues, in particular, the solutions should be free from race conditions. Solutions need not be optimal, but should not be obviously inefficient. If polling (repeated try, semi-busy wait) is used, its implications should be discussed. Busy waiting is banned.
You may not be able to address all problem steps. However, satisfactory solutions to Steps 1-4 are required in order to get a passing grade.
Groups of 3 students are expected to make more comprehensive solutions by picking two extra topics as described above. In general the extra topics are more demanding and should not be embarked upon until satisfactory solutions to the basic problems have been found.
All the files needed have been put together in the file mandat1.jar.You can unpack this by the command
and compile and run the system by:
Alternatively you can import the .jar-file into your favourite Java IDE, eg. Eclipse.
No particular package-scheme is applied for this application. Therefore all classes must be placed and compiled in the same directory.
In this assignment, you should prepare several versions of the file CarControl.java: One for Step 3 (including Step 1) possibly one for Step 4, and one for Step 5 (possibly including Step 4). In the beginning of your files, the actual version should be clearly indicated. It is recommended to develop different versions in different directories/projects to avoid name clashes.
Your files will be tested using JDK version 1.6, but may be developed in any recent version of Java.
For Step 2 (and EXTRA (A)), files containing the Promela model and possible LTL property files must be provided.
Assistance for the assignment will be available in the G-databar as indicated on the course plan.
Also, clarifications, FAQs and packaging instructions will appear on the special update page for this assignment.
This assignment concentrates a number of concurrency issues into a single, contrived setting. In real applications, such problems are likely to appear much more sparsely. However, the intricate problems arising from the combination of cancellation and synchronization are typical of realistic systems.
Have fun!
| Hans Henrik Løvengreen, Sep 24, 2008 |