本篇位置 第 16 篇提出了"需要不可分割的一步"，这一篇给出它
运行环境 容器里的 Linux，gcc（-O0）

一、先试试自己拼一把

第 16 篇的问题是：counter++ 那三条指令中间会被插进来。

直觉的解法：加一个标志位。谁进临界区就把它置 1，出来置 0。别人看见是 1 就等着。

static int naive_flag = 0;

while (naive_flag) ;      /* 有人在里面，等 */
naive_flag = 1;           /* 我进去了 */
counter++;
naive_flag = 0;           /* 我出来了 */

看起来很合理。跑一下：

  用普通变量当锁 结果   1090117 /   4000000  错了

还是错的，而且错得跟没加一样。

⭐ 因为你只是把问题往前挪了一格。while (naive_flag) 是一次读，naive_flag = 1 是一次写——这两步中间那道缝，跟原来 ldr 和 str 之间那道缝一样宽。

两个线程可以同时读到 0，同时认为"没人在里面"，然后一起进去。

⚠️ 这是并发里最重要的一课：你不可能用"不原子的东西"拼出"原子的东西"。 无论嵌套多少层判断，那道缝都还在。

（顺带一提：软件层面确实有纯用普通读写实现互斥的算法——Peterson 算法、面包店算法。它们成立，但需要严格的内存顺序假设，而现代 CPU 的乱序执行会破坏这些假设，所以实践中没人用。理论上可行，工程上不用。）

二、必须从硬件要一条指令

出路只有一条：让硬件提供一条"读和写焊死在一起"的指令。

最经典的是测试并设置（test-and-set）：

把某个地址的旧值读出来，同时把新值写进去，这两件事之间不允许任何人插进来。

硬件保证这一点——在总线层面或缓存一致性协议层面锁住那个地址。

有了它，锁就三行：

static atomic_flag spin = ATOMIC_FLAG_INIT;

while (atomic_flag_test_and_set(&spin)) ;   /* 旧值是 1 说明有人占着，继续转 */
counter++;
atomic_flag_clear(&spin);

关键在于 test_and_set 的返回值是"旧值"。 如果旧值是 0，说明刚才没人占着，而且现在已经被我占上了——因为读和写是同一个动作。

⭐ 这是"原子"这个词的实际含义：不是快，是不可分割。 第 16 篇那个钱箱的比方里，这相当于装了一个取号机——按一下就吐一张号，同时号码自动加一。没有"看一眼再决定"这一步，所以没有缝。

别的形态

不同架构给的原语不一样，但能力等价：

  • 比较并交换（CAS，x86 的 cmpxchg）：如果这个地址的值等于 A，就改成 B。返回是否成功。最通用，无锁数据结构基本都建在它上面。
  • 加载链接 / 条件存储（LL/SC，arm64 的 ldxr/stxr）：读一个值并做个标记；写回时如果这期间没人动过它就成功，否则失败重来。arm64 的原子操作都是用它拼的。
  • 原子加（fetch_add）：直接原子地加一个数。有些操作根本不需要锁。

三、跑一遍看看：四种做法的账

同样的活儿（4 个线程各加一百万次），五种写法：

  什么都不做      结果   1036727 /   4000000  错了     用时  0.00 秒
  用普通变量当锁  结果   1090117 /   4000000  错了     用时  0.01 秒
  自旋锁(原子指令) 结果  4000000 /   4000000  正确     用时  0.74 秒
  pthread 互斥量  结果   4000000 /   4000000  正确     用时  0.08 秒
  原子加          结果   4000000 /   4000000  正确     用时  0.04 秒

三件事值得读：

一、只有后三种是对的。 前两种连结果都不对，谈速度没有意义。

二、⭐ 自旋锁比互斥量慢了九倍（0.74 秒 vs 0.08 秒）。这是最反直觉的一条，第四节专门讲。

三、原子加最快（0.04 秒），因为它根本没有临界区——一条指令就把事办了。

⭐ 最后这条值得记住：能不用锁就不用锁。 很多时候你以为需要互斥，其实只需要一个原子操作。

四、⭐ 自旋锁为什么反而慢

自旋锁的逻辑是"锁被占着，我就在这儿转圈等"。

在单核上，这是灾难：你转圈的时候，拿着锁的那个线程根本没在跑——CPU 被你占着。你必须一直转到时间片用完被抢走，那个线程才能上来把锁放掉。你的整个时间片纯属浪费。

在多核上没那么糟，但还有别的代价：

  • 你在烧 CPU。 那些周期本可以给别人。
  • 缓存行在核之间乒乓。 每次 test_and_set 都是一次带写意图的访问，会把这条缓存行从别的核那里抢过来。四个核抢同一条缓存行，总线上全是这个。

