CPU中也应用到了缓存：CPU3层高速缓存，以及它的缓存一致性问题、MESI协议和Java的一些应用

为什么需要cpu高速缓存？

缓存，一般是为了用来协调两端的数据传输效率差（也可以归纳为性能差），提升响应速度。那么CPU的高速缓存是用来协调什么之间的速度差呢？

CPU在处理一条指令的时候，会读写寄存器、解码指令、控制指令执行和计算。所以寄存器的速度影响了整个指令处理周期长度。我们希望CPU处理指令的速度尽可能地快。

寄存器可以存储一部分数据（指令、数据和地址，已知时点的计算中间结果），而且只包含存储电路。这些数据的读写速度非常快，可以加速计算机程序（指令）的执行，并且寄存器也是CPU的直接工作区域。但是内存和寄存器的访问速度相差很大，如果没有三级缓存，cpu就不得不往内存里放数据、读数据到寄存器，整个指令的执行时间就会变慢。所以三级缓存相当于是CPU（寄存器）到内存之间的一层缓存，协调了内存读写和CPU指令高速执行（寄存器）之间的速度差。

虽然寄存器看起来也很像一层缓存，但和CPU三层高速缓存也有区别，寄存器直接为CPU执行指令提供工作区域，而三级缓存是更完全的缓存作用。

CPU中的高速缓存一般分为L1、L2、L3，即一级二级三级缓存。一级最快，三层最慢，但相对内存来说也快多了。

L1的访问速度几乎等同于寄存器速度，空间较小，分为L1数据缓存（index0 32K）和L1指令缓存（index1 32K L1独有，为CPU分忧）。（每个cpu核心都有）

size可以通过 cat /sys/devices/system/cpu/cpu0/cache/index0/size 获取到

L2的访问速度更慢，但是存储空间更大（index2 256K），只缓存数据，不管指令。（每个cpu核心都有）

L3也是比L2更慢，存储空间更大（index3 16384K），只缓存数据，不管指令。（多个CPU共用）

CPU cache 只和内存打交道，不会直接写硬盘，读写数据都会先加载到内存，从内存加载到CPU cache。按照这个准则再扩展一些，就是每个存储器只和相邻的那层存储设备打交道。而且存储空间越大，读写速度越慢，材料成本越低。

CPU访问内存数据时，会先去看寄存器里有没有，如果没有再逐级读L1、L2、L3，这些cpu内部的存储中不包含想要的数据的话，才会真正去内存中读取数据。这种存储层次结构总体构成了缓存。

如果CPU真的去内存读数据了，它不仅会读取自己想要的部分数据，而是读够一定字节长度的数据填入高速缓存行Cache Line，这样补充三级缓存中的数据，之后读相邻的数据时就可以不去内存而直接在三级缓存中读取了

这种设计在访问速度和容量之间寻找到了平衡。

CPU Cache的结构：由很多CacheLine组成，CPU Line是CPU从内存读取数据的基本单位（读取内存时，读够一定长度的数据填入CacheLine），Line又由Tag和Data Block组成。

查看L1的Cache Line大小：cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 结果为 64 字节，也就是说对于L1一次载入数据大小就是64字节。

举个例子：读取int array[100]的数组，载入[0]时，假设元素大小只占4字节，那么其实会读64字节=array[0]~array[15]这16个元素，那么当程序遍历到下一个array[1]时，直接在CPU Cache中就可以读到，不需要再去内存里取了。

提升CPU三级缓存命中率，可以提升指令执行效率，这是可以在代码中实现的。

如何写出让CPU跑得更快（缓存命中率高）的代码？

要希望缓存命中率高，首先要了解的是，CPU怎么判断要访问的数据到底在不在Cache里呢？

CPU读取内存数据到Cache时，是一块一块读取的，即上文所说的 coherency_line_size ，这块数据在内存中称为「内存块」，想读取这块数据，需要知道内存块的地址。针对这个地址，直接映射Cache策略就是把内存块的地址mapping到一个CPU Line的地址，Cache Line->内存块。具体映射规则就是简单的mod取模运算（Cache的Line少）。地址对应地址。

但由于Cache的Line数量肯定比内存块少，会出现多个内存块映射到同一个Cache Line的现象，因此在一个Cache Line中还有一个组标记Tag，来记录当前存储的数据究竟对应哪个内存块。除了Tag和Data以外，还会有一个标记「有效位」，它用来标记对应的数据是否还有效：如果是脏数据，那么CPU会无视Cache中的数据，直接从内存重新加载。这个逻辑是为了实现缓存一致性，后续小节会详细说明。

CPU 从Line中读取数据时，并不会读整个数据块的内容，而是读取CPU所需的一个数据片段——字（Word）。如何精准地找到这个字？CPU需要一个偏移量来寻找。因此数据的访问地址=组标记+CPU Line索引+偏移量，CPU通过这三个信息定位到Cache中的数据。数据在Cache的存储结构=索引+有效位+组标记+数据块。

