CPU cache 结构和缓存一致性(MESI 协议)

一、cache

cpu cache 已经发展到了三级缓存结构,基本上现在买的个人电脑都是 L3 结构。

1. cache 的意义

为什么需要 CPU cache?因为 CPU 的频率太快了,快到主存跟不上,这样在处理器时钟周期内,CPU 常常需要等待主存,浪费资源。所以 cache 的出现,是为了缓解 CPU 和内存之间速度的不匹配问题(结构:cpu -> cache -> memory)。
CPU cache 有什么意义?cache 的容量远远小于主存,因此出现 cache miss 在所难免,既然 cache 不能包含 CPU 所需要的所有数据,那么 cache 的存在真的有意义吗?当然是有意义的——局部性原理。

A. 时间局部性:如果某个数据被访问,那么在不久的将来它很可能被再次访问;
B. 空间局部性:如果某个数据被访问,那么与它相邻的数据很快也可能被访问;

2. cache 和寄存器

存储器的三个性能指标——速度、容量和每位价格——导致了计算机组成中存储器的多级层次结构,其中主要是缓存和主存、主存和磁盘的结构。那么在主存之上,cache 和寄存器之间的关系是?

举个例子,当你在思考一个问题的时候,寄存器存放的是你当前正在思考的内容,cache 存放的是与该问题相关的记忆,主存则存放无论与该问题是否有关的所有记忆,所以,寄存器存放的是当前 CPU 执行的数据,而 cache 则缓存与该数据相关的部分数据,因此只要保证了 cache 的一致性,那么寄存器拿到的数据也必然具备一致性

二、CPU cache 结构

1. 单核 CPU cache 结构


在单核 CPU 结构中,为了缓解 CPU 指令流水中 cycle 冲突,L1 分成了指令(L1P)和数据(L1D)两部分,而 L2 则是指令和数据共存。

2. 多核 CPU cache 结构


多核 CPU 的结构与单核相似,但是多了所有 CPU 共享的 L3 三级缓存。在多核 CPU 的结构中,L1 和 L2 是 CPU 私有的,L3 则是所有 CPU 核心共享的。

三、MESI(缓存一致性)

缓存一致性:在多核 CPU 中,内存中的数据会在多个核心中存在数据副本,某一个核心发生修改操作,就产生了数据不一致的问题。而一致性协议正是用于保证多个 CPU cache 之间缓存共享数据的一致。
至于 MESI,则是缓存一致性协议中的一个,到底怎么实现,还是得看具体的处理器指令集。

1. cache 的写方式

cache 的写操作方式可以追溯到大学教程《计算机组成原理》一书。
A. write through(写通):每次 CPU 修改了 cache 中的内容,立即更新到内存,也就意味着每次 CPU 写共享数据,都会导致总线事务,因此这种方式常常会引起总线事务的竞争,高一致性,但是效率非常低;
B. write back(写回):每次 CPU 修改了 cache 中的数据,不会立即更新到内存,而是等到 cache line 在某一个必须或合适的时机才会更新到内存中;
无论是写通还是写回,在多线程环境下都需要处理缓存 cache 一致性问题。为了保证缓存一致性,处理器又提供了写失效(write invalidate)和写更新(write update)两个操作来保证 cache 一致性。
写失效:当一个 CPU 修改了数据,如果其他 CPU 有该数据,则通知其为无效;
写更新:当一个 CPU 修改了数据,如果其他 CPU 有该数据,则通知其跟新数据;
写更新会导致大量的更新操作,因此在 MESI 协议中,采取的是写失效(即 MESI 中的 I:ivalid,如果采用的是写更新,那么就不是 MESI 协议了,而是 MESU 协议)。

2. cache line


