分布式共享存储系统.DOC

1、1第七章 分布式共享存储系统第七章 分布式共享存储系统 .17.1 引言 .17.1.1 并行计算机的存储系统组织 .17.1.2 常见的共享存储系统 .37.2 可扩放的高速缓存一致性协议 .77.2.1 高速缓存一致性 .77.2.2 基于目录的高速缓存一致性协议 .87.3 执行正确性模型和存储一致性模型 .137.3.1 执行正确性模型和访存事件次序 .13*7.3.2 目录协议中访存事件次序的实现 .157.3.3 存储一致性模型 .177.3.4 存储一致性模型的框架模型 .207.3.5 高速缓存一致性协议和存储一致性模型 .227.4 硬件 DSM 实例研究 .227.4.1

2、Stanford 的 DASH 多计算机 (CC-NUMA 结构 ) .227.4.2 Kendall Square Research 的 KSR1(COMA 结构 ) .267.5 共享虚拟存储系统 SVM.297.5.1 SVM 系统中的关键技术 .297.5.2 实例研究： JIAJIA 共享虚拟存储系统 .337.6 小结：共享存储系统发展趋势 .40习题 .41参考文献 .44本章首先介绍 DSM 的基本概念和可扩放的高速缓存一致性协议以及存储器一致性模型；接着在实例研究中详细讨论了两种有代表性的硬件 DSM 体系结构的机器采用 CC-NUMA 的 Stanford 大学的 DASH

3、 原型机和采用 COMA 结构的 Kendall Square Research 研制的 KSR1；然后介绍了共享虚拟存储系统中的一些关键技术并以实例研究的方式讨论了JIAJIA 共享虚拟存储系统；最后给出共享存储系统的发展趋势。7.1 引言7.1.1 并行计算机的存储系统组织并行计算机按照存储系统组织及编程界面的不同，可以大致分为两类：即共享存储的多处理机系统和消息传递的分布式存储多计算机系统。21.共享存储系统和分布式存储系统共享存储的并行机通常也称作紧密耦合多处理机，它具有一个所有处理器都可以一致访问的全局物理内存，并且可以通过对同一存储中共享数据（变量）的读写来提供一个简单通用的程序设

4、计模型。用户还可以在这种系统上方便地仿真其它程序设计模型。程序设计的方便性和系统的可移植性使得并行软件的开发费用大为降低。然而，共享存储多处理机由于共享访问介质，使得在访问共享存储时要面临较重的竞争和较长的延迟，相对于分布式系统而言，这些问题会严重地损害其峰值性能和可扩放性。共享存储的多处理机如图7.1（b）所示，其中 P 表示处理器，M 表示存储器。分布式存储的并行机通常也叫做多计算机，是由多个具有本地存储模块的相互独立的处理节点通过互连网络连接而成的。其分布存储所具有的可扩放的性质使这类系统有可能获得非常高的计算性能。然而，不同节点上的进程间通信要使用消息传递模型，即通过显式的收发原语来完

5、成。由于程序设计者需要认真考虑数据分配和消息通信，因而较共享存储系统上的程序设计要困难一些。另外不同地址空间的进程迁移使得问题更加复杂化。这样看来，分布式存储系统尽管硬件方面变得可扩放了，但软件方面的问题却更复杂了。消息传递的多计算机如图 7.1（a）所示。P1M10m-1 P2M20m-1 PnMn0m-1(a) 消 息 传 递 多 计 算 机互 连 网 络 P1 P2Pn(b) 共 享 存 储 多 处 理 机互 连 网 络M10m-1 M2m2-1Mn(n-1)m图 7.1 消息传递多计算机和共享存储多处理机在共享存储系统中，所有处理器共享主存储器，每一处理器都可以把信息存入主存储器，或从

