多级反馈队列（MLFQ）

多级反馈队列根据进程近期行为调整优先级。本课新任务进入最高队列，用完时间片且仍有 CPU 工作时降一级；因 I/O 阻塞后再就绪则回到最高队列。调度器不用预知 burst 长度，就能给短任务与交互任务更多响应机会。

可把它看成多条服务队列：新来者先试快速窗口，处理太久就去时间片更长的队列；离开取资料后回来，再进快速窗口。每十二个时刻，等待在低层的人统一升回顶部，避免旧判断长期生效。本课与同一负载的普通 Round Robin 比较。

MLFQ 如何工作

默认三层：Q0 片长 2，Q1 片长 4，Q2 片长 8。始终选择最高非空队列的队首。

1. 新到达者进入 Q0。
2. 用满片长且当前 CPU burst 仍有工作，降一级；最低层保持最低层。
3. burst 结束转入 I/O 时不因耗时片边界而降级；I/O 完成后，本模型一律返回 Q0。
4. 更高优先级任务就绪，会抢占正在低层运行者，把它放回原队列尾部。
5. 每 12 tick 做一次优先级提升，把 Q1、Q2 中就绪等待任务移到 Q0。正在运行的任务不提升，但可能马上被提升后的高层任务抢占。

Round Robin 基线只有一个 FIFO 队列，固定片长 3。新任务入尾，队首运行，用完片且仍有 CPU 工作则回尾。单队列基线让反馈机制的影响可见。

同 tick 事件先处理到达，再处理 I/O 完成，再做提升，之后才应用抢占或回队。因此同刻新到达者排在时间片耗尽的任务前面。

逐步演示

固定负载：P1 在 t=0 到达，CPU 5、I/O 4、CPU 3；P2 在 t=1 到达，CPU 4；P3 在 t=2 到达，CPU 2、I/O 3、CPU 4；P4 在 t=4 到达，CPU 3。

默认 MLFQ（片长 2/4/8，每 12 提升）：

1. P1 运行 0–2，用完 Q0 片长，降到 Q1。t=2 到达的 P3 先进入 Q0。P2 运行 2–4，随后降级。
2. P3 运行 4–6，恰好完成首个 CPU burst，进入 I/O 至 9，不降级。P4 运行 6–8，仍剩工作，降级。
3. Q0 为空，P1 从 Q1 运行 8–9。t=9，P3 完成 I/O 回 Q0，抢占 P1，后者回 Q1 尾。
4. P3 运行 9–11，用满 Q0 时间片且仍有工作，降到 Q1。P2 从 Q1 运行 11–12。
5. t=12 提升时，Q1 中等待的 P4、P1、P3 按队列顺序进 Q0。运行中的 P2 不提升，被高层就绪任务抢占，回 Q1。
6. P4 运行 12–13 完成，周转 9。P1 运行 13–15，burst 和时间片同时结束，进入 I/O 至 19，不降级。P3 运行 15–17 完成，周转 15。
7. P2 从 Q1 运行 17–18 完成，周转 17。18–19 没有就绪任务，CPU 空闲。
8. P1 在 19 完成 I/O，进 Q0，运行 19–21 后降级，再从 Q1 运行 21–22 完成，周转 22。

Round Robin，片长 3：

1. P1 运行 0–3，期间 P2、P3 到达。P1 回尾后，队列为 P2、P3、P1。
2. P2 运行 3–6，P4 在 4 到达；P2 余一 tick，回尾。
3. P3 运行 6–8 完成首段，I/O 至 11。P1 运行 8–10 完成首个五 tick burst，I/O 至 14。
4. P4 运行 10–13 完成；P3 在 11 完成 I/O 入队。P2 运行 13–14 完成，P1 的 I/O 同刻结束。
5. P3 运行 14–17，余一 tick 回尾。P1 运行 17–20 完成，P3 运行 20–21 完成。全程无空闲，结束时刻 21。

轮转的周转时间按 P1–P4 为 20、13、19、9，首次响应为 0、2、4、6。MLFQ 首次响应为 0、1、2、2，但 P1 周转变成 22，整体也晚一 tick 结束。

进程颜色从到达保持到完成。当前事件卡片有高亮环，时间片计量条随本片已用 tick 增长；降级下移一层，t=12 提升同时移动三张卡。甘特图播放时显示近期窗口，结束时展示全程和指标表。

为什么不必预知 CPU burst

所有任务同时可用、长度已知时，短到长顺序能最小化平均周转；交错到达不直接满足这一定理，实际内核还需要估计未来工作量。MLFQ 用近期 CPU 占用替代预知：耗尽时间片且仍有工作则下移，因 I/O 让出后返回上层。

本例更短的 Q0 片长让新任务早些获得 CPU，首次响应从轮转的 0、2、4、6 变为 0、1、2、2。代价是不同的排队、抢占与 I/O 时序，P1 晚两 tick 完成。P1 在这条轨迹中实际降级两次，其他中断或 burst 完成不能都算降级。

持续的高层任务可能让低层任务饥饿，因此周期提升把等待者重新带回竞争。它限制旧优先级判断的持续时间，不是对任意无界负载给出固定完成时间保证。

边界情况

• burst 与片长同时结束，先处理 burst 完成。P1 在 t=15 进入 I/O，不降级。P4 在 13 则在片长用完前结束，也不回队。
• 到达与耗尽同刻，新到达者先入队：MLFQ 的 t=2 先接 P3，轮转的 t=3 队列为 P2、P3、P1。
• 提升不包括运行者。t=12 的 P2 留在 Q1，被抢占后要到 17 才恢复运行。
• 空闲是调度结果。18–19 只有 P1 做 I/O，甘特图画 IDLE，时钟前进到下一事件。

常见错误

• 把甘特图当成策略。它是规则作用后的输出，要看每次为何选择该任务。
• 认为 I/O 会导致降级。本模型用完时间片且仍有 CPU 工作才降级，阻塞结束后返回 Q0。
• 期望所有指标都胜过轮转。本例响应更快，但 P1 周转更长、总完成更晚。
• 忘记高层抢占。P1 在 Q1 只跑 8–9 一 tick，就被 I/O 返回的 P3 抢占。
• 把层级当进程永久属性。它只是近期行为的判断，提升会重置等待者的旧判断。

模型范围

单 CPU、整数 tick、固定 burst、I/O 返回 Q0、切换免费。省略中断延迟、锁、亲和性、nice 与生产公平性计账。真实 MLFQ 变体还可按累计配额等规则调节，不能把本课每项政策视为所有 MLFQ 的统一定义。