互斥和 API

上一节课我们讲了多处理器编程从入门到放弃。入门就是最简单的线程库 thread.h，你们应该已经下载过代码并且运行过了。它有两个 API：一个是 spawn，你可以把一个函数作为一个线程运行起来，这段代码就可以和其他代码并发、并行地执行，前提是在多处理器硬件上。而且你确实可以验证它们是共享内存的，拥有独立的栈。当这个线程的函数返回时，我们可以用 join 把它等回来。这样你就可以使用多线程程序了。

但是你也发现，如果只依赖于线程库和共享内存的话，你甚至连一加一也不会求了。如果你有两个或者多个线程想做 sum = sum + 1，现在暂时是没有手段的。甚至你连一二三这样的顺序都数不出来了，因为有 weak memory model 的各种奇怪行为。所以我们不是教大家去 hack 这种行为，而是要告诉大家，你们其实打开了一个魔鬼的盒子。

为什么要在操作系统课里讲并发呢？因为 UNIX 引入了进程以后，虽然进程之间是不共享内存的。最早的时候，UNIX 的进程如果只有 fork 和 execve，那么 fork 出来的两个程序副本就是独立运行的，拥有自己独立的地址空间。甚至在早期的实现里，真的就是把内存一个字节一个字节拷贝了一份。

fork 和 execve 虽然不共享内存，但是系统调用的执行是共享内存的。如果我们的操作系统执行一条 syscall 指令，它的行为实际上是一个跳转，和普通的 jump 或 call 很像，只是会附带一个权限的切换。当你穿过 syscall 的时候，你就从一个不被信任的应用程序，交出了控制权。所有的应用程序都是不被信任的，不能随便动计算机硬件的任何配置，包括 I/O 端口、中断等等。如果你动了，操作系统的霸权地位就受到挑战了。但当你进入内核，就好比把自己全身麻醉交给医生，这时程序又恢复到高权限状态。每个进程在操作系统内执行的部分，就变成了一个线程。所以操作系统是最早的并发程序。

一旦 syscall 开始执行，比如一个进程在 syscall 里执行，另外一个进程可能也在执行。操作系统内核代码执行的时候仍然是可能被中断的。这就带来了麻烦：不管是被中断还是真的在两个处理器上运行，P1 和 P2 操作系统内核部分如果操作同一份数据，就会出现上节课讲的“一加一不等于二”或者数不清顺序的问题。操作系统是第一个非常严肃、大型、真正让人类感到头疼的并发程序，很多早期的并发研究成果都来自操作系统的研究者。所以我们顺理成章地在这里讲并发。

今天我们就来解决上一节课没有解决的“一加一”问题。我们希望在操作系统或编程语言里引入一个机制或者 API，让我们能安全地做 sum++。实际上，我们想要的是在你执行 sum++ 或者更新一个数据结构时，可以把这些操作全部包裹在一个“Make it work”的代码块里，然后它就自动正确了。至少我们可以做到，让这段代码退回到“不并发”执行的状态。也就是说，当线程 T1 执行到这个代码块时，如果 T2 也想执行，它们两个不能同时进入。因为一旦 sum++ 同时执行，处理器就会出现各种奇怪行为，结果难以理解。我们需要 Make it work 能保证：如果这个线程在执行 sum++，别的线程就不能执行，至少要等到这个 sum++ 确实完成、值真的写进内存了，它才能继续。相当于我把本来能够并发或并行执行的程序，变得不能并发执行，这样一加一的问题就解决了。

只要把所有对共享变量的访问都包裹在 Make it work 里，这个问题就解决了。恭喜你，你发明了一个很有意思的机制。从上世纪 90 年代开始就有人研究 Transactional Memory（事务内存），我们希望有一块代码，可以很长，比如更新一个数据结构，然后给它一个 atomic 的包裹。包起来以后，里面的代码要么全部执行完，所有写入内存的操作在退出时一次性生效；要么就好像什么都没写一样，要么全做，要么全不做。这样就可以正确实现 sum++，因为 sum++ 实际上包含三件事：读、改、写。你发明了 Transactional Memory。

大概在 2010 年左右，英特尔开始在指令集里加入两条指令：Xbegin 和 Xend，用来支持事务内存。但是这个机制引发了很多问题，包括安全漏洞，所以现在在消费级笔记本电脑和台式机上已经看不到了。不过在服务器上这个特性依然有，Arm 也在一段时间内加入过，但后来似乎也不想在指令集里继续维护了，因为它是一条能和所有指令产生关联的指令，有点像 fork，给指令集体系结构的实现带来很大麻烦。但这其实就是我们想要的 Make it work。

如果你在一个单处理器系统上，并且在操作系统内核里，想实现刚才那个 Make it work，有一个非常简单的方法：关中断。你想，如果只有一个 CPU，把中断关掉以后，这个 CPU 就完全被我独占了。在我们的状态机模型里，看起来模型从固件重启开始执行指令，但如果 CPU 的中断是打开的，它在任何一条指令执行时都有可能响应中断。计算机系统其实是非确定的，中断是并发的来源。但如果你把中断关掉，这种可能性就没有了。此时指令集结构是确定的，我执行 x=1、y=1，那么 PC 取下一条指令的过程是确定性的，执行的代码完全相同。所以操作系统内核把中断关掉以后，就实现了系统其他任何部分都不能再打扰我。当然这也意味着，如果你在内核里写了一个 while(1) 循环并且关中断，这个计算机系统就死掉了。所以为什么我们会有 CPU reset 按钮。在软件工程还不成熟、大家不知道如何构造可靠操作系统的时候，Windows 蓝屏是家常便饭，bug 可能导致卡死或蓝屏。

