并发原语 入门

一条语句不是一条指令。共享计数器上的 x++ 是三条：线程 A 把 x 读进寄存器、加一、写回去。硬件不保证这三条不可分割，调度器可以把线程 B 的三条丢在它们中间的任何地方。

两个线程都从 x = 0 开始、各自要加一，所以答案是 2。把线程 B 的方块沿线程 A 的时间线拖，看最下面那行 —— 每一步之后的 x:

注意只有两个极端位置给出 2。中间任何位置，B 在A 写回之前就读了 x, 两个寄存器都是 0、都写 1,一次自增就这么没了。没有任何东西抛异常。每一行都完全按写的跑，计数器就是错的。

拖方块只能到达调度器可选顺序里的 4 种。两段三指令序列的归并有 20 种，滑块把它们全走一遍：下面那条带子上，你手里的那一种由箭头指着，旁边是结果为 2 的那些和丢了一次更新的那些:

两种。20 种里只有 2 种给出正确答案, 而且都是一个线程跑完另一个才开始的那两种。竞态能活过测试就是因为这个：丢更新不需要特殊硬件、不需要特殊负载 —— 它是默认结果，而恰好把两个线程错开跑的测试会通过。

同样的形状藏在任何「先检查再动手」里。这里线程 A 问 map 某个 key 在不在，4 条指令之后去取它 —— 把线程 B 的 remove在 A 的指令流里滑动：

9 个落点里有 4 个落在检查和动手之间，那几个位置上，取回来的是 null，而代码刚刚证明过这个 key 在。这就是原子性 bug 的常见伪装：两个各自原子的调用，合成一个不原子的序列。ConcurrentHashMap 在这儿救不了你；computeIfAbsent 可以，因为它是一次调用。

硬件也有自己的同款。lock 前缀指令只有在操作数落在一条 64 字节缓存行里的时候才不可分割 —— 把那个 8 字节原子拖过第 60 字节的边界：

因为跨行的操作数横跨两条线，核没法用一次行锁盖住它，只好退回去锁总线：约 1,000 个周期，3 GHz 下 330 ns，对上对齐时的 20 ns。更糟的是，总线锁会卡住这个 socket 上的每个核，不只是你的。 Linux 提供 split_lock_detect，把它变成一个信号而不是一桩慢案。

那个 3 GHz 就是本页每个纳秒数所在的机器：单 socket，所有核在同一 die 上共享一个 L3。每个常数都是按那个主频从周期数推出来的数量级值 —— L1 命中 1 ns、无争用原子 20 ns、缓存行跨核搬一次 100 ns、挂起再唤醒 2 µs —— 不是某个具体型号的跑分。

有两种修法，而且不是同一种。mutex 让整段临界区互斥；fetch_add把它压成一条硬件不会拆开的指令。在两者之间切换，再拖一次线程 B 的方块:

在这两者下面偏移都不再有影响 —— 这正是两者的全部意义。区别在表达力：fetch_add 只管一个机器字，mutex 什么都能管，代价是下一节要花的那些。普通版本破坏掉的不变式是：在一次 read-modify-write 的读和写之间，没有别的线程读或写 x。

glibc 的 mutex 是一个 32 位字，3 个状态：0 空闲、1 持有、2 持有且有等待者。加锁就是一次 0 到 1 的 compare-and-swap，再无其他 ——没有系统调用，没有内核。真的要等的时候内核才登场。

走一遍有争用的获取，看最下面那行的 futex 字，以及进内核的那两步:

注意其中属于内核的有多少。线程 A加锁解锁一次系统调用都没有；只有输掉的线程 B 付 futex_wait 的钱。还有第 4 步：B 得先把字从 1 改成 2，否则 A 解锁时无从知道有人在等，会把 futex_wake 整个跳过。

这个不对称就是全部的性能故事。无争用的一次加锁解锁是两条原子指令、约 40 ns; 要挂起的那次要一次系统调用、一次上下文切换和一次唤醒，约 2 µs。把有争用的比例调上去：

看均值离开地板有多快。在10% 争用时，平均一对已经要 240 ns —— 是无争用那次的 6 倍 —— 尽管 10 次获取里仍有 9 次根本不进内核。锁不慢；等才慢。

所以真实实现都是先自旋再睡。设一个自旋预算，再动持锁方实际占用临界区多久:

在预算以下，等待者根本不睡，等待时间恰好是持锁时长。超过预算，它烧掉了整个预算，睡了过去，然后照样得等持锁方做完 —— 而且它要的 futex_wake 在锁真正空出来之前发不出来，所以它拿到锁是在释放之后 1.5 µs，不是释放的那一刻。 glibc 的 PTHREAD_MUTEX_ADAPTIVE_NP给自旋设上界正是因为这个，也是用户态自旋锁通常是错的原因：持锁方可能在临界区中间被调度出去，于是你自旋一整个时间片。

