中科院讲义_分布式操作系统_分布式共享内存

1、分布式 共享内存在本章中，我们研究实现分布式共享内存(distributed shared memory简称DSM)。第1节引论 第2节体系结构和动力第3节实现分布式共享内存的算法第4节存储一致性(Memory Coherence)第5节一致性协议引论传统上，分布式计算是基于消息传递模型，在这种模型下进程们经由以消息形式交换数据来彼此互相交互和共享数据。Hoare的通讯顺序进程(communicating sequential processes)，客户-服务器模型和远程过程调用都是这种模型的例子。引论分布式共享内存(Distributed shared memory简称DSM)系统是分布式操

2、作系统的一个资源管理成分，它实现在没有物理地共享内存的分布式系统中的共享内存模型。见图1。这个共享内存模型提供一个虚拟地址空间，使得被在一个分布式系统中所有结点（计算机）之间共享。分布式共享内存体系结构和动力具有分布式共享内存，程序访问在共享地址空间中的数据正如同访问在传统的虚存中的数据一样。在支持分布式共享内存的系统中，数据既在辅存和主存之间也在不同结点的主存之间移动。体系结构和动力每个结点可以拥有存贮在共享地址空间中的数据，并且当数据从一个结点移到另一个结点时，拥有关系可以改变。当一个进程访问在共享地址空间中的数据时，一个映照管理者(mapping manager) 映照共享内存地址到物理

3、存储，这个物理存储可以是本地或远程的。体系结构和动力映照管理者是一个或者实现在操作系统内核中或者作为一个运行时库例程的软件层。体系结构和动力为了减少由于通讯误而带来的延迟，当共享内存地址映照到在在一个远程结点上的一个物理内存位置时，分布式共享内存可以移动在共享内存地址中的数据从一个远程结点到正在访问数据的结点。在这样情况下，分布式共享内存利用底层通讯系统的通讯服务。分布式共享内存的优点在消息传递模型中，程序通过明显的消息传递使共享数据可供使用。换句话说，程序员需要意识到进程之间数据移动。程序员不得不明显地使用通讯原语（例如SEND和RECEIVE），放一个重要的负担在它们身上。分布式共享内存的

4、优点相反，分布式共享内存系统隐藏这个明显的数据移动并且提供一个较简单的程序员已经精通的共享数据抽象。因此，利用分布式共享内存比通过明显的消息传递更容易地设计和编写并行算法。分布式共享内存的优点在消息传递模型中，数据在两个不同的地址空间之间移动。这使得它难以在两个进程之间传递复杂的数据结构。而且传递由“引用”的数据和传递包含指针的数据结构一般是困难的和贵的。相反，分布式共享内存系统允许传递由“引用”的复杂的数据结构，于是简化了对分布式应用的算法的开发。分布式共享内存的优点仅移动规定的所引用的数据片来代替由移动整块或包含所引用的引用场点的数据页，分布式共享内存利用程序所显示的引用局部性，因此削减了

5、在网络上的通信开销。分布式共享内存的优点分布式共享内存系统比紧偶合多机系统更便宜。这是因为分布式共享内存系统可以利用off-the-shelf硬件建立不需要复杂的接口把共享内存连接到处理机。分布式共享内存的优点在一个分布式共享内存系统所有结点中可供使用物理内存组合在一起是巨大的。这个大的内存可以用于有效地运行要求大内存的程序而不用招致由于在传统的分布系统中对换引起的磁盘延迟。这个事实也由处理机速度相对于内存速度预料的增加和非常高速网络出现所支持分布式共享内存的优点在具有单个共享内存的紧偶合多机系统中主存经由一个公共总线访问，这限制多机系统为几十个处理机。分布式共享内存系统没有这个缺点，并且可以

6、容易地向上扩充。分布式共享内存的优点为共享内存多处理机写的程序原则上可以不加改变地运行在分布式共享内存系统。至少这样的程序可以容易地移到分布式共享内存系统中。分布式共享内存的优点本质上，分布式共享内存系统努力克服共享内存机器体系结构的限制并且减少在分布系统中写并行程序。所需的努力。实现分布式共享内存的算法实现分布式共享内存的中心课题是：F如何追踪远程数据的位置；F当访问远程数据时，.如何克服.通信延迟和在分布系统中通信协议的执行相联的开销；F为了改善系统性能，.如何使共享数据在几个结点上并发地可供访问。实现分布式共享内存的算法现在我们描述实现分布式共享内存的四个基本算法。F中央服务器(Cent

7、ral-Server)算法F迁移算法F读复制(Read-Replicatin)算法F完全复制算法中央服务器(Central-Server)算法中央服务器算法在中央服务器(Central-Server)算法中，一个中央服务器维护所有的共享数据。它服务从其它结点或者客户来的读请求，返回数据项给它们（见图）。在客户写请求时，它更新数据并返回表示收到的消息。中央服务器算法在表示收到的消息失效情况一个超时(timeout)可以被采用来重发请求。重复的写请求可以由写请求所伴随的顺序号检测。在几次重新传输而又无响应后一个失败的条件被返回到企图访问共享数据的应用。中央服务器算法虽然中央服务器算法其实现是简单的

8、，但中央服务器可能变成一个瓶颈。为了克服这个问题，共享数据可以分布在几个服务器上。在这种情况下，客户必须能够对每次数据访问定位适当的服务器。中央服务器算法多点广播式的数据访问请求是不希望的，因为与中央服务器方案相比，它并不减少服务器的负载。分布数据的一种较好的方法是按地址划分共享数据并且利用一个映照函数定位适当的服务器。迁移算法在中央服务器算法中，每个数据访问请求被发送到数据的位置，与之相比，在迁移算法中的数据被转移到数据访问请求的地点，允许随后的对该数据的访问被本地地执行。迁移算法每次仅允许一个结点访问一个共享数据。迁移算法迁移算法在中央服务器算法中，每个数据访问请求被发送到数据的位置，与之

9、相比，在迁移算法中的数据被转移到数据访问请求的地点，允许随后的对该数据的访问被本地地执行。迁移算法每次仅允许一个结点访问一个共享数据。迁移算法典型地，包含数据项的整个页或块迁移以代替单个请求项。这个算法利用由程序所展示的引用的局部性把迁移的费用分摊到多个访问迁移数据上。但是这种途径对抖动(thrashing)敏感，其中页频繁地在结点间迁移，而仅服务少数请求。迁移算法为了减少抖动，Mirage系统使用一个可调的参量决定一个结点可以拥有一个共享数据项的期间。这允许在页被迁移到另一结点之前一个结点对该页作若干次访问。Munin系统力求采用适合不同的数据访问模式的协议来减少数据移动。迁移算法迁移算法提

10、供了一个机会把分布式共享内存与运行在单个结点上操作系统所提供的虚存集成在一起。当分布式共享内存所用的页大小是虚存页大小的倍数时，一个本地掌握的共享内存页可以被映照到一个应用的虚地址空间并且利用正常的机器指令访问。迁移算法在一个内存访问失效时，如果内存地址映照到一个远程页，在映照页到进程的地址空间之前，一个页失效处理程序将迁移该页。在迁移一页时，该页从所有在以前结点被映照到的地址空间移开。注意，几个进程可以共享在一个结点上的一页。迁移算法为了定位一个数据块，迁移算法可以利用一个服务器追踪页的位置或者通过在结点上所维持的提示。这些提示指向搜寻当前占有该页的结点。另外，一个询问可以广播来定位一页。读

11、复制(Read-Replicatin)算法在前面途径中仅仅在一个结点上的进程可以在如何时刻访问一个共享数据。读复制(Read-Replicatin)算法扩充了迁移算法，即复制数据块并且允许多个结点具有读访问或一个结点具有读写访问（多个读者-一个作者协议）。读复制算法读复制算法由允许多个结点并发地访问数据，读复制可以改善系统性能。但是，写操作是昂贵的，因为一个共享块在各种结点上的所有副本将或者不得不是无效的，或者用当前值来更新以维护共享数据块的一致性。读复制算法在读复制算法中分布式共享内存必须追踪所有数据块副本的位置。在IVY系统中，一个数据块的拥有者结点追踪具有该数据块的一个副本的所有结点。在

12、PLUS系统中，一个分布式链接列表用来追踪具有该数据块的一个副本的所有结点。读复制算法然而，当读对写的比例是大的时候，读复制有减少读操作平均费用的潜力。在节描述在IVY系统中实现的许多读复制算法。完全复制算法完全复制算法是读复制算法的一种扩充。读复制算法它允许多个结点具有对共享数据块的读和写两种访问（多个读者-多个作者协议）。由于许多结点可以并发地写共享数据，对共享数据的访问必须被控制以维持它的一致性。完全复制算法维持一致性的一个简单方法是利用一个无间隙的顺序器(gap-free sequencer)。在这种方案下，所有希望修改共享数据的结点将发送修改给一个顺序器。这个顺序器将赋予一个顺序号并

13、且多点广播这个修改及顺序号到所有具有该共享数据项副本的结点。完全复制算法每个结点以顺序号次序处理修改请求。在一个结点上一个修改请求的顺序号和期待的顺序号之间的间隙指示一个或多个修改已被遗漏。在这种情况下结点将被请求重新传送已经遗漏的修改。这蕴涵在某个结点保留修改的日记。在第5节将讨论若干其它维护共享数据的一致性的协议。完全复制算法存储一致性(Memory coherence)为了改善性能分布式共享内存系统依赖复制共享数据项和允许在许多结点上并发访问。但是，如果并发访问不仔细地加以控制，内存访问可能以不同于程序员所期望的次序被执行。非正式讲，一个内存是一致的，如果由读操作返回的值总归是程序员所期

14、望的值。存储一致性例如，对一个程序员期待一个读操作返回一个最近写操作所存贮的值是相当自然的。存储一致性因此，为了维护共享数据项的一致性，一个控制或同步访问的机制是必要的。同样为了写正确的程序，程序员需要理解如何进行对共享内存的并发更新。允许的内存访问次序集合构成了存储一致性模型。字一致性用于说明一种特殊类型的一致性。存储一致性存储一致性最直观语义是严格一致性(strict consistency)，其定义如下：一个读返回最近写的值。严格一致性要求具有决定最近写的能力，依次它蕴涵请求的全序。由于比一个程序可能实际需要更多的数据移动和同步要求，请求的全序导致非有效性（请参考4）。存储一致性为了解决

15、这个问题，某些分布式共享内存系统企图由提供不严格的一致性语义来改善性能。下列是几种内存一致性形式：存储一致性F顺序的一致性 (Sequential consistency)F一般一致性(General Consistency)F处理机一致性 (Processor consistency)F弱一致性(Weak consistency)F释放一致性(Release consistency)一致性模型实质上是软件和存储器间的契约（Adve和Hill，1990），它是说，如果软件同意服从某模型给出的规则，则存储器允诺软件在这种模型下正确地工作；否则，存储器操作的正确性将得不到保证。存储器一致性问题对于

16、共享地址空间的并行计算机特别重要，已提出二三十种一致性模型。 最严格的一致性模型称为严格一致性，它由下述条件定义：这个定义自然而明白，由于它假定了绝对全局时间（就像在牛顿物理中）的存在，“最近”访问的意义是明确的。传统意义上，单处理机遵守严格一致性，单处理机的编程者正希望这样。 最严格的也是最理想的存储器一致性模型是严格一致性。它定义为：假设X是存在B机器上的变量。A机器上的进程在T1时刻读取X，即发送信包到B以读取X。稍后，在T2时刻，B机器上的进程写X。若遵守严格一致性，不管机器在哪里，也不管T1和T2相距多近，A都应该读出原来的值。然而，若T2 - T1 = 1ns，而机器距离 3米，从

17、A到B传送读操作并使之先于写操作，信号则必须以十倍光速的速度（ ）传递，而这与爱因斯坦相对论矛盾。编程人员有理由在违反了物理原则的情况下要求严格一致性吗？ 秒米秒米/3000000100000013TSVF但是无法保证每个时间间隔内最多只发生一个单一操作。因此，仍需要处理在同一时间间隔内所发生的多个操作。如果同一时间间隔内的两个操作是对相同数据进行操作，并且其中一个操作是写操作，那么称这两个操作是冲突的。F定义一致性模型的一个重要问题就是准确定义出现冲突时，哪些行为是可接受的。F这就要求在软件和存储之间做一个约定。如果这种约定显式或隐式地承诺满足严格一致性，那么存储器就能正常地工作。F另一方面

18、，编程人员也希望能够满足严格一致性。如果不支持严格一致性，程序发生问题就很难说是那方面的问题。F例如，在一个小型多处理机系统中，如果某个处理机写存储器a单元，1ns以后，另一个处理机读存储器a单元，这个处理机可能是从它的局部高速缓存中获得了老的值。这样就很可能同样的程序运行多次得到 的结果却是多个，而不是唯一的。先规定一些符号：P1，P2，代表不同的进程，在图中以不同的高度表示。每一进程完成的操作按水平的显示时间轴向右增加，直线分割不同进程。符号Wi(X)a和Ri(Y)b分别表示进程Pi在X处写a和从Y处读出值为b。当进程访问数据而未发生冲突时，忽略符号Wi(X)和Ri(Y)的下标i。本章中所

19、有图表中变量初值均为0。 总之，对于严格一致性的存储器，写操作在任一时刻对所有进程都是可见的，同时维护一个绝对全局时间顺序。一旦存储器中的值改变，不管读写之间的事件间隔多小，不管哪个进程执行读操作，也不管进程在何处，以后读出的都是新更改的值。同样，如果执行了读操作，不管后面的写操作有多迅速，该读操作仍应读出原来的值。 F严格一致性是理想的编程模式，在一个实际的NUMA系统中，若不采取特殊措施，就不一定能得到保证。例如，在一个处理机访问本地存储器的时间为T1，访问远程存储器的时间为T2的NUMA系统中，记T2-T1=2d。设处理机P1的本地存储器单元x的初值为0，在t时刻处理机P2向远程存储器单

20、元x发出写入值1的指令，在在t+d时刻处理机P1读本地存储器单元x，由于P2的指令尚未到达P1的存储器的控制器，故P1读得的值仍为0。对于常规的编程模式，这无疑会导致程序的结果不正确。尽管严格一致性是理想的编程模式，但在分布式系统中，这几乎不可能实现。经验表明，编程人员通常对弱模式掌握得较好。比如，所有操作系统课本中都谈到临界区和同步互斥的问题。人们认为编写这种正确的并行程序（如生产者-消费者问题）不应考虑进程间的相对速度以及语句的执行在时间上如何交错。 如果一个进程的两个事件发生如此之快，以致其他进程不能在此之间执行任何操作，那可能会带来麻烦。相反，读者的编程方式是：语句执行的确切时间（实际

21、上是存储器访问）并不重要，而当事件（读或写）的顺序是至关重要时，可以使用信号量等方法实现同步操作。接受这种意见意味着采用较弱的一致性模式来编程。经过几次实践，大多数并行程序编写人员都能适应这种模式。因此，程序设计者使用较弱的一致性模式同样可以使存储器正常工作。顺序一致是比严格一致稍弱的存储器模式，Lamport（1979）首先定义了顺序一致存储器应符合的条件： Lamport （1979）定义的顺序一致性存储器满足如下条件： 这个定义意味着，当程序在各个机器上并行运行时，任何一种有效的交错存储器访问顺序都是可认可的行为，但所有处理器必须看见的是同样的访问顺序。如果一个进程（处理器）看见的是一种

22、交错，另一进程看见的是另一种交错，则这样的存储器不是一个顺序一致性的存储器。然而，同一程序再次并行运行，其存储器访问的交错次序会不同于上次的交错次序，这是允许的。 这个定义说明：对于在不同机器上（甚至在伪并行的分时系统上）并行运行的进程，任何有效的交错都是可以接受的行为，但所有进程必须遵守同一访问存储器顺序。在一块存储器中，若一个进程（或处理机）看到一种交错，另一进程看到另一个交错，这就不是顺序一致存储器。注意，这与时间无关，没有最近存入的概念。在这里，进程可以看到所有进程写，但只能看到本进程读。 顺序一致存储器不保证读返回的值是1ns、1ms甚至1分钟以前另一进程写入的。它只保证所有进程以相同的顺序看见存储器访问。如果根据图（a）编写的程序在一次运行后，或许会得到图（b）的结果。结果是不确定的。如果缺少明确的同步操作，在此运行程序或许不能