2011-辽宁大学分布式操作系统复习题-1(1)

1、2011辽宁大学分布式操作系统复习题1. 说明分布式系统相对于集中式系统的优点和缺点。从长远的角度看，推动分布式系统发展的主要动力是什么？答：相对于集中式系统，分布式系统的优点：1）从经济上，微处理机提供了比大型主机更好的性能价格比；2）从速度上，分布式系统总的计算能力比单个大型主机更强；3）从分布上，具有固定的分布性，一些应用涉及到空间上分散的机器；4）从可靠性上，具有极强的可靠性，如果一个极强崩溃，整个系统还可以继续运行；5）从前景上，分布式操作系统的计算能力可以逐渐有所增加。分布式系统的缺点：1）软件问题，目前分布式操作系统开发的软件太少；2）通信网络问题，一旦一个系统依赖网络，那么网络

2、的信息丢失或饱和将会抵消我们通过建立分布式系统所获得的大部分优势；3）安全问题，数据的易于共享也容易造成对保密数据的访问。推动分布式系统发展的主要动力：尽管分布式系统存在一些潜在的不足， 但是从长远的角度看，推动分 布式系统发展的主要动力是大量个人计算机的存在和人们共同工作于信息共享的需要，这种信息共享必须是以一种方便的形式进行。而不受地理或人员，数据以及机器的物理分布的影响2. 多处理机系统和多计算机系统有什么不同？答：共享存储器的计算机系统叫多处理机系统，不共享存储器的计算机系统为多计算机系统。它们之间的本质区别是在多处理机系统中，所有CPU共享统一的虚拟地址空间，在多计算机系统中，每个计

3、算机有它自己的存储器。多处理机系统分为基于总线的和基于交换的。基于总线的多处理机系统包含多个连接到一条公共总线的CPU以及一个存储器模块。基于交换的多处理机系统是把存储器划分为若干个模块，通过纵横式交换 器将这些存储器模块连接到 CPU上。多计算机系统分为基于总线的和基于交换的系统。在基于总线的多计算机系统中，每个CPU都与他自身的存储器直接相连，处理器通过快速以太网这样的共享多重访问网络彼此相连。在基于交换的多计算机系统中，处理器之间消息通过互联网进行路由，而不是想基于总线的系统中那样通过广播来发送。3. 在分布式操作系统中，为什么采用微内核技术，通常微内核提供哪些服务？答：采用微内核技术的

4、原因：1）高度模块化，每一个服务都有一个定义好的接口，每个用户都可以访问任何服务，服务与位置独立；2）高度灵活性，具有添加、删除和修改服务的功能；3）用户定制，用户可以自定义服务。微内核提供的服务有：1）进程间通信机制；2）某些内存管理功能；3）少量的底层进程管理和调度；4） 低层输入/输出服务4. 解释透明性的含义，并举例说明不同类型的透明性。答：对于分布式系统而言，透明性是指它呈现给用户或应用程序时，就好像是一个单独是计算机系统。具体说来，就是隐藏了多个计算机的处理过程，资源的物理分布。具体类型：透明性描述存取透明性隐藏了数据表示和获取资源的具体实现位置透明性用户不必知道资源位于何处迁移透

5、明性资源可以不改名随意移动重定位透明性用户不必知道资源是位置是否改变复制透明性用户不必知道有多少拷贝存在并发透明性多个用户可以自动的共享资源容错透明性用户不必知道系统岀现错误5. 应用哪些技术可以使得一个分布式系统具有可伸缩性? 答：实现分布式可伸缩性，基本的三种技术为：1、减少通信延迟，即使用异步通信方式，使得发送方发送请求后不必阻塞以等待答复，而是处理其他 本地任务。2、分层，即将一个组件分解为几个小层。一个好的例子是DNS 域名系统，它将域名分为三层，均衡了系统负载。3、复制冗余，它能使得资源更容易就近获取，并且它能使资源分布于整个系统，均衡了负载。6. 什么是普适家庭系统？说明其中存在

6、的主要技术问题。 答：普适系统，即将分布的各种小型的，蓄电的，移动的设备，以无线连接的方式整合在一起的系统。 它无需人工进行管理， 最好的情况是其自动配置， 自己管理。 家庭普适系统， 即将各种家用电子设备 （如 电视，手机等）整合在一起的系统。其存在的主要技术问题包括：1、实现完全的自我配置，自我管理存在困难。2、个人空间的存储，安全问题。7. 举例说明三层客户 /服务器体系结构。 答：此三层分为： 用户接口层 （接收用户请求） ，处理层（核心逻辑处理） ，数据层（返回用户所需数据） 。 以一个 Internet 搜索引擎为例，用户使用键盘，鼠标输入想要检索的信息，经过用户接口层传递给处理

