操作系统第 2 章：进程管理

408 操作系统「进程管理」复习：核心知识点、真题题型、通用解法与易错点。

本章依据本站 408 真题 → 操作系统 → 第 2 章进程管理 整理，并结合 408 模拟选择题 → 操作系统 → 第 2 章进程与线程 补充内容。本站把这一章的统考真题分成四大块：进程与线程、CPU 调度与上下文切换、进程同步、死锁；这也基本就是 408 操作系统第二章的完整命题框架。(docs.any1.tech)

这一章和第一章完全不同：第一章大量是概念判断，而第二章不仅选择题多，而且是 操作系统最重要的大题来源之一。尤其是：

进程状态转换 + CPU 调度计算 + PV 信号量 + 死锁/银行家算法

必须做到“看到题就知道属于哪个模型”。

一、第 2 章总框架：到底学什么

建议先建立这张脑图：

进程管理

进程与线程
- 进程、程序、PCB
- 进程状态及转换
- 进程创建/终止
- 线程共享与私有资源
- 用户级线程 / 内核级线程
- 进程通信
CPU 调度
- 调度时机
- FCFS
- SJF / SRTF
- 优先级
- HRRN
- RR
- 多级反馈队列
- 周转时间、等待时间
- 上下文切换
同步与互斥
- 临界资源
- 竞争条件
- Peterson
- TSL / Swap
- 信号量
- PV 大题
- 生产者消费者
- 哲学家
- 前驱关系
死锁
- 四个必要条件
- 预防
- 避免
- 银行家算法
- 检测
- 解除

从网站真题数量和命题形式也能明显看出来：进程同步和 CPU 调度是本章最核心的两部分，死锁次之，线程/状态转换属于稳定选择题考点。 (Any Docs)

二、进程与线程

1. 进程到底是什么

考试最喜欢把：

程序
进程
线程

混在一起。

程序

程序是静态的指令集合。

例如：

chrome.exe

放在磁盘上时只是程序。

进程

进程是：

程序的一次执行过程。

同时，它是传统操作系统中：

资源分配的基本单位。

系统要管理一个进程，就需要一个非常重要的数据结构：

PCB（Process Control Block，进程控制块）

PCB 里面通常保存：

PID
进程状态
PC
寄存器
优先级
内存信息
打开的文件
I/O 信息
调度信息

所以有一个非常重要的判断：

PCB 是进程存在的唯一标志。

三、题型一：什么时候会创建进程

【408 真题·2010】

题目：

下列操作中，哪些会导致创建新进程？

I. 用户登录成功 II. 设备分配 III. 启动程序执行

答案：

I、III。

用户登录通常要创建用户进程；启动程序也要创建相应进程，而设备分配只是给已有进程分资源，不创建新进程。(Any Docs)

秒杀方法

问“是否创建进程”，考虑：

是不是出现了一个新的独立执行实体？

例如：

操作	创建新进程？
登录系统	通常是
启动程序	是
fork	是
分配打印机	否
打开文件	否
缺页	否
I/O 完成	否

四、进程状态转换——本章最稳定的选择题

最基本的三状态：

              调度
      就绪 ----------> 运行
       ↑               |
       |               |
事件完成 |               | 等待事件/I/O
       |               ↓
       +------------- 阻塞

还要补一个：

运行 --时间片耗尽/被抢占--> 就绪

这是整个第二章必须形成条件反射的一张图。

五、题型二：运行、就绪、阻塞怎么判断

最重要的判断原则只有一句：

能运行但没 CPU → 就绪。

即使给 CPU 也运行不了 → 阻塞。

1. 运行 → 阻塞

通常发生在：

等待 I/O
wait/P 操作资源不足
等待某事件
等待临界资源
缺页，需要磁盘调页

2. 运行 → 就绪

通常发生在：

时间片用完
高优先级进程抢占
主动让出 CPU

3. 阻塞 → 就绪

通常因为：

I/O 完成
等待事件发生
信号量 V 操作把它唤醒
所需资源得到满足

注意：

阻塞态不能直接变运行态。

必须：

阻塞 → 就绪 → 运行

六、真题：状态转换一定要会

【408 真题·2015】

题目：

哪个事件会导致进程由执行态变为就绪态？

A. 执行 P(wait) B. 申请内存失败 C. 启动 I/O D. 被高优先级进程抢占

答案 D。(Any Docs)

为什么？

前三个都是：

现在即使给 CPU，也可能不能继续。

所以进入阻塞。

被高优先级进程抢占：

进程仍具备运行条件，只是暂时没有获得 CPU。

所以：

运行 → 就绪

【408 真题·2018】

题目：

哪些事件可能导致进程 P 阻塞？

I. 申请临界资源 II. 从磁盘读取数据 III. CPU 被高优先级进程抢占

答案：

I、II。

III 是运行 → 就绪，不是阻塞。(Any Docs)

【408 真题·2022】

题目：

哪些可能导致执行态 → 阻塞态？

I. 读文件 II. 时间片用完 III. 申请外设 IV. wait()

答案：

I、III、IV。 (Any Docs)

这类题看到“时间片用完”一定条件反射：

运行 → 就绪。

【408 真题·2023】

题目：

当前线程执行什么操作可能从执行态变为就绪态？

A. 键盘输入 B. 缺页异常 C. 主动出让 CPU D. wait()

答案 C。(Any Docs)

这已经说明 408 在逐渐把“进程状态”变成“线程状态”来考，但本质完全一样。

七、一个特别容易错的概念

谁能让阻塞进程变成就绪？

不是阻塞进程自己。

因为：

阻塞进程根本没在 CPU 上运行。

通常由：

中断处理程序
OS
其他进程的 V 操作

完成唤醒。

八、2023 大题：系统调用 + 阻塞 + 中断 + 调度

这是非常值得掌握的一道综合题。

【408 真题·2023，8 分】

进程 P 调用系统调用从键盘接收字符，涉及：

① 将 P 插入就绪队列 ② 将 P 插入阻塞队列 ③ 将字符从键盘控制器读入系统缓冲区 ④ 启动键盘中断处理程序 ⑤ P 从系统调用返回 ⑥ 用户输入字符

