进程调度算法

只有一个 CPU，却有 N 个进程

如果你的电脑只有一个 CPU（单核），但开了浏览器、微信、IDE、终端……这些进程全都”同时”在跑。但物理上 CPU 同一时刻只能执行一个进程。

调度器（Scheduler） 就是操作系统中负责决定”下一个谁用 CPU”的模块。

🏫 类比：大学机房 机房有 1 台高性能电脑（CPU），但 20 个同学（进程）都想用。管理员（调度器）得决定：

• 每人用多久？（时间片）
• 让谁先用？（优先级）
• 怎么保证没人一直等？（公平性）

调度的三个层次

高级调度（作业调度）
  磁盘上的程序 → 创建进程 → 进入内存
        ↓
中级调度（内存调度）
  进程在内存和磁盘间交换（swap in/out）
        ↓
低级调度（CPU调度）
  从就绪队列选一个进程 → 分配CPU

我们主要讨论低级调度——这是最频繁、最影响系统响应速度的调度。

调度算法的评价指标

指标	含义	类比
CPU 利用率	CPU 忙的时间比例	电脑不空转
吞吐量	单位时间完成的进程数	食堂每小时打多少份饭
周转时间	进程从创建到结束的总时间	从排队到吃完饭
等待时间	进程在就绪队列中等待的总时间	排队时间
响应时间	从提交请求到首次响应	点菜后多久服务员回应

没有完美的调度算法——不同的场景需要不同的策略。

经典调度算法

1. 先来先服务（FCFS）

按到达顺序一个一个执行，直到完成才放行下一个。

进程  到达时间  执行时间
P1     0        6
P2     2        3
P3     4        1

FCFS 调度：
P1 ████████████████      ← 0-6
P2        ██████         ← 6-9
P3              ██       ← 9-10

优点：简单、公平（按排队顺序） 缺点：护航效应——一个长进程堵住后面所有短进程

🏫 食堂只有一个窗口，前面的人点了一桌满汉全席，后面只想买瓶矿泉水的人也得等着。

2. 短作业优先（SJF）

选择执行时间最短的进程先执行。

SJF 调度：
P3 ██                   ← 0-1（最短先执行）
P2 ██████               ← 1-4
P1 ████████████████     ← 4-10

平均等待时间：FCFS = (0+4+6)/3 = 3.3，SJF = (0+1+3)/3 = 1.3

优点：最短的平均等待时间（理论最优） 缺点：长作业可能被饿死——如果不断有短作业插入，长作业永远排不上

💡 实际系统中无法预知进程的执行时间，所以 SJF 是理论上的”理想状态”。

3. 最短剩余时间优先（SRTF）

SJF 的抢占式版本——新进程的执行时间比当前剩余时间短，就抢占 CPU。

P1 (0-6) 开始执行
在 t=2 时，P2 到达（执行时间 3），P1 剩余 4
  → P1 继续（因为 4 < 3 不成立？不对，当前剩余 4 > 新来的 3）
  → P2 抢占 P1
在 t=4 时，P3 到达（执行时间 1），P2 剩余 1
  → P3 抢占 P2

SRTF 调度：
P1 ████████               ← 0-2
P2                ██      ← 2-4? 不对...

实际上更复杂，但核心思想是：当前执行的进程随时可能被剩余时间更短的进程抢占。

4. 轮转调度（Round Robin, RR）

每个进程分配一个时间片（Time Quantum），轮流执行。时间片用完后，进程回到队列末尾。

时间片 = 2

P1 ████      ← 0-2
P2    ████   ← 2-4
P3       ██  ← 4-5（P3只需要1就完成了）
P1         ██████████████  ← 5-11（P1剩下的6）

优点：响应快——每个进程最多等 (n-1) × 时间片 缺点：时间片太短→频繁切换（开销大），太长→响应慢

💡 Linux 的 CFS（完全公平调度器）是轮转调度的进化版——它用虚拟运行时间实现”完美公平”，而不是固定的时间片。

5. 优先级调度

每个进程有优先级，高优先级先执行。

进程  优先级
P1     3（高）
P2     1（低）
P3     2（中）

静态优先级：创建时指定，不变 动态优先级：根据行为调整（I/O 密集型提升优先级）

⚠️ 优先级反转：一个低优先级进程占用了高优先级进程需要的资源，导致高优先级进程被低优先级”卡住”——火星探路者就出过这个问题！

6. 多级反馈队列（MLFQ）

最实用的调度算法——结合了以上多种思想：

┌──────────────────────────────────┐
│ 队列1（最高优先级，时间片 8ms）   │ → ──→ 用完时间片降级
├──────────────────────────────────┤
│ 队列2（时间片 16ms）              │ → ──→ 用完时间片降级
├──────────────────────────────────┤
│ 队列3（时间片 32ms）              │ → ──→ 用完时间片降级
├──────────────────────────────────┤
│ 队列4（时间片 64ms，最低优先级）   │ → ──→ 轮转
└──────────────────────────────────┘

规则：

1. 新进程进入最高优先级队列
2. 用完时间片没完成→降一级
3. 在 I/O 操作时主动让出 CPU→优先级不变或提升
4. 始终从最高优先级队列取进程

🏫 学校机房的不同用户

• 新生（短作业，交互型）→ 优先级高，小时间片（快速响应）
• 研究生（混合型）→ 中等优先级
• 跑大作业的（CPU 密集型）→ 优先级低，大时间片

MLFQ 的巧妙之处在于：它不需要预先知道进程的类型——交互型进程通常会因为等待 I/O 而主动让出 CPU（不会用完时间片），所以保持在最高优先级。

现代操作系统的调度策略

系统	调度算法	特点
Linux	CFS（完全公平调度器）	红黑树维护进程，按虚拟运行时间分配 CPU
Windows	基于优先级的抢占式调度	32 级优先级，I/O 密集型自动提权
macOS	混合调度（优先+轮转）	结合服务质量（QoS）级别
实时系统	RMS / EDF	保证截止时间（Deadline）

小结

算法	核心思想	优点	缺点
FCFS	先来先到	公平简单	护航效应
SJF	最短的先做	平均等待最短	长作业饿死
RR	轮流执行	响应均匀	时间片难调
优先级	重要的先做	灵活	可能反转/饿死
MLFQ	多级队列+反馈	自适应	参数复杂

为什么先学这个？ 调度算法是操作系统的核心决策机制——理解了调度，你才对”多任务”有了定量认识。接下来看看更轻量级的并发单元：线程（Thread）与多线程。