CPU Cache

Cache

在这里插入图片描述

Cache 是什么 ?

Cache被称为高速缓冲存储器（cache memory），是一种小容量高速的存储器，属于存储子系统的一部分程序常使用的指令和数据。
在这里插入图片描述

为什么需要 CPU Cache ？

CPU Cache 是为了解决 CPU 与内存速度差距而设计的高速缓存存储器，通常分为 L1、L2、L3 多级结构，相比主存，Cache的存取速度更快但容量更小，用于存放主存中频繁使用的数据块的副本。

Cache的组成

Cache 是以缓存行（Cache Line） 为基本单元，Cache Line是 CPU 从内存读取数据的最小单位，指的是当CPU试图load一个字节数据的时候，如果cache缺失，那么cache控制器会从主存中一次性的load cache line大小的数据到cache中。为什么load cache line大小的数据到cache中呢？看完局部性原理应该懂了。

局部性原理

局部性原理 是Cache 的理论基础是，包括时间局部性和空间局部性：

  • 时间局部性（temporal locality）： 程序中被引入过一次的内存位置很可能在不远的将来再次被多次引用。
  • 空间局部性（spatial locality）：在程序中一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

举个例子：

int sumvec(int v[N])
{
    int num = 0;
    for (int i = 0; i < N; ++i)
    {
        sum += v[i];
    }
    return sum;
}

对于上面代码段，sum来说，有好的时间局部性。另一方面，因为sum是标量，对于sum来说，没有空间局部性。而向量v是被顺序读取的，一个接一个。因此对于变量v,函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。

内存地址寻址

我们知道每个字节由八个位组成，"位"是计算机中最基本的存储单元，只能为0或1，规定1B=8bit，大写的“B”就代表是字节。

由于每个位只能是0和1，我们把所有的组合可能都列出来，最后就能发现，1个位能够访问到2个地址，2个位能够访问到4个地址，3个位能够访问到8个地址，也就是2的N次方。
在这里插入图片描述
我们假设使用一个64字节大小的内存模型。如果按字节编址全部编址需要6个位。接着就可以引入“字”的概念。“字”的大小是可以变化的，例如令1Word=1Byte，那么这个模型下就有64个字；如果令1Word=2Byte，那么这个模型就有32个字；如果令1Word=4Byte，那么这个模型就有16个字。我们以1Word=4Byte，16个字需要4个位就能全部访问。

在这里插入图片描述
为了更好的掩饰，我们更换一下内存模型，此时的每一个“格子”代表了字节，而每一“行”代表了字。
在上面的内存模型中，6位能够访问64个“格”，而4位只能访问16个“行”，缺少的2位就可以被理解为“列”。6位的地址能够直接访问到对应“格”的数据，而先通过4位地址找到对应的“行”，再通过2位地址找到对应的“列”，最后找到的就是6位时访问的“格”。

Cache的读取过程是怎么样的？

现代CPU进行数据读取的时候，无论数据是否已经存储在Cacha中，CPU始终会首先访问Cache。只有当CPU在Cache中找不到数据的时候，才会去访问主存内容，并且将读取到的数据写入Cache中。

问题来了，CPU如何知道要访问的内存数据，存储在Cache的哪个位置呢？ CPU实际上是以地址映射的方式来找到主存地址对应的cache地址的

地址映射

主存的数据块大小称为快，cache的数据大小称为行，单个数据称为字。
主存与cache之间是以数据块为单位进行数据交换的，（为什么以整个数据块为数据拷贝呢？答：空间局部性。）主存与cache的数据块大小是相同的。
在这里插入图片描述例如上面是一个64字节大小的内存模型，一个字等于4字节，2个字等于一个块，那么在下图中我们一共有4行cache line，一行cache line就是2个字。所以我们可以利用地址低1bits用来寻址2 字中某一字，我们称这部分bit组合为偏移量（offset）。同理，4行cache line，为了覆盖所有行。我们需要2 bits查找某一行，这部分地址部分称之为索引（index）。我们再看下图中有8个内存块对应4个缓存行，必然会有两个内存块映射同一缓存行，而怎么知道缓存行对应是哪一内存块呢？为了解决这个问题我们使用一位来进行区别，称为标记（tag）。但如果又有新的内存快要映射到这个缓存行呢?单靠一位无法区分三个不同的内存块。为了解决这一问题，我们需要引入不同的映射策略。
在这里插入图片描述

