分布式操作系统复习(汇总).docx

一、 名词解释

1. 中间件：指一个软件层，放在应用程序和网络操作系统之间，它提供了一个编程抽象以与对底层网络、硬件、

操作系统和编程语言异构性的屏蔽。

2. RPC：RPC 是 remote procedure call（远程过程调用）的简称。RPC 思想是使远程的过程调用就像在本地的过

程一样，调用者不应该意识到此调用的过程是在其他机器上实行的。

3. 名称解析：在名称空间中，根据节点的路径名，就可以寻找到这个节点所存储的任何信息，这个查找的过程

就称为名称解析。

上分布，逻辑上是一个整体。

 硬件方面：每台计算机都是独立、自主的计算机

 软件方面：用户感觉在独占系统

分布式系统发展的前提条件有：

 计算机性能价格比在迅速提高

 网络技术的发展与普与：有线网络、移动计算、无处不在的计算

 计算量增大

 任务本身需要分布式处理

例：

 工作流处理系统：订单自动处理、办公自动化、电网调度等系统

2.什么是 RPC？试简述 RPC 的执行步骤。

答：RPC 是 remote procedure call（远程过程调用）的简称。RPC 思想是使远程的过程调用就像在本地的过程一

样，调用者不应该意识到此调用的过程是在其他机器上实行的。

RPC 的执行步骤：

(1) 客户过程以普通方式调用相应的客户存根；

(8) 远程核将消息发送至客户核；

(9) 客户核将消息交给客户存根；

(10)客户存根将消息解包，从中取出结果返回给客户；

3.常见的选举算法有哪几种？简述他们的算法实现过程。

答：常见的选举算法有：欺负算法、环算法。

欺负算法:

当一个进程 P 发现协调者不响应请求时，它就发起选举；

进程 P 向所有都比它大的进程发送选举消息；

若无人响应，P 获胜成为协调者；

若有大的进程响应，响应者接管选举，P 的工作完成。

该消息将再一次绕环运行，向所有的进程通知谁是协调者（在成员表中进程最大的那个）和新的环成员。

4.简述三种分布式互斥算法（集中式算法、分布式算法、令牌环算法）的算法思想。

答：集中式算法

选一个进程为协调者（比如在最大网络地址的进程）；无论什么时候进程要进入临界区，它将向协调者发送请求信

息，说明它想进入那个临界区并希望获得允许；

如果当前该临界区没有其它任何进程，协调者就发送允许进入信息，当应答到达时，请求者就可以进入临界区；

分布式算法：

当某进程想进入临界区时，它要建立一个消息，包括：

令牌环算法：

构造一个逻辑环，设置一个令牌，令牌在环上依次传递。

获 得 令 牌 后 才 可 以 决 定 是 否 进 入 临 界 区 ， 如 果 离 开 了 临 界 区 或 不 打 算 进 入 临 界 区 ， 则 将 令 牌 下

传 。

不允许使用同一令牌进入第二个临界区

6.试分别解释严格一致性、顺序一致性、因果一致性、PRAM 一致性等几种以数据为中心的一致性模型的含义。下

图中的事件序列对上述哪几种一致性模型是有效的？

7.一致性协议中，复制的写协议有哪几种？请简单解释。

8.在 RPC 中，如果客户机在发送请求后在服务器应答消息到来之前崩溃了，将会发生什么问题？如何解决？

解答：发生现象：客户机在发送请求后在服务器应答消息到来之前崩溃，其已经激活了服务器的相应计算，而客

户没有等待它的结果，将遗留“计算孤儿”。

清除“孤儿”方法：

a) 根绝（extermination）法：客户存根发送 RPC 前在日志文件中记录将要执行的 RPC，若客户重启则依据

答：分布式系统中，文件共享的语义有 Unix 语义、对话语义、不可更改文件语义、事务处理语义等几种。

Unix 语义：当 READ 操作紧跟在 WRITE 操作后执行时，READ 操作返回刚写入的值。当 READ 操作跟在两个紧连的 WRITE

答：所有允许的(读团体, 写团体) 有：(1,10), (2, 9), (3, 8), (4, 7), (5, 6)

11.某多计算机系统中的 256 个 CPU 组成了一个 16X16 的网格方阵。在最坏的情况下，消息的延迟时间有多长(以

跳(hop)的形式给出，跳是结点之间的逻辑距离)?

答：假设路由是可选的，最长的可选路由是从网格中的一个角落到达与其相反的角落，这段路由的长度为 30 跳。

12.举出一个例子，在这个例子中，为了真正访问实体 E，需要把他的地址进一步解析成另一个地址。

答：在因特网中，IP 地址通常就是所谓主机地址，然而，要访问一台主机，就要将主机 IP 地址解析为以太网地址。

14.文件更新有哪几种主要算法？简述其算法思想？

15.说明分布式系统相对于集中式系统的优点和缺点。 从长远的角度看，推动分布式系统发展的主要动力是什么？

答：相对于集中式系统，分布式系统的优点：1）从经济上，微处理机提供了比大型主机更好的性能价格比；2）

从速度上，分布式系统总的计算能力比单个大型主机更强；3）从分布上，具有固定的分布性，一些应用涉与到空

间上分散的机器；4）从可靠性上，具有极强的可靠性，如果一个极强崩溃，整个系统还可以继续运行；5）从前

景上，分布式操作系统的计算能力可以逐渐有所增加。

分布式系统的缺点：1）软件问题，目前分布式操作系统开发的软件太少；2）通信网络问题，一旦一个系统依赖

网络，那么网络的信息丢失或饱和将会抵消我们通过建立分布式系统所获得的大部分优势；3）安全问题，数据的