0%

CPU缓存与MESI

CPU缓存的定义为CPU与内存之间的临时数据交换器,它的出现是为了解决CPU运行处理速度与内存读写速度不匹配的矛盾。但是随着多级独享CPU缓存的引入,同时也引入了数据一致性的问题,如何保证各个缓存之间的数据一致性?

高速缓存

早期的计算机系统中,CPU的频率和内存总线的频率基本上是同一个级别的,内存的访问速度只比寄存器慢一点,从上世纪90年代开始,CPU的频率飞速发展,但是内存总线的频率和内存芯片的性能却没有得到等比例提升,主要原因在于内存的成本太贵了,如果要达到CPU那样的速度,造价会比现有的内存贵好几个数量级。

好在这个问题并非一个非黑即白的选择,CPU高速缓存,便是用来解决上述问题,先来看看CPU高速缓存的结构。

1

在CPU内核与主存之间,存在一个Cache(高速缓存),早期的高速缓存只有一级,但是随着计算机硬件不断发展,导致高速缓存与主存之间的速度差异进一步拉大,从而引入了上图右侧的多级缓存的策略,例如现代计算机常用的三级缓存策略。

CPU高速缓存都是集成在CPU内的缓存,L1最靠近CPU核心,L2次之,L3再次。运行速度方面:L1最快、L2次快、L3最慢(参考下图);容量大小方面则正好相反:L1最小、L2较大、L3最大。

1

L1和L2只能被单个CPU内核使用,L3则可以被同一个插槽上的所有CPU内核使用。

CPU要读取一个数据的时候,依次从L1,L2,L3,主存中进行查找,再把找到的数据依次加载到多级缓存中。

为了更快的执行代码,在加载数据的时候,并不是只加载自己想要的那部分,而是会加载一个Cache Line,Cache Line可以理解为是CPU缓存中的最小缓存单位,在64位系统中,一个Cache Line的大小为64字节,这样当CPU访问相邻的数据时,就不需要再从内存中进行读取。

Cache Line的加载逻辑,引出了一个著名的伪共享(false sharing)问题,有兴趣的同学可以阅读一下【杂谈 什么是伪共享】。

MESI

高速缓存的引入,同时带来了多核并发下的数据可见性的问题,假设有如下场景:

  • CPU-1读取某个Cache line,同时放入CPU-1的高速缓存中;
  • CPU-1修改了Cache line中的数据,然后数据被放回高速缓存中,但是数据并没有及时写入主存;
  • CPU-2访问同一个Cache line,从主存中获取数据;
  • 由于CPU-1还没来得及写回主存,因此此时出现了数据不同步的问题。

针对此问题,衍生出一个规则:CPU-A修改了其高速缓存中的数据时,需要通知其他也持有当前数据的CPU-N,CPU-N会将其缓存的数据失效;当CPU-N需要重新读取数据时,会通知CPU-A回写缓存到主存,然后CPU-N才能读取数据。

基于此规则,衍生出很多一致性的协议,比如MESI。在MESI协议中,每个Cache line有4个状态,用来描述Cache和主存之间的数据关系:

状态 含义
M(Modified) 数据有效;数据被修改了,和内存中的数据不一致;数据只存在于本Cache中。
E(Exclusive) 数据有效;数据和内存中的数据一致;数据只存在于本Cache中。
S(Shared) 数据有效;数据和内存中的数据一致;数据存在于多个Cache中。
I(Invalid) 数据无效。

一个Cache line在不同缓存中的状态兼容关系为:

M E S I
M ✔️
E ✔️
S ✔️ ✔️
I ✔️ ✔️ ✔️ ✔️

举几个实际的例子,假设主存中x=3,如下场景为两个CPU操作数据的几种场景:

