CPU Cache 与 Memory Barrier

基础知识

本篇为 《Memory Barriers: a Hardware View for Software Hackers》 的阅读笔记。

CPU 的一般架构

CPU Cache 的标准做法是使用多级 Cache，一级 Cache 很小，靠近 CPU，访问速率为 1 cycle，二级更大，访问耗时也更长，大概是十几个 cycle。高端 CPU 通常有三级甚至四级 Cache，CPU Cache 和主存之间通过大小一定的数据块来交互，这个块被称为“cache line”，一般大小为 2 的幂次方（16~256 bytes）。

image-20200914114449583

不同 CPU 制造商、甚至同一 CPU 中的不同 level 的 Cache，使用的 缓存失效算法 都可能不太一样，比如 Intel 简略介绍过的一种在 Ivy Bridge 芯片中使用的算法：

image-20200914154025157

这里不去深入下去，可以看到这种算法好像引入了某种分代策略。

考虑效率，CPU 一般不会使用标准的 LRU 算法，而是使用一些伪 LRU 算法（PLRU），CPU Cache 的淘汰算法也是在不断进化的。

CPU 读取 Cache 通常会经历以下两个过程：

  • 当 CPU 第一次访问某个数据项时，该项在 CPU Cache 中是没有的，这叫做一次 “cache miss”（更准确的说，是一种 “startup” 或 “warmup” 类型的 “cache miss”），意味着 CPU 需要等待（或者进入 “stalled” 状态）直到几百个 cycle 后数据从 Memory 中加载到 Cache 中去，这样后续 CPU 对这个数据的访问也能命中 Cache 了。

  • 一段时间后，CPU Cache 满了，接下来的 “cache miss” 会导致一些项会（按某种优先顺序）从 Cache 中被移除来腾出空间，这种叫做 “capacity miss”。尽管如此，即使 Cache 还没满，大多数的 Cache 也支持强制移除某些旧的项来给新项提供空间，这是由于大的 Cache 一般实现是硬件哈希表，而非链表（算法实现问题）。

image-20200914144830547

图中的 Cache 共两路，每路 16 个大小为 256 bytes 的 cache line，一共 8 MBytes，稍大，便于十六进制运算。在硬件领域，这是一种 双向组关联缓存（two-way set-associative cache），类似于具有 16 个 bucket 的软件哈希表，其中每个 bucket 的链表限制为最多两个元素。缓存的大小（例中为 32 个）和关联性（例中为 2 路）统称为 Cache 的“几何配置”。由于 Cache 是在硬件中实现的，因此哈希函数非常简单：从内存地址中提取 4 bits 即可。

“如何读”现在比较清晰了，那 CPU 写缓存行时会发生什么呢？

要让某个数据在所有 CPU 中都保持一致，在某个 CPU 写该数据之前，必须先使其他 CPU 的缓存中的该值被删除或“无效化”，之后 CPU 才可以安全地修改此数据。如果数据已存在于此 CPU 的缓存中，但为 read-only，则称此为 “write miss”。之后，如果其他 CPU 尝试访问数据项，将发生 “cache miss”，称为 “communication miss”（因为它通常发生于 CPU 间通信的场景）。

这里的“缓存无效化”等的实现方式，依靠的就是 缓存一致性协议。

缓存一致性协议

以包含有四种状态的 MESI 缓存一致性协议 为例。

MESI协议 是一个基于失效的缓存一致性协议，是支持 write-back 型缓存最常用的协议。与 write-through 型缓存相比，write-back 型缓存支持 dirty（Cache 与主存不同步）。MESI 协议要求在 cache miss 且数据在另一个 Cache 中时，允许缓存到缓存的数据复制，这减少了主存的事务数量，极大改善了性能。

MESI 状态

MESI 代表缓存行的 “已修改”（modified）、“独有”（exclusive）、“共享”（shared）和 “无效”（invalid）四种状态，它使用了缓存行中的两个 bit 来存储。

Modified

Modified 状态的 cache line 刚被其对应的 CPU 执行了存储操作，且其内容在任何其他 CPU 的 Local Cache 中都不存在，此时 cache line 是脏的（dirty），与主存的值不同，如果别的 CPU 要读主存这块数据，该缓存行必须回写到主存，状态变为 shard。可以说这个 cache line 归该 CPU 独占，此 cache line 保存了数据的最新唯一副本，所以该 CPU 会对 cache line 的回写内存或转交其他 CPU 负责到底，而且保证在这之后才会使用此 cache line 保存其他数据。

