第9章 分布式计算机系统ppt课件计算机操作系统汤小丹梁红兵版

第9章分布式计算机系统第9章分布式计算机系统9.1分布式计算机系统9.2分布式系统的设计9.3分布式系统中的通信问题9.4消息传递9.5远程过程调用9.6进程迁移第9章分布式计算机系统9.7分布式操作系统中的进程同步9.8分布式操作系统中的进程互斥9.9分布式系统的资源管理9.10死锁处理习题第9章分布式计算机系统9.1分布式计算机系统9.1.1概述网络技术的发展使一些计算机系统从集中式走向分布式，那么什么是分布式系统呢?分布式计算机系统(DistributedComputerSystems)是由多个分散的计算机经互连网络连接而成的计算机系统。第9章分布式计算机系统分布式计算机系统是多机系统的一种新形式，它强调资源、任务、功能和控制的全面分布。就资源分布而言，既包括处理机、I/O设备、通信接口、后援存储器等物理设备资源，也包括进程、文件、目录、表、数据库等逻辑资源。它们分布于物理上分散的若干场点中，而各场点经互连网络沟通，彼此通信，构成统一的计算机系统。第9章分布式计算机系统网络操作系统是为计算机网络配置的操作系统，网络中的每台计算机配置各自的操作系统，通过网络操作系统把它们有机地联系起来。因此，它除了具有一般操作系统所具备的存储管理、处理机管理、设备管理、信息管理和作业管理等功能外，还应具有以下网络管理功能：(1)高效可靠的网络通信能力。(2)多种网络服务功能，包括远程作业录入、分时系统服务和文件传输服务等。第9章分布式计算机系统(1)进程通信不能借助公共存储器，因而常采用信息传递方式。(2)系统中的资源分布于多个场点，因而进程调度、资源分配及系统管理等必须满足分布处理要求，并采用保证一致性的分散式管理方式和具有强健性的分布式算法。(3)不失时机地协调各场点的负载，使其达到基本平衡，以充分发挥各场点的作用。(4)故障检测与恢复及系统重构和可靠性等问题的处理和实现都比较复杂。第9章分布式计算机系统9.1.2分布式系统的特征由分布式系统的定义可知，分布式系统是由多台计算机组成的系统。更确切地说，分布式系统是具有以下特点的多计算机系统。(1)分布性：组成系统的部件在物理上是分散的，这些部件包括处理机、数据、算法和操作系统。(2)自治性：系统所有的软硬件资源都是高度自治的，它们能够独立执行任务、提供或拒绝提供服务。第9章分布式计算机系统(3)透明性：系统的分布性、操作和实现对用户完全透明，用户只需提出所需服务，而不必要指明由哪一台设备在什么位置用什么方法来提供这些服务。(4)共享性：系统中的资源为系统中所有用户所共享，在某台计算机终端上的用户，不仅可以使用位于该机上的资源，而且还可以使用位于它机上的资源。(5)协同性：系统中的若干台计算机可以相互协作来完成一个共同任务，或者说，一个程序可以分布在几台计算机上并行运行。第9章分布式计算机系统分布式系统应具备以下三种基本功能：(1)通信。系统提供某种通信机制，使得运行在不同计算机上的用户程序可以利用网络来交换信息。(2)资源共享。系统提供访问它机资源的功能，使得在某机或其终端上的用户或用户程序可以访问位于它机的资源。(3)协同工作。系统提供某种程序设计语言，使得用户可以用它编写能够分布在若干台计算机上并行执行的应用程序，同时系统提供这些应用程序(进程)之间的协调和通信。第9章分布式计算机系统9.1.3分布式系统的结构分布式系统中的场点可用不同的方式将它们从物理上连接起来，每种方式都有其优缺点，下面简单讨论几种常用的连接方式并按以下标准来比较它们的性能。基本开销：连接系统中的各个场点需要多少花费?通信开销：从场点Ai发送信息到场点Aj需要多少时间？(i，j=1，2，3，…，n)可靠性：若系统中某场点或通信线路出现故障，余下的场点是否仍能彼此通信?第9章分布式计算机系统1．全互连结构在一个全互连结构中，每个场点都直接与系统中所有其他的场点相连，如图9.1所示。第9章分布式计算机系统A2A1A4A5A3图9.1全互连结构第9章分布式计算机系统2．部分互连结构在一个部分互连结构中，有些场点间存在直接通信链路，但有些则没有，如图9.2所示。因此这种构形的基本开销比全互连结构要低，但场点间的消息传递可能经由若干中间的场点，以致延缓了通信速度。第9章分布式计算机系统图9.2部分互连结构发消息A1A4A2A3A5第9章分布式计算机系统3．层次结构层次结构中的各场点组织呈树形结构，如图9.3所示。其中，每一场点(根除外)有一个惟一的父节点和若干个(或0个)子节点。这种结构的基本开销一般小于部分互连结构。第9章分布式计算机系统图9.3层次结构A3A4A2A5A1A6第9章分布式计算机系统4．星形结构在星形结构中，系统中的场点之一与系统中所有其余场点相连，其他的场点之间彼此不直接相连，如图9.4所示。第9章分布式计算机系统图9.4星形结构A5A4A1A3A2A6第9章分布式计算机系统5．环形结构在环形结构中，每个场点物理上恰好与另外两个场点相连，如图9.5(a)所示。在双向环形结构中，其中两条通信链路故障就可能导致分割整个系统。在单向环形结构中，单个场点或单条通信链路故障，就可能分割整个系统。一种补救的办法是通过提供双通信链路来扩充这种结构，但这显然会增加基本开销，如图9.5(b)所示。第9章分布式计算机系统A8A7A6A5A4A3A2A1(a)(b)A8A7A6A5A4A3A2A1图9.5环形结构(a)单通信链路；(b)双通信链路第9章分布式计算机系统6．多存取总线结构在多存取总线结构(简称总线结构)中，有一条共享的通信链路(即总线)。系统中所有的场点都直接与这条通信链路相连，它可以组织成直线状(见图9.6(a))，也可以组织成环形(见图9.6(b))，其中的场点可以经由这条总线彼此直接进行通信。第9章分布式计算机系统……AnA1A2A3A4A5A6AnA3A2A1(a)(b)图9.6总线结构(a)线形总线；(b)环形总线第9章分布式计算机系统7．立方体结构立方体结构又称n维立方体分布式网络结构。这种结构把2n＝N个计算机互连起来，各计算机分别位于该立方体的角顶。立方体的每条边把两个场点连接起来，而每个场点则有n个全双向通路把它和n个其他计算机相连。例如，n＝3和n＝4时立方体互连结构分别如图9.7(a)、(b)所示，其中，n为立方体的维数。第9章分布式计算机系统(a)(b)图9.7立方体结构(a) n=3,N=8；(b) n=4,N=16第9章分布式计算机系统9.1.4分布式系统的设计方法传统上，分布式操作系统是按面向进程的方法设计的，近年来提出了面向对象的分布式操作系统的设计方法，它与面向进程的分布式操作系统的设计方法的主要区别是：前者将操作系统视为对象的集合，而且有关用户(进程)对象和系统状态的同步及控制是通过权限(Capability)的管理和分配完成的；而后者则把操作系统看作是进程的集合，有关用户进程和系统状态的同步及控制是通过消息传递实现的。第9章分布式计算机系统9.2分布式系统的设计1．透明性(Transparency)分布式系统的透明性具体表现在：(1)位置透明性。在一个分布式系统中，用户不必知道硬件或软件资源的具体位置。资源的名字不能用资源的位置编码。第9章分布式计算机系统(2)迁移(Migration)透明性。迁移透明性是指资源可以随意从一个计算机(节点)迁移到另一个计算机上，而无需改变资源的名字。(3)复制(Replication)透明性。复制透明性是指用户不知道系统拥有多少副本。(4)并发(Concurrency)透明性。(5)并行(Parallelism)透明性。用户所看到的一个分布式系统是一个单机形式。第9章分布式计算机系统2．灵活性(Flexibility)分布式系统设计的第二个关键问题是灵活性。灵活性涉及到分布式操作系统的结构。分布式操作系统结构有两种不同的形式：一种是单内核(MonolithicKernel)，另一种是微内核(MicroKernel)，如图9.8所示。第9章分布式计算机系统用户程序包括文件、目录和进程管理网络微内核文件服务器微内核目录服务器微内核进程服务器微内核用户程序单内核图9.8分布式操作系统结构(a)单内核；(b)微内核第9章分布式计算机系统微内核结构更加灵活，是一种新的结构，仅仅提供以下四种服务：(1)进程间通信机制；(2)某些内存管理；(3)有限的低级进程管理和调度；(4)低级的输入输出。第9章分布式计算机系统3．可靠性(Reliability)最初分布式系统的设计原因之一是它比集中式系统可靠性更高，即一台机器坏了，其他机器能够接替它的工作。换句话说，在理论上系统可靠性是所有部件可靠性的布尔“或”。第9章分布式计算机系统4．性能(Performance)性能是设计任何一个系统都需要重视的问题。一个分布式系统的透明性再好，灵活性再强，可靠性再高，而它的性能很差，速度很慢，也就失去了建立分布式系统的意义。如何衡量分布式系统性能的好坏是一个有待进一步研究的问题。第9章分布式计算机系统5．可扩展性(Expansibility)在建立一个分布式系统之前，分布式系统的规模也是必须考虑的问题，即所设计的系统应是可扩展的，应避免潜在的瓶颈：集中式部件、集中式表格和集中式算法。第9章分布式计算机系统9.3分布式系统中的通信问题在分布式系统中的通信应注意以下几个方面的问题：发送策略：如何通过通信网发送消息?连接策略：如何去连接彼此希望通信的进程?争夺处理：由于通信网是共享资源，应注意解决在利用它的过程中哪些有冲突的要求和冲突现象。保密：如何保住消息内容的秘密?通信机制：研究分布式操作系统中的基本通信机制。第9章分布式计算机系统9.3.1发送策略当场点A1上的一进程希望同场点A2上的另一进程进行通信时，如何发送消息呢?若从A1到A2之间只有一条物理信道(好像在一个星形结构或层次结构中)，那么，该消息只能经由这条信道发送。若从A1到A2存在多条物理通路，那么，发送该消息就有选择性了。第9章分布式计算机系统(1)固定发送：从A到B的信道事先已规定好且不得更改，除非硬件方面的故障影响到它的通信能力。通常是选择(物理上长度)最短的信道，以减少通信开销。(2)虚拟线路：从A到B的信道在一段时间内是固定的，在不同时期，从A向B发送的信息可能经由不同的信道发送。(3)动态发送：用于从A到B发送信息的信道仅当该消息发送之时才被确定。第9章分布式计算机系统9.3.2连接策略1．线路转换假设两个进程之间需要通信，那么在它们通信期间应建立一永久性的物理通信链路，在这段时间其他进程不能使用这条链路。这种方案与电话系统类似，一旦一通话线路已对两方开放(如甲方给乙方打电话)，其他的人就不可能使用这条信道，除非甲、乙两方的通话结束(如一方已挂上听筒)。第9章分布式计算机系统2．消息转换假设两个进程之间需要通信，那么确定一临时通信链路供其消息传递期间使用。物理通信链路则根据需要在用户间动态地进行分配，而且只允许使用较短的一段时间。每条消息由一个数据块再附加一些系统信息(如发送地、接收地、错误校正码等)组成，这些系统信息辅助通信网络正确地将消息传递到目的地。这种方案与邮局系统类似，每封信可看作是包含发送地和接收地的一条消息，而且来自不同用户的信件(消息)可在相同通信线路上传递。第9章分布式计算机系统3．消息包转换消息一般是可变长度的。为了简化系统的设计，常常把消息设计成定长的形式，并把这种定长的形式称为消息包(Packet)。一条逻辑消息可能不得不划分成若干消息包，每个消息包都可以经由网络中不同的路径单独发送到其目的地，当这些消息包都到达其目的地后，还得拼装起来组成一条完整的消息。第9章分布式计算机系统9.3.3争夺处理1．冲突检测一个场点要在某条通信线路上传递消息之前，必须进行监测以确定当前在该通信线路上是否正在传递另外的消息。若该通信线路空闲，则这个场点可以开始发送，否则它必须等待(同时继续监测)，直到这条线路空闲。第9章分布式计算机系统2．令牌传递(TokenPa