Colderleo's blog
gaoliu
2021-10-06
目录

memory order 内存模型

# 缓存一致性协议MESI

参考： https://zhuanlan.zhihu.com/p/123926004 (opens new window)

不同CPU对cache的读写是一致的，cache可以当做我们平时说的内存，通过缓存一致性协议保证一致。

不同cpu拥有各自的cache，cache读写的最小单位是cache line，一般是64字节。多个cache与内存之间的数据同步该怎么做？缓存一致性协议就是要解决这个问题，协议有多种，可以分为两类：“窥探（snooping）”协议和“基于目录的（directory-based）”协议，MESI协议属于一种“窥探协议“。

cache line的四种状态：

  • Invalid，表明该cache line已失效，它要么已经不在cache中，要么它的内容已经过时。处于该状态下的cache line等同于它从来没被加载到cache中。
  • Shared，表明该cache line是内存中某一段数据的拷贝，处于该状态下的cache line只能被cpu读取，不能写入，因为此时还没有独占。不同cpu的cache line都可以拥有这段内存数据的拷贝。
  • Exclusive，和 Shared 状态一样，表明该cache line是内存中某一段数据的拷贝。区别在于，该cache line独占该内存地址，其他处理器的cache line不能同时持有它，如果其他处理器原本也持有同一cache line，那么它会马上变成“Invalid”状态。
  • Modified，表明该cache line已经被修改，cache line只有处于Exclusive状态才能被修改。此外，已修改cache line如果被丢弃或标记为Invalid，那么先要把它的内容回写到内存中。

我们发现，cpu有读取数据的动作，有独占的动作，有独占后更新数据的动作，有更新数据之后回写内存的动作，根据”窥探协议“的规范，每个动作都需要通知到其他cpu，于是有以下的消息机制：

  • Read，cpu发起读取数据请求，请求中包含需要读取的数据地址。
  • Read Response，作为Read消息的响应，该消息可能是内存响应的，也可能是某cpu响应的(比如该地址在某cpu cache Line中为Modified状态，则该cpu必须返回该地址的最新数据)。
  • Invalidate，cpu发起”我要独占一个cache line，其他cpu请失效对应的cache line“的消息，消息中包含了内存地址，所有的其它cpu需要将对应cache line置为Invalid状态。
  • Invalidate ACK，收到Invalidate消息的cpu在将对应cache line置为Invalid后，返回Invalid ACK。
  • Read Invalidate，相当于Read消息+Invalidate消息，即取得数据并且独占它，将收到一个Read Response和所有其它cpu的Invalidate ACK。
  • Write back，写回消息，即将状态为Modified的cache line写回到内存，通常在该行将被替换时使用。现代cpu cache基本都采用”写回(Write Back)”而非”直写(Write Through)”的方式。

在MESI协议下工作即可保证各cpu之间的cache一致。不过cpu如果每次访问数据cache都经过MESI协议，太慢了，于是又增加了store buffer和invalid queue来加速。

# sotre buffer和invalid queue

参考： https://zhuanlan.zhihu.com/p/125549632 (opens new window)

# store buffer

img

每个cpu内部增加一个store buffer，写数据的时候先写到store buffer里，其他cpu看不到。等需要的时候再写到cache line中，同时通知其他cpu，使该cache line的内容对其他cpu可见。

程序员可以手动增加 Store Barrior 来将数据从store buffer刷到cache line中，从而使该数据对其他线程可见。

# invalid queue

但是仅有store buffer还不够，因为store buffer比较小，很容易满。当需要写到cache line的时候要通知其他cpu这个cache line invalid了，然后等所有cpu回复invalid ack，才能继续往下走。其他cpu回复invalid ack之前要把对应的cache line状态改为invaid，这个操作比较耗时。怎么办呢，就是增加一个invalid queue。cpu在收到invalid消息时，把它放进invalid queue中，然后就回复invalid ack了，而invalid queue可以后续处理。

程序员可以手动增加 Load Barrier 将invalid queue中的数据读入cache line，从而获取其他线程对数据的修改。

