什么是cache的一致性(什么是cache的一致性问题)

什么是多处理机的cache一致性

纵观PC系统和CPU二十年的发展，随着半导体加工工艺水平的不断提高，CPU和存储器的性能都有了很大的提高。 CPU频率的提高，必然要求系统中存储器的存取速度要提高，还要求其容量要增大。

MESI(Modified Exclusive Shared Or Invalid)(也称为伊利诺斯协议,是因为该协议由伊利诺斯州立大学提出)是一种广泛使用的支持写回策略的缓存一致性协议

为什么要考虑cache的一致性问题

当系统中有几个cpu core，而且每个cpu core都有自己的cache的话，就需要考虑cache一致性了。例如我们定义一个变量，这个变量位于内存中，如果cpu1修改了这个变量，这个变量就被cpu1 cache了，当cpu2需要访问这个变量的话，如果没有cache一致性，cpu2就需要等cpu1把cache中的这个变量写到内存中，才能访问到正确的结果。如果有cache一致性的话，cpu2的访问就可以直接对cpu1的cache进行访问，从而提高了效率。

什么是DMA与Cache一致性？

Cache和DMA本身似乎是两个毫不相关的事物。Cache被用作CPU针对内存的缓存，利用程序的空间局部性和时间局部性原理，达到较高的命中率，从而避免CPU每次都必须要与相对慢速的内存交互数据来提高数据的访问速率。DMA可以作为内存与外设之间传输数据的方式，在这种传输方式之下，数据并不需要经过CPU中转。假设DMA针对内存的目的地址与Cache缓存的对象没有重叠区域，DMA和Cache之间将相安无事。

但是，如果DMA的目的地址与Cache所缓存的内存地址访问有重叠，经过DMA操作，与Cache缓存对应的内存中的数据已经被修改，而CPU本身并不知道，它仍然认为Cache中的数据就是内存中的数据，那在以后访问Cache映射的内存时，它仍然使用陈旧的Cache数据。这样就会发生Cache与内存之间数据“不一致性”的错误。所谓Cache数据与内存数据的不一致性，是指在采用Cache的系统中，同样一个数据可能既存在于Cache中，也存在于主存中，Cache与主存中的数据一样则具有一致性，数据若不一样则具有不一致性。需要特别注意的是，Cache与内存的一致性问题经常被初学者遗忘。在发生Cache与内存不一致性错误后，驱动将无法正常运行。如果没有相关的背景知识，工程师几乎无法定位错误的原因，因为这时所有的程序看起来都是完全正确的。Cache的不一致性问题并不是只发生在DMA的情况下，实际上，它还存在于Cache使能和关闭的时刻。例如，对于带MMU功能的ARM处理器，在开启MMU之前，需要先置Cache无效，对于TLB，也是如此。

MESI协议（多核CPU的cache内存一致性协议）

MESI是Midified（已修改），Exclusive（独占），Shared（共享），Invalidated（已失效）的缩写，对应Cache Line的四种状态。

多核CPU的cache和内存的构成可以简化为：每个CPU有自己的独有的cache，然后大家共享内存，当每个CPU从cache中读取数据时，如何保证所有cache和内存中数据的一致性，即使MESI协议要解决的问题。

【已修改】 即脏标记，表示当前cache line中的数据已经被更新过，没有被写到内存中。【已失效】状态，表示这个cache line里的数据已经失效，是不可以读取的数据。

【独占】和【共享】状态都表示这个cache line中的数据是干净的（即与内存中的数据是一致的，共享同时也表示与其他cpu cache中的数据是一致的）。

【独占】是指当前这份数据只保存在当前cpu cache中，其他cpu cache中没有该数据（或者原本有的这份数据变成了已失效的）。所以这个时候更改独占的数据就可以直接自由写入，不需要通知其他的cpu cache（独占的数据更改写一次后，就会变成已修改的）。

而【独占】状态的数据，如果有其他cpu从内存读取相同的数据到各自的cache，那么这个数据就会变成【共享】状态。

进一步的，【共享】状态代表着相同一份数据在多个 CPU 的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为【无失效】状态，然后再更新当前 Cache 里面的数据（这时数据的状态就变为独占的，这时也会同时更新内存中的数据，下一次更改独占的数据，就可以直接更改，不急于更新内存的数据）。

MESI 协议的四种状态之间的流转过程，可以汇总成下面的表格：

其中，本地读写是指当前cpu对于cache line的读写，远程读写是指其他cpu读写相同的数据（对于当前cpu cache line的影响）。

VivioJS MESI help (tcd.ie)

一个可以模拟MESI协议运行过程的网站，可以更好的理解协议的工作过程。

模拟的场景如下图：

cache 的一致维护性是什么意思

1.基于监听协议：

通常使用两种策略来解决Cache一致性问题：写无效策略和写更新策略。

写无效策略（write invalidate）是指当某个处理器更新其私有Cache中的某个数据时，它通知所有其它Cache这一数据在它们中的副本从此均无效。这样就可以避免其它"过时"的副本被使用而造成错误。

写更新策略（write update）是指当某个处理器更新其私有Cache中的某个数据时，它把所更新的数据发送给所有的其它Cache，以更新这一数据在其它Cache中的所有副本。一般来说，使用写更新策略，需要传输更新后的数据，而写无效只需传输写无效信息，因此写更新传输的数据量比写无效要大。而且，被更新的数据的某些副本以后也不一定再被使用。例如上图中，P1更新X后，P2不一定再使用变量X的值。因此每次都对所有的副本都更新是没有必要的。

请注意，写无效和写更新是维护Cache一致性的策略，它与维护Cache与主存储器一致性的策略没有必然的关系。无论是使用写无效策略还是写更新策略，共享存储器中的数据副本都可以通过写直达或写回策略来维护与Cache的一致性。

写回法：当CPU写Cache命中时，只修改Cache的内容，而不立即写入主存；只有当此行被换出时才写回主存。

写直达：又称全写法，当写Cache命中时，Cache与主存同时发生写修改，因而较好的维护了与主存的内容一致性。

写一次法：是写回法与全写法的折中方法：写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。这是因为第一次写Cache时，CPU要在总线上启动一个存储写周期，其他Cache监听到此主存块地址及写信号后，即可拷贝该块或及时作废，以便维护系统全部Cache的一致性。

例如，如果采用写无效策略和写直达策略，当处理器P修改私有Cache中的某一数据时，不但要向其它处理器的Cache发送无效信息，而且要将共享存储器中该数据的副本更新。最终，处理器P的私有Cache和共享存储器中的数据是相同而且是正确的，而其它处理器Cache中该数据的副本被标记为无效。如果采用写无效策略和写回策略，当处理器P修改私有Cache中的某一数据时，不但要向其它处理器的Cache发送无效信息，而且要向共享存储器发送无效信息。最终，只有处理器P的私有Cache中的数据是正确的，而共享存储器和其它处理器Cache中该数据的副本均被标记为无效。

2.基于目录协议

使用Cache目录来存放有关数据块拷贝驻留在Cache中的信息，把使其他Cache数据块无效的一致性命令只发给存放有相应数据块的Cache，从而支持Cache的一致性。 根据目录的结构特点，基于目录的协议可分为3类：全映射（full-map）目录、有限（limited）目录、和链式（chained）目录。

cache一致性小记

1.1 cacheline对齐

  定义数据结构或者数据缓冲区时申明cache line对齐

1.2 cache一致性问题

  cache一致性问题的根源是因为存在多个处理器独占的cache。

1.3 一致性协议

  解决一致性问题的机制有2种：基于目录的协议（Directory-based protocl）和总线窥探协议（Bus

snooping protocl）,其实还有另外一个snarfing协议，在此不作讨论。

这2类协议的主要区别在于基于目录的协议采用全局统一管理不同cache的状态，而总线窥探协议则使用类似于分布式的系统，每个处理负责管理自己的cache状态，通过共享的总线，同步不同cache备份的状态。

  这2类协议中，每个cache block都必须有一个状态字段，cache控制器通常使用一个状态机来维护这个状态域。

基于目录的协议的延迟性较大，但是在拥有很多个处理的系统中，有更好的扩展性。总线窥探协议使用于具有广播能力的总线结构，允许每个处理能监听其它处理器对内存的访问，适合小规模的多核系统。经典的总线窥探协议Write-Once衍生出了MESI协议。

1.4 MESI协议

  MESI是cache

line四种状态的首字母的缩写，分别是修改（Modified）态、独占(Exclusive)态、共享(Shared)态和失效（Invalid）态。

1）修改态

如果该cache line在多个cache中都有备份，那么只有一个备份能处于这种状态，并且“dirty”标志位被置上。拥有修改态的cache

line的cache需要在某个合适的时候将该cache line写回到内存中。但在写回前，任何处理器对该cache

line在内存中相对应的内存块都不能进行读操作。cache

line被写回到内存后，修改态就变为共享态。

2）独占态

可以理解为只有一个处理器首次从一块内存中读取数据，相关的cache

line只在一个cache中有备份或者在其它cache中的状态为失效，这个时候dirty标志是没有置上的，它和内存中的内容保持一致。

3）共享态

该cache

line在多个cache中都有备份，并且是相同的状态，它是和内存内容保持一致的一份拷贝，可以在任何时候变成其他三种状态。

4）失效态

该cache line要么不在cache中，要么它的内容已经过时。一旦某个cache

line被标记为失效，那么它就被认为从没有被加载到cache中。

对于某个内存块，当其在2个或多个cache中都保留了一个备份时，只有部分状态是允许的。下表中，横轴和纵轴分别表示了2个cache中某个cache

line的状态。如果一个cache line被设置成了M或E态，那么另外一个只能设置成I态。

    表1 MESI中2个cache备份的状态矩阵

        M  E  S  I

    M  × × × √

    E  × × × √

    S  × × √ √

    I  √ √ √ √

    表2 MESI状态迁移表