内存屏障

CPU缓存

来个问题先=-=

Q：为什么加缓存？

A：因为CPU和主存的速度差异。

Q：缓存的设计是根据程序局部性原理

A：程序局部性包括时间局部性和空间局部性。

1. 时间局部性是指被访问过一次的内存位置很可能在不远的将来会被再次访问。
2. 空间局部性是指如果一个内存位置被引用过，那么它邻近的位置在不远的将来也有很大概率会被访问。

开始正题^-^

缓存是由 SRAM（静态随机存储）组成的，它的本质是一种时序逻辑电路，具体的每个单元（比特）由一个个锁存器构成，锁存器的功能就是让电路具有记忆功能。

缓存集成到芯片的方式有多种，在多核芯片上，缓存集成的方式主要有以下三种：

• 集中式缓存：一个缓存和所有处理器直接相连，多个核共享这一个缓存

• 分布式缓存：一个处理器仅和一个缓存相连，一个处理器对应一个缓存

• 混合式缓存：在 L3 采用集中式缓存，在 L1 和 L2 采用分布式缓存

越靠近 CPU 核心的缓存其访问速度越快，CPU 访问 L1 Cache 只需要 2~4个时钟周期，访问 L2 Cache 大约 10~20 个时钟周期，访问 L3 Cache 大约 20~60 个时钟周期，而访问内存速度大概在 200~300 个时钟周期之间。如下表格：

缓存的工作原理

介绍

先来学习下cache line（缓存行/缓存块），cache line 是缓存进行管理的一个最小存储单元，也叫缓存块。从内存向缓存加载数据也是按缓存块进行加载的，一个缓存块和一个内存中相同容量的数据块（下称内存块）对应。

上图中的小方框就代表一个缓存块。

整个缓存由组（set）构成，每个组由路（way）构成。所以整个缓存容量等于组数、路数和缓存块大小的乘积：

计算公式：

整个缓存容量=组数×路数×缓存块大小

简单认识

CPU Cache 的数据是从内存中读取过来的，它是以一小块一小块读取数据的，而不是按照单个数组元素来读取数据的，在 CPU Cache 中的，这样一小块一小块的数据，称为 Cache Line（缓存块）。

我们可以根据以下命令查看linux L1 Cache的缓存大小。

 ✘ penge@penge-virtual-machine  ~/Desktop/MordenCpp/tmp1  cat  /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 
64

L1 Cache 一次载入数据的大小是 64 字节。

比如，有一个 int array[100]的数组，当载入 array[0]时，由于这个数组元素的大小在内存只占 4 字节，不足 64 字节，CPU 就会顺序加载数组元素到 array[15]，意味着 array[0]~array[15] 数组元素都会被缓存在 CPU Cache 中了，因此当下次访问这些数组元素时，会直接从 CPU Cache 读取，而不用再从内存中读取，大大提高了 CPU 读取数据的性能。

读取流程

先来个问题：CPU 怎么知道要访问的内存数据，是否在 Cache 里？如果在的话，如何找到 Cache 对应的数据呢？

为了简化寻址方式，内存地址确定的数据块总是会被放在一个固定的组，但可以放在组内的任意路上，也就是说，对于一个特定地址数据的访问，它如果要载入缓存，那么它放在上图中的行数是固定的，但是具体放到哪一列是不固定的。

根据缓存中组数和路数的不同，缓存的映射方式分为三类：

• 直接相连映射：缓存只有一个路，一个内存块只能放置在特定的组上

  • 问题：对于直接相连映射，当多个内存块映射到同一组时，会产生冲突，因为只有一列，会导致缓存块被频繁替换。

• 全相连映射：缓存只有一个组，所有的内存块都放在这一个组的不同路上

  • 问题：当要查询某个缓存块时，需要逐个遍历每个路。

• 组组相连映射：缓存同时由多个组和多个路。

下面以直接相连映射举例：

对于直接映射 Cache 采用的策略，就是把内存块的地址始终「映射」在一个 CPU Line（缓存块） 的地址，至于映射关系实现方式，则是使用「取模运算」，取模运算的结果就是内存块地址对应的 CPU Line（缓存块） 的地址。