互斥量的做法是：拿不到锁就告诉内核"把我挂起来，锁放了再叫我"（Linux 上靠 futex 系统调用）。这样：

  • 拿不到锁的线程进入阻塞态（第 2 篇那条边），不占 CPU。
  • 持锁的线程能立刻拿到 CPU 把活干完。

代价是挂起和唤醒要陷入内核，几百纳秒到几微秒。

⭐ 所以取舍很清楚：

临界区极短、竞争不激烈 → 自旋划算（转几圈就拿到了，比陷入内核便宜）。 临界区较长、竞争激烈 → 挂起划算（省下的 CPU 远超陷入内核的开销）。

上面那个演示属于后者：四个线程死命抢同一把锁，绝大多数时间都在自旋等待。

⚠️ 实际的 pthread_mutex 是自适应的：先自旋一小会儿，还拿不到再挂起。两头的好处都想要一点。而内核里的自旋锁是真自旋——内核代码不能随便睡，而且临界区都极短。

五、还有两个必须知道的问题

公平性

上面的自旋锁不保证公平。一个线程可能连续抢到十次，另一个一次都抢不到——这叫饥饿。

解法是票号锁（ticket lock）：进门先原子地取一个号，然后等叫到你的号。先到先得，严格 FIFO。

⭐ 这又是"取号机"那个比方，而且这次是字面意义上的。代价是即使无人竞争也要做一次原子操作。

锁的粒度

一把大锁保护所有数据，正确但慢——所有线程都在这一把锁上排队，多核就白加了。

拆成很多把小锁，并行度上去了，但：

  • 要小心死锁（第 21 篇）。
  • 锁本身的开销变多。
  • 代码正确性变难验证——你得说清楚每个数据由哪把锁保护。

这是第 18 篇的主题。

六、代价与取舍

锁换来了什么： 一个能把任意长的代码变成"不可分割的一步"的工具。没有它，多线程共享数据无从谈起。

它花了什么：

  • 原子指令本身不便宜。 它要在缓存一致性协议上做文章，通常比普通内存访问贵一个数量级。
  • 序列化。 临界区里同时只有一个线程——它是并行度的天花板。这就是阿姆达尔定律：如果 10% 的代码必须串行，那你堆再多核，加速比也上不了 10 倍。

它放弃了什么： 组合性。 两段各自正确的加锁代码，拼在一起可能死锁。这是并发编程最难的地方——正确性不能靠"每一块都对"来保证。

这也是为什么后来有了别的路子：无锁数据结构（只用 CAS，第 18 篇）、消息传递（Go 的 channel、Erlang 的 actor，干脆不共享）、事务内存（把临界区当数据库事务）。都还没有一个能全面取代锁。

七、小结

  • ⚠️ 你不可能用普通变量拼出一把锁。 标志位方案只是把缝往前挪了一格——“检查"和"置位"之间那道缝和原来一样宽。（Peterson 这类纯软件算法理论上成立，但依赖现代 CPU 不保证的内存顺序，工程上不用。）
  • 必须从硬件要一条把读和写焊死的指令：test-and-set、CAS、LL/SC。⭐ “原子"的意思是不可分割，不是快。
  • 实测：自旋锁 0.74 秒、互斥量 0.08 秒、原子加 0.04 秒。⭐ 自旋锁慢九倍——单核上你自旋的时候持锁者根本没在跑，多核上你在烧 CPU 和抢缓存行。
  • 互斥量拿不到锁就让内核把自己挂起（futex）。取舍：临界区短且竞争少用自旋，长且竞争多用挂起。实际的 pthread_mutex 先自旋一会儿再挂起。
  • ⭐ 能不用锁就不用锁——原子加最快，因为它根本没有临界区。
  • 票号锁用取号解决饥饿，代价是无竞争时也要一次原子操作。
  • 锁放弃的是组合性：两段各自正确的加锁代码拼起来可能死锁。正确性不能靠"每块都对"保证。

思考题

  1. 第一节说标志位方案"把问题往前挪了一格”。那如果加两个标志位、再加一个"轮到谁"的变量呢？（这就是 Peterson 算法。）它在什么假设下成立？现代 CPU 为什么破坏这个假设？
  2. 自旋锁在单核上是灾难。那么，内核里为什么还大量使用自旋锁？（提示：想想内核代码在什么上下文里跑，以及它能不能睡。）
  3. 第三节里"原子加"最快。那能不能所有情况都用原子操作代替锁？举一个明确做不到的例子。
  4. 取号机那个比方里，test_and_set 是"按一下出号且号码自动加一”。那 CAS 对应什么动作？（提示：它带一个条件。）

延伸