- 176- . 分布式共享内存 第 - 176 - 页 第7章 分布式共享内存

在本章中，我们研究实现分布式共享内存(distributed shared memory简称DSM)。 7.1 引论

传统上，分布式计算是基于消息传递模型，在这种模型下进程们经由以消息形式交换数据来彼此互相交互和共享数据。Hoare的通讯顺序进程(communicating sequential processes)，客户-服务器模型和远程过程调用都是这种模型的例子。 分布式共享内存(Distributed shared memory简称DSM)系统是分布式操作系统的一个资源管理成分，它实现在没有物理地共享内存的分布式系统中的共享内存模型。见图7.1。

图7.1分布式系统中的共享内存模型 这个共享内存模型提供一个虚拟地址空间，使得被在一个分布式系统中所有结点（计算机）之间共享。

7.2 体系结构和动力

具有分布式共享内存，程序访问在共享地址空间中的数据正如同访问在传统的虚存中的数据一样。在支持分布式共享内存的系统中，数据既在辅存和主存之间也在不同结点的主存之间移动。 每个结点可以拥有存贮在共享地址空间中的数据，并且当数据从一个结点移到另一个结点时，拥有关系可以改变。当一个进程访问在共享地址空间中的数据时，一个映照管理者(mapping manager) 映照共享内存地址到物理存储，这个物理存储可以是本地或远程的。 映照管理者是一个或者实现在操作系统内核中或者作为一个运行时库例程的软件层。 为了减少由于通讯误而带来的延迟，当共享内存地址映照到在在一个远程结点上的一个物理内存位置时，分布式共享内存可以移动在共享内存地址中的数据从一个远程结点到正在访问数据的结点。在这样情况下，分布式共享内存利用底层通讯系统的通讯服务。 分布式共享内存 .-177. 第 - 177 - 页 7.2.1 分布式共享内存的优点 在消息传递模型中，程序通过明显的消息传递使共享数据可供使用。换句话说，程序员需要意识到进程之间数据移动。程序员不得不明显地使用通讯原语（例如SEND和RECEIVE），放一个重要的负担在它们身上。 相反，分布式共享内存系统隐藏这个明显的数据移动并且提供一个较简单的程序员已经精通的共享数据抽象。因此，利用分布式共享内存比通过明显的消息传递更容易地设计和编写并行算法。 在消息传递模型中，数据在两个不同的地址空间之间移动。这使得它难以在两个进程之间传递复杂的数据结构。而且传递由“引用”的数据和传递包含指针的数据结构一般是困难的和贵的。相反，分布式共享内存系统允许传递由“引用”的复杂的数据结构，于是简化了对分布式应用的算法的开发。 仅移动规定的所引用的数据片来代替由移动整块或包含所引用的引用场点的数据页，分布式共享内存利用程序所显示的引用局部性，因此削减了在网络上的通信开销。 分布式共享内存系统比紧偶合多机系统更便宜。这是因为分布式共享内存系统可以利用货架上的（off-the-shelf）硬件建立不需要复杂的接口把共享内存连接到处理机。 在一个分布式共享内存系统所有结点中可供使用物理内存组合在一起是巨大的。这个大的内存可以用于有效地运行要求大内存的程序而不用招致由于在传统的分布系统中对换引起的磁盘延迟。这个事实也由处理机速度相对于内存速度预料的增加和非常高速网络出现所支持。 在具有单个共享内存的紧偶合多机系统中主存经由一个公共总线访问，这限制多机系统为几十个处理机。分布式共享内存系统没有这个缺点，并且可以容易地向上扩充。 为共享内存多处理机写的程序原则上可以不加改变地运行在分布式共享内存系统。至少这样的程序可以容易地移到分布式共享内存系统中。 本质上，分布式共享内存系统努力克服共享内存机器体系结构的限制并且减少在分布系统中写并行程序。所需的努力。

7.3 实现分布式共享内存的算法 实现分布式共享内存的中心课题是：  如何追踪远程数据的位置；  当访问远程数据时，.如何克服.通信延迟和在分布系统中通信协议的执行相联的开销；  为了改善系统性能，.如何使共享数据在几个结点上并发地可供访问。 现在我们描述实现分布式共享内存的四个基本算法。  中央服务器(Central-Server)算法  迁移算法  读复制(Read-Replicatin)算法  完全复制算法

7.3.1 中央服务器(Central-Server)算法

在中央服务器(Central-Server)算法中，一个中央服务器维护所有的共享数据。它服务从其它结点或者客户来的读请求，返回数据项给它们（见图7.2）。在客户写请求时，它更新数据并返回表示收到的消息。 在表示收到的消息失效情况一个超时(timeout)可以被采用来重发请求。重复的写请求可以由写请求所伴随的顺序号检测。在几次重新传输而又无响应后一个失败的条件被返回到企图访问共享数据的应用。 - 178- . 分布式共享内存 第 - 178 - 页 虽然中央服务器算法其实现是简单的，但中央服务器可能变成一个瓶颈。为了克服这个问题，共享数据可以分布在几个服务器上。在这种情况下，客户必须能够对每次数据访问定位适当的服务器。 多点广播式的数据访问请求是不希望的，因为与中央服务器方案相比，它并不减少服务器的负载。分布数据的一种较好的方法是按地址划分共享数据并且利用一个映照函数定位适当的服务器。

图7.2中央服务器算法 7.3.2 迁移算法

在中央服务器算法中，每个数据访问请求被发送到数据的位置，与之相比，在迁移算法中的数据被转移到数据访问请求的地点，允许随后的对该数据的访问被本地地执行（见图7.3）。 迁移算法每次仅允许一个结点访问一个共享数据。 在中央服务器算法中，每个数据访问请求被发送到数据的位置，与之相比，在迁移算法中的数据被转移到数据访问请求的地点，允许随后的对该数据的访问被本地地执行。

图7.3迁移算法 典型地，包含数据项的整个页或块迁移以代替单个请求项。这个算法利用由程序所展示的引用的局部性把迁移的费用分摊到多个访问迁移数据上。但是这种途径对抖动(thrashing)敏感，其中页频繁地在结点间迁移，而仅服务少数请求。 为了减少抖动，Mirage系统使用一个可调的参量决定一个结点可以拥有一个共享数据项的期间。这允许在页被迁移到另一结点之前一个结点对该页作若干次访问。Munin系统力求采用适合不同的数据访问模式的协议来减少数据移动。 分布式共享内存 .-179. 第 - 179 - 页 迁移算法提供了一个机会把分布式共享内存与运行在单个结点上操作系统所提供的虚存集成在一起。当分布式共享内存所用的页大小是虚存页大小的倍数时，一个本地掌握的共享内存页可以被映照到一个应用的虚地址空间并且利用正常的机器指令访问。 在一个内存访问失效时，如果内存地址映照到一个远程页，在映照页到进程的地址空间之前，一个页失效处理程序将迁移该页。在迁移一页时，该页从所有在以前结点被映照到的地址空间移开。注意，几个进程可以共享在一个结点上的一页。 为了定位一个数据块，迁移算法可以利用一个服务器追踪页的位置或者通过在结点上所维持的提示。这些提示指向搜寻当前占有该页的结点。另外，一个询问可以广播来定位一页。 7.3.3 读复制(Read-Replicatin)算法

在前面途径中仅仅在一个结点上的进程可以在如何时刻访问一个共享数据。读复制(Read-Replicatin)算法扩充了迁移算法，即复制数据块并且允许多个结点具有读访问或一个结点具有读写访问（多个读者-一个作者协议）（见图7.4）。

图7.4读复制 由允许多个结点并发地访问数据，读复制可以改善系统性能。但是，写操作是昂贵的，因为一个共享块在各种结点上的所有副本将或者不得不是无效的，或者用当前值来更新以维护共享数据块的一致性。 在读复制算法中分布式共享内存必须追踪所有数据块副本的位置。在IVY系统中，一个数据块的拥有者结点追踪具有该数据块的一个副本的所有结点。在PLUS系统中，一个分布式链接列表用来追踪具有该数据块的一个副本的所有结点。 然而，当读对写的比例是大的时候，读复制有减少读操作平均费用的潜力。在节描述在IVY系统中实现的许多读复制算法。 7.3.4 完全复制算法

完全复制算法是读复制算法的一种扩充（见图7.5）。读复制算法它允许多个结点具有对共享数据块的读和写两种访问（多个读者-多个作者协议）。由于许多结点可以并发地写共享数据，对共享数据的访问必须被控制以维持它的一致性。 维持一致性的一个简单方法是利用一个无间隙的顺序器(gap-free sequencer)。在这种方案下，所有希望修改共享数据的结点将发送修改给一个顺序器。这个顺序器将赋予一个顺序号并且多点广播这个修改及顺序号到所有具有该共享数据项副本的结点。 - 180- . 分布式共享内存 第 - 180 - 页 每个结点以顺序号次序处理修改请求。在一个结点上一个修改请求的顺序号和期待的顺序号之间的间隙指示一个或多个修改已被遗漏。在这种情况下结点将被请求重新传送已经遗漏的修改。这蕴涵在某个结点保留修改的日记。在第5节将讨论若干其它维护共享数据的一致性的协议。

图7.5完全复制算法 7.4 存储一致性(Memory coherence)

为了改善性能分布式共享内存系统依赖复制共享数据项和允许在许多结点上并发访问。但是，如果并发访问不仔细地加以控制，内存访问可能以不同于程序员所期望的次序被执行。非正式讲，一个内存是一致的，如果由读操作返回的值总归是程序员所期望的值。 例如，对一个程序员期待一个读操作返回一个最近写操作所存贮的值是相当自然的。 因此，为了维护共享数据项的一致性，一个控制或同步访问的机制是必要的。同样为了写正确的程序，程序员需要理解如何进行对共享内存的并发更新。允许的内存访问次序集合构成了存储一致性模型。字一致性用于说明一种特殊类型的一致性。 存储一致性最直观语义是严格一致性(strict consistency)，其定义如下：一个读返回最近写的值。严格一致性要求具有决定最近写的能力，依次它蕴涵请求的全序。由于比一个程序可能实际需要更多的数据移动和同步要求，请求的全序导致非有效性（请参考[4]）。 为了解决这个问题，某些分布式共享内存系统企图由提供不严格的一致性语义来改善性能。下列是几种内存一致性形式：  顺序的一致性(Sequential consistency)  一般一致性(General Consistency)  处理机一致性(Processor consistency)  弱一致性(Weak consistency)  释放一致性(Release consistency)