ENDIX-C-内存屏障

是什么原因，让疯狂的 CPU 设计者将内存屏障强加给可怜的 SMP 软件设计者？

简而言之，这是由于重排内存引用可以达到更好的性能。因此，在某些情况下，如在同步原语中，正确的操作结果依赖于按序的内存引用，这就需要内存屏障以强制保证内存顺序。

对于这个问题，要得到更详细的回答，需要很好理解 CPU 缓存是如何工作的，特别是要使缓存工作的更好，我们需要什么东西。

缓存结构

现代 CPU 的速度比现代内存系统的速度快的多。2006 年的 CPU 可以在的每纳秒内执行 10 条指令。但是需要多个 10ns 才能从物理内存中读取一条数据。它们的速度差异(超过两个数量级)已经导致在现代 CPU 中出现了数兆级别的缓存。这些缓存与 CPU 相关联，如果 C.1 中所示，典型的，可以在几个时钟周期内被访问。

CPU 缓存和内存之间的数据流是固定长度的块，称为“缓存行”，其大小通常是 2 的 N 次方。范围从 16 到 256 字节不等。当一个特定的数据项初次被 CPU 访问时，它在缓存中还不存在，这被称为“缓存缺失”(或者更精确的称为“首次缓存缺失”或者“运行时缓存缺失”)。“缓存缺失”意味着从物理内存中读取数据时，CPU 必须等待(或处于“停顿”状态)数百个 CPU 周期。但是，数据项被装载入 CPU 缓存，因此后续的访问将在缓存中找到，于是 CPU 可以全速运行。

经过一段时间后，CPU 的缓存被填满，后续的缓存缺失很可能需要换出缓存中现有的数据，以便为最近的访问项腾出统建。这种“缓存缺失”被称为“容量缺失”，因为它是由于缓存容量限制而造成的。但是，即便此时缓存还没有被填满，大量缓存也可能由于一个新数据被换出。这是由于大容量缓存是通过硬件哈希表来实现的，这样哈希表有固定长度的哈希桶(或者叫 “sets”，CPU 设计者是这样称呼的)，如图 C.2。

该缓存有 16 个 sets 和两条“路”，共 32 个缓存行，每个节点包含一个 256 字节的“缓存行”，它是一个 256 字节对齐的内存块。对于大容量缓存来说，这个缓存行的长度稍小了点，但是这使得 16 禁止的运行更加简单。从硬件角度来说，这是一个两路组相连缓存，类似于带 16 个桶的软件哈希表，每个桶的哈西链被限制为最多两个元素。大小(本例中是32个缓存行)和相连性(本例中是2)都被称为缓存行的 germetry。由于缓存是硬件实现的，哈希函数非常简单，从地址中取出 4 位作为哈希键值。

在 C.2 中，每个方框对应一个缓存项，每个缓存项包含一个 256 字节的缓存行。不过，一个缓存项可能为空，在图中表现为空框。其他的块用它所包含的内存行的内存地址标记。由于缓存行必须是 256 字节对齐，因此每一个地址的低 8 位为 0。并且，硬件哈希函数的选择。意味着接下来的高 4 位匹配缓存行中的位置。

如果陈旭代码位于地址 0x43210E00 到 0x43210EFF，并且程序一次访问地址 0x1234500 到 0x12345EFF，图中的情况就可能发生。假设程序正在准备访问地址 0x12345F00，这个地址会哈希到 0xF 行，该行的两路都是空的，因此可以容纳对应的 256 字节缓存行。如果程序访问地址 0x1233000，将会被哈希到第 0 行，相应的 256 字节缓存行可以放到第一路。但是，如果程序访问地址 0x123E00，将会哈希到 0xE 行，其中一个已经存在于缓存中缓存行必须被替换出去，以腾出空间给新的缓存行。如果随后访问刚被替换出去的行，会产生一次“缓存缺失”，这样的缓存缺失被称为“关联性缺失”。

更进一步说，我们仅仅考虑了某个 CPU 读数据的情况。当写的时候会发生什么呢？由于让所有 CPU 都对特定数据项达成一致，这一点非常重要。因此，在一个特定的 CPU 写数据前，它必须首先从其他 CPU 缓存中移除，或者叫做“使无效”。一旦“使无效”操作完成，CPU 可以安全的修改数据项。如果数据存在于该 CPU 缓存中，但是是只读的，这个过程被称为“写缺失”、一旦某个特定的 CPU 完成了对某个数据项的“使无效”操作，该 CPU 可以反复的重新写(或读)该数据项。

随后，如果另外某个 CPU 视图访问数据项，将会引起一次缓存缺失，此时，由于第一个 CPU 为了写而使得缓存项无效，这种类型的缓存缺失被称为“通信缺失”、因为通常是由于几个 CPU 使用数据项进行通信造成的。比如，锁就是一个用于在 CPU 之间使用互斥算法进行通信的数据项。

很明显，必须小心确保，所有 CPU 报纸一致性数据视图。可以很容易想到，通过所有取数据、使无效、写操作。它操作的数据可能已经丢失，或者(也许更糟糕)在不同 CPU 缓存之间拥有冲突的值。这些问题由“缓存一致性”来防止，将在下一节介绍。

