分布式共享存储器课件

《分布式共享存储器课件》由会员分享，可在线阅读，更多相关《分布式共享存储器课件（56页珍藏版）》请在金锄头文库上搜索。

1、第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v什么是分布式共享存储器系统什么是分布式共享存储器系统 分布式共享存储器系统是分布式操作系统中的一个资源管理部件，它在没有物理上共享的存储器的分布式操作系统中实现了共享存储器模式。这种共享存储器模式在分布式系统中提供了一个可供系统内所有节点所共享的虚拟地址空间。程序设计者可以像使用传统的存储器一样使用该虚拟地址空间。这种物理上分布逻辑上共享的存储器就叫做分布式共享存储器(Distributed Shared MemoryDSM)。每一个节点都可以拥有存储在共享空间的数据，数据的所有者也可以跟随数据从一个节

2、点移到另一个节点。当一个进程访问共享地址空间中的数据时，映像管理员就把共享存储器地址变换到本地地址或远程的物理存储器地址。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v什么是分布式共享存储器系统什么是分布式共享存储器系统 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v为什么需要分布式共享存储器为什么需要分布式共享存储器 DSM的计算模型和RPC的计算模型相比各有优缺点：1)DSM的计算模型支持数据在系统内移动，使数据更容易访问。2)RPC计算模型是把操作移到数据

3、所在位置。RPC不支持程序利用其访问的局部性优点，对一块远程数据的每个操作都产生通信，对数据的操作必须先定义好。但是RPC支持异构型。3)DSM可把数据移到本地节点，允许程序利用其访问的局部性优点，使用缓存器可以改善响应时间。移动性要求对数据位置进行跟踪；缓存要求解决各副本的一致性。当数据正向某个主机移动时，不能对它进行处理。如果数据经常修改，RPC模型可能更好些。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v为什么需要分布式共享存储器为什么需要分布式共享存储器 从通信机制来看，DSM与报文传递方式有以下不同 ：(1)访问的透

4、明性。使用报文传递方式访问共享的数据变量时，程序必须明确地使用节点地址信息和通信原语(如SEND和RECEIVE)。而在DSM中系统提供了一种抽象的共享地址空间从而隐匿了物理地址和通信细节，使得程序直接面向共享的数据。 (2)共享数据结构的复杂性和异构性。使用报文传递方式，由于数据是在不同的地址空间之间传递，从而使得具有复杂数据结构的数据难于在不同类型的计算机及进程之间传递。而在DSM中，可以借助引用机制(reference)去实现上述数据访问，复杂性与异构性的问题由引用机制去处理，从而进一步简化了并行程序设计。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1

5、 11.1 基本概念基本概念 v为什么需要分布式共享存储器为什么需要分布式共享存储器 从通信机制来看，DSM与报文传递方式有以下不同 ：(3) 数据的局部性。在DSM中，新访问的数据项与其周围的数据一起按块或按页移动，而不是只移动新访问的数据本身。根据程序的局部性原理，这样可以大大地减小网络的通信开销。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v为什么需要分布式共享存储器为什么需要分布式共享存储器 与紧密耦合的多机系统相比，DSM系统具有以下特点：(1) 规模可扩充。在紧密耦合的多机系统中，由于各处理机共享的是一个单一的物理

6、存储器，主存访问都要经过一个集中环节(例如总线)进行，这就限制了多机系统的规模(一般为几十台处理机)。DSM不存在这样的限制，可以扩充至很大的规模(多至上千个节点)。(2) 廉价。由于DSM系统可以用现有的硬件来构造，并且无需连接共享存储器与处理机的复杂接口，因而DSM的构造成本要低于紧密耦合的多机系统。(3) 兼容性。在共享存储器多机系统上编写的程序原则上都可以无需修改或稍加修改后转换到DSM系统上运行。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v共享存储器中缓存一致性方法共享存储器中缓存一致性方法 有两类基本方法实现缓存

