调度:多级反馈队列

Sunday, October 13, 2019

多级反馈队列 MLFQ

基本规则

MLFQ 有许多独立的队列,每个队列有不同的优先级,任何时候,一个工作只能在一个队列,MLFQ 总是执行优先级高的队列。在同一个队列中,采用轮转调度方式。

MLFQ 的关健在于如何设置优先级。且优先级是动态的,根据情况来调整。 比如一个交互型的进程,MLFQ 会让它保持高优先级,如果是一个工作长时间地占用 CPU,MLFQ 会降低优先级。

  • 如果 A > B,运行 A
  • 如果 A = B,轮转运行 A,B

尝试:如何改变优先级

有一点很重要,我们即有强交互型,频繁放弃 CPU 的工作,也有需要大量 CPU 计算,响应时间不重要的工作。 我们调整优先级算法

  • 工作进入系统,放在最高优先级
  • 工作用完整个时间片,降低优先级,移入下一队列
  • 如果工作在其时间片内主动释放 CPU,优先级不变

按照上述规则,如果来了一个需要长时间运行的进程,过程会如图所示。 OS8.2

如果有 I/O,进程在时间片内主动放弃 CPU,优先级不变,比如等待用户的键盘输入这类工作。

OS8.4

缺陷

上述的规则,会有一定的缺陷,比如会有饥饿问题。如果有很多交互型工作,就会不断占用 CPU,导致低优先级的工作永远无法得到 CPU。 其次会被一些用户重写程序来欺骗调度程序,在时间片内调用一下 I/O,从而保持自己一直在高优先级。 最后一个程序可能在不同时间段有不同的行为,比如在某段时间变为交互型。但目前的规则他不会享受到优先级待遇。

尝试:提升优先级

我们可以尝试周期性的提升所有工作的优先级。

  • 经过一段时间 S,将系统所有工作重新加入到最高优先级队列。

新规则解决了刚刚说的两个问题,饿死问题和工作行为转变的问题。

OS8.5

从图可以看出,采用上述规则后,长工作在短工作加入后不会被饿死了。

尝试:更好的计时方式

还有一个问题我们要解决,不被程序欺骗调度程序。 解决方案是,调度程序应该记录一个进程在某一层中消耗的总时间,而不是在调度时重新计时。只要用完了配额,就降级,不管是一次用完还是拆分多次用完。 重写前面的一条规则

  • 一旦工作用完了其在某一层的时间配额(无论中间放弃了多少次 CPU),就降低其优先级。 OS8.6

MLFQ 调优及其他问题

我们该配置多少队列?每一层的时间片配置多大,多久提升一次优先级。这些都是我们需要考虑的。

大多数 MLFQ 变体都支持不同队列可变的时间片长度,比如高优先级队列的时间片很短,最低优先级的时间片很长。

有些甚至是用数学公式来调整优先级,比如 FreeBSD。

有些调度程序将最高优先级队列留给操作系统,普通用户无法得到该队列。

OS

抽象:地址空间

进程调度