分布式共享内存

第第 7 7 章章分布式共享内存分布式共享内存 在本章中 我们研究实现分布式共享内存 distributed shared memory 简称 DSM 7 17 1 引论引论 传统上 分布式计算是基于消息传递模型 在这种模型下进程们经由以消息形式交换数据来彼此互 相交互和共享数据 Hoare 的通讯顺序进程 communicating sequential processes 客户 服务器模型 和远程过程调用都是这种模型的例子 分布式共享内存 Distributed shared memory 简称 DSM 系统是分布式操作系统的一个资源管理成 分 它实现在没有物理地共享内存的分布式系统中的共享内存模型 见图 7 1 图 7 1 分布式系统中的共享内存模型 这个共享内存模型提供一个虚拟地址空间 使得被在一个分布式系统中所有结点 计算机 之间共 享 7 27 2 体系结构和动力体系结构和动力 具有分布式共享内存 程序访问在共享地址空间中的数据正如同访问在传统的虚存中的数据一样 在支持分布式共享内存的系统中 数据既在辅存和主存之间也在不同结点的主存之间移动 每个结点可以拥有存贮在共享地址空间中的数据 并且当数据从一个结点移到另一个结点时 拥有 关系可以改变 当一个进程访问在共享地址空间中的数据时 一个映照管理者 mapping manager 映照共 享内存地址到物理存储 这个物理存储可以是本地或远程的 映照管理者是一个或者实现在操作系统内核中或者作为一个运行时库例程的软件层 为了减少由于通讯误而带来的延迟 当共享内存地址映照到在在一个远程结点上的一个物理内存位 置时 分布式共享内存可以移动在共享内存地址中的数据从一个远程结点到正在访问数据的结点 在这样 情况下 分布式共享内存利用底层通讯系统的通讯服务 精品文档 177欢迎下载 7 2 1分布式共享内存的优点分布式共享内存的优点 在消息传递模型中 程序通过明显的消息传递使共享数据可供使用 换句话说 程序员需要意识到 进程之间数据移动 程序员不得不明显地使用通讯原语 例如 SEND 和 RECEIVE 放一个重要的负担在 它们身上 相反 分布式共享内存系统隐藏这个明显的数据移动并且提供一个较简单的程序员已经精通的共享 数据抽象 因此 利用分布式共享内存比通过明显的消息传递更容易地设计和编写并行算法 在消息传递模型中 数据在两个不同的地址空间之间移动 这使得它难以在两个进程之间传递复杂 的数据结构 而且传递由 引用 的数据和传递包含指针的数据结构一般是困难的和贵的 相反 分布式共 享内存系统允许传递由 引用 的复杂的数据结构 于是简化了对分布式应用的算法的开发 仅移动规定的所引用的数据片来代替由移动整块或包含所引用的引用场点的数据页 分布式共享内 存利用程序所显示的引用局部性 因此削减了在网络上的通信开销 分布式共享内存系统比紧偶合多机系统更便宜 这是因为分布式共享内存系统可以利用货架上的 off the shelf 硬件建立不需要复杂的接口把共享内存连接到处理机 在一个分布式共享内存系统所有结点中可供使用物理内存组合在一起是巨大的 这个大的内存可以 用于有效地运行要求大内存的程序而不用招致由于在传统的分布系统中对换引起的磁盘延迟 这个事实也 由处理机速度相对于内存速度预料的增加和非常高速网络出现所支持 在具有单个共享内存的紧偶合多机系统中主存经由一个公共总线访问 这限制多机系统为几十个处 理机 分布式共享内存系统没有这个缺点 并且可以容易地向上扩充 为共享内存多处理机写的程序原则上可以不加改变地运行在分布式共享内存系统 至少这样的程序 可以容易地移到分布式共享内存系统中 本质上 分布式共享内存系统努力克服共享内存机器体系结构的限制并且减少在分布系统中写并行 程序 所需的努力 7 37 3 实现分布式共享内存的算法实现分布式共享内存的算法 实现分布式共享内存的中心课题是 如何追踪远程数据的位置 当访问远程数据时 如何克服 通信延迟和在分布系统中通信协议的执行相联的开销 为了改善系统性能 如何使共享数据在几个结点上并发地可供访问 现在我们描述实现分布式共享内存的四个基本算法 中央服务器 Central Server 算法 迁移算法 读复制 Read Replicatin 算法 完全复制算法 7 3 17 3 1中央服务器中央服务器 Central Server Central Server 算法算法 在中央服务器 Central Server 算法中 一个中央服务器维护所有的共享数据 它服务从其它结点 或者客户来的读请求 返回数据项给它们 见图 7 2 在客户写请求时 它更新数据并返回表示收到的 消息 在表示收到的消息失效情况一个超时 timeout 可以被采用来重发请求 重复的写请求可以由写请求 所伴随的顺序号检测 在几次重新传输而又无响应后一个失败的条件被返回到企图访问共享数据的应用 虽然中央服务器算法其实现是简单的 但中央服务器可能变成一个瓶颈 为了克服这个问题 共享 数据可以分布在几个服务器上 在这种情况下 客户必须能够对每次数据访问定位适当的服务器 多点广播式的数据访问请求是不希望的 因为与中央服务器方案相比 它并不减少服务器的负载 分布数据的一种较好的方法是按地址划分共享数据并且利用一个映照函数定位适当的服务器 图 7 2 中央服务器算法 7 3 27 3 2迁移算法迁移算法 在中央服务器算法中 每个数据访问请求被发送到数据的位置 与之相比 在迁移算法中的数据被 转移到数据访问请求的地点 允许随后的对该数据的访问被本地地执行 见图 7 3 迁移算法每次仅允许一个结点访问一个共享数据 在中央服务器算法中 每个数据访问请求被发送到数据的位置 与之相比 在迁移算法中的数据被 转移到数据访问请求的地点 允许随后的对该数据的访问被本地地执行 图 7 3 迁移算法 典型地 包含数据项的整个页或块迁移以代替单个请求项 这个算法利用由程序所展示的引用的局 部性把迁移的费用分摊到多个访问迁移数据上 但是这种途径对抖动 thrashing 敏感 其中页频繁地在 结点间迁移 而仅服务少数请求 精品文档 179欢迎下载 为了减少抖动 Mirage 系统使用一个可调的参量决定一个结点可以拥有一个共享数据项的期间 这 允许在页被迁移到另一结点之前一个结点对该页作若干次访问 Munin 系统力求采用适合不同的数据访问 模式的协议来减少数据移动 迁移算法提供了一个机会把分布式共享内存与运行在单个结点上操作系统所提供的虚存集成在一 起 当分布式共享内存所用的页大小是虚存页大小的倍数时 一个本地掌握的共享内存页可以被映照到一 个应用的虚地址空间并且利用正常的机器指令访问 在一个内存访问失效时 如果内存地址映照到一个远程页 在映照页到进程的地址空间之前 一个 页失效处理程序将迁移该页 在迁移一页时 该页从所有在以前结点被映照到的地址空间移开 注意 几 个进程可以共享在一个结点上的一页 为了定位一个数据块 迁移算法可以利用一个服务器追踪页的位置或者通过在结点上所维持的提 示 这些提示指向搜寻当前占有该页的结点 另外 一个询问可以广播来定位一页 7 3 37 3 3读复制读复制 Read Replicatin Read Replicatin 算法算法 在前面途径中仅仅在一个结点上的进程可以在如何时刻访问一个共享数据 读复制 Read Replicatin 算法扩充了迁移算法 即复制数据块并且允许多个结点具有读访问或一个结点具有读写访问 多个读者 一个作者协议 见图 7 4 图 7 4 读复制 由允许多个结点并发地访问数据 读复制可以改善系统性能 但是 写操作是昂贵的 因为一个共 享块在各种结点上的所有副本将或者不得不是无效的 或者用当前值来更新以维护共享数据块的一致性 在读复制算法中分布式共享内存必须追踪所有数据块副本的位置 在 IVY 系统中 一个数据块的拥 有者结点追踪具有该数据块的一个副本的所有结点 在 PLUS 系统中 一个分布式链接列表用来追踪具有 该数据块的一个副本的所有结点 然而 当读对写的比例是大的时候 读复制有减少读操作平均费用的潜力 在节描述在 IVY 系统中 实现的许多读复制算法 7 3 47 3 4完全复制算法完全复制算法 完全复制算法是读复制算法的一种扩充 见图 7 5 读复制算法它允许多个结点具有对共享数据 块的读和写两种访问 多个读者 多个作者协议 由于许多结点可以并发地写共享数据 对共享数据的 访问必须被控制以维持它的一致性 维持一致性的一个简单方法是利用一个无间隙的顺序器 gap free sequencer 在这种方案下 所 有希望修改共享数据的结点将发送修改给一个顺序器 这个顺序器将赋予一个顺序号并且多点广播这个修 改及顺序号到所有具有该共享数据项副本的结点 每个结点以顺序号次序处理修改请求 在一个结点上一个修改请求的顺序号和期待的顺序号之间的 间隙指示一个或多个修改已被遗漏 在这种情况下结点将被请求重新传送已经遗漏的修改 这蕴涵在某个 结点保留修改的日记 在第 5 节将讨论若干其它维护共享数据的一致性的协议 图 7 5 完全复制算法 7 47 4 存储一致性存储一致性 Memory Memory coherence coherence 为了改善性能分布式共享内存系统依赖复制共享数据项和允许在许多结点上并发访问 但是 如果 并发访问不仔细地加以控制 内存访问可能以不同于程序员所期望的次序被执行 非正式讲 一个内存是 一致的 如果由读操作返回的值总归是程序员所期望的值 例如 对一个程序员期待一个读操作返回一个最近写操作所存贮的值是相当自然的 因此 为了维护共享数据项的一致性 一个控制或同步访问的机制是必要的 同样为了写正确的程 序 程序员需要理解如何进行对共享内存的并发更新 允许的内存访问次序集合构成了存储一致性模型 字一致性用于说明一种特殊类型的一致性 存储一致性最直观语义是严格一致性 strict consistency 其定义如下 一个读返回最近写的 值 严格一致性要求具有决定最近写的能力 依次它蕴涵请求的全序 由于比一个程序可能实际需要更多 的数据移动和同步要求 请求的全序导致非有效性 请参考 4 为了解决这个问题 某些分布式共享内存系统企图由提供不严格的一致性语义来改善性能 下列是 几种内存一致性形式 顺序的一致性 Sequential consistency 一般一致性 General Consistency 处理机一致性 Processor consistency 弱一致性 Weak consistency 释放一致性 Release consistency 精品文档 181欢迎下载 7 4 17 4 1顺序的一致性 Sequential Sequential consistency consistency 一个系统是序列的一致性 如果所有处理机任何操作执行的结果是和它们以顺序次序执行一样 并 且每个单个处理机的操作以其程序规定的次序出现在这个顺序中 7 4 27 4 2一般一致性一般一致性 一个系统支持一般一致性 当每个处理机所执行的所有写已被完成时 如果一个内存位置的所有副 本最终地包含同样的数据 7 4 37 4 3处理机一致性处理机一致性 由一个处理机发出的写以他们所发出的同样次序被观察到 但是 从两个进程写的次序出现作为由 它们自身或第三个处理机所观察到的次序不一定相同 即从不同的处理机的同时对同样的位置的两个读可 以产生不同的结果 7 4 47 4 4弱一致性弱一致性 同步访问 访问要求执行同步操作 是顺序一致的 在一个同步访问可以被执行之前 所有以前正 常的数据访问必须完成 在一个正常的数据访问可以被执行之前 所有以前同步访问必须完成 这实质上 把一致性问题留给程序员决定 在一个同步操作之后 内存将立即是一致的 7 4 57 4 5释放一致性释放一致性 释放一致性本质上和弱一致性相同 但是同步访问必须仅是处理机一致的 同步操作被分裂成获得 acquire 和释放 release 操作 所有悬而未决的获得 例如 一个锁操作 必须在一个正常访问完成之 前完成 并且所有正常访问必须在一个释放 例如 一个去锁操作 完成之前完成 在同一处理机内的局 部依赖性必须仍然遵守 释放一致性是弱一致性的进一步放宽而又不丢失一致性 事实上 释放一致性由包含下列次序的放 宽而区别于弱一致性 正常的数据访问不 必等待释放操作完成 因为释放操作标 志正常的访问完成并 且不 涉及访问的次序 获得操作不必等待以前的正常的访问完成 同步操作仅要求是处理机一致的的 而非顺序一致的 7 57 5 一致性协议一致性协议 为了提供并发访问 分布式共享内存系统数据复制 其中数据的副本在所有访问该数据的结点上维 护 数据复制的一个基础问题是确保所有副本具有同样的信息以及结点没有访问过时的数据的困难性 换句话说 需要一个保持复制一致的协议 两个维持一致性的基本协议是写 使无效协议和写更新协议 7 5 17 5 1写写 使无效协议使无效协议 WRITE INVALIDATE WRITE INVALIDATE PROTOCOL PROTOCOL 在写 使无效方法中 一个对共享数据的写 在写能够进行之前 引起那个数据除了一个之外的所有 副本使之无效 一旦无效 副本不再可访问 这种方案的一个主要缺点是无效被发送到所有具有副本的结 点 而不管它们是否将使用这个数据 这个协议较好地适合于几个更新出现在读之间这类应用 以及一个程序显示了高度的每个结点引用 局部性 另一方面 如果许多结点频繁地访问一个对象 这个协议是低效率的 因为一个更新的对象在每 次无效后 将不得不被立即复制回许多结点 写 使无效协议已经被用于大多数分布式共享内存系 统 IVY 27 Clouds 34 DASH 26 Memnet 12 Mermaid 41 和 Mirage 18 其中 IVY 支持严格一 致性 DASH 支持释放一致性 7 5 27 5 2写更新协议写更新协议 WRITE UPDATE WRITE UPDATE PROTOCOL PROTOCOL 在写更新方法中 一个对共享数据的写引起那个数据的所有副本被更新 这种途径比前一种途径更 难实现 因为一个新值不得不被发送以代替使无效消息 这个协议可以期望产生相当网络交通 在 PLUS 系统中的高速缓存一致性 Cache coherence PLUS 系统采用写更新协议和支持一般一致性 8 一个运行在每个结点上的内存一致性管理程序 memory coherence manager 简称 MCM 负责维护一致 性 复制的单位是页 在目前的实现中每页 4 字节 但是 内存访问和一致性维护的单位是一个 32 位 字 7 5 37 5 3PLUSPLUS 系统系统 在 PLUS 系统中一个虚页对应于一页的一个复制品的列表 复制品之一被设定为主副本 master copy 在每个结点上的 MCM 通过一个称为副本列表 copy list 的分布式链接列表知道一页的其它复制 品 副本列表由操作系统内核构造 在每个结点上有两个指针 主指针和下一个副本指针 主指针指向存 放主副本的结点 下一个副本指针指向沿着副本列表包含该页的另一个复制品 如果有此复制品 的结 点 读操作 在一个读失败时 如果地址指示本地内存 本地内存被读 否则本地 MCM 发送一个读请求 给在规定的远程结点上的对手 由远程 MCM 返回的数据被传回到请求处理机 写操作 为了保证一般一致性 在主副本上总归首先执行写 然后传播到副本列表所链接的副本 在一个写失败时 如果本地副本不是主副本 则更新请求被发送到包含主副本结点以便更新 然后进一步 传播 在一个写失败时 如果地址指示一个远程结点 即无本地副本出现 则更新请求被发送到远程结 点 在图中 一个写请求从结点 4 发送到结点 2 如果在那个接点上的副本不是主副本 则更新请求被 发送到包含主副本的结点以便更新然后进一步传播 在图中 结点 2 不是 X 的主副本 把写请求传向结 点 1 为了完全地追踪写更新协议 见图 7 6 精品文档 183欢迎下载 图 7 6 当执行更新操