缓存一致性协议

缓存一致性协议管理缓存行的状态，以防止数据不一致或者丢失数据。这些协议可能十分复杂，可能有数十种状态。但是为了我们的目的，我们仅仅需要关心仅有 4 种状态的 MESI 协议。

MESI 状态

MESI 代表 modified、exclusive、shared、inbalid，特定缓存行可以使用该协议采用的四种状态。因此，使用该协议的缓存，在每一个缓存行中，维护一个两位的状态标记，这个标记附着在缓存行的物理地址和数据后面。

处于 modified 状态的缓存行，已经收到了来自于响应 CPU 最近进行的内存存储。并且相应的内存却白没有在其他 CPU 的缓存中出现。因此，除以 modified 状态的缓存行可以被认为为被 CPU 所“拥有”。由于该缓存行持有最新的数据复制，因此缓存最终有责任：要么将数据写回到内存，要么将数据转移给其他缓存，并且必须在重新使用该缓存行以持有其他数据之前完成这些事情。

exclusive 状态非常类似于 modified 状态，唯一的差别是，该缓存行还没有被相应的 CPU 修改，这也表示缓存行中对内存数据的复制是最新的。但是，由于 CPU 能够在任意时刻将数据存储到该行，而不考虑其他 CPU，因此，处于 exclusive 状态也可以认为被相应的 CPU 所“拥有”。也就是说，由于物理内存中相应的值是最新的，该缓存行可以直接丢弃而不用会写到内存，也不用将该缓存转移给其他 CPU 的缓存。

处于 shared 状态的缓存行可能被复制到至少一个其他 CPU 的缓存行中，这样在没有得到其他 CPU 的许可时，不能向缓存行存储数据。与 exclusive 状态相同，由于内存中的值是最新的，因此可以不用向内存回写值而直接丢弃缓存中的值，也不用将该缓存转移给其他 CPU。

处于 invalid 状态的行是空的，换句话说，他没有持有任何有效数据。当新数据进入缓存时，如果有可能，它就会被放置到一个处于 invalid 状态的缓存行。这个方法是首选的，因为替换其他状态的缓存行将引起开销昂贵的缓存缺失，这些被替换的行在将来会被引用。

由于所有 CPU 必须维护那些已经搬运进缓存行中的数据一致性视图，因此缓存一致性协议提供消息以协调系统中缓存行的动作。

MESI 协议消息

前面章节中描述的许多事务都需要在 CPU 之间通信。如果 CPU 位于单一共享总线上，只需要如下消息就足够了。

读消息：包含要读取的缓存行的物理地址。
读响应消息：包含之前的“读消息”所请求的数据。这个读响应消息要么由物理内存提供，要么由一个其他缓存提供。例如，如果某一缓存拥有处于 modified 状态的目标数据，那么该缓存必须提供读响应消息。
使无效消息：包含要使无效的缓存行的物理地址。所有其他缓存行必须从它们的缓存中移除相应的数据并且响应此消息。
使无效应答消息：一个接收到使无效消息的 CPU 必须在移除指定数据后响应一个使无效应答消息。
读使无效消息：包含要被读取的缓存行的物理地址。同时指示其他缓存移除其数据。因此，正如名字所示，它将读和使无效消息进行合并。读使无效消息同时需要一个读响应消息及一组使无效应答消息进行应答。
写回消息：包含要写回到物理内存的地址和数据(并且也会“嗅探”进其他 CPU 的缓存)。该消息允许缓存在必要时换出处于 modified 状态的数据以便为其他数据腾出空间。

有趣的是，共享内存的多核系统实际上是一个消息传递的计算机。这意味着：使用分布式共享内存的 SMP 机器集群，正在以两种不同级别的系统架构，使用消息传递来共享内存。

MESI 状态图

由于接受或发送协议消息，特定的缓存行状态会变换，如图 C.3 所示：

图中的转换弧如下：

