在共享存储的多核处理器中，存在Cache一致性问题，即如何使同一数据块在不同Cache以及主存中的多个备份保持数据一致的问题。具体来说，一个数据块可能在主存和Cache之中保存多份，而不同的处理器核有可能同时读取或者修改这个数据，导致不同的处理器核观察到的数据的值是不同的。Cache一致性协议（Cache Coherence Protocol）是指在共享存储的多处理器或者多核处理器系统中，一种用来保持多个Cache之间以及Cache与主存之间数据一致的机制。人们已经提出了若干Cache一致性协议来解决这个问题。

1.Cache一致性协议的分类

Cache一致性协议的具体作用就是把某个处理器核新写的值传播给其他处理器核以确保所有处理器核看到一致的共享存储内容。从如何传播新值的角度看，Cache一致性协议可分为写无效（Write-Invalidate）（也可称为写使无效）协议与写更新（Write-Update）协议；从新值将会传播给谁的角度看，它可以分为侦听协议与目录协议。Cache一致性协议决定系统为维护一致性所做的具体动作，因而直接影响系统性能。

1）写无效协议与写更新协议。在写无效协议中，当根据一致性要求要把一个处理器核对某一单元所写的值传播给其他处理器核时，就使其他处理器核中该单元的备份无效；其他处理器核随后要用到该单元时，再获得该单元的新值。在写更新协议中，当根据一致性要求要把一个处理器核对某一单元所写的值传播给其他处理器核时，就把该单元的新值传播给所有拥有该单元备份的处理器核，对相应的备份进行更新。

写无效协议的优点是：一旦某处理器核使某一变量在所有其他Cache中的备份无效后，它就取得了对此变量的独占权，随后它可以随意地更新此变量而不必告知其他处理器核，直到其他处理器核请求访问此变量而导致独占权被剥夺。其缺点是：当某变量在一处理器核中的备份变无效后，此处理器核再读此变量时会引起Cache不命中，在一个共享块被多个处理器核频繁访问的情况下会引起所谓的“乒乓”效应，即处理器核之间频繁地互相剥夺对一个共享块的访问权而导致性能严重下降。写更新协议的优点是：一旦某Cache缓存了某一变量，它就一直持有此变量的最新备份，除非此变量被替换掉。其缺点是：写数的处理器核每次都得把所写的值传播给其他处理器核，即使其他处理器核不再使用所写的共享块。写无效协议适用于顺序共享（Sequential Sharing）的程序，即在较长时间内只有一个处理器核访问一个变量；而写更新协议适用于紧密共享（Tight Sharing）的程序，即多个处理器核在一段时间内频繁地访问同一变量。

2）侦听协议与目录协议。侦听协议的基本思想是，当一个处理器核对共享变量的访问不在Cache 命中或可能引起数据不一致时，它就把这一事件广播到所有处理器核。系统中所有处理器核的Cache都侦听广播，当拥有广播中涉及的共享变量的Cache侦听到广播后，就采取相应的维持一致性的行动（如，使本Cache的备份无效、向总线提供数据等）。侦听协议实现较简单，每个处理器核Cache只需要维护状态信息就可以了。侦听协议适合于通过总线互连的多核处理器，因为总线是一种方便而快捷的广播媒介。在写使无效侦听协议中，当一个Cache侦听到其他处理器核欲写某一单元且自己持有此单元的备份时，就使这一备份无效以保持数据一致性；在写更新侦听协议中，当一个Cache侦听到自己持有备份的某一共享单元的内容被其他处理器核所更新时，就根据侦听到的内容更新此备份的值。

由于侦听协议需要广播，因此只适用于共享总线结构。总线是一种独占式资源，且总线延迟随所连接的处理器核数目的增加而增加，存在可伸缩性差的问题。在采用片上网络互连的多核处理器中通常使用基于目录的Cache一致性协议。目录协议的主要思想是，为每一存储行维持一目录项，该目录项记录所有当前持有此行备份的处理器核号以及此行是否已被改写等信息。当一个处理器核欲往某一存储行写数且可能引起数据不一致时，它就根据目录的内容只向持有此行的备份的那些处理器核发出写使无效/写更新信号，从而避免了广播。典型的目录组织方式为位向量目录。位向量目录中的每一目录项有一个n位的向量，其中n是系统中处理器核的个数。位向量中第i位为“1”表示此存储行在第i个处理器核中有备份。每一目录项还有一改写位，当改写位为“1”时表示某处理器核独占并已改写此行。位向量目录的缺点是，所需的目录存储器容量随处理器核数n以及共享存储容量m的增加以O(m*n)的速度增加，有较大存储开销。