7、层，生成查询语句，然后到达数据层（即数据库）查询数据，再将查询结果返回给处理层，让它对结果 进行排序，生成 HTML 页面，最后返回给用户接口层（即浏览器）显示给用户。8. 给出一个多线程客户端的例子，并给出一种构造多线程服务器的方法。 答：多线程客户端例子，以网页浏览器为例： 浏览器在从服务器获取 HTML 文件时，同时也在显示它。因为一个 HTML 文件可能包含文本，图像， 音频， 视频等文件， 故当一个线程获得其中一个文件并显示它时， 同时还有其它线程正从服务器读取其 它文件。即一个浏览器拥有多个线程与服务器进行交互。构建多线程服务器：使用有限状态机模型， 它使用非阻塞系统调用方法， 可

8、实现并行处理多个请求。 对每一个接收或发送的 消息都将其处理状态存储到一个表中，由多线程对其进行处理。9. 在代码迁移时，需要迁移代码片断、资源片断和执行片断，说明在迁移资源片断时需要考虑的主要问 题。答：迁移资源片段时，有时需要考虑改变资源片段的相关引用，以适应迁移后的使用，但是又不能改变 该资源与其他进程之间的绑定关系。 此外， 有时还需考虑该资源片段与机器之间的绑定关系。例如有些资源片段迁移后可用，但是要花很大代价，有些则迁移后在其他机器上不可执行。10. 什么是有状态服务器和无状态服务器，给出相应的例子，并说明有状态服务器存在的问题。 答：无状态服务器，在请求之间，服务器不保存具体客户

9、的信息，以及与客户端交互活动的有关信息。 它要求每个请求必须是独立的，必须包含全文件名和文件中的偏移量，因此消息长度较长。 有状态服务器，在请求之间，服务器保存客户信息以及与客户交互活动的有关信息，11. 说明在移动 IP 系统中，如何定位一个实体。AddreSSAddfeSSAddleSSNamingI SerViCeLOCatiOnSerVlCe(a)(b)a) 名称与地址的直接映射b) 使用标识符的两极映射12. 在基于DHT的P2P系统中如何定位一个实体，并举例说明。答：DHT全称叫分布式哈希表(DiStribUted HaSh Table),是一种分布式存储方法。每个客户端负责一个小

10、范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。连入DHT网络的用户叫做节点(node)，节点之间互相有路由记录，因此只要和任何一个已经在DHT网络中的节点连接上，客户端就可以寻找到更多的节点，从而连入网络。举例见书p189o .13. 在基于DHT的P2P系统中如何构造多播树，并举例说明影响性能的主要问题。14. 客户-服务器模式的主要思想及优点。答：其主要思想是构造一种操作系统，它由一组协同进程组成，这组进程称为服务进程，为客户机提供服务的进程称为客户。客户和服务器都运行在相同的微内核中，都以进程方式运行。一台机器可以运行多个客户、多个服务器或者两者的结合，客户-服

11、务器模式常常以简单的请求/应答协议为基础，客户向服务器发送一个请求， 请求一些服务，服务器完成后返回所要的数据或者给岀一个错误代码，指岀工作未完成。优点：1)简单，客户发岀一个请求得到一个应答，在使用之前无需建立连接也不需要释放连接；2)有效性，协议栈比较短因而更有效。15. 客户为了发送消息给服务器，它必须知道服务器的地址。试给岀服务器进程编址的几种方法，并说明 如何定位进程。答：方法一。机器号加进程号，内核使用机器号将消息正确地发送到适当的机器上，用进程号决定将消息发送给哪一个进程。方法二。进程选择随机地址，通过广播方式定位进程，进程在大范围的地址空间中随机指定自己的标识号。在支持广播式的

12、LAN中，发送者广播一个特殊的定位包，其中包含目的进程地址，所有的内核查 看地址是不是他们的，如果是则返回消息给岀网络地址，然后发送内核缓存地址。方法三。客户机运行时，使用ASCIl码访问服务。客户机运行时，向名字服务器发送请求信息，名字服务器将ASCII服务器名映射成服务器地址，客户机收到给地址后，可以访问服务器。16. 对于接收消息ReCeiVe原语，为什么需要缓存，缓存的作用是什么？答：如果不适用缓存，服务器接收来的消息会被丢弃或者存在诸如服务器需要存储和管理早到来的消息 这样的问题。缓存的作用就是用来统一管理消息的：它定义了一种叫邮箱的数据结构，接收客户端请求的进程通知内核创建邮箱存储