转 a：缓存行被写回到物理内存，但是 CPU 仍然将它保留在缓存中，并进一步的保留修改它的权限。这个转换需要一个“写回”消息。
转换 b：CPU 将数据写到缓存行，该缓存目前处于排他访问。该转换不需要发送或者接收任何消息。
转换 c：CPU 收到一个针对某个缓存行的“使无效”消息，对应的缓存行已经被修改。CPU 必须使无效本地副本，然后同时响应“读响应”和“使无效应答”消息，同时发送数据给请求的 CPU，并且标示它的本地副本不再有效。
转换 d：CPU 对一个数据项进行一个原子读——修改——写操作，对应的数据没有在他的缓存中。它发送一个“使无效”消息，通过“读响应”消息接收数据。一旦他接收到一个完整的“使无效应答”响应集合，CPU 就完成此转换。
转换 e：CPU 对一个数据项进行一个原子读——修改——写操作，对应的数据在缓存中是只读的。它必须发送一个“使无效”消息，并在完成此转换前，它必须等待一个完整的“使无效应答”响应集合。
转换 f：其他某些 CPU 读取缓存行，其数据由本 CPU 提供，本 CPU 包含一个只读副本，也可能已经将其写回内存。这个转换开始于接收到一个读消息，并且本 CPU 响应一个包含了所请求数据的“读响应”消息。
转换 g：其他 CPU 读取位于本缓存行的数据，并且数据要么是从本 CPU 的缓存提供，要么是从物理内存提供。无论哪种情况，本 CPU 都会保留一个只读副本。该转换开始于接收到一个“读”消息，并且本 CPU 响应一个包含所请求数据的“读响应”消息。
转换 h：当前 CPU 意识到，它很快将要写入一些位于本 CPU 缓存行的数据项，于是发送一个“使无效”消息。直到它接收到完整的“使无效”应答消息集合，CPU 才完成转换。可选的，所有其他 CPU 通过写回消息，从其缓存行将数据取出(可能是为其他缓存行腾出空间)。这样，当前 CPU 就是最后一个缓存该数据的 CPU。
转换 i：其他某些 CPU 对某个数据项进行了一个原子读——修改——写操作，相应的缓存行仅仅被本地的 CPU 缓存所持有。因此本 CPU 将缓存行状态编程无效状态。这个转换开始于接收到“读使无效”消息，并且本 CPU 返回一个“读响应”消息及一个“使无效应答”消息。
转换 j：本 CPU 保存一个数据项到缓存行，但是数据还没有在其他缓存行中。因此发送一个“使读无效”消息。直到它接收到“读响应”消息及完整的“使无效应答”消息集合后，才完成转换。缓存行可能会很快转到“修改”状态，这是在存储完成后由交换 b 完成的。
转换 k：本 CPU 装在一个数据项到缓存中，但是数据项还没有在缓存行中。CPU 发送一个“读”消息，当它接收到相应的“读响应”消息后完成转换。
转换 l：其他 CPU 存储一个位于本 CPU 缓存行的数据项，但是由于其他 CPU 也持有该缓存行的原因，本 CPU 仅仅以只读方式持有该缓存行。这个转换开始于接收到一个“使无效”消息，并且本 CPU 返回一个“使无效应答”消息。

MESI 协议实例

现在，让我们从数据缓存行价值的角度来看这一点。最初，数据驻留在地址为 0 的物理内存中。在一个 4-CPU 的系统中，它在几个直接映射的单缓存行中移动，表 C.1 展示了数据流向。第一列是操作序号，第二列表示执行操作的 CPU，第三列表示执行的操作，接下来的四列表示每一个缓存行的状态(内存地址后紧跟 MESI 状态)。最后两列表示对应的内存内容是否是最新的。V 表示最新，I 表示非最新。

最初，将要驻留数据的的 CPU 缓存行处于 invalid 状态，对应的数据在物理内存中是无效的。当 CPU0 从地址0装载数据时，它在 CPU0 的缓存中进入 shared 状态，并且物理内存中的数据仍是有效的。CPU3 也是从地址0装载数据，这样两个 CPU 中的缓存都处于 shared 状态，并且内存中的数据仍然有效。接下来 CPU0 转载其他缓存行(地址8)，这个操作通过使无效操作强制将地址0的数据换出缓存，将缓存中的数据被换成地址8的数据。现在，CPU2 装载地址0的数据，但是该 CPU 发现它很快就会存储该数据，因此它使用一个“使读无效”消息以获得一个独享副本，这样，将使 CPU3 缓存中的数据变为无效(但是内存中的数据依然是有效的)。接下来 CPU2 开始预期的存储操作，并将状态改为 modified。内存中的数据副本不再是最新的。CPU1 开始一个原子递增操作，使用一个“读使无效”消息从 CPU2 的缓存中窥探数据并使之无效，这样 CPU1 的缓存编程 modified 状态，(内存中的数据仍然不是最新的)。最后，CPU1 从地址 8 读取数据，它使用一个写回消息将地址0的数据会写到内存。

请注意，我们最终使数据位于某缓存行中。

存储导致不必要的停顿

对于特定的 CPU 反复读写特定的数据来说，图 C.1 显示的缓存结构提供了好的性能。但是对于特定缓存行的第一次写来说，其性能是不好的。要理解这一点，参考图 C.4，它显示了 CPU0 写数据到一个缓存行的时间线，而这个缓存行被 CPU1 缓存。在 CPU0 能够写数据前，它必须首先等到缓存行的数据到来。CPU0 不得不停顿额外的时间周期。

其他没有理由强制让 CPU0 延迟这么久，毕竟，不管 CPU1 发送给他的缓存数据是什么，CPU0 都会无条件的覆盖它。

存储缓冲

避免这种不必要的写停顿的方法之一，是在每个 CPU 和它的缓存之间，增加“存储缓冲”，如图 C.5。通过增加这些存储缓冲区，CPU0 可以简单的将要保存的数据放到存储缓冲区中，并且继续运行。当缓存行最终从 CPU1 转到 CPU0 时，数据将从存储缓冲区转到缓存行中。

