P07 发完那天,我回头翻自己的专栏列表,越看越不对劲。

P01 讲生产者消费者,P02 跳到前驱图,P03 又回去讲银行排队,P05 是哲学家,P06 突然钻到指令层讲原子性。这是按我写文章的顺序,不是按做题的顺序。真到考场上,题目不会告诉你"这题该用第 3 篇的方法",它只会给你一段描述,然后问你:设几个信号量、初值多少、P 怎么写。

所以补了这一篇。它不教新东西,只把 7 篇按"这题到底在问什么"重新排一次,再配一张能从题干直接查到解法的表。

图示:7 篇 = 五类题型的完整地图,下方标注 13 道真题的年份分布与篇目归属

第〇节 · 扫盲(一句人话)

408 操作系统卷子上,最后那道大题大概率考 PV 操作。题目给你几个进程、几个共享资源、一堆"必须先……才能……"的约束,让你用信号量写出同步互斥的代码。

信号量可以理解成一个带计数的通行证发放处。里面存着几张票,进程想往下走就得先领一张(这个动作叫 P,票不够就排队等着);用完资源把票还回去(叫 V,顺便叫醒一个在等的人)。票只有一张时,它就成了"一次只能进一个人"的锁,这个被保护的区域叫临界区。

互斥是"这东西同时只能一个人用",同步是"你必须等我做完才能开始"。这两个词分清了,PV 题就入门了。至于死锁——几个人各攥着对方要的东西,谁也不肯先放,全卡住。

从 2009 年统考到 2025 年,一共出了 13 道 PV 大题。我把 13 道全用 pthread 真跑了一遍,每篇都贴了实际运行输出。7 篇按考点分组,一篇装一到三道题。

一句话:这不是"操作系统入门",是"卷子上那道 PV 大题怎么拿分"。

一、这篇怎么用

手上卡着一道题:直接跳到第八节的年份索引,或者第九节的关键词对照表,找到题面那句话,翻对应的篇。

想按题型系统过一遍:从第二节顺着读到第七节。五类按"从骨架到细节"排,前面是所有 PV 题的地基,后面是拉开差距的地方。

考前只想背套路:翻第九节、第十节和文末速查表。没有代码,只有"看到什么,设几个,初值多少"。

二、地图:7 篇分成五类

类这题在问什么篇目真题难度
①生产者消费者骨架:谁等谁P01、P072009(45)、2014(47)、2024(46)★★
②前驱图:几条边要发票P022020(45)、2022(46)、2025(45)★★★
③限额与死锁:顺序不对就卡死P03、P052011(45)、2013(45)、2019(43)★★★★
④初值与锁粒度:别想当然写 0P042015(45)、2017(46)★★★★
⑤底层原子性:PV 自己怎么实现P062021(45)、2023(45)★★★★★

为什么这么排:① 是所有 PV 题的公共骨架,不会这个后面全免谈;② ③ 开始在骨架上加约束;④ 考"读题细不细";⑤ 已经不属于"写应用代码",而是问原理,近五年越来越爱考。

顺带一个趋势:2009~2019 偏"资源 + 互斥",2020 年起偏"最少几个信号量 / 能不能 / 为什么"。光会套模板不够了。

三、第一类|生产者消费者骨架(P01、P07)

篇号篇名真题一句话
408 大题 01拿到题先画一张"谁等谁"的图2009(45)、2014(47)数角色、数资源、数等待边、填 P/V,四步走完不用猜
408 大题 07一个缓冲区三种操作2024(46)写是临界区、读改也是;附 13 题总表与审题六步

P01 那套四步法是整套东西的地基:互斥资源设初值 1、计数资源设总数、每一条"谁等谁"设初值 0,最后按"等的人在前 P、做完的人在后 V"填进去。

这一篇有两个实测值得记住。2009(45) 把 P(mutex) 提到 P(empty) 前面,缓冲区 5/5 占满、奇偶各取 0 个,3 秒判死;2014(47) 的批锁对比连跑 10 次,不加锁时 7 次第 1 批就被切碎,加锁 10/10 连续。输出依赖线程调度,文章里如实标了复跑范围。

P07 的 2024(46) 则是最朴素的一问:无互斥时 200/200 组出现两人同时写 B,加锁后 0 组。它还顺手收了全系列的总表,卡在哪道题可以直接按年份跳。

四、第二类|前驱图同步(P02)

篇号篇名真题一句话
408 大题 02一条边一个信号量,但同线程内的边是免费的2020(45)、2022(46)、2025(45)只有跨线程的箭头才要发票

这类的题眼只有一句:同一线程里的语句顺序,代码天生就保证,不用设信号量。

2022(46) 按字面数有 5 条约束,实际只需 2 个信号量。我用逻辑时钟各跑 200 次:2 个、4 个、5 个的写法违反约束全是 0,故意漏掉 S_CE 的版本 200 次全违反——哪些能省、哪些不能省,数据说话。