正确过程：

P 发起 read()
↓
没有输入
↓
② P 进入阻塞队列
↓
CPU 执行其他进程
↓
⑥ 用户按键
↓
④ 键盘中断
↓
③ 驱动程序读字符
↓
① 唤醒 P，进入就绪队列
↓
调度 P
↓
⑤ 系统调用返回

因此：

②之后一定发生 CPU 切换
①之后 P 才重新有资格被调度
③属于键盘驱动程序
中断执行时 P 尚处于阻塞态
CPU 执行中断处理程序时处于内核态 (Any Docs)

这道题特别重要，因为它把第二章和第一章的：

系统调用、内核态、中断

连起来了。

九、进程创建和终止

【408 真题·2021】

创建新进程时必须：

I. 申请 PCB II. 初始化 PCB III. 立即设为执行态

答案：

I、II。

新进程一般先：

创建态 → 就绪态

而不是立即运行。(Any Docs)

【408 真题·2024】

进程终止时，不一定执行哪个操作？

A. 终止子进程 B. 回收设备 C. 释放 PCB D. 回收内存

答案 A。

设备、内存、PCB 都属于自己的资源，必须回收。

但是：

父进程死了，不代表子进程一定跟着死。

(Any Docs)

十、线程：408 高频概念

线程引入之后：

进程仍然是资源分配基本单位。

线程成为 CPU 调度基本单位。

十一、同一进程线程共享什么？

必须背：

共享

地址空间
代码
全局变量
堆
打开的文件
文件描述符
进程资源

不共享

每个线程自己的：

PC
寄存器
栈
栈指针
线程控制信息

一句话：

资源共享，运行现场独立。

【408 真题·2011】

进程 P 中多个线程不能共享什么？

A. 代码段 B. 打开的文件 C. 全局变量 D. 某线程的栈指针

答案 D。(Any Docs)

【408 真题·2024】

线程 T 打开文件得到 fd，再创建 Ta、Tb。

Ta、Tb 可以共享：

I. P 的地址空间 II. T 的栈 III. fd

答案：

I、III。

栈是线程私有资源。(Any Docs)

十二、父子进程和线程千万别混

同一进程内线程

共享地址空间。

父进程和子进程

拥有各自独立的虚拟地址空间。

【408 真题·2020】

错误的是：

父进程与子进程共享虚拟地址空间。

错误。

虽然 fork 后内容可能一开始相同，甚至物理页面采用 Copy-on-Write，但：

逻辑地址空间仍属于两个独立进程。

(Any Docs)

十三、用户级线程与内核级线程

这是选择题常考。

用户级线程 ULT

线程管理在用户态。

优点：

切换快
不必进入内核
OS 不必直接支持线程

缺点：

经典多对一模型下，一个线程阻塞系统调用可能导致整个进程阻塞。

内核级线程 KLT

由 OS 内核管理。

特点：

内核知道每个线程
调度由 OS 完成
切换一般开销更大
多线程更容易真正运行在多个 CPU 上

【408 真题·2019】

错误的是：

操作系统为每个用户级线程建立 TCB。

错误。

用户级线程由用户态线程库管理，OS 通常并不知道每个 ULT。(Any Docs)

十四、进程通信：管道

【408 真题·2014】

关于 Pipe：

A. 一个管道实现双向传输 B. 容量受磁盘限制 C. 读、写都可能阻塞 D. 一个管道只能一个读者或写者

答案 C。(Any Docs)

因为：

管道空：
read → 阻塞

管道满：
write → 阻塞

普通管道通常是：

半双工。

十五、CPU 调度——本章计算题第一核心

现在进入第二个大模块。

必须先记几个量。

十六、周转时间、等待时间、带权周转时间

设：

到达时间 $A_{i}$
完成时间 $C_{i}$
服务时间 $S_{i}$

周转时间：

T_{i} = C_{i} - A_{i}

平均周转时间：

\overline{T} = \frac{1}{n} i = 1 \sum n T_{i}

带权周转时间：

W_{i} = \frac{T _{i}}{S _{i}}

等待时间，在纯 CPU 调度题中通常：

T_{wait} = T_{turnaround} - T_{CPU}

如果题目还有 I/O，还需要进一步扣除相关非就绪等待时间，不能机械使用。

十七、CPU 调度算法总表

算法	抢占？	特征	饥饿？
FCFS	否	谁先来谁执行	一般不会
SJF	否	最短作业优先	会
SRTF	是	最短剩余时间	会
HRRN	否	综合等待+服务时间	基本避免
静态优先级	可抢占/非抢占	优先级高先运行	会
RR	是	时间片循环	不会
MLFQ	是	多级反馈	视规则

十八、FCFS

先来先服务。

优点：

简单
公平
不容易饥饿

缺点：

护航效应（Convoy Effect）

例如：

100 ms CPU进程
1 ms
1 ms
1 ms

长进程先来，三个短进程全部被堵住。

十九、SJF / SRTF

SJF：

已到达作业里选服务时间最短。

如果所有进程同时到达，SJF 可以最小化平均等待时间。

模拟题：5 个进程同时创建

执行时间：

2,4,6,8,10

要平均等待时间最小：

2 → 4 → 6 → 8 → 10

等待时间：

0, 2, 6, 12, 20

平均：

\frac{0 + 2 + 6 + 12 + 20}{5} = 8

网站模拟题答案也是 8。(Any Docs)

二十、HRRN 高响应比优先

这是理论选择题常考。

响应比：

R = \frac{W + S}{S} = 1 + \frac{W}{S}

其中：

$W$ ：等待时间
$S$ ：要求服务时间

它一方面：

$S$ 小 → 短任务有优势。

另一方面：

$W$ 越大 → 等太久的进程优先级越来越高。

所以：

兼顾 SJF，又能防止长作业无限饥饿。

【408 真题·2009】

综合考虑等待时间和执行时间的算法：

答案：

HRRN。 (Any Docs)

【408 真题·2011】

既满足短任务优先，又不产生饥饿：

答案：