13、消息，并且指定了访问地址。当ReCeiVe原语调用是，系统内核就会提取消息并知道如何处理它。17. 说明在C/S模式下解决消息可靠传输的三种方法？答：1、重新定义非可靠的 Send语义。系统无法保证消息发送成功，完成可靠地通信依赖于用户2、要求接收机器的内核给发送机器的内核发送一个确认消息。只有收到这个确认消息后发送内核释放用户进程。确认消息从一个内核传送到另一个内核，无论是客户还是服务器都看不到确认消息。3、客户在发送消息后阻塞，服务器内核不发送确认消息而是将应答作为确认消息。因此客户进程一直 阻塞到应答消息到来为止，如果时间太长，发送内核会重新发送请求以防止消息丢失。18. 说明 RPC

14、的主要思想及 RPC 调用的主要步骤。 （远程过程调用函数 sum（4,7） 为例说明） 答：主要思想是允许程序去调用位于其他机器上的过程。当位于机器 A 的一个进程调用机器 B 上的某 个过程时，机器 A 上的过程被挂起，被调用的过程在机器 B 上执行。调用者讲消息放在参数表中传送 给被调用者，结果作为过程的返回值返回给调用者。消息的传送与 I/O 操作对于编程人员是不可见的。 主要步骤如下： 1）客户过程以普通方式调用相应的客户存根；2）客户存根建立消息并激活内核陷阱；3）内核将消息发送到远程内核； 4 ）远程内核将消息发送到服务器存根； 5 ）服务器存根取出消息中的 参数后调用服务器过程

15、； 6）服务器完成工作后将结果返回至服务器存根；7）服务器存根将它们打包并激活内核陷阱； 8）远程内核将消息发送会客户内核； 9）客户内核将消息提交给客户存根； 10）客户存 根从消息中取出结果返回给客户。19. 在 RPC 调用时，如果服务器或客户机崩溃了，各有哪些解决方法。 答：如果是服务器崩溃了，用户无法区分服务器是在执行前还是执行后崩溃，解决方案如下：1）至少一次语义，指等待服务器重新启动，然后重发请求。这种方法要求不断重试直至客户收到应答消息。它 保证 RPC 至少执行一次。 2）之多一次语义，指立即放弃并报告失效。它确保RPC 至多执行一次，但也可能根本没有执行； 3）不作保证；

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

17、。20. 一个影响 RPC 执行时间的问题是消息的拷贝问题，试说明在那些环节需要拷贝，并说明减少拷贝次数 的方法。答：需要消息拷贝的环节：在发送端，消息从客户存根拷贝到客户内核缓冲区，再从客户内核缓冲区拷 到客户接口芯片缓冲区（网卡） ，然后消息被拷贝到接收端的服务器接口芯片缓冲区，之后拷贝到服务 器内核缓冲区，最后到达服务器存根（共5 次）拷贝。此外，有时还需要拷贝参数数组。减少拷贝次数的方法：分散 -集中方法（汇集发） ，具有分散 -集中能力的网络芯片可以减少拷贝次数， 他通过拼接 2 个或者多个内存缓冲区来组装报文。 在发送端， 由客户内核缓冲区生成报文消息头。 由客 户存根生成报文消息

18、体，当发送时，由网络芯片组装报文。同样地，接收端将接收来的报文分解成消息 体和消息头，并放入相应的缓冲区。21. 在组通信中，给出组编址的的三种方式。答： 1、每组分配地址，有三种方式：单播，多播，广播，发送进程将消息发送给组地址，消息将会发 布给所有成员2、要求发送端提供一份目的地址的显示列表；3、 判定编址，消息将被发送给所有成员，每条消息包含了判定条件，如果判定条件评估为TRUE ，则 消息被接受，否则消息丢弃。22. 用组通信方式时，举例说明消息顺序的重要性，并说明解决方法说明。答：要使组通信易于理解和使用，有两种性质是不可缺少的，首先是原子广播原语，它确保了一条消息 要么被所有组内成

19、员收到，要么没有一个成员能收到。其次是消息的顺序。例如：有四台机器每台机器 有一个进程，进程 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 ,以

20、很少的时间间隔发送，系统 先取其中一个作为第一个发送给所有组内成员，然后再取下一个发送给组内成员， 这种方法保证组内成员按照统一的顺序收到了消息，但是这个顺序可能并不是发送消息的顺序。LAMPORT 算法中怎样23. 实现分布式系统同步的复杂性表现在哪几个方面？说明先发生关系，并说明在给事件分配时间。答：分布式算法有如下性质：1)相关信息分散在多台机器上；2)进程决策仅依赖于本地信息；3)系统中单点故障应避免；4)没有公用时钟和其他精确的全局时间资源存在。前三点说明在一处收集所有 信息并对他们进程处理是不可接受的，左后一点说明在分布式系统获得时间上的一致并不是容易的。a,在所有进程中都认可给它

