尧图网页设计 
目录1. 从冯诺依曼体系结构说起2.count最终会变成什么3. 为什么需要 Cache4. 单核下的并发问题为什么count会丢失更新5. 从单核走向多核可见性问题6. 多个内存操作之间的顺序又怎么办6.1 Store Buffer6.2 Out-of-Order Execution7. 到这里我们实际上遇到了三个问题8. 硬件如何回答这三个问题8.1 AtomicityAtomic Instruction8.2 VisibilityCache Coherence8.3 OrderingMemory Ordering / Fence9. 总结这一篇继续沿用count只关注硬件层CPU 和内存系统到底会带来哪些并发问题硬件又提供了什么能力1. 从冯诺依曼体系结构说起冯诺依曼提出将程序当作数据对待把程序指令和数据用同样的方式存储。根据这个理论计算机可以分成控制器、运算器、存储器、输入设备和输出设备。运算器和控制器组成 CPUCPU 内部还有寄存器。其中Program CounterPC程序计数器保存下一条指令的地址Instruction RegisterIR指令寄存器保存当前正在处理的指令R1这样的通用寄存器用于保存数据和中间结果。┌──────────────────┐ ┌──────────────────┐ │ 输入设备 │ │ 输出设备 │ └─────────┬────────┘ └─────────▲────────┘ │ │ └───────────────────┬───────────────────┘ │ 系统总线 │ ┌────────────────┴─────────────────┐ │ │ ▼ ▼ ┌────────────────────────┐ ┌────────────────────────┐ │ │ │ 存储器 │ │ │ │ │ │ 控制器 │ │ 程序指令数据 │ │ 运算器 │ │ │ │ 寄存器 │ │ │ │ │ │ │ └────────────────────────┘ └────────────────────────┘CPU 执行程序的过程可以简化为PC 给出指令地址 ↓ Fetch 取指 → Decode 译码 → Execute 执行 ↓ PC 指向下一条指令继续循环也就是说CPU 会不断重复Fetch → Decode → Execute依次执行程序中的机器指令。程序里的count最终也要转换成这样的指令。2.count最终会变成什么为了便于讨论可以把count简化成三条机器指令LOAD R1, [count] // 把 count 读入寄存器 R1 ADD R1, 1 // 在 CPU 内部把 R1 加 1 STORE [count], R1 // 把结果写回 count这里值得关注的是LOAD和STORE都需要访问数据。于是下一个问题自然出现如果每一次 LOAD / STORE 都要直接等待主存会发生什么3. 为什么需要 CacheCPU 的执行速度远高于主存访问速度。如果每次LOAD都要等待主存返回数据每次STORE都要等待主存完成写入CPU 会浪费大量时间。因此现代处理器会在 CPU Core 和主存之间设置更快、容量更小的多级 Cache。下面是一个简化结构具体层级以及哪些 Cache 由多个 Core 共享取决于处理器设计CPU │ ▼ L1 Cache │ ▼ L2 Cache │ ▼ L3 Cache │ ▼ MemoryCPU 访问count时通常会把包含它的整个 Cache Line 加载到 Cache。这里仍简化写成CPU │ ▼ Cachecount 0 │ ▼ Memorycount 0之后 CPU 再访问count时就可能直接命中 Cache而不必每次都访问主存。所以Cache 解决的是 CPU 与主存之间的速度差距。也就是性能问题。但它并不会让count自动变成安全的并发操作。先从单核开始看。4. 单核下的并发问题为什么count会丢失更新假设机器只有一个 CPU CoreThread A ──┐ │ ├── Core 0 ── Cache ── Memory │ Thread B ──┘两个线程不能在这个 Core 上真正同时执行但它们可以交替执行。仍然从count 0开始。Thread A Thread B │ │ ├─ LOAD count - 0 │ │ │ ├─────── context switch ────────────│ │ ├─ LOAD count - 0 │ ├─ ADD 1 │ ├─ STORE count - 1 │ │ │────── context switch ─────────────┤ ├─ ADD 1 │ ├─ STORE count - 1 │线程切换时操作系统会保存 Thread A 的执行上下文包括它已经读到的中间结果。Thread A 恢复执行后仍然会基于之前读到的0继续计算。最终count 1原因是LOAD ADD STORE不是一个不可分割的整体。只要一个执行单元进行到一半时另一个执行单元插进来就可能出现 丢失更新。于是得到第一个问题问题一一个复合操作如何不可分割地完成也就是Atomicity这里先不回答。继续往下看多核又会新增什么问题。5. 从单核走向多核可见性问题如果处理器拥有多个 CPU Core那么两个线程可能真正同时执行Thread A Thread B │ │ ▼ ▼ Core A Core B │ │ ▼ ▼ Cache A Cache B │ │ └──────────────┬───────────────┘ ▼ Memory单核下的count竞态仍然存在。但多核还会带来一个新的问题。假设count 0Core A 和 Core B 都读取过count。那么同一份数据可能同时存在于不同 Cache 中Core A Cache Core B Cache count 0 count 0 Memory count 0现在 Core A 修改countCore A Cache Core B Cache count 1 count 0于是问题来了Core B 手里的旧副本还能不能继续使用也就是说问题二一个 Core 修改数据后其他 Core 什么时候能够观察到新的值即Visibility这里仍然先不回答。继续看第三类问题。6. 多个内存操作之间的顺序又怎么办继续沿用前面的 Counter 例子count 0 ready falseThread A Thread B │ │ ├─ count 1 ├─ 读取 ready └─ ready true └─ 如果为 true读取 count程序员自然会希望如果 Thread B 已经看到ready true那么它也应该看到前面写入的count 1。也就是说我们希望 B 只出现下面两种结果结果一 Thread A Thread B 读取 ready - false 不进入 if 结果二 Thread A Thread B count 1 ready true 读取 ready - true 进入 if 读取 count - 1 打印 1而不是第三种结果Thread A Thread B count 1 这个写入尚未被 B 观察到 ready true 读取 ready - true 进入 if 读取 count - 0 打印 0也就是说当 B 已经读到ready true时如何保证它不能再读到旧的count 0但这里已经不是同一个 count 的多个缓存副本而是两个不同的内存位置count ready以及两个内存操作count 1 ready true之间的关系。于是出现第三个问题问题三多个内存操作允许按照什么顺序被其他 Core 观察也就是Memory Ordering为什么硬件会让这个问题变复杂主要是因为现代 CPU 为了性能会引入各种优化机制。6.1 Store Buffer继续沿用counter。假设count 0Core A 执行LOAD count - 0 ADD 1 - 1 STORE [count], 1其中STORE写入的count 1可能先进入 Store BufferCPUCore A 执行 STORE [count], 1 │ ▼ Store Buffer 暂存 count 1 │ ▼ Memory在 Store Buffer 中的写入对其他 Core 可见之前Core A 已经可以继续执行初始count 0 Core A Core B │ │ ├─ LOAD count - 0 │ ├─ ADD 1 - 1 │ ├─ STORE count - 1 │ │ 写入 Store Buffer │ ├─ 继续执行后面的指令 │ │ ├─ LOAD count - 0 │ │ 仍然读到旧值 └─ count 1 对外可见 │6.2 Out-of-Order Execution现代 CPU 还会为了充分利用执行单元在不破坏必要依赖关系的前提下调整内部执行顺序。只要不改变当前线程自己的执行结果这种调整本身没有问题。问题仍然出在多个 Core 之间。继续沿用前面的 Counter 发布例子Thread A / Core A Thread B / Core B count 1 if ready { ready true print(count) }从源码顺序看A 先写count再写ready。但是在没有额外顺序约束、并且硬件允许这种内存顺序时可能出现初始count 0ready false Thread A / Core A Thread B / Core B │ │ ├─ STORE count 1 │ │ 尚未被 Core B 观察到 │ ├─ STORE ready true │ │ ├─ LOAD ready - true │ └─ LOAD count - 0也就是说A 的源码先写了countB 却先观察到ready true随后仍读到旧的count 0。其他 Core 被允许以什么顺序观察这些内存操作7. 到这里我们实际上遇到了三个问题前面的问题可以归纳成三类问题问题表现硬件需要回答什么Atomicity原子性A、B 都执行count时可能都读到0最后都写回1哪些操作具有原子性Visibility可见性Core A 已经通过count把count写成1Core B 仍可能读到缓存中的0一个 Core 写入后其他 Core 什么时候能够观察到Ordering有序性Core A 先完成count再写入ready trueCore B 却可能先读到ready true随后仍读到count 0哪些操作之间具有顺序关系第一类问题既可能出现在单核线程切换时也可能出现在多核并行执行时。关键不是 CPU Core 的数量而是 Read-Modify-Write 的多个步骤能否被其他执行单元交错。接下来分别看硬件提供了哪些基础能力现代硬件分别提供了什么机制来处理这三个问题8. 硬件如何回答这三个问题8.1 AtomicityAtomic Instruction普通的LOAD ADD STORE是多个步骤。如果希望 Read-Modify-Write 对其他执行单元表现为不可分割的整体就需要硬件提供原子操作例如Compare-And-Swap Exchange Fetch-And-Add这些操作在处理器内部不一定只包含一个微小步骤。“原子”描述的是它们对其他执行单元的可观察结果读取旧值 │ 修改 │ 写入新值 │ └── 对竞争者表现为一个不可分割的原子操作回到count。如果语言把自增实现为硬件支持的原子 Read-Modify-Write那么执行过程可以理解为初始count 0 Thread A Thread B 原子地把 count 从 0 改为 1 原子地把 count 从 1 改为 2 最终count 2A 和 B 谁先执行并不重要。每次原子更新必须基于某个确定的旧值完成因此不会再出现两边都读取0、最后都写入1的情况。8.2 VisibilityCache Coherence多核处理器通过 Cache Coherence Protocol 协调多个 Core 对同一个内存位置的缓存副本。MESI 是最经典的缓存一致性协议之一M - Modified E - Exclusive S - Shared I - Invalid真实处理器中也会使用 MESI 或它的扩展、变体例如MESI MOESI MESIF ...本文不展开状态机的所有转换只看它解决的问题。假设两个 Core 都缓存了包含count的 Cache LineCore A Cache Core B Cache count 0 count 0 Shared Shared如果 Core A 需要修改它count 1硬件需要先协调这个 Cache Line 的所有权和其他副本状态。可以高度简化理解为Core A 要修改 count │ ▼ 取得对应 Cache Line 的写权限 │ ▼ 其他不能继续使用的副本失效 │ ▼ Core A 完成修改Core A 获得写权限后Core B 缓存中的count 0会失效下一次读取count时不能再使用这个旧值。8.3 OrderingMemory Ordering / Fencecount 1 ready true现代 CPU 会使用 Store Buffer 和 Out-of-Order Execution 等机制提高性能。Hardware Memory Model 必须明确哪些内存操作顺序是保证的 哪些重排是允许的 不同 Core 允许观察到哪些结果这就是 Memory Ordering。回到前面的 Counter 发布例子。假设count 1尚未被 B 观察到在允许这种结果的硬件上可能出现Thread A / Core A Thread B / Core B | | -- STORE count 1 | -- STORE ready true | | -- LOAD ready - true | -- LOAD count - 0要阻止这种结果需要用 Fence 约束两侧内存操作的顺序Thread A / Core A Thread B / Core B | | -- STORE count 1 | -- FENCE | -- STORE ready true | | -- LOAD ready - true | -- FENCE | -- LOAD count - 1写入侧的 Fence 保证count 1不能排到ready true之后读取侧的 Fence 保证对count的读取不能排到对ready的读取之前。Fence 不保证 B 一定读到ready true。但当 B 已经读到ready true时随后读取count不能再得到旧值0。9. 总结硬件针对三个并发问题提供了不同的基础能力问题硬件提供的能力Atomicity原子性Atomic Instruction 可以把counter作为一个整体完成其他执行单元不能在中间插入。Visibility可见性Core A 把count修改为1后Core B 再读取count时不能继续使用缓存中的0。Ordering有序性加入 Fence 后Core B 既然读到了ready true再读取count就必须得到1。下一篇回到语言层讨论 Java、Go 和 CPython 的并发语义如何把这些硬件能力转换成程序员可以依赖的规则。本文首发于 ThinkerQAQ 的个人博客由作者本人同步发布。原文可能持续修订最新版本请以个人博客为准。 并发编程（一）：先谈硬件——从 count++ 到原子性、可见性与有序性
目录1. 从冯诺依曼体系结构说起2.count最终会变成什么3. 为什么需要 Cache4. 单核下的并发问题为什么count会丢失更新5. 从单核走向多核可见性问题6. 多个内存操作之间的顺序又怎么办6.1 Store Buffer6.2 Out-of-Order Execution7. 到这里我们实际上遇到了三个问题8. 硬件如何回答这三个问题8.1 AtomicityAtomic Instruction8.2 VisibilityCache Coherence8.3 OrderingMemory Ordering / Fence9. 总结这一篇继续沿用count只关注硬件层CPU 和内存系统到底会带来哪些并发问题硬件又提供了什么能力1. 从冯诺依曼体系结构说起冯诺依曼提出将程序当作数据对待把程序指令和数据用同样的方式存储。根据这个理论计算机可以分成控制器、运算器、存储器、输入设备和输出设备。运算器和控制器组成 CPUCPU 内部还有寄存器。其中Program CounterPC程序计数器保存下一条指令的地址Instruction RegisterIR指令寄存器保存当前正在处理的指令R1这样的通用寄存器用于保存数据和中间结果。┌──────────────────┐ ┌──────────────────┐ │ 输入设备 │ │ 输出设备 │ └─────────┬────────┘ └─────────▲────────┘ │ │ └───────────────────┬───────────────────┘ │ 系统总线 │ ┌────────────────┴─────────────────┐ │ │ ▼ ▼ ┌────────────────────────┐ ┌────────────────────────┐ │ │ │ 存储器 │ │ │ │ │ │ 控制器 │ │ 程序指令数据 │ │ 运算器 │ │ │ │ 寄存器 │ │ │ │ │ │ │ └────────────────────────┘ └────────────────────────┘CPU 执行程序的过程可以简化为PC 给出指令地址 ↓ Fetch 取指 → Decode 译码 → Execute 执行 ↓ PC 指向下一条指令继续循环也就是说CPU 会不断重复Fetch → Decode → Execute依次执行程序中的机器指令。程序里的count最终也要转换成这样的指令。2.count最终会变成什么为了便于讨论可以把count简化成三条机器指令LOAD R1, [count] // 把 count 读入寄存器 R1 ADD R1, 1 // 在 CPU 内部把 R1 加 1 STORE [count], R1 // 把结果写回 count这里值得关注的是LOAD和STORE都需要访问数据。于是下一个问题自然出现如果每一次 LOAD / STORE 都要直接等待主存会发生什么3. 为什么需要 CacheCPU 的执行速度远高于主存访问速度。如果每次LOAD都要等待主存返回数据每次STORE都要等待主存完成写入CPU 会浪费大量时间。因此现代处理器会在 CPU Core 和主存之间设置更快、容量更小的多级 Cache。下面是一个简化结构具体层级以及哪些 Cache 由多个 Core 共享取决于处理器设计CPU │ ▼ L1 Cache │ ▼ L2 Cache │ ▼ L3 Cache │ ▼ MemoryCPU 访问count时通常会把包含它的整个 Cache Line 加载到 Cache。这里仍简化写成CPU │ ▼ Cachecount 0 │ ▼ Memorycount 0之后 CPU 再访问count时就可能直接命中 Cache而不必每次都访问主存。所以Cache 解决的是 CPU 与主存之间的速度差距。也就是性能问题。但它并不会让count自动变成安全的并发操作。先从单核开始看。4. 单核下的并发问题为什么count会丢失更新假设机器只有一个 CPU CoreThread A ──┐ │ ├── Core 0 ── Cache ── Memory │ Thread B ──┘两个线程不能在这个 Core 上真正同时执行但它们可以交替执行。仍然从count 0开始。Thread A Thread B │ │ ├─ LOAD count - 0 │ │ │ ├─────── context switch ────────────│ │ ├─ LOAD count - 0 │ ├─ ADD 1 │ ├─ STORE count - 1 │ │ │────── context switch ─────────────┤ ├─ ADD 1 │ ├─ STORE count - 1 │线程切换时操作系统会保存 Thread A 的执行上下文包括它已经读到的中间结果。Thread A 恢复执行后仍然会基于之前读到的0继续计算。最终count 1原因是LOAD ADD STORE不是一个不可分割的整体。只要一个执行单元进行到一半时另一个执行单元插进来就可能出现 丢失更新。于是得到第一个问题问题一一个复合操作如何不可分割地完成也就是Atomicity这里先不回答。继续往下看多核又会新增什么问题。5. 从单核走向多核可见性问题如果处理器拥有多个 CPU Core那么两个线程可能真正同时执行Thread A Thread B │ │ ▼ ▼ Core A Core B │ │ ▼ ▼ Cache A Cache B │ │ └──────────────┬───────────────┘ ▼ Memory单核下的count竞态仍然存在。但多核还会带来一个新的问题。假设count 0Core A 和 Core B 都读取过count。那么同一份数据可能同时存在于不同 Cache 中Core A Cache Core B Cache count 0 count 0 Memory count 0现在 Core A 修改countCore A Cache Core B Cache count 1 count 0于是问题来了Core B 手里的旧副本还能不能继续使用也就是说问题二一个 Core 修改数据后其他 Core 什么时候能够观察到新的值即Visibility这里仍然先不回答。继续看第三类问题。6. 多个内存操作之间的顺序又怎么办继续沿用前面的 Counter 例子count 0 ready falseThread A Thread B │ │ ├─ count 1 ├─ 读取 ready └─ ready true └─ 如果为 true读取 count程序员自然会希望如果 Thread B 已经看到ready true那么它也应该看到前面写入的count 1。也就是说我们希望 B 只出现下面两种结果结果一 Thread A Thread B 读取 ready - false 不进入 if 结果二 Thread A Thread B count 1 ready true 读取 ready - true 进入 if 读取 count - 1 打印 1而不是第三种结果Thread A Thread B count 1 这个写入尚未被 B 观察到 ready true 读取 ready - true 进入 if 读取 count - 0 打印 0也就是说当 B 已经读到ready true时如何保证它不能再读到旧的count 0但这里已经不是同一个 count 的多个缓存副本而是两个不同的内存位置count ready以及两个内存操作count 1 ready true之间的关系。于是出现第三个问题问题三多个内存操作允许按照什么顺序被其他 Core 观察也就是Memory Ordering为什么硬件会让这个问题变复杂主要是因为现代 CPU 为了性能会引入各种优化机制。6.1 Store Buffer继续沿用counter。假设count 0Core A 执行LOAD count - 0 ADD 1 - 1 STORE [count], 1其中STORE写入的count 1可能先进入 Store BufferCPUCore A 执行 STORE [count], 1 │ ▼ Store Buffer 暂存 count 1 │ ▼ Memory在 Store Buffer 中的写入对其他 Core 可见之前Core A 已经可以继续执行初始count 0 Core A Core B │ │ ├─ LOAD count - 0 │ ├─ ADD 1 - 1 │ ├─ STORE count - 1 │ │ 写入 Store Buffer │ ├─ 继续执行后面的指令 │ │ ├─ LOAD count - 0 │ │ 仍然读到旧值 └─ count 1 对外可见 │6.2 Out-of-Order Execution现代 CPU 还会为了充分利用执行单元在不破坏必要依赖关系的前提下调整内部执行顺序。只要不改变当前线程自己的执行结果这种调整本身没有问题。问题仍然出在多个 Core 之间。继续沿用前面的 Counter 发布例子Thread A / Core A Thread B / Core B count 1 if ready { ready true print(count) }从源码顺序看A 先写count再写ready。但是在没有额外顺序约束、并且硬件允许这种内存顺序时可能出现初始count 0ready false Thread A / Core A Thread B / Core B │ │ ├─ STORE count 1 │ │ 尚未被 Core B 观察到 │ ├─ STORE ready true │ │ ├─ LOAD ready - true │ └─ LOAD count - 0也就是说A 的源码先写了countB 却先观察到ready true随后仍读到旧的count 0。其他 Core 被允许以什么顺序观察这些内存操作7. 到这里我们实际上遇到了三个问题前面的问题可以归纳成三类问题问题表现硬件需要回答什么Atomicity原子性A、B 都执行count时可能都读到0最后都写回1哪些操作具有原子性Visibility可见性Core A 已经通过count把count写成1Core B 仍可能读到缓存中的0一个 Core 写入后其他 Core 什么时候能够观察到Ordering有序性Core A 先完成count再写入ready trueCore B 却可能先读到ready true随后仍读到count 0哪些操作之间具有顺序关系第一类问题既可能出现在单核线程切换时也可能出现在多核并行执行时。关键不是 CPU Core 的数量而是 Read-Modify-Write 的多个步骤能否被其他执行单元交错。接下来分别看硬件提供了哪些基础能力现代硬件分别提供了什么机制来处理这三个问题8. 硬件如何回答这三个问题8.1 AtomicityAtomic Instruction普通的LOAD ADD STORE是多个步骤。如果希望 Read-Modify-Write 对其他执行单元表现为不可分割的整体就需要硬件提供原子操作例如Compare-And-Swap Exchange Fetch-And-Add这些操作在处理器内部不一定只包含一个微小步骤。“原子”描述的是它们对其他执行单元的可观察结果读取旧值 │ 修改 │ 写入新值 │ └── 对竞争者表现为一个不可分割的原子操作回到count。如果语言把自增实现为硬件支持的原子 Read-Modify-Write那么执行过程可以理解为初始count 0 Thread A Thread B 原子地把 count 从 0 改为 1 原子地把 count 从 1 改为 2 最终count 2A 和 B 谁先执行并不重要。每次原子更新必须基于某个确定的旧值完成因此不会再出现两边都读取0、最后都写入1的情况。8.2 VisibilityCache Coherence多核处理器通过 Cache Coherence Protocol 协调多个 Core 对同一个内存位置的缓存副本。MESI 是最经典的缓存一致性协议之一M - Modified E - Exclusive S - Shared I - Invalid真实处理器中也会使用 MESI 或它的扩展、变体例如MESI MOESI MESIF ...本文不展开状态机的所有转换只看它解决的问题。假设两个 Core 都缓存了包含count的 Cache LineCore A Cache Core B Cache count 0 count 0 Shared Shared如果 Core A 需要修改它count 1硬件需要先协调这个 Cache Line 的所有权和其他副本状态。可以高度简化理解为Core A 要修改 count │ ▼ 取得对应 Cache Line 的写权限 │ ▼ 其他不能继续使用的副本失效 │ ▼ Core A 完成修改Core A 获得写权限后Core B 缓存中的count 0会失效下一次读取count时不能再使用这个旧值。8.3 OrderingMemory Ordering / Fencecount 1 ready true现代 CPU 会使用 Store Buffer 和 Out-of-Order Execution 等机制提高性能。Hardware Memory Model 必须明确哪些内存操作顺序是保证的 哪些重排是允许的 不同 Core 允许观察到哪些结果这就是 Memory Ordering。回到前面的 Counter 发布例子。假设count 1尚未被 B 观察到在允许这种结果的硬件上可能出现Thread A / Core A Thread B / Core B | | -- STORE count 1 | -- STORE ready true | | -- LOAD ready - true | -- LOAD count - 0要阻止这种结果需要用 Fence 约束两侧内存操作的顺序Thread A / Core A Thread B / Core B | | -- STORE count 1 | -- FENCE | -- STORE ready true | | -- LOAD ready - true | -- FENCE | -- LOAD count - 1写入侧的 Fence 保证count 1不能排到ready true之后读取侧的 Fence 保证对count的读取不能排到对ready的读取之前。Fence 不保证 B 一定读到ready true。但当 B 已经读到ready true时随后读取count不能再得到旧值0。9. 总结硬件针对三个并发问题提供了不同的基础能力问题硬件提供的能力Atomicity原子性Atomic Instruction 可以把counter作为一个整体完成其他执行单元不能在中间插入。Visibility可见性Core A 把count修改为1后Core B 再读取count时不能继续使用缓存中的0。Ordering有序性加入 Fence 后Core B 既然读到了ready true再读取count就必须得到1。下一篇回到语言层讨论 Java、Go 和 CPython 的并发语义如何把这些硬件能力转换成程序员可以依赖的规则。本文首发于 ThinkerQAQ 的个人博客由作者本人同步发布。原文可能持续修订最新版本请以个人博客为准。