编程语言研究书库
操作系统导论(OSTEP)

并发与线程 — 共享一切的执行点,与一条丢更新的指令轨迹

11 并发与线程 — 共享一切的执行点,与一条丢更新的指令轨迹

1. 这一章讲什么

第一部分的「同时跑」全是错觉——同一时刻只有一个进程在跑。 第二部分的开篇把这个前提掀掉:多核来了,多个执行点真的在同时推进, 而且它们共享同一块内存。线程就是「进程内的多个执行点」: 上下文切换的账簿(TCB)从每进程一份变成每线程一份, 但地址空间是共享的——这正是它方便和致命的双重来源。

本章把问题钉死在一个例子上(两个线程给共享计数器各加一千万次, 结果不是两千万),然后把问题拆解成四个术语。后面三章 (锁、条件变量、信号量)就是这四个术语的逐条解法。

2. 顶层全景

  进程 = 1 个执行点 + 1 个地址空间
  线程 = 进程内多了几个执行点(各自 PC、各自寄存器、各自栈),
         地址空间、堆、打开的文件全部共享
        │
  共享 ⇒ 方便(传指针就是传数据)
       ⇒ 灾难:一句 counter++ 是三条机器指令,
              切换插在任何两条之间,结果就丢
        │
  四个词(全部 Dijkstra 造):
    临界区 → 碰共享资源的那几行代码
    竞态条件 → 两个线程同时进临界区,结果取决于谁快
    不确定性 → 每次运行结果不同
    互斥 → 同一时刻只许一个线程进临界区(我们要的性质)

图说:上半是线程模型与进程的差别,下半是问题的全部词汇。

3. 核心原理

3.1 主线例子:一千万次加法,少了 65 万

书里的小程序 t1.c:全局变量 counter 初始 0,两个线程各执行 counter = counter + 1 一千万次,主线程 join 后打印。 期望值 2000 万。实际运行(书里的真实输出)1:

prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19345221)    ← 少了 654,779
prompt> ./main
...
main: done with both (counter = 19221041)    ← 每次错的还不一样

为什么错:一条指令轨迹走给你看。 counter++ 被编译成 三条 x86 指令(counter 在地址 0x8049a1c)2:

100  mov  0x8049a1c, %eax    # 取 counter 到寄存器
105  add  $0x1,     %eax     # 寄存器加一
108  mov  %eax, 0x8049a1c    # 写回内存

设 counter 从 50 开始,灾难按步展开(书里的图 26.7 逐步对照)3:

步骤谁动作eaxcounter
1T1取:eax = counter5050
2T1加:eax += 15150
3中断OS 保存 T1(含 eax=51),换上 T2050
4T2取:eax = counter(还是 50!)5050
5T2加:eax += 15150
6T2写回:counter = 515151
7中断OS 换回 T1(eax 还是 51)5151
8T1写回:counter = 515151

图说:两次「加一」都执行了,counter 只从 50 变成 51。 T1 在步骤 2 之后被抢走,它的 eax=51 被「存档保护」, 但 counter 这个新值建立在过时的 50 上——T2 的值被整个盖掉。 两次都「成功」地加了一,合力只加了一。程序越大、循环越多, 这种切换命中要害的概率越高——所以丢的不是 1,是 65 万。

3.2 四个术语,一张网

书里把术语集中成一张旁注4:

  • 临界区(critical section):访问共享资源(变量、数据结构)的代码段。 上面的三条指令整体就是一个临界区。
  • 竞态条件(race condition):多个线程大致同时进入临界区, 都试图更新共享数据,结果变得「意外」。
  • 不确定性(indeterminate):含竞态的程序,输出随运行而变—— 计算机最珍贵的「确定性」没了。
  • 互斥(mutual exclusion):我们要的性质——一个线程在临界区内, 其余的被挡在门外;有了它,结果重新确定。

