CPU 结构

现代多核处理器，一个CPU由多个核组成，每个核又可以有多个硬件线程，比如我们说4核8线程，就是指有4个核，每个核2个线程，这在OS看来就像8个并行处理器一样。
CPU缓存有多级缓存，比如L1, L2, L3等：
L1容量最小，速度最快，每个核都有L1缓存，L1又专门针对指令和数据分成L1d(数据缓存),L1i(指令缓存)。
L2容量比L1大，速度比L1慢，每个核都有L2缓存。
L3容量最大，速度最慢，多个核共享一个L3缓存。
有些CPU可能还有L4缓存，不过不常见；此外还有其他类型的缓存，比如TLB(translation lookaside buffer)，用于物理地址和虚拟地址转译，这不是我们关心的缓存。

这里盗个图

CPU 缓存工作原理

CPU cache和内存系统使用固定大小的数据块来进行交互，这个数据块被称为Cache line，Cache line的大小一般是2的整数次幂。根据设计的不同，从16B到256B不等。当CPU首次访问某个数据的时候，它没有在Cpu cache中，我们称之为Cache miss。在这种情况下，cpu需要花费几百个cycle去把该数据对应的Cache line从内存中中加载到cpu cache中，而在这个过程中，cpu只能是等待那个耗时内存操作完成。一旦完成了cpu cache数据的加载，随后的访问会由于数据在cache中而使得cpu全速运行。

运行一段时间之后，cpu cache的所有Cache line都会被填充有效的数据，这时候的，要加载新的数据到cache中必须将其他原来有效的cache数据“强制驱离”（一般选择最近最少使用的那些Cache line）。这种cache miss被称为capacity miss，因为CPU cache的容量有限，必须为新数据找到空闲的Cache line。有的时候，即便是cache中还有闲置的Cache line，旧的cache数据也会被“强制驱离”，以便为新的数据加载到Cache line中做准备。

当然，这是和cache的组织有关。比较大的cache往往实现成hash table（为了硬件性能），所有的cache line被分成了若干个固定大小的hash buckets（更专业的术语叫做set），这些hash buckets之间不是形成链表，而是类似阵列。

缓存结构

一块CPU缓存可以看成是一个数组，数组元素是缓存项(cache entry)，一个缓存项的内容大概是这样的：

1
2
3

+-------------------------------------------+   
|  tag  |   data block(cache line) |  flag  |   
+-------------------------------------------+

• data block就是从内存中拷贝过来的数据，也就是我们说的cache line，从上面信息可知大小是64字节。（linux 内存的最小单位是字节）
• tag 保存了内存地址的一部分，是用来验证是否缓存命中的。
• flag 是一些标志位，比如缓存是否失效，写dirty等等。

我们可以通过以下命令来查看case line 的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[root@CentOS7 ~]# getconf -a | grep CACHE
LEVEL1_ICACHE_SIZE                 32768  # 32KB 指令缓存
LEVEL1_ICACHE_ASSOC                8        # ASSOC表示主存地址映射到缓存的策略，这里L18路组相联
LEVEL1_ICACHE_LINESIZE             64       # cache line 每行的大小为64Bytes
LEVEL1_DCACHE_SIZE                 32768    #
LEVEL1_DCACHE_ASSOC                8    
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144
LEVEL2_CACHE_ASSOC                 4         # ASSOC表示主存地址映射到缓存的策略，这里L2 是4路组相联
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  12582912 # 12M
LEVEL3_CACHE_ASSOC                 16       
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0           # 没有l4 缓存
LEVEL4_CACHE_ASSOC                 0           
LEVEL4_CACHE_LINESIZE              0

缓存映射

缓存首先要解决的问题是：怎么映射内存地址和缓存地址？比如CPU要检查一个内存值是否已经缓存，那么它首先要能算出这个内存地址对应的缓存地址，然后才能检查。

为了解决这个问题，缓存将一个内存地址分成下面几个部分：

1
2
3

+-------------------------------------------+   
|  tag                | index    | offset   |   
+-------------------------------------------+

• tag和缓存项中的tag对应，用来验证是否缓存命中的。
• index 缓存项数组中的索引。
• offset 缓存块(cache line)中的偏移，因为缓存块是64字节，而内存值可能只有4个字节，一个缓存块可以保存多个连续的内存值。这个offset实际上就是指明内存值在cache line中的位置。

直接映射（Direct mapped）

假如缓存的大小是32768B(32KB)，缓存块大小是64B，那么缓存项数组就有‭ 32768‬/64=512 个。

• CPU要访问一个内存地址0x1CAABBDD‬，它首先检查这个内存地址是否在缓存中，检查过程是这样的：

• 先计算内存在cache line中的偏移，因为缓存块是64字节，那么offset需要占6位(2^6=64)，即offset=011101=29。

• 接着要计算缓存项的索引，因为缓存项数组是512个，所以index需要占9位(2^9=512)，即index=011101111=239。

• 现在我们通过offset和index已经找到缓存块的具体位置了，但是因为内存要远比缓存大很多，所以多个内存块是可以映射到同一个位置的，怎么判断这个缓存块位置存的就是这个内存的值呢？答案就是tag：内存地址去掉index和offset的部分，剩下的就是tag=00011100101010101=0x3955。