1

  • A:单CPU加载缓存

    CPU-1发出指令读取数据的时候,由于没有其他CPU持有当前Cache line,则CPU-1的缓存中,Cache line的状态被置位E。

  • B:多个CPU加载缓存

    CPU-2发出指令需要读取数据,CPU-1检测到了地址冲突。此时x存在于两个CPU中,并且状态都被置位了S。

  • C:某个CPU修改了缓存

    CPU-1发出执行需要修改x的值,CPU-1将Cache line的状态设置为M,并且通知同样缓存了x的CPU-2,CPU-2将本地缓存x的Cache line状态设置为I。

  • D-E:其他CPU读取状态为I的数据

    CPU-2发出指令需要读取数据,此时需要分为两步状态。

    • D:CPU-2通知CPU-1,CPU-1将修改之后的数据同步回主存,同时将Cache line中的状态置为E;
    • E:在D的基础上,CPU-2需要读取数据,此时的状态变换类似于B,x被加载到两个CPU的缓存中,同时状态都被置为了S。

更为详细的切换如下表:

  • LC:本地Cache,当前CPU中的Cache;
  • CC:触发Cache,触发读写事件的Cache,如果是本地事件触发,则触发Cache即是本地Cache;
  • OC:其他Cache,除了上述两种之外,其他CPU持有的Cache。
  • 本地读取:当前CPU读取本地Cache数据;
  • 本地写入:当前CPU更新本地Cache数据;
  • 远端读取:其他CPU读取本地Cache数据;
  • 远端写入:其他CPU更新本地Cache数据。
Cache状态 触发本地读取 触发本地写入 触发远端读取 触发远端写入
M LC:M
CC:M
OC:I
LC:M
CC:M
OC:I
LC:M→E→S
CC:I→S
OC:I→S
LC:M→E→S→I
CC:I→S→E→M
OC:I→S→I
E LC:E
CC:E
OC:I
LC:E->M
CC:E->M
OC:I
LC:E->S
CC:I->S
OC:S
LC:E->S->I
CC:I->S->E->M
OC:I->S->I
S LC:S
CC:S
OC:S
LC:S->E->M
CC:S->E->M
OC:S->I
LC:S
CC:S
OC:S
LC:S->I
CC:S->E->M
OC:S->I
I LC:I->S/E
CC:I->S/E
OC:E/M/I->S/I
LC:I->S->E->M
CC:I->S->E->M
OC:M/E/S->S->I
与本地Cache无关 与本地Cache无关

Store Buffers与Invalidate Queues

除了Store Buffers,有些架构的CPU还有Load Buffer,用于读取数据时候的缓存,这里不做介绍。

上述一致性协议能解决数据一致性的问题,但是却引入了一个性能问题:某个CPU要写数据项时,必须先通知其他CPU,将该数据项从其他CPU的cache中移出, 这个操作叫做invalidation,当操作结束之后,CPU就可以安全的修改数据了。在invalidation操作结束之前,CPU会一直等待其他CPU回ACK,这会降低处理器的性能,因为这个等待远远比一个指令的执行时间长很多。

为了避免CPU的运算能力浪费,引入了Store Buffers与Invalidate Queues。

  • Store Buffers

    临时保存需要向内存写入的数据,处理器把要写入主存的值写到缓冲区中,然后继续去处理其他事情,让CPU从等待中解放出来。当所有的通知处理都完成之后,数据才会最终被提交。

    Store Buffers可以保证CPU持续运行,不需要停顿下来等待数据往内存写入的过程。同时,通过批处理的方式刷新写缓冲区,以及合并写缓冲区中对同一内存地址的多次写,可以减少对内存总线的占用。

    注意,当处理器需要读取某个数据的时候,会先去扫描Store Buffers里面是否存在,如果存在的话,会直接使用获取到的值,这个操作也叫做”Store Forwarding“。

    如果不扫描Store Buffers里的值的话,会导致更新一个数据之后,再去读这个数据的话,更新的值在Store Buffers里面,再去读的值可能会从Cache line中获取,因此导致数据不一致。

  • Invalidate Queues

    Store Buffers一般很小,所以CPU的几个store操作就可能填满,填满之后,CPU还是必须要等待invalidation操作的ACK,从而释放Store Buffers。于是衍生出Invalidate Queues,使用Invalidate Queues将invalidate消息入队列,然后立马回复invalidate ACk的消息,然后CPU会尽快处理Invalidate Queues中的数据。

    注意,跟Store Buffers不同的是,CPU读取数据时,并不会扫描Invalidate Queues。

