OSTEP：通过多级反馈的调度策略

第八章：多级反馈队列

优先级的规则：

• 当任务刚进入操作系统的时候其优先级最高
• 优先级的切换：
  • 当任务运行的时间超过时间片，则优先级降低
  • 当任务在时间片中暂停使用CPU，则优先级不变
  • 一个任务在未达到时间片时放弃CPU则优先级不变

  对于交互式任务来说，我们不希望降低它的优先级，而希望它在某一优先级反复执行

  • 每个任务在某一优先级的总时间不超过一个时间片，达到后则强制降低优先级，并在Boost后重置所有任务优先级

根据以上规则完成以下练习：

1. 创建两个任务和队列，并且关闭IO的同时限制任务的长度。计算在MLFQ中的执行情况

   运行的指令如下

   ./mlfq.py -j 2 -n 2 -m 15 -M 0

   得到的结果如下

   OPTIONS jobs 2
   OPTIONS queues 2
   OPTIONS allotments for queue  1 is   1
   OPTIONS quantum length for queue  1 is  10
   OPTIONS allotments for queue  0 is   1
   OPTIONS quantum length for queue  0 is  10
   OPTIONS boost 0
   OPTIONS ioTime 5
   OPTIONS stayAfterIO False
   OPTIONS iobump False
   
   Job List:
   Job  0: startTime   0 - runTime  12 - ioFreq   0
   Job  1: startTime   0 - runTime   6 - ioFreq   0

   计算过程
   

   实际答案

   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 9 ALLOT 1 TIME 11 (of 12) ]
   [ time 1 ] Run JOB 0 at PRIORITY 1 [ TICKS 8 ALLOT 1 TIME 10 (of 12) ]
   [ time 2 ] Run JOB 0 at PRIORITY 1 [ TICKS 7 ALLOT 1 TIME 9 (of 12) ]
   [ time 3 ] Run JOB 0 at PRIORITY 1 [ TICKS 6 ALLOT 1 TIME 8 (of 12) ]
   [ time 4 ] Run JOB 0 at PRIORITY 1 [ TICKS 5 ALLOT 1 TIME 7 (of 12) ]
   [ time 5 ] Run JOB 0 at PRIORITY 1 [ TICKS 4 ALLOT 1 TIME 6 (of 12) ]
   [ time 6 ] Run JOB 0 at PRIORITY 1 [ TICKS 3 ALLOT 1 TIME 5 (of 12) ]
   [ time 7 ] Run JOB 0 at PRIORITY 1 [ TICKS 2 ALLOT 1 TIME 4 (of 12) ]
   [ time 8 ] Run JOB 0 at PRIORITY 1 [ TICKS 1 ALLOT 1 TIME 3 (of 12) ]
   [ time 9 ] Run JOB 0 at PRIORITY 1 [ TICKS 0 ALLOT 1 TIME 2 (of 12) ]
   [ time 10 ] Run JOB 1 at PRIORITY 1 [ TICKS 9 ALLOT 1 TIME 5 (of 6) ]
   [ time 11 ] Run JOB 1 at PRIORITY 1 [ TICKS 8 ALLOT 1 TIME 4 (of 6) ]
   [ time 12 ] Run JOB 1 at PRIORITY 1 [ TICKS 7 ALLOT 1 TIME 3 (of 6) ]
   [ time 13 ] Run JOB 1 at PRIORITY 1 [ TICKS 6 ALLOT 1 TIME 2 (of 6) ]
   [ time 14 ] Run JOB 1 at PRIORITY 1 [ TICKS 5 ALLOT 1 TIME 1 (of 6) ]
   [ time 15 ] Run JOB 1 at PRIORITY 1 [ TICKS 4 ALLOT 1 TIME 0 (of 6) ]
   [ time 16 ] FINISHED JOB 1
   [ time 16 ] Run JOB 0 at PRIORITY 0 [ TICKS 9 ALLOT 1 TIME 1 (of 12) ]
   [ time 17 ] Run JOB 0 at PRIORITY 0 [ TICKS 8 ALLOT 1 TIME 0 (of 12) ]
   [ time 18 ] FINISHED JOB 0
   
   Final statistics:
   Job  0: startTime   0 - response   0 - turnaround  18
   Job  1: startTime   0 - response  10 - turnaround  16
   Avg  1: startTime n/a - response 5.00 - turnaround 17.00

2. 以下为每个章节的实例复现参数

   1. 实例1:单个长工作

      ./mlfq.py -l 0,200,0 -n 3 -q 10 -c

   2. 实例2:来一个短工作

      # 150的运行时间是为了让任务经过两个时间片后保持在最低优先级运行
      ./mlfq.py -l 0,150,0:100,20,0 -n 3 -q 10 -c

   3. 实例3:如果有I/O呢

      # 每次拥有io的进程完成了io操作后，总会先切换到io的任务进行完成
      ./mlfq.py -l 0,190,0:0,10,1 -n 2 -q 10 -i 10 -c

   4. 拥有优先级提升的调度方式 - Boost

      不采用优先级提升时

      # 通过-S参数，忽略强制降低优先级的规则
      ./mlfq.py -l 0,120,0:100,45,9:109,45,9 -i 9 -n 3 -q 10 -S -c

      执行后可以发现，在Job1和Job2执行完毕之前Job0无法执行，被饿死

      采用优先级提升时

      ./mlfq.py -l 0,120,0:100,45,9:109,45,9 -i 9 -n 3 -q 10 -S -B 40 -c

      增加了Boost时间后，Job0能够通过每次提升的间隙运行来避免被饿死的问题

      模拟这个实验的时候遇到了一个不清楚是否为BUG的情况，将PRIORITY 0的任务Boost之后只会升级到PRIORITY 2后运行1 tick的时间，立马降低到PRIORITY 1。不清楚具体原因

   5. 更好的计时方式 - 强制降低优先级

      降低优先级前

      # 在时间片前一时刻放弃CPU，并且I/O操作同样只执行一个时刻，会将另外一个进程几乎饿死
      ./mlfq.py -q 10 -l 0,50,0:1,100,9 -i 1 -S -c

      强制降低优先级后

      # 饿死的情况得到解决，两个任务依次执行平等的时间
      ./mlfq.py -q 10 -l 0,50,0:1,100,9 -i 1 -c

3. MLFQ相当于在RR的思想上加入了优先级的控制，因此如果希望最后呈现的效果和RR相似，只需要设置只有一个queue存在即可

4. 在第二题的拥有优先级提升的调度方式 - Boost已经做了相关演示

5. 至少得到5%的CPU占用就代表在每个Boost的时间区块内，一个时间片的长度就是5%，所以答案为-B 200

6. 使用iodump的情况对比如下

   在不使用iodump的时候，执行队列有

   # 此时的效果类似RR，任务会轮番运行
    ./mlfq.py -l 0,20,0:0,20,10 -i 0 -c

   在使用了iodump之后，执行的队列有

   # 由于io操作会立刻完成，并且更新优先级，因此另外一个进程将被饿死
   ./mlfq.py -l 0,20,0:0,20,10 -i 0 -I -c