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

实用文档

一、名词解释

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一致性等几种以数据为中心的一致性模型的含义。下图中的事件序列对上述哪几种一致性模型是有效的？

P4 R（X）1 R（X）2 R（X）3

解答：

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

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

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

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）低层输入/输出服务

18.解释透明性的含义，并举例说明不同类型的透明性。

答：对于分布式系统而言，透明性是指它呈现给用户或应用程序时，就好像是一个单独是计算机系统。具体说来，就是隐藏了多个计算机的处理过程，资源的物理分布。

19.应用哪些技术可以使得一个分布式系统具有可伸缩性？

答：实现分布式可伸缩性，基本的三种技术为：

1、减少通信延迟，即使用异步通信方式，使得发送方发送请求后不必阻塞以等待答复，而是处理其他本地任

务。

2、分层，即将一个组件分解为几个小层。一个好的例子是DNS域名系统，它将域名分为三层，均衡了系统负

载。

3、复制冗余，它能使得资源更容易就近获取，并且它能使资源分布于整个系统，均衡了负载。

20.举例说明三层客户/服务器体系结构。

答：此三层分为：用户接口层（接收用户请求），处理层（核心逻辑处理），数据层（返回用户所需数据）。

以一个Internet搜索引擎为例，用户使用键盘，鼠标输入想要检索的信息，经过用户接口层传递给处理层，生成查询语句，然后到达数据层（即数据库）查询数据，再将查询结果返回给处理层，让它对结果进行排序，生成HTML页面，最后返回给用户接口层（即浏览器）显示给用户。

21.给出一个多线程客户端的例子，并给出一种构造多线程服务器的方法。

实用文档

答：多线程客户端例子，以网页浏览器为例：

浏览器在从服务器获取HTML文件时，同时也在显示它。因为一个HTML文件可能包含文本，图像，音频，视频等文件，故当一个线程获得其中一个文件并显示它时，同时还有其它线程正从服务器读取其它文件。即一个浏览器拥有多个线程与服务器进行交互。

构建多线程服务器：

使用有限状态机模型，它使用非阻塞系统调用方法，可实现并行处理多个请求。对每一个接收或发送的消息都将其处理状态存储到一个表中，由多线程对其进行处理。

22.什么是有状态服务器和无状态服务器，给出相应的例子，并说明有状态服务器存在的问题。

答：无状态服务器，在请求之间，服务器不保存具体客户的信息，以及与客户端交互活动的有关信息。它要求每个请求必须是独立的，必须包含全文件名和文件中的偏移量，因此消息长度较长。

有状态服务器，在请求之间，服务器保存客户信息以及与客户交互活动的有关信息，

23.说明在移动IP 系统中，如何定位一个实体。

a)名称与地址的直接映射

b)使用标识符的两极映射

24.客户-服务器模式的主要思想及优点。

答：其主要思想是构造一种操作系统，它由一组协同进程组成，这组进程称为服务进程，为客户机提供服务的进程称为客户。客户和服务器都运行在相同的微内核中，都以进程方式运行。一台机器可以运行多个客户、多个服务器或者两者的结合，客户-服务器模式常常以简单的请求/应答协议为基础，客户向服务器发送一个请求，请求一些服务，服务器完成后返回所要的数据或者给出一个错误代码，指出工作未完成。

优点：1）简单，客户发出一个请求得到一个应答，在使用之前无需建立连接也不需要释放连接；2）有效性，协议栈比较短因而更有效。

25.客户为了发送消息给服务器，它必须知道服务器的地址。试给出服务器进程编址的几种方法，并说明如何定位进程。

答：方法一。机器号加进程号，内核使用机器号将消息正确地发送到适当的机器上，用进程号决定将消息发送给哪一个进程。

方法二。进程选择随机地址，通过广播方式定位进程，进程在大范围的地址空间中随机指定自己的标识号。在支持广播式的LAN中，发送者广播一个特殊的定位包，其中包含目的进程地址，所有的内核查看地址是不是他们的，如果是则返回消息给出网络地址，然后发送内核缓存地址。

方法三。客户机运行时，使用ASCII码访问服务。客户机运行时，向名字服务器发送请求信息，名字服务器将ASCII服务器名映射成服务器地址，客户机收到给地址后，可以访问服务器。

26.对于接收消息Receive原语，为什么需要缓存, 缓存的作用是什么?

答：如果不适用缓存，服务器接收来的消息会被丢弃或者存在诸如服务器需要存储和管理早到来的消息这样的问题。缓存的作用就是用来统一管理消息的：它定义了一种叫邮箱的数据结构，接收客户端请求的进程通知内核创建邮箱存储消息，并且指定了访问地址。当Receive原语调用是，系统内核就会提取消息并知道如何处理它。

实用文档

27.说明在C/S模式下解决消息可靠传输的三种方法?

答：1、重新定义非可靠的send语义。系统无法保证消息发送成功，完成可靠地通信依赖于用户。

2、要求接收机器的内核给发送机器的内核发送一个确认消息。只有收到这个确认消息后发送内核释放用户进

程。确认消息从一个内核传送到另一个内核，无论是客户还是服务器都看不到确认消息。

3、客户在发送消息后阻塞，服务器内核不发送确认消息而是将应答作为确认消息。因此客户进程一直阻塞到

应答消息到来为止，如果时间太长，发送内核会重新发送请求以防止消息丢失。

28.在RPC调用时，如果服务器或客户机崩溃了，各有哪些解决方法。

答：如果是服务器崩溃了，用户无法区分服务器是在执行前还是执行后崩溃，解决方案如下：1）至少一次语义，指等待服务器重新启动，然后重发请求。这种方法要求不断重试直至客户收到应答消息。它保证RPC至少执行一次。2）之多一次语义，指立即放弃并报告失效。它确保RPC至多执行一次，但也可能根本没有执行；3）不作保证；4）精确一次语义；

如果是客户机崩溃了，存在孤儿问题（客户已发送请求，在应答到来之前崩溃了，此时已经激活服务器中的过程并获得结果，但是没有客户在等待结果）解决方案如下：1）根除，在客户存根发送RPC消息前先做日志（用来恢复崩溃），系统重新启动后，检查日志，发现孤儿存在并将其杀死；2）再生，把时间分成有序的纪元，当客户端重启时，向所有机器广播一个消息通知一个新纪元的到来，并结束所有的远程计算；3）温和再生，服务器接收到新纪元广播时，检查自己是否有远程计算，只有那些找不到所有者的远程计算终止。4）过期，每个RPC都分配一个标准时间T来完成任务，如果超时没有完成则显示分配一个数额。

