通常我们队进程的执行时间、大小一无所知,如何调度程序?
8.1 MLFQ:基本规则
MLFQ中有许多独立的队列,每个队列有不同的优先级。任何时刻,一个工作只能存在于一个队列中,MLFQ只执行优先级高的工作。没有为每个工作指定不变的优先级,而是根据观察到的行为调整其优先级。
8.2 尝试1:如何改变优先级
MLFQ会有缺点:会产生饿死问题。如果系统有很多交互性工作,就会不断占用CPU,导致长工作永远无法得到CPU。
8.3 尝试2:提升优先级
- 周期性提升所有工作的优先级——经过一段时间,就将系统中所有工作重新加入最高优先级队列。
此处,添加时间段S的值应该如何设置。如果S设置的太高,长工作会借;如果设置的太低,交互性工作得不到合适的CPU时间比例。
8.4 尝试3:更好的计时方式
为MLFQ的每层队列提供更完善的CPU计时方式。调度程序应该记录一个进程在某一层中消耗的的总时间,而不是在每次调度到它时重新计时。只要进程用完了自己的配额,就降低一个优先级。
最终的MLFQ规则:
规则 1:如果 A 的优先级 > B 的优先级,运行 A(不运行 B)。
规则 2:如果 A 的优先级 = B 的优先级,轮转运行 A 和 B。
规则 3:工作进入系统时,放在最高优先级(最上层队列)。
规则 4:一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次CPU),就降低其优先级(移入低一级队列)。
规则 5:经过一段时间 S,就将系统中所有工作重新加入最高优先级队列。
MLFQ不需要对工作的运行方式有先验知识,而是通过观察工作的运行来给出对应的优先级。