直接映射

在这里插入图片描述
内存被划分为与缓存行大小相同的 “内存块”，每个内存块通过 “内存块号 % Cache 总行数” 的计算方式，映射到唯一的 Cache 行。这种方式的优势是硬件实现简单，查找速度快，无需复杂的比较逻辑；但缺点是 “冲突概率高”—— 多个内存块可能映射到同一 Cache 行，导致频繁覆盖，降低命中率。
在这里插入图片描述

由于初始状态Cache块中的数据是空的，也是无效的。为了标识Cache块中的数据，是否已经从内存中读取，需要在Cache块上增加一个有效位（Valid bit）。如果有效位为1，则CPU可以直接读取 Cache 块上的内容，否则需要先从内存读取内存块，并填入Cache块，再将有效位改为 1。

我们首先将地址序列0解析出来，0 00 0，首相访问缓存索引是0位置，此时标记位为空，有效位为0代表缓存行没有数据，此时就会从内存中读取块序号0位置的内存块D1 D2，并写入到缓存的对应位置，同时还需要更新缓存行的标记位为0，有效位为1。此时就能够通过偏移位找到对应的数据。

接下来我们处理剩余地址。
地址：0010

  1. 拆分地址：Tag=0x0，Index=0x01，Offset=0x0

  2. 寻址：定位缓存行1

  3. 校验有效位=0 → 缓存缺失（miss）

  4. 执行回填：从内存读取0x01数据，存入缓存行1，设置Valid=1，Tag=0x0

  5. 完成访问：读取缓存行0对应偏移数据

地址：0011

  1. 拆分地址：Tag=0x0，Index=0x01，Offset=0x1

  2. 寻址：定位缓存行1

  3. 校验：缓存行1有效位=1，Tag匹配 → 缓存命中（hit）

  4. 完成访问：读取缓存行0对应偏移数据

地址：1000

  1. 拆分地址：Tag=0x1，Index=0x0，Offset=0x0

  2. 寻址：定位缓存行0

  3. 校验有效位=1 Tag=0x1 ≠ 0x0 → 缓存缺失

  4. 执行回填：读取内存卡0x4位置数据，存入0位置缓存行，同时更新标记位，Tag=0x1

  5. 完成访问：读取缓存行0对应偏移数据

全相联映射

在这里插入图片描述
对于直接映射存在2个问题：

  • 缓存利用不充分：每个内存块只能映射到固定的位置上，即使Cache上有空闲位置也不会使用。
  • 块冲突率高：直接映射会频繁出现块冲突，影响缓存命中率。
    在这里插入图片描述

为了改进直接相联映射的缺点，全相联映射的策略是：允许内存块映射到任何一个Cache块上。这种方式能够充分利用 Cache 的空间，块冲突率也更低，但是所需要的电路结构物更复杂，成本更高。
在这里插入图片描述

组相连映射

在这里插入图片描述
组相联映射结合了直接相联映射和全相联映射的优点，组相联映射的策略是：将Cache分为多组，每个内存块固定映射到一个分组中，又允许映射到组内的任意Cache块。显然，组相联的分组为1时，就等于全相联映射，而分组等于Cache块个数时，就等于直接映射。
在这里插入图片描述
在这里插入图片描述

