“了解高并发底层原理”，面试官：讲一下MESI（缓存一致性协议）吧

前言：

• 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，有四种状态，分别对应其英文单词，如下：

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状态。