13 - Multiprocessor Programming: From Getting Started to Giving Up
13 - 多处理器编程：从入门到放弃
在UNIX 有了基础的系统调用 API (进程、地址空间、对象访问) 之后随即爆火，新的需求也随之而来，例如进程在 read() 等操作等待 I/O 时可能还可以同时完成其他任务，以及硬件逐渐有了多个 CPU 处理器……进程级的并行显得有些 “不太够用”。我们需要一个新的机制，能让多个执行流共享内存——于是就有了线程。
本讲内容：多线程编程模型、线程库，以及现代多处理器系统上的并发编程为什么困难。
1. 入门：共享内存线程模型与线程库
1.1. 并发编程：动机
void http_server(int fd) {
while (1) {
nread = read(fd, buf, 1024);
handle_request(buf, nread); // read 和 handle 有一块共享的 buf
}
}如果 buf 到来的时间不确定？
瞬间有大量请求到来
代码等 handle_request 完成才读取下一个请求
如果系统里有多个 CPU，这就更浪费了
我们想要有共享内存的进程
1.2. 解决方法：加一个操作系统 API
C 程序的状态机模型
初始状态：main(argc, argv, envp)
状态迁移：执行一条语句 (指令)
多线程程序的状态机模型
增加一个特殊的系统调用：spawn()
增加一个 “状态机”，有独立的栈，但共享全局变量
可以选择不同方向，进行状态变换
状态迁移：选择一个状态机执行一条语句 (指令)
Let's do it with model checker
1.3. 并发 v.s. 并行
并发
逻辑上的 “同时执行”
可以由操作系统/运行库模拟出的 “轮流执行”
(也可以是真正同时执行)
并行
真正意义上的 “同时执行”
有 (共享内存的) 多个处理器
同时执行指令 (load/store 访问共享内存)
前提：有多个 CPU
1.4. 多处理器编程：入门
简化的线程 API (thread.h)
spawn(fn)创建一个入口函数是
fn的线程，并立即开始执行
void fn(int tid) { ... }参数 tid 从 1 开始编号
fn 是内部的逻辑
join()等待所有运行线程的返回
main 返回默认会 join 所有线程
行为：
while (num_done != num_threads) ;
1.5. 多处理器编程入门
#include <thread.h>
int x = 0, y = 0;
// 预期：x 增长速度是 y 的两倍
void inc_x() { while (1) { x++; sleep(1); } }
void inc_y() { while (1) { y++; sleep(2); } }
int main() {
spawn(inc_x);
spawn(inc_y);
while (1) {
// 这里实现实时监控
printf("\033[2J\033[H");
printf("x = %d, y = %d", x, y);
fflush(stdout);
}
}这个程序 “证明” 了全局变量确实是共享的
1.6. More Problem
多线程程序真的利用了多处理器吗？
并发确定了，那是不是真并行？
可能是虚拟的模拟？？？我们都被 OS 骗了
在Linux系统中，你可以使用top或htop命令查看CPU核心的利用率。
线程是否具有独立堆栈？
如果是，栈的范围？
栈是 8M, 上下拥有 4M 的 red zone
栈用于存储局部变量、函数调用的上下文信息
（如返回地址、寄存器值等）
一旦占用超过栈的大小，触及 red zone...就会发出 stack overflow...
program crash
如何用 gdb 单步调试多线程程序？
LLM 帮你读过 The Friendly Manual 了
EuroSys 时的对话：System 人最擅长的就是底层工具的使用，曾经是 “做 system” 的壁垒；但现在有 LLM 了，这都不算什么了
2. 放弃（1）：状态迁移的确定性
2.1. 确定性的丧失
虚拟化使进程认为 “世界上只有自己”
除了系统调用，程序的行为是 deterministic 的
初始状态 (argv, envp) 一样、syscall 行为一样，程序无论运行多少次，结果都是一样的
并发打破了这一点
并发程序每次 non-deterministically 选一个线程执行
这意味着 load 可能读到其他线程的 store (也可能不)
非确定性的程序理解起来相当困难
不能用以前的线性程序的理解来理解多线程程序！
2.2. 确定性丧失的例子
unsigned int balance = 100;
int T_alipay_withdraw(int amount) {
if (balance >= amount) {
balance -= amount;
return SUCCESS;
} else {
return FAIL;
}
}两个线程并发支付 ¥100 会发生什么 (代码演示)
账户里会多出用不完的钱！
Bug/漏洞不跟你开玩笑：Mt. Gox Hack 损失 650,000 BTC
时值 ~$28,000,000,000
很多的并发 bug...触发条件非常苛刻...就等着黑客发现然后亏钱吧！、
2.3. 你发现你连 1+1 都不会了！
计算 1+1+1+…+11+1+1+…+1
共计 2n 个 1，分 2 个线程计算
#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);
}会得到怎样的结果？
2.4. 失去确定性的后果
并发执行三个 T_sum，sum 的最小值是多少？
初始时 sum = 0; 假设单行语句的执行是原子的
void T_sum() {
for (int i = 0; i < 3; i++) {
int t = load(sum);
t += 1;
store(sum, t);
}
}deepseek-r1 & o3-mini: 3
即便给 “还有更小的” 的提示，r1 和 o3-mini 都在非常长的思考后……还是给出 3
2.5. 答案
Model Checker: sum = 2
注意不是 1 (因为循环了 3 次)
“数学视角” 的价值
Nondeterminism 对人类来说是本质困难的
证明才是解决问题的方法
∀∀ 线程调度，程序满足 XXX 性质
2.6. 后果
正确实现并发 1 + 1 比想象中困难得多
1960s，大家争先在共享内存上实现原子性 (互斥)
但几乎所有的实现都是错的
直到 Dekker's Algorithm，还只能保证两个线程的互斥
并发影响了计算机系统世界中的一切
libc 里的函数还能在多线程程序里调用吗？
我们都知道 printf 是有缓冲区的 (fork 的例子)
两个线程同时执行 buf[pos++] = ch 很危险
man 3 printf
3. 放弃（2）：代码按顺序执行
3.1. 编译器
虚拟化：进程只需要看到自己和操作系统
Determinism: 除了系统调用，没人能 “干涉” 程序的状态
编译器：按照 “系统调用” 优化程序
语句/指令不需要按程序声明的那样执行
典型的优化：死代码消除 (dead code elimination)
只要保证优化前后的程序在系统调用层面上等价，可以任意调换/删除语句
但这和 non-determinism 是矛盾的
load 可能会读到来自其他线程写入的值
如果依赖这个假设编程，编译器会教你做人的
会删除你觉得重要的东西...导致你觉得有黑魔法！
3.2. 一个聪明的例子
while(!flag);
这样就可以实现线程的等待了
“等另一个线程举起旗子，我再继续”？
聪明，但不如编译器聪明
如果这是个顺序程序，编译器可以做什么优化？
(这甚至也是一个常见的并发 bug 模式)
3.3. 求和
#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);
}如果添加编译优化？
-O1: 100000000 (n)
-O2: 200000000 (2n)
3.4. 编译器干了什么
T_sum 的行为是对 sum 做 n 次自增
等价的改写 1
t = load(sum);
while (n--) t++;
store(sum, t);
等价的改写 2
t = load(sum);
store(sum, t + n);
编译优化假设 determinism 是绝对必要的
否则程序的性能就不能看了
3.5. 控制优化行为
方法 1：插入 “不可优化” 的代码块
while (!flag) {
// 这是内联汇编代码，告诉编译器不要优化掉这段代码
// 代码会访问内存，防止编译器优化掉对flag的访问
asm volatile ("" ::: "memory");
}方法 2：标记变量 load/store 为不可优化
// volatile关键字告诉编译器
// 这个变量可能会被外部因素（如其他线程）修改
// 不要对其进行优化
int volatile flag;
while (!flag);以上都不是《操作系统》课推荐的方法
Don't play with shared memory.
4. 放弃（3）：全局的指令执行顺序
4.1. 并发程序的状态机模型
状态迁移：选择一个线程执行一条指令
Shared memory 会 “立即写入”、“立即读出”
因此存在一个全局的指令执行顺序
4.2. 过度简化的幻觉 - Spicy
Reading: Memory Models by Russ Cox
多处理器系统很努力地维护这个幻觉
但这个幻觉是靠不住的 (想象我们在星球之间传递数据)
Non-Uniform Memory Access 甚至是分离的核心
4.3. 真实的状态机 - Spicy
为了性能：“宽松内存模型” (relaxed memory model)
Store 写入 local memory (cache)，再慢慢同步给其他处理器
允许 load 读到 local memory (cache) 的旧值
4.4. 无序的真实世界 - Spicy
共享内存导致了 “乱序”
Store 对其他处理器可见的时间点可能不同
处理器内部也会 “乱序”
对同一个地址的 store/load 允许 bypass
不同地址的 load/store 允许重排
“乱序执行” (out-of-order execution): 现代高性能处理器最值得骄傲的特性之一
处理器也是编译器
4.5. “无序”带来的后果 - Spicy
int x = 0, y = 0;
void T1() {
x = 1; int t = y; // Store(x); Load(y)
__sync_synchronize();
printf("%d", t);
}
void T2() {
y = 1; int t = x; // Store(y); Load(x)
__sync_synchronize();
printf("%d", t);
}Model Checker: 01 10 11
实际：00 (????)
4.6. 观测“无序”带来的后果 - Spicy
CPU 设计者面临了难题
更有序的内存模型 = 更糟糕的性能，但更容易编程
x86：市面 “最强” 内存模型 (类比 ARM/RISC-V)
因此，在 ARM 上模拟 x86 是个世界性的难题
Apple cheated! M1 可以把自己 “配置” 成 x86-TSO
4.7. 共享内存 & 地址空间 - Spicy
《计算机系统基础》里还学过一个东西叫 TLB
Translation Lookaside Buffer
存储了虚拟地址到物理地址的映射
每条指令执行都会访问 TLB
(因为 M[PC] 是虚拟机地址)
如果我 munmap/mprotect 改变一段内存？
有另外一个线程在另一个 CPU 上执行
内存都没了，它还在执行？
“TLB shootdown”
5. 总结
Take-away Messages: 我们可以很容易地把状态机模型扩展为共享内存上的多线程模型——只是每次选择一个状态机执行一步，通过提供 spawn 和 join 两个 API 来利用现有多处理器系统的共享内存能力。
然而，由于编译优化的 “无处不在” (处理器也是编译器)，共享内存并发的行为十分复杂。与此同时，人类又恰好是物理世界 (宏观时间) 中的 “sequential creature”，编程语言的直觉 (顺序/选择/循环结构) 也是围绕顺序程序设计，因此共享内存上的并发编程是非常具有挑战性的 “底层技术”。在《操作系统》课中，我们不建议大家 “玩火”——我们之后会介绍多种并发控制技术，使得我们可以在需要的时候避免并发的发生，使并发程序退回到顺序程序，从而使我们能够理解和控制并发。
Last updated