本文已收录到 AndroidFamily，技能和职场问题，请重视公众号 [彭旭锐] 发问。
前语
大家好，我是小彭。
在上一篇文章里，咱们聊到了 CPU 的三级缓存结构，说到 CPU 缓存就一定会聊到 CPU 的缓存共同性问题。那么，什么是缓存共同性问题，CPU Cache 的读取和写入进程是怎么履行的，MESI 缓存共同性协议又是什么？今天咱们将环绕这些问题打开。
学习路线图：
1. 回顾 CPU 三级缓存结构
因为 CPU 和内存的速度差距太大，为了拉平两者的速度差，现代计算机会在两者之间刺进一块速度比内存更快的高速缓存，CPU 缓存是分级的，有 L1 / L2 / L3 三级缓存。
因为单核 CPU 的功能遇到瓶颈（主频与功耗的对立），芯片厂商开始在 CPU 芯片里集成多个 CPU 中心，每个中心有各自的 L1 / L2 缓存。 其间 L1 / L2 缓存是中心独占的，而 L3 缓存是多中心同享的。
根据局部性原理的运用，CPU Cache 在读取内存数据时，每次不会只读一个字或一个字节，而是一块块地读取，每一小块数据也叫 CPU 缓存行（CPU Cache Line）。 为了标识 Cache 块中的数据是否现已从内存中读取，需求在 Cache 块上添加一个 有用位（Valid bit）。
不管对 Cache 数据检查、读取仍是写入，CPU 都需求知道访问的内存数据映射在 Cache 上的哪个方位，这便是 Cache – 内存地址映射问题，映射计划有直接映射、全相联映射和组相联映射 3 种计划。当缓存块满或许内存块映射的缓存块方位被占用时，就需求运用 替换战略 将旧的 Cache 块换出腾出空闲方位。
Cache - 内存的直接映射计划
根据以上结构，就会存在缓存共同性问题。
2. 什么是 CPU 缓存共同性问题？
CPU 缓存共同性（Cache Coherence）问题指 CPU Cache 与内存的不共同性问题。事实上， 在分析缓存共同性问题时，考虑 L1 / L2 / L3 的多级缓存没有意义， 所以咱们提出缓存共同性笼统模型，只考虑中心独占的缓存。
CPU 三级缓存与笼统模型
在单核 CPU 中，只需求考虑 Cache 与内存的共同性。可是在多核 CPU 中，因为每个中心都有一份独占的 Cache，就会存在一个中心修正数据后，两个中心 Cache 数据不共同的问题。因而，我认为 CPU 的缓存共同性问题应该从 2 个维度理解：
- 纵向：Cache 与内存的共同性问题： 在修正 Cache 数据后，怎么同步回内存？
- 横向：多中心 Cache 的共同性问题： 在一个中心修正 Cache 数据后，怎么同步给其他中心 Cache？
接下来，咱们将环绕这两个问题打开。
3. 纵向：Cache 与内存的共同性问题
3.1 CPU Cache 的读取进程
这一节，咱们先来评论 Cache 的读取进程。事实上，Cache 的读取进程会受到 Cache 的写入战略影响，咱们暂时用相对简单的 “写直达战略” 的读取进程：
-
1、CPU 在访问内存地址时，会先检查该地址的数据是否现已加载到 Cache 中（Valid bit 是否为 1）；
-
2、假如数据在 Cache 中，则直接读取 Cache 块上的字到 CPU 中；
-
3、假如数据不在 Cache 中：
- 3.1 假如 Cache 已装满或许 Cache 块被占用，先履行替换战略，腾出空闲方位；
- 3.2 访问内存地址，并将内存地址所处的整个内存块写入到映射的 Cache 块中；
- 3.3 读取 Cache 块上的字到 CPU 中。
读取进程（以写直达战略）
可是，CPU 不仅会读取 Cache 数据，还会修正 Cache 数据，这便是第 1 个共同性问题 —— 在修正 Cache 数据后，怎么同步回内存？有 2 种写入战略：
3.2 写直达战略（Write-Through）
写直达战略是处理 Cache 与内存共同性最简单直接的方法： 在每次写入操作中，一起修正 Cache 数据和内存数据，始终保持 Cache 数据和内存数据共同：
- 1、假如数据不在 Cache 中，则直接将数据写入内存；
- 2、假如数据现已加载到 Cache 中，则不仅要将数据写入 Cache，还要将数据写入内存。
写直达的长处和缺点都很明显：
- 长处： 每次读取操作便是纯粹的读取，不涉及对内存的写入操作，读取速度更快；
- 缺点： 每次写入操作都需求一起写入 Cache 和写入内存，在写入操作上失去了 CPU 高速缓存的价值，需求花费更多时刻。
写直达战略
3.3 写回战略（Write-Back）
已然写直达战略在每次写入操作都会写内存，那么有没有什么方法可以削减写回内存的次数呢？这便是写回战略：
-
1、写回战略会在每个 Cache 块上添加一个 “脏（Dirty）” 标记位 ，当一个 Cache 被标记为脏时，说明它的数据与内存数据是不共同的；
-
2、在写入操作时，咱们只需求修正 Cache 块并将其标记为脏，而不需求写入内存；
-
3、那么，什么时分才将脏数据写回内存呢？—— 就发生在 Cache 块被替换出去的时分：
- 3.1 在写入操作中，假如方针内存块不在 Cache 中，需求先将内存块数据读取到 Cache 中。假如替换战略换出的旧 Cache 块是脏的，就会触发一次写回内存操作；
- 3.2 在读取操作中，假如方针内存块不在 Cache 中，且替换战略换出的旧 Cache 块是脏的，就会触发一次写回内存操作；
可以看到，写回战略只有当一个 Cache 数据将被替换出去时判别数据的状况，“清（未修正过，数据与内存共同）” 的 Cache 块不需求写回内存，“脏” 的 Cache 块才需求写回内存。这个战略可以削减写回内存的次数，功能会比写直达更高。当然，写回战略在读取的时分，有可能不是纯粹的读取了，因为还可能会触发一次脏 Cache 块的写入。
这里还有一个规划： 在方针内存块不在 Cache 中时，写直达战略会直接写入内存。而写回战略会先把数据读取到 Cache 中再修正 Cache 数据，这似乎有点多余？其实仍是为了削减写回内存的次数。虽然在未命中时会添加一次读取操作，但后续重复的写入都能命中缓存。否则，只需一向不读取数据，写回战略的每次写入操作仍是需求写入内存。
写回战略
通过写直达或写回战略，咱们现已可以处理 “在修正 Cache 数据后，怎么同步回内存” 的问题。接下来，咱们来评论第 2 个缓存共同性问题 —— 在一个中心修正 Cache 数据后，怎么同步给其他中心 Cache？
4. 横向：多中心 Cache 的共同性问题
在单核 CPU 中，咱们通过写直达战略或写回战略保持了Cache 与内存的共同性。可是在多核 CPU 中，因为每个中心都有一份独占的 Cache，就会存在一个中心修正数据后，两个中心 Cache 不共同的问题。
举个比如：
-
1、Core 1 和 Core 2 读取了同一个内存块的数据，在两个 Core 都缓存了一份内存块的副本。此刻，Cache 和内存块是共同的；
-
2、Core 1 履行内存写入操作：
-
2.1 在写直达战略中，新数据会直接写回内存，此刻，Cache 和内存块共同。但因为之前 Core 2 现已读过这块数据，所以 Core 2 缓存的数据仍是旧的。此刻，Core 1 和 Core 2 不共同；
-
2.2 在写回战略中，新数据会延迟写回内存，此刻 Cache 和内存块不共同。不管 Core 2 之前有没有读过这块数据，Core 2 的数据都是旧的。此刻，Core 1 和 Core 2 不共同。
-
-
3、因为 Core 2 无法感知到 Core 1 的写入操作，假如继续运用过期的数据，就会呈现逻辑问题。
多核 Cache 不共同
可以看到：因为两个中心的作业是独立的，在一个中心上的修正行为不会被其它中心感知到，所以不管 CPU 运用写直达战略仍是写回战略，都会呈现缓存不共同问题。 所以，咱们需求一种机制，将多个中心的作业联合起来，共同确保多个中心下的 Cache 共同性，这便是缓存共同性机制。
4.1 写传达 & 业务串行化
缓存共同性机制需求处理的问题便是 2 点：
-
特性 1 – 写传达（Write Propagation）： 每个 CPU 中心的写入操作，需求传达到其他 CPU 中心；
-
特性 2 – 业务串行化（Transaction Serialization）： 各个 CPU 中心一切写入操作的次序，在一切 CPU 中心看起来是共同。
第 1 个特性处理了 “感知” 问题，假如一个中心修正了数据，就需求同步给其它中心，很好理解。但只做到同步还不够，假如各个中心收到的同步信号次序不共同，那终究的同步成果也会不共同。
举个比如：假如 CPU 有 4 个中心，Core 1 将同享数据修正为 1000，随后 Core 2 将同享数据修正为 2000。在写传达下，“修正为 1000” 和 “修正为 2000” 两个业务会同步到 Core 3 和 Core 4。可是，假如没有业务串行化，不同中心收到的业务次序可能是不同的，终究数据仍是不共同。
非业务串行化
4.2 总线嗅探 & 总线裁定
写传达和业务串行化在 CPU 中是怎么完成的呢？—— 此处盛大请出计算机总线系统。
-
写传达 – 总线嗅探： 总线除了能在一个主模块和一个从模块之间传输数据，还支持一个主模块对多个从模块写入数据，这种操作便是播送。要完成写传达，其实便是将一切的读写操作播送到一切 CPU 中心，而其它 CPU 中心时刻监听总线上的播送，再修正本地的数据；
-
业务串行化 – 总线裁定： 总线的独占性要求同一时刻最多只有一个主模块占用总线，天然地会将一切中心对内存的读写操作串行化。假如多个中心一起发起总线业务，此刻总线裁定单元会对竞争做出裁定，未取胜的业务只能等候取胜的业务处理完成后才干履行。
提示： 写传达还有 “根据目录（Directory-base）” 的完成计划。
根据总线嗅探和总线裁定，现代 CPU 逐步形成了各种缓存共同性协议，例如 MESI 协议。
4.3 MESI 协议
MESI 协议其实是 CPU Cache 的有限状况机，一共有 4 个状况（MESI 便是状况的首字母）：
- M（Modified，已修正）： 标明 Cache 块被修正过，但未同步回内存；
- E（Exclusive，独占）： 标明 Cache 块被当时中心独占，而其它中心的同一个 Cache 块会失效；
- S（Shared，同享）： 标明 Cache 块被多个中心持有且都是有用的；
- I（Invalidated，已失效）： 标明 Cache 块的数据是过期的。
在 “独占” 和 “同享” 状况下，Cache 块的数据是 “清” 的，任何读取操作可以直接运用 Cache 数据；
在 “已失效” 和 “已修正” 状况下，Cache 块的数据是 “脏” 的，它们和内存的数据都可能不共同。在读取或写入 “已失效” 数据时，需求先将其它中心 “已修正” 的数据写回内存，再从内存读取；
在 “同享” 和 “已失效” 状况，中心没有取得 Cache 块的独占权（锁）。在修正数据时不能直接修正，而是要先向一切中心播送 RFO（Request For Ownership）恳求 ，将其它中心的 Cache 置为 “已失效”，比及取得回应 ACK 后才算取得 Cache 块的独占权。这个独占权这有点类似于开发言语层面的锁概念，在修正资源之前，需求先获取资源的锁；
在 “已修正” 和 “独占” 状况下，中心现已取得了 Cache 块的独占权（锁）。在修正数据时不需求向总线发送播送，可以减轻总线的通讯压力。
事实上，完整的 MESI 协议更杂乱，但咱们没必要记得这么细。咱们只需求记住最要害的 2 点：
-
要害 1 – 阻挠一起有多个中心修正的同享数据： 当一个 CPU 中心要求修正数据时，会先播送 RFO 恳求取得 Cache 块的一切权，并将其它 CPU 中心中对应的 Cache 块置为已失效状况；
-
要害 2 – 延迟回写： 只有在需求的时分才将数据写回内存，当一个 CPU 中心要求访问已失效状况的 Cache 块时，会先要求其它中心先将数据写回内存，再从内存读取。
提示： MESI 协议在 MSI 的基础上添加了 E（独占）状况，以削减只有一份缓存的写操作造成的总线通讯。
MESI 协议有一个十分 nice 的在线体会网站，你可以对照文章内容，在网站上操作指令区，并调查内存和缓存的数据和状况变化。网站地址：www.scss.tcd.ie/Jeremy.Jone…
MESI 协议在线模拟
4.4 写缓冲区 & 失效行列
MESI 协议确保了 Cache 的共同性，但完全地遵循协议会影响功能。 因而，现代的 CPU 会在添加写缓冲区和失效行列将 MESI 协议的恳求异步化，以进步并行度：
- 写缓冲区（Store Buffer）
因为在写入操作之前，CPU 中心 1 需求先播送 RFO 恳求取得独占权，在其它中心回应 ACK 之前，当时中心只能空等候，这对 CPU 资源是一种糟蹋。因而，现代 CPU 会选用 “写缓冲区” 机制：写入指令放到写缓冲区后并发送 RFO 恳求后，CPU 就可以去履行其它任务，等收到 ACK 后再将写入操作写到 Cache 上。
- 失效行列（Invalidation Queue）
因为其他中心在收到 RFO 恳求时，需求及时回应 ACK。但假如中心很忙不能及时回复，就会造成发送 RFO 恳求的中心在等候 ACK。因而，现代 CPU 会选用 “失效行列” 机制：先把其它中心发过来的 RFO 恳求放到失效行列，然后直接回来 ACK，等当时中心处理完任务后再去处理失效行列中的失效恳求。
写缓冲区 & 失效行列
事实上，写缓冲区和失效行列破坏了 Cache 的共同性。 举个比如：初始状况变量 a 和变量 b 都是 0，现在 Core1 和 Core2 别离履行这两段指令，终究 x 和 y 的成果是什么？
Core1 指令
a = 1; // A1
x = b; // A2
Core2 指令
b = 2; // B1
y = a; // B2
咱们知道在未同步的情况下，这段程序可能会有多种履行次序。不管怎么履行，只需 2 号指令是在 1 号指令后履行的，至少 x 或 y 至少一个有值。可是在写缓冲区和失效行列的影响下，程序还有以意料之外的方法履行：
| 履行次序（先不考虑 CPU 超前流水线控制） | 成果 |
|---|---|
| A1 → A2 → B1 → B2 | x = 0, y = 1 |
| A1 → B1 → A1 → B2 | x = 2, y = 1 |
| B1 → B2 → A1 → A2 | x = 1, y = 0 |
| B1 → A1 → B2 → A2 | x = 2, y = 1 |
| A2 → B1 → B2 → A1（A1 与 A2 重排） | x = 0, y = 0 |
| Core2 也会呈现相同的情况，不再赘述 | x = 0, y = 0 |
上图。
写缓冲区造成指令重排
可以看到：从内存的视角看，直到 Core1 履行 A3 来改写写缓冲区，写操作 A1 才算真正履行了。虽然 Core 的履行次序是 A1 → A2 → B1 → B2，但内存看到的次序却是 A2 → B1 → B2 → A1，变量 a 写入没有同步给对变量 a 的读取，Cache 的共同性被破坏了。
5. 总结
-
1、在 CPU Cache 的三级缓存中，会存在 2 个缓存共同性问题：
- 纵向 – Cache 与内存的共同性问题： 在修正 Cache 数据后，怎么同步回内存？
- 横向 – 多中心 Cache 的共同性问题： 在一个中心修正 Cache 数据后，怎么同步给其他中心 Cache？
-
2、Cache 与内存的共同性问题有 2 个战略：
- 写直达战略： 始终保持 Cache 数据和内存数据共同，在每次写入操作中都会写入内存；
- 写回战略： 只有在脏 Cache 块被替换出去的时分写回内存，削减写回内存的次数；
-
3、多中心 Cache 共同性问题需求满意 2 点特性：
- 写传达（总线嗅探）： 每个 CPU 中心的写入操作，需求传达到其他 CPU 中心；
- 业务串行化（总线裁定）： 各个 CPU 中心一切写入操作的次序，在一切 CPU 中心看起来是共同。
-
4、MESI 协议可以满意以上 2 点特性，通过 “已修正、独占、同享、已失效” 4 个状况完成了 CPU Cache 的共同性；
-
5、现代 CPU 为了进步并行度，会在添加 写缓冲区 & 失效行列 将 MESI 协议的恳求异步化， 从内存的视角看便是指令重排，破坏了 CPU Cache 的共同性。
今天，咱们主要评论了 CPU 的缓存共同性问题与对应的缓存共同性协议。这里有一个问题：已然 CPU 现已完成了 MESI 协议，现已在硬件层面完成了写传达和业务串行化，为什么 Java 言语层面还需求定义 volatile 要害字呢？岂不是多此一举？
你可能会说因为写缓冲区和失效行列破坏了 Cache 共同性。好，那不考虑这个要素的话，还需求定义 volatile 要害字吗？这个问题咱们在 下一篇文章 打开评论，请重视。
参考资料
- 浅显易懂计算机组成原理（第 37、38、39 讲） —— 徐文浩 著，极客时刻 出品
- 深化理解 Java 虚拟机（第 5 部分） —— 周志明 著
- Java 并发编程的艺术（第 1、2、3 章） —— 方腾飞 魏鹏 程晓明 著
- 计算机组成原理教程（第 7 章） —— 尹艳辉 王海文 邢军 著
- 10 张图打开 CPU 缓存共同性的大门 —— 小林 Coding 著
- CPU有缓存共同性协议(MESI)，为何还需求 volatile —— 一角钱技能 著
- Cache Miss – What It Is and How to Reduce It —— Linda D. 著
- CPU cache —— Wikipedia
- CPU caches —— LWN.net
- Cache coherence —— Wikipedia
- Directory-based cache coherence —— Wikipedia
- MESI protocol —— Wikipedia