这些存储缓冲对于特定 CPU 来说，是属于本地的。或者在硬件多线程系统中，对于特定核来说，是属于本地的。无论哪一种情况，一个特定 CPU 仅允许访问分配给它的存储缓冲。例如，在图 C.5 中，CPU0 不能访问 CPU0 的存储缓冲，反之亦然。通过将两者关注的点分开，该限制简化了硬件，存储缓冲区提升了连续写的性能，而在 CPU(核或其他可能的东西)之间的通信责任完全由缓存一致性协议承担。然而，及时有了这个限制，仍然有一些复杂的事情需要处理，将在下面两节中描述。

存储转发

第一个复杂的地方，违反了自身一致性。考虑变量 a 和 b 都初始化为 0，包含变量 a 的缓存行，最初被 CPU1 拥有，而包含变量 b 的缓存行最初被 CPU0 拥有。

1 a = 1; 
2 b = a + 1; 
3 assert(b == 2);

人们并不期望断言失败。可是，难道有谁足够愚蠢，以至于使用如果 C.5 所示的简单体系结构，这种体系结构是令人惊奇的。这样的系统可能看起来会按以下的事件顺序。

CPU0 开始执行 a=1。
CPU0 在缓存中查找 a，并且发现缓存缺失。
因此 CPU0 发送一个“读使无效”消息，以获得包含“a”的独享缓存行。
CPU0 将 a 记录到存储缓冲区。
CPU1 接收到“读使无效”消息，它通过发送缓存行数据，并从他的缓存行中移除数据来响应这个消息。
CPU0 开始执行 b=a+1。
CPU0 从 CPU1 接收到缓存行，它仍然拥有一个为 0 的 a 值。
CPU0 从它的缓存中读取到 a 的值，发现其值为 0。
CPU0 将存储队列中的条目应用到最近到达的缓存行，设置缓存行中的 a 的值为 1。
CPU0 将前面加载的 a 值 0 加 1，并存储该值到包含 b 的缓存行中(假设已经被 CPU0 拥有)。
CPU0 执行 assert(b==2)，并引起错误。

问题在于我们拥有两个 a 的副本，一个在缓存中，另一个在存储缓冲区中。

这个例子破坏了一个重要的前提：即每个 CPU 将总是按照编程顺序看到他的操作。没有这个前提，结果将于直觉相反。因此，硬件设计者同情并实现了“存储转发”。在此，每个 CPU 在执行加载操作时，将考虑(或者嗅探)它的存储缓冲，如图 C.6。换句话说，一个特定的 CPU 存储操作直接转发给后续的读操作，而并不必然经过其缓存。

通过就地存储转发，在前面执行顺序的第 8 步，将在存储缓冲区中为 a 找到正确的值 1，因此最终 b 的值将是 2，这也正是我们期望的。

存储缓冲区及内存屏障

要明白第二个复杂性违反了全局内存序。开率如下的代码顺序，其中变量 a、b 的初始值为 0。

1 void foo(void) 
2 { 
3 	a = 1; 
4 	b = 1; 
5 } 
6 
7 void bar(void) 
8 { 
9 	while (b == 0) continue; 
10 		assert(a == 1); 
11 }

假设 CPU0 执行 foo 函数，CPU1 执行 bar 函数，再进一步假设包含 a 的缓存行仅仅位于 CPU1 的缓存中，包含 b 的缓存行被 CPU0 所拥有。那么操作属顺序可能如下：

CPU0 执行 a=1、缓存行不在 CPU0 的缓存中，因此 CPU0 将 a 的新值放到存储缓冲区，并发送一个“读使无效”消息。
CPU1 执行 while(b==0) continue，但是包含 b 的缓存行不再它的缓存内，因此发送一个“读”消息。
CPU0 执行 b=1，它已经拥有了该缓存行(换句话说，缓存行要么处于 modified 要么处于 exclusive)，因此它存储新的 b 值到它的缓存中。
CPU0 接收到“读”消息，并且发送缓存行中的最近更新的 b 的值到 CPU1，同时将缓存行设置为 shared 状态。
CPU1 接收到包含 b 值的缓存行，并将其值写到它的缓存行中。
CPU1 现在结束执行 while(b==0) continue，引文它发现 b 的值为 1，它开始处理下一条语句。
CPU1 执行 assert(a==1)，并且，由于 CPU1 工作在旧的 a 的值，因此断言失败。
CPU1 接收到 “读使无效”消息，并且发送包含 a 的缓存行到 CPU0，同时在它的缓存中，将该缓存行变成无效。但是已经太迟了。
CPU0 接收到包含 a 的缓存行，并且及时将存储缓冲区的数据保存到缓存行中，CPU1 的断言失败受害于该缓存行。

在此，硬件设计者不能直接帮助我们，因为 CPU 没有方法识别那些相关联的变量，更不用说他们之间关联的方式。因此，硬件设计值提供了内存屏障指令，以允许软件告诉 CPU 这些关系的存在。程序必须修改以包含内存屏障。

1 void foo(void) 
2 { 
3 	a = 1; 
4 	smp_mb(); 
5 	b = 1; 
6 } 
7 
8 void bar(void) 
9 { 
10 	while (b == 0) continue; 
11 	assert(a == 1); 
12 }

