编程语言研究书库
操作系统导论(OSTEP)

信号量与并发 bug — Dijkstra 的一个原语,和真实代码库的坑图

14 信号量与并发 bug — Dijkstra 的一个原语,和真实代码库的坑图

1. 这一章讲什么

并发部分收尾。第一块:信号量——Dijkstra 当年为「一个原语包打天下」 而造的同步原语,既能当锁、又能当条件变量、还能当资源计数器, 有界缓冲区问题用它写比锁+CV 更干净。第二块:真实世界—— Lu 等人解剖四个成熟开源项目(MySQL、Apache、Mozilla、OpenOffice) 里 105 个真实并发 bug,给出一张「坑的分布图」:非死锁的 bug 占七成且 97% 是两种形状;死锁占三成,四条件是它的诊断书。 最后一块:事件的另一条路——不写线程写状态机,把并发问题整个换掉。

2. 顶层全景

  信号量 = 一个整数值 + 两个原子操作:
    sem_wait():值减 1;减完 < 0 就睡(等待者数 = 负的值)
    sem_post():值加 1;有等待者就 wake 一个
    初值的口诀:初始化后你愿意立刻送出去多少资源
      =1 → 锁;=0 → 「等事件发生」;=N → N 个槽位的资源池
        │
  真实 bug 分布(Lu et al. 105 个):
    非死锁 74 个:原子性违背(check 与 use 之间被插了一脚)+ 顺序违背(该先发生的后发生)
    死锁 31 个:四条件(互斥/持有并等待/不可剥夺/循环等待)⇒ 破一个即可预防
        │
  另一条路:事件驱动(select 循环 + 状态机)── 没有共享状态就没有锁;
    代价:手工状态管理、阻塞调用是毒药

图说:三块合起来是「原语—病理—替代路线」的完整闭环。

3. 核心原理

3.1 信号量:定义与主线例子

信号量就是一个带两个原子操作的整数1:

sem_wait(sem_t *s)  { s 减 1;若 s < 0,睡 }
sem_post(sem_t *s)  { s 加 1;若有等待者,叫 醒一个 }

负值的绝对值 = 正在睡等它的线程数——这个不变量值得记住2。 Dijkstra 当年叫它们 P() 和 V()(荷兰语词源至今有争议, pyrimidine「用荷兰语版在朋友面前炫」)3。

初值的口诀(Perry Kivolowitz 的版本,书里的旁注): 初值 = 初始化之后你愿意立刻拱手送出的资源数4。

  • **当锁用:初值 = 1。**T0 调 wait:1→0,不睡,进临界区; T1 调 wait:0→−1,睡(图 31.5 的完整轨迹:值 1 → 0 → −1 → 0 → 1, T1 在 −1 处睡、在 T0 post 后被叫醒)5。
  • **当顺序控制用:初值 = 0。**还是 join 问题:父 wait(0→−1,睡)、 子 post(−1→0,叫醒父);若子先跑完,post 把值抬到 1, 父后来的 wait 减到 0 直接返回——两种时序都对6。
  • 当有界缓冲区用:两个信号量。empty 初值 = MAX(空位数), full 初值 = 0(已有货数);生产者 wait(empty) 后放货、post(full); 消费者 wait(full) 后取货、post(empty)。锁+CV 那章要两条件变量
    • 一把锁才能讲清的东西,这里初值本身就编码了条件—— 这是信号量「值即状态」的优雅之处7。

3.2 真实 bug 的分布图(Lu et al.,105 个)

书里引用 Lu 等人对 MySQL/Apache/Mozilla/OpenOffice 四个项目的实证: 共 105 个并发 bug——74 个非死锁(Mozilla 一家就 57 个)、 31 个死锁8。非死锁的那 74 个里,97% 是两种形状9:

原子性违背(atomicity violation)——「检查」和「使用」之间被插了一脚 (MySQL 实例):T1 先 if (thd->proc_info) 再 fputs(thd->proc_info); T2 把 proc_info 置 NULL。T1 在 if 之后、fputs 之前被切走, 回来就向 NULL 解引用,崩。Lu 的正式定义:本意原子的代码区 没有被强制原子10。修法朴素:把检查和使用一起包进同一把锁11。