我也让 AI 给我写了一段关中断然后死循环的代码，需要借助一点汇编。这段代码可以在 x86 上运行。你会看到它有一条 MSR 指令，写一个系统寄存器把中断位清掉。在 x86 上有一条 clear interrupt 指令。CPU 的 flags 寄存器里有很多标志位，其中有一个是操作系统内核可以控制的中断位（interrupt flag）。如果把这个位清掉，处理器就变成了不再响应中断的状态。但我在用户态运行这个程序时，收到一个 SIGILL（illegal instruction）。在 x86 系统上，如果尝试执行这条指令会得到一个 protection error 或 segmentation fault。这就是操作系统内核想要实现的保护。

那么我们也可以把这个机制稍微扩展一下：能不能有一个类似“开始关键代码”和“离开关键代码”的操作？这就是我们今天要讲的最主要内容：互斥的 API。互斥（mutually exclusive）就是指两个人不能同时进入一段代码，这段代码有时叫临界区（critical section）。我们要实现的是：在任何一个线程上，先执行 lock，然后就可以执行任意代码，比如 sum++。等到代码执行完了，不再需要这种“别人不能打断”的强保护时，就 unlock。

lock 和 unlock 实际上是把并发消除了。当我 lock 返回时，我就再也不能和别人的 lock 代码块并发了。我们可以画在时间轴上：如果 T1 lock 并返回了，它就可以做任何事直到 unlock。对于其他线程，无论什么时候 lock，只要在这个时间点上锁没被释放，这个 lock 就不能返回，必须等待。直到 T1 释放锁（unlock），T2 的 lock 才能返回。这样我就把所有的并发都消除了，得到了一个确定的顺序。至少你可以排出 1、2、3 这样的顺序。第一次 T1 的 lock 返回、执行代码、unlock。unlock 还有一个额外的语义：它会保证所有在这里写入的数据全部进入内存，不会像之前那样我写了 x=1 但别人 load 时看不到。这就是 lock 和 unlock 给我们的保证，很直观。

你可以把线程想象成人，把共享内存想象成物理空间。lock 和 unlock 就像是有一个小房间，里面只能容纳一个人。任何人进来后都会把门锁上，别人就进不来了。这个人（线程）可以继续执行代码。如果有别人想进来，他执行 lock 时必须打开房门进入房间，才能执行代码。如果很多人同时想进，只有一个人能进去，其他人需要等。还有一个解读方法：桌上有一把钥匙。lock 就是拿到钥匙才能继续执行，unlock 就是把钥匙还回去。还回去的时候，其他在等钥匙的人就可以拿走。所以 lock 和 unlock 有时也叫 acquire（获取）和 release（释放）。相应的，unlock 会保证在它之前写入的内存，在后续的 acquire 之后能够被看到。你们可能在 C++ 内存模型文档里看到过 acquire semantics 和 release semantics，讲的就是可见性这件事。

如果你所有的代码都正确使用 lock 和 unlock，比如对共享变量 sum 的访问都在锁保护下进行，那就没问题。但如果你有一个没被锁保护的 sum++，那肯定还是错的。相当于世界上的人要达成一致：只有进入房间或拿到钥匙才能做下一件事。如果你不遵循这个协议，就会出错。我们也很自然地能想到，世界上可以不只有一把钥匙或一个房间。你可以创建好几把锁，在访问不同变量时选择不同的锁。比如我有锁 A 和锁 B，对 x 的操作用锁 A 保护，对 y 的操作用锁 B 保护。因为 x 和 y 是不同的内存地址，它们之间不会互相干扰，只需要正确使用对应的锁，就可以正确实现互斥，不会出现上一节课那些奇怪的现象。

今天我们终于可以学会写“一加一”了，这是一个很重要的里程碑。我们准备了 sum.c 这样的代码。线程库除了 threads.h，还有一个 thread-sync.h，所有并发控制相关的代码都在这个头文件里。如果你想要创建一把互斥锁，可以创建一个 mutex 锁对象。对于同一个变量的访问，要用同一把锁把它保护起来。在我的代码里，如果要做 N 次 sum++，我会把实际执行的部分包在 lock 和 unlock 之间，中间做任何事。我在这里故意做了十次 sum++，并且加了一个 compiler barrier 防止编译器优化，这样编译器每次都需要 load、加一、store。在这个 lock 和 unlock 之间，我会做十次读、十次计算、十次写。如果有并发读写，肯定会出问题。但因为有了 lock 和 unlock，我阻止了这段代码所有可能的并发，预期能够得到正确的结果。我们可以编译运行一下，看起来没问题，你可以运行更多次来增加信心。

理解互斥

很好，你学会了并发控制里最重要的互斥。怎么理解或者在实际中使用互斥呢？我们有一个简化的视角。一般理解程序时，还是把线程想象成人，共享内存想象成物理空间。假设你正确地使用了互斥锁，lock 和 unlock 就相当于执行了一个“Stop the World”。哪怕你 lock 的是锁 A，世界上还有线程 3 在 lock B 然后对 y++ 再 unlock B，当你的锁使用正确时，我们可以安全地认为 lock 就是让世界上所有其他部分都停下来，就像 JoJo 里的“The World”一样，可以瞬间停止世界，但自己依然可以活动。在 lock 期间你可以随便对共享内存做任何事，比如 sum++、x++，然后再 unlock。在 unlock 的一瞬间，你施加的所有作用就全部生效了。

