处理机调度算法深度对比与多级反馈队列详解

引言

处理机调度是操作系统进程管理的核心决策机制：当多个就绪进程同时等待 CPU 时，操作系统必须回答"下一个该运行谁"这个看似简单却充满权衡的问题。六种经典调度算法在公平性、响应速度和资源利用率之间各自做出了不同的取舍，而多级反馈队列（MLFQ）则将这些取舍统一在一个框架下，成为现代操作系统的实际选择。

📌 核心要点

• 调度算法的评价是多维度的：平均周转时间衡量"快不快"，响应时间衡量"跟不跟手"，CPU 利用率衡量"省不省"——没有哪个算法在所有维度上同时最优
• FCFS 公平但长作业会阻塞短作业；SJF 平均等待时间最短但可能造成饥饿；RR 响应快但切换开销大；MLFQ 综合了三者长处，是 Linux、Windows 等现代 OS 的实际调度基础
• 多级反馈队列的核心洞察：用"队列等级"和"时间片递进"同时兼顾交互型进程的响应需求与批处理型进程的吞吐量需求，且不需要事先估计运行时间
• 抢占与非抢占是理解所有调度算法的前置概念：前者允许高优先级进程剥夺低优先级进程的 CPU，后者只允许进程主动放弃

---

1. 调度基础：三级调度体系与评价指标

在进入具体算法之前，需要建立两个基础认知：调度发生在什么层次、以及用什么尺度评价调度的好坏。

1.1 三级调度：从作业到进程的完整链路

操作系统中的调度并非只发生在 CPU 选择进程的那一刻。一个作业从提交到最终执行，经过三个层次的调度：

调度层次	别称	调度对象	主要功能	频率
高级调度	作业调度	外存中的作业	将后备队列中的作业调入内存，创建进程	最低（几分钟/次）
中级调度	内存调度	挂起/阻塞的进程	将暂时不能运行的进程挂起到外存（挂起），待条件满足再换入内存	中等
低级调度	进程调度	就绪队列中的进程	按照某种算法将 CPU 分配给就绪进程	最高（毫秒级）

[UNIQUE INSIGHT] 很多教材强调"高级调度频率最低、低级调度频率最高"，但更值得追问的是：为什么中级调度是必要的？答案在于内存是一种稀缺资源。当系统中进程数量过多、内存不足时，中级调度通过"挂起-换入"机制，在保证多道程序度的同时避免了频繁的作业级调入调出，这种设计使系统在高负载下仍能维持响应能力。

[IMAGE] 三级调度层次关系示意图：高级调度（外存→内存）→ 中级调度（挂起↔换入）→ 低级调度（CPU 分配），三个层次从低频到高频构成完整的调度链路。

1.2 当调度发生：进程调度的时机与禁区

进程调度并非随时随地都能触发。操作系统内核在一些关键环节上是"不可中断"的：

• 可以进行调度的情况：当前进程主动放弃 CPU（如等待 I/O）、进程时间片用完、更高优先级的进程到达（抢占式调度）
• 不能进行调度的情况：处理中断的过程中、进程处于操作系统内核程序的临界区内、正在执行原子操作

一个常见的混淆点是将"内核临界区"与"进程临界区"混为一谈。进程访问临界资源时的临界区是可以被调度的（否则会破坏并发性），但内核程序在处理关键数据结构（如就绪队列）时的临界区不能被中断——这属于内核自身的同步保护需求。

1.3 评价指标：五个维度衡量调度质量

任何一个调度算法都可以从以下五个维度进行量化评价：

指标	定义	含义
CPU 利用率	CPU 工作时间 / 总时间	越高越好，反映 CPU 的忙碌程度
系统吞吐量	单位时间内完成的作业数	越高越好，反映系统的处理能力
周转时间	作业完成时间 - 作业到达时间	越短越好，反映"等了多久做完"
带权周转时间	周转时间 / 实际运行时间	不低于 1，越接近 1 越好，反映等待相对于实际运行的比例
等待时间	周转时间 - 实际运行时间	越短越好，反映在就绪队列中的等待时长
响应时间	首次获得 CPU 的时间 - 到达时间	越短越好，反映交互式系统的"跟手程度"