21、一个时间值1)在同一进程中a发生在b之前则C(a)<C(b) ； 2)若aC(a)<C(b) ； 3)对所有事件 a 和 b, C(a) C(b)每个机器都有自己的时钟并以不同且不变的速率工作8下，而进程3的时钟嘀嗒了LamPOrt方法解决。1LAMPORT算法的解决方案是直接使用先发生关系，每条消息都携带发送者的时钟以指岀其发送的时 间，当消息到达时，接受者的时钟比消息发送者时钟小，就立即将自己的时钟调到比发送者的时间大 或更多的值，我们给岀一种测量时间的方法，使得对每一事件C(a),在给事件分配时间时要遵循一下规则：和b分别代表发送消息和接收消息，则(进程1的10下)。举例说明

22、进程之间消息传24. 有三个进程分别运行在不同的机器上，时钟嘀嗒了 6下时，进程2的时钟嘀嗒了答：如右图所示：三个进程进程2给进程递中违反先发生关系的情况，并说明如何用发送消息C和进程1给进程0发送消息 违反了先发生关系，消息到达的时间小于 消息发送的时间。LamPort解决方案直接使用先发生关系，每 条消息携带发送者的时钟以指岀其发送的 时刻，当消息到达时，接受者时钟若比发 送者时钟小，就立即将自己的时钟调到比 发送者大1或者更多的值(这里使用值“ 1”。进程1在收到消息C后将56调整为61,发送消息D的时钟将是69,;进程0在 收到消息D后将54调整为70进程0进程125. 说明RICAR

23、T 和AGRAW ALE 分布式互斥进程2算法；假定A和B是相互独立的两个临界区， 进程0要进入A ,进程1要进入B，R-A分布 式互斥算法会导致死锁吗？说明理由。答：RICART和AGRAWALE算法要求系统中所有事件都是全序的，也就是说，对任何事件组消息，哪 个先发必须无歧义，算法如下：当一个进程想进入临界区时，他要建立一个包括他要进入的临界区的名 字、处理机号、当前时间的消息，然后将消息发送给所有其他进程，也包括发送给自身，当一个进程接 收另一个进程消息时，它取决于接受方的状态以及临界区的名字有三种情况：1)接受者不在临界区，也不想进入临界区，他就向发送者发送OK消息；2)接受者已经在临

24、界区，它不必回答，而是负责对请求队列排队；3)接收者要进入临界区，但是还没有进入，它要负责将发来的消息和它发送给其他进 程的时间戳对比，取小的那个。如果来的消息时间戳小，接收者发送OK消息，否则接收者负责排列请求队列而不发送任何消息。在发送完允许进入临界区的请求后，进程将不再做任何事，仅等待所有的允许消息，一旦得到允许，它 就进入临界区。它从临界区退出时，向队列中所有进程发送OK消息，并将它从队列中删除。该算法可能导致死锁，例如： A和B是相互独立的两个临界区，进程 0要进入A ,进程1要进入B ,而 此时进程0在B中，进程1在A中就会进入死锁。26. 许多分布式算法需要一个协调者，叙述欺负选

25、举算法。答：欺负算法是当一个进程发现协调者不在响应请求时，它就发起选举，进程P负责选举如下：1）P向所有号码比他大的进程发送选举消息；2）若无人响应，P获得成功，称为协调者；3）如有响应，则响应者接管，P的工作完成。在某一时刻，一个进程只能从号码比他小的进程进程那里得到一个选举消息，当消息到达时，接收者发回OK消息，表明它的存在并接管主持选举。除了一个进程外的其他进程都放弃了，那么这个进程就是新的协调者，它将选举获胜的消息发送给所有进程，告知它是新的协调者。若一个进程刚刚崩溃过，而 又得到恢复，它主持选举，该算法中总是进程号最大的进程获胜，所以命名为欺负算法。27. 举例说明用私有工作空间实现

26、事务处理时的基本思想。答：在进程开始一个事务时给它分配一个包含了所有需要访问的文件的私有工作空间，在事务提交或终止前，所有的读写操作都在私有空间而不是真正的文件系统中进行，存在的问题是所有内容都拷贝到私有空间，代价难以承受。优化方法是：1）私有空间中只包含一个指向父辈工作区的指针，当事务处于最顶层时，它的工作区是 真正的文件系统。2）使用索引节点，索引是一个与判断文件所在的磁盘块位置有关的数据库，给方法 不将全部文件考入私有空间，而只是拷贝索引。28. 说明在分布式系统中实现原子性提交的两阶段提交协议的基本思想及其优点。答：两阶段提交协议的基本思想是有一个进程作为协调者，通常是执行事务的进程。