为什么我在 lock A 这边，T3 在 lock B 那边，甚至它们在不同的 CPU 上，我依然可以认为是“Stop the World”呢？前提是你正确地使用了锁。正确使用锁意味着我在锁内读写的所有变量，在锁外都是不相干的。如果我在锁内读 x、读 sum，绝对不可能有另外一个人同时在写 sum。如果出现了，那我的“Stop the World”假设就不成立了。所以我需要假设别人永远不能写我读过的值。这就意味着，虽然 T1 和 T3 在实际中真的是并行执行的，但在理解程序执行效果和结果时，你可以把这段程序的执行挪到后面或者前面。按照先 T1 后 T3，或者先 T3 后 T1 的顺序执行，结果都是一样的。所以虽然我们理解时像是“Stop the World”了，但实际上它们还是并行的，只是我们可以用这种模型来理解它。

这就和在操作系统内核里关中断一样。如果只有一个 CPU，关了中断，世界上真的就没别人了，确实实现了“Stop the World”。但即使世界上有别人，别人执行的效果也可以挪到前面或后面，不会影响我自己看到东西的正确性，所以就好像是“Stop the World”一样。这是对互斥锁的一种理解方式。你在用的时候先把互斥锁上好，然后就会发现上一节课讲的复杂东西都没了，因为它变成了顺序的程序。我们所有的编译优化、以前理解程序的方式又回来了。因为人类本质上是一个 sequential 的生物。我们在训练时从来都是只做好自己就行，人类天生就不太擅长处理多件事同时推进。一个线程也是顺序执行的，当多个线程互相影响时，脑子就炸了。但如果你能通过并发控制（比如互斥）达到“Stop the World”的效果，理解程序就又回到了你熟悉的顺序执行。

当然，刚才的前提是互斥锁的使用是正确的。但是，你有一万种方法用错它。自从 acquire 和 release 这个 API 被设计出来，人类就走上了不断犯错误的道路。我可以毫不夸张地说，现在 Linux 内核里还有数不清的锁相关的问题。因为 lock 和 unlock 是程序员自己负责的。这跟 malloc 和 free 一样：你记得 malloc 之后一定要配一个 free，但你未必做得到。你记得每一个 acquire 之后必须要一个 release。如果你在函数第一行 acquire，最后一行 release，中间却有个 return，程序就错了。你可能觉得你不会犯这种错，但那是因为你只在一个文件里写几行代码。当你有几十个文件、几十把锁的时候，确实很难弄对。

举个例子，链表。你可以只用一把锁保护整个链表，锁住以后就能访问整个链表。但如果你要实现一个性能还过得去的并发数据结构（今天阅读材料里会讲），你就不能用一把锁保护所有节点，而是每个节点都有一把锁。这就带来麻烦了。双向链表有 prev 和 next 指针。如果你想遍历这个链表，你应该怎么办？你必须一边上锁一边解锁。我在持有当前节点的锁时，不能把它释放掉，同时还要去获取下一个节点的锁，这样才能把链接关系锁住。链接关系锁住很重要，否则真的会出错。等我到了下一个节点，我才能把当前节点的锁释放掉。你要保证中间的链接关系不能改变。遍历就已经这么复杂了，插入和删除还需要同时拿到 previous、current 和 next 三把锁。更复杂的是删除后的内存回收：你什么时候可以把这个内存回收掉？你要确保没有任何人持有指向这个节点的引用时才能回收。这比你想象的要困难，你们马上做实验就会知道里面有很多微妙的地方。

如果你只有一把锁，需要原子性时 lock 再 unlock，世界就简单了。否则，手工管理复杂的锁就非常麻烦。所以你真正想要的是 Make it work：你写一个链表，然后说 Make it work，一个好的编译器能把它翻译成高效的代码，而不是你手工去翻译，并且还能保证正确。我觉得离这一天我们可能也不远了，也许我们讲的这些东西很快就没用了。

除了逻辑上在系统里引入很多把锁容易出错以外，你还会犯各种小错误。比如你看到这段代码错在哪了吗？看起来用了同一把锁来保护 sum++，但一个是 lock(&lk)，另一个是 lock(&l)。不要笑，我自己也经常犯这样的错误。现实中你有几十把锁、几十个文件，函数互相调用，你搞不清楚的时候，没有人能相信自己全记得。你经常能看到 Linux 内核社区的人在讨论锁的问题，他们有一些动态检查工具能在运行时检查哪里漏了锁，查出来了就讨论到底谁的问题、怎么修。很有意思。

所以操作系统课给你们的建议是：因为你们是第一次做并发编程，在可以的时候，只用一把锁就可以了。只有一把锁的时候，事情就简单了。但凡可能共享的东西都要上锁，而且都上同一把锁。你需要把上锁的时间延长一点，从你要干这件事开始就得持有这把锁，直到这件事全部干完再释放。你们不要觉得看起来很蠢。Linux 内核在最早从单处理器迁移到多处理器时（大概 2000 年左右），干的第一件事就是引入一个东西叫 Big Kernel Lock（BKL）。这把大锁保平安，有了它系统就是对的。从单处理器到多处理器是很可怕的事情：单处理器时关中断就行了，想保护 sum++，关中断、sum++、开中断就完了。但到两个 CPU 时这事不 work 了，必须要有更好的机制。他不敢一下子就写几万行代码把锁拆细，如果那样做引入了 bug，整个内核可能在很长时间里都无法运行。所以他从一把大锁开始，慢慢往小里拆，先找那些对性能影响关键的路径，把大锁拆成几把小锁，并做好充足的压力测试。

