Dive into MESI Protocol


 

Dive into MESI Protocol

深入理解MESI缓存一致性协议

0x01. 概述

1. 缓存一致性 (Cache Coherence)

硬件层面的问题,指的是由于多核计算机中有多套缓存,各个缓存之间的数据不一致性问题。一致性如何理解,我觉得 CMU 的一位老师说得不错:All processors see the same view of memory at the same time。缓存一致性协议,如MESI解决是多个缓存副本之间的数据的一致性问题,这些协议可能十分复杂,可能有数十种状态。

2. MESI

MESI协议是一个基于失效的缓存一致性协议,是支持回写(write-back)缓存的最常用协议。因为是在伊利诺伊大学厄巴纳-香槟分校被发明的,所以也被称作伊利诺伊协议 (Illinois protocol)。与写通过(write through)缓存相比,回写缓冲能节约大量带宽。总是有“脏”(dirty)状态表示缓存中的数据与主存中不同。MESI协议要求在缓存不命中(miss)且数据块在另一个缓存时,允许缓存到缓存的数据复制。

0x02. 状态

MESI 存在modifiedexclusivesharedinvalid四种状态,协议可以在一个指定的缓存中应用这四种状态。因此,协议在每一个缓存行中维护一个两位的状态tag, 附着在缓存行的物理地址或者数据后。

  • modified:处于该状态的缓存行中的数据被当前CPU独占,不在其他CPU缓存中,且为最新的与主存不同的数据,因为数据已经更新,所以脏位为1,缓存最终有责任将数据写回到内存,并且也应当为其他缓存提供数据,必须在当前缓存缓存其他数据之前完成这些事情。该缓存行写回主存后,状态变为shared
  • exclusive:非常类似于modified状态,唯一的区别是缓存行的数据还没有被相应的 CPU 修改,这表示缓存行中的数据及内存中的数据都是最新的,所以缓存行的脏位是0。但是,由于 CPU 独占该缓存行,所以能够在任何时刻将数据保存到该行,而不考虑其他 CPU。也就是说,由于内存中的值是最新的,该行可以被直接丢弃而不用回写到内存,也可以为其他缓存提供数据。
  • shared:处于该状态的缓存行可能被复制到至少一个其他 CPU 缓存中,这样在没有得到其他 CPU 的许可时,不能向缓存行存储数据。由于exclusive状态下,内存中的值是最新的,因此可以不用向内存回写值而直接丢弃缓存中的值,或者向其他 CPU 提供值。
  • invalid:处于该状态的行是空的,换句话说,它没有保存任何有效数据。当新数据进入缓存时,它替换一个处于invalid状态的缓存行。这个方法是比较好的,因为替换其他状态的缓存行将引起大量的缓存缺失。

对于任意给定的缓存对,给定缓存行的允许状态如下:

img

如当一个缓存中的某个块被标记为M(modified)时,其他缓存中的块副本只能被标记为I(Invalid)。

0x03. 协议消息

  • Read:该消息包含缓存行需读的物理地址。
  • Read Response:该消息包含较早前的read消息的数据。这个read response消息可能由内存或者其他缓存提供。例如,如果一个缓存请求一个处于modified状态的数据,则缓存必须提供read response消息。
  • Invalidate:包含要使无效的缓存行的物理地址。其他的缓存必须从它们的缓存中移除相应的数据并且响应此消息。
  • Invalidate Acknowledge:一个接收到invalidate消息的 CPU 必须在移除指定数据后响应一个invalidate acknowledge消息。
  • Read Invalidate:该消息包含要缓存行读取的物理地址。同时指示其他缓存移除数据。因此,它包含一个read和一个invalidateread invalidate也需要read response以及invalidate acknowledge消息集。英文亦称read with intend to modify,可理解为读其他缓存的数据,并试图修改当前缓存数据,然后指示其他缓存的数据无效化
  • Writeback:该消息包含要回写到内存的地址和数据。(并且也许会通过窥探器请求检查其他 CPUs 的缓存)。这个消息允许缓存在必要时换出modified状态的数据以腾出空间。

0x04. 状态转换

一个指定缓存行的状态变化及协议消息发送及接收如下图所示,四个状态共12条转移路径:

state_transition

本缓存行起始态为modified:缓存行内容为当前缓存所独有的,而且已被修改。

