CPU高速缓存那些事儿

引言

在分析JDK8新增的高并发原子累加器Striped64的时候，发现有一个“伪共享”的概念，而要理解它必须对CPU缓存有一定的了解，所以本文将先对CPU的缓存架构以及一些相关术语做一个研究探索。

 

CPU缓存的原理

      众所周知，在如今的计算机时代，CPU的运算处理速度与内存读写速度的差异非常巨大，为了解决这种差异充分利用CPU的使用效率，CPU缓存应运而生，它是介于CPU处理器和内存之间的临时数据交换的缓冲区。

      CPU缓存和内存都是一种断电即掉的非永久随机存储器RAM，那么它和内存在物理上有什么差异吗？当然有，CPU缓存基本是由SRAM（static RAM）构成（也有IBM的Power系列处理是eDRAM构成的CPU缓存），而内存经常称之为DRAM，其实它是SDRAM（同步动态随机存储器），是DRAM的一种。构成内存的DRAM只含有一个晶体管和一个电容器，集成度非常高可用轻易的做到大容量，但因为靠电容器来存储信息所以需要不间断刷新电容器的电荷，而充放电之间的时间差导致DRAM的数据读写速度较SRAM慢的多。

    构成缓存的SRAM却比构成内存的DRAM的复杂度高了不止一筹，所以占据空间大，成本高，集成度很低，以至于在CPU工艺低下的前期，CPU缓存不能集成进CPU内部而只有集成到主板上，但它的好处却是不需要刷新电路所以读写速度快。

    如果说SRAM与DRAM物理结构及性能的不同展现了CPU高速缓存的物理原理，那么时间局部性原理和空间局部性原理则是支撑CPU高速缓存的逻辑原理。时间局部性原理是说：被引用过的内存位置很可能在不远的将来还会被多次引用，空间局部性原理说的是：如果一个内存位置不引用了，那么程序很可能会在不远的将来引用该内存位置附近的内存位置。

 

CPU缓存的层次结构

    最开始对CPU缓存进行分类是由于CPU内部集成的CPU缓存已经不能满足高性能CPU的需要，而制造工艺上的限制又不能在CPU内部大幅提高缓存的数量，所以出现了集成在主板上的缓存，当时人们就把CPU内部的缓存称为一级缓存，即L1 Cache，在CPU外部主板上的缓存称为二级缓存，即L2 Cache。而一级缓存其实还分为一级数据缓存（Data Cache，D-Cache，L1d）和一级指令缓存（Instruction Cache，I-Cache，L1i），分别用于存放数据和执行数据的指令解码，两者可以同时被CPU访问，减少了CPU多核心，多线程争用缓存造成的冲突。

    早期Intel和AMD似乎对最后一层缓存L2上存在不同的见解，每个CPU核心都具备独立的一级缓存L1，那么二级缓存L2呢？AMD的做法是依然每个CPU核心使用独立的二级缓存，但Intel却采用了一个CPU的多个核心共享二级缓存的设计，即所谓的“Smart Cache”技术，这在当时确实要比AMD的设计性能更好。

    随着制造工艺的提升，L2也被集成进了CPU缓存，但是接踵而来对大数据处理和游戏性能等等需要，在高端CPU上出现了三级缓存L3 Cache。三级缓存的出现据说对CPU的性能有着爬坡似的提升。当然到了2018年的今天，拥有三级缓存已经不再是高端CPU的特权，在一些特殊的CPU上据说还出现了四级缓存，当然这并不是说缓存的级数越多越能提升性能，到了三级缓存之后由于距离CPU的传输距离和本身容量的提升，CPU访问缓存和直接访问内存所能带来的性能提升已经被逐渐抵消，所以与其增加所谓的四级缓存还不如就直接访问内存。 综上所述，大概描述了CPU缓存的层次结构，下图是来至《深入理解计算机系统》书中关于CPU缓存和内存、硬盘存储器的层次结构：

 

 从图上可以看出，深入理解计算机系统一书将寄存器划分为L0级缓存，接着依次是L1，L2，L3，内存，本地磁盘，远程存储。越往上的缓存存储空间越小，速度越快，成本也更高；越往下的存储空间越大，速度更慢，成本也更低。从上至下，每一层都可以看做是更下一层的缓存，即：L0寄存器是L1一级缓存的缓存，L1是L2的缓存，依次类推；每一层的数据都是来至它的下一层，所以每一层的数据是下一层的数据的子集。

 

    在继续CPU缓存之前，借着我的笔记本使用CPU-Z查看到的关于处理器的一些信息，进行简单的介绍：

    
 以上信息也可以通过一个叫CoreInfo的工具查看https://docs.microsoft.com/en-us/sysinternals/downloads/coreinfo，第一张图表明我有L1, L2, L3 级CPU缓存，右下角说明我的处理器是双核四线程的。那么双核四线程是什么意思？双核我们都不陌生，类比以前的单核，就是一个CPU拥有多个核心，每个核心拥有独立的运算处理单元、控制器、寄存器、L1、L2缓存，然后一个CPU的多个核心共享最后一层CPU缓存L3，使其可以同时运行一个进程的多个线程，如下图所示：

那么四线程是什么，其实这就是所谓的超线程技术（HyperthreadingTechnology），就是通过采用特殊的硬件指令，可以为一个逻辑内核再模拟出来一个物理芯片，所以如果你通过Windows的设备管理查看处理器你会看到四个，其实有两个都是模拟出来的，这样做可以将CPU内部暂时闲置的资源充分“调动”起来，因为我们的CPU在运行一个程序时其实还有很多执行单元是被闲置的。模拟出一个核就是为了使用CPU一些空闲的地方（资源），充分榨取CPU的性能。但是模拟出来的内核毕竟是虚拟的，所以它会和被模拟的逻辑核共享寄存器，L1，L2，因此就算是双核四线程还是只有2个一级缓存L1，2个二级缓存L2，一个三级缓存L3，所以假如物理核与它的模拟核中的线程要同时使用同一个执行单元里的东西时，或者访问同一个缓存行数据，还是只能一个一个的来。

    那么双CPU或者双处理器呢？前面所说的双核心是在一个处理器里拥有两个处理器核心，核心是两个，但是其他硬件还都是两个核心在共同拥有，而双CPU则是真正意义上的双核心，不光是处理器核心是两个，其他例如缓存等硬件配置也都是双份的。一个CPU对应一个物理插槽，多处理器间通过QPI总线相连。我们常见的计算机（例如上面我的笔记本）几乎都是单CPU多核心的，真正的多CPU并不是个人PC所常用的。

 

CPU缓存的内部结构

对CPU缓存的层次结构有了了解之后，我们再深入进CPU缓存内部，看看它内部的结构。

 

 

 上图是一个CPU缓存的内部结构视图，来至《深入理解计算机系统》一书，结合上图我这里只做简单的说明，若要细致深入的了解请参考原书。原来，CPU缓存内部一般是由S组构成，这个S的大小与该缓存的存储大小寻址空间有关，然后每一组里面又有若干缓存行cache line，例如上图每一组有E行cache line，E等于2，每一个缓存行包含一个标记其是否有效的有效位和t个标记位，然后才是真正存储缓存数据部分有B个字节大小。整个缓存区的大小C=B*E*S.

而一个内存地址在做缓存查找的时候，首先中间的s位指明了应该放在哪一组，高位的t位指明位于组中的哪一行，低位的b位表示应该从缓存行中的多少个偏移开始读取，毕竟一个缓存行可以存放很多数据的，一般是64个字节。

    这里面，代表行数量的E等于1的时候称之为“直接映射高速缓存”，E等于C/B即一个组包含所有行的时候称之为“全相联高速缓存”，当1>E>C/B即缓存行数介于这之间时称之为“组相联高速缓存”。由于CPU缓存的空间一般很小，内存数据映射到CPU缓存的算法必然将导致有很多不同的数据将被映射放置到相同的缓存行，这种访问同一个缓存行的不同数据就将导致缓存不命中，需要重新到下一级缓存或内存加载数据来替换掉原来的缓存，这种不命中称之为“冲突不命中”，如果这种冲突不命中持续产生，我们将之称之为“抖动”。很显然，直接映射高速缓存每一组只有一行所以这种“抖动”将可能是很频繁的，而这显然也不是最高的缓存设计方案。而“全相联高速缓存”虽然能最大限度的解决这种“抖动”但是由于行数太多想要CPU能够快速的在比较大的缓存中匹配出想要的数据也是非常困难的，而且代价昂贵。所以它只适合做小的高速缓存。最后只有“组相联高速缓存”才是我们最佳的方案。

    在上面CPU-Z的截图中，我的CPU缓存就是采用的组相联高速缓存，L1/L2后面的8-way说明它们每一组有8行，L3有12行，L1 d/L1 i的缓存总大小都是是32KB（注意前面有个乘以2 其实就是指有两个核心），L2的缓存大小是256KB....

    一般缓存行的大小是64个字节（不包含有效位和标记位），即B等于64，其实我的这个笔记本也是，这在上面CPU-Z的第二张图中可以看到，这些信息还可以通过CoreInfo工具或者如果我们用Java编程，还可以通过CacheSize API方式来获取Cache信息， CacheSize是一个谷歌的小项目，java语言通过它可以进行访问本机Cache的信息。示例代码如下：

public static void main(String[] args) throws CacheNotFoundException {
	CacheInfo info = CacheInfo.getInstance(); 
	CacheLevelInfo l1Datainf = info.getCacheInformation(CacheLevel.L1, CacheType.DATA_CACHE);
	System.out.println("第一级数据缓存信息："+l1Datainf.toString());

	CacheLevelInfo l1Instrinf = info.getCacheInformation(CacheLevel.L1, CacheType.INSTRUCTION_CACHE);
	System.out.println("第一级指令缓存信息："+l1Instrinf.toString());
}

 打印结果如下：

第一级数据缓存信息：CacheLevelInfo [cacheLevel=L1, cacheType=DATA_CACHE, cacheSets=64, cacheCoherencyLineSize=64, cachePhysicalLinePartitions=1, cacheWaysOfAssociativity=8, isFullyAssociative=false, isSelfInitializing=true, totalSizeInBytes=32768]
 
第一级指令缓存信息：CacheLevelInfo [cacheLevel=L1, cacheType=INSTRUCTION_CACHE, cacheSets=64, cacheCoherencyLineSize=64, cachePhysicalLinePartitions=1, cacheWaysOfAssociativity=8, isFullyAssociative=false, isSelfInitializing=true, totalSizeInBytes=32768]

显然这是和实际相符的，cacheSets表面有64组，cacheCoherencyLineSize表明缓存行的大小为64字节，cacheWaysOfAssociativity表示一组里面有8个缓存行，totalSizeInBytes就是整个缓存行的大小32KB，L1数据/指令缓存大小都为：C=B×E×S=64×8×64=32768字节=32KB。 

 

CPU缓存的读写与缓存一致性协议

 首先是读，CPU执行一条读内存字w的指令时是从上往下依次查找的，下层查找到包含字w的缓存行之后，再由下层将该缓存行返回给上一层高速缓存，上一层高速缓存将这个缓存行放在它自己的一个高速缓存行中之后，继续返回给上一层，直到到达L1。L1将数据行放置到自己的缓存行之后，从被存储的缓存行中抽取出CPU真正需要的字w，然后将它返回给CPU。大概就是高速缓存确定一个请求是否命中，然后1）组选择；2）行匹配；3）字抽取。

    这里面有一个很重要的地方就是，CPU缓存在不命中的时候，向下层缓存请求的时候，返回的数据是以一个缓存行为单位的，并不是只返回给你想要的单个字，另外当出现不命中冲突的时候，会执行相应的替换策略进行替换。

最后，关于写分为两种请况：

          1.要写一个已经缓存了的字w，即写命中：首先更新本级缓存的w副本之后，怎么更新它的下一级缓存？最简单是“直写”，即立即将包含w的高速缓存行写回到第一层的缓存层， 这样做虽然简单，但是你知道CPU每时每刻可能都在进行写数据，如果大家都不停的写势必会产生很大的总线流量，不利于其他数据的处理；另一种方法称为“写回”，尽可能的推迟更新，只有当替换策略需要替换掉这个更新过的缓存行时才把它写回到紧接着的第一层的缓存中，这样总量流量减少了，但是增加了复杂性，高速缓存行必须额外的维护一个“修改位”，表明这个高速缓存行是否被修改过。

         2.写一个不在缓存中的字，即写不命中：一种是写分配，就是把不命中的缓存先加载过来，然后再更新整个缓存行，后面就是写命中的处理逻辑了；另一种是非写分配，直接把这个字写到下一层。

 

说到CPU缓存的写操作还有一个很重要的话题，那就是缓存一致性协议MESI。关于缓存一致性协议及其变种又是另一个繁杂的内容，而MESI其实仅仅是众多一致性协议中最著名的一个，其名字的得名也来至于该协议中对四种缓存状态的缩写简称，缓存一致性协议规定了如何保证缓存在各个CPU缓存的一致性问题：

以MESI协议为例，每个Cache line有4个状态，可用2个bit表示，它们分别是： 

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

 关于缓存一致性协议，由于其又是一个比较繁多的内容，我这里仅仅粗略的说一下我的理解，总之它是一种保证数据在多个CPU缓存中一致的手段，至于到底是什么样的手段，根据各个CPU厂商采用的一致性协议的不同而不同，以我目前的了解，主要有以下几种：

1. 当CPU在修改它的缓存之前，会通过最后一级缓存L3（因为最后一级缓存是多核心共享的）或者总线（多CPU跨插槽的情况）广播到其他CPU缓存，使其它存在该缓存数据的缓存行无效，然后再更改自己的缓存数据，并标记为M，当其他CPU缓存需要读取这个被修改过的缓存行时（或者由于冲突不命中需要被置换出去时），会导致立即将这个被修改过的缓存行写回到内存，然后其他CPU再从内存加载最新的数据到自己的缓存行。

2. 当CPU缓存采用“直写”这种一更改马上写回内存的方式更新缓存的时候，其他CPU通过嗅探技术，从总线上得知相关的缓存行数据失效，则立即使自己相应的缓存行无效，从而再下次读不命中的时候重新到内存加载最新的数据。

3. 当CPU修改自己的缓存行数据时，主动将相关的更新通过最后一级缓存L3或者总线（如果是多CPU跨插槽的情况）发送给其它存在相关缓存的CPU，使它们同步的更新自己的缓存到一致。

 

总之，达到CPU缓存一致性的手段层出不穷，并且通过以上3种方式，可以看到在处理缓存一致性问题的时候，如果是单CPU多核心处理器，那么总是免不了使用最后一级缓存L3来传递数据，而这还不是最糟糕的，当多处理器跨插槽的时候，数据还要穿过总线跨插槽进行传输以保证缓存一致性， 这对性能将是更严峻的考验。这种CPU缓存一致性带来的问题将是我们在文章开始提出的“伪共享”的根本所在，具体讲在下一章节进行说明。