多级反馈队列（Multi-level Feedback Queue，简称MLFQ）需要解决两方面的问题。首先它要优化周转时间，这可以通过优先执行较短的工作来实现。然而，操作系统常常不知道工作要运行多久，而这又是SJF等算法所必需的。其次，MLFQ希望给用户提供较好的交互体验，因此需要降低响应时间。然而，轮转调度虽然降低了响应时间，周转时间却很差。所以这里的问题是：通常我们对进程一无所知，应该如何构建调度程序来实现这些目标？调度程序如何在运行过程中学习进程的特征，从而做出更好的调度决策？

多级反馈队列：基本规则

为了构建这样的调度程序，本章将介绍多级消息队列背后的基本算法。MLFQ中有许多独立的队列，每个队列有不同的优先级。任何时刻，一个工作只能存在于一个队列中。MLFQ总是优先执行较高优先级的工作（即那些在较高级队列中的工作）。每个队列中可能会有多个工作，它们具有同样的优先级。在这种情况下，我们就对这些工作采用轮转调度。至此，我们得到了MLFQ的两条基本规则：

规则1：如果A的优先级大于B的优先级，运行A不运行B
规则2：如果A的优先级等于B的优先级，轮转运行A和B

上图中，最高优先级有两个工作（A和B），工作C位于中等优先级，而D的优先级最低。按刚才介绍的基本规则，由于A和B有最高优先级，调度程序将交替的调度他们，而C和D永远都没有机会运行，除非A和B已经完成。

如何改变优先级

显然，在一个工作的生命周期中，MLFQ必须按照一定的策略改变其优先级。例如，如果一个工作不断放弃CPU去等待键盘输入，这是交互型进程的可能行为，MLFQ因此会让它保持高优先级。相反，如果一个工作长时间地占用CPU，MLFQ会降低其优先级。通过这种方式，MLFQ在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。下面是我们第一次尝试优先级调整算法。

规则3：工作进入系统时，放在最高优先级（最上层）队列
规则4a：工作用完整个时间片后，降低其优先级（移入低一级队列）
规则4b：如果工作在其时间片以内主动释放CPU，则优先级不变

单个长工作

假如系统中有一个需要长时间运行的工作，我们看看使用当前的MLFQ调度会发生什么。下图展示了在一个有3个队列的调度程序中，随着时间的推移，这个工作的运行情况。

从这个例子可以看出，该工作首先进入最高优先级（Q2）。执行一个10ms的时间片后，调度程序将工作的优先级减1，因此进入Q1。在Q1执行一个时间片后，最终降低优先级进入系统的最低优先级（Q0），一直留在那里。

来了一个短工作

再看一个较复杂的例子，看看MLFQ如何近似SJF。在这个例子中，有两个工作：A是一个长时间运行的CPU密集型工作，B是一个运行时间很短的交互型工作。假设A执行一段时间后B到达。会发生什么呢？

上图展示了这种场景的结果。A（用黑色表示）在最低优先级队列执行（长时间运行的CPU密集型工作都这样）。B（用灰色表示）在时间为100ms时到达，并被加入最高优先级队列。由于它的运行时间很短（只有20ms），经过两个时间片，在被移入最低优先级队列之前，B执行完毕。然后A继续运行（在低优先级）。

通过这个例子，我们可以体会到这个算法的一个主要目标：如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长工作了。通过这种方式，MLFQ近似于SJF。

结合I/O

根据上述规则4b，如果进程在时间片用完之前主动放弃CPU，则保持它的优先级不变。这条规则的意图很简单：假设交互型工作中有大量的I/O操作（比如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃CPU。在这种情况下，我们不想处罚它，只是保持它的优先级不变。

下图展示了这个运行过程，交互型工作B（用灰色表示）每执行1ms便需要进行I/O操作，它与长时间运行的工作A（用黑色表示）竞争CPU。MLFQ算法保持B在最高优先级，因为B总是让出CPU。如果B是交互型工作，MLFQ就进一步实现了它的目标，让交互型工作快速运行。

当前MLQF的一些问题

至此，我们有了基本的MLFQ。它看起来似乎相当不错，长工作之间可以公平地分享CPU，又能给短工作或交互型工作很好的响应时间。然而，这种算法有一些非常严重的缺点。首先，会有饥饿问题。如果系统有“太多”交互型工作，就会不断占用CPU，导致长工作永远无法得到CPU。即使在这种情况下，我们也希望这些长工作也能有所进展。其次，某些用户会用一些手段欺骗调度程序，让它给予进程远超公平的资源。例如，上述算法对如下的攻击束手无策：进程在时间片用完之前，调用一个I/O操作（比如访问一个无关的文件），从而主动释放CPU。如此便可以保持在高优先级，占用更多的CPU时间。做得好时（比如，每运行99%的时间片时间就主动放弃一次CPU），工作可以几乎独占CPU。最后，一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为一个交互型的进程。用目前的方法，它不会享受系统中其他交互型工作的待遇。

提升优先级

我们首先来尝试避免饥饿问题。要让CPU密集型工作也能局的一些进展，一个简单的思路是周期性地提升所有工作地优先级，最简单的实现就是将所有工作一股脑儿地扔到最高优先级队列。于是，我们有了以下规则。

规则5：每经过一段时间，就将系统中所有工作重新加入最高优先级队列

新规则一下解决了两个问题。首先，进程不会饿死——在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享CPU，从而最终获得执行。其次，如果一个CPU密集型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。

在这种场景下，我们展示长工作与两个交互型短工作竞争CPU时的行为。下图左边没有优先级提升，长工作在两个短工作到达后被饿死。右边每50ms就有一次优先级提升（这里只是举例，这个值可能过小），因此至少保证长工作会有一些进展，每过50ms就被提升到最高优先级，从而定期获得执行。

显然，添加时间段引入了新的问题：时间段的值该如何设定？如果设置得太高，厂工作就会饥饿；如果设置得太低，交互型工作又得不到合适的CPU时间比例。

更好的计时方式

为了防止用户欺骗调度程序，让它给予进程远超公平的资源，MLQF为每层队列提供更为完善的CPU计时方式。调度程序记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一级队列中去。不论它是一次用完的，还是拆成很多次用完。

规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）

上图对比了在规则4a、4b的策略下（左），以及在新的规则4（右）的策略下，同样试图欺骗调度程序的进程的表现。没有规则4的保护时，进程可以在每个时间片结束前发起一次I/O操作，从而垄断CPU时间。有了这样的保护后，不论进程的I/O行为如何，都会慢慢地降低优先级，因而无法获得超过公平的CPU时间比例。

其他问题

关于MLFQ调度算法还有一些问题。其中一个大问题是如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。例如，大多数的MLFQ变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如10ms或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是CPU密集型工作，配置更长的时间片会取得更好的效果。

本章包含了一组优化的MLFQ规则。为了方便查阅，我们重新列在这里。

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