This project is an implementation of a small simulation program.

To successfully finish the program, students are expected to:

Study and learn how to use PriorityQueues Study and learn how to write a small simulation program.

Name the file with the main method ProcessScheduling.java. You may define other classes as needed in separate files.

The following describes the scheduling system that is simulated:

Processes arrive at a computer system and the computer system choose which process to execute at each time point based on the processs priority. Each process has a process id, priority, arrival time, and duration. The duration of a process is the amount of time it takes to completely execute the process. The system keeps a priority queue to keep arriving processes and prioritize the execution of processes. When a process arrives, it is inserted into the priority queue. Then, at each timestep the system removes a process with the smallest priority from the priority queue and executes it for a single timestep.

Suppose that a process p with a very large priority arrives at the system while the system is executing another process. While p is waiting in the queue, another process q with a relatively small priority arrives. After the execution of the current process is finished, the system will remove and execute q (because q has a smaller priority), and p must wait until q finishes. If another process with a smaller priority arrives while q is being executed, p will have to wait again after q is completed. If this is repeated, p will have to wait for a very long time. One way of preventing this is as follows: If a process has waited longer than a predetermined maximum wait time, we update the priority of the process by decreasing the priority by one. For example, if the current priority of the process is 5, then it is updated to 4.

For the purpose of this simulation, we assume the following: We use a modified version of the HeapAdaptablePriorityQueue given by the textbook

o Please use the version of net.datastructures given in the project code package and not the net.datastructures package that you used in other assignments.

Each entry in the priority queue keeps a process object, which represents a process.

Each process must have, at the minimum, the following attributes:

id: integer // process id

arrivalTime: integer // the time when the process arrives at the system duration: integer // execution of the process takes this amount of time

The following describes the general behavior of the simulation program:

All processes are stored in a certain data structure D, which is supposed to be external to the computer system.

In each iteration (one time unit), the following occurs (not necessarily in the given order):

We compare the current time with the arrival time of a process with the earliest arrival time in D. If the arrival time of that process is equal to or smaller than the current time, we remove the process from D and insert it into the adaptable priority queue Q (this represents the arrival of a process at the system).

If there is at least one process in Q, then the process with the smallest priority in Q is executed. If multiple processes have the same priority, then Java will arbitrarily decide which process to execute.

The wait time of a process p is the amount of time p has waited in Q. It is calculated by subtracting the arrival time of p from the time when p is removed from Q. For example, if the arrival time of p is 12 and p is removed from Q at time 20, then the wait time is 20 12 = 8.

Update the priorities of some processes. The update is performed as follows. If there is any process in Q that has been waiting longer than the predetermined maximum wait time, then the priority of that process is decreased by one. You may need an additional data structure to help make updates (since changing the priority of a Process will affect the order of Processes in the PriorityQueue).

The current time is increased by one time unit.

The above is repeated until D and Q are empty. At this time, all processes have

arrived at the system. Some of them may have been completed and removed from Q and some may still wait in Q.

Read all processes from an input file and store them in an appropriate data structure, D Initialize currentTime create an empty priority queue Q

// Each iteration of the while loop represents what occurs during one time unit // Must increment currentTime in each iteration While Q and D are not empty // while loop runs once for every time unit until Q is empty

If D is not empty Get (dont remove) a process p from D that has the earliest arrival time If the arrival time of p <= currentTime

Remove p from D and insert it into Q If Q is not empty

Execute the top process in Q for one time step

Update the wait times of all processes in Q Update priorities of processes that have been waiting longer than max. wait time End of While loop

Calculate average wait time

An input file stores information about all processes. The name of the input file is process_scheduling_input.txt. A sample input file is shown below (this sample input is posted on Blackboard):

1 4 25 10 2 3 15 17 3 1 17 26 4 4 9 17 30 5 10 9 40 6 6 14 47 7 7 7 18 52 8 51870 9 21693 10 8 20 125

Each line in the input file represents a process and it has four integers separated by a space(s). The four integers are the process id, priority, duration, and arrival time, respectively, of a process.

While your program is performing the simulation, whenever a different process is being executed, your program must display information about the process that stopped execution and the process that started execution. Your program also needs to print other information as shown in the sample output below.

Note that:

This output was generated using 30 as the maximum wait time. A different maximum

wait time will result in a different output.

Your output may not be the same as the one shown below. This is because when two

processes have the same smallest priority and wait time, the choice is made by Java arbitrarily when a process is removed from the queue.

// print all processes first

Id = 1, priority = 4, duration = 25, arrival time = 10

Id = 2, priority = 3, duration = 15, arrival time = 17

Id = 3, priority = 1, duration = 17, arrival time = 26

Id = 4, priority = 9, duration = 17, arrival time = 30

Id = 5, priority = 10, duration = 9, arrival time = 40

Id = 6, priority = 6, duration = 14, arrival time = 47