这让我想起 Knuth（计算机程序设计艺术的作者）的一句话：“Premature optimization is the root of all evil.”（过早优化是万恶之源）。你写程序时可能会有一种倾向：这里写 x * 2，是不是编译器会编译成一条乘法指令？我是不是应该把它变成左移一位？千万不要干这样的事。编译器比你想象的聪明得多。在绝大部分时候，你脑子一热做出的优化，并不在关键的性能瓶颈上。你看起来做了优化，其实可能没做，反而给你理解代码造成了麻烦。先把你的代码想要做什么准确表达出来（比如你现在就是想要“Stop the World”），然后再慢慢优化导致瓶颈的路径，这才是正确的途径。

这是一个警告，虽然我说多少遍可能都没用。等到你们做内存分配器的 lab（要求实现一个线程安全的 malloc/free），一开始用一把大锁，easy test 就过了，完全正确。当你发现需要把性能提上来过 hard test 时，一旦锁拆开了，你会发现 easy test 也过不去了。因为在巨大的压力下，你会有各种各样奇怪的并发 bug，就像那个 sum 的例子一样。你有一个数据结构，要管理好几把锁，不太容易把它做对，并且我还要求最后 sum 必须是那个正确的值。只要有一点点小错，在非常压力的负载下测试，你们就可能会有各种问题。

同学们学到这，首先已经学会了怎么用互斥，其次可能产生一个疑问：lock 和 unlock 跟并发、并行的动机是冲突的。我们有 64 个、128 个处理器，可以同时执行程序，但一旦上了锁，它就不能并行了，退回到串行按 1、2、3 的顺序执行。而且因为有多个处理器，来回切换甚至比在一个处理器上执行还慢。既然都不并发了，我们为什么还要用线程呢？

这里有两个很有意思的理论结论。第一个名气更大，叫 Amdahl's Law（阿姆达尔定律）。它说，如果你有一个程序，里面有 50% 的代码是不能并行的，比如先要算一个数表，要花一秒，后面有一大堆可以并行的代码，哪怕这部分并行得再好、时间几乎为零，假设可并行部分也是一秒，那么无论你有多少 CPU，最多也只能加速一倍。这个分析是对的。但实际不完全是这样的，我们还有另一个 Gustafson's Law（古斯塔夫森定律）。它是一个更细致的版本，它说如果你的不能并行部分非常少（接近于零），并且可并行部分非常可并行，那么基本上有多少个处理器，你就能得到多少倍的加速比。这个乐观的结论对我们来说更有用。

我们应该怎么解读这个乐观结论呢？如果你要算一个很大的东西，能够并行的部分是绝大多数，你只需要在很少的地方用 lock，剩下的都是可以并行的代码。怎么理解这一点呢？我们的物理世界是有局部性的。我们把自己想象成线程，把物理空间想象成共享内存。我们每一个人都只占据自己的物理空间。如果我们想访问别的物理空间，只能访问相邻的。我们不可能瞬间伸手把月球上的月壤拿过来，我们做不到，物理世界有局部性。

这意味着什么呢？比如你要模拟一个物理系统，像天气预报、神经网络训练等等，都是先把一个很大的网格切分成一块一块的计算任务。每一块计算任务会用到它自己的数据，也可能会用到边界上的数据（需要和别人交互），但绝大部分都是自己的。这一块内部的计算量远远大于需要和别人交互、需要上锁的那部分计算量。所以我可以把这个任务切分成很多块，绝大部分计算是独立完成的。独立完成就意味着我读写的内存别人不会读写，这意味着我可以完全并行，不需要上一把锁。

这样的例子不只是物理世界模拟。比如图书馆里的书，每本书天生就是独立的，每个同学可以拿一本书来读。但拿书的时候你们会共享书架，我必须对书架这个数据结构上锁。你们两个同学同时看到那本漫画书想去抢的时候，就相当于同时想从图书馆数据结构里拿一个东西出来，你不可以同时操作，必须上锁。但一旦书拿到手上，这本书就变成了我的 private memory，世界上只有我能访问它，我就不需要再上那把锁了。我看书的过程是可以并行的，而且不需要上锁。

推广到索引互联网所有页面、训练神经网络（大脑也是并行的）、下棋搜索（Fork-based DFS）等等，都是同样的道理。所以我们在做并发控制时，控制的只是那些关键的数据结构。我们可以在关键数据结构里放一些需要执行很长时间的任务，而任务本身不需要上锁。这样我依然可以用多个线程来实现很高的并行度。虽然我们在并发控制时退回到了串行，但程序里真正需要串行的部分是非常非常少的。这就是互斥的概念和使用。

Peterson 算法

下面我们来看一看，在计算机历史上，lock 和 unlock、acquire 和 release 到底是怎么实现的。这个图上次给大家看过。早在 1965 年，我们有了第一个公开的正确算法（Dekker 算法）。那时用的还是进程（process），因为线程还没在操作系统里出现。一个进程能够进入临界区的条件是：如果别人不想进，或者轮到它了。这听起来像绕口令。这里有一个链接详细解释了这个算法是怎么工作的，是个挺有趣的阅读材料。

Dekker 算法的整个协议状态空间很复杂，有段看起来很奇怪的代码。人类花了很长时间在头脑风暴中想出各种奇妙的算法。直到 1981 年，我们才有了一个大家可能觉得比较满意的算法——Peterson 算法。虽然它还是绕口令：一个进程 P 可以进入临界区，如果别人不想进，或者它声称自己想进并且把轮次让给了对方。完全不知道他在说什么。即使你看到那段非常短的代码，也可能很费解。

