1、1第六章第六章 共享存储的多处理器共享存储的多处理器2第一节第一节 共享存储的一致性共享存储的一致性一、共享存储结构与一致性一、共享存储结构与一致性1 1、共享存储层次结构、共享存储层次结构P1Pn交换机交叉的高速缓存交叉的主存(a)共享缓存(b)集中式共享存储器P1存储器 C Pn C 存储器互连网络P1存储器 C (c)分布式共享存储器互连网络Pn存储器 C 共享缓存集中共享分布共享处理机数8301000限制交换机的延迟结点间间距和延迟数据局部性 目标：目标：减少平均数据访问时间，减少通信带宽。减少平均数据访问时间，减少通信带宽。32 2、一致性问题、一致性问题 包括包括CacheCach
2、e一致性、存储一致性两部分。一致性、存储一致性两部分。（1 1）CacheCache一致性一致性 指私有指私有CacheCache中共享数据的副本和共享存储器中共享数据之中共享数据的副本和共享存储器中共享数据之间的一致性。间的一致性。特征：特征：多处理器对相同存储单元的操作引起的一致性。多处理器对相同存储单元的操作引起的一致性。u:7u:?u:?P1 C u:5 u:5主存 P2 C u:5P3 C u:54（2 2）存储一致性）存储一致性 指多个处理器程序的执行次序与共享存储器中共享数据存指多个处理器程序的执行次序与共享存储器中共享数据存取次序之间的一致性。取次序之间的一致性。特征：特征：不
3、同处理器对不同存储单元的操作引起的一致性。不同处理器对不同存储单元的操作引起的一致性。a.A:=1b.print B,Cc.B:=1d.print A,Ce.C:=1f.print A,BA、B、C为共享变量(初始状态均为0)处理器1处理器2处理器3共享存储器 思考：思考：如何使存取次序的结果与执行次序的结果相同？如何使存取次序的结果与执行次序的结果相同？5（3 3）存储系统的一致性）存储系统的一致性 将对任何存储单元的操作排成一个全序，此序列与执行结将对任何存储单元的操作排成一个全序，此序列与执行结果一致，并且序列具有下列性质时，称存储系统是一致的：果一致，并且序列具有下列性质时，称存储系统
4、是一致的：1 1）任何进程）任何进程发出发出的操作所表现出来的序和该进程向存储的操作所表现出来的序和该进程向存储系统发出的序相同；系统发出的序相同；2 2）每个读操作返回的值是对相应单元的读操作前按串行）每个读操作返回的值是对相应单元的读操作前按串行顺序写入的最后的一个值。顺序写入的最后的一个值。一致性隐含性质：一致性隐含性质：写传播写传播写操作的效果对其他进程可见；写操作的效果对其他进程可见；写串行化写串行化所有进程以相同的顺序看到对所有进程以相同的顺序看到对某单元某单元的所的所有写操作。有写操作。思考：思考：为什么读不需要传播？为什么读不需要传播？63 3、原子性操作、原子性操作 具有下列
5、全部性质的操作称为原子操作：具有下列全部性质的操作称为原子操作：原子性：原子性：一个事务操作具有不可分和有限时间完成两个一个事务操作具有不可分和有限时间完成两个特性；特性；一致性：一致性：一个事务总是将程序由一个一致性状态转换成一个事务总是将程序由一个一致性状态转换成另一个一致性状态；另一个一致性状态；隔离性：隔离性：在一个事务完成前，该事务操作的效果不会对在一个事务完成前，该事务操作的效果不会对其他事务产生影响；其他事务产生影响；持续性：持续性：一旦事务完成，当系统失效时，事务操作的效一旦事务完成，当系统失效时，事务操作的效果仍会持续。果仍会持续。7 写操作串行化与写操作原子性：写操作串行化
6、与写操作原子性：写操作串行化：写操作串行化：是针对相同单元写操作的偏序。是针对相同单元写操作的偏序。P0：P1：RRW1W2W1W1W2R2R3 写操作原子性：写操作原子性：是针对所有单元写操作的全序。是针对所有单元写操作的全序。P0：P1：RRW1W2W1W1W2R2R3 写操作原子性扩充了写操作串行化。写操作原子性扩充了写操作串行化。8二、二、Cache一致性一致性1 1、CacheCache更新主存方法更新主存方法 写直达法：写直达法：处理器写处理器写CacheCache时，同时写主存；时，同时写主存；写回法：写回法：等到某等到某CacheCache块被替换时，才写主存。块被替换时，才写
7、主存。2 2、不一致性原因、不一致性原因 不同处理器对相同单元在各自不同处理器对相同单元在各自CacheCache的拷贝的异步写操作；的拷贝的异步写操作；多处理器中的进程迁移，而又不互相通报；多处理器中的进程迁移，而又不互相通报；绕过绕过CacheCache拷贝拥有者的拷贝拥有者的I/OI/O操作。操作。3 3、CacheCache一致性解决方法一致性解决方法 前两种原因：前两种原因：监听法（基于处理器间总线互连时）、监听法（基于处理器间总线互连时）、目录法（基于处理器间总线或网络互连时）。目录法（基于处理器间总线或网络互连时）。第三种原因：第三种原因：禁止法、刷新法。禁止法、刷新法。94 4
8、、总线监听一致性协议、总线监听一致性协议 思路：思路：利用总线监听一致性定义中的写传播信息实现。利用总线监听一致性定义中的写传播信息实现。总线事务：总线事务：由仲裁、命令由仲裁、命令/地址、数据三个阶段组成，总线地址、数据三个阶段组成，总线事务应具有顺序性和原子性。事务应具有顺序性和原子性。块状态：块状态：指示数据块的特征（无效、脏、共享、独占）。指示数据块的特征（无效、脏、共享、独占）。监听协议：监听协议：控制控制CacheCache块状态变化的策略，是一种分布式算块状态变化的策略，是一种分布式算法，可用状态转换图表示。法，可用状态转换图表示。策略：策略：基于作废、基于更新。基于作废、基于更
9、新。5 5、目录一致性协议、目录一致性协议 思路：思路：在每个共享存储器上建立一个目录，记录使用该数在每个共享存储器上建立一个目录，记录使用该数据的所有处理器信息和数据状态信息，处理器可根据这些信息据的所有处理器信息和数据状态信息，处理器可根据这些信息实现各实现各CacheCache的一致性。的一致性。106 6、I/OI/O操作与操作与CacheCache的一致性的一致性 禁止方法：禁止方法：存储空间中的某些段不允许进入存储空间中的某些段不允许进入CacheCache。刷新方法：刷新方法：操作系统在操作系统在I/OI/O操作前，将有关的段先从操作前，将有关的段先从CacheCache刷新过刷
10、新过来，然后再进行来，然后再进行I/OI/O操作。操作。11三、存储一致性三、存储一致性1 1、顺序一致性（、顺序一致性（SCSC）定义：定义：满足下列特性的多处理机系统是顺序一致的：满足下列特性的多处理机系统是顺序一致的：所有的执行结果都和所有处理器按某一顺序序列执行的所有的执行结果都和所有处理器按某一顺序序列执行的结果一致；结果一致；并且在该顺序序列中各处理器的并且在该顺序序列中各处理器的执行次序执行次序和它的和它的程序次程序次序序一致。一致。保证顺序一致性的充分条件：保证顺序一致性的充分条件：每个进程按照程序的执行次序发出存储操作；每个进程按照程序的执行次序发出存储操作；完成写操作前，进
11、程等待在此之前所有全局的写操作的完成写操作前，进程等待在此之前所有全局的写操作的完成；完成；完成读操作前，进程等待在此之前所有全局的读操作和完成读操作前，进程等待在此之前所有全局的读操作和写操作的完成。写操作的完成。12 顺序一致性的特征：顺序一致性的特征：某某PEPE取操作的结果为其他取操作的结果为其他PEPE对该单元最新存操作的结果；对该单元最新存操作的结果；存储次序与存储次序与全部操作对全部操作对的二元次序相一致；的二元次序相一致；在一个特定程序次序中出现的两个在一个特定程序次序中出现的两个操作操作，一定出现在同，一定出现在同一存储次序中；一存储次序中；对其他存操作而言，交换操作是原子操
12、作；对其他存操作而言，交换操作是原子操作；所有存和交换操作必须完整地结束。所有存和交换操作必须完整地结束。P0：RRW1W1W2P1：W2W1R2SSR3R2 顺序一致性对串行程序的影响：顺序一致性对串行程序的影响：编译器的各种优化编译技术要保证不改变存储操作次序；编译器的各种优化编译技术要保证不改变存储操作次序；系统结构的优化要保证不改变存储操作次序。系统结构的优化要保证不改变存储操作次序。132 2、弱一致性（、弱一致性（WCWC）定义：定义：满足下列条件的多处理机系统是弱一致的：满足下列条件的多处理机系统是弱一致的：在允许其他任何处理器的读写访问前，必须先完成所有在允许其他任何处理器的读
13、写访问前，必须先完成所有的同步访问；的同步访问；在允许其他任何处理器的同步访问前，必须先完成所有在允许其他任何处理器的同步访问前，必须先完成所有的读写访问；的读写访问；各同步访问之间满足各同步访问之间满足顺序一致性顺序一致性。P0：RRW1W1W2P1：W2W1R2SSR3R2 弱一致性对串行程序的影响：弱一致性对串行程序的影响：同步点间的不同地址的读写操作不需要遵循程序次序。同步点间的不同地址的读写操作不需要遵循程序次序。14 弱一致性应用：弱一致性应用：可将存储器的访问进行缓冲，提高共享存储器的性能；可将存储器的访问进行缓冲，提高共享存储器的性能；可根据对存储器访问次序的不同限制，定义各种
14、不同的可根据对存储器访问次序的不同限制，定义各种不同的弱存储器模型。弱存储器模型。TSO TSO弱一致性模型的特征：弱一致性模型的特征：（全部存次序弱一致性）（全部存次序弱一致性）某某PEPE取操作的结果为其他取操作的结果为其他PEPE对该单元最新存操作的结果；对该单元最新存操作的结果；存储次序与存储次序与存操作对存操作对的二元次序相一致；的二元次序相一致；在一个特定程序次序中出现的两个在一个特定程序次序中出现的两个存操作存操作，一定出现在，一定出现在同一存储次序中；同一存储次序中；对其他存操作而言，交换操作是原子操作；对其他存操作而言，交换操作是原子操作；所有存和交换操作必须完整地结束。所有
15、存和交换操作必须完整地结束。153 3、处理器一致性（、处理器一致性（PCPC）定义：定义：满足下列条件的多处理机系统是处理器一致的：满足下列条件的多处理机系统是处理器一致的：相关于其他任一处理器而言，进行某读操作前，必须先相关于其他任一处理器而言，进行某读操作前，必须先完成之前所有的读操作；完成之前所有的读操作；相关于其他任一处理器而言，进行某写操作前，必须先相关于其他任一处理器而言，进行某写操作前，必须先完成之前所有的读和写操作。完成之前所有的读和写操作。P0：RRW1W1W2P1：W2W1R2SSR3R2 处理器一致性对串行程序的影响：处理器一致性对串行程序的影响：不同地址的写操作后的读
16、操作可越过写操作进行访问。不同地址的写操作后的读操作可越过写操作进行访问。处理器一致性应用：处理器一致性应用：可实现存储器的访问缓冲和流水操作。可实现存储器的访问缓冲和流水操作。164 4、释放一致性（、释放一致性（RCRC）定义：定义：满足下列条件的多处理机系统是释放一致的：满足下列条件的多处理机系统是释放一致的：相关于其他任一处理器而言，在进行读写操作之前，必相关于其他任一处理器而言，在进行读写操作之前，必须先完成之前所有的获得操作；须先完成之前所有的获得操作；相关于其他任一处理器而言，在进行释放操作之前，必相关于其他任一处理器而言，在进行释放操作之前，必须先完成之前所有的读写操作；须先完
17、成之前所有的读写操作；所有的特殊操作（获得和释放）之间满足所有的特殊操作（获得和释放）之间满足处理机一致性处理机一致性。P0：RW1W2P1：W2R1R2SA1SR1SA1SR1RR3R1P0：RW1W2P1：W2R1R2SA1SR1SA2SR2RR3R1175 5、存储一致性模型比较、存储一致性模型比较顺序一致性（顺序一致性（SC）任何执行结果认为是在多线程顺序机器上各操作交错执行的结果处理机一致性（处理机一致性（PC）每台处理机发出的写操作顺序不会乱，但两台处理机发出的写操作顺序可能会不一样弱一致性（弱一致性（WC）程序员利用同步操作确保顺序一致性释放一致性（释放一致性（RC）具有获得和释
18、放两类同步操作的弱一致性，每类操作保证处理机一致性强模型非严格模型18 顺序一致性模型与非严格一致性模型比较：顺序一致性模型与非严格一致性模型比较：主要在对共享地址的写主要在对共享地址的写-读、写读、写-写、读写、读-读、读读、读-写操作写操作间的次序要求不同；间的次序要求不同；非严格一致性模型能够提供比顺序一致性模型更优的性非严格一致性模型能够提供比顺序一致性模型更优的性能。能。非严格存储一致性与非严格存储一致性与CacheCache一致性的关系：一致性的关系：CacheCache一致性提供了传播写入新值的机制，存储一致性一致性提供了传播写入新值的机制，存储一致性提供了何时传播写入值的附加机
19、制；提供了何时传播写入值的附加机制；CacheCache一致性过程是非原子性的操作，存储一致性的读一致性过程是非原子性的操作，存储一致性的读写和交换操作是原子性的。写和交换操作是原子性的。19第二节第二节 基于监听的基于监听的CacheCache一致性协议一致性协议 Cache Cache更新策略：更新策略：写策略：写直达法、写回法；写策略：写直达法、写回法；写丢失分配策略：不按写分配方法、按写分配方法。写丢失分配策略：不按写分配方法、按写分配方法。Cache Cache块状态：块状态：写直达法更新策略中的块只有两种状态（有效态、无效写直达法更新策略中的块只有两种状态（有效态、无效态）；态）；
20、写回法更新策略的块可有三种或四种状态（共享态、专有写回法更新策略的块可有三种或四种状态（共享态、专有态、修改态、无效态）。态、修改态、无效态）。写直达法一般与不按写分配方法配对；写直达法一般与不按写分配方法配对；写回法一般与按写分配方法配对。写回法一般与按写分配方法配对。20 Cache Cache块状态：块状态：有效态有效态(V)V)：此块与主存相同此块与主存相同(干净块干净块)；无效态无效态(I)I)：此块已作废此块已作废(空块空块)。一、一、VI写直达协议写直达协议 处理器操作：处理器操作：PrRdPrRd、PrWrPrWr。总线操作：总线操作：BusRdBusRd、BusWrBusWr
21、。状态转换图：状态转换图：VIPrWr/BusWrPrRd/-PrWr/BusWrPrRd/BusRdBusWr/-BusRd/-BusWr/-BusRd/-处理器启动的事务总线启动的事务说明：说明：A/B表示若A事务被观察到，则生成B事务。BusRd的结果由主存提供。21二、二、MSI写回作废式协议写回作废式协议1 1、状态转换图、状态转换图 Cache Cache块状态：块状态：修改态修改态(M)M)：此块与主存不相同此块与主存不相同(脏块脏块)，同一块的修改，同一块的修改态最多只在一个态最多只在一个CacheCache中存在；中存在；共享态共享态(S)S)：此块与主存相同此块与主存相同(
22、干净块干净块)，同一块的共享，同一块的共享态可在多个态可在多个CacheCache中存在；中存在；无效态无效态(I)I)：此块已作废此块已作废(空块空块)。转下二页 Cache Cache块拥有者：块拥有者：块状态为块状态为M M态的态的CacheCache是该块的拥有者，否则主存是该块是该块的拥有者，否则主存是该块的拥有者。的拥有者。块的拥有者负责提供对该块的访问请求。块的拥有者负责提供对该块的访问请求。22 处理器操作：处理器操作：PrRdPrRdI I态产生扑空，态产生扑空，I I态导致总线操作；态导致总线操作；PrWrPrWrI I态产生扑空，态产生扑空，S/IS/I态导致总线操作（先
23、态导致总线操作（先排他读数排他读数据，然后改变状态并在新状态据，然后改变状态并在新状态M下写数据下写数据）。）。总线操作（事务）：总线操作（事务）：BusRdBusRd由扑空的由扑空的PrRdPrRd产生，由存储系统（可为其他的产生，由存储系统（可为其他的CacheCache）提供数据，其他）提供数据，其他CacheCache相应块（读监听命中）有效；相应块（读监听命中）有效；BusRdXBusRdX由由PrWrPrWr产生，由存储系统（可为其他的产生，由存储系统（可为其他的CacheCache）提供数据，其他提供数据，其他CacheCache相应块（排他读相应块（排他读/写监听命中）作废；写
24、监听命中）作废；转下页 BusWBBusWB-由替换动作产生，处理器观察不到，由由替换动作产生，处理器观察不到，由CacheCache提提供数据，主存被更新。供数据，主存被更新。23 状态转换图：状态转换图：返回上二页返回上页返回下页返回下二页PrWr/-PrRd/-PrRd/-MIPrRd/BusRdS 说明：说明：虚线均为监听命中的响应；S态产生的BusRdX不需要数据，I态产生的BusRdX需要块数据。PrWr/(BusRdX+newPrWr)PrWr/(BusRdX+newPrWr)BusRd/-BusRd/FlushBusRd/-BusRdX/-BusRdX/FlushBusRdX/
25、-CaInvd/BusWBCaInvd/-24 替换操作：替换操作：由逻辑上由逻辑上I I态（不存在）的块的态（不存在）的块的PrRdPrRd或或PrWrPrWr操作产生，此操作产生，此时时CacheCache中无中无I I态的块存在。态的块存在。分两个步骤完成替换操作：对被替换的块进行分两个步骤完成替换操作：对被替换的块进行CaInvdCaInvd操操作、对新调进的块（作、对新调进的块（I I态）进行态）进行PrRdPrRd或或PrWrPrWr操作。操作。被替换的块被替换的块M M态时产生态时产生BusWBBusWB操作，其他态无总线操作。操作，其他态无总线操作。新调进的块新调进的块按操作类
26、型，产生相应的总线操作，该块按操作类型，产生相应的总线操作，该块从从I I态变为态变为S S态或态或M M态。态。转上页25 思考思考1 1：为何为何I I态块的态块的PrWrPrWr操作，需要先取得整块数据？操作，需要先取得整块数据？思考思考2 2：某某CacheCache控制器进行控制器进行BusRdBusRd操作时，其他块为操作时，其他块为M M态态的的CacheCache控制器如何能替代主存提供数据？控制器如何能替代主存提供数据？思考思考3 3：块为块为M M态的态的CacheCache控制器如何优先控制器如何优先BusRdXBusRdX操作更新操作更新数据到主存？数据到主存？协议的优
27、化：协议的优化：M M态态BusRdBusRd监听命中时，采用监听命中时，采用M-SM-S非非M-IM-I，使原，使原M M态的处态的处理器可继续使用该块；理器可继续使用该块；S-M S-M的的BusRdXBusRdX采用采用BusUpgrBusUpgr（新增加的总线事务），减（新增加的总线事务），减少总线流量；少总线流量；转上二页 增加一种状态增加一种状态E E，使，使S S态的拷贝只有一个时的操作不产生态的拷贝只有一个时的操作不产生总线操作事务。总线操作事务。262 2、对一致性的保证、对一致性的保证 一致性包含写传播和写串行化两方面。一致性包含写传播和写串行化两方面。写传播保证：写传播保
28、证：发生写操作的发生写操作的CacheCache为该块唯一的拥有者，其他为该块唯一的拥有者，其他CacheCache该该块的状态变为块的状态变为I I态，态，M M态连续写状态不变，后续对该块的访问均态连续写状态不变，后续对该块的访问均由拥有者提供数据，故写操作的效果对任何进程都是可见的。由拥有者提供数据，故写操作的效果对任何进程都是可见的。写串行化保证：写串行化保证：排他读保证了该排他读保证了该CacheCache有该块唯一的拷贝，改变状态后成有该块唯一的拷贝，改变状态后成为拥有者，紧跟的写操作发生在为拥有者，紧跟的写操作发生在CacheCache控制器处理其他总线事务控制器处理其他总线事务
29、之前，该存储次序和访问次序对所有处理器是相同的；之前，该存储次序和访问次序对所有处理器是相同的；同时两个写操作，只有一个同时两个写操作，只有一个CacheCache命中（先完成排他读的命中（先完成排他读的那个），然后为另一个，后续访问的总线请求在第二个写之后那个），然后为另一个，后续访问的总线请求在第二个写之后响应，该存储次序与程序次序相同。响应，该存储次序与程序次序相同。273 3、对顺序一致性的保证、对顺序一致性的保证 从定义看：从定义看：总线串行仲裁定义了针对所有存储块（不只是某个块）总线串行仲裁定义了针对所有存储块（不只是某个块）的总线事务的全序。的总线事务的全序。处理器的执行次序与某
30、程序次序（总线存储次序）一致。处理器的执行次序与某程序次序（总线存储次序）一致。从充分条件看：从充分条件看：总线串行仲裁保证一个写操作完成前另一个写操作的排总线串行仲裁保证一个写操作完成前另一个写操作的排他读得不到总线不响应。他读得不到总线不响应。全局的该读操作前的写操作和读操作的完成由总线串行全局的该读操作前的写操作和读操作的完成由总线串行仲裁保证；相同处理器内的读操作前的写和读操作的完成，由仲裁保证；相同处理器内的读操作前的写和读操作的完成，由程序执行次序保证。程序执行次序保证。28三、三、MESI写回作废式协议写回作废式协议 Cache Cache块状态：块状态：修改态修改态(M)M)：
31、此块与主存不相同此块与主存不相同(脏块脏块)，同一块的拷贝，同一块的拷贝最多只在一个最多只在一个CacheCache中存在；中存在；独占态独占态(E)E)：此块与主存相同此块与主存相同(干净块干净块)，同一块的拷贝，同一块的拷贝只在一个只在一个CacheCache中存在；中存在；共享态共享态(S)S)：此块与主存相同此块与主存相同(干净块干净块)，同一块的拷贝，同一块的拷贝可在多个可在多个CacheCache中存在；中存在；无效态无效态(I)I)：此块已作废此块已作废(空块空块)。29 处理器操作：处理器操作：PrRdPrRdI I态产生扑空，态产生扑空，I I态导致态导致BusRdBusRd
32、操作，状态变为操作，状态变为E E或或S S态（根据块拷贝的唯一性决定）；态（根据块拷贝的唯一性决定）；PrWrPrWrI I态产生扑空，态产生扑空，S/IS/I态导致态导致BusRdXBusRdX操作操作，E/S/IE/S/I态态变为变为M态后在新状态态后在新状态M下写数据下写数据。转下页 总线操作：总线操作：BusRdBusRd由扑空的由扑空的PrRdPrRd产生，由存储系统（可为其他的产生，由存储系统（可为其他的CacheCache）提供数据，其他）提供数据，其他CacheCache相应块（读监听命中）返回监听相应块（读监听命中）返回监听命中指示信号，数据块有效命中指示信号，数据块有效；
33、BusRdXBusRdX由由PrWrPrWr产生，由存储系统（可为其他的产生，由存储系统（可为其他的CacheCache）提供数据，其他提供数据，其他CacheCache相应块（排他读相应块（排他读/写监听命中）作废；写监听命中）作废；BusWBBusWB与与MSIMSI协议相同。协议相同。替换操作：替换操作：与与MSIMSI协议相同。协议相同。30 状态转换图：状态转换图：PrWr/-PrRd/-PrRd/-MIPrRd/BusRd(S#)SEPrRd/-PrRd/BusRd(S)PrWr/-PrWr/BusRdXPrWr/BusRdX说明：说明：PrWr操作除图中标出的总线操作外，还有ne
34、wPrWr操作；M/E/S的BusRd监听命中时，向总线发监听命中指示信号。BusRd/-BusRd/FlushBusRd/-BusRdX/FlushBusRdX/-BusRdX/-返回上页CaInvd/BusWBCaInvd/-CaInvd/-31四、四、Dragon写回更新式协议写回更新式协议1 1、状态转换图、状态转换图 Cache Cache块状态：块状态：干净的独占态干净的独占态(E)E)：此块与主存相同此块与主存相同(干净块干净块)，该存储块，该存储块的拷贝只在一个的拷贝只在一个CacheCache中存在；中存在；干净的共享态干净的共享态(Sc)Sc)：此块与主存可能相同，该存储块
35、可此块与主存可能相同，该存储块可在多个在多个CacheCache中存在；中存在；共享已修改态共享已修改态(SmSm)：此块与主存不相同此块与主存不相同(脏块脏块)，该存储，该存储块可在多个块可在多个CacheCache中存在，但中存在，但SmSm状态只在一个状态只在一个CacheCache中存在；中存在；修改态修改态(M)M)：此块与主存不相同此块与主存不相同(脏块脏块)，该存储块及，该存储块及M M状状态只在一个态只在一个CacheCache中存在。中存在。32 处理器操作：处理器操作：PrRdPrRd均不产生总线操作，不改变状态；均不产生总线操作，不改变状态；PrRdMissPrRdMis
36、s由新块装入引起的扑空，产生由新块装入引起的扑空，产生BusRdBusRd操作操作，根，根据有无监听命中指示据有无监听命中指示(S)，块以，块以Sc态或态或E态装入态装入；PrWrPrWrSc/SmSc/Sm态产生态产生BusUpdBusUpd操作操作，根据有无监听命中指示，根据有无监听命中指示(S)，ScSc状态变为状态变为Sm或或M态，态，Sm状态变为状态变为Sm或或M态态；PrWrMissPrWrMiss由对新块写引起的扑空，首先产生由对新块写引起的扑空，首先产生BusRdBusRd操作操作，有监听命中指示有监听命中指示(S)时，时，块以块以Sm态装入，并产生态装入，并产生BusUpd操
37、作；操作；无监听命中指示时，块以无监听命中指示时，块以M态装入，并进行态装入，并进行PrWr操作操作。转下二页转下页33 状态转换图：状态转换图：返回上页返回下页PrRd/-PrRd/-PrWr/-EScMSmPrRd/-PrRd/-PrWr/BusUpd(S)PrRdMiss/BusRd(s#)PrRdMiss/BusRd(s)PrWr/BusUpd(S#)PrWr/-PrWr/BusUpd(S#)PrWr/BusUpd(S)PrWrMiss/(BusRd(s)+BusUpd)PrWrMiss/(BusRd(s#)+newPrWr)BusRd/FlushBusRd/-BusRd/-BusUp
38、d/UpdateBusRd/FlushBusUpd/UpdateCaInvd/BusWBCaInvd/BusWB34 总线操作：总线操作：BusRdBusRd由扑空的由扑空的PrRdPrRd或或PrWrPrWr产生，由存储系统（可为其产生，由存储系统（可为其他的他的CacheCache）提供数据，其他）提供数据，其他CacheCache相应块（读监听命中）返回相应块（读监听命中）返回监听命中指示信号监听命中指示信号；BusUpdBusUpd将块中修改的字广播到总线上，其他监听命中将块中修改的字广播到总线上，其他监听命中CacheCache的控制器根据总线内容更新该存储块的控制器根据总线内容更新
39、该存储块；BusWBBusWB与与MESIMESI协议相同。协议相同。替换操作：替换操作：被替换的块被替换的块SmSm/M/M态产生态产生BusWBBusWB操作，操作，E/ScE/Sc态无总线操作。态无总线操作。新调进的块新调进的块按操作扑空类型及监听命中指示信号，产按操作扑空类型及监听命中指示信号，产生相应的总线操作，该块可以生相应的总线操作，该块可以E/M/Sc/SmE/M/Sc/Sm态装入。态装入。转上页返回上二页352 2、更新、作废更新、作废一致性一致性协议协议比较比较 协议特性：协议特性：更新协议更新协议实现一对多共享及所有处理器共享数据写的实现一对多共享及所有处理器共享数据写的
40、次数少于访问的次数时性能较好；次数少于访问的次数时性能较好；作废协议作废协议-实现点对点共享及所有处理器共享数据写的实现点对点共享及所有处理器共享数据写的次数多于访问的次数时性能较好。次数多于访问的次数时性能较好。应用不确定性矛盾解决：应用不确定性矛盾解决：硬件上支持两种协议硬件上支持两种协议 a.a.由程序员决定对页或数据结构的协议，由程序员决定对页或数据结构的协议，b.b.运行时硬件自动根据使用情况选择；运行时硬件自动根据使用情况选择；混合协议混合协议更新协议中引入作废，给块一个计数器，每更新协议中引入作废，给块一个计数器，每收到更新减收到更新减1 1，使用时设置，计数到，使用时设置，计数
41、到0 0时作废该块；时作废该块；设置多级设置多级CacheCache不同层次采用不同类型协议。不同层次采用不同类型协议。36 协议评价：协议评价：扑空率扑空率更新协议、混合协议、作废协议递增，三者差更新协议、混合协议、作废协议递增，三者差别不太大；别不太大；升级升级/更新速率更新速率-更新协议、混合协议、作废协议递减，更新协议、混合协议、作废协议递减，三者差别较大，但更新的时延相对扑空时延不太重要；三者差别较大，但更新的时延相对扑空时延不太重要；流量流量-更新协议、混合协议、作废协议递减，三者差别更新协议、混合协议、作废协议递减，三者差别较大。较大。更新协议的使用越来越少，作废协议占主流。更新
42、协议的使用越来越少，作废协议占主流。37五、一致性协议设计中的折中五、一致性协议设计中的折中1 1、一致性协议的性能指标、一致性协议的性能指标 总线带宽需求、存储访问时延。总线带宽需求、存储访问时延。影响总线带宽需求的因素：影响总线带宽需求的因素：协议的总线流量、存储块的大小。协议的总线流量、存储块的大小。不同协议有不同的总线流量，需要不同的总线带宽。不同协议有不同的总线流量，需要不同的总线带宽。影响存储访问时延的因素：影响存储访问时延的因素：扑空率、存储块的大小。扑空率、存储块的大小。不同类型协议有不同的扑空率，存储块的大小也影响不同类型协议有不同的扑空率，存储块的大小也影响扑空率。扑空率。
43、382 2、协议的总线带宽需求、协议的总线带宽需求 协议的总线带宽计算方法：协议的总线带宽计算方法：（基于具体应用进行）（基于具体应用进行）统计应用中一定数量的访问操作所产生的协议的各种状统计应用中一定数量的访问操作所产生的协议的各种状态转换次数；态转换次数；将协议各种状态转换变换成各种总线事务；将协议各种状态转换变换成各种总线事务；将总线事务乘以每个事务的流量，得到地址和数据流量；将总线事务乘以每个事务的流量，得到地址和数据流量；根据应用中存储访问的频率，计算出每条指令流量；根据应用中存储访问的频率，计算出每条指令流量；将指令流量乘以假设的处理速度，得应用需要的总线地将指令流量乘以假设的处理
44、速度，得应用需要的总线地址和数据的带宽需求。址和数据的带宽需求。39 不同协议的带宽需求比较：不同协议的带宽需求比较：方法方法-选择一些具体的应用，在不同协议上运行；选择一些具体的应用，在不同协议上运行；统计出各种协议对应的总线流量；统计出各种协议对应的总线流量；对所得结果进行统计与分析。对所得结果进行统计与分析。条件条件对不同协议，假设对不同协议，假设CacheCache大小、块大小等相同。大小、块大小等相同。结论结论MESIMESI协议较协议较MSIMSI优化型协议略好，较优化型协议略好，较MSIMSI普通型好普通型好得多。得多。403 3、存储访问时延、存储访问时延 T T=HTHT1
45、1+(1-+(1-H H)T T2 2 H H与程序访问地址流、替换算法、更新策略、与程序访问地址流、替换算法、更新策略、CacheCache容量、容量、存储块大小等有关。存储块大小等有关。（1 1）CacheCache访问扑空类型访问扑空类型 冷启动扑空、容量扑空、冲突扑空、通信扑空。冷启动扑空、容量扑空、冲突扑空、通信扑空。冷启动扑空：冷启动扑空：通过增加块的大小来减小；通过增加块的大小来减小；容量扑空：容量扑空：通过增加通过增加CacheCache容量来减小；容量来减小；冲突扑空：冲突扑空：通过增加通过增加CacheCache的关联度来减小。的关联度来减小。通信扑空：通信扑空：分固有通信
46、扑空（真共享扑空）和附加通信分固有通信扑空（真共享扑空）和附加通信扑空（包含伪共享扑空）。扑空（包含伪共享扑空）。41 真共享扑空真共享扑空为固有通信引起的扑空，只能通过增加存为固有通信引起的扑空，只能通过增加存储块的大小和开发通信数据局部性减小；储块的大小和开发通信数据局部性减小；伪共享扑空伪共享扑空为附加通信引起的扑空，可通过减小存储为附加通信引起的扑空，可通过减小存储块的大小或通过软件块的大小或通过软件/硬件的优化来减小。硬件的优化来减小。（2 2）伪共享扑空的缓解方法）伪共享扑空的缓解方法 a.a.通过数据组织和任务分配缓解通过数据组织和任务分配缓解 减少访问模式的空间交叉、适当的数据
47、拷贝提高空间局减少访问模式的空间交叉、适当的数据拷贝提高空间局部性、数据不跨块边界。部性、数据不跨块边界。b.b.数据传送粒度与一致性粒度不一致数据传送粒度与一致性粒度不一致 将存储块分成几个子块，一致性粒度为子块大小。将存储块分成几个子块，一致性粒度为子块大小。c.c.集中几个操作的结果后保持一致性集中几个操作的结果后保持一致性 采用放松的存储一致性模型实现。采用放松的存储一致性模型实现。d.d.采用基于更新的一致性协议采用基于更新的一致性协议42（3 3）CacheCache块大小对扑空率和流量的影响块大小对扑空率和流量的影响 增加块的大小，可以减少扑空率（伪共享扑空除外）；增加块的大小，
48、可以减少扑空率（伪共享扑空除外）；增加块的大小，一般增加总线的流量（部分阶段会减小）；增加块的大小，一般增加总线的流量（部分阶段会减小）；总线流量到达一定数量时，严重影响系统的性能。总线流量到达一定数量时，严重影响系统的性能。434 4、CacheCache中总线带宽需求与存储块大小选择的折中中总线带宽需求与存储块大小选择的折中 在块大小在块大小-扑空率曲线中，选择认可的扑空率范围的块大小；扑空率曲线中，选择认可的扑空率范围的块大小；在块大小在块大小-流量曲线中，从上述所选的块大小范围内，选择流量曲线中，从上述所选的块大小范围内，选择流量相对较小的最大块大小。流量相对较小的最大块大小。（选择时
49、扑空率的优先级大于总线带宽的优先级）（选择时扑空率的优先级大于总线带宽的优先级）系统总线的带宽：系统总线的带宽：根据协议带宽需求的比较，选择使用根据协议带宽需求的比较，选择使用MESIMESI一致性协议；一致性协议；在块大小选定后，根据各种应用的总线带宽需求，选择在块大小选定后，根据各种应用的总线带宽需求，选择其需求最大值；其需求最大值；在此基础上扩充在此基础上扩充50%50%以上的带宽（应付突发的数据传输），以上的带宽（应付突发的数据传输），作为实际的系统总线带宽。作为实际的系统总线带宽。44第三节第三节 同步操作同步操作 同步操作：同步操作：互斥、点对点事件、全局事件。互斥、点对点事件、全
50、局事件。一、同步事件组成一、同步事件组成 组成：组成：获取方法、等待算法、释放方法。获取方法、等待算法、释放方法。等待算法：等待算法：忙等待、阻塞。忙等待、阻塞。应用应用-忙等待适合等待周期较短的场合，阻塞适合等忙等待适合等待周期较短的场合，阻塞适合等待周期较长的场合。待周期较长的场合。优化优化先采用忙等待，超过某时间阀值后转为阻塞。先采用忙等待，超过某时间阀值后转为阻塞。同步事件的实现：同步事件的实现：在基本硬件原语的基础上，用软件实现同步算法。在基本硬件原语的基础上，用软件实现同步算法。说明：本节的讨论均基于忙等待进行。说明：本节的讨论均基于忙等待进行。45二、互斥二、互斥1 1、硬件锁、