顺序违背(order violation)——「A 必须先于 B」没有被强制 (Mozilla 实例):T2 是新线程的入口,它假设 T1 已经设好了 mThread; 若 T2 先跑,读 NULL,崩。正式定义:两个内存访问的期望顺序被颠倒12。 修法:状态变量 + 条件变量(或信号量)把顺序钉死—— 正是上一章 join 问题的同款解法13。

为什么值得背这两类名:它们是检查并发代码的查问清单—— 审任何多线程代码,先问「哪些 check-use 对必须原子?哪些操作间有先后假设?」

3.3 死锁:四条件与它的工程处方

死锁的最小形态14:T1 拿 L1 等 L2,T2 拿 L2 等 L1—— 互相等,图上出现环。发生的四个必要条件(Coffman 条件)15:

条件含义预防法(打破它)
互斥锁一次只属一个线程用无锁结构(难、少见)
持有并等待拿着 A 等 B一把「预防锁」包住所有加锁动作;或一次全拿
不可剥夺锁不能强行没收trylock 抢不到就全放、重试
循环等待等锁关系成环全序/偏序加锁——最实用

图说:第四行的「全序加锁」是工程主力:所有锁排一个总序, 人人按序拿,环就不可能出现。锁多了排不了总序就排偏序 (Linux 内存映射代码的注释里列着十组加锁顺序,从 "i_mutex before i_mmap_rwsem" 到四锁链——书里的真实例子16)。 封装是死锁的帮凶:Java 的 v1.AddAll(v2) 会内部同时锁 v1、v2, 对面同时 v2.AddAll(v1) 就死——接口设计本身在邀请你死锁17。 小技巧:不知道顺序时,按锁地址排序(谁地址大谁先拿), 程序性地保证全序18。更高级的两招书里点到为止: 避免(银行家算法,事前检查会不会不安全)和 检测+恢复(发现环就踢掉一个线程回滚——数据库的路数)19。

3.4 另一条路:事件驱动并发

线程不是并发的唯一形状。GUI 和互联网服务器里流行事件驱动: 一个线程跑一个事件循环——select()/poll() 问内核「哪个 fd 有事?」, 对每个就绪 fd 调一小段事件处理代码(读请求→解析→回响应), 处理完回到循环20。它把并发的三大麻烦整个换掉: 没有共享状态就没有锁;没有切换就没有竞态;调度权回到程序员手里。

代价也清楚:处理函数里任何阻塞调用(磁盘 I/O、页错误)卡住 整个循环——所以事件驱动程序的世界里全是非阻塞 I/O 和 手工状态机(「上次读到一半,这次接着读」的状态要自己存); 状态多了代码比多线程还难懂21。node.js 是这条路的现代代表, 根子在 UNIX 的 select 和 C10K 问题的挣扎22。

收尾对话章里教授的三条朴素建议值得作为本部分的判词: 保持简单;只在绝对需要时上并发;真要并行,找简化的形式 (比如 MapReduce)23。

4. 作者的判断与证据

书里给了证据的判断:

  • 105 个 bug 的分类统计有原始论文 [L+08] 背书;
  • 两种非死锁 bug 各有真实项目(MySQL/Mozilla)的最小复现1012;
  • 四条件是经典结论 [C+71],预防法各配了 Linux 代码级实例1516。

作者的判断(立场):

  • 「97% 的非死锁 bug 是两种形状」被作者推广成程序员自查清单, 也是自动检查工具该主攻的方向9。
  • 事件驱动一节明说是「高级」选读,作者对两条路不站队, 只摆「控制换状态机」的交换条件。

