多级反馈队列

MLFQ

多级反馈队列是一种“从历史中学习的调度算法”。

基本规则

MLFQ中有许多个队列，它们的优先级不同。同一队列中的任务的优先级相同。优先级较高的队列先工作。同一队列中的任务采用轮转的方式进行调度。

MLFQ没有为每一个工作都指定不变的优先级，而是根据工作的行为调整它的优先级。例如，如果一个工作不断放弃CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。相反，如果一个工作长时间地占用 CPU，MLFQ 会降低其优先级。通过这种方式，MLFQ 在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。

MLFQ的两条基本规则：

1. 如果A的优先级 > B的优先级，运行A（不运行B）​
2. 如果A的优先级 = B的优先级，轮转运行A和B

改变优先级

我们需决定一个工作在其生命周期内，它的优先级如何变化。既有运行时间很短、频繁放弃CPU的交互型工作，也有需要很多CPU时间、响应时间却不重要的长时间计算密集型工作。

1. 工作进入系统时，放在最高优先级（最上层队列）
2. 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU）​，就降低其优先级（移入低一级队列）​。
3. 经过一段时间S，就将系统中所有工作重新加入最高优先级队列

前两条规则是为了让长工作之间可以公平地分享CPU，又能给交互型工作很好的响应时间。当一个工作到来时，如果不知道它是短工作还是长工作，就先假设它是短工作（放在最高优先级的队列）。如果它是长工作，一段时间后它会自动进入低优先级队列，如果是短工作，它会在高优先级队列中执行完毕。通过这种方式，MLFQ类似于SJF。

如果是一个交互型任务，在其时间片内主动放弃CPU，它的优先级保持不变，以实现交互的目的。

第三条规则是为了避免长工作饿死（当系统中有太多交互型工作时）。

其它问题

有了上面的基本规则，还需要解决一些问题：设置多少个优先队列，每个队列中有多少任务，时间片设置为多少。

大多数MLFQ支持不同队列可变的时间片长度。高优先级队列时间片长度通常较短，低优先级队列时间片长度通常较长。

总结

现将MLFQ的几条规则总结如下：

1. 如果A的优先级 > B的优先级，运行A（不运行B）​
2. 如果A的优先级 = B的优先级，轮转运行A和B
3. 工作进入系统时，放在最高优先级（最上层队列）
4. 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU）​，就降低其优先级（移入低一级队列）​。
5. 经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

许多系统使用某种类型的 MLFQ
作为自己的基础调度程序，包括类BSD UNIX系统[LM+89，B86]、Solaris[M06]以及 Windows NT和其后的Window系列操作系统。