Id = 7, priority = 7, duration = 18, arrival time = 52

Id = 8, priority = 5, duration = 18, arrival time = 70

Id = 9, priority = 2, duration = 16, arrival time = 93

Id = 10, priority = 8, duration = 20, arrival time = 125

Maximum wait time = 30

Now running Process id = 1 Arrival = 10 Duration = 25 Run time left = 25

at time 10 Executed process ID:1, at time 10 Remaining: 24 Executed process ID:1, at time 11 Remaining: 23 Executed process ID:1, at time 12 Remaining: 22 Executed process ID:1, at time 13 Remaining: 21 Executed process ID:1, at time 14 Remaining: 20 Executed process ID:1, at time 15 Remaining: 19 Executed process ID:1, at time 16 Remaining: 18 Now running Process id = 2 Arrival = 17 Duration = 15 Run time left = 15

at time 17

Executed process ID:2, at time 17 Remaining: 14 Executed process ID:2, at time 18 Remaining: 13 Executed process ID:2, at time 19 Remaining: 12 Executed process ID:2, at time 20 Remaining: 11 Executed process ID:2, at time 21 Remaining: 10 Executed process ID:2, at time 22 Remaining: 9 Executed process ID:2, at time 23 Remaining: 8 Executed process ID:2, at time 24 Remaining: 7 Executed process ID:2, at time 25 Remaining: 6 Now running Process id = 3

Arrival = 26 Duration = 17 Run time left = 17

at time 26 Executed process ID:3, at time 26 Remaining: 16 Executed process ID:3, at time 27 Remaining: 15 Executed process ID:3, at time 28 Remaining: 14 Executed process ID:3, at time 29 Remaining: 13 Executed process ID:3, at time 30 Remaining: 12 Executed process ID:3, at time 31 Remaining: 11 Executed process ID:3, at time 32 Remaining: 10 Executed process ID:3, at time 33 Remaining: 9 Executed process ID:3, at time 34 Remaining: 8 Executed process ID:3, at time 35 Remaining: 7 Executed process ID:3, at time 36 Remaining: 6 Executed process ID:3, at time 37 Remaining: 5 Executed process ID:3, at time 38 Remaining: 4 Executed process ID:3, at time 39 Remaining: 3 Executed process ID:3, at time 40 Remaining: 2 Executed process ID:3, at time 41 Remaining: 1 Executed process ID:3, at time 42 Remaining: 0 Finished running Process id = 3 Arrival = 26 Duration = 17 Run time left = 0

at time 42 Now running Process id = 2 Arrival = 17 Duration = 15 Run time left = 6

at time 43 Executed process ID:2, at time 43 Remaining: 5 Executed process ID:2, at time 44 Remaining: 4 Executed process ID:2, at time 45 Remaining: 3 Executed process ID:2, at time 46 Remaining: 2 Process 1 reached maximum wait time... decreasing priority to 3 Executed process ID:2, at time 47 Remaining: 1 Executed process ID:2, at time 48 Remaining: 0 Finished running Process id = 2 Arrival = 17 Duration = 15 Run time left = 0

at time 48 Now running Process id = 1 Arrival = 10 Duration = 25 Run time left = 18

 at time 49 Executed process ID:1, at time 49 Remaining: 17 Executed process ID:1, at time 50 Remaining: 16 Executed process ID:1, at time 51 Remaining: 15 Executed process ID:1, at time 52 Remaining: 14 Executed process ID:1, at time 53 Remaining: 13 

Executed process ID:1, at time 54 Remaining: 12 Executed process ID:1, at time 55 Remaining: 11 Executed process ID:1, at time 56 Remaining: 10 Executed process ID:1, at time 57 Remaining: 9 Executed process ID:1, at time 58 Remaining: 8 Executed process ID:1, at time 59 Remaining: 7 Process 4 reached maximum wait time... decreasing priority to 8 Executed process ID:1, at time 60 Remaining: 6

Executed process ID:1, at time 61 Remaining: 5 Executed process ID:1, at time 62 Remaining: 4 Executed process ID:1, at time 63 Remaining: 3 Executed process ID:1, at time 64 Remaining: 2 Executed process ID:1, at time 65 Remaining: 1 Executed process ID:1, at time 66 Remaining: 0 Finished running Process id = 1

Arrival = 10 Duration = 25 Run time left = 0

at time 66 Now running Process id = 6 Arrival = 47 Duration = 14 Run time left = 14

at time 67 Executed process ID:6, at time 67 Remaining: 13 Executed process ID:6, at time 68 Remaining: 12 Executed process ID:6, at time 69 Remaining: 11 Process 5 reached maximum wait time... decreasing priority to 9 Now running Process id = 8 Arrival = 70 Duration = 18 Run time left = 18

at time 70...& so on

Finished running all processes at time 178 Average wait time: 41.3