第13讲 · 多处理器编程：从入门到放弃

2026 南京大学《操作系统原理》第十三讲 · 课堂实录重构

对应讲次：第13讲（南京大学 操作系统原理）

制作模型：deepseek-flash（coding-agent / pi；据 ~/.pi/agent/settings.json）

编者说明：本书由课堂录像的语音字幕重构而成，术语、章节骨架与参考链接已按课程官方讲义（lect13.md）校准。讲师的口语风格、类比与案例被尽量保留；编辑性的补充一律以「编者说明」或「编者拓展」标出。

引子：从「系统调用」到「并发的魔鬼」

(参考时间: 00:00)

前面几讲走完了虚拟化：从 CPU Reset 开始，固件加载操作系统，操作系统加载 initramfs 里的 init，pivot_root 到真正的文件系统（systemd，pid=1），再用一系列系统调用创建出你看到的整个应用世界。

值得总结的一点是：「系统调用」这层 API 很好地隔离了应用和指令集——x86、AArch64、RISC-V 共享同一份应用生态（Linux 内核里体系结构相关的代码只占很小一部分）。这样就构建出了一个「上面是庞大应用生态、下面是多种硬件」的计算机系统。

📷 系统调用 API 隔离应用与指令集：x86/ARM64/RISC-V 共享同一份生态
回到原视频 (00:03:00)

从这一讲起，进入新部分：并发编程。标题叫「从入门到放弃」——不是让你放弃并发，而是让你知道多处理器并发编程会遇到什么困难，后面几讲再教你怎么写出「性能又好、又不容易错」的并发程序。

一、并发编程入门

1.1 两个动机

(参考时间: 00:04)

动机 1：系统调用可能执行很长时间。看一个 HTTP 服务器的顺序实现：

void http_server(int fd) {
    while (1) {
        buf = alloc_buf();
        nread = read(fd, buf, 1024);   // syscall：可能要等很久
        handle_request(buf, nread);
    }
}

执行 read 时手上明明还有别的事情可做，却只能等——「我的 CPU 被卡住了，在浪费可同时处理的时间」。能不能同时做几件事？

动机 2：多处理器系统是共享内存的，不用白不用。用 lscpu 看一下，连树莓派都有 4 个 CPU（你的机器可能有几十个）。它们的硬件模型是共享内存：CPU1 写地址 1234，CPU2 过一会儿读同一地址就能读到。但——fork 出来的进程「形同陌路」，无法直接用内存通信，只能用管道等机制把结果送回。

编者拓展｜「先有鸡还是先有蛋」：一旦一开始设计了 SMP（Symmetric Multiprocessing）就「下不了车了」——即便是 NUMA（Non-uniform Memory Access），也要维持共享内存模型。

📷 lscpu：多处理器 + 共享内存的硬件模型
回到原视频 (00:07:00)

1.2 线程：共享内存的「进程」

(参考时间: 00:10)

把 SimpleC 的状态机模型扩展一下：

• 程序最底下是 main 的栈帧，每次函数调用 push 一个新的帧（带自己的 PC）；
• 如果让两个「执行实体」共享全局变量，但各自有独立的栈——这就是线程（thread）。

graph TD
    G["全局变量（共享）"] --- T1["线程 T1：自己的栈"]
    G --- T2["线程 T2：自己的栈"]
    G --- T3["线程 T3：自己的栈"]

为什么要独立的栈？ 因为「执行一条语句」的含义就是「从栈顶帧的 PC 取一条语句执行」；如果两个线程共享栈，就全乱套了。

📷 黑板上的线程模型：各线程独立的栈 + 共享的全局数据
回到原视频 (00:11:00)

于是在这个模型里，只需要给操作系统加一个 spawn()（创建新线程，有独立栈、共享全局）+ thread_exit()——「恭喜你，你已经了解了并发的全部……吗？不，你打开了魔鬼的盒子。」（讲师把讲义发给 AI，AI 直接让他「顺着补几刀，把魔鬼具体化」，完美预言了本讲后面要讲的一切。）

在指令集层面，进程只有一个平坦的地址空间；操作系统只需要为每个线程在地址空间里划分一块区域作为它的栈，并让每个线程的寄存器（尤其 sp）指向自己的栈。「如果你想要设计一套共享内存的『进程』，你就会实现 spawn 和 exit 这两个系统调用。」

1.3 并发 vs 并行

(参考时间: 00:16)

• 并发（concurrency）：逻辑上的「同时执行」——可以只是操作系统/运行库模拟出的「轮流执行」（ABABAB……），在一个较长的时间尺度上看，两个程序都在往前推进；
• 并行（parallelism）：真正意义上的同时执行——有两个（共享内存的）处理器，同时执行指令。

