进程2007级分布试操作系统试卷答案

《分布式操作 系统》 试题答案2007级 

一、综合题(每题10分 共100分  占总成绩的 60%)

1. 什么是分布式系统比较分布式操作系统、 网络操作系统、多处理机分时操作系统的特点和应

用范围。

答分布式系统是由一组具有自治功能的独立计算机构成的系统在用户看来好像是一个计算机系统一样。物理上分布逻辑上是一个整体。

2. 什么是RP C试简述RP C的执行步骤。

答 RPC是remote procedure call 远程过程调用的简称。 RPC思想是使远程的过程调用就像在本地的过程一样调用者不应该意识到此调用的过程是在其他机器上实行的。

RPC的执行步骤

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

(2)客户存根建立消息打包并激活内核陷阱

(3) 内核将消息发送到远程内核

(4)远程内核将消息发送到服务器存根

(5)服务器存根将消息解包取出其中参数后调用服务器过程

(6)服务器完成工作或将结果返回服务器存根

(7)服务器存根将它打包并激活内核陷阱

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

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

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

1

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

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

欺负算法:

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

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

若无人响应 P获胜成为协调者

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

环算法:

假设所有进程是按物理或逻辑排序形成没有令牌的环每一个进程都知道谁是它的后继者 

当任何一个进程发现协调者不再起作用时它就构造一个包含它自身进程号的选举消息发送给它的后继者直到找到一个进程

每次发送者都将自己的进程号加入到消息中 当消息回到始发者的手中始发者接收到包括自己进程号的消息转成协调者消息。

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

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

答集中式算法

选一个进程为协调者比如在最大网络地址的进程

无论什么时候进程要进入临界区它将向协调者发送请求信息说明它想进入那个临界区并希望获得允许

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

分布式算法

当某进程想进入临界区时它要建立一个消息包括a 它要进入的临界区的名字b 它要进入的处理机号c 当前时间

将消息发送给所有其它进程发送的消息假设是可靠的 即每条消息都应该被确认当一个进程接收另一个进程请求消息时它取决于接收方的状态以及临界区的命名。有三种情况要加以区别

(1)接收者不在临界区中也不想进入临界区它就向发送者发送OK消息

(2)接收者已在临界区中它就不必回答而是负责对请求队列排队

(3)接收者要进入临界区消息时间戳对比取小的那个a 如果来的消息的时间戳小接收者发送OK消息b 如果接收者本身时间戳更小接收者负责排列请求队列而不发送任何消息

令牌环算法

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

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

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

2

5. 简述处理机分配算法中图论算法的工作步骤。

答

图论算法的思想

整个系统可以表示为一张带权图每个节点表示一个进程

子图内每条边表示两个进程之间的通信量

从一个子图连向另一个子图的边表示网络通信

6. 试分别解释严格一致性、顺序一致性、因果一致性、 PRAM一致性等几种以数据为中心的一致性模型的含义。下图中的事件序列对上述哪几种一致性模型是有效的

RX 1 WX 2

P2

P4 RX 1 RX 2 RX 3

解答

严格一致性模型所有共享访问事件都有绝对时间顺序

顺序一致性模型所有进程都以相同的顺序检测到所有的共享访问事件

因果一致性模型所有进程都以相同的顺序检测到所有因果联系的事件

PRAM一致性模型所有的进程按照预定的顺序检测到来自一个处理器的写操作来自其他处理器的写操作不必以相同的顺序出现

图中的事件序列对因果一致性、 PRAM一致性是有效的。

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

答复制的写协议写操作可以在多个副本上执行。包括两种类型主动复制和基于法定数量的协议。

主动复制每个副本有一个关联的进程该进程执行更新操作。操作被发送到每个副本。基于法定数量的协议其基本思想是在读或写一个复制的数据项之前要求申请并获得多个服务器的允许。

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

解答发生现象客户机在发送请求后在服务器应答消息到来之前崩溃其已经激活了服务器的相应计算而客户没有等待它的结果将遗留“计算孤儿” 。

清除“孤儿”方法

3

a) 根绝exter minat ion法客户存根发送RPC前在日志文件中记录将要执行的RP C若客户重启则依据日志作准确清除远程计算。b) 再生reinc arnat ion法划分时间为序号纪元时间戳客户重起则广播新纪元开始所有远程计算被终止。c) 温和再生gentl ereinc arnat ion法改进“再生”法 由服务器检查远程计算有无调用者若无则远程计算被终止。d) 过期expin ratio n 法每个rpc执行前给定时间段T rpc到期未完成的必须再申请新

的T。服务器将清除没有再申请新的T的rpc。

9. 分布式系统中文件共享的语义有哪几种阐述各自的工作原理。

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

Unix语义当READ操作紧跟在WRITE操作后执行时 READ操作返回刚写入的值。当READ操作跟在两个紧连的W RITE操作后时读出的值就是后一个写入的值。强调绝对时间顺序

对话语义对一个打开文件的修改仅对修改该文件的进程机器是可见的仅当文件关闭时其修改才对其他进程或机器可见。

不可更改文件语义只有创建和读文件操作。

事务处理语义存取文件时进程执行开始事务处理 以指示跟在其后的操作是不可分的通过系统调用来读写文件。当此工作完成后执行结束事务处理原语。

10.一个文件在10个服务器上复制试列举基于法定数量的协议所有允许的读团体与写团体。答所有允许的(读团体,写团体)有 (1,10), (2,9), (3,8), (4,7), (5,6)

二、小论文占总成绩的 30%

答案略

4