并发编程-MESI缓存一致性协议

缓存一致性是针对多核心CPU系统而言的,因为每个CPU核心内部都有自己的CPU缓存,就需要考虑不同CPU核心保证缓存中数据一致性的问题,单核心CPU是不存在这个问题的。
CPU有一套完整的协议,来保证缓存一致性。MESI协议则是比较经典的缓存一致性协议,奔腾处理器有使用它,很多其他的处理器都也都使用它的变种。

概念

MESI(Modified Exclusive Shared Or Invalid)是一种广泛使用的支持写回(write back)策略的缓存一致性协议。
write-back和write-through是执行写操作的两种策略:
Write back:先标记不写回,等到使用的时候再写回主存。

Write-back (also called write-behind): initially, writing is done only to the cache. The write to the backing store is postponed until the modified content is about to be replaced by another cache block.
Write through:同步修改缓存和主存。
Write-through: write is done synchronously both to the cache and to the backing store.
MESI是write-back的方式。

缓存行(caceh line)

缓存行可以简单理解为CPU缓存中的最小存储单元,也是MESI操作的基本单位。
CPU中的L1、L2、L3级缓存实际上是由很多缓存行组成。根据CPU的不同,缓存行的大小也不同,典型大小是64byte。

多个数据可以存储在一个缓存行,一个数据可以存储在多个缓存行(此种情况会导致MESI协议失效)

MESI协议中的状态

在MESI协议中,每个Cache line有4个状态,使用额外的2个bit表示,它们分别是:

  • M: 被修改(Modified)
    描述:该缓存行数据有效,数据只被缓存在该CPU的缓存中,并且是被修改过的,即与主存中的数据不一致。
    监听:缓存行必须时刻监听其他CPU对该缓存行对应在主存中的数据的读(read)操作,这个read操作会在该缓存行写回主存并将状态变成S(共享)状态之前被延迟执行。

  • E: 独享的(Exclusive)
    描述:该缓存行数据有效,数据只被缓存在该CPU的缓存中,它是未被修改过的,与主存中数据一致。
    当该CPU修改这个缓存行中内容时,则该缓存行变成Modified状态。
    监听:缓存行也必须时刻监听其他CPU对该缓存行对应在主存中的数据的读(read)操作,一旦有这种操作,该缓存行需要变成S(共享)状态。

  • S: 共享的(Shared)
    描述:该缓存行数据有效,数据被多个CPU缓存,并且各个缓存中的数据与主存数据一致。
    监听:缓存行必须时刻监听其他CPU使该缓存行无效或者独享该缓存行的请求,并将该缓存行变成无效(Invalid)。

  • I: 无效的(Invalid)
    描述:该缓存是无效的(有其它CPU修改了该缓存行缓存的数据)。
    监听:无。

M(Modified)和E(Exclusive)状态的缓存行,其中缓存的数据都是CPU独有的,不同点在于M状态的数据是dirty的(和内存的不一致),E状态的数据是clean的(和内存的一致)。
(Shared)状态的缓存行,其中缓存的数据和其他CPU核心缓存行中数据共享。只有clean的数据才能被多个CPU缓存行共享。
I(Invalid)表示这个缓存行无效。

E状态示例如下:

M状态示例如下:

S状态示例如下:

M状态和I状态并存示例如下:

在MESI协议中,每个缓存行的Cache控制器不仅知道自己的读写操作,同时也监听(snoop)其它CPU中缓存行的读写操作。每个缓存行所处的状态根据本核和其它核的读写操作在4个状态间进行迁移。
MESI协议状态迁移图如下:

在上图中,Local Read表示本内核读本Cache中的值,Local Write表示本内核写本Cache中的值,Remote Read表示其它内核读其它Cache中的值,Remote Write表示其它内核写其它Cache中的值,箭头表示本Cache line状态的迁移,环形箭头表示状态不变。
当内核需要访问的数据不在本Cache中,而其它Cache有这份数据的备份时,本Cache既可以从内存中导入数据,也可以从其它Cache中导入数据,不同的处理器会有不同的选择。MESI协议为了使自己更加通用,没有定义这些细节,只定义了状态之间的迁移,下面的描述假设本Cache从内存中导入数据。
MESI状态之间的迁移过程如下:

延伸理解

  • 一个缓存除在Invalid状态外都可以满足cpu的读请求,一个Invalid的缓存行必须从主存中读取(变成S或者 E状态)来满足该CPU的读请求。
  • 一个写请求只有在该缓存行是M或者E状态时才能被执行,如果缓存行处于S状态,必须先将其它缓存中该缓存行变成Invalid状态(也既是不允许不同CPU同时修改同一缓存行,即使修改该缓存行中不同位置的数据也不允许)。该操作经常作用广播的方式来完成,例如:RequestFor Ownership (RFO)。
  • 对于M和E状态而言总是精确的,他们在和该缓存行的真正状态是一致的。而S状态可能是非一致的,如果一个缓存将处于S状态的缓存行作废了,而另一个缓存实际上可能已经独享了该缓存行,但是该缓存却不会将该缓存行升迁为E状态,这是因为其它缓存不会广播他们作废掉该缓存行的通知,同样由于缓存并没有保存该缓存行的copy的数量,因此(即使有这种通知)也没有办法确定自己是否已经独享了该缓存行。

从上面的意义看来E状态是一种投机性的优化:如果一个CPU想修改一个处于S状态的缓存行,总线事务需要将所有该缓存行的copy变成Invalid状态,而修改E状态的缓存不需要使用总线事务。

------ 本文完 ------