其中，周转时间和响应时间是两类场景各自最关注的指标。批处理系统追求平均周转时间最小化，交互式系统则追求响应时间最小化——这两个目标在某些情况下直接冲突，这也正是不同调度算法需要权衡的核心矛盾。

---

2. 非抢占式算法：FCFS、SJF 与 HRRN

2.1 FCFS（先来先服务）：最公平也最粗暴

FCFS（First Come First Served）是所有调度算法中最直观的一种：谁先到达就绪队列，谁先用 CPU，用完才轮到下一个。这就像银行的排队叫号：先来的先办业务，后来的只能等。

优势：实现极其简单，天然公平（按到达顺序），不存在饥饿问题——因为每个进程迟早都会排到队首。

致命缺陷：长作业阻塞效应。如果排在前面的长作业需要运行很久，后面的短作业即便只需要 1ms 也要等上数秒。这种现象常被称为"护航效应"（Convoy Effect）：一个 CPU 密集型长进程会拖慢所有 I/O 密集型短进程。

完整例题：假设有四个进程，括号内分别为（到达时间，服务时间）。

进程	到达时间	服务时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

FCFS 调度过程：

时间线: |--P1--|--P1--|--P1--|--P1--|--P1--|--P1--|--P1--|--P2--|--P2--|--P2--|--P2--|--P3--|--P4--|--P4--|--P4--|--P4--|
        0      1      2      3      4      5      6      7      8      9      10     11     12     13     14     15     16

计算结果：

进程	到达	服务	完成	周转时间	带权周转时间
P1	0	7	7	7	7/7 = 1.00
P2	2	4	11	9	9/4 = 2.25
P3	4	1	12	8	8/1 = 8.00
P4	5	4	16	11	11/4 = 2.75

• 平均周转时间：(7 + 9 + 8 + 11) / 4 = 8.75
• 平均带权周转时间：(1.00 + 2.25 + 8.00 + 2.75) / 4 = 3.50

注意 P3：只需要运行 1 个单位时间，却等了 8 个单位时间才完成，带权周转时间高达 8.0。如果这个"短进程"恰好是用户等待的交互操作，体验会相当糟糕。

考点速记：FCFS 对所有进程在"先来后到"意义上是公平的，但会导致短作业被长作业阻塞（护航效应）。FCFS 属于非抢占式调度，进程一旦获得 CPU 就不会被剥夺。

2.2 SJF/SPF（短作业/短进程优先）：平均等待时间的最优解

SJF（Shortest Job First，短作业优先）和 SPF（Shortest Process First，短进程优先）的核心思想是：每次调度时，从就绪队列中选择预计运行时间最短的进程分配 CPU。SJF 是非抢占式的（一旦开始运行就跑完），这与它的抢占式变体 SRTN（最短剩余时间优先）不同。

为什么 SJF 能获得最小的平均等待时间？ 可以通过一个排队论思想来理解：将运行时间短的进程优先执行，能使后续所有进程的等待时间都减少一个"短进程的运行时间"，从而最小化总的等待时间总和。这是可证明的最优策略——前提是能够准确预知每个进程的运行时间。

SJF 例题（使用与 FCFS 相同数据）：

调度过程：

t=0: 只有 P1 到达，P1 运行 [0, 7]
t=7: P2(4), P3(1), P4(4) 均已到达，选最短的 P3 运行 [7, 8]
t=8: P2(4), P4(4) 均已到达，两者服务时间相同，任选 P2 运行 [8, 12]
t=12: P4 运行 [12, 16]

