CPU高速缓存行与内存关系 及并发MESI 协议

先来一个整体图：

image.png

一.cpu和内存的关系

大致关系： CPU Cache --> 前端总线 FSB (下图中的Bus) --> Memory 内存

CPU 为了更快的执行代码。于是当从内存中读取数据时，并不是只读自己想要的部分。而是读取足够的字节来填入高速缓存行(缓存预读性原理)。根据不同的 CPU ，高速缓存行大小不同。如 X86 是 32BYTES ，而 ALPHA 是 64BYTES 。并且始终在第 32 个字节或第 64 个字节处对齐(内存对齐)。这样，当 CPU 访问相邻的数据时，就不必每次都从内存中读取，提高了速度。 因为访问内存要比访问高速缓存用的时间多得多。

下面一张图可以看出各级缓存之间的响应时间差距，以及内存到底有多慢！

image.png

二. CPU Cache和Cache Line

什么是Cache Line

Cache Line可以简单的理解为CPU Cache中的最小缓存单位。目前主流的CPU Cache的Cache Line大小都是64Bytes。假设我们有一个512字节的一级缓存，那么按照64B的缓存单位大小来算，这个一级缓存所能存放的缓存个数就是512/64 = 8个。具体参见下图：

image.png

例子：一段逻辑代码，会从命令行接收一个参数作为数组的大小创建一个数量为N的int数组。并依次循环的从这个数组中进行数组内容访问，循环10亿次。最终输出数组总大小和对应总执行时间。

如果我们把这些数据做成折线图后就会发现：总执行时间在数组大小超过64Bytes时有较为明显的拐点。原因是当数组小于64Bytes时数组极有可能落在一条Cache Line内，而一个元素的访问就会使得整条Cache Line被填充，因而使得后面的若干个元素受益于缓存带来的加速。而当数组大于64Bytes时，必然至少需要两条Cache Line，继而在循环访问时会出现两次Cache Line的填充，由于缓存填充的时间远高于数据访问的响应时间，因此多一次缓存填充对于总执行的影响会被放大，最终得到下图的结果：

image.png

我们来看下面这个C语言中常用的循环优化例子
下面两段代码中，第一段代码在C语言中总是比第二段代码的执行速度要快。具体的原因相信你仔细阅读了Cache Line的介绍后就很容易理解了。

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int num;   
        arr[i][j] = num;
    }
}
//在内存中顺序填充数组，会在cpu缓存行中也顺序填充

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int   num;       
        arr[j][i] = num;
    }
}
////在内存中不连续填充，会在多个cpu缓存行中填充

三. 下面看CPU Cache与Memory关系图

image.png

上述左图是最简单的高速缓存的图示，数据的读取和存储都经过高速缓存，CPU核心和高速缓存之间有一条特殊的快速通道，在这个简化的图示上，主存（main memory）与高速缓存（cache）都连在系统总线上。这条总线同时还用于其他组件之间的通信。在高速缓存出现后不久，系统变得更加复杂，高速缓存与主存之间的速度差异被拉大，直到加入了另一级的缓存（由于加大一级缓存的做法从经济上考虑是行不通的，所以有了二级缓存甚至三级缓存）。新加入的这些缓存比第一缓存更大但是更慢。

多核发达的年代。情况就不能那么简单了。试想下面这样一个情况。

1、CPU1 读取了一个字节，以及它和它相邻的字节被读入 CPU1 的高速缓存。
2、CPU2 做了上面同样的工作。这样 CPU1 ， CPU2 的高速缓存拥有同样的数据。
3、CPU1 修改了那个字节，被修改后，那个字节被放回 CPU1 的高速缓存行。但是该信息并没有被写入 RAM 。
4、CPU2 访问该字节，但由于 CPU1 并未将数据写入 RAM ，导致了数据不同步。

为了解决这个问题，芯片设计者制定了一个规则。当一个 CPU 修改高速缓存行中的字节时，计算机中的其它 CPU 会被通知，它们的高速缓存将视为无效。于是，在上面的情况下， CPU2 发现自己的高速缓存中数据已无效， CPU1 将立即把自己的数据写回 RAM ，然后 CPU2 重新读取该数据。 可以看出，高速缓存行在多处理器上会导致一些不利。

四. 多核CPU多级缓存一致性协议MESI

多核CPU的情况下有多个一级缓存，如何保证缓存内部数据的一致,不让系统数据混乱。这里就引出了一个一致性的协议MESI。

MESI协议缓存状态

MESI 是指4种状态的首字母。每个Cache line有4个状态，可用2个bit表示，它们分别是：

缓存行（Cache line）:缓存存储数据的单元。

image.png

举个栗子来说：

假设cache 1 中有一个变量x = 0的cache line 处于S状态(共享)。
那么其他拥有x变量的cache 2、cache 3等x的cache line调整为S状态（共享）或者调整为 I 状态（无效）。

多核缓存协同操作

假设有三个CPU A、B、C，对应三个缓存分别是cache a、b、 c。在主内存中定义了x的引用值为0。

image.png

单核读取
那么执行流程是：
CPU A发出了一条指令，从主内存中读取x。
从主内存通过bus读取到缓存中（远端读取Remote read）,这是该Cache line修改为E状态（独享）.

image.png

双核读取
那么执行流程是：
CPU A发出了一条指令，从主内存中读取x。
CPU A从主内存通过bus读取到 cache a中并将该cache line 设置为E状态。
CPU B发出了一条指令，从主内存中读取x。
CPU B试图从主内存中读取x时，CPU A检测到了地址冲突。这时CPU A对相关数据做出响应。此时x 存储于cache a和cache b中，x在chche a和cache b中都被设置为S状态(共享)。

image.png

修改数据
那么执行流程是：
CPU A 计算完成后发指令需要修改x.
CPU A 将x设置为M状态（修改）并通知缓存了x的CPU B, CPU B将本地cache b中的x设置为I状态(无效)
CPU A 对x进行赋值。

image.png

同步数据
那么执行流程是：

CPU B 发出了要读取x的指令。
CPU B 通知CPU A,CPU A将修改后的数据同步到主内存并且cache a 修改为E（独享）
CPU A同步CPU B的x,将cache a和同步后cache b中的x设置为S状态（共享）。

image.png

五. Cache淘汰策略

常见的淘汰策略主要有LRU和Random两种。通常意义下LRU对于Cache的命中率会比Random更好，所以CPU Cache的淘汰策略选择的是LRU。当然也有些实验显示在Cache Size较大的时候Random策略会有更高的命中率。