29.一个影响RPC执行时间的问题是消息的拷贝问题，试说明在那些环节需要拷贝，并说明减少拷贝次数的方法。

答：需要消息拷贝的环节：在发送端，消息从客户存根拷贝到客户内核缓冲区，再从客户内核缓冲区拷到客户接口芯片缓冲区（网卡），然后消息被拷贝到接收端的服务器接口芯片缓冲区，之后拷贝到服务器内核缓冲区，最后到达服务器存根（共5次）拷贝。此外，有时还需要拷贝参数数组。

减少拷贝次数的方法：分散-集中方法（汇集发），具有分散-集中能力的网络芯片可以减少拷贝次数，他通过拼接2个或者多个内存缓冲区来组装报文。在发送端，由客户内核缓冲区生成报文消息头。由客户存根生成报文消息体，当发送时，由网络芯片组装报文。同样地，接收端将接收来的报文分解成消息体和消息头，并放入相应的缓冲区。

30.在组通信中，给出组编址的的三种方式。

答：1、每组分配地址，有三种方式：单播，多播，广播，发送进程将消息发送给组地址，消息将会发布给所有成员2、要求发送端提供一份目的地址的显示列表；3、判定编址，消息将被发送给所有成员，每条消息包含了判定条件，如果判定条件评估为TRUE，则消息被接受，否则消息丢弃。

31.用组通信方式时，举例说明消息顺序的重要性，并说明解决方法说明。

答：要使组通信易于理解和使用，有两种性质是不可缺少的，首先是原子广播原语，它确保了一条消息要么被所有组内成员收到，要么没有一个成员能收到。其次是消息的顺序。例如：有四台机器每台机器有一个进程，进程1、2、3、4属于同一个进程组，进程0与进程4同时想给该组发送一条消息，当两个进程竞相访问LAN 时，在网络中消息传送的顺序是无法确定的，可能是0->1, 4->0,4->1,4->3,0->3,0->4。这样进程1先收到0再收到4，进程3先收到进程4在收到0，则1与3之间可能会出现不一致。

解决方法：1）全局时间顺序，保证立即发送所有消息并让他们保持发送顺序，该方法能将消息精确的按照发送顺序传递到目的地。2）一致时间顺序，若有两条消息A和B，以很少的时间间隔发送，系统先取其中一个作为第一个发送给所有组内成员，然后再取下一个发送给组内成员，这种方法保证组内成员按照统一的顺序收到了消息，但是这个顺序可能并不是发送消息的顺序。

32.实现分布式系统同步的复杂性表现在哪几个方面？说明先发生关系，并说明在LAMPORT算法中怎样给事件分配时间。

答：分布式算法有如下性质：1）相关信息分散在多台机器上；2）进程决策仅依赖于本地信息；3）系统中单点故障应避免；4）没有公用时钟和其他精确的全局时间资源存在。前三点说明在一处收集所有信息并对他们

实用文档

进程处理是不可接受的，左后一点说明在分布式系统获得时间上的一致并不是容易的。

LAMPORT 算法的解决方案是直接使用先发生关系，每条消息都携带发送者的时钟以指出其发送的时间，当消息到达时，接受者的时钟比消息发送者时钟小，就立即将自己的时钟调到比发送者的时间大1或更多的值，我们给出一种测量时间的方法，使得对每一事件a ，在所有进程中都认可给它一个时间值C(a)，在给事件分配时间时要遵循一下规则：1）在同一进程中a 发生在b 之前则C(a)

33.有三个进程分别运行在不同的机器上，每个机器都有自己的时钟并以不同且不变的速率工作（进程1的时钟嘀嗒了6下时，进程2的时钟嘀嗒了8下，而进程3的时钟嘀嗒了10下）。举例说明进程之间消息传递中违反先发生关系的情况，并说明如何用Lamport 方法解决。

答：如右图所示：三个进程进程2给进程1发送消息C 和进

程1给进程0发送消息D 违反了先发生关系，消息到达的时间小于消息发送的时间。 Lamport 解决方案直接使用先发生关系，每条消息携带发送者的时钟以指出其发送的时刻，当消息到达时，接受者时钟若比发送者时钟小，就立即将自己的时钟调到比发送者大1或者更多的值（这里使用值 “1”）。 进程1在收到消息 C 后将56调整为61，发送消息D 的时钟将是69,；进程0在收到消息D 后将54调整为70 34.说明RICART 和AGRAWALE 分布式互斥算法；假定A 和B 是相互独立的两个临界区，进程0要进入A ，进程1要进入B ，R-A 分布式互斥算法会导致死锁吗？说明理由。 答：RICART 和AGRAWALE 算法要求系统中所有事件都是全序

的，也就是说，对任何事件组消息，哪个先发必须无歧义，算法如下：当一个进程想进入临界区时，他要建立一个包括

他要进入的临界区的名字、处理机号、当前时间的消息，然

后将消息发送给所有其他进程，也包括发送给自身，当一个进程接收另一个进程消息时，它取决于接受方的状态以及临界区的名字有三种情况：1）接受者不在临界区，也不想进入临界区，他就向发送者发送OK 消息；2）接受者已经在临界区，它不必回答，而是负责对请求队列排队；3）接收者要进入临界区，但是还没有进入，它要负责将发来的消息和它发送给其他进程的时间戳对比，取小的那个。如果来的消息时间戳小，接收者发送OK 消息，否则接收者负责排列请求队列而不发送任何消息。

在发送完允许进入临界区的请求后，进程将不再做任何事，仅等待所有的允许消息，一旦得到允许，它就进入临界区。它从临界区退出时，向队列中所有进程发送OK 消息，并将它从队列中删除。

该算法可能导致死锁，例如：A 和B 是相互独立的两个临界区，进程0要进入A ，进程1要进入B ，而此时进程0在B 中，进程1在A 中就会进入死锁。

35.举例说明用私有工作空间实现事务处理时的基本思想。

