多级缓存和MESI

首先，CPU 访问速度和主内存的运行速度一定存在差异，且 CPU 的速度快于内存的速度。假设没有缓存机制，那么代码的执行顺序——从内存中读取指令和必要数据等，然后运算，接着等待内存传输数据，这边等待的时候，就严重降低了运算速度——我们的运算上限被内存的运算速度给限制住了！

于是假设，如果一次可以从内存中拉取多一点的数据（CacheLine）然后缓存下来呢？（Cache）

相当于在二者之间搭建一座桥梁，减少运行速度差异带来的影响——CPU需要访问数据，可以依次通过多级缓存先查找，如果都没有的话，再去内存中查找。

当然，这边其实存在一个假设——如果当前读取的是0x100，那么下一时刻访问0x104的可能性也非常大。

接下来使用一个抓取资料的例子——常用的资料往往会放在手边，方便快速查阅，然后不那么重要的就可以放在远一点的柜子——甚至是去图书馆（类比内存），去进行查阅访问

Cache Line

（以64字节作为例子）

由于空间局部性——指令和数据在内存中通常是顺序存放的，所以一次性抓取64字节的数据可以提高缓存集中率（你需要的资料就在手边）

所以如果一次性不是 64 字节的话，就会触发一些性能上的瓶颈——比如

• 伪共享（False Sharing）
• 跨行访问（Unaligned Access）

False Sharing

提供一个简单的 Benchmark 结果来直观感受一下 ——

BM_FalseSharing        0.083 ms        0.011 ms        59865
BM_PaddingSharing      0.036 ms        0.011 ms        63646

两个线程分别访问同一个结构体的两个变量 —— 但是没有对齐的时候,数据会疯狂的像打乒乓球一样在两个线程之间来回跳转; 优化方式 —— 把结构体内的两个变量按照 Cache Line 的字节数对齐

MESI

如果不同的缓存都在访问内存中的同一个变量时，如何保证数据一致？这边引入了一个MESI协议——

• M: Modified 标记数据被修改了，修改后的数据在当前 Cache 内
• E: Exclusive 标记当前 Cache 有效并且与内存中的数据一致，且只存在于当前的 Cache 中
• S: Shared 数据与内存一致，不过多个 Cache 可能同时拥有副本。
• I: Invalid 标记垃圾数据，当前的 Cache Line 无效

借助一个例子来简单看下这个标记过程（其本质上就是一个有限状态机）—— 假设我们读取到了x += 1这样一个简单的指令，并且是双核（两个核心有自己的一级缓存）

1. C1 读取 x
   • x 数据进入 C1
   • C1 标记当前（x 在的）Cache Line 为 E （因为目前没有进行数据修改，且数据已经流入 C1了）
2. C2 读取 x
   • 通过总线探针（Bus Snooping）发现数据冲突（x 在 C1 / C2 中都有数据）
   • 于是把 C1 / C2 中存储 x 的 Cache Line 标记为 S
3. C1 执行 x += 1 （写入操作）
   • C1 发起写入的信号
   • C2 收到信号，把自己当前的Cache Line改称 Invalid
   • C1 把自己存储 x 的Cache Line 修改成 M，然后写入数据
4. C2 再次读取 x:
   • C2 发现自己是 I，发生 Cache Miss。
   • C1 嗅探到 C2 的读取请求，必须先将数据写回内存（或直接转发给 C2），然后双方再次回到 S 状态

Store Bufferes & Invalidate Queue

当然，这样一个状态机的效率显然是不够高的，因为切换状态并且通知到所有的Cache上实在是费时，而且还会阻塞——要等待状态切换结束。

这非常的低效，于是引入缓存存储和无效队列两个概念。

其实就是一次异步处理，来减少运算的“停顿”

Store Bufferes

在发出写指令的时候，不再是发送Invalid信息然后阻塞的等待所有的核心回复，而是简单的把写好的数据丢到 Store Buffer 中，然后发出 Invalid 消息，但是不阻塞等待，而是继续读取之后的指令然后运行。接着 Store Buffer 进行一次异步的处理 —— 得到所有的 Invalid 回复之后 把 Store Bufferes消息写回缓存修改状态为 M

但是这可能会带来一个问题 —— 指令重排序

提供一个简单例子，现在有A，B双核分别执行下面指令，并且假设 x = y = 0 是初始状态

• Core A: x = 1; r1 = y;
• Core B: y = 1; r2 = x;

然后当 A 把 x = 1 执行之后直接把脏数据丢入 Store Bufferes 后直接执行 r1 = y；同理 B 也是。 此时问题来了——当A执行r1 = y 的时候，由于 B 修改的 y 数据还在 Store Bufferes 中，没有同步到总线上 —— 因为异步处理存在一个时间差，此时，Core B 的失效信号还在总线上传播，或者刚进 Core A 的 Invalidate Queue —— 所以 r1 = 0; 同理 r2 = 0

然后在宏观上可以看作是先做了r1 = y; r2 = x 这两条指令，再执行的x = 1; y = 1的赋值，所以是指令重排序

Invalidate Queue

为了提升 Invalidate 回复慢的问题，于是引入这个缓冲队列 —— 当接收到 Invalidate 信号的时候，先把请求入队，然后直接回复 Invalidate 完成的消息，之后再异步的把 Cache Line 标记为 Invalidate