哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 5章 分布式存储器及其时延容忍
??1 层次存储器技术
??2 高缓一致性协议
??3 共享存储器的一致性
??4 分布式高速缓 /主存体系
结构
哈尔滨工业大学计算机科学与技术学院
一,问题的提出
哈尔滨工业大学计算机科学与技术学院
1.一种解决方案,
哈尔滨工业大学计算机科学与技术学院
?2,两种实用的方法,
? 写直达 (Write-through)法,
? 每次写入 Cache时也把相同的数写入
主存储器。
? 特点,
?这种管理写操作的方法虽然简化了
I／ O处理器的访问。
?它增加了中央处理器与主存储器之
间的信息流量，又降低 I／ O性能。
哈尔滨工业大学计算机科学与技术学院
? 写回 (Write-back)法
? 写操作期间中央处理器修改了 Cache数
据之后，并不马上修改主存储器的相
应单元；
? 在 Cache中被修改的行从 Cache中淘汰
时，才把它写入主存储器，这里的
,写回, 是指写回主存储器。
哈尔滨工业大学计算机科学与技术学院
二、多处理机环境下的高速缓存一
致性问题
?1.多个不同的处理器对同一高速
缓存行的写操作
?按所有处理器所见到的存储器事件
的顺序而串行化写。
哈尔滨工业大学计算机科学与技术学院
?可能引起高速缓存不一致的原因
有以下 3种,
(1)不同处理器对各自缓存的同一高速
缓存行的不同拷贝的异步写操作；
(2)多处理器系统中的进程迁移，而又
不互相通报；
(3)绕过高速缓存拷贝拥有者的 I/O操作。
哈尔滨工业大学计算机科学与技术学院
?2.例题 由共享数据写操作引起
的高速缓存一致
?在写操作前后高速缓存状态的变
化由下图所示。假设在更新前两
个处理器各自缓存的数据 (标为 x)
与共享主存中的相应数据是一致
的。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.例题 由进程迁移引起的高
速缓存不一致
?假设处理器 P1的高速缓存中有主
存中数据 x的拷贝，当某进程从
P1，迁移至 P2后将主存数据 x改
写为 y。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?4.例题：由绕过高速缓存的
I/O操作引起的不一致
?下图表明将 I/O作为 WT高速缓存下的
输入设备和 WB高速缓存下的输出设
备时，由于绕过高速缓存的输入／
输出操作所引起的不一致。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?结论,
?WT和 WK不满足实际的需要。
哈尔滨工业大学计算机科学与技术学院
?三、监听一致性协议
?当各处理器的高速缓存都连接到
公共总线时，有两类协议,
?写 --无效 (write-invalidate)协
议；
?写 --更新 (write-update)协议。
哈尔滨工业大学计算机科学与技术学院
?监听一致性协议体现在,
?监听协议需要由总线或环提供
的广播机制 ;
?不断地监听总线上处理器和存
储器模块间的高速缓存操作事
件
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?1.写 — 无效协议
?在下图中，可以看到对主存数据 x
存在 3份高速缓存中的拷贝。
?当某一处理器想要进行写操作时，
首先它必须获得对 x访问的独占权，
然后更新数据为 x’，并使其他处
理器高速缓存中的相应数据拷贝
失效。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?使用 WB高速缓存时，主存相应数
据行也被设置为无效。
?若使用 WT高速缓存，该主存数据
行将会立即更新为 x’。
哈尔滨工业大学计算机科学与技术学院
?2.写 --更新协议
?当某一处理器对高速缓存数据 x作
写操作时，它必须通过广播 x’的方
法来更新 x在所有处理器高速缓存
中的拷贝。
?当其它的处理器要访问修改过的 x’
时，会在本地高速缓存命中。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?写更新协议具有明显的缺点？
?大多数多处理机设计者选择使用
WB高速缓存的写无效一致性协议
哈尔滨工业大学计算机科学与技术学院
?3.基于更新和基于作废协议的对比
? 问题,
? 对一个缓存中某个块的写操作应该使用更新操
作，还是无效操作？
? 基于更新和基于无效协议的相对性能在很大程
度上取决于应用程序负载表现出来的共享模式，
以及各种操作的代价
? 如果处理器采用更新，并可能希望要在将来看
到新的值，更新就会比无效有更好的性能
? 老数据的处理器再不用它了，更新就不必要
? 无效操作清除旧的拷贝，消除了明显的共享
哈尔滨工业大学计算机科学与技术学院
?概念,
?缓存缺失（不命中、扑空,miss)
?总线流量
哈尔滨工业大学计算机科学与技术学院
? 例题,用缓存扑空数和总线流量评价，基于
更新和基于作废协议的相对代价
? 模式 1：重复 k次；处理器 1向变量 V写入一个新的
值，处理器 2到处理器 P读 V的值。
? 这表现了一种单生产者多消费者机制可能出现的情形，
事件同步中处理器访问一个高度争用的标记变量。
? 模式 2：重复 k次；处理器 1向变量 V写 M次，然后
处理器 2读 V
? 这是一种在处理器对之间可能出现的一种共享模式，
其中第一个处理器连续计算一个变量的值，当累加完
成后，另一个处理器读这个值。
哈尔滨工业大学计算机科学与技术学院
?假设,
? 无效过程要消耗 6个字节 (5个字节地址,1
个字节命令 )，更新需 14个字节 (6个字节地
址和命令,8个字节为更新的数据 ),
? 一个常规的缓存扑空要 70个字节 (6个字节
地址和命令，加上 64个字节的数据，对应
一个缓存块 )。
? 还假设,P=16,M=10,k=10，缓存最初都
是空的。
哈尔滨工业大学计算机科学与技术学院
?分析,
? 对于模式 1
? ① 模式 1更新方案,
? 在所有 P个处理器上的第一次迭代将引起一个常
规的缓存扑空 (包括处理器 1在写操作的时候 )加
上由于写的一次更新。在后续的 k-1次迭代中不
会产生更多的扑空，并且每次迭代只有一次更新
产生。这样总体上
? 扑空 =P=16;
? 流量 =P× RdMiss+ k
× Update=16X70+10X14=1260字节。
哈尔滨工业大学计算机科学与技术学院
? ② 模式 1无效方案
? 所有 P个处理器在第一次迭代将引起一个常
规缓存扑空。在后续 k-1，处理器 1将产生
一次升级，但所有其他的处理器将经历一
次读扑空。这样，将升级算作扑空,
? 扑空 =P+(k-1)XP=16+9X16=160，其中 151个
是读扑空,9个是升级；
? 流量 =读扑空 XRdMiss+(k-1)XUpdate=
151X70+9X6 =10624字节
哈尔滨工业大学计算机科学与技术学院
?模式 2,
? ① 模式 2更新方案
? 首次迭代将发生两次常规缓存扑空，处理
器 1一次，处理器 2一次；在后续 k-1次迭代
中，将没有更多的扑空产生，但在每次迭
代会产生 M次更新。这样，我们将看到扑空
=2；
? 流量 =2XRdMiss+MX(k-1)
XUpdate=2X70+10X9X14=1400字节
哈尔滨工业大学计算机科学与技术学院
? ② 模式 2无效方案
? 首次迭代将发生两次常规缓存扑空。在后
续 k-1次迭代中，每次迭代产生 1次升级
(对于第一个写 )和一次常规读扑空。这样，
将升级算作扑空，总体上
扑空 =2+(k-1) =2+9=11；
? 流量 =扑空 XRdMiss+(k-1)XUpgrade
=11X70+9X6=824字节
? 结论,
? 各有优缺点；
? 有可能设计出方案来，使更新和作废协议
双方的优点都体现出来。
哈尔滨工业大学计算机科学与技术学院
?3.基于更新和基于无效协议的结合
? 结合优点，二者都支持。
?通过页面粒度动态决定，一个缓存页
的一致性是通过更新还是通过无效来
维护。
哈尔滨工业大学计算机科学与技术学院
? 关于协议选择的决定可以通过系统调
用指出
? 它们利用 TLB来向一致性子系统指明用哪
一种协议。
? 这种方案的主要缺点是它们给程序员增
加了为页或者数剧结构选择协议的负担。
? 由于控制的粒度较粗，也使得这种决定
不容易作出，因为适应不同数据结构的
页可能落在相同的页面上。
哈尔滨工业大学计算机科学与技术学院
? ① 替代的方法
? 是通过在运行时观察共享的行为，在缓
存块的粒度来选择协议。理想情况每一
个写希望能够看到未来所有处理器对当
前缓存块的引用，然后再决定是否的拷
贝或者更新。由于这个信息显然是得不
到的，还由于有缓存替换和伪共享带来
的严重的波动，需要一种更实际的方案。
哈尔滨工业大学计算机科学与技术学院
? ② 竞争性方案
? 是基于运行时观察到的模式，从硬件上
在作废和更新之间改变对于一个存储块
的协议。
? 这种方案的关键是，如果对一个缓存块
作了错误的决定，由于那个错误带来的
损失应该保持有界并且很小,
? 例如，如果一个块当前用更新模式，一
旦一个处理器连续向它写，但没有其他
处理器从中读，它就不应该保留在更新
个模式中。
哈尔滨工业大学计算机科学与技术学院
? ③ 限制更新协议的损失
? 让每一缓存块和一个向下计数器联系起来
? 只要一个缓存块被本地处理器访问，它计数值就被置
一个阈值 k。每当一个块收到一次更新，计数器就递
减。如果计数器到了 0，这个块就在本地被无效作废。
? 本地作废的后果是下一次一个更新在总线上产生时，
它可能找不到持有一个有效拷贝的缓存；这种情况将
切换到已修改状态，并且将停止产生更新。
? 如果现在某个处理器访问这一块，它就要再次被切换
到共享状态，这个混合协议会又开始产生更新。
哈尔滨工业大学计算机科学与技术学院
? ④ 一个在 SunSparcCenter2000中实
现的方法
? 是以某种概率有选择地无效，而不是更
新，这个概率是在配置机器时建立的
? 还可以有一些其他混合的做法。
? 例如，在一级缓存上用一种基于作废的
协议，在二级缓存上缺省地用基于更新
的协议。
哈尔滨工业大学计算机科学与技术学院
?4,无效，更新和混合协议方法，利用
工作负载驱动的评估
? 下图按类表示四种应用扑空率
? 条件：用 1MB四路组相联缓存和 64字节的
块。
? 所用的混合协议是刚才描述的基于阈值
方案
? 容量性扑空，扑空有时在使用更新协议时增
加。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 如果升级的（更新）操作大概 4倍于
扑空
? 将这些操作和其他扑空分别表示是有
用的
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?结论,
? 更新协议的流量相当大的。这主要是由于同一
个处理器对相同的块在一发出的多个写操作都
要产生更新。而对无效协议来说，第一个写可
能引起作废，但可以简单地累积在本地块中，
在回写或者向别的缓存提供数据时以一次总线
事务传送。这种增加的流量引起冲突，能够大
大增加扑空的代价。
? 复杂的更新方案延迟更新的时机，以取得一种
类似的效果 (通过合并写缓冲中的写操作 )或者
用其来减少流量和改进性能。
? 带宽要求支持更新所带来缓存块变大的趋势，
以及多道顺序程序负载的收集鼠现象，使得基
于更新的协议用得越来越少。
? 更新对多处理器系统设计者的吸引力越来越低
哈尔滨工业大学计算机科学与技术学院
?四、侦听的状态转换图表示
? 状态转换图实际上是一个有限状态机，
它决定了高速缓存块在它的状态之间是
如何转换的
? 与每个高速缓存块相关的状态转换图。对
于每一个高速缓存块，除了标记 (Tag)和数
据外，还有一个与它相关的状态。
? 在多处理机系统中，一个内存块在每个处
理器的高速缓存中都有一个状态，所有的
这些状态都按照状态转换图来转换。
哈尔滨工业大学计算机科学与技术学院
? 一般来说，在侦听高速缓存一致性协
议中，每个高速缓存控制器接收两方
面输入,
?处理器发出的内存请求
?总线上侦听到的事务
?作为对这些输入的响应，高速缓存
控制器可能要根据相应块的当前状
态及状态转换图来更新该块的状态，
并且也可能要执行一些动作。
哈尔滨工业大学计算机科学与技术学院
? 侦听协议实际上是一组互相协作的有限状
态机所表示的分布式算法，它由三部分组
成,
? ① 状态集合：一个与本地高速缓存中内存
块相关联的状态集合；
? ② 状态转换图：以当前状态和处理器请求
或观察到的总线事务作为输入，输出该块
的下一个状态；
? ③ 动作：与每个状态转换相关的实际动作，
这是由总线、高速缓存和处理器的具体设
计来决定的。
哈尔滨工业大学计算机科学与技术学院
? 动作,
? 一个状态到另一个状态的转换由一个带
箭头的弧线表示，弧线由记号 A／ B来标
记。
? A／ B表示高速缓存控制器观察到事件 A发
生了，或者说由于事件 A导致了该转换的
发生，除了发生状态转换外，还要产生
一个动作 B
哈尔滨工业大学计算机科学与技术学院
? 对同一个块的不同状态机不是独立操作的，
而是通过总线事务来相互协调的。
? 下图描述了一个简单的使无效协议的状态
转换图，该协议采用了写直达且写不分配
的高速缓存。
? 其中，每个高速缓存块有无效 I和有效 V两个状
态。对于不在高速缓存中的块，可看做处于无
效状态。每个转换由一个输入和输出来表示。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 输入表示引发该转换的条件，输出表示
该转换产生的总线事务
? 当控制器看到一个处理器发出的读请求
在高速缓存中缺失时，发出一个总线读
(BusRd)事务，并在总线事务完成时，
将该块状态变为有效状态
? 当控制器看到处理器发出写请求时，产
生一个总线写 (BusWr)事务来更新主存，
但不改变块状态。
哈尔滨工业大学计算机科学与技术学院
? 这个状态转换图与单处理机情况下的主要
不同点是,
? 当高速缓存控制器在总线上侦听到一个
总线写事务，并且在本地高速缓存中有
该事务请求的内存块的拷贝时，就将该
内存块 在本地高速缓存中的拷贝状态置
为无效状态
? 所有的高速缓存控制器相互合作来保证
在任意时刻只能有一个处理器对一个数
据块进行写操作，但同时可以有多个处
理器进行读操作
哈尔滨工业大学计算机科学与技术学院
?分析该协议保证高速缓存一致性
? 按照高速缓存一致性的定义
? 总线上同时只能有一个事务，处理器必须等到
前一个总线事务完成后才发出下一个内存请求。
? 在写直达策略中所有的写操作 都出现在总线上，
但由于同时只能有一个总线事务出现在总线上，
所以在任意执行中所有对同一个位置的写操作
都按照它们出现在总线上的次序 —— 总线序
(BusOrder)被全局串行化了。
? 使无效也按总线序被全局串行化了,由于所有
的侦听高速缓存控制器在总线事务中都执行了
使无效动作。
哈尔滨工业大学计算机科学与技术学院
? 读操作未被完全全局串行化,因为读命中不产
生总线事务，所以它们可以独立产生。读缺失
与写操作一起被总线序全局串行化，从而它可
根据全局的总线序来获得最新写入的值。
? 读命中获得的值或者是同一个处理器中对该位
置的一个最近的写操作所产生的，或是在同一
个处理器中最近一次读缺失获得的值，因为这
两种情况都出现在总线上，所以读命中同样也
是按照一致的全局总线序来获得值。
? 可见在该协议下，总线序和程序序共同
保证了对高速缓存一致性的要求。
哈尔滨工业大学计算机科学与技术学院
? 五、三态写回无效 MSI协议
? 1.MSI(ModifiedSharedlnvalid)协议
? 三种状态,
? ① 无效 (I)状态：它意味着该块在高速缓存中是无效的，
或者该块还没有进入高速缓存，在其他高速缓存中可能
有，也可能没有该块的有效拷贝；
? ② 共享 (S)状态：它意味着该块在高速缓存中未被修改过，
主存中是最新的，在其他高速缓存中可能有，也可能没
有该块的有效拷贝；
? ③ 修改过 (M)状态：也叫做脏状态，它意味着只有该高速
缓存中有该块的最新拷贝，主存中的拷贝是过时的
(Stale)，在其他高速缓存中没有该块的有效拷贝。
哈尔滨工业大学计算机科学与技术学院
? 已知在侦听高速缓存一致性协议中，每个高速缓
存控制器接收两方面输入,
? 处理器发出的请求和总线上侦听到的事务。
? 对于前者，处理器发出处理器读 (PrRd)和处理
器写 (PrWr)两种类型的请求，并且读或写都有
可能是对已经在或者不在高速缓存中的内存块
进行。
? 假如是对不在高速缓存中的内存块进行读或写，
若缓存已满，则当前高速缓存中的一块就必须
被新请求的块替换出去。并且，若被替换出去
的块处于 M状态的话，则必须将其内容写回到
内存中。
哈尔滨工业大学计算机科学与技术学院
? 对于后者，假设总线允许以下三种事务,
① 总线读 (BusRd),
? 高速缓存控制器将地址放到总线上，请求一个它不准备去修
改的数据块，由主存或者另一个高速缓存提供数据。
② 总线互斥读 (BusRdX),
? 高速缓存控制器将地址放到总线上，请求一个它准备修改的
互斥拷贝，由主存或者另一个高速缓存提供数据。所有其他
高速缓存中的拷贝都必须被置为无效。该事务是由对某个不
在缓存或虽然在缓存但没有被标记为 M的块的写操作引起的。
一旦缓存获得互斥拷贝，写操作就能在缓存中执行，处理器
可能会要求一个确认信号作为该事务的结果。总线互斥读事
务是唯一一个为了实现高速缓存一致性才引入的新事务。
③ 总线写回 (BusWB),
? 缓存控制器将主存块的地址和内容放到总线上，主存用该最
新的内容来更新。这种事务由缓存控制器的写回操作引起，
处理器并不知道，也不期望得到响应。
哈尔滨工业大学计算机科学与技术学院
?除此之外,
? ④ 刷新 (Flush)：为支持写回协议，除了改
变缓存块的状态外，还需要一种新的动作，
即高速缓存控制器能够响应出现在总线上的
事务，并能把该事务所请求的块从缓存中放
到总线上，而不是让内存提供数据，这个动
作称为刷新 (Flush)。当然，高速缓存控制
器的工作还包括发出一个新的总线事务，为
写回提供数据以及接受主存提供的数据。
哈尔滨工业大学计算机科学与技术学院
? 2．状态转换
? 在 MSI侦听协议中，控制每个高速缓存中的
某个块的状态转换图
? 如下图中 M,S和 I分别代表相应的修改过、
共享和无效状态。
? 记号 A／ B中,,—,表示空动作； Flush动作表
示由高速缓存来提供请求块到总线上。有些弧线
上有多个记号，表示这些事件引起相同的状态转
换。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 3.从状态转换图可以看出的转换,
? 当一个处理器读一个无效块时，高速缓存控制器就通
过产生一个 BusRd事务来得到该块，并且该块状态变
为 S状态；
? 当写一个共享或者无效块时，就通过产生一个 BusRdX
事务来得到该块的互斥拥有权，并将该块状态置为 M；
? 如果高速缓存控制器在总线上观察到一个 BusRd事务，
并且该事务请求的块在本地高速缓存中处于 M状态，
则将该块内容放到总线上 (Flush)，同时将该块状态
置为 S态
? 如果在总线上观察到 BusRdX事务，并且所请求的块在
本地高速缓存处于 S状态，则只要简单将该块置为 I状
态；
? 如果在本地高速缓存中处于 M状态，则要将该块内容
放到总线上 (Flush)，然后将该块状态置为 I状态。
哈尔滨工业大学计算机科学与技术学院
?4.例题
? 具体的一个状态转换的例子可看下表，显示了
在下图的例子中采用 MSI协议时，所产生的总线
事务和内存块状态的转换情况。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 一个状态转换的例子一览表
处理器
动作
P1中
状态
P2中
状态
P3中状
态
总线事务 数据提供者
Pl读 u S —— —— BusRd 主存
P3读 u S —— S BusRd 主存
P3写 u I —— M BusRdX 主存
P1读 u S —— S BusRd P3高速缓存
P2读 u S S S BusRd 主存
哈尔滨工业大学计算机科学与技术学院
?六,MESI监听协议
?1.前言
?MESI属于写无效协议。它根据所
有的读、写、命中或不命中，与
在总线上监听的事件来跟踪高速
缓存行的状态。
哈尔滨工业大学计算机科学与技术学院
? MESI(ModifiedExclusiveShared lnvalid)
协议是 MSI协议的改进协议。
? 这个协议最初是由在 Urbana— Champaign
的 Illinois大学的研究者提出的，所以也
称为 Illinois协议。
哈尔滨工业大学计算机科学与技术学院
? 许多现代微处理器设计中已经实现了 MESI
协议，例如 Intel Pentium,i860、
PowerPC 601等。
? 与 MSI协议相比,MESI协议增加了一个互
斥 (E)状态。
? 小规模的 SMP机器的一类主要的工作负载是顺
序程序，假如采用 MSI协议，当一个顺序程序
先读人一个数据项，然后修改一个数据项时，
就要产生两个总线事务,
哈尔滨工业大学计算机科学与技术学院
? ① 一个 BusRd事务，用来得到内存块，并
置为 S状态 产生一个 BusRdX事务，用来将该块
状态从 S变为 M状态。而在顺序程序中数据项不
存在共享者，因此只会在一个高速缓存有该块
拷贝,
? ② 后一个 BusRdX事务是不必要的。为了改进这
种情况,加入了一个 E状态,用来表示只有一个
高速缓存中有这个内存块，且该块内容没有被
修改过。
? 只要开始发出 BusRd事务，得到内存块，并置为 E状
态，就可以直接进行修改，而不需要产生 BusRdX事
务。
哈尔滨工业大学计算机科学与技术学院
?MESI协议由四个状态组成,
? 修改过 (M)(或称为脏状态 )、互斥干净
(E)、共享 (S)和无效。
? 其中,M和 I状态和 MSI协议中意思是相同
的；
?E状态表示只有一个高速缓存中有这个内
存块，且该块内容没有被修改过
? 主存中是最新的
? 共享状态表示有两个或者更多高速缓存
中有该块拷贝。
哈尔滨工业大学计算机科学与技术学院
? MESI协议对总线信号有一些新要求。
? 在产生 BusRd事务并装入内存块时，高速缓存控
制器要知道别的高速缓存中是否存在该块的拷贝，
来决定将该块置为 S状态还是 E状态。
? 这就需要总线提供一个额外的共享 (S)信号线。
在总线事务的地址阶段，所有的高速缓存都要
检查是否含有请求块的拷贝，若有，则置位共
享信号线。
? 发出总线事务的高速缓存控制器，只要检查一
下共享信号线，就能判断出是否有别的高速缓
存中存在该块拷贝，以此决定该块装入后置为
S状态还是 E状态。
哈尔滨工业大学计算机科学与技术学院
? 在 S状态下，如果发生一个处理器写，由于该
高速缓存已经有最新的拷贝了，因此不需要
获得数据，这时可以采用一个新的总线事
务 —— 总线升级 (BusUpgr)，然后转换到 M状
态。
? 所有其他的高速缓存侦听到该事务，将其相
关的拷贝置为无效状态
? 不同点在于总线升级事务不需要数据响应，
也就不会导致实际的数据传输，主存或其他
的高速缓存不需要提供数据。
哈尔滨工业大学计算机科学与技术学院
? 2．状态转换
? 下图所示是 MESI协议的状态转换图。图中的记号与 MSI
状态转换图相似，具体的协议转换也与 MSI协议类似。
? 若在无效状态 I下有处理器读 (PrRd)发生，则根据 S
线是否被置位，来决定是转换到 E状态还是 S状态，
若置位则转换到 S状态，否则转换到 E状态，其中
BusRd(S)表示在 BusRd事务中 S线被置位。
? 在 E状态下，若发生处理器写 (PrWr)，将导致由 E状
态转换到 M状态，不产生总线事务；若观察到一个总
线读 (BusRd)事务，将导致由 E状态转换到 S状态，同
时由该高速缓存提供数据；若观察到一个总线互斥
读 (BusRdX)事务，将导致由 E状态转换到 I状态，同
时由该高速缓存提供数据。其他状态转换与 MSI协议
类似。
哈尔滨工业大学计算机科学与技术学院
? 还有一个不同点在于当高速缓存和主存中都有
最新数据时由谁来提供数据。在 S状态下，若
观察到一个总线读 (BusRd)事务或总线互斥读
(BusRdX)事务，在进行状态转换的同时，在
MSI协议中由主存提供数据，而在 MESI中由处
于 S状态下的某一个高速缓存提供数据，其他
的高速缓存不产生动作。
? 这一点在协议设计时可酌情处理。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?七、四态写回更新 (Dragon)协
议
1,Dragon协议
? 现在来看一个基于写回高速缓存的写更新协议，
也称为 Dragon协议。
哈尔滨工业大学计算机科学与技术学院
?Dragon协议有四种状态,
? (1)互斥且干净 E(Exclusive— Clean)：用
来表示仅有一个缓存 (本缓存 )拥有 该块的
拷贝，并且没有被修改过，也就是说，主
存中是最新的。
? (2)共享且干净 SC(Shared— Clean)：用来
表示可能有两个或更多缓存中拥有该块，
并且主存中可能是,也可能不是最新的。
哈尔滨工业大学计算机科学与技术学院
? (3)共享且修改过 SM(Shared— Modified)
? 用来表示可能 有两个或更多缓存中拥有该块，
且主存中不是最新的 。缓存应当负责当该块
由缓存中被替换出时，更新主存中的数据。
在某个时刻，一个块只可能在一个缓存中处
于 SM状态。然而，一个块在某个缓存中处于
SM状态，而在另一个缓存中处于 SC状态是可
以的。或者，一个块在任何缓存中都不处于
SM状态，而在某些缓存中处于 SC状态。这就
是为什么缓存中的块处于 SC状态，而主存中
却可能是也可能不是最新的，这依赖于是否
在某个缓存中该块处于 SM状态。
哈尔滨工业大学计算机科学与技术学院
? （ 4)修改过 M(Modified)
? 用来表示该块仅在该缓存中处于被修改过 (脏
状态 )，主存中已经过时。缓存负责在该块被
替换出来时更新主存。
? 注意到与前面的协议不同，这里没有显式
的无效状态。这是因为 Dragon是基于更新
的协议，在该协议中，缓存中的块总是最
新的。
? 只要某块在缓存中，该块总是有效的。然
而，对于不在缓存中的块，可以想像为一
种特殊的无效状态。
哈尔滨工业大学计算机科学与技术学院
? Dragon协议中的处理器请求、总线事务和动
作，与在 MESI协议中的相似。
? 先来看一下处理器请求。假设处理器还是
只发出读 (PrRd)和写 (PrWr)请求。但由于
本协议中不存在无效状态，为了表达出处
理器第一次请求一个新内存块这个动作，
增加了处理器读缺失 (PrRdMiss)和处理器
写缺失 (PrWrMiss)两种处理器请求。
哈尔滨工业大学计算机科学与技术学院
? 总线事务,
? 有总线读 (BusRd)、总线写回 (BusWB)和总线更
新 (BusUpd)事务。 BusUpd事务将处理器所写的
内容在总线上进行广播，使得所有其他的高速
缓存都能进行更新。通过只广播修改过的内容，
而不是整个内存块，可以更充分利用总线带宽。
? 为了支持 E状态，与 MESI协议一样，也需要一个
共享信号。另外，高速缓存控制器还要一个新
动作，就是根据总线上出现的 BusUpd事务，来
更新高速缓存中的相应块的内容。
哈尔滨工业大学计算机科学与技术学院
? 2．状态转换
? 状态转换图如下图所示。下面就分别描述一下，
当发生读高速缓存缺失、执行写操作以及高速
缓存块被替换出去时，所发生的一系列动作。
? (1)读缺失 (ReadMiss) 产生一个 BusRd事务。
根据共享信号 (S)的状态，决定该块被装入本
地高速缓存后，是处于 E状态，还是 SC状态。
? (2)写 (Write) 如果所写的块在本地高速缓存
中处于 M状态，就不需要执行任何动作。如果
该块在本地高速缓存中处于 E状态，则直接将 E
状态改为 M状态，也不需要再执行什么动作。
哈尔滨工业大学计算机科学与技术学院
? 如果该块处于 SC或 SM状态，则要产生一个总
线更新 (BusUpd)事务更新 (BusUpd)事务
? 其他任何有该数据拷贝的高速缓存，都要置
位共享信号线，更新本地拷贝中对应的字节，
并且如果需要的话，要将状态变为 SC。
? 本地高速缓存根据共享信号线来决定状态转
换，同时更新该块的拷贝，如果共享信号线
被置位，则将它的状态变为 SM。如果共享信
号线未被置位，则表明没有其他的高速缓存
中含有该数据的拷贝，则将状态变为 M。主
存内容不被更新。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? (3)替换 (Replacement)
? 在发生替换时，只有被替换的块处于 M或
SM状态时，才需要用一个总线事务将其
写回到内存中。
? 如果被替换块处于 SC状态，则要么是其
他高速缓存中有该块的处于 SM状态的拷
贝，要么是主存中已经有最新的值了。
这两种情况下，都只要将该块丢弃即可。
哈尔滨工业大学计算机科学与技术学院
八、例,Pentium多处理机系统采用了
MESI协议
哈尔滨工业大学计算机科学与技术学院
?数据高速缓存中所有行总是处于
下述 4种状态之一,
?已修改 (modified,M)状态
?独占 (exclusive,E)状态
?共享 (shared,S)状态
?无效 (invalid,I)状态
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?1.写直达协议
?对于写直达高速缓存行而言，
初始状态为 I。
?上图的上部由 S和 I状态及其周
边粗虚线和实现组成的双状态
子图单独称为 WT高速缓存事件
的 SI协议 (S／ protocol)。
哈尔滨工业大学计算机科学与技术学院
? 2.回写式高速缓存
? 在 WB方式下，数据被载人某一高速缓存
后为 E状态，也就是说它是系统中唯一有
效的高速缓存拷贝。
? 对外部事件的监听工作相当简单,
① 所有的远程写 (remote write)使该
数据的其它高速缓存拷贝失效。
② 所有的远程读 (remote read)命中使
数据进入 S状态。
哈尔滨工业大学计算机科学与技术学院
?3.WB高速缓存的 MSI协议
?如果我们将 E状态并入 S状态，则
得到在 WB高速缓存下的 3状态 MSI
协议。
?从 MESI状态图中抽取出 MSI子图得
到以下 3种子图转换,
哈尔滨工业大学计算机科学与技术学院
?高速缓存行的唯一有效拷贝状态,
?系统中存在两个以上有效拷贝,
哈尔滨工业大学计算机科学与技术学院
? WT高速缓存的 SI协议
① 可以将 3状态 MSI协议进一步简化为
WT高速缓存下的二状态 SI协议。
② 如果取消高速缓存，则单状态协议
也是可能的。
③ 采用监听协议时，一致性协议的状
态多寡反映了它区分高速缓存行不
同共享状态的能力强弱。
哈尔滨工业大学计算机科学与技术学院
?九,本节总结
?一致性协议具有越多的状态，它
就能区分越多的高速缓存事件和
可能的状态转换。
?实现复杂的协议要付出实现效率
的代价。
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 5章 分布式存储器及其时延容忍
??1 层次存储器技术
??2 高缓一致性协议
??3 共享存储器的一致性
??4 分布式高速缓 /主存体系
结构
哈尔滨工业大学计算机科学与技术学院
一,问题的提出
哈尔滨工业大学计算机科学与技术学院
1.一种解决方案,
哈尔滨工业大学计算机科学与技术学院
?2,两种实用的方法,
? 写直达 (Write-through)法,
? 每次写入 Cache时也把相同的数写入
主存储器。
? 特点,
?这种管理写操作的方法虽然简化了
I／ O处理器的访问。
?它增加了中央处理器与主存储器之
间的信息流量，又降低 I／ O性能。
哈尔滨工业大学计算机科学与技术学院
? 写回 (Write-back)法
? 写操作期间中央处理器修改了 Cache数
据之后，并不马上修改主存储器的相
应单元；
? 在 Cache中被修改的行从 Cache中淘汰
时，才把它写入主存储器，这里的
,写回, 是指写回主存储器。
哈尔滨工业大学计算机科学与技术学院
二、多处理机环境下的高速缓存一
致性问题
?1.多个不同的处理器对同一高速
缓存行的写操作
?按所有处理器所见到的存储器事件
的顺序而串行化写。
哈尔滨工业大学计算机科学与技术学院
?可能引起高速缓存不一致的原因
有以下 3种,
(1)不同处理器对各自缓存的同一高速
缓存行的不同拷贝的异步写操作；
(2)多处理器系统中的进程迁移，而又
不互相通报；
(3)绕过高速缓存拷贝拥有者的 I/O操作。
哈尔滨工业大学计算机科学与技术学院
?2.例题 由共享数据写操作引起
的高速缓存一致
?在写操作前后高速缓存状态的变
化由下图所示。假设在更新前两
个处理器各自缓存的数据 (标为 x)
与共享主存中的相应数据是一致
的。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.例题 由进程迁移引起的高
速缓存不一致
?假设处理器 P1的高速缓存中有主
存中数据 x的拷贝，当某进程从
P1，迁移至 P2后将主存数据 x改
写为 y。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?4.例题：由绕过高速缓存的
I/O操作引起的不一致
?下图表明将 I/O作为 WT高速缓存下的
输入设备和 WB高速缓存下的输出设
备时，由于绕过高速缓存的输入／
输出操作所引起的不一致。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?结论,
?WT和 WK不满足实际的需要。
哈尔滨工业大学计算机科学与技术学院
?三、监听一致性协议
?当各处理器的高速缓存都连接到
公共总线时，有两类协议,
?写 --无效 (write-invalidate)协
议；
?写 --更新 (write-update)协议。
哈尔滨工业大学计算机科学与技术学院
?监听一致性协议体现在,
?监听协议需要由总线或环提供
的广播机制 ;
?不断地监听总线上处理器和存
储器模块间的高速缓存操作事
件
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?1.写 — 无效协议
?在下图中，可以看到对主存数据 x
存在 3份高速缓存中的拷贝。
?当某一处理器想要进行写操作时，
首先它必须获得对 x访问的独占权，
然后更新数据为 x’，并使其他处
理器高速缓存中的相应数据拷贝
失效。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?使用 WB高速缓存时，主存相应数
据行也被设置为无效。
?若使用 WT高速缓存，该主存数据
行将会立即更新为 x’。
哈尔滨工业大学计算机科学与技术学院
?2.写 --更新协议
?当某一处理器对高速缓存数据 x作
写操作时，它必须通过广播 x’的方
法来更新 x在所有处理器高速缓存
中的拷贝。
?当其它的处理器要访问修改过的 x’
时，会在本地高速缓存命中。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?写更新协议具有明显的缺点？
?大多数多处理机设计者选择使用
WB高速缓存的写无效一致性协议
哈尔滨工业大学计算机科学与技术学院
?3.基于更新和基于作废协议的对比
? 问题,
? 对一个缓存中某个块的写操作应该使用更新操
作，还是无效操作？
? 基于更新和基于无效协议的相对性能在很大程
度上取决于应用程序负载表现出来的共享模式，
以及各种操作的代价
? 如果处理器采用更新，并可能希望要在将来看
到新的值，更新就会比无效有更好的性能
? 老数据的处理器再不用它了，更新就不必要
? 无效操作清除旧的拷贝，消除了明显的共享
哈尔滨工业大学计算机科学与技术学院
?概念,
?缓存缺失（不命中、扑空,miss)
?总线流量
哈尔滨工业大学计算机科学与技术学院
? 例题,用缓存扑空数和总线流量评价，基于
更新和基于作废协议的相对代价
? 模式 1：重复 k次；处理器 1向变量 V写入一个新的
值，处理器 2到处理器 P读 V的值。
? 这表现了一种单生产者多消费者机制可能出现的情形，
事件同步中处理器访问一个高度争用的标记变量。
? 模式 2：重复 k次；处理器 1向变量 V写 M次，然后
处理器 2读 V
? 这是一种在处理器对之间可能出现的一种共享模式，
其中第一个处理器连续计算一个变量的值，当累加完
成后，另一个处理器读这个值。
哈尔滨工业大学计算机科学与技术学院
?假设,
? 无效过程要消耗 6个字节 (5个字节地址,1
个字节命令 )，更新需 14个字节 (6个字节地
址和命令,8个字节为更新的数据 ),
? 一个常规的缓存扑空要 70个字节 (6个字节
地址和命令，加上 64个字节的数据，对应
一个缓存块 )。
? 还假设,P=16,M=10,k=10，缓存最初都
是空的。
哈尔滨工业大学计算机科学与技术学院
?分析,
? 对于模式 1
? ① 模式 1更新方案,
? 在所有 P个处理器上的第一次迭代将引起一个常
规的缓存扑空 (包括处理器 1在写操作的时候 )加
上由于写的一次更新。在后续的 k-1次迭代中不
会产生更多的扑空，并且每次迭代只有一次更新
产生。这样总体上
? 扑空 =P=16;
? 流量 =P× RdMiss+ k
× Update=16X70+10X14=1260字节。
哈尔滨工业大学计算机科学与技术学院
? ② 模式 1无效方案
? 所有 P个处理器在第一次迭代将引起一个常
规缓存扑空。在后续 k-1，处理器 1将产生
一次升级，但所有其他的处理器将经历一
次读扑空。这样，将升级算作扑空,
? 扑空 =P+(k-1)XP=16+9X16=160，其中 151个
是读扑空,9个是升级；
? 流量 =读扑空 XRdMiss+(k-1)XUpdate=
151X70+9X6 =10624字节
哈尔滨工业大学计算机科学与技术学院
?模式 2,
? ① 模式 2更新方案
? 首次迭代将发生两次常规缓存扑空，处理
器 1一次，处理器 2一次；在后续 k-1次迭代
中，将没有更多的扑空产生，但在每次迭
代会产生 M次更新。这样，我们将看到扑空
=2；
? 流量 =2XRdMiss+MX(k-1)
XUpdate=2X70+10X9X14=1400字节
哈尔滨工业大学计算机科学与技术学院
? ② 模式 2无效方案
? 首次迭代将发生两次常规缓存扑空。在后
续 k-1次迭代中，每次迭代产生 1次升级
(对于第一个写 )和一次常规读扑空。这样，
将升级算作扑空，总体上
扑空 =2+(k-1) =2+9=11；
? 流量 =扑空 XRdMiss+(k-1)XUpgrade
=11X70+9X6=824字节
? 结论,
? 各有优缺点；
? 有可能设计出方案来，使更新和作废协议
双方的优点都体现出来。
哈尔滨工业大学计算机科学与技术学院
?3.基于更新和基于无效协议的结合
? 结合优点，二者都支持。
?通过页面粒度动态决定，一个缓存页
的一致性是通过更新还是通过无效来
维护。
哈尔滨工业大学计算机科学与技术学院
? 关于协议选择的决定可以通过系统调
用指出
? 它们利用 TLB来向一致性子系统指明用哪
一种协议。
? 这种方案的主要缺点是它们给程序员增
加了为页或者数剧结构选择协议的负担。
? 由于控制的粒度较粗，也使得这种决定
不容易作出，因为适应不同数据结构的
页可能落在相同的页面上。
哈尔滨工业大学计算机科学与技术学院
? ① 替代的方法
? 是通过在运行时观察共享的行为，在缓
存块的粒度来选择协议。理想情况每一
个写希望能够看到未来所有处理器对当
前缓存块的引用，然后再决定是否的拷
贝或者更新。由于这个信息显然是得不
到的，还由于有缓存替换和伪共享带来
的严重的波动，需要一种更实际的方案。
哈尔滨工业大学计算机科学与技术学院
? ② 竞争性方案
? 是基于运行时观察到的模式，从硬件上
在作废和更新之间改变对于一个存储块
的协议。
? 这种方案的关键是，如果对一个缓存块
作了错误的决定，由于那个错误带来的
损失应该保持有界并且很小,
? 例如，如果一个块当前用更新模式，一
旦一个处理器连续向它写，但没有其他
处理器从中读，它就不应该保留在更新
个模式中。
哈尔滨工业大学计算机科学与技术学院
? ③ 限制更新协议的损失
? 让每一缓存块和一个向下计数器联系起来
? 只要一个缓存块被本地处理器访问，它计数值就被置
一个阈值 k。每当一个块收到一次更新，计数器就递
减。如果计数器到了 0，这个块就在本地被无效作废。
? 本地作废的后果是下一次一个更新在总线上产生时，
它可能找不到持有一个有效拷贝的缓存；这种情况将
切换到已修改状态，并且将停止产生更新。
? 如果现在某个处理器访问这一块，它就要再次被切换
到共享状态，这个混合协议会又开始产生更新。
哈尔滨工业大学计算机科学与技术学院
? ④ 一个在 SunSparcCenter2000中实
现的方法
? 是以某种概率有选择地无效，而不是更
新，这个概率是在配置机器时建立的
? 还可以有一些其他混合的做法。
? 例如，在一级缓存上用一种基于作废的
协议，在二级缓存上缺省地用基于更新
的协议。
哈尔滨工业大学计算机科学与技术学院
?4,无效，更新和混合协议方法，利用
工作负载驱动的评估
? 下图按类表示四种应用扑空率
? 条件：用 1MB四路组相联缓存和 64字节的
块。
? 所用的混合协议是刚才描述的基于阈值
方案
? 容量性扑空，扑空有时在使用更新协议时增
加。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 如果升级的（更新）操作大概 4倍于
扑空
? 将这些操作和其他扑空分别表示是有
用的
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?结论,
? 更新协议的流量相当大的。这主要是由于同一
个处理器对相同的块在一发出的多个写操作都
要产生更新。而对无效协议来说，第一个写可
能引起作废，但可以简单地累积在本地块中，
在回写或者向别的缓存提供数据时以一次总线
事务传送。这种增加的流量引起冲突，能够大
大增加扑空的代价。
? 复杂的更新方案延迟更新的时机，以取得一种
类似的效果 (通过合并写缓冲中的写操作 )或者
用其来减少流量和改进性能。
? 带宽要求支持更新所带来缓存块变大的趋势，
以及多道顺序程序负载的收集鼠现象，使得基
于更新的协议用得越来越少。
? 更新对多处理器系统设计者的吸引力越来越低
哈尔滨工业大学计算机科学与技术学院
?四、侦听的状态转换图表示
? 状态转换图实际上是一个有限状态机，
它决定了高速缓存块在它的状态之间是
如何转换的
? 与每个高速缓存块相关的状态转换图。对
于每一个高速缓存块，除了标记 (Tag)和数
据外，还有一个与它相关的状态。
? 在多处理机系统中，一个内存块在每个处
理器的高速缓存中都有一个状态，所有的
这些状态都按照状态转换图来转换。
哈尔滨工业大学计算机科学与技术学院
? 一般来说，在侦听高速缓存一致性协
议中，每个高速缓存控制器接收两方
面输入,
?处理器发出的内存请求
?总线上侦听到的事务
?作为对这些输入的响应，高速缓存
控制器可能要根据相应块的当前状
态及状态转换图来更新该块的状态，
并且也可能要执行一些动作。
哈尔滨工业大学计算机科学与技术学院
? 侦听协议实际上是一组互相协作的有限状
态机所表示的分布式算法，它由三部分组
成,
? ① 状态集合：一个与本地高速缓存中内存
块相关联的状态集合；
? ② 状态转换图：以当前状态和处理器请求
或观察到的总线事务作为输入，输出该块
的下一个状态；
? ③ 动作：与每个状态转换相关的实际动作，
这是由总线、高速缓存和处理器的具体设
计来决定的。
哈尔滨工业大学计算机科学与技术学院
? 动作,
? 一个状态到另一个状态的转换由一个带
箭头的弧线表示，弧线由记号 A／ B来标
记。
? A／ B表示高速缓存控制器观察到事件 A发
生了，或者说由于事件 A导致了该转换的
发生，除了发生状态转换外，还要产生
一个动作 B
哈尔滨工业大学计算机科学与技术学院
? 对同一个块的不同状态机不是独立操作的，
而是通过总线事务来相互协调的。
? 下图描述了一个简单的使无效协议的状态
转换图，该协议采用了写直达且写不分配
的高速缓存。
? 其中，每个高速缓存块有无效 I和有效 V两个状
态。对于不在高速缓存中的块，可看做处于无
效状态。每个转换由一个输入和输出来表示。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 输入表示引发该转换的条件，输出表示
该转换产生的总线事务
? 当控制器看到一个处理器发出的读请求
在高速缓存中缺失时，发出一个总线读
(BusRd)事务，并在总线事务完成时，
将该块状态变为有效状态
? 当控制器看到处理器发出写请求时，产
生一个总线写 (BusWr)事务来更新主存，
但不改变块状态。
哈尔滨工业大学计算机科学与技术学院
? 这个状态转换图与单处理机情况下的主要
不同点是,
? 当高速缓存控制器在总线上侦听到一个
总线写事务，并且在本地高速缓存中有
该事务请求的内存块的拷贝时，就将该
内存块 在本地高速缓存中的拷贝状态置
为无效状态
? 所有的高速缓存控制器相互合作来保证
在任意时刻只能有一个处理器对一个数
据块进行写操作，但同时可以有多个处
理器进行读操作
哈尔滨工业大学计算机科学与技术学院
?分析该协议保证高速缓存一致性
? 按照高速缓存一致性的定义
? 总线上同时只能有一个事务，处理器必须等到
前一个总线事务完成后才发出下一个内存请求。
? 在写直达策略中所有的写操作 都出现在总线上，
但由于同时只能有一个总线事务出现在总线上，
所以在任意执行中所有对同一个位置的写操作
都按照它们出现在总线上的次序 —— 总线序
(BusOrder)被全局串行化了。
? 使无效也按总线序被全局串行化了,由于所有
的侦听高速缓存控制器在总线事务中都执行了
使无效动作。
哈尔滨工业大学计算机科学与技术学院
? 读操作未被完全全局串行化,因为读命中不产
生总线事务，所以它们可以独立产生。读缺失
与写操作一起被总线序全局串行化，从而它可
根据全局的总线序来获得最新写入的值。
? 读命中获得的值或者是同一个处理器中对该位
置的一个最近的写操作所产生的，或是在同一
个处理器中最近一次读缺失获得的值，因为这
两种情况都出现在总线上，所以读命中同样也
是按照一致的全局总线序来获得值。
? 可见在该协议下，总线序和程序序共同
保证了对高速缓存一致性的要求。
哈尔滨工业大学计算机科学与技术学院
? 五、三态写回无效 MSI协议
? 1.MSI(ModifiedSharedlnvalid)协议
? 三种状态,
? ① 无效 (I)状态：它意味着该块在高速缓存中是无效的，
或者该块还没有进入高速缓存，在其他高速缓存中可能
有，也可能没有该块的有效拷贝；
? ② 共享 (S)状态：它意味着该块在高速缓存中未被修改过，
主存中是最新的，在其他高速缓存中可能有，也可能没
有该块的有效拷贝；
? ③ 修改过 (M)状态：也叫做脏状态，它意味着只有该高速
缓存中有该块的最新拷贝，主存中的拷贝是过时的
(Stale)，在其他高速缓存中没有该块的有效拷贝。
哈尔滨工业大学计算机科学与技术学院
? 已知在侦听高速缓存一致性协议中，每个高速缓
存控制器接收两方面输入,
? 处理器发出的请求和总线上侦听到的事务。
? 对于前者，处理器发出处理器读 (PrRd)和处理
器写 (PrWr)两种类型的请求，并且读或写都有
可能是对已经在或者不在高速缓存中的内存块
进行。
? 假如是对不在高速缓存中的内存块进行读或写，
若缓存已满，则当前高速缓存中的一块就必须
被新请求的块替换出去。并且，若被替换出去
的块处于 M状态的话，则必须将其内容写回到
内存中。
哈尔滨工业大学计算机科学与技术学院
? 对于后者，假设总线允许以下三种事务,
① 总线读 (BusRd),
? 高速缓存控制器将地址放到总线上，请求一个它不准备去修
改的数据块，由主存或者另一个高速缓存提供数据。
② 总线互斥读 (BusRdX),
? 高速缓存控制器将地址放到总线上，请求一个它准备修改的
互斥拷贝，由主存或者另一个高速缓存提供数据。所有其他
高速缓存中的拷贝都必须被置为无效。该事务是由对某个不
在缓存或虽然在缓存但没有被标记为 M的块的写操作引起的。
一旦缓存获得互斥拷贝，写操作就能在缓存中执行，处理器
可能会要求一个确认信号作为该事务的结果。总线互斥读事
务是唯一一个为了实现高速缓存一致性才引入的新事务。
③ 总线写回 (BusWB),
? 缓存控制器将主存块的地址和内容放到总线上，主存用该最
新的内容来更新。这种事务由缓存控制器的写回操作引起，
处理器并不知道，也不期望得到响应。
哈尔滨工业大学计算机科学与技术学院
?除此之外,
? ④ 刷新 (Flush)：为支持写回协议，除了改
变缓存块的状态外，还需要一种新的动作，
即高速缓存控制器能够响应出现在总线上的
事务，并能把该事务所请求的块从缓存中放
到总线上，而不是让内存提供数据，这个动
作称为刷新 (Flush)。当然，高速缓存控制
器的工作还包括发出一个新的总线事务，为
写回提供数据以及接受主存提供的数据。
哈尔滨工业大学计算机科学与技术学院
? 2．状态转换
? 在 MSI侦听协议中，控制每个高速缓存中的
某个块的状态转换图
? 如下图中 M,S和 I分别代表相应的修改过、
共享和无效状态。
? 记号 A／ B中,,—,表示空动作； Flush动作表
示由高速缓存来提供请求块到总线上。有些弧线
上有多个记号，表示这些事件引起相同的状态转
换。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 3.从状态转换图可以看出的转换,
? 当一个处理器读一个无效块时，高速缓存控制器就通
过产生一个 BusRd事务来得到该块，并且该块状态变
为 S状态；
? 当写一个共享或者无效块时，就通过产生一个 BusRdX
事务来得到该块的互斥拥有权，并将该块状态置为 M；
? 如果高速缓存控制器在总线上观察到一个 BusRd事务，
并且该事务请求的块在本地高速缓存中处于 M状态，
则将该块内容放到总线上 (Flush)，同时将该块状态
置为 S态
? 如果在总线上观察到 BusRdX事务，并且所请求的块在
本地高速缓存处于 S状态，则只要简单将该块置为 I状
态；
? 如果在本地高速缓存中处于 M状态，则要将该块内容
放到总线上 (Flush)，然后将该块状态置为 I状态。
哈尔滨工业大学计算机科学与技术学院
?4.例题
? 具体的一个状态转换的例子可看下表，显示了
在下图的例子中采用 MSI协议时，所产生的总线
事务和内存块状态的转换情况。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 一个状态转换的例子一览表
处理器
动作
P1中
状态
P2中
状态
P3中状
态
总线事务 数据提供者
Pl读 u S —— —— BusRd 主存
P3读 u S —— S BusRd 主存
P3写 u I —— M BusRdX 主存
P1读 u S —— S BusRd P3高速缓存
P2读 u S S S BusRd 主存
哈尔滨工业大学计算机科学与技术学院
?六,MESI监听协议
?1.前言
?MESI属于写无效协议。它根据所
有的读、写、命中或不命中，与
在总线上监听的事件来跟踪高速
缓存行的状态。
哈尔滨工业大学计算机科学与技术学院
? MESI(ModifiedExclusiveShared lnvalid)
协议是 MSI协议的改进协议。
? 这个协议最初是由在 Urbana— Champaign
的 Illinois大学的研究者提出的，所以也
称为 Illinois协议。
哈尔滨工业大学计算机科学与技术学院
? 许多现代微处理器设计中已经实现了 MESI
协议，例如 Intel Pentium,i860、
PowerPC 601等。
? 与 MSI协议相比,MESI协议增加了一个互
斥 (E)状态。
? 小规模的 SMP机器的一类主要的工作负载是顺
序程序，假如采用 MSI协议，当一个顺序程序
先读人一个数据项，然后修改一个数据项时，
就要产生两个总线事务,
哈尔滨工业大学计算机科学与技术学院
? ① 一个 BusRd事务，用来得到内存块，并
置为 S状态 产生一个 BusRdX事务，用来将该块
状态从 S变为 M状态。而在顺序程序中数据项不
存在共享者，因此只会在一个高速缓存有该块
拷贝,
? ② 后一个 BusRdX事务是不必要的。为了改进这
种情况,加入了一个 E状态,用来表示只有一个
高速缓存中有这个内存块，且该块内容没有被
修改过。
? 只要开始发出 BusRd事务，得到内存块，并置为 E状
态，就可以直接进行修改，而不需要产生 BusRdX事
务。
哈尔滨工业大学计算机科学与技术学院
?MESI协议由四个状态组成,
? 修改过 (M)(或称为脏状态 )、互斥干净
(E)、共享 (S)和无效。
? 其中,M和 I状态和 MSI协议中意思是相同
的；
?E状态表示只有一个高速缓存中有这个内
存块，且该块内容没有被修改过
? 主存中是最新的
? 共享状态表示有两个或者更多高速缓存
中有该块拷贝。
哈尔滨工业大学计算机科学与技术学院
? MESI协议对总线信号有一些新要求。
? 在产生 BusRd事务并装入内存块时，高速缓存控
制器要知道别的高速缓存中是否存在该块的拷贝，
来决定将该块置为 S状态还是 E状态。
? 这就需要总线提供一个额外的共享 (S)信号线。
在总线事务的地址阶段，所有的高速缓存都要
检查是否含有请求块的拷贝，若有，则置位共
享信号线。
? 发出总线事务的高速缓存控制器，只要检查一
下共享信号线，就能判断出是否有别的高速缓
存中存在该块拷贝，以此决定该块装入后置为
S状态还是 E状态。
哈尔滨工业大学计算机科学与技术学院
? 在 S状态下，如果发生一个处理器写，由于该
高速缓存已经有最新的拷贝了，因此不需要
获得数据，这时可以采用一个新的总线事
务 —— 总线升级 (BusUpgr)，然后转换到 M状
态。
? 所有其他的高速缓存侦听到该事务，将其相
关的拷贝置为无效状态
? 不同点在于总线升级事务不需要数据响应，
也就不会导致实际的数据传输，主存或其他
的高速缓存不需要提供数据。
哈尔滨工业大学计算机科学与技术学院
? 2．状态转换
? 下图所示是 MESI协议的状态转换图。图中的记号与 MSI
状态转换图相似，具体的协议转换也与 MSI协议类似。
? 若在无效状态 I下有处理器读 (PrRd)发生，则根据 S
线是否被置位，来决定是转换到 E状态还是 S状态，
若置位则转换到 S状态，否则转换到 E状态，其中
BusRd(S)表示在 BusRd事务中 S线被置位。
? 在 E状态下，若发生处理器写 (PrWr)，将导致由 E状
态转换到 M状态，不产生总线事务；若观察到一个总
线读 (BusRd)事务，将导致由 E状态转换到 S状态，同
时由该高速缓存提供数据；若观察到一个总线互斥
读 (BusRdX)事务，将导致由 E状态转换到 I状态，同
时由该高速缓存提供数据。其他状态转换与 MSI协议
类似。
哈尔滨工业大学计算机科学与技术学院
? 还有一个不同点在于当高速缓存和主存中都有
最新数据时由谁来提供数据。在 S状态下，若
观察到一个总线读 (BusRd)事务或总线互斥读
(BusRdX)事务，在进行状态转换的同时，在
MSI协议中由主存提供数据，而在 MESI中由处
于 S状态下的某一个高速缓存提供数据，其他
的高速缓存不产生动作。
? 这一点在协议设计时可酌情处理。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?七、四态写回更新 (Dragon)协
议
1,Dragon协议
? 现在来看一个基于写回高速缓存的写更新协议，
也称为 Dragon协议。
哈尔滨工业大学计算机科学与技术学院
?Dragon协议有四种状态,
? (1)互斥且干净 E(Exclusive— Clean)：用
来表示仅有一个缓存 (本缓存 )拥有 该块的
拷贝，并且没有被修改过，也就是说，主
存中是最新的。
? (2)共享且干净 SC(Shared— Clean)：用来
表示可能有两个或更多缓存中拥有该块，
并且主存中可能是,也可能不是最新的。
哈尔滨工业大学计算机科学与技术学院
? (3)共享且修改过 SM(Shared— Modified)
? 用来表示可能 有两个或更多缓存中拥有该块，
且主存中不是最新的 。缓存应当负责当该块
由缓存中被替换出时，更新主存中的数据。
在某个时刻，一个块只可能在一个缓存中处
于 SM状态。然而，一个块在某个缓存中处于
SM状态，而在另一个缓存中处于 SC状态是可
以的。或者，一个块在任何缓存中都不处于
SM状态，而在某些缓存中处于 SC状态。这就
是为什么缓存中的块处于 SC状态，而主存中
却可能是也可能不是最新的，这依赖于是否
在某个缓存中该块处于 SM状态。
哈尔滨工业大学计算机科学与技术学院
? （ 4)修改过 M(Modified)
? 用来表示该块仅在该缓存中处于被修改过 (脏
状态 )，主存中已经过时。缓存负责在该块被
替换出来时更新主存。
? 注意到与前面的协议不同，这里没有显式
的无效状态。这是因为 Dragon是基于更新
的协议，在该协议中，缓存中的块总是最
新的。
? 只要某块在缓存中，该块总是有效的。然
而，对于不在缓存中的块，可以想像为一
种特殊的无效状态。
哈尔滨工业大学计算机科学与技术学院
? Dragon协议中的处理器请求、总线事务和动
作，与在 MESI协议中的相似。
? 先来看一下处理器请求。假设处理器还是
只发出读 (PrRd)和写 (PrWr)请求。但由于
本协议中不存在无效状态，为了表达出处
理器第一次请求一个新内存块这个动作，
增加了处理器读缺失 (PrRdMiss)和处理器
写缺失 (PrWrMiss)两种处理器请求。
哈尔滨工业大学计算机科学与技术学院
? 总线事务,
? 有总线读 (BusRd)、总线写回 (BusWB)和总线更
新 (BusUpd)事务。 BusUpd事务将处理器所写的
内容在总线上进行广播，使得所有其他的高速
缓存都能进行更新。通过只广播修改过的内容，
而不是整个内存块，可以更充分利用总线带宽。
? 为了支持 E状态，与 MESI协议一样，也需要一个
共享信号。另外，高速缓存控制器还要一个新
动作，就是根据总线上出现的 BusUpd事务，来
更新高速缓存中的相应块的内容。
哈尔滨工业大学计算机科学与技术学院
? 2．状态转换
? 状态转换图如下图所示。下面就分别描述一下，
当发生读高速缓存缺失、执行写操作以及高速
缓存块被替换出去时，所发生的一系列动作。
? (1)读缺失 (ReadMiss) 产生一个 BusRd事务。
根据共享信号 (S)的状态，决定该块被装入本
地高速缓存后，是处于 E状态，还是 SC状态。
? (2)写 (Write) 如果所写的块在本地高速缓存
中处于 M状态，就不需要执行任何动作。如果
该块在本地高速缓存中处于 E状态，则直接将 E
状态改为 M状态，也不需要再执行什么动作。
哈尔滨工业大学计算机科学与技术学院
? 如果该块处于 SC或 SM状态，则要产生一个总
线更新 (BusUpd)事务更新 (BusUpd)事务
? 其他任何有该数据拷贝的高速缓存，都要置
位共享信号线，更新本地拷贝中对应的字节，
并且如果需要的话，要将状态变为 SC。
? 本地高速缓存根据共享信号线来决定状态转
换，同时更新该块的拷贝，如果共享信号线
被置位，则将它的状态变为 SM。如果共享信
号线未被置位，则表明没有其他的高速缓存
中含有该数据的拷贝，则将状态变为 M。主
存内容不被更新。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? (3)替换 (Replacement)
? 在发生替换时，只有被替换的块处于 M或
SM状态时，才需要用一个总线事务将其
写回到内存中。
? 如果被替换块处于 SC状态，则要么是其
他高速缓存中有该块的处于 SM状态的拷
贝，要么是主存中已经有最新的值了。
这两种情况下，都只要将该块丢弃即可。
哈尔滨工业大学计算机科学与技术学院
八、例,Pentium多处理机系统采用了
MESI协议
哈尔滨工业大学计算机科学与技术学院
?数据高速缓存中所有行总是处于
下述 4种状态之一,
?已修改 (modified,M)状态
?独占 (exclusive,E)状态
?共享 (shared,S)状态
?无效 (invalid,I)状态
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?1.写直达协议
?对于写直达高速缓存行而言，
初始状态为 I。
?上图的上部由 S和 I状态及其周
边粗虚线和实现组成的双状态
子图单独称为 WT高速缓存事件
的 SI协议 (S／ protocol)。
哈尔滨工业大学计算机科学与技术学院
? 2.回写式高速缓存
? 在 WB方式下，数据被载人某一高速缓存
后为 E状态，也就是说它是系统中唯一有
效的高速缓存拷贝。
? 对外部事件的监听工作相当简单,
① 所有的远程写 (remote write)使该
数据的其它高速缓存拷贝失效。
② 所有的远程读 (remote read)命中使
数据进入 S状态。
哈尔滨工业大学计算机科学与技术学院
?3.WB高速缓存的 MSI协议
?如果我们将 E状态并入 S状态，则
得到在 WB高速缓存下的 3状态 MSI
协议。
?从 MESI状态图中抽取出 MSI子图得
到以下 3种子图转换,
哈尔滨工业大学计算机科学与技术学院
?高速缓存行的唯一有效拷贝状态,
?系统中存在两个以上有效拷贝,
哈尔滨工业大学计算机科学与技术学院
? WT高速缓存的 SI协议
① 可以将 3状态 MSI协议进一步简化为
WT高速缓存下的二状态 SI协议。
② 如果取消高速缓存，则单状态协议
也是可能的。
③ 采用监听协议时，一致性协议的状
态多寡反映了它区分高速缓存行不
同共享状态的能力强弱。
哈尔滨工业大学计算机科学与技术学院
?九,本节总结
?一致性协议具有越多的状态，它
就能区分越多的高速缓存事件和
可能的状态转换。
?实现复杂的协议要付出实现效率
的代价。
