“了解高并发底层原理”,面试官:讲一下MESI(缓存一致性协议)吧

YuShiwen 发表于 2022/03/31 10:25:44 2022/03/31
【摘要】 JVM不是真实存在的,只是一个抽象的概念。volatile关键字底层也是借助MESI缓存一致性协议和内存屏障得以实现有序性和可见性的。 MESI是计算机底层的协议,所有支持高并发的编程语言的底层都是基于MESI协议来保证并发安全的,所以MESI协议更有助于我们去理解底层原理,知其所以然! 本期围绕着,什么是(Who),为何来(How),是什么(What),这三点内容来进行讲解该协议。

前言:

  • JVM不是真实存在的,只是一个抽象的概念。volatile关键字底层也是借助MESI缓存一致性协议和内存屏障得以实现有序性和可见性的。
  • MESI是计算机底层的协议,所有支持高并发的编程语言的底层都是基于MESI协议来保证并发安全的,所以MESI协议更有助于我们去理解底层原理,知其所以然!
  • 本期围绕着,什么是(Who),为何来(How),是什么(What),这三点内容来进行讲解该协议。

1.什么是(Who):

MESI(Modified Exclusive Shared Or Invalid)协议是基于Invalidate的高速缓存一致性协议,并且是支持回写高速缓存的最常用协议之一。 它也被称为伊利诺伊州协议(由于其在伊利诺伊大学厄巴纳 - 香槟分校的发展)。用于解决缓存一致的问题。


2.为何来(How):

2.1缓存不一致带来的后果

在这里插入图片描述
如上图,数据加载的流程如下:(从内存到寄存器)

  1. 将程序和数据从硬盘加载到内存中

  2. 将程序和数据从内存加载到缓存中(目前多三级缓存,数据加载顺序:L3->L2->L1)

  3. CPU将缓存中的数据加载到寄存器中,并进行运算

  4. CPU会将数据刷新回缓存,并在一定的时间周期之后刷新回内存

现在的CPU基本都是多核CPU,服务器更是提供了多CPU的支持,而每个核心也都有自己独立的缓存,当多个核心同时操作多个线程对同一个数据进行更新时,如果核心2在核心1还未将更新的数据刷回内存之前读取了数据,并进行操作,就会造成程序的执行结果造成随机性的影响,举个例子如下:

如果由两个cpu同事开始读取了int i =0,然后同同时执行如下语句,会出现如下情况:

......
int i = 0;
i++;
......

刚开始,i初始化为0,假设有两个线程A,B,

  1. A线程在CPU0上进行执行,从主存加载i变量的数值到缓存,然后从缓存中加载到寄存器中,在寄存器中执行i+1操作,得到i的值为1,此时得到i等于1的值还存放在CPU0的缓存中;
  2. 由于线程A计算i等于1的值还存放在缓存中,还没有刷新会内存,此时线程B执行在CPU1上,从内存中加载i的值,此时i的值还是0,然后进行i+1操作,得到i的值为1,存到CPU1的缓存中,
  3. A,B线程得到的值都是1,在一定的时间周期之后刷新回内存
    4.写回内存后,两次i++操作之后,其值还是1;
    可以看到虽然我们做了两次++i操作,但是只进行了一次加1操作,这就是缓存不一致带来的后果。

2.2解决方法:

在先前的解决方案中,大致有两种思路:
总线加锁的方式:

  • 先前大佬们提供了一种总线加锁的方式,而总线加锁是对整个内存进行加锁,在一个核心对一个数据进行修改的过程中,其他的核心也无法修改内存中的其他数据,这样对导致CPU处理性能严重下降。

总线加锁的方式导致CPU性能严重下降,此时我们提出了缓存一致性协议(MESI):

  • 缓存一致性协议提供了一种高效的内存数据管理方案,它只会对单个缓存行(缓存行是缓存中数据存储的基本单元)的数据进行加锁,不会影响到内存中其他数据的读写。
  • cache line,缓存行是为了简化与RAM之间的通信,高速缓存控制器是针对数据块,而不是字节进行操作的。从程序设计的角度讲,高速缓存其实就是一组称之为缓存行(cache line)的固定大小的数据块。

因此,我们引入了缓存一致性协(MESI)议来对内存数据的读写进行管理。


3.是什么(What)

3.1数据在缓存中的四种状态:

MESI的英文全程为:Modified Exclusive Shared Or Invalid,有四种状态,分别对应其英文单词,如下:

状态 具体描述 状态所在缓存对应的CPU是否独占数据 cache line 是否是最新数据 对数据的写入
M: 被修改(Modified) 该缓存行只被缓存在该CPU的缓存中,并且是被修改过的(dirty),即与主存中的数据不一致,该缓存行中的数据需要在未来的某个时间点(允许其它CPU读取主存中相应数据之前)写回(write back)主存。当被写回主存之后,该缓存行的状态会变成独享(exclusive)状态。 可以
E: 独享的(Exclusive) 该数据只被缓存在该CPU的缓存行中,它是未被修改过的(clean),与主存中数据一致。该状态可以在任何时刻当有其它CPU读取该内存时变成共享状态(shared)。同样地,当CPU修改该缓存行中内容时,该状态可以变成Modified状态。 可以
S: 共享的(Shared) 该状态意味着该数据可能被多个CPU缓存读取,并且各个缓存中的数据与主存数据一致(clean),当有一个CPU修改自己的缓存行中的数据时,数据对应的缓存行状态变成Modified状态,其它CPU中该缓存行变成无效状态(Invalid)。 可以
I: 无效的(Invalid) 该缓存是无效的(可能有其它CPU修改了该缓存行)。 否 (无数据) 无数据 无数据,不可以