2025(45) 三人种树是另一个坑:pits(还能挖几个,额度)和 empty(已挖好几个,存量)不能合并。去掉额度信号量,坑峰值从 3/3 冲到 30;去掉铁锹锁,5 次复跑撞出 33~44 次同时持锹。

五、第三类|限额与死锁(P03、P05)

篇号篇名真题一句话
408 大题 03先抢座位还是先抢门2011(45)、2013(45)同样是 P 顺序写反,银行不死锁、博物馆直接卡死
408 大题 05哲学家为什么要少一个碗2019(43)plate = min(m, n−1),那个 −1 是算出来的

P03 是全系列最该看的一篇。同样是 P(mutex) 提前,银行只是"持锁等座位 16 次"但还是跑完 30/30,博物馆却是馆内 20/20、出门 0 人。判据我压成一句话:执行 V(额度) 的那一方,要不要同一把锁? 要,就死锁;不要,只是难看。这比背"先资源后互斥"有用得多。

P05 把死锁真跑出来了:plate=5 照抄碗数,5 人各攥一根左筷、0/100 完成;plate=4 / 2 / 4 三组全部 100/100。文章里还对照了课本经典版(最多 4 人上桌、奇偶号反手拿筷),并提醒 m > n−1 时把碗数和限人数合并成一个信号量会重新放开到 n 人——min 就是在防这个。

六、第四类|初值与锁粒度(P04)

篇号篇名真题一句话
408 大题 04信箱里本来就有信2015(45)、2017(46)full 初值是 x、y 不是 0;临界资源按变量细分才叫"最大程度并发"

2015(45) 的坑在读题:信箱里初始已有 x 封和 y 封信,四个信号量的初值得按题给的数填。我照"全写 0"跑了一遍,双方各完成 0 轮,一封信都没动就卡死。这里还有个反直觉的写法:V 全部落在另一个信箱上。

2017(46) 考的是"最大程度并发"。一把大锁时临界区同时有两人 0 次、30 轮耗时 1887 ms;按变量拆成三把细分锁,重叠 17~58 次、耗时 1398 ms。注意这个"重叠"是合法的——改的是不同变量,本来就该允许并发,不是冲突。评分说明里那句要求也值得抄进笔记。

七、第五类|底层原子性(P06)

篇号篇名真题一句话
408 大题 06PV 自己也得是原子的2021(45)、2023(45)对 S 的读改写必须一次完成,函数调用替代不了原子指令

这类不写应用代码,问的是"wait/signal 凭什么可信"。2021(45) 我用语义模拟跑了开关中断:全程关中断的方法 1 空转 200 万步 S 仍是 0、死循环;循环体内开中断的方法 2 能返回。(用户态真关不了中断,文中已注明是语义模拟。)

2023(45) 抓到一个真死锁:把原子 swap 换成普通函数 newSwap,非原子交换丢更新,把 lock 永久写成了 1,程序直接卡死;放大并发窗口后卡死前还偶发 0~4 次两人同时进临界区。4 线程 8 万次进入,原题伪代码冲突约 6.4 万次,原子 swap 版恒为 0。

八、13 道真题年份索引

年份题号考什么信号量要点在哪篇
200945三进程奇偶缓冲区4 个:mutex=1、empty=N、odd=0、even=0P01
201145银行叫号、10 个座位额度 10 + 取号机互斥 1P03
201345博物馆 500 人、一个出入口容量 500 + 门互斥 1P03
201447消费者连取 10 件加一把"批锁",防止一批被切碎P01
201545信箱辩论、初始已有邮件4 个,full 初值 x / y 不是 0P04
201746三线程复数、细粒度加锁按变量拆锁,不是一把大锁P04
201943哲学家与 m 个碗plate = min(m, n−1)P05
202045五操作前驱图4 条边 = 4 个初值 0P02
202145开/关中断实现 PV语义题,不设信号量P06
202246两线程前驱图、最少信号量5 条约束只需 2 个(同线程免费)P02
202345swap 指令与临界区互斥函数不能替代原子指令P06
202446缓冲区 C1/C2/C3mutex=1 + full=0P07
202545三人种树、额度与存量额度和存量两个信号量不能合并P02

九、题干关键词 → 第一反应(全篇最该背)

考场上没时间从零推。看到左边这句话,右边就该冒出来。

