分布式操作系统期末复习（辽宁大学王龙主讲）包含往年期末题_分布式系统期末大题

目录

一、题目

1.1 简答题

1.2 综合题

二、题目答案

2.1 简答题目答案

2.2 综合题目答案

三、期末题型分值分布

3.2 题型和分值

---

一、题目

1.1 简答题

1什么是中间件 22.1（22年期末考试第一题）24.1

2 什么是名称解析 23.1

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

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

5．标识符是否可以包含它所引用实体的信息？ 22.3（22年期末考试第三题）24.2

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

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

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

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

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

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

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

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

1.2 综合题

1.什么是分布式系统？分布式系统发展的前提条件有哪些？  22.7 23.7 24.5

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

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

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

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

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

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

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

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

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

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

12. 分布式令牌环算法存在令牌丢失的问题，如果令牌丢失，会导致算法失败，请将改算法改进一下，使该算法既能检测到令牌丢失，也能进行补救。(22.13)  23.13 24.10

二、题目答案

2.1 简答题目答案

1什么是中间件 22.1

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

2 什么是名称解析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 综合题目答案

1.什么是分布式系统？分布式系统发展的前提条件有哪些？  22.7

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

1. 硬件方面：每台计算机都是独立、自主的计算机
2. 软件方面：用户感觉在独占系统

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

1. 计算机性能价格比在迅速提高
2. 网络技术的发展与普及：有线网络、移动计算、无处不在的计算
3. 计算量增大
4. 任务本身需要分布式处理

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

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

RPC的执行步骤：

1. 客户过程以普通方式调用相应的客户存根；
2. 客户存根建立消息，打包并激活内核陷阱；
3. 内核将消息发送到远程内核；
4. 远程内核将消息发送到服务器存根；
5. 服务器存根将消息解包，取出其中参数后调用服务器过程；
6. 服务器完成工作或将结果返回服务器存根；
7. 服务器存根将它打包并激活内核陷阱；
8. 远程内核将消息发送至客户内核；
9. 客户内核将消息交给客户存根；

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

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

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

欺负算法:

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

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

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

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

环算法:

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

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

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

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

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

答：集中式算法

选一个进程为协调者（比如在最大网络地址的进程）；无论什么时候进程要进入临界区，它将向协调者发送请求信息，说明它想进入那个临界区并希望获得允许；

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

分布式算法：

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

1. 它要进入的临界区的名字；
2. 它要进入的处理机号；
3. 当前时间；

将消息发送给所有其它进程；发送的消息假设是可靠的，即每条消息都应该被确认；

当一个进程接收另一个进程请求消息时，它取决于接收方的状态以及临界区的命名。有三种情况要加以区别：

1. 接收者不在临界区中，也不想进入临界区，它就向发送者发送OK消息
2. 接收者已在临界区中，它就不必回答，而是负责对请求队列排队
3. 接收者要进入临界区，消息时间戳对比，取小的那个
   1. 如果来的消息的时间戳小，接收者发送OK消息
   2. 如果接收者本身时间戳更小，接收者负责排列请求队列而不发送任何消息

令牌环算法：

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

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

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

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

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

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

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

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

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

具体类型：

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

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

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

8.有三个进程分别运行在不同的机器上，每个机器都有自己的时钟并以不同且不变的速率工作（进程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

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

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

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

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

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

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

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

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

12. 分布式令牌环算法存在令牌丢失的问题，如果令牌丢失，会导致算法失败，请将改算法改进一下，使该算法既能检测到令牌丢失，也能进行补救。(22.13) 

为了改进分布式令牌环算法，以便检测到令牌丢失并进行补救，可以引入以下改进措施：

1. 令牌超时机制：在原有的分布式令牌环中，为每个令牌设置一个超时时间。当一个令牌在规定时间内没有被正确传递，即发生令牌丢失，系统会检测到并触发补救措施。

2. 令牌冗余备份：在分布式环中，创建多个冗余令牌，使其与原始令牌具有相同的身份和功能。这样，当原始令牌丢失时，系统可以自动切换到冗余令牌，确保算法的持续正常运行。

3. 令牌状态监测：在算法中引入令牌状态监测机制，即定期检查令牌的传递情况。通过周期性地检测令牌是否按照预期的顺序传递，系统可以快速发现令牌丢失并采取相应的补救措施。

4. 自适应令牌传递速率：根据令牌环中各个节点的处理能力和网络延迟等情况，动态调整令牌的传递速率。这样可以在一定程度上减少令牌丢失的概率，降低算法失败的风险。

5. 错误恢复机制：在检测到令牌丢失后，系统应该具备相应的错误恢复机制。例如，可以重新分配或复制丢失的令牌，并将其插入到环中的适当位置，确保算法的正常运行。

通过以上改进措施，分布式令牌环算法可以更加可靠地检测到令牌丢失并进行补救。这样可以提高算法的鲁棒性和容错性，减少因令牌丢失导致算法失败的情况发生

三、期末题型分值分布

3.2 题型和分值

期末考试：100分*60%，平时分40分

6个简答，30分

7个综合，70分