0、引言

在上篇文章操作系统学习（一）：浅析操作系统进程调度算法中讲到，在一个通用的操作系统中，操作系统通常对每个作业的长度知之甚少。因此，我们如何建立一个没有这种先验知识的 SJF/STCF？更进一步，我们如何能够将已经看到的一些想法与 RR 调度程序结合起来，以便响应时间也变得很好？没有工作长度的先验（priori）知识，如何设计一个能同时减少响应时间和周转时间的调度程序？

多级反馈队列是用历史经验预测未来的一个典型的例子，操作系统中有很多地方采用了这种技术。

1、多级反馈队列（MLFQ）的基本规则

如果A的优先级 > B的优先级，运行A（不运行B）

如果A的优先级 = B的优先级，轮转运行A和B

工作进入系统时，放在最高优先级（最上层队列）

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

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

你可能还不明白这些规则是什么意思，不要紧，我们一步一步来看。

2、MLFQ的规则具体说明

MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）。

当然，每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，我们就对这些工作采用轮转调度。

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

由此我们得到了 MLFQ 的两条基本规则：

规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）

规则 2：如果 A 的优先级 = B 的优先级，轮转运行A 和 B

而当工作刚刚来到时，我们并不能判断它是计算密集型工作还是交互型工作，因此，我们得到一个规则：

规则 3：将刚进入系统时的工作放入最上层

当工作用完一个时间片后，降低其优先级，移入下一个队列（说明计算比较密集）；而当工作主动放弃CPU时，优先级不变（可能是交互型工作）。其实可以总结一下：当来一个工作时，我们默认他是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕；如果不是短工作，就会被慢慢移入低优先级队列。其实在这里MLFQ近似于SJF。

在这里会有两个问题：一是如果交互操作太频繁了，会使长工作永远无法获得CPU（饿死），并且一个工作可能不是一直是计算密集型，它也可能需要交互；二是黑客可以通过一些手段进行攻击：比如在时间片即将用完的时候，调用一个I/O操作，比如访问一个无关的文件，从而主动放弃CPU，这样就可以保持在高优先级，操作得当的话，几乎可以独占CPU。

解决问题一的方式可以提炼出一个规则：

规则 5：经过一段时间S后，将所有工作都加入到最高优先级

这样的话，计算型的工作也可以以轮转的方式和其他工作共享CPU（因为他们在同一优先级）。同时，如果一个工作从计算密集型变成了交互型，当所有工作都加入到最高优先级时，这样的工作也可以获得CPU。

咱们再来解决问题二，这里的痛点是工作在时间片以内释放 CPU时，就保留它的优先级。那么解决办法就是让CPU为每个工作分配的时间比例尽量“公平”，也就是说，调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次用完的，还是拆成很多次用完。那么我们可以总结一下这个规则：

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

这样，不论进程的 I/O 行为如何，都会慢慢地降低优先级，因而无法获得超过公平的 CPU 时间比例。

3、MLFQ调优及其他问题

关于 MLFQ 调度算法还有一些问题。其中一个大问题是如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。

例如，大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如 10ms 或者更少），因而这一层的交互工作可以更快地切换。

4、总结

     

MLFQ 有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ 可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于 SJF/STCF 的很好的全局性能，同时对长时间运行的CPU 密集型负载也可以公平地、不断地稳步向前。