HRRN。 (Any Docs)

二十一、优先级调度

这里首先搞清：

数值大，到底是优先级高还是低？

题目必须看清。

有时：

priority 越大 → 权限越高

有时：

priority 数值越小 → 权限越高

408 故意两种都出过。

二十二、抢占式优先级题的万能做法

绝对不要在脑中算。

画时间轴。

步骤：

按到达时刻排序。
写正在运行的进程。
每出现一个新进程，检查是否抢占。
被抢占的进程记剩余时间。
完成一个后重新选最高优先级进程。

二十三、【408 真题·2023】抢占优先级综合计算

题目：

进程	到达	优先级	CPU 时间
P1	0	1	60
P2	20	10	42
P3	30	100	13

题目规定：

数值越大优先级越高。

因此：

0-----20-----30-----43---------75----------115
  P1      P2       P3          P2            P1

分析：

$0 \sim 20$

P1 运行 20ms，剩余：

60 - 20 = 40

$t = 20$

P2 到达：

10 > 1

抢占 P1。

$20 \sim 30$

P2 运行 10ms，剩余：

42 - 10 = 32

$t = 30$

P3 到达：

100 > 10

抢占 P2。

P3 运行 13ms：

30 \sim 43

完成。

之后：

P2 优先级高于 P1：

43 \sim 75

P2 完成。

最后：

75 \sim 115

P1 完成。

周转：

T_{1} = 115 - 0 = 115

T_{2} = 75 - 20 = 55

T_{3} = 43 - 30 = 13

平均：

\frac{115 + 55 + 13}{3} = 61 ms

答案 B。(Any Docs)

二十四、调度次数怎么数

【408 真题·2022】

进程：

进程	到达	优先级（越小越高）	CPU
P0	0	15	100
P1	10	20	60
P2	10	10	20
P3	15	6	10

时间：

0     10    15    25    40 ...
P0 → P2 → P3 → P2 → P0 → P1

调度选择共：

所以答案 6 次。(Any Docs)

易错点

不要只数“进程切换”。

题目如果问：

进程调度次数

初始选择 P0 往往也算一次。

二十五、时间片轮转 RR

时间片 $q$ 。

过程：

P1 q
P2 q
P3 q
...
没执行完 → 队尾

时间片越小：

响应更快
切换更多
开销更大

时间片非常大：

RR 会逐渐退化成 FCFS。

二十六、【408 真题·2024】RR 秒杀题

系统：

10 个进程
时间片 $5 ms$
P 位于队尾
P 最短，需要 $25 ms$

P 需要时间片数：

\frac{25}{5} = 5

由于 P 是最短进程，所以 P 完成之前其余 9 个进程每轮都不会提前退出。

每轮：

10 \times 5 = 50 ms

5 轮：

T = 5 \times 50 = 250 ms

答案 250 ms。(Any Docs)

二十七、时间片题易错点

时间片耗尽：

不是阻塞。

而是：

执行 → 就绪

【408 真题·2017】直接考过这一点。(Any Docs)

二十八、多级反馈队列 MLFQ

这是现在非常重要的算法。

基本思想：

Q1 高优先级，小时间片
↓
没做完
Q2 较低优先级，较长时间片
↓
没做完
Q3 ...

新进程一般：

进入最高优先级队列。

高优先队列：

优先于低优先队列。

因此它同时照顾：

短任务
交互任务
长任务

【408 真题·2019】

两级反馈队列：

Q1：RR，10ms
Q2：SJF
P1 30ms
P2 20ms

过程：

0~10   P1
10~20  P2

进入 Q2 后：

P1 剩20
P2 剩10

Q2 用 SJF：

20~30 P2
30~50 P1

等待时间：

P1：

20 ms

P2：

10 ms

平均：

15 ms

答案 C。(Any Docs)

二十九、CPU 与 I/O 并行题

这是一个看似计算，实际上是“排流水线”的题型。

【408 真题·2016】

3 个作业，每个都是：

输入 2ms
计算 3ms
输出 4ms

机器有：

1 输入设备
1 CPU
1 输出设备

三者可以并行。

最优安排：

J1: 输入 0-2    CPU 2-5    输出 5-9
J2: 输入 2-4    CPU 5-8    输出 9-13
J3: 输入 4-6    CPU 8-11   输出 13-17

所以总时间：

17 ms

而不是：

3 (2 + 3 + 4) = 27 ms

(Any Docs)

核心

不同设备：

可以并行。

同一设备：

必须串行。

三十、调度算法与饥饿

必须背：

可能饥饿

SJF
SRTF
静态优先级

通常不饥饿

FCFS
RR
HRRN

【408 真题·2014】明确考过：

不可能导致饥饿的是时间片轮转。(Any Docs)

三十一、老化 Aging

解决优先级饥饿的重要办法。

【408 真题·2016 大题】

题目要求设计动态 priority。

网站给出一种可行形式：

p r i or i t y = ni ce + c p u T im e - w ai tT im e

题设是“数值越小优先级越高”。

所以：

进程一直运行：

c p u T im e ↑

导致：

p r i or i t y ↑

优先级降低。

进程一直等待：

w ai tT im e ↑

导致：

p r i or i t y ↓

优先级提高。

这就是：

老化机制。

(Any Docs)

三十二、上下文切换考什么

上下文切换就是：

保存当前运行现场，恢复另一个进程的运行现场。

通常包括：

PC
SP
通用寄存器
状态寄存器
页表相关寄存器

【408 真题·2024】

页式存储系统进行进程切换，需要更新：

I. PC II. 栈基址寄存器 III. 页表基址寄存器

答案：

全部。 (Any Docs)

这道题实际上把：

第二章进程切换 + 第三章页表

结合了起来。

三十三、下面进入本章最重要部分：同步与互斥

如果第二章只能学好一个大题模块：

优先学 PV。

三十四、同步和互斥区别

互斥

强调：

不能同时做。

例如：

P1 修改余额
P2 修改余额

必须串行。

同步

强调：

必须按照某个先后次序做。

例如：

生产数据 → 消费数据

必须：