3.2MESI的六种消息(请求消息和响应消息)

cpu接收响应消息的顺序决定了其他cpu感知到的当前线程的执行顺序

  1. read:(请求消息)
    “read” 消息用来获取指定物理地址上的 cache line(如果在缓存中,从缓存中取,不在缓存中则从内存中取) 数据。
  2. read response:(响应消息)
    "read response"消息包含先前“read”消息请求的数据。此“read response”消息可能来自内存或其他CPU的缓存。
  3. invalidate:(请求消息)
    Invalidate。该消息将其他 CPU cache 中指定的数据设置为失效。该消息携带物理地址,其他 CPU cache 在收到该消息后,必须进行匹配,发现在自己的 cache line 中有该地址的数据,那么就将其从 cahe line 中移除,并响应 Invalidate Acknowledge 回应。
  4. invalidate acknowledge:(响应消息)
    该消息用做回应 Invalidate 消息。
  5. read invalidate:(请求消息)
    该消息中带有物理地址,用来说明想要读取哪一个 cache line 中的数据,同时指示其他缓存删除数据。可以看作是 read + Invalidate 消息的组合,“read invalidate”消息需要“read response”和一组“invalidate acknowledge”消息作为应答。
  6. writeback:
    “writeback”消息包含要写回内存的地址和数据(也可能是沿途“窥探”到其他cpu的缓存中)。该消息用在 modified 状态的 cache line 被置换时发出,用来将最新的数据写回 memory 或其他下一级 cache 中。

3.3MESI四种状态通过六种消息进行转换(利用3.1与3.2章节的知识点)

在这里插入图片描述
上图的转换详细说明:

  • a
    cache 通过 writeback 将数据回写到 memory 或者下一级 cache 中。这时候状态由 modified 变成了 exclusive 。
  • b
    cpu 直接将数据写入 cache line ,导致状态变为了 modified 。
  • c
    CPU 收到一个 read invalidate 消息,该消息中带有物理地址,用来说明想要读取哪一个 cache line 中的数据,同时指示其他缓存删除数据。此时 CPU 必须将对应 cache line 设置成 invalid 状态 , 并且响应一个 read response 消息和 invalidate acknowledge 消息。
  • d
    CPU 需要执行一个原子的 readmodify-write 操作,并且其 cache 中没有缓存数据。这时候 CPU 就会在总线上发送一个 read invalidate 消息来请求数据,并试图独占该数据。CPU 可以通过收到的 read response 消息获取到数据,并等待所有的 invalidate acknowledge 消息,然后将状态设置为 modifie 。
  • e
    CPU需要执行一个原子的readmodify-write操作,并且其local cache中有read only的缓存数据(cacheline处于shared状态),这时候,CPU就会在总线上发送一个invalidate请求其他cpu清空自己的local copy,以便完成其独自霸占对该数据的所有权的梦想。同样的,该cpu必须收集所有其他cpu发来的invalidate acknowledge之后才能更改状态为 modified。
  • f
    在本cpu独自享受独占数据的时候,其他的cpu发起read请求,希望获取数据,这时候,本cpu必须以其local cacheline的数据回应,并以read response回应之前总线上的read请求。这时候,本cpu失去了独占权,该cacheline状态从Modified状态变成shared状态(有可能也会进行写回的动作)。
  • g
    这个迁移和f类似,只不过开始cacheline的状态是exclusive,cacheline和memory的数据都是最新的,不存在写回的问题。总线上的操作也是在收到read请求之后,以read response回应。
  • h
    需要发送invalidate以通知其他cpu相应数据将要失效,并等待其他cpu的回应消息(invalidate acknowledge)。
  • i
    其他的CPU进行一个原子的read-modify-write操作,但是,数据在本cpu的cacheline中,因此,其他的那个CPU会发送read invalidate,请求对该数据以及独占权。本cpu回送read response”和“invalidate acknowledge”,一方面把数据转移到其他cpu的cache中,另外一方面,清空自己的cacheline。
  • j
    cpu想要进行write的操作但是数据不在local cache中,因此,该cpu首先发送了read invalidate启动了一次总线transaction。在收到read response回应拿到数据,并且收集所有其他cpu发来的invalidate acknowledge之后(确保其他cpu没有local copy),完成整个bus transaction。当write操作完成之后,该cacheline的状态会从Exclusive状态迁移到Modified状态。
  • k
    本CPU执行读操作,发现local cache没有数据,因此通过read发起一次bus transaction,来自其他的cpu local cache或者memory会通过read response回应,从而将该 cache line 从Invalid状态迁移到shared状态。
  • l
    当cache line处于shared状态的时候,说明在多个cpu的local cache中存在副本,因此,这些cacheline中的数据都是read only的,一旦其中一个cpu想要执行数据写入的动作,必须先通过invalidate获取该数据的独占权,而其他的CPU会以invalidate acknowledge回应,清空数据并将其cacheline从shared状态修改成invalid状态。

该篇已完结
后续将在写一篇博文介绍在Java语言中某个关键字的底层是如何用到MESI协议以及内存屏障的。
author:YuShiwen
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。