第二章分布式通信机制.ppt

1 2 1概述2 2消息传递2 3远程过程调用 第二章分布式通信机制 2 2 1概述 本章讨论分布式系统中的通信问题 在考虑这一问题时 应注意以下几个方面 发送策略 如何通过通信网发送消息 连接策略 如何去连接彼此希望通信的进程 争夺处理 由于通信网是共享资源 应注意解决在利用它的过程中那些有冲突的要求和冲突现象 保密 如何保住消息内容的秘密 通信机制 研究分布式操作系统中的基本通信机制 3 2 1 1发送策略 当场点A上的一个进程希望同场点B上的另一个进程进行通信时 如何发送消息 常用的几种发送策略是 固定发送 从A到B的信道事先已规定好并且不得更改 除非硬件的故障影响到它的通信能力 通常选择物理上长度最短的信道 以减少通信开销 虚拟线路 从A到B的信道在一段时期内是固定的 在不同时期 从A向B发送的消息可能经由不同的信道发送 动态发送 用于从A到B发送消息的信道仅当该消息发送时才确定 由于这种选择是自动进行的 单一的消息可能分给不同的信道 4 上述几种方案各有利弊 固定发送不适用于通信负载的改变 即如果已在场点A和B之间确立了一条信道 那么消息只能经由这条信道传送 即使这条信道已经超载 而其它信道还处于尚未满载的状态 可以利用虚拟线路策略进行改善或通过动态发送策略来加以完全地解决 固定发送和虚拟线路策略可以确保按消息的发送次序从A向B发送消息 采用动态发送策略 消息的到达次序不一定和消息的发送次序相一致 这可以通过给每条消息赋以一个顺序号来解决 5 2 1 2连接策略 有许多不同的方法来连接一对彼此希望通信的场点 或进程 最常用的方法有线路转换 消息转换和消息包转换 线路转换 circulateswitch 如果两个进程希望通信 那么就在它们之间设立一条永久性的物理通信链路 这条通信链路供其消息转移期间使用 在这段期间其它进程不能使用这条链路 这种方案与电话系统类似 一旦一条通话线路已对通话双方开通 例如甲方给乙方打电话 其它人就不能使用这条信道 除非甲乙两方已明显地结束其通话 例如一方已挂起话筒 6 消息转换 messageswitch 如果两个进程希望通信 那么就确定一个临时的通信链路供其消息转移期间使用 物理通信链路则根据需要在用户间动态进行分配 而且只允许使用较短的一段时间 每条消息由一个数据再加上某些系统信息 如发送处 接收处和错误校正码等 组成 这些系统信息将辅助通信网络正确地将消息转移到目的地 这种方案与邮局系统类似 每封信可看作是包含发送处和接收处的一条消息 而且来自不同用户的信件 消息 可在相同通信线路上转移 7 消息包转换 packetswitch 消息一般是可变长度的 为了简化系统的设计 常常把消息设计成定长的形式 并把这种定长的形式称为消息包 packet 一条逻辑消息可能不得不划分成若干消息包 每个消息包都可以经由网络中不同的路径单独地发送到其目的地 当这些消息包都到达其目的地后 还得拼装起来组成一条完整的消息 线路转换需要安装时间但传送每条消息的开销较少 消息转换和消息包转换需要较少的安装时间 但转移每条消息的开销较大 此外 在采用消息包转换方法时 每条消息可能得先 化整为零 然后再 集零为整 8 2 1 3争夺处理 由于一条通信链路往往连结多个场点 而这些场点有可能希望同时在这条通信链路上转移信息 从而发生争夺现象 这种情况在环结构或多存取总线结构中表现得尤为突出 解决争夺现象的技术 常用的有冲突检测 令牌转移和消息槽 9 冲突检测 一个场点要在某条通信线路上转移消息之前 它必须进行监测以确定当前在该通信线路上是否正在转移另外的消息 若该通信线路空闲 则这个场点可以开始发送 否则它必须等待 同时继续监测 直到这条线路空闲 采用这种途径的主要问题是 当系统非常忙时 可能发生许多冲突现象 因此整个系统的性能由于冲突检测方面的工作而受到衰减 这种方法已成功地用在以太网系统 10 令牌转移 TokenPassing 令牌是一个特殊的消息类型 它不断地在系统 通常在一个环结构 中循环 希望转移消息的场点必须等待直至令牌到达 当令牌到达后 该场点就从环中取走令牌并开始转移它的消息 当它完成了相应的消息转移后再重新发送令牌 这就给另一个场点提供了占有令牌的机会 一旦占有 就可开始它的消息转移 如果令牌丢失 那么系统应能发现这种情况并产生一个新令牌 该方法已由Primenet系统所采用 11 消息槽 slot 若干定长的消息槽连续不断地在系统 通常是一个环结构 中循环 每个消息槽可以容纳一定长的消息和有关的控制信息 如像发送处 接收处 消息槽满 空等 希望转移消息的场点必须等待直到一个空消息槽到达 然后 该场点将它的消息插入这个空消息槽并附上适当的控制信息 此消息在网络中继续流动 当它到达某个特定的场点时 该场点就查看此消息槽的控制信息 以确认此消息槽是否包含了发送给它的消息 若没有 它就放过此消息槽 否则 它取走消息糟中的消息 重新设置控制信息以指明该消息槽为空 12 2 1 4保密问题 编码是保护信息的常用方法之一 信息在发送之前先予以编码 当信息到达其目的地后就进行译码 编码技术 最常用的一种就是提供一个通用的编码算法E 一个通用的译码算法D 并对每次应用提供一个保密键 key 令Ek和Dk分别表示具有保密键k的那个特定应用的编码和译码算法 那么 对于任何消息m 该编码系统必须满足下面的特性 Dk Ek m m Ek和Dk都能有效地计算 该系统的保密性只依赖于键k的保密性而不依赖于算法E和D的保密性 13 一个称之为 数据编码标准 DataEncryptionStandard 的编码系统已由美国国家标准局所采用 不过 该方案还存在 键分布 问题 即 开始通信之前 保密键必须秘密地转移给发送者和接收者 但在一个通信网络环境中很难有效地完成这一点 解决此问题的办法之一是利用一个 公共键 publickey 编码方案 每个用户有一个公共键和一个私有键 两个彼此知道他们的公共键的用户才可以相互通信 基于上述思想的编码方案已设计出来了 这个方案曾被认为是差不多不可破译的 其中的公共编码键是一对偶 e n 私有键是对偶 d n 这里e d n都是正整数 每条消息用0 n 1之间的一个整数表示 较长的消息可分成若干较短的消息 它们每一个都可用这样的一个整数表示 函数E和D定义为 14 E m memodn CD C Cdmodn这里的主要问题是选择编码和译码键 整数n可用下式计算n p q其中p和q是随机选取的两个较大的素数 例如 它们是由100位或更多位数字组成 d是随机选取的一个与 p 1 q 1 互质的较大整数 即d满足GCD d p 1 q 1 1而e则应满足e dmod p 1 q 1 1应指出的是 虽然n可能是大家知道的 但p和q却很难为他人所知 因为 对这里的n进行因式分解是比铰困难的 因此 d和e也是不易试探出来的 15 例如 令p 5和q 7 那么n 35 p 1 q 1 24 由于11与24互质 所以可选取d 11 因为11 11mod24 12lmod24 1 因此 e 11 假定 给定m 3 那么C memodn 311mod35 12而Cdmodn 1211mod35 3 m因此 如果我们利用e对 进行编码 那么 我们就能用 对它进行译码 16 2 2消息传递 2 2 1消息传递原语 在分布式系统中 进程相互通信是通过彼此交换消息进行的 一个消息是从一进程发往另一些进程的信息单位 源进程通过执行send操作发送消息 宿进程则通过执行receive操作来获取消息 如果必要 在其获取消息后再通过执行reply操作给发送者一个回复 因此 分布式操作系统通常提供send receive和reply等基本通信原语来实现进程间的通信和同步 17 消息转移原语分为两类 同步型和异步型 1 异步型 在这类通信机制中 转移消息的进程不等待接收者的回复 又称 不等 转移 sendnoWait 即允许发送方可任意超前于接收方 因而具有下面的特征 接收方收到的消息与发送方目前的状态是无关的 由于通信机制与同步机制几乎被截然分开 因此 系统应具有 无限 的缓冲空间来容纳任意超前发出而尚未处理的消息 以此来解决消息发送速度和消息处理速度之间的差异 能比较充分地利用系统的潜在能力 但实现时须解决许多实际的控制问题 18 图2 2同步消息传递和异步消息传递 19 2 同步型 它与异步型消息转移正好相反 总是要求发送方等待接收方的回复 然后 发送方与接入方同步继续向下执行 其主要特征是 消息的发送方和接收方在完成信息交换后彼此知道对方的状态 同步机制和通信机制合二为一 一般无需大的缓冲区 实现容易 但效率较低 同步型消息转移和异步型消息转移示意图 见图2 2 20 消息本身要占用存贮空间 并常常存放在系统的缓冲区中 当使们异步消息转移机制时 系统中的每个进程在某一时刻可能有多个尚未处理的消息 由于消息缓冲区是一个有穷的资源 因此 当使用异步消息传递方式传递消息时 可能会发生消息缓冲区溢出的情况 因此 异步消息传递需要特定的消息缓冲区管理算法来处理这方面的问题 但在采用同步消息传递方式时 系统中的每个进程决不可能存在一个以上尚未处理的消息 因此 其消息缓冲区的管理算法比较简单 21 2 2 2同步消息传递方式的应用 同步消息转移方式特别适合于client server模型 一个client通过向一个server发送一个消息来请求该server为它服务 然后这个client就挂起 直至对应的server发来回复消息 即告之所请求的服务已经完成 server可以写成一个无穷循环程序 它等待接收请求 然后处理相应的请求 最后发回复消息 client们在等待所请求的服跟务完成时就阻塞自己 仅当没有消息给server 即没有供它做的事情时 该server就阻塞 见图2 3 其中c1ient们向time server发送一请求给出时间的消息 send time server gettime time time server循环等待请求读时钟的消息 然后执行 读时钟 工作 并在处理下一请求消息之前发出回复 即time server和client可分别编写成如下的程序段 22 timeserver whiletruedoreceive request readclock time reply time end client send timeserver gettime time 图2 3使用消息转移方式的client server模型 23 一般 server可以设计成依次重复执行下述步骤的程序段 等待接收来自clients发送的 请求服务 的消息 接收clients发来的 请求服务 的消息 处理clients发来的 请求服务 的消息 向clients发送 服务已完成 的回复消息 仅当没有 请求服务 的消息到达时 server就阻塞自己 clients在等待server的回复消息时就阻塞它们自己 从而实现了clients与server的同步 在设计server进程时 通常要求 server必须能调度和回复多个并发的请求消息 server处理请求消息和发送回复消息的次序与接收该请求消息的次序无关 在server给client发送回复消息时 决不应阻塞 某个相关的client故障 不应影响server的操作 24 同步原语有一种与信息交换不同的特性 当一个进程引用了一个挂起的原语时 它就阻塞自己直至此原语执行完毕 同步原语的这种 阻塞 特性 类似于单处理机中所使用的信号量 可用于同步目的 图2 4 a 展示了两个进程使用信号量进行同步例子 其中 当P1在信号量sem上等待时 它就彼阻塞直至P2唤醒它 一个进程等待另一进程的类似效果也可利用同步send receive原语实现 见图2 4 b 25 图2 4同步 26 还有不少其它形式的send receive原语 例如 选择性接收 selectivereceive 和 条件发送 conditionalsend 一个selectivereceive操作允许其用户选择一个进程或一组进程去接收发送来的消息 当执行conditionalsend操作时 如果相关的接收者不是处于阻塞状态正等待接收消息 那么它将立即完成而不发送消息 实际上 大多数异步send操作后紧随着一个receive操作 基于这个原因 许多分布式操作系统只提供同步消息传递原语 27 2 3远程过程调用 远程过程调用 RemoteProcedureCall 就是把过程调用的概念加以扩允后引入分布式环境中的一种形式 远程过程调用的形式和行为与传统的过程调用的形式和行为类似 主要差别在于被调用的过程实际运行在一个与调用者所在场点不同的场点上 见图2 6 因此 需要设计相应的软件来实现两者之间的连接和信息沟通 28 图2 5消息转移与过程调用的类似性 图2 6远程过程调用示意图 29 2 3 1RPC机制的结构及实现 1 RPC机制的结构由下列成份组成 stub client和server各一个 控制部分 为追踪RPC的调用状态所设 传送部分 确定如何将信息从一个场点传送到另一个场点 实现RPC的一般过程可概括如图2 7所示 图2 7实现RPC的一般过程 30 client sstub与一个client连接 它对于该client就像一个 server 在调用时 它截取client的远程过程调用命令后 利用通信网络向server发送 请求服务 的信息 在返回时 它获取返回消息 并带返回结果返回到client 然后client继续执行 31 Server sstub与一个server连接 它对于该server就像一个 client 在调用时 它收到远程调用请求后 产生一个本地调用 去执行被请求的远程过程 在返回时 它截取远程过程的返回结果 并形成返回消息发送出去 stub包含了一组RPC机制的操作原话 这些原语构成了RPC调用的实现细节 它可独立于client和server编程 在编译时再连接起来 32 RPC的实现要考虑两个方面的问题 第一 当进行远程过程调用时 调用场点必须能定位出被调用的过程实际上运行在哪个场点上 第二 相关的两个场点必须能协同合作交换信息 所有这些对用户都是透明的 这些的工作是依次进行的 下面介绍一种实现RPC的方法 其实现思想已概括在图2 8中 33 图2 8RPC的实现概况 34 每个远程过程由若干成分组成 调用者 caller 或用户 user 调用代码段以及被调用者 callee 或server被调用代码段 这些都可用常规的程序设计语言编写 不需要利用特别的设施 就象它们在同一场点上执行一样 与调用者相关的stub与被调用者相关的stubRPCruntime子程序 可在系统中所有场点上运行 2 RPC的实现 35 stub程序的功能是把这种过程调用中所带的参数组装和拆卸成消息形式 并进行相应的类型检查 然后把这些消息转移给RPCruntime子程序 后者再把它们发送到系统中的其它场点 程序设计者定义了过程并写好了过程体 而系统生成了对应的stub 实现一个远程过程调用的主要工作环节如下 36 调用者用通常方式调用对应stub中的一个过程 这个stub过程把有关的参数组装成一个消息包或一组消息包 以形成一条消息 运行此过程的那个场点的 地址 和那个场点上指称此过程的 标识符 都应包含在这条消息中 将这条消息发送给对应的RPCruntme子程序 该子程序再把它发送给指定的场点 37 在接收此消息时 远程runtime子程序引用与被调用者对应的stub中的一个子程序 并让它来处理这条消息 被调用者对应的stub中的这个子程序拆卸有关的参数并用通常的过程调用方式调用所需的过程 返回调用结果 整个远程过程调用以与调用者对应的stub程序执行 return 语句返回到用户而终止 38 在上面的述中 我们回避了一个重要的问题 即与用户对应的stub如何知道实际运行远程过程的场点之地址呢 一些解决这一向题的方法 当系统生成与调用者对应的stub时 可把该远程场地的地址也一同并入其中 不过这种做法不太灵活 在进行调用之前 与调用者对应的stub向系统中的其它场点进行广播 请求有关的场点通报其地址 这必然引起一系列的消息转移 特别 当这种广播是在若干网络之间进行时 其转移速度是很慢的 由系统管理一个表 其表项的内容为 场点地址 该场点上将运行的远程过程的名字 39 2 3 2RPC执行时各部分之间的关系 RPC执行时 各部分的关系如图2 9所示 其中 传输部分是RPC的最低层 其主要功能为 提供对网络传输层协议的选择 建立 释放逻辑信道 发送 接收消息等 管理RPC中的消息缓冲区 40 图2 9RPC执行时各部分的关系图 41 控制部分的主要功能是 确定RPC中消息的方向 发送或接收 当client的stub开始一次RPC调用或者server向server的stub返回调用结果时 该部分负责控制传输部分进行发送 场点间会合与进程同步 场点间会合是指为使两个场点间进程同步 它们必须同意 会合 rendezvous 即早到达的进程要等待晚到达的进程 会话进程通过场点间会合建立一致的起点 并以该起点作为进程同步点进行对话 若干状态信息的处理 由上可知 由于client的stub的作用 使得client可用常规过程调用方式去调用远程过程 由于server的stub的作用 使得server程序可以独立于调用者来编程 因而比较灵活 42 本地调用和远程过程调用之间存在许多不同之处 如果远程调用是在两种异型机器间进行 这就存在数据表示问题 例如 这两类机器的字长可能不同 解决这一向题的方法之一是它在转移数据之前 让RPC机制将有关的数据转换成一种统一的格式 接收场点在接收数据时 再把它们转换成本地所允许的数据格式 第二个问题是如何解释指针 更确切他说 一个指针到底访问的是什么 在不具有共享地址空间的情况下 RPC不可能允许在网络范围内转移指针 因此 在RPC中是不可能用 reference方式 传递参数的 2 3 3RPC的语义 43 更严