• 通过index找到缓存项，比较缓存项中的tag是否与内存地址中的tag相同，如果相同表示命中，就直接取缓存块中的值；如果不同表示未命中，CPU需要将内存值拷贝到缓存(替换掉老的)。

这种映射方式就称为直接映射(Direct mapped)，它的缺点就是多个内存地址会映射到同一个缓存地址，拿上面的内存地址来看，只要offset和index相同的内存地址，就一定会映射到同一个地方.

比如内存地址为：

1
2
3

00011100101010100 011101111 011101
00011100101010110 011101111 011101
00011100101010111 011101111 011101

组相联映射

为了解决上面的问题，我试着把缓存项数组分成2个数组(2路)，比如分成2个256的数组，那么按照上述的匹配，会匹配出如下图所示：

• 先通过index找到数组索引，只不过因为是2路，所以存在2个数组。
• 然后通过内存tag依次比较2个缓存顶的tag，如果其中一个tag相等，说明这个数组缓存命中；
• 如果两个都不相等，说明缓存不命中，CPU会拷贝内存值到缓存中，但是现在有2个位置，需要淘汰一个缓存，然后在进行写入。

那这个和直接映射相比，好在哪里呢，因为一个内存值会随机拷贝到2路中的1个，所以缓存冲突(多个内存地址映射到同一个缓存地址)的概率会降低一半；如果把缓存项数组分成4个数组，这就是4路组相联。上面LEVEL1_ICACHE_ASSOC的值等于8，表明是8路组相联。分组越多，缓存冲突率越低，但是CPU要遍历的数组就越多，这是一个权衡的问题。通过观察也可以发现，其实直接映射就是1路组相联。如果直接分成512个数组，那每个数组只有1项，这种就是全相联，CPU直接遍历512个数组，判断内存地址在哪1个。

关于缓存映射，这里还有动画演示

缓存分配策略和更新策略

读数据

当CPU从内存读数据时，如果该数据没有在缓存中(read miss)，CPU会把数据拷贝到缓存。

写数据

缓存写策略， 我们看到缓存当中有个一个flag，flag的存在是在表示该缓行的状态。

• Write through 更新缓存的数据，同时更新内存的数据。

  当cache写命中时，处理器对Cache写入的同时，将数据写入到内存中，内存的数据和Cache中的数据都是同步的，这种方式比较简单、可靠。但是处理每次对cache更新都需要对内存写操作，因此总线工作繁忙，内存的带宽被大大占用，因此运行速度会受到影响。

  假设一段程序在频繁地修改一个局部变量，局部变量生存周期很短，而且其他进程/线程也用不到它，CPU依然会频繁地在Cache和内存之间交换数据，造成不必要的带宽损失。当cache写未命中时，只有直接向主存写入了，但此时是否将修改过的主存块取到cache，

  如果在写的时候数据没有在缓存中(write miss)，也有两种策略

  • WTWA（Write–Through–with–Write–Allocate) 在写之前先把数据加载到缓存，然后再实施上面的写策略。

  • WTNWA法（WriteThrough–with．NO-Write–Allocate) 加载缓存，直接把数据写到内存。数据只有在 read miss 时才会加载到缓存

• Write back

  当CPU对cache写命中时，只修改cache的内容不立即写入主存，只当此行被换出时才写回主存。这种策略使cache在CPU－主存之间，不仅在读方而且在写方向上都起到高速缓存作用。对一cache行的多次写命中都在cache中快速完成修改，只是需被替换时才写回速度较慢的主存，减少了访问主的次数从而提高了效率。为支持这种策略，每个cache行必须配置一个修改位，以反映此行是否被CPU修改过。

  当某行被换出时，根据此行修改位为是为0。对于cache写未命中，写回法的处理是为包含欲写字的主存块在cache分配一行，将此块整个拷贝到Cache后对其进行修改， 因为尔后对此块的多读/写访问的可能性很大。拷贝主存块时虽已读访问到主存，但此时并不对主存块修改。因为换出的cache很可能此期间要写回主存，为避免此过程耗时长，写未命中对将新块读入后，只在cache中进行写修改。统一地将主存写修改操作留待换出时进行

• Write-once

  写一次是一种基于写回又结合了写通的写策略，即写命中和写未命中的处理与写回法基本相同，只是第一次写命中时要同时写入主存。这策略主要用于某些处理器的片内cache，例如Pentium处理器的片内数据cache就采用的是写一次法。因为片内cache写命中时，写操作就在CPU内部高完成，若没有 内存地址及其它指示信号送出，就不便于系统中的其它cache监听（snoop）。采用写一次法，在第一次片内cache写命中时，CPU要在线上启动一个存储写周期。其它cache监听到此主存块地址及写信号后，即可把它们各自保存可能有的该块拷贝及时作废（无效处理）。尔后若有 对片cache此行的再次或多次写命中，则按回写法处理，无需再送出信号了。

• 其他

  WC（write-combining）， UC（uncacheable）在这里不做详细展开，有兴趣可以自己深入了解。

关于写策略，可以参看这个 动画演示。