Exclusive

Exclusive 与 Modified 非常相似，唯一的区别是 此时 cache line 尚未被相应的 CPU 修改，这意味着 主存中对应的数据是最新的（和 cache line 中的一致）。但是，由于 CPU 可以随时修改该 cache line 而无需咨询其他 CPU，因此仍可以说这个 cache line 归该 CPU 独占。而由于主存中的值是最新的，因此该缓存可以丢弃此数据而无需将其回写主存或转交给其他 CPU。

cache line 只在当前 Cache 中，但是他是干净的（clean），即与主存保持一致。当别的 Cache 读取它时，状态变为 Shared，当前 CPU 写数据时，cache line 变为 Modified。

Shared

Shared 状态的 cache line 可能会存在于其他至少一个 CPU 的 Cache 中，因此，如果未先咨询其他 CPU，则不允许该 CPU 修改该 cache line。与 exclusive 一样，由于主存中的值是最新的，因此该 Cache 可以丢弃此数据而无需将其回写主存或交给其他 CPU。

Invalid

处于 Invalid 状态的 cache line 为空（不保存任何数据），当新数据进入 Cache 时可能会放到 Invalid 的 cache line 中（此为首选方式，因为如果要替换其它 cache line，则可能导致代价高昂的 cache miss）。

由于所有 CPU 必须维护 cache line 数据的一致性视图，因此缓存一致性协议中的“消息”可以协调 cache line 在系统中的移动。

MESI 协议消息

如上文所述，我们在很多时候都需要依赖 CPU 之间的通信，假设总线只有一条，那么将会有以下几种类型的消息：

  • Read

    将被读取的 cache line 的物理地址。

  • Read Response

    包含先前 Read 消息所请求的数据，此消息可能由主存或其他 Cache 提供，比如其中一个 Cache 具有处于 modified 状态的所需数据，那么该 Cache 必须提供 Read Response 消息（由于 Modified 状态是独有的脏写数据）。

  • Invalidate

    包含将被无效化的 cache line 物理地址，所有其他 Cache 必须删除对应的数据。

  • Invalidate Acknowledge

    删除 Invalidate 消息对应数据后给出的响应。

  • Read Invalidate

    包含要读取的 cache line 的物理地址，同时要求其他 Cache 删除这一数据，是 Read 和 Invalidate 的组合。此消息对应一个 Read Response 和一批 Invalidate Acknowledge。

  • Writeback

    包含要回写内存的数据和地址（因为总线窥探器的存在，这个操作可能还会被其他 CPU 的 Cache 窥探（snooping）到）。该消息允许 Cache 根据需要删除 Modified 状态的 cache line，以便为其他数据腾出空间。

有意思的是，基于共享内存的多核系统其底层是基于消息传递的计算机系统。这也就意味着由多个 SMP 机器组成的共享内存的集群系统实际上在 两个不同的 level 上使用了消息传递机制，一个是 SMP 内部的 message passing，另外一个是 SMP 机器之间的。

MESI 状态机

image-20200918144417127

a) cache line 回写主存中，但是 CPU 将其保留在 Cache 中，并进一步保留修改它的权利，对应一条 Writeback 消息。

b) CPU 写其已具有独占访问权的 cache line，这里没有任何消息。

c) CPU 收到（其它 CPU 发出的）已修改的 cache line 的 Read Invalidate 消息，它必须使自己 Cache 中对应的数据无效，然后以 Read Response 和 Invalidate Acknowledge 消息进行响应，二者均将数据发送到发出请求的 CPU，并指示其不再具有本地拷贝。

d) CPU 对它 Cache 中不存在的数据项执行原子的 “read-modify-write” 操作，它发送 Read Invalidate 消息（获取数据的独占权），并通过 Read Response 接收数据，收到全部的 Invalidate Acknowledge 响应（其它 CPU 没有 local copy 了）后才成功完成操作。

e) CPU 对先前在其 Cache 中为只读的数据执行 “read-modify-write” 操作，它必须发送 Invalidate 消息获取数据的独占权，等待收到所有 Invalidate Acknowledge 后，操作完成。