6、中取出信息，处理器之间的通信通过访问共享变量来实现。而在消息传递系统中，每个处理器都有一个只有它自己才能访问的局部存储器，处理器之间的通信必须通过显式的消息传递来进行。从图 7.1 可以看出，在消息传递多计算机系统中，每个处理机的存储器是单独编址的；而在共享存储多处理机系统中，所有存储器统一编址。2.分布式共享存储系统与消息传递系统相比，共享存储系统由于支持传统的单地址编程空间，减轻了程序员的编程负担，因此共享存储系统具有较强的通用性，且可以方便地移植现有的应用软件。然而，在共享存储系统中，多个处理机对同一地址空间的共享也带来了一些问题。共享必然会引起冲突，从而使共享存储器成为系统瓶颈。目前在

7、规模较大的共享存储系统中，都把共享存储器分成许多模块并分布于各处理机之中(这类系统称为分布式共享存储系统) 。此外，共享存储系统都采用高速缓存来缓和由共享引起的冲突以及由存储器分布引起的长延迟对性能的影响。然而，存储器的分布会引起非一致的访存 NUMA(Non-Uniform 3Memory Access)问题，即不同处理器访问同一存储单元可能有不同的延迟。而高速缓存的使用又带来了高速缓存一致性问题，即如何保证同一单元在不同高速缓存中的备份数据的一致。访存时间的不一致以及同一单元的多个备份也破坏了存储访问的不可分割性(Atomicity)，使得同一单元内容的变化在不同的时刻被不同的处理器所认识

8、，从而影响系统的正确性。为了保证正确性，需要对访存操作的发生次序进行严格的限制，许多在单处理机中行之有效的提高性能的技术，如流水、多发射、预取、缓存等，不能在共享存储系统中盲目使用，这不利于提高性能。同时，维持高速缓存一致性需要复杂的硬件，影响了共享存储系统的可扩放性。可见，分布式共享存储多处理机系统中的存储系统有着不同于其它计算机存储系统的特征，它带来了一些新问题。目前国际上在这些问题上尚无兼顾到系统的正确性、可扩放性、以及系统性能的圆满解决方案。因此，必须在分布式共享存储系统的体系结构方面进行深入的研究；在维护分布式共享存储系统的体系结构方面进行深入的研究；在维护分布式共享存储系统的数据一

9、致性、提高系统的性能和增加系统的可扩放性等方面提出创新的解决方案。并行向量机系统和 SMP 系统都属于共享存储系统，机群系统和异构计算机系统属于消息传递系统，大多数 MPP 系统都是消息传递系统。共享存储 MPP 系统的典型代表是 SGI的 Origin 2000，但与同期的消息传递产品相比，Origin 2000 由于硬件的复杂性，其可扩放性也是有限的。此外，Cray-T3D 等系统也提供了共享空间，但硬件不负责维护高速缓存一致性。7.1.2 常见的共享存储系统根据共享存储器的分布，共享存储系统又可分为集中式共享存储和分布式共享存储两大类。在集中式共享存储系统中，多个处理器通过总线、交叉开关

10、或多级互连网络等与共享存储器相连，所有处理器访问存储器时都有相同的延迟。随着处理器个数的增加，集中式的存储器很容易成为系统瓶颈。 网 络 控 制 器存 储 器 处 理 器高 速 缓 存 网 络 控 制 器存 储 器 处 理 器高 速 缓 存 网 络 控 制 器存 储 器 处 理 器高 速 缓 存 DSM共 享地 址 空 间互 连 网 络图 7.2 DSM 系统的结构组织示意图为了解决上述问题，人们提出了分布式共享存储 DSM(Distributed Shared Memory)的概念。DSM 系统就是在物理上分布存储的系统上逻辑地实现共享存储模型。图 7.2 为 DSM系统的结构组织示意图。系