从上面描述我们知道，当我们向一个内存写数据时，内存中的数据可能不马上被更新，这个新数据可能还在cache line呆着。因为每个核都有自己的缓存，如果CPU不做处理，可以想象一定会出问题的：比如核1改了数据，核2去读同一个数据，此时数据还在核1的缓存中，核2读到的就是老的数据。CPU为了处理多核间的缓存同步,有一套复杂的一致性协议。

MESI 协议

MESI 协议状态

MESI是“modified”, “exclusive”, “shared”, 和 “invalid”首字母的大写，当使用MESI 协议的时候，cacheline可以处于这四个状态中的一个，因此除了物理地址和具体的数据之外，还需要为每一个cacheline设计一个2-bit的tag来标识该cacheline的状态。

modified 状态

处于modified状态的cacheline说明近期有过来自对应cpu的写操作，同时也说明该该数据不会存在其他cpu对应的cache中。因此，处于modified状态的cacheline也可以说是被该CPU独占。而又因为只有该CPU的cache保存了最新的数据（最终的memory中都没有更新），所以，该cache需要对该数据负责到底。例如根据请求，该cache将数据及其控制权传递到其他cache中，或者cache需要负责将数据写回到memory中，而这些操作都需要在reuse该cache line之前完成。

exclusive

exclusive状态和modified状态非常类似，唯一的区别是对应CPU还没有修改cacheline中的数据，也正因为还没有修改数据，因此memory中对应的data也是最新的。在exclusive状态下，cpu也可以不通知其他CPU cache而直接对cacheline进行操作，因此，exclusive状态也可以被认为是被该CPU独占。由于memory中的数据和cacheline中的数据都是最新的，因此，cpu不需对exclusive状态的cacheline执行写回的操作或者将数据以及归属权转交其他cpu cache，而直接reuse该cacheline（将cacheine中的数据丢弃，用作他用）。

share

处于share状态的cacheline，其数据可能在一个或者多个CPU cache中，因此，处于这种状态的cache line，CPU不能直接修改cacheline的数据，而是需要首先和其他CPU cache进行沟通。和exclusive状态类似，处于share状态的cacheline对应的memory中的数据也是最新的，因此，cpu也可以直接丢弃cacheline中的数据而不必将其转交给其他CPU cache或者写回到memory中。

invalid

处于invalid状态的cacheline是空的，没有数据。当新的数据要进入cache的时候，优选状态是invalid的cacheline，之所以如此是因为如果选中其他状态的cacheline，则说明需要替换cacheline数据，而未来如果再次访问这个被替换掉的cacheline数据的时候将遇到开销非常大的cache miss。

CPU中每个缓存行（Caceh line)使用4种状态进行标记，使用2bit来表示:

MESI 协议消息

当cpu对内存数据进行修改的或者读取的时候，自然缓存状态需要改变，因此，多核CPU就要通过总线来告知其他cpu自己对某个缓存的状态修改。因此CPU之间也会通过传递消息来传递这种消息的改变

MESI 协议状态变换

下图是MESI 协议通过MESI 消息进行的变换

对上图中的状态迁移解释如下：

• Transition (a)：

cache可以通过writeback 消息 将一个cacheline的数据写回到memory中（或者下一级cache中），这时候，该cacheline的状态从Modified迁移到Exclusive状态。对于cpu而言，cacheline中的数据仍然是最新的，而且是该cpu独占的，因此可以不通知其他cpu cache而直接修改之。

• Transition (b)：

在Exclusive状态下，cpu可以直接将数据写入cacheline，不需要其他操作。相应的，该cacheline状态从Exclusive状态迁移到Modified状态。这个状态迁移过程不涉及bus上的Transaction（即无需MESI Protocol Messages的交互）。

• Transition ©：

CPU 在总线上收到一个read invalidate的请求，同时，该请求是针对一个处于modified状态的cacheline，在这种情况下，CPU必须该cacheline状态设置为无效，并且用read response”和“invalidate acknowledge来回应收到的read invalidate的请求，完成整个bus transaction。一旦完成这个transaction，数据被送往其他cpu cache中，本地的copy已经不存在了。

• Transition (d)：

CPU需要执行一个原子的readmodify-write操作，并且其cache中没有缓存数据，这时候，CPU就会在总线上发送一个read invalidate用来请求数据，同时想独自霸占对该数据的所有权。该CPU的cache可以通过read response获取数据并加载cacheline，同时，为了确保其独占的权利，必须收集所有其他cpu发来的invalidate acknowledge之后（其他cpu没有local copy），完成整个bus transaction。

• Transition (e)：

CPU需要执行一个原子的readmodify-write操作，并且其local cache中有read only的缓存数据（cacheline处于shared状态），这时候，CPU就会在总线上发送一个invalidate请求其他cpu清空自己的local copy，以便完成其独自霸占对该数据的所有权的梦想。同样的，该cpu必须收集所有其他cpu发来的invalidate acknowledge之后，才算完成整个bus transaction。

• Transition (f):

在本cpu独自享受独占数据的时候，其他的cpu发起read请求，希望获取数据，这时候，本cpu必须以其local cacheline的数据回应，并以read response回应之前总线上的read请求。这时候，本cpu失去了独占权，该cacheline状态从Modified状态变成shared状态（有可能也会进行写回的动作）。

• Transition (g)：