这四个词几乎全是 Dijkstra 在 1965–68 年间的论文里造的 (《Cooperating Sequential Processes》把整套思考写透了5)。 注意一个历史注脚:并发问题先是操作系统自己的问题—— 中断可以在任何时候插入,内核里每个数据结构(页表、进程表、 文件系统位图)都是潜在临界区;多线程应用只是把老问题领回了家6。

3.3 原子性:问题的正确表述

上面问题的精确表述是:我们想要那三条指令「原子地」执行—— 要么全部生效,要么全不生效,中间状态不可见7。 理想是一条超级指令 memory-add 0x8049a1c, $0x1, 硬件保证它不可中断8。但现实中没有「原子更新 B 树」这种指令—— 所以我们要的是几样基础的原子硬件原语,用它们搭出通用的 同步原语;再往上搭应用程序。这正是后面三章的脚手架: 锁(12 章)、条件变量(13 章)、信号量(14 章)9。

线程想用的两个理由也值得记下:一是并行——大数组的加法 拆给多个 CPU;二是不卡在 I/O 上——一个线程等磁盘, 别的线程继续算,单程序内部的重叠(多道程序的老思想)10。

3.4 线程模型在地址空间上的痕迹

回到第 06 章那个「两端对长」的优雅布局:多线程一来它就毁了—— 每个线程要自己的栈,栈区变成一串散布在地址空间里的块 (图 26.1:单线程一根栈,双线程两根栈,中间夹着空闲)11。 这解释了当时埋的伏笔。线程切换保存的是线程控制块(TCB): PC、寄存器、栈指针——和进程切换几乎一样,只是不换地址空间。

3.5 线程 API 一瞥(ch 27 插话)

创建线程 pthread_create(&tid, attr, start_routine, arg): 新线程从 start_routine(arg) 起跑,和 fork 的「从调用点复制」不同, 它像一次「异步的函数调用」——调用的同时调用者继续走12。 pthread_join(tid, &retval) 等线程收工并取返回值。 一个 Pthread_create/join 大写的封装:出错就打印退出—— 线程例程的错误处理纪律从第一行代码开始13。

4. 作者的判断与证据

书里给了证据的判断:

  • 丢更新的两条真实运行输出(19345221 / 19221041)可直接复现;
  • 三步指令分解 + 中断时刻的逐步轨迹(图 26.7)是完整的机理证据3。

作者的判断(立场):

  • 「并发应该让你的脑袋有点疼;不疼说明你还没懂」——作者把困惑 当成理解的路标,这是并发教学最诚实的定调9。
  • 术语全部归功于 Dijkstra,并指回 1968 年原文——历史线索给得足。

5. 边界与局限

  • 竞态的量化(到底多大概率丢、怎么测)本章没给; 工具留到第 32 章(AFxP 研究 + 工具)。
  • 单处理器上的关闭中断、多处理器上的硬件原子指令—— 这些「解法的第一块砖」在下一章(锁)才登场。
  • 线程 API 一章自承是参考性质,「更好的用法在后续章节慢讲」。

6. 可带走的

  1. 共享内存 + 抢占调度 = 竞态的配方。缺一不可: 不共享没冲突,不抢占(自己让出)也能靠纪律避免。
  2. counter++ 丢更新的轨迹值得能默画:取、加、写回, 切换插在任两条之间,至少丢一次更新。
  3. 四词链:临界区 → 竞态 → 不确定性 → 互斥。 诊断并发 bug 时按这个链条问:临界区在哪?谁在抢?结果确定吗?
  4. 原子性是「全或无」;大结构的互斥只能用原语搭,别指望硬件懂你 的业务结构。
  5. 每个线程有私有栈——栈上的变量天然线程私有, 堆上的才需要保护。这决定了「数据该放哪」的设计直觉。
  6. 并发问题先是 OS 自己的问题(中断 vs 内核数据结构), 应用线程只是把战场扩大了。

7. 原文地图

