关于算法:131A-难点解答

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:
• 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.
• 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.
• 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:
• The scheduler must determine which Tunnel the input Vehicle is in, then call the
  Tunnel’s exitTunnel method.
• 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.