type
status
date
slug
summary
tags
category
icon
password
类型
标签
状态
多级反馈队列（Multi-level Feedback Queue，MLFQ）需要解决两方面的问题：
- 优化周转时间
- 降低响应时间
没有工作长度的先验(prior)知识，如何设计一个能同时减少响应时间和周转时间的调度程序？
基础规则
MLFQ中有许多独立的队列（queen），每个队列有不同的优先级（priority）。任何时刻，一个工作只能存在于一个队列中。MLFQ总是有优先执行较高优先级的工作。
每个队列中可能会有多个工作，因此有相同的优先级。此时我们对这些工作采用轮转调度。
因此MLFQ调度策略的关键在于如何设置优先级。它没有额外i每个工作指定不变的优先情绪，而是根据观察到的行为调整它的优先级。例如，如果一个工作不断放弃CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。
通过这种方式，MLFQ在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。现在我们得到了两条基本规则：
- 规则1：如果A的优先级 > B的优先级，运行A而不运行B
- 规则2：如果A的优先级 = B的优先级，轮转运行A和B。
如何改变优先级
需先记得工作负载：既有运行时间很短，频繁放弃CPU的交互型工作，也有需要很多CPU时间、响应时间却不重要的长时间计算密集型工作。
- 规则3：工作进入系统时，放在最高优先级（嘴上层队列）。
- 规则4a：工作用完整个时间片后，降低其优先级（一移入下一个队列）
- 规则4b：如果工作在其时间片内主动释放CPU，则优先级不变。
实例1：单个长工作
如果系统中有一个需要长时间运行的工作，如下图所示,在一个有3个队列的调度程序中，随着时间推移，这个工作的运行情况。
可知，该工作受首先进入最高优先级（Q2）。执行一个 10ms 的时间片后，调度程序将工作的优先级减1，因此进入Q1。在Q1执行一个时间片后，最终降低优先级进入系统的最低优先级（Q0)，一直留在那里。
实例2：有了一个短工作
当有两个工作：A是一个长时间运行的 CPU 密集型工作，B 是一个运行时间很短的交互型工作。假设 A 执行一段时间后 B 到达。会发生什么呢？对 B 来说，MLFQ 会近似于 SJF 吗？
如果不知道工作是短工作还是长工作，那么从一开始就假设其是短工作，并赋予其最高优先级。如果确实是短工作，则很快执行完毕，否则将别慢慢移入低优先级队列，而这时该工作也被认为是长工作了。此时MLFQ近似于SJF。
实例3：如果有I/O
如果进程在时间片之前主动放弃了CPU，则保持它的优先级不变。这条规则的意图简单：假设交互型工作中有大量的 I/O 操作（比如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃 CPU。在这种情况下，我们不想处罚它，只是保持它的优先级不变。下图中灰色表示交互型工作，黑色表示长时间运行的工作。
当前MLFQ的问题
- 饥饿问题，当系统中有太多交互型工作，就会不断占用CPU，导致长工作永远无法得到CPU。
- 如何使调度程序维持资源的公平分配。上述算法无法处理以下攻击：进程在时间片用完之前，调用一个 I/O 操作（比如访问一个无关的文件），从而主动释放 CPU。如此便可以保持在高优先级，占用更多的 CPU 时间。
- 一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为一个交互型的进程。
提升优先级别
利用周期性地提升（boost）所有工作的优先级，可以一定程度上避免饥饿问题。其实现的最简单方法就是将所有所有的工作放在最高优先级队列。
- 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列中，它会以轮转的方式，于其他高优先级工作分享CPU，从而最终获得执行。其次，如果一个 CPU 密集 型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。
下图为有无优先级提升的对比：
但是S的值如果设置得太高，长工作就会被饿死，设置得太短，交互型工作又得不到合适的CPU时间比例。
更好的计时方式
如何阻止调度程序维持资源分配的公平性：为 MLFQ 的每层队列提供更完善的 CPU 计时方式（accounting）。调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次用完的，还是拆成很多次用完。我们就需要从写规则4a 和规则 4b。
- 规则4：一旦工作用完了其在某一层中的事件配额（无论中间放弃了多少次CPU），就降低其优先级。
下图对比了在规则 4a、4b 的策略下（左图），以及在新的规则 4（右图）的策略下，同样试图愚弄调度程序的进程的表现。
没有规则 4 的保护时，进程可以在每个时间片结束前发起一次 I/O 操作，从而垄断 CPU 时间。有了这样的保护后，不论进程的 I/O 行为如何，都会慢慢地降低优先级，因而无法获得超过公平的 CPU 时间比例。
MLFQ调优及其他问题
现在我们还需要处理一个最大的问题：如何配置一个调度程序？
例如，大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如 10ms 或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是 CPU 密集型工作，配置更长的时间片会取得更好的效果。
避免巫毒常量（Ousterhout 定律）
尽可能避免巫毒常量是个好主意。但是却难以实现，我们也可以让系统自己去学习一个很优化的值，但这同样也不容易。因此，通常我们会有一个写满各种参数值默认值的配置文件，使得系统管理员可以方便地进行修改调整。然而，大多数使用者并不会去修改这些默认
值，这时就寄希望于默认值合适了。
时分调度类TS很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级。
管理员可以通过这些表，让调度程序的行为方式不同。该表默认有 60 层队列，时间片长度从 20ms（最高优先级），到几百 ms（最低优先级），每一秒左右提升一次进程的优先级。
而有些MLFQ调度程序没有表，甚至没用上述规则，有些采用数学公式来计算某个工作的当前优先级。有些调度程序还有些上文未提及的特征。例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议（advice），比
小结
多级反馈队列—有多级队列，并利用反馈信息决定某个工作的优先级。关注进程的一贯表现，然后区别对待。
MLFQ的相关规则：
- 规则 1：如果 A 的优先级 > B 的优先级，运行 A（不运行 B）。
- 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
- 规则 3：工作进入系统时，放在最高优先级（最上层队列）。
- 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
- 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。
MLFQ不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ 可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于 SJF/STCF 的很好的全局性能，同时对长时间运行的CPU 密集型负载也可以公平地、不断地稳步向前。
- Author:Uonlra
- URL:https://www.uonlra.blog//article/1cc54775-fb6a-8014-9061-c0387d2868b2
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