# 编译器屏障和内存屏障

# 参考：

https://zhuanlan.zhihu.com/p/43526907 (opens new window)

# 编译器屏障

阻止编译器重排，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行，并且不可以从寄存器中取变量。 （注意该指令只会对编译器产生影响，并不能阻值cpu乱序执行。下面有cpu内存屏障的说明）

#define barrier() __asm__ __volatile__("": : :"memory")
1

# cpu屏障

img

Intel提供三种内存屏障指令：

  • sfence ，实现Store Barrior 会将store buffer中缓存的修改刷入L1 cache中，使得其他cpu核可以观察到这些修改，而且之后的写操作不会被调度到之前，即sfence之前的写操作一定在sfence完成且全局可见；

  • lfence ，实现Load Barrior 会将invalidate queue失效，强制读取入L1 cache中，而且lfence之后的读操作不会被调度到之前，即lfence之前的读操作一定在lfence完成（并未规定全局可见性）；

  • mfence ，实现Full Barrior 同时刷新store buffer和invalidate queue，保证了mfence前后的读写操作的顺序，同时要求mfence之后写操作结果全局可见之前，mfence之前写操作结果全局可见；

  • lock 用来修饰当前指令操作的内存只能由当前CPU使用，若指令不操作内存仍然有用，因为这个修饰会让指令操作本身原子化，而且自带Full Barrior效果；还有指令比如IO操作的指令、exch等原子交换的指令，任何带有lock前缀的指令以及CPUID等指令都有内存屏障的作用。

GNU中的三种内存屏障定义方法，结合了编译器屏障和三种CPU屏障指令：

#define lfence() __asm__ __volatile__("lfence": : :"memory") 
#define sfence() __asm__ __volatile__("sfence": : :"memory") 
#define mfence() __asm__ __volatile__("mfence": : :"memory")
1
2
3

C++11为内存屏障提供了专门的函数std::atomic_thread_fence，方便移植统一行为而且可以配合内存模型进行设置，比如实现Acquire-release语义。原子变量的使用相当于附带了该功能。

#include <atomic>
std::atomic_thread_fence(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acquire);
std::atomic_thread_fence(std::memory_order_release);
std::atomic_thread_fence(std::memory_order_seq_cst);
1
2
3
4
5

# x86上简单总结

读写内存顺序有4种组合: LoadLoad(对应C++11的Acquire memory order) StoreStore(对应C++11的Release memory order)、 LoadStore、 StoreLoad。对于x86来说，只有StoreLoad才可能出现问题，另外三种都是保证顺序的。

因此对于编译器屏障，只需要用std::atomic_thread_fence(std::memory_order_relaxed) 对于cpu屏障，只需要用std::atomic_thread_fence(std::memory_order_seq_cst)

# C++ Memory Order

# 参考

如何理解 C++11 的六种 memory order： https://www.zhihu.com/question/24301047/answer/1193956492 (opens new window)

# 什么是原子操作、什么是Memory Order

原子操作就是对一个内存上变量（或者叫左值）的读取-变更-存储（load-add-store）作为一个整体一次完成。 （即上文中的从cache line读写是一个整体）

各种memory order是对本线程上下文的约束（包括普通变量）。对于relaxed操作，就是只有自身是atomic，不约束上下文。

比如 memory_order_release:

atomic<int> a;
a.store(1, memory_order_release);

// 等同于下面的操作 再加一个编译器屏障：
a.store(1, memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_release);
1
2
3
4
5
6

其效果是，把cpu的 store buffer 里面的内容 release 到cache中，让其他线程可以看到。（主要是release上下文中的普通变量，因为atomic变量总会release）

# 读写关系举例

C++里的memory order是用来指定原子操作（atomic operation）和同线程内其他非原子操作之间的执行顺序的。

# Sequential Consistency

memory_order_seq_cst，即顺序一致性模型。

# Acquire-Release 模式

memory_order_release前面不会被reorder到本句之后；memory_order_acquire之后的代码不会被reorder到本句之前；memory_order_acq_rel同时包含acquire和release标志。

