一、 深度突破:到底什么是“中间产物”?怎么精准提取?
1. “中间产物”的物理本质
在操作系统中,同步关系的本质就是“事件发生”或“半成品的传递”。
所谓的“中间产物”,就是上一道工序完成后交出的“半成品实体”或“就绪标志”。后一道工序没有拿到这个半成品,手里就没活可干,必须被操作系统挂起(阻塞)。
2. 审题提取公式:【动词 + 名词】拆解法
在题目中找工序交接点,提炼为:【前序动词】了【某个名词】 形成【中间产物】 供【后序动词】消耗。
| 题目真实情境 | 前序工序(生产) | 产生的“中间产物”(名词) | 对应同步信号量含义 | 后序工序(消耗) |
|---|---|---|---|---|
| 植树问题 | 甲 挖 树坑 | 树坑(已挖好、还没填土的坑) | dug_holes(已挖好待填的坑数) | 乙 填 土 |
| 植树问题 | 乙 填 好土 | 树苗(已填土、还没浇水的树) | planted_trees(已填好待浇的树数) | 丙 浇 水 |
| 流水线装配 | 工人 A 加工 零件 | 零件(已加工完、待组装的零件) | parts(待组装的零件个数) | 工人 B 组装 成品 |
| 车间喷漆 | 工人甲 组装 车架 | 车架(裸车架,待喷漆) | frames(待喷漆车架数) | 工人乙 喷 漆 |
3. 中间产物信号量的三大铁律
-
初值必须设为 0:
-
考题开头通常有隐含条件(或明确说明):“初始时无任何半成品”。
-
产物数量初值为 0,后序工序一上来执行
wait(产物)就会立刻让计数器变为 -1,直接安全阻塞,完美保证了“前序不干完,后序绝不能抢跑”。
-
-
生产端是增量,消耗端是减量:
-
前序工序把活干完:执行一次
signal(产物),产物数量加 1,唤醒后序。 -
后序工序开工之前:执行一次
wait(产物),产物数量减 1,没产物就睡觉。
-
-
一个工序链有 个环节,就有 类中间产物:
-
甲 乙 丙(3 个角色,2 次接力):必须有 2 个中间产物信号量(
甲给乙的、乙给丙的)。
-
二、 破题四步法(标准解题流水线)
Plaintext
第1步:提取工序链与“中间产物”(找同步:谁产出、谁等待)
工序A --[生产产物1]--> 工序B --[生产产物2]--> 工序C
初值一律为 0;A 产出 signal(产物1);B 开工 wait(产物1)
↓
第2步:判定容量/配额约束(找缓冲区上限:空间信号量)
题干是否有“最多堆积/容纳 N 个”的限制?
初值设为 N;生产前 wait(配额);彻底消耗后 signal(配额)
↓
第3步:盘点独占物理工具(找互斥资源:工具信号量)
工具是否被 ≥2 个不同的角色争抢?
若有竞争,设 mutex = 1;借工具 wait(mutex);还工具 signal(mutex)
↓
第4步:实施信号量极简化(排查扣分暗坑)
单人独占工具严禁设信号量;严格核对“先配额后拿锁”防死锁。
三、 四步法通识深度解析
步骤 1:同步关系(抓中间产物)
-
依据上面的公式提取各级半成品,有几个环节交接就设几个同步信号量,初值全部为 0。
步骤 2:容量限制(抓空位配额)
-
为什么要有配额? 防止工序 A 拼命挖坑/生产,把缓冲区撑爆。
-
配额与产物的对偶关系(核心本质):
-
中间产物信号量(
product)初值为 0,表示里面有多少东西。 -
空位配额信号量(
empty_quota)初值为 ,表示还能放多少东西。 -
关系恒成立:。
-
-
归还时机(高频失分):
-
只有当这个中间产物被后续工序彻底消除、不再占用原空间时,才能执行
signal(empty_quota)。 -
例如:树坑在乙“填土”完成后才算消失,所以必须在填完土后还配额。
-
步骤 3:工具竞争(抓互斥)
-
真互斥:铁锹同时被甲(挖坑)和乙(填土)需要,两个人会打架,必须设
mutex = 1。 -
伪互斥(高频失分):水桶全场只有丙一个人浇水在用,没有任何竞争者,绝对不设互斥信号量。
步骤 4:优化与安全检查(防死锁)
-
嵌套 P 操作顺序:必须是
wait(配额)wait(互斥锁)。-
绝不能先拿互斥锁再等配额。否则一旦配额用尽,占着工具不放会导致死锁。
-
四、 通用代码骨架模版(直接迁移复用)
以“三工序流水线”为例(工序1由甲负责,工序2由乙负责,工序3由丙负责;甲乙争用工具 T,丙独占工具 W;工序1的产物上限为 ):
C
// ================= 信号量定义与初值说明 =================
semaphore empty_quota = N; // 同步信号量:工序1的空位/配额上限,初值为 N
semaphore product_1 = 0; // 同步信号量:工序1产出、供工序2消耗的中间产物,初值为 0
semaphore product_2 = 0; // 同步信号量:工序2产出、供工序3消耗的中间产物,初值为 0
semaphore mutex_tool_T = 1;// 互斥信号量:甲与乙争用的工具 T,初值为 1
// 工具 W 仅由丙独占使用,不存在并发竞争,无需设置信号量!
// ================= 各角色工序进程 =================
process 角色甲() {
while (true) {
wait(empty_quota); // 1. 检查并申请空位配额(防爆仓)
wait(mutex_tool_T); // 2. 争抢物理工具 T
执行工序1; // 3. 生产操作
signal(mutex_tool_T); // 4. 释放物理工具 T
signal(product_1); // 5. 产出中间产物1,唤醒工序2
}
}
process 角色乙() {
while (true) {
wait(product_1); // 1. 等待中间产物1到位
独立准备工作; // 2. 无需工具的动作放锁外,缩短临界区
wait(mutex_tool_T); // 3. 争抢物理工具 T
使用工具执行工序2;
signal(mutex_tool_T); // 4. 释放物理工具 T
signal(empty_quota); // 5. 中间产物被消化,归还一个空位配额
signal(product_2); // 6. 产出中间产物2,唤醒工序3
}
}
process 角色丙() {
while (true) {
wait(product_2); // 1. 等待中间产物2到位
使用独占工具执行工序3; // 2. 独占工具直接使用,不加 PV
}
}
五、 408 核心命题陷阱与避坑准则
WARNING
“中间产物”漏提或概念混淆
题目只要有先后工序,每多一层交接,就必定多一个“初值为 0 的同步信号量”。
必须分清是哪个工序生产、哪个工序消耗,千万不能一个信号量从头用到尾。
死锁顺序倒置(核心必考点)
凡是既要申请“空间配额(或前置产物)”,又要拿“物理锁”的,必须先申请数量配额,再申请互斥锁。
记牢口诀:“先看有没有资格(配额),再看能不能动手(工具)”。
为独占资源画蛇添足
题目出现“定义尽可能少的信号量”,只要看到某资源全流程只有单个进程使用,坚决不写信号量。写了就会被扣“信号量未达最简”的分。
归还配额时机错误
- 配额代表“旧中间产物何时腾出空间”。一定要看准题干中是哪个具体动作让旧产物被替换/填平,就在那个动作执行完后立刻
signal(empty_quota)。