答：在进程开始一个事务时给它分配一个包含了所有需要访问的文件的私有工作空间，在事务提交或终止前，所有的读写操作都在私有空间而不是真正的文件系统中进行，存在的问题是所有内容都拷贝到私有空间，代价难以承受。

优化方法是：1）私有空间中只包含一个指向父辈工作区的指针，当事务处于最顶层时，它的工作区是真正的文件系统。2）使用索引节点，索引是一个与判断文件所在的磁盘块位置有关的数据库，给方法不将全部文件考入私有空间，而只是拷贝索引。

36.说明在分布式系统中实现原子性提交的两阶段提交协议的基本思想及其优点。

答：两阶段提交协议的基本思想是有一个进程作为协调者，通常是执行事务的进程。

实用文档

在准备提交阶段，协调者向日志中写入Prepare ，然后向所有服务器发送准备提交消息，服务器接收到消息后，检查自己是否准备提交，如果是就向日志中写入Ready ，然后向协调者发送准备好消息。

在提交阶段，协调者接收所有响应后决定提交还是撤销，如果所有服务器都准备提交，则提交事务；否则撤销事务。无论如何协调者都会写入日志，并发送决定消息，服务器接到消息后也将结果写入日志，并发送结束消息，完成整个过程

37.举例说明为什么使用集中式的死锁检测算法会产生假死锁，并给出一种解决办法。

答：集中式的死锁检测算法每台机器的资源图中只包含它自己的进程和资源，协调者节点保存整个系统（所有资源图的集合）的资源图。当机器资源图发生变化时相应的消息发送给协调者以提供更新，当协调者检测到环路时，它终止一个进程以解决死锁。

如上图圆表示进程，方框表示资源，开始时如同a ，b ，c 所示，过来一段时间，B 释放R 并请求T ，这是一个合法的操作，机器0向协调者发送一条消息申明它释放资源R ，机器1向协调者发送一条消息声明进程B 正在等待它的资源T ，不幸的是机器1的消息先到达协调者，导致生成资源图如图d 所示。协调者得出错误的结论——死锁存在，这种情况称为假死锁。

解决办法是：使用Lamport 算法以提供全局统一的时间，对协调者收到的消息按照时间戳排序

38.举例说明分布式死锁检测方法Chandy-Misra-Has 算法的思想以及如何解除死锁。

答：算法允许进程一次请求多个资源，例如下图所示的资源图。图中只给出进程，每条弧穿过一个资源，当某个进程等待资源时，生成一个探测消息（阻塞的进程，发送消息的进程，接收消息的进程）发送给占用资源的进程。消息到达后，如果接受者也在等待其他进程占用的资源，则跟新探测消息，第一个字段保持不变，第二个字段改为当前的进程号，第三个字段改为等待的进程号，跟新后的探测消息发送给等待的占有资源的进程。如果存在多个进程则要发送多个不同的消息。如果消息又回到最初的发送者说明存在一个又死锁的环路系统 解除死锁的方法：1）令最初发送探测消息的进程自杀。如果多个进程同时阻塞同时发送探测消息，那么每个进程都会发现死锁并因此自杀。2）将每个进程的标识符添加到探测消息的末尾，将编号最大的进程中止或者发送消息请求的进程自杀。多个进程发现同一环路会选择同一个牺牲者。

实用文档

39.说明wait-die和wound-wait分布式死锁预防方法。事务时间戳为50的进程申请事务时间戳为100的进程占用的资源。按以上两种策略，结果会如何?

答：（时间戳越小的进程越是年老）wait-die死锁预防算法：当较老的进程请求年轻进程所占有的资源时，老进程只能等待；如果年轻进程请求老进程占有的资源时，年轻进程会被终止。

Wound-wait死锁预防算法：当老进程请求年轻进程所拥有的资源时，老进程抢占年轻进程的资源，年轻进程被终止；当年轻进程请求老进程所拥有的资源时，年轻进程等待。

40.说明发送者发起的分布式启发算法和接收者发起的分布式启发算法及各自的主要缺点。

答：发送者发起的分布式启发算法：当创建进程时，创建进程的机器将对一个随机选取的机器发生询问，询问它的负载是否低于某个阈值，如果是，将发送进程否则将选择另一台机子发送询问。如果在N次询问内还没有找到合适的机器，算法停止新进程将在创建它的机器上运行。该算法的缺点是：在负载十分严重的情况下，所有机器都会不停的毫无意义的向其他机器发送询问，想找到一台愿意接受更多工作的机器，在这种情况下，几乎没有进程会被减轻负载，但却会引起相当可观的额外开销。

接收者发起的分布式启发算法：当一个进程结束时，系统将检查自己是否有足够的工作可做，如果没有，将随机向一台机器申请工作，如果那台机器没有要给予的工作，系统将继续询问第二，第三台机器，如果询问N台机器都没有申请到工作，系统将暂停申请开始处理系统队列中一个等待进程，当这个进程结束后，开始下一轮的申请；如果系统无事可做，则将进入空闲状态，一定时间后从新开始申请。给算法的缺点是：系统在无事可做时会造成相当大的询问负载。

41.说明主机后备容错方法的主要思想，在主机崩溃后存在的问题及解决方法。

答：主机后备容错方法的主要思想是在任何时候，服务器都由主机完成所有工作，如果主机失效，则由后备机接管工作。

在RPC过程中，主机崩溃后产生的情况如下：1）主机在执行任务前崩溃，则没有损失，客户端会超时重发直到连上后备机，任务至执行一次；2）主机在执行任务后，向后备机发送跟新消息前崩溃，此时后备机接管，消息再次到来，任务被执行2次；3）主机在后备机执行任务后自己发送相应消息前崩溃，则任务被执行3次，一次由主机完成，一次由后备机完成，一次由后备机接管时完成。如果请求消息带有序号，则可以减少任务执行次数。

42.多处理机系统中，fail-silent类型和Byzantine类型处理机错误各需要至少多少个处理机才能满足要求？说明理由。

答：fail-silent类型处理机错误是指失效的处理机只是停止运行，对接下来的输入不做反应也不产生进一步的输出，即宣布它不在工作了。对于这样的错误，需要K+1个这样的处理机以满足K容错要求，因为若K个处理机停止工作，那么剩下的那个处理机继续工作。

