408 高频考点精讲:同步问题设计¶
模块归属:操作系统 · 进程管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
1. 考查频次与题号清单¶
- 近十年考查频次:5 次(2019 年第 43 题、2020 年第 45 题、2021 年第 45 题、2022 年第 46 题、2025 年第 45 题)
- 历年总考查频次:10 次(统考历史考查包含 2009 年第 45 题、2011 年第 45 题、2013 年第 45 题、2014 年第 46 题、2015 年第 45 题、2019 年第 43 题、2020 年第 45 题、2021 年第 45 题、2022 年第 46 题、2025 年第 45 题)
- 出题形式:综合解答题(以 7~8 分的算法设计与系统机制分析大题呈现)
2. 命题特点分析¶
- 出题频率极高且规律显著:进程同步问题设计是 408 操作系统综合大题中分量最重、命题率最高的王牌考点。近十年考查 5 次,平均每两年必考一道大题,2019 至 2022 年甚至出现连续四年考查的局面。
- 现实工程与生活场景深度融合:早期试题偏向教科书经典模型的直接复现(如生产者-消费者、读者-写者、理发师、吸烟者),近几年命题全面转向“现实业务流抽象”。例如 2019 年哲学家就餐问题增加公用碗限制、2022 年多线程前驱依赖关系、2025 年植树流水线多工序多资源协调。
- 兼顾代码编写规范与底层硬件机制:既考查高层信号量并发控制逻辑(如 P/V 操作嵌套次序、死锁规避、最少信号量设计),又考查底层整型与记录型信号量的原子实现、开/关中断等硬件控制机理(如 2021 年第 45 题)。
- 评分标准高度关注边界与防死锁设计:阅卷核心扣分点集中在:信号量物理含义及初值说明不全、同步与互斥 P 操作次序颠倒、未考虑死锁环路条件、同一线程内添加冗余信号量。
3. 近十年考查年份分布表格¶
+--------------+----------+----------+----------+----------+----------+----------+----------+----------+----------+----------+
| 年份 | 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 | 2024 | 2025 |
+--------------+----------+----------+----------+----------+----------+----------+----------+----------+----------+----------+
| 考查题号 | -- | -- | -- | 43题 | 45题 | 45题 | 46题 | -- | -- | 45题 |
+--------------+----------+----------+----------+----------+----------+----------+----------+----------+----------+----------+
| 题型分值 | -- | -- | -- | 解答(8分)| 解答(7分)| 解答(7分)| 解答(8分)| -- | -- | 解答(7分)|
+--------------+----------+----------+----------+----------+----------+----------+----------+----------+----------+----------+
二、 具体考察内容¶
1. 核心概念与工作机制¶
(1) 并发环境下的制约机制¶
- 间接相互制约(互斥访问):多个并发进程因竞争同一排他性共享资源(临界资源)而产生的制约关系。一个进程正在临界区执行时,其他试图进入临界区的进程必须等待。
- 直接相互制约(时序同步):并发进程为了协调推进时序,相互等待对方发送信号或完成特定前驱操作而建立的执行次序依赖。
(2) 临界区访问准则¶
任何有效的互斥控制机制必须严格遵守以下四项基本准则: - 空闲让进:临界区空闲时,应允许一个请求进入临界区的进程立即进入。 - 忙则等待:已有进程处于临界区内时,其他试图进入的进程必须等待。 - 有限等待:对请求访问临界区的进程,应保证能在有限时间内进入,防止进程饥饿。 - 让权等待:进程不能进入临界区时,应立即释放 CPU 控制权,避免忙等待(整型信号量违背该准则,记录型信号量满足该准则)。
(3) 记录型信号量机制¶
记录型信号量(Counting Semaphore)通过引入进程阻塞等待队列,消除了忙等待。其数据结构定义如下:
底层原子操作语义:
- wait(S) 操作(即 P(S) 操作):
$\(S.value = S.value - 1;\)$
若 \(S.value < 0\)$ \text{,调用进程执行 block() 原语,自我阻塞并插入到等待队列} $\(S.list\) 中,转为阻塞态,主动放弃 CPU。
- signal(S) 操作(即 V(S) 操作):
$\(S.value = S.value + 1;\)$
若 \(S.value \le 0\)$ \text{,表明队列中仍有进程处于等待状态,调用 wakeup() 原语从等待队列} $\(S.list\) 中唤醒一个等待进程,将其转为就绪态。
2. 核心定理推导与数学/算法模型¶
(1) 信号量数值状态模型¶
设信号量初始值为 \(S_0\): - 若 \(S.value > 0\):\(S.value\) 的绝对值表示当前系统中可用临界资源的空闲单位数量。 - 若 \(S.value = 0\):表示系统中的临界资源已被分配完毕,且当前无进程处于阻塞等待状态。 - 若 \(S.value < 0\)$ \text{:表示系统中的临界资源已耗尽,且} $\(|S.value|\) 的绝对值精确等于当前阻塞在该信号量等待队列中的进程数目。
信号量取值范围定理:若 \(n\)$ \text{个并发进程共享初始值为} $\(m\)(\(m \ge 1\)$ \text{)的某类临界资源,则在任意合法运行状态下,该信号量} $\(S\) 的取值范围满足: $\(S \in [m - n, m]\)$ - 当所有 \(n\)$ \text{个进程均未申请该资源时,} $\(S = m\); - 当所有 \(n\)$ \text{个进程均请求该资源时,前} $\(m\)$ \text{个进程成功分配,后} $\(n - m\)$ \text{个进程进入等待队列,此时} $\(S = m - n\)。
(2) 前驱图(Precedence Graph)映射模型¶
设并发任务由有向无环图 \(G = (V, E)\)$ \text{描述,其中节点} $\(u \in V\)$ \text{表示基本操作,有向边} $\((u, v) \in E\)$ \text{表示操作} $\(u\)$ \text{必须在操作} $\(v\) 开始之前完成。
- 跨并发实体的边映射规则:对于跨越不同进程(线程)的每条边 \((u, v)\)$ \text{,分配一个唯一的同步信号量} $\(S_{uv}\),初始值设为 0。
- 节点执行时序规则:
- 在节点 \(u\) 的操作完成后,调用 signal(S_uv) 发送完成信号;
- 在节点 \(v\) 的操作开始前,调用 wait(S_uv) 等待前驱完成信号。
- 同实体内部时序规则:若节点 \(u\)$ \text{与节点} $\(v\) 属于同一个线程内部且存在先后顺序,依赖程序计数器与代码顺序自然保序,禁止引入多余的信号量。
(3) 有限缓冲区生产者-消费者模型¶
设缓冲区容量上限为 \(N\):
- 资源不变式:在任意稳态下,空闲缓冲区数与已用缓冲区数满足:
$\(empty + full = N\)$
初始时 \(empty = N\),\(full = 0\)。
- P 操作嵌套核心定理:
在生产者和消费者进程中,若同时存在同步信号量(如 empty、full)和互斥信号量(mutex),必须严格先执行同步 P 操作,再执行互斥 P 操作:
wait(mutex); wait(empty);。当缓冲区满(\(empty = 0\))时,生产者进程先成功获取锁 wait(mutex),随后在 wait(empty) 处发生阻塞。此时消费者进程试图消费数据以释放空位,但在执行 wait(mutex) 时因锁已被生产者持有而阻塞。系统进入相互无限等待状态,引发不可逆死锁。
(4) 哲学家就餐防死锁定理¶
\(n\)$ \text{位哲学家围坐圆桌,共有} $\(n\) 根筷子,每人必须同时获取左、右两根筷子才能进餐。 - 死锁环路条件:若所有哲学家同时拿起左侧筷子,系统形成环路等待链: $\(Philosopher_i \to Chopstick_{(i+1) \bmod n} \to Philosopher_{(i+1) \bmod n}\)$ - 破环并发度控制模型: 通过引入计数信号量限制最多允许 \(k\) 位哲学家同时竞争筷子。根据抽屉原理,只要保证: $\(k \le n - 1\)$ 则在 \(k\) 位哲学家中,至少有 1 位哲学家能同时集齐两根筷子完成进餐,破坏死锁的“循环等待”条件。 - 碗资源拓展模型(2019#43): 当系统同时引入 \(m\) 个公用碗时,就餐的并发度受碗数量与防死锁并发度的双重制约。控制并发就餐的信号量上限必须满足: $\(Plate = \min(m, n - 1)\)$
3. 核心对比辨析¶
表 2-1:整型信号量与记录型信号量机制对比¶
| 对比维度 | 整型信号量(Integer Semaphore) | 记录型信号量(Record Semaphore) |
|---|---|---|
| 数据结构构成 | 单一整型变量 \(S\)$ \text{ | 整型变量} $\(S.value\)$ \text{+ 阻塞进程队列指针} $\(S.list\) |
| P 操作等待方式 | while (S <= 0); 忙等待循环消耗 CPU |
block() 原语使进程主动放弃 CPU 并挂起 |
| 让权等待准则 | 不满足(违背让权等待) | 严格满足 |
| V 操作行为 | 仅执行数值自增 \(S = S + 1\)$ \text{ | 自增后检查} $\(S.value \le 0\),调用 wakeup() 唤醒阻塞进程 |
| 单处理机适用性 | 在未关中断时极易死循环;关中断后陷入不可逆死锁 | 适用于多任务抢占式及非抢占式调度系统 |
表 2-2:互斥信号量与同步信号量机制对比¶
| 对比维度 | 互斥信号量(Mutex) | 同步信号量(Synchronization) |
|---|---|---|
| 初始值设定 | 通常为 1(表示临界资源可用数为 1) | 通常为 0(前驱同步)或资源容量 \(N\)(缓冲区配额) |
| P/V 操作空间分布 | P 操作与 V 操作必须出现在同一进程的同一逻辑块的两端 | P 操作与 V 操作分布在不同协作进程的代码中 |
| 执行物理语义 | 加锁(申请访问权)与解锁(归还访问权) | 等待前驱操作完成信号与发送操作完成信号 |
| 对调嵌套风险 | 处于内层(临界区入口) | 处于外层(资源分配入口),不可颠倒 |
表 2-3:并发互斥实现机制演进对比¶
| 机制类型 | 实现方式 | 运行特权级别 | 缺点与适用边界 |
|---|---|---|---|
| 软件算法 | Peterson 算法、Dekker 算法 | 用户态 | 仅支持两进程,存在忙等待,依赖内存强一致顺序 |
| 硬件开关中断 | cli(关中断)/ sti(开中断) |
内核态(特权指令) | 用户程序不可用;多核处理机无效;滥用导致系统调度瘫痪 |
| 硬件原子指令 | TSL(Test-and-Set)、Swap/XCHG | 用户态可通过指令调用 | 硬件总线锁定,存在忙等待,未实现让权等待 |
| 系统信号量 | 记录型信号量结合调度器原语 | 内核管理 | 具有系统调用开销,但彻底解决让权等待与复杂拓扑同步 |
三、 近十年真题精讲(2016~2025)¶
【真题 1】2019 年 408 第 43 题 · 哲学家就餐模型变式与死锁规避¶
题目¶
有 \(n\)(\(n \ge 3\)$ \text{)位哲学家围坐在一张圆桌边,每位哲学家交替地就餐和思考。在圆桌中心有} $\(m\)(\(m \ge 1\))个碗,每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后,才能就餐,进餐完毕,将碗和筷子放回原位,并继续思考。为使尽可能多的哲学家同时就餐,且防止出现死锁现象,请使用信号量的 P、V 操作(wait()、signal() 操作)描述上述过程中的互斥与同步,并说明所用信号量及初值的含义。
【解析】¶
- 知识定位:本题考查经典哲学家就餐问题的资源拓扑建模、多类型临界资源申请次序以及死锁预防机制。
- 临界资源与约束分析:
- 筷子资源:共有 \(n\)$ \text{根筷子,编号为} $\(0 \sim n-1\)$ \text{。第} $\(i\)$ \text{位哲学家左手侧筷子编号为} $\(i\)$ \text{,右手侧筷子编号为} $\((i + 1) \bmod n\)。相邻哲学家互斥共享一根筷子。由于每位哲学家需要两根特定筷子,使用初值全为 1 的信号量数组
chopstick[n]实现互斥。 - 碗资源与死锁规避:圆桌中心有 \(m\) 个公用碗,就餐必须取一个碗。
- 若 \(m < n\)$ \text{:公用碗的数量天然构成了并发就餐人数的上限。因为最多只有} $\(m\)$ \text{位哲学家能同时取到碗,而} $\(m \le n - 1\)$ \text{,此时至多有} $\(n - 1\) 位哲学家同时竞争两侧的筷子,根据抽屉原理,必有一人能同时拿到两侧筷子,死锁自然被破坏。
- 若 \(m \ge n\)$ \text{:若简单将碗信号量初值设为} $\(m\)$ \text{,则可能出现} $\(n\)$ \text{位哲学家每人拿一个碗,且每人拿起左手侧一根筷子,导致全部等待右手侧筷子的循环死锁。因此,为防止死锁,必须限制同时竞争筷子的哲学家数不超过} $\(n - 1\)。
- 综合两项约束,为使“尽可能多的哲学家同时就餐”且“防止死锁”,限制进入取筷阶段的信号量初值必须精确取为 \(\min(m, n - 1)\)。
- P/V 嵌套次序:必须先获取碗(控制并发度入口),再互斥申请左、右两侧筷子。释放资源时先归还筷子,最后归还碗。
【标准参考解答】¶
(1) 信号量定义及初值说明:
- semaphore chopstick[n];:互斥信号量数组,chopstick[i] 表示编号为 \(i\)$ \text{的筷子是否可用,初值全部为 1(} $\(i = 0, 1, \dots, n-1\))。
- semaphore bowl;:计数信号量,用于控制可同时就餐的哲学家数量上限,既表示碗的可用配额,又起到破除死锁环路的作用。其初值设为 \(\min(m, n - 1)\)。
(2) 哲学家进程算法描述:
semaphore chopstick[n] = {1, 1, ..., 1};
semaphore bowl = min(m, n - 1);
void philosopher(int i) { // 哲学家编号 i 取值范围: 0 至 n - 1
while (1) {
think(); // 思考
wait(bowl); // 申请碗(同时限制并发数,防止死锁)
wait(chopstick[i]); // 申请左侧筷子
wait(chopstick[(i + 1) % n]); // 申请右侧筷子
eat(); // 进餐
signal(chopstick[(i + 1) % n]); // 释放右侧筷子
signal(chopstick[i]); // 释放左侧筷子
signal(bowl); // 归还碗,释放就餐名额
}
}
【真题 2】2020 年 408 第 45 题 · 多进程前驱图同步设计¶
题目¶
现有 5 个操作 A、B、C、D 和 E,操作 C 必须在 A 和 B 完成后执行,操作 E 必须在 C 和 D 完成后执行,请使用信号量的 wait()、signal() 操作(P、V 操作)描述上述操作之间的同步关系,并说明所用信号量及其初值。
【解析】¶
- 知识定位:本题考查基于有向无环图(DAG)的多进程纯前驱同步机制设计。
- 前驱关系剖析:
- 依赖条件一:操作 C 必须在 A 和 B 完成后执行 \(\implies\)$ \text{存在有向边} $\(A \to C\)$ \text{和} $\(B \to C\);
- 依赖条件二:操作 E 必须在 C 和 D 完成后执行 \(\implies\)$ \text{存在有向边} $\(C \to E\)$ \text{和} $\(D \to E\)。
- 信号量分配策略: 每一个跨操作的单向先行制约关系对应一个独立的同步信号量,初值均设为 0:
- \(S_{AC}\):表示 A 已执行完毕,用于 A 与 C 之间的同步,初值为 0;
- \(S_{BC}\):表示 B 已执行完毕,用于 B 与 C 之间的同步,初值为 0;
- \(S_{CE}\):表示 C 已执行完毕,用于 C 与 E 之间的同步,初值为 0;
- \(S_{DE}\):表示 D 已执行完毕,用于 D 与 E 之间的同步,初值为 0。
- 执行控制流设计:
- 操作 A:完成自身计算后触发
signal(S_AC); - 操作 B:完成自身计算后触发
signal(S_BC); - 操作 C:必须同时等待 A 与 B 的完成信号
wait(S_AC)、wait(S_BC),执行自身操作后触发signal(S_CE); - 操作 D:完成自身计算后触发
signal(S_DE); - 操作 E:必须同时等待 C 与 D 的完成信号
wait(S_CE)、wait(S_DE),随后执行操作 E。
【标准参考解答】¶
(1) 信号量定义及初值说明:
- semaphore S_AC = 0;:表示操作 A 是否完成,用于控制操作 C 的启动,初值为 0。
- semaphore S_BC = 0;:表示操作 B 是否完成,用于控制操作 C 的启动,初值为 0。
- semaphore S_CE = 0;:表示操作 C 是否完成,用于控制操作 E 的启动,初值为 0。
- semaphore S_DE = 0;:表示操作 D 是否完成,用于控制操作 E 的启动,初值为 0。
(2) 各操作的同步实现:
semaphore S_AC = 0;
semaphore S_BC = 0;
semaphore S_CE = 0;
semaphore S_DE = 0;
void Process_A() {
操作 A;
signal(S_AC); // 通知操作 C:A 已完成
}
void Process_B() {
操作 B;
signal(S_BC); // 通知操作 C:B 已完成
}
void Process_C() {
wait(S_AC); // 等待操作 A 完成
wait(S_BC); // 等待操作 B 完成
操作 C;
signal(S_CE); // 通知操作 E:C 已完成
}
void Process_D() {
操作 D;
signal(S_DE); // 通知操作 E:D 已完成
}
void Process_E() {
wait(S_CE); // 等待操作 C 完成
wait(S_DE); // 等待操作 D 完成
操作 E;
}
【真题 3】2021 年 408 第 45 题 · 信号量底层互斥机制与开/关中断分析¶
题目¶
下表给出了整型信号量 S 的 wait() 和 signal() 操作的功能描述,以及采用开/关中断指令实现信号量操作互斥的两种方法。
| 功能描述 | 方法 1 | 方法 2 |
|---|---|---|
Semaphore S;wait(S) {while (S <= 0);S = S - 1;}signal(S) {S = S + 1;} |
Semaphore S;wait(S) {关中断;while (S <= 0);S = S - 1;开中断;}signal(S) {关中断;S = S + 1;开中断;} |
Semaphore S;wait(S) {关中断;while (S <= 0) {开中断;关中断;}S = S - 1;开中断;}signal(S) {关中断;S = S + 1;开中断;} |
请回答下列问题。 (1) 为什么在 wait() 和 signal() 操作中对信号量 S 的访问必须互斥执行? (2) 分别说明方法 1 和方法 2 是否正确。若不正确,请说明理由。 (3) 用户程序能否使用开/关中断指令实现临界区互斥?为什么?
【解析】¶
- 知识定位:本题考查信号量底层实现的原子性保障机理、关中断导致的死锁反例推演以及操作系统特权级保护机制。
- 问题 (1) 剖析:
信号量 \(S\)$ \text{是被所有并发进程共享的公共全局变量。
wait()中的S = S - 1与signal()中的S = S + 1在机器指令级别均包含“读内存到寄存器} $\(\to\)$ \text{寄存器运算} $\(\to\)$ \text{写回内存”多步非原子操作。若不对访问过程实施互斥保护,并发交叉执行将破坏操作的原子性,引发竞争条件(Race Condition),导致} $\(S\) 的计数值失真,进而彻底瓦解整个同步互斥机制。 - 问题 (2) 剖析:
- 方法 1 判定与理由:错误。在
wait()中,进程首先执行“关中断”,随后进入while (S <= 0);循环。若当前 \(S \le 0\)$ \text{,CPU 将在关中断状态下进入死循环。由于中断已被屏蔽,系统无法响应时钟中断,无法发生进程调度;在单处理机环境下,其他能够执行signal()释放资源的进程永远无法获得 CPU,导致} $\(S\) 的值永远不可能增加,系统彻底陷入死锁。 - 方法 2 判定与理由:正确。方法 2 在
while (S <= 0)循环体内部加入了开中断; 关中断;。当 \(S \le 0\)$ \text{时,进程在开中断的瞬间允许 CPU 响应外部中断并引发进程调度,使得执行signal()的进程有机会运行并修改} $\(S\)$ \text{的值;随后再次关中断安全地检测条件,既保证了每次读写} $\(S\) 时的互斥性,又避免了关中断死循环导致的系统死锁。 - 问题 (3) 剖析: 不能。开中断与关中断指令属于特权指令,只能在操作系统的内核态(管态)下执行,用户程序运行在用户态(目态),无权执行特权指令(若在用户态执行将触发硬件异常并陷入内核)。若允许用户程序自由使用关中断指令,一旦某个用户程序关中断后发生死循环或恶意不执行开中断,整个操作系统将彻底丧失抢占调度能力,威胁整个计算机系统的安全稳定。
【标准参考解答】¶
(1)
信号量 \(S\)$ \text{是可被多个并发进程共享访问的临界变量。多个进程均可通过 wait() 和 signal() 对} $\(S\) 进行读、写与修改操作。若不互斥执行,多进程并发交替读写将发生指令交织,破坏操作的原子性,导致竞争条件并产生错误的信号量值,从而无法保证正确的同步互斥功能。
(2)
- 方法 1 错误。理由:在 wait() 操作中,若 \(S \le 0\)$ \text{,进程执行关中断后陷入 while (S <= 0); 忙等待。由于中断已被屏蔽,单处理机系统无法进行进程调度,其他进程无法运行并执行 signal() 来增加} $\(S\) 的值,导致该进程在关中断状态下永久陷入死循环,引发系统死锁。
- 方法 2 正确。理由:方法 2 在 while (S <= 0) 循环体内执行了开中断操作。当 \(S \le 0\)$ \text{时,开中断使得 CPU 能够响应时钟等中断并调度其他进程执行,从而允许其他进程运行 signal() 修改} $\(S\) 的值,打破循环等待条件,避免系统死锁。
(3) 不能。因为开中断指令和关中断指令都属于特权指令,只能在内核态下执行,用户程序运行在用户态,无权执行特权指令(执行将触发特权指令异常并被操作系统终止)。若允许用户程序随意关中断,恶意或有缺陷的用户程序一旦关中断后不再开中断,将剥夺系统的调度能力,导致整个操作系统瘫痪。
【真题 4】2022 年 408 第 46 题 · 多线程前驱约束与内部时序同步¶
题目¶
某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E 和 F 共 6 个操作,其中 T1 执行 A、E 和 F,T2 执行 B、C 和 D。下图表示上述 6 个操作的执行顺序所必须满足的约束:C 在 A 和 B 完成后执行,D 和 E 在 C 完成后执行,F 在 E 完成后执行。请使用信号量的 wait()、signal() 操作描述 T1 和 T2 之间的同步关系,并说明所用信号量的作用及其初值。
+---+ +---+
| A | | B |
+---+ +---+
\ /
\ /
v v
+---+
| C |
+---+
/ \
/ \
v v
+---+ +---+
| D | | E |
+---+ +---+
|
v
+---+
| F |
+---+
【解析】¶
- 知识定位:本题考查多线程拓扑约束下的最简同步设计,核心考核能否准确剔除“线程内部自然时序”,仅对“跨线程时序”设立信号量。
- 操作所属线程划分:
- 线程 T1 负责执行:操作 A、操作 E、操作 F;
- 线程 T2 负责执行:操作 B、操作 C、操作 D。
- 时序依赖关系精细甄别:
- 约束 1(B \(\to\) C):操作 B 和 C 均由线程 T2 执行。在 T2 代码中将
B;写在C;之前即可保证严格顺序,属于线程内部时序,无需任何信号量。 - 约束 2(A \(\to\)$ \text{C):操作 A 由 T1 执行,操作 C 由 T2 执行。属于跨线程前驱制约,必须设置同步信号量} $\(S_{AC}\),初始值为 0。T1 完成 A 后释放信号,T2 执行 C 前等待该信号。
- 约束 3(C \(\to\) D):操作 C 和 D 均由线程 T2 执行。在 T2 代码中将
C;写在D;之前即可保证顺序,属于线程内部时序,无需任何信号量。 - 约束 4(C \(\to\)$ \text{E):操作 C 由 T2 执行,操作 E 由 T1 执行。属于跨线程前驱制约,必须设置同步信号量} $\(S_{CE}\),初始值为 0。T2 完成 C 后释放信号,T1 执行 E 前等待该信号。
- 约束 5(E \(\to\) F):操作 E 和 F 均由线程 T1 执行。在 T1 代码中将
E;写在F;之前即可保证顺序,属于线程内部时序,无需任何信号量。 - 易错避坑总结: 若考生为 B \(\to\) C、C \(\to\) D、E \(\to\) F 也定义了信号量,说明没有理解单线程指令流的串行保序特征,会因设计冗余而失分。
【标准参考解答】¶
(1) 信号量定义及初值说明:
- semaphore AC = 0;:表示操作 A 是否执行完毕,用于 T1 向 T2 发送同步信号,初值为 0。
- semaphore CE = 0;:表示操作 C 是否执行完毕,用于 T2 向 T1 发送同步信号,初值为 0。
(注:B 与 C、C 与 D 的执行顺序由线程 T2 内部的代码顺序保证;E 与 F 的执行顺序由线程 T1 内部的代码顺序保证,均无需额外定义信号量。)
(2) 线程 T1 与 T2 的代码实现:
semaphore AC = 0;
semaphore CE = 0;
void Thread_T1() {
操作 A;
signal(AC); // 通知 T2:操作 A 已执行完毕
wait(CE); // 等待 T2 完成操作 C
操作 E;
操作 F;
}
void Thread_T2() {
操作 B;
wait(AC); // 等待 T1 完成操作 A
操作 C;
signal(CE); // 通知 T1:操作 C 已执行完毕
操作 D;
}
【真题 5】2025 年 408 第 45 题 · 植树流水线与多资源协同互斥设计¶
题目¶
三个人一起植树,甲挖坑,乙放树苗入坑并填土,丙负责为新种树苗浇水。步骤依次为:挖树坑,放树苗,填土和浇水。现在有铁锹和水桶各一个,铁锹用于挖树坑,填土。水桶用于浇水。当树坑数量小于 3 时,甲才可以挖树坑。设初始坑 = 0,铁锹水桶均可用,定义尽可能少的信号量,用 wait() 和 signal() 操作描述植树过程中三人的同步互斥关系,并说明所用信号量的作用及其初值。
【解析】¶
- 知识定位:本题考查多阶段流水线同步模型、有限容量缓冲区配额控制、多共享互斥资源分配以及最简信号量设计原则。
- 实体角色与工序拆解:
- 甲(挖树坑):需使用铁锹。前置条件:未填土的树坑数小于 3(树坑缓冲容量上限为 3)。
- 乙(放树苗、填土):需已有挖好的树坑。放树苗无需工具,填土需使用铁锹。乙完成填土后释放树坑空间,并产生一棵待浇水的新树苗。
- 丙(浇水):需有新种好的树苗,需使用水桶。
- 共享资源与制约关系精确分析:
- 铁锹(互斥资源):甲(挖树坑)与乙(填土)需要竞争同一把铁锹,属于临界资源,必须设置互斥信号量
mutex_shovel,初值为 1。 - 树坑数量控制(有界缓冲区同步):
- 题设“当树坑数量小于 3 时,甲才可以挖树坑”,说明甲挖坑产生树坑,乙填土消耗树坑,树坑池容量上限为 3,初始坑数为 0。
- 需定义两个信号量进行容量控制:
empty_pits:表示当前允许继续挖坑的空位配额,初值为 3;full_pits:表示已挖好但尚未填土的树坑数量,初值为 0。
- 浇水树苗(前驱同步关系):
- 乙填土完成后,新种树苗产生,通知丙浇水。需设置同步信号量
trees,表示待浇水的树苗数,初值为 0。
- 乙填土完成后,新种树苗产生,通知丙浇水。需设置同步信号量
- 水桶(独占资源甄别):
- 水桶仅供丙浇水使用,甲和乙均不使用水桶。既然只有丙一人顺序使用水桶,不存在多并发实体的竞争,因此无需为水桶设置互斥信号量。这完全契合题目“定义尽可能少的信号量”的严格要求。
- P/V 操作顺序校验:
- 甲必须先申请挖坑名额
wait(empty_pits),再互斥申请铁锹wait(mutex_shovel)。若颠倒,甲在坑满时霸占铁锹阻塞,乙因无铁锹无法填土腾出坑位,导致死锁。 - 乙获取已有树坑
wait(full_pits),放入树苗,随后申请铁锹wait(mutex_shovel)填土。释放铁锹后,执行signal(empty_pits)恢复坑位配额,并执行signal(trees)唤醒丙。
【标准参考解答】¶
(1) 信号量定义及初值说明:
- semaphore empty_pits = 3;:表示允许甲继续挖树坑的容量配额,初值为 3(保证未填土的树坑数小于 3)。
- semaphore full_pits = 0;:表示已挖好、等待乙放树苗与填土的树坑数量,初值为 0。
- semaphore mutex_shovel = 1;:互斥信号量,用于甲与乙互斥使用铁锹,初值为 1。
- semaphore trees = 0;:表示已填土完毕、等待丙浇水的新树苗数量,初值为 0。
(注:水桶仅由丙一人在浇水时使用,不存在多进程并发竞争,故无需为水桶设置互斥信号量,满足题目定义尽可能少信号量的要求。)
(2) 三人协作过程的算法描述:
semaphore empty_pits = 3;
semaphore full_pits = 0;
semaphore mutex_shovel = 1;
semaphore trees = 0;
void Person_Jia() { // 甲:负责挖树坑
while (1) {
wait(empty_pits); // 检查树坑配额(保证树坑数量小于 3)
wait(mutex_shovel); // 互斥申请铁锹
挖树坑;
signal(mutex_shovel);// 释放铁锹
signal(full_pits); // 增加一个已挖好的树坑
}
}
void Person_Yi() { // 乙:负责放树苗入坑并填土
while (1) {
wait(full_pits); // 等待有挖好的树坑
放树苗入坑;
wait(mutex_shovel); // 互斥申请铁锹
填土;
signal(mutex_shovel);// 释放铁锹
signal(empty_pits); // 释放一个树坑配额,允许甲继续挖坑
signal(trees); // 通知丙有一棵新树苗可以浇水
}
}
void Person_Bing() { // 丙:负责浇水
while (1) {
wait(trees); // 等待有新填土的树苗
使用水桶浇水;
}
}
四、 综合考法拓展¶
1. 综合大题解题标准化五步法¶
+-------------------------------------------------------------+
| 步骤一:识别并发实体(提取进程/线程数量,确定是一次性还是 while(1) 循环)|
+-------------------------------------------------------------+
|
v
+-------------------------------------------------------------+
| 步骤二:梳理两大制约关系(互斥:排他临界资源;同步:先后时序与缓冲容量) |
+-------------------------------------------------------------+
|
v
+-------------------------------------------------------------+
| 步骤三:定义信号量(精炼命名、准确阐述物理含义、严格推导初始值) |
+-------------------------------------------------------------+
|
v
+-------------------------------------------------------------+
| 步骤四:代码骨架设计(严格遵循“先同步/资源后互斥锁,临界区极小化”原则)|
+-------------------------------------------------------------+
|
v
+-------------------------------------------------------------+
| 步骤五:死锁自查与优化(验证对称竞争死锁环路、剔除单实体内部冗余信号量)|
+-------------------------------------------------------------+
(1) 步骤一:识别并发实体与生命周期¶
- 明确题目包含哪些独立并发运行的角色(如读者/写者、甲/乙/丙、线程T1/T2)。
- 判断执行模式:
- 持续流水线型(如 2019 哲学家、2025 植树):主逻辑必须包含在
while (1)循环体内; - 任务图一次性执行型(如 2020 前驱图、2022 线程时序):按单次函数调用书写,不可加入死循环。
(2) 步骤二:梳理两大制约关系¶
- 互斥制约:哪些硬件设备或共享内存变量同一时刻只允许一个进程访问(如铁锹、打印机、计数变量)。
- 同步制约:
- 单向执行先后次序(\(A\)$ \text{必须先于} $\(B\) 完成);
- 缓冲区容量约束(生产受空位限制,消费受产品数量限制)。
(3) 步骤三:规范定义信号量及初值¶
- 每个信号量必须具备三要素:变量类型与名称、明确的物理含义、严密的初始值。
- 初值设定准则:
- 互斥锁初值必为 1;
- 单向前驱同步初值必为 0;
- 缓冲容量配额初值必为上限容量 \(N\);
- 已就绪产品/任务数初值必为初始已存量(通常为 0)。
(4) 步骤四:精准布置 P/V 序列¶
- 入临界区次序:必须
wait(资源/同步信号量)在外,wait(互斥信号量)在内。 - 出临界区次序:必须尽快执行
signal(互斥信号量)释放锁,缩小临界区跨度,再执行signal(资源/同步信号量)唤醒下游。
(5) 步骤五:死锁自查与规范校验¶
- 检查是否存在交叉死锁:如两个进程分别以
wait(A); wait(B);和wait(B); wait(A);申请资源。 - 检查单线程内部顺序是否误加了同步信号量。
2. 经典四大考查模型的迁移与变形套路¶
(1) 生产者-消费者模型的延伸变形¶
- 多类产品/多缓冲池模式:例如奇偶数缓冲池问题、水质检测多工序问题。
- 解题要点:各类产品设置独立的计数信号量,但若共享同一存储物理块,需统一受同一互斥锁保护。
- 流水线串联模式(如 2025 植树问题):
- 中间角色(如乙)既是上游工序的消费者,又是下游工序的生产者;
- 必须同时持有上游消费品信号量与自身下游生产容量信号量。
(2) 读者-写者模型的延伸变形¶
- 读优先(经典模型):第一个读者加锁,最后一个读者解锁;可能导致写者饥饿。
- 写优先/读写公平模型:
- 引入一个额外的信号量
w_mutex或queue,读者与写者在进入前均需排队。当写者到达后,后续新到的读者将被阻塞在该队列上,从而保证写者不会长期饥饿。
(3) 哲学家就餐模型的延伸变形¶
- 解法一(限制并发度,如 2019#43):使用计数信号量限制并发人数不超过 \(n-1\)。
- 解法二(奇偶编号偏序策略):规定奇数号哲学家先拿左侧筷子后拿右侧筷子,偶数号哲学家先拿右侧筷子后拿左侧筷子,打破全局同向循环等待链。
- 解法三(原子申请策略/AND 信号量):利用互斥信号量保证一位哲学家在拿筷子时具有排他性,要么两根同时拿到,要么一根都不拿。
五、 考点速记清单¶
1. 核心要点速记¶
- 信号量数值小于 0 时,其绝对值精确等于该信号量阻塞队列中的进程数。
- 整型信号量由于存在
while (S <= 0);忙等待,违背让权等待准则。 - 记录型信号量利用
block()原语让出 CPU,严格满足让权等待准则。 - 关中断与开中断指令是特权指令,用户态程序禁止执行。
- 单线程内部天然具备先后时序,切忌跨语句增设冗余同步信号量。
- 互斥信号量 P/V 操作必须在同一进程配对;同步信号量 P/V 操作分别位于不同协作进程。
2. 常用信号量初值设定速查表¶
| 场景模型 | 信号量类型 | 推荐命名 | 标准初值 | 典型物理含义 |
|---|---|---|---|---|
| 临界区互斥 | 互斥信号量 | mutex |
1 |
临界资源空闲,允许 1 个进程进入 |
| 单向前驱 | 同步信号量 | S 或 done |
0 |
前驱任务尚未完成 |
| 有限缓冲容量 | 同步/计数信号量 | empty |
N |
缓冲区尚有 \(N\) 个空位可供写入 |
| 缓冲产品存量 | 同步/计数信号量 | full |
0 |
缓冲区初始有 0 个成品可供消费 |
| 哲学家防死锁 | 并发控制信号量 | plate / quota |
min(m, n-1) |
限制同时竞争筷子的最大人数 |
3. 临界区与 P/V 操作四大避坑准则¶
- 准则一:先同步,后互斥。绝不能先拿互斥锁再等同步资源,否则在资源耗尽时必引发现场死锁。
- 准则二:先互斥,后同步释放。退出临界区时,必须先释放互斥锁,再发信号通知等待资源的进程,以最大化系统并发吞吐量。
- 准则三:同体保序无需锁。同一进程(线程)内部先后执行的语句块,绝对不要定义信号量。
- 准则四:独占资源无需锁。仅有一个并发实体使用的硬件资源(如 2025 年真题中的水桶),绝对不可盲目添加互斥信号量。
4. 考场解题核心口诀¶
前驱画图边定锁,单向前行初值零;
多进互斥初值为一,临界资源独占行。
先同后斥防死锁,嵌套颠倒全盘崩;
同体保序莫滥设,少用信号显奇功。