CPU Scheduling Simulation Solution

Introduction:




In this assignment, you need to implement a priority queue PQueue class using a max-heap and to implement a MaxHeap class using an array. Each node in the max-heap contains a process. The Process class implements Comparable interface so that the comparison between nodes in max-heap can be made by calling compareTo method. To implement the compareTo method, process with larger priority level has a higher priority. In case of a tie, process with earlier arrival time should be picked.




This assignment simulates the CPU round robin scheduling. The CPU scheduling works as follows.




A system defines a unit time (time slice).



A priority queue holds the processes waiting for CPU time.



Each process has a priority level, time remaining to finish, and arrival time.



The system assigns the next CPU time (time slice) to the highest priority process (if there is a tie, the one arriving first is picked) in the priority queue.



Each time a process get a time slice from CPU, its remaining time to finish should be decre-mented by one.



In order to avoid starvation problem, the system will increment the priority for lower priority processes. In this simulation, if any process does not get any time slice for a certain amount of time (timeToIncrementPriority), its priority will be incremented by one until it reaches the highest allowable priority level.



Description:




There are 2 java source files in ∼jhyeh/cs321/labs/lab2/files/.




You can copy these two files to your own assignment directory. Please do not modify these two files since my test program relies on the print statements in the provided sources codes.




CPUScheduling.java: simulates the round robin CPU scheduling algorithm. This class is completed.



Averager.java: keeps track of the number of processes in the simulation and computes the average turn around time. This class is completed.



In addition to these two java classes, you should implement other classes for the CPU scheduling simulation. Suggested other classes includes, but are not limited to




ProcessGenerator.java randomly generates processes with a given probability. At beginning of each time unit, whether a process will arrive is decided by the given probability. In addition, while generating a new process, both its priority and the required time units to finish the process are randomly generated within given ranges.



Process.java defines a process. You need to implement the compareTo method in this class. Each process has a priority level, time remaining to finish, and arrival time.



MaxHeap.java defines a max-heap. Each node in the max-heap contains a process.



PQueue.java defines a priority queue using a max-heap.



What you need to do:




Create a directory ∼/cs321/lab2 for this assignment.



Copy CPUScheduling.java and Averager.java to your assignment directory from



∼jhyeh/cs321/labs/lab2/files/




Write those suggested classes and additional classes if any.



To run the simulation, the following command-line arguments need to be provided:



java CPUScheduling <maxProcessTime <maxPriorityLevel <timeToIncrementPriority <simulationTime <processArrivalRate




where




maxProcessTime: largest possible time units required to finish a process. That is, any process arrived will require at least 1 time unit and at most maxPriorityLevel time units to finish.



maxPriorityLevel: highest possible priority in this simulation. That is, a process can have a priority, ranging from 1, 2, . . . , maxPriorityLevel.



timeToIncrementPriority: if a process didn’t get any CPU time for this timeToIn-crementPriority time units, the process’s priority will be increased by one.



simulationTime: the total time units for the simulation.



processArrivalRate: using this rate to decide whether to generate a new process in each time unit.



The simulation flow chart for each CPU time unit is given in the figure on the last page.




A sample output file sample result of the simulation java CPUScheduling 5 5 5 100 0.4






is in the directory




∼jhyeh/cs321/labs/lab2/files/




You can test the correctness of your program using provided testing programs. Please follow the instruction in a README file, located in



∼jhyeh/cs321/labs/lab2/files/test/README




Submission:




Submit your program(s) from onyx by copying all of your files (.java files only) to an empty directory (with no subdirectories) and typing the following FROM WITHIN this directory:




submit jhyeh cs321 p2




Start







Waint until next

CPU time unit




New Arrival?

N




Y




Create a new job










Insert the job to




the priority queue










Extract the

N

highest priority job A




from the queue




Y




Assign the current




CPU time to the job A:

Update job A status
Update all jobs in queue









Job A
Y
finished?





N




Insert job A back

to priority queue


































Create a new job including

assign random values to

priorityLevel



requiredProcessingTime and set the variables to



timeNotProcessed = 0
timeRemaining = requiredProcessingTime
arrivalTime = current time unit
























Update job A status:

timeRemaining −−
timeNotProcessed = 0



Update each job in queue:

timeNotProcessed ++



if timeNotProcessed = timeToIncrementPriority timeNotProcessed = 0;



if (priorityLevel < maxPriorityLevel) priorityLevel++; MaxHeapifyUp this job;