进程调度算法:多级反馈队列
收藏


进程调度算法的基础在上一篇文章中我们已经聊过了,这里不再重复,只是跟大家再复习一下: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,这也是最终的目的。最后感谢阅读,更多内容持续更新中。

官方公众号