内存屏障 smp_mb 将导致 CPU 在刷新后续的存储到变量的缓存行之前，前面的存储缓冲被刷新。在继续处理之前，CPU 可能简单的停顿下来，直到存储缓冲区变为空；也可能是使用存储缓冲区来持有后续的存储操作，直到前面所有的存储缓冲区已经被保存到缓存行中。

后一种情况下，操作序列可能如下所示。

CPU0 执行 a=1。缓存行不在 CPU0 的缓存内，因此 CPU0 将 a 的新值放到存储缓冲中，并发送一个“读使无效”消息。
CPU1 执行 while(b==0) continue，但是包含 b 的缓存行不在它的缓存中，因此它发送一个“读”消息。
CPU0 执行 smp_mb，并标记当前所有存储缓冲区的条目。即 a=1 这个条目。
CPU0 执行 b=1。它已经拥有这个缓存行了。(即缓存行已经处于 modified 或 exclusive)，但是在存储缓冲区中存在一个标记条目。因此，它不讲 b 的新值存放到缓存行，而是存放到存储缓冲区，这里 b 不是一个标记条目。
CPU0 接收到“读”消息，随后发送包含原始 b 值的缓存行给 CPU1.它也标记该缓存行的复制为 shared 状态。
CPU1 读取到包含 b 的缓存行，并将它复制到本地缓存中。
CPU1 现在可以装在 b 的值了。但是，由于它发现其值仍然我 0，因此它重复执行 while 语句。b 的心智被安全的隐藏在 CPU0 的存储缓冲区中。
CPU1 接收到“读使无效”消息，发送包含 a 的缓存行给 CPU0，并且是他的缓存无效。
CPU0 接收到包含 a 的缓存行，使用存储缓冲区的值替换缓存行，将这一行设置为 modified 状态。
由于被存储的 a 是存储缓冲区中唯一被 smp_mb 标记的条目，因此 CPU0 能够存储 b 的新值到缓存行中，除非包含 b 的缓存行当前处于 shared 状态。
CPU0 发送一个“使无效”消息给 CPU1。
CPU1 接收到“使无效”消息，使包含 b 的缓存行无效，并且发送一个“使无效应答”消息给 CPU0.
CPU1 执行 while(b==0) continue，但是包含 b 的缓存行不再它的缓存中，因此它发送一个“读”消息给 CPU0.
CPU0 接收到“使无效应答”消息，将包含 b 的缓存行设置成 exclusive 状态。CPU0 现在存储新的 b 值到缓存行。
CPU0 接收到“读”消息，同时发送包含新的 b 值的缓存行给 CPU1。他也标记该缓存行的复制为“shared”状态。
CPU1 接收到包含 b 的缓存行，并将它复制到本地缓存中。
CPU1 现在能够装载 b 的值了，由于它发现 b 的值为 1，它对出 while 循环并执行下一条语句。
CPU1 执行 assert(a==1)，但是包含 a 的缓存行不再它的缓存中。一旦它从 CPU0 获得这个缓存行，它将使用最新的 a 的值，因此断言语句将通过。

正如你看到的那样，这个过程涉及不少工作。即使某些事情从直觉上看是简单的操作，就像“加载 a 的值”这样的操作，都会包含大量复杂的步骤。

存储序列导致不必要的停顿

不幸的是，每一个存储缓冲区相对而言都比较小，这意味着执行一段较小的存储操作序列的 CPU，就可能填满它的存储缓冲区(比如当所有的这些结果发生了缓存缺失时)。从这一点来看，CPU 在能够继续执行前，必须再次等待刷新操作完成，其目的是为了清空它的存储缓冲。相同的情况可能在内存屏障之后发生，内存屏障之后的所有存储操作指令，都必须等待刷新操作完成，而不管这些后续存储是否存在缓存缺失。

这可以通过使用“使无效应答”消息更快到达 CPU 来得到改善。实现这一点的方法之一是使用每 CPU 的使无效消息队列，或者成为“使无效队列”。

使无效队列

“使无效应答”消息需要如此长的时间，其原因之一是它们必须确保相应的缓存行确实已经变成无效了。如果缓存比较忙的话，这个使无效操作可能被延迟。例如，如果 CPU 密集的装载或者存储数据，并且这些数据都在缓存中。另外，如果在一个较短的时间内，大量的“使无效”消息到达，一个特定的 CPU 会忙于处理它们。这会使得其他 CPU 陷入停顿。

但是，在发送应答前，CPU 不必真正使无效缓存行。它可以将使无效消息排队，在发送各国的关于该缓存行的消息前，需要处理这个消息。

使无效队列及使无效应答

图 C.7 显示了一个包含使无效队列的系统。只要将使无效消息放入队列，一个带有使无效队列的 CPU 就可以迅速应答使无效消息，而不必等待相应的缓存行真的变成无效状态。当然，CPU 必须在准备发送使无效消息前引用它的使无效队列。如果一个缓存行对应的条目在使无效队列中，则 CPU 不能立即发送使无效消息，它必须等待使无效队列中的条目被处理。