信号量是同一个字，把标志换成计数。许可数决定 8 个 worker 里有几个能同时在里面：

1 个许可时它就是 mutex，只有一个差别会咬人：信号量没有 owner，任何线程都能 post 它，一个从没 wait 过的线程调sem_post 完全合法。这让它适合做有界队列，不适合做互斥 —— 互斥里正是那个 owner 检查抓住了重复解锁。

条件变量补上缺的那块 —— 睡到有人说状态变了 —— 陷阱在于「被唤醒」对谓词什么也没说。把守卫在 if 和 while 之间切换，然后一步步走这个序列：

用 if 时，等待者因为一个发给别人的唤醒离开cond_wait，发现谓词仍然是假, 照样动手。POSIX 明确允许这个：虚假唤醒是合法的，pthread_cond_signal 也可以唤醒不止一个等待者。那个 while 不是防御性写法，它是白纸黑字的契约。

两把锁两个线程，是互斥反过来咬自己的地方。选好线程 B 拿锁的顺序，再走那 4 步获取:

同序时永远不成环：拿到锁 1 的那个跑完并把两把都放掉。把 B 反过来，第 4 步就把环闭合了 —— 每个线程都持着对方要的东西，谁也不会让。没有东西检测它，没有东西超时；进程就是停住了。全局锁序能防住它，而且是机械可查的：按地址排序，或者给每把锁一个静态 rank。

最后一把锁是大家凭反射去拿的那把。rwlock把临界区买回来，收你一次缓存行传输的钱：它的计数器是争用的，一次读要碰它 3 次，而 mutex 碰自己那个字只要 2 次：

注意临界区得值多少钱才行。在500 ns 的临界区上， rwlock 做到 3.1 M/s,mutex 是 1.4 M/s, 而且一直赢到 80% 的写比例。把临界区降到100 ns,它在任何比例下都不再赢: 它的读路径在计数器那条线上多走的那一趟就是 100 ns, 正好是它保护的整个临界区。临界区得比一次传输更值钱。

compare_exchange 是通用的 read-modify-write: 只有内存里还是你读到的那个值时，才把新值发布出去。不是的时候，你没丢数据 —— 你输了一次竞争，再来一遍。

把别的核先到的次数调上去，对比每次尝试读到的值和交换执行时内存里真正的值:

注意循环失败的时候并没有出错 —— 失败就是机制本身。但读和交换之间算出来的一切每次都被丢掉，所以 CAS 循环必须短、必须没有副作用。一个会分配内存、会打日志、或者会再拿一把锁的循环，每次尝试都干一遍那些活。

fetch_add 看着是同一回事，其实不是：它的重试发生在核内部，不在你的循环里。往一个计数器上堆核:

两者的吞吐并不相同，而两行的原因是同一个。缓存行才是串行资源：它一次只能待在一个核里，搬一次要 100 ns。fetch_add 每次自增只花一趟，所以不管几个核，它都稳在每秒 1000 万次。循环是每次尝试花一趟：在8 个核时，8 次尝试里有 7 次被丢掉, 而那 7 次每次都各付过一趟，同一条线只交付得出每秒 130 万次成功自增 —— 八分之一。选那条把循环做进硬件里的指令。

那条线宽 64 字节，它不在乎你那两个计数器是不同的变量。把核 1 的计数器拖进核 0 那条线里：

因为两次写现在落在同一条线上，每次自增这条线都要在两个核之间来回弹， 20 ns 的原子操作变成 100 ns ——两个八竿子打不着的变量，5 倍。这就是伪共享，它在源码里完全看不出来，而 alignas(64) 和 Java 的 @Contended就是为了把它填到一整条线而存在的。

无锁代码有一个失败模式，再多的原子性也防不住。把另一个线程的弹出、弹出、压回滑进我们读和我们 CAS 之间的窗口：

看 CAS 成功了。我们比较的指针和读到的那个逐位相同，硬件无从反对 —— 但它指的那个节点在这中间被释放又被压回来了,head 现在指进了分配器已经交出去的内存。这就是 ABA。修法是带标签的指针 —— 在空余位里放一个版本计数，每次压入就加一 —— 或者一套回收方案，比如 hazard pointer 或 epoch。

有了这些，价目表就很短了。一条原子指令买的是这条线的一趟，下面唯一在变的是有几个核想要这条线:

1 个核时，原子操作是 20 ns，普通读是 1 ns —— 20 倍的价钱，而且仍然便宜。到8 个核,CAS 循环是 800 ns, 它的条被切成付掉的 8 趟，其中只有最后一趟成功。由此得出的规则：原子操作按指令算便宜，按争用的行算贵，所以优化是把行摊开，不是把原子操作去掉。

一次写不会直接去内存。它进的是每核一份的存储缓冲, 然后立刻退休 —— 所以一次写只要 0.3 ns，而不是缓存未命中那几十纳秒。这也意味着另一个核看到你的写是在缓冲排空的时候，不是你发出的时候。

生产者先写 data = 42，再写flag = 1。移动这两次写各自离开缓冲的时刻，读最下面那行：

把 flag 放在 data前面出去，另一个核就看到一个已置位的标志盖着一份旧数据：一个信任标志的消费者读到 0，还当它是 42。这里没有编译器 bug，也没有硬件 bug —— 两次写的地址毫无关系，那段代码的单线程语义里也没有任何东西给它们排序。

约束的正是这个，就是 memory_order 的用处： release 写不许被重排到它前面那些写的前头。选一种内存序，再擦动消费者读的时刻:

relaxed 下有一个窗口 —— 在第 2 拍,flag 可见而 data 不可见。acquire/release 下没有这个窗口，不是因为写变快了，而是因为编译器不许再乱序发出它们、核也不许再乱序排空它们。bug 就是那个窗口，内存序把它关上。

内存序是成对的。单独一个 release 什么都不保证；读者得接住另一头。在两头都装上之前，消费者读到的每一个值都是旧的 —— 滑块一次装一半:

注意在两半都到位之前什么都不会发生。被 relaxed 读读到的 release 写仍然是一个数据竞争，release 之前那 3 次写仍然是旧值。一旦acquire 读读到了那次 release 写下的值, 生产者在它之前做的每一次写，对消费者在它之后做的每一件事都可见。这就是 happens-before 的全部，而且它可传递。

有一种重排在所有造出来过的机器上都活过 acquire/release。两个核各自先写、再读对方的变量 —— 先关着屏障走一遍那 4 种结果, 再打开：

两个核都能读到 0，而这是两段程序的任何交错都产不出的结果。另一个核的读出去的时候，每一次写都还坐在自己那份存储缓冲里。只有全屏障 —— mfence，或者 seq_cst编译成的那条带 lock 前缀的写 —— 会先把缓冲排空，这正是为什么 seq_cst 在 x86 上要花钱，而 acquire 和 release 不用。

这也正是换机器就不成立的那部分。切换架构，走一遍那三种内存序:

x86 白送地禁掉 4 种重排里的 3 种，所以 relaxed 的代码是「碰巧几乎正确」,seq_cst是你唯一真花钱的那种 —— 20 ns 的 xchg对上 0.3 ns 的写。 ARMv8 四种全允许，所以 acquire/release 要花 ldar 和 stlr，而seq_cst 在那之上不再多花一分, 因为那一对本来就是顺序一致的。陷阱在第一列：只在 x86 上跑过的代码，它的内存序从来没被测试过。

在 2 ns 上没有什么比一条原子指令更好，其余的都是在给一条指令加锁。要到252 ns,rwlock 才领先 —— 比多数人猜的晚，因为 8 个读者得先赚回它计数器上多走的那一趟。再注意 mutex 从来做不到的一件事：它的条永远不是最短的，因为自旋在锁一空出来的那一刻就拿到，挂起做不到。它有的是里面那根条。在3.2 µs 上，自旋锁空烧掉整整一个核 3.2 µs，还是 7 个核一起，而自适应 mutex 烧完 1 µs 预算就去睡了。延迟是你感觉到的，里面那根条是你付的。

int want = 0;
if (!cas(&m, &want, 1))  // 0 -> 1
    lock_slow(&m);  // futex_wait
/* ... critical section ... */
if (xchg(&m, 0) == 2)  // waiters?
    futex_wake(&m, 1);

那一个字也是整台机器的天花板。在一个每次操作有5% 落在锁内的负载上，把核数调上去：

注意曲线会拐回来。过了31 个核, 多出来的核搬缓存行的时间比它贡献的还多： 64 个核给出 7.8 倍，31 个核给出 9.0 倍。Amdahl 只把曲线压平；一致性那一项才让硬件越多越差。

• 用 if 守的 cond_wait。 循环是契约。
• 线程之间用 relaxed。 它什么顺序都不给。
• 一个 struct 里两个热计数器。同一条行，5 倍的税。
• 用户态自旋锁。持锁方会在临界区里被调度出去。
• 按顺口的顺序拿锁。先定全局锁序。