谢宝友教你学Linux：深入理解Linux RCU之从硬件说起

。在最初5ns期间, 仅仅CPU 3拥有变量的值。在接下来的10ns，CPU 2和3看到不一致的变量值，但是随后都一致的认为其值是"2"。 但是，CPU 1在整个300ns内认为其值是"1"，并且 CPU 4 在整个500ns内认为其值是"4"。

这真是一个匪夷所思的测试结果。同一个变量，竟然在不同的CPU上面被看到不同的值！！！！

如果不理解硬件，就不会接受这个匪夷所思的测试结果。当然了，此时如果有一位大师站在你的面前，你也不能够跟随大师的节奏起舞。

四、为什么需要MESI

请不要说：我还不知道MESI是什么？

简单的说，MESI是一种内存缓存一致性协议。

现代CPU的速度比现代内存系统的速度快得多。2006 年的CPU可以在每纳秒内执行十条指令。但是需要很多个十纳秒才能从物理内存中取出一个数据。它们的速度差异（超过2个数量级）导致在现代CPU中出现了数兆级别的缓存。这些缓存与CPU是相关联的，如下图。典型的，缓存可以在几个时钟周期内被访问。借助于CPU流水线的帮助，我们暂且可以认为，缓存能够抵消内存对CPU性能的影响。

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

经过一段时间后，CPU的缓存将会被填满，后续的缓存缺失需要换出缓存中现有的数据，以便为最近的访问项腾出空间。这种"cache miss"被称为"capacitymiss"，因为它是由于缓存容量限制而造成的。但是，即使此时缓存还没有被填满，大量缓存也可能由于一个新数据而被换出。这是由于大量的缓存是通过硬件哈希表来实现的，这些哈希表有固定长度的哈希桶（或者叫"sets"，CPU设计者是这样称呼的），如下图。

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

在程序代码位于地址0x43210E00- 0x43210EFF，并且程序依次访问地址0x12345000-0x12345EFF时，图中的情况就可能发生。假设程序正准备访问地址0x12345F00，这个地址会哈希到 0xF行，该行的两路都是空的，因此可以提供对应的256字节缓存行。如果程序访问地址0x1233000，将会哈希到第0行，相应的256字节缓存行可以放到第1路。但是，如果程序访问地址0x1233E00，将会哈希到第0xE行，必须有一个缓存行被替换出去，以腾出空间给新的行。如果随后访问被替换的行，会产生一次"cache miss"，这样的缓存缺失被称为"associativitymiss"。

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

最后，如果另外某个CPU试图访问数据项，将会引起一次缓存缺失，此时，由于第一个CPU为了写而使得缓存项无效，这被称为"communication miss"。因为这通常是由于几个CPU使用缓存通信造成的（例如，一个用于互斥算法的锁使用这个数据项在CPU之间进行通信）。

很明显，所有CPU必须小心的维护数据的一致性视图。这些问题由"缓存一致性协议"来防止，常用的缓存一致性是MESI。

五、MESI的四种状态

MESI 存在"modified"，"exclusive"，"shared"和"invalid"四种状态，协议可以在一个指定的缓存行中应用这四种状态。因此，协议在每一个缓存行中维护一个两位的状态标记，这个标记附着在缓存行的物理地址和数据后面。

处于"modified"状态的缓存行是由于相应的CPU最近进行了内