生产完成
↓
消费者才能消费

三十五、临界资源与临界区

临界资源：

一次只允许一个进程使用的资源。

临界区：

访问临界资源的代码段。

经典结构：

进入区

临界区

退出区

剩余区

三十六、互斥机制四原则

通常学习：

空闲让进
忙则等待
有限等待
让权等待

但要特别注意：

让权等待不是实现互斥正确性的绝对必要条件。

忙等待的自旋锁也能实现正确互斥。

【408 真题·2020】考过：实现临界区互斥必须满足的是“互斥、空闲让进、有限等待”，而“不能进入临界区的运行进程立即放弃 CPU”并不是所有互斥方法必须满足。(Any Docs)

三十七、竞争条件 Race Condition

【408 真题·2011】

初始：

x=1

P1：

load R1,x
inc R1
store x,R1

P2：

load R2,x
dec R2
store x,R2

如果串行：

x = 1

但可以：

P1: load 1
P2: load 1

P1: 算出2
P2: 算出0

如果 P1 最后写：

x = 2

如果 P2 最后写：

x = 0

因此：

x \in {0, 1, 2}

(Any Docs)

三十八、这种题怎么做？

不要“凭感觉并发”。

把一个高级语句拆成：

读
计算
写

例如：

x++;

不是原子操作。

本质：

load x
add 1
store x

然后枚举不同交错顺序。

三十九、Peterson 算法

两个进程：

flag[i] = true;
turn = j;
while(flag[j] && turn == j);
critical section
flag[i] = false;

含义：

flag[i]：

表示进程希望进入临界区。

turn=j：

若双方同时希望进入，可依据让步机制决定进入顺序。

【408 真题·2010】

网站给出的正是 Peterson 算法，问：

是否保证互斥？
是否饥饿？

答案：

能保证互斥，也不会出现饥饿。

(Any Docs)

四十、软件互斥题的分析套路

考试给出一个奇怪算法，不要死算所有交错。

检查四件事情：

① 两个人能否同时进去？

找到一个反例即可判互斥失败。

② 临界区空闲时能否进入？

否则违反“空闲让进”。

③ 会不会无限等待？

检查饥饿。

④ 是忙等还是阻塞？

while(lock);

一般是忙等待。

四十一、模拟题：错误的双 flag 算法

P0：

while(flag[1]);
flag[0]=true;
critical section;

P1 类似。

问题：

两个进程可能同时：

看到对方 flag=false

然后：

P0 flag[0]=true
P1 flag[1]=true

然后一起进入。

所以：

“检查”与“置位”不是原子的。

网站模拟题也专门用这个例子强调了这一点。(Any Docs)

这是非常值得预测的一种新题。

四十二、TSL / Test-and-Set / Swap

硬件提供：

原子读—改—写操作。

常用于实现：

自旋锁

【408 真题·2016】

while(TSL(&lock));
critical section;
lock=FALSE;

等待进程在：

while(...)

里不断转。

所以：

不主动放弃 CPU。

答案 B。(Any Docs)

四十三、忙等待和让权等待

TSL / Swap / 自旋锁

通常：

忙等待。

记录型信号量

资源不够时：

进程阻塞，让出 CPU。

因此满足：

让权等待。

四十四、2023 真题：Swap 实现互斥

这是非常有代表性的“看代码改错题”。

题中某同学写：

bool key = TRUE;

if(key == TRUE)
    swap(key,lock);

临界区;

lock = TRUE;

两个主要错误：

错误 1

if

应该反复竞争：

while

错误 2

离开临界区应该释放锁：

lock=FALSE;

而不是 TRUE。

另外，普通 C 函数：

newSwap()

不能自动替代硬件 swap 指令，因为普通函数由若干指令组成：

不具有原子性。

这正是 2023 真题强调的内容。(Any Docs)

四十五、为什么普通 load/store 不行？

核心：

原子性。

例如：

if(lock==false)
    lock=true

可能发生：

P1读到false
切换
P2读到false
P2置true
P2进入
切换
P1置true
P1进入

互斥立即失效。

四十六、信号量——第二章真正的大题工具

定义：

P(S) / wait(S)

V(S) / signal(S)

四十七、记录型信号量值的意义

这个必须精确掌握。

若：

S \geq 0

那么：

S = 可用资源数

若：

S < 0

那么：

∣ S ∣ = 等待该资源的进程数

【408 真题·2010】

信号量初值 3，当前值 1。

问：

可用资源 M
等待进程 N

答案：

M = 1, N = 0

(Any Docs)

四十八、P/V 对信号量的影响

P：

S--
if S<0:
    block

V：

S++
if S<=0:
    wakeup

一定记住这个细节：

V 后是 $S \leq 0$ 时唤醒。

为什么包括 0？

例如 V 前：

S = - 1

代表：

有 1 个阻塞进程。

V 后：

S = 0

此时必须唤醒它。

网站模拟题甚至指出一处关于 <0 与 <=0 的转录易错点，因此这里尤其值得注意。(Any Docs)

四十九、PV 大题最重要的方法

以后所有 PV 大题都按下面 5 步。

第一步：找进程

例如：

生产者
消费者

或者：

A
B
C

第二步：找“同步关系”

把题目中的：

A 做完以后 B 才能做

翻译成：

A → B

于是：

A;
V(S);

P(S);
B;

同步信号量：

S = 0

第三步：找“互斥关系”

问：

哪些代码会同时访问同一个共享资源？

例如：

put()
get()

访问同一个缓冲区：

P(mutex);
访问;
V(mutex);

其中：

m u t e x = 1

第四步：资源计数

例如 N 个空位：

e m pt y = N

初始没有产品：

f u l l = 0

第五步：检查 P 的顺序

一般原则：

同步 P 在前，互斥 P 在后。

典型：

P(empty);
P(mutex);

put();

V(mutex);
V(full);

不要：

P(mutex);
P(empty);

否则：

占着 mutex 等 empty

有可能导致别人无法进入临界区释放条件，产生死锁。

五十、经典模型一：前驱关系

这是最简单，也最应该拿满分的 PV 题。

假设：

