Processes

Due:: 11:00pm, Friday February 11, 2022

Description

For this assignment we will run process related simulators from the textbook supplementary material (source) and answer related questions. A zip file with the simulator programs linked on the assignments page. The README files for each program are listed below that contain information on how to run each simulator program. Read these before answering the questions that follow.

`schedule.py` README

This program, scheduler.py, allows you to see how different schedulers perform under scheduling metrics such as response time, turnaround time, and total wait time. Three schedulers are “implemented”: FIFO, SJF, and RR.

There are two steps to running the program.

First, run without the -c flag: this shows you what problem to solve without revealing the answers. For example, if you want to compute response, turnaround, and wait for three jobs using the FIFO policy, run this:

prompt> ./scheduler.py -p FIFO -j 3 -s 100

If that doesn’t work, try this:

prompt> python ./scheduler.py -p FIFO -j 3 -s 100

This specifies the FIFO policy with three jobs, and, importantly, a specific random seed of 100. If you want to see the solution for this exact problem, you have to specify this exact same random seed again. Let’s run it and see what happens. This is what you should see:

prompt> ./scheduler.py -p FIFO -j 3 -s 100
ARG policy FIFO
ARG jobs 3
ARG maxlen 10
ARG seed 100

Here is the job list, with the run time of each job: 
  Job 0 (length = 1)
  Job 1 (length = 4)
  Job 2 (length = 7)

Compute the turnaround time, response time, and wait time for each job. When you are done, run this program again, with the same arguments, but with -c, which will thus provide you with the answers. You can use -s or your own job list (-l 10,15,20 for example) to generate different problems for yourself.

As you can see from this example, three jobs are generated: job 0 of length 1, job 1 of length 4, and job 2 of length 7. As the program states, you can now use this to compute some statistics and see if you have a grip on the basic concepts.

Once you are done, you can use the same program to “solve” the problem and see if you did your work correctly. To do so, use the “-c” flag. The output:

prompt> ./scheduler.py -p FIFO -j 3 -s 100 -c
ARG policy FIFO
ARG jobs 3
ARG maxlen 10
ARG seed 100

Here is the job list, with the run time of each job: 
  Job 0 (length = 1)
  Job 1 (length = 4)
  Job 2 (length = 7)

** Solutions **

Execution trace:
  [time   0] Run job 0 for 1.00 secs (DONE)
  [time   1] Run job 1 for 4.00 secs (DONE)
  [time   5] Run job 2 for 7.00 secs (DONE)

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 1.00  Wait 0.00
  Job   1 -- Response: 1.00  Turnaround 5.00  Wait 1.00
  Job   2 -- Response: 5.00  Turnaround 12.00  Wait 5.00

  Average -- Response: 2.00  Turnaround 6.00  Wait 2.00

As you can see from the figure, the -c flag shows you what happened. Job 0 ran first for 1 second, Job 1 ran second for 4, and then Job 2 ran for 7 seconds. Not too hard; it is FIFO, after all! The execution trace shows these results.

The final statistics are useful too: they compute the “response time” (the time a job spends waiting after arrival before first running), the “turnaround time” (the time it took to complete the job since first arrival), and the total “wait time” (any time spent ready but not running). The stats are shown per job and then as an average across all jobs. Of course, you should have computed these things all before running with the “-c” flag!

If you want to try the same type of problem but with different inputs, try changing the number of jobs or the random seed or both. Different random seeds basically give you a way to generate an infinite number of different problems for yourself, and the “-c” flag lets you check your own work. Keep doing this until you feel like you really understand the concepts.

One other useful flag is “-l” (that’s a lower-case L), which lets you specify the exact jobs you wish to see scheduled. For example, if you want to find out how SJF would perform with three jobs of lengths 5, 10, and 15, you can run:

prompt> ./scheduler.py -p SJF -l 5,10,15
ARG policy SJF
ARG jlist 5,10,15

Here is the job list, with the run time of each job: 
  Job 0 (length = 5.0)
  Job 1 (length = 10.0)
  Job 2 (length = 15.0)
...

And then you can use -c to solve it again. Note that when you specify the exact jobs, there is no need to specify a random seed or the number of jobs: the jobs lengths are taken from your comma-separated list.

Of course, more interesting things happen when you use SJF (shortest-job first) or even RR (round robin) schedulers. Try them and see!

And you can always run

prompt> ./scheduler.py -h

to get a complete list of flags and options (including options such as setting the time quantum for the RR scheduler).

`mlfq.py` README