对x86来说，这两种内存序都是自动保证的，用memory_order_relaxed做一个编译器屏障就可以了。对Arm则需要使用acquire和release做保障。

#include <thread>
#include <chrono>
#include <mutex>
#include <thread>
#include <assert.h>
#include <atomic>

int a=0, b=0;
std::atomic<int> s = 0;

void t1_fun() {
    a = 1;
    s.store(9, std::memory_order_release); //除了s本身store， 上文中a的修改也被release到cache(memory)中
}
void t2_fun() {
    while (s.load(std::memory_order_acquire) != 9) {
        continue;
    }; //除了读取s， 也从cache(memory)读取a的值。
    assert(a == 1); //一定成功
}
int main() {
    std::thread t1(t1_fun);
    std::thread t2(t2_fun);
    t1.join();
    t2.join();
}
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

# Relaxed模式

松散的，不约束上下文其他变量的重排。对于一个atomic<int> a; relaxed是它对别人relaxd，对自己是atomic的，一个atomic操作包括从cache line中读取、修改、写入这一套是不被分割的。

有文章说 “memory_order_relaxed: 只保证当前操作的原子性，不考虑线程间的同步，其他线程可能读到新值，也可能读到旧值。比如 C++ shared_ptr 里的引用计数，我们只关心当前的应用数量，而不关心谁在引用谁在解引用。” 这个说法有问题。一个atomic变量写时用relaxed，其他线程中读或者修改时会读到新值，因为atomic relax写时会写到cache line，另一个线程用atomic读时也会从cache line读。

# Release-Consume 模式

参考: https://blog.csdn.net/netyeaxi/article/details/80718781 (opens new window)

memory_order_consume，可以被安全的替换为memory_order_acquire。 在一个线程release后，另一个线程可以通过consume获取。与acquire不同的是，它只获取与该原子变量有相关依赖的变量。

然而实际上gcc貌似并没有实现该特性，所以没有必要的话先使用memory_order_acquire吧。另外x86上memory_order_acquire是自动保证的，用relaxed就可以。

# intel x86 Memory Order

评论里有很多关于x86内存模型的指正，放在这里：（英特尔的官方文档可查）

Loads are not reordered with other loads.Stores are not reordered with other stores.Stores are not reordered with older loads.

然后最重要的：

Loads may be reordered with older stores to different locations.

因为 store-load 可以被重排，所以x86不是顺序一致。但是因为其他三种读写顺序不能被重排，所以x86是 acquire/release 语义。

aquire语义：load 之后的读写操作无法被重排至 load 之前。即 load-load, load-store 不能被重排。

release语义：store 之前的读写操作无法被重排至 store 之后。即 load-store, store-store 不能被重排。

最简单的试试 relaxed ordering 的方法就是拿出手机。写个小程序，故意留个 race condition，然后放到 iPhone 或者安卓手机上调，不用 release -- acquire 保准出错。然而这种 bug 你在 x86 的 host 机上是调不出来的，即便拿模拟器也调不出来。

（貌似x86的Sotre Buffer是FIFO，所以store-store不能被重排）

# 常见内存模型（类似于设计模式）

  • 参考: https://www.cnblogs.com/miaolong/p/12574481.html (opens new window)
  • Sequential Consistency 顺序一致性，简称SC
  • Total Store Ordering, 全存储排序，简称TSO
  • Relaxed memory models，松弛型内存模型
  • 还有一些其他的各种各样的内存模型： Processor Consistency、Partial Consistency Ordering (PSO)、Weak Consistency、Release Consistency、Data-Race-Free-0 等待

# C内嵌汇编实现cpu内存屏障（x86）

c语言内嵌汇编的语法格式：

__asm__　__volatile__("Instruction List" : Output : Input : Clobber/Modify);
1

cpu内存屏障的实现方法:

#define barrier() do { __asm__ __volatile__("lock"; addl $0 0(%%esp)" ::: "cc", "memory"); } while(0)
1
  • lock会对被指令操作的数据地址上总线锁或缓存锁，并使该指令的执行变成原子操作，并且前后的指令都不能越过lock重排（阻止cpu乱序执行）；
  • addl $0 0(%%esp)的含义是将栈顶加0，相当于空指令，这是因为lock语法不允许在后面写空指令；
  • "cc", "memory" cc表示修改了寄存器；memory表示修改了内存；

汇总

//编译器屏障，防止编译器重排优化，（只在编译器层面，并不会对cpu的执行有影响）。
#define mem_barrier() do { __asm__ __volatile__("": : :"memory"); } while(0)


//cpu内存屏障， 防止cpu乱序，兼具编译器屏障的作用。
#define cpu_barrier() do { __asm__ __volatile__("lock"; addl $0 0(%%esp)" ::: "cc", "memory"); } while(0)


//读写某个变量的内存。  =表示输出， m表示memory中的变量（只在编译器层面防止重排）
#define memory_read(var) do { __asm__ __volatile__("" : "=m"(var) : : ); } while(0)
#define memory_write(var)  do { __asm__ __volatile__("" :  : "m"(var) : ); } while(0)


//原子操作, 防止多线程竞争
static inline void atomic64_add(origin, dst, value) {
    __asm__ __volatile__(
        "lock"; addl $0 0(%%esp)" 
        : "=r"(origin), "+m"(dst)
        : 未完待续
        : "cc", "memory");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 测试上面的 memory_read 和 memory_write:

#define memory_read(var) do { asm volatile("" : "=m"(var) : : ); } while(0) #define memory_write(var) do { asm volatile("" : : "m"(var) : ); } while(0)

# c代码

example1.c：

int main(int __argc, char* __argv[])
{
    int* __p = (int*)__argc;
    (*__p) = 9999;

    //__asm__ volatile("":::"memory");

    if((*__p) == 9999)
        return 5;

    return (*__p);
}
1
2
3
4
5
6
7
8
9
10
11
12

O3编译， 并查看汇编结果：

gcc -O3 -S example1.c
cat example1.s
1
2

# 不带编译器屏障

//__asm__ volatile("":::"memory");

main:
.LFB0:
        .cfi_startproc
        movslq  %edi, %rdi
        movl    $5, %eax
        movl    $9999, (%rdi)
        ret
        .cfi_endproc
1
2
3
4
5
6
7
8
9
10

# 带编译器屏障

__asm__ volatile("":::"memory");

$ cat example1.s
main:
.LFB0:
        .cfi_startproc
        movslq  %edi, %rdi
        movl    $9999, (%rdi)
        movl    (%rdi), %eax
        movl    $5, %edx
        cmpl    $9999, %eax
        cmove   %edx, %eax
        ret
        .cfi_endproc
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 带上memory_read，和编译器屏障效果一样

__asm__ volatile("":"=m"(*__p)::);

main:
.LFB0:
        .cfi_startproc
        movslq  %edi, %rdi
        movl    (%rdi), %eax
        movl    $5, %edx
        cmpl    $9999, %eax
        cmove   %edx, %eax
        ret
        .cfi_endproc
1
2
3
4
5
6
7
8
9
10
11
12

# 带上memory_write，和不带编译器屏障一样，没效果

__asm__ volatile(""::"m"(*__p):);

main:
.LFB0:
        .cfi_startproc
        movslq  %edi, %rdi
        movl    $9999, (%rdi)
        movl    $5, %eax
        ret
        .cfi_endproc
1
2
3
4
5
6
7
8
9
10
编辑 (opens new window)
上次更新: 2023/05/07, 17:27:54
hpc_common.hpp
类型推导之auto-template-decltype

← 类型推导之auto-template-decltype→

最近更新
01
通过模板实现结构体成员拷贝-按成员名匹配
05-07
02
c++17通过模板获取类成员的个数
05-01
03
avx-sse切换惩罚
04-30
更多文章>
Theme by Vdoing | Copyright © 2019-2023 Colder Leo | MIT License
×