7、一致性：即探听缓存方法和使用目录的方法。 探听探听( (snooping)snooping)缓存方法缓存方法用于具有广播能力的通信介质中，例如共享总线。每个缓存器为了保持自己数据的一致性要监听共享总线上进行的由其他处理机发出的存储器操作。 Berkeley是一个典型例子，它是一种写无效协议，它假设通过单总线访问共享的物理存储器。此协议采用一个所有权方案。一个数据块的所有者是一个缓存器，是上次对该数据块的修改者，如果该块被其所有者清除，则主存作为其所有者。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v共享存储器中缓存一致性方法共

8、享存储器中缓存一致性方法 Berkeley探听协议数据块有四种状态：重写(dirty)、共享重写、有效和无效：(1)无效。该缓存块不包含有效数据。(2)有效。该缓存块中数据是有效的。(3)重写。共享存储器中的数据是不正确的，该缓存块是唯一有效的数据副本。该缓存块是数据的所有者。(4)共享重写。共享存储器中的数据是不正确的，该缓存块是数据的所有者，其他缓存中有同样的副本。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v共享存储器中缓存一致性方法共享存储器中缓存一致性方法 探听协议的写操作：探听协议的写操作：数据只能由所有者提供。有

9、效块和无效块在替换时可以简单地扔掉。重写块和共享重写块在替换时要写回共享存储器，并把共享存储器设置为所有者。如果对缓存块进行写，而缓存块的状态是重写的，则写操作可以直接进行；但是如果缓存块是共享重写、或有效，则必须向其他缓存器发送“无效”信号，然后可以进行写操作；如果缓存块是无效的，要从当前所有者那里取得数据块，再向其他缓存器发送“无效”信号，然后可以进行写操作。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v共享存储器中缓存一致性方法共享存储器中缓存一致性方法 目录协议：目录协议：在共享存储器中设置存储器块的目录。当发生缓存不

10、命中时，先把请求转到此目录。通常目录项中包含所有权、副本集(copyset)和该块的重写位。副本集指出该块数据在哪些缓存器中有副本，可用位向量来实现。发生读未命中时，先检查重写位，如果该块不处于重写状态，则共享存储器中的版本是有效的，于是简单地返回该块，并对副本集信息进行更新；如果该块的重写位置位，则该块的所有者必须修改该块，并且要更新共享存储器中的版本，向读者提供读副本。写未命中或者从读权变成写权时，要求目录的副本集使其他副本无效。与探听缓存方案不同，读副本的位置都已经知道，因此，可以用顺序方式而不是以广播方式发送“无效”报文。目录方案不要求广播介质，但在每次缓存未命中时要增加一次查表。 分

11、布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 vDSMDSM的设计与实现问题的设计与实现问题 (1)共享地址空间结构和粒度。共享地址空间的结构指的是存储器中共享数据的布局方法，它依赖于应用程序类型，地址空间可以是平面的，分段的或物理的。粒度是指共享单元的大小，可以是字节、字、页或复杂的数据结构，它也是可用的并行性的度量，依赖于通信开销和应用程序表现的局部性类型。结构和粒度是密切相关的。 (2)缓存一致性协议。不同的协议有不同的假设，选择协议依赖于存储器访问模式和支持环境。在写无效协议中，一块共享数据可能有很多个只读副本，但仅有一个可

12、写副本，每进行一次写时，除了一个以外，其他副本均变成无效。在写更新协议中。每次写都要对所有副本进行更新。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 vDSMDSM的设计与实现问题的设计与实现问题 (3)同步原语。在并发访问下，光有缓存一致性协议还不能维持共享数据一致性。尚需要同步原语对访问共享数据的活动进行同步，例如信号灯、事件计数和锁等。 (4)替换策略。在允许数据迁移的系统中，当共享数据占满了缓存器的有效空间时，必须决定将那些数据转移出去并且放到哪里去。 (5)可扩充性。DSM系统比起紧密耦合系统来，一个重大的优点是具有可

13、扩充性。限制可扩充性有两个因素：集中的瓶颈(像紧密耦合系统中的总线)和全局公用信息的操作及存储(如广播报文或目录等)。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 vDSMDSM的设计与实现问题的设计与实现问题 (6)异构性。如何实现对两个具有不同体系结构的机器的存储器共享是个很困难的问题。两个机器甚至对基本数据类型(如整数、浮点数等)都使用不同的表达方式。 (7)数据定位和访问。为了在一个DSM系统中共享数据，应用程序必须能找到并且检索所需要的数据。对于一个支持数据迁移的系统，实现这一点就更为复杂。 (8)颠簸。DSM系统特别

