动态slc缓存算法（内存屏障高速缓存）

上节讲了：JMM相关知识点及synchronized、volatile关键字相关底层细节

本节继续分析一下一些关于内存屏障、高速缓存、MESI协议等相关的知识点。

1、内存屏障

Java 如何保证底层操作的有序性和可见性？

内存屏障是被插入两个 CPU 指令之间的一种指令，用来禁止处理器指令发生重排序（像屏障一样），从而保障有序性的。

另外，为了达到屏障的效果，它也会使处理器写入、读取值之前，将主内存的值写入高速缓存，清空无效队列，从而保障可见性。

举个例子说明：

Store1;//写入指令

Store2;//写入指令

Load1;//读取指令

StoreLoad; //内存屏障

Store3;//写入指令

Load2;//读取指令

Load3;//读取指令

对于上面的一组 CPU 指令（Store 表示写入指令，Load 表示读取指令，StoreLoad 代表写读内存屏障），StoreLoad 屏障之前的 Store 指令无法与 StoreLoad 屏障之后的 Load 指令进行交换位置，即重排序。

但是 StoreLoad 屏障之前和之后的指令是可以互换位置的，即 Store1 可以和 Store2 互换，Load2 可以和 Load3 互换。

常见有 4 种屏障：

LoadLoad 屏障：对于这样的语句 Load1；LoadLoad；Load2，在 Load2 后续读取操作要读取的数据被访问前，保证 Load1 要读取的数据被读取完毕。

StoreStore 屏障：对于这样的语句 Store1；StoreStore；Store2，在 Store2 后续写入操作执行前，保证 Store1 的写入操作对其他处理器可见。

LoadStore 屏障：对于这样的语句 Load1；LoadStore；Store2，在 Store2 及后续写入操作被执行前，保证 Load1 要读取的数据被读取完毕。

StoreLoad 屏障：对于这样的语句 Store1；StoreLoad；Load2，在 Load2 及后续所有读取操作执行前，保证 Store1 这些写入对所有处理器可见。它的开销是四种屏障中最大的（冲刷写缓冲器，清空无效化队列）。

Java 对内存屏障的使用在一般的代码中不太容易见到，常见的有 volatile 和 synchronized 关键字修饰的代码块。

2、synchronized实现原理

其实synchronized底层的原理，是跟jvm指令和monitor有关系的，你如果用到了synchronized关键字，在底层编译后的jvm指令中，会有monitorenter和monitorexit两个指令

每个对象都有一个关联的monitor，比如一个对象实例就有一个monitor，一个类的Class对象也有一个monitor，如果要对这个对象加锁，那么必须获取这个对象关联的monitor的锁

他里面的原理和思路大概是这样的，monitor里面有一个计数器，从0开始的。如果一个线程要获取monitor的锁，就看看他的计数器是不是0，如果是0的话，那么说明没人获取锁，他就可以获取锁了，然后对计数器加1。

Synchronized可保证原子性、可见性、有序性。

1）原子性：加锁和释放锁，

2）可见性：加了Load屏障和Store屏障，释放锁flush数据，加锁会refresh数据

在monitorexit指令之后，会有一个Store屏障，让线程把自己在同步代码块里修改的变量的值都执行flush处理器缓存的操作，刷到高速缓存（或者主内存）里去；然后在monitorenter指令之后会加一个Load屏障，执行refresh处理器缓存的操作，把别的处理器修改过的最新值加载到自己高速缓存里来。所以说通过Load屏障和Store屏障，就可以让synchronized保证可见性。

3）有序性：(Acqurie)LoadLoad LoadStore屏障和(Release)StoreLoad StoreStore屏障，保证同步代码块内部的指令可以重排，但是同步代码块内部的指令和外面的指令是不能重排的。在monitorenter指令之后，Load屏障之后，会加一个Acquire屏障，这个屏障的作用是禁止读操作和读写操作之间发生指令重排序。在monitorexit指令之前，会加一个Release屏障，这个屏障的作用是禁止写操作和读写操作之间发生重排序。

3、高速缓存

数据结构

处理器高速缓存的底层数据结构实际是一个拉链散列表的结构，就是有很多个bucket，每个bucket挂了很多的cache entry（缓冲条目），每个cache entry由三个部分组成：tag、cache line和flag，其中的cache line就是缓存的数据。

tag指向了这个缓存数据在主内存中的数据的地址，flag标识了缓存行的状态，另外要注意的一点是，cache line中可以包含多个变量的值，那么处理器在读写高速缓存的时候，实际上会根据变量名执行一个内存地址解码的操作，解析出来3个东西，index、tag和offset。index用于定位到拉链散列表中的某个bucket，tag是用于定位cache entry，offset是用于定位一个变量在cache line中的位置，如果说可以成功定位到一个高速缓存中的数据，而且flag还标志着有效，则缓存命中；否则不满足上述条件，就是缓存未命中。如果是读数据未命中的话，会从主内存重新加载数据到高速缓存中，现在处理器一般都有三级高速缓存，L1、L2、L3，越靠前面的缓存读写速度越快。

因为有高速缓存的存在，所以就导致各个处理器可能对一个变量会在自己的高速缓存里有自己的副本，这样一个处理器修改了变量值，别的处理器是看不到的，所以就是为了这个问题引入了缓存一致性协议（MESI协议）。

4、MESI协议中硬件原理

MESI协议规定：对一个共享变量的读操作可以是多个处理器并发执行的，但是如果是对一个共享变量的写操作，只有一个处理器可以执行，其实也会通过排他锁的机制保证就一个处理器能写，之前说过那个cache entry的flag代表了缓存数据的状态，MESI协议中划分为：

（1）invalid：无效的，标记为I，这个意思就是当前cache entry无效，里面的数据不能使用。

（2）shared：共享的，标记为S，这个意思是当前cache entry有效，而且里面的数据在各个处理器中都有各自的副本，但是这些副本的值跟主内存的值是一样的，各个处理器就是并发的在读而已。

（3）exclusive：独占的，标记为E，这个意思就是当前处理器对这个数据独占了，只有他可以有这个副本，其他的处理器都不能包含这个副本。

（4）modified：修改过的，标记为M，只能有一个处理器对共享数据更新，所以只有更新数据的处理器的cache entry，才是exclusive状态，表明当前线程更新了这个数据，这个副本的数据跟主内存是不一样的。

MESI协议规定了一组消息，就说各个处理器在操作内存数据的时候，都会往总线发送消息，而且各个处理器还会不停的从总线嗅探最新的消息，通过这个总线的消息传递来保证各个处理器的协作。

下面来详细的图解MESI协议的工作原理：

处理器0读取某个变量的数据时，首先会根据index、tag和offset从高速缓存的拉链散列表读取数据，如果发现状态为I是无效的，此时就会发送read消息到总线接着主内存会返回对应的数据给处理器0，处理器0就会把数据放到高速缓存里，同时cache entry的flag状态是S共享的。

在处理器0对一个数据进行更新的时候，如果数据状态是S，则此时就需要发送一个invalidate消息到总线，尝试让其他的处理器的高速缓存的cache entry全部变为I无效的，以获得数据的独占锁。

其他的处理器1会从总线嗅探到invalidate消息，此时就会把自己的cache entry设置为I无效的，也就是过期掉自己本地的缓存，然后就是返回invalidate ack消息到总线，传递回处理器0，处理器0必须收到所有处理器返回的ack消息。

接着处理器0就会将cache entry先设置为E独占这条数据，在独占期间，别的处理器就不能修改数据了，因为别的处理器此时发出invalidate消息，这个处理器0是不会返回invalidate ack消息的，除非他先修改完再说。

接着处理器0就是修改这条数据，接着将数据设置为M修改过的，也有可能是把数据此时强制写回到主内存中，具体看底层硬件实现。

然后其他处理器此时这条数据的状态都是I无效了，那如果要读的话，全部都需要重新发送read消息，从主内存（或者是其他处理器）来加载，这个具体怎么实现要看底层的硬件了，都有可能的。

5、采用写缓冲器和无效队列优化MESI协议

MESI协议如果每次写数据的时候都要发送invalidate消息等待所有处理器返回ack，然后获取独占锁后才能写数据，那可能就会导致性能很差了，因为这个对共享变量的写操作，实际上在硬件级别变成串行的了所以为了解决这个问题，硬件层面引入了写缓冲器和无效队列

写缓冲器的作用是，一个处理器写数据的时候，直接把数据写入缓冲器，同时发送invalidate消息，然后就认为写操作完成了，接着就干别的事儿了，不会阻塞在这里。接着这个处理器如果之后收到其他处理器的ack消息之后，才会把写缓冲器中的写结果拿出来，通过对cache entry设置为E加独占锁，同时修改数据，然后设置为M。

其实写缓冲器的作用，就是处理器写数据的时候直接写入缓冲器，不需要同步阻塞等待其他处理器的invalidate ack返回，这就大大提升了硬件层面的执行效率了。

引入无效队列，就是说其他处理器在接收到了invalidate消息之后，不需要立马过期本地缓存，直接把消息放入无效队列，就返回ack给那个写处理器了，这就进一步加速了性能，之后从无效队列里取出来消息，过期本地缓存即可。

可见性和有序性的问题：

可见性：写缓冲器和无效队列导致的，写数据不一定立马写入自己的高速缓存（或者主内存），是因为可能写入了写缓冲器；读数据不一定立马从别人的高速缓存（或者主内存）刷新最新的值过来，invalidate消息在无效队列里面

解决可见性问题：

Store屏障 Load屏障

如果加了Store屏障之后，就会强制性要求你对一个写操作必须阻塞等待到其他的处理器返回invalidate ack之后，对数据加锁，然后修改数据到高速缓存中，必须在写数据之后，强制执行flush操作，要求一个写操作必须刷到高速缓存（或者主内存），不能停留在写缓冲里。

如果加了Load屏障之后，在从高速缓存中读取数据的时候，如果发现无效队列里有一个invalidate消息，此时会立马强制根据那个invalidate消息把自己本地高速缓存的数据设置为过期，然后就可以强制从其他处理器的高速缓存中加载最新的值，就是refresh操作。

解决有序性问题：

内存屏障，Acquire屏障，Release屏障，但是都是由基础的StoreStore屏障,StoreLoad屏障，可以避免指令重排序的效果

StoreStore屏障，会强制让写数据的操作全部按照顺序写入写缓冲器里，他不会让你第一个写到写缓冲器里去，第二个写直接修改高速缓存了。

StoreLoad屏障，他会强制先将写缓冲器里的数据写入高速缓存中，接着读数据的时候强制清空无效队列，对里面的validate消息全部过期掉高速缓存中的条目，然后强制从主内存里重新加载数据。

,