Appearance
多级反馈队列调度
2026 大纲 二（二）4 CPU 调度算法的多级反馈队列调度（MLFQ），它是多级队列允许"队列间移动"之后的改进版。指标口径与算例数据沿用 调度的基本概念与目标。
交互可视化
可我事先并不知道这个进程是长是短
多级队列的分界很清楚：进程被永久分配到某条队列。 这就要求系统提前知道它是什么类型——交互的还是批处理的、长的还是短的。
可这个要求在真实系统里不成立。用户提交一个程序时，没人知道它要跑多久； SJF 也栽在同一件事上（它要预知服务时间）。
MLFQ 的解法很漂亮：不问，让它自己暴露。
具体做法是：新进程一律进最高优先级队列（先当短作业待遇）， 在本级时间片内没跑完就降一级。于是—— 真正的短作业在高优先级队列里就跑完了，享受了最好的响应； 长作业会被一级级降下去，最终落到低优先级队列里慢慢跑。
"长短"这件事不再需要预知，而是由"被降级几次"这个事后行为自动区分， 而且分错了能自动纠正（一个先算很久后来转为交互的进程，会随着不再耗尽时间片而重新升上去）。
还有一处设计值得留意：优先级从高到低，时间片却从小到大。 理由是——能降到第
⚠️ 但 MLFQ 仍然可能饥饿：只有高优先级队列全部为空才轮到低优先级队列。 补丁是老化（等太久就提回高优先级）——注意它是补丁，不是基本规则。
一、降级与被抢占：本篇最容易搞混的一步
当进程正在第
| 时间片用完 | 被抢占 | |
|---|---|---|
| 触发 | 该进程在本队列的时间片耗尽，仍未做完 | 更高优先级队列来了新进程 |
| 它证明了什么 | 这个进程确实比本级时间片长 | 什么也没证明——它可能只跑了一瞬 |
| 处理 | 降到下一级队列的队尾 | 回到原队列的队尾，级别不变 |
| 下次运行时的时间片 | 下一级的（更大） | 本级的，且是一个完整的新时间片 |
判据一句话：降级是"根据它已经跑掉多少"作出的判断，被抢占是"外部原因"，与它自身的长短无关，所以不能拿来当降级依据。
时间片为什么从小到大
这条能推，不用背：
一个进程能降到第
级，说明它已经在前 级各用完了一整个时间片却还没做完 ⇒ 它是长作业的证据在累积 ⇒ 长作业的特点是"需要很多 CPU、但对响应时间不敏感" ⇒ 给它更大的时间片，它一次能多做一些，总的切换次数减少 ⇒ 切换开销被摊薄。
反过来看最高级队列为什么时间片最小：那里挤满了刚到达的、还不知道长短的进程，给小时间片是为了让真正的短作业尽快做完就走，也让每个新进程都能很快得到第一次响应。若反过来从大到小，新到的短作业要么被大时间片里的长作业挡住，要么自己占着大时间片却用不完——两头都不讨好。
配合时间片轮转里的
二、老化：把"可能饥饿"补上
| 做法要素 | 内容 | 参数怎么定 |
|---|---|---|
| 触发条件 | 一个进程在某队列中等待时间超过阈值 | 也可实现为"每隔周期 |
| 提升幅度 | 提升一级，或直接提回最高级队列 | 提一级更平滑，直接提回最高级更强力 |
| 配套动作 | 提升后应重置它的等待计时；有的实现同时把所有进程一次性全部提回最高级队列（周期性重置） | 周期性重置实现最简单，但会周期性地丢失已积累的长短判断 |
这与优先级调度里的老化是同一个机制，只是那里改的是优先数、这里改的是队列号。
三、三个参数各自影响什么
| 参数 | 调大 | 调小 | 影响的核心指标 |
|---|---|---|---|
| 队列数 | 长短作业的分辨率更细；但一个长作业要经过更多次降级才沉到底，沉底速度慢 | 分辨率粗，长短作业容易被混在同一级； | 区分长短作业的精度 |
| 时间片倍率（下一级是上一级的几倍） | 低级队列切换开销摊得更薄；但低级队列里的进程一旦上 CPU 就占用很久，同级其他进程的响应变差 | 切换更频繁， | 低级队列的切换开销 vs 同级响应 |
| 老化阈值 | 防饥饿变弱，低级进程实际等待时间长 | 所有进程很快被提回高级队列，长短作业的区分被冲掉，退化为 RR | 防饥饿强度 vs 区分能力 |
四、MLFQ 好在哪里，以及与多级队列的分界
| 优点 | 说明 | 由哪条规则给出 |
|---|---|---|
| 无需预知服务时间 | 靠"降了几级"这个事后行为自动区分长短 | 规则 ③ |
| 无需提前分类 | 不像多级队列那样要先知道进程类型 | 规则 ② + ③ |
| 对短作业友好 | 短作业在高优先级队列（时间片小、优先级高）就能完成 | 规则 ① + ② |
| 响应时间极好 | 新进程一律进最高级队列，几乎立刻得到第一次服务 | 规则 ② |
| 对长作业仍公平 | 长作业虽降级，但最终会在低级队列得到执行；配合老化则等待有上界 | 规则 ⑤ + 老化 |
| ⚠️ 可能饥饿 | 高优先级队列持续有新进程时，低级长作业长期得不到调度 | 规则 ④；靠老化缓解 |
| 特性 | 多级队列 | 多级反馈队列 |
|---|---|---|
| 队列间移动 | 不允许 | 允许（降级 + 老化升级） |
| 预先分类 | 必须提前确定进程类型 | 不需要，自动分类 |
| 分类依据 | 进程的静态类型（系统/交互/批处理） | 进程的动态行为（跑了几个时间片） |
| 分类错了怎么办 | 无法纠正，一错到底 | 自动纠正（行为变了级别就会变） |
这张表其实只有第一行是独立的，后面三行都是它的推论。
逐步推演：每一步标出这是"降级"还是"被抢占"，以及与其他六种算法的横向对比（想在时间轴上看清进程怎么一级级沉下去时展开）
三级队列，Q1 的
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
| 时间 | 运行 | 在哪一级 | 本次跑了 | 结束原因 | 去向 | 各队列状态（运行后） |
|---|---|---|---|---|---|---|
| 0–1 | P1 | Q1 | 1 | 时间片用完 | 降到 Q2 | Q1:[] Q2:[P1] |
| 1–2 | P1 | Q2 | 1 | 被抢占（t=2 时 P2 进 Q1） | 回 Q2 队尾 | Q1:[P2] Q2:[P1] |
| 2–3 | P2 | Q1 | 1 | 时间片用完 | 降到 Q2 | Q1:[] Q2:[P1,P2] |
| 3–4 | P1 | Q2 | 1 | 被抢占（t=4 时 P3 进 Q1） | 回 Q2 队尾 | Q1:[P3] Q2:[P2,P1] |
| 4–5 | P3 | Q1 | 1 | 做完 | 完成 | Q1:[P4] Q2:[P2,P1] |
| 5–6 | P4 | Q1 | 1 | 时间片用完 | 降到 Q2 | Q1:[] Q2:[P2,P1,P4] |
| 6–8 | P2 | Q2 | 2 | 时间片用完 | 降到 Q3 | Q2:[P1,P4] Q3:[P2] |
| 8–10 | P1 | Q2 | 2 | 时间片用完 | 降到 Q3 | Q2:[P4] Q3:[P2,P1] |
| 10–12 | P4 | Q2 | 2 | 时间片用完 | 降到 Q3 | Q2:[] Q3:[P2,P1,P4] |
| 12–13 | P2 | Q3 | 1 | 做完 | 完成 | Q3:[P1,P4] |
| 13–15 | P1 | Q3 | 2 | 做完 | 完成 | Q3:[P4] |
| 15–16 | P4 | Q3 | 1 | 做完 | 完成 | 空 |
两处最值得停下来看的地方：
- t=1–2 与 t=3–4：P1 两次在 Q2 里只跑了 1 个单位就被抢占，两次都回到 Q2 而不是降到 Q3。它真正被降到 Q3 是在 t=8–10 那次——那次它用完了 Q2 完整的 2 个单位。
- P4 于 t=5 到达、t=5 就上了 CPU：因为新进程一律进最高优先级队列，而此刻 Q1 恰好只有它。
| 区间 | 0–2 | 2–3 | 3–4 | 4–5 | 5–6 | 6–8 | 8–10 | 10–12 | 12–13 | 13–15 | 15–16 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 进程 | P1 | P2 | P1 | P3 | P4 | P2 | P1 | P4 | P2 | P1 | P4 |
| 进程 | 完成时间 | 周转时间 | 带权周转时间 | 等待时间 | 响应时间 |
|---|---|---|---|---|---|
| P1 | 15 | 15 | 15/7 ≈ 2.14 | 8 | 0 |
| P2 | 13 | 11 | 11/4 = 2.75 | 7 | 0 |
| P3 | 5 | 1 | 1/1 = 1.00 | 0 | 0 |
| P4 | 16 | 11 | 11/4 = 2.75 | 7 | 0 |
| 平均 | 9.50 | 2.16 | 5.50 | 0.00 |
四个进程的响应时间全是 0，这不是巧合：新进程一律进最高优先级队列，而更高优先级队列里没有别人，所以它一到达就能上 CPU。
| 算法 | 平均周转 | 平均带权周转 | 平均响应 |
|---|---|---|---|
| FCFS | 8.75 | 3.50 | 4.75 |
| SJF（非抢占） | 8.00 | 2.56 | 4.00 |
| SRTF（抢占） | 7.00 | 1.51 | 0.50 |
| RR（ | 9.00 | 2.38 | 1.50 |
| 优先级（抢占） | 9.00 | 4.10 | 3.00 |
| MLFQ | 9.50 | 2.16 | 0.00 |
读法：MLFQ 的平均周转时间在这组数据里并不出众，但它的响应时间是全场最好的 0.00，而且它是唯一一个不需要预知服务时间、也不需要提前给进程分类就能做到这一点的算法。SRTF 的周转最优，但它要求预知服务时间——这个前提在真实系统里拿不到。
考点速记
- MLFQ 的核心规则：优先级从高到低、时间片从小到大；新进程一律进最高级队列；本级时间片内没跑完就降一级。
- ⚠️时间片从小到大是有理由的：能降到第
级，就说明它比前面各级都长；既然注定要跑久，就给更大的时间片摊薄切换开销。 - ⚠️被抢占与时间片用完必须分清：时间片用完 → 降一级；被更高优先级进程抢占 → 回原队列队尾、级别不变。
- ⚠️只有高优先级队列全部为空才调度低优先级队列，因此 MLFQ 仍可能饥饿；靠老化补上（
级、阈值 时等待上界 ）。老化是补丁不是基本规则。 - MLFQ 不需要预知服务时间、也不需要提前分类——长短由"被降级几次"这一事后行为自动区分，而且分类错了能自动纠正（先算很久后来转为交互的进程会重新升上去）。
- 三个参数（队列数、时间片倍率、老化阈值）调到极端都会塌回 RR。
这一节在真题里被考过的形式：
两道题，一道手算、一道问设计要素。
- 给二级反馈队列的参数与各进程的到达和执行时间，算等待时间或完成时刻（2019-27）。⚠️ 手算时最容易漏的两处："降级"发生在时间片用完的那一刻（不是跑完的时刻）、被抢占回到原队列队尾而不降级（速记第三条）。另外要看清题目给的各级时间片分别是多少——它们通常不等。
- 问设计多级反馈队列调度算法时要考虑哪些因素（2020-26，在调度的基本概念讲）。答四条全部：就绪队列的数量、各队列的优先级、各队列的调度算法、进程在队列间的迁移条件。⚠️最后一条正是它区别于多级队列的地方（多级队列不迁移，所以不需要定这一条）。
复习优先级：必须拿满，手算要练。 第三条（降级 vs 被抢占）是手算题唯一的技术难点； 第五条（不需要预知服务时间）是 MLFQ 相对 SJF 的最大卖点，也是概念题的落点。 第四条（仍可能饥饿、靠老化补）容易被误判成"MLFQ 不会饥饿"，要单独记。
易错：认为进程被抢占后也要降一级。只有时间片用完才降级；被抢占是回原队列队尾。
易错：认为 MLFQ 不会饥饿。会——高优先级队列一直不空，低优先级就一直排不上，靠老化补救。
易错：认为各级队列的时间片一样大。从小到大——越低级时间片越大，为的是摊薄切换开销。
易错：认为 MLFQ 需要提前知道进程是长是短。不需要——靠"被降级几次"事后自动区分。
易错：把老化当成 MLFQ 的基本规则。它是防饥饿的补丁，不是那五条核心规则之一。
教材出处
- 汤小丹《计算机操作系统》3.3.5 多级反馈队列调度算法（多个就绪队列、优先级最高的队列时间片最小且下一级是上一级的两倍、新进程放入第一队列末尾、时间片内未完成则转入下一队列末尾、仅当第 1～(i−1) 队列均空才调度第 i 队列、运行中若更高优先级队列来了新进程则把当前进程放回第 i 队列末尾），印刷 p95–p96
相关知识
调度的基本概念与目标｜多级队列调度｜公平调度算法｜优先级调度｜时间片轮转调度｜SJF 短作业优先调度