缓存替换策略

  • 随机法： 使用一个随机数生成器，随机地选择要被替换的 Cache 块。优点是实现简单，缺点是没有利用 “局部性原理”，无法提高缓存命中率。
  • FIFO 先进先出法： 记录各个Cache块的加载事件，最早调入的块最先被替换。缺点同样是没有利用 “局部性原理”，无法提高缓存命中率。
  • LRU（Least Recently Used，近期最少使用）算法是把CPU近期最少使用的块替换出去。这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。每块也设置一个计数器，Cache每命中一次，命中块计数器清零，其他各块计数器增1。当需要替换时，将计数值最大的块换出。优点是利用 “局部性原理”，提高缓存命中率，缺点是实现起来比较复杂，系统开销较大。
  • PLRU替换算法，即伪最近最少使用算法。 该算法是在LRU算法的基础上进行改进的，它可以有效地减少缓存替换带来的性能损失。 PLRU算法的核心思想是利用一个二叉树来维护缓存中每个块的使用情况。

三种映射策略对比

在这里插入图片描述

CPU Cache 的数据写入

CPU不仅要读数据，还需要写数据，问题是，CPU在写入数据的时候，怎么既不牺牲性能，又能保证数据的一致性呢？我们现在用的 CPU，通常都是多核的的。每一个 CPU 核里面，都有独立属于自己的L1、L2 的 Cache，然后再有多个 CPU 核共用的 L3 的 Cache、主内存。

第一个问题是：我们写入的数据，到达应该写到Cache里还是主内存呢？如果我们直接写入到主内存里，Cache里的数据是否会失效呢？为了解决这些问题，我们需要先了解两种写入策略

写直达（Write-Through）

把数据同时写入内存和 Cache 中，这种方法称为写直达（Write Through）。这种方式简单直观，但是性能就会受限于内存的访问速度。
在这里插入图片描述

写直达法很直观，也很简单，但是问题明显，无论数据在不在 Cache 里面，每次写操作都会写回到内存，这样写操作将会花费大量的时间，无疑性能会受到很大的影响。为了要减少数据写回内存的频率，就出现了写回的方法。

写回（Write-Back）

在写回机制中，当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」时才需要写到内存中，减少了数据写回内存的频率，这样便可以提高系统的性能。

在这里插入图片描述

那具体如何做到的呢？下面来详细说一下：

  • 如果当发生写操作时，数据已经在 CPU Cache 里的话，则把数据更新到 CPU Cache 里，同时标记 CPU Cache 里的这个 Cache Block 为脏（Dirty）的，这个脏的标记代表这个时候，我们 CPU Cache 里面的这个 Cache Block 的数据和内存是不一致的，这种情况是不用把数据写到内存里的；

  • 如果当发生写操作时，数据所对应的 Cache Block 里存放的是「别的内存地址的数据」的话，就要检查这个 Cache Block 里的数据有没有被标记为脏的，如果是脏的话，我们就要把这个 Cache Block 里的数据写回到内存，然后再把当前要写入的数据，写入到这个 Cache Block 里，同时也把它标记为脏的；如果 Cache Block 里面的数据没有被标记为脏，否则就直接将数据写入到这个 Cache Block 里，然后再把这个 Cache Block 标记为脏的就好了。

可以发现写回这个方法，在把数据写入到 Cache 的时候，只有在缓存不命中，同时数据对应的 Cache 中的 Cache Block 为脏标记的情况下，才会将数据写到内存中，而在缓存命中的情况下，则在写入后 Cache 后，只需把该数据对应的 Cache Block 标记为脏即可，而不用写到内存里。

这样的好处是，如果我们大量的操作都能够命中缓存，那么大部分时间里 CPU 都不需要读写内存，自然性能相比写直达会高很多。

多核缓存一致性

