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

1. 这一章讲什么¶

上一章立了问题:临界区需要互斥,互斥需要原子性。本章造锁。它是一场三级跳:硬件先给一两条原子指令(test-and-set 们); 操作系统再给「睡与醒」(park/unpark);程序员最后拿到一把既正确又公平还不浪费 CPU 的锁。中间每一跳都踩着前一跳的缺陷前进—— 失败不是插曲,是设计的主线。

2. 顶层全景¶

  尝试一:关中断 ── 单 CPU 有效;信任问题、丢中断、多核无效 → 只限内核自用
  尝试二:普通 load/store 标志位 ── 测试与设置之间可切换,两个线程都进了临界区
  尝试三:test-and-set 自旋锁 ── 正确!但无公平保证,单 CPU 上烧整个时间片
  尝试四:票锁(fetch-and-add)── 公平了(按票叫号),还是在自旋
  尝试五:yield 让出 ── 少烧 CPU,但上下文切换贵,还防不了饿死
  尝试六:park/unpark + 等待队列 ── 睡而不是转;公平 + 不浪费
  工程终态:futex ── 无争用时只付一次原子操作;争用时才陷入内核

图说:六跳的每一跳都不是「更好」,而是「堵上一跳的洞」。锁的历史就是「洞—补丁—新洞」的链条。

3. 核心原理¶

3.1 评估三把尺与两种错误起点¶

评价任何锁实现,先立三把尺¹:正确性(真能提供互斥吗)、 公平性(排队的线程会不会饿死)、性能(分三种场景: 无争用、单 CPU 上多线程争用、多 CPU 上争用——同一个锁在三种场景下表现完全不同)。

错误起点一:关中断。单 CPU 上,进临界区关中断 = 不可被打断 = 原子。但三宗罪:它把特权操作交给任意程序(恶意程序关中断死循环, 系统只能重启);多核上根本无效(别的核照样跑);关久了丢中断, 磁盘完成了读却没人知道²。结论:只在内核自己用(内核信自己)³。

错误起点二:普通标志位(load/store)。十行代码,看似对:

void lock(lock_t *m) {
    while (m->flag == 1) ;  // 测试:有人持有就空转
    m->flag = 1;            // 设置:我拿下了
}

为什么错:测试和设置是两步。书里的交错轨迹:T1 测试 flag=0, 正要设置,中断;T2 测试 flag=0,设置 1,进临界区;切回 T1, 继续设置 1——两个线程都进了临界区⁴。外加性能病: 空等时死循环检查(spin-waiting),在单 CPU 上是纯烧时间片⁵。

顺带一个「用锁」的权衡:粒度。前面都在造一把锁;真用起来还有一道选择题。粗粒度(coarse-grained):一把大锁,任何线程进任何临界区都抢它,简单,但任意两个临界区互相串行。 细粒度(fine-grained):不同的数据、数据结构各配一把锁, 不相关的临界区互不阻塞,同时待在锁里的线程多得多,并发立刻上去 ²¹;代价是要管理多把锁以及拿锁的顺序——顺序拿错了就是死锁, 那是第 14 章的主题。POSIX 的 mutex 用法里藏着这个提示: lock/unlock 都要把一个锁变量传进去,正因为一个程序里本来就可以有好几把锁。

3.2 主线例子:TestAndSet 为什么一次就对¶

硬件出手:把「测试旧值、写入新值」做成一条不可分割的指令 (test-and-set;x86 的 lock xchg,SPARC 的 ldstub)⁶:

int TestAndSet(int *ptr, int new) {
    int old = *ptr;   // 取旧值
    *ptr = new;       // 写新值
    return old;       // 返回旧值 —— 三步,硬件保证原子
}

锁的完整实现只有一行核心:

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ; // 返回 1 = 别人持有,自旋;返回 0 = 我拿到了
}

走一遍两种情形⁷:没人持锁(flag=0):第一次调用返回旧值 0, 原子地写成 1——获得锁。有人持锁(flag=1):每次调用都返回 1 (同时写 1,无害),线程原地自旋直到持有者 unlock() 清 0; 下一次 TestAndSet 返回 0,抢锁成功。「测试」和「设置」之间再没有缝可插。