没关系，我们今天给大家讲解一下，让大家看看那个时代的人是怎么解决并发问题的。Peterson 算法做了一个协议：假设现在有 Alice 和 Bob 两个人。Alice 拿着 Bob 的名字，Bob 拿着 Alice 的名字。如果你想进入房间，协议是这样的：首先，Alice 要举起自己的手，然后在不管任何事情的前提下，把手上的名字贴到门上。这时门上有一个名字，手也举起来了。她对世界状态的修改就完成了。接下来她开始观察世界状态：先看 Bob 有没有举手。如果 Bob 没有举手，她就可以直接进入房间。如果 Bob 举着手，她就要额外看门上的字。如果字是自己的，她还是可以进去。如果要出去，就把手放下来，门上的字就留在那儿，没关系。

比较有趣的情况是 Alice 和 Bob 同时想要进入。他们都会举手，然后进入下一步：把自己手上的名字贴到门上。后贴的人会把先贴的人的名字覆盖掉。这时他们互相观察，发现对方的手都是举起来的，于是观察门上的字。如果门上的字是自己，就可以进入。假设 Alice 先进去，Bob 就等着。Alice 进入后把手放下，Bob 看到 Alice 手放下后，Bob 也可以进入。这样就完成了协议。

为什么不是把自己的名字贴在门上，而是要把对方的名字贴在门上？这是一个很神奇的协议。它的直观逻辑是：如果只有一个人举手，他就可以直接进；但如果两个人举手，就要由门上的标签来决定。这是一个看似简单但实际会覆盖的协议，设计得非常精妙。你会花一点时间去研究教科书，觉得这是一个非常有趣的算法。但这不是算法课，这是操作系统课。操作系统课想做的是用一个正确的机制去直接解决这样的问题。

我最早从上操作系统课开始，就会人肉模拟整个 Peterson 算法的过程。如果把整个人包括举手状态、门上的字、执行到哪一步都写成状态，那就是 X、Y、turn 以及 PC1、PC2。初始时 PC1=0，PC2=0。如果 Alice 走一步，她会举手，状态变成 (1, 0, B) 之类的。这样我要讲 20 分钟，一边讲一边讲算法背后的直觉。但后来我们很快想通了一件事：既然我可以在黑板上模拟这个程序，而这个程序本身是代码，我完全可以在电脑上执行它，并实现一个解释器，从当前状态让 Alice 或 Bob 执行一步到下一个状态。这就是所谓的模型检查器（model checker）。

我这里有很多例子，操作系统里的各种概念都可以用模型检查器来检查。比如我写了一个 Python 算法，执行它以后会得到一个状态图。状态里有共享内存的状态、局部变量的状态。我可以把状态迁移图画出来，证明 Peterson 算法是正确的。我看到状态里要么 Alice 在临界区，要么 Bob 在临界区，没有他们同时进去的情况。我们还可以把这个算法稍微改一下，比如如果不是先举手再贴名字，而是先贴名字再举手，这还对不对？我期末考试就出这种题。你看我 Python 上有多少种变体，一秒钟我就能知道它错了。如果放下旗子之后把门上的字条撕掉，还对不对？观察举手和名字的顺序交换，会不会存在死锁或不公平的行为？如果我们每一个都像这样在黑板上推一遍，这节课就完全结束了。

我们做计算机科学的人有一种倾向，就是想方设法把自己杀死问题的过程自动化。编程就是把人类世界里的过程投影到信息世界里。我们千方百计地想把自己做过的事情在计算机里自动化再做一遍。最早是普通的循环程序，后来有了模型检查器。模型检查器做的是 proof by brute force：我只要暴力地遍历所有可能的状态，一个一个看它对不对就可以了。这相当于用一个程序操控另一个程序的执行，有点像套了一层虚拟机。这个技术在 2007 年得了图灵奖。

就是因为有这样的技术，不管是模型检验还是大语言模型，都使我们的智能被延伸了。所以我非常喜欢“电脑”这两个字，比 computer 翻译得还好。电脑是一种 scalable 的智能，它可以无限复制。一旦这种智能有了，它就能提供一样的服务。它是确定性的，但又具有类似人的智能，非常神奇。它可以帮我们回答底下这些各种各样的问题。我觉得这是我们做计算机科学的人的一种“叛逆”本质。

有时候讲到这，我会想起以前班上老师总是夸的好学生。他每次都会认认真真完成老师作业，工工整整记笔记。这启发了思维，但也可能浪费了生命。就像我最早在黑板上模拟 Peterson 算法时，感到非常不适。第一很容易错，一边要应对讲课，一边要理清每一个逻辑步骤。第二，何必呢？如果我的智能可以被替代，能不能够被一个程序替代？当我问出这个问题的时候，我就实现了 model checker。后来的课上就有了它。今天我一直坚持让大家和 AI 对话，因为它是一种 scalable 的智能，你拥有了它，就可以以比之前快得多的效率学到新东西。

刚才 Peterson 算法的证明，以及我在 Python model checker 里的证明，都是有假设的，而且做了一些过度简化的假设。比如我们假设了 load 和 store 指令是瞬间完成且生效的，并且假设指令按照程序书写的顺序去执行。这是 Peterson 算法的假设。我们刚才证明这个算法的正确性也是在这个假设下才成立的。根据我们上一节课的内容，所有这两个假设显然都是不对的。但这些假设在 Peterson 算法提出的时代是合情合理的，因为那时第一没有高性能的编译器，第二没有多处理器的计算机。在他们眼里，计算机就是 load、store 一条条指令执行完了才执行下一条。