进程	到达	服务	完成	周转时间	带权周转时间
P1	0	7	7	7	7/7 = 1.00
P2	2	4	12	10	10/4 = 2.50
P3	4	1	8	4	4/1 = 4.00
P4	5	4	16	11	11/4 = 2.75

• 平均周转时间：(7 + 10 + 4 + 11) / 4 = 8.00（优于 FCFS 的 8.75）
• 平均带权周转时间：(1.00 + 2.50 + 4.00 + 2.75) / 4 = 2.56（显著优于 FCFS 的 3.50）

P3 的带权周转时间从 FCFS 的 8.00 降到了 4.00，改善明显。但如果不断有新的短进程到达，长进程可能一直得不到服务——这就是 饥饿（Starvation） 问题。

考点速记：SJF/SPF 能获得最小的平均等待时间和平均周转时间，但需要预知进程的运行时间（实际系统中很难做到），且长作业可能发生饥饿。属于非抢占式调度。

2.3 HRRN（高响应比优先）：FCFS 和 SJF 的折中方案

HRRN（Highest Response Ratio Next，高响应比优先）是一个设计精巧的折中算法，它通过"响应比"这个指标同时考量等待时间和服务时间：

$$\text{响应比}=\frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}=1+\frac{\text{等待时间}}{\text{要求服务时间}}$$

响应比的公式揭示了一层关键洞察：等待时间越长，分子越大，响应比越高——长进程不会永远饥饿。同时，服务时间越短，分母越小，响应比越高——短进程仍有优势。这使得 HRRN 在保证短作业优先的同时，长作业的优先级会随着等待时间的增加而逐步"老化"提升。

HRRN 例题（使用相同数据）：

t=0: 只有 P1，运行 [0, 7]
t=7: P2 等 5, P3 等 3, P4 等 2
     R(P2) = (5+4)/4 = 2.25
     R(P3) = (3+1)/1 = 4.00  ← 最大
     R(P4) = (2+4)/4 = 1.50
     → 选 P3 运行 [7, 8]

t=8: P2 等 6, P4 等 3
     R(P2) = (6+4)/4 = 2.50  ← 最大
     R(P4) = (3+4)/4 = 1.75
     → 选 P2 运行 [8, 12]

t=12: P4 运行 [12, 16]

进程	到达	服务	完成	周转时间	带权周转时间
P1	0	7	7	7	1.00
P2	2	4	12	10	2.50
P3	4	1	8	4	4.00
P4	5	4	16	11	2.75

• 平均周转时间：8.00，平均带权周转时间：2.56

在这个特定数据集中，HRRN 的结果与 SJF 一致。但在有持续新进程到达的场景中，HRRN 会表现出与 SJF 的显著差异——长进程的响应比逐渐提升，最终获得调度。

[UNIQUE INSIGHT] 响应比公式中"1 + 等待时间/要求服务时间"的形式揭示了 HRRN 的数学本质：当等待时间趋近于 0 时，响应比趋近于 1，所有进程"机会均等"；当等待时间趋于无穷时，响应比也趋于无穷，长进程必然被选中。这个公式本质上是一个自动的"动态优先级"系统——不需要人工调参，等待时间天然充当了优先级调整的杠杆。

---

3. 抢占式算法：RR 与优先级调度

3.1 RR（时间片轮转）：分时系统的基石

RR（Round Robin，时间片轮转）将所有就绪进程排成一个循环队列，每个进程每次运行一个固定的时间片（Time Quantum），时间片耗尽后让出 CPU 给下一个进程。

时间片大小是 RR 调度最关键的设计参数。时间片太大，RR 退化为 FCFS——交互响应变差。时间片太小，进程切换太频繁——上下文切换开销吞掉 CPU 时间。一个经验原则是：时间片应当使切换开销不超过 CPU 总时间的 1%。

RR 例题（q=2，使用相同数据）：

进程	到达时间	服务时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

时间片 q=2 详细调度过程：

