03 - CPU 调度算法¶
⏰ 建议学习时间：2.5 小时 🎯 难度等级：⭐⭐⭐ 📋 前置知识：进程概念、进程状态转换
📋 本章目录¶
一、调度的基本概念¶
1.1 为什么需要 CPU 调度？¶
在多道程序设计系统中，就绪队列中有多个进程等待 CPU。CPU 一次只能运行一个进程（单核），因此需要调度器（Scheduler）决定：下一个获得 CPU 使用权的是哪个进程？
1.2 调度的三个层次¶
Text Only
┌──────────────────────────────────────────┐
│ 高级调度（作业调度 / Long-term） │
│ 决定哪些作业从磁盘调入内存（创建进程） │
│ 控制多道程序的"道数" │
│ 执行频率：低（秒/分钟级） │
├──────────────────────────────────────────┤
│ 中级调度（内存调度 / Medium-term） │
│ 决定哪些进程换入/换出内存（挂起/激活） │
│ 调节内存负载 │
│ 执行频率：中 │
├──────────────────────────────────────────┤
│ 低级调度（CPU调度 / Short-term） │ ★ 本章重点
│ 决定就绪队列中哪个进程获得 CPU │
│ 执行频率：极高（毫秒级，每次时钟中断） │
└──────────────────────────────────────────┘
1.3 调度时机¶
CPU 调度器在以下时机做出决策：
- 进程从运行态变为阻塞态（如发起 I/O 请求）→ 必须调度
- 进程从运行态变为就绪态（如时间片用完、被抢占）→ 可以调度
- 进程从阻塞态变为就绪态（如 I/O 完成）→ 可能抢占当前进程
- 进程终止 → 必须调度
非抢占式调度：仅在情况 1、4 时调度（进程主动放弃 CPU） 抢占式调度：在所有情况下都可能调度（OS 可以强制剥夺 CPU）
二、调度评价指标¶
2.1 四个核心指标¶
| 指标 | 定义 | 公式 | 优化目标 |
|---|---|---|---|
| CPU 利用率 | CPU 忙碌时间占总时间的比例 | CPU忙碌时间 / 总时间 | 越高越好 |
| 吞吐量 | 单位时间内完成的进程数 | 完成进程数 / 总时间 | 越大越好 |
| 周转时间 | 进程从提交到完成的全部时间 | 完成时间 - 到达时间 | 越小越好 |
| 等待时间 | 进程在就绪队列中等待的总时间 | 周转时间 - 实际运行时间 | 越小越好 |
还有一个重要指标： - 响应时间：从提交请求到第一次响应（不是完成）的时间，交互式系统中尤为重要
2.2 衍生指标¶
Text Only
带权周转时间 = 周转时间 / 实际运行时间
（衡量"相对等待程度"，值越接近 1 越好）
平均周转时间 = Σ(各进程周转时间) / 进程数
平均等待时间 = Σ(各进程等待时间) / 进程数
平均带权周转时间 = Σ(各进程带权周转时间) / 进程数
三、七大调度算法¶
3.1 FCFS — 先来先服务¶
核心思想：按照进程到达就绪队列的先后顺序依次调度，先到先服务。
类型：非抢占式
数据结构：FIFO 队列
示例计算：
Text Only
进程 到达时间 服务时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4
FCFS Gantt 图：
时间轴: 0 2 4 5 7 11 12 16
| | | | | | | |
[ P1 ] [ P2 ] [P3][ P4 ]
0 7 11 12 16
计算结果：
P1: 周转时间 = 7-0 = 7, 等待时间 = 0
P2: 周转时间 = 11-2 = 9, 等待时间 = 9-4 = 5
P3: 周转时间 = 12-4 = 8, 等待时间 = 8-1 = 7
P4: 周转时间 = 16-5 = 11,等待时间 = 11-4 = 7
平均周转时间 = (7+9+8+11)/4 = 8.75
平均等待时间 = (0+5+7+7)/4 = 4.75
优点：简单、公平 缺点：护航效应（Convoy Effect）——一个长进程排在前面，所有短进程都要等待很久
3.2 SJF — 最短作业优先¶
核心思想：从就绪队列中选择预计运行时间最短的进程优先执行。
类型：非抢占式
示例计算（使用同样的进程数据）：
Text Only
进程 到达时间 服务时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF Gantt 图：
时间 0: 只有 P1 到达 → 执行 P1
时间 7: P2(4), P3(1), P4(4) 都已到达 → 选最短的 P3(1)
时间 8: P2(4), P4(4) → 选 P2（先到达）
时间 12: P4
时间 16: 完成
[ P1 ] [P3][ P2 ][ P4 ]
0 7 8 12 16
P1: 周转 = 7-0 = 7, 等待 = 0
P3: 周转 = 8-4 = 4, 等待 = 4-1 = 3
P2: 周转 = 12-2 = 10,等待 = 10-4 = 6
P4: 周转 = 16-5 = 11,等待 = 11-4 = 7
平均周转时间 = (7+10+4+11)/4 = 8.0（比FCFS的8.75好）
平均等待时间 = (0+6+3+7)/4 = 4.0（比FCFS的4.75好）
优点：平均等待时间最优（在非抢占式算法中） 缺点： - 长进程可能饥饿（永远等不到执行） - 难以准确预估运行时间
3.3 SRTF — 最短剩余时间优先¶
核心思想：SJF 的抢占式版本。每当有新进程到达，比较新进程和当前运行进程的剩余时间，选择更短的执行。
类型：抢占式
示例计算：
Text Only
进程 到达时间 服务时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SRTF 逐步分析：
时间 0: P1 到达，P1运行 (剩余7)
时间 2: P2 到达(4) vs P1(剩余5) → P2更短，抢占！ P2运行
时间 4: P3 到达(1) vs P2(剩余2) → P3更短，抢占！ P3运行
时间 5: P3结束，P4到达(4) vs P2(剩余2) vs P1(剩余5) → P2最短
时间 7: P2结束，P4(4) vs P1(5) → P4运行
时间 11: P4结束，P1运行
时间 16: P1结束
[P1 ][P2 ][P3][P2][ P4 ][ P1 ]
0 2 4 5 7 11 16
P1: 周转 = 16-0 = 16, 等待 = 16-7 = 9
P2: 周转 = 7-2 = 5, 等待 = 5-4 = 1
P3: 周转 = 5-4 = 1, 等待 = 1-1 = 0
P4: 周转 = 11-5 = 6, 等待 = 6-4 = 2
平均周转时间 = (16+5+1+6)/4 = 7.0（最优！）
平均等待时间 = (9+1+0+2)/4 = 3.0（最优！）
优点：在所有调度算法中，SRTF 的平均等待时间最优 缺点：与 SJF 相同——饥饿、难以预估运行时间，且频繁抢占增加切换开销
3.4 优先级调度（Priority Scheduling）¶
核心思想：每个进程有一个优先级，调度器总是选择优先级最高的进程执行。
类型：可以是抢占式或非抢占式
优先级分类： - 静态优先级：创建时确定，不再改变 - 动态优先级：根据进程行为和等待时间动态调整
问题：优先级反转（Priority Inversion）
Text Only
经典案例（火星探路者号故障）：
高优先级 T_high ─────────────── 等待(锁被T_low持有) ──────
中优先级 T_mid ──────── 抢占T_low ─── 运行中 ─────────
低优先级 T_low ── 获取锁 ─── 被T_mid抢占 ─── 等待 ────
结果：T_high 被 T_mid 间接阻塞！ （T_high等锁 ← T_low持锁但被T_mid抢占）
解决方案：
1. 优先级继承协议：T_low 临时继承 T_high 的高优先级
2. 优先级天花板协议：进入临界区时，提升到资源的最高优先级
3.5 RR — 时间片轮转¶
核心思想：为每个进程分配一个固定的时间片（Time Quantum），进程在时间片用完后被放到就绪队列末尾，轮流执行。
类型：抢占式
示例计算（时间片 q = 2）：
Text Only
进程 到达时间 服务时间
P1 0 7
P2 2 4
P3 4 1
P4 5 4
RR(q=2) 逐步分析：
时间 0-2: P1运行2个单位 (剩余5) 就绪队列: []→[P2,P1]
时间 2-4: P2运行2个单位 (剩余2) 就绪队列: [P1]→[P1,P3,P2]
时间 4-6: P1运行2个单位 (剩余3) 就绪队列: [P3,P2]→[P3,P2,P4,P1]
时间 6-7: P3运行1个单位 (完成) 就绪队列: [P2,P4,P1]
时间 7-9: P2运行2个单位 (完成) 就绪队列: [P4,P1]
时间 9-11: P4运行2个单位 (剩余2) 就绪队列: [P1]→[P1,P4]
时间 11-13: P1运行2个单位 (剩余1) 就绪队列: [P4]→[P4,P1]
时间 13-15: P4运行2个单位 (完成) 就绪队列: [P1]
时间 15-16: P1运行1个单位 (完成)
Gantt 图：
[P1][P2][P1][P3][P2][P4][P1][P4][P1]
0 2 4 6 7 9 11 13 15 16
P1: 周转 = 16-0 = 16, 等待 = 16-7 = 9
P2: 周转 = 9-2 = 7, 等待 = 7-4 = 3
P3: 周转 = 7-4 = 3, 等待 = 3-1 = 2
P4: 周转 = 15-5 = 10, 等待 = 10-4 = 6
平均周转时间 = (16+7+3+10)/4 = 9.0
平均等待时间 = (9+3+2+6)/4 = 5.0
时间片大小的影响：
Text Only
时间片太大（q → ∞）：退化为 FCFS
时间片太小（q → 0）：切换过于频繁，大量时间浪费在上下文切换上
经验法则：时间片应大于 80% 的 CPU 突发时间
典型值：Linux 默认大约 4ms（CFS 中根据进程数动态调整）
3.6 多级队列调度（Multilevel Queue）¶
核心思想：将就绪队列分成多个队列，每个队列有自己的调度策略，队列之间有优先级关系。
Text Only
┌─────────────────────────┐ 最高优先级
│ 系统进程队列（Priority） │ ← 操作系统核心进程
├─────────────────────────┤
│ 交互进程队列（RR） │ ← 用户交互程序（编辑器、浏览器）
├─────────────────────────┤
│ 批处理进程队列（FCFS） │ ← 后台计算任务
├─────────────────────────┤
│ 空闲进程队列（FCFS） │ ← 低优先级后台任务
└─────────────────────────┘ 最低优先级
调度规则：
1. 高优先级队列非空时，低优先级队列不能运行（或分配较少时间比例）
2. 进程创建时被永久分配到某个队列（不能在队列间移动）
缺点：进程不能在队列间移动，缺乏灵活性，低优先级进程可能饥饿。
3.7 多级反馈队列调度（MLFQ — Multilevel Feedback Queue）¶
核心思想：在多级队列的基础上，允许进程在队列之间移动。根据进程的行为动态调整其所在队列。
Text Only
Queue 0 (最高优先级, RR q=8ms)
┌─────────────────────────┐ ← 新進程进入这里
│ 时间片=8ms │
│ 用完时间片→降到Queue 1 │
├─────────────────────────┤
Queue 1 (中优先级, RR q=16ms)
│ 时间片=16ms │
│ 用完时间片→降到Queue 2 │
├─────────────────────────┤
Queue 2 (最低优先级, FCFS)
│ FCFS 调度 │
│ 长期等待→可能升到Queue 0 │ ← 防止饥饿
└─────────────────────────┘
调度规则：
1. 新进程进入最高优先级队列（Queue 0）
2. 如果在当前队列的时间片内完成 → 离开
3. 如果时间片用完还没完成 → 降到下一级队列
4. 只有当高优先级队列为空时，才调度低优先级队列的进程
5. 定期将所有进程提升到最高优先级队列（防止饥饿，称为 Priority Boost）
MLFQ 的设计智慧：
- 短进程：在高优先级队列就完成了 → 响应时间短
- I/O 密集型进程：经常主动让出 CPU → 停留在高优先级队列
- CPU 密集型进程：不断用完时间片 → 逐渐降到低优先级队列
- 防止饥饿：定期 Priority Boost → 所有进程重新开始
🎯 面试要点：MLFQ 被认为是目前最好的通用调度算法之一，它兼顾了响应时间（对短进程/交互式进程友好）和吞吐量（对长进程公平），而且不需要预先知道进程的运行时间。
七大算法对比总结¶
| 算法 | 类型 | 是否抢占 | 优点 | 缺点 |
|---|---|---|---|---|
| FCFS | 非抢占 | ❌ | 简单公平 | 护航效应 |
| SJF | 非抢占 | ❌ | 平均等待最优 | 饥饿、需预知运行时间 |
| SRTF | 抢占 | ✅ | 所有算法中平均等待最优 | 饥饿、开销大 |
| Priority | 可选 | 可选 | 重要任务优先 | 饥饿、优先级反转 |
| RR | 抢占 | ✅ | 公平、响应好 | 时间片选择敏感 |
| MLQ | 可选 | 可选 | 分类管理 | 不灵活、可能饥饿 |
| MLFQ | 抢占 | ✅ | 兼顾响应和吞吐 | 设计参数多 |
四、实时调度¶
4.1 EDF — 最早截止时间优先¶
核心思想：总是选择截止时间（Deadline）最早的任务执行。
类型：抢占式
调度能力：只要 CPU 利用率 ≤ 100%，EDF 就能保证所有任务在截止时间前完成（理论最优）。
Text Only
可调度性条件：
U = Σ(Ci/Ti) ≤ 1
其中：Ci = 任务 i 的执行时间，Ti = 任务 i 的周期
示例：
任务 T1: C1=1, T1=4 (每 4 个时间单位执行 1 个单位)
任务 T2: C2=2, T2=6 (每 6 个时间单位执行 2 个单位)
U = 1/4 + 2/6 = 0.25 + 0.33 = 0.58 ≤ 1 → 可调度
4.2 RM — 速率单调调度¶
核心思想：周期越短的任务优先级越高（固定优先级）。
类型：抢占式、静态优先级
调度能力：
Text Only
RM 可调度的充分条件（Liu & Layland 界限）：
U = Σ(Ci/Ti) ≤ n(2^(1/n) - 1)
n=1: U ≤ 1.0
n=2: U ≤ 0.828
n=3: U ≤ 0.780
n→∞: U ≤ ln2 ≈ 0.693
注意：这是充分条件，不满足不一定不可调度
4.3 EDF vs RM 对比¶
| 特性 | EDF | RM |
|---|---|---|
| 优先级 | 动态（每次调度都可能变化） | 静态（创建时确定） |
| 最大利用率 | 100% | 约 69.3%（n→∞） |
| 实现复杂度 | 较高（需要动态排序） | 低（优先级固定） |
| 实际应用 | 理论研究较多 | 工业界更常用 |
五、Linux CFS 调度器¶
5.1 CFS 概述¶
CFS（Completely Fair Scheduler，完全公平调度器）是 Linux 2.6.23（2007年）引入的默认进程调度器，由 Ingo Molnár 开发。
核心理念：让所有进程公平地共享 CPU 时间。理想情况下，如果有 N 个进程，每个进程应该获得 1/N 的 CPU 时间。
5.2 vruntime（虚拟运行时间）¶
CFS 的核心数据结构是 vruntime（virtual runtime），用于跟踪每个进程"实际获得的 CPU 时间"：
Text Only
vruntime 的更新：
vruntime += 实际运行时间 × (NICE_0_WEIGHT / 进程权重)
其中：
- NICE_0_WEIGHT = 1024（nice=0 的进程的权重）
- 进程权重由 nice 值决定
关键性质：
- nice 值高（低优先级）→ 权重小 → vruntime 增长快 → 更少机会运行
- nice 值低（高优先级）→ 权重大 → vruntime 增长慢 → 更多机会运行
- CFS 总是选择 vruntime 最小的进程运行
5.3 nice 值与权重映射¶
Text Only
nice 值范围：-20（最高优先级）到 +19（最低优先级）
默认 nice 值：0
nice 值到权重的映射（部分）：
nice 权重(weight) 相对nice=0的比例
-20 88761 约 86.7 倍
-10 9548 约 9.3 倍
-5 3121 约 3.0 倍
0 1024 1.0 倍（基准）
5 335 约 0.33 倍
10 110 约 0.11 倍
19 15 约 0.015 倍
设计原则：每差 1 个 nice 值，CPU 时间相差约 10%
（相邻 nice 值的权重比约为 1.25:1）
5.4 红黑树组织¶
CFS 使用红黑树（Red-Black Tree）组织所有就绪进程，以 vruntime 为键值：
Text Only
红黑树示例：
┌───────┐
│P3(50) │ ← 根节点
│ (黑) │
└───┬───┘
┌──────┴──────┐
┌────┴────┐ ┌────┴────┐
│ P1(30) │ │ P5(70) │
│ (红) │ │ (红) │
└────┬────┘ └────┬────┘
┌───┴───┐ ┌───┴───┐
┌────┴──┐ ┌──┴───┐ ┌──┴───┐
│P4(20) │ │P2(40)│ │P6(80)│
│ (黑) │ │ (黑) │ │ (黑) │
└───────┘ └──────┘ └──────┘
最左节点 = P4(vruntime=20) → 下一个被调度的进程
操作复杂度：
- 查找最小 vruntime：O(1)（缓存最左节点）
- 插入新进程：O(log n)
- 删除进程：O(log n)
5.5 CFS 调度过程¶
Text Only
CFS 调度器的工作流程：
1. [选择进程]
从红黑树中取出最左节点（vruntime 最小的进程）
→ 时间复杂度 O(1)（维护了 rb_leftmost 指针）
2. [分配时间片]
计算该进程的理想运行时间：
time_slice = sched_period × (进程权重 / 所有就绪进程权重之和)
其中 sched_period（调度周期）：
if (进程数 ≤ sched_nr_latency=8):
sched_period = sysctl_sched_latency = 6ms
else:
sched_period = 进程数 × sysctl_sched_min_granularity (0.75ms)
3. [运行进程]
将 CPU 分配给选中的进程
4. [更新 vruntime]
进程运行后，更新其 vruntime：
vruntime += 实际运行时间 × 1024 / 进程权重
5. [重新插入红黑树]
将进程按新的 vruntime 插入红黑树
→ 时间复杂度 O(log n)
6. [重复]
回到步骤 1
5.6 CFS 示例¶
Text Only
假设有 3 个进程，nice 值和权重如下：
P1: nice=0, weight=1024
P2: nice=0, weight=1024
P3: nice=5, weight=335
总权重 = 1024 + 1024 + 335 = 2383
调度周期 = 6ms（3 个进程 ≤ 8）
各进程的时间片：
P1: 6ms × 1024/2383 ≈ 2.58ms
P2: 6ms × 1024/2383 ≈ 2.58ms
P3: 6ms × 335/2383 ≈ 0.84ms
vruntime 增长速度：
P1: 每运行 1ms → vruntime += 1 × 1024/1024 = 1
P2: 每运行 1ms → vruntime += 1 × 1024/1024 = 1
P3: 每运行 1ms → vruntime += 1 × 1024/335 ≈ 3.06
→ P3 的 vruntime 增长最快，所以获得的 CPU 时间最少
→ P1 和 P2 平分约 86% 的 CPU 时间，P3 获得约 14%
→ 体现了"完全公平"的设计理念
六、Python 模拟代码¶
6.1 调度算法模拟器¶
Python
"""
CPU 调度算法模拟器
支持 FCFS、SJF、SRTF、RR、Priority 算法
"""
from dataclasses import dataclass, field
from typing import List, Optional
from collections import deque
import copy
@dataclass # 自动生成__init__等方法
class Process:
"""进程数据结构"""
pid: str
arrival_time: int
burst_time: int
priority: int = 0 # 数值越小优先级越高
remaining_time: int = -1
start_time: int = -1
finish_time: int = -1
def __post_init__(self):
if self.remaining_time == -1:
self.remaining_time = self.burst_time
@property # @property将方法变为属性访问
def turnaround_time(self) -> int:
return self.finish_time - self.arrival_time
@property
def waiting_time(self) -> int:
return self.turnaround_time - self.burst_time
@property
def response_time(self) -> int:
return self.start_time - self.arrival_time
def print_results(processes: List[Process], algorithm: str):
"""打印调度结果"""
print(f"\n{'='*60}")
print(f" 调度算法: {algorithm}")
print(f"{'='*60}")
print(f"{'进程':>6} {'到达':>6} {'服务':>6} {'开始':>6} {'完成':>6} "
f"{'周转':>6} {'等待':>6} {'响应':>6}")
print("-" * 60)
total_turnaround = 0
total_waiting = 0
for p in sorted(processes, key=lambda x: x.pid): # lambda匿名函数：简洁的单行函数
print(f"{p.pid:>6} {p.arrival_time:>6} {p.burst_time:>6} "
f"{p.start_time:>6} {p.finish_time:>6} "
f"{p.turnaround_time:>6} {p.waiting_time:>6} "
f"{p.response_time:>6}")
total_turnaround += p.turnaround_time
total_waiting += p.waiting_time
n = len(processes)
print("-" * 60)
print(f"平均周转时间: {total_turnaround/n:.2f}")
print(f"平均等待时间: {total_waiting/n:.2f}")
def fcfs(processes: List[Process]) -> List[Process]:
"""先来先服务调度"""
procs = copy.deepcopy(processes)
procs.sort(key=lambda p: p.arrival_time)
current_time = 0
for p in procs:
if current_time < p.arrival_time:
current_time = p.arrival_time
p.start_time = current_time
p.finish_time = current_time + p.burst_time
current_time = p.finish_time
return procs
def sjf(processes: List[Process]) -> List[Process]:
"""最短作业优先（非抢占）"""
procs = copy.deepcopy(processes)
completed = []
current_time = 0
while len(completed) < len(procs):
# 找到已到达且未完成的进程中服务时间最短的
available = [p for p in procs
if p.arrival_time <= current_time and p not in completed]
if not available:
current_time += 1
continue
shortest = min(available, key=lambda p: p.burst_time)
shortest.start_time = current_time
shortest.finish_time = current_time + shortest.burst_time
current_time = shortest.finish_time
completed.append(shortest)
return procs
def srtf(processes: List[Process]) -> List[Process]:
"""最短剩余时间优先（抢占式 SJF）"""
procs = copy.deepcopy(processes)
current_time = 0
completed = 0
n = len(procs)
while completed < n:
# 找到已到达且未完成的进程中剩余时间最短的
available = [p for p in procs
if p.arrival_time <= current_time and p.remaining_time > 0]
if not available:
current_time += 1
continue
shortest = min(available, key=lambda p: p.remaining_time)
if shortest.start_time == -1:
shortest.start_time = current_time
shortest.remaining_time -= 1
current_time += 1
if shortest.remaining_time == 0:
shortest.finish_time = current_time
completed += 1
return procs
def round_robin(processes: List[Process], quantum: int) -> List[Process]:
"""时间片轮转调度"""
procs = copy.deepcopy(processes)
procs.sort(key=lambda p: p.arrival_time)
queue = deque()
current_time = 0
idx = 0 # 下一个到达的进程索引
completed = 0
n = len(procs)
# 添加初始到达的进程
while idx < n and procs[idx].arrival_time <= current_time:
queue.append(procs[idx])
idx += 1
while completed < n:
if not queue:
if idx < n:
current_time = procs[idx].arrival_time
while idx < n and procs[idx].arrival_time <= current_time:
queue.append(procs[idx])
idx += 1
continue
p = queue.popleft()
if p.start_time == -1:
p.start_time = current_time
run_time = min(quantum, p.remaining_time)
p.remaining_time -= run_time
current_time += run_time
# 添加在此期间到达的进程
while idx < n and procs[idx].arrival_time <= current_time:
queue.append(procs[idx])
idx += 1
if p.remaining_time == 0:
p.finish_time = current_time
completed += 1
else:
queue.append(p) # 放回队列末尾
return procs
# ========== 测试 ==========
if __name__ == "__main__":
# 测试数据
test_processes = [
Process("P1", arrival_time=0, burst_time=7),
Process("P2", arrival_time=2, burst_time=4),
Process("P3", arrival_time=4, burst_time=1),
Process("P4", arrival_time=5, burst_time=4),
]
# 运行各算法
print_results(fcfs(test_processes), "FCFS（先来先服务）")
print_results(sjf(test_processes), "SJF（最短作业优先）")
print_results(srtf(test_processes), "SRTF（最短剩余时间优先）")
print_results(round_robin(test_processes, quantum=2), "RR（时间片轮转, q=2）")
七、练习题与计算例题¶
计算例题 1：综合对比¶
Text Only
给定以下进程信息：
进程 到达时间 服务时间
P1 0 5
P2 1 3
P3 2 8
P4 3 6
请分别用 FCFS、SJF（非抢占）、SRTF（抢占）、RR(q=4) 计算各进程的
完成时间、周转时间、等待时间，以及平均周转时间和平均等待时间。
FCFS 解答：
Text Only
Gantt: [ P1 ][ P2 ][ P3 ][ P4 ]
0 5 8 16 22
P1: 完成=5, 周转=5-0=5, 等待=0
P2: 完成=8, 周转=8-1=7, 等待=7-3=4
P3: 完成=16, 周转=16-2=14,等待=14-8=6
P4: 完成=22, 周转=22-3=19,等待=19-6=13
平均周转 = (5+7+14+19)/4 = 11.25
平均等待 = (0+4+6+13)/4 = 5.75
SJF（非抢占）解答：
Text Only
时间0: 只有P1 → 执行P1
时间5: P2(3),P3(8),P4(6) → 选P2(最短3)
时间8: P3(8),P4(6) → 选P4(最短6)
时间14: P3
时间22: 完成
Gantt: [ P1 ][ P2 ][ P4 ][ P3 ]
0 5 8 14 22
P1: 周转=5, 等待=0
P2: 周转=7, 等待=4
P4: 周转=11, 等待=5
P3: 周转=20, 等待=12
平均周转 = (5+7+20+11)/4 = 10.75
平均等待 = (0+4+12+5)/4 = 5.25
选择题¶
1. 在以下算法中，最可能导致"饥饿"问题的是： - A. FCFS - B. RR - C. SJF - D. MLFQ
答案：C。SJF 中，如果不断有短进程到达，长进程可能永远得不到执行。FCFS 和 RR 天然公平。MLFQ 有 Priority Boost 防止饥饿。
2. Linux CFS 调度器使用红黑树的主要原因是： - A. 红黑树查找最小值是 O(1) - B. 红黑树插入删除是 O(log n)，查找最小值可以通过缓存实现 O(1) - C. 红黑树比其他数据结构占用更少的内存 - D. 红黑树实现最简单
答案：B。CFS 需要频繁地取出最小 vruntime 的进程（O(1)缓存指针），以及插入/删除进程（O(log n)），红黑树完美满足这些需求。
八、面试要点¶
🔥 高频面试题¶
Q1：比较 FCFS、SJF、RR 三种调度算法的优缺点¶
| FCFS | SJF | RR | |
|---|---|---|---|
| 优点 | 简单公平 | 平均等待最优 | 公平、响应好 |
| 缺点 | 护航效应 | 饥饿、需预知 | 时间片敏感 |
| 适用 | 简单系统 | 批处理 | 分时交互 |
Q2：解释 Linux CFS 调度器的工作原理¶
回答要点： 1. CFS 追求完全公平，让每个进程获得它应得的 CPU 份额 2. 核心机制是 vruntime：每个进程维护一个虚拟运行时间 3. vruntime 增长速度与 nice 值权重成反比——高优先级进程 vruntime 增长慢 4. CFS 使用红黑树组织就绪进程，总是选择 vruntime 最小的进程运行 5. 时间片不是固定的，而是根据进程权重动态计算
Q3：什么是多级反馈队列？为什么说它是最好的通用调度算法？¶
回答要点： MLFQ 维护多个优先级队列，新进程进入最高优先级。用完时间片未完成则降级。这样：短进程和 I/O 密集进程留在高优先级——响应快；CPU 密集进程逐渐降级——不影响交互体验。定期 Boost 防止饥饿。它不需要预知运行时间，兼顾响应和吞吐。
Q4：什么是优先级反转？如何解决？¶
回答要点：低优先级进程持有锁，高优先级进程等锁，中优先级进程抢占低优先级进程——导致高优先级被中优先级间接阻塞。解决方案：优先级继承（临时提升持锁进程的优先级）、优先级天花板协议。火星探路者号就遇到过此问题。
📌 下一章：04-内存管理 — 分页/分段/虚拟内存/页面置换算法