Byzantine类型的错误是指出错的处理机继续运行，产生问题的错误答案，并可能和其他出错的处理机一起“恶意”地工作。对于这类错误，那么至少需要2K+1个处理机才能满足K容错要求，因为出错的处理机仍然运行并发出错误或随机应答，最坏情况下，K个失效处理器偶然产生同样的应答，剩下K+1个未出错的处理机也将产生相同应答，因此客户或者表决器只要相信大多数应答就可得到正确的结果。

43.举例说明Lamport等人提出的算法是如何解决Byzantine将军问题的。

答：Lamport等人设计了一种递归算法可在特定条件下解决这一问题。例如：N = 4（有四个将军），M = 1（其中有一个叛徒），对这样的参数，参数运行四步。

第一步，每个将军发送可靠的消息给其他所有的将军，声明自己真实的军队人数，忠诚的将军声明的是真值，叛徒则可能对其他每个将军都撒一个不同的谎。如图a；

第二步，把第一步声明的结果组成向量形式，如图b；

第三步，每个将军把图b中各自的向量传递给其他每一个将军，这里叛徒再一次撒谎，使用了12个新值。A—J。如图c；

第四步，每个将军检查所有新接收向量的每一个元素，若某个值占多数则把该值放入结果向量中，

实用文档

44.在实时分布式系统中，动态调度和静态调度的含义是什么？比较动态调度和静态调度算法。

答：动态调度是指在程序运行期间进行调度决定下面运行哪一个进程。静态调度是指在系统开始运行前就已经进行，算法的输入包含了所有任务的列表及它们各自的运行时间。两者比较如下：

1）静态调度适合时间触发系统的设计，动态调度适合事件触发系统的设计；2）在资源利用方面动态调度比静态调度有更大潜力；3）若给定足够的处理能力，对静态系统一个最优或次优的调度可以事先获得，动态系统在运行期间无法承受复杂的调度计算花费。

45.说明使用主动复制方法的容错的主要思想，并给出以下TMR 系统可应付多少个故障元件（设备和表决器），举例说明可屏蔽掉的最坏的情况。

答：主动复制是使用物理冗余来提供容错的一种著名的技术，这种方法也适用于电子电路的容错。主动复制的一个主要问题是需要复制多少份才合适，这取决于要达到的容错量。

如果系统在k 个部件出错时仍能达到系统设计的要求而正常工作，那么这个系统称为是k 级容错的。如fail-slient 类型，有k+1个这样的部件可以满足k 级容错，若k 个处理机简单停止工作，那么可以使用剩下的那个处理机的结果；如byzantine 类型，至少需要2k+1个部件才可以满足k 级容错，最坏情况下k 个失效的处理机偶然（甚至有意）地产生相同的应答，然而剩下的k+1个未出错的处理机也将产生相同的应答，因此客户机可以根据大多数的应答得到正确结果。 如上图中的TMR 系统是每个设备复制三次，每级电路都设置三个表决器，每个表决器都有三个输出和一个输入，若两个或者三个输入相同，输出则等于输入，因此它可以处理6个失效的元件。Eg ：第一行的元件全部失效的情况。

实用文档

46.简述三模冗余的基本思想，并举例说明三模冗余能否处理Byzabtine故障。

答：三模冗余是使用物理冗余来提供容错的技术，是使用主动复制方法的容错。在电子电路中有设备A、B、C，然后每个设备复制三次，结果就是每级电路都设置了三个表决器，每个表决器有三个输入和一个输出，若两个或者三个输入相同，输出则等于输入，若三个输入各不相同，输出就是不定值，这种设计就是TMR。

若处理机是Byzabtine类型的，出错的处理机仍然工作并发出错误的随机的应答，那么至少需要2k+1个处理机才能达到k级容错。最坏情况下k个失效的处理机偶然（甚至有意）地产生相同的应答，然而剩下的k+1个未出错的处理机也将产生相同的应答，因此客户机可以根据大多数的应答得到正确结果。

三模冗余在每组中有一个部件出现Byzabtine故障时可以处理，而一组中有两个甚至三个同时出现Byzabtine 故障则不能处理。

47.举例说明采用图论确定性算法进行处理机分配的实现方法。

答：整个系统可以表示为一张带权图，每个节点表示一个进程，每条边表示两个进程之间的通信量。从数学角度看，整个问题就变成了如何根据特定的限制将图划分成k（k为系统中cpu数量）个不相连的子图（如每个子图的总cpu和内存需求在一定限制内）。对于每种满足限制的解决方案，子图内部的边意味着机器内部的通信，可以忽略。从一个子图连向另一个子图的边表示网络通信。该算法的目标就是在满足限制下，找到一种划分方式使网络通信量最小。下图表示了图的两种划分:

方案A:通信量=(3＋2＋4＋4)＋(2＋8＋5＋2)＝30

方案B:通信量=(3＋2＋4＋4)＋(3＋5＋5＋2)＝28

48.举例说明时间触发和事件触发的区别。

答：事件触发是指，当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的cpu得到一个中断请求。

时间触发是指，在每隔固定的时间t后产生一次时钟中断，对选定的传感器进行采样，并且驱动（特定的）执行机构。

举例，考虑一个100层楼的电梯控制器设计。假定电梯正在60层安静的等待顾客，有人在一层按下按钮。就在100毫秒后，另一人在100层按下按钮。在事件触发系统中，第一次按钮产生一个中断，将使电梯启动下行，就在他做出下行决定后，第二个按下按钮的事件到来，因此第二个事件被记录下来以作将来的参考，但电梯还是继续下行。

若考虑时间触发系统，没500毫秒采样一次。若两次按下按钮都在一次采样周期中出现，控制器就不得不进行决定，例如按最近用户优先原则，此时电梯将上行。

由以上例子可以看出，事件触发的设计在低负载时会更快响应，但在高负载时可能崩溃。时间触发相反，仅适用于相对静态的环境。

49.使用上载/下载模式的文件服务器系统与使用远程访问模式的文件系统之间有什么区别？

答：文件服务分为两种类型：上载/下载模式和远程访问模式。

上载/下载模式。只提供两种主要的操作（读文件和写文件），读操作将整个文件从文件服务器传输到请求客户端，写操作则刚好相反，文件系统运行在客户端。优点是系统概念简单，应用程序取得需要的文件，并在本地