14、容易出现颠簸，例如若两个节点对一个数据项同时进行写，就可能产生以高速率来回传送数据的现象(乒乓效应)，使得任何实际工作都不能进行。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v一致性语义一致性语义 共享存储器中常使用的一些一致性语义 ：(1)严格一致性。对一个数据项所进行的任何读操作所返回的值总是对该数据项最近一次进行写操作的结果。 (2)顺序一致性。所有进程对数据项的所有操作可以认为是按照某个顺序进行的，任何进程对这个顺序的观点是一样的。 (3)处理机一致性。不仅要求一个进程中的所有写操作能够以它在该进程中出现的顺序被所有其

15、他进程看见，还要求不同进程对同一个数据项的写操作，应该被所有进程以相同的顺序看见。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.1 11.1 基本概念基本概念 v一致性语义一致性语义 共享存储器中常使用的一些一致性语义 ：(4)弱一致性。程序员使用同步算符，使得对数据的多个操作组来说是顺序一致性的。即不同进程的多个操作组可以认为是按照某个顺序进行的，任何进程对这个顺序的观点是一样的。但是操作组内的多个操作其他进程是不可见的。对同步算符是顺序一致性的。 (5)释放一致性。使用了“获得”和“释放”这两类同步算符，对同步算符是处理机一致的。 分布式共享存储器课件第十

16、一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v算法使用的模型和环境算法使用的模型和环境 共享存储器模型为访问共享数据提供了两个基本操作：data:=read(address)write(data,address)read返回由address指出的数据项。Write把由地址address指出的内容设置为data。 根据是否允许迁移或复制，可以将DSM的实现算法分成四类：中央服务员算法、迁移算法、读复制算法和全复制算法。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的

17、算法 v算法使用的模型和环境算法使用的模型和环境 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v中央服务员算法中央服务员算法 使用一个中央服务员，负责为所有对共享数据的访问提供服务并保持共享数据唯一的副本。读和写操作都包括由执行该操作的进程向中央服务员发送请求报文，中央服务员执行请求并回答，读操作时回答数据项，写操作时回答一个承认。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v迁移算法迁移算法 数据总是被迁移到访问它的节点。这是一

18、个“单读者/单写者”(SRSW)协议，因为在整个系统中，一次只有一个进程读或写一个给定的数据项。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v读复制算法读复制算法 对于一个当前不在本地的块中的一个数据项进行读操作时，先与远程节点通信以获得那个块的一个只读副本，然后再进行读操作。若被执行写操作的数据所在的块不在本地或在本地但主机无写权时，必须先使此块在其他节点的所有副本无效，之后再进行写操作。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的

19、算法 v全复制算法全复制算法 全复制算法允许数据块在进行写时也可以复制，因而它遵从了“多读者/多写者”(MRMW)协议。保持复制数据一致性的一种可能的方法是对所有的写操作进行全局排序，而只对与发生在执行读操作节点上的写操作相关的那些读操作进行排序 。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v算法性能算法性能基本代价：基本代价： (1) p：一个包事件的代价，即发送或接收一个短包的处理代价，包括可能的任务切换、数据复制及中断处理开销。实际系统的典型值的变化范围是1到几个毫秒。(2) P：发送或接收一个数据块的

20、代价。这与p十分相似，但P值要高得多。对于一个通常需要多个包的8K字节的块来说，典型值的范围是20至40个毫秒。(3) S：参与分布式共享内存的节点数。(4) r：读/写比，即平均有r个读操作时才有一个写操作。这个参数也用于整个块的访问模式。显然这两个比可能不同，但为了简化分析假定相等。分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v算法性能算法性能基本代价：基本代价： (5) f：非复制数据块(用于迁移算法)访问故障的概率。它等于单一节点连续访问一个块(以后由另一个节点访问此块导致故障)的平均次数的倒数。它说明迁