f) 本 CPU 独占数据期间，其他一些 CPU 发起对 cache line 的 Read 请求，此时本 CPU 使用 Read Response 回应本 CPU cache line 中的内容，并失去该 cache line 的独占权（可能会包含回写内存的动作）。

g) 与 (f) 类似，只是 Exclusive 状态的数据是 clean 的，所以不会包含回写内存的动作。

h) 本 CPU 意识到它马上要写这个 cache line，并且会因此发出 Invalidate 消息，在收到所有 Invalidate Acknowledge 后转换完成。或者还有一种办法，就是其他所有 CPU 都通过 Writeback 消息从 Cache 中删除了此 cache line（应该是为其他数据腾出空间而这样做），之后该 CPU 自动获取数据独占权，成为最后一个对数据进行缓存的 CPU。

i) 其他一些 CPU 对仅保留在本 CPU 中的某 cache line 数据执行原子性的 “read-modify-write” 操作，因此本 CPU 会使数据无效化。其它 CPU 会发送 Read Invalidate 消息，本 CPU 响应 Read Response 和 Invalidate Acknowledge 消息。

j) 本 CPU 想 write 不在其 Cache 中的数据，它发送 Read Invalidate 消息，在收到 Read Response 和所有 Invalidate Acknowledge 消息后，read 完成，之后的 write 会导致 cache line 通过 (b) 的转换使其状态由 Exclusive 改为 Modified。

k) 本 CPU 想 read 不在其 Cache 中的数据，它发送 Read 请求，在接收到相应的 Read Response 后操作完成。

l) 其他一些 CPU 有存储此 cache line，cache line 状态为 Shared，因此其状态为 read-only。如果某个 CPU 要 write，则会发送 Invalidate 消息，本 CPU（以及其它拥有此 copy 的 CPU）会以 Invalidate Acknowledge 消息进行响应。

MESI 协议示例

最开始，数据保存在内存中，地址为 0，随后，该数据会穿行于四个 CPU 的 Local Cache 中。为方便起见，我们让 CPU Local Cache 仅拥有一个 cache line。

如下图所示：

image-20200921142402350

第一列显示了操作顺序，第二列显示了执行操作的 CPU，第三列显示了正在执行的操作，接下来的四列分别显示了每个 CPU 的 cache line 状态（内存地址/MESI 状态），最后一列描述了主存中（对应 cache line 地址为 0 和 8 的数据）的数据状态：Ⅴ表示最新（和 Cache 一致），Ⅰ表示不是最新（最新的在 Cache 中）。

  1. 最初，各 CPU 的 cache line 都是 Invalid 状态，最新数据都在主存中。
  2. 当 CPU-0 将数据加载到地址 0，cache line 进入 Shared 状态，主存中数据仍然有效。
  3. CPU-3 将数据加载到地址 0，此时两个 CPU 的 cache line 均处于 Shared 状态，并且在主存中仍然有效。
  4. CPU-0 加载了其他的一些高速缓存行（地址 8），该行通过无效化操作将地址 0 的数据清除，替换为地址 8 的数据。
  5. CPU-2 加载地址 0 的数据，并且知道自己需要进行 write 操作，因此它使用 Read Invalidate 消息来获取数据的独占权，从而让 CPU-3 的中的 cache line 无效化（尽管主存中的值仍然是最新的）。
  6. CPU-2 进行其预期的 write 操作，cache line 状态更改为 Modified，此时内存中的地址 0 的数据已过期（任何其他 CPU 发起对地址 0 的读操作都不能直接从主存中读取了，而是通过 snoop 的方式从 CPU-2 的 Local Cache 中获取）。
  7. CPU-1 执行原子递增操作，使用 Read Invalidate 来嗅探来自 CPU-2 Local Cache 中的数据，并使数据无效化以便独占数据，之后 cache line 处于 Modified 状态（此时主存中数据依然是过期的）。
  8. 最后，CPU-1 读取地址 8 的数据，Modified 状态的 0 地址数据需要通过发送 Writeback 消息回写到主存。由于回写操作，主存中的值又变成了有效的最新数据了。

存储数据导致了不必要的停顿

尽管上文中的 CPU 缓存结构为数据项的重复读取和写入提供了良好的性能，但其 第一次 写入给定缓存行的性能却相当差。考虑下图这样，CPU-0 写数据，数据存在于 CPU-1 中，那么 CPU-0 需要通过 Invalidate 消息使 CPU-1 的 cache line 无效，这是个漫长的等待过程：