实用文档

使用它。当程序结束时，将所有修改的文件或新创建的文件写回去，不需要管理复杂的文件服务接口，文件传输效率高。缺点是客户端需要足够的存储空间，当需要部分文件是需要传输整个文件。

远程访问模式。提供了大量的操作，如打开、关闭文件，读写部分文件等等。文件系统在服务器端运行。优点是客户不需要大量存储空间，当需要部分文件是不需要传输整个文件。

50.分布式系统中处理共享文件的四种方法（文件共享的四种语义）。

答：1）UNIX 语义。系统使所有的操作都有一个绝对时间顺序，READ 操作读取最近一个WRITE 操作后的内容，要求对一个文件系统的任何操作对所有进程都是及时可见的。

2）会话语义。对于打开文件的修改最初只对修改文件的进程是可见的，当文件关闭后，对文件的修改对其他进程才是可见的。

3）不可修改语义。不允许打开文件进行写操作，只提供CREATE 和READ 两种操作。只能进程讲的的共享和复制。

4） 事务语义。使用原子事务，即所有的操作要么全做，要么全不做。

51.说明保持客户高速缓存一致性的四种算法。

答：1）直接写，当缓存中的文件被更新后，新的值在缓存在保存，而且同时发送到服务器，而当另外的进程访问文件时，读到的是最新值，但是存在一个问题，其他进程在更新之前读到的文件内容可能是过期的，那么在每次用到文件时需要从服务器中读取文件版本进行比较，查看是否过期，但是每次都要在服务器和客户端之间通信，这样就体现不出缓存的作用了。

2）延迟写，操作不立即发送给服务器，而是延迟一段时间，也就减少了网络消息，当进程读取文件时，依赖于时间。具体读到的是那次操作的结果不确定，语义模糊。

3）关闭写，操作只有在文件关闭后才写回服务器，配合session 语义。

4）集中控制，就是在文件服务器上保存了进程对文件的操作方式等信息，类似于锁机制的管理，避免写操作的文件被其他进程操作，但是当修改的操作结束时，会将操作结束消息通知服务器，操作的结果也就立即会送到服务器

52.说明分布式系统提供文件复制服务的原因以及实现复制的三种方法。

答：分布式系统通常保持文件的多个拷贝，每个拷贝放在一台单独的文件服务器上，提供这种服务主要有一些几种原因：1）数据不丢失，通过对每个文件的独立备份来增加系统的可靠性；2）当一个文件服务器出现问题时，仍然允许进行文件访问；3）负载均衡，将工作量分配到多个服务器上。

三种复制方法一次如上图所示：

1）显示复制，如图a 所示，是为编程人员控制整个进程所用，当进程产生一个文件时，可以在其他服务器上生产另外的拷贝，如果目录服务允许一个文件有多个拷贝，所有拷贝的网络地址都可以和这个文件名联系起来。

实用文档

2）懒惰拷贝，如图b所示，只要在某个服务器上建立每个文件的一个拷贝服务器自己在其他的服务器上也可以自动生成副本。

3）用组复制文件，如图c所示，所有的写系统调用同时传送到所有的服务器，于是，其他的拷贝在源文件产生时就产生了。

53.说明更新复制文件的两种主要算法：主拷贝算法、Gifford算法。

答：主拷贝算法，使用时，指定一个服务器为主服务器，其他所有服务器为从服务器，当要更新一个复制文件时，我们就将该改变发送至主服务器上，在本地完成修改，然后向各从服务器发出命令，命令他们也完成修改。

这样可以在任何一个（主或者从）服务器上进行读操作。这种方法简单，但是有个问题，当主服务器停机时，所有的更细将不能进行。

Gifford算法，基本思想是在读写一个复制文件之前要求先申请并获得多个服务器的允许。例如，读一个已经有N个副本的复制文件，客户需要获得一个读法定数，它是任何Nr个或更多个服务器的任一集合，同样的，修改一个文件需要一个至少Nw个服务器的写法定数。Nr和Nw的值必修满足约束条件Nr+Nw>N，只有在适当数目的服务器同意参与时，文件才能进行读写操作。

54.说明基于总线的多处理机系统中的write-through和write once协议。

答：通写缓存一致性协议是一种特别简单的，通用的协议。当CPU从存储器中首次读取某个字时，该字通过总线取出并存储在提出请求的CPU缓存中，当再次需要这个字时，CPU不再提出访问存储器的请求，而是直接从缓存中获取，这样减少了总线流量，通写缓存一致性协议概括如下：

（通过监听）其他CPU的读写操作如何反应。例如，当监听者发现其他CPU写入的字在其缓存中（从监听者角度看是命中）时，监听者必须采取措施，即从本缓存中删除这个字。通写协议易于理解和使用。缺点是所有的读写操作必须通过纵向，因此允许挂在单一总线上的CPU数量仍然很少，不能满足大型多处理机的需求。

write-once协议：该协议管理缓存块，每个块处于一下三种状态之一：1）无效，本缓存块没有有效数据；2）干净，存储器被更新，该块可能在别的缓存中；3）脏，存储器错误，该数据块不在其他缓存中。

基本思想是允许正被多个CPU读取的字出现在它们所有的缓存中，而仅被一个CPU经常写的字只保存在他的缓存中，为减少总线流量，不必每次都写回存储器。

55.说明顺序一致性应满足的要求；在如下并行执行的进程P1和P2，列出顺序一致性所允许的6种语句交叉执行情况。

a=1; b=1;

if (b= =0) kill (P2) if(a= =0) kill (P1)

(a) P1 (b) P2

答：顺序一致性模型由下述条件定义：1）如果所有进程以一定顺序执行操作，每一进程的操作都以程序规定的顺序出现，则任何操作的结果都是一样的；2）要求分布式系统中的所有成员和它们的进程共享一个通用视图，此视图记录了对于共享能存访问操作的顺序。顺序一致性所允许的6种语句交叉执行情况：

实用文档

56.系统的同一页上。然而，它们都不是共享变量。是否会发生错误共享？说明理由。

答：错误共享是指无关的变量出现在同一页上，当一进程使用它们之一时，进程也得到了其他变量。有效页越大，发生错误共享的可能性越大。假设有一页包含了两个无关的共享变量A 和B ，如下图所示，进程1经常对A 执行读写操作，进程2经常使用B ，这时包含两个变量的页将经常在两个进程之间传送。