2.Cache 状态

Cache一致性协议的实现方式为：在Cache中每一个Cache行设置一致性状态来记录该Cache行的读写状态，确保Cache行不会被多个处理器核同时修改。Cache行的一致性状态的实现有多种具体形式，如最简单的三状态ESI，较为常见的MESI及其变种MOESI等。

ESI 是指Cache 行的三种一致性状态：E（Exclusive，独占），S（Shared，共享），I （Invalid，无效）。Invalid状态表示当前Cache行是无效的，对其进行任何读写操作都会引发缓存缺失（Cache Miss）。Shared状态表明当前Cache行可能被多个处理器核共享，只能读取，不能写入，对其写入也会引发缓存缺失。Exclusive状态表明对应Cache行被当前处理器核独占，该处理器核可以任意读写这个Cache行，而其他处理器核如果想读写这个Cache行需要请求占有这个Cache行的处理器核释放该Cache行。图11.3给出了三个状态之间的转换关系。

图 11.3: 三状态Cache一致性协议状态转换图

MESI 在ESI 的基础上增加了M（Modified，修改）状态。其中Shared状态和Invalid状态和ESI的完全一样，而Exclusive 状态表示当前Cache块虽然被当前处理器核独占，但是还没有被修改，与内存中的数据保持一致，如果处理器核想将其替换出去，并不需要将该Cache行写回内存。Modified状态表示当前Cache行被当前处理器核独占并且已经被修改过了，如果处理器核想替换该Cache行，需要将该Cache行写回内存。与ESI协议相比，增加一个Modified状态的优点是减少了Cache到内存的数据传输次数，Cache只需要将Modified状态的Cache行写回内存。

下面通过一个写无效的位向量目录协议例子简单说明Cache一致性协议的工作原理。通常,一个Cache一致性协议应包括以下三方面的内容：Cache行状态、存储行状态以及为保持Cache一致性的状态转化规则。

该协议采用ESI实现，Cache的每一行都有三种状态：无效状态（INV）、共享状态（SHD）以及独占状态（EXC）。在存储器中，每一行都有一相应的目录项。每一目录项有一n位的向量，其中n是系统中处理器核的个数。位向量中第i位为“1”表示此存储行在第i个处理器核Pi中有备份。此外，每一目录项有一改写位，当改写位为“1”时，表示某处理器核独占并已改写此行，相应的存储行处于DIRTY 状态；否则相应的存储行处于CLEAN 状态。

当处理器核Pi发出一取数操作“LOAD x”时，根据x在Cache 和存储器中的不同状态采取如下不同的操作：若x在Pi的Cache中处于共享或独占状态，则取数操作“LOAD x”在Cache 命中。若x在Pi的Cache 中处于无效状态，那么这个处理器核向存储器发出一个读数请求read(x)。存储器在收到这个read(x)后查找与单元x相对应的目录项，如果目录项的内容显示出x所在的存储行处于CLEAN 状态（改写位为“0”），即x在存储器的内容是有效的，那么存储器向发出请求的处理器核Pi发出读数应答rdack(x)提供x所在行的一个有效备份，并把目录项中位向量的第i位置为“1”；如果目录项的内容显示出x所在的存储行已被某个处理器核Pk改写（改写位为“1”），那么存储器向Pk发出一个写回请求wtbk(x)，Pk在收到wtbk(x)后，把x在Cache的备份从独占状态（EXC）改为共享状态（SHD），并向存储器发出写回应答wback(x)提供x所在行的一个有效备份，存储器收到来自Pk的wback(x)后向发出请求的处理器核Pi发出读数应答rdack(x)提供x所在行的一个有效备份，把目录项中的改写位置为“0”并把位向量的第i位置为“1”。如果x不在Pi的Cache中，那么Pi先从Cache中替换掉一行再向存储器发出一个读数请求read(x)。