image-20200921153724047

从一个 CPU 的 Cache 转移到另一个 CPU 的 Cache 所需的时间通常比执行一条简单的寄存器到寄存器指令所需的时间长几个数量级之久。

但其实没必要等这么久，毕竟，不管 CPU-1 返回的数据是什么，CPU-0 都会无条件地覆盖它。

Store Buffers

有一种可以防止 CPU 进入这样的等待状态的方法，那就是在 CPU 和 Cache 之间增加 Store Buffer 这个硬件模块，这些 store buffers 为每个 CPU 私有：

image-20200921154011265

CPU-0 可以简单地将它的写入记录放入其 store buffer 中，无需等待其它 CPU 的 Invalidate Acknowledge 即可继续往下执行。当所有 Invalidate Acknowledge 消息到达 CPU-0 后，数据就可以从 store buffer 移到 cache line 中去了。

个人理解就是个临时存储空间，用于存储未来即将落到 Cache 中的“写”动作。

store buffer 增加了 CPU 的连续写性能，但也带来了两个复杂的问题。

Store Forwarding

第一个问题，它违反了自我一致性。

考虑以下代码：

image-20200921161923328

假设变量 a、b 初始值均为零，并且变量 a 的 cache line 最初由 CPU-1 拥有，b 的由 CPU-0 拥有。

正常来说，assert 会成功，但如果使用上文所示的看似非常简单的 Store Buffer 结构，结果可能会出乎意料，因为该结构可能会产生以下事件序列：

  1. CPU-0 执行 a = 1；
  2. CPU-0 在 Cache 中查找 a，发现没有；
  3. CPU-0 发送 Read Invalidate 消息以获得包含 a 数据的缓存行的独占权；
  4. CPU-0 将写记录放入其 store buffer 中；
  5. CPU-1 接收 Read Invalidate 消息，发送 cache line 给 CPU-0，并将其从 Cache 中删除；
  6. CPU-0 开始执行 b = a + 1；
  7. CPU-0 从 CPU-1 接收 cache line（Read Response 消息），其中 a 的值仍为 0；
  8. CPU-0 从 Cache 中加载 a（等于 0）；
  9. 由于接收到 Invalidate Acknowledge 消息，CPU-0 将其 store buffer 移到 cache line 中，并将 Cache 中的 a 值设为 1；
  10. CPU-0 将加载到的 a（为 0）加 1，并将其存储到包含 b 的 cache line 中（假定它已由 CPU-0 独占），b 变为 1；
  11. CPU-0 执行 assert(b == 2)，失败。

问题在哪儿呢？

这个问题是由于我们有两个 a 的副本所导致的，其中，一个在 Cache 中，另一个在 store buffer 中，这违反了一个非常重要的原则，即每个 CPU 都应该看的到自己的操作。

Store Forwarding 使我们 CPU 在执行 读操作的时候都会引用 store buffer 中的值，而不是直接通过 Cache，从而解决了这一问题，如图所示：

image-20200921164634658

个人理解就是 store buffer 中的值优先。

这样一来，我们在例中第 8 步就能从 store buffer 中正确地加载到 a 的值 1，从而使 b 最终为 2。

What cache invalidation algorithms are used in actual CPU caches?

Cache prefetching

Cache replacement policies

Store Buffers 和 Memory Barriers

另一个问题是，store buffer 违反了内存的全局顺序性。

考虑以下代码：

image-20200921170144489

假设 CPU-0 执行 foo()，CPU-1 执行 bar()，进一步假设包含 a 的 cache line 仅在 CPU-1 的 Cache 中，并且包含 b 的 cache line 归 CPU-0 所独占。