引入的Store Buffers与Invalidate Queues,大大提高了CPU的效率,但是却引入了内存数据一致性的问题,假设有如下场景:

1
2
3
4
5
6
7
8
9
10
int value = 2;
void cpuA() {
value = 10;
flag = true;
}
void cpuB() {
if (flag) {
assert value == 10;
}
}
  • CPU-A和CPU-B都在高速缓存中,缓存了value变量,则value的缓存状态为S;
  • flag变量只存在于CPU-A中,则flag在CPU-A中的缓存状态为E;

  • CPU-A执行函数:

    • 执行value=10时,value的缓存状态由S变成M(修改);
    • CPU-A将修改操作存入Store Buffers中,缓冲区会通知其他CPU进行数据失效操作,待通知完毕之后将数据写入主存;
    • CPU-A继续执行flag=true,由于flag缓存状态是E,则可以直接修改Cache line,不需要写入到Store Buffers中。
  • CPU-B执行函数:

    • 由于flag没有存在在CPU-B中,因此执行if判断时,CPU-B向总线发出信号读取flag,得到CPU-A修改之后的值true,判断通过,同时CPU-A和CPU-B中的flag缓存状态均为S;
    • 执行assert的时候,假设CPU-A发送的数据失效的通知还存在于Invalidate Queue,没有来得及处理,那么此时value在CPU-B中的值还是2,并且由于Cache line的状态是S,则CPU-B会直接从Cache中取value的值,即是2,导致assert失败。

memory barrier(内存屏障)

我们发现在硬件层面,很难做到在满足高并发时候高性能的同时,能兼顾数据一致性的问题,因为在优化过程中,从硬件层面也很难知道调用者的意图。既然硬件层面没法处理,那么就提供一些功能,让写代码的人来告诉硬件该如何操作,从而控制缓存可见性的某些行为。

这里提供的功能,就是内存屏障指令,在X86的系统中,主要的内存屏蔽指令有:

  • StoreMemoryBarrier(写屏障):这个内存屏障的操作会在执行后续的store操作之前刷新Store Buffers,也就是将之前缓存在Store Buffers中的的值写入到Cache Line中。
  • LoadMemoryBarrier(读屏障):在指令前插入Load Barrier,可以让高速缓存中的数据失效,强制重新从主内存加载数据。

上述案例加入内存屏障指令之后,可以优化成如下形式,以解决数据不可见的问题:

1
2
3
4
5
6
7
8
9
10
11
12
int value = 2;
void cpuA() {
value = 10;
storeMemoryBarrir();
flag = true;
}
void cpuB() {
if (flag) {
loadMemoryBarrier();
assert value == 10;
}
}
  • cpuA函数执行到storeMemoryBarrir的时候,会强制让value刷新到Cache line中;
  • cpuB函数执行到loadMemoryBarrier的之后,会让告诉缓存中的数据失效,从而发送指令给总线获取value的值。

指令重排序

大多数现代计算机为了提高性能,采用了指令级并行技术(Instruction-Level Parallelism, ILP)来将多条指令重叠执行,如果不存在数据依赖性,处理器可以改变语句对应机器指令的执行顺序。这种优化在也会导致多处理器之间的数据一致性的问题,而使用内存屏障也可以解决这一类问题。

内存屏障使得CPU在对内存进行操作的时候,严格按照一定的顺序来执行,内存屏障之前的所有写操作都要写入内存;内存屏障之后的读操作都可以获得同步屏障之前的写操作的结果。

参考



-=全文完=-