将一个条目放进使无效队列，实际上是由 CPU 承诺，在发送任何与该缓存行相关的 MESI 协议消息前处理该条目。只要相应的数据结构不存在大的竞争，CPU 会很出色的完成此事。

但是，消息能够被缓冲在使无效队列中，该事实带来了额外的内存乱序机会，浙江在下一节讨论。

使无效队列及内存屏障

我们假设 CPU 将使用使无效请求队列，并立即响应它们。这个方法使得执行存储操作的 CPU 看到的缓存使无效消息的延迟降到最小，但是这会将内存屏障失效，看看如下示例。

假设 a 和 b 都被初始化为 0，a 是只读的(MESI 状态为 shared)，b 被 CPU0 拥有(MESI 状态为 exclusive 或 modified)。然后假设 CPU0 执行 foo 而 CPU1 执行 bar，代码片段如下。

1 void foo(void) 
2 { 
3 	a = 1; 
4 	smp_mb(); 
5 	b = 1; 
6 } 
7 
8 void bar(void) 
9 { 
10 	while (b == 0) continue; 
11 	assert(a == 1); 
12 }

操作顺序可能如下：

CPU0 执行 a=1。在 CPU0 中，对应的缓存行是只读的，因此 CPU0 将 a 的新值放入存储缓冲区，并发送一个“使无效”消息，这是为了使 CPU1 的缓存中的对应缓存行失效。
CPU1 执行 while(b==0) continue，但是包含 b 的缓存行不在它的缓存中，因此发送一个“读”消息。
CPU1 接收到 CPU0 的“使无效”消息，将其排队并立即响应该消息。
CPU0 接收到来自于 CPU1 的使无效消息，因此它放心的通过第 4 行的 smp_mb，从存储缓冲区移动 a 的值到缓存行。
CPU0 执行 b=1。它已经拥有这个缓存行(也即是说，缓存行已经处于 modified 或者 exclusive 状态)，因此它将 b 的新值存储到缓存行中。
CPU0 接收到“读”消息，并且发送包含 b 的新值的缓存行到 CPU1，同时在自己的缓存中标记缓存行为“shared”状态。
CPU1 接收到包含 b 的缓存行并且将其应用到本地缓存。
CPU1 现在可以完成 while(b==0) continue，因为它发现 b 的值为 1，因此开始处理下一条语句。
CPU1 执行 assert(a==1)，并且，由于旧的 a 值还在 CPU1 的缓存中，因此陷入错误。
虽然陷入错误，CPU1 处理已经排队的使无效消息，并且(迟到)在自己的缓存中刷新包含 a 值的缓存行。

如果加速使无效响应会导致内存屏障被忽略，那么就没有什么意义了。但是，内存屏障指令能够与使无效队列交互，这样，当一个特定的 CPU 执行一个内存屏障时，它标记无效队列中的所有条目，并强制所有后续的装载操作进行等待，直到所有标记的条目都保存到 CPU 的缓存中。因此，我们可以在 bar 函数中添加一个内存屏障，具体如下：

1 void foo(void) 
2 { 
3 	a = 1; 
4 	smp_mb(); 
5 	b = 1; 
6 } 
7 
8 void bar(void) 
9 { 
10 	while (b == 0) continue; 
11 	smp_mb(); 
12 	assert(a == 1); 
13 }

有了这个变化之后，操作顺序可能如下：

CPU0 执行 a=1。对应的缓存行在 CPU0 的缓存中是只读的，因此 CPU0 将 a 的新值放入它的存储缓冲区，并且发送一个使无效消息以刷新 CPU1 对应的缓存行。
CPU1 执行 while(b==0) continue，但是包含 b 的缓存行不再它的缓存中，因此它发送一个读消息。
CPU1 接收到 CPU0 的使无效消息，将其排队并立即响应它。
CPU0 接收到 CPU1 的响应，因此它放心的通过第 4 行 smp_mb 语句将 a 从他的存储缓冲区移到缓存行。
CPU0 执行 b=1。它已经拥有该缓存行(MESI 状态为 modified 或 exclusive)，因此它存储 b 的新值到缓存行。
CPU0 接收到读消息，并且发送包含新的 b 值的缓存行给 CPU1，同时在自己的缓存行中，标记缓存行为 shared 状态。
CPU1 接收到包含 b 的缓存行并更新到它的缓存中。
CPU1 现在结束执行 while 循环，引文它发现 b 的值为 1，因此开始处理小一条语句，这是一条内存屏障指令。
CPU1 必须停顿，知道它处理完使无效队列中的所有消息。
CPU1 处理已经入队的使无效消息，从它的缓存中使无效包含 a 的缓存行。
CPU1 执行 assert(a==1)，由于包含 a 的缓存行已经不在它的缓存中，它发送一个读消息。
CPU0 使用包含新的 a 值的缓存行来响应该读消息。
CPU1 接收到该缓存行，它包含新的 a 的值 1，因此断言不会被触发。

