|
|
|
|
|
02158 Concurrent Programming Fall 2024 |
Mandatory Assignment 3: Monitors and Cancellation in Java |
| Home | Plan | Material |
You should be familiar with the general notion of monitors as given in [Andrew 5-5.2] as well as Java's built-in monitor notion [Andrews 5.4], [Sync 5]. Also, you are supposed to have completed CP Lab 3.
The assignment extends the playground setting known from Mandatory Assignment 2 (and CP Lab 3). You should refer to this for a survey of the program structure.
All files for the assignment have been packed into man3.zip to be downloaded and integrated into your favourite IDE. Again, no package structure should be imposed.
Your solutions will be tested using JDK 17. If you compile with a higher version of Java, you must set the compliance level to 17.
The shed from CP Lab3 has now been torn down again as it caused too much inconvenience. Correspondingly, the innerLeave() mechanism has been removed.
Bumping is prevented by the given class Field class which should not be changed. You are also given a basic implementation BasicAlley.java of the Alley.java class.
However, 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.
For this the GUI has been extended with controls buttons for activating and deactivating the barrier. Furthermore the threshold of the barrier may be dynamically adjusted (in Problems 4 and 7).
In this assignment, you are supposed to analyze, solve, and implement various versions of such an 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 gates. [Remember that the gates may be individually opened/closed by clicking them.]
The barrier should be implemented as an extension of the given abstract class Barrier.java with the interface:
public abstract class Barrier {
static Barrier create(CarDisplayI cd) { ... }
public void sync(int no) { } // Wait for others to arrive (if barrier active)
public void on() { } // Activate barrier
public void off() { } // Deactivate barrier
public void set (int k) { } // For setting threshold
}
The on() and off() methods are called from barrierOn() and barrierOff() offered by the CarControl class as part of the CarControlI interface.
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 the barrier line until all cars have arrived. Whenever this happens, all cars are released and are let pass the barrier line. If any cars are waiting at the barrier when it is deactivated, they must all be released.
The barrier should be able to deal properly with extremely fast cars which after being released may get back to the barrier again in almost no time (such as the special car no. 0 and possibly others).
All barriers must be implemented as monitors. Except for Problem 7, the built-in Java monitor notion (based on synchronized methods) should be used.
You are given a proposed implemenation NaiveBarrier and several skeleton implementations. The static Barrier.create() factory method should be used to select the relevant implementation.
Describe your solution to Lab 3 C and hand in your MonGate.java file.
[Your solution may be used in the Mandatory 3 code base instead of SemGate if you like.]
A student from another university (none mentioned) has suggested a solution to the barrier problem given in the NaiveBarrier.java class. The student has tested the solution extensively and concludes that it works flawlessly.
Now, you should study the solution and:
Hand-in the remedied version of NaiveBarrier.java.
Although spurious wakeups are rare, they may occur. Therefore, you are now supposed to provide a basic solution of the barrier which works as specified and is resilent to spurious wakeups.
Analyze the problem carefully and describe your solution idea.
The solution should be implemented by filling out the SafeBarrier.java skeleton class and changing the Barrier.create() method to use this.
Hand-in the SafeBarrier.java file.
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 current threshold value, k, have arrived. Whenever the number of waiting cars reaches k all the waiting cars must be released.
The threshold value is to be changed using the barrierSet(k) method acativated from the GUI selector which again calls the set(k) in the barrier. The threshold must be within the range 1..9. Initially the threshold should be 9 corresponding to a basic barrier.
When k is less than or equal to the current threshold, the set() method should immediately change the threshold and return. If there are k or more cars waiting, they should all be released.
The children might get cross if they have to wait longer than would be expected when arriving at the barrier. Therefore, if there are cars waiting when the threshold is to be raised, the threshold change must be deferred until the next release (using the current threshold) or when the barrier is deactivated. Meanwhile, the call of barrierSet(k) should block, i.e. the call must not return until the new threshold can be set.
When the barrier is deactivated, all cars waiting at the barrrier must be released and any pending threshold setting must be finalized. The value of the threshold should otherwise not be affected by the barrier being turned on/off.
[The GUI will run barrierSet(k) asynchronously on its own thread but will ensure that only one setting is done at a time. Therefore, barrierSet() cannot be called again while barrierSet(k) is blocked. Any blocking can be observed as a colouring of the barrier.]
You should hand in the DynamicBarrier.java file.
To prevent car break-downs, the attendants would like to be able to immediately remove a car for service (wherever it is) and restore it later. A removed car should not show anywhere on the ground. The car must be restored to its gate position.
For a playground with the given Field and Alley classes, carefully analyze, design and implement such a facility. You should assume that the barrier is not activated (so it does not matter which version you use). For the gates, either the given SemGate or your own MonGate may be used.
The solution should be made by modifying the given CarControl and Conductor classes only.
In the GUI, a removal of a car is requested by [SHIFT+Click] at the gate and restoration by [CTRL+Click] at the gate.
It is acceptable (and recommended) to create a new Conductor object when restoring a car.
Pay special attention to the fact that cars may be restored immediately after being removed or vice versa (eg. using the test program).
Also, notice that cars must be removed even if they are blocked, e.g. waiting in the alley queue.
Hand in your revised CarControl.java file. If you also do Problem 6, a common version should be handed in.
Provide a remove/restore solution that also works when the basic barrier (without threshold setting) is used such that:
For this you should further modify the CarControl and Conductor classes as well as develop a new basic barrier by filling out the skeleton RemBarrier.java allowing for removal. Since this is likely to be extended with new methods, the barrier should explicitly be instantiated with this class in CarControl.java.
For this problem you should hand in the RemBarrier.java file as well as the combined, modified version of CarControl.java for both Problems 5 and 6.
This optional problem is more advanced and extra-curricular. It is offered for those that would appreciate a more production-like challenge.
In order to reduce the load on the alley, the playground attendants may stop the individual cars at the gates. However the children do not find this to be fair. Therefore, the attendants come up with the idea that the barrier construction could be reworked in order to control the number of currently active cars in a fair way. This sticky barrier should work as follows:
Conductor threads should still call sync() when arriving at the barrier line. The barrier has a current capacity k ranging from 1 to 9. When active, all cars should stop at the barrier line until the capacity of the barrier has been reached. When k cars waiting, any new car arriving should release one of the waiting cars keeping the number of blocked cars at k. For fairness, the cars should be released in first-in-first-out (FIFO) order. When deactivated all cars should be released.
The current capacity should be changed using the set() method controlled by the threshold setting. If the barrier is active, a change of capacity should have immediate effect. The initial capacity of the barrier should be 9 eventually stopping all cars.
Analyze the problem and describe your solution idea. Implement your solution as a Java monitor filling out the class StickyBarrier.java extending the Barrier class.
In order to control the order of thread wakeups, the solution calls for use of Java's elaborate Lock and Condition framework found in the lang.util.concurrency.locks package. Using this, each conductor thread may assigned its own private condition for waiting and wake up.
Hand in the StickyBarrier.java file.
For the basic alley solution, describe how starvartion may occur - especilly when slowing down the speed in the alley.
Now implement a monitor FairAlley.java so that the alley access becomes fair towards both upgoing and downgoing cars (i.e. so that starvation may not occur).
As a general fairness principle, one must prevent cars in one direction from (re-)entering the alley - at least if there are cars waiting in the other direction. The solution should still be efficient though, allowing cars to follow each other. Especially, it should work if all cars in one direction are trapped in their gates.
Hint: Use some extra fields to keep track of pending cars.
Hand in the FairAlley.java file.
The assignment should be made in groups of 2-3 students. If you for some reason would prefer to do the assignment on your own, you must get prior permission from the teacher (HHL) (if you have not already done so).
Your previous groups have been transferred to the Mandatory 3 Groups. If you have any changes to the groups, the teacher must me informed no later than Thursday November 7.
All groups should do Problems 1, 2, 3 and 5. Furthermore groups of 3 students are expected to do one of the extras: Problem 4, 6, 7, or 8. Notice that Problem 7 is extra-curricular.
Of course, each group must work on its own. In particular you must not exchange any form of code or texts with other groups. Any repositories you use, must be private.
Use of generative AI is not recommended, but if you do anyhow, it must be declared (for what and how).
The asssignment must be handed in on Inside no later than
The hand-in should comprise the following:
The report should include
Assistance for the assignment will be available on November 7, during the lab session as indicated on the course plan.
In case of amendments or updates, these will appear here. Major updates will be announced on DTU Learn.
Drive carefully!
| Hans Henrik Løvengreen, Nov 1, 2024 |