11、统设计者可以通过各种各样的方法，以硬件或软件方式实现分布式共享存储机制。DSM 系统对于程序设计者来说，隐藏了远程通信机制，保持了共享存储系统所具有的程序设计的方便性和可移植性。它可以通过对现有共享存储系统上的应用程序进行简单的修改（甚至不作任何修改）便可获得高效的执行，从而在维护软件投资的4同时获得最大的性能。另外，DSM 系统底层分布式存储的可扩放性和代价有效性（Cost Effective）仍然被继承下来了。因此 DSM 系统为构造高效率的、高可靠性的、大规模的并行机提供了一个可行的选择。在分布式共享存储系统中，共享存储器分布于各节点(一个节点可能有一个或多个处理器)之中，每个节点包含共

12、享存储器的一部分。节点之间通过可扩放性好的互连网络（如网孔等）相连。分布式的存储器和可扩放的互连网络增加了访存带宽，但却导致了不一致的访存结构。集中式和分布式的共享存储系统又分别可以分成若干类。根据存储器的分布和一致性的维护、以及实现方式等特征，目前常见的共享存储系统的体系结构可以分为以下几种：1.无高速缓存结构在这种系统中处理器没有高速缓存，诸处理器通过交叉开关或多级互连网络等直接访问共享存储器。由于系统中任一存储单元只有一个备份，所以这类系统不存在高速缓存一致性问题，但系统的可扩放性受交叉开关或多级互连网络带宽的限制。采用这种结构的典型例子是并行向量机及一些大型机，如 Cray-XMP，Y

13、MP-C90 等。此外，无高速缓存的结构还见于早期的分布式共享存储系统中，如 CMU 的 Cm*、BBN 的 Butterfly、和 Illinois的 CEDAR 等。2.共享总线结构 SMP 系统所采用的就是此结构。在这类系统中，每个处理器都有高速缓存，诸处理器通过总线与存储器相连，且具有相同的访问时间，所以也常叫作均匀存储访问UMA(Uniform Memory Access)模型。在共享总线的系统中，每个处理器的高速缓存均通过侦听总线来维持数据一致性。但由于总线是一独占性资源，这类系统的可扩放性是有限的。此结构常见于服务器和工作站中，如 DEC、SUN、Sequent 以及 SGI 等

14、公司的多机工作站产品均属于此类。3.CC-NUMA 结构 P1 P2 Pnx互 联 网 络 宿 主拷 贝 拷 贝 拷 贝x x0m-1 m2m-1 (n-1)mnm-1 处 理 器保 证 一 致 性的 高 速 缓 存高 速 缓 存控 制 器分 布 式共 享 内 存图 7.3 CC-NUMA 内存组织CC-NUMA(Cache-Coherent Non-Uniform Memory Access)结构，即高速缓存一致的非均5匀存储访问系统。这类系统的共享存储器分布于各节点之中。节点之间通过可扩放性好的互连网络(如网孔，环绕等)相连，每个处理器都能缓存共享单元，并通常采用基于目录的方法来维持处理器

15、之间的高速缓存一致性。高速缓存一致性的维护是这类系统的关键，决定着系统的可扩放性。这类系统的例子有 Stanford 大学的 DASH 和 FLASH，MIT 的Alewife，以及 SGI 的 Origin 2000 等。图 7.3 描述了 CC-NUMA 结构的内存组织结构。4.COMA 结构COMA(Cache-Only Memory Architecture)结构，即唯高速缓存存储结构。这类系统的共享存储器的地址是活动的。存储单元与物理地址分离，数据可以根据访存模式动态地在各节点的存储器间移动和复制。每个节点的存储器相当于一个大容量高速缓存，数据一致性也在这一级维护。这类系统的优点是在

16、本地共享存储器命中的概率较高。其缺点是当处理器的访问不在本节点命中时，由于存储器的地址是活动的，需要一种机制来查找被访问单元的当前位置，因此延迟很大。目前采用唯高速缓存结构的系统有 Kendall Square Research的 KSR1 和瑞典计算机研究院的 DDM。此外，COMA 结构常用于共享虚拟存储SVM(Shared Virtual Memory)系统中。图 7.4 描述了 COMA 结构的内存组织结构。P1 P2 Pnx x x互 联 网 络拷 贝 属 主 拷 贝 处 理 器高 速 缓 存保 证 一 致 性的 共 享 内 存高 速 缓 存控 制 器图 7.4 COMA 内存组织5