补充：我们提到 CPU 访问内存数据时，是一小块一小块数据读取的，具体这一小块数据的大小，取决于 coherency_line_size的值，一般 64 字节。在内存中，这一块的数据我们称为内存块（Bock），读取的时候我们要拿到数据所在内存块的地址。

举个例子，内存共被划分为 32 个内存块，CPU Cache 共有 8 个 CPU Line，假设 CPU 想要访问第 15 号内存块，如果 15 号内存块中的数据已经缓存在 CPU Line 中的话，则是一定映射在 7 号 CPU Line 中，因为 15 % 8的值是 7。

机智的你肯定发现了，使用取模方式映射的话，就会出现多个内存块对应同一个 CPU Line，比如上面的例子，除了 15 号内存块是映射在 7 号 CPU Line 中，还有 7 号、23 号、31 号内存块都是映射到 7 号 CPU Line 中。

因此，为了区别不同的内存块，在对应的 CPU Line 中我们还会存储一个组标记（Tag）。这个组标记会记录当前 CPU Line 中存储的数据对应的内存块，我们可以用这个组标记来区分不同的内存块。

除了组标记信息外，CPU Line 还有两个信息：

• 一个是，从内存加载过来的实际存放数据（Data）。
• 另一个是，有效位（Valid bit），它是用来标记对应的 CPU Line 中的数据是否是有效的，如果有效位是 0，无论 CPU Line 中是否有数据，CPU 都会直接访问内存，重新加载数据。

CPU 在从 CPU Cache 读取数据的时候，并不是读取 CPU Line 中的整个数据块，而是读取 CPU 所需要的一个数据片段，这样的数据统称为一个字（Word）。那怎么在对应的 CPU Line 中数据块中找到所需的字呢？答案是，需要一个偏移量（Offset）。

因此，一个内存的访问地址，包括组标记、CPU Line 索引、偏移量这三种信息，于是 CPU 就能通过这些信息，在 CPU Cache 中找到缓存的数据。而对于 CPU Cache 里的数据结构，则是由索引 + 有效位 + 组标记 + 数据块组成。

如果内存中的数据已经在 CPU Cahe 中了，那 CPU 访问一个内存地址的时候，会经历这 4 个步骤：

1. 根据内存地址中索引信息，计算在 CPU Cahe 中的索引，也就是找出对应的 CPU Line 的地址；
2. 找到对应 CPU Line 后，判断 CPU Line 中的有效位，确认 CPU Line 中数据是否是有效的，如果是无效的，CPU 就会直接访问内存，并重新加载数据，如果数据有效，则往下执行；
3. 对比内存地址中组标记和 CPU Line 中的组标记，确认 CPU Line 中的数据是不是我们要访问的内存数据，如果不是的话，CPU 就会直接访问内存，并重新加载数据，如果是的话，则往下执行；
4. 根据内存地址中偏移量信息，从 CPU Line 的数据块中，读取对应的字。

程序优化

如果下次访问内存时，数据已经在缓存中了，这就是缓存命中，它获取目标数据的速度非常快。如果数据没在缓存中，这就是缓存缺失，此时要启动内存数据传输，而内存的访问速度相比缓存差很多。

下面，将举出一些和缓存相关的例子，加深在程序上面的应用。

例子

int a[N][N];
// pro1:
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		a[i][j]++;
	}
}
// pro2:
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		a[j][i]++;
	}
}

显然，pro1的执行时间更短，也就是我们常常说的程序局部一致性原理。

为什么pr2的性能不够好呢？

原因：主要原因是当按行访问时地址是连续的，下次访问的元素和当前大概率在同一个 cache line（一个元素 8 字节，而一个 cache line 可以容纳 8 个元素），但是当按列访问时，由于地址跨度大，下次访问的元素基本不可能还在同一个 cache line，因此就会增加 cache line 被替换的次数，所以性能劣化。

例子2

