COMPUTER SCIENCE 131A
OPERATING SYSTEMS
PROGRAMMING ASSIGNMENT 4
CARS AND TUNNELS PREEMPTIVE PRIORITY
SCHEDULER
Description
Now that you have written a non-preemptive priority scheduler for Cars and Sleds you will
now add a preemptive priority scheduler that can also handle a new Vehicle type,
Ambulances.
Ambulance
The Ambulance is a Vehicle that is guaranteed to have the highest priority of any non-
Ambulance Vehicles.
PreemptiveTunnel
The PreemptiveTunnel class will contain logic governing a Vehicle admittance policy
that includes Ambulances.
At all times, the PreemptiveTunnel’s state must satisfy the same policy as the
BasicTunnel, however, it must also handle Ambulances according to the following rules:
- An Ambulance can always enter a PreemptiveTunnel unless there is another
Ambulance already inside.
- When an Ambulance enters a PreemptiveTunnel all other Vehicles in the
PreemptiveTunnel must stop and wait for the Ambulance to exit the Tunnel
before continuing.
- Any Vehicle entering a PreemptiveTunnel when an Ambulance is currently
inside should enter then pull over immediately.
When a Vehicle is pulled over part-way through the PreemptiveTunnel, it should
continue driving from where they left off.
For example, consider a Vehicle that requires 100 ms to travel through the Tunnel. Suppose
it sleeps 70 ms before being preempted by an Ambulance. After the Ambulance leaves the
Tunnel, it should only sleep for another 30 ms.
Use Java’s System.currentTimeMillis() method to implement this behavior.
2
Pulling Over Vehicles
Before reading this section, you should first read the run method of the Vehicle class. In the
given implementation, the method simulating Vehicle behavior in a Tunnel,
doWhileInTunnel() simply has the Vehicle thread sleep for some amount of time
dependent on the speed field. In order to implement the concept of pulling over Vehicles in
the PreemptiveTunnel when an Ambulance enters, modifications need to be made to the
Vehicle’s doWhileInTunnel method.
You may use all of the multithreading concepts you have learned thus far in Java to solve this
problem, but you must use monitors to avoid busy waiting while an ambulance is in a
tunnel.
You may also add any additional fields or methods to the Vehicle class as you see fit. You
should not change the way log entries are entered in the Log.
Grading
There are no hidden unit tests that will be used for grading this assignment. To make sure you do
not have race conditions, set PrioritySchedulerTest.NUM_RUNS = 10.
Passing all of the test cases does not mean you will get a high score. Make sure that you:
● Properly achieve mutual exclusion using Java synchronization mechanisms. This includes
controlling access to shared data structures.
● Implement PreemptivePriorityScheduler’s admittance policy correctly. Your
solution must ensure that:
- Ambulances properly cause all other Tunnel occupants to cease driving till it
leaves. This includes the case of when a Vehicle enters a Tunnel occupied by
an Ambulance.
- Vehicles should properly resume driving after an Ambulance leaves.
- Ambulances should not wait unnecessarily for an opening.
Make sure you import and export the Eclipse project properly. The submitted project should
have a structure that looks exactly like the skeleton. An improperly structured project will
receive a 0.
Do not modify any files outside of the submission package. Failing to follow this
instruction will result in a 0.
The project needs to be renamed FirstnameLastnamePA4 (make sure to use Eclipse’s Refactor >
Rename). The zip file you submit should be named FirstnameLastnamePA4.zip.
3
Allowed Libraries
The only additional classes related to concurrency and synchronization you can use are
Condition and Lock/ReentrantLock which can be found in
java.util.concurrent.locks. You are not allowed to use synchronized data structures
such as LinkedBlockingQueue.
Remarks
This is an individual assignment. Any sign of collaboration will result in a 0 score for the
assignment. Please check the academic integrity policies in the syllabus of the course.
Late policy: Please check the syllabus for the late submission policies of the course.