OS 202-02 2019-20 Fall Lab 2 Scheduling Page 1In this lab you will simulate scheduling in order to see how the time required depends on the schedulingalgorithm and the request patterns.A process is characterized by just four non-negative integers A, B, C, and M . A is the arrival time of theprocess and C is the total CPU time needed. A process execution consists of computation alternating withI/O. I refer to these as CPU bursts and I/O bursts.To calculate CPU burst times we make the simplifying assumption that, for each process, the CPU bursttimes are uniformly distributed random integers (or UDRIs for short) in the interval (0, B]. To obtain aUDRI t in some interval (0, U ] use the function randomOS(U) described below. So the next CPU burst israndomOS(B). If the value returned by randomOS(B), is larger than the total CPU time remaining, set thenext CPU burst to the remaining time.The I/O burst time for a process is its preceding CPU burst time multiplied by M .You are to read a file describing n processes (i.e., n quadruples of numbers) and then simulate the n processesuntil they all terminate. The way to do this is to keep track of the state of each process (e.g., ready, running,blocked) and advance time, making any state transitions needed. At the end of the run you first print anidentification of the run including the scheduling algorithm used, any parameters (e.g. the quantum for RR),and the number of processes simulated.You then print for each process• A, B, C, and M• Finishing time.• Turnaround time (i.e., finishing time – A).• I/O time (i.e., time in Blocked state).• Waiting time (i.e., time in Ready state).You then print the following summary data.• Finishing time (i.e., when all the processes have finished).• CPU Utilization (i.e., percentage of time some job is running).• I/O Utilization (i.e., percentage of time some job is blocked).• Throughput, expressed in processes completed per hundred time units.• Average turnaround time.• Average waiting time.You must simulate each of the following scheduling algorithms, assuming, for simplicity, that a context switchtakes zero time. You need only do calculations every time unit (e.g., you may assume nothing happens attime 2.5).• FCFS• RR with quantum 2.• SJF (This is not preemptive, but is not uniprogrammed, i.e., we do switch on I/O bursts). Recallthat SJF is shortest job first, not shortest burst first. So the time you use to determine priority is thetotal time remaining (i.e., the input value C minus the number of cycles this process has run).• HPRN. Define the denominator to be max(1, running time), to prevent dividing by zero for a job thathas yet to be run. Remember that HPRN is non-preemptive.For each scheduling algorithm there are several runs with different process mixes. A mix is a value of nfollowed by n A,B,C,M quadruples.Here are the first two input sets. The comments are not part of the input.1 0 1 5 1 about as easy as possible2 0 1 5 1 0 1 5 1 should alternate with FCFSAll the input sets, with their corresponding outputs are on the NYU Classes.The simple function randomOS(U), which you are to write, reads a random non-negative integer X from a filenamed random-numbers (in the current directory) and returns the value 1 + (X mod U). I will supply a filewith a large number of random non-negative integers. The purpose of standardizing the random numbers isso that all correct programs will produce the same answers.OS 202-02 2019-20 Fall Lab 2 Scheduling Page 2Breaking tiesThere are three places where the above specification is not deterministic and different choices can lead todifferent answers. To standardize the answers, you must do the following.1. A running process can have up to three events occur during the same cycle.i. It can terminate (remaining CPU time goes to zero).ii. It can block (remaining CPU burst time goes to zero).iii. It can be preempted (e.g., the RR quantum goes to zero).They must be considered in the above order. For example if all three occur at one cycle, the processterminates.2. Many jobs can have the same “priority”. For example, in RR several jobs can become ready at thesame cycle and thus have the same priority. You must decide in what order they will subsequently berun. These ties are broken by favoring the process with the earliest arrival time A. If the arrival timesare the same for two processes with the same priority, then favor the process that is listed earliest inthe input. We break ties to standardize answers. We use this particular rule for two reason. First, itdoes break all ties. Second, it is very simple to implement. It is not especially wonderful and is notused in practice. I refer to this method as the “lab 2 tie-breaking rule” and often use it on exams forthe same two reasons.Running your programYour program must read its input from a file, whose name is given as a command line argument. Thepreceding sentence is a requirement. The format of the input is shown above (but the “comments” are notnecessary); sample inputs are on the NYU Classes. Be sure you can process the sample inputs. Do notassume you can change the input by adding or removing whitespace or commas, etc.Your program must send its output to the screen (printf() in C; System.out in Java).In addition your program must accept an optional “–verbose” flag, which if present precedes the file name.When –verbose is given, your program is to produce detailed output that you will find useful in debugging(indeed, you will thank me for requiring this option). See the sample outputs on the NYU Classes for theformat of debugging output. So the two possible invocations of your program are –verbose My program also supports an even more verbose mode (show-random) that prints the random number choseneach time. This is useful, but your program is not required to support it.