主题原书章原文位置
对话:并发篇开场25.A Dialogue on Concurrencytext/27-ch25-25-a-dialogue-on-concurrency.txt:1(搜「concurrency」)
线程与进程:共享地址空间26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:31(搜「stack」)
用线程的两个理由26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:75(搜「Why Use Threads」)
线程创建与三种执行次序26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:116(搜「Thread Creation」)
一千万次加法的输出26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:335(搜「19345221」)
三条指令分解26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:372(搜「0x8049a1c」)
中断轨迹(50→51)26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:431(搜「Figure 26.7」)
四术语旁注26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:548(搜「KEY CONCURRENCY TERMS」)
Dijkstra 与术语来历26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:452(搜「Dijkstra」)
原子性与同步原语26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:457(搜「ATOMIC OPERATIONS」)与:523(搜「CRUX」)
并发为何在 OS 课26.Concurrency: An Introductiontext/28-ch26-26-concurrency-an-introduction.txt:569(搜「Why in OS Class」)
pthread_create/join27. Interlude: Thread APItext/29-ch27-27-interlude-thread-api.txt:46(搜「pthread_create」)

Footnotes

  1. 出处:「26.Concurrency: An Introduction」第 264–350 段(text/28-ch26-26-concurrency-an-introduction.txt:335,搜「19345221」)。代码在图 26.6,两次异常输出在正文。 ↩

  2. 出处:「26.Concurrency: An Introduction」第 367–380 段(text/28-ch26-26-concurrency-an-introduction.txt:372,搜「0x8049a1c」)。 ↩

  3. 出处:「26.Concurrency: An Introduction」第 407–445 段(text/28-ch26-26-concurrency-an-introduction.txt:431,搜「Figure 26.7」)。轨迹假设 counter 初值 50。 ↩ ↩2

  4. 出处:「26.Concurrency: An Introduction」第 548–567 段(text/28-ch26-26-concurrency-an-introduction.txt:548,搜「KEY CONCURRENCY TERMS」)。 ↩

  5. 出处:「26.Concurrency: An Introduction」第 452–453 段(text/28-ch26-26-concurrency-an-introduction.txt:452,搜「Dijkstra」)与参考文献 [D65]D68。 ↩

  6. 出处:「26.Concurrency: An Introduction」第 569–589 段(text/28-ch26-26-concurrency-an-introduction.txt:569,搜「Why in OS Class」)。 ↩

  7. 出处:「26.Concurrency: An Introduction」第 457–476 段(text/28-ch26-26-concurrency-an-introduction.txt:457,搜「ATOMIC OPERATIONS」)。 ↩

  8. 出处:「26.Concurrency: An Introduction」第 478–504 段(text/28-ch26-26-concurrency-an-introduction.txt:484,搜「memory-add」)。 ↩

  9. 出处:「26.Concurrency: An Introduction」第 505–527 段(text/28-ch26-26-concurrency-an-introduction.txt:523,搜「CRUX」)。 ↩ ↩2

  10. 出处:「26.Concurrency: An Introduction」第 75–114 段(text/28-ch26-26-concurrency-an-introduction.txt:83,搜「parallelism」)。 ↩

  11. 出处:「26.Concurrency: An Introduction」第 30–73 段(text/28-ch26-26-concurrency-an-introduction.txt:54,搜「Single-Threaded」)。 ↩

  12. 出处:「27. Interlude: Thread API」第 27–80 段(text/29-ch27-27-interlude-thread-api.txt:46,搜「pthread_create」)。 ↩

  13. 出处:「27. Interlude: Thread API」第 20 段及 common_threads.h 说明(text/29-ch27-27-interlude-thread-api.txt:260,搜「wrapper」)。 ↩

两个完整的虚拟机系统 — VAX/VMS 与 Linux 怎样把零件拼成整车

Previous Page

锁 — 从一条硬件指令到睡得着的锁

Next Page

On this page

11 并发与线程 — 共享一切的执行点,与一条丢更新的指令轨迹1. 这一章讲什么2. 顶层全景3. 核心原理3.1 主线例子:一千万次加法,少了 65 万3.2 四个术语,一张网3.3 原子性:问题的正确表述3.4 线程模型在地址空间上的痕迹3.5 线程 API 一瞥(ch 27 插话)4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes