多级反馈队列
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
复习
- 调度要解决什么：响应、吞吐、公平和优先级之间的矛盾
- 先来先服务与最短任务优先：简单调度为何会出现等待和饥饿
- 时间片与优先级调度：让多个程序都感觉自己被及时响应
TL;DR
- 多级反馈队列用多个优先级队列，让进程“先高后低”地浮动
- 新进程从高优先级开始，用完时间片还没完，就降到下一级
- 短任务在高优先级迅速完成，长任务逐级下沉，不必事先知道长短
- 它是“自动适应任务长短”的一种巧妙设计
正文
前面几种调度，要么要求“知道任务要跑多久”，要么需要人手工设定优先级。可现实中，调度器往往两眼一抹黑：来的到底是几毫秒的小任务，还是几小时的大家伙？
多级反馈队列（MLFQ，Multi-Level Feedback Queue）就是为这种“未知”而生的。
多个队列，先高后低
MLFQ 设置多个就绪队列，每个队列有不同的优先级：
高优先级 Q0 ← 新进程从这里开始
Q1
Q2
低优先级 Q3
规则大致是这样的：
- 新进程先进入最高优先级的队列
- 同一队列内，用时间片轮转
- 一个进程用完自己的时间片还没结束，就降到下一级队列
- 只有高优先级队列空了，才轮到低优先级队列
它为什么聪明
这套规则的效果很妙：
- 短任务：一上来就在高优先级，往往一两个时间片就跑完了，很快离开系统
- 长任务：占用 CPU 的时间越来越长，于是逐级下沉，把高优先级让给新来的短任务
- 交互任务：经常等 I/O、很少用满时间片，于是能一直待在较高优先级，保持响应
换句话说，它不用事先知道任务的长短，而是通过“观察它用了多少 CPU”来推断：总是很快就让出 CPU 的，多半是短任务或交互任务，给它高优先级；一直霸着 CPU 的，多半是长任务，把它压下去。
别忘了老化
不过，如果高优先级源源不断地来新任务，长任务会被一直压在最底层，又出现饥饿。所以 MLFQ 通常还要配一条老化规则：低优先级队列里的进程，等得够久，就把它升回高一级；或者定期把所有进程都提到最高优先级，重新洗一次牌。
一句话总结
MLFQ 把“优先级”变成了一个动态的、会自我调整的东西：谁表现得像短任务，谁就享受高优先级；谁表现得像长任务，谁就退居二线。它不需要预知，也不需要人工调参，是许多真实操作系统调度器的思想来源。
思考题
一个交互程序，每跑一小会儿就要等一次键盘输入；另一个是长时间计算的任务。它们在 MLFQ 里，大致会分别停在哪一级？为什么？
小结
知识点
- 多级反馈队列：多个优先级队列
- 新进程从高优先级开始，用满时间片则降级
- 通过“用 CPU 多少”间接推断任务长短
- 需要老化来防止长任务饥饿
参考资料
- Wikipedia(zh)：多级反馈队列：MLFQ
- Wikipedia(zh)：调度_(计算)：调度算法综述
思考题答案（仅供参考）
交互程序会在较高优先级。因为它经常等待输入，很少用满时间片，不会被降级；而每次等待结束、重新就绪时，又往往能排到靠前的位置。长时间计算任务则会逐渐沉到较低优先级，因为它总是用满时间片、被一次次降级。只有当高优先级没有别的任务、或老化机制把它提上来时，长任务才会重新获得较高优先级。这正是 MLFQ “按表现分配优先级”的体现。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