当处理器核Pi发出一存数操作“STORE x”时，根据x 在Cache和存储器中的不同状态采取如下不同的操作：若x在Pi的Cache中处于独占状态，则存数操作“STORE x”在Cache 命中。若x在Pi的Cache中处于共享状态，那么这个处理器核向存储器发出一个写数请求write(x)，存储器在收到这个write(x)后查找与单元x 相对应的目录项，如果目录项的内容显示出x所在的存储行处于CLEAN 状态（改写位为“0”），并没有被其他处理器核所共享（位向量中所有位都为“0”），那么存储器向发出请求的处理器核Pi发出写数应答wtack(x)表示允许Pi独占x所在行，把目录项中的改写位置为“1”并把位向量的第i位置为“1”；如果目录项的内容显示出x所在的存储行处于CLEAN 状态（改写位为“0”），并且在其他处理器核中有共享备份（位向量中有些位为“1”），那么存储器根据位向量的内容向所有持有x的共享备份的处理器核发出一个使无效信号invld(x)，持有x的有效备份的处理器核在收到invld(x)后把x在Cache的备份从共享状态（SHD）改为无效状态（INV），并向存储器发出使无效应答invack(x)，存储器收到所有invack(x)后向发出请求的处理器核Pi发出写数应答wtack(x)，把目录项中的改写位置为“1”并把位向量的第i位置为“1”，其他位清“0”。若x在Pi的Cache中处于无效状态，那么这个处理器核向存储器发出一个写数请求write(x)，存储器在收到这个write(x)后查找与单元x相对应的目录项，如果目录项的内容显示出x所在的存储行处于CLEAN 状态（改写位为“0”），并没有被其他处理器核所共享（位向量中所有位都为“0”），那么存储器向发出请求的处理器核Pi发出写数应答wtack(x)提供x所在行的一个有效备份，把目录项中的改写位置为“1”，并把位向量的第i位置为“1”；如果目录项的内容显示出x所在的存储行处于CLEAN 状态（改写位为“0”），并且在其他处理器核中有共享备份（位向量中有些位为“1”），那么存储器根据位向量的内容向所有持有x的共享备份的处理器核发出一个使无效信号invld(x)，持有x的有效备份的处理器核在收到invld(x)后，把x在Cache 的备份从共享状态（SHD）改为无效状态（INV），并向存储器发出使无效应答invack(x)，存储器收到所有invack(x)后向发出请求的处理器核Pi发出写数应答wtack(x)提供x所在行的一个有效备份，把目录项中的改写位置为“1”并把位向量的第i 位置为“1”，其他位清“0”；如果目录项的内容显示出x所在的存储行已被某个处理器核Pk改写（改写位为“1”，位向量第k 位为“1”），那么存储器向Pk发出一个使无效并写回请求invwb(x)，Pk在收到invwb(x)后把x在Cache的备份从独占状态EXC改为无效状态INV，并向存储器发出使无效并写回应答invwback(x)提供x所在行的有效备份，存储器收到来自Pk 的invwback(x)后向发出请求的处理器核Pi发出写数应答wtack(x)提供x所在行的一个有效备份，把目录项中的改写位置为“1”，并把位向量的第i位置为“1”，其他位清“0”。如果x不在Pi的Cache中，那么Pi先从Cache中替换掉一行再向存储器发出一个写数请求write(x)。

如果某处理器核要替换一Cache行且被替换行处在EXC状态，那么这个处理器核需要向存储器发出一个替换请求rep(x)把被替换掉的行写回存储器。

假设单元x 初始时在存储器中处于CLEAN状态(改写位为“0”)，并被处理器核Pj和Pk所共享（在Pj和Pk的Cache中处于SHD状态），如图11.4a所示。接着x被多个处理器核按如下次序访问：处理器核Pi发出存数操作“STORE x”，处理器核Pk发出存数操作“STORE x”，处理器核Pi发出取数操作“LOAD x”，处理器 Pj发出取数操作“LOAD x”。图11.4b~f显示出上述访问序列引起的一系列消息传递，以及x在Cache及在存储器中的状态的转化过程。

图 11.4: 基于目录的写无效Cache一致性协议