前趋图与多线程同步PV操作全题型秒杀模板
💡 学长应试破局点拨:为什么 408 的 PV 大题越来越爱考“前趋图”?
早年 408 喜欢考复杂的缓冲区生产者-消费者变式,但从 2019、2021、2022、2023 年开始,命题人极度偏爱**“给一张前趋图(或几条线程的执行序列),让你填
wait()/signal()(即P/V操作)”。 这种题简直是白给的 8~10 分**!只要记住下面这句**“前趋箭线口诀”和“同线程消箭线铁律”**,考场上 2 分钟就能拿满分,绝对不会多设或漏设信号量!
一、核心破题铁律(30 秒学会所有前趋图 PV 题)
1. 万能口诀:“前 V 后 P,初值全 0;同线程顺序跑,箭线直接砍掉!”
遇到任何前趋图(有向无环图 DAG)同步问题,严格按以下 3 步走:
第一步:看清哪些操作在“同一个线程/进程”内部(最关键的防坑步!)
- 如果题目规定操作 和操作 本来就在同一个线程的代码里按顺序一前一后执行(比如线程 依次执行
B -> C -> D):- 代码写出来天然就是先跑完
B;才会往下跑C;,再跑D;! - 同线程内部的先后箭线(如 、)由程序计数器 PC 自动保证,绝对不需要设信号量!直接把这些箭线从图上划掉!
- 代码写出来天然就是先跑完
- 只有跨越不同线程/进程的箭线(比如线程 的操作 指向线程 的操作 ),才需要设置信号量来强制同步!
第二步:为每一条“跨线程箭线”配 1 个初值为 0 的信号量
- 设跨线程箭线为 :
- 定义同步信号量:
semaphore S_XY = 0; - 物理含义模板(阅卷踩分必写):信号量
S_XY用于实现操作 与操作 的同步,表示操作 是否已经执行完毕(初值为0)。
- 定义同步信号量:
第三步:沿着箭线套用“前 V 后 P”
- 在箭线起点(前操作 )刚执行完的屁股后面,立刻写
V(S_XY)(或signal(S_XY)),大喊一声:“我 干完了,放行!” - 在箭线终点(后操作 )准备执行的前面,立刻写
P(S_XY)(或wait(S_XY)),先卡住检查:“ 干完了吗?没干完我就阻塞等它!”
flowchart LR X["线程1:执行前操作 X"] --> VX["V(S_XY) / signal(S_XY)"] VX -.->|"跨线程同步信号量 S_XY = 0"| PY["P(S_XY) / wait(S_XY)"] PY --> Y["线程2:执行后操作 Y"]
二、2022 年 408 统考第 46 题实战拆解(原卷标准真题满分示范)
1. 题目条件回顾(对照原卷第 10 页 46 题)
- 同一进程下有两个线程 和 并发执行 6 个操作:
- 线程 包含的操作序列:
A -> E -> F - 线程 包含的操作序列:
B -> C -> D
- 线程 包含的操作序列:
- 约束条件与前趋箭线:
- 在 和 完成后执行(即 和 );
- 和 在 完成后执行(即 和 );
- 在 完成后执行(即 )。
- 设问:使用信号量的
wait()、signal()操作描述 和 之间的同步关系,并说明所用信号量的作用及其初值。
2. 解题思路(三步秒杀推演)
第一步:砍掉“同线程内部”自带的箭线!
把 5 条箭线逐一拉出来过安检,看起点和终点是不是在同一个线程里:
| 图中的前趋箭线 | 起点所在线程 | 终点所在线程 | 是否跨线程? | 考场处理结论 |
|---|---|---|---|---|
| ❌ 同在 | 顺序执行 B 后自然执行 C,无需信号量(直接砍掉!) | |||
| ❌ 同在 | 顺序执行 C 后自然执行 D,无需信号量(直接砍掉!) | |||
| ❌ 同在 | 顺序执行 E 后自然执行 F,无需信号量(直接砍掉!) | |||
| ✅ 跨线程() | 必须设信号量 S_AC = 0(或 S_A = 0) | |||
| ✅ 跨线程() | 必须设信号量 S_CE = 0(或 S_C = 0) |
爽快结论:原本看着眼花缭乱的 5 条箭线,砍掉同线程内部的 3 条后,全场只剩下 2 条跨线程箭线( 和 )!只需要 2 个信号量!
第二步:对剩下的 2 条跨线程箭线套用“前 V 后 P”
- 针对跨线程箭线 (信号量
S_AC = 0):- 前 V:在 执行完
A之后,立刻调用signal(S_AC); - 后 P:在 执行完
B、准备执行C之前,必须先调用wait(S_AC)。
- 前 V:在 执行完
- 针对跨线程箭线 (信号量
S_CE = 0):- 前 V:在 执行完
C之后,立刻调用signal(S_CE); - 后 P:在 准备执行
E之前,必须先调用wait(S_CE)。
- 前 V:在 执行完
flowchart TD T1_A["T1:执行 A"] --> T1_V["T1:signal(S_AC)"] T2_B["T2:执行 B"] --> T2_P["T2:wait(S_AC)"] T1_V -.->|"S_AC = 0(保证 A 在 C 前)"| T2_P T2_P --> T2_C["T2:执行 C"] T2_C --> T2_V["T2:signal(S_CE)"] T2_V --> T2_D["T2:执行 D"] T1_V --> T1_P["T1:wait(S_CE)"] T2_V -.->|"S_CE = 0(保证 C 在 E 前)"| T1_P T1_P --> T1_E["T1:执行 E"] T1_E --> T1_F["T1:执行 F"]
3. 试卷规范写法(面向阅卷老师的满分卷面)
(1)信号量定义、含义及初值:
- 定义两个同步信号量
S_AC和S_CE,初值均为0:S_AC = 0:表示线程 中的操作A是否执行完毕,用于实现操作A在操作C之前执行的同步关系;S_CE = 0:表示线程 中的操作C是否执行完毕,用于实现操作C在操作E之前执行的同步关系。
(2)同步伪代码实现:
semaphore S_AC = 0; // 表示 A 是否执行完毕,初值为 0
semaphore S_CE = 0; // 表示 C 是否执行完毕,初值为 0
void T1() {
A;
signal(S_AC); // 通知 T2:操作 A 已完成,允许执行 C
wait(S_CE); // 等待 T2:操作 C 完成后,才能执行 E
E;
F;
}
void T2() {
B;
wait(S_AC); // 等待 T1:操作 A 完成后,才能执行 C
C;
signal(S_CE); // 通知 T1:操作 C 已完成,允许执行 E
D;
}三、命题人常考的 3 大变式与避坑铁律
变式 1:如果图中 6 个结点 A、B、C、D、E、F 是“6 个独立的进程”(没有合并在两个线程里)怎么办?
- 答:如果每个结点都是一个独立的并发进程(没有任何两个操作在同一个线程内顺序执行),那么图中每一条有向边都是跨进程的!
- 此时有 5 条箭线,就必须老老实实定义 5 个初值为 0 的信号量:
S_AC = 0, S_BC = 0, S_CD = 0, S_CE = 0, S_EF = 0- 在进程
C开头连写两个wait:wait(S_AC); wait(S_BC); C; signal(S_CD); signal(S_CE); - ⚠️ 铁律:同一个纯同步操作开头连续多个
wait(P 操作)时,因为没有互斥锁参与,这两个wait的先后顺序可以任意颠倒,不会发生死锁!
变式 2:如果既有“前趋同步(初值 0)”,又要求访问同一个共享变量/缓冲区(“互斥,初值 1”),顺序怎么放?
- 黄金保命口诀:“先 P 同步(等资源/等前趋),再 P 互斥(进临界区);先 V 互斥,再 V 同步!”
- 如果颠倒成“先
wait(mutex)锁住临界区,再wait(同步信号量)死等别人”,别人进不了临界区永远无法signal唤醒你,当场死锁扣光步骤分!
变式 3:题目要求写 wait()/signal(),我写成 P()/V() 会扣分吗?
- 应试规范:题干写的是
wait()/signal(),卷面上就严格照抄写wait()和signal();题干写P()/V()就写P()和V()。顺着题干符号写,永远不给阅卷老师任何扣印象分的机会!
四、双链索引
- 主索引笔记:2022
- 同年操作系统大题姊妹篇:UNIX混合索引文件与目录检索访盘次数全题型秒杀