网络分布式系统设计02.pdf

下载 第2章分布式程序设计语言 在这一章里 我们概述通用分布式程序设计语言并介绍类 C S P分布式控制描述语言 D C D L 这种语言用于描述一些控制结构 如并行的表示 进程间通信和同步 容错设计 用 D C D L表示 的控制算法在抽象层上提出 可以应用于操作系统层 语言运行时系统层或用户层 2 1 分布式程序设计支持的需求 显然 传统的顺序程序设计语言如 F o r t r a n P a s c a l和C不适合于分布式系统 这些语言不能 解决诸如并发 通信 同步和可靠性的问题 基本上 可在三个方面区分分布式程序设计和顺序程序设计 7 多个P E的使用 PE之间的合作 对局部故障的生存能力 多个P E的使用是和并行的表示相联系的 P E之间的合作包括两种类型的交互 通信和同步 通信一般包括两个或更多收发消息的进程 同步可能由于竞争 c o m p e t i t i o n 或条件 c o n d i t i o n 当几个进程试图访问系统中有限资源时就发生了竞争 这个问题称做互斥 第 4章将做详细讨论 由条件产生的同步发生在当一个进程在下述意义上依赖于其他进程时 它的进度可能被阻塞直 到系统状态的某个条件变为真 虽然分布式系统具有对部分故障的存活潜力 用户或系统设计 者还是要负责把这种潜力转化为现实 注意 上述问题可以在以下某一层次上得以解决 a 用户层 b 语言运行时层 c 操 作系统层 我们不考虑不同层次上这些问题的实现细节 而是着重于独立于层次的抽象解决方案 用于提供抽象解决方案的语言是 D C D L 它是一种框架控制驱动语言 skeleton control driven language 与模式驱动语言 P R O L O G 数据驱动语言 VA L 或需求驱动语言 F P 相比 D C D L类似于通信顺序进程 communicating sequential processes C S P 2 7 另一种分类 法把程序设计语言分为命令型和应用型 D C D L是一种面向语句和顺序的命令型语言 应用型语 言通过功能应用和绑定来表示程序 一种程序设计语言通过它的语法和语义来定义 语法定义了程序中的合法的符号串 语义 定义了每个语法结构的意义或相对于每个语法结构所要采取的动作类型 D C D L将用于描述任意 层次上的算法 附录给出了 D C D L中常用的符号列表 D C D L中每个结构的意义不通过形式语义 模型如操作型 公理型和指称型语义来描述 而是通过后面几节中的实例来描述 2 2 并行 分布式程序设计语言概述 我们要把分布式程序设计语言和并行程序设计语言区分开来 分布式程序设计语言必须考 虑通信的开销而并行程序设计语言通常工作在共享存储器上 这一章我们只讨论分布式程序设 计语言而不涉及主要针对并行计算的并行程序设计语言 在并行程序设计语言中 信号量和管程主要用于同步对共享存储器的协同多路访问 一个 信号量 1 8 是一个非负整型变量 在它上面定义了两种操作 P操作 等待 和V操作 发信号 对共享存储器的每次访问都必须在一个 P操作之后和一个 V操作之前 管程 2 5 定义了一套资源和 管理这些资源的操作 资源只能通过管程自身定义的操作来访问 在分布式程序设计语言中 语言本身就使得问题的分解变得和通信细节一样明显 其中 C S P 2 7 对其他面向消息传递系统的程序语言的设计有重大的影响 一些程序设计语言介于以上两种模型之间 比如 协同式语言中 问题的分解是显式的 但一些通信细节被隐藏起来了 最好的例子是 L i n d a 1 5 它通过提供元组空间 tuple space 的 抽象去耦 d e c o u p l e 通信中的接发双方 通过访问元组空间可以得到其他线程事先放在其中的 值 发送方线程无需知道接收方线程甚至无需知道接收方线程是否存在 通过引入更高层的抽 象 页面空间 以上概念已经被扩展到W W W的框架 1 7 S k i l l i c o r n和Ta l i a 4 3 给出了并行模型的分类 允许编写任意计算的任意计算结构 a r b i t r a r y computation structures 和限制计算的形式从而限制通信量和通信类型的限制计算结构 restricted computation structures 在限制计算结构中 数据并行程序设计语言由于它们在为高 性能计算和通信 H P C C 应用所进行的数值计算中的广泛应用而得到重视 它们中的大部分是 流行的C C 和F o r t r a n的扩展 例如 在欧洲 欧洲联盟 Europe Consortium 基于主动对 象 active object 定义了并行C 在日本 建立了M P C 程序 2 9 来为C 编译器的用户 层扩展提供强大的机制 在美国 H P C 联盟正在开发H P C 8 作为可移植并行C 的标 准模型 它是一个C 库和语言扩展框架 在 F o r t r a n的修订版本中 Fortran 77和Fortran 90 1 已成为A N S I标准 而高性能F o r t r a n论坛 H P F 3 8 正在开发一种事实上的标准 有一些分布式程序设计的标准 如 M P I 消息传递接口 3 9 和P V M 并行虚拟机 2 4 P V M 是分布式计算的事实标准 M P I被认为是未来的消息传递标准 一般认为 M P I在大型系统中的速 度更快 它比P V M有更多的点到点通信和组通信的可选项 如果算法依赖于某个特别的通信可 选项的话 这一点就显得很重要 当应用运行在异型网络上时 P V M则表现得更好 它具有不 同主机间的良好的互操作性 P V M支持容错应用的开发 容错应用在主机或任务出现故障时能 继续工作 由于P V M模型是建立在虚拟机的概念上 它提供了一套强大的动态资源管理和进程 控制功能 并行 分布式程序设计的工具正在成熟 这些工具包括 a 代码并行化辅助工具 b 创 建程序的G U I 图形用户接口 c 跟踪任意进程或线程状态的调试器 2 3 并行性的表示 并行性的表示有几种方法 一个重要的因素是并行性单元 一个并行性单元可以是 一个进程 一个对象 在面向对象程序设计中 一个语句 一个子句 c a u s e 在逻辑程序设计中 第2章认分布式程序设计语言部分21 下载 22部分分布式系统设计 下载 表2 1 四种基本的顺序控制机制和相应的并行机制 控制类型顺序控制并行控制 语句类型 顺序 并行语句b e g i n S1 S2e n dparbegin S1 S2parend f o r k j o i n 选择语句goto caseguarded commands i f C then S1else S2G C 重复语句for d odoall for all 子程序Procedure subroutineprocedure subroutine 表2 1表示四种顺序控制机制和相应的并行机制 并行语句可以用优先图来表示 节点代表语句 有向边代表优先关系 优先图是有向无环 图 D A G 也就是说 它是不带环路的有向图 图 2 1表示了八个语句的优先图 注意 在优 先图中不存在冗余的连接 优先顺序 如果一个优先 顺序可以从其他优先顺序导出 它就是冗余的 例如在 图2 1中 从S1到S4的连接是冗余的 因为它可以从 S1到 S2的连接和S2到S4的连接导出 也就是说 优先顺序是 传递的 一个优先顺序集合 R是非冗余的当且仅当不存 在R的子集使得它们有相同的传递闭包 直观上 当 R不 能进一步缩减时 它就是非冗余的 在D C D L中 一个并行语句表示为 S1 S2 Sn 代表语句S1 S2 S n是并行执行的 在许多并行 分 布式语言中 这种结构也表示为 p a r b e g i n和p a re n d 或 c o b e g i n和c o e n d Si 1 i n 可以是一个命令列表C 或一个D i j k s t r a保护命令 guarded command 1 9 G C 其中 G是一个由布尔表达式列表组成的保护 g u a r d C是一个命令列表 一个被保护的命令 当它的保护执行成功时 它可以被执行 在 D C D L中 顺序语句S1 S2 Sn表示为 S1 S2 Sn 在D C D L中 图2 1中的优先图可以表示为 S1 S2 S3 S4 S5 S6 S7 S8 不是所有的优先图都能用 D C D L语句表示 比如图 2 2 这个问题有三种可能的解决方法 一个简单的解决方法是把给定的优先图转换为一个更具限制性的优先图 使得它可以用 D C D L提 供的并行和顺序语句来表示 如果优先图 G 的所有优先顺序可以从G的优先顺序导出 则优先图 G比G 更具有限制性 在图 2 2中 如果我们用从 S3到S2的连接取代从S3到S5的连接 我们就可以 如下表示新的图 图2 1 八个语句的优先图 S1 S3 S2 S4 S5 S6 注意 从S3到S5的连接可以用从S3到S2的连接和从S2到S5的连接导出 新图是原图的限制性版本 自然 从S1到S2的连接就成了冗余的了 限制性图可能会 失去一定程度的并行性 第二种解决方法使用了一种更有效的结构 f o r k j o i n 实际上 任何优先图都可以用 f o r k j o i n语句表示 fork L 指令在一个程序中产生两个 或更多 的并发执行 一个 执行从标有L的语句开始 其他则接着 f o r k指令继续当前 的执行线程 j o i n指令有一个参数用于指出要结合 j o i n 的线程数 除最后一个线程外的所有线程在到达 j o i n语句 时退出 对于图2 2中的优先图 其相应的使用f o r k和 j o i n 语句的程序如下 s1 c1 2 fork L1 s2 c2 2 fork L2 s4 go to L3 L1 s3 L2 j o i n c1 s5 L3 j o i n c2 s6 注意 以上解决方法中每个计数器 如 c1和c2 的初始化可以放在相应的结合语句执行前 的任何地方 当需要产生几个线程时 可以使用 f o r k L1 L2 L n 来产生n个新的线程 这种结构和n个顺序语句等价 f o r k Li 其中1 i n 第三种解决方法使用了 p a r b e g i n p a r e n d语句和信号量 这种结合与 f o r k j o i n语句有同样的表 示能力 信号量可用于管理一组资源 更正式地讲 信号量是一个具有两个操作 P操作和V 操作的对象 P操作得到与信号量相关联的资源的一个拷贝 而 V操作则释放该资源的一个拷贝 如果信号量忙 也就是说 它已经用完资源的拷贝 那么请求进程 发出 P操作的进程 将被 中断直到资源被释放 当另一个进程对信号量执行 V操作时 被中断的进程将被释放并允许访问 第2章认分布式程序设计语言部分23 下载 图2 2 不能用DCDL语句表示的优先图 原文为V 译者注 资源 信号量s的一种典型实现是使用一个非负整数 V s 操作对s加一 P s 对s减一 如 果s是正数 这个操作成功 如果它是零 那么执行 P操作的进程将被中断直到信号量变为正数 二元信号量s是一种特殊的信号量 其中s只能是0或1 为了表示优先图 将使用多个二元信号量 优先图中的每条连接一个 对于两个语句 Si和Sj 并且Sj直接跟在Si后面 将使用信号量 si j Si完成时将对si j发出V操作 类似地 Sj执行前将对si j发 出P操作 信号量可以被认为是一个锁 一个语句只有当它通过 P操作从所有它前面的语句获得 许可时才能开始执行 当一个语句结束时 它必须把许可授予它的所有直接后继 也就是说 通过相应信号量上的V操作把锁的钥匙授予其每个后继 根据以上修改 每个语句 Si变为 S i 一系列P操作 Si 一系列V操作 然后 所有这些S i 通过一个没有任何进一步限制的并行语句连接 实际上 所有优先关 系的限制通过定义在每个S i 中的信号量得以实现 图2 2优先图中的每个节点可以表示为 S 1 S1 V s1 2 V s1 3 S 2 P s1 2 S2 V s2 4 V s2 5 S 3 P s1 3 S3 V s3 5 S 4 P s2 4 S4 V s4 6 S 5 P s2 5 P s3 5 S5 V s5 6 S 6 P s4 6 P s5 6 S6 所以 该优先图的程序如下 所有二元信号量初始化为零 S i 1 6 S i 1 6 代表六个顺序语句S i 1 i 6 的并发语句 并行进程的执行也可以用类似的方法表示 P1 P2 Pn 其中 P1 P2 Pn是每个进程的名字 每个进程在别处定义 所以 D C D L可以在进程级和 语句级描述并行性 假设每个进程由几个顺序语句组成 这些进程的并行执行产生了这些进程 中的所有语句的排列 只要这种排列保持语句在其原来进程中的顺序 例如 对于P1 p1 1 p1 2 和P2 p2 1 p2 2 p2 3 语句 P1 P2 产生以下排列之一 p1 1 p1 2 p2 1 p2 2 p2 3 p1 1 p2 1 p1 2 p2 2 p2 3 p1 1 p2 1 p2 2 p1 2 p2 3 p1 1 p2 1 p2 2 p2 3 p1 2 p2 1 p1 1 p1 2 p2 2 p2 3 p2 1 p1 1 p2 2 p1 2 p2 3 24部分分布式系统设计 下载 p2 1 p1 1 p2 2 p2 3 p1 2 p2 1 p2 2 p1 1 p1 2 p2 3 p2 1 p2 2 p1 1 p2 3 p1 2 p2 1 p2 2 p2 3 p1 1 p1 2 一个选择语句表示为 G1 C1 G2 C2 Gn Cn 选择语句选择其组成的被保护的命令之一执行 如果多于一个命令可被选择 选择将是不 确定的 1 3 2 1 实例2 1 x y m x y x m y 如果x y 将x赋予m 如果y x 将y赋予m 如果x y并且y x 将x或y之一赋予m 一个重复语句指定其组成选择语句的交互次数 这些语句带保护或不带保护 它的形式如 下 带保护的选择语句 当所有的保护都经过时 重复语句终止 即 不带保护的选择语句 后者的执行不终止 我们如何表示要终止执行的传统程序呢 我们用的方法是区别程序的 执行 正执行语句的无限序列 和程序的实现 正执行语句的无限序列的有限前部 程序的某 个状态称为固定点 当且仅当在这个状态下程序中任何语句的执行都不改变程序的状态 程序 在固定点时的结果就是相应程序的结果 n 选择语句 是一个特别的重复语句 其重复的次数最多为 n 注意 当语句中的所有保护 如果存在 失败 时 这个语句仍然可能在重复执行其选择语句 n次前终止 实例2 2约会时间问题 1 6 这个问题是为三个参与者 A B C安排合适的约会时间 初 始时 建议的约会时间t为零 如果一个参与者不能在该时间赴约 他或她就分别通过 a b c把 建议的约会时间值t增加为下一个可能的时间 在固定点 r将是一个公共的约会时间 约会时间调度 t 0 t a t r b t r c t 符号 代表一个函数 或过程 的定义 在这个程序中 不确定地选择执行其中任 何一个赋值使计算继续下去 选择也必须遵守公平规则 每个赋值被无限次执行 例如 假设 以上例子被执行无限次 如果 A在每6k 6k 3 6k 4步被选中执行 B在每6k 2 6k 5步被 选中执行 C在每6k 1步被选中执行 虽然A B C被选中的概率不同 我们说这种选择仍是公 平的 公平性在分布式系统中是一个独特而复杂的问题 详细的讨论见 2 2 选择语句和重复语句可以结合使用来解决更加复杂的问题 实例2 3给出一个确定的数组b 1 m 1 n 其中1 m 1n i i 1 j 1 在计算表达式x y时 如果x为假 我们就可以不计算 y而节省时间 因为不论 y为何值 表 达式总是为假 这种优化称之为短路 实例2 4R u b i n问题 2 0 确定一个m n的矩阵a 1 m 1 n 中某一行的所有元素是否全部为 零 这是一个2维的查找问题 这个问题被R u b i n提出来作为一个用 g o t o 语句最容易解决的例 子 困难集中在如何终止嵌套循环的问题上 下面的方法说明不用 g o t o语句的简单方法也是可行 的 i 1 p m 1 i p j 1 q n 1 j q a i j 0 j j 1 a i j 0 q j j n p i j n i i 1 f o u n d i m 1 上述算法生成一个布尔变量f o u n d 如果f o u n d T 则存在这样的全零行 否则 不存在 当两个语句并发执行时 可能产生与顺序执行不同的结果 让我们先定义以下符号 R Si Si的读集 即值在Si中被引用的所有变量的集合 W Si Si的写集 即值在Si中被改变的所有变量的集合 B e r n s t e i n 9 提出了以下三个条件 对于两个并发执行的语句 S1和S2 必须满足这三个条件才 能使其结果与它们以任意次序顺序执行时的结果相同 1 R S1 W S2 2 W S1 R S2 3 W S1 W S2 我们使用S1 S2表示语句S1和S2满足这三个条件 可以并行执行 实例2 5假设S1 a x y S2 b x z 则这两个语句可以并发执行 因为 26部分分布式系统设计 下载 第2章认分布式程序设计语言部分27 下载 R S1 x y R S2 x z W S1 a W S2 b 然而 S2不能和S3 x z 1并发执行 因为 R S2 W S3 x 以上条件也称为B e r n s t e i n条件 一般 一个语句集Si 1 i n 如果两两满足B e r n s t e i n条件 那么可以并行执行 即 S1 S2 Sn i jSi Sj 我们还可以利用B e r n s t e i n条件来寻找语句中可以并行执行的最大子集 为此我们定义了一 个无向图 节点集由给定的语句集组成 如果 Si Sj 则节点Si和Sj相连 最大的语句子集对应于 最大的完全子图 实例2 6假设S1 a x y S2 b x z S3 x y z S4 c y 1 利用B e r n s t e i n条件 我们有S1 S2 S1 S3 S1 S4 S2 S4 相应的图表示在图2 3中 显然 S1 S2 S3形成最大的完全子 图 也就是说 S1 S2 S3 图2 3 Bernstein条件的图模型 2 4 进程通信与同步 分布式系统设计的一个重要问题就是如何让一个程序在不同 P E上并行运行的各部分协同工 作 这种协同包括两种类型的交互 通信和同步 原则上 分布式系统中存在两种互补的通信 方式 消息传递 允许进程交换消息 进程间的通信手段基本上提供了两种抽象的操作 发送 消息 和接收 消息 共享数据 在没有共享存储器的分布式系统中为通信提供共享数据 在 L i n d a中使用的被 称为元组空间 1 5 的分布式数据结构的概念是提供共享数据的一种方法 使用共享数据的关键问题在于防止多个进程同时修改数据 注意 在共享存储器系统中的 机制 如管程和信号量不能被用在这里 消息传递方式的实现一般要求对以下几点做出决策 一对一还是一对多 同步的还是异步的 单向通信还是双向通信 直接通信还是间接通信 自动缓冲还是显式缓冲 隐式接收还是显式接收 一对一消息传递也称为点到点消息传递 而一对多消息传递支持高效的广播和组播方式 3 4 在同步消息传递时 发送方被阻塞直到接收方收到消息 在异步消息传递中 发送方不等待接 收方 单向通信体现了发送方和接收方间的一方面的交互 而双向通信则意味着发送方和接收 方间的多方面的交互 包括后向的和前向的 直接通信和间接通信的区别在于发送方消息是直 接还是间接发送给接收方 间接发送通过一个中间对象 通常称为邮箱或端口 邮箱支持多个发送方和接收方共享同一个存储单元 端口是一种特殊的邮箱 通常隶属于 发送方或接收方 当端口隶属于发送方时 它支持一个发送方和多个接收方 当端口隶属于接 收方时 它支持多个发送方和一个接收方 通常端口是一个由内核维护的有限的先进先出 F I F O 队列 在许多情况下端口和邮箱可以互换使用 在通信方式中 如果发送方和接收方互相指定对方 则这种通信方式是对称的 如果只有 发送方指定接收方 则这种通信方式是不对称的 显式缓冲要求发送方说明接收方用于容纳消 息的缓冲区的大小 以便确知消息来源 发送方 而隐式接收不考虑消息的来源 有五种常用的消息传递模型 7 同步点对点 异步点对点 会合 远程过程调用和一对多 同步点对点方式被O c c a m程序设计语言 1 4 所采用 它使用了发送方和接收方间的单向通信 利用发送和接收原语编写程序相对困难 因为程序员必须考虑许多细节 如请求消息和响应的 一一对应 数据的表示 了解远程处理机或服务器的地址 考虑通信故障和系统故障 两种常 用的更高层的通信结构是会合 用于 A d a 和远程过程调用 R P C 用于D P 2 6 R P C使用双向 通信 类似于客户 服务器模型 在客户 服务器模型中 客户请求服务并等待服务器的结果 这 两种方法的不同点在于在R P C中 调用者或发送方被阻塞而在会合中不被阻塞 对 R P C的详细研 究将在下一节讨论 一对多的消息传递不常用 虽然有些语言如广播顺序进程 B S P 2 3 使用这 种方式 到目前为止讨论的问题都是逻辑上的或是在应用软件层上的 作为基础的硬件层和网络层 存在更多的实现方面的问题 这些问题包括 4 0 如何建立通信链接 一个通信链接能否同两个以上的进程联系 在每一对进程间该有多少链接 一个链接的通信能力如何 消息的大小如何 定长还是变长 链接是单向还是双向的 这些问题的详细讨论超出了本书的范围 接下来我们将集中讨论 D C D L提供的用于进程通信 和同步的命令 在D C D L中采用了异步点到点消息传递 消息通过异步静态通道 链路 传递给指定的接收 方进程 一个输出命令的形式如下 send 消息列表 t o 目的地 其中 目的地是一个进程名 一对一通信 或代表所有其他进程 一对全通信 的关键字a l l 28部分分布式系统设计 下载 一个输入命令有如下形式 re c e i v e 消息列表 f ro m 信源 其中 信源是一个进程名 可选 这个输入命令支持显式和隐式的消息接收 隐式的消息接收 表示为 re c e i v e 消息列表 异步静态通道 链路 是两个进程间的一个 F I F O队列 除非另外说明 否则我们假设任意两个 进程间只有一个通道 注意 同步通信可以通过异步通信来模拟 在发送方 我们有 s e n d 消息列表 t o 目的地 receive 空信号 f ro m 目的地 在接收方 我们有 re c e i v e 消息列表 f ro m 发送方 s e n d空信号 t o 发送方 以上结构可以扩展以实现屏蔽同步 用多种迭代算法依次计算解的更好逼近值 直至得出 最后解或者迭代已经收敛 每次迭代依赖于上一次的结果 注意 带真保护的迭代对应于一个 周期性的进程 true 实现进程Pi的代码 等待所有的n个进程完成 在上述算法中 t ru e是一个布尔常量 它总是返回真值 也就是说 条件总是满足 这种类 型的同步称为屏蔽同步 3 1 每次迭代结束时的延迟点体现了屏蔽 所有进程到达这个点后才允许 任意一个进程通过 在非对称实现中 有一个进程被称为协调者 其余的是工作者 当协调者收到每个工作者 的消息时给所有的工作者发一个特别的信号 工作者 i t ru e 实现进程Pi的代码 s e n d s i g n a l t o 协调者 re c e i v e a c k f ro m 协调者 协调者 t ru e c o u n t e r 0 c o u n t e r n 第2章认分布式程序设计语言部分29 下载 re c e i v e d s i g n a l counter c o u n t e r 1 s e n d a c k to all 要构造一个对称的屏蔽 每个进程中代码相同的屏蔽 我们可以利用两个进程的屏蔽作为 构件 假设b a rr i e r Pi Pj 是进程Pi和Pj之间的屏蔽同步 如上面的实例之一 对于八个进程 的屏蔽如下 阶段1 b a rr i e r P1 P2 b a rr i e r P3 P4 b a rr i e r P5 P6 b a rr i e r P7 P8 阶段2 b a rr i e r P1 P3 b a rr i e r P2 P4 b a rr i e r P5 P7 b a rr i e r P6 P8 阶段3 b a rr i e r P1 P5 b a rr i e r P2 P6 b a rr i e r P3 P7 b a rr i e r P4 P8 它的图示如图2 4 下面的例子给出了更多D C D L中发送和接收命令的使用 图2 4 三阶段对称屏蔽 实例2 7s q u a s h 2 7 s q u a s h程序用一个上箭头 代替每一对连续的星号 假设输 入的最后一个字符不是星号 squash re c e i v e c f rom input c s e n d c t o o u t p u t c receive c f rom i n p u t c s e n d t o o u t p u t s e n d t o output c s e n d t o o u t p u t 30部分分布式系统设计 下载 阶段1 阶段2 阶段3 i n p u t 输入 进程是一个重复命令 input s e n d c t o squash o u t p u t 输出 进程是另一个重复命令 output re c e i v e c f rom squash 在一个重复命令中使用接收命令作为保护时 保护的执行将被延迟直到相应的发送命令被 执行 一个保护中有接收命令的命令只有在相应的发送方终止时才终止 实例2 8我们可以用如下递归的方法计算f n f n 1 n2 n 1并且f 1 1 p i 1 n receive m f rom p i 1 m 1 s e n d 1 t o p i 1 m 1 s e n d m 1 t o p i 1 re c e i v e r f rom p i 1 send m m r t o p i 1 p 0 s e n d n t o p 1 re c e i v e result f rom p 1 f n 的解法是所有n 1个进程的并行执行 p i 0 n 在上述解法中 n 1个进程用于解决该问题 见图 2 5 这种方法只能用于举例说明进程间 通信的使用 绝非一个有效的方法 p 0 是一个用户程序 把n送给p 1 并从p 1 接收结果f n 每个p i 计算f n i 1 1 i n 活动的p i 数取决于n 图2 5 实例2 8的递归解法 一种方法可以只使用一个进程解决这个问题 f n 的定义可以容易地转化为一个递归过程来 计算f n 第2章认分布式程序设计语言部分31 下载 结果 32部分分布式系统设计 下载 p n a n s ans 1 n 0 skip n 0 p n 1 a n s a n s a n s n n 在以上解法中 f n 的结果存放在变量 a n s中 递归对于导出问题的简单解法特别有用 同 时 至少在理论上 任何递归程序都可以用迭代的形式编写 反之亦然 实际上 这样做可能 更有意义 也许是空间和时间效率的问题推动了迭代的使用 f n i n a n s 1 i 1 ans a n s i i i i 1 实例2 9D C D L也可用于实现一个二元信号量s Semaphore s v a l 0 receive V f rom p roc i val v a l 1 val 0 receive P f rom p roc i v a l v a l 1 其中 p ro c i 是向信号量s请求P或V操作的进程 对于某些其他问题 还存在几个解决不同进程间的通信结构的方法 实例2 1 0F i b o n a c c i数列是由递推公式F i F i 1 F i 2 i 1 定义的一列整数 其初 始值F 0 0 F 1 2 我们提供一个F i 的D C D L实现 每个F i 一个进程 我们再一次定义一系列进程 f i 用于计算F n i 1 显然 如果n i 1 1 f i 取决于f i 1 和f i 2 的计算结果 一个自然的解法就是如果 n i 1 大于1 f i 从f i 1 接收 n i 1 并把 n i 传递给f i 1 然后f i 等待f i 1 和f i 2 的结果 把它们相加 并把 相加的结果传递给f i 1 和f i 2 见图2 6 图2 6 F n 的解法 f 0 s e n d n to f 1 receive p f rom f 2 receive q f rom f 1 ans q f i receive n f ro m f i 1 n 1 s e n d n 1 to f i 1 receive p f rom f i 2 receive q f rom f i 1 send p q to f i 1 send p q to f i 2 n 1 send 1 to f i 1 send 1 to f i 2 n 0 send 0 t o f i 1 send 0 t o f i 2 f 1 receive p f rom f 1 在上述算法中 f 0 是U S E R f 1 是虚进程 如果我们把f i 中的语句send p qt o f i 2 改成 i 1 s e n d p q to f i 2 则f 1 可以删去 第二个解法使通信只局限于邻居之间 即 f i 只能和f i 1 和f i 1 通信 见图2 7 图2 7 F n 的另一种解法 f 0 n 1 s e n d n t o f 1 receive p f rom f 1 receive q f rom f 1 ans p n 1 ans 1 n 0 ans 0 f i re c e i v e n f rom f i 1 n 1 send n 1 t o f i 1 receive p f ro m f i 1 receive q f rom f i 1 第2章认分布式程序设计语言部分33 下载 send p q to f i 1 send p to f i 1 n 1 send 1 to f i 1 send 0 to f i 1 2 5 远程过程调用 分布式系统的基本通信范例是输入和输出 上一节讨论的 s e n d和re c e i v e命令 然而 有些 程序员更喜欢集中式系统中没有显式通信原语的编程风格 所以引入了远程过程调用 R P C 1 2 它具有发送和接收命令的功能但看起来很像一个本地过程调用 R P C的一般实现如下 当一个程序需要从一个文件中读取数据 而该读操作是一个远程过程 时 一个客户桩模块 client stub 被置入库中 在读操作调用之后 客户桩模块把调用参数包 装在一个消息中并调用远端的服务器桩模块 server stub 接着阻塞自身直到响应到达 当消 息到达服务器时 服务器桩模块解开消息并调用服务器过程 仿佛它是被客户直接调用似的 服务器执行被请求的工作并把结果返回给调用者 服务器桩模块 调用完成后服务器桩模块重 新得到控制并把结果包装后返回给客户 当消息到达客户时 由内核把消息拷贝到等待缓冲区 并激活客户进程 客户桩模块解开结果并把它拷贝给它的调用者 当调用者得到控制时 它所 知道的只是它所要求的数据已经得到了 至于是在本地还是在远端做的工作它一无所知 然而 基本的R P C有以下一些缺陷 通信开销 当客户用同样的数据调用几个过程时 每次调用都要传送一次该数据 因为 R P C不支持远程对象 在嵌套过程调用时 每次中间调用的结果都必须被传回给客户再发 送给服务器 缺乏并行性 R P C的语义很简单 但它的执行是顺序的 调用者被挂起直到获得结果 缺乏灵活性 一个R P C的客户只能使用有限的几种服务 每个新的过程都必须由有经验的 程序员准备并安装好 有很多对基本R P C的扩展 然而 许多扩展 R P C为了包含并行特性 5 导致复杂的语义 结果 反而失去了R P C的主要优点 L i s k o v和S h r i r a 3 6 提出的异步R P C已成功地在M I T的M e r c u r y通信系 统上实现 B e r s h a d 1 0 提出的轻量级R P C通过利用线程的概念来提高性能 线程又叫做轻量级进 程 多个线程可以共享同一个地址空间 在这样一个系统中 一个 重量级 进程包含一个地 址空间和一个或多个控制线程 每个线程有自己的程序计数器 寄存器状态和栈 每个线程可 以独立地进行远程过程调用 在 4 2 中可以找到R P C的其他扩展 它支持对多个服务器的并发访 问和对多个请求的同时服务 另一种与R P C接近的机制是远程求值 remote evaluation R E V 4 4 它允许把几个过程 代码和数据 封装在一个过程里传到远程地点就像 R P C中的过程调用一样 相应的远程地点执 行被封装的过程 在封装过程中传送的数据可以被封装过程中的过程多次使用 而且产生的中 间结果 如果有 也不必传回客户 但是如果不能有效利用以上这些优点 由于过程 代码和 数据 的频繁传送反而会增加通信开销 而且 重定位也是个问题 特别是在异型系统中 因 34部分分布式系统设计 下载 为要把可执行代码从一台机器移植到另一台指令集和数据表示都不相同的机器上并非一件容易 的事 最近又提出了一种上下文驱动调用 context driven call C D C 4 8 模型 它是著名的R P C的 扩展 但结合了 R P C和R E V的优点 类似于 R P C C D C允许一系列过程位于一个远程处理机上 并通过和本地过程一样的语言结构 一个过程调用 来调用 但C D C采用了不同的实现机制 另外 C D C支持个别向远程地点传送数据和从远程地点接收数据的机制 程序员无需关心这些 数据的移动 C D C支持两种类型的数据对象 本地的和远程的 本地对象是分配在当前主系统 m a s t e r 的地址空间的一个变量 远程对象是分配在从系统 s l a v e 的地址空间的一个变量 为了对一 个带远程变量的表达式进行本地或远程求值 C D C发送数据给远程地点 远程求值并从远程地 点接收数据 特别地 对一个一般的表达式 x e x1 x2 xn 其中至少包含一个远程对象 如 果它是在本地求值 本地地点需要从远程地点接收输入数据 如果有 执行本地求值 最后如 果x是一个远程对象的话就把 结果 数据送回远程地点 如果表达式是在远程求值 本地地点 需要先把输入数据发送到相应的远程地点 由远程地点执行远程求值 最后如果 x是本地对象的 话 本地地点从远程地点接收结果 类似的情形同样适用于带远程对象的过程 void f x1 x2 xn 的本地或远程求值 当远程对象来自不同的远程地点时进行本地求值 这种情况下本地地点 从远程地点接收 远程 数据并执行本地求值 当所有的远程对象来自同一个远程地点时进行 远程求值 这种情况下本地地点把 本地 数据发送给远程地点并在那里执行远程求值 为了支持以上操作 我们介绍以下函数 这些函数可以从客户端 本地地点 向服务器 远程地点 请求 rcreate 在远程地点创建一个确定大小的远程对象 以一个唯一的名字 句柄 命名该对 象 并返回句柄给调用者 rremove 根据输入的对象句柄删除一个远程对象 rread 根据输入的对象句柄和缓冲区地址把一个远程对象拷贝到本地缓冲区 rwrite 根据输入的对象句柄和缓冲区地址把本地缓冲区的内容拷贝到一个远程对象 rfork 是一个非阻塞调用 它调用远程桩模块来产生一个新的线程并把远程对象的地址作 为参数传递给它 以上函数用于实现各种表达式和过程的求值 例如 rcreate 和 rwrite 分别用于创建和初 始化远程对象 对远程过程的调用通过 rfork 实现 rread 用于客户获得一个远程对象的值 客户通过rremove 释放一个远程对象的存储空间 D C D L中不包括以上任何机制 我们尽量保持发送命令和接收命令的简单 使读者能够把重 点放在D C D L描述的算法上 2 6 健壮性 与集中式系统相比 分布式系统有更高的可靠性和有效性 但要达到这种可靠性仍然是操 作系统 语言运行时系统和程序员的责任 分布式系统中有两种用于实现可靠性的方法 程序设计容错 第2章认分布式程序设计语言部分35 下载 通信容错 这两种方法是相关的 程序设计容错可以通过向前恢复 forward recovery 或向后恢复 backward recovery 实现 向前恢复试图确定错误所在并基于这个知识改正包含错误的系统状 态 11 高级语言如 A d a P L 1和C L U中的异常处理提供了支持向前恢复的系统结构 向后错误 恢复通过把系统恢复到错误发生前的状态来改正系统状态 恢复阻塞方案 recovery block s c h e m e 2 8 提供了这样一个系统结构 另外一个常用的程序设计容错技巧是错误屏蔽 n版本 程序设计 N version programming 6 利用同一个算法独立开发的几个版本 一个最后投票系 统将用于这 n个版本产生的结果并最终产生一个正确的结果 目前为止还没有支持向后恢复方 案的商用语言 尽管有些研究人员提出了一些语言框架 3 0 3 2 和底层的支持机制 如恢复缓冲 3 和恢复元程序 2 通信容错处理进程通信中发生的故障 通信容错依赖于使用的通信方式 消息传递还是R P C 和故障的类型 故障 停止类型 4 1 还是拜占庭类型 3 3 通常 有四种类型的通信故障 1 一个节点发出的消息没有到达它的目的地 2 消息不是按原来发送的顺序接收的 3 消息在传送过程中被破坏 4 消息在传送过程中被复制 第2 3 4种情况可以通过顺序号 数据加密和校验和来解决 然而 确定出错的原因并非 易事 例如 如果一个调用异常终止 计时器超时 有四种互斥的可能性 1 接收方没收到调用消息 2 响应消息没到达发送方 3 接收方在调用执行过程中崩溃 并且一直保持崩溃状态或崩溃恢复后没有继续原调用的 执行 4 接收方仍在执行调用 在这种情况下 该执行将干扰客户后来的活动 最简单的通信容错是使用故障 停止模型的消息传递 其中 P E要么正常工作要么完全停 止 容错是通对检测故障并随之对系统进行重新配置实现的 4 以下是用D C D L描述的故障检测 过程 4 7 sender s e t u p time t send diagnostic signal to receiver receive ack f ro m receiver status normal t i m e o u t t s t a t u s a b n o r m a l 通过上述高层D C D L算法 一个有故障的P E将被发送方节点通过检查状态变量的值发现 基于R P C的通信有副作用 所以准确地指明一个调用的语义是很重要的 各种可靠性语义已 经在R P C的上下文中提出 正好一次 e x a c t l y o n c e 最后一个 l a s t o n e 至少一次 a t l e a s t o n c e 多个中的最后一个 l a s t o f m a n y 最多一次 a t m o s t o n c e 4 5 36部分分布式系统设计 下载 在基于对象的系统中 3 5 局部故障是通过利用原子动作的概念 3 7 来实现的 原子动作的故 障原子性保证了一个计算要么正常终止 产生期望的结果 要么被异常中断 不产生任何结果 这个问题的详细讨论见第11章 一般而言 在分布式系统中实现局部故障是一个多元行动 multidimensional activity 必 须同时解决以下部分或全部问题 故障限制 故障检测 故障屏蔽 重试 故障诊断 重配置 恢复 重起动 修复和重新集成 这方面问题的详细讨论见 4 6 和最近几年的 I E E E可靠分布 式系统会议录 the Proceedings of the IEEE Symposium on Reliable Distributed System 表2 2总结了不同语言中使用的并行性 通信和局部故障原语 7 表2 2 语言原语 Language primitive 7 原语实例语言 并行性 表示并行性 进程Ada Concurrent C Linda NIL 对象Emerald Concurrent Smalltalk 语句O c c a m 表达式Par Alfl FX 87 子句Concurrent PROLOG PA R L O G 映射 静态Occam StarMod 动态Concurrent PROLOG ParAlfl 迁移 m i g r a t i o n E m e r a l d 通信 消息传递 点到点消息C S P Occam NIL 会合 r e n d e z v o u s Ada Concurrent C 远程过程调用D P Concurrent CLU LY N X 一对多消息B S P StarMod 数据共享 分布式数据结构Linda Orca 共享逻辑变量Concurrent PROLOG PA R L O G 非确定性 选择语句C S P Occam Ada Concurrent C SR 带保护H o r n子句Concurrent PROLOG PA R L O G 局部故障 故障检测Ada SR 原子事务A rgus Aeolus Av a l o n 零 N I L 第2章认分布式程序设计语言部分37 下载 基于对象和面向对象的系统都使用对象的概念 但基于对象的系统不支持继承 参考文献 1 Adams J C W S Brainerd J T Martin B T Smith and J L Wa g e n e r F o rtran 90 Handbook Intertext Publication McGraw Hill Publishing Company 1992 2 Ancona M G Dodero V Gianuzzi A Clematis and E B Fernandez A system architecture for fault tolerance in concurrent software IEEE Computers 23 10 Oct 1990 23 32 3 Anderson