上面讲到了cache(高速缓存)的读写一致性，这主要是基于单核的角度讨论的，在单核系统中，cache line中的数据是primary memory(主存/内存)中对应位置的数据的一个拷贝(副本)，“cache一致性”就是cache和内存之间的数据一致性。而在多核系统中(限定于只有一级local cache的情况)，每个CPU(processor/core)的cache line中的数据都是它们共享的内存中对应位置的数据的一个拷贝，因此多核系统的“cache一致性”既包括cache和内存之间的一致性，还包括各个CPU的cache之间的一致性，也就是说，对内存同一位置的数据，不同CPU的cache line不应该有不同(或者说不一致)的值。

现在 CPU 都是多核的，由于 L1/L2 Cache 是多个核心各自独有的，那么会带来多核心的缓存一致性（Cache Coherence） 的问题，如果不能保证缓存一致性的问题，就可能造成结果错误。

那缓存一致性的问题具体是怎么发生的呢？我们以一个含有两个核心的 CPU 作为例子看一看。

假设 A 号核心和 B 号核心同时运行两个线程，都操作共同的变量 i（初始值为 0 ）。
在这里插入图片描述
这时如果 A 号核心执行了 i++ 语句的时候，为了考虑性能，使用了我们前面所说的写回策略，先把值为 1 的执行结果写入到 L1/L2 Cache 中，然后把 L1/L2 Cache 中对应的 Block 标记为脏的，这个时候数据其实没有被同步到内存中的，因为写回策略，只有在 A 号核心中的这个 Cache Block 要被替换的时候，数据才会写入到内存里。

如果这时旁边的 B 号核心尝试从内存读取 i 变量的值，则读到的将会是错误的值，因为刚才 A 号核心更新 i 值还没写入到内存中，内存中的值还依然是 0。这个就是所谓的缓存一致性问题，A 号核心和 B 号核心的缓存，在这个时候是不一致，从而会导致执行结果的错误。
在这里插入图片描述
那么，要解决这一问题，就需要一种机制，来同步两个不同核心里面的缓存数据。要实现的这个机制的话，要保证做到下面这 2 点：

  • 第一点，某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为写传播（Wreite Propagation）；

  • 第二点，某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串形化（Transaction Serialization）。

第一点写传播很容易就理解，当某个核心在 Cache 更新了数据，就需要同步到其他核心的 Cache 里。

而对于第二点事务的串形化，我们举个例子来理解它。

假设我们有一个含有 4 个核心的 CPU，这 4 个核心都操作共同的变量 i（初始值为 0 ）。A 号核心先把 i 值变为 100，而此时同一时间，B 号核心先把 i 值变为 200，这里两个修改，都会「传播」到 C 和 D 号核心。
在这里插入图片描述
那么问题就来了，C 号核心先收到了 A 号核心更新数据的事件，再收到 B 号核心更新数据的事件，因此 C 号核心看到的变量 i 是先变成 100，后变成 200。

而如果 D 号核心收到的事件是反过来的，则 D 号核心看到的是变量 i 先变成 200，再变成 100，虽然是做到了写传播，但是各个 Cache 里面的数据还是不一致的。

所以，我们要保证 C 号核心和 D 号核心都能看到相同顺序的数据变化，比如变量 i 都是先变成 100，再变成 200，这样的过程就是事务的串形化。

要实现事务串形化，要做到 2 点：

  • CPU 核心对于 Cache 中数据的操作，需要同步给其他 CPU 核心；

  • 要引入「锁」的概念，如果两个 CPU 核心里有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进行对应的数据更新。

那接下来我们看看，写传播和事务串形化具体是用什么技术实现的。

总线嗅探

写传播的原则就是当某个 CPU 核心更新了 Cache 中的数据，要把该事件广播通知到其他核心。最常见实现的方式是总线嗅探（Bus Snooping）。

我还是以前面的 i 变量例子来说明总线嗅探的工作机制，当 A 号 CPU 核心修改了 L1 Cache 中 i 变量的值，通过总线把这个事件广播通知给其他所有的核心，然后每个 CPU 核心都会监听总线上的广播事件，并检查是否有相同的数据在自己的 L1 Cache 里面，如果 B 号 CPU 核心的 L1 Cache 中有该数据，那么也需要把该数据更新到自己的 L1 Cache。