即使有很多 MESI 消息传递，CPU 最终都会正确的应答。下一节阐述了 CPU 设计者为什么必须格外小心的处理它的缓存一致性优化操作。

读和写内存屏障

在前一节，内存屏障用来标记存储缓冲区和使无效队列中的条目。但是在我们的代码片段中 foo 没有必要进行使无效队列相关的任何操作，类似的，bar 也没有必要进行与存储缓冲区相关的任何操作。

因此，很多 CPU 体系结构提供更弱的内存屏障指令，这些指令仅仅做其中一项或者几项工作。不准确的说，一个“读内存屏障”仅仅标记它的使无效队列，一个“写内存屏障”仅仅标记它的存储缓冲区，而完整的内存屏障同时标记使无效队列和存储缓冲区。

这样的效果是，读内存屏障仅仅保证执行该指令的 CPU 上面的装载顺序，因此所有在读内存平展之前的装载，将在所有随后的装载前完成。类似的，写内存屏障仅仅保证写之间的属性怒，也是针对执行该指令的 CPU 来说。同样的，所有在内存屏障之前的存储操作，将在其后的存储操作完成之前完成。完整的内存屏障同时保证写和读之间的顺序，这也仅仅针对执行该内存屏障的 CPU 来说的。

我们修改 foo 好 bar，以使用读和写内存屏障，如下所示：

1 void foo(void) 
2 { 
3 	a = 1; 
4 	smp_wmb(); 
5 	b = 1; 
6 } 
7 
8 void bar(void) 
9 { 
10 	while (b == 0) continue; 
11 	smp_rmb(); 
12 	assert(a == 1); 
13 }

某些计算机甚至拥有更多的内存屏障，理解这三个屏障通常能让我们更好的理解内存屏障。

内存屏障示例

本节提供了一些有趣的、但是稍显不同的内存屏障用法。虽然他们能在大多数时候正常工作，但是其中一些仅能在特定 CPU 上运行。如果目的是为了产生哪些能在所有 CPU 上都能运行的代码，那么这些用法是必须要避免的。为了能够更好理解他们之间的细微差别，我们首先要关注乱序体系结构。

乱序体系结构

一定数量的乱序计算机系统已经被生产了数十年。不过乱序问题的实质十分微秒，真正理解它需要非常丰富的特定硬件方面的知识。与其针对一个特定的硬件厂商说事，这会把读者带到详细的技术规范中去，不如让我们设计一个虚构的、最大限度的乱序体系结构。

这个硬件必须遵循以下顺序约束：

单个 CPU 总是按照编程顺序来感知它自己的内存访问。
仅仅在操作不同地址时，CPU 才对给定的存储操作进行重排序。
一个特定的 CPU，在内存屏障之前的所有装载操作(smp_rmb)将在所有读内存屏障后面的操作之前被其他 CPU 所感知。
一个特定的 CPU，所有在写内存屏障之前的写操作(smp_wmb)都将在所有内存屏障之后的写操作之前被其他 CPU 所感知。
一个特定的 CPU，所有在内存屏障之前的内存访问(装载和存储)(smp_mb)都将在所有内存屏障之后的内存访问之前，被所有其他 CPU 感知。

假设一个大的非一致性缓存体系(NUCA)系统，为了给特定节点内部的 CPU 提供一个公平的内部访问带宽，在每一个节点的内连接口提供了一个每 CPU 队列，如图 C.8。虽然一个特定 CPU 的访问是由内存屏障排序的，但是，一堆相关 CPU 的相关访问顺序被严重的重排，正如我们将要看到的。

示例 1

表 C.2 展示了三个代码片段，被 CPU 0/1/2 并发执行，a、b、c 都被初始化为 0。

假设 CPU0 刚经过很多缓存缺失，因此它的消息队列是满的，但是 CPU1 在它的缓存中独占性运行，因此它的消息队列是空的。那么 CPU0 在向 a/b 赋值时，看起来节点 0 的缓存是立即生效的(因此对 CPU1 来说也是可见的)，但是将阻塞于 CPU0 之前的流量。与之相对的是，CPU1 向 c 赋值时，由于 CPU1 的消息队列为空，因此可以很快执行。因此，CPU2 将在看到 CPU0 对 a 的赋值前，先看到 CPU1 对 c 的赋值，这将导致验证失败，即使有内存屏障也会如此。

可移植代码不能认为断言不会触发。由于编译器和 CPU 都能够重排代码，因此可能触发断言。

示例 2

表 C.3 展示了代码片段，在 CPU 0/1/2 上并行执行，a/b 均被赋值为 0。

我们再一次假设 CPU0 刚遇到很多缓存缺失，因此它的消息队列满了，但是 CPU1 在它的缓存中独占性运行，因此它的消息是空的。那么，CPU0 给 a 赋值将立即反映在及诶单 0 上，(因此对于 CPU1 来说也是立即可见的)，但是将阻塞于 CPU0 之前的流量。相对的，CPU1 对 b 的赋值将于 CPU1 的空队列进行工作。因此，CPU2 在看到 CPU2 对 a 赋值前，可以看到 CPU1 对 b 的赋值。这将导致断言失败，尽管存在内存屏障。