27、在准备提交阶段，协调者向日志中写入Prepare,然后向所有服务器发送准备提交消息，服务器接收到消息后，检查自己是否准备提交，如果是就向日志中写入Ready，然后向协调者发送准备好消息。在提交阶段，协调者接收所有响应后决定提交还是撤销，如果所有服务器都准备提交，则提交事务；否 贝U撤销事务。无论如何协调者都会写入日志，并发送决定消息，服务器接到消息后也将结果写入日志， 并发送结束消息，完成整个过程29. 举例说明为什么使用集中式的死锁检测算法会产生假死锁，并给岀一种解决办法。答：集中式的死锁检测算法每台机器的资源图中只包含它自己的进程和资源，协调者节点保存整个系统（所有资源图的集合）的资源图。

28、当机器资源图发生变化时相应的消息发送给协调者以提供更新，当协调者检测到环路时，它终止一个进程以解决死锁。a 机器0b 机器1C 协调者d 协调者如上图圆表示进程，方框表示资源，开始时如同a，b，C所示，过来一段时间，B释放R并请求T,这是一个合法的操作，机器0向协调者发送一条消息申明它释放资源R，机器1向协调者发送一条消息声明进程B正在等待它的资源 T,不幸的是机器1的消息先到达协调者， 导致生成资源图如图d所示。协 调者得岀错误的结论一一死锁存在，这种情况称为假死锁。解决办法是：使用LamPort算法以提供全局统一的时间，对协调者收到的消息按照时间戳排序30. 举例说明分布式死锁检测方法Ch

29、andy-MiSra-HaS算法的思想以及如何解除死锁。答：算法允许进程一次请求多个资源，例如下图所示的资源图。图中只给出进程，每条弧穿过一个资源,当某个进程等待资源时，生成一个探测消息（阻塞的进程，发送消息的进程，接收消息的进程）发送给0.趴 UJ占用资源的进程。消息 到达后，如果接受者也 在等待其他进程占用的 资源，则跟新探测消息, 第一个字段保持不变， 第二个字段改为当前的 进程号，第三个字段改为等待的进程号，跟新后的探测消息发送给等待的占有资源的进程。如果存在多个进程则要发送多个不同的消息。如果消息又回到最初的发送者说明存在一个又死锁的环路系统解除死锁的方法：1）令最初发送探测消息的进

30、程自杀。如果多个进程同时阻塞同时发送探测消息，那 么每个进程都会发现死锁并因此自杀。2）将每个进程的标识符添加到探测消息的末尾，将编号最大的进程中止或者发送消息请求的进程自杀。多个进程发现同一环路会选择同一个牺牲者。31. 说明wait-die和WOUnd-Wait分布式死锁预防方法。 事务时间戳为50的进程申请事务时间戳为 100的进 程占用的资源。按以上两种策略，结果会如何？答：（时间戳越小的进程越是年老）wait-die死锁预防算法：当较老的进程请求年轻进程所占有的资源时，老进程只能等待；如果年轻进程请求老进程占有的资源时，年轻进程会被终止。WOUnd-Wait死锁预防算法：当老进程请求

31、年轻进程所拥有的资源时，老进程抢占年轻进程的资源，年轻进程被终止；当年轻进程请求老进程所拥有的资源时，年轻进程等待。32. 说明发送者发起的分布式启发算法和接收者发起的分布式启发算法及各自的主要缺点。答：发送者发起的分布式启发算法：当创建进程时，创建进程的机器将对一个随机选取的机器发生询问， 询问它的负载是否低于某个阈值，如果是，将发送进程否则将选择另一台机子发送询问。如果在N次询问内还没有找到合适的机器，算法停止新进程将在创建它的机器上运行。该算法的缺点是：在负载十分严重的情况下，所有机器都会不停的毫无意义的向其他机器发送询问，想找到一台愿意接受更多工作的机器，在这种情况下，几乎没有进程会被

32、减轻负载，但却会引起相当可观的额外开销。接收者发起的分布式启发算法：当一个进程结束时，系统将检查自己是否有足够的工作可做，如果没有，将随机向一台机器申请工作，如果那台机器没有要给予的工作，系统将继续询问第二，第三台机器，如 果询问N台机器都没有申请到工作，系统将暂停申请开始处理系统队列中一个等待进程，当这个进程 结束后，开始下一轮的申请；如果系统无事可做，则将进入空闲状态，一定时间后从新开始申请。给算 法的缺点是：系统在无事可做时会造成相当大的询问负载。33. 说明主机后备容错方法的主要思想，在主机崩溃后存在的问题及解决方法。答：主机后备容错方法的主要思想是在任何时候，服务器都由主机完成所有工