This program, mlfq.py, allows you to see how the MLFQ scheduler presented in this chapter behaves. As before, you can use this to generate problems for yourself using random seeds, or use it to construct a carefully-designed experiment to see how MLFQ works under different circumstances. To run the program, type:

prompt> ./mlfq.py

Use the help flag (-h) to see the options:

Usage: mlfq.py [options]
Options:
  -h, --help            show this help message and exit
  -s SEED, --seed=SEED  the random seed
  -n NUMQUEUES, --numQueues=NUMQUEUES
                        number of queues in MLFQ (if not using -Q)
  -q QUANTUM, --quantum=QUANTUM
                        length of time slice (if not using -Q)
  -Q QUANTUMLIST, --quantumList=QUANTUMLIST
                        length of time slice per queue level, 
                        specified as x,y,z,... where x is the 
                        quantum length for the highest-priority 
                        queue, y the next highest, and so forth
  -j NUMJOBS, --numJobs=NUMJOBS
                        number of jobs in the system
  -m MAXLEN, --maxlen=MAXLEN
                        max run-time of a job (if random)
  -M MAXIO, --maxio=MAXIO
                        max I/O frequency of a job (if random)
  -B BOOST, --boost=BOOST
                        how often to boost the priority of all 
                        jobs back to high priority (0 means never)
  -i IOTIME, --iotime=IOTIME
                        how long an I/O should last (fixed constant)
  -S, --stay            reset and stay at same priority level 
                        when issuing I/O
  -l JLIST, --jlist=JLIST
                        a comma-separated list of jobs to run, 
                        in the form x1,y1,z1:x2,y2,z2:... where 
                        x is start time, y is run time, and z 
                        is how often the job issues an I/O request
  -c                    compute answers for me

There are a few different ways to use the simulator. One way is to generate some random jobs and see if you can figure out how they will behave given the MLFQ scheduler. For example, if you wanted to create a randomly-generated three-job workload, you would simply type:

prompt> ./mlfq.py -j 3

What you would then see is the specific problem definition:

Here is the list of inputs:
OPTIONS jobs 3
OPTIONS queues 3
OPTIONS quantum length for queue  2 is  10
OPTIONS quantum length for queue  1 is  10
OPTIONS quantum length for queue  0 is  10
OPTIONS boost 0
OPTIONS ioTime 0
OPTIONS stayAfterIO False

For each job, three defining characteristics are given:
  startTime : at what time does the job enter the system
  runTime   : the total CPU time needed by the job to finish
  ioFreq    : every ioFreq time units, the job issues an I/O
              (the I/O takes ioTime units to complete)

Job List:
  Job  0: startTime   0 - runTime  84 - ioFreq   7
  Job  1: startTime   0 - runTime  42 - ioFreq   2
  Job  2: startTime   0 - runTime  51 - ioFreq   4

Compute the execution trace for the given workloads.
If you would like, also compute the response and turnaround
times for each of the jobs.

Use the -c flag to get the exact results when you are finished.

This generates a random workload of three jobs (as specified), on the default number of queues with a number of default settings. If you run again with the solve flag on (-c), you’ll see the same print out as above, plus the following:

Execution Trace:

[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] JOB BEGINS by JOB 1
[ time 0 ] JOB BEGINS by JOB 2
[ time 0 ] Run JOB 0 at PRIORITY 2 [ TICKS 9 ALLOT 1 TIME 83 (of 84) ]
[ time 1 ] Run JOB 0 at PRIORITY 2 [ TICKS 8 ALLOT 1 TIME 82 (of 84) ]
[ time 2 ] Run JOB 0 at PRIORITY 2 [ TICKS 7 ALLOT 1 TIME 81 (of 84) ]
[ time 3 ] Run JOB 0 at PRIORITY 2 [ TICKS 6 ALLOT 1 TIME 80 (of 84) ]
[ time 4 ] Run JOB 0 at PRIORITY 2 [ TICKS 5 ALLOT 1 TIME 79 (of 84) ]
[ time 5 ] Run JOB 0 at PRIORITY 2 [ TICKS 4 ALLOT 1 TIME 78 (of 84) ]
[ time 6 ] Run JOB 0 at PRIORITY 2 [ TICKS 3 ALLOT 1 TIME 77 (of 84) ]
[ time 7 ] IO_START by JOB 0
IO DONE
[ time 7 ] Run JOB 1 at PRIORITY 2 [ TICKS 9 ALLOT 1 TIME 41 (of 42) ]
[ time 8 ] Run JOB 1 at PRIORITY 2 [ TICKS 8 ALLOT 1 TIME 40 (of 42) ]
[ time 9 ] Run JOB 1 at PRIORITY 2 [ TICKS 7 ALLOT 1 TIME 39 (of 42) ]
...

