分布式系统试题及答案.doc

分布式系统复习题库及答案1、 计算机系统的硬件异构性、软件异构性主要表现在哪几方面？参考答案：计算机系统的硬件异构性主要有三个方面的表现，即：计算机的指令系统不同。这意味着一种机器上的程序模块不能在另一种不兼容的机器上执行，很显然，一种机器上的可执行代码程序不能在另一种不兼容的机器上执行。数据表示方法不同。例如不同类型的计算机虽然都是按字节编址的，但是高字节和低字节的规定可能恰好相反。浮点数的表示方法也常常不一样。机器的配置不同。尽管机器的类型可能相同，其硬件配置也可以互不兼容。计算机系统的软件异构性包括操作系统异构性和程序设计语言异构性。操作系统异构性的三个主要表现方面为：操作系统所提供的功能可能大不相同。例如，不同的操作系统至少提供了不同的命令集。操作系统所提供的系统调用在语法、语义和功能方面也不相同。文件系统不同。程序设计语言的异构性表现在不同的程序设计语言用不同方法在文件中存储数据。2、 由于分布计算系统包含多个（可能是不同种类的）分散的、自治的处理资源，要想把它们组织成一个整体，最有效地完成一个共同的任务，做到这一点比起传统的集中式的单机系统要困难得多，需要解决很多新问题。这些问题主要表现在哪些方面？参考答案：资源的多重性带来的问题。由于处理资源的多重性，分布计算系统可能产生的差错类型和次数都比集中式单机系统多。最明显的一个例子是部分失效问题：系统中某一个处理资源出现故障而其他计算机尚不知道，但单机系统任何一部分出现故障时将停止整个计算。另一个例子是多副本信息一致性问题。可见，资源多重性使得差错处理和恢复问题变得很复杂。资源多重性还给系统资源管理带来新的困难。资源的分散性带来的问题。在分布计算系统中，系统资源在地理上是分散的。由于进程之间的通信采用的是报文传递的方式进行的，通信将产生不可预测的、有时是巨大的延迟，特别是在远程网络所组成的分布计算系统中更是这样。例如使用卫星通信会产生270毫秒的延迟。在分布计算系统中，系统的状态信息分布在各个分散的节点上。分布式的状态信息和不可预知的报文延迟使得系统的控制和同步问题变得很复杂，要想及时地、完整地搜集到系统各方面的信息是很困难的，从而使处理机进行最佳调度相当困难。系统的异构性带来的问题。在异构性分布计算系统中，由于各种不同资源（特别是计算机和网络）的数据表示和编码、控制方式等均不相同，这样一来就产生了翻译、命名、保护和共享等新问题。由于上述原因，分布计算系统的研制，特别是软件的验证、调试、测量和维护问题变得很复杂。这些正是分布计算系统研制者要解决的主要问题。3、 分布式计算系统具有透明性时，系统有什么主要优点？参考答案：系统具有透明性时有以下一些优点：使软件的研制变得容易，因为访问资源的方法只有一种，软件的功能与其位置无关。系统的某些资源变动时不影响或较少影响应用软件。系统的资源冗余（硬件冗余和软件冗余）使操作更可靠，可用性更好。透明性使得在实现这种冗余的时候，各种冗余资源的互相替换变得容易。在资源操作方面，当把一个操作从一个地方移到若干地方时没有什么影响。4、 简述基于中间件技术的分布式计算系统的组成结构。参考答案：对于基于中间件的分布计算系统，它的组成结构可以用图1表示。机器C机器B机器A分布式应用中间件服务NOS服务NOS服务NOS服务本地OS本地OS本地OS硬核硬核硬核网络图1 基于中间件的分布计算系统的组成结构许多分布式应用程序直接使用网络操作系统提供的编程接口。例如，应用程序的通信功能通过网络操作系统提供的socket机制来实现，使得不同机器上的进程之间能够相互传送报文。另外，应用程序通过本地文件系统提供的接口使用文件。这种直接利用网络操作系统提供的服务编制的应用程序很难具有很高的透明度。为了解决这个问题，可以在应用程序和网络操作系统之间增加一个软件层次，提供一个更高的抽象层次。这样的一个软件层次称为中间件，它位于应用程序和网络操作系统之间，如图1所示。5、 简述分布式程序设计和顺序程序设计的基本区别。参考答案：分布式程序设计和顺序程序设计的三个基本区别是：使用多个处理机、处理机合作和存在着部分失效。使用多个处理机。分布式程序在不同的处理机上并行执行其代码的不同部分。高性能应用程序使用这种并行性达到加速执行的目的，它的目标在于如何最佳地使用可以得到的处理机，考虑哪些计算需要并行计算是非常重要的。在容错应用程序中，不同处理机执行的功能要根据增加可靠性和可用性来决定。对于专用功能和固有的分布式应用程序，功能可在一个给定的处理机上执行，因为这个处理机具有某种能力或者包含有服务所需的数据。总而言之，对分布式程序设计支持的第一个要求就是系统应该具有把一个程序的不同部分分配到不同处理机上执行的能力。处理机合作。分布计算系统的各个进程在执行分布式应用程序时需要合作。运行并行的应用程序时，各个进程有时需要交换中间结果，对它们的活动要进行同步。例如，在控制自动工厂的系统中，各处理机要相互监视，检测出失效的处理机。分布式操作系统的各服务程序需要相互支持，例如进程服务可能需要文件服务的帮助以获得进程的二进制映像文件。在分布式电子邮件中，必须在各个进程之间转发报文。上述各个例子中，各个进程必须能相互通信和同步，这是对分布式程序设计支持的第二个要求。处理部分失效。在单机系统中，如果CPU失效，所有的工作立即停止。但在分布计算系统中一些CPU失效时，其他CPU照样工作。可利用这个性质编写一个能对硬件失效容错的程序。这对于容错应用程序特别重要，其他应用程序也需要。例如对于能用于比赛的分布式下棋程序来说，能对处理机失效容错是非常有用的。所以对分布式程序设计支持的第三个要求是能对系统的部分失效进行检测并恢复。6、 分布式计算系统故障的基本处理方法主要有哪些？参考答案：故障的基本处理方法有三种，它们是：主动复制。所有的复制模块协同进行，并且它们的状态紧密同步。被动复制。只有一个模块处于动态，其他模块的交互状态由这一模块的检查点定期更新。半主动复制。是主动复制和被动复制的混合方法。此种方法所需的恢复开销相对较低。容错是建立在冗余的基础上的，冗余是设置超过正常系统操作所需要的信息、资源或时间。冗余的类型取决于故障的处理方法和故障的特性。对于永久性的故障，常用硬件冗余的方法来屏蔽；而对于暂时性的故障，常通过时间冗余的方法进行重试。当使用主动复制的方法时，通常使用N-模块化冗余（NMR）。在被动复制中可以使用向前式恢复和向后式恢复。7、 说明分布式计算系统处理死锁常见策略。参考答案：有多种策略用于处理死锁，其中最常见的策略有：预防死锁。通过限制请求，保证四个死锁条件中至少有一个不能发生，从而预防死锁。（1） 进程在开始执行之前同时获得所有所需资源。（2） 所有的资源都要被赋予一个唯一的数字编号。（3） 每个进程被赋予一个唯一的优先级标识。（4） 使用时间戳的动态优先级预防死锁方案避免死锁。如果结果状态是安全的，就将资源动态地分配给进程。如果至少有一个执行序列使所有的进程都能完成运行，那么这个状态就是安全的。虽然死锁避免策略在集中式系统中广为应用，并且有许多算法，但是在分布式系统很少使用。这是因为在分布式系统中没有全局时钟，检查安全性状态会涉及到大量进程和资源的计算，这些会引起昂贵的开销。检测死锁和从死锁中恢复。允许死锁发生，然后发现并解除死锁。（1） 集中式死锁检测算法。（2） 分布式死锁检测算法（3） 等级式死锁检测算法。8、 给出Lamport时间戳互斥算法的主要思想，报文传递数量参考答案：Lamport时间戳互斥算法由以下5条规则组成，为方便起见，认为每条规则定义的活动形成单个事件：一个进程Pi如果为了申请资源，它向其它各个进程发送具有时间戳Tm:Pi的申请资源的报文，并把此报文也放到自己的申请队列中；一个进程Pj如果收到具有时间戳Tm:Pi的申请资源的报文，它把此报文放到自己的申请队列中，并将向Pi发送一个带有时间戳的承认报文。如果Pj正在临界区或正在发送自己的申请报文，则此承认报文要等到Pj从临界区中退出之后或Pj发送完自己的申请报文之后再发送，否则立即发送；一个进程Pi如果想释放资源，它先从自己的申请队列中删除对应的Tm:Pi申请报文，并向所有其他进程发送具有时间戳的Pi释放资源的报文；一个进程Pj如果收到Pi释放资源的报文，它从自己的申请队列中删除Tm:Pi申请报文；当满足下述两个条件时，申请资源的进程Pi获得资源：（a）Pi的申请队列中有Tm:Pi申请报文，并且根据时间戳它排在所有其它进程发来的申请报文前面；（b）Pi收到所有其它进程的承认报文，其上面的时间戳值大于Tm。使用Lamport时间戳互斥算法，进入一次临界区共需要3(n-1)个报文，n为参加互斥的进程数。9、 给出公开密钥加密技术实现数字签名的主要思想。参考答案：使用公开密钥加密技术实现数字签名要求加密函数E和解密函数D满足下列条件：E(D(P)=P， 当然同时还有D(E(P)=P也就是E和D可以互换。现在，假定A向B发送一个签名报文P。A的公开密钥为KeA，保密密钥为KdA。B的公开密钥为KeB，保密密钥为KdB。图2显示了使用公开密钥加密技术实现数字签名的过程。图中DA(P)=D(KdA,P)， EB(P)=E(KeB,P)。A先对报文P进行签名，形成P的签名形式DA(P)；然后对报文的签名形式进行加密，形成签名报文的加密形式EB(DA(P)；B收到这个加过密的签名报文后，使用自己的保密密钥解密，得到报文的签名形式DA(P)=DB(EB(DA(P)；最后B对签名的报文进行验证并获得报文的明文形式P=EA(DA(P)，同时保留P的签名形式DA(P)。B知道这个签名报文确实是从A那儿发送来的，因为只能用A的公开密钥KeA才能解密成功。同时，A不能否认，因为B保留有P的签名形式DA(P)。图2 使用公开密钥实现数字签名10、 多副本更新算法参考答案：有很多方法解决多副本数据库的相互一致性问题，它们在达到相互一致性的质量、性能、开销、坚定性以及所作的假设性条件等各方面有很大的不同。分布式多副本数据库本身是一个分布式控制问题。复制控制算法用来保证兼容可串行化，保持数据库多副本间的相互一致性。复制控制算法分为两大类：表决法和非表决法。表决法是在控制者之间交换报文，对分布式数据库要进行的各事务处理的整个次序达成一致意见。非表决法使用控制优先权，一种方法是在各控制者之间建立主从关系。表决法又分为同步和异步两大类。在同步表决方案中，各控制者对一个给定事务处理进行表决，一旦取得一致意见就共同执行此事务处理的各步骤。在异步表决方案中，允许各控制者和存储处理机并发地对不同事务处理的请求和执行进行表决。不管是哪种表决，都是根据全局事务处理排序方案决定先后顺序，每个事务处理都盖有时间戳，所以给定的一组事务处理可根据时间戳标记进行排序。注意：本次分布式计算系统考试（11月7日 10:0012:00）所有试题均从本题库中抽取，考试方式为闭卷。试题及答案说明：为了让大家对所学课程有基本的了解，胡明老师并没有给出试题答案。所有试题答案均由本人从教材中摘录，其中第1、2、3、4、5、6、8、9等8道题目答案为标准答案，第7、10题答案为本人从教材中总结的答案，仅供参考。所有题目答案均来源于分布式系统电子版教材。（包含在分布式系统课件压缩包中，可至群共享中下载）其中1-4题来源于第一章绪论，第5题来源于第三章分布