题目

现有 5 个操作 A、B、C、D、E，约束：

• 操作 C 必须在 A 和 B 完成后执行
• 操作 E 必须在 C 和 D 完成后执行

请使用信号量的 wait()、signal() 操作（P、V 操作）描述上述操作之间的同步关系，并说明所用信号量及其初值。

解析

把约束画成前驱图

• 顶点 = 操作
• 有向边 = "前者必须先于后者完成"

关键技巧：每条边对应一个信号量

每条边 X → Y 都需要一个 init=0 的信号量 S_XY：

• X 完成后 V(S_XY) —— "我做完了"
• Y 开始前 P(S_XY) —— "等前驱完成"

本题前驱图有 4 条边 → 需要 4 个信号量：

信号量	表示什么	初值
SAC	A → C	0
SBC	B → C	0
SCE	C → E	0
SDE	D → E	0

信号量与代码

semaphore SAC = 0;   // A 是 C 的前驱
semaphore SBC = 0;   // B 是 C 的前驱
semaphore SCE = 0;   // C 是 E 的前驱
semaphore SDE = 0;   // D 是 E 的前驱

A() {
    操作 A;
    V(SAC);          // 通知 C：A 已完成
}

B() {
    操作 B;
    V(SBC);          // 通知 C：B 已完成
}

C() {
    P(SAC);          // 等 A 完成
    P(SBC);          // 等 B 完成
    操作 C;
    V(SCE);          // 通知 E：C 已完成
}

D() {
    操作 D;
    V(SDE);          // 通知 E：D 已完成
}

E() {
    P(SCE);          // 等 C 完成
    P(SDE);          // 等 D 完成
    操作 E;
}

易错点

编者注（前驱图题统一套路）：

1. 每条边对应一个独立信号量——不要试图用一个信号量"通用"。如果用一个 S = 0，E 该 P 几次？P 两次的话，可能 P 走 SAC 和 SBC 而不是该等的 SCE 和 SDE → 顺序错乱。

2. 信号量初值都是 0——表示"前驱事件还未发生"。看到题目里说"X 必须在 Y 完成后"，立刻反应：信号量 init=0、Y 完成后 V、X 开始前 P。

3. 多个前驱时，P 的顺序无所谓——本题 C 中 P(SAC); P(SBC); 也可以写成 P(SBC); P(SAC);，只要两个都 P 完才进操作 C 即可。但不能写成 P(SAC) 后立刻"操作C"再 P(SBC)，那样 B 完成前 C 就开始了，违反约束。

4. D 不用等任何前驱——题目里 D 没有前驱（只有 D → E 这条出边），所以 D() 内部直接执行操作即可，无需任何 P。同理 A、B 也无前驱、直接执行。

5. 没有互斥信号量——本题只有"先后顺序"约束，没有"两个操作不能同时跑"约束。所以不要自作多情加 mutex——考研评分会扣"未做到尽可能少"的分。

这套"边对应信号量"的方法适用于所有前驱图题型——2022-46 也是这种结构（虽然画法不同），用同一套思路即可解。