可以发现，总线嗅探方法很简单， CPU 需要每时每刻监听总线上的一切活动，但是不管别的核心的 Cache 是否缓存相同的数据，都需要发出一个广播事件，这无疑会加重总线的负载。

另外，总线嗅探只是保证了某个 CPU 核心的 Cache 更新数据这个事件能被其他 CPU 核心知道，但是并不能保证事务串形化。

于是，有一个协议基于总线嗅探机制实现了事务串形化，也用状态机机制降低了总线带宽压力，这个协议就是 MESI 协议，这个协议就做到了 CPU 缓存一致性。

MESI 协议

MESI 协议其实是 4 个状态单词的开头字母缩写，分别是：

  • Modified，已修改

  • Exclusive，独占

  • Shared，共享

  • Invalidated，已失效

这四个状态来标记 Cache Line 四个不同的状态。

「已修改」状态就是我们前面提到的脏标记，代表该 Cache Block 上的数据已经被更新过，但是还没有写到内存里。而「已失效」状态，表示的是这个 Cache Block 里的数据已经失效了，不可以读取该状态的数据。

「独占」和「共享」状态都代表 Cache Block 里的数据是干净的，也就是说，这个时候 Cache Block 里的数据和内存里面的数据是一致性的。

「独占」和「共享」的差别在于，独占状态的时候，数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。

另外，在「独占」状态下的数据，如果有其他核心从内存读取了相同的数据到各自的 Cache ，那么这个时候，独占状态下的数据就会变成共享状态。

那么，「共享」状态代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。

我们举个具体的例子来看看这四个状态的转换：

  1. 当 A 号 CPU 核心从内存读取变量 i 的值，数据被缓存在 A 号 CPU 核心自己的 Cache 里面，此时其他 CPU 核心的 Cache 没有缓存该数据，于是标记 Cache Line 状态为「独占」，此时其 Cache 中的数据与内存是一致的；

  2. 然后 B 号 CPU 核心也从内存读取了变量 i 的值，此时会发送消息给其他 CPU 核心，由于 A 号 CPU 核心已经缓存了该数据，所以会把数据返回给 B 号 CPU 核心。在这个时候， A 和 B 核心缓存了相同的数据，Cache Line 的状态就会变成「共享」，并且其 Cache 中的数据与内存也是一致的；

  3. 当 A 号 CPU 核心要修改 Cache 中 i 变量的值，发现数据对应的 Cache Line 的状态是共享状态，则要向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后 A 号 CPU 核心才更新 Cache 里面的数据，同时标记 Cache Line 为「已修改」状态，此时 Cache 中的数据就与内存不一致了。

  4. 如果 A 号 CPU 核心「继续」修改 Cache 中 i 变量的值，由于此时的 Cache Line 是「已修改」状态，因此不需要给其他 CPU 核心发送消息，直接更新数据即可。

  5. 如果 A 号 CPU 核心的 Cache 里的 i 变量对应的 Cache Line 要被「替换」，发现 Cache Line 状态是「已修改」状态，就会在替换前先把数据同步到内存。

所以，可以发现当 Cache Line 状态是「已修改」或者「独占」状态时，修改更新其数据不需要发送广播给其他 CPU 核心，这在一定程度上减少了总线带宽压力。

事实上，整个 MESI 的状态可以用一个有限状态机来表示它的状态流转。还有一点，对于不同状态触发的事件操作，可能是来自本地 CPU 核心发出的广播事件，也可以是来自其他 CPU 核心通过总线发出的广播事件。下图即是 MESI 协议的状态图：
在这里插入图片描述
MESI 协议的四种状态之间的流转过程，我汇总成了下面的表格，你可以更详细的看到每个状态转换的原因：
在这里插入图片描述

posted @ 2026-03-23 22:30  放飞梦想C  阅读(2)  评论(0)    收藏  举报