前趋图与多线程同步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”

  1. 针对跨线程箭线 (信号量 S_AC = 0):
    • 前 V:在 执行完 A 之后,立刻调用 signal(S_AC);
    • 后 P:在 执行完 B、准备执行 C 之前,必须先调用 wait(S_AC)。
  2. 针对跨线程箭线 (信号量 S_CE = 0):
    • 前 V:在 执行完 C 之后,立刻调用 signal(S_CE);
    • 后 P:在 准备执行 E 之前,必须先调用 wait(S_CE)。
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()。顺着题干符号写,永远不给阅卷老师任何扣印象分的机会!

四、双链索引