缓存一致性协议MESI

明明记得在哪里学过这部分内容,还看到过一个贼好的图。。今天找了很久又没找着,这就是学了不记笔记的后果。。

本文参考资源:

CPU体系结构之cache小结_运维_Hober-CSDN博客

001-CPU多级缓存架构 - bjlhx15 - 博客园

volatile与内存屏障_Java_weiqing的博客-CSDN博客

极客时间《深入浅出计算机组成原理》

缓存一致性问题

在现代的CPU(大多数)上,所有的内存访问都需要通过层层的缓存来进行。也有些例外,比如,对映射成内存地址的I/O口、写合并(Write-combined)内存,这些访问至少会绕开这个流程的一部分。但这两者都是罕见的场景(意味着绝大多数的用户态代码都不会遇到这两种情况)。并且由于程序通常具有良好的时间局部性和空间局部性,缓存对提高程序运行的效率起到很大帮助。

存储器层次

然而上面这张图没有表示清楚的是,三级缓存和CPU核心之间的关系:(由于没有找到之前看过的那张图特意找了三张图好表示清楚)

缓存一致性协议MESI

缓存一致性协议MESI

缓存一致性协议MESI

L1是最接近CPU的,它容量最小,速度最快,每个核上都有一个L1 Cache(准确地说每个核上有两个L1 Cache,一个存数据 L1d Cache,一个存指令 L1i Cache)

L2 Cache 更大一些,例如256K,速度要慢一些,一般情况下每个核上都有一个独立的L2 Cache;二级缓存就是一级缓存的缓冲器:一级缓存制造成本很高因此它的容量有限,二级缓存的作用就是存储那些CPU处理时需要用到、一级缓存又无法存储的数据。

L3 Cache是三级缓存中最大的一级,例如12MB,同时也是最慢的一级,在同一个CPU插槽之间的核共享一个L3 Cache。三级缓存和内存可以看作是二级缓存的缓冲器,它们的容量递增,但单位制造成本却递减。

我电脑上的CPU cache

高速缓存行的结构这里不提,有时间把CSAPP里面的笔记放上来。

那么这样设计的问题是什么呢?因为 CPU 的每个核各有各的缓存,互相之间的操作又是各自独立的,就会带来缓存一致性(Cache Coherence)的问题。

这里需要先提到cache写机制

cache写机制

Write-through(直写模式)在数据更新时,同时写入缓存Cache和后端存储。此模式的优点是操作简单;缺点是因为数据修改需要同时写入存储,数据写入速度较慢。

Write-back(回写模式)在数据更新时只写入缓存Cache。只在数据被替换出缓存时,被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快,因为不需要写存储;缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况,数据将无法找回。

缓存一致性问题

试想下面这样一个情况。

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

为了解决这个缓存不一致的问题,我们就需要有一种机制,来同步两个不同核心里面的缓存数据。那这样的机制需要满足什么条件呢?我觉得能够做到下面两点就是合理的。

第一点叫写传播(Write Propagation)。写传播是说,在一个CPU 核心里,我们的 Cache 数据更新,必须能够传播到其他的对应节点的 Cache Line 里。

第二点叫事务的串行化(Transaction Serialization),事务串行化是说,我们在一个 CPU 核心里面的读取和写入,在其他的节点看起来,顺序是一样的。

写传播很容易理解。既然我们数据写完了,自然要同步到其他 CPU 核的 Cache 里。而事务的串行化,则是指假设很短时间内,一个数据被两次修改,并且分别是由两个CPU核心处理的,当它们同步数据更改到其他核心的时候,可能会出现顺序不一致的问题,即对不同的核心表现为修改的顺序不一致,造成最终结果不一致。

