代写data课程、java程序语言代写

日期：2022-03-26 12:09

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.