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
每个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")
# cpu屏障
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")
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);
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);
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();
}
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);
cpu内存屏障的实现方法:
#define barrier() do { __asm__ __volatile__("lock"; addl $0 0(%%esp)" ::: "cc", "memory"); } while(0)
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");
}
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);
}
2
3
4
5
6
7
8
9
10
11
12
O3编译, 并查看汇编结果:
gcc -O3 -S example1.c
cat example1.s
2
# 不带编译器屏障
//__asm__ volatile("":::"memory");
main:
.LFB0:
.cfi_startproc
movslq %edi, %rdi
movl $5, %eax
movl $9999, (%rdi)
ret
.cfi_endproc
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
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
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
2
3
4
5
6
7
8
9
10