计算机在执行程序的时候，每条指令都是在CPU中执行的，而执行的时候，又免不了要和数据打交道。而计算机上面的数据，是存放在主存（物理内存）当中的。但是随着CPU技术的发展，CPU的执行速度越来越快。而由于内存的技术并没有太大的变化，所以从内存中读取和写入数据的过程和CPU的执行速度比起来差距就会越来越大,这就导致CPU每次操作内存都要耗费很多等待时间。
为了避免内存成为计算机处理的瓶颈，我们在CPU和内存之间增加高速缓存：
当程序在运行过程中，会将运算需要的数据从主存复制一份到CPU的高速缓存当中，那么CPU进行计算时就可以直接从它的高速缓存读取数据和向其中写入数据，当运算结束之后，再将高速缓存中的数据刷新到主存当中
在高速缓存出现后不久，系统变得越来越复杂，高速缓存与主存之间的速度差异被拉大，直到加入了另一级缓存，新加入的这级缓存比第一缓存更大，但是更慢，而且经济上不合适，所以有了二级缓存，甚至有些系统已经拥有了三级缓存，于是就演变成了多级缓存。这三种缓存的技术难度和制造成本是相对递减的，所以其容量也是相对递增的。
L1最靠近CPU核心；L2其次；L3再次。在运行速度方面：L1最快、L2次快、L3最慢；在容量大小方面：L1最小、L2较大、L3最大
当CPU要读取一个数据时，首先从一级缓存中查找，如果没有找到再从二级缓存中查找，如果还是没有就从三级缓存或内存中查找。
1. 内部结构
高速缓存存在于每个处理器内，处理器在执行读、写操作的时候并不需要直接与内存交互，而是通过高速缓存进行。
高速缓存内其实就是为应用程序访问的变量保存了一个数据副本。高速缓存相当于一个容量极小的散列表（Hash Table），其键是一个内存地址，值是内存数据的副本或是我们准备写入的数据。从其内部来看，其实相当于一个拉链散列表，也就是包含了很多桶，每个桶上又可以包含很多缓存条目（想想HashMap），如图：
缓存条目
在每个缓存条目中，其实又包含了Tag、Data Block、Flag三个部分，咱们来个小图：
- **Data Block : **也就是我们常常叨叨的缓存行（Cache Line）,它其实是高速缓存与主内存间进行数据交互的最小单元，里面存储着我们需要的变量数据。
- **Tag : **包含了缓存行中数据内存地址的信息（其实是内存地址的高位部分的比特）
- Flag : 标识了当前缓存行的状态（MESI咯）
那么，我们的处理器又是怎么寻找到我们需要的变量呢？
其实，在处理器执行内存访问变量的操作时，会对内存地址进行解码的(由高速缓存控制器执行)。而解码后就会得到tag、index 、offset三部分数据。
index : 我们知道高速缓存内的结构是一个拉链散列表，所以index就是为了帮我们来定位到底是哪个缓存条目的。
tag : 很明显和我们缓存条目中的Tag 一样，所以tag 相当于缓存条目的编号。主要用于，在同一个桶下的拉链中来寻找我们的目标。
offset : 我们要知道一个前提，就是一个缓存条目中的缓存行是可以存储很多变量的，所以offset的作用是用来确定一个变量在缓存行中的起始位置。
所以，在如果在高速缓存内能找到缓存条目并且定位到了响应的缓存行，而此时缓存条目的Flag标识为有效状态，这时候也就是我们所说的缓存命中（Cache Hit）,否则就是缓存未命中（Cache Miss）。
缓存未命又包括读未命中（Read Miss）和写未命中(Write Miss)两种,对应着对内存的读写操作。
而在读未命中（Read Miss） 产生时，处理器所需要的数据会从主内存加载并被存入高速缓存对应的缓存行中，此过程会导致处理器停顿（Stall）而不能执行其他指令。
2. 缓存一致性
在多线程进行共享变量访问时，因为各个线程执行的处理器上的高速缓存中都会保存一份变量的副本数据，这样就会有一个问题，那当一个副本更新后怎么保证其它处理器能马上的获取到最新的数据。这其实就是缓存一致性的问题，其本质也就是怎么防止数据的脏读。
为了解决这个问题，处理器间出现了一种通信机制，也就是缓存一致性协议（Cache Coherence Protocol）。
多级缓存-缓存一致性（MESI），MESI是一个协议，这协议用于保证多个CPU cache之间缓存共享数据的一致性。它定义了CacheLine的四种数据状态，而CPU对cache的四种操作可能会产生不一致的状态。因此缓存控制器监听到本地操作与远程操作的时候需要对地址一致的CacheLine状态做出一定的修改，从而保证数据在多个cache之间流转的一致性。
缓存一致性协议有很多种，MESI（Modified-Exclusive-Shared-Invalid）协议其实是目前使用很广泛的缓存一致性协议，x86处理器所使用的缓存一致性协议就是基于MESI的。
我们可以把MESI对内存数据访问理解成我们常用的读写锁，它可以使对同一内存地址的读操作是并发的，而写操作是独占的。所以在任何时刻写操作只能有一个处理器执行。而在MESI中，一个处理器要向内存写数据时必须持有该数据的所有权。
MESI将缓存条目的状态分为了Modified、Exclusive、Shared、Invalid四种，并在此基础上定义了一组消息用于处理器的读、写内存操作。如图：
2.1. MESI的四种状态
- M: Modified 修改，指的是该缓存行只被缓存在该CPU的缓存中，并且是被修改过的，因此他与主存中的数据是不一致的， 该缓存行中的数据需要在未来的某个时间点（允许其他CPU读取主存相应中的内容之前）写回主存，而当数据被写回主存之后，该缓存行的状态会变成E（独享）。由于MESI协议中任意时刻只能有一个处理器对同一内存地址对应的数据进行更新，也就是说再多个处理器的高速缓存中相同Tag值的缓存条目只能有一个处于Modified状态。
- E：Exclusive 独享 缓存行只被缓存在该CPU的缓存中，是未被修改过的，与主存的数据是一致的，此时其他CPU上高速缓存当前都不保留该数据的有效副本。可以在任何时刻当有其他CPU读取该内存时，变成S（共享）状态，同样的当CPU修改该缓存行的内容时，会变成M（被修改）的状态
- S：Share 共享，当前CPU和其他CPU中都有共同数据，并且和主存中的数据一致；意味着该缓存行可能会被多个CPU进行缓存，并且各缓存中的数据与主存数据是一致的，当有一个CPU修改该缓存行时，在其他CPU中的该缓存行是可以被作废的，变成I(无效的) 状态
- I：Invalid 无效的，代表这个缓存是无效的，可能是有其他CPU修改了该缓存行；数据应该从主存中获取，其他CPU中可能有数据也可能无数据，当前CPU中的数据和主存被认为是不一致的；对于invalid而言，在MESI协议中采取的是写失效（write invalidate）。
CacheLine有四种数据状态（MESI），而引起数据状态转换的CPU cache操作也有四种：
- local read：读本地缓存中的数据
- local write：将数据写到本地缓存里面
- remote read：将内（主）存中的数据读取到缓存中来
- remote write：将缓存中的数据写回到主存里面去
在一个典型的多核系统中，每一个核都会有自己的缓存来共享主存总线，每个相应的CPU会发出读写（I/O）请求，而缓存的目的是为了减少CPU读写共享主存的次数。一个缓存除了在 Invalid 状态之外，都可以满足CPU的读请求。
一个写请求只有在该缓存行是M状态，或者E状态的时候才能够被执行。如果当前状态是处在S状态的时候，它必须先将缓存中的该缓存行变成无效的（Invalid）状态，这个操作通常作用于广播的方式来完成。这个时候它既不允许不同的CPU同时修改同一个缓存行，即使修改该缓存行不同位置的数据也是不允许的，这里主要解决的是缓存一致性的问题。一个处于M状态的缓存行它必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S状态之前被延迟执行。
一个处于S状态的缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。
一个处于E状态的缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S状态。
因此，对于M和E两种状态而言总是精确的，他们在和该缓存行的真正状态是一致的。而S状态可能是非一致的，如果一个缓存将处于S状态的缓存行作废了，而另一个缓存实际上可能已经独享了该缓存行，但是该缓存却不会将该缓存行升迁为E状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的copy的数量，因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行。
从上面的意义看来E状态是一种投机性的优化：如果一个CPU想修改一个处于S状态的缓存行，总线事务需要将所有该缓存行的copy变成invalid状态，而修改E状态的缓存不需要使用总线事务。
2.2. MESI处理机制
MESI协议到底是怎么来协调处理器进行内存的读写呢？
其实，想协调处理必然需要先和各个处理器进行通信。所以MESI协议定义了一组消息机制用于协调各个处理器的读写操作。
我们可以参考HTTP协议来进行理解，可以将MESI协议中的消息分为请求和响应两类。
处理器在进行主内存读写的时候会往总线（Bus）中发请求消息，同时每个处理器还会嗅探（Snoop）总线中由其他处理器发出的请求消息并在一定条件下往总线中回复响应消息。
针对于消息的类型，有如下几种：
- Read : 请求消息，用于通知其他处理器、主内存，当前处理器准备读取某个数据。该消息内包含待读取数据的主内存地址。
- Read Response: 响应消息，该消息内包含了被请求读取的数据。该消息可能是主内存返回的，也可能是其他高速缓存嗅探到Read 消息返回的。
- Invalidate： 请求消息，通知其他处理器删除指定内存地址的数据副本。其实就是告诉他们你这个缓存条目内的数据无效了，删除只是逻辑上的，其实就是更新下缓存条目的Flag.
- Invalidate Acknowledge： 响应消息，接收到Invalidate消息的处理器必须回复此消息，表示已经删除了其高速缓存内对应的数据副本。
- Read Invalidate: 请求消息，此消息为Read 和 Invalidate消息组成的复合消息，作用主要是用于通知其他处理器当前处理器准备更新一个数据了，并请求其他处理器删除其高速缓存内对应的数据副本。接收到该消息的处理器必须回复Read Response 和 Invalidate Acknowledge消息。
- Writeback: 请求消息，消息包含了需要写入主内存的数据和其对应的内存地址。
了解完了基础的消息类型，那么我们就来看看MESI协议是如何协助处理器实现内存读写的。
举例：假如内存地址0xxx上的变量s 是CPU1 和CPU2共享的我们先来说下CPU上读取数据s
高速缓存内存在有效数据时：
CPU1会根据内存地址0xxx在高速缓存找到对应的缓存条目，并读取缓存条目的Tag和Flag值。如果此时缓存条目的Flag 是M、E、S三种状态的任何一种，那么就直接从缓存行中读取地址0xxx对应的数据，不会向总线中发送任何消息。
高速缓存内不存在有效数据时：
- 如CPU2 高速缓存内找到的缓存条目状态为I时，则说明此时CPU2的高速缓存中不包含数据s的有效数据副本。
- CPU2向总线发送Read消息来读取地址0xxx对应的数据s.
- CPU1（或主内存）嗅探到Read消息，则需要回复Read Response提供相应的数据。
- CPU2接收到Read Response消息时，会将其中携带的数据s存入相应的缓存行并将对应的缓存条目状态更新为S。
从宏观的角度看，就是上面的流程了，我们再继续深入下，看看在缓存条目为I的时候到底是怎么进行消息处理的
说完了读取数据，我们就在说下CPU1是怎么写入一个地址为0xxx的数据s的
MESI协议解决了缓存一致性的问题，但其中有一个问题，那就是需要在等待其他处理器全部回复后才能进行下一步操作，这种等待明显是不能接受的，下面就继续来看看大神们是怎么解决处理器等待的问题的。
2.3. 写缓冲和无效化队列
因为MESI自身有个问题，就是在写内存操作的时候必须等待其他所有处理器将自身高速缓存内的相应数据副本都删除后，并接收到这些处理器回复的Invalidate Acknowledge/Read Response消息后才能将数据写入高速缓存。
为了避免这种等待造成的写操作延迟，硬件设计引入了写缓冲器和无效化队列。
写缓冲器（Store Buffer）
在每个处理器内都有自己独立的写缓冲器，写缓冲器内部包含很多条目（Entry）,写缓冲器比高速缓存还要小点。
那么，在引入了写缓冲器后，处理器在执行写入数据的时候会做什么处理呢？还会直接发送消息到BUS吗？
我们来看几个场景：
（注意x86处理器是不管相应的缓存条目是什么状态，都会直接将每一个写操作结果存入写缓冲器）
1、如果此时缓存条目状态是E或者M：
代表此时处理器已经获取到数据所有权，那么就会将数据直接写入相应的缓存行内，而不会向总线发送消息。
2、如果此时缓存条目状态是S
- 此时处理器会将写操作的数据存入写缓冲器的条目中，并发送Invalidate消息。
- 如果此时相应缓存条目的状态是I ，那就称之为写操作遇到了写未命中（Write Miss），此时就会将数据先写入写缓冲器的条目中，然后在发送Read Invalidate来通知其他处理器我要进行数据更新了。
- 处理器的写操作其实在将数据写入缓冲器时就完成了，处理器并不需要等待其他处理器返回Invalidate Acknowledge/Read Response消息
- 当处理器接收到其他处理器回复的针对于同一个缓存条目的Invalidate Acknowledge消息时，就会将写缓冲内对应的数据写入相应的缓存行中
通过上面的场景描述我们可以看出，写缓冲器帮助处理器实现了异步写数据的能力，使得处理器处理指令的能力大大提升。
无效化队列（Invalidate Queue）
其实在处理器接到Invalidate类型的消息时，并不会删除消息中指定地址对应的数据副本（也就是说不会去马上修改缓存条目的状态为I），而是将消息存入无效化队列之后就回复Invalidate Acknowledge消息了，主要原因还是为了减少处理器等待的时间。
所以不管是写缓冲器还是无效化队列，其实都是为了减少处理器的等待时间，采用了空间换时间的方式来实现命令的异步处理。
总之就是，写缓冲器解决了写数据时要等待其他处理器响应得问题，无效化队列帮助解决了删除数据等待的问题。
但既然是异步的，那必然又会带来新的问题 – 内存重排序和可见性问题。
3. 指令重排序
指令重排序处理器为提高运算速度而做出违背代码原有顺序的优化。
例如代码
a=10;
b=200;
result=a*b;
在CPU重排序后可能变为
b=200;
a=10;
result=a*b;
可以看到CPU重排序执行优化后的代码并不会对计算结果造成影响，但这也只是其中一种没被影响的情况而已。在单核时代，处理器保证做出的优化不会导致执行结果远离预期目标。但是在多核环境下则并非如此，因为在多核环境下同时会有多个核心在执行指令，每个核心的指令都可能被乱序。另外处理器还引入了L1、L2等多级缓存机制，而每个核心都有自己的缓存，这就导致了逻辑次序上后写入的数据未必真的写入了。如果我们不做任何防护措施，那么处理器最终处理的结果可能与我们代码的逻辑结果大不相同。比如我们在一个核心上执行数据写入操作，并在最后写一个标记用来表示之前的数据已经准备好了。然后从另外一个核心上通过判断这个标记来判定所需要的数据是否已准备就绪，这种做法就存在一定的风险，标记位可能先被写入，而数据并未准备完成，这个未完成既有可能是没有计算完成，也有可能是缓存没有被及时刷新到主存之中，这样最终就会导致另外的核心使用了错误的数据，所以我们才经常在多线程的情况下保证线程安全。
4. 内存屏障
由于写缓冲器和无效化队列的出现，处理器的执行都变成了异步操作。缓冲器是每个处理器私有的，一个处理器所存储的内容是无法被其他处理器读取的。
举个例子：
CPU1 更新变量到缓冲器中，而CPU2因为无法读取到CPU1缓冲器内容所以从高速缓存中读取的仍然是该变量旧值。
其实这就是写缓冲器导致StoreLoad重排序问题，而写缓冲器还会导致StoreStore重排序问题等。
为了使一个处理器上运行的线程对共享变量所做的更新被其他处理器上运行的线程读到，我们必须将写缓冲器的内容写到其他处理器的高速缓存上，从而使在缓存一致性协议作用下此次更新可以被其他处理器读取到。
处理器在写缓冲器满、I/O指令被执行时会将写缓冲器中的内容写入高速缓存中。但从变量更新角度来看，处理器本身无法保障这种更新的”及时“性。为了保证处理器对共享变量的更新可被其他处理器同步，编译器等底层系统借助一类称为内存屏障的特殊指令来实现。
内存屏障中的存储屏障（Store Barrier）会使执行该指令的处理器将写缓冲器内容写入高速缓存。
内存屏障中的加载屏障（Load Barrier）会根据无效化队列内容指定的内存地址，将相应处理器上的高速缓存中相应的缓存条目状态标记为I。
处理器都支持一定的内存屏障(memory barrier)或栅栏(fence)来控制重排序和数据在不同的处理器间的可见性。例如，CPU将数据写回时，会将store请求放入write buffer中等待flush到内存，可以通过插入barrier的方式防止这个store请求与其他的请求重排序、保证数据的可见性。可以用一个生活中的例子类比屏障，例如坐地铁的斜坡式电梯时，大家按顺序进入电梯，但是会有一些人从左侧绕过去，这样出电梯时顺序就不相同了，如果有一个人携带了一个大的行李堵住了（屏障），则后面的人就不能绕过去了:)。另外这里的barrier和GC中用到的write barrier是不同的概念。
内存屏障的分类
几乎所有的处理器都支持一定粗粒度的barrier指令，通常叫做Fence(栅栏、围墙)，能够保证在fence之前发起的load和store指令都能严格的和fence之后的load和store保持有序。通常按照用途会分为下面四种barrier
LoadLoad Barriers
指令顺序如：Load1; LoadLoad; Load2;
保证Load1的数据在Load2及之后的load前加载
StoreStore Barriers
指令顺序如：Store1; StoreStore; Store2
保证Store1的数据先于Store2及之后的数据 在其他处理器可见
LoadStore Barriers
指令顺序如：Load1; LoadStore; Store2
保证Load1的数据的加载在Store2和之后的数据flush前
StoreLoad Barriers
指令顺序如：Store1; StoreLoad; Load2
保证Store1的数据对其他处理器变得可见(如flush到内存)先于Load2和之后的load的数据的加载。StoreLoad Barrier能够防止load读取到旧数据而不是最近其他处理器写入的数据。StoreLoad Barriers会使该屏障之前的所有内存访问指令完成之后，才执行该屏障之后的内存访问指令
StoreLoad Barriers是一个“全能型”的屏障，它同时具有其他3个屏障的效果。现代的多处理器大多支持该屏障（其他类型的屏障不一定被所有处理器支持）。执行该屏障开销会很昂贵，因为当前处理器通常要把写缓冲区中的数据全部刷新到内存中（Buffer Fully Flush）。
举个例子说明，假设有一组 CPU 指令：
- Store 表示“存储指令”
- Load 表示“读取指令”
- StoreLoad 代表“写读内存屏障”
StoreLoad 屏障之前的 Store 指令，无法与 StoreLoad 屏障之后的 Load 指令进行交换位置，即重排序。
但是 StoreLoad 屏障之前和之后的指令是可以互换位置的，即 Store1 可以和 Store2 互换，Load2 可以和 Load3 互换。
5. 参考资料
https://cloud.tencent.com/developer/article/1429393
https://www.jianshu.com/p/64240319ed60
https://mp.weixin.qq.com/s/SZl2E5NAhpYM4kKv9gyQOQ
https://mp.weixin.qq.com/s/0H9yfiYvWGQByjFT-fj-ww
