ch6-第六章CacheCoherence

1、第六章 Cache Coherence6.1 Cache Coherence问题6.1.1 Cache Coherence的提出6.1.2 多个Cache不一致的原因6.1.3 两种设计Cache一致性协议策略6.2 监听总线协议 6.2.1 写一次协议6.3 基于目录的Cache一致性协议 6.3.1 目录的一般性问题6.3.2 全映射目录6.3.3 有限目录6.3.4 链式目录6.4 三种Cache一致性策略 6.4.1 采用Write-Through策略的Cache 6.4.2 采用Write-Bach策略的Cache 6.4.3 采用Write-Once策略的Cache6.1 Cach

2、e Coherence问题6.1.1 Cache Coherence问题的提出 在多处理器系统中，多个Cache中，对应的copy内容应该一致，如下图：MemoryCachePCachePCacheP这几个copy应该一致6.1.2 多个Cache不一致的原因 1.共享可写数据的不一致性（sharing of writable data）P1P2更新前xxx处理机CachesharedmemoryP1P2写通过xxxP1P2写回xxx2.进程迁移的不一致性P1P2迁移前xx处理机CacheP1P2写通过xxxP1P2写回xxx上图中： 右图为：包含共享变量x的进程原来在P1上运行，并对x进行了

3、修改（但采取写回策略，所以暂时没有修改Memory），由于某种原因迁移到P2，修改过的x仍在P1的Cache中，P2运行时从Memory中得到x，这个x其实是“过时”的，所以造成了不一致。 中间图为：P2中运行的进程对x进行了修改，采取写通过策略，所以把Memory中的x也修改为x，由于某种原因该进程迁移到P1，但P1的Cache中仍为x，所以造成不一致。3. I/O操作（绕过Cache的I/O操作）P1P2xx存储器P1P2写通过xxP1P2写回xxxxxxxI/O存储器输入存储器输出c1c2总线上图中： 中间图为：当I/O处理机将一个新的数据x写入主存储器时，绕过采用写通过策略的cache

4、，则C1和共享存储器之间产生了不一致。 右图为：直接从主存储器输出数据时（绕过Cache），采用写回策略的高速缓存产生不一致性。6.1.3 两种设计Cache一致性协议策略 1.写无效（write invalidate） 任一处理器写它的私有Cache时，它都使所有其它的Cache中的副本失效。 对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。 对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。2.写更新（write update） 任一处理器写它的私有Cache时，它都立

5、即更新所有其它的Cache中的副本。 对Write-through，它也更新主存储器中的副本。 对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。3. 示意图 下图表示数据块x在共享存储器和三台处理机的Cache中的副本一致的情形。x共享存储器CacheP1xP2xxP3总线处理机 下图表示P1进行写无效操作后的情形。写通过：xI表示无效P1IP2xIP3写回：xI表示无效P1IP2IIP3 下图表示P1进行写更新操作后的情形（写通过）。xI表示无效P1xP2xxP34.写无效的问题主要开销在两个方面： （1）作废各Cache副本的开销； （2）由作废引起缺失造成的

6、开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。 后果： 如果一个处理机经常对某个块连续写，且各处理处理机间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即处理机之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。5. 写更新的问题 由于更新时，所有的副本均需要更新，开销很大。6.2 监听总线协议(Snoopy protocol) 通过总线监听机制实现Cache和共享存储器之间的一致性。适用性分析： 适用于具有广播能力的总线结构多机系统，允许

7、每台处理机监听其它处理机的存储器访问情况。 只适用于小规模的多处理机系统。6.2.1 写一次(write-once)协议 写无效监听一致性协议，将写通过和写回策略结合。 为了减少总线流量，高速缓存块的第一次写用写通过方法，产生一份正确的主存储器副本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器。1. 一致性协议的内容 （1）Cache可能出现的状态集合 （2）共享主存的状态 （3）为维护一致性而引起的状态转换。2. 每份Cache中的副本可能出现的四种状态 （1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cac

8、he副本不是唯一的副本。 （2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。 （3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。 （4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到。3. 局部命令（Local commands） （1）P-Read：本地处理机读自己的Cache副本。 （2）P-Write：本

9、地处理机写自己的Cache副本。4. 一致性命令 （1）Read-blk：从另一Cache读一份有效的副本。 （2）Write-inv：在写命中时在总线上广播一个无效命令。 （3）Read-inv：在写缺失时在总线上广播一个无效命令。 Dirty: modified more than once, the only copy in the system; Invalid: inconsistent copy; Reserved: after written once, the only copy consistent with memory; Valid: A copy consistent

10、with the memory copy.5. Write-Once一致性协议状态转移图其中，四种状态的含义如下：InvalidValidDirtyReservedRead-inv(4)P-Write(1)P-Write(hit:local still dirty)P-Write(hit:local, not memoryupdate, local copy becomes dirty)P-Write(hit:local,updatememory copy,broadcastwrite-inv to all cache,local copybecomesreserved)Read-blk(3)

11、Read-inv(4)P-Read(2)Read-blk(3)Read-inv(4)/Write-inv(5)P-Read(hit:alwayslocal,no statetransition)下一节(用鼠标点击连线来察看详细信息）P-Write(1)(1)P-Write(miss: take a dirty copy from a remote cache, or from memory; send Read-inv to invalidate all copies; update local copy into a dirty one).InvalidValidDirtyReserved下

12、一节InvalidValidDirtyReserved(2)P-Read(miss: if no dirty copy exists, memory supplies a validcopy, otherwise, the cache inhibits memory and supplies a copyand updates memory. Both copies become valid).P-Read(2)下一节InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become va

13、lid).Read-blk(3)下一节InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)下一节InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)下一节InvalidValidDirtyReserved(4)

14、Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)下一节InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).(5)Write-inv(A remote cache updates its local copy d

15、uring a write-hits and invalidates all other copies).Read-inv(4)/Write-inv(5)下一节 (1)P-Write(miss: take a dirty copy from a remote cache which then updates memory, or from memory; send Read-inv to invalidate all copies; update local copy into a dirty one). (2)P-Read(miss: if no dirty copy exists, mem

16、ory supplies a valid copy, otherwise, the cache inhibits memory and supplies a copy and updates memory. Both copies become valid). (3)Read-blk(read from remote processors, the local copy become valid). (4)Read-inv(A remote cache reads a block during a write-miss, updates it and invalidates all other

17、 copies). (5)Write-inv(A remote cache updates its local copy during a write-hits and invalidates all other copies).6. Write-Once一致性协议状态转移表必是局部进行，不影响有效状态第一次写命中，用写通过法。同时修改本地和主存副本并广播Write-inv使所有副本失效commandcurrentstatenextstatestatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次写命中，用写回法。但不修改主存的副本P-Writ

18、e保留重写Write-hit写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write无效保留 Write-missaction（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hitcommandcurrentstatenextstatestatusaction（续表）读缺失时,如远程Cache中没有重写副本，则主存中一定有一份正确的副本，供给发请求的Cache。如远程的Cache有重写的副本，则它禁止主存操作，并将副本发给请求的Cache，两种

19、情况均使发请求的Cache得到的副本为有效。P-Read无效有效 Read-miss远程Cache读此副本，读后两份副本均有效Read-blk保留或重写有效commandcurrentstatenextstatestatusaction（续表）写缺失时，远程Cache读一个块，并修改它，并使所有其它Cache的副本无效。Read-inv除无效外的其它状态无效写命中时，一远程Cache修改其本地副本，并使数据块的其它副本无效Write-inv有效无效commandcurrentstatenextstatestatusaction（续表）如果副本处于重写状态，必须通过块替换写回主存，否则不产生替换

20、操作Write-inv有效无效替代7. 一个具体的例子如下图的系统：MemoryC1P1C2P2C3P3读的情况： （1）如果C1为Valid，读C1，则Read hit，状态不变。 （2）如果C1为Reserved，读C1，则Read hit，状态不变。 （3）如果C1为Dirty，读C1，则Read hit，状态不变。 （4）如果C1为Invalid，C2和C3没有东西，则读C1时Read miss，这时只有memory中有正确的副本，把它取到C1，C1改为Valid（P-Read负责实现状态的改变）。 （5）如果C1为Invalid，C2为Dirty，则读C1时Read miss，这时只

21、有C2中的内容是正确的，要发Read-blk信号把副本从C2读到C1，同时修改memory，把C1，C2都改为Valid（程序状态转移图中P-Read(2)使C1Valid，Read-blk(3)使C2 Valid）。 （6）如果C1为Invalid，C2为Reserved，则读C1时Read miss，这时发Read-blk信号把 C2C1，C1，C2都改为Valid，其中Read-blk(3)负责把C2由ReservedValid，P-Read(2)负责把C1由InvalidValid。写的情况： （1）如果C1为Valid，写C1，则Write hit，发P-write修改C1内容，修改

22、memory，发Write-inv(4)给所有Cache，C1变成Reserved状态。 （2）如果C1为Reserved，写C1，则Write hit，发P-write修改C1内容，不修改memory，C1状态变为Dirty。 （3）如果C1为Dirty，写C1，则Write hit，发P-write修改C1内容，不修改memory，状态仍为Dirty。 （4）如果C1为Invalid，C2，C3没有东西，这时memory中有这个地址的数据副本，从memory中读取该副本到C1，再把要写的内容写入C1，这时C1和memory内容不一致，把C1的状态变为Dirty。 （5）如果C1为Inval

23、id，C2为Dirty，这时memory中内容和C2中的内容不一致，把 C2C1，再把要写的内容写入C1，C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。 （6）如果C1为Invalid，C2为Reserved，这时memory中的内容和C2内容一致，把C2C1，再把要写的内容写入C1，这时C1与memory内容不一致，使C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。C1的三种状态的图示:xxP1xP2xP3C1C2C3memoryvalidC1中的副本和memory中一致xxP1IP2IP3C1C2C3memoryReservedInva

24、lidC1中的副本和memory中一致，都正确xxP1IP2IP3C1C2C3memoryDirtyInvalidC1中的副本和memory不一致，只有C1中的副本正确8.其它的一些问题 CPU要向Cache写数据，如果write miss，表示该数据块不在Cache中或者该数据快处于无效状态，那么需要把正确的数据从memory或其它的Cache中取过来，然后再写操作。 为什么不能直接写？ （1）可能该数据块根本不在Cache中，所以需要从其它地方调入。 （2）已在Cache中，但数据不正确，这时如果直接写入数据，整个数据块可能还是不正确的。例如，数据不正确的原因是100号单元数据已修改，如果

25、要写入一个数据到101单元，这时不能直接写，否则100号单元还是错的。 Cache Coherence问题概要：多处理机系统共享存储器Cache块的状态访问的数据是最新的，不是“过时”的内容6.3 基于目录的Cache一致性协议6.3.1 目录的一般性问题 1.Cache一致性协议的开销分析 （1）采用写无效协议无效后，当其它处理机再读该副本时，出现Read miss，要有开销 （2）采用写更新协议需要更新所有Cache和memory中的副本，所以开销大，有些处理机对更新后的数据可能不会使用。 2. 基于目录的一致性协议的基本思想 当处理机台数增加时，一般不用总线结构，而采用多级互连网络。多级

26、互连网络实现广播功能代价很大。 为什么需要广播功能？把一致性命令，如Write-inv，Read-inv等命令要发送给所有的Cache。 能不能只发送给存放该副本的Cache?基于目录的协议的基本思想 3. 目录的结构 （1）目录里放什么有关Cache副本驻留在哪里的信息：所有共享数据块的所有Cache副本的地址表。 （2）每个目录项（每个数据结构）包含若干个指向这个块（每个数据块有个目录项）的Cache副本地址的指针以及一个重写位（用来说明是否有一个Cache允许把有关的数据写入）。 （3）基于目录的Cache一致性协议是依靠一个目录来记录系统之中哪些处理机的Cache中有指定存储块的副本。

27、当一台处理机希望写某个共享块时，通过目录向有该块的副本的那些处理机“点对点”的发无效信号，使所有其它的副本无效。 4. 目录的方式（1）集中目录方式（中心目录）1976年Tang提出。用一个中心目录存放所有Cache目录的副本，它能提供为保证一致性所需要的所有信息。 缺点：容量非常大，必须采用联想方法来检查，冲突多，检索时间长。（2）分布式目录1978年Censier和Feautrier提出。每个存储模块维护各自的目录，目录中记录着每个存储块的当前信息。当前信息指明哪些Cache有该存储块的副本。如下面的图：D1M1D2M2DmMmD1M1D2M2DmMm互连网络 如果C2读miss，这时C1

28、中有Dirty的副本，则把它写回memory，内存再给C2一个副本，变成Valid。 如果C1写命中，它告诉memory控制器，控制器发无效命令给在D1的当前向量中有记录的所有Cache。 5. 三种目录 全映射（full map）目录：存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是处理机数目）。 有限（limited）目录：每个目录项有固定数目的指针（小于N）。 链式（chained）目录：将目录分布到各个Cache（其余同全映射目录）。6.3.2 全映射目录 1.目录项结构 目录项中有N个处理机位（对应N台处理机）和一

29、个重写位，如下图所示：目录项：重写位（1位）处理机位（N位） 处理机位表示相应处理机的Cache block的状态（存在或不存在）。 有一个也只有一个处理机位为“1”，那么该处理机可以对该块进行写操作。 Cache的每个块有两个状态位：有效位有效块是否允许写有效1位 Cache的状态位应该和目录项的状态一致。1位允许写目录项：重写位（1位）处理机位（N位）Cache状态位：2.目录的三种情况我们来看三台处理机（三个Cache）的例子。（1）C1，C2，C3都没有单元X的副本Shared Memoryx:c000dataC1P1C2P2C3P3（2）C1，C2，C3同时请求X单元的副本，这时目录

30、项中的三个指针（处理机位）被置1，表示这些Cache中已有数据副本。 目录项的重写位被置为未写（c）状态，表示无一处理机允许写入该数据块。Shared Memoryx:c111datax:P1x:P2x:P3C1C2C3（3）C3请求对该块的写允许权时出现第（3）种情形，重写被置成D状态，且有一个指针指向C3的数据块。Shared Memoryx:D001dataP1P2 x:P3C1C2C3data3.第二种情况第三种情况的过程 P3向C3发出写请求时：（1）C3检测出包含单元X的块是有效的，但Cache中的块允许位状态表示不允许处理机对该块进行写操作。（2）C3向包含单元X的存储器模块发出

31、写请求，并暂停P3工作。（3）该存储器模块发出一个无效请求给C1和C2（根据目录项的内容发几个无效信号）（4）C1和C2收到无效请求后，把相应位置0，表示含单元X的块已无效，并发送一个回答信号给请求的存储器模块。（5）存储器模块收到回答信号后，将重写位置 D，清除指向C1、C2的指针，发出允许信号给C3。（6）C3收到写允许信号后，修改Cache的状态并激活处理机P3。4. 目录所占空间 假设存储器大小和处理机台数N成正比，即台数增加时，存储器的模块数也增加，所以数据块的个数也和N成正比。 另外目录项的大小也和处理机台数N成正比，所以目录的总所占空间和N2成正比。 即：目录项数*项大小 = O

32、 ( N2) 太大不便于扩展。6.3.3 有限目录 解决目录过大的问题。任意一个数据块在Cache中同时存在的副本数量有一定限制，那么目录大小的增加不会超过一个常数。符号表示法： DiriX i:指针的数量。X是NB，表示没有广播功能的方案。 DirNNB表示没有广播功能的全映射方式 DiriNB（i N）：使用i个指针的没有广播功能的有限目录协议方式。 除了多于i个Cache请求读一个特定的数据块的情况外，有限目录协议与全映射协议类似。 有限目录中指针不是每台处理机一位，而是针对处理机的二进制标识符进行编码，所以指针占log2N位存储器。 在全映射方式中，每个处理机对应一个指针，所以N台处理

33、机一共用了N位，而有限目录中只用log2N位，设N =16，则log216 = 4。 如果允许两个指针，则需要8位。 所以目录的存储容量为O（Nlog2N），比全映射容易扩充。 如果多处理机系统中的处理机具有局部性，即在任何给定的时间间隔内，只有一小部分处理机访问某个给定的存储器字，那么有限目录足以应付这个小的工作处理机组了。6.3.4 链式目录 用目录指针链来跟踪共享数据副本。 两种方法，单链法与双链法。 数据块共享副本的数目并无限制。 所占的空间及可扩展性同有限目录。 它的工作原理如下过程所示。（1）P1要读单元X，则memory发送一份副本给C1，同时送给C1一个链结束指针（CT：Cha

34、in Termination），存储器也保存指向C1的指针。Shared Memoryx:cdataP1P2P3C1C2C3x:CTdata（2）当P2要读单元X时，存储器送一份副本给C2，同时送给C2一个指向C1的指针，存储器保存指向C2的指针。Shared Memoryx:cdataP1P2P3C1C2C3x:CTdatax:data（3）重复以上步骤，所有Cache都得到单元X的副本。（4）如果P3要对单元X进行写操作，它必须沿着链发送一个数据无效信息。为了保证顺序一致性，在有链结束指针的处理机回答无效信号之前，存储器模块不给P3写允许权。 无效命令从一个Cache到一个Cache顺序进

35、行，不象snoopy协议那样同时发送给所有Cache。（5）替换。假设C1到CN都有单元X的副本，还假设单元X和单元Y都映射到同一个高速缓存块（直接映射法）。如果处理机Pi要读单元Y，它首先必须把X所在的块从Cache中去掉，这可以采用两种方法： 1）沿着链发一个消息使Ci+1的指针指向Ci-1，这样使Ci从链中去掉（这时Ci中存放Y了）。 2）使Ci+1到CN中的单元X无效（这时Ci中存放Y了）。目录占用的存储容量：指针的尺寸以处理机数目的对数关系增长（这和有限目录相同）log2N，每个Cache块的指针数目与处理机个数无关。解决Cache一致性的其它办法：（1）不允许有私有 Cache：S

36、hared Cache方案（2）可写的共享数据不存放在Cache中6.4 三种Cache一致性策略6.4.1 采用Write-Through策略的Cache 数据块的两种状态：有效和无效（指本地处理机相应数据块的状态，并非整个Cache的状态。) 一致性的四种操作： Rr和Wr：其它处理机对该数据块（指在其它处理机Cache中的数据块）的读写 Rl和Wl：是本地处理机对该数据块的读写状态转移图如下：有效无效RrWlRlRl, WlWrRr, WrCache的数据块为无效时： 其它处理机的任何操作都不会影响本地Cache的这种无效状态； 只有在本地处理机读或者写了数据块中的某个数据，即对Cach