这个迁移和f类似，只不过开始cacheline的状态是exclusive，cacheline和memory的数据都是最新的，不存在写回的问题。总线上的操作也是在收到read请求之后，以read response回应。

• Transition (h)：

如果cpu认为自己很快就会启动对处于shared状态的cacheline进行write操作，因此想提前先霸占上该数据。因此，该cpu会发送invalidate敦促其他cpu清空自己的local copy，当收到全部其他cpu的invalidate acknowledge之后，transaction完成，本cpu上对应的cacheline从shared状态切换exclusive状态。还有另外一种方法也可以完成这个状态切换：当所有其他的cpu对其local copy的cacheline进行写回操作，同时将cacheline中的数据设为无效（主要是为了为新的数据腾些地方），这时候，本cpu坐享其成，直接获得了对该数据的独占权。

• Transition (i)：

其他的CPU进行一个原子的read-modify-write操作，但是，数据在本cpu的cacheline中，因此，其他的那个CPU会发送read invalidate，请求对该数据以及独占权。本cpu回送read response”和“invalidate acknowledge”，一方面把数据转移到其他cpu的cache中，另外一方面，清空自己的cacheline。

• Transition (j)：

cpu想要进行write的操作但是数据不在local cache中，因此，该cpu首先发送了read invalidate启动了一次总线transaction。在收到read response回应拿到数据，并且收集所有其他cpu发来的invalidate acknowledge之后（确保其他cpu没有local copy），完成整个bus transaction。当write操作完成之后，该cacheline的状态会从Exclusive状态迁移到Modified状态。

• Transition (k):

本CPU执行读操作，发现local cache没有数据，因此通过read发起一次bus transaction，来自其他的cpu local cache或者memory会通过read response回应，从而将该cacheline从Invalid状态迁移到shared状态。

• Transition (l)：

当cacheline处于shared状态的时候，说明在多个cpu的local cache中存在副本，因此，这些cacheline中的数据都是read only的，一旦其中一个cpu想要执行数据写入的动作，必须先通过invalidate获取该数据的独占权，而其他的CPU会以invalidate acknowledge回应，清空数据并将其cacheline从shared状态修改成invalid状态。

MESI 协议例子

OK，在理解了各种cacheline状态、各种MESI协议消息以及状态迁移的描述之后，我们从cache line数据的角度来看看MESI协议是如何运作的。开始，数据保存在memory的0地址中，随后，该数据会穿行在四个CPU的local cache中。

为了方便起见，我们让CPU local cache使用最简单的Direct-mapped的组织形式。具体的过程可以参考下面的图片：

• 最开始的时候（sequence 0），各个cpu cache中的cacheline都是Invalid状态，而Memory中的数据都保存了最新的数据。

• 随后（sequence 1），CPU 0执行了load操作，将address 0的数据加载到寄存器，这个操作使得保存0地址数据的那个cacheline从invalid状态迁移到shared状态。

• 随后（sequence 2），CPU3也对0地址执行了load操作，导致其local cache上对应的cacheline也切换到shared状态

• sequence 3中，CPU 0执行了对地址8的load操作，由于地址0和地址8都是选择同一个cache set，而且，我们之前已经说过，该cache是direct-mapped的（即每个set只有一个cacheline），因此需要首先清空该cacheline中的数据（该操作被称为Invalidation），由于cacheline的状态是shared，因此，不需要通知其他CPU。 invalidation local cache上的cacheline之后，cpu 0的load操作将该cacheline状态修改成Shared状态（保存地址8的数据）

• sequence 4 CPU 2也开始执行load操作了虽然是load操作，但是CPU知道程序随后会修改该值（不是原子操作的read-modify-write，否就是迁移到Modified状态了，也不是单纯的load操作，否则会迁移到shared状态），因此向总线发送了read invalidate命令，一方面获取该数据（自己的local cache中没有地址0的数据），另外，CPU 2想独占该数据（因为随后要write）。这个操作导致CPU 3的cacheline迁移到invalid状态。当然，这时候，memory仍然是最新的有效数据。

• Sequence5 CPU 2的store操作很快到来，由于准备工作做的比较充分（Exclusive状态，独占该数据），cpu直接修改cacheline中的数据（对应地址0），从而将其状态迁移到modified状态，同时要注意的是：memory中的数据已经失效，不是最新的数据了，任何其他CPU发起对地址0的load操作都不能从memory中读取，而是通过嗅探（snoop）的方式从CPU 2的local cache中获取。

• sequence 6中，CPU 1对地址0的数据执行原子的加1操作，这时候CPU 1会发出read invalidate命令，将地址0的数据从CPU 2的cacheline中嗅探得到，同时通过invalidate其他CPU local cache的内容而获得独占性的数据访问权。这时候，CPU 2中的cacheline状态变成invalid状态，而CPU 1将从invalid状态迁移到modified状态

• sequence 7，CPU 1对地址8进行load操作，由于cacheline被地址0占据，因此需要首先将其驱逐出cache，于是执行write back操作将地址0的数据写回到memory，同时发送read命名，从CPU 0的cache中获得数据加载其cacheline，最后，CPU1的cache变成shared状态（保存地址8的数据）。由于执行了write back操作，memory中地址0的数据又变成最新的有效数据了。