A → C
B → C
C → E
D → E

可以：

A;
V(SA);

B;
V(SB);

P(SA);
P(SB);
C;
V(SC1);
V(SC2);

D;
V(SD);

P(SC1);
P(SD);
E;

五十一、【408 真题·2020】

题目：

5 个操作 A、B、C、D、E。

要求：

A ─┐
   ├→ C ─┐
B ─┘     ├→ E
D ───────┘

也就是：

C 在 A、B 后
E 在 C、D 后

这就是标准前驱关系型 PV。网站真题给出的核心也是为相应完成事件设置初值为 0 的同步信号量。(Any Docs)

五十二、【408 真题·2022】更聪明的一种前驱图

两个线程：

T1：

A → E → F

T2：

B → C → D

额外约束：

A、B → C
C → D、E
E → F

关键不是给每条箭头都建信号量。

因为：

T2 自己本来：

B → C → D

所以：

B→C 不用信号量
C→D 不用
T1 自己 E→F 也不用

只需要跨线程：

A → C
C → E

所以只需要两个：

S_{A} = 0, S_{C} = 0

T1：

A;
V(SA);

P(SC);
E;
F;

T2：

B;
P(SA);
C;
V(SC);
D;

网站真题也给出了这个最简解。(Any Docs)

这是 PV 大题一个非常重要的进阶原则

同一进程/线程内部已有的程序顺序，不需要再用信号量保证。

五十三、经典模型二：生产者—消费者

标准版：

缓冲区大小 N。

定义：

e m pt y = N

f u l l = 0

m u t e x = 1

生产者：

while(1){
    produce();

    P(empty);
    P(mutex);

    put();

    V(mutex);
    V(full);
}

消费者：

while(1){
    P(full);
    P(mutex);

    get();

    V(mutex);
    V(empty);

    consume();
}

五十四、为什么要三个信号量？

empty

防止生产者：

缓冲区满了还生产。

full

防止消费者：

缓冲区空了还消费。

mutex

防止：

两个进程同时修改缓冲区内部结构。

所以：

empty/full：同步
mutex：互斥

五十五、【408 真题·2009】奇偶消费者

这是非常经典的大题。

题目：

P1 产生正整数放进 N 个单元缓冲区。

P2：

只拿奇数。

P3：

只拿偶数。

需要：

e m pt y = N

o dd = 0

e v e n = 0

m u t e x = 1

生产者：

x=produce();

P(empty);
P(mutex);

put(x);

V(mutex);

if(x%2)
    V(odd);
else
    V(even);

奇数消费者：

P(odd);
P(mutex);

getodd();

V(mutex);
V(empty);

偶数消费者：

P(even);
P(mutex);

geteven();

V(mutex);
V(empty);

这道题的网站真题解析也强调了：

生产者实际放入之后，再增加 odd/even；消费者真正取出后，再增加 empty。(Any Docs)

五十六、这道题真正应该学会什么？

不是背：

odd
even

而是学：

产品有几种“可消费类别”，往往就给几类产品设置计数信号量。

预测题完全可以改成：

红球 / 蓝球
奇数 / 偶数
普通任务 / 紧急任务
男生 / 女生
A 类数据 / B 类数据

方法不变。

五十七、经典模型三：容量限制

【真题模型：展馆容量】

题目模型：

展馆最多容纳 500 人，只有一个出入口。

可以设置：

c a p a c i t y = 500

d oor = 1

过程：

P(capacity);

P(door);
进门;
V(door);

参观;

P(door);
出门;
V(door);

V(capacity);

网站给出的真题解法正是这个结构。(Any Docs)

五十八、容量信号量非常重要

这不是简单互斥。

例如：

capacity=500

表示：

最多允许 500 个实体同时处于某一状态。

这种题未来可以变：

停车场 100 个车位
实验室最多 20 人
数据库最多 50 个连接
电梯最多 10 人

统一写：

c a p a c i t y = N

五十九、经典模型四：银行叫号

【408 真题·2011】

题目：

1 个服务窗口
10 个等待座位
一个取号机
取号机一次只能一人使用
营业员空闲时叫号

需要至少理解四种关系：

座位

se a t = 10

取号机互斥

t i c k e t = 1

已经等待的顾客

c u s t o m er = 0

已经叫出的号

c a l l e d = 0

网站真题给出的主体结构是：顾客先取得座位和取号机，取号后通知营业员有顾客；营业员等到存在顾客后叫号，再唤醒一名顾客。(Any Docs)

六十、这种复杂 PV 题怎么拆？

千万别一次性想完整代码。

先把中文转换成约束：

必须有空座 → 才能等待

所以：

se a t

一个人用取号机

所以：

t i c k e t = 1

有顾客 → 营业员才能叫号

所以：

c u s t o m er = 0

叫过号 → 顾客才能去服务

所以：

c a l l e d = 0

最后再拼代码。

六十一、经典模型五：“连续执行 N 次”

【408 真题·2014】

缓冲区：

1000

多个生产者和消费者。

额外条件：

一个消费者连续取出 10 件产品以后，其他消费者才能取。

除了标准：

e m pt y = 1000

f u l l = 0

m u t e x = 1

还需要：

co n s u m er M u t e x = 1

消费者：

P(consumerMutex);

for(i=0;i<10;i++){
    P(full);
    P(mutex);

    get();

    V(mutex);
    V(empty);
}

V(consumerMutex);

网站真题正是这样利用第二个消费者互斥信号量，把“连续 10 次”整体包起来。(Any Docs)

六十二、这是很值得预测的变式

以后出现：

某线程必须连续完成 $k$ 个操作。

就考虑：

给这一整组操作外面再套一层组级 mutex。

例如：

P(groupMutex);

for(...)
    ...

V(groupMutex);

六十三、经典模型六：信箱

【408 真题·2015】

A、B 辩论。

A：

从 A 信箱取邮件
→ 回答
→ 放进 B 信箱

B 相反。

A 信箱容量 M，初始 x 封。

B 信箱容量 N，初始 y 封。

定义：

A f u l l = x

A e m pt y = M - x

B f u l l = y