5. 边界与局限

  • Lu 研究的是 2008 年前的四个 C/C++ 项目;如今 Rust 等语言 用所有权在编译期消灭一整类原子性违背——书中图景对「系统语言」 仍成立,对带 GC/所有权的语言要打折(补充,不在书里)。
  • 信号量一节故意「只讲使用、不讲实现」;由锁+CV 搭信号量、 反向也行的构造习题,留给读者。
  • 死锁的「避免/检测」两招只有轮廓;真要做到数据库级事务(一组要么全成、要么全不成的操作)的严格保证, 还得回 Gray 的事务处理圣经(参考文献 [GR92])。

6. 可带走的

  1. 初值口诀:信号量初值 = 愿意立刻送出的资源数。 1 = 锁,0 = 等事件,N = 资源池。记住它,信号量类问题都变成数数。
  2. 信号量把「条件」编码进值里,比锁+CV 少写状态变量—— 但有界缓冲区的 CV 版更能看清「等待-唤醒」的本质。两个都该会。
  3. 审并发代码两问:哪些 check-use 必须原子(原子性违背)? 哪些操作有先后假设(顺序违背)?97% 的坑在这里。
  4. 死锁四条件 = 诊断书;全序加锁 = 最便宜的药; 封装内部偷偷加锁 = 最阴险的病源。
  5. 事件驱动不是银弹,是换一种付账方式:用状态机复杂度 换掉锁和切换。选型前问自己:瓶颈是计算、I/O 等待,还是状态管理?
  6. 「保持简单;只在必要时并发」——这是全书并发部分的落点, 也是最常被违背的一条。

7. 原文地图

主题原书章原文位置
信号量定义与 wait/post31. Semaphorestext/33-ch31-31-semaphores.txt:37(搜「sem_init」)与:69(搜「sem_wait」)
负值 = 等待线程数31. Semaphorestext/33-ch31-31-semaphores.txt:64(搜「negative」)
P/V 词源31. Semaphorestext/33-ch31-31-semaphores.txt:29(搜「passering」)
当锁用:两线程轨迹31. Semaphorestext/33-ch31-31-semaphores.txt:94(搜「Binary Semaphores」)与:129(搜「Thread Trace」)
当顺序控制用:join 两情形31. Semaphorestext/33-ch31-31-semaphores.txt:172(搜「Ordering」)与:227(搜「Case 1」)
初值口诀31. Semaphorestext/33-ch31-31-semaphores.txt:279(搜「give away」)
有界缓冲区:empty/full31. Semaphorestext/33-ch31-31-semaphores.txt:265(搜「Bounded Buffer」)
105 bug 分布表32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:33(搜「105」)
原子性违背(MySQL 例)32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:58(搜「Atomicity-Violation」)
顺序违背(Mozilla 例)与修复32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:108(搜「Order-Violation」)
97% 两类形状32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:186(搜「97%」)
死锁示例与依赖图32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:197(搜「Deadlock」)与:221(搜「Dependency Graph」)
四条件32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:264(搜「Four conditions」)
全序/偏序与 Linux 实例32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:280(搜「Circular Wait」)与:291(搜「memory mapping」)
封装与 AddAll 陷阱32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:246(搜「encapsulation」)
按地址排序加锁32. Common Concurrency Problemstext/34-ch32-32-common-concurrency-problems.txt:298(搜「LOCK ADDRESS」)
事件驱动的问题动机33. Event-based Concurrency (Advanced)text/35-ch33-33-event-based-concurrency-advanced.txt:11(搜「two-fold」)
并发部分三条建议34. Summary Dialogue on Concurrencytext/36-ch34-34-summary-dialogue-on-concurrency.txt:17(搜「keep it simple」)