17、.NCC-NUMA 结构NCC-NUMA(Non-Cache-Coherent Non-Uniform Memory Access)结构，即高速缓存不一致的非均匀存储访问系统。其典型代表是 Cray 公司的 T3D 及 T3E 系列产品，这种系统的特点是虽然每个处理器都有高速缓存，但硬件不负责维护高速缓存一致性。高速缓存一致性由编译器或程序员来维护。在 T3D 和 T3E 中，系统为用户提供了一些用于同步的库函数，便于用户通过设置临界区等手段来维护数据一致性。这样做的好处是系统可扩放性强，高档的 T3D 及 T3E 产品可达上千个处理器。以上这些共享存储系统都是硬件实现统一编址的共享存储空间的

18、，可以统称为硬件共享存储系统，图 7.5 对硬件共享存储系统作了分类，它包括共享总线结构的和分布式共享存储系统两种，其中的分布式共享存储系统包括无高速缓存结构的和有高速缓存结构的两种，而有高速缓存结构的分布式共享存储系统又包括高速缓存一致的结构和高速缓存不一致的 NCC-NUMA 结构两种，进而高速缓存一致的结构又可进一步分为 CC-NUMA 结构和唯高速缓存的 COMA 结构两种。硬件分布式共享存储系统由于搜索和查询目录的工作都是6硬件实现的，因此访问远程数据的延迟相对于软件实现要少得多，从而性能也要比 SVM系统好得多。另外，由于硬件自动维护的一致性粒度是高速缓存行，使得假共享和碎片的影响

19、很小。然而，采用复杂的一致性协议和时延隐藏技术使得硬件的设计和验证非常复杂，因此这种结构一般在高档系统和那些只追求高性能的系统中才会被采用。目前代表性的硬件分布式共享存储系统包括 Memnet、Stanford DASH、Stanford FLASH、KSR1，DDM、SCI、MIT Alewife 和 MIT StartT-Voyager 等。共享总线结构(UMA,SMP) CC-NUMA 结构硬件共享存储系统 高速缓存一致有高速缓存结构 唯高速缓存COMA 结构高速缓存不一致NCC-NUMA 结构分布式共享存储系统(DSM) 无高速缓存结构(PVP)图 7.5 硬件共享存储系统分类6.共享

20、虚拟存储 SVM 结构共享虚拟存储系统，简称 SVM(Shared Virtual Memory)系统，又称为软件 DSM 系统，此概念最早由 K.Li 在 1986 年提出 1。其出发点是结合共享存储系统的可编程性好和消息传递系统的硬件简单。SVM 系统在基于消息传递的 MPP 或机群系统中，用软件的方法把分布于各节点的多个独立编址的存储器组织成一个统一编址的共享存储空间，其优点是在消息传递的系统上实现共享存储的编程界面，但主要问题是难以获得满意的性能：与硬件共享存储系统相比，SVM 系统中较大的通信和共享粒度( 通常是存储页，页大小由操作系统决定) 会导致假共享及额外的通信； 在基于机群的

21、 SVM 系统中，通信开销很大。与消息传递系统（如 MPI）相比，基于 SVM 系统的并行程序通信量通常比基于消息传递的并行程序的通信量大。然而，最近 SVM 系统技术和网络技术的发展使得 SVM 系统的性能得到了极大提高：诸如懒惰释放一致性(Lazy Release Consistency)协议 2的实现技术以及多写(Multiple Writer)协议 3等针对 SVM 系统的优化措施的提出，大大减少了 SVM 系统中的假共享和额外通信；网络技术的发展降低了系统性能对通信量的敏感程度；SVM 系统可以有效利用硬件支持，如在 SMP 机群系统中，可以在节点内利用 SMP 硬件提供的共享存储，

