Computer Science 4500/8506 Programming Assignment 2 Fall 2011UNIVERSITY OF NEBRASKA AT OMAHAComputer Science 4500/8506Operating SystemsFall 2011Programming Assignment 2IntroductionThe purpose of this assignment is to provide some experience with process scheduling algorithms. Inparticular, you are to implement a program that implements a simulation of processes executing with thescheduling policy described below.Processes will exist in one of five states: not-yet-submitted, ready, running, blocked, and completed. Ofcourse not-yet-submitted and completed are not normally considered process states, but they make iteasier to understand the scheduling algorithm. All processes begin in the not-yet-submitted state.Each process moves from the not-yet-submitted state to the ready state at the time specified in the inputdata for its submission (the input data is described below). At some point, the scheduler will select theprocess for execution, and move it to the running state. Processes are described with six parameters: theprocess ID, the process priority, the time of submission, the total CPU time required, the compute cycletime, and the /O cycle time. Processes will alternate between computing (for the compute cycle time)and doing I/O (for the I/O cycle time) until they have accumulated the total CPU time required.For example, suppose the only process in the system was submitted at time 0, has a total CPU timerequirement of 20 time units (TU, an arbitrary unit), a compute time of 5 TU, and an I/O time of 50 TU;since there’s only one process, its priority is unimportant. After computing for 5 TU, it will becomeblocked for 50 TU (doing I/O), then compute again for 5 TU, then become blocked again for 50 TU, andso forth. The process will complete execution at time 170 (after being blocked for a total of 150 TU).Remember that this example has only a single process.There may be more than one process, more than one CPU, and a quantum size less than infinite. In theprevious example (with only one process), it makes no difference if we have additional CPUs, or if thequantum size is less than 5 TU; note that we’re also assuming a context switch is free – it takes no time!Suppose, however, we have two identical processes, each submitted at time 0, a quantum size of 4 TU,and a single CPU. The first process, after running for 4 TU, will experience quantum runout and bemoved back to the ready state – it still has one TU’s worth of computation to complete before it beginsI/O. So, at time 4 the second process will be allowed to run, for 4 TU, of course. At time 8 the secondprocess will experience quantum runout, and be moved to the ready state. Also at time 8 the first processwill again be allowed to use the CPU. This time it only needs one TU of CPU time before it beginsdoing I/O. So, at time 9 the first process is moved to the blocked state (where it will remain until time59), and the second process will move to the running state. You should convince yourself that the firstprocess will complete execution at time 186, with the second process finishing at time 187.The following set of steps provides a concise, well-defined behavior for the scheduling and processing ofprocesses in this system. The only undefined behavior is associated with, for example, two processeswith the same priority both being ready for execution at the same time (for example, they were bothsubmitted at the same time). Note that the ordering of processes in the queues is usually well-defined byComputer Science 4500/8506 Programming Assignment 2 Fall 2011the following steps. If any ambiguity ever arises, however, your simulation should always first select theprocess with the smallest process ID. For example, if processes 10 and 15 have the same priority and areboth submitted at time 0, process 10 will be selected to run first.Simulation ProcedureYour simulation will be controlled by a simulated time, T, and the set of events that occur at the currentsimulated time. This is not a real time, so do not attempt to synchronize your simulation with any systemtiming features. (One of the primary positive features of simulation is that it can usually be done muchfaster than doing the “real” activity, and that is certainly true for this simulation.)The initial time for the simulation is, of course, 0. But since nothing happens until the first process issubmitted, the simulation time will “jump” to the time of that submission (see step 2). At that time, thesimulation processes all events that occur then. The various events that are possible in this simulation areas given in the following list. Note that some of these events may also trigger other events. For example,if a high-priority process moves from the blocked state to the ready state, it may have a higher prioritythat a running process, and thus preempt a running process.- A new process is submitted (moved from the not-yet-submitted state to the ready state)- A running process completes all of its input/output and computation, and moves to thecompleted state- A running process uses all of its current execution quantum (and still has more execution todo before it starts doing input/output)- A running process finishes with its current computation effort and begins doing input/output(and is moved to the blocked state)- A running process is preempted by a higher-priority ready process (which was just submitted,or just left the blocked state)- A blocked process finishes its input/output and moves to the ready state- A CPU becomes available, and if there is an available ready process, it is selected forexecutionHere are the steps you should follow in simulating the scheduling of the processes in each input data set.1. [READ INPUT] Read the data for the entire set of processes for the next simulation, placing eachprocess in the not-yet-submitted state. Set the ready, running, blocked, and completed processsets to empty.2. [ADVANCE T TO FIRST EVENT TIME] Set the simulation time (T) to the earliest time of anyprocess in the not-yet-submitted state. (Recall that all processes are initially in the not-yet-submitted state, so this is really the earliest submission time of any process.)3. [HANDLE PROCESS COMPLETIONS] If a running process completes execution at time T,then move it from the running state to the completed state. If all processes have now completedexecution, the simulation terminates after displaying all desired statistical information.Computer Science 4500/8506