而在 CPU Cache 里做到事务串行化,需要做到两点,第一点是一个 CPU 核心对于数据的操作,需要同步通信给到其他 CPU 核心。第二点是,如果两个 CPU 核心里有同一个数据的 Cache,那么对于这个 Cache 数据的更新,需要有一个“锁”的概念。只有拿到了对应 Cache Block 的“锁”之后,才能进行对应的数据更新。接下来,我们就看看实现了这两个机制的 MESI 协议。

总线嗅探与MESI协议

总线嗅探

要解决缓存一致性问题,首先要解决的是多个 CPU 核心之间的数据传播问题。最常见的一种解决方案呢,叫作总线嗅探

这个策略,本质上就是把所有的读写请求都通过总线(Bus)广播给所有的 CPU 核心,然后让各个核心去“嗅探”这些请求,再根据本地的情况进行响应。

基于总线嗅探机制,其实还可以分成很多种不同的缓存一致性协议。不过其中最常用的,就是今天我们要讲的 MESI 协议。和很多现代的 CPU 技术一样,MESI 协议也是在 Pentium 时代,被引入到 Intel CPU 中的。

MESI协议

MESI 协议,是一种叫作写失效(Write Invalidate)的协议。在写失效协议里,只有一个 CPU 核心负责写入数据,其他的核心,只是同步读取到这个写入。在这个 CPU 核心写入 Cache 之后,它会去广播一个“失效”请求告诉所有其他的 CPU 核心。其他的 CPU 核心,只是去判断自己是否也有一个“失效”版本的 Cache Block,然后把这个也标记成失效的就好了。

相对于写失效协议,还有一种叫作写广播(Write Broadcast)的协议。在那个协议里,一个写入请求广播到所有的 CPU 核心,同时更新各个核心里的 Cache。

写广播在实现上自然很简单,但是写广播需要占用更多的总线带宽。写失效只需要告诉其他的 CPU 核心,哪一个内存地址的缓存失效了,但是写广播还需要把对应的数据传输给其他 CPU 核心。

MESI 协议的由来呢,来自于我们对 Cache Line 的四个不同的标记,分别是:

  • M:代表已修改(Modified)
  • E:代表独占(Exclusive)
  • S:代表共享(Shared)
  • I:代表已失效(Invalidated)

MESI状态机

我们先来看看“已修改”和“已失效”,这两个状态比较容易理解。所谓的“已修改”,就是“脏”的 Cache Block。Cache Block 里面的内容我们已经更新过了,但是还没有写回到主内存里面。而所谓的“已失效”,自然是这个 Cache Block 里面的数据已经失效了,我们不可以相信这个 Cache Block 里面的数据。

然后,我们再来看“独占”和“共享”这两个状态。这就是 MESI 协议的精华所在了。无论是独占状态还是共享状态,缓存里面的数据都是“干净”的。这个“干净”,自然对应的是前面所说的“脏”的,也就是说,这个时候,Cache Block 里面的数据和主内存里面的数据是一致的。

那么“独占”和“共享”这两个状态的差别在哪里呢?这个差别就在于,在独占状态下,对应的 Cache Line 只加载到了当前 CPU 核所拥有的 Cache 里。其他的 CPU 核,并没有加载对应的数据到自己的 Cache 里。这个时候,如果要向独占的 Cache Block 写入数据,我们可以自由地写入数据,而不需要告知其他 CPU 核。

在独占状态下的数据,如果收到了一个来自于总线的读取对应缓存的请求,它就会变成共享状态。这个共享状态是因为,这个时候,另外一个 CPU 核心,也把对应的 Cache Block,从内存里面加载到了自己的 Cache 里来。

在共享状态下,因为同样的数据在多个 CPU 核心的 Cache 里都有。所以,当我们想要更新 Cache 里面的数据的时候,不能直接修改,而是要先向所有的其他 CPU 核心广播一个请求,要求先把其他 CPU 核心里面的 Cache,都变成无效的状态,然后再更新当前 Cache 里面的数据。这个广播操作,一般叫作 RFO(Request For Ownership),也就是获取当前对应 Cache Block 数据的所有权。

