2.3.4 前趋图与PV操作
本课核心知识点整理
本节导学
前趋图与 PV 操作是软考里非常典型的“看图填 P/V”题。字幕强调，这类题只要掌握技巧，通常属于稳定拿分点。前趋图的节点表示活动或进程，有向边表示明确的逻辑先后关系：箭头流出的节点是前驱，箭头流入的节点是后继，只有前驱完成，后继才能开始。
它考的不是互斥，而是同步。互斥关心“同一时刻谁能用临界资源”；前趋图关心“谁必须等谁完成”。
前趋图的含义
若存在：
text
A -> B含义是 B 必须等待 A 完成。用 PV 表达时，A 完成后需要通知 B，B 开始前需要等待这个通知：
text
A:
执行 A
V(Sab)
B:
P(Sab)
执行 B同步信号量 Sab 初值通常为 0，因为在 A 没完成之前，B 不应该开始。
一条边对应一个同步条件
做题时最稳的方式是“一条前趋边配一个信号量”。边多，信号量也会多；不要试图把所有边混成一个信号量，否则很容易把不同先后关系合并错。
| 图结构 | PV 写法 |
|---|---|
| 一个前驱指向一个后继 | 前驱结束 V，后继开始 P |
| 多个前驱指向同一后继 | 后继开始前对每条入边都 P |
| 一个前驱指向多个后继 | 前驱结束后对每条出边都 V |
如果节点 D 有 A、B、C 三个前驱，D 不能只等其中一个完成。它开始前必须分别检查三个同步条件：
text
P(Sad)
P(Sbd)
P(Scd)
执行 D如果节点 A 有多个后继，A 完成后要分别通知每个后继：
text
执行 A
V(Sab)
V(Sac)
V(Sad)为什么初值通常为 0
同步信号量表示“某个前驱事件是否已经发生”。在程序刚开始时，前驱通常还没完成，所以信号量初值为 0。后继如果抢先执行 P，会被阻塞；等前驱完成执行 V 后，后继才被唤醒进入就绪队列。
做题路线
- 给每条箭头命名一个信号量，例如
A -> D命名为Sad。 - 对每个节点，先处理所有入边：开始前写对应的
P。 - 执行该节点任务。
- 再处理所有出边：结束后写对应的
V。 - 没有箭头直接相连的节点之间没有先后约束，可并发或任意顺序执行。
例题
若前趋图中存在 A -> B，常见 PV 写法是：
前趋边对应的同步信号量初值通常为：
如果一个任务有多个前驱，正确处理方式是：
自查要点
- 前趋图中的箭头表示资源流向还是执行先后？
- 为什么同步信号量初值通常为 0？
- 多入边和多出边分别怎么写 P/V？