伪共享（false-sharing）的意思是说，当两个线程同时各自修改两个相邻的变量，由于缓存是按缓存块来组织的，当一个线程对一个缓存块执行写操作时，必须使其他线程含有对应数据的缓存块无效。这样两个线程都会同时使对方的缓存块无效，导致性能下降。

#include <stdio.h>
#include <pthread.h>
 
struct S{
   long long a;
   long long b;
} s;
void *thread1(void *args){
    for(int i = 0;i < 100000000; i++){
        s.a++;
    }
    return NULL;
} 
void *thread2(void *args){
    for(int i = 0;i < 100000000; i++){
        s.b++;
    }
    return NULL;
}
int main(int argc, char *argv[]) {
    pthread_t t1, t2;
    s.a = 0;
    s.b = 0;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("a = %lld, b = %lld\n", s.a, s.b);
    return 0;
}

在这个例子中，main 函数中创建了两个线程，分别修改结构体 S 中的 a 、b 变量。a 、b 均为 long long 类型，都占 8 字节，所以 a 、b 在同一个 cache line 中，因此会发生为伪共享的情况。

根据上述知识，知道解决伪共享的办法是，将 a 、b 不要放在同一个 cache line，这样两个线程分别操作不同的 cache line 不会相互影响。

将结构体修改成

struct S{
   long long a;
   long long nop_0;
   long long nop_1;
   long long nop_2;
   long long nop_3;
   long long nop_4;
   long long nop_5;
   long long nop_6;
   long long nop_7;
   long long b;
} s;

因为在 a、b 中间插入了 8 个 long long 类型的变量，中间隔了 64 字节，所以 a、b 会被映射到不同的缓存块。

分别运行上述的程序，具体运行时间如下所示：

penge@penge-virtual-machine  ~/Desktop/MordenCpp/tmp1  ./main                        
a = 100000000, b = 100000000
520934.0000000000%
penge@penge-virtual-machine  ~/Desktop/MordenCpp/tmp1  g++ example.c -o main -pthread
penge@penge-virtual-machine  ~/Desktop/MordenCpp/tmp1  ./main                        
a = 100000000, b = 100000000
342973.0000000000%   

缓存一致性协议MESI

基本术语

缓存和内存的更新策略

• 写回 （ Write Back）：对缓存的修改不会立刻传播到主存，只有当缓存块被替换时，这些被修改的缓存块，才会写回并覆盖内存中过时的数据

• 写直达 （Write Through）：缓存中任何一个字节的修改，都会立刻传播到内存

写缓存时 CPU 之间的更新策略

• 写更新（Write Update）：如果 CPU 采取写更新策略，每次它的缓存写入新的值，该 CPU 都必须发起一次总线请求，通知其他 CPU 将它们的缓存值更新为刚写入的值，所以写更新会很占用总线带宽。
• 写无效（Write Invalidate）：如果在一个 CPU 修改缓存时，将其他 CPU 中的缓存全部设置为无效

从写缓存时数据是否被加载

• 写分配（Write Allocate）：在写入数据前将数据读入缓存
• 写不分配（Not Write Allocate）：在写入数据时，直接将要写入的数据传播内存，而并不将数据块读入缓存

开始正题：

Q：为什么要设计这个协议呢？

A：因为当多核CPU对缓存数据进行读写操作的时候，导致不一致性。因此引入这个协议保证不让系统数据混乱。

MESI 是指4中状态的首字母。每个Cache line有4个状态，可用2个bit表示，它们分别是：

缓存行（Cache line）:缓存存储数据的单元。

状态	描述	监听任务
M 修改 (Modified)	该Cache line有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中。	缓存行必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S（共享）状态之前被延迟执行。
E 独享、互斥 (Exclusive)	该Cache line有效，数据和内存中的数据一致，数据只存在于本Cache中。	缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S（共享）状态。
S 共享 (Shared)	该Cache line有效，数据和内存中的数据一致，数据存在于很多Cache中。	缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。
I 无效 (Invalid)	该Cache line无效。	无

MESI状态转换

触发事件：

各个状态转移情况

• M状态

• E状态

• S状态

• I状态

总结

