12 锁 — 从一条硬件指令到睡得着的锁Copy Anchor Link

1. 这一章讲什么Copy Anchor Link

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

2. 顶层全景Copy Anchor Link

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

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

3. 核心原理Copy Anchor Link

3.1 评估三把尺与两种错误起点Copy Anchor Link

评价任何锁实现,先立三把尺¹:正确性(真能提供互斥吗)、 公平性(排队的线程会不会饿死)、性能(分三种场景: 无争用、单 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 为什么一次就对Copy Anchor Link

硬件出手:把「测试旧值、写入新值」做成一条不可分割的指令 (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 原子指令家族与票锁Copy Anchor Link

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

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

3.4 从「转」到「睡」:yield、队列与 futexCopy Anchor Link

票锁公平了,但等待方式还是烧 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 一个比性能更狠的理由:优先级反转Copy Anchor Link

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

4. 作者的判断与证据Copy Anchor Link

书里给了证据的判断:

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

作者的判断(立场):

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

5. 边界与局限Copy Anchor Link

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

6. 可带走的Copy Anchor Link

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

7. 原文地图Copy Anchor Link