Footnotes

  1. 出处:「31. Semaphores」第 39–78 段(text/33-ch31-31-semaphores.txt:69,搜「sem_wait」)。 ↩

  2. 出处:「31. Semaphores」第 64–67 段(text/33-ch31-31-semaphores.txt:64,搜「negative」)。 ↩

  3. 出处:「31. Semaphores」第 27–34 段(text/33-ch31-31-semaphores.txt:29,搜「passering」)。 ↩

  4. 出处:「31. Semaphores」第 273–285 段(text/33-ch31-31-semaphores.txt:279,搜「give away」)。 ↩

  5. 出处:「31. Semaphores」第 94–170 段(text/33-ch31-31-semaphores.txt:149,搜「Thread Trace」)。 ↩

  6. 出处:「31. Semaphores」第 172–263 段(text/33-ch31-31-semaphores.txt:239,搜「Case 1」)。 ↩

  7. 出处:「31. Semaphores」第 265–400 段(text/33-ch31-31-semaphores.txt:287,搜「First Attempt」)。 ↩

  8. 出处:「32. Common Concurrency Problems」第 28–49 段(text/34-ch32-32-common-concurrency-problems.txt:33,搜「105」)。 ↩

  9. 出处:「32. Common Concurrency Problems」第 185–191 段(text/34-ch32-32-common-concurrency-problems.txt:186,搜「97%」)。 ↩ ↩2

  10. 出处:「32. Common Concurrency Problems」第 58–106 段(text/34-ch32-32-common-concurrency-problems.txt:81,搜「serializability」)。 ↩ ↩2

  11. 出处:「32. Common Concurrency Problems」第 87–106 段(text/34-ch32-32-common-concurrency-problems.txt:93,搜「proc_info_lock」)。 ↩

  12. 出处:「32. Common Concurrency Problems」第 108–183 段(text/34-ch32-32-common-concurrency-problems.txt:164,搜「flipped」)。 ↩ ↩2

  13. 出处:「32. Common Concurrency Problems」第 167–183 段(text/34-ch32-32-common-concurrency-problems.txt:128,搜「mtLock」)。 ↩

  14. 出处:「32. Common Concurrency Problems」第 197–216 段(text/34-ch32-32-common-concurrency-problems.txt:203,搜「deadlock」)。 ↩

  15. 出处:「32. Common Concurrency Problems」第 263–277 段(text/34-ch32-32-common-concurrency-problems.txt:264,搜「Four conditions」)。 ↩ ↩2

  16. 出处:「32. Common Concurrency Problems」第 279–330 段(text/34-ch32-32-common-concurrency-problems.txt:291,搜「memory mapping」)。 ↩ ↩2

  17. 出处:「32. Common Concurrency Problems」第 246–262 段(text/34-ch32-32-common-concurrency-problems.txt:246,搜「encapsulation」)。 ↩

  18. 出处:「32. Common Concurrency Problems」第 298–319 段(text/34-ch32-32-common-concurrency-problems.txt:298,搜「LOCK ADDRESS」)。 ↩

  19. 出处:「32. Common Concurrency Problems」第 357–500 段(text/34-ch32-32-common-concurrency-problems.txt:357,搜「No Preemption」)。 ↩

  20. 出处:「33. Event-based Concurrency (Advanced)」第 9–60 段(text/35-ch33-33-event-based-concurrency-advanced.txt:11,搜「two-fold」)。 ↩

  21. 出处:「33. Event-based Concurrency (Advanced)」第 60–200 段(text/35-ch33-33-event-based-concurrency-advanced.txt:61,搜「select」)。 ↩

  22. 出处:「33. Event-based Concurrency (Advanced)」第 1–8 段(text/35-ch33-33-event-based-concurrency-advanced.txt:9,搜「node.js」)。 ↩

  23. 出处:「34. Summary Dialogue on Concurrency」第 20–40 段(text/36-ch34-34-summary-dialogue-on-concurrency.txt:17,搜「keep it simple」)。 ↩

加锁的数据结构与条件变量 — 先量再优化的计数器,和「等一个条件」的正确姿势

Previous Page

I/O 与磁盘 — 中断和 DMA 解放 CPU,RAID 用冗余换可靠

Next Page

On this page

14 信号量与并发 bug — Dijkstra 的一个原语,和真实代码库的坑图1. 这一章讲什么2. 顶层全景3. 核心原理3.1 信号量:定义与主线例子3.2 真实 bug 的分布图(Lu et al.,105 个)3.3 死锁:四条件与它的工程处方3.4 另一条路:事件驱动并发4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes