多级反馈队列（Multi-level Feedback Queue，MLFQ）
多级反馈队列解决的问题：
我们对进程一无所知，我们应该如何构建调度程序来实现这些目标？调度程序如何在运行过程中学习进程的特征，从而做出更好的调度决策？即：没有工作长度的先验（priori）知识，如何设计一个能同时减少响应时间和周转时间的调度程序？
MLFQ 基本规则
MLFQ中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ总是优先执行较高优先级的工作（即在较高级队列中的工作）。由于每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，我们就对这些工作采用轮转调度。由以上，引出MLFQ的两个规则：
- 规则1：如果A的优先级 > B的优先级，运行A（不运行B）。
- 规则2：如果A的优先级 = B的优先级，轮转运行A和B。
问题：
- 若A，B两个进程处于高优先级，C进程处于低优先级，那么C进程只能在A,B进程执行完成后才执行
由于低优先级的进程会饿死，所以我们尝试改变优先级，引出以下三个规则：
- 规则3：工作进入系统时，放在最高优先级（最上层队列）。
- 规则4：工作用完整个时间片后，降低其优先级（移入下一个队列）。
- 规则5：如果工作在其时间片以内主动释放CPU，则优先级不变。
分析：
- 单个长工作：假设此MLFQ存在三个优先级队列，该工作首先进入最高优先级。执行一个时间片后，调度程序将工作的优先级减1，因此进入中间优先级。在中间优先级执行一个时间片后，最终降低优先级进入系统的最低优先级，一直留在那里。
- 一个短工作：一个短工作到达并被加入最高优先级队列。由于它的运行时间很短（假设20ms），在被移入最低优先级队列之前，短工作执行完毕。
- I/O工作：如果I/O工作在时间片用完之前主动放弃CPU，则保持它的优先级不变。这条规则的意图很简单：假设交互型工作中有大量的I/O操作（比如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃CPU。在这种情况下，我们不想处罚它，只是保持它的优先级不变。
问题：
- 饥饿（starvation）问题。如果系统有太多交互型工作，就会不断占用CPU，导致长工作永远无法得到CPU（它们饿死了）。
- 一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为一个交互型的进程。
- 愚弄调度程序：进程在时间片用完之前，调用一个I/O操作，从而主动释放CPU。如此便可以保持在高优先级，占用更多的CPU时间。
为了避免饥饿问题，我们将提升优先级，因此引出以下规则：
- 规则6：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
分析：
- 长工作与两个交互型短工作竞争CPU时：长工作每 S ms就有一次优先级提升，因此至少保证长工作会有一些进展，每过 S ms就被提升到最高优先级，从而定期获得执行。
问题：
- S的值应该如何设置？如果S设置得太高，长工作会饥饿；如果设置得太低，交互型工作又得不到合适的CPU时间比例。
因为工作在时间片以内释放CPU，我们就保留了它的优先级，这将导致调度程序被愚弄，为了阻止调度程序被愚弄，我们改变规则4，5：
- 规则4，5：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
分析：
- 不论进程的I/O行为如何，都会慢慢地降低优先级，因而无法获得超过公平的CPU时间比例。
MLFQ 其他问题
- 配置多少队列？
- 每一层队列的时间片配置多大？
- 为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？
这些问题没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。
- 例如，大多数的MLFQ变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如10ms或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是CPU密集型工作，配置更长的时间片会取得更好的效果。
- 例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议，比如通过命令行工具nice，可以增加或降低工作的优先级
- 例如，有些采用数学公式来调整优先级。
Comments | NOTHING