文章

整理：内存一致模型

发表于 更新于
作者 Roderick.Huang 9 分钟阅读

1. CPU Cache 内部结构

CPU structure

一个core内部结构：

  • cache
  • store buffer
  • invalidate queue

结构如下图所示：

CPU cache structure

1.1. Cahce一致性协议 MESI

MESI是CPU内部多个core同步通讯协议，保证多个core中的cache的数据一致性。MESI这四个字母分别代表了每一个cache line可能处于的四种状态：Modified、Exclusive、Shared 和 Invalid。

通过给cache line设置状态位，以及CPU core（也可能有内存控制器参与）之间的消息同步逻辑，让多个core中的cache数据保持一致性。

在没有store buffer, invalidate queue之前，MESI可以保证不需要memory fence指令也可以保证数据的一致性。

1.2. False sharing

False sharing的原因是两个CPU访问的变量，在内存中的位置，同时落入一个cache line范围内，根据MESI协议，一个CPU写操作，将导致另一个CPU的读写操作之前，需要进行memory及两个CPU的cache line同步操作。通常发生在两个线程操作同一个数据结构体的时候。

false sharing

1
2
3
4
5
6
7
8
9

#define CACHE_ALIGN_SIZE 64
#define CACHE_ALIGNED __attribute__((aligned(CACHE_ALIGN_SIZE)))

struct aligned_value {
  int64_t val;
} CACHE_ALIGNED; // Note: aligning the struct to a cache line size
aligned_value aligned_data[2] CACHE_ALIGNED;

// sizeof(aligned_value) == 128

1.3. 现代CPU上MESI的局限

由于MESI同步协议导致处理器之间同步的代价很高，现代处理器再每个core里面增加两个异步队列: store buffer和invalidate queue来减少CPU的空闲等待。这两个异步队列，导致MESI协议失效。

  • store buffer: CPU将write/store操作数据放入store buffer，cache负责flush操作。
  • invalidate queue: cache收到Invalidate消息，不是马上执行，而是放入invalidate queue，等待CPU空闲时，再执行。

其原因是：针对发起方CPU，其认为自己的store / invalidate操作已经完成，但是由于数据/消息是放在store buffer / invalidate queue中，所以可能还没来得及被其他CPU看到，导致数据不一致。

其中的一个解决办法是：发起方的store buffer被清空，接收方的invalieate queue被处理掉。在此之后，MESI协议可以正常工作。

2. memory barrier

2.1. 概念及理论

  • 同步点：针对同一个原子变量的load操作与store操作，分别构成一个同步点。其概念有三要素：(1)：load/store操作，(2)：针对同一个原子变量，(3)：以及在不同线程中；
  • synchronize-with 关系，该概念包含两个含义：(1)：同一个同步点，(2)：读取的值是另一个同步点写入的值；
  • happens-before 关系；

memory fence定义的是同步点操作，即分别在store一方插入一个write barrier指令，在load一方插入一个read barrier指令。

因此，memory barrier需要成对出现，否则达不到同步效果。

2.2. 详细解释

由于多核处理器 CPU 之间独立的L1/L2 cache，会出现cache line不一致的问题，为了解决这个问题，有相关协议模型，比如 MESI 协议来保证 cache 数据一致，同时由于 CPU 对 MESI 进行的异步优化，对写和读分别引入了「store buffer」和「invalid queue」，很可能导致后面的指令查不到前面指令的执行结果（各个指令的执行顺序非代码执行顺序），这种现象很多时候被称作「CPU乱序执行」。

为了解决乱序问题（也可以理解为可见性问题，修改完没有及时同步到其他的CPU），又引出了「内存屏障」的概念；内存屏障可以分为三种类型：写屏障，读屏障以及全能屏障（包含了读写屏障），屏障可以简单理解为：在操作数据的时候，往数据插入一条特殊的指令。只要遇到这条指令，那前面的操作都得「完成」。

  1. 写屏障指令(write barrier, or sfence)，等待之前的写操作完成，并把该指令「之前」存在于「store Buffer」中的所有写指令刷入cache。就可以让CPU修改的数据马上暴露给其他CPU(MESI)，达到「写操作」可见性的效果。

  2. 读屏障指令(read barrier, or lfence)，会把该指令「之前」存在于「invalid queue」中的所有的指令都处理掉。通过这种方式就可以确保当前CPU的缓存状态是准确的，达到「读操作」一定是读取最新的效果。

由于不同CPU架构的缓存体系不一样、缓存一致性协议不一样、重排序的策略不一样、所提供的内存屏障指令也有差异，所以一些语言c++/java/go/rust 都有实现自己的内存模型, 比如golang大牛Russ Cox写的内存模型系列文章 Memory Models 值得深入了解。

2.3. x86上面的fence实操演示

ARM架构CPU有Store Buffer、Invalidate Queue，是一个松散内存一致性模型。x86架构只有Store Buffer，是一个强内存一致性模型。

在x86架构下，对StoreLoad操作进行重排(乱序)。其余几种保持顺序：StoreStore, LoadLoad, LoadStore，即不需要设置fence指令也可以保持CPU之间的内存一致性。

禁止编译器重排：

1
2
3

X = 1;
asm volatile("" ::: "memory"); // Prevent compiler reordering
r1 = Y;

禁止编译器及CPU重排：

1
2
3

X = 1;
asm volatile("mfence" ::: "memory"); // Prevent compiler and CPU reordering
r1 = Y;

详细知识参考：

3. C++11 内存一致性模型定义

内存一致性模型作用
memory_order_release作用于store操作。约束：本线程在此操作之前的所有R/W操作，均不能重排到此操作之后。故其他线程中acquire操作之后，可以看见本线程中本操作之前的所有写入操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <thread>
#include <atomic>
#include <cassert>
#include <string>

std::atomic<std::string*> ptr{nullptr};
int data{42};

void producer() {
  std::string* p  = new std::string("Hello");
  data = 42;
  ptr.store(p, std::memory_order_release);
}

void consumer() {
  std::string* p2;
  while (nullptr == (p2 = ptr.load(std::memory_order_acquire)));
  assert(*p2 == "Hello"); // never fires
  assert(data == 42); // never fires
}

int main() {
  std::thread t1(producer);
  std::thread t2(consumer);
  t1.join(); t2.join();
  return 0;
}

更多资料

cpp
cpp cpu
本文由作者按照 CC BY 4.0 进行授权