CPU访问内存数据（假设已经在Cache内）的步骤：

1. 将内存地址映射到Cache地址中：根据内存地址中的索引信息计算CPUCache中的索引。（内存地址=组标记+索引+偏移量）
2. 找到对应CPU Line之后判断有效位，是否可读。
3. 对比Tag，确认CPU Line是不是要找的数据。
4. 根据内存偏移量信息，在Line中按照偏移量来读取相应的字。

就像小节题目一样，让CPU跑得更快本质上就是让CPU多去缓存中读取数据而不是内存中，所以问题的根本是“如何写出缓存命中率高的代码”？

对于L1来说，需要分别考虑数据缓存和指令缓存的命中率。

数据缓存命中率

假设遍历二维数组赋值，外层for i内层for j，先行后列（[i][j])会比先列后行([j][i])要快很多，因为行所占用的的内存是连续的。在读[i][0]时会加载到[i][3]，这意味着下一个遍历的元素已经读到Cache中了。

这个例子总结下来就是访问数据元素的方式尽量是连续的，不要跳跃。

指令缓存命中率

假设有一个元素为随机数的数组，需要有两个操作：循环遍历，将小于50的元素置为0；将数组排序。这两个操作谁先执行会比较快呢？

对于if条件语句，CPU有一个分支预测器，会预测接下来将要执行if的指令还是else的指令（接下来走哪个分支？），如果能够预测，就会提前把接下来要走的分支指令放到指令缓存中，这样CPU Cache包含指令，读取很快。如果数组中元素是随机的，就无法进行预测了。当数组元素是顺序的，分支预测器会根据历史的命中数据来对未来分支进行预测，预加载指令到缓存，命中率会很高。

因此，先排序再遍历速度会快。若前几次 if n < 50 次数很多，则分支预测器会将if里的指令加载到Cache中，后续执行就从Cache读即可。

此外，c/c++编译器可以根据likely这种宏来表达该分支的可能性比较高。

多核CPU的缓存命中率

进程在不同cpu核心间切换执行，对Cache来说是不利的，因为没有办法用到L1L2缓存，这两层缓存的命中率会下降。如果需要执行「计算密集型」线程，可以将其绑定到同一个核心上，避免切换。

使用方法：linux提供的 sched_setaffinity 方法。或者使用taskset工具。

编程语言的话，其实也是让os去做抉择，比如java使用最多的hotspot虚拟机，会将一个java线程直接映射到一个操作系统线程，没有额外的结构了。hotspot虚拟机也不干涉线程调度，全由os去完成，即1:1线程模型。

所以编程语言层面也只是套一层，最终还是系统层面去实现绑核。用C/C++去调用其实更便捷一些，java的话，比如 Java-Thread-Affinity 这个项目，是基于JNA调用DLL文件从而实现绑核。绑核能带来近1-2s的性能优化。（另一种术语是「线程亲和性」）举个例子：可以腾出核心专门给IO线程使用，避免IO线程的时间片争抢（避免IO线程切换）。

缓存一致性

话说回来，CPU具备高速缓存之后，虽然说可以优先读取高速缓存，没命中再读取内存，但是一份数据保存在多个地方会带来一个问题：不一致。那么CPU Cache如何保证缓存一致性的呢？

缓存一致性有两个维度：

• 一个核心缓存和内存数据的一致性（用写直达或写回）
• 多个核心缓存中相同数据的一致性

写入操作使用的策略是「写回」，当写操作改变了Cache中的数据（程序执行时，读的话先将内存中的数据加载到L3 Cache，再到L2再到L1再被CPU读，是按照层级关系一层层转移的，写也是一样；这跟应用->redis->数据块的逻辑是一样的），标记这个Cache Block为脏，此时还不用把数据写到内存。如果写操作时对应的Cache Block内存放的是别的内存地址的数据，就要检查这个标记是否为脏，如果是的话就需要把这块占地的脏数据写回到内存，然后再把当前的数据，从内存读入到CacheBlock里，再写入最新的，并标记为脏。

这样如果一直能命中缓存，其实是不用把缓存的内容写回到内存里的。当块中的脏数据为了给新读取的内容挪地，才需要写回到内存中。

为什么即使写入数据，也要先把内存中的旧数据读到cache里再修改？因为多核情况下，根据MESI协议（后述），此刻其他核心有可能修改了数据但还没往内存里写，你需要通知那个核心写回，然后读到正确的「当前」数据。

缓存一致性基本规则：

1. CPU对数据的操作只能通过缓存，不能直接访问内存
2. 如果修改一个内存地址的数据，首先需要从内存将数据块读入缓存
3. 保证修改前缓存和内存数据一致性

在这种策略下，虽然通过尽可能提高缓存命中率减少操作内存而提高了cpu的效率，但在多核场景下，L1/L2的缓存不共享，会造成标记为脏但未写回内存时，另一个核心从内存读到的还是旧的数据。解决方案有两点：

1. 写传播：cache数据更新时，需要传播给其他核心
2. 事务串行化：某个核心对数据的操作顺序，必须在其他核心看来顺序一致，比如A先+100，B再+200，那么广播之后，C和D核心都必须是先+100再+200.

如何实现事务串行化？

1. 数据操作需要同步给其他核心
2. 引入「锁」，如果两个核心有相同数据的Cache，则只有拿到锁的核心才能更新数据。

总线嗅探——写广播的实现方式，一致性的基础

每个CPU核心都会监听总线上的广播事件，例如A修改了i的值为+100，则每个核心检查自己的L1Cache里是否有相同数据，如果有则更新。

但频繁发出广播事件会加重总线的负载。而且并不能实现事务串行化。所以还需要补充一些机制。

MESI协议——基于总线嗅探做到CPU缓存一致性

MESI协议在总线嗅探的基础上增加了状态机机制，降低了总线广播带宽压力，并实现了事务串行化。

• Modified 已修改： 【修改数据无需广播】脏标记，代表Cache中的数据已经更新，但还没写到内存。
• Exclusive 独占：【修改数据无需广播】CacheBlock中的数据是干净的，且其他cpu内不存在这个数据的缓存，可以自由写入而不需要通知其他cpu。（若其他核心从内存读了该数据，则此状态变为共享）
• Share 共享： CacheBlock中的数据是干净的，如果要更新需要广播（广播会导致其他cpu核心将自己缓存的对应数据标记为已失效）
• Invalidated 已失效：注意跟已修改区分开，这里是表明CacheBlock中的数据失效，不可以再读取

重点在于，如果A更改数据，需要向其他核心广播该数据，让其他核心将其标记为「已失效」，自己再改数据并变为「已修改」。「已修改」状态也会在被替换时将数据同步到内存。

如果A为「已修改」此刻B也要修改数据，A会先收到广播事件，发现自己有这块数据并且标记为「已修改」，则将数据写回到内存中。B广播之后，也会收到A回复的“我已经有这块数据并修改了，此刻已写回内存，你去读一下”，再从内存里读取数据，再进行修改。

MESI协议仅在Share和Invalidated状态时修改数据需要广播，降低了广播的频率。

MESI协议就是最终解决方案了吗？写缓冲区和失效队列

MESI协议虽然保证了事务串行化，但是自然地，他的效率变低了：假设A要写一条数据，需要向总线发送「无效化」消息，并确认收到「无效化」ack消息之后才动手执行操作，将数据写入到高速缓存中并设定状态为「独占」。

优化方式是异步：A将数据写入到一个新的东西「写缓冲器」中，发送「无效」消息给总线，就认为成功了，可以去干别的事。等到收到所有核心返回的ack之后，从写缓冲器中取出数据，设为独占，写入到自己的高速缓存中，写完后，设为共享。

至于其他核心，嗅探到「无效」消息后，直接返回ack，将消息放到「无效队列」中，等过段时间再从队列中取出消息进行消费，将自己的状态设置为过期。

延伸——MESI协议存在了，volatile还有什么其他作用？

硬件层面已经实现了缓存一致性，为什么Java语言还要定义volatile关键字？

CPU为了提高并行度，会在增加写缓冲区和失效队列（这两个是中间状态，MESI并没有办法控制）时将MESI协议的请求异步，这是一种处理器级别的指令重排，破坏了CPU Cache的一致性。

即使不考虑这个因素，仍然需要volatile去保证「顺序一致性」。（MESI解决的是「数据一致性」的问题）

为了追求并行度，处理器和编译器有很多重排序优化，没有依赖关系的指令谁先执行无所谓。在Java虚拟机和处理器实现中就是不要求顺序与编码顺序完全一致。允许每个线程看到的全局顺序不一致，允许看不到其他线程已执行指令的结果（不符合内存可见性）。

Java虚拟机会使用上述弱顺序一致性模型。

重排序在单线程下是安全的，多线程下是不安全的。怎么纠正？编译器和处理器提供了「内存屏障指令」的方式来管控顺序，程序员则使用高级语法synchronized volatile final CAS等来调用内存屏障。

总结

从缓存的作用——协调两端的性能差说起，虽然着重讨论的是CPU的高速缓存的形式和作用，但其实大部分缓存都可以应用这个逻辑：解决性能差、产生一致性问题。而MESI协议的状态机其实也可以理解为一种加锁机制，锁就是「独占」状态。最后，MESI也不是完美的，还需要考虑性能和数据一致性之间的问题。此外还扩展了Java的一些特性，包括如何绑核来提升性能、关键字禁止指令重排序的作用。