多级反馈队列?

MLFQ

MLFQ 的基本规则:

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

MLFQ 调度策略的关键在于如何设置优先级。MLFQ 没有为每个工作指定不变的优先情绪而已,而是根据观察到的行为调整它的优先级。例如,如果一个工作不断放弃 CPU 去等待键盘输入,这是交互型进程的可能行为,MLFQ 因此会让它保持高优先级。相反,如果一个工作长时间地占用 CPU,MLFQ 会降低其优先级。通过这种方式,MLFQ 在进程运行过程中学习其行为,从而利用工作的历史来预测它未来的行为。 这个算法的一个主要目标: 如果不知道工作是短工作还是长工作,那么就在开始的时候假设其是短工作,并赋予最高优先级。如果确实是短工作,则很快会执行完毕,否则将被慢慢移入低优先级队列,而这时该工作也被认为是长工作了。通过这种方式,MLFQ 近似于 SJF。

看一个有 I/O 的例子: 如果进程在时间片用完之前主动放弃 CPU,则保持它的优先级不变。’这条规则的意图很简单:假设交互型工作中有大量的 I/O 操作(比如等待用户的键盘或鼠标输入),它会在时间片用完之前放弃 CPU。在这种情况下,我们不想处罚它,只是保持它的优先级不变。交互型工作 B(用灰色表示)每执行 1ms 便需要进行 I/O 操作,它与长时间运行的工作 A(用黑色表示)竞争 CPU。MLFQ 算法保持 B 在最高优先级,因为 B 总是让出 CPU。如果 B 是交互型工作,MLFQ 就进一步实现了它的目标,让交互型工作快速运行。

饥饿(starvation)问题: 如果系统有“太多”交互型工作,就会不断占用 CPU,(因为他的优先级没有发生改变)导致长工作永远无法得到 CPU(它们饿死了)。即使在这种情况下,我们希望这些长工作也能有所进展。

愚弄调度程序(game the scheduler): 其次,聪明的用户会重写程序,愚弄调度程序(game the scheduler)。愚弄调度程序指的是用一些卑鄙的手段欺骗调度程序,让它给远超公平的资源。上述算法对如下的攻击束手无策:进程在时间片用完之前,调用一个 I/O 操作(比如访问一个无关的文件),从而主动释放 CPU。如此便可以保持在高优先级,占用更多的 CPU 时间。做得好时(比如,每运行 99%的时间片时间就主动放弃一次 CPU),工作可以几乎独占 CPU。

至此,我们得到了 MLFQ 的两条基本规则。

规则 1:如果 A 的优先级 > B 的优先级,运行 A(不运行 B)。

意味着高优先级的队列的任务比低优先级队列的任务要先执行。

规则 2:如果 A 的优先级 = B 的优先级,轮转运行 A 和 B。

意味着同一级队列的任务交替轮流按照先来先执行的原则交替执行。

存在的问题:低优先级队列的任务将被饿死 (每次新到到达的任务 CPU 假设它是短作业且优先级别比较高) Q8 队列源源不断的有新的任务到来执行,那么低优先级队列的任务将被饿死。

基础版规则 3:刚进入的任务放在最高优先级(最上层队列)。

基础版规则 4a:工作用完整个时间片后,降低其优先级(移入下一个队列)。

基础版规则 4b:如果工作在其时间片以内主动释放 CPU,则优先级不变。

存在的问题:当某个任务每次都执行到 CPU 分配给他的时间片的 99%的时候,主动放弃 CPU 永远使得自己占据着最高优先级的队列,而且如果他自身就需要很长的时间,那么低优先级队列的任务将被饿死。

进阶版规则 4:任务用完这层队列分配给它的最大的时间配额时,无论中间主动放弃了多少次 CPU,都把该任务降低优先级(移入下一个队列)。

为 MLFQ 的每层队列提供更完善的 CPU 计时方式(accounting)。调度程序应该记录一个进程在某一层中消耗的总时间,而不是在调度时重新计时。只要进程用完了自己的配额,就将它降到低一优先级的队列中去。不论它是一次用完的,还是拆成很多次用完。

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

避免饥饿问题。要让 CPU 密集型工作也能取得一些进展(即使不多),我们能做些什么?

周期性地提升(boost)所有工作的优先级。可以有很多方法做到,但我们就用最简单的:将所有工作扔到最高优先级队列。于是有了新规则。

其他存在的问题:配置多少个级别的队列?每个队列的时间额度配比怎么设置大小?多久提升一次进程的优先级?

MLFQ 的变体:

1.支持不同队列可变的时间片长

高优先级队列通常只有较短的时间片(比如 10ms 或者更少),因而这一层的交互工作可以更快地切换。低优先级队列中更多的是 CPU 密集型工作,配置更长的时间片会取得更好的效果。 Solaris 的 MLFQ 实现(时分调度类 TS)很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级,每层的时间片多大,以及多久提升一个工作的优先级[。管理员可以通过这些表,让调度程序的行为方式不同。该表默认有 60 层队列,时间片长度从 20ms(最高优先级),到几百 ms(最低优先级),每一秒左右提升一次进程的优先级。其他一些 MLFQ 调度程序没用表,甚至没用本章中讲到的规则,有些采用数学公式来调整优先级。例如,FreeBSD 调度程序(4.3 版本),会基于当前进程使用了多少 CPU,通过公式计算某个工作的当前优先级。另外,使用量会随时间衰减,这提供了期望的优先级提升,但与这里描述方式不同。阅读 Epema 的论文,他漂亮地概括了这种使用量衰减(decay-usage)算法及其特征。

最后,许多调度程序有一些我们没有提到的特征。例如,有些调度程序将最高优先级队列留给操作系统使用,因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议(advice),比如通过命令行工具 nice,可以增加或降低工作的优先级(稍微),从而增加或降低它在某个时刻运行的机会。操作系统很少知道什么策略对系统中的单个进程和每个进程算是好的,因此提供接口并允许用户或管理员给操作系统一些提示(hint)常常很有用。我们通常称之为建议(advice),因为操作系统不一定要关注它,但是可能会将建议考虑在内,以便做出更好的决定。这种用户建议的方式在操作系统中的各个领域经常十分有用,包括调度程序(通过 nice)、内存管理(madvise),以及文件系统(通知预取和缓存)。 一组优化的 MLFQ 规则。为了方便查阅,我们重新列在这里。

总结

规则 1:如果 A 的优先级 > B 的优先级,运行 A(不运行 B)。

规则 2:如果 A 的优先级 = B 的优先级,轮转运行 A 和 B。

规则 3:工作进入系统时,放在最高优先级(最上层队列)。

规则 4:当每个任务完成自己在该层被分配到的时间分额时,就会降低优先级。(无论中间主动放弃了多少次 CPU)。

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

Tags: golang
Share: X (Twitter) Facebook LinkedIn