第13讲：多处理器编程——从入门到放弃
2026 南京大学操作系统原理
一、线程的概念
回顾：虚拟化与操作系统
上一节课我们完成了虚拟化部分的最后一讲。从应用视角来看，操作系统就是一组 API；我们把这组 API 逐层展开，讲了许多内容。总结一下，你们应该能留下这样一个印象：整个计算机系统从 CPU Reset 开始，Firmware 先把操作系统加载起来，操作系统再完成后续的初始化工作。
具体来说，操作系统会把 Init RAM FS 中的文件系统树加载到内存，执行其中的 Init 程序。待真正的磁盘文件系统挂载完成后，再通过系统调用切换到新的 Init 程序——也就是我们在 ps 命令里看到的第一个进程 systemd。systemd 再用各种系统调用创建出我们所见到的应用程序世界。
从操作系统视角看，这一切都是系统调用 API。在 API 之上，还有一层层的"洋葱"：Libc 提供符合 ISO 标准、可移植的基座；Libc 之上又有各种库函数，用于终端显示、图形界面等；再往上是 JavaScript、Python 等应用生态。例如 VS Code 是基于 Electron 框架的 JavaScript 程序，最终也依赖底层的 Libc。
这套设计的优雅之处在于：操作系统 API 向上支撑不断壮大的应用生态，向下兼容多种体系结构——X86、ARM64、RISC-V 等架构都可以跑同一套操作系统 API。Linux 内核用 C 实现（现在也在引入 Rust 的部分），C 语言本身具有相当的可移植性。体系结构相关的代码在整个内核中占比相对较小，这就构成了计算机系统世界的基础抽象。
为什么需要共享内存并发
今天我们正式进入并发编程部分。这一讲叫"从入门到放弃"，目的不是让大家真的放弃，而是让大家了解多处理器并发编程会遇到哪些困难，以及如何写出既有性能又不容易出错的并发程序。
在此之前，我们的程序模型是顺序（Sequential）的：程序是一个状态机，一条一条指令顺序执行。这在某些场景下会带来明显的问题。举个例子：如果你要写一个 HTTP 服务器，它需要同时处理网络请求、读磁盘、做计算。一旦执行 read 这样的阻塞系统调用，即使手上还有其他事情可以做，CPU 也只能空等——这是一种浪费。
第二个动机来自硬件。现代系统都是多处理器的，哪怕一块树莓派也有 4 个 CPU（编号 0 到 3），服务器可能有几十乃至上百个核。这些处理器提供的硬件模型是共享内存的：物理内存是一个统一的地址空间，CPU1 写入某个地址，CPU2 就能读到——既然有这样的硬件能力，不用白不用。
使用多进程（fork）可以实现并行，但如果想把计算结果汇总回主进程，就必须借助管道等 IPC 机制，非常繁琐。如果能让多个执行流直接共享同一块内存，写起来就简单多了——这正是引入共享内存并发的直接动机。
线程的定义
回顾 Sequential C 的执行模型：程序有一个函数调用栈，栈底是 main，每次函数调用都会在栈顶压入一个新的栈帧，每个栈帧里有一个 PC；此外还有全局变量（Globals）。
要让两个执行流共享内存但又能独立运行，每个执行流就必须拥有独立的栈（因为程序的执行依赖于 top frame 的 PC），同时共享同一份全局数据。这就自然推导出了线程的概念：
在指令集的意义上，整个地址空间是平坦的（一个由 mmap 创建的地址空间）。我们需要为每个线程在地址空间中分配不同的区域作为它的栈，并让每个线程的栈指针（SP）指向自己的栈空间。
基于这个模型，我们在操作系统中增加两个 API：
spawn(f)：在已有线程不变的基础上，创建一个新线程，入口函数为 f。
这两个 API 和进程的 fork/exit 非常相像，只不过这里的"fork"发生在进程内部，新线程与原线程共享内存。这就是线程——如果让你从零设计，你也会这样设计。
并发与并行的区别
并发（Concurrency） 是逻辑上的同时执行：即使只有一个 CPU，也可以让多个程序轮流上 CPU 运行（ABABAB 交替），在较长时间尺度上都有进展，这是操作系统或运行库模拟出来的。
并行（Parallelism） 是物理上的同时执行：两个线程真正加载到两个 CPU 上同时运行。
并发程序可能并行，也可能不并行；但并行程序一定是并发的。
在概念模型上，线程执行有两种理解方式：一是"每次选一个线程执行一条语句"；二是"所有线程同时向前推进"。实际 CPU 更接近后者，但由于每条指令的执行速度因缓存命中、流水线状态等因素而各不相同，真实的并行行为远比概念模型复杂——这里埋下了一个伏笔。
二、多线程编程入门
最小线程库
为了方便理解，我提供了一个最小的线程库，它在 POSIX pthread 之上做了简化，只有两个 API：
spawn(f)：创建一个入口函数为 f 的线程，函数参数是一个整数线程编号（从 1 开始）。join()：等待所有已创建的线程结束后，主函数才真正返回。
这个库在内部维护一个计数器，每次 spawn 加一，每次线程结束减一，直到计数归零才从 join 返回。POSIX 标准规定的接口，在各类平台（包括鸿蒙系统）上都有支持。
用实验验证线程模型
有了线程库，我们可以写一些程序来验证前面的概念模型：
验证共享内存：让一个线程每秒对 x 加一，另一个线程每两秒对 y 加一，主线程定期读取并打印 x 和 y。如果能在主线程中读到另一个线程写入的值，就证明了内存确实是共享的。实验结果显示 x 比 y 更新得快，印证了共享内存模型。
验证栈的独立性：在线程函数中取局部变量的地址，可以发现不同线程的局部变量地址属于同一个地址空间，但分布在不同区域。你甚至可以把指向一个线程局部变量的指针传给另一个线程，后者可以成功访问——因为它们都在同一个地址空间里。
测量线程栈的大小：通过一个不断递归的函数 probe，每次调用在栈上分配 64 字节的局部变量，同时记录观察到的最高和最低地址，直到栈溢出（stack overflow）导致线程崩溃。结果显示，Linux 默认为每个线程分配约 8 MB 的栈空间。与主线程（栈大小几乎无限制）不同，线程栈必须在创建时就在地址空间中分配好，因此大小是有限的。
用 GDB 调试多线程程序
多线程程序也可以用 GDB 调试。关键命令如下：
info threads：查看当前所有线程及其状态。set scheduler-locking on：开启后，单步执行只推进当前线程，其他线程暂停——这对应了"每次选一个线程执行一步"的概念模型，便于调试。
通过在各线程入口处打断点，再在线程间切换，可以精确地单步跟踪每个线程的执行，将抽象的线程模型与真实的汇编指令对应起来。当然，调试并发程序需要在线程间反复切换，相当繁琐。
三、非确定性
什么是确定性
引入并发之后，第一个需要"放弃"的是：状态迁移的确定性。
数学意义上的确定性来自函数的定义：给定相同的输入，永远产生唯一确定的输出。程序的确定性与此类似——在我们的 NEMU 模拟器中，状态迁移函数 f(s) = s' 就是这样一个确定的数学函数。给定相同的初始状态，程序无论运行多少次，输出必然相同。
这种确定性给了我们"可控感"：测试用例今天通过，明天还会通过；测试用例用了代码不改，行为就不变。这也是函数式编程（Functional Programming）中"纯函数"（Pure Function）受欢迎的原因——它是绝对可重复的。
然而，引入并发彻底摧毁了这一点。
并发如何破坏确定性
线程的执行速度没有任何保证。两个处理器的频率可能不同，缓存状态不同，执行同一段代码的速度就不同。在共享内存模型下，一个线程写入的值，另一个线程可能立刻读到，也可能没读到——这取决于它们执行的相对速度。
因此，多线程程序的执行模型不再是"确定地取一个线程执行一条语句"，而是：每一步都可以任意选择任意一个线程执行。这是一个指数级的可能性爆炸：两个线程各执行一步，就有 4 种顺序组合；执行 n 步，就有 2^n 种可能。你今天测试了一百万次都通过，不代表提交到 Online Judge 上也能通过。
经典案例：sum++ 求和出错
来看最简单的例子：创建两个线程，每个线程都对全局变量 sum 执行 N 次加一，期望最终得到 2N。
实际运行后，sum 的值每次都不同，且远小于 2N。原因在于：sum++ 不是原子操作，它编译后是三条指令——load（把 sum 读入寄存器）、加一（在寄存器中加）、store（把结果写回内存）。两个线程各自 load 了同一个值，各自加一，然后互相覆盖对方的写入结果，导致大量的加法操作被"丢失"。
并发的最小值问题（NP 完全）
这个问题可以作为一道考题：创建三个线程，每个线程各对 sum 执行一次 load/加一/store 操作，sum 的最小可能值是多少？
直觉上回答"3"，但实际上最小值是 1——可以构造一种极端的交错执行顺序，使得所有线程几乎都在读到同一个值后相互覆盖，最终只有最后一次写入生效。
更深层的问题：验证某个交错顺序是否合法，本身是一个 NP 完全问题。因此，即使是 1960 年代的研究者，在共享内存上实现正确的互斥（mutual exclusion）也困难重重——几乎所有早期的实现都是错的，直到 Dekker 算法才出现了第一个正确的解法。正如 Peterson 论文中引用的那句话："Unfortunately, the authors believe the correct solution is incorrect." 连发表在论文中的算法都会出错，可见并发程序的验证有多困难。
并发影响一切
并发破坏的不只是简单的计数，而是计算机系统世界里的一切。
以 printf 为例：printf 内部维护一个缓冲区，多线程程序中多个线程会同时向同一个缓冲区写字符（相当于并发执行 buf[pos++] = ch）。两个线程同时写，会互相覆盖，最终输出乱七八糟的内容。幸运的是，系统设计者已经帮我们"兜了底"：POSIX 手册明确说明 printf 系列函数是线程安全的（thread-safe）——内部已经做了保护，不会损坏缓冲区，但不保证多线程输出的原子性。
几乎所有的系统调用（read、write 等）都可以在多线程中安全使用，但行为可能有细微差异。这就是为什么每当你实现任何东西时，一旦程序是多线程的，都必须格外小心。
四、更多反直觉行为的来源
编译器优化带来的麻烦
并发程序的麻烦远不止非确定性。我们的执行模型一直是 Sequential C——从 top frame 取一条语句执行。但现实世界为了极致性能，有两层"隐形编译器"都在悄悄改变程序的行为。
第一层：GCC 编译器优化。
编译器认为，在顺序程序中，不存在"别人会在我执行过程中修改我的变量"这种情况（否则任何优化都无法做）。基于这个假设，编译器会对代码做等价变换：
- 把
x++; x++; x++; 合并成 x += 3
一个常见的陷阱是用忙等待（busy-wait）实现同步：
ounter(linewhile (!flag); // 等待另一个线程把 flag 设为 1
在编译器看来，当前线程内没有任何代码会修改 flag，因此它可以把这个循环优化成：先判断一次，如果 flag 为 0 就直接进入死循环（永远不再读内存）。这就是为什么这种朴素的同步方式是错误的。
以 sum++ 为例，用 -O1 编译时，编译器会把循环优化为：先把 sum load 到寄存器，在寄存器里循环累加 N 次，最后再 store 回去。这意味着两个线程各自有很长时间持有 sum 的旧值，最后互相覆盖，结果必然远小于 2N。
而用 -O2 编译时，整个循环直接被优化成一条 sum += N 的加法，两个线程执行这条指令的时间窗口极短，碰撞概率极低，结果看起来"几乎正确"——这才是最危险的：测试一百万次都通过，某天上线之后悄悄出错，你完全不知道原因。
要正确地在多线程中使用共享变量，需要编译器屏障（Compiler Barrier，如 asm volatile("" ::: "memory")）或 volatile 关键字——但操作系统课程的建议是：不要和共享内存玩游戏。两个线程同时访问同一个内存地址（没有同步原语保护）叫做数据竞争（Race Condition），在 C/C++ 中是未定义行为（Undefined Behavior），非常危险。
硬件乱序执行带来的麻烦
第二层"编译器"是 CPU 本身。
为了性能，现代处理器不是严格按照指令顺序执行的。它会在内部维护一个指令窗口，动态分析数据依赖关系，将没有依赖关系的指令并行执行，甚至乱序执行（Out-of-Order Execution）。只要最终结果在单线程视角下与顺序执行等价，硬件就认为是合法的。
在多处理器场景下，这带来了**内存一致性（Memory Consistency）**问题。直观上，共享内存模型应该是"每次选一个线程执行一条指令"，但实际上：
- 每个 CPU 都有自己的缓存（Cache），写操作先写入本地缓存，不会立刻对其他 CPU 可见。
- 两个 CPU 之间的内存视图可能长期不一致，只有在执行特殊的内存屏障（Memory Barrier / Fence）指令时才会同步。
经典反例（Store-Load 重排序）：
ounter(lineounter(line线程 T1：x = 1; load y → 期望读到 1线程 T2：y = 1; load x → 期望读到 1
按照任何顺序执行，至少有 x 或 y 中的一个先被设为 1，因此 T1 和 T2 读到的结果不可能都是 0。但实际运行时，可以大量观察到 (x=0, y=0) 的结果——因为每个 CPU 写完本地缓存后立刻读，读的还是本地缓存的旧值，而另一个 CPU 的写入还没有同步过来。
实验验证：运行 10 万次这样的测试，结果约 6 万次是 (0, 0)，4 万次是 (0, 1)，(1, 1) 极少出现。
这说明，我们脑海中"共享内存 = 所有线程看到同一个内存"的模型根本不存在于实际硬件中。更准确的描述是：每个线程都仿佛有一份自己的内存副本，load/store 都作用于自己的副本，副本之间的同步是不确定的，直到执行特殊指令才强制一致。
小结
并发程序打破了我们对程序执行的一切简化假设：
- 编译器优化：GCC 会在顺序程序假设下对共享变量做激进的 load/store 合并与提升。
- 处理器乱序执行：CPU 会在硬件级别重排指令，并维护各自的缓存视图。
- 非确定性：执行顺序的选择是指数级的，测试无法穷举所有情况。
这三者相互交织，产生极难理解和复现的 bug。"从入门到放弃"中需要放弃的，不是并发编程本身，而是用顺序执行的简化模型去理解并发程序——这会让你丢失大量可能发生的行为，从而导致严重的错误。
在后续课程中，我们将讨论如何正确地控制并发：用互斥锁、条件变量、原子操作等机制，在受控的条件下实现线程安全的并发程序。
