2007级_分布试操作系统_试卷答案.doc

分布式操作系统 试题答案（2007级）一、综合题(每题10分，共100分；占总成绩的60%)1. 什么是分布式系统？比较分布式操作系统、网络操作系统、多处理机分时操作系统的特点和应用范围。答：分布式系统是由一组具有自治功能的独立计算机构成的系统，在用户看来好像是一个计算机系统一样。物理上分布，逻辑上是一个整体。项目网络操作系统分布式操作系统多处理机分时操作系统表现是否象一台单机否是是各台机器是否运行同样的操作系统否是是操作系统有多少拷贝多多1通信如何完成共享文件消息共享存储器是否要求一致的网络协议是是否是否具有唯一的运行队列否否是文件共享是否具有统一的语义通常没有有有2. 什么是RPC？试简述RPC的执行步骤。答：RPC是remote procedure call（远程过程调用）的简称。RPC思想是使远程的过程调用就像在本地的过程一样，调用者不应该意识到此调用的过程是在其他机器上实行的。RPC的执行步骤：(1) 客户过程以普通方式调用相应的客户存根；(2) 客户存根建立消息，打包并激活内核陷阱；(3) 内核将消息发送到远程内核；(4) 远程内核将消息发送到服务器存根；(5) 服务器存根将消息解包，取出其中参数后调用服务器过程；(6) 服务器完成工作或将结果返回服务器存根；(7) 服务器存根将它打包并激活内核陷阱；(8) 远程内核将消息发送至客户内核；(9) 客户内核将消息交给客户存根；(10) 客户存根将消息解包，从中取出结果返回给客户；3. 常见的选举算法有哪几种？简述他们的算法实现过程。答：常见的选举算法有：欺负算法、环算法。欺负算法:当一个进程P发现协调者不响应请求时，它就发起选举；进程P向所有号码都比它大的进程发送选举消息；若无人响应，P获胜成为协调者；若有大的进程响应，响应者接管选举，P的工作完成。环算法:假设所有进程是按物理或逻辑排序，形成没有令牌的环，每一个进程都知道谁是它的后继者；当任何一个进程发现协调者不再起作用时，它就构造一个包含它自身进程号的选举消息发送给它的后继者（直到找到一个进程）每次发送者都将自己的进程号加入到消息中，当消息回到始发者的手中，始发者接收到包括自己进程号的消息；转成协调者消息。该消息将再一次绕环运行，向所有的进程通知谁是协调者（在成员表中进程号码最大的那个）和新的环成员。4. 简述三种分布式互斥算法（集中式算法、分布式算法、令牌环算法）的算法思想。答：集中式算法选一个进程为协调者（比如在最大网络地址的进程）；无论什么时候进程要进入临界区，它将向协调者发送请求信息，说明它想进入那个临界区并希望获得允许；如果当前该临界区内没有其它任何进程，协调者就发送允许进入信息，当应答到达时，请求者就可以进入临界区；分布式算法：当某进程想进入临界区时，它要建立一个消息，包括：a 它要进入的临界区的名字；b 它要进入的处理机号；c 当前时间；将消息发送给所有其它进程；发送的消息假设是可靠的，即每条消息都应该被确认；当一个进程接收另一个进程请求消息时，它取决于接收方的状态以及临界区的命名。有三种情况要加以区别：(1) 接收者不在临界区中，也不想进入临界区，它就向发送者发送OK消息(2) 接收者已在临界区中，它就不必回答，而是负责对请求队列排队(3) 接收者要进入临界区，消息时间戳对比，取小的那个a 如果来的消息的时间戳小，接收者发送OK消息b 如果接收者本身时间戳更小，接收者负责排列请求队列而不发送任何消息令牌环算法：构造一个逻辑环，设置一个令牌，令牌在环上依次传递。获得令牌后才可以决定是否进入临界区，如果离开了临界区或不打算进入临界区，则将令牌下传。不允许使用同一令牌进入第二个临界区5. 简述处理机分配算法中图论算法的工作步骤。答：图论算法的思想：整个系统可以表示为一张带权图，每个节点表示一个进程；子图内每条边表示两个进程之间的通信量；从一个子图连向另一个子图的边表示网络通信；P1W（X）1 W（X）3P2R（X）1 W（X）2P3P4R（X）1 R（X）3 R（X）2 R（X）1 R（X）2 R（X）3 6. 试分别解释严格一致性、顺序一致性、因果一致性、PRAM一致性等几种以数据为中心的一致性模型的含义。下图中的事件序列对上述哪几种一致性模型是有效的？解答：严格一致性模型：所有共享访问事件都有绝对时间顺序；顺序一致性模型：所有进程都以相同的顺序检测到所有的共享访问事件；因果一致性模型：所有进程都以相同的顺序检测到所有因果联系的事件；PRAM一致性模型：所有的进程按照预定的顺序检测到来自一个处理器的写操作，来自其他处理器的写操作不必以相同的顺序出现；图中的事件序列对因果一致性、PRAM一致性是有效的。7. 一致性协议中，复制的写协议有哪几种？请简单解释。答：复制的写协议：写操作可以在多个副本上执行。包括两种类型：主动复制和基于法定数量的协议。主动复制：每个副本有一个关联的进程，该进程执行更新操作。操作被发送到每个副本。基于法定数量的协议，其基本思想是：在读或写一个复制的数据项之前要求申请并获得多个服务器的允许。8. 在RPC中，如果客户机在发送请求后在服务器应答消息到来之前崩溃了，将会发生什么问题？如何解决？解答：发生现象：客户机在发送请求后在服务器应答消息到来之前崩溃，其已经激活了服务器的相应计算，而客户没有等待它的结果，将遗留“计算孤儿”。清除“孤儿”方法：a) 根绝（extermination）法：客户存根发送RPC前在日志文件中记录将要执行的RPC，若客户重启则依据日志作准确清除远程计算。b) 再生（reincarnation） 法：划分时间为序号纪元（时间戳）， 客户重起则广播新纪元开始，所有远程计算被终止。c) 温和再生（gentle reincarnation）法：改进“再生”法，由服务器检查远程计算有无调用者，若无则远程计算被终止。d) 过期（expinration） 法：每个rpc执行前给定时间段T，rpc到期未完成的必须再申请新的T 。服务器将清除没有再申请新的T的rpc。9. 分布式系统中，文件共享的语义有哪几种？阐述各自的工作原理。答：分布式系统中，文件共享的语义有Unix语义、对话语义、不可更改文件语义、事务处理语义等几种。Unix语义：当READ操作紧跟在WRITE操作后执行时，READ操作返回刚写入的值。当READ操作跟在两个紧连的WRITE操作后时，读出的值就是后一个写入的值。强调绝对时间顺序对话语义：对一个打开文件的修改仅对修改该文件的进程（机器）是可见的；仅当文件关闭时，其修改才对其他进程（或机器）可见。不可更改文件语义：只有创建和读文件操作。事务处理语义：存取文件时，进程执行开始事务处理，以指示跟在其后的操作是不可分的；通过系统调