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

资料内容仅供您学习参考如有不当或者侵权请联系改正或者删除。

一、 名词解释

1. 中间件:指一个软件层,放在应用程序和网络操作系统之间, 它提供了一个编程抽象以及对底层网络、 硬件、 操作系统和编程语言异构性的屏蔽。

2. RPC : RPC是remote procedure call (远程过程调用)的简称。 RPC思想是使远程的过程调用就像在本地的过程一样,调用者不应该意识到此调用的过程是在其它机器上实行的。

3. 名称解析:在名称空间中,根据节点的路径名,就能够寻找到这个节点所存储的任何信息,这个查找的过程就称为名称解析。

4. 严格一致性模型:所有共享访问事件都有绝对时间顺序。

5. 容错( fault tolerance ) :避免系统失效。 在故障发生时系统仍能正常运行(提供服务) 。

二、 综合题

1.什么是分布式系统?分布式系统发展的前提条件有哪些?试列举2个分布式系统的例子?比较分布式操作系统、 网络操作系统、 多处理机分时操作系统的特点和应用范围。

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

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

 软件方面:用户感觉在独占系统

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

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

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

资料内容仅供您学习参考如有不当或者侵权请联系改正或者删除。

 计算量增大

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

例:

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

 银行 ”一卡通”系统、 电信 ”神州行”系统、 飞机订票系统等

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 如果接收者本身时间戳更小,接收者负责排列请求队列而不发送任何消息

令牌环算法:

资料内容仅供您学习参考如有不当或者侵权请联系改正或者删除。

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

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

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

6.试分别解释严格一致性、 顺序一致性、 因果一致性、 PRAM一致性等几种以数据为中心的一P1 W ( X ) 1 W ( X ) 3

P2 R ( X ) 1 W ( X ) 2

P3 R ( X ) 1 R ( X ) 3 R

P4 R ( X ) 1 R ( X ) 2 R

致性模型的含义。 下图中的事件序列对上述哪几种一致性模型是有效的?

解答:

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

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

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

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操作后时,读出的值就是后一个写入的值。 强调绝对时间顺序对话语义:对一个打开文件的修改仅对修改该文件的进程(机器)是可见的;仅当文件关闭时,其修改才对其它进程(或机器)可见。

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

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

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

11.某多计算机系统中的256个CPU组成了一个16X16的网格方阵。 在最坏的情况下,消息的延迟时间有多长(以跳(hop)的形式给出,跳是结点之间的逻辑距离)?

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

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

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

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

答:文件更新有主拷贝复制和表决( Voting )算法两种主要算法。

主拷贝复制算法:

资料内容仅供您学习参考如有不当或者侵权请联系改正或者删除。

 指定一个服务器为主服务器,其它服务器为从服务器;

 当要更新一个复制文件,将该更新文件送至主服务器;

 在主服务器处完成修改,然后向各从服务器发命令,完成修改;

 容错方法:将日志写在稳定存储器。

表决( Voting )算法:

基本思想:在读或写一个复制文件之前要求申请并获得多个服务器的允许, 并将新的版本号与

文件联系起来, 用以识别文件版本;

读法定数( read quorum ) Nr:读文件操作前必须达到的服务器数;

写法定数( write quorum ) Nw:更新文件前必须达到的服务器数;

Nr与Nw遵循的规则: NwN/2 (服务器总数的一半) , NrNwN 。

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

答:相对于集中式系统,分布式系统的优点: 1 )从经济上,微处理机提供了比大型主机更好的性能价格比; 2 )从速度上,分布式系统总的计算能力比单个大型主机更强; 3 )从分布上,具有固定的分布性, 一些应用涉及到空间上分散的机器; 4)从可靠性上,具有极强的可靠性,如果一个极强崩溃,整个系统还能够继续运行; 5 )从前景上,分布式操作系统的计算能力能够逐渐有所增加。

分布式系统的缺点: 1 )软件问题, 当前分布式操作系统开发的软件太少; 2 )通信网络问题,一旦一个系统依赖网络,那么网络的信息丢失或饱和将会抵消我们经过建立分布式系统所获得的大部分优势; 3 )安全问题,数据的易于共享也容易造成对保密数据的访问。

资料内容仅供您学习参考如有不当或者侵权请联系改正或者删除。

推动分布式系统发展的主要动力:尽管分布式系统存在一些潜在的不足, 可是从长远的角度看,推动分布式系统发展的主要动力是大量个人计算机的存在和人们共同工作于信息共享的需要, 这种信息共享必须是以一种方便的形式进行。而不受地理或人员,数据以及机器的物理分布的影响

16.多处理机系统和多计算机系统有什么不同?

答:共享存储器的计算机系统叫多处理机系统,不共享存储器的计算机系统为多计算机系统。它们之间的本质区别是在多处理机系统中,所有CPU共享统一的虚拟地址空间,在多计算机系统中,每个计算机有它自己的存储器。

多处理机系统分为基于总线的和基于交换的。 基于总线的多处理机系统包含多个连接到一条公共总线的CPU以及一个存储器模块。基于交换的多处理机系统是把存储器划分为若干个模块,经过纵横式交换器将这些存储器模块连接到CPU上。

多计算机系统分为基于总线的和基于交换的系统。在基于总线的多计算机系统中,每个CPU都与她自身的存储器直接相连,处理器经过快速以太网这样的共享多重访问网络彼此相连。在基于交换的多计算机系统中,处理器之间消息经过互联网进行路由, 而不是想基于总线的系统中那样经过广播来发送。

17.在分布式操作系统中, 为什么采用微内核技术, 一般微内核提供哪些服务?

答:采用微内核技术的原因: 1 )高度模块化,每一个服务都有一个定义好的接口, 每个用户都能够访问任何服务,服务与位置独立; 2)高度灵活性,具有添加、删除和修改服务的功能;

3 )用户定制, 用户能够自定义服务。

微内核提供的服务有: 1 )进程间通信机制; 2 )某些内存管理功能; 3 )少量的底层进程管理和调度; 4 )低层输入/输出服务