时间段	运行进程	剩余时间	事件
0 - 2	P1	P1=5	P2 在 t=2 到达
2 - 4	P2	P2=2	P3 在 t=4 到达
4 - 6	P1	P1=3	P4 在 t=5 到达
6 - 7	P3	P3=0	P3 在 t=7 完成
7 - 9	P2	P2=0	P2 在 t=9 完成
9 - 11	P4	P4=2	—
11 - 13	P1	P1=1	—
13 - 15	P4	P4=0	P4 在 t=15 完成
15 - 16	P1	P1=0	P1 在 t=16 完成

进程	完成时间	周转时间	带权周转时间
P1	16	16	16/7 ≈ 2.29
P2	9	7	7/4 = 1.75
P3	7	3	3/1 = 3.00
P4	15	10	10/4 = 2.50

• 平均周转时间：(16 + 7 + 3 + 10) / 4 = 9.00
• 平均带权周转时间：(2.29 + 1.75 + 3.00 + 2.50) / 4 ≈ 2.38

时间片 q=5 对比：

时间段	运行进程	事件
0 - 5	P1 (余 2)	P2、P3、P4 均已到达
5 - 9	P2 (完成)	t=9 完成
9 - 10	P3 (完成)	t=10 完成
10 - 14	P4 (完成)	t=14 完成
14 - 16	P1 (完成)	t=16 完成

进程	完成	周转	带权周转
P1	16	16	2.29
P2	9	7	1.75
P3	10	6	6.00
P4	14	9	2.25

• 平均周转时间：(16 + 7 + 6 + 9) / 4 = 9.50，平均带权周转时间 ≈ 3.07

q=5 的平均周转时间比 q=2 更差，且 P3（最短进程）在 q=5 时带权周转时间恶化到 6.00。但 q=2 时上下文切换了 9 次（包括完成），而 q=5 只切换了 4 次——切换开销更低。

考点速记：RR 算法公平、响应好，是分时系统的标准选择。时间片太大退化为 FCFS，太小导致切换开销过大。RR 的周转时间通常不如 SJF，但响应时间显著更好。

3.2 优先级调度：最灵活但需防饥饿

优先级调度为每个进程分配一个优先级，每次调度选择就绪队列中优先级最高的进程。它可以是抢占式（新到高优先级进程立刻得到 CPU），也可以是非抢占式（等待当前进程运行完）。

优先级的设计原则（在实践中被广泛遵循）：

• 系统进程的优先级高于用户进程
• 前台进程（交互型）高于后台进程（批处理型）
• I/O 密集型进程高于 CPU 密集型进程（因为 I/O 进程占 CPU 时间短，优先处理可以提高 I/O 设备的利用率）

抢占式优先级调度例题（进程格式：到达时间，服务时间，优先级——数值越小优先级越高）：

进程	到达时间	服务时间	优先级
P1	0	7	1
P2	2	4	2
P3	4	1	3
P4	5	4	2

调度过程：

t=0: P1 到达，投入运行
t=2: P2 到达，优先级 2 高于 P1 的优先级 1
     P2 抢占 P1。P1 剩余 5，P2 运行
t=4: P3 到达，优先级 3 高于 P2 的优先级 2
     P3 抢占 P2。P2 剩余 2，P3 运行
t=5: P3 完成，P4 到达（优先级 2）
     当前就绪：P1(优先级 1, 剩余 5), P2(优先级 2, 剩余 2), P4(优先级 2)
     优先级最高者 P1 运行
t=10: P1 完成
     就绪：P2(优先级 2, 剩余 2), P4(优先级 2)
     同优先级，可任选 P2 运行
t=12: P2 完成，P4 运行
t=16: P4 完成

进程	完成时间	周转时间	带权周转时间
P1	10	10	10/7 ≈ 1.43
P2	12	10	10/4 = 2.50
P3	5	1	1/1 = 1.00
P4	16	11	11/4 = 2.75

• 平均周转时间：(10 + 10 + 1 + 11) / 4 = 8.00
• 平均带权周转时间：(1.43 + 2.50 + 1.00 + 2.75) / 4 ≈ 1.92