对应到概念模型：SimpleC 每次选一个线程执行一条语句 = 并发模型；每个线程同时执行一条语句 = 并行模型。（后者其实过于简化——现实里每条指令执行速度不同。）

编者拓展｜这里埋了一个「魔鬼的伏笔」：真实处理器上，你的指令执行得快慢取决于整个系统复杂的状态（hit/miss、load/store 天生慢、乘除要多个周期）。所以真实并行程序到底发生了什么，其实很难理解。这个伏笔，会在本讲最后爆发。

1.4 迷你线程库与「亲手验证」

(参考时间: 00:19)

讲师提供了一个最小线程库 thread.h（对 POSIX pthreads 做减法，只适合理解原理）：

• spawn(fn)：创建一个入口函数为 fn 的线程（void fn(int tid)），tid 从 1 开始编号；
• join()：等待所有线程结束（main 返回也会默认 join）。

用它就能「证明」一些事：

• 全局变量确实共享：一个线程 x++（sleep 1s），另一个 y++（sleep 2s），main 不断打印 x, y——你会看到 x 走得比 y 快，说明数据是共享的；
• 多个线程真的并行了：两个函数各打 A/B，会看到交替出现（且顺序不确定）；
• 每个线程有独立的栈、且栈在同一个地址空间：取局部变量地址就能验证；甚至可以测出栈有多大——写一个无穷递归，每次递归记录看到的最小/最大地址，直到 stack overflow：

📷 hello.c：两个线程交替打印 A / B，顺序不确定
回到原视频 (00:23:00)

📷 x++/y++：证明线程间「全局变量共享、栈独立」
回到原视频 (00:26:00)

编者拓展｜每个线程的栈有多大？ test_stack.c 打印出 T1 的栈「大于等于 8192（KB）」——每个线程的栈默认是 8 MB。这与「主程序在 Linux 里几乎可以一直往后用栈」不同：因为每个线程的栈都必须预先在地址空间里分配好一段，所以创建线程时就得决定它有多大。

📷 test_stack：递归探测，测出每个线程栈约 8MB
回到原视频 (00:29:00)

1.5 用 gdb 调试多线程

(参考时间: 00:31)

多线程程序当然也能调试。以前讲师的第一句话是「去 read the friendly manual」（gdb Threads），现在 AI 帮你读过了：

• info threads：查看所有线程；
• thread N：切换线程；
• set scheduler-locking on：让只有当前线程往前走（其余的暂停）——把调试器「退回到」那个「选一个线程执行一步」的模型，方便你观察。

📷 gdb info threads：在多个线程之间切换、单步
回到原视频 (00:32:30)

📷 gdb set scheduler-locking on：一次只让一个线程执行一步
回到原视频 (00:34:00)

编者说明：讲师的评价很值得记：「System 人最擅长的底层工具使用，曾经是做 system 的壁垒；现在有 LLM 了，这都不算什么。」（那时候 agent 还不那么好用，现在 agent 可以直接替你用工具。）

二、放弃（1）：状态迁移的确定性

2.1 数学的确定性 vs 程序的确定性

(参考时间: 00:35)

• 数学的确定性来自函数的定义：给定输入，产生唯一输出；这让全世界的数学得以交流和发展；
• 程序的确定性：SimpleC、NEMU 的状态迁移是一个函数 s' = f(s)——给定相同初始状态，程序总是执行相同的指令序列（「Everything is a state machine」）。

确定性给了我们「可控」的感觉：程序总是可重复的（这也是我们喜欢 functional programming 的原因）。

编者说明：实际程序也有不确定性，但都来自系统调用（读键盘、getpid、rddrand/rdtsc……）和初始状态（argv/envp/auxv、随机化地址）。一旦初始状态确定，含迁移的函数就是确定的。

2.2 共享内存打破了确定性

线程执行的速度是没有保证的——这意味着一次 load 可能读到其他线程的 store，也可能不。看一个「山寨支付宝」：

unsigned int balance = 100;
int T_alipay_withdraw(int amount) {
    if (balance >= amount) {   // 检查
        balance -= amount;     // 写入
        return SUCCESS;
    } else return FAIL;
}

两个线程并发各取 ¥100：如果它们「同时」判断余额都是 100，就会各扣一次，余额变成 100 - 100 - 100 = -100——而它是 unsigned，于是账户里多出了无穷的钱。

编者拓展｜这不只是理论：历史上真实的 Mt. Gox 黑客事件损失 650,000 BTC（时值约 $28,000,000,000）；还有经典的 Diablo I「物品复制」bug：鼠标事件覆盖了「拿起的物品」变量，你把 1 块钱复制成了两份物品。「检查和写入分开」是这一大类 bug 的共同结构。

