408 大题 7 篇合集导航:13 道 PV 真题,按“设几个信号量“重排一次
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、P07 | 2009(45)、2014(47)、2024(46) | ★★ |
| ② | 前驱图:几条边要发票 | P02 | 2020(45)、2022(46)、2025(45) | ★★★ |
| ③ | 限额与死锁:顺序不对就卡死 | P03、P05 | 2011(45)、2013(45)、2019(43) | ★★★★ |
| ④ | 初值与锁粒度:别想当然写 0 | P04 | 2015(45)、2017(46) | ★★★★ |
| ⑤ | 底层原子性:PV 自己怎么实现 | P06 | 2021(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 大题 06 | PV 自己也得是原子的 | 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 道真题年份索引
| 年份 | 题号 | 考什么 | 信号量要点 | 在哪篇 |
|---|---|---|---|---|
| 2009 | 45 | 三进程奇偶缓冲区 | 4 个:mutex=1、empty=N、odd=0、even=0 | P01 |
| 2011 | 45 | 银行叫号、10 个座位 | 额度 10 + 取号机互斥 1 | P03 |
| 2013 | 45 | 博物馆 500 人、一个出入口 | 容量 500 + 门互斥 1 | P03 |
| 2014 | 47 | 消费者连取 10 件 | 加一把"批锁",防止一批被切碎 | P01 |
| 2015 | 45 | 信箱辩论、初始已有邮件 | 4 个,full 初值 x / y 不是 0 | P04 |
| 2017 | 46 | 三线程复数、细粒度加锁 | 按变量拆锁,不是一把大锁 | P04 |
| 2019 | 43 | 哲学家与 m 个碗 | plate = min(m, n−1) | P05 |
| 2020 | 45 | 五操作前驱图 | 4 条边 = 4 个初值 0 | P02 |
| 2021 | 45 | 开/关中断实现 PV | 语义题,不设信号量 | P06 |
| 2022 | 46 | 两线程前驱图、最少信号量 | 5 条约束只需 2 个(同线程免费) | P02 |
| 2023 | 45 | swap 指令与临界区互斥 | 函数不能替代原子指令 | P06 |
| 2024 | 46 | 缓冲区 C1/C2/C3 | mutex=1 + full=0 | P07 |
| 2025 | 45 | 三人种树、额度与存量 | 额度和存量两个信号量不能合并 | 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 = 容量。写完先拿它验一遍,能挡掉一半初值错误。
十、死锁自查清单(按这五条过一遍)
-
P 的顺序:是不是先额度、后门?把
P(mutex)提到容量信号量前面,是最常见的死法。 -
V 方被自己挡住:执行
V(额度)的那一方,需不需要你手里这把互斥锁?需要就死锁(P03 博物馆)。 -
闭环:画一圈"谁等谁",能连成环就是死锁。破环靠少发一张入场券(
n−1、少一个碗、最多 4 人上桌)。 -
忘 V 或 V 错位置:资源真正释放才 V;门用完立刻 V。漏一个 V,跑几轮就全停。
-
初始状态:容器一开始是空的还是有货?存量初值写 0,双方可能一步都动不了(P04 信箱)。
五条里第 2 条最容易被忽略,因为它不影响"看起来对不对",只影响"会不会跑着跑着停住"。
十一、照着题库解析背,会踩的四个坑
这 7 篇里陆续抓到 4 处资料错误,都不是我推演出来的,是真跑对照后发现的:
| 处 | 题目 | 问题 |
|---|---|---|
| 1 | 2014(47) | 解析文字把 empty / full 初值写反(代码本身是对的)。判断依据:看代码里 P 的是谁 |
| 2 | 2017(46) | 评分表写「thread3 和 thread4」,题目里根本没有 4 号线程;解析代码 w.b=1 与题目 w.b=2 不符 |
| 3 | 2011(45) | 解析有 OCR 乱码,fu11 实为 full |
| 4 | 2024(46) | 第(2)问 P2 注释写成「执行 C1,从 B 中读出一个数组分组」,应为 C2、数据分组 |
另有一处不算错误但会误导:2011(42) 那类中位数题的解析复杂度写 O(n),实际 O(log n)——这属于算法系列 A11,但同一个题库,读解析时都留个心眼。
结论不是"解析不能看",是凡涉及初值、编号、变量名,一律回到题面自己数一遍。
十二、七篇反复出现的七条硬规矩
-
先数角色和容器,再动笔。 角色数决定是否要"同类互斥",容器初始状态决定存量初值。
-
互斥设 1、计数设总数、等待边设 0。 三类信号量别混。
-
同线程的边免费。 只有跨线程的约束才需要发票。
-
先 P 额度,再 P 门。 限制并发人数的信号量要提到所有其它 P 之前。
-
V 落在"资源真正释放"那一刻,别提前、别漏、别 V 到自己手里的锁上。
-
题目要求"最大程度并发"就细分锁,但别为了并发把互斥丢掉——P07 的 200/200 丢更新就是代价。
-
写完用恒等式和闭环各查一遍,四分钟,专查初值、V 位置、P 顺序这三处。
十三、怎么练
第一遍,照着敲,编译跑通,看输出和文章是否一致。多线程程序的冲突次数每次不同,别拿某一次的数字当标准答案,要看"模式"——该连续的是不是连续、该卡死的是不是卡死。
第二遍,关掉文章默写,只留题面,20 分钟写出完整 PV 代码。写不出来就回去看是哪一步断了,多半是"等待边"没数全。
第三遍,只读题面,5 分钟说思路:几个角色、几个信号量、初值各多少、P 什么顺序、会不会死锁。考场上真正卡人的是这一步。
时间分配沿用算法大题那套:读题 3 分钟、画"谁等谁"图 5 分钟、写代码 12 分钟、回查 4 分钟。15 分的题,超过 25 分钟就该收手。
十四、速查表(文末收藏版)
| 你要找的 | 去哪篇 |
|---|---|
| 四步法、生产者消费者、死锁反例 | P01 |
| 前驱图、同线程免费、三人种树 | P02 |
| P 顺序、银行与博物馆、死锁判据 | P03 |
| 初始已有邮件、细粒度加锁 | P04 |
哲学家、min(m, n−1) | P05 |
| 开关中断、原子 swap | P06 |
| 2024 三操作缓冲区、13 题总表、审题六步 | P07 |
| 题干关键词 → 信号量设置 | 本文第九节 |
| 死锁自查 | 本文第十节 |
| 题库解析勘误 | 本文第十一节 |
一句话总结:13 道题做下来,408 的 PV 大题从来不考"背模板"。它考的是——你能不能把题目里那几句"必须先……才能……",一个不漏地翻译成信号量,再确认这几张票不会把人锁死。
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目,面向数字基础设施四大核心场景(服务器、云计算、边缘计算、嵌入式),全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
图示:7 篇 = 五类题型的完整地图,下方标注 13 道真题的年份分布与篇目归属

所有评论(0)