饥饿问题与解决方案：如果不断有高优先级的新进程到达，低优先级进程可能永远得不到 CPU。解决方案是"老化"（Aging）——随着进程等待时间的增加，逐步提升它的优先级，确保每个进程最终都能被调度。

---

4. 多级反馈队列（MLFQ）：现代操作系统的实际答案

4.1 为什么需要 MLFQ？

前述五种算法各自存在明显的短板：

• FCFS 对短进程不友好，响应时间差
• SJF 需要预知运行时间（实际系统做不到），且可能饥饿
• RR 对长进程不友好，周转时间长
• 优先级调度需要手动配置优先级，且可能饥饿
• HRRN 每次调度都要计算响应比，开销较大

多级反馈队列（Multilevel Feedback Queue, MLFQ）的设计目标是：在不预先知道进程运行时间的前提下，同时满足交互型进程的响应需求和批处理型进程的吞吐量需求。它由 Corbato 等人在 1962 年提出，是最早被实际部署在兼容分时系统（CTSS）中的高级调度算法——半个多世纪后，其核心思想仍然是 Linux CFS、Windows NT 调度器等现代实现的基础。

4.2 MLFQ 的五条规则

MLFQ 的核心结构是多个优先级从高到低排列的就绪队列，每个队列的时间片大小随优先级降低而递增：

[CHART] 多级反馈队列架构示意图：5 个优先级队列从 Q1（最高优先级，时间片 1 单位）到 Q5（最低优先级，时间片 8 单位），进程在队列之间动态迁移。

MLFQ 遵循以下五条规则：

1. 多级队列，优先级递减，时间片递增：设有 n 级就绪队列 Q1, Q2, …, Qn。Q1 优先级最高，时间片最短；Qn 优先级最低，时间片最长。相邻队列之间时间片通常以 2 的幂次递增（如 1, 2, 4, 8, …）。

2. 新进程入最高级队列：任何新创建的进程首先进入 Q1 的队尾，获得最短的时间片和最高的优先级。

3. 高优先级优先调度：只有当 Qk 为空时，才会调度 Q(k+1) 中的进程。这意味着任何位于高优先级队列的进程都会抢占低优先级队列中正在运行的进程。

4. 时间片耗尽则降级：如果进程在 Qk 中用完了分配的时间片仍未完成，它将被降级到 Q(k+1) 的队尾——时间片加倍，优先级减半。

5. 时间片内主动放弃则不动：如果进程在时间片用完之前主动释放 CPU（如发起 I/O 操作），它保留在当前队列。这条规则使得 I/O 密集型进程能持续获得高优先级的快速响应。

4.3 MLFQ 为什么"聪明"：动态类型识别

MLFQ 的核心洞察在于：调度器不需要被告知一个进程是"短进程"还是"长进程"——它通过进程的行为模式自动推断。

• 交互型（I/O 密集型）进程：频繁释放 CPU 等待 I/O，在时间片内主动放弃，因此始终停留在高优先级队列，获得快速响应。这相当于 MLFQ 自动给了它们类似 RR 的响应待遇。

• 批处理型（CPU 密集型）进程：每次都把时间片用满，因此不断被降级到低优先级队列。但在低优先级队列中，它们获得更长的时间片——每次运行更久、切换更少，从而获得了类似 FCFS 的高吞吐量效果。而且低优先级队列仅在无高优先级就绪进程时才被调度，所以长进程不会饿死，只是执行频率低。

[PERSONAL EXPERIENCE] 我在用 C 语言实现 mini-OS 教学内核时发现，MLFQ 最微妙的设计不是规则本身，而是规则 4 和规则 5 之间的博弈：时间片内释放 CPU 则保留等级，用尽则降级。这意味着调度器不需要维护"进程类型"的状态字段——进程自己的行为就是它的身份标识。这种"行为即身份"的设计哲学在操作系统的很多模块中反复出现（如页置换的 LRU 近似），值得反复体会。

