写在前面这是本系列的第十三篇。在 UNIX 有了基础的系统调用 API (进程、地址空间、对象访问) 之后系统随即爆火。但新的需求也随之而来例如进程在read()等操作等待 I/O 时如果还能同时完成其他任务该多好加上硬件逐渐发展出了多个 CPU 处理器……传统的“进程级并行”显得有些不太够用了。我们需要一个新的机制能让多个执行流共享内存——于是线程Thread诞生了。本讲内容多线程编程模型、线程库以及为什么在现代多处理器系统上进行并发编程极其困难甚至会让你觉得编译器和 CPU 在对你施展黑魔法。入门共享内存线程模型与线程库并发编程动机voidhttp_server(intfd){while(1){nreadread(fd,buf,1024);handle_request(buf,nread);// read 和 handle 有一块共享的 buf}}如果 buf 到来的时间不确定瞬间有大量请求到来。传统的单线程代码必须等handle_request完成后才能去读取下一个请求。如果系统里有多个 CPU这种串行处理就太浪费算力了。于是我们想要有共享内存的并发执行流。解决方法加一个操作系统 APIC 程序的状态机模型初始状态main(argc, argv, envp)状态迁移执行一条语句 (指令)多线程程序的状态机模型增加一个特殊的系统调用spawn()它能增加一个“状态机”这个状态机有自己独立的栈但和原状态机共享全局变量。从此状态机可以选择不同的方向进行状态变换。状态迁移每次随机选择一个状态机执行一条语句 (指令)。并发 v.s. 并行并发 (Concurrency):逻辑上的“同时执行”。可以由操作系统/运行库在单核 CPU 上模拟出的“轮流执行”时间片轮转。包含了真正同时执行的情况。并行 (Parallelism):真正意义上的物理“同时执行”。必须有共享内存的多个物理处理器。多个 CPU 同时执行指令load/store 访问共享内存。多处理器编程入门简化的线程 API (thread.h)spawn(fn)创建一个入口函数是fn的线程并立即开始执行。例如void fn(int tid) { ... }参数tid从 1 开始编号fn是线程内部的逻辑。join()等待所有正在运行的线程返回。main 函数返回前默认会join所有线程。底层行为类似while (num_done ! num_threads) ;多线程代码初体验#includethread.hintx0,y0;// 预期x 增长速度是 y 的两倍voidinc_x(){while(1){x;sleep(1);}}voidinc_y(){while(1){y;sleep(2);}}intmain(){spawn(inc_x);spawn(inc_y);while(1){// 这里实现实时监控printf(\033[2J\033[H);printf(x %d, y %d,x,y);fflush(stdout);}}这个简单的程序直接“证明”了全局变量确实是被多个线程共享的。更多需要思考的问题 (More Problems)多线程程序真的利用了多处理器吗代码层面并发确定了那是不是真并行会不会是虚拟的模拟我们是否被 OS 骗了提示在Linux系统中你可以使用top或htop命令按1展开查看各个 CPU 核心的真实利用率。线程是否具有独立堆栈是的。栈的范围通常是 8M并在上下两端设置了不可访问的 4M 红色警戒区 (Red Zone)。栈用于存储局部变量、函数调用的上下文信息如返回地址、寄存器值等。一旦深度递归导致占用超过栈的大小触及 Red Zone系统就会发出Stack Overflow错误并 Crash。如何用 GDB 单步调试多线程程序建议让 LLM 帮你阅读 GDB 官方手册中的 Threads 章节。EuroSys 会议上的趣闻System 领域的研究人员曾经最擅长的就是底层复杂工具的使用这曾是“做 system”的壁垒但现在有了 LLM工具的使用门槛被彻底抹平了。放弃1状态迁移的确定性确定性的彻底丧失虚拟化使进程认为“世界上只有自己”。除了系统调用单线程程序的行为是 Deterministic (确定性) 的。只要初始状态argv,envp一样、系统调用行为一样程序无论运行多少次结果都是绝对一样的。并发彻底打破了这一点并发程序每次会 Non-deterministically (非确定性地) 选一个线程执行。这意味你的load指令可能读到其他线程刚刚store的值也可能读不到非确定性的程序理解起来相当困难。千万不能再用以前线性程序的思维去理解多线程程序确定性丧失的真实灾难unsignedintbalance100;intT_alipay_withdraw(intamount){if(balanceamount){balance-amount;returnSUCCESS;}else{returnFAIL;}}如果两个线程并发去扣款 ¥100 会发生什么并发 Bug 会导致账户里多出用不完的钱Bug 和漏洞绝不跟你开玩笑著名的 Mt. Gox 黑客事件正是利用并发漏洞盗取了 650,000 枚比特币时值约 280 亿美元。很多的并发 Bug 触发条件非常苛刻平时测试根本测不出就等着黑客在极端情况下触发并导致巨额亏损你发现你连 11 都不会了计算 111…1共计 $ 2n $ 个 1分 2 个线程计算#defineN100000000longsum0;voidT_sum(){for(inti0;iN;i)sum;}intmain(){spawn(T_sum);spawn(T_sum);join();printf(sum %ld\n,sum);}最终你会得到怎样的结果绝不可能是 200000000每次运行的结果可能都不一样。失去确定性的后果思考题如果并发执行三个T_sum(每个循环 3 次)sum** 的最小值是多少**假设单行语句的执行被拆解为底层汇编voidT_sum(){for(inti0;i3;i){inttload(sum);t1;store(sum,t);}}AI 时代大模型测试DeepSeek-r1 和 o3-mini 经过极其漫长的思考给出的答案是3。正确答案 (通过 Model Checker 穷举得出)sum 2为什么不是 1因为无论如何穿插三个线程各自的 3 次循环必然会导致某些写操作被覆盖但绝不可能被覆盖得只剩下 1。具体推导证明留给读者提示Trace recovery is NP-Complete。“数学视角”的价值Nondeterminism (非确定性) 对人类大脑来说是本质困难的。只有严格的数学证明才是解决并发问题的方法证明对于 $ \forall $ 的线程调度程序都满足某某性质。放弃2代码按顺序执行编译器教你做人虚拟化进程只需要看到自己和操作系统。除了系统调用没人能“干涉”程序的状态。编译器会利用上述假设进行极其激进的代码优化语句和指令根本不需要按你代码写的顺序执行编译器可以任意调换、重排甚至删除死代码消除你的语句只要保证单线程视角下的最终结果一致即可。但这和多线程的并发共享是绝对矛盾的你的load可能会读到来自其他线程写入的值。如果你依赖共享内存做逻辑编译器会把你觉得极其重要、但它觉得“没用”的代码直接删掉导致你觉得程序里有黑魔法一个自作聪明的例子intflag0;voidthread1(){// 做一些准备工作...flag1;}voidthread2(){while(!flag);// 自旋等待等线程 1 举起旗子我再继续// 继续执行...}你以为这样就能实现线程同步了太天真了编译器比你聪明得多。在单线程视角下编译器发现thread2里的flag在循环内部根本没有被修改于是它会直接把代码优化成死循环// 编译器优化后的实际逻辑if(!flag){while(1);// 彻底死循环哪怕后来 thread1 把 flag 改成了 1它也永远看不见}回到刚才的求和问题voidT_sum(){for(inti0;iN;i)sum;}如果开启编译优化呢-O1优化打印出100000000($ N $)。-O2优化居然奇迹般地打印出了正确的200000000($ 2N $)编译器干了什么对于T_sum编译器发现你只是对sum加了 N 次于是它帮你做了等价的改写// 等价改写 1把变量提到寄存器里加最后写回内存tload(sum);while(n--)t;store(sum,t);// 等价改写 2直接变成加法常量公式tload(sum);store(sum,tn);正因为编译器把它优化成了只读一次、只写一次锁冲突的时间窗被无限压缩所以-O2反而得到了“正确”的结果但这证明了编译优化是建立在 Determinism (确定性) 绝对必要的假设上的。否则单线程程序的性能就没法看了。如何强行控制编译器的优化行为方法 1插入“不可优化”的内联汇编 (Memory Barrier)while(!flag){// 告诉编译器这段代码可能修改了内存别给我乱优化asmvolatile(:::memory);}方法 2使用volatile关键字// 告诉编译器这个变量可能会被外部因素硬件或异核线程修改每次必须去内存里老老实实读intvolatileflag;while(!flag);终极法则以上都不是《操作系统》课推荐的方法真正的法则是Don’t play with shared memory! (不要用裸露的共享内存玩火老老实实用锁)放弃3全局的指令执行顺序 (Spicy ️)哪怕我们搞定了编译器甚至直接手写汇编在多核处理器上依然会出大问题。曾经美好的并发幻觉我们天真地以为并发只是选择一个线程执行一条指令。共享内存会“立即写入”、“立即读出”因此世界上存在一个所有 CPU 都能看到的“全局指令执行顺序”。过度简化的幻觉现代多处理器系统非常努力地在维持这个幻觉但这幻觉在极致的性能面前是绝对靠不住的。在 NUMA 架构甚至分离核心的体系下跨 CPU 同步数据就像在不同星球之间传递信息一样存在光速延迟。真实的无序世界宽松内存模型 (Relaxed Memory Model)为了压榨物理性能现代 CPU 采用了“宽松内存模型”当 CPU 1 执行Store写入时它其实只是写到了自己的 Local Memory (L1 Cache/Store Buffer) 中然后再慢慢同步给其他处理器。此时 CPU 2 执行Load它读到的依然是旧值“乱序执行”带来的毁灭性后果不仅跨 CPU 同步有延迟CPU 处理器内部也会乱序CPU 发现对不同内存地址的load和store没有依赖关系时为了流水线满载它会自动将它们重排 (Out-of-order execution)。处理器本身也是一个微观的编译器来看看这段恐怖的代码intx0,y0;voidT1(){x1;intty;// 先写 x后读 yprintf(%d,t);}voidT2(){y1;inttx;// 先写 y后读 xprintf(%d,t);}在严格的全局顺序下无论怎么交替执行最终的结果只可能是01,10, 或11。但是在实际的多核机器上运行你可能会惊恐地得到00这就是因为 CPU 的乱序执行把读指令排到了写指令前面或者写指令还没同步到另一个 CPU。CPU 设计者面临的世纪难题更有序的内存模型 更容易编程但性能更糟糕。更宽松的内存模型 性能极高但程序员每天都在拔头发。x86 架构拥有市面上“最强”的内存模型几乎保证了顺序一致性让程序员过得很舒服。ARM / RISC-V 架构采用了极致的弱内存模型Weak Memory Model性能极高但经常乱序。因此在 ARM 处理器的 Mac 上用虚拟机模拟 x86 是个世界性的性能难题。苹果 M1 芯片是怎么解决的Apple cheated!M1 芯片内部直接做了一个特殊的寄存器开关一键把自己“硬件配置”成了 x86-TSO 强内存模型从而实现了 Rosetta 2 的恐怖模拟性能共享内存与 TLB 的幽灵不仅普通数据会出问题虚拟内存映射也会出问题。每条指令执行都会访问 TLB (Translation Lookaside Buffer页表缓存)。如果线程 1 调用munmap或mprotect删除了某段内存但线程 2 正在另一个 CPU 上狂奔。线程 2 的 TLB 缓存里依然存着旧的映射关系它甚至还能继续读写那段已经被释放的内存为了解决这个问题操作系统必须发起极其昂贵的“TLB Shootdown” (TLB 击落)强行中断其他 CPU清空它们的缓存。总结Take-away Messages:我们可以很容易地把状态机模型扩展为共享内存的多线程模型每次选择一个状态机执行一步通过spawn和join来利用多核 CPU 的算力。然而由于编译优化的“无处不在”编译器会优化CPU 乱序执行机制也是一种编译器共享内存并发的行为变得诡异且复杂。与此同时我们人类大脑恰恰是物理世界中的 “Sequential Creature” (顺序生物)我们对程序的直觉全是围绕单线顺阻展开的。因此共享内存并发编程是非常具有挑战性的“底层暗黑技术”。在《操作系统》课中我们强烈不建议大家“玩火”——不要用裸奔的全局变量和死循环去做同步。在后续的课程中我们将学习多种强大的并发控制技术互斥锁、条件变量、信号量迫使并发程序在关键时刻退回顺序执行从而让我们能够驾驭这股狂暴的并发洪流。
南京大学 操作系统 (JYY) 学习笔记：并发编程、线程与多处理器的深渊 (Concurrency)
写在前面这是本系列的第十三篇。在 UNIX 有了基础的系统调用 API (进程、地址空间、对象访问) 之后系统随即爆火。但新的需求也随之而来例如进程在read()等操作等待 I/O 时如果还能同时完成其他任务该多好加上硬件逐渐发展出了多个 CPU 处理器……传统的“进程级并行”显得有些不太够用了。我们需要一个新的机制能让多个执行流共享内存——于是线程Thread诞生了。本讲内容多线程编程模型、线程库以及为什么在现代多处理器系统上进行并发编程极其困难甚至会让你觉得编译器和 CPU 在对你施展黑魔法。入门共享内存线程模型与线程库并发编程动机voidhttp_server(intfd){while(1){nreadread(fd,buf,1024);handle_request(buf,nread);// read 和 handle 有一块共享的 buf}}如果 buf 到来的时间不确定瞬间有大量请求到来。传统的单线程代码必须等handle_request完成后才能去读取下一个请求。如果系统里有多个 CPU这种串行处理就太浪费算力了。于是我们想要有共享内存的并发执行流。解决方法加一个操作系统 APIC 程序的状态机模型初始状态main(argc, argv, envp)状态迁移执行一条语句 (指令)多线程程序的状态机模型增加一个特殊的系统调用spawn()它能增加一个“状态机”这个状态机有自己独立的栈但和原状态机共享全局变量。从此状态机可以选择不同的方向进行状态变换。状态迁移每次随机选择一个状态机执行一条语句 (指令)。并发 v.s. 并行并发 (Concurrency):逻辑上的“同时执行”。可以由操作系统/运行库在单核 CPU 上模拟出的“轮流执行”时间片轮转。包含了真正同时执行的情况。并行 (Parallelism):真正意义上的物理“同时执行”。必须有共享内存的多个物理处理器。多个 CPU 同时执行指令load/store 访问共享内存。多处理器编程入门简化的线程 API (thread.h)spawn(fn)创建一个入口函数是fn的线程并立即开始执行。例如void fn(int tid) { ... }参数tid从 1 开始编号fn是线程内部的逻辑。join()等待所有正在运行的线程返回。main 函数返回前默认会join所有线程。底层行为类似while (num_done ! num_threads) ;多线程代码初体验#includethread.hintx0,y0;// 预期x 增长速度是 y 的两倍voidinc_x(){while(1){x;sleep(1);}}voidinc_y(){while(1){y;sleep(2);}}intmain(){spawn(inc_x);spawn(inc_y);while(1){// 这里实现实时监控printf(\033[2J\033[H);printf(x %d, y %d,x,y);fflush(stdout);}}这个简单的程序直接“证明”了全局变量确实是被多个线程共享的。更多需要思考的问题 (More Problems)多线程程序真的利用了多处理器吗代码层面并发确定了那是不是真并行会不会是虚拟的模拟我们是否被 OS 骗了提示在Linux系统中你可以使用top或htop命令按1展开查看各个 CPU 核心的真实利用率。线程是否具有独立堆栈是的。栈的范围通常是 8M并在上下两端设置了不可访问的 4M 红色警戒区 (Red Zone)。栈用于存储局部变量、函数调用的上下文信息如返回地址、寄存器值等。一旦深度递归导致占用超过栈的大小触及 Red Zone系统就会发出Stack Overflow错误并 Crash。如何用 GDB 单步调试多线程程序建议让 LLM 帮你阅读 GDB 官方手册中的 Threads 章节。EuroSys 会议上的趣闻System 领域的研究人员曾经最擅长的就是底层复杂工具的使用这曾是“做 system”的壁垒但现在有了 LLM工具的使用门槛被彻底抹平了。放弃1状态迁移的确定性确定性的彻底丧失虚拟化使进程认为“世界上只有自己”。除了系统调用单线程程序的行为是 Deterministic (确定性) 的。只要初始状态argv,envp一样、系统调用行为一样程序无论运行多少次结果都是绝对一样的。并发彻底打破了这一点并发程序每次会 Non-deterministically (非确定性地) 选一个线程执行。这意味你的load指令可能读到其他线程刚刚store的值也可能读不到非确定性的程序理解起来相当困难。千万不能再用以前线性程序的思维去理解多线程程序确定性丧失的真实灾难unsignedintbalance100;intT_alipay_withdraw(intamount){if(balanceamount){balance-amount;returnSUCCESS;}else{returnFAIL;}}如果两个线程并发去扣款 ¥100 会发生什么并发 Bug 会导致账户里多出用不完的钱Bug 和漏洞绝不跟你开玩笑著名的 Mt. Gox 黑客事件正是利用并发漏洞盗取了 650,000 枚比特币时值约 280 亿美元。很多的并发 Bug 触发条件非常苛刻平时测试根本测不出就等着黑客在极端情况下触发并导致巨额亏损你发现你连 11 都不会了计算 111…1共计 $ 2n $ 个 1分 2 个线程计算#defineN100000000longsum0;voidT_sum(){for(inti0;iN;i)sum;}intmain(){spawn(T_sum);spawn(T_sum);join();printf(sum %ld\n,sum);}最终你会得到怎样的结果绝不可能是 200000000每次运行的结果可能都不一样。失去确定性的后果思考题如果并发执行三个T_sum(每个循环 3 次)sum** 的最小值是多少**假设单行语句的执行被拆解为底层汇编voidT_sum(){for(inti0;i3;i){inttload(sum);t1;store(sum,t);}}AI 时代大模型测试DeepSeek-r1 和 o3-mini 经过极其漫长的思考给出的答案是3。正确答案 (通过 Model Checker 穷举得出)sum 2为什么不是 1因为无论如何穿插三个线程各自的 3 次循环必然会导致某些写操作被覆盖但绝不可能被覆盖得只剩下 1。具体推导证明留给读者提示Trace recovery is NP-Complete。“数学视角”的价值Nondeterminism (非确定性) 对人类大脑来说是本质困难的。只有严格的数学证明才是解决并发问题的方法证明对于 $ \forall $ 的线程调度程序都满足某某性质。放弃2代码按顺序执行编译器教你做人虚拟化进程只需要看到自己和操作系统。除了系统调用没人能“干涉”程序的状态。编译器会利用上述假设进行极其激进的代码优化语句和指令根本不需要按你代码写的顺序执行编译器可以任意调换、重排甚至删除死代码消除你的语句只要保证单线程视角下的最终结果一致即可。但这和多线程的并发共享是绝对矛盾的你的load可能会读到来自其他线程写入的值。如果你依赖共享内存做逻辑编译器会把你觉得极其重要、但它觉得“没用”的代码直接删掉导致你觉得程序里有黑魔法一个自作聪明的例子intflag0;voidthread1(){// 做一些准备工作...flag1;}voidthread2(){while(!flag);// 自旋等待等线程 1 举起旗子我再继续// 继续执行...}你以为这样就能实现线程同步了太天真了编译器比你聪明得多。在单线程视角下编译器发现thread2里的flag在循环内部根本没有被修改于是它会直接把代码优化成死循环// 编译器优化后的实际逻辑if(!flag){while(1);// 彻底死循环哪怕后来 thread1 把 flag 改成了 1它也永远看不见}回到刚才的求和问题voidT_sum(){for(inti0;iN;i)sum;}如果开启编译优化呢-O1优化打印出100000000($ N $)。-O2优化居然奇迹般地打印出了正确的200000000($ 2N $)编译器干了什么对于T_sum编译器发现你只是对sum加了 N 次于是它帮你做了等价的改写// 等价改写 1把变量提到寄存器里加最后写回内存tload(sum);while(n--)t;store(sum,t);// 等价改写 2直接变成加法常量公式tload(sum);store(sum,tn);正因为编译器把它优化成了只读一次、只写一次锁冲突的时间窗被无限压缩所以-O2反而得到了“正确”的结果但这证明了编译优化是建立在 Determinism (确定性) 绝对必要的假设上的。否则单线程程序的性能就没法看了。如何强行控制编译器的优化行为方法 1插入“不可优化”的内联汇编 (Memory Barrier)while(!flag){// 告诉编译器这段代码可能修改了内存别给我乱优化asmvolatile(:::memory);}方法 2使用volatile关键字// 告诉编译器这个变量可能会被外部因素硬件或异核线程修改每次必须去内存里老老实实读intvolatileflag;while(!flag);终极法则以上都不是《操作系统》课推荐的方法真正的法则是Don’t play with shared memory! (不要用裸露的共享内存玩火老老实实用锁)放弃3全局的指令执行顺序 (Spicy ️)哪怕我们搞定了编译器甚至直接手写汇编在多核处理器上依然会出大问题。曾经美好的并发幻觉我们天真地以为并发只是选择一个线程执行一条指令。共享内存会“立即写入”、“立即读出”因此世界上存在一个所有 CPU 都能看到的“全局指令执行顺序”。过度简化的幻觉现代多处理器系统非常努力地在维持这个幻觉但这幻觉在极致的性能面前是绝对靠不住的。在 NUMA 架构甚至分离核心的体系下跨 CPU 同步数据就像在不同星球之间传递信息一样存在光速延迟。真实的无序世界宽松内存模型 (Relaxed Memory Model)为了压榨物理性能现代 CPU 采用了“宽松内存模型”当 CPU 1 执行Store写入时它其实只是写到了自己的 Local Memory (L1 Cache/Store Buffer) 中然后再慢慢同步给其他处理器。此时 CPU 2 执行Load它读到的依然是旧值“乱序执行”带来的毁灭性后果不仅跨 CPU 同步有延迟CPU 处理器内部也会乱序CPU 发现对不同内存地址的load和store没有依赖关系时为了流水线满载它会自动将它们重排 (Out-of-order execution)。处理器本身也是一个微观的编译器来看看这段恐怖的代码intx0,y0;voidT1(){x1;intty;// 先写 x后读 yprintf(%d,t);}voidT2(){y1;inttx;// 先写 y后读 xprintf(%d,t);}在严格的全局顺序下无论怎么交替执行最终的结果只可能是01,10, 或11。但是在实际的多核机器上运行你可能会惊恐地得到00这就是因为 CPU 的乱序执行把读指令排到了写指令前面或者写指令还没同步到另一个 CPU。CPU 设计者面临的世纪难题更有序的内存模型 更容易编程但性能更糟糕。更宽松的内存模型 性能极高但程序员每天都在拔头发。x86 架构拥有市面上“最强”的内存模型几乎保证了顺序一致性让程序员过得很舒服。ARM / RISC-V 架构采用了极致的弱内存模型Weak Memory Model性能极高但经常乱序。因此在 ARM 处理器的 Mac 上用虚拟机模拟 x86 是个世界性的性能难题。苹果 M1 芯片是怎么解决的Apple cheated!M1 芯片内部直接做了一个特殊的寄存器开关一键把自己“硬件配置”成了 x86-TSO 强内存模型从而实现了 Rosetta 2 的恐怖模拟性能共享内存与 TLB 的幽灵不仅普通数据会出问题虚拟内存映射也会出问题。每条指令执行都会访问 TLB (Translation Lookaside Buffer页表缓存)。如果线程 1 调用munmap或mprotect删除了某段内存但线程 2 正在另一个 CPU 上狂奔。线程 2 的 TLB 缓存里依然存着旧的映射关系它甚至还能继续读写那段已经被释放的内存为了解决这个问题操作系统必须发起极其昂贵的“TLB Shootdown” (TLB 击落)强行中断其他 CPU清空它们的缓存。总结Take-away Messages:我们可以很容易地把状态机模型扩展为共享内存的多线程模型每次选择一个状态机执行一步通过spawn和join来利用多核 CPU 的算力。然而由于编译优化的“无处不在”编译器会优化CPU 乱序执行机制也是一种编译器共享内存并发的行为变得诡异且复杂。与此同时我们人类大脑恰恰是物理世界中的 “Sequential Creature” (顺序生物)我们对程序的直觉全是围绕单线顺阻展开的。因此共享内存并发编程是非常具有挑战性的“底层暗黑技术”。在《操作系统》课中我们强烈不建议大家“玩火”——不要用裸奔的全局变量和死循环去做同步。在后续的课程中我们将学习多种强大的并发控制技术互斥锁、条件变量、信号量迫使并发程序在关键时刻退回顺序执行从而让我们能够驾驭这股狂暴的并发洪流。