这里有个动画，来说明CPU MESI协议的工作原理 这里做个传送门MESI协议动画演示

Store Buffers

在上面的现代计算机cache结构图，我们可以看出，针对某些特定地址的数据（在一个cacheline中）重复的进行读写，这种结构可以获得很好的性能，不过，对于第一次写，其性能非常差。下面的这个图可以展示为何写性能差：

cpu 0发起一次对某个地址的写操作，但是local cache没有数据，该数据在CPU 1的local cache中，因此，为了完成写操作，CPU 0发出invalidate的命令，invalidate其他CPU的cache数据。只有完成了这些总线上的transaction之后，CPU 0才能正在发起写的操作，这是一个漫长的等待过程，
但是，其实没必要等待这么长的时间，毕竟，物理CPU 1中的cacheline保存有什么样子的数据，其实都没有意义，这个值都会被CPU 0新写入的值覆盖的。

有一种可以阻止cpu进入无聊等待状态的方法就是在CPU和cache之间增加store buffer。

注意下图，写入store buffer是单向的

一旦增加了store buffer，那么cpu0无需等待其他CPU的相应，只需要将要修改的内容放入store buffer，然后继续执行就OK了。当cacheline完成了bus transaction，并更新了cacheline的状态后，要修改的数据将从store buffer进入cacheline。

这些store buffer对于cpu而言是私有的的，多核CPU的情况下，每一个cpu拥有自己私有的stroe buffer，一个cpu只能访问自己私有的那个store buffer。

在上图中，cpu 0不能访问cpu1的store buffer，store buffer增加了CPU连续写的性能，同时把各个CPU之间的通信的任务交给维护cache一致性的协议。当然这种设计会引入了一些复杂性问题。

Store Forwarding

上文提到store buffer引入了复杂性，我们先看第一个例子：本地数据不一致的问题。我们先看看下面的代码：

1
2
3

int a = 1;
int b = a + 1;
System.out.println(b == 2)

• a和b都是初始化为0，并且变量a在CPU 1的cacheline中，变量b在CPU 0的cacheline中。

• （1） CPU 0执行a=1的赋值操作，但是load a的时候遇到了cache miss
• （2）CPU 0发送read invalidate消息想从CPU 1那里获得数据，并invalid其他cpu保存a数据的local cacheline。但是不能等回复消息，就紧接着将要写入的数据“1”放入store buffer 里
• （3）CPU 1收到read invalidate后回应，把本地cacheline的数据发送给CPU 0并清空本地cache中a的数据

• （4）CPU 0要开始执行 b = a + 1，再次之前需要load a值，此时CPU 0 收到来自CPU 1的数据，该数据是“0”，这样啊= 0 就被缓存到了cache里
• （5）CPU 0从cacheline中加载a，获得0值
• （6）此时，storebuffer里的数据写会到了cache中。 所以a值是“1”

• （7） CPU 0执行a＋1，得到1并将该值写入b
• （8）CPU 0 executes assert(b == 2)你期望b等于2，但是实际上b等于了1

导致这个问题的根本原因是我们有两个a值，一个在cacheline中，一个在store buffer中。

上面这个出错的例子之所以发生是因为它违背了一个基本的原则，即每个CPU按照其视角来观察自己的行为的时候必须是符合program order的。一旦违背这个原则，会导致一些非常不直观的软件行为，对软件工程师而言就是灾难。还好，有”好心“的硬件工程师帮助我们，修改了CPU的设计如下：

注意storebuffer 是可以进行cpu 和 cache的干预的

这种设计叫做store forwarding，当CPU执行load操作的时候，不但要看cache，还有看store buffer是否有内容，如果store buffer有该数据，那么就采用store buffer中的值。因此，即便是store操作还没有写入cacheline，store forwarding的效果看起来就好象cpu的store操作被向前传递了一样（后面的load的指令可以感知到这个store操作）。

有了store forwarding的设计，上面的步骤（5）和 （6）中就可以在store buffer获取正确的a值是”1“而不是”0“，因此计算得到的b的结果就是2，和我们预期的一致了。

如下图：

Memory Barriers

关于store buffer引入的复杂性，我们再来看看第二个例子：

1
2
3
4
5
6
7
8
9
10
11
12

int a = b = 0;
void foo(void)
{
  a = 1;
  b = 1;
}
  
void bar(void)
{
  while (b == 0) continue;
  assert(a == 1);
}

同样的，a和b都是初始化成0.我们假设CPU 0执行foo函数，CPU 1执行bar函数。我们再进一步假设a变量在CPU 1的cache中，b在CPU 0 cache中

执行的操作序列如下：

• （1）CPU 0将a值放到store buffer中之后，发送了read invalidate命令到总线上去。

• （2）CPU 1执行 while (b == 0) 循环，由于b不在CPU 1的cache中，因此 CPU1发送一个read message到总线上，看看是否可以从其他cpu的local cache中或者memory中获取数据

• （3）CPU 0继续执行b=1的赋值语句，由于b就在自己的local cache中（cacheline处于modified状态或者exclusive状态），因此CPU0可以直接操作将新的值1写入cache line。

