Cache Coherence
缓存一致性
CPU缓存
由于内存和CPU之间速度存在的巨大差异，在CPU和内存之间引入缓存，缓存速度介于内存于CPU之间，以减轻这种差异。
如果仅仅是从内存读到缓存，然后读写缓存，最后写会内存这3个简单步骤，缓存的作用就发挥不出来，甚至因为多拷贝、写回一次导致副作用。而由于程序的
- 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
- 空间局部性（Spatial Locality）：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。
这两个原理，就让本来需要多次读写内存，改为一次读写内存，多次读写缓存。而由于缓存的速度较内存快得多，所以能够提高效率。
CPU多核心缓存
现代CPU一般都是多个核心的，每一个核心都拥有自己的缓存，通过总线与内存交互数据。两核实例如下
实际上，Cache也不只一级，通常是3级缓存，L1和L2是CPU核心专属，L3是CPU核心共享。
而由于存在多个缓存，数据总是要进行同步的，否则会导致一致性问题。比如A = 0, 两个核心同时让A = A+1，导致，写回内存的时候，内存看到A就是1，而需求上，A应该是2。
为了解决这类问题，需要一定的机制来实现缓存一致性。就是本文的主题MESI协议和总线嗅探。
MESI缓存一致性协议
MESI（Modified Exclusive Shared Or Invalid）(也称为伊利诺斯协议，是因为该协议由伊利诺斯州立大学提出的）是一种广泛使用的支持写回策略的缓存一致性协议。为了保证多个CPU缓存中共享数据的一致性，定义了缓存行(Cache Line)的四种状态，而CPU对缓存行的四种操作可能会产生不一致的状态，因此缓存控制器监听到本地操作和远程操作的时候，需要对地址一致的缓存行的状态进行一致性修改，从而保证数据在多个缓存之间保持一致性。
CPU缓存数据的基本单位是缓存行（Cache Line）。
MESI协议定义了四种状态如下
- Modified，已修改
- Exclusive，独占
- Shared，共享
- Invalidated，已失效。
其中，已修改和独占都是仅当前缓存存有该数据。
根据本地（Local）和内存（remote）读写，进行状态的变更，整个过程可以用有限状态机（finite-state machine）表示。
每个状态对于不同的行为产生的变化如下表。
MESI仅仅是描述了缓存行的状态变迁，没有提到如何防止两个缓存同时操作的互斥问题，比如两个核心同时写一个数据对应的缓存行，究竟谁先谁后、缓存如何知道其他缓存的操作等。所以，引出总线嗅探和总线仲裁机制。
总线嗅探 & 总线仲裁
总线嗅探（Bus snooping or bus sniffing）后的基本思想是，所有内存传输都发生在一条共享的总线上，而所有的处理器都能看到这条总线：缓存本身是独立的，但是内存是共享资源，所有的内存访问都要经过仲裁（arbitrate）：同一个指令周期中，只有一个缓存可以读写内存。
窥探协议的思想是，缓存不仅仅在做内存传输的时候才和总线打交道，而是不停地在窥探总线上发生的数据交换，跟踪其他缓存在做什么。所以当一个缓存代表它所属的处理器去读写内存时，其他处理器都会得到通知，它们以此来使自己的缓存保持同步。只要某个处理器一写内存，其他处理器马上就知道这块内存在它们自己的缓存中对应的段已经失效。
总线嗅探机制保证了缓存能够立即监听其他缓存的处理，从而改变本身的状态。
总线仲裁：高并发情况下可能出现两个CPU同时修改缓存a，并同时向总线发出将各自的缓存行更改为M状态的情况，此时总线会采用相应的裁决机制进行裁决，将其中一个置为M状态，另一个置为I状态，且I状态的缓存行修改无效。
说到这里，MESI协议、总线嗅探和总线仲裁机制保证了缓存一致性。但也引出一些效率方面的问题。
问题及优化
MESI协议、总线嗅探和总线仲裁机制保证了缓存一致性，但完全地遵循协议会影响性能。
缓存的一致性消息传递是要时间的，这就使其切换时会产生延迟。当一个缓存切换状态，其他缓存收到消息，完成各自的切换，并且发出回应消息，这么一长串的时间中CPU都会等待所有缓存响应完成。可能出现的阻塞都会导致各种各样的性能问题和稳定性问题。
比如你需要修改本地缓存中的一条信息，必须等到其他拥有该数据的缓存的状态变为invalid。等待确认的过程会阻塞处理器，这会降低处理器的性能。因为这个等待远远比一个指令的执行时间长的多。
Store Buffer
为了避免这种CPU运算能力的浪费，Store Buffer被引入使用。
为了提高效率，可以使用异步的方式去处理：先将值写入到一个 Buffer 中，再发送通讯的信号，等到信号被响应，再应用到 cache 中。这么做有两个风险
- 处理器会尝试从存储缓存（Store buffer）中读取值，但它还没有进行提交。这个的解决方案称为
Store Forwarding，它使得加载的时候，如果存储缓存中存在，则进行返回。 - 不保存什么时候会完成，这个并没有任何保证。
除了优化主动修改缓存呢，还有优化被动通告修改缓存，类似Store Buffer，引入了**失效队列(invalidate queue)**。
Invalidate Queue
接到Invalidate请求后，回Invalidate Acknowlege消息但异步执行实际的invalidate操作。
- 对于所有的收到的Invalidate请求，Invalidate Acknowlege消息必须立刻发送。
- Invalidate并不真正执行，而是被放在一个特殊的队列中，在方便的时候才会去执行。
- 处理器不会发送任何消息给所处理的缓存条目，直到它处理Invalidate。
布局
引入Store Buffer和Invalid Queue后，可能会发生”重排序（reorderings）“现象。注意，这不意味着你的指令的位置被恶意（或者好意）地更改。它只是意味着其他的CPU会读到跟程序中写入的顺序不一样的结果。
引入Store Buffer和Invalid Queue后的布局如下
内存屏障
引入Store Buffer和Invalid Queue，效率是更高了，但是结果的一致性无法保证了。
干脆处理器将这个任务丢给了写代码的人。这就是内存屏障（Memory Barriers）。
如果引入了store buffer、invalidate queue之后，又该如何工作呢？
- 必须要有办法，将该store buffer中的更新，通知到其他CPU，这就是write barrier干的事情。它就是暂停CPU 0执行，并将CPU 0把store buffer中记录的一些更新应用到cache中，此时会触发cache一致性协议MESI通知CPU 1 cacheline invalidate；
- 必须要有办法，将CPU 1中invalidate queue记录下来的invalidate对应的cacheline及时清理掉，这就是read barrier干的事情。它就是暂停CPU 1执行，将其invalidate queue中的每个invalidate请求对应的cacheline全部标记为无效，下次读取时从内存或者CPU 0读取最新数据；
写屏障 Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一条告诉处理器在执行这之后的指令之前，应用所有已经在存储缓存（store buffer）中的保存的指令。
读屏障Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一条告诉处理器在执行任何的加载前，先应用所有已经在失效队列（Invalidate Queue）中的失效操作的指令。
总结一下
- 这里的读写屏障要依赖处理器提供的屏障指令
- 在屏障指令之上，内核可以按需选择，如Linux在x86平台选择用
lock; addl来实现读写屏障 smp_mb/smp_rmb/smp_wmb，x86其实也提供了mfence、lfence、sfence。至于Linux为什么这么选择，应该是跟x86实现有关系，一条指令lock;addl同时实现全屏障/读屏障/写屏障足矣。 - 其他编程语言内存模型，通常会定义一些Happens-Before关系，这里面就隐含了各种屏障的应用。基于屏障实现的各种同步原语如mutex、semaphore等就比较常见了。
重排序
重排序的 3 种情况
- 编译器优化
- 内存的“重排序”
- CPU 重排序
volatile
volatile 不能解决多线程中的问题,，仅仅用于抑制编译器重排和优化。
按照Hans Boehm & Nick Maclaren 的总结，volatile只在三种场合下是合适的。
- 和信号处理（signal handler）相关的场合；
- 和内存映射硬件（memory mapped hardware）相关的场合；
- 和非本地跳转（
setjmp和longjmp）相关的场合。
volatile、Memory Barrier、std::atomic的区别如下
| C++ | volatile |
Memory Barrier | atomic |
|---|---|---|---|
| 抑制编译器重排 | Yes | Yes | Yes |
| 抑制编译器优化 | Yes | No | Yes |
| 抑制 CPU 乱序 | No | Yes | Yes |
| 保证访问原子性 | No | No | Yes |
参考
TODO
- 理解内存模型：为什么定义内存模型、它们的区别与联系。
- happens-before语义有什么用？跟MESI、Store Buffer、Invalidate Queue有什么联系？
std::atomic底层实现