内存模型和原子操作笔记

1. 缓存一致性协议

缓存一致性协议MESI可以保证，在所有的脏缓存段被回写后，任意缓存级别的所有缓存段中的内容，和它们对应的内存中的内容一致。此外，在任意时刻，当某个位置的内存被一个处理器加载入独占缓存段时，那它就不会再出现在其他任何处理器的缓存中。

缓存段独占权的有效期是一个CPU时钟周期。

2. 缓存队列

缓存一致性协议可以保证数据访问的一致性，就像所有CPU共享了一个L1缓存一样，但是现实总是不尽如人意。

2.1 CPU写缓存队列

L1缓存的写速度跟不上CPU的频率，缓存一致性协议的存在更加剧了这个情况(写之前要首先独占缓存段)，因此在CPU内部有一个写缓存队列(storage buffer)，在把写数据提交给L1缓存之前做一个缓存。

收益：
1）根据局部性原理，可以合并写入，减少写(缓存)内存次数(缓存更新是以缓存段为单位的)。
2）因为数据已经被缓存在队列，CPU不必等写指令完全执行完，就可以接着执行后续的指令(这是SL乱序执行产生的部分原因)。

影响：数据写入L1缓存不及时，导致其他CPU可能读到旧数据(数据还在CPU内部，还没进入缓存一致性协议的管辖范围)。

2.2 Cache事件队列

缓存有很多事情要做，加载/写数据，不能保证在一个时钟周期内响应总线上的事件，需要引入一个事件队列，先把收到的总线事件入队，等空闲了再响应。

影响：可能导致没有及时失效某些缓存段，导致CPU读到旧数据。

3 原子操作

我自己给原子操作的定义：

• 在Read-Modify-Write之间，没有其他CPU对这个变量执行写操作；
• 两个原子操作，在顺序上必须有一个先后，具体是A操作在前，还是B操作在前，无所谓。但是，这两个操作比如是可以排序的，必须是先后发生，A和B的执行期间不能交织。

为了确保原子操作，在读任何东西前先获得缓存段的所有权；并且，只有当我们在整个原子操作期间一直握有独占权，才可以把操作的结果回写。

因此，如果指令能够在一个时钟周期内执行完，那么缓存独占+指令执行就可以非常完美的实现原子操作。如果操作不能在一个时钟周期内完成，就得想点别的辙了。

3.1 X86内存总线锁指令LOCK

X86的原子操作在很多情况下需要使用LOCK指令。LOCK要求锁定内存总线，需要所有CPU达成一致(显而易见，其他CPU要把自己的脏缓存段先刷进L2缓存这里假定L2是CPU共享缓存，才能同意独占请求)，在读-写-修改完成后，再释放总线(可能经历了很多个时钟周期)。这个成本是很高的。

3.2 乐观锁指令LL/SC

大多数RISC处理器，通过乐观锁的方式实现原子操作。它的思路是把所有正在进行原子操作的缓存段“监控”起来，在原子操作完成前，如果有其他处理器请求这个缓存段，那我们的原子操作要从头再来。

4 指令重排和乱序

现代CPU都会充分利用流水线执行、分支预测等优化技术，不保证指令是按照你写的顺序执行，这就叫“乱序”执行。而绝大多数指令都涉及到内存操作，这就要求CPU必须有明确的内存模型保证，无论指令执行顺序怎么重排，要符合内存模型的约束。

有的CPU(比如X86)是强内存模型，有的CPU(比如手机的CPU)是弱内存模型。

C++11抽象出了语言级别的内存模型，分别对应如下：

relaxed：没有任何约束，处理器和CPU可以随便搞。 acquire: 保证LL、LS指令序列按序执行，也就是说保证“最先读”。 release: 保证LS、SS指令序列按需执行，也就是说保证“最后写”。 acq_rel: 同时满足acquire和release。 consume: 放宽acquire的要求，只要有依赖关系的变量，按顺序从内存读即可。 sequentially consistent：保证所有指令序列都按序执行。

如果所有这四种内存访问指令序列都按序执行了，就是所谓的“顺序一致性”模型。也就是说，顺序一致性模型保证后续执行的指令一定可以看到先前执行指令的写入，无论是执行在几个CPU上。这是一个成本很高的要求，因为除了确保访存指令不乱序执行，还要考虑虑缓存队列引入的滞后效应。

举个X86的例子，
   atomic<int> a;
   a.store(1, std::memory_order_release);  // 汇编代码是： movl  $1, a(%rip)
   a.store(1);  // 汇编代码是: movl  $1, a(%rip);  mfence

   // 像mov这样的内存写指令是原子的(如果有正确的对齐，它们不需要锁定前缀)。
   // 但是这个指令通常是在CPU缓存中执行的，所以其他线程在这个时候并不全局可见。
   // 也就是说,store写入会延迟，其他CPU读取变量a时load会读到旧值。
   // 如果要求后续指令可以看到对a的写入值1，需要执行内存屏障mfentce。这就是顺序一致性的含义。
   // 在X86上，mfence防止访存指令乱序执行，并把CPU缓存队列写入L1缓存，因此对全局可见。

4.1 X86乱序执行

X86天然保证不对LL、LS、SS指令重排，只会对SL指令序列重排（参考前面的CPU写缓冲队列）。换句话说，在X86上不需要acquire/release内存屏障，它自己就能保证。只有在需要对SL也限制的时候，才需要内存屏障。