操作顺序如下：

  1. CPU-0 执行 a = 1，cache line 不在 CPU-0 的 Cache 中，因此 CPU-0 将 a 的新值放入其 store buffer 中，并发送 Read Invalidate 消息；
  2. CPU-1 执行 while(b == 0) continue，但是包含 b 的 cache line 不在其 Cache 中，因此它发送 Read 消息；
  3. CPU-0 执行 b = 1，此时它已独占此 cache line（Modified 或 Exclusive 状态），因此它直接将 b 的新值存储在其 cache line 中；
  4. CPU-0 接收到 Read 消息，并将包含当前更新的 b 值发送到 CPU-1，同时在其自己的 Cache 中将该行标记为 Shared；
  5. CPU-1 接收包含 b 的 cache line，并将其放入 Cache；
  6. CPU-1 现在可以完成 while(b==0) continue 的执行，并且由于它发现 b 的值为 1，因此继续执行下一条语句；
  7. CPU-1 执行 assert(a == 1)，并且由于 CPU-1 使用 a 的旧值工作，因此该 assert 失败；
  8. CPU-1 接收 Read Invalidate 消息，将包含 a 的 cache line 传输到 CPU-0，并从其自身的 Cache 中使该 cache line 无效；
  9. CPU-0 接收到包含 a 的 cache line，将 a 更新为 1，但已经晚了。

遇到这样的问题，CPU 设计者也帮不上什么忙，毕竟 CPU 并不知道哪些变量有相关性，以及他们是如何相关的。不过 CPU 设计者可以间接提供一些工具让软件工程师来控制这些相关性，这些工具就是 memory-barrier 指令。

要想程序正常运行，必须增加一些 memory barrier 的操作，具体如下：

image-20200921173040790

内存屏障 smp_mb() 将导致 CPU 在将每个后续的写应用于其变量的 cache line 之前先刷新其 store buffer。CPU 可以简单地等到 store buffer 变为空，或者直到 store buffer 中之前的所有记录都成功应用，才使用 store buffer 来保存后续的写操作。

使用后一种方法，操作顺序可能如下：

  1. CPU-0 执行 a = 1，cache line 不在 CPU-0 的 Cache 中，因此 CPU-0 将 a 的新值放入其 store buffer 中，并发送 Read Invalidate 消息；
  2. CPU-1 执行 while(b == 0) continue，但是包含 b 的 cache line 不在其 Cache 中，因此它发送 Read 消息；
  3. CPU-0 执行 smp_mb()，并标记所有当前的 store buffer 记录（即 a = 1）。
  4. CPU-0 执行 b = 1，由于此时它已独占此 cache line（Modified 或 Exclusive 状态），但 store buffer 中有一个已被标记的记录，因此，这里不会将 b 的新值存储在 cache line 中，而是放置在 store buffer 中（但未被标记）；
  5. CPU-0 接收到 Read 消息，并将包含 b 初始值 的 cache line 发送到 CPU-1，同时在其自己的 Cache 中将该行标记为 Shared；
  6. CPU-1 接收包含 b 的 cache line，并将其放入自身的 Cache 中；
  7. CPU-1 现在可以读 b 的值，但是由于发现 b 的值仍为 0，因此它会重复 while 语句，b 的新值安全地隐藏在 CPU-0 的 store buffer 中；
  8. CPU-1 接收 Read Invalidate 消息，将包含 a 的 cache line 传输到 CPU-0，并从其自身的 Cache 中使该 cache line 无效化；
  9. CPU-0 接收到包含 a 的高速缓存行，并将 store buffer 中的更改应用到 Cache，将该行置于 Modified 状态；
  10. 包含 a 的 cache line 是唯一被 smp_mb() 标记的记录，因此 CPU-0 也可以存储 b 的新值，除非包含 b 的 cache line 处于 Shared 状态；
  11. 包含 b 的 cache line 的确处于 Shared 状态，因此，CPU-0 将 Invalidate 消息发送给 CPU-1；
  12. CPU-1 接收到 Invalidate 消息，从其 Cache 中包含 b 的 cache line 无效化，然后向 CPU-0 发送 Invalidate Acknowledge 消息；
  13. CPU-1 执行 while(b == 0) continue，但是包含 b 的 cache line 不在其 Cache 中，因此，它将发送 Read 消息到 CPU-0；
  14. CPU-0 接收到 Invalidate Acknowledge 消息，并将包含 b 的 cache line 置于 Exclusive 状态，现在，CPU-0 将 b 的新值存储到 cache line 中；
  15. CPU-0 接收到 Read 消息，并将包含 b 的新值的 cache line 发送到 CPU-1，它还将自己的 cache line 标为 Shared；
  16. CPU-1 接收包含 b 的高速缓存行，并将其放入其 Cache 中；
  17. CPU-1 现在可以读 b 的值了，由于发现 b 的值为 1，因此它退出 while 循环并继续执行下一条语句；
  18. CPU-1 执行 assert(a == 1)，但是包含 a 的 cache line 不再存在于其 Cache 中，一旦从 CPU-0 获得该缓存，它将使用 a 的最新值，因此 assert 通过。