21、移算法数据访问的局部性。(6) f：读复制算法用于对复制数据块访问故障的概率。它是连续访问本地数据块中数据项(以后访问一个非本地数据块中某数据项)的平均次数的倒数。它说明读复制算法数据访问的本地性。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.2 11.2 实现实现DSMDSM的算法的算法 v算法性能算法性能四种算法的平均访问代价：四种算法的平均访问代价： 中央服务员算法：Cc=(1-1/S)4p迁移算法：Cm=f(2P+4p)读复制算法：Crr=f2P+4p+Sp/(r+1)全复制算法：Cfr=1/(r+1)(S+2)p每一个表达式都有两部分，第一部分在“”

22、的左边，表示访问远程数据项的概率。第二部分在“”的右边，等于访问远程数据项的平均代价。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v目录方案的分类目录方案的分类 目录：不用广播的缓存器一致性协议必须保存每块共享数据的所有缓存器副本的位置。此缓存位置表，不管是集中的还是分散的，都叫做目录。每个数据的目录项包括许多指针，用来指出此块各副本所在位置。每一个目录项还有一个“重写”位用来指明是否允许某一个(只有一个)缓存器进行写。 目录协议有三种主要类型：全映像目录、有限目录和链式目录 。全映像目录的每个目录项保持N个指

23、针，这里N是系统中处理器的个数。有限目录和全映像目录的不同之处在于，有限目录的每个目录项具有固定数量的指针，与系统中处理机数量无关。链式目录与全映像目录相似，只是它将目录分布于各缓存器。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v全映像目录全映像目录 全映像目录协议使用的目录每项包含每个处理机，有一个指针并且有一个“重写”位。指针所对应的每一位代表该块在相应处理机缓存器中的状态(存在或不存在)。如果“重写”位置位，那么有且只有一个处理机的指针位被置位，允许这个处理机对该数据块进行写操作。缓存器保存每块数据的两

24、个状态位：一位表明此数据块是否有效，另一位表明一个有效的数据块是否可写。缓存器一致性协议必须在存储器目录中保存这些状态位，并维持缓存一致性。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v全映像目录全映像目录 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v全映像目录全映像目录 写过程：(1) C3检测到包含单元X的数据块是有效的，但是该处理机对数据块无写的权限，这由块的允许写位表示。(2) C3发出一个对包含单元X的存储模块的写请求

25、，并且停止处理机P3。(3) 存储器模块向C1和C2发出无效请求。(4) C1和C2收到无效请求后，设置对应的位指出包含单元X的数据块是无效的，并向存储器模块发回一个承认。(5) 存储器模块收到这个承认，将“重写”位置位，清除指向C1和C2的指针，并向C3发出写允许报文。(6) C3收到写允许报文，更新该缓存器中的状态，并且激活处理机P3。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v有限目录有限目录 有限目录协议是为解决目录大小问题而设计的。限制对同一数据块同时进行缓存的任务数目，即限制一个数据块的缓存数目，

26、就可以将每个目录项的大小限定为一个常数。分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v链式目录链式目录 它通过保持一个目录指针链对共享副本进行跟踪。单向链式结构：单向链式结构：分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v链式目录链式目录 缓存器块的替换缓存器块的替换 ：假设从C1到CN都有单元X的副本，并且单元X和单元Y都直接映射到缓存器同一行上。如果处理机Pi读单元Y，必须从它的缓存器中先驱逐单元X。在这种情况下，有两种可能性：

27、 (1) 沿着链路向Ci-1发送一个报文，将Ci-1的指针指向Ci+1，将Ci从链路中脱离开。(2) 使从Ci到CN中的单元X无效。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.3 11.3 使用目录的使用目录的DSMDSM v链式目录链式目录 双向链式结构：另外一种解决替换问题的方法是使用双向链。这种方案为每个缓存器副本保持一个向前和一个向后的指针，这样当缓存器替换时，协议不必遍历整个链。双向链目录优化替换条件是以更大的平均报文长度(由于传送更多的目录指针)、缓存器中的指针的存储空间加倍和更为复杂的一致性协议为代价的。 分布式共享存储器课件第十一章第十一章

28、分布式共享存储器分布式共享存储器 11.4 DSM11.4 DSM系统的实现v实现实现DSMDSM的基本方法的基本方法 DSM有三种实现方法，有的系统使用了不止一种方法。(1) 硬件实现。把传统的高速缓存技术扩展到可扩充的体系结构中。(2) 操作系统和程序库的实现。通过虚拟存储器的管理机构达到共享和一致性。(3) 编译程序的实现。把共享访问自动转换成同步和一致性原语。 分布式共享存储器课件分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.4 DSM11.4 DSM系统的实现v结构和粒度结构和粒度 1)DSM的硬件实现方法典型地支持了较小的粒度。 2)页的大小：较大的

29、页能够减少分页的开销，但是可能引起争用可能性越大。另一个影响页大小选择的因素是必须保留该系统中有关页的目录信息：页越小，则目录越大。 3)结构化共享存储器的一个实现方法是根据数据类型进行共享。这种方法是把共享存储器作为面向对象的分布式系统中的对象而进行构造。4)另一个方法是把共享存储器构造成像一个数据库。Linda就是一个这种模式的系统。它把它的共享存储器安排成为一个相联存储器，叫做元组(tuple)空间。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.4 DSM11.4 DSM系统的实现v数据定位与访问数据定位与访问 1)集中的服务员：集中的服务员来跟踪所有共

30、享数据。这种集中的方法有两个缺陷：服务员串行执行定位查询，从而削弱了并行性；服务员负载过重，降低了整个系统的速度。 2)广播数据请求：不幸的是，广播的可扩充性不好，所有的节点(不仅是数据所在的节点)都必须处理广播请求。广播在网络上的等待有可能使访问花费很长时间才能完成。3)基于所有者的分布式的模型：每一块数据都有一个与之相联系的所有者，这个所有者就是拥有数据主副本的节点。当数据在整个系统中迁移时，它的所有者也会随之而改变。当另一个节点需要数据的一个副本时，就向所有者发送请求。所有者如果仍保留着这个数据，就返回该数据；若所有者已将数据发送给其他节点，则把这一请求转发给那个新所有者。缺点是一个请求

31、可能被转发多次后才能到达当前所有者。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.4 DSM11.4 DSM系统的实现v一致性协议一致性协议 两类一致性协议：两类一致性协议：写无效协议和写更新协议 在写无效协议中，一块数据可能有很多个只读副本，但是，只有一个是可写副本。这种协议之所以被称作写无效协议，是因为在开始一次写操作之前，除了将被写的那个副本之外，其他副本均变成无效。在写更新方式中，一次写操作将更新所有副本。 分布式共享存储器课件DashDash系统简化的写无效协议系统简化的写无效协议(DC(DC代表目录控制器代表目录控制器) ) 分布式共享存储器课件P

32、lusPlus写更新协议，写更新协议，MCMMCM代表存储一致性控制器代表存储一致性控制器 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.4 DSM11.4 DSM系统的实现v颠簸颠簸 DSM系统特别容易出现颠簸。如果两个节点对一个数据项同时进行写，该数据项就有可能以高速率来来回回地被传送(乒乓效应)，任何实际工作都做不成 。 1)Munin系统允许程序员把共享数据和类型联系起来：写一次、写多次、生产者消费者、专用、迁移、结果、常读、同步及一般的读/写。为避免两个竞争写者的颠簸，一个程序员可以把类型指定为写多次，系统将使用延迟写策略。 2)Mirage系统在一致

33、性协议中，增加了一个动态可调整参数，它决定一页在一个节点上保持可用的最小时间量()。例如若一个节点对一个共享页执行一次写操作，则此页在该节点上时间内是可写的。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.4 DSM11.4 DSM系统的实现v可扩充性可扩充性 DSM系统一个理论上的优点是它们比紧密耦合系统具有更好的可扩充性。前面说过，对可扩充性限制有两种因素：集中瓶颈(例如紧密耦合系统中的总线)和全局公用信息的操作及存储(例如广播报文或目录，它的大小与节点数成比例)。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.4 DSM11

34、.4 DSM系统的实现v异构性异构性 1)在Agora系统中，把存储器构造为在异构性机器之间共享对象。2)Mermaid探索了另一种不同寻常的方法：存储器以页方式共享，并且一页只包含一种数据类型。当在不同体系结构的两个系统之间移动一页时，变换子程序都会把该页上的数据转换成适当的格式。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy软件实现的软件实现的DSMDSM Ivy中进程地址空间分成专用和共享两部分。专用部分不能由其他进程寻址。共享部分由虚拟共享存储器实现，是个平面地址空间，为运行在不同节点上

35、的所有进程所共享，也就是被各线程共享的单地址空间。 地址空间是分页的。一页是同步的最小单位，当需要时它可以从一个节点迁移到另一个节点。每个节点上有一个存储器管理程序，满足本地和远程请求并实现缓存器一致性协议。当访问共享空间的一个地址时，阻塞故障进程，Ivy存储器管理程序检查待访问页是否在本地。如果不在本地，向远程存储器发送请求。得到该页后，发生页故障的进程恢复执行。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy一致性协议一致性协议 Ivy所使用的一致性概念是多个读/单个写的语义。对某地址的读操作

36、总是得到最近对该地址写的值，一致性协议保证执行这一语义。 Ivy的每个处理机都有自己的页表。表中的每一项纪录着该主机的访问权，可以对一页拥有读、写权或无任何权利。一页的访问权是与缓存器中一个块的状态相当的。分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy一致性协议一致性协议 当访问一个共享地址时，该主机检查它是否有权在指定方式下访问含有此地址的那一页。如果没有，则根据访问方式产生一个读或者写故障，其步骤如下：读故障：(1) 找出谁是所有者；(2) 所有者把该故障主机填入副本集；(3) 所有者把自己的

37、访问权变成只读；(4) 所有者向故障主机发送该页。分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy一致性协议一致性协议 当访问一个共享地址时，该主机检查它是否有权在指定方式下访问含有此地址的那一页。如果没有，则根据访问方式产生一个读或者写故障，其步骤如下：写故障：(1) 找到所有者；(2) 所有者向故障主机发送该页和该页的副本集，并将它的那项标为无效；(3) 故障主机根据副本集送出“无效”报文；(4) 返回对“无效”报文的承认，进程继续执行。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分

38、布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy一致性协议一致性协议 三种不同的一致性协议 ：1)集中管理者方法类似于管程，管程由一个数据结构和一些过程组成，提供对数据结构的互斥访问。集中管理者固定在一个处理机上，维持一张页表。每个处理机也有一张页表，每一项有两个域：访问和锁。访问域记录本地处理机上的页面的可访问信息。每个处理机知道中心管理者，并且在本地没有数据对象时能够向管理者发出请求。当一个处理机上有多个进程等待同一个页面时，加锁机制防止处理机发出多个请求。对一个页面成功执行写操作就会成为页面的所有者。 分布式共享存储器课件第十一章第十一章 分布式共

39、享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy一致性协议一致性协议 三种不同的一致性协议 ：2)有两种类型的固定分布式管理者算法：固定的和广播的。固定算法中，每个处理机预定管理一部分页面。通常一个适当的散列函数用于把页面映射到处理机。广播算法中，访问页面出故障的处理机发出广播确定页面的真正所有者。广播算法性能比较差，因为所有处理机必须处理每个请求，减慢处理机的计算。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy一致性协议一致性协议 三种不同的一

40、致性协议 ：3)动态分布式管理者方法的核心是每个处理机的页表中记录所有页的所有者。页表中，集中管理者算法中的所有者域被替换成另一个域，叫做可能所有者(probowner)域，它可能是页面的真正所有者，也可能是页面的可能所有者。可能所有者域构成一个链，从一个节点到另一个节点，最终会指向真正的所有者。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy存储器管理存储器管理 (1)页替换。 Ivy的虚拟共享存储器的页有五种：可写的、所有者可读的、只读的、空的和不使用的。空页和不用页都具有最高的被替换优先权，

41、即如果需要一页则先替换它们。由于只读页可被其所有者制造备份，所以可以简单地丢弃。对于所有者读的页和可写页的丢弃当然需要所有权的转让。 (2)存储器分配。为了支持动态数据结构，使用动态存储器分配方案是必要的。Ivy有两种方法。第一种是集中式方法，即所有进程向集中式的“存储器分配程序”请求存储器和归还存储器。这是个简单的方法。第二个方法，除了集中式分配程序外，每个节点还有它自己的分配子程序。每个节点请求一大块存储器并执行来自本地进程的存储器请求。仅在本地节点用完存储器时才和集中式管理程序联系。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM

42、实例：Ivy和MemNetvMemNetMemNet硬件实现的硬件实现的DSM DSM 在MemNet中，全部主机共享一个公共的地址空间。此地址空间是分页的，这些页可根据要求在系统内迁移。对此地址空间的访问被直接送到主机内的接口部件(作为一个智能存储器模块)。这个部件能缓存一部分共享存储器并和其他主机的这种部件相互作用调进另外的页。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvMemNetMemNet缓存一致性协议缓存一致性协议 MemNet使用的缓存一致性协议和Ivy使用的相同，即读操作必须总是返回该数据

43、最近的值。每个MemNet部件有一块表，表中每项对应整个共享地址空间中的每一块，还包括下述状态标志：(1) 有效。指出此缓存器对该块是否有一个有效副本。(2) 独占。指出本主机对该块是否有独占的访问权。(3) 保留。指出该块的保留空间是否在本主机中。(4) 位置。如果块是在本主机内，指出该块副本的位置。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvMemNetMemNet缓存一致性协议缓存一致性协议 1)当该部件收到从处理机来的读请求时，先检查是否有一个覆盖该地址的块的有效副本。如果有，则请求很容易满足，否

44、则发送一个带有空白的数据请求报文。每个主机依次检查MemNet请求。第一个具有有效副本的主机满足读请求。 2)当MemNet部件收到对共享空间某地址的写请求时，先检查它是否有一个有效副本和对该块的独占访问权。如果是，则请求被满足。否则，如果该部件有该块的一个有效副本但对其无独占访问权，则发送“无效”请求。最后，如果该部件没有该块的有效副本，则发送一个独占数据请求。当一个部件收到一个“无效”请求时，如果该块被缓存则使其无效。独占的数据请求除有类似的作用外，具有该块有效副本的第一个部件还必须在无效前供给该块。当最初的请求返回时，被阻塞的进程就恢复执行。 分布式共享存储器课件第十一章第十一章 分布式

45、共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvMemNetMemNet缓存一致性协议缓存一致性协议 3)MemNet的缓存替换方法是为每块设置一个保留区，使用随机替换策略。当一个部件要从其缓存器中替换一个块时，发送更新块请求并带走此块。为此块保留空间的部件为此请求服务，将此保留空间更新。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy与与MemNetMemNet的比较的比较 1)Ivy的目标是支持并行处理并证明用软件实现共享虚拟存储器是可行的； MemNe

46、t则侧重于DSM的硬件实现，使用共享总线把部件连到处理机上，这样很自然地要共享物理地址空间。 2)Ivy对页定位问题研究得很全面，认为固定分布是最简单和有效的方案，转发方案具有全分布式控制的优点。MemNet则在一个令牌环上实现，使用广播简单地确定最近的副本的位置。 3)Ivy对每页维持一个副本集以避免使用广播方法的“无效”操作，而MemNet则利用其令牌环的优点并使用广播方式。 分布式共享存储器课件第十一章第十一章 分布式共享存储器分布式共享存储器 11.5 DSM11.5 DSM实例：Ivy和MemNetvIvyIvy与与MemNetMemNet的比较的比较 4)Ivy和MemNet都使用单个写多个读的协议。读操作总是返回一页的最新内容。 5)Ivy的同步单位是页。如果使用Ivy开发细粒度并行性是不现实的，所以页长为1KB是合理的。MemNet的高速令牌环和硬件实现允许开发较细粒度的并行性，因此其同步单位较小，仅为32字节。 6)Ivy研究了使用磁盘和其他节点主存储器进行替换的方法。后一方法由于未来工作站可能具有更大主存而更加有意义。MemNet的不寻常之处是保留主存对块进行后备。这对MemNet是很重要的，因为它依赖于可预言的短的故障修复时间以避免任务切换。 分布式共享存储器课件