Final statistics:
  Job  0: startTime   0 - response   0 - turnaround 175
  Job  1: startTime   0 - response   7 - turnaround 191
  Job  2: startTime   0 - response   9 - turnaround 168

  Avg  2: startTime n/a - response 5.33 - turnaround 178.00

The trace shows exactly, on a millisecond-by-millisecond time scale, what the scheduler decided to do. In this example, it begins by running Job 0 for 7 ms until Job 0 issues an I/O; this is entirely predictable, as Job 0’s I/O frequency is set to 7 ms, meaning that every 7 ms it runs, it will issue an I/O and wait for it to complete before continuing. At that point, the scheduler switches to Job 1, which only runs 2 ms before issuing an I/O. The scheduler prints the entire execution trace in this manner, and finally also computes the response and turnaround times for each job as well as an average.

You can also control various other aspects of the simulation. For example, you can specify how many queues you’d like to have in the system (-n) and what the quantum length should be for all of those queues (-q); if you want even more control and varied quanta length per queue, you can instead specify the length of the quantum (time slice) for each queue with -Q, e.g., -Q 10,20,30] simulates a scheduler with three queues, with the highest-priority queue having a 10-ms time slice, the next-highest a 20-ms time-slice, and the low-priority queue a 30-ms time slice.

You can separately control how much time allotment there is per queue too. This can be set for all queues with -a, or per queue with -A, e.g., -A 20,40,60 sets the time allotment per queue to 20ms, 40ms, and 60ms, respectively.

If you are randomly generating jobs, you can also control how long they might run for (-m), or how often they generate I/O (-M). If you, however, want more control over the exact characteristics of the jobs running in the system, you can use -l (lower-case L) or –jlist, which allows you to specify the exact set of jobs you wish to simulate. The list is of the form: x1,y1,z1:x2,y2,z2:… where x is the start time of the job, y is the run time (i.e., how much CPU time it needs), and z the I/O frequency (i.e., after running z ms, the job issues an I/O; if z is 0, no I/Os are issued).

For example, if you wanted to recreate the example in Figure 8.3 you would specify a job list as follows:

prompt> ./mlfq.py --jlist 0,180,0:100,20,0 -q 10

Running the simulator in this way creates a three-level MLFQ, with each level having a 10-ms time slice. Two jobs are created: Job 0 which starts at time 0, runs for 180 ms total, and never issues an I/O; Job 1 starts at 100 ms, needs only 20 ms of CPU time to complete, and also never issues I/Os.

Finally, there are three more parameters of interest. The -B flag, if set to a non-zero value, boosts all jobs to the highest-priority queue every N milliseconds, when invoked as such:

  prompt> ./mlfq.py -B N

The scheduler uses this feature to avoid starvation as discussed in the chapter. However, it is off by default.

The -S flag invokes older Rules 4a and 4b, which means that if a job issues an I/O before completing its time slice, it will return to that same priority queue when it resumes execution, with its full time-slice intact. This enables gaming of the scheduler.

Finally, you can easily change how long an I/O lasts by using the -i flag. By default in this simplistic model, each I/O takes a fixed amount of time of 5 milliseconds or whatever you set it to with this flag.

You can also play around with whether jobs that just complete an I/O are moved to the head of the queue they are in or to the back, with the -I flag. Check it out, it’s fun!

Questions

(SJF & FIFO) What types of workloads does SJF deliver the same turnaround times as FIFO?
(SJF & RR) What types of workloads and quantum lengths does SFJ deliver the same response times as RR?
(SJF) What happens to response time as job lengths increase?
(RR) What happens to response time as quantum lengths increase?
(RR) Can you write an equation that gives the worst-case response time given N jobs? If so, write the equation. Otherwise explain why it cannot be done.
(MLFQ & RR) How would you configure the parameters to behave exactly like the RR scheduler?
(MLFQ) Create a workload with two jobs and scheduler parameters so that one job takes advantage of the older rules 4a and 4b (enabled with the -S flag) to game the scheduler and obtain 99% of the CPU over a particular time interval. What is the command that you entered?
(MLFQ) Given a system with a quantum length of 10ms in its highest queue, how often would you have to boost jobs back to the highest priority level (with the -B flag) in order to guarantee that a single long-running job gets at least 5% of the CPU?

Turning in the Assignment

Create a text file named assignment2.txt containing your answers to the questions. Submit your solution to the appropriate folder on D2L.

Note that your answers must be correctly numbered and only the answers must be in your submission; any answer solution that does not satisfy these requirements will be marked as a zero.