B e m pt y = N - y

A：

P(Afull);
从A取;
V(Aempty);

回答;

P(Bempty);
放入B;
V(Bfull);

B 对称。(Any Docs)

六十四、为什么这题可以没有 mutex？

因为：

A 信箱：

只有 A 取
只有 B 放

B 信箱：

只有 B 取
只有 A 放

不存在多个同类生产者同时修改同一个位置管理结构的题设竞争。

所以网站解析也指出：

题设下无须额外设置互斥信号量。(Any Docs)

这是非常容易丢分的地方

不是所有生产者消费者题：

都必须机械写 mutex。

先看是否确实存在并发访问冲突。

六十五、经典模型七：哲学家问题

【408 真题·2019】

n 个哲学家。

每人需要：

一个碗
左筷子
右筷子

共有 m 个碗。

要：

尽可能多人同时吃
防止死锁

筷子：

c h o p s t i c k [i] = 1

碗的信号量可取：

b o w l = min (m, n - 1)

为什么 $n - 1$ ？

如果允许 n 个人同时开始：

每人拿左筷子
↓
所有人等右筷子

形成循环等待。

只允许：

n - 1

个人进入拿筷子阶段：

至少有一人不持有筷子，因此循环被破坏。

网站真题正是利用这一点防止哲学家死锁。(Any Docs)

六十六、PV 与死锁经常融合

所以不要把：

2.3 同步

和：

2.4 死锁

割裂学习。

PV 代码里面最常见的死锁来源：

错误 P 顺序

P(mutex);
P(empty);

可能：

拿着锁等资源。

另一个进程需要 mutex 才能产生这个资源。

于是死锁。

六十七、线程共享变量题

【408 真题·2017】

有三个线程访问全局复数：

x,y,z

thread1：

读 x,y

thread2：

读 y,z

thread3：

修改 z
修改 y

题目要求：

互斥正确，同时最大化并发。

正确思路：

x

只有读：

不需要锁。

y

有读有写：

m_{y} = 1

z

有读有写：

m_{z} = 1

thread2 同时读 y、z：

P(my);
P(mz);

read y,z;

V(mz);
V(my);

thread3 修改 y、z 时分别只锁对应变量。

这样比给整个程序一个全局 mutex：

并发度更高。

网站解答还特别采用固定锁顺序，以避免多个锁获取顺序不同导致死锁。(Any Docs)

六十八、多锁题的重要规则

如果需要同时拿：

L_{1}, L_{2}

所有线程最好统一：

先 L1
再 L2

不要：

线程A：L1 → L2
线程B：L2 → L1

否则：

A 持有 L1 等 L2
B 持有 L2 等 L1

直接形成循环等待。

六十九、死锁——第三个核心模块

死锁：

一组进程互相等待对方占有的资源，从而所有进程都无法继续。

七十、死锁四个必要条件

必须完整背下来。

① 互斥

资源不能共享使用。

② 请求并保持

进程：

保持已有资源，同时请求新资源。

③ 不可剥夺

资源不能被系统强行抢走。

④ 循环等待

存在：

P1 等 P2
P2 等 P3
...
Pn 等 P1

七十一、关系

死锁：

\Rightarrow

四条件全部成立。

但：

四条件存在，也不意味着当前一定死锁。

这是必要条件，不是充分条件。

七十二、死锁处理四大方法

必须区分：

死锁预防

提前破坏四条件之一。

死锁避免

不破坏四条件，但是：

每次分配前检查安全性。

典型：

银行家算法。

死锁检测

先允许死锁发生。

然后：

定期检查。

死锁解除

发生之后：

杀进程
剥夺资源
回退

七十三、最容易混的：预防 vs 避免

预防

改变规则，例如：

所有资源按编号递增申请。

这破坏：

循环等待。

避免

允许各种申请顺序，但系统检查：

“如果现在分配资源，系统是否仍处于安全状态？”

这才是银行家算法。

【408 真题·2013】

银行家算法：

A. 预防死锁 B. 安全状态下系统一定无死锁 C. 不安全状态下一定死锁 D. 破坏请求保持条件

答案 B。(Any Docs)

必须记：

安全 \Rightarrow 不死锁

但是：

不安全 \neq \Rightarrow 已死锁

不安全的意思只是：

存在将来发生死锁的风险。

七十四、同类资源“保证不死锁”公式

这一类是真题反复考。

假设有 $n$ 个进程。

进程 $P_{i}$ 最大需要：

R_{i}

个同类资源。

最坏状态：

每个进程都已经拿：

R_{i} - 1

然后每个人都只差 1 个。

只要系统还能剩 1 个资源，就可以让其中一个完成。

因此保证不死锁：

R_{m i n} = i = 1 \sum n (R_{i} - 1) + 1

七十五、【408 真题·2014】

三个进程分别最多需要：

3, 4, 5

台设备。

最小设备数量：

(3 - 1) + (4 - 1) + (5 - 1) + 1

= 2 + 3 + 4 + 1

= 10

答案 B。(Any Docs)

七十六、统一需求时进一步简化

如果：

n 个进程
每个最多需要 k 个同类资源

保证不死锁：

R_{m i n} = n (k - 1) + 1

【408 真题·2021】

n 个进程。

每个都需要 2 个资源。

于是：

R_{m i n} = n (2 - 1) + 1

= n + 1

答案：

n + 1

(Any Docs)

七十七、“至少几个进程可能死锁”反过来考

【408 真题·2009】

8 台打印机。

每个进程最多需要 3 台。

要发生死锁，可以让每个进程：

先拿 2 台，再等第 3 台。

如果 K 个进程：

2 K \geq 8

于是：

K \geq 4

K 最小：

4

网站真题答案也是 4。(Any Docs)

七十八、这两种题不要混

问：

至少多少资源确保不死锁？

用：

\sum (R_{i} - 1) + 1

问：

已知资源数，至少多少进程可能形成死锁？

构造：

每个进程都拿到“最大需求减 1”，然后大家等最后一个。

七十九、银行家算法——必须手算熟练

四个核心量：

Max

最大需求：

M a x

