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

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

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

1. 这一章讲什么

锁到手之后,两件事马上来:怎么把它加到数据结构上不犯错, 和锁解决不了的那类问题。第一件比看起来阴险——加锁的正确性 好办,性能却可能灾难(一个共享计数器,四个线程比单线程慢 一百多倍);第二件是:线程常常需要等一个条件成立 (缓冲区非空、孩子线程跑完),干等烧 CPU,睡错了死锁。 条件变量就是为「等」而生的原语,但它有严格的使用纪律。

2. 顶层全景

  加锁的数据结构:
    起步:一把锁包住全部操作 ── 正确、简单;先量,不够再优化
    计数器的扩展瓶颈:所有 CPU 抢一把锁 → 近似计数器
      (每核本地计数 + 阈值 S 才汇总到全局;S 调性能与精确的权衡)
    链表的两个坑:失败路径别忘了 unlock;锁的范围越小越好(只锁真临界区)
        │
  锁管不了的「等」:
    自旋等条件 ── 烧 CPU
    条件变量:wait(释放锁+睡) / signal(叫醒一个)
    三条纪律:wait 外面必须 while 不是 if;signal/wait 都要持锁;
             不同条件用不同 CV

图说:上半是「加锁的科学与手艺」,下半是「睡与醒的纪律」。

3. 核心原理

3.1 主线例子:计数器,从零到一百七十倍

**起点:一把锁包一切。**结构体里塞一个 mutex,增删查各 lock/unlock 一次。正确性完工。性能实测(书里的数字):iMac 四核 i5, 单线程加一百万次用时约 0.03 秒;两个线程各加一百万次, 用时 超过 5 秒——多了 170 倍,线程越多越糟1。 原因不用猜:所有核的每次自增都在抢同一把锁,锁的来回比加法本身贵。

优化:近似计数器(approximate counter)。一个逻辑计数器 = 每核一个本地计数器 + 一个全局计数器,各配一把锁。 线程只加自己核的本地计数(几乎无竞争);本地累计到门槛值 S(这个可调的门栏叫阈值) 才抓全局锁、把本地值倒进全局、清零2。

书里的轨迹(S=5,4 个核):L1 数到 5 时把 5 倒进 G,L4 数到 5 再倒 5, G 变 10……本地账和全局账之间,最多差「核数 × S」3。 实测:S=1024 时,四线程四百万次加法的时间和单线程一百万次几乎一样—— 性能回来了,精确性让了步(全局读数是近似值,最多滞后 4×1024)4。

这个权衡的旋钮就是 S:S 小 ≈ 精确版(慢),S 大 ≈ 飞快的近似版。 「更并发不一定更快」是本章的判词:每加一把锁都是开销, 唯一诚实的验证是把两个版本都写出来跑 benchmark5。

3.2 链表的两个真实教训

教训一:失败路径上的 unlock。带锁 insert 里,malloc 失败要 return −1——别忘了先 unlock。这种「很少走的路径」正是 bug 重灾区: 一项对 Linux 内核补丁的研究发现,近 40% 的 bug 出在这类罕见路径上6。 解法是把锁收窄:malloc 在锁外做(反正 malloc 自己线程安全), 锁只包住真正改链表的那两行;罕见路径自然不再持锁7。

**教训二:锁的粒度从粗到细是拿复杂度换并发。**一把大锁 (coarse-grained)防所有临界区最简单;给每个节点配一把锁 (fine-grained)能让更多线程并行,但代码和死锁面都翻倍。 书里给的方向:够用就别动;不够用时,先量,再决定动哪里5。

3.3 条件变量:join 问题的正确解

先看需求:父线程要等子线程跑完再往下走。naive 版用一个 volatile int done 自旋——烧 CPU 且可能错8。

条件变量是一个显式的等待队列:状态不对时线程把自己挂进 队列睡(wait);改状态的线程从队列里叫醒一个(signal)。 名字来自 Hoare 的管程工作,思想可追溯到 Dijkstra 的「私有信号量」9。

join 的正确实现(图 30.3,照抄骨架)10:

void thr_exit() {
    lock(m); done = 1; signal(c); unlock(m);   // 改状态 + 叫醒
}
void thr_join() {
    lock(m);
    while (done == 0)                            // 注意是 while
        wait(c, m);                              // 原子地:放锁 + 入睡
    unlock(m);
}

