进程调度算法详解

进程调度是操作系统的核心功能之一，它决定了 CPU 资源如何在多个进程之间分配，直接影响系统的性能和响应速度。

一、进程调度的基本概念

1.1 什么是进程调度

进程调度是操作系统内核的调度程序（Scheduler）决定哪个进程获得 CPU 使用权的过程。

就绪队列                CPU
┌─────────────────┐    ┌─────┐
│ P1 │ P2 │ P3 │ ... ──→│ CPU │
└─────────────────┘    └─────┘
     ↑ 调度程序选择

1.2 调度的层次

层次	说明	频率
长程调度	选择哪些进程进入就绪队列	低
中程调度	内存与外存之间的进程交换	中
短程调度	选择哪个进程获得 CPU	高

1.3 调度的时机

进程调度可能发生在：

• 进程从运行态 → 等待态（I/O 请求）
• 进程从运行态 → 就绪态（时间片用完）
• 进程从等待态 → 就绪态（I/O 完成）
• 进程终止

1.4 调度方式

方式	说明
非抢占式	进程主动放弃 CPU
抢占式	操作系统强制剥夺 CPU

现代操作系统

现代操作系统几乎都采用抢占式调度，以保证公平性和响应性。

二、调度算法的评价指标

2.1 CPU 利用率

$$CPU\mathrm{利}\mathrm{用}\mathrm{率}=\frac{CPU\mathrm{忙}\mathrm{碌}\mathrm{时}\mathrm{间}}{\mathrm{总}\mathrm{时}\mathrm{间}}\times 100\mathrm{\%}$$

2.2 吞吐量

$$\mathrm{吞}\mathrm{吐}\mathrm{量}=\frac{\mathrm{完}\mathrm{成}\mathrm{的}\mathrm{进}\mathrm{程}\mathrm{数}}{\mathrm{总}\mathrm{时}\mathrm{间}}$$

单位时间内完成的进程数量。

2.3 周转时间

$$\mathrm{周}\mathrm{转}\mathrm{时}\mathrm{间}=\mathrm{完}\mathrm{成}\mathrm{时}\mathrm{间}-\mathrm{到}\mathrm{达}\mathrm{时}\mathrm{间}$$

进程从提交到完成所经历的总时间。

$$\mathrm{平}\mathrm{均}\mathrm{周}\mathrm{转}\mathrm{时}\mathrm{间}=\frac{\sum _{i=1}^n\mathrm{周}\mathrm{转}\mathrm{时}{\mathrm{间}}_i}{n}$$

2.4 等待时间

$$\mathrm{等}\mathrm{待}\mathrm{时}\mathrm{间}=\mathrm{周}\mathrm{转}\mathrm{时}\mathrm{间}-\mathrm{执}\mathrm{行}\mathrm{时}\mathrm{间}$$

进程在就绪队列中等待的总时间。

$$\mathrm{平}\mathrm{均}\mathrm{等}\mathrm{待}\mathrm{时}\mathrm{间}=\frac{\sum _{i=1}^n\mathrm{等}\mathrm{待}\mathrm{时}{\mathrm{间}}_i}{n}$$

2.5 响应时间

$$\mathrm{响}\mathrm{应}\mathrm{时}\mathrm{间}=\mathrm{首}\mathrm{次}\mathrm{运}\mathrm{行}\mathrm{时}\mathrm{间}-\mathrm{到}\mathrm{达}\mathrm{时}\mathrm{间}$$

从进程提交到首次运行的时间。

2.6 指标关系

指标	目标	衡量内容
CPU 利用率	越高越好	CPU 忙碌程度
吞吐量	越大越好	系统处理能力
周转时间	越短越好	作业完成速度
等待时间	越短越好	用户体验
响应时间	越短越好	交互响应速度

三、先来先服务（FCFS）算法

3.1 算法思想

按照进程到达的先后顺序进行调度，先到达的先执行。

3.2 示例

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

FCFS 调度:
时间: 0 ─────────────────────── 30
      │    P1    │ P2 │ P3 │
      0         24   27   30

等待时间: P1 = 0, P2 = 23, P3 = 25
平均等待时间 = (0 + 23 + 25) / 3 = 16
周转时间: P1 = 24, P2 = 26, P3 = 28
平均周转时间 = (24 + 26 + 28) / 3 = 26

3.3 特点

优点	缺点
实现简单	长作业后面的短作业等待时间长
公平	对 I/O 密集型进程不友好
适合 CPU 密集型	可能产生"护航效应"

护航效应

一个长作业先到达，后面多个短作业必须等待，导致平均等待时间很长。

四、短作业优先（SJF）算法

4.1 算法思想

优先调度执行时间最短的进程。

4.2 非抢占式 SJF

使用上面相同的进程：

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

SJF (非抢占):
时间: 0 ─────────────────────── 30
      │    P1    │ P2 │ P3 │
      0         24   27   30

P1 先到达，执行完后 P2、P3 都已到达
选择执行时间短的 P2，然后 P3

等待时间: P1 = 0, P2 = 23, P3 = 25
平均等待时间 = 16

4.3 抢占式 SJF（SRTF）

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

SRTF (抢占式):
时间: 0 ─────────────────────── 30
      │P1│ P2 │ P3 │   P1    │
      0  1    4    7        30

到达时间 1: P2 剩余 3 < P1 剩余 23，切换到 P2
到达时间 2: P3 剩余 3 = P2 剩余 3，继续 P2
P2 完成后: P3 剩余 3 < P1 剩余 23，执行 P3
P3 完成后: 执行 P1

等待时间: P1 = 0 + (7-1) = 6, P2 = 0, P3 = 4-2 = 2
平均等待时间 = (6 + 0 + 2) / 3 = 2.67

4.4 特点

优点	缺点
平均等待时间最短	对长作业不公平
吞吐量高	可能导致长作业"饥饿"
适合批处理系统	需要预知执行时间

饥饿问题

如果不断有短作业到达，长作业可能永远得不到执行。

五、时间片轮转（RR）算法

5.1 算法思想

每个进程轮流使用 CPU 一个时间片（Quantum），时间片用完后切换到下一个进程。

5.2 示例

时间片 q = 4

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

RR (时间片=4):
时间: 0 ──────────────────────── 30
      │P1│P2│P3│ P1 │  P1  │
      0  4  7  10  14    30

轮转过程:
0-4:   P1 执行 (剩余 20)
4-7:   P2 执行 (完成)
7-10:  P3 执行 (完成)
10-14: P1 执行 (剩余 16)
14-18: P1 执行 (剩余 12)
...直到 P1 完成

等待时间: P1 = 0 + (10-4) + (14-10) + ... = 6
          P2 = 4-1 = 3
          P3 = 7-2 = 5

5.3 时间片大小的影响

时间片大小	影响
太大	退化为 FCFS
太小	上下文切换频繁，开销大
适中	平衡响应时间和切换开销

时间片选择

• 通常选择 10-100ms
• 上下文切换时间应 < 时间片的 1%
• 响应时间要求高 → 较小时间片
• 吞吐量要求高 → 较大时间片

5.4 特点

优点	缺点
公平，每个进程都有机会	时间片选择很关键
响应时间好	上下文切换开销
适合交互式系统	平均周转时间可能较长

六、优先级调度算法

6.1 算法思想

为每个进程分配一个优先级，优先调度优先级高的进程。

6.2 优先级类型

类型	说明
静态优先级	创建时确定，运行期间不变
动态优先级	运行期间根据情况调整

6.3 优先级确定因素

优先级 = f(进程类型, 执行时间, 等待时间, I/O 频率, ...)

常见规则:
- I/O 密集型 > CPU 密集型
- 短作业 > 长作业
- 等待时间长 → 提高优先级
- 用户进程 > 系统进程（可配置）

6.4 示例

进程	到达时间	执行时间	优先级
P1	0	10	3
P2	1	5	1
P3	2	8	4
P4	3	3	2

优先级数字越小优先级越高。

优先级调度:
时间: 0 ──────────────────────── 26
      │P1│ P2 │ P4 │   P3   │
      0  10   15   18       26