Allocation

已经分配：

A l l oc a t i o n

Need

还需要：

N ee d = M a x - A l l oc a t i o n

Available

系统当前剩余：

A v ai l ab l e = T o t a l - \sum A l l oc a t i o n

八十、安全性算法

不断寻找：

N ee d_{i} \leq A v ai l ab l e

的进程。

假设让它完成。

完成之后：

A v ai l ab l e = A v ai l ab l e + A l l oc a t i o n_{i}

然后继续。

如果所有进程最终都能“模拟完成”：

存在安全序列。

系统安全。

八十一、一个很重要的理解

为什么完成以后加的是：

A l l oc a t i o n_{i}

不是：

M a x_{i}

？

因为安全性算法是假设：

剩余 Need 暂时给它，它完成后这些临时给出的 Need 又回到了系统。

相对检查前，系统真正净增加的是：

它原来已经占有的 Allocation。

八十二、【408 真题·2020】银行家算法

A、B 各有 6 个。

进程	已分配A	已分配B	总需求A	总需求B
P1	2	3	4	4
P2	2	1	3	1
P3	1	2	3	4

已分配：

A：

2 + 2 + 1 = 5

B：

3 + 1 + 2 = 6

所以：

A v ai l ab l e = (1, 0)

Need：

P_{1} = (2, 1)

P_{2} = (1, 0)

P_{3} = (2, 2)

只有 P2：

(1, 0) \leq (1, 0)

所以先 P2。

P2 完成释放：

A l l oc a t i o n_{2} = (2, 1)

得到：

A v ai l ab l e = (3, 1)

此时 P1 可完成。

P1 完成：

A v ai l ab l e = (5, 4)

最后 P3。

因此：

P2 → P1 → P3

是安全序列。(Any Docs)

八十三、银行家算法选择题最快方法

如果题目给了 4 个候选安全序列：

不要自己完整搜索。

直接：

拿选项逐个验证。

对一个候选序列：

P3 → P4 → P2 → P1 → P0

依次检查：

N ee d_{i} \leq A v ai l ab l e

成立：

A v ai l ab l e + = A l l oc a t i o n_{i}

中间任何一步失败：

此选项直接排除。

八十四、【408 真题·2012】

系统资源总数：

(18, 6, 22)

根据 Allocation 求：

A v ai l ab l e = (2, 3, 3)

对应 Need：

P_{0} = (2, 3, 7)

P_{1} = (1, 3, 3)

P_{2} = (0, 0, 6)

P_{3} = (2, 2, 1)

P_{4} = (1, 1, 0)

正确安全序列：

P3 → P4 → P2 → P1 → P0

(Any Docs)

八十五、安全序列个数怎么数

【408 真题·2022】

Available：

(1, 3, 2)

Need：

P_{0} = (0, 2, 1)

P_{1} = (1, 2, 3)

P_{2} = (0, 1, 3)

初始只有 P0 能完成。

所以：

第一个必须 P0

P0 完成后：

A v ai l ab l e = (3, 3, 3)

此时：

P1、P2 都能执行。

所以两种：

P0 → P1 → P2

P0 → P2 → P1

安全序列：

2

个。(Any Docs)

八十六、这里有一个非常常见的坑

某进程满足：

N ee d_{i} \leq A v ai l ab l e

而且：

A l l oc a t i o n_{i} = 0

它虽然可以完成，却：

不会释放任何原先占有的资源。

【408 真题·2018】

4 个同类资源。

P1、P2、P3 最大需求：

4, 3, 1

已经获得：

2, 1, 0

已分配 3 个，所以：

A v ai l ab l e = 1

Need：

2, 2, 1

P3 可以先完成。

但是：

A l l oc a t i o n_{3} = 0

所以 P3 完成后：

A v ai l ab l e

还是 1。

P1、P2 都需要 2。

因此：

不存在安全序列。

系统不安全。(Any Docs)

非常经典。

八十七、死锁环分析

【408 真题·2016】

资源：

R_{1}, R_{2}, R_{3}

进程：

P1 要 R1,R2
P2 要 R2,R3
P3 要 R1,R3
P4 只要 R2

问：

若发生死锁，至少多少个进程死锁？

可以构造：

P1 持 R1 → 等 R2
P2 持 R2 → 等 R3
P3 持 R3 → 等 R1

形成：

P1 → P2 → P3 → P1

所以至少：

3

个进程。(Any Docs)

八十八、资源分配图题

如果是：

单实例资源

资源分配图中存在环：

通常可判死锁。

但如果资源：

有多个实例

出现环不一定死锁。

要进一步做：

图化简 / 死锁检测。

网站模拟题也专门设置了多实例资源图化简题：能够不断找到可满足进程并释放资源，则图可以完全化简，不死锁。(Any Docs)

八十九、死锁预防的四种思路

对应四条件：

破坏互斥

让资源共享。

但打印机等资源做不到。

破坏请求并保持

要求：

一次申请所有资源。

或者：

申请新资源前先释放已有资源。

缺点：

资源利用率低。

破坏不可剥夺

申请失败：

释放已经持有的资源。

破坏循环等待

统一编号：

R1<R2<R3

所有进程只能：

R1 → R2 → R3

申请。

这是考试最喜欢问的。

九十、避免 vs 检测真题

【408 真题·2015】

S1：死锁避免 S2：死锁检测

题目比较：

I. 避免必须限制资源申请顺序 II. 避免需要最大资源需求信息，检测不一定需要 III. 避免不会批准导致不安全状态的分配，而检测可以先分配

答案：

II、III。

I 错：

限制申请顺序是“预防循环等待”的方法，不是银行家算法的必要要求。(Any Docs)

九十一、这一章几个必须分清的“箭头关系”

建议直接记这几个。

时间片用完

运行 \to 就绪

被高优先级抢占

运行 \to 就绪

wait 失败

运行 \to 阻塞

I/O 请求

运行 \to 阻塞

I/O 完成

阻塞 \to 就绪

V 唤醒

阻塞 \to 就绪

调度

就绪 \to 运行

九十二、本章选择题的典型“错误说法”