由此可见，即使是看上去很简单的“加载 a 的值”这一操作，都可能涉及许多复杂的步骤。

存储数据的顺序导致了不必要的停顿

但是，每个 store buffer 都必须相对较小，以正常速度执行 store 操作的 CPU 会很容易将 store buffer 填满（假设所有 store buffer 均导致 cache miss），此时，CPU 必须等所有 Invalidate Acknowledge 都收到，才能将 store buffer 写入 cache line 以让出 store buffer 的空间，然后继续执行。这在有 Memory Barrier 之后也是一样，因为一旦 store buffer 中有被标记的记录，无论是否 cache miss，操作都需要进 store buffer 而非 cache line。

为缓解这一情况，又出现了 invalidate queues 这种设计。

Invalidate Queues

Invalidate Acknowledge 花费很长时间的其中一个原因是，“使 cache line 无效化”的操作没那么快，特别是 Cache 繁忙的时候（比如 CPU 正在密集地读写数据，则会存在竞争）。另外，如果短时间来了大量 Invalidate 消息，CPU 很可能出现延迟，导致其他 CPU 停顿。

但是，CPU 在发送 Invalidate Acknowledge 之前实际上 并不需要马上使 cache line 无效化，所以，我们可以把 Invalidate 消息放进一个队列慢慢消费，然后马上回复 Invalidate Acknowledge，但在 CPU 发送相关 cache line 之前，对应的 Invalidate 消息必须消费完。

Invalidate Queues 和 Invalidate Acknowledge

加入 Invalidate Queues 后的结构长这样：

image-20200923112928492

CPU 可以在 Invalidate 消息入队后立即进行 Invalidate Acknowledge 确认，不必等 cache line 真正无效化。

当然，Invalidate 消息的发送方在发消息前，必须参考 invalidate queue 中的内容，如果相应的 cache line 的条目位于队列中，则 CPU 无法立即发送 Invalidate 消息，需要等待消费完成。

实际上，“放到 invalidate queue”意味着 CPU 承诺在发送任何相关 cache line 的 MESI 消息之前，会先处理 queue 中消息。只要对应的数据结构竞态不严重，性能就还行没啥问题。但是，invalidate queues 也带来了其它问题，比如内存乱序。

Invalidate Queues 和 Memory Barriers

让我们假设 CPU 将 Invalidate 消息排队，但立即作出 Invalidate Acknowledge 响应，虽然可以减少无效化 Cache 的延迟，但是可能破坏 Memory Barriers。

如下所示：

image-20200923114435879

假设 a 和 b 的初始值为 0， a 为只读复制（即 MESI 的 Shared）状态，b 为 CPU-0 独占（MESI Exclusive 或 Modified）状态，CPU-0 执行 foo()，而 CPU-1 执行功能 bar()，思考以下时序：

  1. CPU-0 执行 a = 1，由于包含 a 的 cache line 为 Shared，因此 CPU-0 将 a 的新值放入其 store buffer 中并发送 Invalidate 消息，以便从 CPU-1 的缓存中清除相应的 cache line；
  2. CPU-1 执行 while(b == 0) continue，但是包含 b 的高速 cache line 不在其 Cache 中，因此，它发送 Read 消息；
  3. CPU-1 收到 CPU-0 的 Invalidate 消息，将其放入 invalidate queue，然后立即作出 Invalidate Acknowledge 响应；
  4. CPU-0 收到来自 CPU-1 的 Invalidate Acknowledge 响应，正常通过 smp_mb()，将 a 的值从其 store buffer 移到其 cache line；
  5. CPU-0 执行 b = 1，由于它已经独占此 cache line（Modified 或 Exclusive），因此 CPU-0 直接将 b 的新值存储在其 cache line 中；
  6. CPU-0 接收到 Read 消息，并将包含更新后当前 b 的值的 cache line 发送到 CPU-1 ，同时将该 cache line 标记为 Shared；
  7. CPU-1 接收包含 b 的高速 cache line ，并将其放入 Cache 中；
  8. 现在，由于发现 b 的值为 1，CPU-1 完成 while(b==0) continue，继续执行下一条语句；
  9. CPU-1 执行 assert(a == 1)，并且由于 a 的旧值仍在 CPU-1 的 Cache 中，因此失败；
  10. assert 失败后，CPU-1 才处理到排队的 Invalidate 消息，并从其自身的 Cache 中使包含 a 的 cache line 无效（为时已晚）。

