MESI协议
高速缓存内部是一个拉链哈希表，是不是很眼熟，是的，和HashMap的内部结构十分相似，高速缓存中分为很多桶，每个桶里用链表的结构连接了很多cache entry，在每一个cache entry内部主要由三部分内容组成：
- tag：指向了这个缓存数据在主内存中的数据的地址
- cache line：存放多个变量数据
- flag：缓存行状态
各个处理器在操作内存数据时，都会往总线发送消息，各个处理器还会不停的从总线嗅探消息，通过这个消息来保证各个处理器的协作。同时MESI中有以下两个操作：
- flush操作：强制处理器在更新完数据后，将更新的数据（可能写缓冲器、寄存器中）刷到高速缓存或者主内存（不同的硬件实现MESI协议的方式不一样），同时向总线发出信息说明自己修改了某一数据
- refresh操作：从总线嗅探到某一数据失效后，将该数据在自己的缓存中失效，然后从更新后的处理器高速缓存或主内存中加载数据到自己的高速缓存中
CPU读写流程
传统的MESI协议中有两个行为的执行成本比较大。一个是将某个Cache Line标记为Invalid状态，另一个是当某Cache Line当前状态为Invalid时写入新的数据。所以CPU通过Store Buffer和Invalidate Queue组件来降低这类操作的延时。如图：
当一个核心在Invalid状态进行写入时，首先会给其它CPU核发送Invalid消息，然后把当前写入的数据写入到Store Buffer中。然后异步在某个时刻真正的写入到Cache Line中。当前CPU核如果要读Cache Line中的数据，需要先扫描Store Buffer之后再读取Cache Line（Store-Buffer Forwarding）。但是此时其它CPU核是看不到当前核的Store Buffer中的数据的，要等到Store Buffer中的数据被刷到了Cache Line之后才会触发失效操作。而当一个CPU核收到Invalid消息时，会把消息写入自身的Invalidate Queue中，随后异步将其设为Invalid状态。和Store Buffer不同的是，当前CPU核心使用Cache时并不扫描Invalidate Queue部分，所以可能会有极短时间的脏读问题。
接下来我们来说明在两个处理器情况下，其中一个处理器（处理器0）要修改数据的整个过程。假定数据所在cache line在两个高速缓存中都处于S(Shared)状态。
- 处理器0发送invalidate消息到总线；
- 处理器1在总线上进行嗅探，嗅探到invalidate消息后，通过地址解析定位到对应的cache line，发现此时cache line的状态为S，则将cache line的状态改为I，同时返回invalidate ack消息到总线；
- 处理器0在总线在嗅探到所有（例子中只有处理器1）的invalidate ack后，将要修改的cache line状态置为E(Exclusive)，表示要进行独占修改，修改完以后将cache line状态置为M(Modified)，同时可能将数据刷回主内存。
在这个过程中，如有其他处理器要修改处理器0中的cache line状态将会被阻塞。同时，假如此时处理器1要读取相应的cache line数据，则会发现状态为I(Invalid)。于是处理器1向总线中发出read消息，处理器0嗅探到read消息后，将会从自己的高速缓存或者主内存中将数据发送到总线，并将自身对应的cache line状态置为S(Shared)，处理器1从总线中接收到read消息后，将最新的数据写入到对应的cache line，并将状态置为S(Shared)。由此处理0与处理器1中对应的cache line状态又都变成了S(Shared)。
更新和读取数据的过程如下所示：
MESI协议能保证各个处理器间的高速缓存数据一致性，但是同样带来两个严重的效率问题：
- 当处理器0向总线发送invalidate消息后，要等到所有其他拥有相同缓存的处理器返回invalidate ack消息才能将对应的cache line状态置为E并进行修改,但是在这过程中它一直是处于阻塞状态，这将严重影响处理器的性能
- 当处理1嗅探到invalidate消息后，会先去将对应的cache line状态置为I，然后才会返回invalidate ack消息到总线，这个过程也是影响性能的。
基于以上两个问题，设计者又引入了写缓冲器和无效队列。在上面的场景中，处理器0，先将要修改的数据放入写缓冲器，再向总线发出invalidate消息来通知其他有相同缓存的处理器缓存失效，处理器0就可以继续执行其他指令，当接收到其他所有处理器的invalidate ack后，再将处理器0中的cache line置为E，并将写缓冲器中的数据写入高速缓存。处理器1从总线嗅探到invalidate消息后，先将消息放入到无效队列，接着立刻返回invalidate ack消息。这样来提高处理的速度，达到提高性能的目的。
写缓冲器和无效队列提高MESI协议下处理器性能，但同时也带来了新的可见性与有序性问题如下：
如上图所示：假设最初共享变量x=0同时存在于处理0和处理1的高速缓存中，且对应状态为S(Shared)，此时处理0要将x的值改变成1，先将值写到写缓冲器里，然后向总线发送invalidate消息，同时处理器1希望将x的值加1赋给y，此时处理器1发现自身缓存中x=0状态为S，则直接用x=0进行参与计算，从而发生了错误，显然这个错误由写缓冲器和无效队列导致的，因为x的新值还在写缓冲器中，无效消息在处理1的无效队列中。
典型案例：并发加
可见性问题最经典的案例即是并发加操作，如下两个线程同时在更新变量test的count属性域的值，第一次都会将 count=0 读到各自的CPU缓存里，执行完 count+=1 之后，各自CPU缓存里的值都是1，同时写入内存后，我们会发现内存中是1，而不是我们期望的2。之后由于各自的CPU缓存里都有了count的值，两个线程都是基于CPU缓存里的count值来计算，所以导致最终count的值都是小于20000的。
Thread th1 = new Thread(()->{
test.add10K();
});
Thread th2 = new Thread(()->{
test.add10K();
});
count += 1;
在Java中，如果多个线程共享一个对象，并且没有合理的使用volatile声明和线程同步，一个线程更新共享对象后，另一个线程可能无法取到对象的最新值。当一个共享变量被volatile修饰时，它会保证修改的值会立即被更新到主存，当有其他线程需要读取时，它会去内存中读取新值。通过synchronized和Lock也能够保证可见性，synchronized和Lock能保证同一时刻只有一个线程获取锁然后执行同步代码，并且在释放锁之前会将对变量的修改刷新到主存当中。因此可以保证可见性。
Links