标号 最终状态 描述
a exclusive 缓存行被写回内存,但是CPU将它保留在缓存中,并进一步保留修改它的权利。此转换需要writeback消息。
c invalid CPU 接收到一条read invalidate消息,表示相应的缓存行数据已经在其他CPU缓存中被修改。CPU必须使其本地副本无效,然后响应read responseinvalidate acknowledge消息,两者都将发送数据给请求方,表示本 CPU 不再具有本地副本。
f shared 其他一些 CPU 读取缓存行,数据由本 CPU 缓存提供,本 CPU 缓存保留只读副本,也可能将其写入内存。此转换由接收read消息开始,本 CPU 使用包含所请求数据的read response消息进行响应。

本缓存行起始态为exclusive:缓存内容不存在于其他缓存中,被当前缓存独占,可在不咨询其他缓存的情况下覆盖它。

标号 最终状态 描述
b modified 本 CPU 将数据写入它已经具有独占访问权的缓存行。此转换不需要发送或接收任何消息。
g shared 其他一些 CPU 读取本缓存行中的数据,并且数据是从本 CPU 的缓存或者内存中提供的。在这两种情况下,本 CPU 都保留只读副本。此转换开始于接收到一个read消息,并且本 CPU 响应了一个read response消息。
i invalid 其他的 CPU 进行了一个原子读写操作,相应的缓存行被本 CPU 独有。本 CPU 将缓存行变成无效状态。此转换开始于接收到read invalidate消息,并且本 CPU 响应一个read response消息以及一个invalidate acknowledge消息。

本缓存行起始态为shared:当前缓存行中的内容在至少一个其他 CPU 缓存中存在副本,即内容被共享。

标号 最终状态 描述
e modified 本 CPU 进行一个原子读写操作,相应的数据在缓存中是只读的。它必须发送一个invalidate消息,并等待其他 CPU 响应invalidate acknowledge消息集以完成此转换。
h exclusive 当前 CPU 将要写入一些数据到缓存行,于是发送一个invalidate消息。直到它接收到所有invalidate acknowledge消息后,CPU 才完成转换。或者其他 CPUs 通过writeback消息将缓存行的数据换出。这样,当前 CPU 就是最后一个缓存该数据的 CPU,自然顺理成章地独占数据。
l invalid 其他 CPU 存储一个数据到缓存行,但是由于该缓存行数据也被保存在其他 CPU 缓存中(比如当前CPU的高速缓存),所以它处于只读状态。此转换开始于接收到一个invalidate消息,当前 CPU 响应一个invalidate acknowledge消息。

本缓存行起始态为invalid:缓存行的内容无效,或者说缓存行数据块为空,valid状态为0。

标号 最终状态 描述
d modified CPU 进行一个原子读写操作,相应的数据没有在它的缓存中。它发送一个read invalidate消息,通过read response接收数据。一旦它接收到一个完整的invalidate acknowledge响应集合,CPU 就完成此转换。
j exclusive 本 CPU 保存一个数据到缓存行,但是数据还没有在它的缓存行中。因此发送一个read invalidate消息。直到它接收到read response消息以及所有invalidate acknowledge消息后,它才完成转换。
k shared 本 CPU 装载一个数据,但是数据还没有在缓存行中。CPU 发送一个read消息,当它接收到相应相应的read response消息后完成转换。

0x05. 例子

最初,数据储存在内存的地址 0中。它在一个 4CPU 的系统中的几个直接映射的单行缓存中移动。下表展示了数据流,第一列是操作顺序,第二行表示执行操作的 CPU,第三行表示执行的操作,接下来是四个 CPU 的缓存行状态(MESI 状态在内存地址后面)。最后两列表示相应的内存内容是否是最新的(V为最新, I不是最新)。

example

  • 最初,CPU 缓存行处于invalid状态,数据在内存中。
  • CPU 0地址 0装载数据,CPU 0中相应的的缓存行进入shared状态,并且内存中的数据是有效的。
  • CPU 3也从地址 0装载数据,这样其中相应的的缓存行也处于shared状态,并且内存中的数据仍然有效。
  • 接下来CPU 0装载其他缓存行 (地址 8),通过使无效操作强制将地址 0的数据换出缓存,原缓存行中的数据被换成地址 8的数据。
  • CPU 2装载地址 0的数据,但是该 CPU 发现它将很快就会存储数据,因此它使用一个read invalidate消息以获得一个独享副本。CPU 3缓存中的数据变成无效(但是内存中的数据仍然是有效的)。
  • 按下来CPU 2开始预期的存储操作,并将状态改变为modified。内存中的数据将不再是最新的。
  • CPU 1开始一个原子自增操作,使用一个read invalidate操作从CPU 2的缓存中窥探数据并使之无效,这样CPU 1的缓存变成 modified状态(内存中的数据仍然是过期的)。
  • 最后,CPU 1地址 8读取数据,使用一个writeback消息将地址 0数据回写到内存。

0x06. 参考

0x07. 相关文章