4.4 MLFQ 综合了哪些算法的优点？

算法	被 MLFQ 继承的特性	MLFQ 中的体现
FCFS	低优先级队列用长时​​间片运行，切换少	Qn 中进程按到达顺序执行，近似 FCFS
SJF/SPF	短进程天然获得快速完成	短进程在 Q1/Q2 就完成了，不会被降级
RR	高优先级队列时间片短，响应快	Q1 中小时间片轮转，交互友好
优先级调度	高优先级的 I/O 进程优先响应	I/O 型进程在时间片内主动让出，保持高优先级

4.5 MLFQ 的实际参数示例

一个典型的 MLFQ 配置（参考早期 BSD 调度器设计）：

队列	优先级	时间片	目标进程类型
Q1	最高	8ms	交互终端、鼠标/键盘事件
Q2	高	16ms	网络 I/O、磁盘 I/O
Q3	中	32ms	编译任务、中等计算
Q4	低	64ms	批处理计算、后台任务

每个队列内部采用 RR 调度。当 Q1 有进程就绪时，Q2-Q4 中的进程立即让出 CPU——这就是抢占在 MLFQ 中的具体运作方式。

[UNIQUE INSIGHT] 现有教材在讲解 MLFQ 时，大多聚焦于"规则"的描述，但很少追问：时间片以 2 的幂次递增这条设计有没有理论依据？事实上它可以从"调度开销均摊"的角度来解释：如果一个进程在高优先级队列用了 k 个单位的时间片后被降级到低优先级队列并获得 2k 的时间片，那么它每单位时间内的上下文切换次数减半。这种指数递减的切换频率使得长进程的总切换开销被控制在常数级——无论进程有多长，切换次数不会随运行时间线性增长。

---

5. 六大算法全景对比

[CHART] 六种调度算法在各评价维度上的表现对比柱状图（平均周转时间、平均带权周转时间、响应时间、实现复杂度）。

算法	类型	核心原则	优点	缺点	适用场景
FCFS	非抢占	先到先运行	实现简单，绝对公平	长作业阻塞短作业	早期批处理系统
SJF/SPF	非抢占	估计运行时间最短优先	平均等待时间最小	需预知运行时间，长作业饥饿	批处理系统（如作业调度）
HRRN	非抢占	响应比 = 1 + 等待/服务	综合 FCFS 和 SJF 优点，不饥饿	每次调度需计算响应比	批处理系统
RR	抢占	固定时间片轮流	公平，响应时间好	切换开销大，周转时间长	分时系统
优先级	均可	优先级高者得 CPU	灵活，可适应不同需求	低优先级可能饥饿	实时系统、通用系统
MLFQ	抢占	多级队列 + 动态升降级	综合各算法优势，无需预知运行时间	参数调优复杂	现代通用操作系统

---

6. 多处理机调度简介

当系统拥有多个 CPU 核心时，调度问题增加了一个维度：进程应该被分配到哪个 CPU 上运行？

处理器亲和性（Processor Affinity）：一个进程在某个 CPU 上运行一段时间后，该 CPU 的缓存中会积累大量与该进程相关的数据（指令、数据页、TLB 条目）。如果将该进程迁移到另一个 CPU，这些缓存全部失效，性能会明显下降。因此现代调度器倾向于保持"软亲和性"——尽量不迁移进程，除非负载均衡需要。

负载均衡（Load Balancing）：确保各个 CPU 之间任务量大致均衡。有两种实现方式：推迁移（Push Migration）——一个专门的线程定期检查各 CPU 的负载，将任务从过载 CPU 推送到空闲 CPU；拉迁移（Pull Migration）——空闲 CPU 主动从其他 CPU 的就绪队列中拉取进程。Linux 的 CFS 调度器结合了这两种策略。

