进程调度算法：多级反馈队列

更多内容尽在公众号：Go语言之美。持续更新中。

进程调度算法的基础在上一篇文章中我们已经聊过了，这里不再重复，只是跟大家再复习一下：FIFO 先进先出，哪个进程先来了我们就先执行哪个，知道当前进程结束再执行下一个到来的进程。最短任务优先（SJF）与最短完成时间优先（STCF），先执行时间短的，再执行时间长的。上面的算法中主要考量的是平均周转时间，除此之外还有另外的考量标准就是响应时间，与此对应的是轮转（RR）算法，就是轮训执行进程。在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务。重复执行，直到所有结束。这几个算法都是基础，也就是在这些算法上慢慢完善才会出现更加完美的方案，今天就和大家聊一个改进的算法多级反馈队列。

多级反馈队列（Multi-level Feedback Queue，MLFQ），1962年 Corbato 首次提出多级反馈队列，应用于兼容时分共享系统（CTSS）。我们还记得之前的两方面问题，周转时间和响应时间，这个算法主要就是解决这两个问题。

MLFQ 中有许多独立的队列，每个队列有不同的优先级，任何时刻，一个工作只能存在与一个队列中，而且 MLFQ 总是优先执行高优先级的工作。当然，每个队列中可能有多个工作，而且具有同样的优先级，这种情况，就对这些工作采用轮转调度。

因此，MLFQ 调度策略的关键就在于优先级应该如何设置。这里我们再说一个题外话，通常我们对进程是一无所知的，所以我们应该如何确定优先级呢？MLFQ 是用历史经验预测未来的一个典型例子，如果工作有明显的阶段性行为，因此可以预测，那么这种方式就很有效。同样这么做也是有风险的，也可能让系统做出比一无所知更糟糕的决定。

言归正传，MLFQ 如何设置优先级呢？她没有为每个工作指定不变的优先级，而是通过观察工作的行为来调整它的优先级。例如：如果有一个工作不断的放弃 CPU 去等待键盘输入，MLFQ 因此会保持它最高优先级。相反，如果一个工作长时间的霸占 CPU，那么 MLFQ 就会降低它的优先级。但是大家想一个问题：假如有三个工作，A 和 B 都是最高优先级，而 C 是最低优先级，这时根据我们之间说的，操作系统就会先执行 A 和 B，由于他们两个是相同优先级，调度程序就交替的调度他们两个，这种情况，C 程序就没有机会执行了。

接下来要说的就是优先级不是一成不变的，那么我们如何来合理的调整优先级呢？

首先我们要记住工作负载：既有运行时间很短、频繁放弃 CPU 的交互型工作，也有需要很多 CPU 时间、响应时间却不重要的长时间计算密集型工作。

先看单个长工作的情况。

上图中展示了一个长时间运行的工作的优先级改变的情况。从这个例子可以看出，该工作首先进入最高优先级（Q2），执行一个 10 的时间片后，调度程序将其优先级降1，进入Q1。同样，经过10的时间片后，从Q1降低为Q0。由于Q0是最低优先级，所以就一直在这个级别不动了。

接下来大家可以想一下如果来了一个短工作会怎样呢？

假如我们有一个工作 A，此时 A 的优先级为最低，这时又来了一个新的工作 B，恰巧 B 是一个运行时间很短的交互型工作，那么根据之前我们所说的，如果一个工作频繁的放弃 CPU，那么它就一直是最高优先级，如果说同时来了大量的类似 B 这种短的交互型工作呢？这样长工作就没有机会得到 CPU 了。而且，假如程序员知道了这问题，那么再写程序的时候可以手动实现短工作，从而霸占 CPU，这是致命的问题。下图展示了长工作被饿死的情况：

此时，我们面临的问题就是，如何解决长工作无法获得 CPU 的问题，一个简单的思路就是，周期性的提升所有工作的优先级。在一段时间后，将所有工作的优先级都设置为最高，然后再根据工作的具体行为来决定优先级。这样我们就可以保证长工作不会饿死了。但是这个时间该如何设置？这个时间的设置是重中之重，如果时间设置的太高，长工作就会饿死，如果太低，交互型短工作又得不到合适的 CPU 时间。

这时我们就需要一个最好的计时方式。这里的解决方案就是，为 MLFQ 的每层队列提供更完善的 CPU 计时方式，调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降低到下一个优先级的队列中，不论它是一次用完的，还是拆分多次用完的。

下图就是采用了新的计时方式的两个工作的情况：

开始黄色的工作为最高优先级，在 Q1 队列经过了 10 的时间后，将其优先级降低一级，当在 Q2 队列经过了 10 的时间后，再将其优先级降低一级，通过这样的方式来防止 CPU 的垄断。

到目前位置，我们已经将 MLFQ 算法说的已经差不多了，一些重要的点都和大家说过了，也给出了基本的解决办法，现在我们再总结一下：

MLFQ：多级反馈队列，有多个等级的队列，并利用反馈的信息决定某个工作的优先级，同时合理的改变所有工作的优先级。

基本规则（参考自操作系统导论）：

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

目前位置 MLFQ 算法基本上属于告一段落了，这个算法的精髓就是，它不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的策略，从而让各个工作可以更加公平合理的使用 CPU，这也是最终的目的。（更多内容尽在公众号：Go语言之美）