6.823计算机系统结构 多处理机系统 习题集6 2002春 我强四建议，学生每三人分规一个小组合作完成作业。每阻月西要交一骨该习题复的答案。学生应 该在决定时问的课前灵交作业。为了便于评分，各种习题应该分黄，面且每个学生最许所在组编号必须填 号在每道习题后商（如果你更换了小相。请说明。我们会为修指定一个新的阳编号），一卫参考答案已经发 放，我们将不再接收作业，为了完成下面的习恩，可能需要位一找假设，请在你的答常中明曲地说用这线 假及。 间题1：同步 BenB1ddde正在开发一个基于D此3X的对称多处理机系领(sMP),为了实现同岁源适，Bn向DLX 15A中加入了如下指令. FXCH R2A(RI) 有2与MR1>+A中的内容互晚. Temp+-MI+A]:M[+A]-R2:R2+Temp LL R2AIRI) 链接装入，用M+A:R2-M[=+A then Cancel other processors' eTvM0n0n≤RI>+A,sR1>+A1-≤R2:R2+ 1eleR2+-0. 问题1A 用SC实现EXCH AaPk告诉Bn.他不表要C用指令，因为用LL和SC指李藏能将其实现，请用L和SC 猫令写一段代到，使其等价于EXCH2,0《民1) 凤题1B SC与SW sC暂令与SMP(督有无效Ce一置性协议)上的标准的SW西季相比，有顿外的开销吗？请解利 如何考心总拉用法及必频采取的提作。 问愿1.C 用山SC更好
6.823 计算机系统结构 多处理机系统 习题集 #6 2002 春 我们强烈建议，学生每三人分成一个小组合作完成作业。每组只需要交一份该习题集的答案。学生应 该在决定时间的课前提交作业。为了便于评分，各种习题应该分类，而且每个学生最终所在组编号必须填 写在每道习题后面（如果你更换了小组，请说明，我们会为你指定一个新的组编号）。一旦参考答案已经发 放，我们将不再接收作业。为了完成下面的习题，可能需要做一些假设，请在你的答案中明确地说明这些 假设。 问题 1：同步 Ben Bitdiddle 正在开发一个基于 DLX 的对称多处理机系统（SMP）。为了实现同步原语，Ben 向 DLX ISA 中加入了如下指令。 EXCH R2,A(R1) 将 R2 与 M[+A]中的内容互换。 Temp ← M[+A]; M[+A] ← R2; R2 ← Temp LL R2,A(R1) 链接装入。用 M[+A]中内容装载 R2，把内存地址+A 存 入特殊链接寄存器( Rlink ,不是 R31)。 Rlink ← +A; R2 ← M[+A]; SC A(R1),R2 有条件保存。检查内存地址是否被有效保存入链接寄存器。若是， 则将 R2 中内容写入 M[+A]并将 R2=1;否则不做内存存储且 R2=0. if = +A then Cancel other processors’ reservation on +A;M[+A] ← ; R2 ← 1;else R2 ← 0; 问题 1.A 用 LL/SC 实现 EXCH Alyssa P. Hacker 告诉 Ben ,他不需要 EXCH 指令，因为用 LL 和 SC 指令就能将其实现。请用 LL 和 SC 指令写一段代码，使其等价于 EXCH R2，0（R1） 问题 1.B SC 与 SW SC 指令与 SMP（带有无效 cache 一致性协议）上的标准的 SW 指令相比，有额外的开销吗？请解释 如何考虑总线用法及必须采取的操作。 问题 1.C 用 LL/SC 更好 1
观在思考如下一段代码，实现如倾肌制《在代码夏的开始。民1包含互斥体的内存地址)： AD2,R0,1 try: EXCH R20R1) BNEZ R2,try 如果你从XC2间取)处桶入称的代码，你将仍得到一个互序提作。然到，代码可能被改善，在 MP上运行得更好。用L和SC对新的加顾代码做一下修政。用山C代科显语交换有什么好处专 间题1.D 上下文切换 BC始m一组SMP程序超行在新表统上，当仅仅超行ob的一个程序时，一切工作良好， 然面。当同时话行地的2个成更多程序时，机器境拾出了错误结果。小y@告诉B:地认为与连拔寄存器 一起的山C在上下文切换时未是其正确的同步。 错险一个说明心y四履点的问圈情形，考虑这样一种情形：一台处理器运行几个任务，它们共享某一 存销区。.往意：一个必理B仅有一个楼寄存器(RIk): Bm做哪叁修政才能实现上下文切换时的正确同步： 问题2：监视Cache一致共享内存 在这一问题中，我门算限材一个用于写国e的无效一资性协权，这与sN线衡采用的相似 在大部分的无效协议中，任童时制仅有一个xe可以铜有一个ce行的一铃修改找具。然面。障免许 有干净数据的多份共享持贝外，修政数据的多份共享携贝也可能存在。《在这里，修数据指不月手于内存 的数据，当修改数据的多检共享携贝存在的时候，一个加用有数据的当前携项。有不是内存的，)任 何时候只要个新的值业《写)拷具被创健。所有的共享将见侧无效。 我们美心的MBu事务： ·一致读(CR)：读不命中时由一个cxhe传送，要象装入一个cahe行， ·一数读且无效(C)：写不命中后写分配时由一个k发出： ·一败无效《C)，当需要写一个处于共享找态的内存块时发生 ·块写(WR)在写日一个ce块时由一个ce传送。 ·一致写且无效(CW)在块写（任何时规的一整块）是由一个0处理机(DM4》发出 障了这牛恭本的总线事务外，还有： Cc间干CCh装用于在适当的时候，一个加为另外一个的对事务提供支持，一 个1干裤并强制内存正常给出的数据，与内存相关的，夏求快速响应的数据色夏用C1的悉式 提供数属，包是，只有包含数据的ce支持CCI方式的响应. 数压块可使的5种规态： ·无效：数暴块不存在于ee中， ·干净专有，Clan excushe(CE目ehe中的数据和内存中一发，包不存在于其他cac中. ·白己专有，esclusive (OE)hc中的数墨与内存中的不同，并且不存在于其他xhe中.当其他 ce请滚得列此数据的备督时，辑有数据的ce响请求，而不是内作响应请求。 干净其享ean shared(CS)数据一控缓存储存，是不会棱CU更政的。同一数据着干个CS备检和 量多一个O8盏份可以同时存在， 2
现在思考如下一段代码，实现加锁机制（在代码段的开始，R1 包含互斥体的内存地址）： ADDI R2，R0，#1 try： EXCH R2,0(R1) BNEZ R2,try 如果你从 EXCH R2,0(R1) 处插入你的代码，你将仍得到一个互斥操作。然而，代码可能被改善，在 SMP 上运行得更好。用 LL 和 SC 对新的加锁代码做一下修改。用 LL/SC 代替原语交换有什么好处？ 问题 1.D 上下文切换 Bob Cratchet 给 Ben 一组 SMP 程序运行在新系统上。当仅仅运行 Bob 的一个程序时，一切工作良好。 然而，当同时运行他的 2 个或更多程序时，机器竟给出了错误结果。Alyssa 告诉 Ben,她认为与连接寄存器 一起的 LL/SC 在上下文切换时未提供正确的同步。 描绘一个说明 Alyssa 观点的问题情形。考虑这样一种情形：一台处理器运行几个任务，它们共享某一 存储区。注意：一个处理器仅有一个链接寄存器（Rlink）。 Ben 做哪些修改才能实现上下文切换时的正确同步？ 问题 2： 监视 Cache 一致共享内存 在这一问题中，我们将探讨一个用于写回 cache 的无效一致性协议，这与 SUN Mbus 所采用的相似。 在大部分的无效协议中，任意时刻仅有一个 cache 可以拥有一个 cache 行的一份修改拷贝。然而，除允许 有干净数据的多份共享拷贝外，修改数据的多份共享拷贝也可能存在。（在这里，修改数据指不同于内存 的数据。当修改数据的多份共享拷贝存在的时候，一个 cache 拥有数据的当前拷贝，而不是内存的。）任 何时候只要一个新的修改（写）拷贝被创建，所有的共享拷贝则无效。 我们关心的 MBus 事务： z 一致读（CR）：读不命中时由一个 cache 传送，要求装入一个 cache 行。 z 一致读且无效（CRI）：写不命中后写分配时由一个 cache 发出。 z 一致无效（CI ）：当cache需要写一个处于共享状态的内存块时发生 z 块写（WR）：在写回一个 cache 块时由一个 cache 传送。 z 一致写且无效（CWI）：在块写（任何时候的一整块）是由一个 I/O 处理机（DMA）发出。 除了这些基本的总线事务外，还有： z Cache间干涉(CCI)： 被用于在适当的时候，一个cache 为另外一个cache的写事务提供支持。一 个CCI干涉并强制内存正常给出的数据。与内存相关的、要求快速响应的数据必须用CCI的形式 提供数据，但是，只有包含数据的cache支持CCI方式的响应。 数据块可能的5种状态： • 无效 (I)： 数据块不存在于cache中。 • 干净专有，Clean exclusive (CE)： cache中的数据和内存中一致，但不存在于其他cache中。 • 自己专有， exclusive (OE)： cache中的数据与内存中的不同，并且不存在于其他cache中. 当其他 cache请求得到此数据的备份时，拥有数据的cache响应请求，而不是内存响应请求。 •干净共享 Clean shared (CS)： 数据一经缓存储存，是不会被CPU更改的。同一数据若干个CS备份和 最多一个OS备份可以同时存在。 2
·白己共享司O8:从内存中读出的数据是不一样的。相同数据的其他C8氢份可以共存，当其 他ece要求数据备价时，Cc时于支背数据。eae担任主要责任而不是内存。（注意，此状态只能从 0E开始) 下而的问题将有助于加深你对一发性协议的理解。《这年小同思的答室移不必上交。》 丨根根C家，CI和C阳的用追，用达及由内存和相关的不同的。所装家的 动作，制示它之风的区别 2解样家在总找上为什么不能枝镇所。 3解甲CW1帮助缝免的O一数性问题. 间题2A 当前值在内存系统的何处 在下页的表中。弟一列e中某一地址X的初方，第二列指示地量X当前量否被存于其的cc中。 紧随一个总线事务之后，由Cc控制器甲可得知青要Ch的信皂。因此，Ca小e控制昌采取的操作多领 独立于这个信号，日是，载态转换妇围要侯镜它)第3章列举了地址X所有的变量操作，包括由CU传进 的读写操作，总找(CR,CU,口等等)的监新，©加自己的初始化〔复位)。某些状操作不可能合并： 你应该将他们作个记号，（查看例子的第一个表）在第6,7.8章中《分别与加，其他ce和内存相关)， 检在所有可能位置，将会发现第章中晋经密观的数探块更新各铃授作。第一我表已经为你完成了，相后 这些表中的答案对你会有刚助， 间题2.B 复用总线Cab块状态转换表 在本圈中，要求标在第4章和第5章中捕写状方转愧。在第5章中，捕写第3章中辑逃过提作的代态结 果。在第4章，列举出必要的由©xe传远的复用总线事务。记住，应该初始化势议，以便无论利时提供的 数据都使用CC☐方式以及只有辑有一个线路的Ce可以传运CCI事务
• 自己共享 shared (OS)： 从内存中读出的数据是不一样的。相同数据的其他CS备份可以共存。当其 他cache要求数据备份时， Cache对于支持数据， cache担任主要责任而不是内存。（注意，此状态只能从 OE开始） 下面的问题将有助于加深你对一致性协议的理解。（这些小问题的答案你不必上交。） 1 根据CR，CI 和CRI的用途、用法及由内存和相关的不同的cache 所采取的 动作，揭示它们之间的区别。 2 解释WR在总线上为什么不能被侦听。 3 解释CWI帮助避免的I/O一致性问题。 问题2.A 当前值在内存系统的何处 在下页的表中，第一列为cache中某一地址X的初态。第二列指示地址X当前是否被存于其他cache中。 (紧随一个总线事务之后，由Cache控制器即可得知需要Cache的信息。因此，Cache控制器采取的操作必须 独立于这个信号， 但是，状态转换却需要依赖它) 第3章列举了地址X所有的变量操作， 包括由CPU传送 的读写操作，总线（CR,CRI,CI等等）的监听，cache自己的初始化（复位）。某些状态操作不可能合并； 你应该将他们作个记号。（查看例子的第一个表） 在第6，7，8章中（分别与cache、其他cache和内存相关）， 检查所有可能位置， 将会发现第3章中曾经出现的数据块更新备份操作。第一张表已经为你完成了，相信 这些表中的答案对你会有帮助。 问题2.B 复用总线Cache块状态转换表 在本问题中，要求你在第4章和第5章中填写状态转换。在第5章中，填写第3章中描述过操作的状态结 果。在第4章，列举出必要的由cache传送的复用总线事务。记住，应该初始化协议，以便无论何时提供的 数据都使用CCI方式, 以及只有拥有一个线路的Cache可以传送CCI事务。 3
正餐 cacbed 面万白 Iavalid no c00 DooE CFUmad CR CE CPUwEiN CRI 339 CR Doot CRI 230t 1 7 330t pattible 精限 peoe ,四 CWI DoOE Iavalid yot c00 CFUsad C静 reglace 红 CR CRI o a WR CWI da正aw 6 20 CE CPU WTI w WR CWT n.mA vone 物 4 的 Le 200 OE CFU Tead 好 CR 05 C I WR
4
a 21 钩 BCLoei by t ■ cleasSbared 端 scc CPU Nad CPUWN CR CRI h1■ cleaeSbared 啊 C0■ CU牌 k R above a 心满 性裤 0s■ CU■ CU神 CR C ■ CWI 6 wordSh国 洲 CPU Nad CPUwriN R C 0用 R CWI
5
间题3：基于目录的Cache-一致性协议 在本问圈中，我们考虑一个CCDSM《C一致分布共序内存)系统，该系统由一相互连的单元构 成。知函1所示，每个单元包括一个CU,一个L1型e,一个共享内存和一个协议处理部件PP.PP程 用括手日染的Cc一放静文实现全Cc一放。对每一个C:组，我们段置一个Cc状老，同手指示 C组的当明一数就态，对棒一个内存块，我们设置一个目录项，用于记录当静已经对此内存执C的 单元。对每一个全局角址，有一个主单元存收物用角址和日录项。假授，全局地址中的一第分可以指定主 单元： processor PP L1 cache shared memory to interconnection network 桂用一个简单全映射目录结构。每一个日录现记录一卧完琴的单元记录，这找记录在内存中共享。在 每个日录项中，最常见的执行是位向量。一个位向量中的每一比静对应一个单元：标识内存块有效备榜是 香保存在某个单元中，由“脏比特标识内存块是否已经酸修政，这种基于目承约协议不恢靠广播使旧备份 无效，因为共享的备督牧置是可加的，所风通过发送点对点传议清皇C了要砖问的内存块的单元，米 保证C:e一效性，解弃广播，可克服朝有大量寄存惑的并行机间要衡量C小e一发系统的主要局限。 甲负责为内存访问指令，静议消息的处理和C闲图规5，主目录机5的准护提供支转，当处理雪传 送一个内存访同指令，PP检查工作C能铜的状态。如果Ce状态是不细令不能在木地执行，P中图挂起该 指令并发运一个静议请求消息给恒应的主单元，在该请求到达主目求后，主单元的？检直主日录状志，发 送一个势议应整清息返日恰请课单元，应答消息包括应答数据和（成）专有所有权（为了实现此应溶，主 日录可能需要从运程单元处铁取大分的最新数据和成专有所有权，如果内存块被修或过：如果内存块是 共享的并且收到的协议消息是一个存储请零，则要身所有的其享备份设为无效)，当收到静这应答销息 后，请象单元恢复被挂起的内存访民指令。 6
问题3： 基于目录的Cache一致性协议 在本问题中， 我们考虑一个CCDSM（Cache一致分布共享内存）系统。该系统由一组互连的单元构 成。如图1所示，每个单元包括一个CPU，一个L1型cache，一个共享内存和一个协议处理部件(PP)。PP使 用基于目录的Cache一致协议实现全局Cache一致。对每一个Cache组，我们设置一个Cache状态，用于指示 Cache组的当前一致状态。对每一个内存块，我们设置一个目录项，用于记录当前已经对此内存块Cache的 单元。对每一个全局地址，有一个主单元存放物理地址和目录项。假设，全局地址中的一部分可以指定主 单元。 使用一个简单全映射目录结构。每一个目录项记录一份完整的单元记录，这些记录在内存中共享。在 每个目录项中，最常见的执行是位向量。一个位向量中的每一比特对应一个单元，标识内存块有效备份是 否保存在某个单元中。由“脏”比特标识内存块是否已经被修改，这种基于目录的协议不依靠广播使旧备份 无效。因为共享的备份位置是可知的，所以通过发送点对点协议消息到Cache了要访问的内存块的单元，来 保证Cache一致性。摒弃广播，可克服拥有大量寄存器的并行机间要衡量Cache一致系统的主要局限。 PP负责为内存访问指令，协议消息的处理和Cache组状态、主目录状态的维护提供支持。当处理器传 送一个内存访问指令，PP检查工作Cache组的状态。如果Cache状态显示指令不能在本地执行，PP则挂起该 指令并发送一个协议请求消息给相应的主单元。在该请求到达主目录后，主单元的PP检查主目录状态，发 送一个协议应答消息返回给请求单元， 应答消息包括应答数据和（或）专有所有权（为了实现此应答，主 目录可能需要从远程单元处获取大部分的最新数据和/或专有所有权，如果内存块被修改过；如果内存块是 共享的并且收到的协议消息是一个存储请求，则要将所有的共享备份设为无效）。当PP收到协议应答消息 后，请求单元恢复被挂起的内存访问指令。 6
对于互连网格。我们做如下量设 传输的息是可靠的。可以从死镜中释放。活镜和候死。换一句话说，任协这消息的传输潜力是 有限的。 传输的清息是先进先出《FD)方式的。因此，同源单元和日的单元的议酒夏总是传 运的顺序酸接收的： 内存指◆，基本的内存动问指令是装入(L四)和存储《S),当一个存储折令写一个特定值到指定地 址时。一个装入指季读取新定地址的量新显据。我们1还应考虑e置换授作。如是Ce组被信位过，测 置美操作将设置该C一组为无效。并将修改过的数据写国内存。 装入和存储超令杯是由处理酒发递的，另外，就写失数的装入存储指令由于会导我中关无冲突。 所以明妃置换操作。在此种情况下。在置操作完成镇这类装存储指令是不能按热行的。这藏是装入 存储细令的脚作用一个处于解态的C加用不能较置换。 Cac状态：每一个Cch组，有知下四种状态： ·C.无效：eace中授有核访问的数据， C共享，酸铸问的数据在c中。并且可能同时存在于其他单元中，肉存中的数据有效 C已修改：藏访问的数都具存在于一个©e中，并且己经技修查过，内存中的数摆不是最新数据， ·C解老：被诗的数据处于解〔比如。某单元刚发运了一个铸请求，但是，还没有收到相应的 议应答。 主日录代态：每一个内存块有下面4种民态： 。Cae:肉存块授有被任何单元Ce。肉存保存有量新数貂， ·共享小：内存块被S中的指定的几个单元共享(S为一系列单无)，内存中的数据有效。 ·H己修政m:内存块只由m单元Ca能，在该单元中数据己被修。内存中的数据不是量新的 ·-瞬态，内存块处于暂时状态。（比。为了获得最新数据，主日求已轻向修政单元发送了一个协议 请求，阳是还没有收到响应的协议应答》，H码态说用主单无正在等将它发出的无效请求的成答这样 一种鲜问状老。为了实现此状老。需要一个计数器-e心u. 静议消息：在下面的表中叙遍了12种诗议消息（后面将损违清是它们的含义》。梅议酒夏包括消息类刚， 要铸问的内存地址，以发多要时的请求或者同写数据。静文消息通常是一对请求和应答。但是有丙种消息 除外：回写和意试，回写折将一个已修改的C阻内的数摇写国内存，它是单向消皇，不需要应答。《相 对其饱传议面言，它节省了一个应答清息)重试是一种NAK《否定应答》酒息，它表明发生了异凳事件， 某些请象无法被处理，面要稍后重试：这种可能性是由并行系统列起的，因为弹行系统果用分布式的运行 方式，以至于请知从一个单元发送一个协议清息到另外一个单元的这类操作不能被看作原子梨操作面执行， 7
对于互连网络， 我们做如下假设： z 传输的消息是可靠的， 可以从死锁中释放，活锁和饿死。换一句话说，任何协议消息的传输潜力是 有限的。 z 传输的消息是先进先出（FIFO）方式的。因此， 同一源单元和目的单元的协议消息总是按照他们传 送的顺序被接收的。 内存指令：基本的内存访问指令是装入（Load）和存储（Store）。当一个存储指令写一个特定值到指定地 址时，一个装入指令读取指定地址的最新数据。我们还应考虑cache置换操作。如果Cache组被修改过，则 置换操作将设置该Cache组为无效，并将修改过的数据写回内存。 装入和存储指令都是由处理器发送的。另外，读/写失败的装入/存储指令由于会导致cache中关联冲突， 所以引起置换操作。在此种情况下，在置换操作完成前这类装入/存储指令是不能被执行的。 (这就是装入/ 存储指令的副作用)一个处于瞬态的Cache组不能被置换。 Cache状态：每一个Cache组， 有如下四种状态： z C-无效：cache中没有被访问的数据。 z C-共享：被访问的数据在cache中，并且可能同时存在于其他单元中。内存中的数据有效。 z C-已修改：被访问的数据只存在于一个cache中，并且已经被修改过。内存中的数据不是最新数据。 z C-瞬态：被访问的数据处于瞬态（比如，某单元刚发送了一个协议请求，但是，还没有收到相应的协 议应答。 主目录状态：每一个内存块有下面4种状态： z H-未Cache：内存块没有被任何单元Cache，内存保存有最新数据。 z H-共享[s]：内存块被S中的指定的几个单元共享（S为一系列单元）。内存中的数据有效。 z H-已被修改[m]：内存块只由m单元Cache，在该单元中数据已被修改。内存中的数据不是最新的。 z H-瞬态：内存块处于暂时状态。（比如，为了获得最新数据，主目录已经向修改单元发送了一个协议 请求，但是还没有收到响应的协议应答）。H-瞬态说明主单元正在等待它发出的无效请求的应答这样 一种瞬间状态，为了实现此状态， 需要一个计数器-count。 协议消息：在下面的表中叙述了12种协议消息（后面将描述清楚它们的含义）。协议消息包括消息类型， 要访问的内存地址，以及必要时的请求或者回写数据。协议消息通常是一对请求和应答。但是有两种消息 除外：回写和重试。回写指将一个已修改的Cache组内的数据写回内存。它是单向消息，不需要应答。（相 对其他协议而言，它节省了一个应答消息）重试是一种NAK（否定应答）消息，它表明发生了异常事件， 某些请求无法被处理，需要稍后重试，这种可能性是由并行系统引起的，因为并行系统采用分布式的运行 方式，以至于诸如从一个单元发送一个协议消息到另外一个单元的这类操作不能被看作原子型操作而执行。 7
No. Message Type Includes data? 1o3d-r99u9过 no store-request 110 3 shared-copy-request no 4 exclusive-copy-request 0 invalidate-request 0 6 load-reply s store-reply 5 8 shared.copy-reply 9 exclusive-copy-reply w 10 invalidate-reply 110 11 write-back s 12 retry no Caxr状态转换 当处理器发送一个装入指今： 如果e状老是C共享或者C-己修政，P向处厘器规供cc中的数属。Cac小e状志不被更政. 如果状态是C无效，甲牡起装入指令，并向棱诗问内存的主单元发送一个装入信息请求。用于获相数 据。cae状态更效XC瞬奉，当隋后收到相悦的鞋入应容清息后，PP重置cae中的数累，并将c@e状态 更改为C其享，重新执行被桂起的装入购令。 当处理器发送一个存储指季： 如果ehe代5是C-枝修政，p尤许处理器写cache。ee状态不较修改， 如果e状壶是C无效成者C己修改，PP挂起存指令，并向整访问内存的主单元发送一个存储请课，用 干庆得数据的鞋占所有权。c状老更政为智时， 当…个特翼操作发生的时候 如果ehe状老是C-其享，PP就将eah状老改C-无效， 知果状态是C-已桃放，P发送一个写回消息将修技后的数据写入内存。并格@状态改为C无效， 生日录状志转模： 当一个来自姑点k的载入请象列达主姑点， 知果主目录状态是北C3e,PP发运一个载入容复给站来复供所香数墨。目录规态被改为H共料 其中5=k3. 如果主日晨找态是北共享同。印发递一个载入答复给站来规供新首数匙。甘读状态枝政为共享图 其中5-8u. 如果主日录找志是出己修政，P甲发适一个共李复制储求给站点m为了得到量新的数貂。日录状志装设为 瞬态，之后当相应的共享复制容复到达主站点时，印更新内存，发送一个载入答复始站：规供新香数匙， 然后将日录状态效出.共料5，其中5=mk: 当一个来自站点k的存储请求到达主点 知果主目录根态是化Ce,PP发递一个存储答复给站k来规供新万数墨以及所有权，目录代态较为 H己修政 如果主日录状态是北共享图。叩发适一个使无效请求始S中指定的每个站点，目承状态然后装政为瞬态， 一个专用计数器将用发送的使无效请求的数日米舒始。随后当所有的无效被确认之后，？发送一个存储答 复给站点L。政变日录状老为H已修政门
Cache状态转换： 当处理器发送一个装入指令： ·如果cache状态是C-共享或者C-已修改，PP向处理器提供cache中的数据。Cache状态不被更改。 ·如果cache状态是C-无效，PP挂起装入指令，并向被访问内存的主单元发送一个装入信息请求，用于获得数 据。cache状态更改为C-瞬态。当稍后收到相应的装入应答消息后，PP重置cache中的数据，并将cache状态 更改为C-共享，重新执行被挂起的装入指令。 当处理器发送一个存储指令： ·如果cache状态是C-被修改，PP允许处理器写cache。 cache状态不被修改。 ·如果cache状态是C-无效或者C-已修改，PP挂起存储指令，并向被访问内存的主单元发送一个存储请求，用 于获得数据的独占所有权。cache状态更改为暂时。 当一个替换操作发生的时候, ·如果cache状态是C-共享，PP就将cache状态改为C-无效。 ·如果状态是C-已修改，PP发送一个写回消息将修改后的数据写入内存，并将cache状态改为C-无效。 主目录状态转换： 当一个来自站点k的载入请求到达主站点， ·如果主目录状态是H-未Cache，PP发送一个载入答复给站点k来提供所需数据。目录状态被改为H-共享[S], 其中S={k}。 ·如果主目录状态是H-共享[S]，PP发送一个载入答复给站点k来提供所需数据。目录状态被改为H-共享[S], 其中S’=S∪{k}。 ·如果主目录状态是H-已修改[m]，PP发送一个共享复制请求给站点m为了得到最新的数据。目录状态被改为 H瞬态。之后当相应的共享复制答复到达主站点时，PP更新内存，发送一个载入答复给站点k提供所需数据， 然后将目录状态改为H-共享[S]，其中S={m,k}。 当一个来自站点k的存储请求到达主站点， ·如果主目录状态是H-未Cache，PP发送一个存储答复给站点k来提供所需数据以及所有权。目录状态被改为 H-已修改 [k]。 ·如果主目录状态是H-共享[S]，PP发送一个使无效请求给S中指定的每个站点。目录状态然后被改为H瞬态， 一个专用计数器将用发送的使无效请求的数目来初始。随后当所有的无效被确认之后，PP发送一个存储答 复给站点k，改变目录状态为H-已修改[k]。 8
如果主目录就态是已改刘m],PP发递一个排斥复制请零给站点m为了得到最新的数据和推他所有权，目 录状态树后技改H瞬老，随后当相碗的排斥复制答复收到后，印发送存健容复给站点k。并查变日录找态 为H已修 当一个来自姑点m的写日到选主站点， 如果主日录找志是己修政面购H瞬志，P叩用写国的数国更新内存，并修或日录找态为出衣C 注意：上自辑速的ae代态转换是对在ahe线大小较度的每个物理地址真言的. 问题支A Cache状态转换 表1是示了CCHE规定协议转移。当前规态是CACHE线状老。事件接收是PP收到的可以作为写/ 读费令的一个替横操作或者一个从根地址发运的梅议消息的事料，下一状老是在P处理收到事件后的下一 个CACE线状态，这个通常包害生成一线新协议清息，置换一整CACHE中的数据等。 问题3B 目最状态转换 表2显示了主目凑表明了协议的转移，当前规态是当前主目晨规态，“接收的清息”是叩接收的协 议清息。·下一状态”是P处理报收的清息后的下·个日录状老。“动作”是当处坪所接收的事件时，吧 必類做的事情。这个适常含产生一些新的静文消息，用量近使用数据更斯内存等。我们同K来精述发运 接受到丽息的地址。如cm状态。我们用)描述发进巢始协议要求的胞址， 间题3C 协议理解 考也一下这种情况，限地址发进一个率一携见要零给一个地址，这个可以仅仅发生在当主目晨是示在 一定地灶的修改的样具。根地址塑要钱得最多的UP心心人T认数暴，以及唯一的所有权，然后发送给其他 有第存要求的地址。表1中，最后一个行(9)指出了P行为当信的CACHE状态为智时面不是修政，并 且收到一个“专有排见请零”。 间题3D 非FIFO网络 对协议的正确性来说，先入失出清息特通担负着必须的青任。观在服设网塔不采用先入先出，给一个 静文失殿的例子， 9
如果主目录状态是H-已修改[m]，PP发送一个排斥复制请求给站点m为了得到最新的数据和排他所有权。目 录状态然后被改为H瞬态。随后当相应的排斥复制答复收到后，PP发送存储答复给站点k，并改变目录状态 为H-已修改[k]。 当一个来自站点m的写回到达主站点， ·如果主目录状态是H-已修改[m]或H瞬态，PP用写回的数据更新内存，并修改目录状态为H-未Cache。 注意：上面描述的cache状态转换是对在cache线大小粒度的每个物理地址而言的。 问题 3.A Cache 状态转换 表 1 显示了 CACHE 规定协议转移。当前状态是 CACHE 线状态。事件接收是 PP 收到的可以作为写/ 读指令的一个替换操作或者一个从根地址发送的协议消息的事件。下一状态是在 PP 处理收到事件后的下一 个 CACHE 线状态。这个通常包裹生成一些新协议消息，置换一些 CACHE 中的数据等。 问题 3.B 目录状态转换 表 2 显示了主目录表明了协议的转移。当前状态是当前主目录状态。 “接收的消息”是 PP 接收的协 议消息。“下一状态”是 PP 处理接收的消息后的下一个目录状态。“动作”是当处理所接收的事件时，PP 必须做的事情。这个通常包含产生一些新的协议消息，用最近使用数据更新内存等。我们用 K 来描述发送 接受到消息的地址。如 H-transient 状态，我们用 J 描述发送原始协议要求的地址。 问题 3.C 协议理解 考虑一下这种情况，根地址发送一个唯一拷贝要求给一个地址。这个可以仅仅发生在当主目录显示在 一定地址的修改的拷贝。根地址想要获得最多的 UPTODATA 数据，以及唯一的所有权，然后发送给其他 有储存要求的地址。表 1 中，最后一个行（19）指出了 PP 行为当前的 CACHE 状态为暂时而不是修改，并 且收到一个“专有拷贝请求”。 问题 3.D 非 FIFO 网络 对协议的正确性来说，先入先出消息传递担负着必须的责任。现在假设网络不采用先入先出，给一个 协议失败的例子。 9
Carreat State 上TatR Sest State Ach国 0 Ce的t C-arvalid Culil I得e以 Ga时 C xchsio-copy-roqus1 C-dhaund lond C-shannd e reploce C shaind iraidnfe-cequest C-modfied 00d C-modfied C-modhed 0T000 13 C-todfind shered copy -nequeed -Gy4 14 C-mraeieet g 7 C-rarAeEt rwvaidoo-nequest C-ENcEI shored-copy-request 19 C-laENcEl CeCy两 Table 1:Cache State Tramitions 表1Ce状态转横 5材 4 54时5te H 3 4 0 s 58 H4内 a 学 3 日4可 54牌 H-coddem] 3海■ Hoo46c4m1 5得a 日64 月 5 日o rb支 H8订 a标6不7 H Ho■门 a0闻 ored-coey-rephy eclunve-cop-rply Table2 Hose Directory Ste Tramnitious 表2主日承状态转典 10
表 1 Cache 状态转换 表 2 主目录状态转换 10