从原理上来说，编写可移植代码不能用上面的例子，但是，正如前面一样，实际上这段代码可以在大多数主流的计算机上正常运行。

示例 3

表 C.4 展示了三个代码片段，在 CPU 0/1/2 上并行执行。所有变量均被初始化为 0。

请注意，不管是 CPU1 还是 CPU2 都要看到 CPU0 在第三行对 b 的赋值后，才能处理第 5 行，一旦 CPU 1 和 2 已经执行了第 4 行的内存屏障，他们就能看到 CPU0 在第 2 行的内存屏障前的所有赋值。类似的，CPU0 在第 8 行的内存屏障与 CPU1 和 CPU2 在第 4 行的内存屏障是一对内存屏障，因此 CPU0 将不会执行第 9 行的内存赋值，直到它对 a 的赋值被其他 CPU 可见。因此，CPU2 在第 9 行的 assert 将不会触发。

Linux 内核中的 synchronize_rcu 原语使用了类似于本地中的算法。

内存屏障是永恒的吗

已经有不少最近的系统，他们对于通常的乱序执行，特别是对乱序内存引用不大积极。这个趋势将会持续下去以至于将内存屏障变为历史吗？

赞成这个观点的人会拿大规模多线程硬件体系说事，这样一来每个线程都必须等待内存就绪，在此期间，可能有数十个、数百个甚至数千个线程在继续运行。在这样的体系结构中，没有必要使用内存屏障了。因为一个特定的线程在处理下一条指令前，将简单的等待所有外部操作全部完成。由于可能有数千个其他线程，CPU 将被完全利用，没有 CPU 周期会被浪费。

反对者则会说，极少量的应用有能力扩展到上千个线程。除此以外，还有越来越严重的实时响应需求，对某些应用来说，其响应需求是数十毫秒。在这种系统中，实时响应需求是难以实现的。而且，对于大规模多线程场景来说，机器低的单线程吞吐量更难以实现。

另一种支持的观点认为，更多的减少延迟的硬件实现技术会给 CPU 一种假象，使得 CPU 觉得按全频率、一致性的运行，这几乎提供了与乱序执行一样的性能优势。反对的观点则会认为，对于电池供电的设备及环境责任来说，这将带来严重的能耗需求。

没法下结论谁是对的，因此咱们还是准备同时接受两者吧。

对硬件设计者的建议

硬件设计者可以做很多事情，这些事情给软件开发者带来了困难。以下是我们在过去遇到的一些事情，在此列出来，希望能够帮助你防止在将来出现下列问题。

IO 设备忽略了缓存一致性

这个糟糕的特性将导致从内存中机械能 DMA 会丢失刚从输出缓冲区中对他进行的修改。同样不好的是，也导致输入缓冲区在 DMA 完成后被 CPU 缓存中的内容覆盖。要使你的系统在这样的情况下正常工作，必须在为 IO 设备准备 DMA 缓冲区时，小心刷新 CPU 缓存。类似的，在 DMA 操作完成后，你需要刷新所有位于 DMA 缓冲区的缓存。而且，你需要非常小心的避免指针方面的 BUG，因为错误的读取输入缓冲区可能会导致对输入数据的破坏。

外部总线错误的发送缓存一致性数据

该问题是上一问题的一个更难缠的变种，导致设备组甚至是在内存自身不能遵从缓存一致性。我痛苦的责任是通知你：随着嵌入式系统转移到多核体系，不用怀疑，这样的问题会越来越多。希望这些问题能在 2015 年得到处理。

设备中忽略了缓存一致性

这听起来真的无辜，毕竟中断不是内存引用，对吧？但是假设一个 CPU 有一个分区的缓存，其中一个缓存带非常忙，因此一直持有输入缓冲的最后一个缓存行。如果对应的 IO 完成中断到达这个 CPU，在 CPU 中引用这个缓存行的内存引用将返回旧值，再导致数据被破坏，在随后以异常转储的形式被发现。但是，当系统对引起错误的输入缓冲区进行转储时，DMA 很可能已经完成了。

核间中断(IPI)忽略了缓存一致性

当位于对应的消息缓冲区的所有缓存行，他们被提交到内存之前，IPI 就已经到达该目标 CPU，这可能会有问题。

上下文切换领先于缓存一致性

如果内存访问可以完全乱序，那么上下文切换就很麻烦。如果任务从一个 CPU 切迁移到另一个 CPU，而原 CPU 上的内存访问在目标 CPU 上还不完全可见，那么任务就会发现，它看到的变量还是以前的值，这会扰乱大多数算法。

过度宽松的模拟器和仿真器

编写模拟器或者仿真器来模拟内存乱序是很困难的。因此在这些环境上面运行得很好的软件，在实际硬件上运行时，将得到令人惊讶的结果。不幸的是，规则仍然是，硬件比模拟器和仿真器更复杂，但是我们这种状况能够改变。

我们再次鼓励硬件设计者避免这些做法。

Feedback

Was this page helpful?

Glad to hear it! Please tell us how we can improve.

Sorry to hear that. Please tell us how we can improve.