题目

某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E、F 共 6 个操作，其中 T1 执行 A、E、F，T2 执行 B、C、D。

操作之间的执行顺序约束（如题 46 图）：

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

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

解析

拆解：哪些边是"跨线程"的？

线程内部的操作天然顺序执行（A → E → F 在 T1 内部依次跑、B → C → D 在 T2 内部依次跑），不需要信号量。只有跨线程边需要信号量同步：

前驱图边	在哪个线程完成 → 在哪个线程开始	跨线程？
A → C	T1 完成 → T2 开始	✅ 跨
B → C	T2 完成 → T2 开始	❌ 同线程内
C → D	T2 完成 → T2 开始	❌ 同线程内
C → E	T2 完成 → T1 开始	✅ 跨
E → F	T1 完成 → T1 开始	❌ 同线程内

跨线程的边只有 2 条：A→C 和 C→E。所以只需要 2 个信号量。

信号量与代码

semaphore AC = 0;    // T1 通知 T2：A 已完成
semaphore CE = 0;    // T2 通知 T1：C 已完成

T1() {
    A;
    signal(AC);      // A 做完，通知 T2 可以执行 C 的"A 部分前驱"
    
    wait(CE);        // 等 T2 完成 C
    E;
    F;               // F 在 T1 内紧跟 E，无需信号量
}

T2() {
    B;               // B 在 T2 内最先执行，无需等待
    wait(AC);        // 等 T1 完成 A
    C;               // C 已等到 A、B 双前驱
    signal(CE);      // C 做完，通知 T1 可以执行 E
    D;               // D 在 T2 内紧跟 C，无需信号量
}

信号量含义说明（答题必写）

信号量	初值	含义
AC	0	"A 已完成"事件；T1 V 之后 T2 才能 P 通过
CE	0	"C 已完成"事件；T2 V 之后 T1 才能 P 通过

易错点

编者注（关键洞察）：

1. 同一线程内的操作天然有序——这是本题与 2020-45 的最大差别。2020-45 里 5 个操作"独立运行"，所以每条边都要信号量；本题分到 2 个线程后，线程内部的边自动保序，所以只需 2 个跨线程信号量（不是 4 个）。"尽可能少"的关键就是识别这一点。

2. B → C 不需要信号量：B 和 C 都在 T2 内、按代码顺序写就保证 B 先于 C。写顺序 = 执行顺序这条规则在单线程内永远成立。

3. wait 和 signal 的"配对"：

   • signal(AC) 在 T1（A 之后）；wait(AC) 在 T2（C 之前）→ 跨线程通知
   • signal(CE) 在 T2（C 之后）；wait(CE) 在 T1（E 之前）→ 跨线程通知

   永远是"先做的人 signal、要等的人 wait"——记住这一条不会写错符号。

4. T2 中 wait(AC) 必须在 B 之后：B 不依赖 A，可以先跑。但 C 依赖 A 和 B 都完成。把 wait(AC) 放 C 之前即可——B 早做、A 等到、C 才跑。不要把 wait(AC) 放在 B 之前——这会让 B 等 A，多走一步同步。

5. T1 中 wait(CE) 必须在 E 之前：E 依赖 C 完成。但 A 不依赖 C，所以 A 可以先做（也只能先做，否则 A 永远做不完，T2 永远等不到 AC）。

本题与 2020-45 的对比：

	2020-45	2022-46
操作数	5	6
边数	4	5
进程 / 线程数	5（每个操作一个）	2（A/E/F 在 T1，B/C/D 在 T2）
需要信号量	4（每边一个）	2（只有跨线程的边）

一道题的"复杂度"不只看图复杂度，还要看分配到几个并发实体——这是同步题答好的关键技巧。