33、作，如果主机失效，则由 后备机接管工作。在RPC过程中，主机崩溃后产生的情况如下：1）主机在执行任务前崩溃，则没有损失，客户端会超时重发直到连上后备机，任务至执行一次；2）主机在执行任务后，向后备机发送跟新消息前崩溃，此时后备机接管，消息再次到来，任务被执行2次；3）主机在后备机执行任务后自己发送相应消息前崩溃,则任务被执行3次，一次由主机完成，一次由后备机完成，一次由后备机接管时完成。如果请求消息带 有序号，则可以减少任务执行次数。34. 多处理机系统中，fail-silent类型和ByZantine类型处理机错误各需要至少多少个处理机才能满足要求？ 说明理由。答：fail-silent类型

34、处理机错误是指失效的处理机只是停止运行，对接下来的输入不做反应也不产生进一步的输出，即宣布它不在工作了。对于这样的错误，需要K+1个这样的处理机以满足 K容错要求，因为若K个处理机停止工作，那么剩下的那个处理机继续工作。ByZantine类型的错误是指岀错的处理机继续运行，产生问题的错误答案，并可能和其他岀错的处理机一起“恶意”地工作。对于这类错误，那么至少需要2K+1个处理机才能满足 K容错要求，因为岀错的处理机仍然运行并发岀错误或随机应答，最坏情况下，K个失效处理器偶然产生同样的应答，剩下K+1个未岀错的处理机也将产生相同应答，因此客户或者表决器只要相信大多数应答就可得到正确的结果。35.

35、 举例说明LamPort等人提出的算法是如何解决 ByZantine将军问题的。答：LamPOrt等人设计了一种递归算法可在特定条件下解决这一问题。例如：N = 4 （有四个将军），M =1 （其中有一个叛徒），对这样的参数，参数运行四步。第一步，每个将军发送可靠的消息给其他所有的将军，声明自己真实的军队人数，忠诚的将军声明的是真值，叛徒则可能对其他每个将军都撒一个不同的谎。如图a；第二步，把第一步声明的结果组成向量形式，如图b；第三步，每个将军把图 b中各自的向量传递给其他每一个将军，这里叛徒再一次撒谎，使用了12个新值。A J。如图C;第四步，每个将军检查所有新接收向量的每一个元素，若某个

36、值占多数则把该值放入结果向量中，将军 1(G1) 1KG1 = (1K, 2K, X, 4K)将军 2(G2) 2KG2 = (1K, 2K, Y , 4K)将军 4(G4) 4KG3 = (1K, 2K, 3K, 4K)将军 3(G3) X,Y,ZG4 = (1K, 2K, Z, 4K)abG1 = (1K, 2K, UNKNOW, 4K)G2 = (1K, 2K, UNKNOW, 4K)G4 = (1K, 2K, UNKNOW, 4K)G2 = (1K, 2K, 3K, 4K)G1 = (1K,2K,X,4K) (1K,2K,Y,4K) (A,B,C,D) (1K,2K,Z,4K)G2 =

37、 (1K,2K,X,4K) (1K,2K,Y,4K) (E,F,G,H) (1K,2K,Z,4K)G3 = (1K,2K,X,4K) (1K,2K,Y,4K) (1K,2K,3K,4K) (1K,2K,Z,4K)G1 = (1K,2K,X,4K) (1K,2K,Y,4K) (I,J,K,L) (1K,2K,Z,4K)C36. 在实时分布式系统中，动态调度和静态调度的含义是什么？比较动态调度和静态调度算法。答：动态调度是指在程序运行期间进行调度决定下面运行哪一个进程。静态调度是指在系统开始运行前就已经进行，算法的输入包含了所有任务的列表及它们各自的运行时间。两者比较如下：1）静态调度适合时间触发

38、系统的设计，动态调度适合事件触发系统的设计；2）在资源利用方面动态调度比静态调度有更大潜力；3）若给定足够的处理能力，对静态系统一个最优或次优的调度可以事先获 得，动态系统在运行期间无法承受复杂的调度计算花费。37. 说明使用主动复制方法的容错的主要思想，并给出以下TMR系统可应付多少个故障元件（设备和表决器），举例说明可屏蔽掉的最坏的情况。答：主动复制是使用物理冗余来提供容错的一种著名的技术，这种方法也适用于电子电路的容错。主动复制的一个主要问题是需要复制多少份才合适，这取决于要达到的容错量。如果系统在k个部件岀错时仍能达到系统设计的要求而正常工作，那么这个系统称为是 k级容错的。如fail

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

40、冗余能否处理ByZabtine故障。答：三模冗余是使用物理冗余来提供容错的技术，是使用主动复制方法的容错。在电子电路中有设备 A、B、C,然后每个设备复制三次，结果就是每级电路都设置了三个表决器，每个表决器有三个输入和一 个输出，若两个或者三个输入相同，输出则等于输入，若三个输入各不相同，输出就是不定值，这种设 计就是TMR。若处理机是 ByZabtine类型的，出错的处理机仍然工作并发出错误的随机的应答，那么至少需要2k+1个处理机才能达到k级容错。最坏情况下k个失效的处理机偶然（甚至有意）地产生相同的应答，然而 剩下的k+1个未出错的处理机也将产生相同的应答，因此客户机可以根据大多数的应答

41、得到正确结果。三模冗余在每组中有一个部件出现ByZabtine故障时可以处理，而一组中有两个甚至三个同时出现ByZabtine故障则不能处理。39. 举例说明采用图论确定性算法进行处理机分配的实现方法。答：整个系统可以表示为一张带权图，每个节点表示一个进程，每条边表示两个进程之间的通信量。从数学角度看，整个问题就变成了如何根据特定的限制将图划分成k （ k为系统中CPU数量）个不相连的子图（如每个子图的总 CPU和内存需求在一定限制内）。对于每种满足限制的解决方案，子图内部的边 意味着机器内部的通信，可以忽略。从一个子图连向另一个子图的边表示网络通信。该算法的目标就是在满足限制下，找到一种划分

42、方式使网络通信量最小。下图表示了图的两种划分：Ca)(b)方案 A:通信量=(3 + 2 + 4+4)+(2+8+ 5 + 2)= 30方案 B:通信量=(3 + 2 + 4+ 4) + (3+5+ 5 + 2) = 2840. 举例说明时间触发和事件触发的区别。答：事件触发是指，当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的 cpu 得到一个中断请求。时间触发是指，在每隔固定的时间 t 后产生一次时钟中断，对选定的传感器进行采样，并且驱动（特定 的）执行机构。举例，考虑一个 100 层楼的电梯控制器设计。假定电梯正在 60 层安静的等待顾客，有人在一层按下按 钮。就在 1

43、00 毫秒后，另一人在 100 层按下按钮。在事件触发系统中，第一次按钮产生一个中断，将使 电梯启动下行， 就在他做出下行决定后， 第二个按下按钮的事件到来， 因此第二个事件被记录下来以作 将来的参考，但电梯还是继续下行。若考虑时间触发系统， 没 500 毫秒采样一次。 若两次按下按钮都在一次采样周期中出现， 控制器就不得 不进行决定，例如按最近用户优先原则，此时电梯将上行。由以上例子可以看出， 事件触发的设计在低负载时会更快响应， 但在高负载时可能崩溃。 时间触发相反， 仅适用于相对静态的环境。41. 使用上载 /下载模式的文件服务器系统与使用远程访问模式的文件系统之间有什么区别？ 答：文件

44、服务分为两种类型：上载 /下载模式和远程访问模式。上载 /下载模式。只提供两种主要的操作（读文件和写文件） ，读操作将整个文件从文件服务器传输到请 求客户端，写操作则刚好相反，文件系统运行在客户端。优点是系统概念简单，应用程序取得需要的文 件，并在本地使用它。当程序结束时，将所有修改的文件或新创建的文件写回去，不需要管理复杂的文 件服务接口， 文件传输效率高。 缺点是客户端需要足够的存储空间， 当需要部分文件是需要传输整个文 件。远程访问模式。 提供了大量的操作， 如打开、关闭文件， 读写部分文件等等。 文件系统在服务器端运行。 优点是客户不需要大量存储空间，当需要部分文件是不需要传输整个文件

45、。42. 分布式系统中处理共享文件的四种方法（文件共享的四种语义）。答： 1）UNIX 语义。系统使所有的操作都有一个绝对时间顺序，READ 操作读取最近一个 WRITE 操作后的内容，要求对一个文件系统的任何操作对所有进程都是及时可见的。2）会话语义。对于打开文件的修改最初只对修改文件的进程是可见的，当文件关闭后，对文件的修改 对其他进程才是可见的。3）不可修改语义。不允许打开文件进行写操作，只提供CREATE 和 READ 两种操作。只能进程讲的的共享和复制。4）事务语义。使用原子事务，即所有的操作要么全做，要么全不做。43. 说明保持客户高速缓存一致性的四种算法。答： 1）直接写，当缓存

46、中的文件被更新后，新的值在缓存在保存，而且同时发送到服务器，而当另外 的进程访问文件时， 读到的是最新值， 但是存在一个问题， 其他进程在更新之前读到的文件内容可能是 过期的， 那么在每次用到文件时需要从服务器中读取文件版本进行比较， 查看是否过期， 但是每次都要 在服务器和客户端之间通信，这样就体现不出缓存的作用了。2）延迟写，操作不立即发送给服务器，而是延迟一段时间，也就减少了网络消息，当进程读取文件时， 依赖于时间。具体读到的是那次操作的结果不确定，语义模糊。3）关闭写，操作只有在文件关闭后才写回服务器，配合session 语义。4）集中控制，就是在文件服务器上保存了进程对文件的操作方式

