【软考每日一练003】前趋图与 PV 操作全解析
一、典例题目
二、 题目解析
1. 信号量设置（按箭头标注）
我们为图中的 5 条边设置信号量：
- P1→P2P1 \rightarrow P2P1→P2：信号量S1S1S1
- P1→P3P1 \rightarrow P3P1→P3：信号量S2S2S2
- P3→P2P3 \rightarrow P2P3→P2：信号量S3S3S3
- P3→P4P3 \rightarrow P4P3→P4：信号量S4S4S4
- P2→P4P2 \rightarrow P4P2→P4：信号量S5S5S5
2. 逐一匹配进程操作
根据“进入 P，退出 V”的原则：
| 进程 | 位置 | 操作内容 | 逻辑说明 |
|---|---|---|---|
| P1 | a (出口) | V(S1),V(S2)V(S1), V(S2)V(S1),V(S2) | P1 结束，通知 P2(S1S1S1) 和 P3(S2S2S2) |
| P2 | b (入口) | P(S1),P(S3)P(S1), P(S3)P(S1),P(S3) | P2 开始前，需等待 P1(S1S1S1) 和 P3(S3S3S3) |
| P2 | c (出口) | V(S5)V(S5)V(S5) | P2 结束，通知 P4(S5S5S5) |
| P3 | d (入口) | P(S2)P(S2)P(S2) | P3 开始前，需等待 P1(S2S2S2) |
| P3 | e (出口) | V(S3),V(S4)V(S3), V(S4)V(S3),V(S4) | P3 结束，通知 P2(S3S3S3) 和 P4(S4S4S4) |
| P4 | f (入口) | P(S4),P(S5)P(S4), P(S5)P(S4),P(S5) | P4 开始前，需等待 P3(S4S4S4) 和 P2(S5S5S5) |
3. 最终选项核对
- 第一组 (a, b, c)：
- 匹配结果：V(S1)V(S2)V(S1)V(S2)V(S1)V(S2)、P(S1)P(S3)P(S1)P(S3)P(S1)P(S3)、V(S5)V(S5)V(S5)
- 对应图中第一组选项的C。
- 第二组 (d, e, f)：
- 匹配结果：P(S2)P(S2)P(S2)、V(S3)V(S4)V(S3)V(S4)V(S3)V(S4)、P(S4)P(S5)P(S4)P(S5)P(S4)P(S5)
- 对应图中第二组选项的A。
结论：正确答案是 C、A。
三、 核心概念：什么是前趋图？
1. 定义
前趋图 (Precedence Graph)是一个有向无环图 (DAG)。在操作系统中，它用来描述程序执行的先后顺序。
- 结点：代表一个进程、一个程序段或一条语句。
- 有向边：代表两个结点之间的前趋关系。例如P1→P2P1 \rightarrow P2P1→P2，表示P1P1P1必须先执行完，P2P2P2才能开始。
2. 什么是前趋进程？
如果存在P1→P2P1 \rightarrow P2P1→P2，那么P1P1P1就是P2P2P2的直接前趋，而P2P2P2是P1P1P1的直接后继。
简单来说，前趋进程就是“必须先完成的前置任务”。
四、 PV 操作：为什么是“出 V 进 P”？
1. 谁定义的？
这一概念是由计算机科学奠基人之一、荷兰学者艾兹赫尔·戴克斯特拉 (Edsger W. Dijkstra)在 1965 年提出的。
2. 为什么叫 P 和 V？
这两个缩写来自荷兰语：
- P (Proberen)：意为“测试”或“尝试减少”。
- V (Verhogen)：意为“增量”或“释放”。
3. 设计逻辑（重点）
PV 操作的核心是利用信号量 (Semaphore)来进行进程同步。
- 信号量SSS：你可以把它理解为一个“通行证”或“资源计数器”。在本题同步问题中，初值通常设为000。
- P(S)P(S)P(S)操作：相当于“申请/检查”。进程开始前执行PPP，如果S≤0S \le 0S≤0，进程就会阻塞，直到前趋任务给它发信号。
- V(S)V(S)V(S)操作：相当于“通知/释放”。进程结束后执行VVV，将SSS加111，唤醒正在等待该信号的后继进程。
规则总结：
- 进程开始处（入口）：有几个箭头指进来，就执行几个PPP操作（等待所有前趋任务完成）。
- 进程结束处（出口）：有几个箭头发出去，就执行几个VVV操作（通知所有后继任务可以开始了）。
五、 信号量SxS_xSx的定义与标注
1.xxx是如何定义的？
在解题时，xxx只是一个编号。每一个SxS_xSx代表前趋图中一条特定的“有向边（逻辑连接）”。
2. 标注技巧（实战演练）
针对本题，我们为每一条路径手动标记信号量，确保不重不漏：
- 从P1P1P1出发的边：P1→P2P1 \rightarrow P2P1→P2标为S1S1S1；P1→P3P1 \rightarrow P3P1→P3标为S2S2S2。
- 从P3P3P3出发的边：P3→P2P3 \rightarrow P2P3→P2标为S3S3S3；P3→P4P3 \rightarrow P4P3→P4标为S4S4S4。
- 从P2P2P2出发的边：P2→P4P2 \rightarrow P4P2→P4标为S5S5S5。
六、 总结：解题口诀
信号量标在箭头上，
入 P 出 V 莫记混。
入度几个就几个 P，
出度几个就几个 V。
