Appearance
多级反馈队列调度
考情分析
MLFQ 被认为是最好的调度算法，408 真题中偶有考查其调度规则。属于 🔥🔥 中高频考点。
前面所有算法各有长短板：FCFS 简单但慢，SJF 快但要预知时间，RR 公平但对短作业没有加速。MLFQ 的野心是把这些优点全融合在一起——不需要预知服务时间，短作业快速完成，长作业也不会饿死。
算法规则
多级反馈队列调度（Multi-Level Feedback Queue, MLFQ）是多级队列的改进——进程可以在队列间移动。
核心规则
- 设置多个就绪队列，优先级从高到低，时间片从小到大
- 新进程进入最高优先级队列
- 在当前队列的时间片内没执行完 → 降级到下一级队列
- 只有高优先级队列全部为空时，才调度低优先级队列
- 最低优先级队列通常使用 FCFS
抢占规则
当一个进程在低优先级队列中执行时，如果更高优先级队列有新进程到达，立即抢占当前进程，将其放回原队列尾部。
调度示例
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 5 | 1 |
队列设置：Q1(q=1), Q2(q=2), Q3(FCFS)
时间: 0 1 2 3 4 5 6 7 12 13
P1 P2 [P1 ][P2 ]P3 [P2][P1 ][P2]
Q1 Q1 Q2 Q2 Q1 Q2 Q3 Q3- t=0：P1进入Q1，执行1个时间片（t=0~1）→ 降到Q2。P1已用1，剩余7
- t=1：P2进入Q1（高优先级），执行1个时间片（t=1~2）→ 降到Q2。P2已用1，剩余3
- t=2：Q1为空，Q2中P1先到，执行2个时间片（t=2~4）→ 用完降到Q3。P1已用3，剩余5
- t=4：Q2中P2开始执行（q=2）
- t=5：P3到达Q1（高优先级），抢占P2，P2回到Q2尾部。P2本轮已用1个时间片，剩余Q2时间片1。P2已用2，剩余2
- t=5：P3在Q1执行1个时间片（t=5~6）→ P3完成
- t=6：Q2中P2继续执行剩余1个时间片（t=6~7）→ 用完降到Q3。P2已用3，剩余1
- t=7：Q3按FCFS，P1先到（剩余5），执行（t=7~12）→ P1完成
- t=12：Q3中P2（剩余1），执行（t=12~13）→ P2完成
交互可视化
为什么 MLFQ 是"最好的"
| 优点 | 说明 |
|---|---|
| 对短作业友好 | 短作业在高优先级队列就能完成 |
| 对长作业公平 | 长作业虽然降级，但最终会在低级队列得到执行 |
| 兼顾交互性 | 新到达的进程总是从高优先级开始，响应快 |
| 无需预知服务时间 | 通过动态降级自动区分长短作业 |
| ⚠️ 可能饥饿 | 若高优先级队列不断有新进程到达，低级队列中的长作业可能长期得不到调度。可通过**老化（Aging）**机制缓解——周期性将低级队列进程提升到高级队列 |
与多级队列的对比
| 特性 | 多级队列 | 多级反馈队列 |
|---|---|---|
| 队列间移动 | 不允许 | 允许（降级/升级） |
| 预先分类 | 需要提前确定进程类型 | 不需要，自动分类 |
| 饥饿 | 可能 | 可能（长作业在低级队列被新进程不断抢占） |
考研高频考点
- 🔥🔥🔥 MLFQ 的调度规则（进入最高级、时间片用完降级、高级非空抢占）
- 🔥🔥 MLFQ 不需要预知服务时间
- 🔥🔥 MLFQ 与多级队列的区别（能否在队列间移动）
- 🔥 时间片随队列级别递增
MLFQ 追求综合最优，但它并没有把"公平性"作为核心目标。下一篇看公平调度算法如何保证每个进程或每个用户获得合理的 CPU 份额。