MESI协议：当CPU写数据(M)时，如果发现操作的变量是共享变量(s) ，会发出信号通知其他CPU将该变量的缓存行置为无效状态(1) ，因此当其他CPU需要读取这个变量时，发现自己缓存中缓存该变量的缓存行是无效的，那么它就会从内存重新读取，确保一致性。

内存模型

在上面的章节我们学习到，在 Share 状态下，如果一个核想独占缓存进行修改，就需要先给所有 Share 状态的同伴发出 Invalid 消息，等所有同伴确认并回复它“Invalid acknowledgement”以后，它才能把这块缓存的状态更改为 Modified，这是保持多核信息同步的必然要求。但是这个过程是很耗费时间的。【简单来说，一个CPU每次的修改都要等待另外的CPU的确认信息，这是比较耗费时间的】

那就继续优化！！！

写缓冲与写屏障

CPU 的设计者为每个核都添加了一个名为 store buffer 的结构，store buffer 是硬件实现的缓冲区，它的读写速度比缓存的速度更快，所有面向缓存的写操作都会先经过 store buffer。

增加了 store buffer 以后的 CPU 缓存结构

这里，如果 CPU 的某个核再要对一个变量进行赋值，它就不必等到所有的同伴都确认完，而是直接把新的值放入 store buffer，然后再由 store buffer 慢慢地去做核间同步，并且将新的值刷入到 cache 中去就好了。而且，每个核的 store buffer 都是私有的，其他核不可见。

但是有个Bug：就是它并不能保证变量写入缓存和主存的顺序。

来个看经典的例子：

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

在这个代码块中，CPU0 执行 foo 函数，CPU1 执行 bar 函数。但在对变量 a 和 b 进行赋值的时候，有两种情况会导致它们的赋值顺序被打乱。

第一种情况是 CPU 的乱序执行。可能会b先执行，然后再执行a。这是因为CPU 为了提升运行效率和提高缓存命中率，采用了乱序执行。

第二种情况是 store buffer 在写入时，有可能 b 所对应的缓存行会先于 a 所对应的缓存行进入独占状态，也就是说 b 会先写入缓存。【store buffer将变量放进缓存的顺序不一致】

简单来说就是因为Store Buffer的存在，最后结果不确定。

1. a的值可能因为是Share（共享）先被写入了Store Buffer，并发送通知其他cpu置为Invalid(失效)。
2. b的值，可能因为在cache中已经存在并且是Exclusive（独占）直接被写进cache中。
3. 读取的时候因为先读b的值，b被刷进主存供读取。
4. 后面要读a，因为还没收到失效通知，从cache中直接拿到a，断言失败。

为此，CPU 设计者就引入了内存屏障，屏障的作用是前边的读写操作未完成的情况下，后面的读写操作不能发生。

来看看加了内存屏障的代码

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

smp_mb 就代表了多核体系结构上的内存屏障。由于在不同的体系结构上，指令各不相同，我们使用一个函数对它进行封装。加上这一道屏障以后，CPU 会保证 a 和 b 的赋值指令不会乱序执行，同时写入 cache 的顺序也与程序代码保持一致。

所以说，内存屏障保证了，其他 CPU 能观察到 CPU0 按照我们期望的顺序更新变量。

总的来说，store buffer 的存在是为提升写性能，放弃了缓存的顺序一致性，我们把这种现象称为弱缓存一致性。

失效队列与读屏障

上述过程中还存在问题，当一个 CPU 向同伴发出 Invalid 消息的时候，它的同伴要先把自己的缓存置为 Invalid，然后再发出 acknowledgement。这个从“把缓存置为 Invalid”到“发出 acknowledgement”的过程所需要的时间也是比较长的。由于 store buffer 的存在提升了写入速度，那么 invalid 消息确认速度相比起来就慢了，这就带来了速度的不匹配。很容易导致 store buffer 的内容还没有及时更新到 cache 里，自己的容量就被撑爆了，从而失去了加速的作用。

为此，引入了失效队列（invalid queue）。