“错误共享”问题是由于有效页太大产生的，有效页越大，发生错误共享的可能性越大，共享页越小，发生错误共享的可能性越小。

图中所示的情况会发生错误共享，因为两个变量A 和B 恰好位于基于分页的DSM 系统的同一页上，即使不是共享变量，由于他们出现在同一页上，当一进程使用它们之一时，进程也得到了另一个变量，因此发生错误共享。

57.说明基于分页的分布式共享存储器置无效协议中如何读写存储器的一页。

答：在这个协议中，任意时间每一页或者在R 状态（可读），或者在W 状态（可读可写），在执行程序时，页的状态可以改变，当页处于W 状态时，只有一个拷贝，当页处于R 状态时，拥有者有一个拷贝，其他进程可能有其拷贝。每一页有一个拥有者，即最近在该页上写入的进程。

图（a ）给出了处理机1上的进程P 要读一页的六种情况。在前四种情况中，P 仅做读操作，页被映射到他们的地址空间，所以读操作由硬件完成，不会激活陷阱程序。第五六种情况，发生缺页错误，DSM 的软件获得控制权，发送消息给拥有者以获得一份拷贝。当拷贝传到时，页被映射，出错的指令继续执行，如果拥有者处于W 状态，必须将之降级为R 状态。

图（b ）给出了处理机1上的进程P 要写一页的六种情况，第一种情况，因为页映射为只读模式吗，所以写操作只是发生了，而不激活陷阱程序；第二种情况，也被改为W 状态，并写入；第三种情况，该页有其他拷贝，所以在写以前，必须先置无效这些拷贝。在后三种情况中，当P 要执行写操作时，其他进程是拥有者，P 必须要求现在的拥有者将其置无效，将拥有权传给P ，除非P 已经有了一个拷贝，将该页的一个拷贝也传给P 。只有这样写操作才能开始。在这三例中，P 最后拥有该页的唯一拷贝，其状态为W 。在所有的六例中，在写操作执行以前，协议保证要写得进程的地址空间中只有页的一个拷贝存在，这样可以保证一致性。

实用文档

58.在基于分页的DSM系统中，复制页更新时需要通过置无效协议以实现一致性，试给出一种寻找复制页拷贝的方法。

答：广播的方式，要求拥有者对申请消息进行响应，从而确定所需拷贝页的拥有者。

使用拥有者定位协议，在系统中指定一个进程为页管理者，来跟踪哪个进程有哪些页，在具体实现时有四消息和三消息两种方法。

四消息方法，申请者向页管理者提交请求，页管理者返回消息指出拥有者是谁。申请者在向拥有者发送请求，拥有者返回所需的页的拷贝或者拥有权。同时也管理者根据新的信息将相应的进程中的页置为无效页。

三消息方法，申请者向页管理者提交申请后，页管理者将请求消息转发给响应的拥有者，由拥有者对申请者直接给出所需页的拷贝或者拥有权。消息传送完成后，页管理者对页的拥有者做出改变，同时设置无效页。

1．按照资源共享的观念定义的计算机网络具备哪几个主要特征？

实用文档

答：三个主要特征：1.建立的目的是实现计算机资源的共享，包括数据资源\软件资源和硬件资源。2.互连的计算机是分布在不同地理位置的多台独立的”自治计算机”。3.连网的计算机之间的通信必须遵循共同的网络协议。

2．为什么传输层通信服务常常不适于构建分布式应用程序？

答：因为它不适合用于支持多层客户-服务器交互过程所使用的同步请求-应答方式，在可靠传输中，造成许多开销都耗费在连接的管理上。

3．描述一下客户和服务器之间使用套接字的无连接通信是如何进行的？

答：首先服务器和客户端都要创建一个套接字，并遵循UDP协议，服务器将其所在的IP地址以及一个端口号绑定到套接字，完成绑定后，服务器就能接收来自客户端的UDP数据包了。同样，客户端在创建套接字后，能够向服务器发送UDP包进行通信，通信过程中，服务器和客户端之间是不用建立连接的。

4．简述TCP和UDP协议在通信中的区别

TCP是面向连接的可靠的协议，适用于传输大批量的文件，检查是否正常传输。而UDP是面向非连接的不可靠的协议，适用于传输一次性小批量的文件，不对传输数据报进行检查。

TCP需要先建立连接才能通话；而UDP不需要，实时性要高点。

TCP可以形象比喻为打电话的过程；UDP可以比喻为发短信的过程。

TCP不能发送广播和组播，只能单播；UDP可以广播和组播。

6．标识符是否可以包含它所引用实体的信息？

答：标识符可以包含它所引用实体的信息，但是，这些信息不允许修改，因为那意味着标识符被改变。

7．在深度为k的分层定位服务中，当移动实体改变它的位置时，最多需要更新多少条位置记录？

答：移动实体改变位置会产生删除操作和插入操作，删除操作至少需要更新k条位置记录。同样，插入操作也需要更新k条位置记录。最后，删除与插入更新移动实体位置的记录共需要2k+1条。

8．要使用Lamport时间戳实现全序多播，是不是每个消息都必须要被严格地确认？

答：不需要，任何类型的消息，只要它的时间戳大于所接收到的消息的时间戳，就可以被加入消息队列，使用Lamport时间戳实现全序多播。

9．许多分布式算法需要使用协调进程。讨论一下，这样的算法实际上可以在什么程度上被看作为分布式的？

答：在集中式算法中，一般会选择一个固定的进程作为协调者，其它的进程可以分布在不同的机器上运行。分布式算法中也同样可以引入协调进程，但是，这个进程并不是固定的，它是从作为算法一部分的进程中选择的。因此，使用协调进程并不会影响算法的分布性。

10．作业调度和进程调度有何区别？

答：作业调度与进程调度之间的差别主要是：作业调度是宏观调度，它所选择的作业只是具有获得处理机的资格，但尚未占有处理机，不能立即在其上实际运行；而进程调度是微观调度，动态地把处理机实际地分配给所选择的进程，使之真正活动起来。另外，进程调度相当频繁，而作业调度执行的次数一般很少。

11．请解释DNS如何进行复制，以及它实际运行很好的原因。

