操作系统导论-多级反馈队列

第八章:多级反馈队列

优先级的规则:

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

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

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

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

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

    运行的指令如下

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

    得到的结果如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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

    计算过程
    MLFQ_1

    实际答案

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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:单个长工作

      1
      ./mlfq.py -l 0,200,0 -n 3 -q 10 -c
    2. 实例2:来一个短工作

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

      1
      2
      # 每次拥有io的进程完成了io操作后,总会先切换到io的任务进行完成
      ./mlfq.py -l 0,190,0:0,10,1 -n 2 -q 10 -i 10 -c
    4. 拥有优先级提升的调度方式 - Boost

      不采用优先级提升时

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

      执行后可以发现,在Job1Job2执行完毕之前Job0无法执行,被饿死

      采用优先级提升时

      1
      ./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. 更好的计时方式 - 强制降低优先级

      降低优先级前

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

      强制降低优先级后

      1
      2
      # 饿死的情况得到解决,两个任务依次执行平等的时间
      ./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的时候,执行队列有

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

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

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

操作系统导论-多级反馈队列
https://halc.top/p/b7974b6
作者
HalcyonAzure
发布于
2022年4月5日
许可协议