Version 3.0 – Pito Salas 1
COMPUTER SCIENCE 131A
OPERATING SYSTEMS
PROGRAMMING ASSIGNMENT 3
CARS AND TUNNELS PRIORITY SCHEDULER
Introduction
In this programming assignment you will implement a priority scheduler that manages a
collection of vehicles attempting to enter a set of tunnels. We will provide you starter code
representing vehicles and tunnels and you will add to the code to implement certain more
sophisticated behaviors
Why vehicles and tunnels? The metaphor here is to think of Vehicles as CPU processes that
want to (and need to) run and Tunnels as the CPU cores on which they may run. In that world,
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.
Purpose
I think this is an interesting project at this point in the course. It is one thing to read or to hear
about concurrency and multi core. But writing and especially debugging concurrent code brings
your understanding to a whole other level. The purposes of this assignment are several:
1. Get more practice working with concurrency in Java.
2. Gain a deeper understanding of synchronization, semaphores, and concurrent algorithms.
3. Develop a sense of how scheduling algorithms work in the operating systems, in general
and in the case of allocating threads and processes to particular CPU cores.
4. Gain an understanding of scheduling cores in particular.
Description of code and key classes
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. Your assignment is to implement the indicated methods and
ensure that all tests run successfully and without deadlock, race conditions, or errors.
When solving this PA, you are only allowed to modify the submission package.
Version 3.0 – Pito Salas 2
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 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.
- 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:
void tryToEnterInner(Vehicle v)
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.
void exitTunnelInner(Vehicle v)
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.
Version 3.0 – Pito Salas 3
Tunnel admit(Vehicle vehicle)
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.
Note 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.
Void exit(Vehicle v)
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.
Review of key 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
Version 3.0 – Pito Salas 4
(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.
ReentrantLock: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.
Version 3.0 – Pito Salas 5
- 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.
Code Commenting
These are your guidelines for commenting your code:
1. Only add Javadoc comments to methods you defined or modified. For example, if you
used created an additional method in a class, or if you modified an existing method, you
should add or correct the Javadoc.
2. The PAs in this class give you a lot of flexibility and design options. People can have
different data structures, completely different implementations of a method, etc. So for
the code you write or structures you defined, please thoroughly comment. Otherwise, if
you did not change the code, you do not need write new comments.
3. For the classes you modified, please also replace the header comment with your header
comment.
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.
WX：codehelp mailto: thinkita@qq.com