答：DNS进行复制的基本思想是：域名服务器可以缓存以前查找过的结果。由于DNS的名称到地址的映射很少更改，因此，这些结果可以缓存很长一段时间。

12．简述进程与程序的联系和区别

答：（1）联系：一个进程可以涉及到一个或几个程序的执行；一个程序可以对应一个或多个进程，即同一程序段可以在不同数据集合上运行，可构成不同的进程，例如打印输出程序段，例如同一高级语言编译程序与多个用户源程序。

（2）进程和程序的区别主要体现在：

1）进程是动态的，具有一定的生命周期，而程序是静态的；

2）进程可并发执行，而没有创建进程的程序是不能执行的；

3）进程是操作系统中申请和分配资源的基本单位，而没有创建进程的程序是不能申请资源的；

4）进程包括程序、数据和进程控制块；

实用文档

5）同一程序的多次执行对应多个进程

13．在下图中，一个顺序一致的存储器允许6种可能的语句交叉。请列举出这6种可能的情况。

(1) a=1; if ( b= =0 ); b=1; if ( a= =0 );

(2) a=1; b=1; if ( a= =0 ); if ( b= =0 );

(3) a=1; b=1; if ( b= =0 ); if ( a= =0 );

(4) b=1; if ( a= =0 ); a=1; if ( b= =0 );

(5) b=1; a=1; if ( b= =0 ); if ( a= =0 );

(6) b=1; a=1; if ( a= =0 ); if ( b= =0 );

14．一个文件被复制在10个服务器上，请列出表决算法允许的所有读团体和写团体。

答：下列可能性的读团体和写团体是合法的：

（1，10）、（2，9）、（3，8）、（4，7）、（5，6）、（6，5）、（7，4）、（8，3）、（9，2）、（10，1）。

15．原子多播的可扩展性重要到哪种程度上？

答：它取决于一组包含多个进程的状态。如果进程为故障容错进行了复制，拥有少量的副本可能就足够了，在这种情况下，可扩展性几乎不成问题。如果是由不同进程构成的组，可扩展性就可能成了一个问题。当为了性能而复制时，原子多播自身可能超出负荷的能力。

16．在两阶段提交协议中，为什么即使在参与者们选择一个新的协调者的情况下也不会完全消除阻塞？

答：因为选举结束后，新的协调者也同样可能会崩溃。在这种情况下，其余的参与者也不能做出最后决定，因为这需要由新当选的协调者发起选举。

17．假设Alice希望向Bob发送一条消息m。她没有使用Bob的公钥K+B加密m，而是生成了一个会话密钥K A,B，然后发送[K A,B(m), K+B(K A,B)]。为什么一般来讲，这种方法更好？（提示：考虑性能问题）。

答：会话密钥有一个短而固定的长度，而消息m可能是任意长度。因此，采用会话密钥和公钥结合加密短消息通常在性能方面优于只使用一个公钥加密的消息。

18．列举出为密钥管理使用集中式服务的一些优点和缺点。

答：一个显著的优点是简单。比如：若有N个客户在一个集中式的服务器上共享了1个密钥，我们就只需要维护N个密钥；如果是成对共享密钥，那我们就需要维护N(N-1)/2个。而且使用集中式服务器存储和维护都在一个站点上，使存储和维护都比较方便。潜在的缺点：首先是服务器有可能成为性能和可用性的瓶颈。其次，如果服务器机密被泄露，就必须建立新的密钥。

19．一个网络中，DNS服务器应该部署在什么地方最合适？

答：要用域名访问Internet上的服务器必须先访问DNS服务器，经过DNS对域名的解析才能连接到相应的主机。所以，在一个网络中，DNS服务器应该部署在客户端可以集中访问的网络位置上。

20．进程间同步和互斥的含义是什么?

答：进程间同步是并发进程之间存在的相互制约和相互依赖的关系。

进程间互斥是若干进程共享一资源时，任何时刻只允许一个进程使用。

四．综合题（本题结果不是唯一的，每小题n分，共m分）

1．有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答：

(1)若对资源分配不加限制，会发生什么情况?为什么?

实用文档