所以在今天我可以告诉大家，Peterson 算法其实是错的。当然，不是说没办法写一个对的 Peterson 算法（比如加上很多 memory barrier）。我给大家提供了一个正确的实现版本，但加了很多 barrier。如果我把 barrier 定义成空的，这个程序就不正确。你可以在你的计算机上观察到它出错。我有一个检查机制：每当一个进程进入临界区，就会有一个原子计数器加一。如果有两个进程进入，计数器变成 2，就说明有两个进程同时进入了你的房间（锁的房间），那就错了。你会看到 serve fail。

但是我非常惊奇地发现，这样一个错误的代码在我的系统上竟然没法复现错误。上一节课我非常明确地给大家复现了 weak memory model 的行为，但这个错误的 Peterson 算法在我这台机器上竟然不能复现。这也是并发最可怕的地方：这个算法真的是错的，在你的电脑上跑可能 crash，也可能因为各种机缘巧合看起来是对的。也就是说，你很可能在马上要做的实验里跑了很多轮测试，觉得自己的 malloc/free 做得很对，但是交到 OJ 上就是过不了。而且我还没有做非常非常 intensive 的测试。这是并发最难的地方，你不知道状态空间有多大，这个协议到底对不对、为什么对，远远超出了我们的想象。

甚至 Peterson 算法还有一个致命缺陷：它只适用于两个线程的同步。我们刚才讲的时候，牌子一个是 Alice，一个是 Bob。这意味着 Alice 需要知道对方是 Bob，Bob 需要知道对方是 Alice，这样才能写 0 或 1。但在实际当中，我们可以用 spawn 产生成百上千个线程，线程可以动态地创建和结束，我们根本不知道在任何时刻系统里还有多少个线程。所以这根本不 work。Peterson 算法虽然可以扩展到多个线程，但那超出了我们课程要讨论的范围。我们要的不是智力体操，我们需要的是 absolutely correct 的工程化方案。所以我今天讲 Peterson 算法并不是要让大家做智力题，而是让你们理解中间的复杂性，并且用合适的方式管控它。

原子指令和 futex

所以我真的要教你们的是：到底我们怎么样实现正确的互斥？Peterson 算法做了一个错误路线上的尝试：试图在 load 和 store 之上实现互斥，假设 load 和 store 是原子的。1965 年这个假设可能还勉强，但计算机系统是我们自己造的，我们当然可以把它改造成更容易实现互斥的样子。你看，解决问题的方式是解决提出问题的人——不，是推翻问题的假设。这才是我们 systems 人解决问题的最好思路：去理解假设，并在工程意义上合适的时候推翻它。一旦假设被推翻，你就打开了一片全新的天地。我们要做的事情是把计算机系统改造成容易实现互斥的样子。这就是计算机科学和自然科学很大的不同。自然科学（比如生命科学）的规则不是我们定的，我们只能理解规则然后做事。但计算机科学的规则全是我们自己定的。只要不违背物理极限，软件不好解决的就让硬件来帮忙。如果我们觉得互斥是件很重要的事，那就让计算机系统给我们添加一些指令，只要在电路上实现不太复杂。比如操作系统给一条关中断的指令，它就能实现互斥了。所以下一步我们要做的事就是在硬件上增加一条指令，帮助我们实现多处理器上的互斥。

我们应该怎么实现多处理器上的互斥呢？我们再回到最初的那个模型。什么是互斥锁？互斥锁在 acquire 和 release 的时候，就是我们有一个桌子，桌子上有一把钥匙。lock 就是你需要把钥匙拿过来，release 就是把钥匙放回去。Peterson 算法在做假设的时候面临一个最大挑战：它假设一条指令要么做 load，要么做 store。这在现实意义上意味着，当我去看别人的时候（load），我的手必须背在后面不能动。刚才我们说第一步是举手（store），第二步是贴名字（store）。一旦 store 完了，你就只能观看。所以 Peterson 算法的假设是：你在 load 时手是背在后面的（只能看），你在 store 时眼睛是蒙起来的（不能看）。而在物理世界当中，如果你想实现 acquire，也就是把桌上的钥匙拿起来，这对人来说是一个再自然不过的过程，你从来没有觉得困难。为什么？因为你是一边 load 一边 store：你的手在伸过去的时候，眼睛是能看到的。所以当两个人同时伸手时，他们自然而然就能互相协同一下，谁快谁慢，礼让一下就拿过来了。我们在谈论 acquire 时，和 Peterson 算法的根本假设是不一样的。

因此，如果我们想要解决这个问题，其实只需要有一条指令能帮我们完成一个 load 加一个 store 就可以了。如果我们写一个不正确的 lock 代码：看到桌上有钥匙就把它拿走，没有就重试。unlock 就是把钥匙放回去。这个代码直接运行为什么不对呢？和前两天那个山寨支付宝的例子一样：两个线程都想扣 100 块钱，扣之前都要判断钱够不够。如果我看到钱够，等我执行扣钱操作时，钱可能已经被别人扣走了。本质上是：我刚刚看到桌上还有钥匙，等我执行“把钥匙拿走”时，钥匙已经被别人拿走了。我只要把这两句话合起来，有一小段时间的“Stop the World”就好了。

