1COMPUTER SCIENCE 131A
OPERATING SYSTEMS
PROGRAMMING ASSIGNMENT 3
CARS AND TUNNELS PRIORITY SCHEDULER
Introduction
You will implement a priority scheduler that manages a collection of vehicles attempting to enter
a set of tunnels. The purpose of this project is to expose you to the operating system task of
managing and allocating CPU processes. In this PA, you can think of Vehicles as CPU
processes and Tunnels as CPU cores. The mechanism by which the CPU scheduler allows for
threads to be run on cores is represented by the PriorityScheduler class admitting a
Vehicle into a Tunnel.
Description
Most of the logic surrounding Vehicles and Tunnels is already implemented. However, there
are two classes that have been left unimplemented: BasicTunnel.java and
PriorityScheduler.java. When solving this PA, you are only allowed to modify the
submission package.
Vehicles
There are two types of Vehicles in this PA: Cars and Sleds. Each Vehicle has a
priority and direction. The PriorityScheduler and Tunnels use this
information to allocate tunnel spaces to Vehicles. Both of these classes are already
implemented, but more detailed information about their behavior can be found in
Vehicle.java.
BasicTunnel
The BasicTunnel class contains the logic governing the Vehicle admittance policy.
Although both types of Vehicles are functionally the same, BasicTunnel policy distinguishes
between them.
At all times, the BasicTunnel’s state must satisfy the following policy:
- No more than CAR_CAPACITY Cars can be in the BasicTunnel at once.
- No more than SLED_CAPACITY Sleds can be in the BasicTunnel at once.
2- Sleds and Cars cannot share a BasicTunnel.
- All Vehicles in a tunnel must be traveling in the same direction, indicated by that
Vehicle’s direction field.
The following two methods require implementation in order to enforce the above class invariant:
tryToEnterInner: Vehicle → boolean
When the priority scheduler wants to check if a Vehicle is eligible to enter a Tunnel, it will
call the Tunnel’s tryToEnter method. This method will subsequently call BasicTunnel’s
tryToEnterInner method. tryToEnterInner should return true if the input
Vehicle can be admitted and false otherwise.
exitTunnelInner: Vehicle → [void]
When a Vehicle has finished passing through a Tunnel, it will have the
PriorityScheduler make a call to exitTunnel. A Vehicle’s behavior while passing
through a Tunnel is defined in the doWhileInTunnel method in the Vehicle class.
exitTunnel will subsequently call BasicTunnel’s exitTunnelInner method. This
method should be written so that future calls to it and tryToEnterInner will follow the
admittance policy.
PriorityScheduler
The PriorityScheduler class handles the requests made by Vehicles to be admitted into
an available Tunnel. The PriorityScheduler will be instantiated with a collection of
Tunnels to manage. A Vehicle attempting to enter a Tunnel will call the
PriorityScheduler’s admit method, passing in a reference to itself as the parameter.
admit: Vehicle → Tunnel
The PriorityScheduler’s admit method must satisfy mutual exclusion. Here, mutual
exclusion is the concept of restricting access to a code block to only one thread at a time. The
method must then behave as follows:
1. If the input Vehicle has priority greater than or equal to all currently waiting
Vehicles, then the Vehicle should attempt to find an available Tunnel. Vehicles
can check if a particular Tunnel is available by calling that Tunnel’s tryToEnter
method.
2. If the input Vehicle is unable to enter any of the Tunnels then it should wait until a
space in a Tunnel may be available.
3. If the input Vehicle has a priority less than the highest priority, then it should continue
to wait in the waiting queue.
Once the Vehicle can be successfully entered into a Tunnel, the Tunnel it was admitted to
should be returned.
3Note that a Vehicle’s priority can be obtained by calling
Vehicle:getVehiclePriority(). Do not use the Vehicle:getPriority()
method because it will return the Thread superclass’s priority instead of the Vehicle’s.
exit: Vehicle → [void]
The PriorityScheduler’s exit method must also satisfy mutual exclusion. The method
must then behave as follows:
1. The scheduler must determine which Tunnel the input Vehicle is in, then call the
Tunnel’s exitTunnel method.
2. After a Vehicle has exited a Tunnel, this method should wake up waiting Vehicles
so that they can retry to enter the scheduler’s Tunnels if appropriate.
Java Synchronization Mechanisms
Java provides two tools for method synchronization that can be used on this PA. You must decide
where and how to use these tools to solve this PA.
Synchronized methods
In Java, to force a method to be mutually exclusive, one can add the synchronized keyword to its
declaration. For example,
public synchronized void methodName()
Adding the synchronized method ensures that it is not possible for two calls of synchronized
methods of the same object to interleave. When one thread is executing a synchronized method
of an object all other threads that invoke synchronized methods for that same object block
(suspend execution) until the first thread releases ownership of the object’s Mutex lock.
The following Object methods are relevant to this keyword:
Object:wait() - Causes the current thread to wait until another thread invokes the
notifyAll() method for this object.
Object:notifyAll() - Wakes up all threads that are waiting on this object's monitor.
ReentrantLock and Condition
A ReentrantLock is a mutual exclusion lock with the same behavior as the implicit object
lock accessed using synchronized methods, but with extended capabilities. In particular, since the
lock can be acquired at any point in a method, it is more flexible for choosing which block of
code should be mutually exclusive. The ReentrantLock class offers two useful methods for
this PA:
ReentrantLock:lock() - A thread calling this method will attempt to acquire the lock. If
unsuccessful, the thread will become disabled for scheduling purposes until the lock is acquired.
4ReentrantLock:unlock() - A thread calling this method will attempt to release the lock. If the
thread did not own the lock before calling this method, an
IllegalMonitorStateException will be thrown.
In order to utilize the functionality of the Object’s wait() and notifyAll() one must
instantiate Condition objects from the ReentrantLock.
ReentrantLock:newCondition() - Returns a Condition instance for use with this
ReentrantLock instance.
Condition:await() - Causes the current thread to wait until it is signaled or interrupted.
Condition:signalAll() - Wakes up all waiting threads
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 PriorityScheduler’s admittance policy correctly. Your solution must
ensure that:
- The highest priority Vehicle is entered into a Tunnel as soon as a space
becomes available and never waits unnecessarily.
- Thread synchronization techniques are properly used to ensure that Vehicles
never busy-wait.
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 FirstnameLastnamePA3 (make sure to use Eclipse’s Refactor >
Rename). The zip file you submit should be named FirstnameLastnamePA3.zip.
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.
5Remarks
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.

欢迎咨询51作业君