4.2 编译器优化

编译器会对生成的可执行代码做一定优化，造成乱序执行甚至省略（不执行）。

gcc编译器在遇到内嵌汇编语句：

asm volatile('' ::: 'memory');

将以此作为一条内存屏障，重排序内存操作。即此语句之前的各种编译优化将不会持续到此语句之后。也可用内建的__sync_synchronize

Microsoft Visual C++的编译器内存屏障为：

_ReadWriteBarrier() MemoryBarrier()

Intel C++编译器的内存屏障为：

__memory_barrier()

==需要强调的是，内存屏障同时也是编译屏障，所以，我们通常不需要在代码中考虑编译屏障。==

5 FAQ

5.1 原子操作为什么要求变量内存对齐？

考虑缓存组的概念，如果一个变量跨越了两个L1缓存段，就没办法实现了（不要考虑X86指令Lock的极端情况）。另外，大多数CPU都不支持内存不对齐和跨缓存段的原子访问。

5.1 原子操作和内存屏障有什么关系？

原子操作和内存屏障是两个独立的概念，但实现上，原子操作往往已经满足了内存屏障的要求。所以，C++11把内存屏障和原子操作结合在一起，不花任何额外的成本，就可以宣称已经放置了内存屏障，很鸡贼。

例如，在X86中，几乎所有的原子操作前都有Lock指令，Lock指令前后的内存访问指令不会重排（参考《Intel® 64 and IA-32 Architectures Software Developer’s Manual》），所以，它碰巧也起到了内存屏障的作用。

还有一层原因，使得原子操作和内存屏障往往联系在一起。想想你在操作一个普通变量(不支持原子操作)，你设置了内存屏障acq/rel，它该如何解释呢？你的内存操作可能跨越了多个缓存段，可能需要执行多条访存指令，acq/rel的语义无处安放（能想到的，也就是在你一些列内存操作指令序列的尾部，加上内存屏障）。

==所以，在原子操作上设置内存屏障，是在在C++11中，获取acq/rel语义的首选方法。==

5.2 Mutex是如何实现的，它能起到内存屏障的作用么？

Mutex在加锁失败时，会把当前进程(或线程)投入睡眠队列，直到锁可用时，被系统唤醒。因此，这些操作在用户空闲显然是办不到的，必然需用到系统调用。所以说，Mutex的实现，是要依赖系统调用的。

在Linux上，Mutex是基于Futexes实现的。它的大致意思是，尽量不陷入内核，首先利用自旋锁转一会，实在抢不到锁再陷入内核，当前进程(或线程)到备胎队列中排队，直到被缓存。在锁竞争不激烈时，不用陷入内核(陷入内核成本很高，考虑切换上下文，进程切换，页表失效，缓存失效）。

Mutex能不能起到内存屏障的作用呢？答案是可以，这也是锁这个原语的一个语义约束。

自己试着解释下锁为什么能够起到内存屏障的作用。
- 加锁/解锁通常是一个函数，无论编译器还是CPU，对函数调用通常都是按顺序执行的，因为不知道函数可能会用到哪些内存，不敢乱来。
- 加锁操作显然需要原子操作，正如上面分析的，原子操作往往已经满足内存屏障的要求了。
- 如果加锁失败陷入内核，显然需要刷新缓存，自然就起到内存屏障作用了。

5.3 乱序执行的例子

thread1 thread2 if(flag) { //A1 value = 99; //A3 print(value); //A2 flag = 1; //A4 } //SS乱序：假如A3、A4乱序，线程1的行为就乱了，得不到正确的value值； //LL乱序：假如A1、A2乱序，考虑执行顺序A2->A3->A4->A1，此时线程1得到的是value的旧值，显然不对。 thread1 thread2 value++; //A1 count += value //A3 print(count); //A2 //LS乱序：假如A1、A2乱序，考虑执行顺序A2->A3->A1，线程1得到的count是旧值，显然不对。 thread int expected = 0; if (flag.compare_exchange_strong(expected, 1, memory_order_relaxed)) //bug1 { // Lock was successful sharedValue++; flag.store(0, memory_order_relaxed); //bug2 count++; } //SL乱序：假如在获取flag锁之前(这是一个写操作)，提取读取了sharedValue变量（二者之间没有依赖关系），在这期间它可能被其他线程改变，等获取到锁的时候，再写入的值可能就乱套了。 这是一段有BUG的代码，正确的语义应该在bug1和bug2分别使用memory_order_acq和memory_order_release内存屏障。

参考资料

原文

1. Cache coherency primer
2. Atomic operations and contention
3. Acquire and Release Semantics
4. Weak vs. Strong Memory Models
5. This Is Why They Call It a Weakly-Ordered CPU
6. Memory Consistency Models: A Tutorial
7. 《Intel® 64 and IA-32 Architectures Software Developer’s Manual》
8. 《Anthony Williams, C++ Concurrency in Action》

译文/网文

1. 内存模型：这个被很多人忽略的概念，很值得认真了解一下
2. 缓存一致性（Cache Coherency）入门
3. 原子操作和竞争
4. Linux的原子操作与同步机制
5. C++11 memory order
6. Linux内核中的队列 kfifo
7. Linux Futex浅析

工具

1. ==cross-compiler:在线C++编译器，支持各种编译器，各种CPU平台==
2. x86指令速查