按三把尺评分:正确性 ✓;公平性 ✗(纯靠运气,可能永远抢不到, 会饿死);性能——单 CPU 上很糟(持有者被抢占,其余 N−1 个线程各烧掉一整个时间片自旋),多核上可以接受(临界区短的话, 在另一个核上等一会儿不算浪费)⁸。

这里藏着一句没说出口的前提:「单 CPU 上很糟」的分析本身就假定调度器是抢占式的。自旋锁在单 CPU 上要想还能进展,必须靠定时器中断把烧 CPU 的自旋者强行拽下去、把持有者换上来; 没有抢占,自旋的线程永远不放手 CPU,持有者永远轮不到运行, 锁永远等不到——所以原书说,没有抢占式调度器,自旋锁在单 CPU 上「没多大意义」²⁰。

3.3 原子指令家族与票锁¶

各架构的原子原语不止一种,书里给了全家福⁹:

原语	语义	造出来的锁
test-and-set / xchg	返回旧值,写入新值	基本自旋锁
compare-and-swap	旧值==预期才写入,返回旧值	同上,更通用(无锁结构的基础)
load-linked / store-conditional	LL 读,SC 写——中间没人碰过才成功	同上(MIPS/ARM/Power)
fetch-and-add	原子加一,返回旧值	票锁(ticket lock)

图说:票锁是本章的亮点。每个想进临界区的线程先 FetchAndAdd(&ticket) 取号(myturn),然后等全局 turn == myturn 才进; unlock 就是 turn += 1——叫下一个号¹⁰。公平性就此解决:一旦拿到号,前面的人过完必轮到你。 (历史旁注:Dijkstra 时代没有原子指令,Dekker 和 Peterson 用纯 load/store 写出了正确算法;它们既复杂又死在现代内存模型的乱序上, 成了「理论练习的绝唱」¹¹。)

3.4 从「转」到「睡」:yield、队列与 futex¶

票锁公平了,但等待方式还是烧 CPU。两阶改良:

第一阶:yield。拿不到锁就 yield() 让出 CPU(自己从运行态挪回就绪态)。两个线程时很好;100 个线程争一把锁时, 99 个轮流「跑一次、yield 一次」才轮到持有者运行—— 上下文切换的代价又成了新的浪费,且依然不防饿死¹²。

第二阶:队列 + park/unpark。Solaris 提供一对原语: park() 让线程睡死,unpark(tid) 点名唤醒。锁里加一个等待队列:拿不到锁的线程把自己登记进队列、释放保护标志、然后 park 睡觉;unlock 时不只清标志,而是从队列头取一个线程点名唤醒,并把锁「预支」给它¹³。等待者睡了不占 CPU, 唤醒是点名制所以公平。这是现代互斥锁的标准结构。

但这套结构自己还留着一个竞态。缝在「登记进队列、放掉 guard」和「park()」之间:等待者已经决定了要睡,可还没睡;这时被切换走, 锁持有者恰好运行,unlock 从队列里取出的正是这个等待者, unpark 发出——没人接住:等待者还没 park,唤醒信号当场蒸发; 等调度器切回来,等待者执行迟到的 park(),一睡不醒。这个洞叫 wakeup/waiting race:唤醒发生在等待完成之前,信号丢失¹⁸。

Solaris 的堵法是加第三个系统调用 setpark():线程在放掉 guard 之前先 setpark(),声明「我马上要 park」¹⁹。语义只有一条: 如果 unpark 抢在真正的 park() 之前到达,这次 park 不再睡觉、立即返回。于是一条原本会蒸发的唤醒变成了粘住的唤醒—— 竞态窗口没有被消除,而是被填进了缓冲:窗口里到达的唤醒先记账,等 park 落地时兑现。改动只有一行,插在 queue_add 和 guard = 0 之间。(另一条路是把 guard 一起带进内核,让内核原子地「放锁 + 睡下」,从根上取消这个窗口; 代价是要给内核加专门支持¹⁸。)

工程终态:futex( Linux )。队列锁在「无争用」的常见情形下也白付一次系统调用,可惜。futex 的思路是两阶段锁: 先只查一次用户态标志(无争用时:一次原子操作 + 一次查,完事, 零内核介入);只有在真的争用时才陷入内核走队列¹⁴。于是「没人抢」这个最常见的情形,便宜到几乎免费。

