Select Homework for Chapter 8 of 《Operating Systems: Three Easy Pieces》: MLFQ Scheduling
1
root@C202511211157657:~# python3 mlfq.py -j 2 -M 0 -m 4 -n 2 -q 1
Here is the list of inputs:
OPTIONS jobs 2
OPTIONS queues 2
OPTIONS allotments for queue 1 is 1
OPTIONS quantum length for queue 1 is 1
OPTIONS allotments for queue 0 is 1
OPTIONS quantum length for queue 0 is 1
OPTIONS boost 0
OPTIONS ioTime 5
OPTIONS stayAfterIO False
OPTIONS iobump 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 3 - ioFreq 0
Job 1: startTime 0 - runTime 2 - ioFreq 0
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.
So I am trying to make this work easier by adjusting all the arguments as precise as possible.
For This one, job 0 will go to queue 1 but will soon drop to queue 0 since it would use out its allotment.
So it would be like:
START JOB0
START JOB1
Run JOB 0 at PRIORITY 1
Run JOB 1 at PRIORITY 0
Run JOB 1 at PRIORITY 0
Run JOB 0 at PRIORITY 0
Run JOB 0 at PRIORITY 0
| Job | StartTime | Response | Turnaround |
|---|---|---|---|
| 0 | 0 | 0 | 5 |
| 1 | 0 | 1 | 4 |
Actually:
Execution Trace:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] JOB BEGINS by JOB 1
[ time 0 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 2 (of 3) ]
[ time 1 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 1 (of 2) ]
[ time 2 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 1 (of 3) ]
[ time 3 ] Run JOB 1 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 2) ]
[ time 4 ] FINISHED JOB 1
[ time 4 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 3) ]
[ time 5 ] FINISHED JOB 0
Final statistics:
Job 0: startTime 0 - response 0 - turnaround 5
Job 1: startTime 0 - response 1 - turnaround 4
Avg 1: startTime n/a - response 0.50 - turnaround 4.50
I made a mistake that all jobs should start with the highest priority.
Let’s go on for the next generated problem:
root@C202511211157657:~# python3 mlfq.py -j 2 -M 0 -m 8 -n 2 -q 2 -s 3
Here is the list of inputs:
OPTIONS jobs 2
OPTIONS queues 2
OPTIONS allotments for queue 1 is 1
OPTIONS quantum length for queue 1 is 2
OPTIONS allotments for queue 0 is 1
OPTIONS quantum length for queue 0 is 2
OPTIONS boost 0
OPTIONS ioTime 5
OPTIONS stayAfterIO False
OPTIONS iobump 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 2 - ioFreq 0
Job 1: startTime 0 - runTime 3 - ioFreq 0
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.
It would be like:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] JOB BEGINS by JOB 1
[ time 0 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 1 (of 2) ]
[ time 1 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 2 (of 3) ]
[ time 2 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 2) ]
[ time 2 ] FINISHED JOB 0
[ time 3 ] Run JOB 1 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 1 (of 3) ]
[ time 4 ] Run JOB 1 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 3) ]
[ time 4 ] FINISHED JOB 1
| Job | StartTime | Response | Turnaround |
|---|---|---|---|
| 0 | 0 | 0 | 3 |
| 1 | 0 | 1 | 5 |
Actually:
Execution Trace:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] JOB BEGINS by JOB 1
[ time 0 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 1 (of 2) ]
[ time 1 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 0 (of 2) ]
[ time 2 ] FINISHED JOB 0
[ time 2 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 2 (of 3) ]
[ time 3 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 1 (of 3) ]
[ time 4 ] Run JOB 1 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 0 (of 3) ]
[ time 5 ] FINISHED JOB 1
Final statistics:
Job 0: startTime 0 - response 0 - turnaround 2
Job 1: startTime 0 - response 2 - turnaround 5
Avg 1: startTime n/a - response 1.00 - turnaround 3.50
Okay, I made another mistake. I though the unit of allotment is the unit of time. It is actually a whole time segment.
And the job should be finished at the next time unit.
Just give me another chance:(And the last one)
root@C202511211157657:~# python3 mlfq.py -j 2 -M 0 -m 8 -n 2 -q 2 -s 7
Here is the list of inputs:
OPTIONS jobs 2
OPTIONS queues 2
OPTIONS allotments for queue 1 is 1
OPTIONS quantum length for queue 1 is 2
OPTIONS allotments for queue 0 is 1
OPTIONS quantum length for queue 0 is 2
OPTIONS boost 0
OPTIONS ioTime 5
OPTIONS stayAfterIO False
OPTIONS iobump 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 3 - ioFreq 0
Job 1: startTime 0 - runTime 5 - ioFreq 0
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.
It would be like:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] JOB BEGINS by JOB 1
[ time 0 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 2 (of 3) ]
[ time 1 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 1 (of 3) ]
[ time 2 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 4 (of 5) ]
[ time 3 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 3 (of 5) ]
[ time 4 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 0 (of 3) ]
[ time 5 ] FINISHED JOB 0
[ time 5 ] Run JOB 1 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 2 (of 5) ]
[ time 6 ] Run JOB 1 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 1 (of 5) ]
[ time 7 ] Run JOB 1 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 0 (of 5) ]
[ time 8 ] FINISHED JOB 1
| Job | StartTime | Response | Turnaround |
|———-|———-|———-|———-|
| 0 | 0 | 0 | 5 |
| 1 | 0 | 2 | 8 |
Actually:
Finally it’s the same as my answer.
One single long job:
root@C202511211157657:~# python3 mlfq.py -l 0,40,0 -q 2 -a 2 -c
Here is the list of inputs:
OPTIONS jobs 1
OPTIONS queues 3
OPTIONS allotments for queue 2 is 2
OPTIONS quantum length for queue 2 is 2
OPTIONS allotments for queue 1 is 2
OPTIONS quantum length for queue 1 is 2
OPTIONS allotments for queue 0 is 2
OPTIONS quantum length for queue 0 is 2
OPTIONS boost 0
OPTIONS ioTime 5
OPTIONS stayAfterIO False
OPTIONS iobump 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 40 - ioFreq 0
Execution Trace:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] Run JOB 0 at PRIORITY 2 [ TICKS 1 ALLOT 2 TIME 39 (of 40) ]
[ time 1 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 2 TIME 38 (of 40) ]
[ time 2 ] Run JOB 0 at PRIORITY 2 [ TICKS 1 ALLOT 1 TIME 37 (of 40) ]
[ time 3 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 1 TIME 36 (of 40) ]
[ time 4 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 2 TIME 35 (of 40) ]
[ time 5 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 2 TIME 34 (of 40) ]
[ time 6 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 33 (of 40) ]
[ time 7 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 32 (of 40) ]
[ time 8 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 31 (of 40) ]
[ time 9 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 30 (of 40) ]
...
[ time 39 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 40) ]
[ time 40 ] FINISHED JOB 0
Final statistics:
Job 0: startTime 0 - response 0 - turnaround 40
Avg 0: startTime n/a - response 0.00 - turnaround 40.00
Adding a short job:
root@C202511211157657:~# python3 mlfq.py -l 0,40,0:20,8,0 -q 2 -a 2 -c
Here is the list of inputs:
OPTIONS jobs 2
OPTIONS queues 3
OPTIONS allotments for queue 2 is 2
OPTIONS quantum length for queue 2 is 2
OPTIONS allotments for queue 1 is 2
OPTIONS quantum length for queue 1 is 2
OPTIONS allotments for queue 0 is 2
OPTIONS quantum length for queue 0 is 2
OPTIONS boost 0
OPTIONS ioTime 5
OPTIONS stayAfterIO False
OPTIONS iobump 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 40 - ioFreq 0
Job 1: startTime 20 - runTime 8 - ioFreq 0
Execution Trace:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] Run JOB 0 at PRIORITY 2 [ TICKS 1 ALLOT 2 TIME 39 (of 40) ]
[ time 1 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 2 TIME 38 (of 40) ]
[ time 2 ] Run JOB 0 at PRIORITY 2 [ TICKS 1 ALLOT 1 TIME 37 (of 40) ]
[ time 3 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 1 TIME 36 (of 40) ]
[ time 4 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 2 TIME 35 (of 40) ]
[ time 5 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 2 TIME 34 (of 40) ]
[ time 6 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 33 (of 40) ]
[ time 7 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 32 (of 40) ]
[ time 8 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 31 (of 40) ]
...
[ time 19 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 20 (of 40) ]
[ time 20 ] JOB BEGINS by JOB 1
[ time 20 ] Run JOB 1 at PRIORITY 2 [ TICKS 1 ALLOT 2 TIME 7 (of 8) ]
[ time 21 ] Run JOB 1 at PRIORITY 2 [ TICKS 0 ALLOT 2 TIME 6 (of 8) ]
[ time 22 ] Run JOB 1 at PRIORITY 2 [ TICKS 1 ALLOT 1 TIME 5 (of 8) ]
[ time 23 ] Run JOB 1 at PRIORITY 2 [ TICKS 0 ALLOT 1 TIME 4 (of 8) ]
[ time 24 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 2 TIME 3 (of 8) ]
[ time 25 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 2 TIME 2 (of 8) ]
[ time 26 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 1 (of 8) ]
[ time 27 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 0 (of 8) ]
[ time 28 ] FINISHED JOB 1
[ time 28 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 19 (of 40) ]
...
[ time 47 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 40) ]
[ time 48 ] FINISHED JOB 0
Final statistics:
Job 0: startTime 0 - response 0 - turnaround 48
Job 1: startTime 20 - response 0 - turnaround 8
Avg 1: startTime n/a - response 0.00 - turnaround 28.00
I/O involved:
root@C202511211157657:~# python3 mlfq.py -l 0,40,0:5,8,1 -q 2 -a 2 -c
Here is the list of inputs:
OPTIONS jobs 2
OPTIONS queues 3
OPTIONS allotments for queue 2 is 2
OPTIONS quantum length for queue 2 is 2
OPTIONS allotments for queue 1 is 2
OPTIONS quantum length for queue 1 is 2
OPTIONS allotments for queue 0 is 2
OPTIONS quantum length for queue 0 is 2
OPTIONS boost 0
OPTIONS ioTime 5
OPTIONS stayAfterIO False
OPTIONS iobump 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 40 - ioFreq 0
Job 1: startTime 5 - runTime 8 - ioFreq 1
Execution Trace:
[ time 0 ] JOB BEGINS by JOB 0
[ time 0 ] Run JOB 0 at PRIORITY 2 [ TICKS 1 ALLOT 2 TIME 39 (of 40) ]
[ time 1 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 2 TIME 38 (of 40) ]
[ time 2 ] Run JOB 0 at PRIORITY 2 [ TICKS 1 ALLOT 1 TIME 37 (of 40) ]
[ time 3 ] Run JOB 0 at PRIORITY 2 [ TICKS 0 ALLOT 1 TIME 36 (of 40) ]
[ time 4 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 2 TIME 35 (of 40) ]
[ time 5 ] JOB BEGINS by JOB 1
[ time 5 ] Run JOB 1 at PRIORITY 2 [ TICKS 1 ALLOT 2 TIME 7 (of 8) ]
[ time 6 ] IO_START by JOB 1
IO DONE
[ time 6 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 2 TIME 34 (of 40) ]
[ time 7 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 33 (of 40) ]
[ time 8 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 32 (of 40) ]
[ time 9 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 31 (of 40) ]
[ time 10 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 30 (of 40) ]
[ time 11 ] IO_DONE by JOB 1
[ time 11 ] Run JOB 1 at PRIORITY 2 [ TICKS 0 ALLOT 2 TIME 6 (of 8) ]
[ time 12 ] IO_START by JOB 1
IO DONE
[ time 12 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 29 (of 40) ]
[ time 13 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 28 (of 40) ]
[ time 14 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 27 (of 40) ]
[ time 15 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 26 (of 40) ]
[ time 16 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 25 (of 40) ]
[ time 17 ] IO_DONE by JOB 1
[ time 17 ] Run JOB 1 at PRIORITY 2 [ TICKS 1 ALLOT 1 TIME 5 (of 8) ]
[ time 18 ] IO_START by JOB 1
IO DONE
[ time 18 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 24 (of 40) ]
[ time 19 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 23 (of 40) ]
[ time 20 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 22 (of 40) ]
[ time 21 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 21 (of 40) ]
[ time 22 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 20 (of 40) ]
[ time 23 ] IO_DONE by JOB 1
[ time 23 ] Run JOB 1 at PRIORITY 2 [ TICKS 0 ALLOT 1 TIME 4 (of 8) ]
[ time 24 ] IO_START by JOB 1
IO DONE
[ time 24 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 19 (of 40) ]
[ time 25 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 18 (of 40) ]
[ time 26 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 17 (of 40) ]
[ time 27 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 16 (of 40) ]
[ time 28 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 15 (of 40) ]
[ time 29 ] IO_DONE by JOB 1
[ time 29 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 2 TIME 3 (of 8) ]
[ time 30 ] IO_START by JOB 1
IO DONE
[ time 30 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 14 (of 40) ]
[ time 31 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 13 (of 40) ]
[ time 32 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 12 (of 40) ]
[ time 33 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 11 (of 40) ]
[ time 34 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 10 (of 40) ]
[ time 35 ] IO_DONE by JOB 1
[ time 35 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 2 TIME 2 (of 8) ]
[ time 36 ] IO_START by JOB 1
IO DONE
[ time 36 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 9 (of 40) ]
[ time 37 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 8 (of 40) ]
[ time 38 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 7 (of 40) ]
[ time 39 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 6 (of 40) ]
[ time 40 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 5 (of 40) ]
[ time 41 ] IO_DONE by JOB 1
[ time 41 ] Run JOB 1 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 1 (of 8) ]
[ time 42 ] IO_START by JOB 1
IO DONE
[ time 42 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 4 (of 40) ]
[ time 43 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 2 TIME 3 (of 40) ]
[ time 44 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 2 TIME 2 (of 40) ]
[ time 45 ] Run JOB 0 at PRIORITY 0 [ TICKS 1 ALLOT 1 TIME 1 (of 40) ]
[ time 46 ] Run JOB 0 at PRIORITY 0 [ TICKS 0 ALLOT 1 TIME 0 (of 40) ]
[ time 47 ] FINISHED JOB 0
[ time 47 ] IO_DONE by JOB 1
[ time 47 ] Run JOB 1 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 0 (of 8) ]
[ time 48 ] FINISHED JOB 1
Final statistics:
Job 0: startTime 0 - response 0 - turnaround 47
Job 1: startTime 5 - response 0 - turnaround 43
Avg 1: startTime n/a - response 0.00 - turnaround 45.00
- I thought setting just one queue would work.
4.Omitted.
5.10ms / 5% = 200ms.
6.Omitted.