【操作系统】前趋图与PV操作（结合前趋图解题）
考点频率：★★★★★（下午题必考，选择题常考）
难度：⭐⭐⭐⭐
建议：掌握前趋图与PV操作的互转规则，这是下午题信号量填空的核心技能
1️⃣ 什么是前趋图？
前趋图是一个有向无环图（DAG），用于描述多个进程或程序段之间的执行顺序依赖关系。
- 节点：表示一个进程或程序段（用
P1, P2, ...或S1, S2, ...表示） - 有向边：
Pi → Pj表示Pi必须在Pj之前执行（Pi是Pj的前驱）
生活类比：前趋图就像菜谱里的步骤依赖图——必须“先洗菜才能切菜，先切菜才能下锅”。每条有向边都代表一个“必须等上一步完成”的约束。
2️⃣ 前趋图与PV操作的关系
前趋图描述的是同步关系（谁先谁后），而PV操作是实现同步的工具。软考下午题的经典考法：
- 给前趋图，补全PV操作代码中的信号量
- 给PV操作代码，画出对应的前趋图
两者的转换有一套固定的规则：
转换规则：入边 → P，出边 → V
对于每个节点（进程/程序段）：
| 规则 | 说明 |
|---|---|
| 入边 → P操作 | 有几条入边，开头就放几个P(信号量)（按顺序等待所有前驱） |
| 出边 → V操作 | 有几条出边，末尾就放几个V(信号量)（逐个通知所有后继） |
3️⃣ 完整转换示例
给定前趋图
┌───┐ │ S1│ └─┬─┘ │ ┌────┴────┐ │ │ ▼ ▼ ┌───┐ ┌───┐ │S2 │ │S3 │ └─┬─┘ └─┬─┘ │ │ └────┬────┘ │ ▼ ┌───┐ │ S4│ └───┘转换步骤
第1步：识别所有边，为每条边分配一个信号量
| 边 | 信号量名 |
|---|---|
| S1 → S2 | a |
| S1 → S3 | b |
| S2 → S4 | c |
| S3 → S4 | d |
所有信号量初值均为0（同步信号量）。
第2步：对每个节点，按“入边P、出边V”规则生成代码
| 节点 | 入边数量 | 出边数量 | 需要写的PV操作 |
|---|---|---|---|
| S1 | 0 | 2（→S2, →S3） | 末尾写V(a); V(b) |
| S2 | 1（S1→S2） | 1（S2→S4） | 开头P(a)；末尾V(c) |
| S3 | 1（S1→S3） | 1（S3→S4） | 开头P(b)；末尾V(d) |
| S4 | 2（S2→S4, S3→S4） | 0 | 开头P(c); P(d) |
第3步：写完整的代码框架
semaphore a=0;// S1→S2semaphore b=0;// S1→S3semaphore c=0;// S2→S4semaphore d=0;// S3→S4S1(){// S1的代码V(a);// 通知S2V(b);// 通知S3}S2(){P(a);// 等待S1完成// S2的代码V(c);// 通知S4}S3(){P(b);// 等待S1完成// S3的代码V(d);// 通知S4}S4(){P(c);// 等待S2完成P(d);// 等待S3完成// S4的代码}4️⃣ 反过来：由PV操作画前趋图
如果题目给你PV操作代码，让你画前趋图，按以下步骤反推：
- 找出所有信号量：统计出现了哪些信号量，注意初值是否为0（同步信号量）或1（互斥信号量）。同步信号量（初值为0）才是用来表示前趋关系的。
- 确定边的方向：对每个同步信号量
s，找到V(s)所在的位置和P(s)所在的位置：- 画一条从
V(s)所在的节点 →P(s)所在的节点的有向边
- 画一条从
- 确认节点：列出所有执行单元（函数/进程），按边画图。
示例：已知代码中有一个同步信号量s（初值0），S1中执行V(s)，S2中执行P(s)→ 画出S1 → S2。
5️⃣ 考试中的常见陷阱
| 陷阱 | 正确做法 |
|---|---|
| 漏掉信号量初始化 | 每个边对应的信号量必须初值 = 0（同步信号量） |
| P操作个数不匹配 | 入边数量 = P操作数量，必须相等 |
| V操作个数不匹配 | 出边数量 = V操作数量，必须相等 |
| 把互斥信号量（初值1）混入前趋图 | 前趋图中只涉及同步信号量（初值0）；互斥信号量是另外加的 |
| 忘记写P操作的顺序 | 一个节点有多个P操作时，顺序一般不重要（因为要全部完成才能继续），但应写全。前趋图中若某节点有多个前驱，必须所有P都通过才能执行，注意审题看信号量是“与”关系还是“或”关系。 |
6️⃣ 经典例题
例题1：某系统有3个进程P1、P2、P3，前趋关系为 P1→P2，P2→P3。信号量s1、s2初值为0，补全代码：
P1() { // 代码 (1) ; // 空处填什么？ } P2() { (2) ; // 代码 (3) ; } P3() { (4) ; // 代码 }解：边为 P1→P2 和 P2→P3。对应关系为：P1的V通知P2，P2先P后V通知P3。按规则填入即可。
答案：
- (1)
V(s1) - (2)
P(s1) - (3)
V(s2) - (4)
P(s2)
例题2（稍复杂）：前趋图有4个节点S1、S2、S3、S4，边为：S1→S2，S1→S3，S2→S4，S3→S4。信号量 a,b,c,d 对应4条边，初值均为0。则S4中应写（ ）。
A.P(a); P(b)
B.P(c); P(d)
C.V(c); V(d)
D.V(a); V(b)
解析：S4的入边是 S2→S4 和 S3→S4，对应的信号量是 c 和 d。入边对应P操作，所以 S4 开头写P(c); P(d)。选B。
7️⃣ 记忆口诀
前趋图有向无环，入边P来出边V。
每条边对应一信号，初值全部设为0。
V在末尾P在头，顺序执行靠它走。
8️⃣ 小测验（评论区对答案）
某系统有4个进程P1、P2、P3、P4，前趋图如下：P1→P2，P1→P3，P2→P4，P3→P4。信号量 s1、s2、s3、s4 分别对应4条边，初值均为0。则 P4 中需要写几个 P 操作？分别对应哪些信号量？
🔔本专栏日更2篇，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #前趋图 #PV操作 #进程同步 #操作系统