3.5 一个比性能更狠的理由:优先级反转¶

旁注里有个全书最生动的案例¹⁵:高优先级线程 T3 等一把被低优先级 T1 持有的锁;中优先级 T2 一堆计算活,把 T1 压在 CPU 下—— T3 优先级最高却干等,系统实际被中优先级统治。纯自旋版本更惨(火星探测器 Pathfinder 的事故): T2 自旋等 T1 的锁,而 T1 永远轮不到 CPU,死锁。解法:不用自旋锁;或优先级继承(等待者把自己的高优先级临时借给持有者,让它跑完临界区);最简单的偷懒:所有线程同优先级。

4. 作者的判断与证据¶

书里给了证据的判断:

纯标志位失败有完整的两线程交错轨迹(图 28.2)⁴;
票锁的公平保证有明确论证(拿到号 ⇒ 必被叫到)¹⁰;
优先级反转是引用真实事故(火星 Pathfinder)的案例¹⁵。

作者的判断(立场):

「把调度器想成恶意的」是本书推荐的思考法:不需要高概率, 只要一种可能的交错搞砸,方案就不成立¹⁶。
Lauer 定律(「代码越少越好」)被引用来为 futex 式的「常见路径极简」背书¹⁷。

5. 边界与局限¶

本章的锁都假设临界区「短」。长临界区(遍历大链表)下, 等待成本分析完全不同——第 13 章的并发数据结构接着讨论。
两阶段锁/futex 的讨论停在「用户态快路径 + 内核慢路径」, 没展开现代实现里的自适应自旋(adaptive spinning, 等一会儿再睡)——那是性能的下一层微调(补充,不在书里)。
内存序(memory ordering)问题被一笔带过(Peterson 算法「死在乱序上」),而真实锁实现必须配内存屏障——这是现代并发编程最容易被教科书略掉的坑。

6. 可带走的¶

锁 = 原子指令 + 睡眠机制。理解任何锁实现,先问: 原子原语是什么?等待者睡还是转?
测试+设置分成两条普通指令 = 必错;合成一条原子指令 = 正确。并发的正确性常常就差「不可分割」四个字。
三把尺记牢:正确、公平、性能(且性能要分场景测)。「这个锁很快」是无意义的句子。
自旋只在「等得短」且「核够多」时合理;否则睡觉。
票锁思想(取号叫号)是公平的通用模板,不止于锁—— 任何「排队资源」都能用。
优先级反转:资源共享让优先级形同虚设。遇到「高优先级任务莫名卡顿」,先查它是不是在等一个低优先级任务手里的锁。

7. 原文地图¶

