《高级操作系统》配套教学课件

高级操作系统1课程主要内容介绍2分布式计算机系统分布式通信机制分布式协同处理分布式资源管理分布式进程与处理机任务分配与负载平衡分布式文件系统命名服务分布式事务处理故障恢复与容错分布式共享内存3

教学要求

要求学生掌握上述主要内容中的基本概念，了解相关的一些典型算法，并就分布式操作系统中的设计模型、实现方法及有待进一步解决和探索的问题加以关注，写出相关论文。1.1分布式系统概述1.2分布式计算机系统的特点1.3分布式计算机系统的体系结构1.4分布式系统的拓扑结构1.5分布式资源管理1.6分布式操作系统4第一章分布式计算机系统1.1分布式系统概述

计算机技术发展迅猛。从1945年现代计算机时代开始直到1985年，计算机一直是庞大昂贵的设备。即便是小型计算机也要花数万美元。这使得大多数机构通常只有为数不多的几台机器，并且由于它们之间缺少互连的手段，这些机器都是各自独立地工作。

51.1分布式系统概述

然而，从80年代开始，两项技术进步改变了这种局面。第一项是功能日益强大的微型计算机的发展。第二项进步是高速局域网的出现。局域间能将数十台机器、甚至数百台机器连接在一起，数据在机器之间传输只需要几us的时间。大量的数据能以超过10Mbps的速率传输。61.1分布式系统概述

分布式计算机系统是由多个分散的计算机经互连网络连接而成的计算机系统。其中各个资源单位（物理的或逻辑的）既相互协同又高度自治，能在全系统范围内实现资源管理，动态地进行任务分配或功能分配，并且能够并行地运行分布式程序。71.1分布式系统概述8分布式计算机系统示意图1.1分布式系统概述

分布式操作系统（DistributedOperatingSystem，缩写为DOS）是为分布式计算机系统配置的操作系统。它在这种多机环境下，负责控制和管理以协同方式工作的多种系统（的物理和逻辑）资源，进程的同步和执行，处理机间的通信、调度等控制事务，自动实行全系统范围内的任务分配和负载平衡并具有高度并行性的一种高级软件系统。91.2分布式系统的优缺点(1)分布式系统相对于集中式系统的优点优点说明经济性微处理器能提供比大型机更好的性能价格比速度分布系统能提供比大型机更强的计算能力固有的分布性在一些应用包含物理上分散的机器可靠性当某台机器崩溃时、整个系统仍能正常工作可扩展性计算能力逐步增加10表1分布式系统相对于集中式系统的优点1.2分布式系统的优缺点(2)分布式系统相对于独立PC机的优点优点说明数据共享允许许多用户共享同一个数据库外设共享允许用户共享昂贵的外设，如彩色打印机通信使得人与人间的通信更加方便，例如通过电子邮件灵活性将工作负载更有效地分派到合适的机器上11表2分布式系统相对于PC机的优点的优点1.2分布式系统的优缺点(3)分布式系统的缺点缺点说明软件目前很少有分布式系统的软件网络网络可能饱和，或让系统遇到其他麻烦安全方便的数据共享意味着机密数据容易被窃取12表3分布式系统的缺点1.3分布式计算机系统的特点

分布式计算机系统具有如下明显的主要特点：⑴结构模块性：分布式计算机系统的资源单位形成相对独立的模块，它们经互连网络连接成一个单一系统。模块在一定范围内的增减或替换不影响系统的整体性。⑵资源分散性（distributed）：系统资源分布于物理上分散的若干场点中。在对用户透明基础上实现资源共享，使单个用户的可用资源成倍地增长。

131.3分布式计算机系统的特点14⑶协同自治性（autonomous）：系统资源的操作是高度自治的，既不存在全系统的主/从控制关系，又能利用处理局部化的原则以减少各场点间的通信量。⑷工作并行性（parallesm）：分布式计算机系统中分散的资源单位可以相互协作，一起解决同一个问题。在分布式操作系统控制下，实现按任务资源重复或按功能时间重叠等不同形式的并行性。15

⑸系统透明性（transparency）：系统对于用户是透明的。用户可以像单机系统一样使用分布式计算机系统。⑹整体强健性（robustness）：系统中的资源的冗余和自治控制方式使系统具有动态重构能力，即使系统受到局部性破坏也能继续工作。所以具有可靠性和容错性。1.3分布式计算机系统的特点1.3分布式计算机系统的特点⑺灵活的可扩充性：以模块作为系统扩充或资源更新的增加单位，不必像集中式系统那样替换整个系统或更改系统中的很大部分。系统的配置容易改变，以适应不同应用对象的各种需求。⑻良好的实时性：计算机资源更加靠近用户，特别是使分散的用户能得到计算机的快速响应和直接服务，从而把大型机的强功能、高速度与微型机的使用方便性、灵活性结合了起来。161.3分布式计算机系统的特点分布式计算机系统是近年来计算机科学技术领域中倍受青睐、发展迅速的一个方向。一些专家亦断言：将来任何一个有效的计算机系统，都将是一个分布式系统。17181.4分布式计算机系统的体系结构

分布式计算机系统的体系结构可用处理机之间的耦合度为主要标志来加以描述。耦合度是系统模块之间互连的紧密程度，它是数据传输率、响应时间、并行处理能力等性能指标的综合反映，主要取决于所选用的互连拓扑结构和通信链路的类型。1.4分布式计算机系统的体系结构运程计算机网络采用串行数据传输，且受复杂的通信协议制约，故其耦合度最低，属于松散耦合系统（looselycouple）。具有共享内存的多处理机系统有着很高的并行处理速度，固其耦合度最高，属于紧密耦合系统（looselycouple）。191.4分布式计算机系统的体系结构按地理环境衡量耦合度，分布式计算机系统可以分为机体内系统、建筑物内系统、建筑物间系统和不同地理范围的区域系统等，它们的耦合度依次由高到低。2021按应用领域的性质决定耦合度，可以分成三类。一种是面向计算任务的分布并行计算机系统和分布式多用户计算机系统，它们要求尽可能高的耦合度，以便发展成为能分担大型计算机和分时计算机系统所完成的工作。第二种是面向管理信息的分布式数据处理系统，耦合度可以适当降低。第三种是面向过程控制的分布式计算机控制系统。耦合度要求适中，当然对于某些实时应用，其耦合度的要求可能很高。分布式计算机系统可看作是并行处理系统的一种常见形式和特例。1.4分布式计算机系统的体系结构221.5分布式系统的拓扑结构

分布式系统中的场点可用不同的方式将它们从物理上连结起来，每种方式都有优缺点。下面简单讨论几种常用的连结方式并按以下标准来比较它们的性能：⑴基本开销：连结系统中的各个场点要多少花费？⑵通信开销：从场点A发送消息到场点B需要多少时间？⑶可靠性：若系统中的场点或通信链路故障，余下的场点是否仍能彼此通信？一个系统称之为分割的（partition），如果它已被分划成两个或多个子系统，且不同子系统中的场点已不再能彼此通信。231.全互连结构