两个细节是全章的纪律:

  1. wait(c, m) 带着锁进来:它把「释放锁」和「入睡」合成一个 原子动作——否则「刚放锁还没睡」的缝里,signal 来了就永远错过 (图 30.5 的无锁版展示了这个经典翻车:子线程 signal 时父线程 还没睡下,signal 落空,父睡死)11。
  2. 醒来要重新抢锁才能从 wait 返回——防止醒来的瞬间条件 又被别人改掉。

3.4 翻车考古:三个错误版本,三种死法

书里故意给出三个错误实现,每种错对应一条纪律12:

错误版死法教出的纪律
去掉状态变量 done(图 30.4)子先跑完、signal 落空,父再 wait 无人来叫,死锁必须有一个记录状态的变量;睡与醒都围绕它
去掉锁(图 30.5)「检查 done」与「睡下」之间被插入子线程的 signal,signal 落空,父死睡wait/signal 必须持锁,锁把检查和等待焊成一个临界区
join 用 if 而非 whileMesa 语义下,醒来时条件可能已不成立,直接往下跑出错永远用 while 重查条件

图说:这张表是条件变量「三条纪律」的来历——每条都不是风格要求, 是某一种具体死法的疫苗。

3.5 生产者/消费者:为什么一个 CV 不够

Dijkstra posed 的 bounded-buffer 问题:生产者放、消费者取, 缓冲区满了生产者等、空了就消费者等13。

**错误版(单 CV + if)**的翻车轨迹(书里的图 30.9,两个消费者 Tc1/Tc2 + 一个生产者):Tc1 发现空,睡;Tp 放数、signal 叫醒 Tc1 (注意:只是移回就绪,还没跑);Tp 发现满,睡;Tc2 插队抢到锁、 把数取走、还 signal 叫醒了 Tp;轮到老实的 Tc1 跑——它从 wait 返回 (锁也回来了),直奔 get(),缓冲区却是空的,断言爆炸14。

两针疫苗:while 替代 if(醒来后重查条件,发现空就接着睡), 和两个条件变量(「非空」「非满」各一个 CV,谁等哪个条件 就挂在哪个队列——signal 不再错配对象)15。修好之后, 这套结构就是 grep | wc 背后的内核管道、线程池任务队列的原型: 一个缓冲区 + 两个条件 + 一把锁,是并发编程出现频率最高的骨架。

Mesa 语义(顺带留名):POSIX 的 signal 只是「建议你去看看」, 不保证醒来时条件还成立——所以 while 是硬性纪律,不是洁癖16。

4. 作者的判断与证据

书里给了证据的判断:

  • 计数器 0.03 秒 → 5 秒的实测曲线,和近似计数器 S=1024 的恢复曲线14;
  • 40% 罕见路径 bug 的研究引自 Linux 内核补丁实证6;
  • 三个错误版各有完整的线程轨迹图(图 30.4/30.5/30.9)1214。

作者的判断(立场):

  • 「简单方案先上,量了不够再优化」是明确的工程立场, 甚至反对「为了并发而并发」5。
  • 「不量不知道」直接说破:性能的事,build both and measure。

5. 边界与局限

  • 近似计数器牺牲的是可线性化(linearizability)语义; 对「全局精确读」有刚需的场合不适用。
  • 链表的手锁版(fine-grained,如 hand-over-hand locking) 本书没展开,留给文献——那是性能极限玩家的领域,代价是正确性风险。
  • 条件变量一节全是 POSIX 语义;其他生态(Java 的 wait/notify、 C++ 的 condition_variable)同宗但细节有别,纪律通用。

6. 可带走的

  1. 先正确、再量、再优化——顺序反了的代价大于优化的收益。
  2. 共享计数器是锁争用的教科书病;「本地累计 + 定期汇总」 是治它的通用方(数据库缓冲、指标统计里到处都是)。
  3. 锁的粒度:粗锁是设计起点不是耻辱;细锁的每一分并发 都要用死锁面和代码量付账。
  4. 条件变量三纪律:while 重查;持锁 signal;每个条件一个 CV。
  5. 「状态变量 + 锁 + 条件变量」三件套必须同时存在, 缺一件都有对应的死法可查。
  6. 生产者/消费者骨架值得默写:它是管道、线程池、事件队列的共同原型。

7. 原文地图