37、e执行了Read或Write命令时，该数据块的状态才会成为“有效”。 Cache的数据块为“有效”时： 本地处理机的读、写操作，不会影响该状态； 其它处理机对存有相同内容的数据块读，不会影响该状态； 其它处理机对存有相同内容的数据块执行了写操作，该数据块状态变成无效。6.4.2 采用Write-Back策略的Cache 1.数据块的三种状态 RO (只读）状态：表示整个系统中不止一个副本正确（例如一个在Cache中，一个在memory中）。 读-写状态：表示整个系统中，只有这个副本是正确的，其它都“过时”（即无效），这说明这个 Cache的数据块至少被写过一次，但memory中的内容还没有被修

38、改。 无效状态：“过时”数据。2. 一致性的四种操作： Rr和Wr：其它处理机对该数据块（指在其它处理机Cache中的数据块）的读写 Rl和Wl：是本地处理机对该数据块的读写状态转移图如下：3. 处于RO状态 本地读，远程读不会改变状态 本地写，使ROR-W（这时只有一个数据块正确） 远程写，使RO无效无效ROWlWrRl, RrW-R4. 处于读-写状态无效RORrWrRl,WlW-R 本地读、写不会改变状态 远程读：这时只有这个 Cache的数据块是正确的，所以要有“写回”动作（即把内容写回Memory），另外还需要把正确的数据传递给远程读的处理机相应的Cache。两个Cache的状态RO

39、 远程写：把本地处理机的数据块传递给远程处理机，远程处理机对数据块进行写操作，远程处理机对应的Cache状态变为RO，而本地的Cache变为无效状态。5. 处于无效状态无效ROWlRr,WrW-RRl 本地读：无效RO 本地写：无效WR（同时使其它拥有相同内容的数据块的Cache中相应的数据块的状态变成无效） 远程写、远程读：不影响状态的改变*6.4.3 采用Write-Once策略的Cache 1. Write-Through和Write-Back的缺点 Write-Through策略的弱点是每次都要修改memory，所以总线流量增大； Write-Back策略的弱点是Cache写了一次后，

40、Memory中的内容不一致。2. Write-Once的基本思想 把Write-Through和Write-Back两者的优点结合在一起：减少总线流量。 Cache的第一次写采用Write-Through策略（有一个以上的副本正确）； Cache而后的写采用Write-Back策略（只有一份副本正确）。 为了区分是否是第一次写，把“读-写”状态分成两个状态：Reserved和Drity。3. 数据块的四种状态 有效状态（Valid）：相当于Write-Back里的“只读”，从共享存储器中读入的并与存储器副本一致的Cache数据块。 无效状态（Invalid）：在Cache中找不到或Cache中

41、的数据块内容与共享存储器中的内容不一致的Cache数据块。 保留状态（Reserved）：数据从共享存储器读入Cache只被写过一次。Cache中的副本与共享存储器中的副本是一致的，并且它是正确的副本。 重写状态（Dirty）：Cache中的数据块不止一次被写过，此时共享存储器中的数据块也不是正确的数据块，唯一正确的数据块在Cache中。4. 如果处于“有效”状态有效保留WrRl, Rr无效Wl重写（1）本地读Rl，不影响状态。（2）本地写Wl（第一次写），采用Write-Through策略，这时要发无效命令给其它Cache中相应的副本，并修改memory。有效保留（3）远程写Wr（不管是第几

42、次写），远程CPU会发无效命令：有效无效（4）远程读Rr：不影响状态。5. 如果处于“保留”状态有效保留WrRl无效Rr重写Wl（1）本地读Rl，不影响状态。（2）远程读Rr：这时Cache中只有处于保留状态的数据块是正确的，所以把该数据块送到远程CPU的Cache中（远程Cache中该数据块变为有效），本数据块状态已变为有效。 （3）本地写Wl：第二次及以后的写，采取Write-Back策略，不修改Memory，状态由Reserved变为Dirty（这时只有一个副本有效），发无效命令给其它Cache的对应的副本，使Memory中的副本也无效。（4）远程写Wr：远程CPU会发无效命令，使状态由

43、Reserved变为Invalid。6. 如果处于“重写”状态有效保留WrRr无效Rl，Wl重写（1）本地读Rl：不影响状态。（2）本地写Wl：不影响状态。（3）远程读Rr：这时只有这个Cache的数据块是正确的，所以把该数据块发送给远程的Cache，远程Cache的数据块和本Cache中的数据块都变得有效。（4）远程写Wr：远程CPU写后，发无效命令使状态由重写无效。7. 如果处于“无效”状态有效保留RlWr, Rr无效Wl重写（1）本地读Rl：这时产生Read-Miss，设法找到有效的数据块调入Cache： 如果系统存在处于有效，保留或重写状态的相应数据块，则将其调入本地Cache 如果系

44、统中不存在处于有效、保留或重写状态的相应数据块，则说明共享存储器中的数据块是正确的，直接从共享存储器读入即可。 读入后相应数据块进入“有效”状态。（2）远程读Rr：状态不变（3）本地写Wl：一定是Write-Miss，系统首先把正确的内容调入Cache，然后写Cache，因为是第一次写，所以Write-Through策略，同时写memory，将本地Cache状态置为“保留”，同时将系统中其它相应的数据块置为“无效”（4）远程写Wr：状态不变第七章 Memory Consistency7.1 问题的提出7.1.1 存储器一致性问题7.1.2 存储器访问的原子性问题7.1.3 存储器访问操作的三个

45、阶段7.1.4 一个例子*7.1.5 多处理机存储器的行为7.2 四种存储器一致性模型 7.2.1 顺序一致性模型7.2.2 弱一致性模型7.2.3 处理机一致性7.2.4 释放一致性7.2.5 四种模型的其它说明7.1 问题的提出7.1.1 存储器一致性问题1.定义存储器一致性是指一个系统正确执行存储器操作的能力。各处理机看到存储器的值是一致的。2.顺序一致性程序次序执行次序存储器访问次序顺序一致性：存储器访问次序同程序执行次序一致。顺序不一致性：存储器访问次序同程序执行次序不一致。3. 实际系统中的问题 在单机系统中，一个取数指令返回的总是对同一存储单元最近一次写指令所写的值。 但实际系统

46、中，采用Cache、写缓冲和pipeline等技术在不破坏数据相关性的同时，允许存储器操作不按程序指定的顺序发出。 在多处理机环境下，一个存储单元可以被多个处理机访问，“最近一次写操作”、“下一次写操作”、“之后的读操作”这些概念的含义是不清楚的，可能出现多个处理机发出的多个存储请求不按要求的顺序执行，这就要求重新定义存储器一致性模型：当n个处理机同时发出存储访问请求时，什么样的访问顺序是合法的？4. 多机系统中的难点 在多机系统中，只检测多处理机的内部相关性是不够的，顺序一致性比较难维持，这是因为： （1）多个指令流的执行次序并不一定一样，如无同步，大量指令交叉执行可能发生。 （2）如想改善

47、性能，每台处理机中指令执行的次序与程序次序不同，则会发生更多的指令交叉执行。 （3）由于互连网络对不同的存储器访问而引起不一样且无法预测的延迟（如冲突），可能存储器访问命令按程序次序发生，但到达存储器的次序不一样了。 （4）存储器访问对Cache-based的系统就不是原子访问，如并非所有的Cache副本同时修改或失效，则可按程序发出访问命令并到达Memory，但完成不一定按程序次序，不同处理机观察到的将是不同的交叉。此时，一个程序可能会产生多种执行情况。7.1.2 存储器访问的原子性问题 如果所有处理机同时看到一份数据拷贝，则系统中的存储器访问是原子性的。 如果存操作所写的值对所有处理机同时

48、可读，则此写操作是原子操作。 如果存储器更新时为所有处理机所知道，那么这就是原子共享存储器访问。 所以原子存储器成为顺序一致的充分必要条件是要所有存储器访问的执行都必须保持所有各个程序的次序。 因此：在Cache-based系统中，不存在原子性。 例：如下的程序。P1a: A=1b: Print B CP2c: B=1d: Print A CP3e: C=1f: Print A B 假设指令执行的顺序为a，c，e，b，d，f，开始时，A=B=C=0，在非原子系统中： P1 executes b, P1s copy of B has not been updated, P1s copy of C

49、 has been updated. P2 executes d, P2s copy of C has not been updated, P2s copy of A has been updated. P3 executes f, P3s copy of A has not been updated, P3s copy of B has been updated. 这里指令按程序次序执行，但其他处理机并不按程序次序观察到结果，执行结果为0110017.1.3 存储器存取操作的三个阶段 一个存储器存取操作可以分为三个不同的阶段：形成、发生和完成。 形成：当一个处理机提出存储器访问请求，就说该存

50、储器请求“形成”了，这个请求的完成不由该处理机控制。 发生：当一个已形成的请求离开了处理机（包括CPU及本地缓冲），正在向存储器系统传送时，就说这个已形成的请求“发生”了。 完成：对一个读操作，当对同一地址发出的写请求不会影响该读操作的返回值，就说该读操作在此刻“完成”了；对于写操作，在该写操作之后，在下一个对同一地址的写操作之前，所发出的对同一地址的读操作都返回该写操作所写的值，就说该写操作“完成”了。1. 如何确定write的结束点 （1）对本台处理机（进程）而言，则是在处理机和Cache之间的写缓冲器中写入新值。 With respect to a process - writes th

51、e new value to a write buffer between processor and Cache. （2）对存储器而言，则是值进入Cache。 With respect to memory - The value enters Cache. （3）对其它处理机而言，则是使其它Cache副本更新或失效。 With respect to other processor(s) - updates or invalidates other cached copies. （4）全局结束则是所有处理机对它们Cache的修改。换言之，当写修改值传给所有处理机时，则write全局完成。 Al

52、l processor finish updating the copies of their cache lines. In other words, a write is globally performanced when its modification has been propagated to all processors.2. 如何确定read的结束点 （1）对除了发出read之外的所有处理机而言，发read的处理机可访问并Cache命中，其它处理机不能改变回送值。 With respect to all processors other than the issueing p

53、rocessor the issueing processor is granted access and has a Cache hit, so no other processor can change the value to be returned.（2）对指定处理机在Cache缺失时，供给Cache副本的指定处理机不能再改变回送值 With respect to a designated processor during Cache miss the designated processor to supply the cache copy is no longer able to

54、change the value to be returned. （3）对所有处理机，则无处理机能改变回送值 With respect to all processor No processor is able to change the value to be returned. （4）全局结束，没有一台处理机发送对同一地址读命令，而得到此单元变量的前一个值。换言之，在读的值限定以及写此值的写操作全局完成时，read才全局完成。 Globally complete No processor that has a read to the same address will be able to

55、 see an earlier value of the variable. In other words, a read is globally performed when the value it returns is bound and the write that wrote this value is globally performed.3. 区分“对某个处理机完成”与“全局完成” 对于非原子的存取操作，需要区分“对某个处理机来讲完成”和“全局完成”（1）处理机i的写操作对于处理机k来讲完成：当处理机k随后发出的对同一地址的读操作返回该写操作所写的值。（2）处理机i的读操作对于处

56、理机k来讲完成：当处理机k随后发出的对同一地址的写操作不会影响该读操作返回的值。（3）一个写操作是全局完成的：如果它对于所有处理机来讲完成（即所有处理机随后发出的对同一地址的读操作返回该写操作所写的值）。（4）一个读操作是全局完成的：如果它对于所有处理机来讲完成（即所有处理机对同一地址的写操作不会影响该读操作返回的值），并且决定该读操作返回值的写操作已经全局完成。7.1.4 例:多处理机中的存储器系统访问次序P1a: A=1b: Print B CP2c: B=1d: Print A CP3e: C=1f: Print A BShared MemoryA，B，C是存储器中的共享变量（初始时 A

57、=B=C=0）开关在原子系统中： Print语句在同一周期内不可分割地输出二个变量。 如果把三台处理机的输出按P1，P2，P3的次序串连起来，则输出就形成一个二进制向量的6元组。 有26=64种可能的输出组合。 (1)如果所有处理机按各自的程序次序执行指令： 会出现的执行交叉为：a,b,c,d,e,f ，产生的输出向量为001011。 会出现的执行交叉为：a,c,e,b,d,f ，产生的输出向量为111111。 (2)如果允许处理机不按程序次序执行指令（假设重新排序后指令之间不存在数据相关） 如执行交叉为：b,d,f,e,a,c ，产生的输出向量为000000。 这个例子一共有6！=720种交

58、叉执行可能，其中90种可保持各自的程序次序。 输出011001不可能，如下图：P1输出01b before ce before bP2输出01a before dd before eP3输出01f before ac before fe before ca before ec before aa before c矛盾*7.1.5 多处理机存储器的行为（1）所有处理机都保持程序次序，并且有相同的执行次序。（2）所有处理机都可以不按程序次序执行，但有相同的执行次序。 （3）不同处理机都可以不按程序次序执行，并且有不同的执行次序。 原子存储器成为顺序一致性的充分必要条件是所有存储器访问的执行都必须保

59、持所有多个程序的次序。 在非原子存储器访问的多处理机中，遵守各自的程序次序并不是顺序一致性的充分条件。7.2 四种一致性模型7.2.1 顺序一致性模型1.定义 顺序一致性存储模型（Sequential Consistency，SC）中，所有处理机的取、存和交换操作（原子取存）都可以看作是按一种单一的全局存储次序在顺序的执行，这种存储次序与处理机各自的程序次序是相符合的，如图所示：单端口存储器P1P2P3Pn存储器的访问次序与程序的执行次序一致 Lamport定义（1979）：如果任意一次执行的结果都象所有处理机的（memory）操作是以某种顺序执行所得到的一样，而且就在这个序列中，多台处理机的

60、（memory）操作都按照它的程序所指定的次序出现，那么这样的多处理机是顺序一致性系统。A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operation of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the o