cache line 是 cache 与内存数据交换的最小单位,根据操作系统一般是 32byte 或 64byte。在 MESI 协议中,状态可以是 M、E、S、I,地址则是 cache line 中映射的内存地址,数据则是从内存中读取的数据。
工作方式:当 CPU 从 cache 中读取数据的时候,会比较地址是否相同,如果相同则检查 cache line 的状态,再决定该数据是否有效,无效则从主存中获取数据,或者根据一致性协议发生一次 cache-to—chache 的数据推送(参见 MESI 协议,文章最后的链接);
工作效率:当 CPU 能够从 cache 中拿到有效数据的时候,消耗几个 CPU cycle,如果发生 cache miss,则会消耗几十上百个 CPU cycle;
cache 的工作原理以及在主板上的结构如下两图所示:

3. 状态介绍

MESI 协议将 cache line 的状态分成 modify、exclusive、shared、invalid,分别是修改、独占、共享和失效。

  • modify:当前 CPU cache 拥有最新数据(最新的 cache line),其他 CPU 拥有失效数据(cache line 的状态是 invalid),虽然当前 CPU 中的数据和主存是不一致的,但是以当前 CPU 的数据为准;
  • exclusive:只有当前 CPU 中有数据,其他 CPU 中没有改数据,当前 CPU 的数据和主存中的数据是一致的;
  • shared:当前 CPU 和其他 CPU 中都有共同数据,并且和主存中的数据一致;
  • invalid:当前 CPU 中的数据失效,数据应该从主存中获取,其他 CPU 中可能有数据也可能无数据,当前 CPU 中的数据和主存被认为是不一致的;
    对于 invalid 而言,在 MESI 协议中采取的是写失效(write invalidate)。

4. cache 操作

MESI 协议中,每个 cache 的控制器不仅知道自己的操作(local read 和 local write),每个核心的缓存控制器通过监听也知道其他 CPU 中 cache 的操作(remote read 和 remote write),今儿再确定自己 cache 中共享数据的状态是否需要调整。
local read(LR):读本地 cache 中的数据;
local write(LW):将数据写到本地 cache;
remote read(RR):其他核心发生 read;
remote write(RW):其他核心发生 write;

5. 状态转换和 cache 操作

如上文内容所述,MESI 协议中 cache line 数据状态有 4 种,引起数据状态转换的 CPU cache 操作也有 4 种,因此要理解 MESI 协议,就要将这 16 种状态转换的情况讨论清楚。
初始场景:在最初的时候,所有 CPU 中都没有数据,某一个 CPU 发生读操作,此时必然发生 cache miss,数据从主存中读取到当前 CPU 的 cache,状态为 E(独占,只有当前 CPU 有数据,且和主存一致),此时如果有其他 CPU 也读取数据,则状态修改为 S(共享,多个 CPU 之间拥有相同数据,并且和主存保持一致),如果其中某一个 CPU 发生数据修改,那么该 CPU 中数据状态修改为 M(拥有最新数据,和主存不一致,但是以当前 CPU 中的为准),其他拥有该数据的核心通过缓存控制器监听到 remote write 行文,然后将自己拥有的数据的 cache line 状态修改为 I(失效,和主存中的数据被认为不一致,数据不可用应该重新获取)

5.1 modify

场景:当前 CPU 中数据的状态是 modify,表示当前 CPU 中拥有最新数据,虽然主存中的数据和当前 CPU 中的数据不一致,但是以当前 CPU 中的数据为准;
LR:此时如果发生 local read,即当前 CPU 读数据,直接从 cache 中获取数据,拥有最新数据,因此状态不变;
LW:直接修改本地 cache 数据,修改后也是当前 CPU 拥有最新数据,因此状态不变;
RR:因为本地内存中有最新数据,当本地 cache 控制器监听到总线上有 RR 发生的时,必然是其他 CPU 发生了读主存的操作,此时为了保证一致性,当前 CPU 应该将数据写回主存,而随后的 RR 将会使得其他 CPU 和当前 CPU 拥有共同的数据,因此状态修改为 S;
RW:同 RR,当 cache 控制器监听到总线发生 RW,当前 CPU 会将数据写回主存,因为随后的 RW 将会导致主存的数据修改,因此状态修改成 I;