📷 山寨支付宝：两个线程并发取款，balance 被扣成负数
回到原视频 (00:43:00)

2.3 你连 1 + 1 都不会求了

(参考时间: 00:47)

#define N 100000000
long sum = 0;
void T_sum() { for (int i = 0; i < N; i++) sum++; }
int main() { create(T_sum); create(T_sum); join(); printf("sum = %ld\n", sum); }

两个线程各加 N 次，结果却不是 2N，而且每次运行结果都不一样。

📷 两个线程各 `sum++`：结果每次不同（lost update）
回到原视频 (00:47:00)

原因：sum++ 包含 load + 加法 + store 三个操作；线程 A 读到 1000、算出 1001、还没写回，线程 B 已经把值写到 2000——A 把 2000 覆盖回 1001，两个线程互相读、互相覆盖（lost update / race condition）。

这个问题本质上很难：给定每个线程看到的历史，恢复出全局顺序是 NP 完全的（Trace recovery is NP-Complete）。讲师做过一个 sequentially-consistent 小游戏（拖动事件、让每次读都读到最近的写），还把它做成 OJ 题：三个线程、每个 load; +1; store，sum 的最小值是多少？（第一反应是 3，答案是 2。）

编者拓展｜模型智力测试：2025 年，deepseek-r1、o3-mini 全军覆没；2026 年，Deepseek Expert、Qwen-3.5-max、GLM-5.1 都做对了（不允许调用工具）；而小一号的 Deepseek Instant、Qwen-3.6-plus 还做不对。

📷 OJ 题 / 小游戏：求 sum 的最小值（NP 完全）
回到原视频 (00:50:30)

2.4 确定性丧失的历史与后果

• 1960 年代，大家争先在共享内存上实现原子性（互斥），但几乎所有的实现都是错的——直到 Dekker 算法，才第一次有正确的两点互斥算法；
• 甚至 Peterson 在论文里吐槽：「Unfortunately the authors believe the correct solution is incorrect.」——发表出来的算法都有错的；
• 并发影响了计算机系统里的一切：还记得上一讲 printf 的缓冲区吗？两个线程同时 buf[pos++] = ch 是危险的。所以 printf(3) 手册明确标注了线程安全（但也只是「不损坏内存」，不保证你期望的原子性）。

📷 Peterson / Dekker：实现「正确的 1+1」比想象中困难得多
回到原视频 (00:55:00)

三、放弃（2）：顺序执行的幻想

(参考时间: 00:59)

如果只看 SimpleC，世界是清楚的——但所有人都想要极致的性能（「性能就是钱」，AI 时代更是如此；Fran Allen 2006 年因编译优化获图灵奖）。而编译器看 SimpleC 时，会大杀四方：

• 三个 x++ 可以合并成 x += 3（因为纯计算是确定的）；
• 但 syscall 是不可跨越的边界（后面 x++ 的结果要送进 syscall，不能乱改）；
• 问题是：所有优化都建立在「确定性程序」的假设上——编译器默认「没有别人会改我的 x」。

3.1 while (!flag); 与 ad hoc synchronization

(参考时间: 01:03)

你想等另一个线程「举起旗子」：

while (!flag);   // 「等旗子举起来，我就能继续」

你聪明，编译器更聪明：如果 flag 没人能改（编译器的假设），这就是个死循环，它可以把它优化成「先判断一次，如果不成立就永远转」——于是真的死循环了。这类代码（Ad hoc synchronization considered harmful）正是很多「聪明」的系统程序员写的。

3.2 求和（再次出现）：O1 得到 N，O2 得到 2N

(参考时间: 01:07)

同一份 sum++ 代码：

• -O1：编译器做循环优化——先把 sum load 到寄存器，然后循环里不停地在寄存器里加 1，最后再 store 回内存。于是一次 load 和一次 store 之间隔了很长时间（和「山寨支付宝」一样），两个线程几乎必然互相覆盖 → 结果 ≈ N；
• -O2：整个循环被优化掉，直接变成一次 sum += N——两个线程各自几纳秒就执行完，碰撞概率极低 → 结果看起来是 2N。

这才是最危险的：「你测试了 100 万次都正确，交付给客户某一天程序就挂了。」（讲师说现在不用再手撕汇编解释了，让 AI 读汇编就行。）

📷 O1/O2 对 sum++ 的优化：结果从 N 变到 2N
回到原视频 (01:07:30)

编者拓展｜控制编译优化的两种方法（但课程不推荐）： 1. 插入 compiler barrier：asm volatile("" ::: "memory");——告诉编译器「我可能改了任意内存」，优化不能跨过它； 2. 把变量标记为 volatile：volatile int flag;——禁止对它的访问被优化（这也是 MMIO 寄存器的常见写法：你先读一个字节「扔掉」再读一个，编译器不能合并这两次读）。