P1 先到达，执行
执行完后: P2(优先级1) > P4(优先级2) > P3(优先级4)
依次执行 P2 → P4 → P3

6.5 饥饿问题与解决

问题： 低优先级进程可能永远得不到执行。

解决方案：老化（Aging）技术

随着时间推移，提高等待进程的优先级

初始优先级:  P1=10, P2=20, P3=30
等待 5 个单位后: P1=5, P2=15, P3=25
等待 10 个单位后: P1=0, P2=10, P3=20

最终 P1 会获得最高优先级

6.6 特点

优点	缺点
可以区分任务紧急程度	低优先级可能饥饿
灵活性高	优先级确定困难
适合实时系统	需要老化机制防止饥饿

七、多级反馈队列调度算法

7.1 算法思想

结合了 FCFS、SJF、RR 的优点，设置多个就绪队列，每个队列有不同的优先级和时间片。

7.2 数据结构

高优先级 ┌─────────────────────────────┐
队列1:   │ P_a → P_b → P_c          │ 时间片=1
         └─────────────────────────────┘
                ↓ 时间片用完
         ┌─────────────────────────────┐
队列2:   │ P_d → P_e                 │ 时间片=2
         └─────────────────────────────┘
                ↓ 时间片用完
         ┌─────────────────────────────┐
低优先级 │ P_f → P_g → P_h           │ 时间片=4
队列3:   └─────────────────────────────┘
(FCFS)

7.3 规则

1. 新进程进入最高优先级队列
2. 进程在当前队列时间片用完 → 降到下一级队列
3. 高优先级队列为空时，才调度低优先级队列
4. 高优先级队列有新进程 → 立即抢占

7.4 示例

新进程 P1 到达，进入队列1 (时间片=1)

队列1: [P1]
       ↓ P1 时间片用完，未完成
队列1: []
队列2: [P1]
       ↓ 新进程 P2 到达，进入队列1，抢占 CPU
队列1: [P2]
队列2: [P1]
       ↓ P2 时间片用完
队列1: []
队列2: [P1, P2]
       ...

7.5 特点

优点	说明
兼顾多种需求	短作业快速完成，长作业也能执行
响应性好	新进程优先级高
无需预知执行时间	根据实际运行情况调整
实现合理	Unix、Linux、Windows 都采用变体

现代操作系统的调度

Linux 的 CFS（完全公平调度器）使用红黑树管理进程，以虚拟运行时间（vruntime）作为调度依据，是多级反馈队列的一种变体。

八、各算法对比与适用场景

8.1 对比表

算法	抢占	公平	响应	吞吐	饥饿	复杂度
FCFS	否	是	差	低	无	低
SJF	否	否	差	高	有	中
SRTF	是	否	中	高	有	中
RR	是	是	好	中	无	低
优先级	可选	否	好	中	有	中
多级反馈	是	是	好	高	无	高

8.2 适用场景

场景	推荐算法	原因
批处理系统	SJF/SRTF	吞吐量高
交互式系统	RR	响应时间好
实时系统	优先级调度	可预测性
通用系统	多级反馈队列	兼顾多种需求

8.3 实际应用

操作系统	调度算法
早期 Unix	多级反馈队列
Linux 2.6	O(1) 调度器
Linux 2.6.23+	CFS (完全公平调度器)
Windows	多级反馈队列 + 优先级
macOS	基于 Mach 的多级调度

九、总结

9.1 调度算法选择建议

需要简单公平？         → FCFS / RR
追求最大吞吐量？       → SJF
需要快速响应？         → RR (小时间片)
需要区分优先级？       → 优先级调度 + 老化
通用系统？            → 多级反馈队列

9.2 核心要点

要点	说明
FCFS	简单但有护航效应
SJF	平均等待时间最短但可能饥饿
RR	公平响应好但时间片选择关键
优先级	灵活但需要老化机制
多级反馈	综合最优，现代系统首选

面试要点

1. 掌握各算法的执行过程和计算方法
2. 理解各算法的优缺点和适用场景
3. 能够计算平均等待时间和周转时间
4. 了解现代操作系统的调度策略
5. 理解饥饿问题和解决方案