dslztx
0%

MESI协议

发表于 更新于 专题于 Disqus：

在多核CPU中，每个CPU核内都有高速缓存——L1高速缓存和L2高速缓存，由于这些高速缓存缓存相同主存，因此需要高速缓存一致性协议来确保高速缓存状态和操作的语义一致性；而L3高速缓存是属于多CPU核共享的，因此不存在一致性问题。

在众多的高速缓存一致性协议中，MESI协议是应用较为广泛的一种，本文接下来就主要介绍MESI协议。

需要说明的是，如无特别说明，接下来的“缓存”和“Cache”均代指“高速缓存”。

一、MESI协议简介

MESI协议是众多高速缓存一致性协议中的一种，它支持的高速缓存写策略是：Write Back（写回）。

另外，需要提及的一点是：存在一个选择，具体是“当某个CPU核A需要访问的数据不在A内缓存，而另一个CPU核B内缓存存在所需数据，那么此时A是从B内缓存复制数据到本地缓存，还是从主存复制数据到本地缓存（后者显而易见会增加主存总线的锁住时间，采用前者可提高主存的存取速度）？”，对于这个选择，MESI协议本身并未作出规定，而是交由MESI协议的具体实现来决定。我们这里以从主存复制为例进行说明。

二、MESI协议——Cache Line的4种状态

2.1、4种Cache Line状态

MESI协议将Cache Line的状态分为4种，分别是：modify-修改-M、exclusive-独占-E、shared-共享-S和invalid-失效-I。4个状态需要2个标记比特位。
另外，根据《高速缓存》笔记可知，采用“Write Back（写回）”高速缓存写策略的Cache Line原就有2个标记比特位，分别是：valid-是否有效和dirty-是否修改。
综上，Cache Line现有4个标记比特位，特别需要强调的是：“4个状态对应的2个标记比特位”与“另外2个标记比特位”存在耦合依赖关系，并非互相独立，这个关系描述详见表1。

表1

MESI协议规定的4个状态 2个状态标记比特位值 valid标记比特位值 dirty标记比特位值 状态描述
modify-M 00 0-有效 1-存在修改 该Cache Line有效，存在修改，与主存相应数据块不一致，且新于主存相应数据块。只有当前CPU核内的缓存加载了该Cache Line
exclusive-E 01 0-有效 0-不存在修改 该Cache Line有效，不存在修改，与主存相应数据块一致。只有当前CPU核内的缓存加载了该Cache Line
shared-S 10 0-有效 0-不存在修改 该Cache Line有效，不存在修改，与主存相应数据块一致。多于1个的CPU核（包括当前CPU核）内的缓存加载了该Cache Line。实际中，可能由于替换，最终少于2个的CPU核内的缓存加载了该Cache Line
invalid-I 11 1-无效 0-不存在修改 该Cache Line无效

备注：

  • 以上表中4个标记比特位的值只是为了便于示例说明，而不一定是实际值
  • 一个Cache Line或者不加载，或者加载后处于上面4种状态之一的某种状态
  • 处于无效状态的Cache Line需要重新加载，从这个角度来看，其等价于“未加载”
  • 特别需要注意的是，当状态转换时，“valid标记比特位”和“dirty标记比特位”也需要作相应的修改，以保持正确的耦合依赖关系

2.2、合法的Cache Line状态组合

在多CPU核情形中，对于同一个Cache Line，当被大于1个CPU核内的Cache加载时，从全局视角看，合法的Cache Line状态组合有：

  • =1个M，>=1个I，此时如果发生Cache Line替换，则可能的合法状态组合有>=1个I，=1个M，>=0个I，>=0个I
  • =1个E，>=1个I，此时如果发生Cache Line替换，则可能的合法状态组合有>=1个I，=1个E，>=0个I，>=0个I
  • >=2个S，>=0个I，此时如果发生Cache Line替换，则可能的合法状态组合有>=2个S，>=0个I，>=1个S，>=0个I，>=0个I
  • >=2个I，此时如果发生Cache Line替换，则可能的合法状态组合有>=1个I，>=0个I

三、MESI协议——会引起Cache Line状态转换的4种操作

MESI协议将会引起Cache Line状态转换的操作分为4种：

  • Local Read-LR，读取本CPU核内缓存中的Cache Line
  • Local Write-LW，写数据到本CPU核内缓存中的Cache Line
  • Remote Read-RR，读取其他CPU核内缓存中的Cache Line
  • Remote Write-RW，写数据到其他CPU核内缓存中的Cache Line

四、MESI协议——4种状态*会引起状态转换的4种操作=16种状态转换情形

如上文所述，MESI协议中Cache Line的状态有4种，而会引起状态转换的操作也有4种，因此共有16种状态转换情形，接下来就主要介绍这16种状态转换情形，以进一步理解MESI协议。总的16种状态转换示意图如图1。
需要说明的是，为实现MESI协议，每个Cache控制器不仅知晓自己的操作和Cache Line状态，也知晓其他Cache控制器的操作和Cache Line状态。

