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