• （4）CPU 0收到了read message，将最新的b值”1“回送给CPU 1，同时将b cacheline的状态设定为shared

• （5）CPU 1收到了来自CPU 0的read response消息，将b变量的最新值”1“值写入自己的cacheline，状态修改为shared。

• （6） CPU 1 判断b值等于1了，因此CPU 1跳出while (b == 0)的循环，继续前行。
• （7） CPU 1执行assert(a == 1)，这时候CPU 1的local cache中还是旧的a值，因此assert(a == 1)失败。
• （8）CPU 1收到了来自CPU 0的read invalidate消息，以a变量的值进行回应，同时清空自己的cacheline，但是这已经太晚了。

遇到这样的问题，CPU设计者也不能直接帮什么忙，毕竟CPU并不知道哪些变量有相关性，这些变量是如何相关的。不过CPU设计者可以间接提供一些工具让软件工程师来控制这些相关性。这些工具就是memory-barrier指令。要想程序正常运行，必须增加一些memory barrier的操作.

memory-barrier

1
2
3
4
5
6
7
8
9
10
11
12
13

int a = b = 0;
void foo(void)
{
  a = 1;
  smp_mb();
  b = 1;
}
  
void bar(void)
{
  while (b == 0) continue;
  assert(a == 1);
}

smp_mb() 这个内存屏障的操作会在执行后续的store操作之前，首先flush store buffer（也就是将之前的值写入到cacheline中）smp_mb() 操作主要是为了让数据在local cache中的操作顺序是符合program order的顺序的，为了达到这个目标有两种方法：

• CPU stall，直到完成了清空了store buffer（也就是把store buffer中的数据写入cacheline了）

• CPU可以继续运行，不过需要在store buffer中做些文章，也就是要记录store buffer中数据的顺序，在将store buffer的数据更新到cacheline的操作中，严格按照顺序执行，即便是后来的store buffer数据对应的cacheline已经ready，也不能执行操作，要等前面的store buffer值写到cacheline之后才操作。

接下来，我们再来看一下整个的运行过程：