失效队列工作流程：收到 Invalid 消息的 CPU，比如我们称它为 CPU1，在收到 Invalid 消息时立即向 CPU0 发回确认消息，但这个时候 CPU1 并没有把自己的 cache 由 Share 置为 Invalid，而是把这个失效的消息放到一个队列中，等到空闲的时候再去处理失效消息，这个队列就是 invalid queue。

运行上面增加内存屏障的代码，第 11 行的断言又可能失败了。

核心0 中 a 所对应的缓存行是 S 状态，b 所对应的缓存行是 E 状态；核心1中 a 所对应的缓存行是 S 状态，b 所对应的缓存行是 I 状态；

• 因为有内存屏障在，a 和 b的写入缓存的顺序不会乱。
• a 先向其他核心发送 Invalid 消息，并且等待 Invalid 确认消息；
• Invalid 消息先入 核心1 对应的 Invalid Queue 并立刻返回确认消息，等待 核心1 处理；
• 核心0 收到确认消息后把 a 写入缓存，继续处理 b 的写入，由于 b 是 E 状态，直接写入缓存；
• 核心1 发送 BusRd 消息，读取到新的 b 值，然后获取 a（S 状态）值是0，因为使其无效的消息还在 Invalid Queue 中，第 11 行断言失败。

引入 Invalid Queue 后，对核心1 来说看到的 a 和 b 的写入又出现乱序了。

解决办法是继续加内存屏障，核心1 想越过屏障必须清空 Invalid Queue，及时处理了对 a 的无效，然后读取到新的 a 值，如下代码：

int a = 0, b = 0;
// CPU0
void foo() {
    a = 1;
    smp_mb();
    b = 1;
}
// CPU1
void bar() {
    while (b == 0) continue;
    smp_mb(); //继续加内存屏障
    assert(a == 1);
}

这里使用的内存屏障是全屏障，包括读写屏障，过于严格了，会导致性能下降，所以有了细粒度的读屏障和写屏障。

读写屏障分离

完全遵守MESI协议CPU性能下降，但是增加了这两个队列就无法保证一致性。

分离的写屏障和读屏障的出现，是为了更加精细地控制 Store Buffer 和 Invalid Queue 的顺序。

也就是说

• 写屏障之前的写操作一定会比之后的写操作先写到缓存中。
• 屏障前后的读操作都不能翻过屏障。

【store buffer写进缓存顺序写，失效队列消费完成了再读】

优化前面的代码如下

int a = 0, b = 0;
// CPU0
void foo() {
    a = 1;
    smp_wmb(); //写屏障
    b = 1;
}
// CPU1
void bar() {
    while (b == 0) continue;
    smp_rmb(); //读屏障
    assert(a == 1);
}

注意，这种修改只有在区分读写屏障的体系结构里才会有作用，比如 alpha 结构。而在 X86 和 Arm 中是没有作用的，这是因为 X86 采用的 TSO 模型不存在缓存一致性的问题，而 Arm 则是采用了另一种称为单向屏障的分类方式。

单向屏障

单向屏障 (half-way barrier) 也是一种内存屏障，但它不是以读写来区分的，而是像单行道一样，只允许单向通行，例如 ARM 中的 stlr 和 ldar 指令就是这样。

• stlr 的全称是 store release register，包括 StoreStore barrier 和 LoadStore barrier（场景少），通常使用 release 语义将寄存器的值写入内存；
• ldar 的全称是 load acquire register，包括 LoadLoad barrier 和 LoadStore barrier（对，你没看错，我没写错），通常使用 acquire 语义从内存中将值加载入寄存器；
• release 语义的内存屏障只不允许其前面的读写向后越过屏障，挡前不挡后；
• acquire 语义的内存屏障只不允许其后面的读写向前越过屏障，挡后不挡前;
• StoreLoad barrier 就只能使用 dmb（全屏障） 代替了。

参考资料

• CPU Cache Line：CPU缓存行/缓存块
• 缓存一致性协议MESI
• 全知乎最详细的并发研究之CPU缓存一致性协议(MESI)有这一篇就够了！
• [金阶之路：内存屏障（Memory Barriers）](金阶之路：内存屏障（Memory Barriers） - 知乎 (zhihu.com))
• 《极客时间》