在一个全互连结构中，每个场点都直接与系统中所有其它的场点相连（图1.2），这种构形的基本开销很高，场点间的消息转移非常快，此外，这种结构是很可靠的，因为只有在相当多的通信键路故障的情况下，才可能分割该系统。图1.2全互连拓扑结构242.部分互连结构

在一个部分互连结构中，有些场点间存在直接通信链路，但有些则没有，如图1.3所示。因此这种构形的基本开销比全互连结构要低，但场点间的消息转移可能经由若干中间的场点，以致延缓了通信速度。例如，在图1.3中，从场点⑤④.发送一消息到场点③必须经由场点①和②。图1.3部分互连拓扑结构25

此外，部分互连系统也不如全互连系统可靠，因为其中的一个通信键路故障就可能分割该系统。例如，在图1.3中，若从场点①到场点②的通信链路故障，则该系统便分割成两个子系统，一个包括①，④，⑤；一个包括②和③，而且这两个子系统中的场点彼此不再能通信。为了减少这种情况发生，通常让每个场点要少与另外两个场点连给。例如，如果我们在图1.3中增加一条从场点③到场点⑤的通信键路，那么任何单条通信链路故障都不可能导致对该系统的分割。263.层次结构

层次结构中的各场点组织成树形结构。如图1.4所示，其中，这种构形的基本开销一般小于部分互连结构。在这种环境中，父子之间可直接通信，孩子之间只能经由它们的共同父亲进行通信，若父场点故障，那么，它的孩子们彼此就不能相互通信，也不能与其它进程通信。一般而言，除叶结点外，任何中间结点故障都可能将这种结构分割成若干不相交的子树。图1.4层次结构27

4.星形结构

在星形结构中，系统中的场点之一与系统中所有其余场点相连，其它的场点之间彼此不直接相连，见图1.5。这种构形的基本开销是场点个数的线性函数，其通信速度看起来也不会很慢，但这种通信速度却是难以预测的，因为中央场点可能变成瓶颈，虽然转移消息所需转接的次数不多，但转移消息所花的时间可能不少。在一些星形结构系统中，中央场点完全担负着消息转接的任务。如果中央场点故障，那么该系统就完全地被分割了。图1.5星形结构285.环形结构

在环形结构中，每个场点物理上恰好与另外两个场点相连，见图1.6。这样的环形结构可以是单向的，也可以是双向的。这种结构的基本开销不会很高，但通信代价可能较高，因为从一个场点向另一场点转移消息需沿环按预定方向转移直至到达目的地。在单向环结构中，这最多可能需要n-1次转接，在双向环结构中，则最多可能需要n/2次转接，其中n是网络中场点的个数。29图1.6环形结构

在双向环形结构中，其中两条通信链路故障就可能导致分割整个系统。在单向环形结构中，单个场点或单条通信链路故障，就可能分割整个系统。一种补救的办法是通过提供双通信链路来扩充这种结构，但这显然会增加基本开销，如图1.6(b)所示。306.多存取总线结构

在多存取总线结构（简称总线结构）中，它可以组织成直线状，见图1.7(a)，也可以组织成环状，如图1.7(b)所示，其中的场点可以经由这条总线彼此直接进行通信。这类结构的基本开销是场点个数的线性函数，通信代价也很低，除非这条总线变成了瓶颈。这类结构类似于带有一个中央场点的星形结构，其中某个场点故障不会影响其它场点间的通信，但是，若这条总线故障，那么该结构就完全地被分割了。31图1.7多存取总线结构

327.环-星形结构

环-星形结构由环、星型结构叠加而成，其优缺点介于星形和环形结构之间，见图1.8。图1.8环-星形结构338.有规则结构

有规则结构（见图1.9）中的每个场点都与它相邻的上、下、左、右场点相连，因而具有高性能、高速度、和高可靠性。不过，这种结构比较复杂，且一般要求各场点是完全一致的，构造这种系统的费用也较高。图1.9有规则结构349.不规则结构

不规则结构中的各场点间的连接关系无一定规则可依，其优点是：可随意增加不同类型的结点，各结点互连起来也较方便，还可提供任意冗余和重组能力；其缺点是运行时需要较复杂的路径选择算法（见图1.10）。图1.10不规则结构3510.立方体互连结构

立方体互连结构又称n维立方体分布式网络结构。这种结构把2n＝N个计算机互连起来，各计算机分别位于该立方体的角顶。立方体的每条边把两个场点连接起来，而每个场点则有n个全双向通路把它和n个其它计算机相连。例如，n=3，n=4时立方体互连结构如图1.11所示，其中，n为立方体的维数。此外，还有交叉开关网、树形网、网状网、立方体网和超立方体等。36图1.11立方体互连结构1.6分布式系统的资源管理资源管理有四种方式：（1）全集中管理方式（2）分担管理方式（3）轮流管理方式（4）全分散管理方式采取哪种资源管理方式，必须根据总体要求和资源性质决定。37381.7分布式操作系统1.多机操作系统的基本结构

多机操作系统有以下三种基本结构：主从式独立式分布式⑴主从式在多机系统上最早设计的多机操作系统都采用主从式，这是比较容易实现的一种形式。在具体设计和实现时，可在具备多道程序设计的操作系统基础上加以扩充而成。但是，它在管理和利用全系统资源方面的效率较低。其主要特点为：39

①管理程序始终由同一个处理机（称为主机master）执行，从而减化了控制信息的管理问题。若从机需要使用管理程序提供的服务，则应先向主机提出申请并等待现行程序中断后，由管理程序根据一定策略来决定是否满足这一申请并提供相应的控制。管理程序及其所用子程序不得重入，因为使用它们的只有一台处理机。②若主机不能以足够快的速度执行调度程序和收、发信息，以使从机保持充分地忙碌状态，那么从机的空闲时间就会增多，从而影响了整个系统的效率。③这种操作系统主要用于工作负载能精确给定的一些应用场合，或由于从机能力小于主机能力的非对称系统。④当主机故障时，影响整个系统，此时需外来干预；整个系统的灵活性也较差。40

⑵独立式独立式操作系统的主要特点是：①系统中的每台处理机的管理程序仅为自身的需要服务。某些程序所使用的子程序必须是再入式或复制品，以便为每台处理机提供各自单独的副本。②各台处理机借助公用信息相互联系。整个系统除了公用信息外，处理机的管理程序还可管理和使用各自的专用信息，因此，其信息的存取控制比主从式复杂。③系统中的每台处理机各自都有一套显示设备、I/O设备、文件、目录等。41

⑶分布式①可由多台处理机同时执行管理、控制和服务程序，但“主处理机”是浮动的，可由一台切换为另－台。由于多台处理机可同时执行同一管理、控制和服务程序，因此，这些程序必须是再入式的。②在这种操作系统的管理和控制下，整个系统中的所有资源单元均可获较好的负载平衡。③当服务请求发生冲突时，可根据固定的优先级或动态控制策略确定的优先级予以解决。④当系统中出现局部故障时，可通过自动重构，适度降级（gracefuldegradation）使用，或通过错误恢复手段使系统继续运行，因而系统有较好的可用性和可靠性。422.设计分布式操作系统时应考虑的问题

(1)灵活性

(2)可靠性

(3)性能

(4)可申缩性43

⑵分布式操作系统的结构本身也应是分布式的，系统中的各场点都可包含该操作系统或其中的一部分。一般把分布式操作系统划分成若干不相交的并行模块，并将它们分别指派给系统中的各场点，且每个场点都有一个局部操作系统的内核模块的副本。在系统运行时，各场点间的逻辑关系是完全平等的。分布式操作系统的模块可以全部并行地在各场点上运行，而控制流和数据流的移动则在各场点上的局部操作系统的内核模块的合作协调下进行。⑶分布式操作系统可划分为高层和局部，划分的原则是：①属于本机独立运行的基本管理功能划归为本场点（本机）局部操作系统。②本场点（本机）与其它场点（它机）之间的通信、同步、消息转移等管理功能也划归为本场点局部操作系统。44

③各场点间协调合作完成的功能，如任务分配、负载平衡、死锁处理、错误处理与系统重构等及其它公共事务划归为高层操作系统。这种划分使各场点在运行中既有自治性，又能使系统中各场点协调一致地进行合作。④分布式操作系统的基本调度单位已不再是单机操作系统的进程，而是一种任务队列，这种队列是由位于多个场点上的并发进程所组成的任何队列。同一任务队列中的诸并发进程可分布在不同的场点上并行地执行；同一场点上也可执行多个不同的任务队列中的并发进程。⑤在分布式系统中，需要提供一个支持资源共享的环境，把任务分解并分配到相应的场点。若整个系统由不同类型的处理机组成，由于每个处理机的处理能力及硬设备配置等方面都可能各具特点。因此，操作系统应该根据这些特点给处理机分配任务。45若系统由同类型的处理机组成，则在任何给定的时刻，任务都可分配给任何一个处理机，并可随时进行任务的迁移，以平衡系统的负载。显然，这要求分布式操作系统有任务或进程间通信及运程任务控制的能力。⑥分布式操作系统的构成与分布式计算机系统的耦合方式紧密相关。在紧密耦合的分布式系统中，各处理机共享存储器和时钟，通信是经由共享存储器进行的，系统资源的耦合程度很高，因而需要专门的各种软件和硬件机制来解决冲突和竞争等问题。在松散耦合的分布式系统中，各处理机无共享存储器和时钟，而都配有自己的本地资源，它们彼此之间经由各种通信线路进行通信。因此，分布式操作系统必须解决的主要问题是处理机以及进程之间的通信和同步。所以，多机系统的耦合方式不同，相应的分布式操作系统所要解决的主要问题也不同。⑦分布式操作系统必须具有探测任一处理机停机或发生故障的能力，并且要包含适当的处理措施，如自动重构，、降级使用和错误恢复等。463.构造分布式操作系统的途径

对于如何构造分布式操作系统，可归纳为下面几个主要观点：⑴从头开始因为分布式操作系统不同于现有的单机、集中式和网络操作系统，因此，不少学者主张完全从头开始构造一个分布式操作系统，即在裸机上重头开始。这种途径的最吸引人之处是给予设计者以完全的自由度。但不足之处在于其中所涉及到的所有系统软件和应用软件几乎全都要重新编写。

⑵修改、扩充式对现有的操作系统进行修改和扩充，使之具有分布处理和通信的功能。这种途径通过尽量保持与现有操作系统的相容性而使重新编写新软件的工作量减到最少。而且存在一个与开发期间的新版本进行比较的原有工作版本，这就给我们提供了测试和比较新版本性能的基础。这种途径的不利之处是开发期间的某些决策由于要考虑到如何与原有操作系统相容而不得不采取折衷方案。4748

⑶层次式在现有操作系统和用户之间增加一个层次以提供分布处理和通信功能。这类系统有点类似网络操作系统，它具有前述两种途径的优点且不必改动现有的操作家统,其不足之处在于所有对底层操作系统的引用由于必须经由中间层而使系统性能受到了衰减，此外，还有不少局限性。利用这三种途径构造分布式操作系统的示意图，见图1.15。49图1.15构造分布式操作系统的三种途径504.分布式操作系统的结构模型

分布式操作系统的结构是指其整体逻辑结构，主要有以下几种：⑴分布式操作系统内核：各场点上都配有一个分布式操作系统内核，它仅提供存储管理、辅存管理、进程管理、进程间的同步与通信等核心管理功能及相应的操作原语。例如，Accent和V核就属于这种结构模型。⑵集成式：集成式（integratedmodel）意指每个场点上运行着一个比较完整或集成的高度可组合的标准化的操作系统模块集，该集包含相应场点上所需要的几乎所有的服务功能，决大多数工作都是在本场点上完成的。每个场点也可访问远程资源，即当必要时才发生场点间的交叉访问。LOCUS等就是这种模型的例子。51

⑶客户/服务器（client/server）模型：在这种模型中，系统中的场点分为客户和服务器两大类。分布式操作系统的所有服务程序及相应的共享信息都分散地驻留在一些特定的场点上，并加以实现。而客户场点仅包含足以访问相应服务器场点上服务程序及相应的共享信息的接口软件，参见。这种模型常常分为两种形式：服务池模型和资源池模型。对于前者，系统中的所有服务功能都是由服务池按服务类提供的，如文件服务类、命名服务类、终端服务类和通信服务类等。对于后者，系统管理着一个可重用的资源池，如处理机、外设、文件、服务程序和数据等，其中的资源可动态地分配给申请者，用完后再收回到资源池中供再次使用。52

⑷中央式：系统在硬件结构上有一个中央场点和若干卫星场点。中央场点运行一个中央控制程序，由它处理所有对分布式操作系统的调用。每个卫星场点上运行的进程彼此不能直接通信，它们只能借助中央控制程序进行交往。⑸分散式：分散式模型意指将分布式操作系统的功能分散到各个场点，以构成单个场点上的局部操作系统，使得每个场点上的局部操作系统仅担负整个系统的部分管理功能。由各场点上的局部操作系统的核模块和核外部分采用协商、合作的方式来实现对全系统的管理That’sall532.1概述2.2消息传递2.3远程过程调用54第二章分布式通信机制552.1概述

本章讨论分布式系统中的通信问题。在考虑这一问题时，应注意以下几个方面：

发送策略：如何通过通信网发送消息？

连接策略：如何去连接彼此希望通信的进程？

争夺处理：由于通信网是共享资源，应注意解决在利用它的过程中那些有冲突的要求和冲突现象。

保密：如何保住消息内容的秘密？

通信机制：研究分布式操作系统中的基本通信机制。562.1.1发送策略

当场点A上的一个进程希望同场点B上的另一个进程进行通信时，如何发送消息？常用的几种发送策略是：

⑴固定发送:从A到B的信道事先已规定好并且不得更改，除非硬件的故障影响到它的通信能力。通常选择物理上长度最短的信道，以减少通信开销。⑵虚拟线路:从A到B的信道在一段时期内是固定的，在不同时期，从A向B发送的消息可能经由不同的信道发送。⑶动态发送:用于从A到B发送消息的信道仅当该消息发送时才确定。由于这种选择是自动进行的，单一的消息可能分给不同的信道。57上述几种方案各有利弊。固定发送不适用于通信负载的改变。即如果已在场点A和B之间确立了一条信道，那么消息只能经由这条信道传送，即使这条信道已经超载，而其它信道还处于尚未满载的状态。可以利用虚拟线路策略进行改善或通过动态发送策略来加以完全地解决。固定发送和虚拟线路策略可以确保按消息的发送次序从A向B发送消息。采用动态发送策略，消息的到达次序不一定和消息的发送次序相一致。这可以通过给每条消息赋以一个顺序号来解决。582.1.2连接策略

有许多不同的方法来连接一对彼此希望通信的场点（或进程）。最常用的方法有线路转换、消息转换和消息包转换。

⑴线路转换（circulateswitch）：如果两个进程希望通信，那么就在它们之间设立一条永久性的物理通信链路。这条通信链路供其消息转移期间使用，在这段期间其它进程不能使用这条链路。这种方案与电话系统类似，一旦一条通话线路已对通话双方开通（例如甲方给乙方打电话），其它人就不能使用这条信道，除非甲乙两方已明显地结束其通话（例如一方已挂起话筒）。

⑵消息转换（messageswitch）：如果两个进程希望通信，那么就确定一个临时的通信链路供其消息转移期间使用。物理通信链路则根据需要在用户间动态进行分配，而且只允许使用较短的一段时间。每条消息由一个数据再加上某些系统信息（如发送处，接收处和错误校正码等）组成，这些系统信息将辅助通信网络正确地将消息转移到目的地。这种方案与邮局系统类似，每封信可看作是包含发送处和接收处的一条消息，而且来自不同用户的信件（消息）可在相同通信线路上转移。5960

⑶消息包转换（packetswitch）：消息一般是可变长度的。为了简化系统的设计。常常把消息设计成定长的形式，并把这种定长的形式称为消息包（packet）。一条逻辑消息可能不得不划分成若干消息包，每个消息包都可以经由网络中不同的路径单独地发送到其目的地，当这些消息包都到达其目的地后，还得拼装起来组成一条完整的消息。线路转换需要安装时间但传送每条消息的开销较少；消息转换和消息包转换需要较少的安装时间，但转移每条消息的开销较大。此外，在采用消息包转换方法时，每条消息可能得先“化整为零”，然后再“集零为整”。612.1.3争夺处理

由于一条通信链路往往连结多个场点，而这些场点有可能希望同时在这条通信链路上转移信息，从而发生争夺现象。这种情况在环结构或多存取总线结构中表现得尤为突出。解决争夺现象的技术，常用的有冲突检测，令牌转移和消息槽。

⑴冲突检测：一个场点要在某条通信线路上转移消息之前，它必须进行监测以确定当前在该通信线路上是否正在转移另外的消息。若该通信线路空闲，则这个场点可以开始发送，否则它必须等待（同时继续监测），直到这条线路空闲。采用这种途径的主要问题是，当系统非常忙时，可能发生许多冲突现象，因此整个系统的性能由于冲突检测方面的工作而受到衰减。这种方法已成功地用在以太网系统。6263

⑵令牌转移（TokenPassing）：令牌是一个特殊的消息类型，它不断地在系统（通常在一个环结构）中循环。希望转移消息的场点必须等待直至令牌到达。当令牌到达后，该场点就从环中取走令牌并开始转移它的消息，当它完成了相应的消息转移后再重新发送令牌，这就给另一个场点提供了占有令牌的机会，一旦占有，就可开始它的消息转移。如果令牌丢失。那么系统应能发现这种情况并产生一个新令牌。该方法已由Primenet系统所采用。64

⑶消息槽(slot)：若干定长的消息槽连续不断地在系统（通常是一个环结构）中循环。每个消息槽可以容纳一定长的消息和有关的控制信息（如像发送处，接收处，消息槽满/空等）。希望转移消息的场点必须等待直到一个空消息槽到达，然后，该场点将它的消息插入这个空消息槽并附上适当的控制信息，此消息在网络中继续流动，当它到达某个特定的场点时，该场点就查看此消息槽的控制信息，以确认此消息槽是否包含了发送给它的消息；若没有，它就放过此消息槽，否则，它取走消息糟中的消息，重新设置控制信息以指明该消息槽为空。652.1.4保密问题

编码是保护信息的常用方法之一。信息在发送之前先予以编码，当信息到达其目的地后就进行译码。编码技术，最常用的一种就是提供一个通用的编码算法E，一个通用的译码算法D，并对每次应用提供一个保密键（key），令Ek和Dk分别表示具有保密键k的那个特定应用的编码和译码算法，那么，对于任何消息m，该编码系统必须满足下面的特性：⑴Dk(Ek(m))=m；⑵Ek和Dk都能有效地计算；⑶该系统的保密性只依赖于键k的保密性而不依赖于算法E和D的保密性。66

一个称之为“数据编码标准”（DataEncryptionStandard)的编码系统已由美国国家标准局所采用。不过，该方案还存在“键分布”问题，即，开始通信之前，保密键必须秘密地转移给发送者和接收者，但在一个通信网络环境中很难有效地完成这一点。解决此问题的办法之一是利用一个“公共键”（publickey）编码方案。每个用户有一个公共键和一个私有键，两个彼此知道他们的公共键的用户才可以相互通信。基于上述思想的编码方案已设计出来了。这个方案曾被认为是差不多不可破译的。其中的公共编码键是一对偶(e,n)，私有键是对偶(d,n),这里e,d,n都是正整数。每条消息用0～n-1之间的一个整数表示（较长的消息可分成若干较短的消息，它们每一个都可用这样的一个整数表示），函数E和D定义为：67E(m)=memodn=CD(C)=Cdmodn

这里的主要问题是选择编码和译码键。整数n可用下式计算n=pq

其中p和q是随机选取的两个较大的素数（例如，它们是由100位或更多位数字组成），d是随机选取的一个与(p-1)(q-1)互质的较大整数，即d满足GCD(d,(p-1)(q-1))=1

而e则应满足edmod(p-1)(q-1)=1

应指出的是，虽然n可能是大家知道的，但p和q却很难为他人所知。因为，对这里的n进行因式分解是比铰困难的。因此，d和e也是不易试探出来的。

68例如，令p=5和q=7，那么n=35，(p-1)(q-1)＝24。由于11与24互质，所以可选取d=11。因为1111mod24＝12lmod24=1，因此，e=11。假定，给定m＝3，那么C=memodn=311mod35=12而Cdmodn=1211mod35=3=m因此，如果我们利用e对ｍ进行编码，那么，我们就能用ｄ对它进行译码。692.2消息传递2.2.1消息传递原语

在分布式系统中，进程相互通信是通过彼此交换消息进行的。一个消息是从一进程发往另一些进程的信息单位。源进程通过执行send操作发送消息，宿进程则通过执行receive操作来获取消息；如果必要，在其获取消息后再通过执行reply操作给发送者一个回复。因此，分布式操作系统通常提供send、receive和reply等基本通信原语来实现进程间的通信和同步。70

消息转移原语分为两类：同步型和异步型。

1.异步型：在这类通信机制中，转移消息的进程不等待接收者的回复，又称“不等”转移（sendnoWait)，即允许发送方可任意超前于接收方，因而具有下面的特征：①接收方收到的消息与发送方目前的状态是无关的；②由于通信机制与同步机制几乎被截然分开，因此，系统应具有“无限”的缓冲空间来容纳任意超前发出而尚未处理的消息，以此来解决消息发送速度和消息处理速度之间的差异；③能比较充分地利用系统的潜在能力，但实现时须解决许多实际的控制问题。71图2.2同步消息传递和异步消息传递72

2.同步型：它与异步型消息转移正好相反，总是要求发送方等待接收方的回复，然后，发送方与接入方同步继续向下执行，其主要特征是：①消息的发送方和接收方在完成信息交换后彼此知道对方的状态；②同步机制和通信机制合二为一，一般无需大的缓冲区；③实现容易，但效率较低。同步型消息转移和异步型消息转移示意图，见图2.2。73

消息本身要占用存贮空间，并常常存放在系统的缓冲区中。当使们异步消息转移机制时，系统中的每个进程在某一时刻可能有多个尚未处理的消息。由于消息缓冲区是一个有穷的资源，因此，当使用异步消息传递方式传递消息时，可能会发生消息缓冲区溢出的情况。因此，异步消息传递需要特定的消息缓冲区管理算法来处理这方面的问题。但在采用同步消息传递方式时，系统中的每个进程决不可能存在一个以上尚未处理的消息，因此，其消息缓冲区的管理算法比较简单。742.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可分别编写成如下的程序段：75timeserver:

whiletruedo receive(request); readclock(time); reply(time);end;client：send(timeserver,gettime,time);图2.3使用消息转移方式的client/server模型76

一般，server可以设计成依次重复执行下述步骤的程序段：⑴等待接收来自clients发送的“请求服务”的消息；⑵接收clients发来的“请求服务”的消息；⑶处理clients发来的“请求服务”的消息；⑷向clients发送“服务已完成”的回复消息。仅当没有“请求服务”的消息到达时，server就阻塞自己。clients在等待server的回复消息时就阻塞它们自己，从而实现了clients与server的同步。在设计server进程时，通常要求：⑴server必须能调度和回复多个并发的请求消息；⑵server处理请求消息和发送回复消息的次序与接收该请求消息的次序无关；⑶在server给client发送回复消息时，决不应阻塞；⑷某个相关的client故障，不应影响server的操作。77

同步原语有一种与信息交换不同的特性。当一个进程引用了一个挂起的原语时，它就阻塞自己直至此原语执行完毕。同步原语的这种”阻塞”特性，类似于单处理机中所使用的信号量，可用于同步目的。图2.4(a)展示了两个进程使用信号量进行同步例子，其中，当P1在信号量sem上等待时，它就彼阻塞直至P2唤醒它。一个进程等待另一进程的类似效果也可利用同步send/receive原语实现，见图2.4(b)。78图2.4同步79

还有不少其它形式的send/receive原语。例如，“选择性接收”（selectivereceive）和”条件发送”（conditionalsend）。一个selectivereceive操作允许其用户选择一个进程或一组进程去接收发送来的消息。当执行conditionalsend操作时，如果相关的接收者不是处于阻塞状态正等待接收消息，那么它将立即完成而不发送消息。实际上，大多数异步send操作后紧随着一个receive操作。基于这个原因，许多分布式操作系统只提供同步消息传递原语。

802.3远程过程调用

远程过程调用（RemoteProcedureCall）就是把过程调用的概念加以扩允后引入分布式环境中的一种形式。远程过程调用的形式和行为与传统的过程调用的形式和行为类似，主要差别在于被调用的过程实际运行在一个与调用者所在场点不同的场点上，见图2.6。因此，需要设计相应的软件来实现两者之间的连接和信息沟通。81图2.5消息转移与过程调用的类似性图2.6远程过程调用示意图822.3.1RPC机制的结构及实现1.RPC机制的结构由下列成份组成：⑴stub：client和server各一个；⑵控制部分：为追踪RPC的调用状态所设；⑶传送部分：确定如何将信息从一个场点传送到另一个场点。实现RPC的一般过程可概括如图2.7所示：图2.7实现RPC的一般过程83client’sstub与一个client连接，它对于该client就像一个“server”。在调用时，它截取client的远程过程调用命令后，利用通信网络向server发送“请求服务”的信息。在返回时，它获取返回消息，并带返回结果返回到client，然后client继续执行。

Server’sstub与一个server连接，它对于该server就像一个“client”。在调用时，它收到远程调用请求后，产生一个本地调用，去执行被请求的远程过程。在返回时，它截取远程过程的返回结果，并形成返回消息发送出去。stub包含了一组RPC机制的操作原话，这些原语构成了RPC调用的实现细节，它可独立于client和server编程，在编译时再连接起来84RPC的实现要考虑两个方面的问题。第一，当进行远程过程调用时，调用场点必须能定位出被调用的过程实际上运行在哪个场点上；第二，相关的两个场点必须能协同合作交换信息。所有这些对用户都是透明的，这些的工作是依次进行的。下面介绍一种实现RPC的方法．其实现思想已概括在图2.8中。8586图2.8RPC的实现概况87

每个远程过程由若干成分组成：调用者（caller）或用户（user）调用代码段以及被调用者（callee）或server被调用代码段。这些都可用常规的程序设计语言编写，不需要利用特别的设施，就象它们在同一场点上执行一样。与调用者相关的stub与被调用者相关的stubRPCruntime子程序，可在系统中所有场点上运行。2.

RPC的实现stub程序的功能是把这种过程调用中所带的参数组装和拆卸成消息形式，并进行相应的类型检查，然后把这些消息转移给RPCruntime子程序，后者再把它们发送到系统中的其它场点。程序设计者定义了过程并写好了过程体，而系统生成了对应的stub。实现一个远程过程调用的主要工作环节如下。88⑴调用者用通常方式调用对应stub中的一个过程；⑵这个stub过程把有关的参数组装成一个消息包或一组消息包，以形成一条消息。运行此过程的那个场点的“地址”和那个场点上指称此过程的“标识符”都应包含在这条消息中；⑶将这条消息发送给对应的RPCruntme子程序，该子程序再把它发送给指定的场点。89⑷在接收此消息时，远程runtime子程序引用与被调用者对应的stub中的一个子程序，并让它来处理这条消息；⑸被调用者对应的stub中的这个子程序拆卸有关的参数并用通常的过程调用方式调用所需的过程。⑹返回调用结果，整个远程过程调用以与调用者对应的stub程序执行“return”语句返回到用户而终止。90

在上面的述中，我们回避了一个重要的问题，即与用户对应的stub如何知道实际运行远程过程的场点之地址呢？一些解决这一向题的方法：⑴当系统生成与调用者对应的stub时，可把该远程场地的地址也一同并入其中，不过这种做法不太灵活。⑵在进行调用之前，与调用者对应的stub向系统中的其它场点进行广播，请求有关的场点通报其地址，这必然引起一系列的消息转移。特别，当这种广播是在若干网络之间进行时，其转移速度是很慢的。⑶由系统管理一个表，其表项的内容为①场点地址；②该场点上将运行的远程过程的名字。

912.3.2RPC执行时各部分之间的关系

RPC执行时，各部分的关系如图2.9所示。其中，传输部分是RPC的最低层，其主要功能为：⑴提供对网络传输层协议的选择；⑵建立/释放逻辑信道，发送/接收消息等；⑶管理RPC中的消息缓冲区。9293图2.9RPC执行时各部分的关系图94

控制部分的主要功能是：⑴确定RPC中消息的方向（发送或接收）；当client的stub开始一次RPC调用或者server向server的stub返回调用结果时，该部分负责控制传输部分进行发送。⑵场点间会合与进程同步；场点间会合是指为使两个场点间进程同步，它们必须同意“会合（rendezvous）”，即早到达的进程要等待晚到达的进程。会话进程通过场点间会合建立一致的起点，并以该起点作为进程同步点进行对话。⑶若干状态信息的处理。由上可知，由于client的stub的作用，使得client可用常规过程调用方式去调用远程过程；由于server的stub的作用，使得server程序可以独立于调用者来编程，因而比较灵活。

本地调用和远程过程调用之间存在许多不同之处。如果远程调用是在两种异型机器间进行，这就存在数据表示问题，例如，这两类机器的字长可能不同。解决这一向题的方法之一是它在转移数据之前，让RPC机制将有关的数据转换成一种统一的格式，接收场点在接收数据时，再把它们转换成本地所允许的数据格式。第二个问题是如何解释指针，更确切他说，一个指针到底访问的是什么，在不具有共享地址空间的情况下，RPC不可能允许在网络范围内转移指针。因此，在RPC中是不可能用“reference方式”传递参数的。

952.3.3RPC的语义

更严重的问题是调用者和被调用者都可能在调用期间发生故障，而且经常是被调用者故障，留下调用者挂起。如果发生这种情况，调用者可能不得不夭折，这在本地调用中是决不会出现的。96

一个远程过程调用故障之后，调用者很难得知在故障发生前，该过程调用已经进行到了哪一步。这通常有三种可能：⑴在被调用者接收到调用它的命令之前，它发生了故障。⑵在执行其过程体时，被调用者发生了故障；⑶被调用者正确地完成了其过程体的执行，但在把结果返回给调用者之前发生了故障。此外，还有调用者在发出调用命令之后并在获得调用结果之前发生了故障。

97

由于调用者无法知道到底出现哪种情况，因此，系统必须提供一些基本的保护机制来确保RPC正确效果。不过，这个问题由于通信方面也可能出错以及系统试图进行错误矫正而混杂在一起，使得一个远程过程在成功地完成其执行之前，实际上可能引用了若干次。不同的RPC实现方案定义的这种效果或RPC语义是有差别的，几种常用的定义RPC语义的规则是：98

⑴1ast-of-many对执行一个远程过程调用而言，被调用的过程可能执行若干次，但规定其最后一次执行的结果作为返回结果；⑵at-most-once若调用者收到了回复消息，则被调用的过程正确地完成了它的一次（仅仅一次）执行。如果调用者没收到回复消息，或者，如果调用者在获得回复消息之前发生故障，那么，这时的调用效果就看作是根本就没有执行相应的过程。

99

⑶at-1east-once在场点正常情况下，则远程过程至少执行一次，且回复消息可能返回一次或多次。在场点故障时，就不能保证远程过程是否已被执行或曾返回任何回复消息。⑷exactly-once若server正常，则远程过程将恰好执行一次，并返回一个调用结果。同send/receive通信原语有许多变种一样，RPC也有一些不同的形式。例如可以允许异步远程过程调用，因此，调用者和被调用者可以并行执行，调用者负责在稍后某一时刻执行一个所谓的会合（rendezvous）来获取调用结果。100101Thanks!第3章分布式协同处理

3.1时间定序与时戳3.2分布式互斥算法3.3选择算法

3.1时间定序与时戳3.1.1分布式算法的基本特征

在集中式方案中，一个场点被指定为中央控制场点，由它来控制对共享资源的存取。每当一个场点希望存取一共享对象时，它就向该中央场点发一请求消息。当所指共享对象可供某场点使用时，控制场点就回送一个“可以访问”的消息给它。这种方案的弱点是中央控制场点可能变成瓶颈，而且一旦它故障，整个系统就崩溃了。可见，一个集中式算法具有两个明显的特点：⑴只有一个中央控制场点在进行决策；⑵所有必要的信息都集中在该中央控制场点上。

与之相反，一个分布式算法的基本特征是：⑴所有的场点都有差不多同等数量的信息；⑵所有的场点都是根据本地信息来进行决策的；⑶所有的场点对最终的决策都负有同等的责任；⑷所有的场点在影响最终决策时都付出了同等的努力；⑸算法具有强健性，系统的局部故障不影响算法的有效性。实际上，不管分布的程度和方式如何，对所有的分布式算法都有如下两种基本的假定。

假定1每个场点只是整个系统的一部分，且决策都是根据本地信息进行的；

假定2不存在全系统范围内的公共时钟。

假定2是一个主要的制约，因为能确定出事件发生的先后次序是极其重要的，它是计算系统中的一个基本概念。例如，在进行资源分配时，通常规定仅当某资源已经释放之后才可再次使用它。在分布式系统中，由于没有公共时钟，所以直接说某事件在另一事件之前或之后发生是不严格的。为了确定设计分布式算法的牢固基础，我们必须寻求一种在全分布式系统范围内进行事件定序的方法。3.1.2分布式系统中的事件定序方法

由于没有公共的时钟如何定序分布式系统中的事件呢？因为进程本身具有顺序性，所以在单个进程中的事件是按时间完全定序的。此外，根据因果法则我们可以假定”发送”一个消息的事件发生在“接收”同一消息的事件之前。以上两点自然给系统中的事件提供了一个偏序，称之为HappenedBefore关系（筒称HB），并用“”表示，其定义如下：

⑴ab①若a和b是同一进程中的两个事件，且a在b前发生；或者，②若a是一进程中发送消息的事件，且b是另一进程中接收同一消息的事件。

⑵该关系是转移的，即若ab且bc，则有ac。

⑶该关系是非自反的。

⑷若两个不同的事件之间不存在这种关系，即(ab)且(ba)，则a和b称为并发事件。因而，它们可以并发执行。例如，图中某些事件的HB关系是：

p1q2 r0q4 q3r1 p1q4（因为p1q2且q2q4）图中的某些并发事件是：

q0和p2 r0和q3 r0和p3 q3和p3图3.1三个并发进程的相对时间并发和HB关系可用图示加以说明，如图3.1所示，

因此，引进一个系统的逻辑时钟，用它的值来反映这个关系，从而实现整个系统中的事件定序。现假定，对每个进程pi，有一个与其相关的逻辑时钟Ci，赋给进程pi中事件a的逻辑时钟之值即Ci(a)。这种逻辑时钟可用一个计数器实现。若用C表示系统的逻辑时钟，则为使系统的逻辑时钟C能正确的计值，下面的条件应成立：时钟（clock）条件：对系统中的任何事件a和b，若ab，则C(a)<C(b)。若下面两个条件满足，则时钟条件成立：

条件1：对于进程pi中的两个事件a和b，若ab则有Ci(a)<Ci(b)；

条件2：若a是进程pi发送消息的事件，b是进程pj接收同一消息的事件，则有Ci(a)<Cj(b)

若按下面方法实现这种逻辑时钟，则上述两条件可以满足：⑴进程pi在其任何两个相继的事件之间使Ci增值；⑵若事件a表示进程pi中发送消息m的事件，则发送消息m的事件就附有时间戳Tm＝Ci(a)；⑶若事件b是进程pj(ij)中接收消息m的事件，pj就置Cj(b)之值为Cj(b)=max(Cj,Tm)+1

我们称进程pi中的事件a先于进程pj中的事件b（以ab表示）当且仅当⑴Ci(a)<Cj(b)；或⑵Ci(a)=Cj(b)，且pipj，其中关系“”是进程的一个任意偏序。实现关系“”的一个简单方法是给系统中每个进程赋以一个唯一的进程号，且规定：若i<j，则pipj。可以证明下列结果：⑴若ab，则一定不成立ba。⑵若ab，则ab。⑶若ab，bc则ac。分布式互斥的几点要求：（1）安全性：在某一时刻至多只有一个进程在临界段内执行。（2）可用性：请求进入临界段的进程终将准入。（3）定序：按关系“”排定的次序进入临界段。3.2分布式互斥算法3.2.1分布式互斥算法的基本假定分布式算法有如下的基本假定：⑴一个分布式系统由n个场点组成，它们从1到n唯一地编号，每个场点含有一个进程，而且进程和场点间存在一一对应的关系。⑵流水线（pipeline）特性成立，即从一个进程发送给另一进程的消息是按它们发送的次序接收的。⑶每条消息在有穷时间间隔内都能正确地转移到它的目的地。⑷系统是全互连的，因而每个进程都可直接给其它的进程发送消息。3.2.2集中式算法

分布式系统中实现互斥最直接的方法就是模拟单处理器系统的互斥方法。选择一个进程作为协调者（即运行在最高网址的机器上的某个进程）。某个进程要进入临界区时，向协调者发请求信息，指出它要进入临界区，然后等待协调者的许可。如果当前没有其他进程在该临界区中，协调者就返回一个许可消息，请求信息的进程接收到许可响应后，就进入临界区，否则就要等待。如下图所示集中式算法3.2.3分布式算法(Lamport算法)

第一个分布式方法是由Lamport[1978]提出的。算法的工作过程如下。进程要进入临界区时，建立一个包含临界区名，进程号和当前时间的消息。然后将该消息发送给其他所有进程，概念上说也包括发送消息的进程本身。每个进程管理一个请求队列。发送进入临界区的请求消息后，进程就坐等其他进程的许可消息。一但它得到所有进程的许可，就可以进入临界区了。进程退出临界区时，向在该进程的队列中的所有进程发送OK消息，并从队列中删除这些进程。某进程接收到其他进程发送的请求消息后。所采取的动作由它和消息中所包含临界区名决定。共分以下三种情况：

1）如果接收者不在临界区内，而且它不想进人临界区，就返回一个OK消息给发送者。

2）如果接收者在临界区内，就不做任何响应，只是将请求送入等待队列。

3）如果接收者要进入临界区。但还没有进入，它就比较接收到的消息中的时间戳与它自己发送给其他进程的请求消息中的时间戳。时间戳小的请求获胜。如果当前接收到的消息中的时间戳小，就发送一个OK消息。否则，如果该进程自己发送的消息中的时间戳小，就不做任何响应，只将接收到的请求放入队列中。分布式算法改进的Lamport算法

设R是某分布式系统中所有进程的集合，R={P1，P2，……Pn}，Ti是Pi进程的逻辑时间戳。一个进程要进入临界区需要执行以下的算法步骤：申请临界区

当Pi进程要进入临界区时，向R中的每一个进程发送消息REQ(Ti，Pi)；当Pj接收到来自Pi的请求消息时，可以根据临界区的使用情况及进程自己的状态，做出三种处理：第一种情况，若接收者Pj不在临界区中，也不想进入临界区，Pj向Pi发送REPLY应答消息。第二种情况，若接收者Pj已在临界区中，则不应答并暂存Pi的请求消息，对请求队列排队。第三种情况，若接收者Pj也向R中的其他进程发送了进入临界区的请求，但还没有进入临界区时，Pj将接收到的消息与自己发送的消息的时间戳进行比较，如果接收到的Pi时间戳小，进程Pj向Pi发送REPLY应答消息；否则，接收者Pj的时间戳小，则不应答任何请求消息，只负责暂存请求消息和对请求队列的排队。进入临界区

当Pi进程接收到R进程集合中所有的应答消息REPLY后，Pi进程进入临界区。退出临界区

当Pi进程退出临界区时，向排队等候进入临界区的所有进程发送REPLY消息。3.2.4令牌环算法

这里有一个总线网络如图所示，（如，以太网），其中的进程没有内定的次序。软件中构造一个逻辑环每个进程在环上被给定一个位置，

初始化环时，给进程0一个令牌（token）。令牌在环上循环传播。令牌从进程k到进程k＋1（对环的大小取模）由点到点的消息完成。进程从它的相邻结点获得令牌后，检查自己是否要进入临界区，如果是，就进入临界区，完成所需要工作后退出临界区。退出之后，该进程就将令牌在环上向后传递。这里不允许某个进程利用同一个令牌进人第二个临界区。

如果进程得到令牌时不要进入临界区，它就将令牌直接传送给环上的下一个结点。因此，所有的进程都不需进入临界区时，令牌就在环上高速循环传送。该算法的正确性是显而易见的。任何时刻都只有一个进程得到令牌，因此只有一个进程可以进入临界区。三种算法的比较三种互斥算法的比较算法进入/退出临界区所需的消息数等待进入延迟（消息时间）问题集中式32协调着崩溃分布式3（n-1）2（n-1）任何进程崩溃令牌环1～∞0～n-1令牌丢失，进程崩溃3.3选举算法许多分布式算法中都要一个进程充当协调者。假定每个进程都有一个唯一的进程号，通常选举算法都指定具有最高进程号的进程作为协调者。

选举算法的目的就是：保证在选举执行后，所有进程都认可某个进程成为了新的协调者。3.3.1Bully算法

当某个进程注意到协调者无法响应进程的请求时，该进程就初始启动一个选举过程。进程P执行的选举过程如下：

l）P向所有进程号比它高的进程发ELECTION消息。

2)如果得不到其他进程的响应，进程P获胜，成为协凋者。

3)如果有一个进程号更高的进程响应，该进程就接管选举过程。进程P的任务完成。

bully选举算法

3.3.2环算法

另外一个选举算法利用了环，但与前不同的是，这里没有用到令牌。假定对所有进程进行了物理或逻辑排序，因此每个进程都知道它的后继进程是哪个进程。任何一个进程发现协调者不再起作用时，就创建一条包含该进程号的ELECTION消息．并将该消息发送给其后继进程。如果后继进程已经中止，就跳过它发送给下一个进程，依此类推．直到找到一个正在运行的进程为止。每个进程接收到ELECTION消息后，就将自己的进程号加入消息中的进程表。最后ELECTION消息会回到创建它的那个进程。进程接收到的ELECTION消息中已经包含该进程的进程号时，就可以断定这条消息是由它自己创建的。这时，将消息类型改为COORDINATOR，再次在环上循环发送。这次是将新的协调者（进程表中进程号最大的进程）和环上现有的成员通知给其他进程，COORDINATOR消息在环上循环一周后，从环上移去该消息，各进程恢复其原有操作。环选举算法That'sAll!第四章分布式资源管理1354.1资源共享4.2资源管理策略4.3分布式系统中的死锁处理1364.1资源共享实现资源共享的三种方法。4.1.1数据迁移数据迁移的两种方法：

第一种方法是将整个文件转移给场点A，尔后，所有对该文件的存取都是局部的了。当用户不再需要访问该文件时，它的副本（如果它被修改过）被回送给场点B。对一个文件的任何微小的修改，都得将这整个文件传送回去。137

另一种方法是只将该文件中实际需要的部分转移给A。一旦用户不再使用该文件，该文件的任何已作过修改时部分必须回送给场点B。显然，如果只访问一个较大文件的一小部分，那么采用后一种方法较好；否则采用第一种方法较合适。不过，仅仅从一个场点向另一个场点转移数据是不够的，系统还得执行各种数据转换（如果两个场点不是直接兼容的话）。例如，如果它们使用了不同的字符代码表示。138

4.1.2计算迁移

在某些情形中，转移计算比转移数据更有效。例如，考虑这样一个作业，它需要存取位于不同场点上的若干较大的文件，以获得它们的概况。一种比较有效的办法是在它们驻留的场点上各自存取这些文件，然后分别回送所需要的值给初启该计算的那个场点。计算的实现方式：可用一个远程过程调用来初启。进程p引用场点A上预定义的一个过程，该过程执行完后给p回送所需要的结果。139

通过消息传递的方式。进程p可以发送一条消息给场点A，操作系统在场点A创建一个新进程q，q的功能是执行由该消息所指定的任务，当q完成其执行后，它又通过消息系统给p回送所需要的结果。这两种方案都可用来存取驻留在各个场点上的若干文件。1404.1.3作业迁移当一个作业提交给系统后，系统可以在一特定的场点上执行这整个作业，或在不同的场点上执行它的某一部分利用这种方案的主要原因是：⑴负载均衡：作业（或子作业）可以分散到系统中以均衡系统的工作负载。⑵计算速度的提高：如果单个作业可以分解成若干子作业，这些子作业可以在不同的场点并发地执行，那么，整个作业的周转时间将会减少。

⑶硬件特性：该作业可能有这祥一些特性，即它比较适合于在某些特殊的处理机上执行。例如，矩阵转换就比较适合于在阵列机上执行。⑷软件特性：该作业可能需要特定场点上的软件或不能移动的软件，或者移动该作业比较划算。显示迁移隐式迁移1411424.2资源管理管理策略

分布式系统对于资源管理有两种基本的观点：单个资源管理单个资源与多个管理机构相互关系的角度进行分析。多个资源管理多个资源与多个管理机构相互关系的角度进行分析。前者是后者的基础，后者是前者的提高。143

⑴单个资源管理，有四种资源管理方式：集中管理方式：只有一个管理者对该资源的各种活动统一进行管理，其它管理者对该资源均不具有管理职能和责任。该方式也称为专制（autocratic）管理方式。功能分布管理方式：多个管理者按照不同的资源活动分担管理职能和责任，且每种活动只由一个管理者管理。该方式也称为分担管理方式或分割（partitioned)管理方式。144浮动管理方式：多个管理者均可同等地担负管理职能和责任，但在一段时间内，只有一个管理者行使职权，“任期”满后再由另一管理者接替，如此轮流下去。该方式也称轮流（successive）管理方式。分散管理方式：多个管理者采取协商一致的原则对资源活动进行全面管理，其中各个管理者的地位和功能是完全平等的。该方式也称民主(democratic）管理方式。

145⑵从多个资源管理，可分为如下四种管理方式：

集中：每一类资源只属一个管理者管理。它控制该类全部资源。

分管（集中分布式）：每一类资源由多个管理者管理，但每一资源只属一个管理者管理。

合管（完全分布式）：不仅每一类资源存在多个管理者管理，而且该类中每个资源属于全部管理者共同管理。

部分管理：每一类资源由多个管理者管理，每一资源属于若干管理者管理。如图4.1所示。其中圆圈表示管理者，三角形表示资源。146图4.1资源管理方式147

分布式管理方式和集中式管理方式的主要区别是对同类资源是采用多个管理者还是一个管理者