• (1） CPU 0执行a=1的赋值操作，由于a不在local cache中，因此，CPU 0将a值放到store buffer中之后，发送了read invalidate命令到总线上去。

• （2） CPU 1执行 while (b == 0) 循环，由于b不在CPU 1的cache中，因此，CPU发送一个read message到总线上，看看是否可以从其他cpu的local cache中或者memory中获取数据

• （3） CPU 0执行smp_mb()函数，给目前store buffer中的所有项做一个标记（后面我们称之marked entries）。当然，针对我们这个例子，store buffer中只有一个marked entry就是“a=1”。

• （4）CPU 0继续执行b=1的赋值语句，虽然b就在自己的local cache中（cacheline处于modified状态或者exclusive状态），不过在store buffer中有marked entry，因此CPU0并没有直接操作将新的值1写入cache line，取而代之是b的新值”1“被写入store buffer，当然是unmarked状态。

• （5）CPU 0收到了read message，将b值”0“（新值”1“还在store buffer中）回送给CPU 1，同时将b cacheline的状态设定为shared。

• （6） CPU 1收到了来自CPU 0的read response消息，将b变量的值（”0“）写入自己的cacheline，状态修改为shared。

• （7） 完成了bus transaction之后，CPU 1可以load b到寄存器中了（local cacheline中已经有b值了），当然，这时候b仍然等于0，因此循环不断的loop。虽然b值在CPU 0上已经赋值等于1，但是那个新值被安全的隐藏在CPU 0的store buffer中。

• （8）CPU 1收到了来自CPU 0的read invalidate消息，以a变量的值进行回应，同时清空自己的cacheline。
  （9）CPU 0将store buffer中的a值写入cacheline，并且将cacheline状态修改为modified状态。
• （10） 因此，完成step 9之后，store buffer的b也可以进入cacheline了。不过需要注意的是，当前b对应的cacheline的状态是shared。因此还不能进入到cacheline里
• （11）CPU 0发送invalidate消息，请求b数据的独占权
• （12） CPU 1收到invalidate消息，清空自己的b cacheline，并回送acknowledgement给CPU 0。
• （13） CPU 1继续执行while (b == 0)，由于b不在自己的local cache中，因此 CPU 1发送read消息，请求获取b的数据。
• （14）CPU 0收到acknowledgement消息，将b对应的cacheline修改成exclusive状态，这时候，CPU 0终于可以将b的新值1写入cacheline。

• （15） CPU 1 再次执行循环，读取b的值，发现已经失效，一次你给CPU 0发了read消息， CPU 0收到read消息，将b的新值1回送给CPU 1，同时将其local cache中b对应的cacheline状态修改为shared。
• （16） CPU 1获取来自CPU 0的b的新值，将其放入cacheline中，由于b值等于1了，因此CPU 1跳出while (b == 0)的循环，继续前行。
• （17） CPU 1执行assert(a == 1)，不过这时候a值没有在自己的cacheline中，因此需要通过cache一致性协议从CPU 0那里获得，这时候获取的是a的最新值，也就是1值，因此assert成功。

通过上面的描述，我们可以看到，一个直观上很简单的给a变量赋值的操作，都需要那么长的执行过程，而且每一步都需要芯片参与，最终完成整个复杂的赋值操作过程。

Store Sequences Result in Unnecessary Stalls

Invalidate Queues

不幸的是：每个cpu的store buffer不能实现的太大，其entry的数目不会太多。当cpu以中等的频率执行store操作的时候（假设所有的store操作导致了cache miss），store buffer会很快的被填满。在这种状况下，CPU只能又进入等待状态，直到cache line完成invalidation和ack的交互之后，可以将store buffer的entry写入cacheline，从而为新的store让出空间之后，CPU才可以继续执行。这种状况也可能发生在调用了memory barrier指令之后，因为一旦store buffer中的某个entry被标记了，那么随后的store都必须等待invalidation完成，因此不管是否cache miss，这些store都必须进入store buffer。

引入invalidate queues可以缓解这个状况。store buffer之所以很容易被填充满，主要是其他CPU回应invalidate acknowledge比较慢，如果能够加快这个过程，让store buffer尽快进入cacheline，那么也就不会那么容易填满了。

invalidate acknowledge不能尽快回复的主要原因是invalidate cacheline的操作没有那么快完成，特别是cache比较繁忙的时候，这时，CPU往往进行密集的loading和storing的操作，而来自其他CPU的，对本CPU local cacheline的操作需要和本CPU的密集的cache操作进行竞争，只要完成了invalidate操作之后，本CPU才会发生invalidate acknowledge。此外，如果短时间内收到大量的invalidate消息，CPU有可能跟不上处理，从而导致其他CPU不断的等待。

然而，CPU其实不需要完成invalidate操作就可以回送acknowledgement消息，这样，就不会阻止发生invalidate请求的那个CPU进入无聊的等待状态。CPU可以buffer这些invalidate message（放入Invalidate Queues），然后直接回应acknowledgement，表示自己已经收到请求，随后会慢慢处理。当然，再慢也要有一个度，例如对a变量cacheline的invalidate处理必须在该CPU发送任何关于a变量对应cacheline的操作到bus之前完成。

Invalidate Queues and Invalidate Acknowledge

有了Invalidate Queue的CPU，在收到invalidate消息的时候首先把它放入Invalidate Queue，同时立刻回送acknowledge 消息，无需等到该cacheline被真正invalidate之后再回应。当然，如果本CPU想要针对某个cacheline向总线发送invalidate消息的时候，那么CPU必须首先去Invalidate Queue中看看是否有相关的cacheline，如果有，那么不能立刻发送，需要等到Invalidate Queue中的cacheline被处理完之后再发送。

一旦将一个invalidate（例如针对变量a的cacheline）消息放入CPU的Invalidate Queue，实际上该CPU就等于作出这样的承诺：在处理完该invalidate消息之前，不会发送任何相关（即针对变量a的cacheline）的MESI协议消息。只要是对该cacheline的竞争不是那么剧烈，CPU还是对这样的承诺很有信心的。

然而，缓存了invalidate消息也会引入一些其他的memory order的问题，我们在下一节讨论。

Invalidate Queues and Memory Barriers

我们假设CPU缓存invalidation消息，在操作cacheline之前直接回应该invalidation消息。这样的机制对于发送invalidation的CPU侧是非常好的事，该CPU的store性能会非常高，但是会使内存屏障指令失效，我们来看看下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12

void foo(void)
{
    a = 1;
    smp_mb();
    b = 1;
}

void bar(void)
{
 while (b == 0) continue;
 assert(a == 1);
}

在上面的代码片段中，我们假设a和b初值是0，并且a在CPU 0和CPU 1都有缓存的副本，即a变量对应的CPU0和CPU 1的cacheline都是shared状态。b处于exclusive或者modified状态，被CPU 0独占。我们假设CPU 0执行foo函数，CPU 1执行bar函数。

• （1） CPU 0执行a=1的赋值操作，由于a在CPU 0 local cache中的cacheline处于shared状态，因此，CPU 0将a的新值“1”放入store buffer，并且发送了invalidate消息去清空CPU 1对应的cacheline。

• （2）CPU 1执行while (b == 0)的循环操作，但是b没有在local cache，因此发送read消息试图获取该值。

• （3）CPU 1收到了CPU 0的invalidate消息，放入Invalidate Queue，并立刻回送Ack。

• （4） CPU 0收到了CPU 1的invalidate ACK之后，即可以越过程序设定内存屏障（第四行代码的smp_mb() ），这样a的新值从store buffer进入cacheline，状态变成Modified。

• （5） CPU 0 越过memory barrier后继续执行b=1的赋值操作，由于b值在CPU 0的local cache中，因此store操作完成并进入cache line。
• （6） CPU 0收到了read消息后将b的最新值“1”回送给CPU 1，并修正该cacheline为shared状态。
• （7） CPU 1收到read response，将b的最新值“1”加载到local cacheline。对于CPU 1而言，b已经等于1了，因此跳出while (b == 0)的循环，继续执行后续代码
• （9） CPU 1执行assert(a == 1)，但是由于这时候CPU 1 cache的a值仍然是旧值0，因此assertion 失败
• （10） 该来总会来，Invalidate Queue中针对a cacheline的invalidate消息最终会被CPU 1执行，将a设定为无效，但素，大错已经酿成。

很明显，在上文中的场景中，加速Invalidation response导致foo函数中的memory barrier失效了，因此，这时候对Invalidation response已经没有意义了，毕竟程序逻辑都错了。怎么办？其实我们可以让memory barrier指令和Invalidate Queue进行交互来保证确定的memory order。具体做法是这样的：当CPU执行memory barrier指令的时候，对当前Invalidate Queue中的所有的entry进行标注，这些被标注的项次被称为marked entries，而随后CPU执行的任何的load操作都需要等到Invalidate Queue中所有marked entries完成对cacheline的操作之后才能进行。因此，要想保证程序逻辑正确，我们需要给bar函数增加内存屏障的操作，具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

```java
void foo(void)
{
    a = 1;
    smp_mb();
    b = 1;
}

void bar(void)
{
 while (b == 0) continue;
 smp_mb();
 assert(a == 1);
}

具体的过程跟上述例子一样，只不过在CPU 1 执行 asserrt a == 1 的时候会有些许不同。 我们这里只列出来不同的部分，上述问题过程8 之后执行如下过程

• （9） 对于CPU 1而言，b已经等于1了，因此跳出while (b == 0)的循环，继续执行memory barrier的代码。
• （10） CPU 1现在不能继续执行代码，只能等待，直到Invalidate Queue中的message被处理完成， CPU 1处理队列中缓存的Invalidate消息，将a对应的cacheline设置为无效。
• （11） 由于a变量在local cache中无效，因此CPU 1在执行assert(a == 1)的时候需要发送一个read消息去获取a值。CPU 0用a的新值1回应来自CPU 1的请求。
• （12） CPU 1获得了a的新值，并放入cacheline，这时候assert(a == 1)不会失败了。

Read and Write Memory Barriers

在我们上面的例子中，memory barrier指令对store buffer和invalidate queue都进行了标注，不过，在实际的代码片段中，foo函数不需要mark invalidate queue，bar函数不需要mark store buffer

因此，许多CPU architecture提供了弱一点的memory barrier指令只mark其中之一。如果只mark invalidate queue，那么这种memory barrier被称为read memory barrier。相应的，write memory barrier只mark store buffer。一个全功能的memory barrier会同时mark store buffer和invalidate queue。

我们一起来看看读写内存屏障的执行效果：对于read memory barrier指令，它只是约束执行CPU上的load操作的顺序，具体的效果就是CPU一定是完成read memory barrier之前的load操作之后，才开始执行read memory barrier之后的load操作。read memory barrier指令象一道栅栏，严格区分了之前和之后的load操作。同样的，write memory barrier指令，它只是约束执行CPU上的store操作的顺序，具体的效果就是CPU一定是完成write memory barrier之前的store操作之后，才开始执行write memory barrier之后的store操作。全功能的memory barrier会同时约束load和store操作，当然只是对执行memory barrier的CPU有效。

现在，我们可以改一个用读写内存屏障的版本了，具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

void foo(void)
{
    a = 1;
    smp_wmb();
    b = 1;
}

void bar(void)
{
 while (b == 0) continue;
 smp_rmb()
 assert(a == 1);
}

总结

简单总结一下：smp_mb 包含的语义有些“重”，既包含了 Store Buffer 的 flush，又包含了 Invalidate Queue 的等待环节，但现实场景下，我们可能只需要与其中一个数据结构打交道即可。于是，CPU 的设计者把 smp_mb 屏障进一步拆分，一分为二， smp_rmb 称之为读内存屏障，smp_wmb 称之为写内存屏障。他们分别的语义也相应做了简化：

• smp_wmb(StoreStore)：执行后需等待 Store Buffer 中的写入变更 flush 完全到缓存后，后续的写操作才能继续执行，保证执行前后的写操作对其他 CPU 而言是顺序执行的；

• smp_rmb(LoadLoad)：执行后需等待 Invalidate Queue 完全应用到缓存后，后续的读操作才能继续执行，保证执行前后的读操作对其他 CPU 而言是顺序执行的；

如果没有 smp_wmb，那么 foo 方法对于别的 CPU 而言，a 与 b 赋值语句的执行顺序是不确定的，可能会导致 assert failed；如果没有 smp_rmb，那么 bar 方法对于其他 CPU 而言，b 与 a 的 读取指令的执行顺序也是不确定的，也可能会导致 assert failed。（这里做个说明，如果 当b 读取成功后，那么意味着 a 在其他的cpu已经值已经完成，那么load b 之后 在去load a 就是没问题的就会让其他CPU 告诉 a = 1 这样是没问题的，如果没有这个屏障，相当于a还是等于0，那么意味着这个cpu 是先load a的值，然后用a的值惊醒操作，在load b 之后，a = 1 已经写入内存完成，那么就产生了乱序。）

参考

• 程序优化：CPU缓存基础知识
• CPU多级缓存
• 内存屏障
• 内存屏障Memory Barrier: a Hardware View
• x86-TSO : 适用于x86体系架构并发编程的内存模型
• 从 Java 内存模型看内部细节
• 为什么在 x86 架构下只有 StoreLoad 屏障是有效指令？

• ← Previous Post
• Next Post →

赏 支付宝打赏 微信打赏

赞赏一下