考研提示：408 统考中多处理机调度通常作为选择题或简答题的辅助考点出现，重点掌握亲和性与负载均衡这两个概念的含义及它们之间的矛盾关系。

---

7. 常见误区与总结

⚠️ 常见坑

1. 混淆"进程临界区"与"内核临界区"：进程在访问临界资源时可以被调度，但内核在操作关键数据结构（如就绪队列）的临界区内不能调度。这在"进程调度的时机"考点中经常以选择题形式出现。

2. 误认为 SJF 的"最短"是指最短剩余时间：SJF 是非抢占式的，选择的是估计运行时间最短的就绪进程，一旦开始就不中断。抢占式版本叫 SRTN（最短剩余时间优先），两者是不同的算法。

3. HRRN 响应比的计算时机：响应比是每次调度决策时动态计算的，不是一个预分配的值。很多同学忘记在每次调度时重新计算等待时间，导致结果错误。

4. MLFQ 的"抢占"细节：当更高优先级队列中出现新进程时，它会抢占当前低优先级队列中正在运行的进程。但同一队列内部是 RR 调度，不抢占同队列内进程。

📌 总结

处理机调度算法的演进史，本质上是一个不断在"公平性"和"效率"之间寻找更优折中的过程。FCFS 追求公平但牺牲了效率；SJF 追求效率但牺牲了公平；MLFQ 则通过"行为自动识别 + 动态队列迁移"的机制，让调度器在不依赖先验信息的前提下，自适应地为不同类型的进程提供合适的调度策略。掌握了这六种算法的设计思路和计算方式，不仅能够应对考研中的调度计算题，更重要的是理解一个操作系统设计中的贯穿性智慧：好的系统设计不是选择立场，而是让对立的诉求在同一个框架下各自找到合适的位置。

---

8. FAQ

Q1: FCFS 和 SJF 哪个的平均周转时间更短？

在绝大多数非平凡场景下，SJF 的平均周转时间更短——这是可以证明的最优结果。但 SJF 要求预知进程的运行时间，而实际系统中几乎不可能准确预知。FCFS 不需要预知运行时间，但其性能严重受进程到达顺序影响。

Q2: 时间片轮转中，时间片大小如何选择？

时间片的经验原则是使上下文切换开销不超过 CPU 总时间的 1%。假设每次切换耗时 0.1ms，则时间片至少应设为 10ms。实际系统中时间片通常在 1ms 到 100ms 之间，兼顾响应时间和切换效率。

Q3: MLFQ 的缺点是什么？

MLFQ 的主要缺点是参数调优复杂。队列数量、各队列时间片大小、降级策略都需要针对具体工作负载进行调整，没有一套"万能参数"。此外，如果 I/O 密集型进程过于频繁地释放 CPU，可能导致 CPU 密集型进程"饿死"在低优先级队列。

Q4: HRRN 和 MLFQ 的核心区别是什么？

HRRN 在单一就绪队列中用响应比公式同时考量等待时间与运行时间。MLFQ 则用多级就绪队列和进程的动态迁移实现相似的目标。HRRN 每次调度需要计算所有就绪进程的响应比，时间复杂度为 O(n)；MLFQ 每级队列内按 FCFS 或 RR 调度，时间复杂度更低。

Q5: 408 考研中调度算法通常以什么形式考查？

通常以选择题考查算法特性辨析（如"以下哪种算法不会导致饥饿"），以综合应用题考查给定进程集合的具体计算（要求画出甘特图、计算各进程的周转时间和带权周转时间、比较不同算法的效果）。近年真题中 MLFQ 的考查频率明显上升。

---

📚 延伸阅读

• INTERNAL-LINK: 本系列第一篇文章 进程基础：进程状态、PCB 与上下文切换
• INTERNAL-LINK: 本系列后续文章 进程同步与互斥：信号量、管程与经典同步问题
• INTERNAL-LINK: 本系列后续文章 死锁：必要条件、预防避免与银行家算法

---