当前状态

事件

行为

下一个状态

I(Invalid)

Local Read

如果其它Cache没有这份数据,本Cache从内存中取数据,Cache line状态变成E;

如果其它Cache有这份数据,且状态为M,则将数据更新到内存,本Cache再从内存中取数据,2个Cache 的Cache line状态都变成S;

如果其它Cache有这份数据,且状态为S或者E,本Cache从内存中取数据,这些Cache 的Cache line状态都变成S

E/S

Local Write

从内存中取数据,在Cache中修改,状态变成M;

如果其它Cache有这份数据,且状态为M,则要先将数据更新到内存;

如果其它Cache有这份数据,则其它Cache的Cache line状态变成I

M

Remote Read

既然是Invalid,别的核的操作与它无关

I

Remote Write

既然是Invalid,别的核的操作与它无关

I

E(Exclusive)

Local Read

从Cache中取数据,状态不变

E

Local Write

修改Cache中的数据,状态变成M

M

Remote Read

数据和其它核共用,状态变成了S

S

Remote Write

数据被修改,本Cache line不能再使用,状态变成I

I

S(Shared)

Local Read

从Cache中取数据,状态不变

S

Local Write

修改Cache中的数据,状态变成M,

其它核共享的Cache line状态变成I

M

Remote Read

状态不变

S

Remote Write

数据被修改,本Cache line不能再使用,状态变成I

I

M(Modified)

Local Read

从Cache中取数据,状态不变

M

Local Write

修改Cache中的数据,状态不变

M

Remote Read

这行数据被写到内存中,使其它核能使用到最新的数据,状态变成S

S

Remote Write

这行数据被写到内存中,使其它核能使用到最新的数据,由于其它核会修改这行数据,

状态变成I

I

MESI协议与java volatile关键字的关系

既然CPU有缓存一致性协议(MESI),为什么JMM还需要volatile关键字? - 知乎

volatile的语义有:
1. 保证了不同线程对这个变量进行操作时的可见性,即一个线程修改了某个变量的值,这新值对其他线程来说是立即可见的。
2. 禁止进行指令重排序

对于x86的体系结构,voltile变量的访问代码会被java编译器生成不乱序的,带有lock指令前缀的机器码。而lock的实现还要区分,这个数据在不在CPU核心的专有缓存中(一般是指L1/L2)。如果在,MESI才有用武之地。如果不满足就会要用其他手段,涉及到内存屏障。

通过反汇编可以发现,Java中volatile变量修饰的共享变量在进行写操作时候会多出一行汇编:

lock addl $0×0,(%esp);

在x86架构中,Lock前缀指令可以用作storeLoad barrier,在支持SSE2拓展指令集的cpu上还可以使用mfence指令。在多核处理器环境中,lock前缀指令保证了某个处理器对共享内存的独占使用。内存屏障不仅仅是MESI这么简单。

多处理器总线嗅探:
1. 为了提高处理速度,处理器不直接和内存进行通信,而是先将系统内存的数据读到内部缓存后在进行操作,但写回操作不知道这个更改何时回写到内存。
2. 但是对变量使用volatile进行写操作时,JVM就会向处理器发送一条lock前缀的指令,将这个变量所在的缓存行的数据写回到系统内存。
3. 在多处理器中,为了保证各个处理器的缓存一致性,每个处理器通过嗅探在总线上传播的数据来检查自己的缓存值是不是过期了,如果处理器发现自己缓存行对应的内存地址被修改,就会将当前处理器的缓存行设置为无效状态,就相当于写回时发现状态标识为0失效,当这个处理器对数据进行修改操作时,会重新从系统内存中读取数据到CPU缓存中。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%bc%93%e5%ad%98%e4%b8%80%e8%87%b4%e6%80%a7%e5%8d%8f%e8%ae%aemesi/

发表评论

电子邮件地址不会被公开。