22、在节点间由软件实现共享存储；又如，SVM 系统可充分利用某些互连网络实现的7远程 DMA 功能提高远程访问的速度。研究表明，对于大量的应用程序，SVM 系统的性能可达消息传递系统性能的 80%以上 4。此外，SVM 系统的实现既可以在操作系统上改进，如 Ivy、Mermaid 、Mirage 和Clouds 等；也可以由运行系统来支撑，如 CMU Midway5、Rice Munin6、Rice TreadMarks7、Utah Quarks、 DIKU CarlOS、Maryland CVM 和 JIAJIA8等；还可以从语言级来实现，如 MIT CRL、Linda 和 Orca 等。此外，

23、还有混合实现的分布式共享存储系统，其基本思想是结合软硬件实现的分布式共享存储系统的优点，对存储器的管理进行分工，将复杂的管理工作交给软件，而在硬件级上维护一致性，如 Simple COMA、Wisconsin Typhoon、Tempest 和 Plus 等。或者是仍在页级维护一致性，但却采用细粒度的通信硬件以提高性能，如 Princeton SHRIMP。7.2 可扩放的高速缓存一致性协议7.2.1 高速缓存一致性在 4.2 节我们已经讨论了高速缓存一致性协议和内存一致性模型，对于基于共享总线的对称多处理机系统，顺序一致性模型和侦听一致性协议保证了系统的正确性。正如 4.2节所述，共享存储系

24、统一般都采用了高速缓存来缓和由共享引起的冲突以及由存储器分布引起的长延迟对性能的影响，而高速缓存的使用又带来了高速缓存一致性问题，即如何保证同一单元在不同高速缓存中的备份的数据一致。无高速缓存结构的分布式共享存储系统虽然不存在高速缓存一致性问题，但系统的可扩放性受限于交叉开关或多级互连网络的带宽。而有高速缓存结构的分布式共享存储机器在硬件上又可以选择支持高速缓存一致性（CC-NUMA）或不支持高速缓存一致性（NCC-NUMA） 。硬件上最简单的方案是不支持高速缓存一致性(NCC-NUMA 结构)，而只关注于存储系统的可扩放性。目前已经有好几家公司制造了此类的机器，比较典型的是 Cray 公司的

25、Cray T3D。在此类机器中，主存被分布到各个节点上，所有的节点通过网络互连在一起。访问可以是本地的也可以是远程的，这由每个节点内部的一个控制器根据所访问地址来判断该数据是在本地主存中还是在远地主存中。如果是在远地主存中，那么系统就向远地的控制器发送一个消息来访问该数据。此类系统内部都含有高速缓存，但为了避免一致性问题，共享数据被标识为不可高速缓存的，只有私有数据才能被高速缓存。当然通过软件的控制可把共享数据从共享地址空间拷贝到本地私有地址空间以显式地共享高速缓存数据值，但这样的话，一致性就要由软件来维护。这种机制的好处在于仅需要很少的硬件支持就足够了，但它同时也失去了块拷贝的好处，因为每次

26、远地访问只能取回一个单字或双字，而不是一个高速缓存块(行)。这种系统存在若干缺点：支持透明的软件高速缓存一致性的编译机制非常有限，因为现有的编译技术主要被应用于结构性较好的循环级并行的程序；同时由于显式数据拷贝的存在，这些技术带来的额外开销很大。对于那些不规则问题或涉及到动态数据结构和指针的问题（例如操作系统） ，基于编译支持的软件高速缓存一致性是不太现实的。最基本的困难在于软件的一致性算法必须是保守的，因为编译器不能很准确地对实际的共享模式进行预测，任何可能被共享的数据块必须保守地被认为都是共享的数据块。由此所产生的一致性开销过于高昂，因为在维护一致性方面所涉及的事务非常复杂，要求程序员来维

27、护高速缓存一致性是不切实际的。如果没有高速缓存一致性，那么在与访问远地单字所需的8同等开销下系统将失去获取并使用一个高速缓存行中多个字的优点。当每次访问远地主存只能获得一个单字时，共享存储所具有的空间局部性的优点就荡然无存了。当然通过对存储器间的 DMA 机制的支持或许会改善系统的性能，但这种机制开销过大（它们常常需要操作系统的干预）或者实现起来过于昂贵，因为它需要有特殊用途的硬件和缓冲区的支持，况且只有当需要进行大块数据拷贝时这种 DMA 的好处才能明显地表现出来。如果可以同时处理多个字（如一个高速缓存行）时，则诸如预取等延迟容忍技术效果才能更好（我们将在第 8 章中更详细地讨论这种技术）

28、。这些缺点在远地访存延迟远大于本地访存延迟时表现得越发突出。例如，在 Cray T3D系统中，本地的高速缓存访问延迟为 2 周期，而远地访存的开销为 150 周期。因此，在小规模的多机系统中，高速缓存一致性是一个广为接受的基本需求。对于大规模的多机系统而言，扩展分布式共享存储的高速缓存一致性协议需要面对一些新的挑战。尽管我们可以用可扩放性更好的机间互连网络替换总线，可以把主存分布到各个处理器上以使存储带宽具有更好的可扩放性，但是我们仍然不得不面对侦听协议的可扩放性问题。侦听协议要求在每个高速缓存缺失包括在对共享数据的写操作时引发的一致性操作时要同所有处理器上的高速缓存进行通信。侦听协议中无需一

29、个集中的数据结构来记录每个高速缓存块的当前状态，这虽是基于侦听的高速缓存一致性协议的优点因为它无需任何存储开销 ，但这同时也损害了侦听协议的可扩放性。例如：一个含有 16 个处理器的多处理机的数据高速缓存容量为 64KB，其高速缓存行大小为 64 字节。假设 1995 年一个超标量处理器每 5 纳秒能发出一个数据请求，那么对于并行应用程序 Barnes 所需的带宽为 500MB/sec，Ocean所需的带宽为 9400MB/sec。SGI 公司的 Challenge 是 1995 年基于总线的具有最高带宽的多处理机，它所提供的带宽却仅为 1200MB/sec。因此，对于较大规模的多机系统，必须

30、采用扩展性更好的方法来构造可扩放的高速缓存一致的共享存储的机器(CC-NUMA)，尤其需要寻找一种可扩放的一致性协议来替换侦听协议，而目录协议就是一种可供选择的协议。7.2.2 基于目录的高速缓存一致性协议当某个处理器采用写无效协议正在更新一个变量而其它的处理器也试图读该变量时，则就会发生读缺失且可能导致总线的流量大大增加。此外，写更新协议更新了远程高速缓存中的数据，但其它处理器可能永远也不会使用这些数据。因此，这些问题使采用总线来构造大型多处理机系统受到限制。当用多级互连网络来构造有数百个处理器的大型系统时，高速缓存的侦听协议就必须修改。因为在多级网络上实现广播功能的代价很大，所以可把一致性

31、命令只发给那些存放块拷贝的高速缓存，这就产生了用于网络连接的多处理机系统的基于目录的协议。在基于目录的协议中，每一存储块都有一个目录状态与之对应。不论系统是基于侦听的协议还是基于目录的协议，它们基本的高速缓存状态集通常是一样的（如 MESI 协议） 。从概念上讲对于任何一种协议，某一存储块的高速缓存状态是一个向量，它包含了该存储块在整个系统的各个高速缓存中的状态，包括哪些高速缓存中含有该存储块，是否处于“脏”状态等等。通常，目录表的大小正比于每台机器存储块数和处理器数的乘积，这在少于 100 个处理器时这还可以忍受，但当处理器数不断增加时，我们必须寻找一种办法使得目录结构不至于过于庞大，现有的

32、方法是在目录表中保留尽量少的存储块的信息（如只保留那些已被高速缓存的存储块而不是全部的）或者使目录表的每个入口含有较少的位数。为了防止目录成为系统瓶颈，可以把目录项分布到各个处理器上。这样访问不同的目录项可以寻址到不同的处理器上。在分布式目录表中，每个处于共享状态的高速缓存块的9信息只会存放在一个处理器上，这就避免了广播。1.目录结构 在多级网络中，高速缓存目录存放了有关高速缓存行拷贝驻留在哪里的信息，以支持高速缓存一致性。各种目录协议的主要差别是目录如何维护信息和存放什么信息。第一个目录方案是用一个中心目录存放所有高速缓存目录的拷贝，中心目录能提供为保证一致性所需要的全部信息。因此，其容量非

33、常大且必须采用联想方法进行检索，这和单个高速缓存的目录类似。大型多处理机系统采用中心目录会有冲突和检索时间过长两个缺点。分布式目录方案是由 Censier 和 Feautrier 提出来的 9。在分布式目录中每个存储器模块维护各自的目录，目录中记录着每个存储器块的状态和当前的信息，其中状态信息是本地的，而当前信息指明哪些高速缓存中有该存储器块的拷贝。图 7.6 中高速缓存 C2 的读缺失（图中用细线表示）将产生一个请求并送给存储器模块，存储器的控制器将该请求再传送给高速缓存 C1 中的脏拷贝（也就是重写拷贝） 。这个高速缓存再把此拷贝写回存储器，于是存储器模块就可以向请求的高速缓存提供一份拷贝

34、。在高速缓存写命中时(图 7.6 中用粗线表示 )它就发一个命令给存储器的控制器，存储器的控制器再发无效命令给在目录 D1 的当前向量中有记录的所有高速缓存( 高速缓存 C2)。M1互 连 网 络C1P1M2D2 MmDmC2P2 CnPnD1 图 7.6 基于目录的高速缓存一致性方案的基本原理不使用广播的高速缓存一致性协议，必须将所有高速缓存中每个共享数据块拷贝的地址都存储起来，这张高速缓存地址表，不管它是集中的还是分布的，都称为高速缓存目录。每个数据块的目录项中包含大量的用来指明块拷贝地址的指针，还包含一个用来说明是否有一个高速缓存允许把有关的数据块写入的脏位。不同类型的目录协议可分为全映

35、射(Full-map)目录、有限(Limited)目录和链式(Chained)目录三类。全映射目录存放与全局存储器中每个块有关的数据，这样，系统中的每个高速缓存可以同时存储任何数据块的拷贝（每个目录项包含 N 个指针，N 是系统中处理器的数目） ；有限目录与全映射目录不同之处是不管系统规模有多大，其每个目录项均含有固定数目的指针；链式目录将目录分布到各个高速缓存，其余与全映射目录相同。下面根据Chaiken、Fields、Kwihara 和 Agarwal10最早的分类对三种高速缓存目录进行讨论。102.全映射目录用全映射协议实现的目录项中有一个处理器位和一个脏位：前者表示相应处理器的高速缓存

36、块( 存在或不存在)的状态；后者如果为“1” ，而且有一个也只有一个处理器位为“1”，则该处理器就可以对该块进行写操作。高速缓存的每块有两个状态位：一位表示块是否有效；另一位表示有效块是否允许写。高速缓存一致性协议必须保证存储器目录的状态位与高速缓存的状态位一致。图 7.7(a)给出了全映射目录的三种不同状态：第一种状态表示全系统所有高速缓存中都没有单元 X 的拷贝；当三个高速缓存 (C1，C 2 和 C3)同时请求读单元 X 的拷贝时，就出现了第二种状态，这时目录项中的三个指针(处理器位) 被置 “1”，表示这些高速缓存已有数据块拷贝（在前述这两种状态下，目录项最左边的脏位被置为未写(C)状态，表示没有一个处理器允许写入该数据块） ；在 C3 请求对该块的写许可权时出现了第三种状态，这时脏位被置成脏(D)状态，而且有一个指针指向 C3 的数据块。