这就是计算机系统给我们提供的原子指令。未必一定是原子指令，还有一种办法是真的实现一小段时间的“Stop the World”。有两种实现方式。像 x86 有一个指令前缀 lock，比如 lock add eax, [mem]。它真的是一把总线上的锁，会把总线锁住，别人就不能访问内存了。这时我就可以对这个地址先做一个 load，再做一个 store。因为是同一个内存地址，如果我把这个地址锁住，就没有人可以打断我了，我就好像达到了“Stop the World”的效果。只要实现了这个，不管哪个体系结构其实都支持，问题不就解决了吗？问题的解决比你想象的要简单。你不仅可以用它来实现 lock 和 unlock，甚至它还提供了一系列非常高效的原子指令。你只要有一条比如 lock add 汇编指令，就可以实现正确的 sum++。这个总线锁在最早的 80486 支持 lock 指令时，就是画在图上的，总线上真的有一个锁信号。

我们也给大家准备了这样的代码。这里的锁叫 spinlock（自旋锁）。spinlock 和 mutex lock 的使用方法是完全一样的。spinlock 的实现就是刚才说的那个思路：试图把钥匙拿过来。在计算机世界里，我们没有办法直接表达出一把“钥匙”，必须用变量。所以我用两个不同的值来表示，比如 0 表示空，1 表示钥匙。我可以做很多种原子操作，比如原子的加一，或者是原子的交换（exchange）。我可以用原子交换指令把我手上一个“空”的值和内存里的“钥匙”值交换。只要这个 exchange 指令实现了“Stop the World”的效果，那么无论有多少人来，只有最先执行 exchange 的人能把钥匙换出来。剩下的人就只能换到我手上那个“白纸”了。

这个指令有一些变体，比如 compare-and-exchange（比较并交换），它可以先比较，如果相等再交换。这样我可以先看一眼它是不是钥匙，如果是再换过来，这样能节省一次内存写，性能更好。但基本上，你可以做一个这样的 atomic exchange，编译器会帮你编译成对应体系结构的代码（无论是 x86、ARM 还是 RISC-V）。我这里用了一个更强的内存模型（acquire-release），这也是没问题的。我希望把 lock 换进去，并把里面的结果拿出来。如果里面的结果是 FREE，那么我就可以进入临界区。这个例子和 mutex lock 的使用完全一样，你可以看到我这里有十次循环，每次做 sum++，它确实可以实现多处理器上的“一加一”。相当于你可以手工实现一个 mutex lock。

但是刚才的那个方法有一个非常严重的问题。你想想我们是怎么实现互斥的：桌上有一把钥匙，然后有好多人，每个人都盯着这把钥匙，每个人都在一个 while(1) 循环里，试图去把里面的钥匙换出来。一旦有一个人把钥匙换走了，这个人很开心，可以继续执行了。但是所有其他人在干什么？他们在死循环。因为现在桌上已经是白纸了，他们就是拿白纸和白纸交换，但他们不知道这个人什么时候才会把钥匙还回去。所以 CPU 就浪费掉了。除了获得锁的那个线程可以执行，其他处理器上的线程都在空转浪费。这叫做“一核有难，八核围观”。如果你这把锁持有的时间很长，你不如把 CPU 让给别的线程去执行。

第二个问题更严重。今天我们说了，操作系统可以关中断，应用程序不能关中断。这就意味着，现在拿到钥匙的线程可能会被中断。比如说我现在有四个或八个 CPU，但系统里可能有 100 个可以运行的线程。当持有钥匙的线程被中断后，操作系统可能会换另外一个线程上来运行一会儿，因为我们要公平地造成并发的假象。我现在有 100 个线程要运行，只能把一秒钟切成 1000 份，轮流执行。这下就惨了：持有自旋锁的线程被切换出去了。操作系统可以把这个线程扔到磁盘上，甚至做个快照扔到另一台计算机上运行（有个叫 CRIU 的工具可以做到）。他消失了，可能一年以后才回来。这时系统里所有的其他线程又换上来，也想得到这把锁，结果系统里百分之百的资源都被浪费掉了。这显然不是你想要的。

所以一方面，原子指令 exchange 的方式确实能实现互斥，但另一方面，如果我们能把“拿钥匙拿不到”这件事告诉操作系统，操作系统就能做出更好的决策。比如我换了一次没换到，我就告诉管理员：“我先去睡觉了，能不能等钥匙回来了再把我叫醒？”这样没拿到钥匙的人都去睡觉了，真正需要 CPU 的人就可以上来运行了。这显然是一个系统调用。这是线程自己解决不了的问题，必须通过操作系统。

理论上说，我们可以实现一个 sys_acquire 和 sys_release，把锁的实现放到内核里。内核里会关中断（当然内核自己的锁既要关中断也要自旋）。在内核里如果发现锁还没归还，就可以直接把这个线程变成睡眠状态，并给它做个标记，告诉内核这个线程在等哪把锁。等到那把锁被释放、钥匙回来的时候，再把线程唤醒。这是完全没有问题的。

在 Linux 里，它并没有直接用 sys_acquire 和 sys_release，而是有一个非常有趣的机制叫 futex（fast userspace mutex）。大家可以去看手册。futex 是一个非常复杂、难以理解的机制。你们回去可以看两篇文章，其中有一篇叫“Futexes Are Tricky”，里面就吐槽了 futex 非常难用。这里有一个吐槽说，Rusty Russell 发布了一些代码，实际上是错的，他后来也承认了弄错很正常，他自己第一次也搞错了。futex 的复杂度在于它一部分在用户态，一部分在内核态。