题干里出现第一反应关键初值 / 陷阱
同一时刻只能一个人用、一次一个互斥信号量1
最多容纳 N 人 / N 个空位 / N 个单元额度信号量N;先 P 额度再 P 门
缓冲区已有数据、信箱已有邮件存量信号量题给几就是几,别默认 0
A 做完 B 才能开始、必须先……等待边0;只有跨线程的边才要发票
同一线程里"先做 X 再做 Y"什么都不用设语句顺序免费
连续取 10 件、一批要完整加一把批锁锁要包住整批,不是单件
已挖好几个 / 还能挖几个两个信号量,别合并存量与额度是两件事
碗 m 个、n 个人限制并发人数min(m, n−1)
最大程度并发、尽可能并行按变量细分锁大锁不算错,但拿不到满分
前驱图、最少几个信号量数跨线程箭头同线程的边全删掉
出入口、门、取号机一把互斥 + 检查 V 方V(额度) 方要不要这把锁
B 为空才能写、非空才能读改mutex + full 两个读写都是临界区
开关中断、原语、原子性不写应用代码读改写必须一次完成
swap / TestAndSet 指令硬件原子指令普通函数会死锁

配套一个恒等式:同一容器 full + empty = 容量。写完先拿它验一遍,能挡掉一半初值错误。

十、死锁自查清单(按这五条过一遍)

  1. P 的顺序:是不是先额度、后门?把 P(mutex) 提到容量信号量前面,是最常见的死法。

  2. V 方被自己挡住:执行 V(额度) 的那一方,需不需要你手里这把互斥锁?需要就死锁(P03 博物馆)。

  3. 闭环:画一圈"谁等谁",能连成环就是死锁。破环靠少发一张入场券(n−1、少一个碗、最多 4 人上桌)。

  4. 忘 V 或 V 错位置:资源真正释放才 V;门用完立刻 V。漏一个 V,跑几轮就全停。

  5. 初始状态:容器一开始是空的还是有货?存量初值写 0,双方可能一步都动不了(P04 信箱)。

五条里第 2 条最容易被忽略,因为它不影响"看起来对不对",只影响"会不会跑着跑着停住"。

十一、照着题库解析背,会踩的四个坑

这 7 篇里陆续抓到 4 处资料错误,都不是我推演出来的,是真跑对照后发现的:

处题目问题
12014(47)解析文字把 empty / full 初值写反(代码本身是对的)。判断依据:看代码里 P 的是谁
22017(46)评分表写「thread3 和 thread4」,题目里根本没有 4 号线程;解析代码 w.b=1 与题目 w.b=2 不符
32011(45)解析有 OCR 乱码,fu11 实为 full
42024(46)第(2)问 P2 注释写成「执行 C1,从 B 中读出一个数组分组」,应为 C2、数据分组

另有一处不算错误但会误导:2011(42) 那类中位数题的解析复杂度写 O(n),实际 O(log n)——这属于算法系列 A11,但同一个题库,读解析时都留个心眼。

结论不是"解析不能看",是凡涉及初值、编号、变量名,一律回到题面自己数一遍。

十二、七篇反复出现的七条硬规矩

  1. 先数角色和容器,再动笔。 角色数决定是否要"同类互斥",容器初始状态决定存量初值。

  2. 互斥设 1、计数设总数、等待边设 0。 三类信号量别混。

  3. 同线程的边免费。 只有跨线程的约束才需要发票。

  4. 先 P 额度,再 P 门。 限制并发人数的信号量要提到所有其它 P 之前。

  5. V 落在"资源真正释放"那一刻,别提前、别漏、别 V 到自己手里的锁上。

  6. 题目要求"最大程度并发"就细分锁,但别为了并发把互斥丢掉——P07 的 200/200 丢更新就是代价。

  7. 写完用恒等式和闭环各查一遍,四分钟,专查初值、V 位置、P 顺序这三处。

十三、怎么练

第一遍,照着敲,编译跑通,看输出和文章是否一致。多线程程序的冲突次数每次不同,别拿某一次的数字当标准答案,要看"模式"——该连续的是不是连续、该卡死的是不是卡死。

第二遍,关掉文章默写,只留题面,20 分钟写出完整 PV 代码。写不出来就回去看是哪一步断了,多半是"等待边"没数全。

第三遍,只读题面,5 分钟说思路:几个角色、几个信号量、初值各多少、P 什么顺序、会不会死锁。考场上真正卡人的是这一步。

时间分配沿用算法大题那套:读题 3 分钟、画"谁等谁"图 5 分钟、写代码 12 分钟、回查 4 分钟。15 分的题,超过 25 分钟就该收手。


十四、速查表(文末收藏版)

你要找的去哪篇
四步法、生产者消费者、死锁反例P01
前驱图、同线程免费、三人种树P02
P 顺序、银行与博物馆、死锁判据P03
初始已有邮件、细粒度加锁P04
哲学家、min(m, n−1)P05
开关中断、原子 swapP06
2024 三操作缓冲区、13 题总表、审题六步P07
题干关键词 → 信号量设置本文第九节
死锁自查本文第十节
题库解析勘误本文第十一节

一句话总结:13 道题做下来,408 的 PV 大题从来不考"背模板"。它考的是——你能不能把题目里那几句"必须先……才能……",一个不漏地翻译成信号量,再确认这几张票不会把人锁死。

Logo

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目,面向数字基础设施四大核心场景(服务器、云计算、边缘计算、嵌入式),全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