企业官网建设流程全解析

【软考每日一练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”的原则：

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. 标注技巧（实战演练）

针对本题，我们为每一条路径手动标记信号量，确保不重不漏：

1. 从P1P1P1出发的边：P1→P2P1 \rightarrow P2P1→P2标为S1S1S1；P1→P3P1 \rightarrow P3P1→P3标为S2S2S2。
2. 从P3P3P3出发的边：P3→P2P3 \rightarrow P2P3→P2标为S3S3S3；P3→P4P3 \rightarrow P4P3→P4标为S4S4S4。
3. 从P2P2P2出发的边：P2→P4P2 \rightarrow P4P2→P4标为S5S5S5。

六、 总结：解题口诀

信号量标在箭头上，

入 P 出 V 莫记混。

入度几个就几个 P，

出度几个就几个 V。