CPU单核的发展受到了物理限制，进而演进出了SMP、NUMA等多核CPU架构。CPU需要与内存交互，但是内存访问速度相对于CPU实在太慢，为了不让CPU浪费在等待内存存取上，所以现代CPU都增加了缓存层。
CPU缓存的意义
数据的访问遵循局部性原理。可以分为时空两部分：
1.时间局部性：如果某个数据被访问，那么在不久的将来它很有可能会被再次访问。
2.空间局部性：如果某个数据被访问，那么与它相邻的数据很快也能被访问。
据统计，L1和L2的命中率大概都有80%，所以缓存的意义是相当大的。缓存不是越大越好，所以不同CPU的L1和L2通常差别不是很大，CPU的价格主要看L3。
缓存位置如图：
CPU缓存架构
典型的缓存架构是三层，如下图：
其中L1和L2被单核独享，L3被所有核共享。L1又分为数据缓存和指令缓存。按访问速度，L1>L2>L3。大小和单位价格则反过来。
缓存中被分成多个小块，称作cache line，通常情况下，现代64位CPU的cache line都是64bytes（部分L3是128bytes）。CPU不直接与内存打交道，需要访问数据的时候查询L1，L1不存在则由缓存管理系统从L2加载，依此类推。所以可以得出一个结论，L1中有的数据L2中肯定有，L2中有的数据L3中肯定有。
缓存一致性协议
我们现在知道了CPU加缓存是为了提高CPU的利用率，但也衍生出一个问题：多核CPU的情况下，每个CPU都有自己独立的缓存，它们各自之间是不可见的，这就会导致对应CPU读取的数据都是自己缓存中的，无法看到别人对共享数据的修改，从而可能导致并发BUG。
缓存一致性协议就是要解决这个问题，协议有多种，可以分为两类：“窥探（snooping）”协议和“基于目录的（directory-based）”协议。
目前应用最广的是MESI协议或者类似变种，它属于一种“窥探协议”。本文拿MESI协议来解释和理解。
窥探协议
窥探协议的思想是，CPU缓存不仅仅在做内存传输（或缓存间传输）的时候才与总线打交道，而是不停地窥探总线上发生的数据交换，跟踪其他缓存在做什么。所以当一个缓存代表它所属的CPU去读写内存时，其它CPU都会得到通知，以此来使自己的缓存保持同步。只要某个处理器一写内存，其它处理器马上知道这块内存在它们的缓存段中已失效。
MESI协议
MESI协议通过对共享数据进行不同状态的标识，来决定CPU何时把缓存的数据同步到主存，何时可以从缓存读取数据，何时又必须从主存读取数据。
MESI名称来自4个状态的首字母的缩写，分别是Modified、Exclusive、Share、Invalid，每个CPU读取共享数据之前先要识别数据的对象状态，然后根据这几个状态分别执行不同的策略，下面我们分别了解下每个状态所代表的含义。
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 acknowledge
收到Invalidate消息的CPU在将对应cache line置为Invalid后，返回invalidate acknowledge。
Read Invalidate
相当于Read消息加上Invalidate消息，即取得数据并且独占它，将收到一个Read Response和所有其它CPU的invalidate acknowledge。
Write back
写回消息，即将状态为Modified的cache line写回到内存，通常在该cache line将被替换时使用。
MESI状态图
ME：将一个cache line的数据写回到内存中，同时CPU在cache中保留它（独占）。该状态迁移需要write back消息。
EM：CPU修改已在cache line中独占的数据。该状态迁移过程不涉及任何消息。
MI：CPU修改了cache line，并在总线上收到一个read invalidate的请求。在这种情况下，CPU必须将该cache line状态设置为无效，并且用read response和invalidate acknowledge来回应收到的请求，完成整个状态迁移。
IM：CPU需要执行一个原子的read-modify-write操作，并且其cache中没有缓存数据。CPU在总线上发送一个read invalidate用来请求数据，通过read response获取数据并加载cache line。同时，为了确保其独占的权利，必须收集所有其他CPU发来的invalidate acknowledge之后，完成整个状态迁移。
SM：CPU需要执行一个原子的read-modify-write操作，并且其cache line中有read only的缓存数据。CPU在总线上发送一个invalidate请求其他CPU清空自己的本地拷贝。同样的，该CPU必须收集所有其他CPU发来的invalidate acknowledge之后，才算完成整个状态迁移。
MS：其他CPU要读取本CPU缓存提供的数据，本地变成只读的拷贝，可能写回内存。该状态迁移来自其他CPU的read请求，本地CPU用read response回应。
ES：类似MS，只不过不存在写回内存的问题。
SE：如果CPU意识到会很快修改本地cache line中的数据，想独占，因此发出invalidate消息。当收到全部invalidate acknowledge之后完成该请求。或者，其他CPU通过write back写回数据（给其他cache line让地方），因此该CPU成了最后一个缓存该数据的。
EI：其他的CPU进行一个原子的read-modify-write操作，但是，数据在本CPU的cache line中，因此本CPU invalidate该cache line。该状态转移来自于收到read invalidate，本CPU用read response和invalidate acknowledge回应。
IE：本CPU想store数据，但不在本地cache line中，因此发出read invalidate消息。直到收到read response和全部invalidate acknowledge消息才能完成状态迁移。store完成后，cache line可能通过EM迁移到Modified状态。
IS：本CPU读取不在缓存中的cache line中的数据。发出一个read消息，等收到read response完成迁移。
SI：本CPU和其他CPU共享某数据，其他CPU要修改该数据。本CPU收到其他CPU发出的invalidate消息，用invalidate acknowledge消息回应。
store buffer & invalid queue
MESI协议逻辑很严谨，但是简单直观的实现有两个特别低效的行为。首先，当准备写入数据到无效的cache line中时，需要先发出read invalidate消息通知其他CPU，然后等待所有CPU的invalidate acknowledge消息回来后才能继续执行，这是一种同步行为；其次，把cache line置为Invalid状态也很耗时。对应的，硬件工程师给CPU设计了store buffer和invalid queue来解决。
store buffer
store buffer用于写入到无效的cache line时。因为store操作怎么都会执行，CPU对某个共享变量修改时，只需向其他CPU发出read invalid消息，无需等待其他CPU的invalidate acknowledge响应，而是直接把最新值写入到store buffer中，然后就可以继续干其他的事情了。等其他CPU的invalidate acknowledge响应到达后再把最新值从store buffer写到cache line中。
引入store buffer之后的CPU见下图：
store forwarding
如果写入store buffer之后，写回cache line之前，本CPU需要访问数据，访问到cache line中的数据就出错了，所以这种情况下就需要从store buffer中取。这个设计就叫做store forwarding。还好这个是硬件设计，软件工程师不用担心。
注意，这只能解决本CPU的问题，其他CPU是无法访问该CPU的store buffer中的数据的。也就是说，本CPU修改完了，但是暂存在store buffer中，其他CPU无法感知到该数据修改，可能造成数据读取错误。这就引入了写屏障，负责清空store buffer，保证所有store操作刷新到cache中。虽然CPU提供该指令，但是如何用、什么时候用就属于软件工程师需要关注的范畴了，我们先谈完硬件设计后面再谈软件相关的。
引入store forwarding之后的CPU见下图：
invalid queue
store buffer的大小是有限的，所有的写入操作发生cache missing（数据不在本地）时都会使用store buffer，特别是出现内存屏障时，后续的所有写入操作（不管是否cache missing）都会积压在store buffer中（直到store buffer中屏障前的条目处理完），因此store buffer很容易满。当store buffer满了之后，CPU还是会卡在等对应的invalidate acknowledge以处理store buffer中的条目。因此还是要回到invalidate acknowledge中来，invalidate acknowledge耗时的主要原因是CPU要先将对应的cache line置为Invalid后再返回invalidate acknowledge，一个很忙的CPU可能会导致其它CPU都在等它回invalidate acknowledge。
解决思路还是化同步为异步，增加一个invalid queue: CPU不必等处理了cache line之后才回invalidate acknowledge，而是可以先将Invalid消息放到某个请求队列Invalid Queue，然后就返回invalidate acknowledge。CPU可以后续再尽快处理Invalid Queue中的消息，大幅度降低invalidate acknowledge响应时间。
这同样引入了一个问题，CPU只是尽快处理Invalid Queue中的消息，而不是立即。如果CPU读取cache line数据的时候，invalid queue中已标明无效，但是CPU不知道，读取到的数据就是旧的，得有机制可以强制刷新invalid queue。因为invalid queue在缓存的另一侧，CPU无法采用类似store forwarding的方法直接访问它。这就引入了读屏障，负责清空invalid queue，保证其他CPU的写操作对本CPU可见。
引入invalid queue之后的CPU见下图：
内存屏障
针对单核而言，CPU执行指令是允许乱序的，只要保证跟不乱序执行得到的最终结果一致就可以。对于弱内存模型的CPU来说，除了存在数据依赖、控制依赖以及地址依赖等的前后指令不能被乱序之外，其余指令间都有可能存在乱序。单核没问题，多核就可能出现问题。
CPU缓存优化和流水线技术提升了CPU效率，大部分时间我们无需关心它们。但是在多核编程时，必须考虑优化带来的潜在问题。参见上文提到的引入store buffer和invalid queue之后带来的问题。
CPU提供了指令，软件工程师可以在必要的时候使用它们禁用优化，得到正确的结果。使用了内存屏障后，写入数据时候会保证所有的指令都执行完毕，这样就能保证修改过的数据能及时的暴露给其他的CPU。在读取数据的时候保证所有的“无效队列”消息都已经被读取完毕，这样就保证了其他CPU修改的数据消息都能被当前CPU知道，然后根据Invalid消息判断自己的缓存是否处于无效状态，这样读取数据的时候就能正确的读取到最新的数据。
Store Barrier（写屏障）
强制所有在store屏障指令之前的store指令，都在该store屏障指令执行之前被执行，并把store缓冲区的数据都刷到CPU缓存。
这个屏障的意思就是只要看到Store Barrier指令了，那么就必须把Store Barrier指令之前的所有写入指令执行完毕才可以往下执行，通过这种方式就可以让CPU修改的数据可以马上暴露给其他CPU。
Load Barrier（读屏障）
强制所有在load屏障指令之后的load指令，都在该load屏障指令执行之后被执行，并且一直等到load缓冲区被该CPU读完才能执行之后的load指令。
这个指令的意思是，在Load屏障指令执行后就能保证后面的读取数据指令一定能读取到最新的数据。
Full Barrier（全屏障）
包含了Store Barrier 和Load Barrier的功能。
C++11 memory module
不同体系的CPU提供的内存屏障指令是不一样的，给我们跨平台编程带来很大麻烦。好在C++11引入了内存模型，统一了表述，我们得以一次编写终身使用。但是实际应用的时候，要认真、认真再认真的甄别需要补充内存屏障的地方，写错或者漏掉都会给我们造成潜在的麻烦，而且一般情况下发生概率很低。
引用
http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf
