调度：多级反馈队列（MLFQ：Multi-Level Feed Queue）

续接上一节中最后的问题，没有完备的关于进程相关的知识背景，如何设计一个调度方案？

答：从历史中学习，MLFQ就是从历史经验中预测未来的一个典型例子，如果工作具有明显的阶段性行为，因此可以预测，那么此时可能会很有效，当然也需要格外小心使用这种技术，因为它可能会出错，导致比最初不知道的情况下做出还要糟糕的反馈。

MLFQ：基本规则

MLFQ于1962年，由Corbato提出，当时主要用于兼容分时共享系统（CTSS）。

MLFQ中有许多独立的队列，每个队列有不同的优先级，任何时刻，一个任务只能存在于一个队列中，MLFQ总是优先执行优先级较高的队列中的任务；而同一个队列中会存在多个任务，这些都具有同样的优先级，这些任务的调度采用轮转调度。

MLFQ的关键就是：如何设定任务的优先级？此时对于任务的优先级并不是一层不变的，它会观察任务的行为，从而动态调整它的优先级。

比如：有个任务执行过程中不停放弃CPU去等待IO输入，那么就会认为这个任务是高交互任务，就需要保持它的优先级处于较高的位置。而如果一个任务长时间占用CPU，MLFQ就会降低它的优先级。

因此得到了两条基本规则：

规则1：如果A的优先级大于B的优先级，运行A（不运行B）
规则2：如果A和B的优先级一样，轮转调度A和B

但是基于这条规则下，可能会出现一个问题：那就是加入A和B优先级最高，那么此时低优先级的C和D可能永远也无法执行，这很明显太不公平了。

尝试1：如何改变优先级

需要考虑一些情况：我们可能既有频繁放弃CPU等待IO的交互型任务，也会有长时间占用CPU的计算密集型任务，因此尝试调整规则：

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

实例1：单个长工作：

任务刚开始的时候，处于最高优先级，随着时间推移，逐步降低到最低优先级队列中：

实例2：来一个短工作：

在基于前面提到的长工作基础上，假设此时又来一个段工作，假设此时A为长工作，且是CPU密集型的任务，B是短工作，那么在A运行一段时间后，如果此时B到达，则B开始时处于最高优先级，加入B只经历了两个时钟周期就结束了，则B就可以在还未降级到最低队列的时候就执行完成了。

可以看到MLFQ在不知道任务到底是长任务还是短任务的情况下，统一默认都是短任务，随着时间的推移，如果不是短任务的，会逐渐集中到最低优先级队列中，而真正的短任务则会在还未移入到低优先级队列之前就执行完成了，从而达到了类似于SJF的效果。

实例3：如果有IO呢：

基于前面的4b假设，如果一个任务A在工作期间内主动释放CPU控制权，保持其优先级不变，那这样的话可以考虑有一种任务，它在一段始终周期内会主动释放CPU，并进入等待IO的状态，同时如果此时有另一个长时间运行的CPU密集型任务B，那么在A等待IO的时候，B可以运行，这样也可以保证B这种交互型任务能尽快得到响应。

MLFQ问题

基于前面的三个实例分析之后，大致对MLFQ有了一个基本的认识，但是这里面实际上存在一个问题：那就是饥饿问题。

试着考虑这样一个问题：如果此时有很多的交互型任务，同时也有一些CPU密集的长任务，那么在那些交互型任务互相切换到过程中，CPU密集型的任务可能永远都得不到运行的机会，这类任务也就等于被”饿死“了。

另外还存在一个隐患：就是如果有些”聪明“的程序员可以编写一些”愚弄“这种调度方案的程序：比如在一个始终周期内，99%的时间运行自己的任务，然后留1%故意发起一个IO（一个无关紧要的空IO调用这种），这样就基本上达到了CPU 99%的时间都会被它占用了。

尝试2：提升优先级

这种情况是基于前面那些规则下存在一些问题而提出来的，具体就是：

规则5：经过一段时间S后，就将系统中所有的任务重新加入到最高优先级队列中。

这样的好处就是：程序不会有被”饿死“的风险了，因为无论如何，经过一段时间后，最终都会重新得到运行。

【不采用优先级提升（左）和采用（右）】

但是这时候又带来了一个新的问题，这个一段时间S的具体值如何设置现在成为了关键：太长了，任务会”饥饿“，太短了则交互型任务得不到充分的CPU时间比例。即所谓的”巫毒常量“问题。

尝试3：更好的计时方式

针对前面提到的MLFQ被”愚弄“的问题，这里考虑一种新的解决方案；

其实被”愚弄“的元凶可以看到实际上就是4a和4b规则导致的，因此这里针对这两个规则做一个调整，调度程序单独对每个任务在某个优先级队列中做一个总时长记录，一旦任务用完了时间配额，就自动降到低一级的队列中，无论它是分多少次用完的。

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

不采用愚弄反制：

采用愚弄反制：

MLFQ调优及其他问题

如何配置一个调度程序

应该配置多少队列
每一层的队列时间片设置应该是多大
为了避免”饥饿“问题，应该多久调整一次任务优先级

在没有先验知识的前提下，这些都没法具体确定，只能在不断运行过程中，根据历史经验总结得到一个比较符合具体情况的数据。

比如：大多数的MLFQ都支持可变的时间片长度，高优先级队列拥有更短的时间片，因此这一层的任务可以更快进行切换；而对于低优先队列一般都是CPU密集型任务，给予更长的时间片可以得到更好的效果。

这里给出了一个Solaris的一个MLFQ实例介绍，它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级，管理员可以配置表来调整对应的行为，该表默认有60层，时间片长度从20ms到几百ms不等；每一秒左右提升一次任务优先级。

其他一些 MLFQ 调度程序没用表，甚至没用本章中讲到的规则，有些采用数学公式来调整优先级。例如，FreeBSD 调度程序（4.3 版本），会基于当前进程使用了多少 CPU，通过公式计算某个工作的当前优先级。

最后，许多调度程序有一些我们没有提到的特征。例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议（advice），比如通过命令行工具 nice，可以增加或降低工作的优先级（稍微），从而增加或降低它在某个时刻运行的机会。