5.2 exclusive

场景:当前 CPU 中的数据状态是 exclusive,表示当前 CPU 独占数据(其他 CPU 没有数据),并且和主存的数据一致;
LR:从本地 cache 中直接获取数据,状态不变;
LW:修改本地 cache 中的数据,状态修改成 M(因为其他 CPU 中并没有该数据,因此不存在共享问题,不需要通知其他 CPU 修改 cache line 的状态为 I);
RR:本地 cache 中有最新数据,当 cache 控制器监听到总线上发生 RR 的时候,必然是其他 CPU 发生了读取主存的操作,而 RR 操作不会导致数据修改,因此两个 CPU 中的数据和主存中的数据一致,此时 cache line 状态修改为 S;
RW:同 RR,当 cache 控制器监听到总线发生 RW,发生其他 CPU 将最新数据写回到主存,此时为了保证缓存一致性,当前 CPU 的数据状态修改为 I;

5.3 shared

场景:当前 CPU 中的数据状态是 shared,表示当前 CPU 和其他 CPU 共享数据,且数据在多个 CPU 之间一致、多个 CPU 之间的数据和主存一致;
LR:直接从 cache 中读取数据,状态不变;
LW:发生本地写,并不会将数据立即写回主存,而是在稍后的一个时间再写回主存,因此为了保证缓存一致性,当前 CPU 的 cache line 状态修改为 M,并通知其他拥有该数据的 CPU 该数据失效,其他 CPU 将 cache line 状态修改为 I;
RR:状态不变,因为多个 CPU 中的数据和主存一致;
RW:当监听到总线发生了 RW,意味着其他 CPU 发生了写主存操作,此时本地 cache 中的数据既不是最新数据,和主存也不再一致,因此当前 CPU 的 cache line 状态修改为 I;

5.4 invalid

场景:当前 CPU 中的数据状态是 invalid,表示当前 CPU 中是脏数据,不可用,其他 CPU 可能有数据、也可能没有数据;
LR:因为当前 CPU 的 cache line 数据不可用,因此会发生读内存,此时的情形如下。
A. 如果其他 CPU 中无数据则状态修改为 E;
B. 如果其他 CPU 中有数据且状态为 S 或 E 则状态修改为 S;
C. 如果其他 CPU 中有数据且状态为 M,那么其他 CPU 首先发生 RW 将 M 状态的数据写回主存并修改状态为 S,随后当前 CPU 读取主存数据,也将状态修改为 S;
LW:因为当前 CPU 的 cache line 数据无效,因此发生 LW 会直接操作本地 cache,此时的情形如下。
A. 如果其他 CPU 中无数据,则将本地 cache line 的状态修改为 M;
B. 如果其他 CPU 中有数据且状态为 S 或 E,则修改本地 cache,通知其他 CPU 将数据修改为 I,当前 CPU 中的 cache line 状态修改为 M;
C. 如果其他 CPU 中有数据且状态为 M,则其他 CPU 首先将数据写回主存,并将状态修改为 I,当前 CPU 中的 cache line 转台修改为 M;
RR:监听到总线发生 RR 操作,表示有其他 CPU 读取内存,和本地 cache 无关,状态不变;
RW:监听到总线发生 RW 操作,表示有其他 CPU 写主存,和本地 cache 无关,状态不变;

5.5 总结

MESI 协议为了保证多个 CPU cache 中共享数据的一致性,定义了 cache line 的四种状态,而 CPU 对 cache 的 4 种操作可能会产生不一致状态,因此 cache 控制器监听到本地操作和远程操作的时候,需要对地址一致的 cache line 状态做出一定的修改,从而保证数据在多个 cache 之间流转的一致性。