CPU Cache

CPU Cache结构

CPU包含多个核心，每个核心又有独自的一级缓存（细分成代码缓存和数据缓存）和二级缓存，各个核心之间共享三级缓存，并统一通过总线与内存进行交互

运行程序时，每个核心都有数据的一个副本（在各自的缓存中），这将会导致数据的一致性问题

Cache Line

整个Cache被分成多个Line，每个Line通常是32byte或64byte
Cache Line是Cache和内存交换数据的最小单位

每个Cache Line包含三个部分
Valid：当前缓存是否有效
Tag：对应的内存地址
Block：缓存数据

映射

主存与Cache的对应关系
将主存和Cache划分成若干大小相等的块

全关联映射

主存任意一块可以映射到Cache的任意一块
优点：空间利用率高、命中率高
缺点：访问存储器时，每次都要全部查找，速度低，基本不使用

直接映射

主存中的一块只能映射到Cache的一个特定的块中
优点：映射简单，访问速度快
缺点：替换频繁，命中率低

组相连映射

主存根据Cache大小划分多个区，每个区划分成多个组，每个组内划分多个块
Cache划分成多个组，每个组内划分多个块
主存的每个区与Cache直接映射，组内采用全映射方式

替换策略

随机

随机确定要替换的块

先进先出

选择最先调入的块进行替换

LRU（最近最少使用）

根据块的使用情况，选择最近最少使用的块进行替换，反映了程序的局部性规律

写模式

直写（Write Through）

透过本级缓存，直接把数据写到下一级缓存（或直接到内存）中，如果对应的段被缓存了，同时更新缓存中的内容（甚至直接丢弃）
缓存中的段永远和它对应的内存内容匹配

写回（Write Back）

缓存不会立即把写操作传递到下一级，而是仅修改本级缓存中的数据，并且把对应的缓存段标记为“脏”段。脏段会触发回写，也就是把里面的内容写到对应的内存或下一级缓存中。回写后，脏段又变“干净”了。当一个脏段被丢弃的时候，总是先要进行一次回写
回写定律：当所有的脏段被回写后，任意级别缓存中的缓存段的内容，等同于它对应的内存中的内容
弱一致性：要么缓存段的内容和内存一致（如果缓存段是干净的话），要么缓存段中的内容最终要回写到内存中（对于脏缓存段来说）
优点：能过滤掉对同一地址的反复写操作，并且，如果大多数缓存段都在回写模式下工作，那么系统经常可以一下子写一大片内存，而不是分成小块来写，前者的效率更高

一致性

单核是没有问题的，但多核情况下，每个核都有自己的缓存，该如何确保各核缓存数据的一致性？

窥探协议

所有内存传输都发生在一条共享的总线上，而所有的处理器都能看到这条总线：缓存本身是独立的，但是内存是共享资源，所有的内存访问都要经过仲裁（arbitrate）：同一个指令周期中，只有一个缓存可以读写内存。
缓存不仅仅在做内存传输的时候才和总线打交道，而是不停地在窥探总线上发生的数据交换，跟踪其他缓存在做什么。所以当一个缓存代表它所属的处理器去读写内存时，其他处理器都会得到通知，它们以此来使自己的缓存保持同步。只要某个处理器一写内存，其他处理器马上就知道这块内存在它们自己的缓存中对应的段已经失效。
在直写模式下，是很直接的，因为写操作一旦发生，它的效果马上会被“公布”出去，确保所有核都得到通知
在回写模式下，就有问题了，因为有可能在写指令执行过后很久，数据才会被真正回写到物理内存中。在这段时间内，其他处理器的缓存也可能会去写同一块内存地址，导致冲突

MESI缓存一直性协议

每个Cache line有2个标志：dirty（数据是否被修改）和valid（数据是否有效）标志，描述了Cache和主存之间的数据关系

在MESI协议中，每个Cache line有4个状态

状态	描述
M(Modified)	数据有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中
E(Exclusive)	数据有效，数据和内存中的数据一致，数据只存在于本Cache中
S(Shared)	数据有效，数据和内存中的数据一致，数据存在于很多Cache中
I(Invalid)	这行数据无效

M(Modified)和E(Exclusive)状态的Cache line，数据是独有的，不同点在于M状态的数据是dirty的(和内存的不一致)，E状态的数据是clean的(和内存的一致)
S(Shared)状态的Cache line，数据和其他Core的Cache共享。只有clean的数据才能被多个Cache共享

E状态
只有Core 0访问变量x，它的Cache line状态为E(Exclusive)

S状态
3个Core都访问变量x，它们对应的Cache line为S(Shared)状态

M状态和I状态
Core 0修改了x的值之后，这个Cache line变成了M(Modified)状态，其他Core对应的Cache line变成了I(Invalid)状态

MESI协议状态迁移
Local Read表示本内核读本Cache中的值，Local Write表示本内核写本Cache中的值，Remote Read表示其它内核读其它Cache中的值，Remote Write表示其它内核写其它Cache中的值，箭头表示本Cache line状态的迁移，环形箭头表示状态不变

当前状态	事件	行为	下一个状态
I(Invalid)	Local Read	如果其它Cache没有这份数据，本Cache从内存中取数据，Cache line状态变成E；如果其它Cache有这份数据，且状态为M，则将数据更新到内存，本Cache再从内存中取数据，2个Cache 的Cache line状态都变成S；如果其它Cache有这份数据，且状态为S或者E，本Cache从内存中取数据，这些Cache 的Cache line状态都变成S	E/S
Local Write	从内存中取数据，在Cache中修改，状态变成M；如果其它Cache有这份数据，且状态为M，则要先将数据更新到内存；如果其它Cache有这份数据，则其它Cache的Cache line状态变成I	M
Remote Read	既然是Invalid，别的核的操作与它无关	I
Remote Write	既然是Invalid，别的核的操作与它无关	I
E(Exclusive)	Local Read	从Cache中取数据，状态不变	E
Local Write	修改Cache中的数据，状态变成M	M
Remote Read	数据和其它核共用，状态变成了S	S
Remote Write	数据被修改，本Cache line不能再使用，状态变成I	I
S(Shared)	Local Read	从Cache中取数据，状态不变	S
Local Write	修改Cache中的数据，状态变成M，其它核共享的Cache line状态变成I	M
Remote Read	状态不变	S
Remote Write	数据被修改，本Cache line不能再使用，状态变成I	I
M(Modified)	Local Read	从Cache中取数据，状态不变	M
Local Write	修改Cache中的数据，状态不变	M
Remote Read	这行数据被写到内存中，使其它核能使用到最新的数据，状态变成S	S
Remote Write	这行数据被写到内存中，使其它核能使用到最新的数据，由于其它核会修改这行数据，状态变成I	I

*MESI定律：在所有的脏缓存段（M状态）被回写后，任意缓存级别的所有缓存段中的内容，和它们对应的内存中的内容一致。此外，在任意时刻，当某个位置的内存被一个处理器加载入独占缓存段时（E状态），那它就不会再出现在其他任何处理器的缓存中。

伪共享（false sharing）

发生在不同处理器上的线程修改位于同一个cache line的变量的情景下（本来每个线程都访问不同的数据，不会造成同步问题，但因为数据都处于同一cache line中，根据MESI协议，cache line中任意数据的修改都需要同步给其他内核，导致不应同步的操作变成同步了）
这会导致cache line失效并强制刷新，因此导致性能下降

解决办法：字节对齐，将字节填满一个cache line
Java中主要有sun.misc.Contended和Disruptor框架

参考

每个程序员都应该了解的CPU高速缓存
关于CPU Cache -- 程序猿需要知道的那些事
缓存一致性（Cache Coherency）入门
《大话处理器》Cache一致性协议之MESI
伪共享(False Sharing)
Java 7与伪共享的新仇旧恨
Java8中用sun.misc.Contended避免伪共享(false sharing)