操作系统教程—Linux实例分析 孟庆昌 第10章 分布式系统

第10章分布式系统10.1概述10.2分布式操作系统10.3分布式系统的通信10.4分布式进程管理10.5分布式系统中的同步10.6分布式系统中的死锁10.7分布式文件系统习题10.1概述10.1.1分布式系统特征一般认为，分布式处理是把计算任务和智能由主机分散到构成整个系统的各个子系统和外部设备中，实现系统和资源的动态管理和分配。具有这种结构和功能的完整系统就认为是分布式处理系统（简称分布式系统）。图10-1分布式系统的总体结构分布式系统是多个处理机通过通信线路互连而构成的松散耦合系统。系统中每个站点都是一个完整的计算机系统，有自己的本地内存和I/O设备等资源。在统一的协调和管理下，实现全系统资源的透明共享。如图10-1所示。因此，分布式系统具有以下特征：（1）分布性。（2）自治性。（3）并行性。（4）全局性。10.1.2分布式系统优点1.资源共享若干个不同的站点通过通信网络彼此互连，这样，一个站点上的用户就可以使用其他站点上的资源，如允许设备共享，使众多用户共享昂贵的外部设备，如彩色打印机；允许数据共享，使众多用户访问共用的数据库；可以共享远程的文件，使用远程特有的硬件设备，如高速阵列处理器，以及执行其他操作。2.加快计算速度如果一个特定的计算机任务可以划分成若干并行运行的子任务，那么我们就可以把这些子任务分散到不同的站点上，它们同时在这些站点上运行，从而加快计算速度。3.可靠性高分布式系统具有高可靠性的优点。如果其中某一站点失效了，那么其余的站点可以继续操作，整个系统就不至于因一个或少数几个站点的故障而全体崩溃。分布式系统有很好的容错性能。4.方便快捷的通信分布式系统中各站点通过一个通信网络互连在一起，通信网络是由通信线路、调制解调器和通信处理器等组成的。10.1.3三种多机操作系统的比较在分布式系统中必须有一个单一的、全局进程通信机制，所以任何进程之间都可彼此通信，而且通信机制是相同的，不管是在不同机器上，还是本地通信或者远程通信，都一样，也必须有一个全局保护模式。在分布式系统中任何地方的进程管理都必须相同。不同机器上，进程的创建、终止、启动及停止等都没有区别。在所有机器上都使用同一组系统调用，并且不会产生异样感觉。总之，分布式操作系统与多处理器操作系统和网络操作系统相比，既有相同之处，又有差别。表10-1列出了这三种操作系统之间的某些不同点。表10-1三种多机操作系统的比较10.2分布式操作系统10.2.1分布式操作系统的功能在分布式操作系统中，用户访问远程资源的方式和访问本地资源的方式是相同的。在这种操作系统的控制下，可以实现数据和进程从一个站点到另一个站点的迁移。分布式操作系统要实现用户面前的虚拟单处理机系统到具体的分布式系统的映射。它的基本功能包括：（1）进程管理。（2）通信管理。（3）资源管理。10.2.2分布式操作系统的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 因素1.透明性设计透明性最重要的一个问题或许是如何实现单一系统映像，即如何让每个用户感觉这种分布式系统就是老式的单处理器分时系统，实现这一目标的系统通常被称为是透明的。透明性概念可以用于分布式系统的若干方面。表10-2列出了不同种类的透明性。表10-2分布式系统不同种类的透明性2.灵活性系统应该是灵活的，它可以根据用户需求和使用情况，方便地进行修改或者扩充。操作系统结构有两种主要模型：一种是整体核心，它大而且复杂；另一种是微内核，它小巧灵活，易于扩充或移植。多数分布式系统都采用这种设计模型。微内核是操作系统的极小核心。3.可靠性建立分布式系统的基本目标之一是使它们比单处理器系统更可靠。如果某个机器不能工作了，那么有另外的机器做它的工作。可靠性有几个方面：可用性、安全性和容错性。4.高性能分布式系统有很高的性能，这是不言而喻的。性能指标包括多个方面，如执行速度、响应时间、吞吐量、系统利用率、网络通信能力等等。利用基准测试（Benchmark）手段可以部分度量系统的性能。5.可扩充性扩充可分为水平扩充和垂直扩充，前者是指添加或移去客户工作站对性能影响很小，后者是指移植到更大的或者更快的服务器机器或多服务器上。分布式系统应能根据使用环境的应用需要，方便地扩充或缩减其规模。10.3分布式系统的通信10.3.1ISOOSI参考模型OSI(OpenSystemsInterconnection)参考模型是ISO开发出的协议分层模型。OSI模型共分七层，如图10-2所示。图10-2OSI模型示意各层功能叙述如下：(1)物理层——涉及在物理信道上传输原始比特(即0，1电位)，处理与物理传输介质有关的电气的、机械的和信号的接口。(2)数据链路层——分为介质访问控制(MAC)和逻辑链路控制(LLC)两个子层。(3)网络层——负责将数据从物理连接的一端传到另一端，主要任务是路由选择，以及与之相关的流量控制和堵塞控制等。(4)传输层——通过向上提供一个 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的、通用的界面，使上层与通信子网(下三层)的细节相隔离。(5)会话层——主要任务包括会话管理、传输同步以及活动管理等。它主要针对远程终端访问。(6)表示层——主要功能是信息转换，包括信息压缩、加密、与标准格式的转换(以及上述各操作的逆操作)等。(7)应用层——提供最常用的通用应用程序，包括电子邮件、文件传输和与远程终端的连接等。10.3.2客户—服务器模型如上所述，每次传送一个消息要通过很多层次，还要对消息逐层加头，到接收方又要逐层去头，等等。做这些工作都要花费时间。在广域网上，数据传输速率往往相当慢(如64kb／s)，在这种情况下，上述开销还并不算是严重问题，影响性能的关键因素是线路传输能力。而对于基于LAN的分布式系统来说，这种协议开销就往往很大了。CPU因运行协议而耗费了时间，从而影响了LAN的吞吐能力。所以，多数基于LAN的分布式系统不采用分层协议模型，而采用客户／服务器模型。客户—服务器模型的思想是：把操作系统作为一组协作进程加以构造，它们为用户提供各种服务。用户也称为客户，协作进程也称为服务器。客户和服务器机器通常全部运行相同的微内核，客户和服务器都作为用户进程运行。一台机器可以只运行一个进程，也可以运行多个客户进程、多个服务器进程或者二者的混合。图10-3客户—服务器模型10.3.3远程过程调用尽管客户—服务器模型提供了构造分布式操作系统的简便方法，但它也存在根本缺陷：进行通信要做大量的I/O工作。发送过程和接收过程基本上都忙于I／O。围绕着I／O建立系统并非最佳方法。RPC的思想很简单：允许程序调用另外机器上的过程。当机器A的一个进程(或者线程)调用机器B上的一个过程时，A上的调用进程挂起，被调过程在B上开始执行。调用者以参数形式把信息传送给被调用者，被调用者把过程执行结果回送给调用者。对程序员来说，完全看不到消息传送或者I／O。RPC像一个常规过程，要进行同步。调用者发出命令后一直等待着，直到它得到结果。RPC把过程调用在网络环境所产生的各种复杂情况都隐藏起来。10.3.4组通信在上面通信模式中认为通信只涉及两个进程：发送进程和接收进程。但在实际的系统中，通信可能涉及到多个进程。所谓组是进程的集合，它们按照某个系统或用户指定的方式协同工作。组的重要特性是：当某个消息发送到一个组时，组内的所有成员都能接收到该消息。可见，组通信具有“一对多”的形式，即一个发送者、多个接收者，而不是简单的“点—点”的通信方式。组是动态的。可以创建新组、撤消旧组；一个进程可以加入某个组，也可以离开某个组；一个进程可以同时是多个组的成员。为此，需要有一个机制来管理组和组成员。（1）组播。在一些网络中，可以为组指定一个特殊的网络地址（例如，将节点机网络地址的高位置1），该组的成员利用这个地址进行监听。（2）广播。有的网络不允许组播，那么可以采用广播方式。（3）单播。如果网络不支持组播和广播方式，那么就采用单播方式实现组通信，即让消息发送者分别给组的每个成员发送消息。10.4分布式进程管理10.4.1进程迁移1.数据迁移（DataMigration)假设站点A上的用户想访问站点B上的数据（例如一个文件），系统传送数据的方法有两种：整体传送和部分传送。（1）整体传送。就是把那个文件整体地从站点B传送到站点A。（2）部分传送。仅把文件中用户当前需要的那部分从站点B传到站点A。2.计算迁移（ComputationMigration）在某些情况下，传送计算比传送数据更有效，这种方法称为计算迁移。3.进程迁移（ProcessMigration）进程迁移是计算迁移的逻辑延伸。当一个进程被提交执行时，并不一定始终都在同一站点上运行，整个进程或者其一部分可能在不同的站点上执行。在分布式系统中引入进程迁移可以使各站点工作负载平衡，加快计算速度，为进程运行提供更合适的硬件和软件环境，另外也避免大量数据迁移带来的影响。有两种技术可用于进程迁移。第一种是系统对客户隐藏进程迁移的事实。这种方式的优点是，用户不必显式地编写程序来实现进程迁移。这种方式往往用于在同构系统间实现负载均衡和加速计算。另一种方式是允许（或要求）用户显式地指定进程应如何迁移。这种方式往往用于为了满足偏爱硬件或软件的特定条件而必须迁移进程的情况。10.4.2分布式系统的进程管理在分布式系统中往往采用线程概念实现进程管理。如第2章所述，线程是一个独立的执行单位，一个线程只能属于一个进程，一个进程可以有多个线程，但至少有一个线程。同一进程的所有线程共享该进程的所有资源。线程创建快速、维护方便，可以更自然地共享数据，提供非常经济的多任务形式。线程允许并行机制。例如有一个文件服务器，在它的进程内线程的组织形式可以有三种：分派者/工作者模式、工作组模式和管道模式，如图10-4所示。图10-4一个进程内的三种线程组织形式(a)分派者/工作者模式；(b)工作组模式；(c)管道模式10.4.3处理器分配分布式系统由多个处理器组成。它们可以构成个人工作站集合体、公用处理器池或者某种混合形式。在各种情况下都需要采用某种算法来决定哪个进程在哪台机器上运行。处理器的分配策略主要分为两类：非迁移型和迁移型。10.5分布式系统中的同步分布式系统的同步机制比集中式系统更为复杂。在集中式系统中可以把系统的所有信息收集到一个地方，然后由某个进程检测这些信息，再做出同步决策。而在分布式系统中往往不可能这样做。分布式系统使用分布式算法，一般有以下特点：（1）相关信息分布在多台机器上；（2）进程只根据本地可用的信息做出决策；（3）应避免系统中因单机失效而使系统工作不可靠；（4）没有公共时钟或其他精确的全局时间源。10.5.1事件排序在分布式系统中没有全局一致的时间，每个机器都有自己的时钟，因此，时钟之间的不同步会产生戏剧性的结果：一件后面发生的事反而可能被赋予较早的发生时间。这种情况下，象make之类的程序就无法得到正确结果。定义一组事件的前趋关系如下：（1）若A和B是同一进程的两个事件，且A在B之前发生，则有前趋关系A→B。（2）若A是一个进程发送消息的事件，而B是另一个进程接收该消息的事件，则A→B。（3）若A→B且B→C，则A→C，即前趋关系有传递性。10.5.2互斥1.集中式算法集中式算法是对单处理器系统中互斥方法的模拟，其基本思想是：在系统的所有活动进程中选择一个进程作为协调者（即运行在最高网址的机器上的某个进程）。2.分布式算法由于协调者的故障会导致系统的瘫痪，这通常是不可接受的。于是，研究人员提出了分布式算法。该算法的工作过程描述如下。当某个进程想进入临界区时，它就建立一个消息，其中包含临界区名、进程号和时间戳，然后将该消息发送给系统中所有进程（概念上也包括自己）。假定消息发送是可靠的，即每个消息都得到确认。如果存在可靠的组通信，就采用组通信方式。当一个进程收到其他进程发来的消息后，执行下列操作：（1）如果接收者不在临界区内且不想进入，则立即返回一个OK消息给发送者。（2）如果接收者在临界区内，则不做任何响应，只是将该请求送入等待队列。（3）如果接收者也想进入临界区，但尚未进入，则将自己请求消息的时间戳与所接收的消息的时间戳进行比较。分布式算法可以实现进程间的互斥，而且不会产生死锁和饥饿。但是该算法存在以下问题：（1）每个想进入临界区的进程必须知道系统中所有进程的名字。（2）如果系统中有一个进程失效，则必然使发出请求消息的进程无法收到全部响应，而默认为访问被拒绝。（3）没能进入临界区的进程必须频繁地暂停，以便其他进程进入临界区。3.令牌环算法令牌本身是一种特定格式的报文。系统中的进程一旦持有令牌，便具有进入临界区的权利。由于系统中仅有一个令牌，因此在任何时刻，只能有一个进程在临界区内。系统中的进程在逻辑上（而不是物理拓扑）组成一个环，环中每个进程都有惟一的前趋者和惟一的后继者。令牌在环中循环。10.6分布式系统中的死锁10.6.1死锁的检测在分布式系统中所采用的死锁检测算法其基本原理与在集中式系统中采用的是相同的，即首先按照各进程之间对共享资源的占有和申请情况，构成进程等待图，然后检测该等待图。1.集中式死锁检测法在该算法中，每个节点维持自己的进程—资源图，同时用一个中心协调者维护整个系统的资源图（是所有单个图的并集）。2.分布式死锁检测法每台机器上的进程可能等待本地资源，也可能等待分布在其他机器上的资源。10.6.2死锁的预防死锁的预防算法的基本思想是：进程因等待另一进程正在使用的资源而被阻塞时，先检查它们的时间戳哪个大（即更年轻），如果等待进程的时间戳小于被等待进程的时间戳（即更老），就允许进程阻塞等待。按照这种办法，沿着任何等待链，时间戳都是增加的，因此不会出现环路。10.7分布式文件系统10.7.1文件服务接口文件可以有属性，它是有关该文件的若干信息，但并不是文件本身的一个部分。典型的文件属性有文件主、大小、创建日期和存取权限。通常文件服务提供了对某些属性进行读、写的原语。通常情况下，文件被创建后可以进行修改。但在某些分布式系统中对文件的操作只有CREATE和READ。这样，一旦文件被创建，它就是不变的。其好处是很容易支持文件缓存和复制。分布式系统中文件保护所用技术基本上与单CPU系统相同：存取权限和存取控制表。存取权限针对用户，指明其拥有的存取类型；存取控制表针对文件，它指明每个文件允许哪类用户进行何种访问。文件服务可分成两种类型：上载／下载模式和远程存取模式。前者如图10-5(a)所示，文件服务仅提供两个主要操作：读文件和写文件。读文件把整个文件从一个文件服务器传送到所需的客户；写文件把整个文件从客户传到服务器。整个文件可在两个方向上移动。根据需要，文件可存于内存或本地磁盘上。上载／下载模式的优点是概念清晰。图10-5文件服务的两种类型(a)上载/下载模式；(b)远程存取模式10.7.2目录服务器接口目录服务提供的操作有创建和删除目录、命名和重新命名文件，把文件从一个目录移到另一个目录。目录服务的特性并不依赖于单个文件是整体传送还是远程存取。文件名由字母、数字和某些专用字符组成。有的系统把文件名分为两部分——文件名和扩展名，后者标识文件类型。所有分布式系统允许目录包含子目录，从而用户可把相关文件组织在一起。子目录还可包含子目录，构成树型目录，往往称为层次文件系统，如图10-6(a)所示。在某些系统中可以建立任意目录间的链接，从而不仅构成目录树，而且构成任意目录图，其功能更强。如图10-6(b)所示。树和图之间的差别在分布式系统中格外重要。图10-6分布式系统目录结构(a)在一个机器上包含的目录树；(b)在两个机器上的目录图1.命名透明性这种路径命名形式的基本问题是非完全透明性。透明性有两种形式——位置透明性和位置无关性。前者只表明路径名，并未给出文件(或其他对象)位于何处的暗示。如路径／server1／dir1／dir2／ff告诉ff位于服务器1上，但并未告诉服务器1位于何处。该服务器可自由移到网中的任何地方，不必修改路径名。这样该系统就具有位置透明性。2.二级命名多数分布式系统采用二级命名形式，即符号名和二进制名。前者供用户使用，如prog.c，后者由系统内部使用。实际上目录所做的工作就是在这两级命名之间提供映射。用户(和程序)使用符号名(ASCII)打开文件，系统立刻在相应目录中查找该名，得到对应的二进制名，然后用它实际定位文件。10.7.3文件共享语义当两个或更多个用户共享同一文件时，必须精确定义读/写语义，以避免出现问题。像在UNIX这样的单处理器系统中，写之后进行读，读返回的值就是刚写入的值。连续两次写之后进行读，读的值是最后一次所保存的值。实际上，这种系统对所有操作按绝对时间排序，返回值总是最近的一个，这种模式称为UNIX语义。在分布式系统中，只要仅有一个文件服务器，并且客户不缓存文件，那么也容易实现UNIX语义。但实际上这种系统的性能相当差。解决这个问题的常用办法是允许客户在自己的缓存中保持常用文件的本地拷贝。然而如果一个客户在本地修改了缓存中的文件，不久之后另一个客户从服务器读取该文件，就会得到一个过时的文件。习题1.什么是分布式系统？2.简述分布式系统的主要特征。3.你认为分布式系统有什么优点？4.试比较三种多机操作系统的异同之处。5.设计分布式操作系统时应主要考虑哪些因素？6.在客户—服务器模型中，进程间如何进行通信？7.为什么要进行进程迁移？8.在分布式系统中为什么要进行事件排序？9.什么是逻辑时钟？什么是时间戳？如何利用时间戳实现分布式系统中事件的排序？10.分布式系统中实现互斥的常用方法有哪些？11.分布式系统中检测死锁的常用方法是什么？12.何谓文件服务？何谓文件服务器？13.在分布式文件系统中文件服务有哪两种常用类型？各自如何工作？