但《操作系统》课的忠告是：Don't play with shared memory. 两个线程同时访问同一内存地址（data race）在 C/C++ 里是 undefined behavior，非常危险。

📷 `-O1` 的优化：load/store 被提到循环外，中间是长时间的寄存器自增
回到原视频 (01:11:00)

四、放弃（3）：指令的顺序执行

(参考时间: 01:12)

你以为只有 gcc 是编译器？处理器也是一个编译器：

• .c → .s：编译器调换语句顺序、删死代码、内联、常量传播……
• .s → CPU 的内部状态：处理器内部有多条 on-the-fly 的指令，会做动态数据流分析，「擅自调整」指令执行顺序，还能在一个时钟周期执行多条指令（乱序执行、分支预测）。

📷 CPU 也是编译器：乱序执行、动态数据流分析、分支预测
回到原视频 (01:15:30)

编者拓展｜宽松内存模型（Relaxed Memory Model）：为了让 <1, 2, 3> 数得对（见下），硬件也「一切为了性能」——store 先写进 local memory（cache），再慢慢同步给其他处理器；load 允许读到 cache 的旧值。所以多处理器系统的「内存」其实像每个线程各有一份副本，它们之间只保证 eventual consistency，直到执行特殊的同步指令才达成一致。推荐阅读 Russ Cox 的 Memory Models。

4.1 Litmus test：你可能会看到「00」

(参考时间: 01:17)

int x = 0, y = 0;
void T_1() { x = 1; int t = y; }   // Store(x); Load(y)
void T_2() { y = 1; int t = x; }   // Store(y); Load(x)

按「顺序执行」的直觉推理：

但唯独「(0,0)」在顺序模型下不可能出现。然而真实运行几乎只能看到 00：因为 x=1 只写进了自己的 cache，还没送到另一个 CPU 的内存里，另一线程就读了。

📷 litmus test：反复实验 + `sort | uniq -c`，看到大量 00
回到原视频 (01:20:00)

编者拓展｜x86 的 TSO 与 Rosetta 2：Intel 当年让 x86 有一个「很强」的内存模型（TSO，Total Store Order）——既没有强到好编程，又给性能拖了后腿（还让在 ARM 上模拟 x86 变得很麻烦）。Apple 的 Rosetta 2 为此用了 TSOEnabler 这样的「作弊」手段。这些 litmus tests 可以用来逆向出一个 CPU 属于哪种内存模型。

总结

• 把状态机模型扩展一步，就得到共享内存上的多线程模型：每次选一个状态机执行一步，用 spawn / join 利用多处理器。入门只需要这一点。
• 但「单步语义」的直觉是幻想：sp 指向各自的栈、全局变量共享——这没问题；问题是这个简化模型与真实机器严重脱节。
• 放弃（1）确定性：共享内存让「每一步选谁」变成指数级可能，1 + 1 都算不对（lost update）；trace recovery 是 NP 完全的；连 1960 年代的互斥算法都错了很久。
• 放弃（2）顺序执行：编译器会基于「确定性」假设做优化（while(!flag); 死循环、O1/O2 的 sum 差异）；data race 在 C/C++ 里是 undefined behavior。
• 放弃（3）指令顺序：处理器也是编译器——乱序执行、store buffer、relaxed memory model，让你能看到顺序模型下「不可能」的 (0,0)。
• 共同点：这些都是「图方便，把刀直接递给程序员」的过度开放机制——共享内存多线程（1+1 不会写）、宽松内存模型（1,2,3 数不对）、malloc/free（use-after-free）、open/close（忘 close）。
• AI 时代的思考：AI 是「核动力牛马」，不需要「图方便」；只要在 critical path 上给它极限性能的能力，让它麻烦一点没问题。
• 本课的态度：不鼓励「玩火」——后面会介绍多种并发控制技术，让并发程序在需要时退回到顺序程序，从而可以理解和控制。

附：官方参考与延伸阅读

本讲的讲义见课程主页，以下链接按书中出现顺序整理：

阅读材料：教科书 Operating Systems: Three Easy Pieces 第 25 章（Dialogue on Concurrency）、第 26 章（Concurrency and Threads）、第 27 章（Thread API）；延伸阅读 Russ Cox 的 Memory Models。

版权说明：本讲讲义与幻灯片作者为蒋炎岩，采用 Creative Commons BY-NC 4.0 许可，来源于 https://jyywiki.cn/OS/2026/。视频画面与字幕版权归原作者所有。本书为课堂内容的学习性重构。