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 次)

• (Trace recovery is NP-Complete.)

“数学视角” 的价值

• 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 模式)

  • “Ad hoc synchronization considered harmful”

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”，编程语言的直觉 (顺序/选择/循环结构) 也是围绕顺序程序设计，因此共享内存上的并发编程是非常具有挑战性的 “底层技术”。在《操作系统》课中，我们不建议大家 “玩火”——我们之后会介绍多种并发控制技术，使得我们可以在需要的时候避免并发的发生，使并发程序退回到顺序程序，从而使我们能够理解和控制并发。