为便于接下来的叙述方便，首先给出一些约定：

  • 分别以a和b指代不同CPU核内的Cache控制器，a和b加载同一个Cache Line A，可分别以“aA”和“bA”表示，“aA”和“bA”相同不代表它们在Cache中的位置一定一致（比如在组相联映射方案中，通过遍历组找到存放Cache Line的目标位置，而“aA”和“bA”对应的最终遍历到目标位置很有可能不同），而只是代表它们对应的主存数据块相同
  • “xA”表示由某个Cache控制器x加载的Cache Line A

在接下来的叙述中，面向Cache Line A，执行LR和LW操作的Cache控制器是a，执行RR和RW操作的Cache控制器是b。

图1[1]

4.1、M

  • LR：根据所有包含M的合法Cache Line状态组合，无需向内存总线发送RR操作信号，直接读取aA，状态不变
  • LW：根据所有包含M的合法Cache Line状态组合，无需向内存总线发送RW操作信号，直接写数据到aA，状态不变
  • RR：当a监听到内存总线上有RR操作信号时，在b真正执行上述RR操作前，a首先将存在修改的aA写回主存，然后b再真正执行上述RR操作，此时aA和bA都为最新且一致，因此，需要将aA和bA的状态都设为S
  • RW：当a监听到内存总线上有RW操作信号时，在b真正执行上述RW操作前，a首先将存在修改的aA写回主存，然后b再真正执行上述RW操作，此时aA的状态设为I，bA的状态设为M

4.2、E

  • LR：根据所有包含E的合法Cache Line状态组合，无需向内存总线发送RR操作信号，直接读取aA，状态不变
  • LW：根据所有包含E的合法Cache Line状态组合，无需向内存总线发送RW操作信号，直接写数据到aA，状态设为M
  • RR：aA和bA的状态设为S
  • RW：aA的状态设为I，bA的状态设为M

4.3、S

  • LR：根据所有包含S的合法Cache Line状态组合，无需向内存总线发送RR操作信号，直接读取aA，状态不变
  • LW：根据所有包含S的合法Cache Line状态组合，可能存在处于S状态的xA，因此需要向内存总线发送RW操作信号，直接写数据到aA，状态设为M，所有xA的状态设为I
  • RR：aA和bA的状态设为S
  • RW：aA的状态设为I，bA的状态设为M

4.4、I

在继续之前，首先需要说明的是：1）对于一个Cache Line A，如果其未加载，那么就等价处于I状态；2）有效xA表示Cache Line A被加载，且状态不为I。

  • LR：
    • 如果其他CPU核内Cache中不存在有效xA，显而易见的是，a无需向内存总线发送RR操作信号，它从主存重新加载aA，并则aA的状态设为E
    • 如果其他CPU核内Cache中存在有效xA，且状态为S，则a无需向内存总线发送RR操作信号，它从主存重新加载aA，aA的状态设为S
    • 如果其他CPU核内Cache中存在有效xA，且状态为E，则a需要向内存总线发送RR操作信号，它从主存重新加载aA，最终所有有效xA的状态设为S，aA的状态也设为S
    • 如果其他CPU核内Cache中存在有效xA，且状态为M，根据所有包含M的合法Cache Line状态组合可知，只可能存在一个状态为M的xA，假定该xA所在的Cache控制器为p，那么该xA又可被称为pA。此时a需要向内存总线发送RR操作信号，当p监听到内存总线上有RR操作信号时，p先将存在修改的pA写回主存，并将其状态设为S，随后a从主存重新加载aA，并则aA的状态设为S
  • LW：
    • 如果其他CPU核内Cache中不存在有效xA，显而易见的是，a无需向内存总线发送RW操作信号，它从主存重新加载aA，然后直接写数据到aA，并将aA的状态设为M
    • 如果其他CPU核内Cache中存在有效xA，且状态为S或者E，则a需要向内存总线发送RW操作信号，所有有效xA的状态设为I，a从主存重新加载aA，然后直接写数据到aA，并将aA的状态设为M
    • 如果其他CPU核内Cache中存在有效xA，且状态为M，根据所有包含M的合法Cache Line状态组合可知，只可能存在一个状态为M的xA，假定该xA所在的Cache控制器为p，那么该xA又可被称为pA。此时a需要向内存总线发送RW操作信号，当p监听到内存总线上有RW操作信号时，p先将存在修改的pA写回主存，并将其状态设为I，随后a从主存重新加载aA，然后直接写数据到aA，并将aA的状态设为M
  • RR：
    • aA处于无效状态，其他CPU核内Cache控制器的读取操作与aA无关，因此状态不变
  • RW：
    • aA处于无效状态，其他CPU核内Cache控制器的写操作与aA无关，因此状态不变

五、MESI协议实际运作举例

假定现有3个Cache控制器a，b，c，面向Cache Line A。

  1. a读取A，则a加载A，此时aA的状态为E，b和c未加载A
  2. b读取A，则b加载A，此时aA和bA的状态为S，c未加载A
  3. c写数据到A，则c加载A再写数据到cA，此时aA和bA的状态为I，cA的状态为M
  4. a读取A，aA和cA的状态为S，bA的状态仍为I

参考文献：

[1]https://blog.csdn.net/muxiqingyang/article/details/6615199
[2]https://blog.csdn.net/reliveIT/article/details/50450136
[3]https://www.infoq.cn/article/cache-coherency-primer

您的支持将鼓励我继续分享！