(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么?

(1)多个进程动态地共享系统的资源可能会产生死锁现象。死锁的产生，必须同时满足四个条件，第一个是互斥条件，即一个资源每次只能由一个进程占用；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其它资源；第三个是非出让条件，任何一个进程不能抢占另一个进程已经获得且未释放的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只须确保上述四个条件之一不出现，则系统就不会发生死锁。

只要资源分配策略能保证进程不出现循环等待，则系统就不会发生死锁。

(2) 银行家算法分配资源的原则是：系统掌握每个进程对资源的最大需求量，当进程要求申请资源时，系统就测试该进程尚需资源的最大量，如果系统中现存的资源数大于或等于该进程尚需的最大量时，则就满足进程的当前申请。这样可以保证至少有一个进程可能得到全部资源而执行到结束，然后归还它所占用的全部资源供其它进程使用。银行家算法破坏了产生死锁的第四个条件，即不可能产生循环等待，从而可以避免死锁的发生。

防止进程发生循环等待的另一种资源分配策略是按序分配算法，其基本思想如下：把系统中所有的资源排一个顺序，例如系统共有m个资源，用ri表示第i个资源，那么这m个资源是：

r1, r2, r3 ……, rm

规定任何进程不得在占用资源ri（1

令牌环的维护

令牌环的故障处理功能主要体现在对令牌和数据帧的维护上。令牌本身就是比特串，绕环传递过程中也可能受干扰而出错，以至造成环路上无令牌循环的差错；另外，当某站点发送数据帧后，由于故障而无法将所发的数据帧从网上撤消时，又会造成网上数据帧持续循环的差错。令牌丢失和数据帧无法撤消，是环网上最严重的两种差错，可以通过在环路上指定一个站点作为主动令牌管理站，以此来解决这些问题。

主动令牌管理站通过一种超过机制来检测令牌丢失的情况，该超时值比最长的帧为完全遍历环路所需的时间还要长一些。如果在该时段内没有检测到令牌，便认为令牌已经丢失，管理站将清除环路上的数据碎片，并发出一个令牌。

为了检测到一个持续循环的数据帧，管理站在经过的任何一个数据帧上置其监控位为1，如果管理站检测到一个经过的数据帧的监控拉的已经置为1，便知道有某个站未能清除自己发出的数据帧，管理站将清除环路的残余数据，并发出一个令牌。

7．分布式可繁也可以简，请你组建一个最简单的分布式系统模型。

8．一个最完备的分布式体系由以下模块组成。请说明各模块的功能？

实用文档

①分布式处理系统必须有能力在短时间内动态地组合成面向不同服务对象的系统。对用户来说系统是透明的，用户只需指定系统干什么而不必指出哪个部件可以提供这一服务。系统各组成部分是自主的，但不是无政府状态，而是遵循某个主计划由高级操作系统进行协调工作。在一个计算机网中有多台主机不一定都是分布式处理。如果这样的系统不具备动态组合及任务再指派的能力，那么它们仍然是集中式处理。

②分布式查询可以访问来自多种异类数据源的数据，而这些数据可存储在相同或不同的计算机上。

③分布式数据库系统由分布于多个计算机结点上的若干个数据库系统组成,它提供有效的存取手段来操纵这些结

点上的子数据库。分布式数据库在使用上可视为一个完整的数据库,而实际上它是分布在地理分散的各个结点上。当然,分布在各个结点上的子数据库在逻辑上是相关的。

④分布式缓存支持一些基本配置：重复（replicated）、分配（partitioned）和分层（tiered）。重复（Replication）用于提高缓存数据的可用性。在这种情况下，数据将重复缓存在分布式系统的多台成员机器上，这样只要有一个成员发生故障，其他成员便可以继续处理该数据的提供。另一方面，分配（Partitioning）是一种用于实现高可伸缩性的技巧。通过将数据分配存放在许多机器上，内存缓存的大小加随着机器的增加而呈线性增长。结合分配和重复这两种机制创建出的缓存可同时具备大容量和高可伸缩的特性。

⑤分布式文件系统具有执行远程文件存取的能力,并以透明方式对分布在网络上的文件进行管理和存取。

⑥分布式网络通信能够连接跨越了多台计算机的应用程序各节点。

⑦分布式监控管理可以有效避免最上层服务器因顾及不暇而出现管理疏漏的现象。

⑧用于编写运行于分布式计算机系统上的分布式程序。一个分布式程序由若干个可以独立执行的程序模块组成,它们分布于一个分布式处理系统的多台计算机上被同时执行。它与集中式的程序设计语言相比有三个特点：分布性、通信性和稳健性。

⑨分布式系统的执行存在着许多非稳定性的因素。分布式算法起到分布性和并发性的作用，这一点不同于集中式算法。

9．设计一个分布式网络管理系统的架构与开发模型。（200字左右）

分布式网络管理系统的实现主要有对等式、层次式和混合式三种实现方式。

对等式（P2P）网络管理：网管功能被分布到多个管理者上，完成各自域内的网络逻辑管理（综合管理），而每个被管设备都是具有一定自我管理能力的自治单元。

层次式网络管理：引入中层管理站MLM（Middle-Level Manager）以减轻顶层管理站MOM（Manager Of Managers）的负担，减少网络传输、消除瓶颈，增加可靠性和扩展性，从而提高整个网络管理系统的性能。是一种很具生命力的方法。

实用文档

混合式网络管理：它结合了两者的优点，但当网络规模扩大时，集成管理站和单元管理站的增多将导致管理关系复杂性的非线性增长。

10．论分布式共享存储一致性协议的关键技术（200字左右）。

分布式共享存储可以使那些原来彼此独立的计算机共享一个统一的地址空间，称作虚拟共享存储空间。分布式共享存储层必需负责维护一致性。也就是说，任何处理机的读操作都要保证返回最新写的值，而不管这个写操作是由谁来执行的。一般来说，虚拟共享存储空间是按页进行管理的，当对一个远程的共享数据进行访问时，将会在本产生一个缺页，这个缺页将被软件共享存储层截获并负责从相应的处理机将需要的共享数据取来，并进行相应的一致性维护。如果这个共享数据在其他处理机上有副本，那么还要与其他处理机通信来维护一致性。高速缓存的一致性设计为其关键技术。典型：基于目录的一致性协议，包括目录状态设置及其转换、转发策略、死锁处理机制等。

新型：基于锁的高速缓存一致性协议。

12．论分布式软件可靠性评价（200字左右）。

软件可靠性评价是软件可靠性活动的重要组成部分，既可在软件开发过程实施，也可针对最终软件系统实施。软件可靠性评价的难点在于软件可靠性模型的选择和软件可靠性数据的收集与处理。请围绕“软件可靠性评价”论题，依次从以下三个方面进行论述。

（1）简要概述你参与实施的或你研究的软件开发项目以及你承担的主要工作。

（2）说明你在课题研究实施过程中所选择的软件可靠性模型，并论述在软件可靠性模型选择时应该考虑的主要因素。

（3）收集软件可靠性数据时经常遇到的问题有哪些？简述你收集软件可靠性数据时所遇到的具体问题及解决的方法。

13．论软件的静态演化和动态演化及其应用（200字左右）。

软件演化（Software Evolution）是指软件在其生命周期内的更新行为和过程。演化是一系列贯穿软件生命周期始终的活动，系统需求改变、功能实现增强、新功能加入、软件架构改变、软件缺陷修复、运行环境改变均要求软件系统能够快速适应变化，具有较强的演化能力。软件静态演化（Static Evolution）和动态演化（Dynamic Evolution）是目前软件演化的两种重要类型。

请围绕“软件的静态演化和动态演化及其应用”论题，依次从以下三个方面进行论述。

（1）概要叙述你参与管理或开发的软件项目以及你在其中所担任的主要工作。

（2）请分别对软件静态演化和动态演化的特点进行论述，说明两种软件演化类型各自的优缺点及其应用场合，并举例说明各自的常见演化技术手段。

（3）具体阐述你参与管理和开发的项目中所进行的软件演化活动的特点、演化的类型，以及所采取的对应演化技术手段，说明具体实施过程以及实际应用的效果。

14．结合你在分布式系统领域的工作或研究方向，设计一个面向服务计算方面的软件应用模型。

面向服务的计算代表了分布式计算和软件开发的最新发展方向。按下面要求用300字左右来描述。

（1）面向服务计算的基本过程

（2）建立服务对象模型

（3）定义服务

（4）算法描述