47、等信息，类似于锁机制的管理，避免 写操作的文件被其他进程操作， 但是当修改的操作结束时， 会将操作结束消息通知服务器， 操作的结果 也就立即会送到服务器44. 说明分布式系统提供文件复制服务的原因以及实现复制的三种方法。 答：分布式系统通常保持文件的多个拷贝， 每个拷贝放在一台单独的文件服务器上， 提供这种服务主要 有一些几种原因： 1）数据不丢失，通过对每个文件的独立备份来增加系统的可靠性；2）当一个文件服务器岀现问题时，仍然允许进行文件访问；3）负载均衡，将工作量分配到多个服务器上1¥s1C2s2*以后以后SlS3s2s2文件1.142.163.19proc.c1.212.433

48、.41符号名对个二进制地址以后以后S3三种复制方法一次如上图所示:1）显示复制，如图a所示，是为编程人员控制整个进程所用，当进程产生一个文件时，可以在其他服 务器上生产另外的拷贝，如果目录服务允许一个文件有多个拷贝，所有拷贝的网络地址都可以和这个文件名联系起来。2）懒惰拷贝，如图b所示，只要在某个服务器上建立每个文件的一个拷贝服务器自己在其他的服务器 上也可以自动生成副本。3）用组复制文件，如图 C所示，所有的写系统调用同时传送到所有的服务器，于是，其他的拷贝在源 文件产生时就产生了。45. 说明更新复制文件的两种主要算法：主拷贝算法、Gifford算法。答：主拷贝算法，使用时，指定一个服务器

49、为主服务器，其他所有服务器为从服务器，当要更新一个复 制文件时，我们就将该改变发送至主服务器上，在本地完成修改，然后向各从服务器发岀命令，命令他 们也完成修改。这样可以在任何一个（主或者从）服务器上进行读操作。这种方法简单，但是有个问题, 当主服务器停机时，所有的更细将不能进行。GiffOrd算法，基本思想是在读写一个复制文件之前要求先申请并获得多个服务器的允许。例如，读一 个已经有N个副本的复制文件，客户需要获得一个读法定数，它是任何Nr个或更多个服务器的任一集合，同样的，修改一个文件需要一个至少NW个服务器的写法定数。Nr和NW的值必修满足约束条件N叶Nw>N ,只有在适当数目的服务

50、器同意参与时，文件才能进行读写操作。46. 说明基于总线的多处理机系统中的Write-through 和Write once协议。答：通写缓存一致性协议是一种特别简单的，通用的协议。当CPU从存储器中首次读取某个字时，该字通过总线取岀并存储在提岀请求的CPU缓存中，当再次需要这个字时，CPU不再提岀访问存储器的请求，而是直接从缓存中获取，这样减少了总线流量，通写缓存一致性协议概括如下：事件缓存响应本地CPU操作时执行缓存响应远程CPU操作时执行的动作读失败Read miss从存储器中取得数据并存储到缓存中无动作读命中Read hit从本地缓存中取得数据无动作写失败Write miss更新存储器

51、中的数据并存储到缓存中无动作写命中Write hit更新存储器和缓存使缓存无效表中的第一列列岀了可能发生的四种基本事件，第二列说明缓存如何响应CPU的操作，第三列说明缓存发现（通过监听）其他 CPU的读写操作如何反应。例如，当监听者发现其他 CPU写入的字在其缓存 中（从监听者角度看是命中）时，监听者必须采取措施，即从本缓存中删除这个字。通写协议易于理解和使用。缺点是所有的读写操作必须通过纵向，因此允许挂在单一总线上的CPU数量仍然很少，不能满足大型多处理机的需求。Write-OnCe协议：该协议管理缓存块，每个块处于一下三种状态之一：1)无效，本缓存块没有有效数据； 2)干净，存储器被更新，

52、该块可能在别的缓存中；3)脏，存储器错误，该数据块不在其他缓存中。基本思想是允许正被多个CPU读取的字出现在它们所有的缓存中，而仅被一个CPU经常写的字只保存在他的缓存中，为减少总线流量，不必每次都写回存储器。47. 说明顺序一致性应满足的要求；在如下并行执行的进程 P1和P2,列出顺序一致性所允许的6种语句交叉执行情况。a=1;b=1;if (b= =0) kill (P2)if(a= =0) kill (P1)(a) P1(b) P2答：顺序一致性模型由下述条件定义：1)如果所有进程以一定顺序执行操作，每一进程的操作都以程序规定的顺序岀现，则任何操作的结果都是一样的；2)要求分布式系统中的所有成员和它们的进程共享一个通用视图，此视图记录了对于共享能存访问操作的顺序。顺序一致性所允许的6种语句交叉执行情况：a = 1;b = 1;a = 1;b = 1;a = 1;b = 1;if(b = 0)