主题	原书章	原文位置
锁的语义与 mutex	28. Locks	`text/30-ch28-28-locks.txt:30`(搜「lock variable」)
评估三把尺	28. Locks	`text/30-ch28-28-locks.txt:104`(搜「Evaluating Locks」)
关中断及其三宗罪	28. Locks	`text/30-ch28-28-locks.txt:129`(搜「Controlling Interrupts」)
纯标志位失败轨迹	28. Locks	`text/30-ch28-28-locks.txt:199`(搜「Failed Attempt」)与`:223`(搜「Trace」)
TestAndSet 定义	28. Locks	`text/30-ch28-28-locks.txt:250`(搜「test-and-set」)
自旋锁正确性论证	28. Locks	`text/30-ch28-28-locks.txt:342`(搜「why this lock works」)
自旋锁评估(单 CPU 之痛)	28. Locks	`text/30-ch28-28-locks.txt:385`(搜「Evaluating Spin Locks」)
Peterson/Dekker 历史旁注	28. Locks	`text/30-ch28-28-locks.txt:271`(搜「DEKKER'S」)
CAS 与 LL/SC	28. Locks	`text/30-ch28-28-locks.txt:428`(搜「Compare-And-Swap」)与`:463`(搜「Load-Linked」)
票锁	28. Locks	`text/30-ch28-28-locks.txt:540`(搜「Fetch-And-Add」)
yield 方案及其问题	28. Locks	`text/30-ch28-28-locks.txt:637`(搜「Just Yield」)
队列 + park/unpark 锁	28. Locks	`text/30-ch28-28-locks.txt:688`(搜「Using Queues」)
wakeup/waiting race 与 setpark	28. Locks	`text/30-ch28-28-locks.txt:813`(搜「wakeup/waiting race」)与`:814`(搜「setpark」)
自旋锁的抢占式调度器前提	28. Locks	`text/30-ch28-28-locks.txt:380`(搜「preemptive scheduler」)
锁的粒度权衡	28. Locks	`text/30-ch28-28-locks.txt:76`(搜「coarse-grained」)
优先级反转	28. Locks	`text/30-ch28-28-locks.txt:749`(搜「PRIORITY INVERSION」)

出处:「28. Locks」第 104–124 段(text/30-ch28-28-locks.txt:104,搜「Evaluating Locks」)。 ↩
出处:「28. Locks」第 129–170 段(text/30-ch28-28-locks.txt:149,搜「negatives」)。 ↩
出处:「28. Locks」第 191–197 段(text/30-ch28-28-locks.txt:191,搜「limited」)。 ↩
出处:「28. Locks」第 199–240 段(text/30-ch28-28-locks.txt:232,搜「Figure 28.2」)。 ↩↩
出处:「28. Locks」第 241–248 段(text/30-ch28-28-locks.txt:243,搜「spin-waiting」)。 ↩
出处:「28. Locks」第 250–267 段(text/30-ch28-28-locks.txt:258,搜「test-and-set」)。 ↩
出处:「28. Locks」第 342–376 段(text/30-ch28-28-locks.txt:342,搜「why this lock works」)。 ↩
出处:「28. Locks」第 385–427 段(text/30-ch28-28-locks.txt:401,搜「single CPU」)。 ↩
出处:「28. Locks」第 428–565 段(text/30-ch28-28-locks.txt:428,搜「Compare-And-Swap」)。 ↩
出处:「28. Locks」第 567–585 段(text/30-ch28-28-locks.txt:568,搜「ticket lock」)。 ↩↩
出处:「28. Locks」第 271–311 段(text/30-ch28-28-locks.txt:271,搜「DEKKER'S AND PETERSON'S」)。 ↩
出处:「28. Locks」第 637–686 段(text/30-ch28-28-locks.txt:676,搜「99」)。 ↩
出处:「28. Locks」第 688–745 段(text/30-ch28-28-locks.txt:702,搜「queue」)。 ↩
出处:「28. Locks」第 830–871 段(text/30-ch28-28-locks.txt:830,搜「futex」)与第 892–903 段(text/30-ch28-28-locks.txt:892,搜「Two-Phase Locks」)。 ↩
出处:「28. Locks」第 749–777 段(text/30-ch28-28-locks.txt:749,搜「PRIORITY INVERSION」)。 ↩↩
出处:「28. Locks」第 365–373 段(text/30-ch28-28-locks.txt:365,搜「MALICIOUS SCHEDULER」)。 ↩
出处:「28. Locks」第 554–565 段(text/30-ch28-28-locks.txt:554,搜「LAUER」)。 ↩
出处:「28. Locks」第 807–824 段(text/30-ch28-28-locks.txt:813,搜「wakeup/waiting race」)。原文:解锁线程若恰在等待者 park 之前唤醒它,这次唤醒丢失,等待者「可能永远睡下去」。内核替代方案(把 guard 传入内核、原子地放锁+睡下)见同段(:822,搜「pass the guard into the kernel」)。 ↩↩
出处:「28. Locks」第 814–821 段(text/30-ch28-28-locks.txt:814,搜「setpark」)与代码改动(:820,搜「new code」)。原文:若 unpark 先于 park 发生,之后的 park 立即返回而不是睡觉。 ↩
出处:「28. Locks」第 377–383 段(text/30-ch28-28-locks.txt:380,搜「preemptive scheduler」)。原文:没有抢占,自旋的线程不会交出 CPU,自旋锁在单 CPU 上「没多大意义」。 ↩
出处:「28. Locks」第 70–79 段(text/30-ch28-28-locks.txt:76,搜「coarse-grained」)。原文:一把大锁随时守住任何临界区 = 粗粒度;不同数据用不同锁 = 细粒度,更多线程能同时处于锁内代码。 ↩