看到这些要警惕：

“时间片用完进入阻塞态”

错。

“阻塞态可以直接进入运行态”

错。

“线程拥有独立地址空间”

同一进程线程：错。

“父子进程共享地址空间”

错。

“用户级线程切换必须进入内核”

错。

“TSL 满足让权等待”

错。

“信号量值为 -3 表示还有 3 个资源”

错。

代表：

3

个等待进程。

“不安全状态就是死锁”

错。

“银行家算法属于死锁预防”

错。

属于：

死锁避免。

“资源分配图有环就一定死锁”

多实例资源情况下不一定。

九十三、PV 大题的万能识别表

看到中文条件：

中文描述	想到
最多 N 个	计数信号量 $S = N$
只能一个	mutex=1
A 后才能 B	S=0，A 后 V，B 前 P
有产品才能取	full=0
有空位才能放	empty=N
两种产品	两个产品计数信号量
连续执行 K 次	外层组级 mutex
多变量分别访问	多把锁
需要同时拿多把锁	统一锁顺序
大家各拿一个再等另一个	警惕死锁

九十四、调度计算题万能模板

以后拿到调度计算题，按下面顺序。

Step 1：先标清

到达时间
CPU时间
优先级
时间片
抢占/非抢占

Step 2：画时间轴

不要脑算。

0-----3-----7-----...

Step 3：每个关键时刻重新检查

关键时刻：

新进程到达
当前进程完成
时间片耗尽
阻塞
I/O 完成

Step 4：写完成时间

C_{i}

Step 5：统一求

T_{i} = C_{i} - A_{i}

九十五、银行家算法万能模板

每次先写四行：

N ee d = M a x - A l l oc a t i o n

A v ai l ab l e = T o t a l - \sum A l l oc a t i o n

然后循环：

N ee d_{i} \leq A v ai l ab l e

则：

A v ai l ab l e \leftarrow A v ai l ab l e + A l l oc a t i o n_{i}

直到：

全部完成 → 安全
再也找不到 → 不安全

九十六、后续值得关注的 408 新变式

结合本站真题和模拟题，这一章很适合继续这样变。

预测 1：线程 + 页表 + 上下文切换

问：

线程切换和进程切换分别需要修改：

PC
SP
页表基址寄存器

同一进程线程切换：

一般不需要切换整个地址空间。

不同进程：

通常需要。

2024 真题已经出现页表基址寄存器与进程切换组合，继续考线程版本非常自然。(Any Docs)

预测 2：PV + 死锁判断

给一段：

P(mutex);
P(empty);

然后问：

是否可能死锁？怎样修改？

重点：

P(empty);
P(mutex);

属于非常自然的综合题。

预测 3：多把锁

线程 A：

lock x
lock y

线程 B：

lock y
lock x

问：

是否可能死锁？

答案：

可能。

修改：

所有线程固定统一加锁顺序。

2017 真题已经体现“最大化并发 + 多锁”的方向。(Any Docs)

预测 4：MLFQ + 新进程到达 + 抢占

不是简单两个进程，而是：

Q1 RR
Q2 RR
Q3 FCFS
中途新进程进入 Q1

要求计算：

完成时间
平均等待
响应时间

这是目前非常值得练的调度综合题。

九十七、第二章复习优先级

如果以 408 得分为目标，建议这样分层。

第一优先级：必须彻底掌握

1. PV 信号量

尤其：

生产者消费者
前驱关系
多资源
连续操作
哲学家
多锁

2. CPU 调度

尤其：

RR
优先级
SJF
MLFQ
周转时间

3. 死锁

尤其：

四条件
银行家算法
保证不死锁资源数

第二优先级

状态转换
PCB
进程创建终止
线程共享
ULT/KLT
上下文切换

第三优先级

Pipe
Peterson 代码细节
TSL/Swap
管程概念

不是说不考，而是通常更多作为选择题。

九十八、考前“最小记忆集”

如果最后只剩 5 分钟，至少回忆下面这些。

进程状态

时间片 → 就绪
抢占 → 就绪
I/O → 阻塞
wait失败 → 阻塞
I/O完成 → 就绪

线程

共享：
代码、地址空间、全局变量、文件

私有：
PC、寄存器、栈

调度

T = C - A

R_{HRRN} = 1 + \frac{W}{S}

PV

同步：
S=0
A; V(S)
P(S); B

互斥：
mutex=1
P(mutex)
critical
V(mutex)

生产者消费者：

empty=N
full=0
mutex=1

信号量值

S \geq 0 \Rightarrow S = 可用资源数

S < 0 \Rightarrow ∣ S ∣ = 阻塞进程数

死锁

互斥
请求并保持
不可剥夺
循环等待

银行家：

N ee d = M a x - A l l oc a t i o n

保证同类资源不死锁：

R_{m i n} = \sum (R_{i} - 1) + 1

统一最大需求 $k$ ：

R_{m i n} = n (k - 1) + 1

九十九、整章真正的解题核心

第二章看起来东西很多，但真正需要练出的其实只有 4 个条件反射：

第一，看到进程状态题，先问“现在给它 CPU，它能不能跑？” 能跑但没有 CPU，就是就绪；给 CPU 也跑不了，就是阻塞。

第二，看到调度题，立即画时间轴。 不要脑算，到达、抢占、完成、时间片耗尽都是时间轴节点。

第三，看到 PV 题，把自然语言翻译成两类关系： “不能同时”就是互斥；“A 做完 B 才能做”就是同步。然后再补容量计数。

第四，看到死锁题，先判断它问的是预防、避免、检测，还是安全序列。 银行家算法只做一件事情：

N ee d_{i} \leq A v ai l ab l e

找到能完成的进程，释放 Allocation，循环即可。

如果这四套反应形成了，操作系统第二章的大多数 408 真题其实都可以归到固定模型中。本站里的历年真题也非常明显地体现了这种重复命题规律：表面场景从银行、信箱、哲学家、缓冲区、线程、打印机不断变化，但底层其实始终是 状态机、调度时间轴、同步依赖图、资源分配图 四种模型。(Any Docs)