可以看到，由于 Invalidate 消息的入队，导致 CPU-1 没有及时使 a 的 cache line 无效化并发出 Read 消息，从而导致问题。

如果 Invalidate Queues 会导致 Memory Barrier 失效，那么加速 Invalidate Acknowledge 响应显然没有多大意义。但我们可以使 Memory Barrier 指令与 Invalidate Queues 进行交互，当 CPU 执行到 Memory Barrier 时，标记当前在其 invalidate queue 中的所有条目，并强制所有后续的 load 进行等待，直到将所有标记的条目落到 Cache。因此，我们可以向 bar() 方法添加一个 Memory Barrier：

image-20200923143927038

这样一来，步骤变成：

  1. CPU-0 执行 a = 1，由于包含 a 的 cache line 为 Shared，因此 CPU-0 将 a 的新值放入其 store buffer 中并发送 Invalidate 消息，以便从 CPU-1 的缓存中清除相应的 cache line；
  2. CPU-1 执行 while(b == 0) continue，但是包含 b 的高速 cache line 不在其 Cache 中，因此，它发送 Read 消息；
  3. CPU-1 收到 CPU-0 的 Invalidate 消息，将其放入 invalidate queue，然后立即作出 Invalidate Acknowledge 响应；
  4. CPU-0 收到来自 CPU-1 的 Invalidate Acknowledge 响应，正常通过 smp_mb()，将 a 的值从其 store buffer 移到其 cache line；
  5. CPU-0 执行 b = 1，由于它已经独占此 cache line（Modified 或 Exclusive），因此 CPU-0 直接将 b 的新值存储在其 cache line 中；
  6. CPU-0 接收到 Read 消息，并将包含更新后当前 b 的值的 cache line 发送到 CPU-1 ，同时将该 cache line 标记为 Shared；
  7. CPU-1 接收包含 b 的高速 cache line ，并将其放入 Cache 中；
  8. 现在，由于发现 b 的值为 1，CPU-1 完成 while(b==0) continue，继续执行下一条语句 smp_mb()；
  9. 由于 Memory Barrier 的存在，CPU-1 必须 等所有 invalidate queue 中的消息都处理完才能继续执行；
  10. CPU-1 处理 invalidate queue 中对 a 的 Invalidate 消息；
  11. CPU-1 执行 assert(a == 1)，并且由于 a 已无效，因此 CPU-1 发送 Read 消息；
  12. CPU-0 响应 a 的 Read 消息；
  13. CPU-1 收到包含 a 的 cache line，assert 不再 fail。

读内存屏障和写内存屏障

上文例中，我们使用了 Memory Barrier 来标记 Invalidate Queues 和 Store Buffer 中的条目，但是在示例代码中，foo() 没必要对 invalidate queue 做任何事情，而 bar() 同样没有理由对 store buffer 做任何事。

因此，许多类型的 CPU 架构都提供了较弱的内存屏障指令，这些指令只能执行这两个语义中的一个。简单地说，“read memory barrier”仅标记 invalidate queue，而“write memory barrier”仅标记 store buffer，而“full memory barrier”则同时标记两者。

这样做的结果是，read memory barrier 仅对 CPU 的读进行排序，因此，read memory barrier 之前的所有读操作看起来都发生在 read memory barrier 之后的所有读操作之前。类似地，write memory barrier 仅作用在 CPU 的写操作上，从而使 write memory barrier 之前的所有写操作看起来都发生在 write memory barrier 之后的所有写操作之前。而 full memory barrier 使读写都具有顺序性，但仅发生在执行 memory barrier 的 CPU 上。

如果我们改成使用更细粒度的 read/write memory barrier，代码可能如下：

image-20200923150610936

一些计算机拥有更多的 memory barrier 特性，但是懂得这些基础会帮助我们进一步了解这些扩展特性。

本节之后，论文进行了一些 Example 的展示以及对特殊架构 CPU 的指导，这里不再深入。