099 多级反馈队列：最实用的调度算法

前面我们学了几种调度算法：FCFS 简单但低效，SJF 理论最优但无法预知运行时间，RR 公平但平均等待时间一般，优先级调度实用但可能饿死低优先级进程。

有没有一种算法，能综合这些算法的优点，规避它们的缺点？

有。它叫多级反馈队列（Multilevel Feedback Queue, MFQ）——现代操作系统中最常用的调度算法。

核心思想

设置多个就绪队列，每个队列有不同的优先级和时间片：

• 高优先级队列：时间片小，响应快
• 低优先级队列：时间片大，适合长任务

关键特征：进程可以在队列之间移动（这就是"反馈"的含义）。

具体架构

队列 0（最高优先级）：时间片 = 8
队列 1：时间片 = 16
队列 2：时间片 = 32
队列 3（最低优先级）：时间片 = 64

调度规则

规则 1：新进程进入最高优先级队列

每个新创建的进程都从队列 0 开始——给它一个快速响应的机会。

规则 2：时间片用完降到下一级

如果一个进程在当前队列的时间片内没有完成，它就被降级到下一级队列。

比喻：新员工第一天在 VIP 窗口服务，如果业务处理时间太长（超过了这个窗口的时间片），就被移到普通窗口。

规则 3：I/O 阻塞后回到高优先级

如果一个进程在时间片内因为等待 I/O 而阻塞，当 I/O 完成后，它会被放回较高优先级队列。

比喻：如果某个顾客只是来问个问题（I/O 密集型，很快完成），他就一直在 VIP 窗口服务，不用排队。

规则 4：高优先级队列为空才服务低优先级

调度器总是优先服务高优先级队列。只有当所有高优先级队列都为空时，才服务低优先级队列。

执行示例

假设两个队列：队列 0 时间片=4，队列 1 时间片=8。

进程	运行时间
P1	10
P2	3
P3	6

执行过程：

时间 0-3: P2 在队列0 运行（完成！3 < 4）
时间 3-7: P1 在队列0 运行（时间片用完，降到队列1）
时间 7-11: P3 在队列0 运行（时间片用完，降到队列1）
时间 11-17: P1 在队列1 运行（时间片8，运行6，完成）
时间 17-19: P3 在队列1 运行（运行2，完成）

P2 是短任务，在最高优先级队列就完成了。
P1 和 P3 较长，被降级到低优先级队列。

为什么 MFQ 是最实用的

1. 短任务得到快速响应

短任务在第一级（高优先级、小时间片）就能完成，响应时间很好——类似 RR 对小任务的优势。

2. 长任务不会饿死

虽然长任务会被降级，但低优先级队列最终也会被服务（尤其是当高优先级队列为空时）。加上老化机制（长期等待的进程可以提升优先级），保证不会饿死。

3. I/O 密集型任务得到优待

频繁做 I/O 的进程（如交互式应用）每次 I/O 后都回到高优先级，能很快得到响应——用户感受到的延迟很小。

4. 自适应调整

MFQ 不需要预知进程的运行时间（SJF 的缺点），它通过实际运行行为自动将进程分到合适的队列：

• 经常短时间完成的 → 自动留在高优先级
• 需要长时间运行的 → 自动降到低优先级

5. 综合了多种算法的优点

特点	来自哪种算法
短任务快速响应	SJF、RR
公平性	RR
优先级区分	优先级调度
自适应调整	无（MFQ 独有）

实际系统中的应用

现代操作系统的调度器都是 MFQ 的变体：

Linux CFS（Completely Fair Scheduler）：

• 用红黑树管理进程
• 跟踪每个进程的"虚拟运行时间"
• 总是调度虚拟运行时间最小的进程
• 本质上是动态优先级 + 公平调度的结合

Windows 调度器：

• 有 32 个优先级（0-31）
• 0-15 是可变的（动态调整）
• 16-31 是实时的
• 根据进程行为动态调整优先级

软考考点

• **多级反馈队列（MFQ）**的基本规则
• 队列之间的降级和升级机制
• MFQ 如何综合多种算法的优点
• I/O 密集型和 CPU 密集型进程的调度差异
• 实际操作系统中的调度策略

小结

多级反馈队列是现代操作系统最常用的调度算法。它通过多个优先级队列和动态升降级机制，实现了对短任务的快速响应、对长任务的公平对待、对 I/O 任务的优待。它不需要预知进程的运行时间，而是通过实际行为自适应调整——这是它相比 SJF 的最大优势。可以说，你电脑上每一次流畅的操作，背后都是 MFQ 在默默工作。

---

💬 你觉得 MFQ 像不像公司里的"能者多劳"？干得快的人被安排更重要的任务！评论区聊聊！觉得有用点个赞吧～