我们可以大概了解一下 futex。它叫“快速用户空间互斥”。它有两个操作，一个叫 FUTEX_WAIT，一个叫 FUTEX_WAKE。它可以有一个 fast path 在用户态。相当于如果我 exchange 拿到了钥匙，我就不需要进入内核，直接继续执行。所以在没有人争抢这把锁的时候，我不需要进入内核，只需要 exchange 就行了。如果发生了争抢（exchange 发现不是 FREE），我就需要有一个绝对正确的 slow path 进入内核。这里的难点在于，不仅 acquire 时的 fast path 想不进入内核，release 时你也不想进入内核，而这就非常麻烦了。它的目标是在没有锁竞争、不拥挤的时候，可以不进入内核完成所有同步。这个比较复杂，我们暂时不需要知道细节。

但我们可以做的是对比不同的求和方式，看看它们的区别。我今天最后一个例子，我觉得非常喜欢。我们可以写这样一份代码。今天我讲了很多个实现互斥的方法，包括 atomic exchange、mutex lock/unlock、spinlock，以及内核里的 futex。到底谁好谁坏、什么时候好什么时候坏？其实你们完全可以做个实验来知道。而且今天在有 AI agent 的时候，你们做实验会比以前前所未有的简单。

我就做了这样一个程序。我希望做 N 次 sum++，把这 N 次分配到 T 个线程里。T 是在命令行里输入的。我可以用这个 main 函数和好几个不同的实际实现链接起来，包括原子指令（在 x86 里是 lock add）、mutex（我直接用了 pthread 的 mutex，和我们的线程库里的 mutex lock 一样）、spinlock（不停 exchange 的自旋锁），还有我让 AI 帮我写了一个每次都进入系统调用的 futex 版本（强制每次 acquire 和 release 都用 futex 系统调用进入内核），看看它们到底有多快多慢。

你真的只需要一个 prompt 就行。我今天做这个就只用了一个 prompt。你们要能想到这一点，这是一个很重要的量化研究方法。你不知道发生了什么，但根据线索（比如上课讲“一核有难八核围观”），你觉得性能应该不一样。如果你觉得性能应该不一样，你就能够准确地度量性能的变化和差异。所以我就给了这样的 prompt：希望对比这些实现，做一个控制变量的对比实验。控制总的 sum++ 次数不变，但把它们分布在 1、2、4、8、16 个线程上，分别为三种实验重复五次（一定要做可复现的实验，千万不要做 cherry picking）。统计一次 sum++ 的平均时间，保存原始数据为 CSV，并生成带 error bar 的图。你完全不需要知道怎么写脚本，只需要知道你确实需要一个科学的定量对比，就可以看到有趣的结果。

他收集了实验的原始结果，并画成了图。这里有两张图：一个是每次 sum++ 所需的平均时间（纳秒），另一个是它的倒数，也就是一秒钟能执行多少次 sum++。这个图符不符合你们的预期呢？你们发现，只有一个线程时，所有程序执行同样多的 sum++，速度都是最快的。不管你是用陷入内核的、自旋的、mutex 的还是 atomic 的。而且你会发现，陷入内核（futex 系统调用）的代价远远高于其他。你马上就学到了：进入操作系统内核是有额外代价的，所以你希望每一次系统调用（比如 read）能读出尽可能多的数据。几百纳秒的代价，如果你只是在用户态，可能只要几纳秒就能做一次 sum++。

但是一旦你开始进入两个线程、三个、四个，它们的表现就很不一样了。这个曲线叫 scalability（扩展性）。随着处理器数量的增加，树莓派有四个处理器，你看到从 1 到 2 到 4，无论用原子指令、mutex 还是 spin，差距都不是很大。但当线程数超过处理器数量时，mutex 和 atomic 的性能基本没有显著下降，但 spin 的性能下降非常显著。这就是刚才说的那种情况：如果我持有自旋锁的时候被切换出去，所有在 CPU 上运行的线程都在浪费算力。所以你可以观察到绿色的线（spinlock）现象很明显。看另一张图（每秒操作数）也能看到类似情况：原子指令性能最好，mutex 的 scalability 更好（基本上随线程增加还是一条直线），spin 较差，而 trap 的性能很差。

这是一种对待数据的科学方法。你在任何时候总是可以做很多对比实验，然后清楚地了解一个系统到底发生了什么。因为你们未来很有可能会走上一点科研的道路，我郑重地要求每一个同学在做实验之前都阅读一遍“Systems Benchmarking Crimes”这篇文章。这里面列举了很多基准测试的罪过。比如有一种叫“selective dataset hiding deficiencies”。这个图线跟我们刚才的图线有点像。最好的 scalability 是线性的。因为我的 mutex lock/unlock 之间的区域是不能并行的，所以你可以预期刚才那个是正确的：两个、三个、四个线程不可能跑过一个线程的速度，因为你还要在线程之间切换。我把所有事在一个线程里执行完一定是最快的。

而如果你是一个多线程服务器，随着线程增加，每秒处理的数据量也增加，那就相当于我刚才那几个程序上的是不同的锁，每个线程上不同的锁，处理的是分开的 sum，最后再汇总。那你会看到类似的曲线：随着线程增加，每秒完成的 sum 次数增加，这是一个好的结果。但实际上这可能是一个有 scalability 问题的程序，当超过 CPU 数量时性能会急剧下降，就有点像刚才的 spinlock。当 CPU 和线程差不多多时，每个 CPU 上都有一个线程在做 sum，围观的情况很少出现，没有显著影响，但这明显是一个 scalability 瓶颈。

你不能做任何 benchmarking crime。因为做实验很重要，你要证明你的方法是有效的。我听说在某些领域，把测试集混一点到训练集里，提升 1% 是个不成文的规矩。但在 systems 领域，我们还没有这种规矩。每个同学如果要从事这样的研究，可以从中获得很多有趣的观察，但一定要特别留意，不要有任何 benchmarking crime。