cache一致性协议实现的基本方法

Cache一致性协议实现的基本方法主讲：周艳芳副讲：缴万鑫知识回顾（一）解决主存速度与CPU速度差距的办法：Cache--主存存储层次：采用高速缓冲存储器方式知识回顾（二）Cache存储器中保存的字块是主存中相应字块的一个副本。如果程序执行过程中要对该字块的某个单元进行读写操作，就会遇到如何保持Cache与主存的一致性问题。1)不命中时：直接把待写的信息写入主存。2)命中时：有两种写入方式。①写回法：只更新Cache单元，并加以标记，当该块从Cache移出时，再更新相应的主存单元。②写直达法：Cache单元与主存单元同时写。写回法速度快，但有一段时间主存内容与Cache内容不一致；写直达法能随时保持主存数据的正确性，但有可能增加多次不必要的写主存。

问题引出Cache数据与主存数据一致是指：在采用Cache的系统中，同样一个数据可能既存在于Cache中，也存在于主存中，两者数据相同则具有一致性，数据不相同就叫做不一致性。如果不能保证数据的一致性，那么，后续程序的运行就要出现问题。

Cache一致性

目前，在并行系统的产品中大多数都采用基于总线的存储器结构。总线是保证高速缓存一致性的最方便的设备，它允许系统中各个处理机能够监测对存储器进行的所有操作，如果这些操作破坏了本地高速缓存中数据的一致性状态，高速缓存控制器就可以采取相应的动作维护高速缓存的一致性。采用这种机制维护高速缓存一致性的协议的系统中，每个高速缓存都在监听其它高速缓存的操作，所以称为监听总线协议。而对于可扩展多处理机系统，常常采用互连网络实现多处理机互连，其网络带宽随着处理机数目的增加而增大，但是这些网络没有方便的监听机制，也难于进行有效的广播，所以常常采用基于目录的协议。下面分别对这两类协议进行介绍。

解决Cache一致性问题的两种协议

如果接在共享总线上的处理机具有自己的本地高速缓存，那么可以采用两种方法：1.写无效策略和写更新策略：1）写无效（Writeinvalidate）当任何一个处理机写自己的高速缓存时，由它负责把其他的高速缓存复本变成无效的，使其他高速缓存中（和主存中）的复本都是“过时”的。根据对于主存中复本的处理不同，又可以分成写通过和写回策略：——写通过：更新主存中的复本，最后的状态是一个高速缓存中的复本和主存中的复本是有效的，其他复本都是无效的。——写回：它使主存中的复本也无效，最终只有一个高速缓存中的复本使有效的。2）写更新

当任何一个处理机写自己的高速缓存时，改写其它所有的复本。所以操作的结果是所有数据块的复本都是“有效”的。监听总线协议

这两种策略都存在缺点和问题。写无效的问题在于两个方面：使各个高速缓存中数据块的复本无效的开销比较大；由于无效复本引起缺失造成的开销。而写更新的问题在于更新所有复本的开销比较大。2、写一次协议结合了上面介绍的协议的优点，JamesGoodman在1983年提出了一种基于总线的多处理机系统的高速缓存一致性协议。它的主要思想和作法是：高速缓存块的第一次写采用写通过策略，产生一份正确的主存复本，并且使其他高速缓存的复本无效；之后，就采用写回策略：其他高速缓存和主存中的复本均无效。在设计、分析高速缓存一致性协议时要考虑和解决的几个主要问题有

1）高速缓存可能出现的状态集合

2）共享主存的状态

3）为维护一致性而引起的状态转换下面分别结合写一次协议进行说明1）每个高速缓存复本可能出现的四种状态（1）有效（Valid）与主存复本一致的高速缓存复本，即该复本未经修改，所以这个复本不是唯一的正确复本。别的高速缓存中也可能存在该数据块的有效复本。（2）保留（Reserved）这一高速缓存的复本是第一次被修改，并采用写通过方法写入主存。所以这个高速缓存中的复本与主存中的复本是一致的。而且系统中也只有这两个复本是有效的。（3）重写（Dirty）高速缓存中的复本不止一次被修改过，由于不再采用写通过的方法，所以这个高速缓存中的复本是唯一的有效复本，与主存和其他高速缓存中的复本都不一致。主存中的复本也是无效的。（4）无效（Invalid）与主存中和其他高速缓存中的复本不一致或在高速缓存中根本没有该复本。2）进行高速缓存操作时用到的信号（1）P-Write：本地处理机写自己的高速缓存复本（2）P-Read：本地处理机读自己的高速缓存复本这两条命令都是局部/本地命令（3）Write-inv：远程高速缓存在写命中时在总线上广播一个无效命令（4）Read-inv：远程高速缓存在写缺失时在总线上广播一个无效命令（5）Read-blk：从另外一个高速缓存中读出一份有效复本。这两条属于一致性命令3）写操作可能遇到的几种情况（1）如果C1为VALID，写C1时，则写命中（Write

hit）

a.如果内存单元所在的块在高速缓存中，则可以写高速缓存命中。

b.如果内存单元所在的块不在高速缓存中，则写缺失，将内存单元所在块读入高速缓存，再进行写操作发P-Write修改C1内容，修改内存，发Write-Inv给所有高速缓存，使它们的状态变为无效。同时使本地的高速缓存中数据块的状态变Reserved。（2）如果C1为Reserved，对C1进行写操作时，则写命中。发P-Write命令修改C1内容，不修改内存中的复本，C1状态变为Dirty（3）如果C1为Dirty，写C1时则写命中。发出P-Write命令修改C1的内容，不修改主存中的复本，C1保持Dirty状态（4）如果C1为Invalid，则写不命中。如果其他高速缓存中也没有该数据块的复本，只有主存中有该数据块的复本，则将主存中的复本复制到C1中，再将要写入的内容13写入C1，这是C1和主存内容不一致。把C1状态置为Dirty。写入后，C1与主存中的内容至少有一个单元不一致。（5）如果C1为Invalid，C2为Dirty，这时主存中的内容与C2中的不一致。将C2中的数据块复制到C1中，将C1的状态置为Dirty，发Read-inv使其他高速缓存的有关复本变成无效（6）如果C1为Invalid，C2为Reserved，这时主存中的内容和C2的一致，将C1的状态置为Dirty，发Read-inv，使其他高速缓存中的有关复本变成无效状态。4）读操作可能遇到的情况（1）