主题原书章原文位置
加锁计数器与 0.03s→5s 实测29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:76(搜「0.03」)
近似计数器设计29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:124(搜「approximate counter」)
S=5 的轨迹29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:155(搜「threshold」)
S=1024 的性能恢复29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:162(搜「1024」)
「更并发不一定更快」29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:246(搜「ISN'T NECESSARILY」)
40% 罕见路径 bug29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:268(搜「40%」)
链表:锁收窄到临界区29. Lock-based Concurrent Data Structurestext/31-ch29-29-lock-based-concurrent-data-structures.txt:275(搜「rearrange」)
自旋等条件的低效30. Condition Variablestext/32-ch30-30-condition-variables.txt:32(搜「spin」)
条件变量定义30. Condition Variablestext/32-ch30-30-condition-variables.txt:65(搜「queue that threads」)
join 正确版30. Condition Variablestext/32-ch30-30-condition-variables.txt:80(搜「done = 0」)
wait 的原子放锁+入睡30. Condition Variablestext/32-ch30-30-condition-variables.txt:369(搜「releases the lock」)
无锁版翻车30. Condition Variablestext/32-ch30-30-condition-variables.txt:189(搜「No Lock」)
持锁 signal 的提示30. Condition Variablestext/32-ch30-30-condition-variables.txt:205(搜「HOLD THE LOCK」)
生产者/消费者问题由来30. Condition Variablestext/32-ch30-30-condition-variables.txt:244(搜「Dijkstra」)
单 CV 翻车轨迹30. Condition Variablestext/32-ch30-30-condition-variables.txt:394(搜「Thread Trace」)

Footnotes

  1. 出处:「29. Lock-based Concurrent Data Structures」第 53–78 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:76,搜「0.03」)。原文:单线程一百万次约 0.03 秒;双线程各一百万次超过 5 秒。 ↩ ↩2

  2. 出处:「29. Lock-based Concurrent Data Structures」第 122–154 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:124,搜「approximate counter」)。 ↩

  3. 出处:「29. Lock-based Concurrent Data Structures」第 155–160 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:155,搜「threshold」)。轨迹:G 在 L1、L4 各到 5 时变 5、10。 ↩

  4. 出处:「29. Lock-based Concurrent Data Structures」第 161–164 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:162,搜「1024」)。 ↩ ↩2

  5. 出处:「29. Lock-based Concurrent Data Structures」第 246–254 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:246,搜「ISN'T NECESSARILY FASTER」)。 ↩ ↩2 ↩3

  6. 出处:「29. Lock-based Concurrent Data Structures」第 266–271 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:268,搜「40%」)。 ↩ ↩2

  7. 出处:「29. Lock-based Concurrent Data Structures」第 272–287 段(text/31-ch29-29-lock-based-concurrent-data-structures.txt:275,搜「rearrange」)。 ↩

  8. 出处:「30. Condition Variables」第 31–53 段(text/32-ch30-30-condition-variables.txt:32,搜「spin」)。 ↩

  9. 出处:「30. Condition Variables」第 62–71 段(text/32-ch30-30-condition-variables.txt:65,搜「queue that threads」)。 ↩

  10. 出处:「30. Condition Variables」第 80–112 段(text/32-ch30-30-condition-variables.txt:80,搜「done = 0」)。 ↩

  11. 出处:「30. Condition Variables」第 180–199 段(text/32-ch30-30-condition-variables.txt:189,搜「No Lock」)。 ↩

  12. 出处:「30. Condition Variables」第 148–199 段(text/32-ch30-30-condition-variables.txt:156,搜「broken」)。 ↩ ↩2

  13. 出处:「30. Condition Variables」第 241–267 段(text/32-ch30-30-condition-variables.txt:244,搜「Dijkstra」)。 ↩

  14. 出处:「30. Condition Variables」第 365–404 段(text/32-ch30-30-condition-variables.txt:394,搜「Thread Trace」)。 ↩ ↩2

  15. 出处:「30. Condition Variables」第 405–560 段(text/32-ch30-30-condition-variables.txt:522,搜「while (count == 1)」)。修正版见图 30.12(:542,搜「Two CVs」)与「use two condition variables」(:551)。 ↩

  16. 出处:「30. Condition Variables」第 405–460 段(text/32-ch30-30-condition-variables.txt:415,搜「Mesa semantics」)。原文:几乎所有系统都采用 Mesa 语义,因此醒来后必须重查条件。 ↩

锁 — 从一条硬件指令到睡得着的锁

Previous Page

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

Next Page

On this page

13 加锁的数据结构与条件变量 — 先量再优化的计数器,和「等一个条件」的正确姿势1. 这一章讲什么2. 顶层全景3. 核心原理3.1 主线例子:计数器,从零到一百七十倍3.2 链表的两个真实教训3.3 条件变量:join 问题的正确解3.4 翻车考古:三个错误版本,三种死法3.5 生产者/消费者:为什么一个 CV 不够4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes