分布式计算机系统ppt课件计算机操作系统汤小丹梁

1、第第9 9章章 分布式计算机系统分布式计算机系统 第第9章章 分布式计算机系统分布式计算机系统 9.1 分布式计算机系统分布式计算机系统9.2 分布式系统的设计分布式系统的设计 9.3 分布式系统中的通信问题分布式系统中的通信问题 9.4 消息传递消息传递 9.5 远程过程调用远程过程调用 9.6 进程迁移进程迁移 第第9 9章章 分布式计算机系统分布式计算机系统 9.7 分布式操作系统中的进程同步分布式操作系统中的进程同步 9.8 分布式操作系统中的进程互斥分布式操作系统中的进程互斥9.9 分布式系统的资源管理分布式系统的资源管理9.10 死锁处理死锁处理 习题习题第第9 9章章 分布式计算

2、机系统分布式计算机系统 9.1 分布式计算机系统分布式计算机系统 9.1.1 概述 网络技术的发展使一些计算机系统从集中式走向分布式，那么什么是分布式系统呢?分布式计算机系统(Distributed Computer Systems)是由多个分散的计算机经互连网络连接而成的计算机系统。 第第9 9章章 分布式计算机系统分布式计算机系统 分布式计算机系统是多机系统的一种新形式，它强调资源、任务、功能和控制的全面分布。就资源分布而言，既包括处理机、I/O设备、通信接口、后援存储器等物理设备资源，也包括进程、文件、目录、表、数据库等逻辑资源。它们分布于物理上分散的若干场点中，而各场点经互连网络沟通，

3、彼此通信，构成统一的计算机系统。第第9 9章章 分布式计算机系统分布式计算机系统 网络操作系统是为计算机网络配置的操作系统，网络中的每台计算机配置各自的操作系统，通过网络操作系统把它们有机地联系起来。因此，它除了具有一般操作系统所具备的存储管理、处理机管理、设备管理、信息管理和作业管理等功能外，还应具有以下网络管理功能： (1) 高效可靠的网络通信能力。 (2) 多种网络服务功能，包括远程作业录入、分时系统服务和文件传输服务等。第第9 9章章 分布式计算机系统分布式计算机系统 (1) 进程通信不能借助公共存储器，因而常采用信息传递方式。 (2) 系统中的资源分布于多个场点，因而进程调度、资源分

4、配及系统管理等必须满足分布处理要求，并采用保证一致性的分散式管理方式和具有强健性的分布式算法。 (3) 不失时机地协调各场点的负载，使其达到基本平衡，以充分发挥各场点的作用。 (4) 故障检测与恢复及系统重构和可靠性等问题的处理和实现都比较复杂。第第9 9章章 分布式计算机系统分布式计算机系统 9.1.2 分布式系统的特征 由分布式系统的定义可知，分布式系统是由多台计算机组成的系统。更确切地说，分布式系统是具有以下特点的多计算机系统。 (1) 分布性：组成系统的部件在物理上是分散的，这些部件包括处理机、数据、算法和操作系统。 (2) 自治性：系统所有的软硬件资源都是高度自治的，它们能够独立执行

5、任务、提供或拒绝提供服务。 第第9 9章章 分布式计算机系统分布式计算机系统 (3) 透明性：系统的分布性、操作和实现对用户完全透明，用户只需提出所需服务，而不必要指明由哪一台设备在什么位置用什么方法来提供这些服务。 (4) 共享性：系统中的资源为系统中所有用户所共享，在某台计算机终端上的用户，不仅可以使用位于该机上的资源，而且还可以使用位于它机上的资源。 (5) 协同性：系统中的若干台计算机可以相互协作来完成一个共同任务，或者说，一个程序可以分布在几台计算机上并行运行。第第9 9章章 分布式计算机系统分布式计算机系统 分布式系统应具备以下三种基本功能： (1) 通信。系统提供某种通信机制，使

6、得运行在不同计算机上的用户程序可以利用网络来交换信息。 (2) 资源共享。系统提供访问它机资源的功能，使得在某机或其终端上的用户或用户程序可以访问位于它机的资源。 (3) 协同工作。系统提供某种程序设计语言，使得用户可以用它编写能够分布在若干台计算机上并行执行的应用程序，同时系统提供这些应用程序(进程)之间的协调和通信。第第9 9章章 分布式计算机系统分布式计算机系统 9.1.3 分布式系统的结构 分布式系统中的场点可用不同的方式将它们从物理上连接起来，每种方式都有其优缺点，下面简单讨论几种常用的连接方式并按以下标准来比较它们的性能。 基本开销：连接系统中的各个场点需要多少花费? 通信开销：从

7、场点Ai发送信息到场点Aj需要多少时间？(i，j=1，2，3，n) 可靠性：若系统中某场点或通信线路出现故障，余下的场点是否仍能彼此通信?第第9 9章章 分布式计算机系统分布式计算机系统 1全互连结构 在一个全互连结构中，每个场点都直接与系统中所有其他的场点相连，如图9.1所示。 第第9 9章章 分布式计算机系统分布式计算机系统 A2A1A4A5A3图9.1 全互连结构第第9 9章章 分布式计算机系统分布式计算机系统 2部分互连结构 在一个部分互连结构中，有些场点间存在直接通信链路，但有些则没有，如图9.2所示。因此这种构形的基本开销比全互连结构要低，但场点间的消息传递可能经由若干中间的场点，

8、以致延缓了通信速度。 第第9 9章章 分布式计算机系统分布式计算机系统 图9.2 部分互连结构发消息A1A4A2A3A5第第9 9章章 分布式计算机系统分布式计算机系统 3层次结构 层次结构中的各场点组织呈树形结构，如图9.3所示。其中，每一场点(根除外)有一个惟一的父节点和若干个(或0个)子节点。这种结构的基本开销一般小于部分互连结构。 第第9 9章章 分布式计算机系统分布式计算机系统 图9.3 层次结构A3A4A2A5A1A6第第9 9章章 分布式计算机系统分布式计算机系统 4星形结构 在星形结构中，系统中的场点之一与系统中所有其余场点相连，其他的场点之间彼此不直接相连，如图9.4所示。

9、第第9 9章章 分布式计算机系统分布式计算机系统 图9.4 星形结构A5A4A1A3A2A6第第9 9章章 分布式计算机系统分布式计算机系统 5环形结构 在环形结构中，每个场点物理上恰好与另外两个场点相连，如图9.5(a)所示。 在双向环形结构中，其中两条通信链路故障就可能导致分割整个系统。在单向环形结构中，单个场点或单条通信链路故障，就可能分割整个系统。一种补救的办法是通过提供双通信链路来扩充这种结构，但这显然会增加基本开销，如图9.5(b)所示。第第9 9章章 分布式计算机系统分布式计算机系统 A8A7A6A5A4A3A2A1(a)(b)A8A7A6A5A4A3A2A1图9.5 环形结构

10、(a) 单通信链路；(b) 双通信链路 第第9 9章章 分布式计算机系统分布式计算机系统 6多存取总线结构 在多存取总线结构(简称总线结构)中，有一条共享的通信链路(即总线)。系统中所有的场点都直接与这条通信链路相连，它可以组织成直线状(见图9.6(a)，也可以组织成环形(见图9.6(b)，其中的场点可以经由这条总线彼此直接进行通信。 第第9 9章章 分布式计算机系统分布式计算机系统 AnA1A2A3A4A5A6AnA3A2A1(a)(b)图9.6 总线结构(a) 线形总线；(b) 环形总线第第9 9章章 分布式计算机系统分布式计算机系统 7立方体结构 立方体结构又称n维立方体分布式网络结构。

11、这种结构把2nN个计算机互连起来，各计算机分别位于该立方体的角顶。立方体的每条边把两个场点连接起来，而每个场点则有n个全双向通路把它和n个其他计算机相连。例如，n3和n4时立方体互连结构分别如图9.7(a)、(b)所示，其中，n为立方体的维数。第第9 9章章 分布式计算机系统分布式计算机系统 (a)(b)图9.7 立方体结构(a) n=3, N=8；(b) n=4, N=16第第9 9章章 分布式计算机系统分布式计算机系统 9.1.4 分布式系统的设计方法 传统上，分布式操作系统是按面向进程的方法设计的，近年来提出了面向对象的分布式操作系统的设计方法，它与面向进程的分布式操作系统的设计方法的主

12、要区别是：前者将操作系统视为对象的集合，而且有关用户(进程)对象和系统状态的同步及控制是通过权限(Capability)的管理和分配完成的；而后者则把操作系统看作是进程的集合，有关用户进程和系统状态的同步及控制是通过消息传递实现的。第第9 9章章 分布式计算机系统分布式计算机系统 9.2 分布式系统的设计分布式系统的设计 1透明性(Transparency) 分布式系统的透明性具体表现在： (1) 位置透明性。在一个分布式系统中，用户不必知道硬件或软件资源的具体位置。资源的名字不能用资源的位置编码。 第第9 9章章 分布式计算机系统分布式计算机系统 (2) 迁移(Migration)透明性。迁

13、移透明性是指资源可以随意从一个计算机(节点)迁移到另一个计算机上，而无需改变资源的名字。 (3) 复制(Replication)透明性。复制透明性是指用户不知道系统拥有多少副本。 (4) 并发(Concurrency)透明性。 (5) 并行(Parallelism)透明性。用户所看到的一个分布式系统是一个单机形式。 第第9 9章章 分布式计算机系统分布式计算机系统 2灵活性(Flexibility) 分布式系统设计的第二个关键问题是灵活性。灵活性涉及到分布式操作系统的结构。分布式操作系统结构有两种不同的形式：一种是单内核(Monolithic Kernel)，另一种是微内核(Micro Ker

14、nel)，如图9.8所示。第第9 9章章 分布式计算机系统分布式计算机系统 用户程序包括文件、目录 和进程管理网络微内核文件服务器微内核目录服务器微内核进程服务器微内核用户程序单内核图9.8 分布式操作系统结构(a) 单内核；(b) 微内核第第9 9章章 分布式计算机系统分布式计算机系统 微内核结构更加灵活，是一种新的结构，仅仅提供以下四种服务： (1) 进程间通信机制； (2) 某些内存管理； (3) 有限的低级进程管理和调度； (4) 低级的输入输出。第第9 9章章 分布式计算机系统分布式计算机系统 3可靠性(Reliability) 最初分布式系统的设计原因之一是它比集中式系统可靠性更高

15、，即一台机器坏了，其他机器能够接替它的工作。换句话说，在理论上系统可靠性是所有部件可靠性的布尔“或”。 第第9 9章章 分布式计算机系统分布式计算机系统 4性能(Performance) 性能是设计任何一个系统都需要重视的问题。一个分布式系统的透明性再好，灵活性再强，可靠性再高，而它的性能很差，速度很慢，也就失去了建立分布式系统的意义。如何衡量分布式系统性能的好坏是一个有待进一步研究的问题。 第第9 9章章 分布式计算机系统分布式计算机系统 5可扩展性(Expansibility) 在建立一个分布式系统之前，分布式系统的规模也是必须考虑的问题，即所设计的系统应是可扩展的，应避免潜在的瓶颈：集中

16、式部件、集中式表格和集中式算法。第第9 9章章 分布式计算机系统分布式计算机系统 9.3 分布式系统中的通信问题分布式系统中的通信问题在分布式系统中的通信应注意以下几个方面的问题： 发送策略：如何通过通信网发送消息? 连接策略：如何去连接彼此希望通信的进程? 争夺处理：由于通信网是共享资源，应注意解决在利用它的过程中哪些有冲突的要求和冲突现象。 保密：如何保住消息内容的秘密? 通信机制：研究分布式操作系统中的基本通信机制。第第9 9章章 分布式计算机系统分布式计算机系统 9.3.1 发送策略 当场点A1上的一进程希望同场点A2上的另一进程进行通信时，如何发送消息呢? 若从A1到A2之间只有一条

17、物理信道(好像在一个星形结构或层次结构中)，那么，该消息只能经由这条信道发送。若从A1到A2存在多条物理通路，那么，发送该消息就有选择性了。第第9 9章章 分布式计算机系统分布式计算机系统 (1) 固定发送：从A到B的信道事先已规定好且不得更改，除非硬件方面的故障影响到它的通信能力。通常是选择(物理上长度)最短的信道，以减少通信开销。 (2) 虚拟线路：从A到B的信道在一段时间内是固定的，在不同时期，从A向B发送的信息可能经由不同的信道发送。 (3) 动态发送：用于从A到B发送信息的信道仅当该消息发送之时才被确定。 第第9 9章章 分布式计算机系统分布式计算机系统 9.3.2 连接策略 1线路

18、转换 假设两个进程之间需要通信，那么在它们通信期间应建立一永久性的物理通信链路，在这段时间其他进程不能使用这条链路。这种方案与电话系统类似，一旦一通话线路已对两方开放(如甲方给乙方打电话)，其他的人就不可能使用这条信道，除非甲、乙两方的通话结束(如一方已挂上听筒)。第第9 9章章 分布式计算机系统分布式计算机系统 2消息转换 假设两个进程之间需要通信，那么确定一临时通信链路供其消息传递期间使用。物理通信链路则根据需要在用户间动态地进行分配，而且只允许使用较短的一段时间。每条消息由一个数据块再附加一些系统信息(如发送地、接收地、错误校正码等)组成，这些系统信息辅助通信网络正确地将消息传递到目的地

19、。这种方案与邮局系统类似，每封信可看作是包含发送地和接收地的一条消息，而且来自不同用户的信件(消息)可在相同通信线路上传递。第第9 9章章 分布式计算机系统分布式计算机系统 3消息包转换 消息一般是可变长度的。为了简化系统的设计，常常把消息设计成定长的形式，并把这种定长的形式称为消息包(Packet)。一条逻辑消息可能不得不划分成若干消息包，每个消息包都可以经由网络中不同的路径单独发送到其目的地，当这些消息包都到达其目的地后，还得拼装起来组成一条完整的消息。第第9 9章章 分布式计算机系统分布式计算机系统 9.3.3 争夺处理 1冲突检测 一个场点要在某条通信线路上传递消息之前，必须进行监测以

20、确定当前在该通信线路上是否正在传递另外的消息。若该通信线路空闲，则这个场点可以开始发送，否则它必须等待(同时继续监测)，直到这条线路空闲。 第第9 9章章 分布式计算机系统分布式计算机系统 2令牌传递(Token Passing) 令牌是一个特殊的消息类型，它不停地在系统(通常在一个环形结构)中循环。希望传递消息的场点必须等待令牌到达。当令牌到达后，该场点就从环中取走令牌并开始传递它的消息。 3消息槽(Slot) 若干定长的消息槽连续不断地在系统(通常是一个环形结构)中循环。每个消息槽可以容纳一定长的消息和有关的控制信息(如发送处、接收处、消息槽满/空等)。 第第9 9章章 分布式计算机系统分

21、布式计算机系统 9.3.4 保密 系统必须提供适当的措施让用户保护他们的信息(数据)。编码是保护信息的常用方法之一。信息在发送之前先予以编码，当信息到达目的地后就进行译码。问题在于如何研制一个不可能(或很难)破译的编码系统。对此，有许多解决办法，常用的一种就是提供一个通用的编码算法E和一个通用的译码算法D，并对每次应用提供一个密钥。 第第9 9章章 分布式计算机系统分布式计算机系统 令Ek和Dk分别表示具有密钥k的那个特定应用的编码和译码算法，那么，对于任何消息m，该编码系统必须满足下面的特性： (1) Dk(Ek(m)=m； (2) Dk和Ek都能有效地计算； (3) 该系统的保密性只依赖于

22、密钥k的保密性而不依赖于算法E和D的保密性。第第9 9章章 分布式计算机系统分布式计算机系统 基于上述思想的编码方案已由Rivest，Shamir和Adleman(1978)设计出来了。这个方案简称RSA算法，曾被认为是不可破译的。其中的公共钥是对偶(e，n)，私钥是对偶(d，n)。这里e，d，n都是正整数。每条消息用0n-1之间的一个整数表示(较长的消息可分成若干较短的消息，它们每一个都可用这样的一个整数表示)。函数E和D定义为 E(m)me mod nC D(C)Cd mod n第第9 9章章 分布式计算机系统分布式计算机系统 这里的主要问题是选择编码和钥。整数n可用下式计算：npq 其中

23、，p和q是随机选取的两个较大的素数(例如，它们是由100位或更多位数字组成的)；d是随机选取的一个与(p-1)(q-1)互质的较大整数，即d满足GCDd, (p-1)(q-1)1 而e满足 ed mod (p-1)(q-1)1第第9 9章章 分布式计算机系统分布式计算机系统 9.4 消消 息息 传传 递递 9.4.1 异步型 在这类通信机制中，发送消息的进程不等待接收者的回复，即允许发送方任意超前于接收方，因而它具有下面的特征： (1) 接收方收到的消息与发送方目前的状态是无关的。换言之，接收消息中反映的发送状态一般不是发送方的当前状态。第第9 9章章 分布式计算机系统分布式计算机系统 (2)

24、 由于通信机制与同步机制几乎被截然分开，因此，系统应具有“无限”的缓冲空间来容纳任意超前发出而尚未处理的消息，以此来解决消息发送速度和消息处理速度之间的差异。 (3) 能比较充分地利用系统的潜在能力，但实现时需解决许多实际的控制问题。第第9 9章章 分布式计算机系统分布式计算机系统 9.4.2 同步型 同步型与异步型消息传递正好相反，总是要求发送方等待接收方的回复，然后发送方与接收方同步继续向下执行。其主要特征如下： (1) 消息的发送方和接收方在完成信息交换后彼此知道对方的状态。 (2) 同步机制和通信机制合二为一，一般无需大的缓冲区。 (3) 实现容易，但效率较低。第第9 9章章 分布式计

25、算机系统分布式计算机系统 9.4.3 组通信 1组通信的用途 如果一个进程想和另一组进程进行通信，单个的消息交换并非最好的模式。比如，一个服务是由多个计算机上的多个进程完成的时候，就会出现一个进程和一组进程间的通信。 第第9 9章章 分布式计算机系统分布式计算机系统 如果需要设计一个具有如下特征的分布式系统，则组播消息是一个非常有用的方式。 (1) 以重复服务为基础的容错性。每当一个客户发出一个请求消息时，它实际上是将这条消息发送给一组服务器。 (2) 定位分布式服务中的对象。组播消息可以用来在一个分布式服务中寻找一个对象，例如在分布式文件服务中寻找一个文件。 第第9 9章章 分布式计算机系统

26、分布式计算机系统 (3) 通过保留数据的副本来提高性能。分布式系统可以使用数据的副本来提高服务的性能，有时候副本就保存在用户的本地机之中。 (4) 多重刷新。对一个组的组播可在发生某些事件时通知该组中的进程。 第第9 9章章 分布式计算机系统分布式计算机系统 2组通信的特性 1) 原子性(Atomicity) 在上面提到的第(1)种“将这条消息发送给一组服务器”的情况中，每个服务器都收到所有的请求，因此每个服务器执行的操作都是相同的，并且在任一时刻每个服务器的状态都是一样的。要实现这样的目标，必须使用原子组播。第第9 9章章 分布式计算机系统分布式计算机系统 所谓原子组播(Aatomic Mu

27、lticast)，就是指任何一条以原子组播方式发送的消息，要么被接收的服务器组中的所有成员全部收到，要么其中的成员一个也收不到。这里我们规定，失效的进程不可能是任一个服务器组中的成员。第第9 9章章 分布式计算机系统分布式计算机系统 2) 定序(Ordering) 原子组播和可靠组播在进程对之间都提供FIFO式的定序。在FIFO式的定序中，从任一个客户发送到某个服务器的次序也就是它们发出时的次序，我们可以在消息中加上一个序列号来实现这一目的。第第9 9章章 分布式计算机系统分布式计算机系统 BBAAP1时间P2P3P4图9.9 无定序限制的组播第第9 9章章 分布式计算机系统分布式计算机系统

28、9.5 远程过程调用远程过程调用 9.5.1 概述 在单处理机系统中，不同进程之间可以通过过程(函数)调用方式实现进程通信。在调用时，调用进程必须给出被调用的过程名，传送所需参数和提供返回参数的缓冲区。 第第9 9章章 分布式计算机系统分布式计算机系统 9.5.2 基本RPC操作 在分布式操作系统中，为实现进程间的通信，通常要设计一些通信原语(如前述的send、receive)。这些原语是按照通信协议所规定的规则实现的，这些通信原语就构成了分布式系统基本的通信机制。 第第9 9章章 分布式计算机系统分布式计算机系统 为了解RPC是如何工作的，首先要了解清楚传统的(即单机上)过程调用是如何工作的

29、。考虑这样一个过程调用： count=read(fd，buf，nbytes); 这里fd是一个整数，buf是一个字符型数组，nbytes也是一个整数。若主程序调用该过程，调用前堆栈的情况如图9.10(a)所示。调用开始时，调用者按序将参数压入堆栈，后进入的先弹出，如图9.10(b)所示。 第第9 9章章 分布式计算机系统分布式计算机系统 主程序局部变量nbytesSPSP00buffd返回地址read的局部变量主程序局部变量SP主程序局部变量(a)(b)(c)图9.10 基本的RPC操作(a) 调用之前的栈状态；(b) 过程执行中的栈；(c) 返回到调用者之后的栈第第9 9章章 分布式计算机系

30、统分布式计算机系统 客户存根调用调用客户机返回返回参数打包内核内核网上传送的消息椭圆代表进程，阴影部分表示存根服务器存根参数拆包结果打包服务器结果拆包图9.11 RPC调用和消息第第9 9章章 分布式计算机系统分布式计算机系统 RPC的主要步骤是：(1) 客户过程以普通方式调用相应的客户代理。(2) 客户代理建立消息并激活内核陷阱。(3) 内核将消息发送到远程内核。(4) 远程内核将消息送到服务器代理。(5) 服务器代理取出消息中的参数后调用服务器的过程。第第9 9章章 分布式计算机系统分布式计算机系统 (6) 服务器完成工作后将结果返回至服务器代理。(7) 服务器代理将结果打包并激活内核陷阱

31、。(8) 远程内核将消息发送至客户内核。(9) 客户内核将消息交给客户代理。(10) 客户代理从消息中取出结果返回给客户。第第9 9章章 分布式计算机系统分布式计算机系统 9.5.3 两种通信方式的比较 远程过程调用在广泛的应用中，也暴露了一些缺点，不能满足某些方面的要求，主要有： (1) 远程过程调用的参数在系统内不同机种之间通用的能力有所不足。 (2) 缺乏在一次调用过程中多次接收、返回的能力。 (3) 远程过程调用缺乏传送大量数据的能力。 第第9 9章章 分布式计算机系统分布式计算机系统 9.6 进进 程程 迁迁 移移 9.6.1 数据和计算的迁移 1数据迁移(Data Migratio

32、n) 假如系统A中的用户希望去访问系统B中的数据，比如一份文件，可采取以下两种方法来实现数据的传送。 第一种方法是将系统B中的整个文件送到系统A。 第二种方法是把文件中用户当前需要的那一部分从系统B传送到A。 第第9 9章章 分布式计算机系统分布式计算机系统 2计算迁移(Computation Migration) 在某些情况下，传送计算要比传送数据更有效。例如，有一个作业，它需访问多个驻留在不同系统中的大型文件，以获得这些文件的摘要。 第第9 9章章 分布式计算机系统分布式计算机系统 9.6.2 引入进程迁移的原因 1负荷均衡(Load Balancing) 在分布式系统中，各个系统中的负荷

33、，经常会是不均匀的。此时，可通过进程迁移的方法来均衡各个系统的负荷，即将重负荷系统中的进程迁移到轻负荷系统中去，以改善系统的性能。 第第9 9章章 分布式计算机系统分布式计算机系统 2通信性能 对于那些分布在不同系统中，而彼此交互性又非常强的一些进程，应将它们迁移到同一系统中，以减少由于它们之间频繁地交互而加大的通信费用。 3加速计算 对于一个大型作业，如果始终运行在一台处理机上，可能会花费较多的时间，使作业的周转时间很长；但如果能为该作业建立多个进程，并将这些进程迁移到多个处理机上，使它们并行执行，就会大大加速该作业的完成，从而缩短作业的周转时间。第第9 9章章 分布式计算机系统分布式计算机

34、系统 4需要特殊资源 当某进程必须在具有某种特殊功能的处理机上运行才能完成其任务时，就需要将该进程迁移到该处理机上去运行。 5提高可利用性 在分布式系统中，如果某个系统发生了故障，而在该系统中的进程又希望能继续运行下去，则分布式OS便可将这些进程迁移到其他系统中去运行。 第第9 9章章 分布式计算机系统分布式计算机系统 9.6.3 进程迁移机制 为了实现进程迁移，在分布式系统中必须建立相应的进程迁移机制。该机制应该解决以下几个问题： (1) 由谁来发动进程迁移？ (2) 应迁移进程的哪些部分？ (3) 如何进行进程迁移？ (4) 对尚未完成的报文和消息应如何处理？第第9 9章章 分布式计算机系

35、统分布式计算机系统 1进程迁移的启动 由谁来启动进程迁移，取决于在设计进程迁移机制时所要达到的目标。如果其目标是为了均衡负荷，则在进程迁移机制中，应为各个系统配置系统负荷监视模块，并指定其中之一为主控模块。主控模块定时地与各系统中的监视模块交互有关系统负荷情况的信息。 第第9 9章章 分布式计算机系统分布式计算机系统 2进程迁移前后 在进程进行迁移时，应将源系统中的已迁移的进程撤消，在目标系统中建立一个相同的新进程，此时是所谓的进程迁移而不是进程复制。在进程迁移时，所迁移的是进程实体或称进程映像(Process Image)。通常它都包含进程控制块、程序、数据和栈。此外，被迁移的进程与其他进程

36、之间的链应做适当修改。第第9 9章章 分布式计算机系统分布式计算机系统 3如何进行迁移 (1) 传送整个地址空间。它是指一次性地将程序、数据等全部从源系统传送到目标系统。 (2) 仅传送在内存中的那部分地址空间。在程序运行时若还需要附加的部分，则可通过请求方式予以传送。 第第9 9章章 分布式计算机系统分布式计算机系统 4对未完成报文的处理 在一个进程由源系统向目标系统迁移期间，可能会有其他进程继续向源系统中已迁移的进程发来报文和信号，我们把这些报文和信号称为未完成报文和信号。 第第9 9章章 分布式计算机系统分布式计算机系统 9.6.4 迁移的协商 为了实现这种迁移协商(Negotiatio

37、n of Migration)，在Charlatte系统中设置了一进程迁移机构。它由若干个Starter来决定应将哪些进程迁移到目标系统中去；同时，这些Starter还负责作业调度和内存分配，并使这三项任务协调起来。每一个Starter进程可以管理一组机器(系统)，每当要进行进程迁移时，都需有两个Starter进程参与决定。图9.12是进程迁移的协商示意。进程迁移是按照下述步骤进行协商的。第第9 9章章 分布式计算机系统分布式计算机系统 KJSK JD(3)Starter进程Starter进程P(2)(1)(5)(6)(4)(7)图9.12 进程迁移的协商示意图 第第9 9章章 分布式计算机系

38、统分布式计算机系统 (1) 当Starter已决定将系统S中的进程P迁移到指定的系统D时，便发送一个要求传送进程的报文给系统D的Starter。 (2) 系统D的Starter若准备接受该进程，便返回一同意接收的报文。 (3) 由系统S的Starter向系统S的内核通知这个决定。 第第9 9章章 分布式计算机系统分布式计算机系统 (4) 当系统S的内核接到通知后，先向D发送一份含有被迁移进程P有关信息的报文。 (5) 在D接收到该报文后，如果本系统的现有资源尚不能满足P的运行需要，便拒绝进程P的迁移；否则，由D向本系统的Starter转发报文F。 (6) 由系统D的Starter利用迁入调用(

39、Migration Call)通知D：决定迁入进程P。 (7) D准备好进程P所需要的资源，然后向S发送同意接收的报文。第第9 9章章 分布式计算机系统分布式计算机系统 9.7 分布式操作系统中的进程同步分布式操作系统中的进程同步 1事件排序 在分布式操作系统中，为了实现进程的同步，首先要对系统中发生的事件进行排序，还要有良好的分布式同步算法。第第9 9章章 分布式计算机系统分布式计算机系统 须遵循规则： 第一，根据事件发生的先后，赋予每个事件惟一的逻辑时钟值。 第二，若事件a是进程i发送的一条消息m，消息m中应包含一个时间邮戳T(m)=Ci(a)；当接收进程j在收到消息时，如果其逻辑时钟Cj

40、 Ci(a)，则应当重置Cj大于或等于Ci(a)(通常置Cj= Ci(a) +1)。第第9 9章章 分布式计算机系统分布式计算机系统 其次，看同步算法。在所有的同步算法中，都包含以下四项假设： (1) 每个分布式系统具有N个节点，每个节点有惟一的编号，可以从1到N。每个节点中仅有一个进程提出访问共享资源的请求。 (2) 按序传送信息，即发送进程按序发送消息，接收进程也按相同顺序接收消息。第第9 9章章 分布式计算机系统分布式计算机系统 (3) 每个消息能在有限的时间内被正确地传送到目标进程。 (4) 在处理机间能实现直接通信，即每个进程能把消息直接发送到指定的进程，不需要通过中转处理机。第第9

41、 9章章 分布式计算机系统分布式计算机系统 2Lamport算法 在Lamport算法中，利用事件排序方法，对要求访问临界资源的全部事件进行排序，并按照先来先服务原则，对事件进行处理。该方法规定，每个进程Pi在发送请求消息Request时，应为它打上时间邮戳(Ti，i)(其中Ti是进程Pi的逻辑时钟值)；而在每一进程中都保持一个请求队列，队列中包含了按逻辑时钟排序的请求信息。Lamport算法用下述五个规则定义：第第9 9章章 分布式计算机系统分布式计算机系统 第一，当进程Pi请求访问某个资源时，该进程把请求信息挂在自己的请求队列中，也送一Request(Ti，i)消息给所有其他进程。 第二，

42、当进程Pj收到Request(Ti，i)消息时，形成一个打上邮戳的Reply(Tj，j)消息，将它放在自己的请求队列中。应该说明，若进程Pj在收到Request(Tj，j)前也已提出过对同一资源的访问请求，那么其邮戳时间应比(Ti，i)小。第第9 9章章 分布式计算机系统分布式计算机系统 第三，若满足以下两个条件，则允许进程Pi访问该资源： (1) Pi自身请求访问该资源的消息已处于请求队列的最前面。 (2) Pi已接收到从所有其他进程发来的响应消息，这些响应消息上邮戳的时间晚于(Ti，i)。此条件表明，所有其他进程或者都不访问该资源，或者要求访问，但时间较晚。第第9 9章章 分布式计算机系统

43、分布式计算机系统 第四，为了释放该资源，Pi从自己的请求队列中消去请求信息，且发送一打上时间邮戳的Release消息给其他所有进程。 第五，当进程Pj收到进程Pi的Release消息后，从自己的队列中消去Pi的Request消息。第第9 9章章 分布式计算机系统分布式计算机系统 9.8 分布式操作系统中的进程互斥分布式操作系统中的进程互斥 实现分布式互斥的几点要求如下： (1) 安全性：在某一时刻至多只有一个进程在临界区内执行。 (2) 可用性：请求进入临界段的进程终将准入(只要在临界区执行的进程最终离开临界区)。 (3) 定序：按关系排定的次序进入临界区。第第9 9章章 分布式计算机系统分布

44、式计算机系统 已经提出了许多实现分布式系统中互斥的算法(Lamport 1978；Thomas 1979；Gifford 1979；Ricart and Agrawala 1981；Maekawa l985，等等)。尽管它们的要求和目的各不相同，但这些分布式算法都有如下的基本假定： (1) 一个分布式系统由n个场点组成，它们从1到n惟一地编号，每个场点含有一个进程，而且进程和场点间存在一一对应的关系。第第9 9章章 分布式计算机系统分布式计算机系统 (2) Pipeline特性成立，即从一个进程发送给另一个进程的消息是按它们发送的次序接收的。 (3) 每条消息在有穷的时间间隔内都能正确地传送到

45、它的目的地。 (4) 系统是全互连的，因而每个进程都可直接给其他的进程发送消息。第第9 9章章 分布式计算机系统分布式计算机系统 1集中式算法 用于解决分布式互斥问题的集中式算法中，通常选定某个进程负责协调进入临界区的工作，每个希望进入临界区(引用互斥)的进程都得给协调者进程发送一Request消息，仅当此进程接收到协调者的Reply消息时，它才可以进入它的临界区。当它退出临界区时，此进程发送一Release消息给协调者进程，然后继续它的执行。第第9 9章章 分布式计算机系统分布式计算机系统 2Ricart and Agrawla 算法 Lamport发表的时钟同步算法中给出了第一个互斥算法。

46、Ricart和Agrawala 1981年改进了Lamport算法，而且可以为分布式算法提供时间戳。第第9 9章章 分布式计算机系统分布式计算机系统 Ricart and Agrawala算法的描述如下： (1) 当进程Pi要求访问某个资源时，它发送一个Request(Ti，i)消息给所有其他进程。 (2) 当进程Pj收到Request(Ti，i)消息后，执行如下操作： 若进程Pj正处在临界区中，则推迟向进程Pi发出Reply响应； 若进程Pj当前并不要求访问临界资源，则立即返回一个有时间戳的Reply消息；第第9 9章章 分布式计算机系统分布式计算机系统 若进程Pj也要求访问临界资源，而在消

47、息Request(Ti，i)中的邮戳时间早于(Tj，i)，同样立即返回一个有时间戳的Reply消息，否则Pj保留Pi发来的消息Request(Ti，i)并推迟发出Reply响应。 (3) 当进程Pi收到所有其他进程发来的响应时，便可访问该资源。 (4) 当进程释放该资源后，仅向所有推迟发来Reply消息的进程发送Reply消息。 第第9 9章章 分布式计算机系统分布式计算机系统 该算法能够获得较好的性能：能够实现诸进程对共享资源的互斥访问；能够保证不发生死锁，因为在进程-资源图中没有环路；不会出现饥饿现象，因为对共享资源的访问是按照邮戳时间排序的，即按照FCFS原则服务的；每次对共享资源访问时

48、，只要求发2(N-1)个消息。图9.13说明了进程在访问共享资源时的状态转换。第第9 9章章 分布式计算机系统分布式计算机系统 互斥请求从临界区退出已收到所有的Reply消息给每个其他进程发送一条Request消息将Reply消息回复给正等待进入临界区的进程请求互斥等待计算激活其他进程临界区图9.13 进程在访问共享资源时的状态转换图第第9 9章章 分布式计算机系统分布式计算机系统 3令牌传送法 1) 令牌传送法的基本原理 为了实现进程互斥，在系统中设置了象征存取权利的令牌(Token)。令牌本身是一种特定格式的报文，通常只有一个字节长，它不断地在由进程所组成的逻辑环(Logical Ring

49、)中循环。环中的每一个进程都有惟一的前趋者(Predecessor)和惟一的后继者(Successor)。这样的逻辑结构并不意味任何特定的物理拓扑。第第9 9章章 分布式计算机系统分布式计算机系统 2) 令牌传送法的性能及基本要求 利用令牌传送法实现进程互斥所需的消息数目是不定的。因为不管是否有进程要求进入其临界区，令牌总是在逻辑环中循环。当逻辑环中所有进程都要求进入其临界区时，平均每个进程访问临界资源只需一个消息。 第第9 9章章 分布式计算机系统分布式计算机系统 使用令牌传送法时，必须满足下述两点要求： (1) 逻辑环应能够及时发现环路中某进程失效或退出以及通信链路的故障。一旦发现了这种进

50、程或故障，便应立即撤消该进程，并重构逻辑环。 (2) 必须能保证逻辑环中在任何时候都有个令牌在循环。一旦发现令牌丢失，应立即选定一个进程来产生新令牌。第第9 9章章 分布式计算机系统分布式计算机系统 9.9 分布式系统的资源管理分布式系统的资源管理 资源的调度和管理是操作系统的一项主要功能。单机操作系统通常采用一类资源由一个管理者来管理的集中式管理方法。 第第9 9章章 分布式计算机系统分布式计算机系统 分布式管理方式又可分为集中分布式管理和完全分布式(也称分散)管理两种方式。采用集中分布式管理，一类资源由多个管理者来管，但每个具体资源只存在一个管理者对其负责。 第第9 9章章 分布式计算机系

51、统分布式计算机系统 分布管理方式与集中管理方式的主要区别是对同类资源采用多个管理者还是一个管理者。 集中分布管理方式让资源管理者对他所管理的资源拥有全部控制权，而完全分布管理方式只允许资源管理者对资源拥有部分控制权。采用集中式管理时，一类资源只有一个管理者，他控制这类全部资源。 第第9 9章章 分布式计算机系统分布式计算机系统 9.10 死死 锁锁 处处 理理 分布式系统中的死锁问题与单机系统类似，只是更为复杂，原因是所有与死锁有关的信息都分布在多台机器上。有些人把分布式死锁分为两类：通信死锁与资源死锁。实际上也没有这个必要，因为与通信死锁有关的信道、缓冲区等也是资源，所以完全可以将其归并到资源死锁中。第第9 9章章 分布式计算机系统分布式计算机系统 对死锁问题的处理通常采取如下的策略：(1) 鸵鸟算法(不考虑死锁问题)。(2) 死锁检测(允许死锁发生，检测井恢复)。(3) 死锁预防(静态地使死锁在结构上不可能发生)。(4) 死锁避免(通过精心分配资源，避免死锁)。第第9 9章章