分布式操作系统

《分布式操作系统》由会员分享，可在线阅读，更多相关《分布式操作系统（9页珍藏版）》请在金锄头文库上搜索。

1、第一章 知识点 1.说明分布式系统相对于集中式系统的优点和缺点。 从长远的角度看，推动分布式系统发 展的主要动力是什么？（不要列表） 优点：经济性 微处理机提供了比大型主机更好的性能价格比速度 分布式系统中的计算能力比单个大型主机更强固有的分布性 一些应用涉及到空间上分散的机器可靠性 如果一个机器崩溃，整个系统还可以运转渐增式的增长方式 计算能力可以逐渐有所增加 缺点：软件：目前为分布式系统开发的软件还很少；网络：网络可能饱和和引起其他的问题；安全：容易 造成对保密数据的访问。 从长远的角度看，推动分布式系统发展的主要动力是大量个人计算机的存在和人们共同工作与信息共享的 需要。 2.多处理机系

2、统和多计算机系统有什么不同？ MIMD 计算机分成两类：具有共享存储器的多处理机和不具有共享存储器的多计算机。 在多处理机中， 所有的 CPU 共享统一的虚拟地址空间。在多计算机中，每个计算机有它自己的存储器。 3.真正的分布式操作系统的主要特点是什么？ 必须有一个单一的、全局的进程间通信机制。进程管理必须处处相同。文件系统相同。使用相同的系统调 用接口 5.在分布式操作系统中，为什么采用微内核技术，通常微内核提供哪些服务？ 内核尽可能少的提供服务，大量的操作系统服务可从用户级服务器上获得。 微内核具有更好的灵活性。 只提供四种最小的服务：1.进程间通信机制 2.某些内存管理功能 3.少量的低

3、层进程管理和调度 4. 低层输 入/输出服务。 第二章 知识点 9.说明在 C/S 模式下解决消息可靠传输的三种方法? （1）重新定义非可靠的 send 语义。系统无法保证消息成功发送，完成可靠的通信依赖于用户。 （2）要求接收机器的内核给发送机器的内核发送一个确认消息 （3）客户机在发送消息后阻塞，服务器的内核不发送确认消息，而是将应答作为确认消息。超时重发。 （4）折衷方案。当一个请求到达服务器内核，计时器启动，如果服务器能很快给出应答，这个应答就是 确认消息。否则，单独发送确认消息。 10.说明 RPC 的主要思想及 RPC 调用的主要步骤。 （远程过程调用函数 sum(4,7) 为例说

4、明） RPC 的基本思想：调用远程过程就像调用本地过程一样 主要步骤：（1）客户过程以普通方式调用相应的客户存根；（2）客户存根建立消息并激活内核陷阱； （3）内核将消息发送给远程内核；（4）远程内核将消息送到服务器存根；（5）服务器存根取出消息中 的参数后调用服务器的过程；（6）服务器完成工作后将结果返回给服务器存根；（7）服务器存根将它打 包并激活内核陷阱；（8）远程内核将消息发送给客户内核；（9）客户内核将消息交给客户存根；（10） 客户存根从消息中取出结果返回给客户。sum 调用的参数为 4 和 7，客户过程以普通方式调用相应的客户存根； 客户存根获取这两个参数打包入消息中，并将调用过

5、程的名字或过程号放入消息中； 当消息到达服务器后，由存根检查消息以确定需要哪个过程，然后调用相应进程 sum； 服务器进程一结束，服务器存根再次取得控制权，它将获取运行结果并将其打包形成消息，激活内核陷阱； 远程内核将消息发送至客户内核；客户内核将消息交给客户存根；客户存根从消息中取出结果，返回给客 户进程。 12.RPC 信包发送可采用爆发协议，但是会产生超限错误(overrun error)，给出解决办法。 （1）如果超限错误是由于芯片处理中断而暂时无法接收信包引起的，发送者可在发送两个信包之间加入 一段延迟时间。 （2）如果超限错误是由于芯片的缓冲区不够而引起的，如果缓冲区容量为 n 个

6、信包，则可在发送 n 个信 包后留一个间隙，或是在发出 n 个信包后，得到一个确认后再发送后面的包。 13.一个影响 RPC 执行时间的问题是消息的拷贝问题，试说明在哪些环节需要拷贝，并说 明减少拷贝次数的方法。 八次拷贝 客户存根客户内核缓冲区客户接口芯片缓冲区服务器接口芯片缓冲区服务器内核缓冲区服务 器存根 如果此调用含有一个大的值参数组时，还需另外三步拷贝： 将数组拷入客户进程的堆栈以调用客户存根。 客户存根组装时，将数组从堆栈拷贝到消息缓冲区中。 服务器存根将数组从消息中取出，放入服务器进程的堆栈中。 减少拷贝次数的方法： 分散-集中(汇集） 具有分散- 集中能力网络接口芯片可以减少拷

7、贝次数。它通过连接两个或多个内存缓冲区来装配一个信 包。 在发送端， 由客户内核缓冲区生成报文消息头，由客户存根生成报文消息体，当发送时，由网络芯片 组装报文。 接受端将接收来的报文分解成消息体和消息头，并放入相应的缓冲区。 14.在组通信中，给出组编址的的三种方式。 （1）给每个组一个唯一的地址。有三种方式：单播、多播、广播，发送进程将消息发送给组地址，消息 将会发布给所有成员。 （2）要求发送者提供一个所有目的地址的显式列表。 （3）判定编址。消息将被发送给所有成员，每条消息中包含了判定条件，如果判定评估为 TRUE，则消 息被接收，否则被抛弃。 第三章 知识点 16.实现分布式系统同步的

8、复杂性表现在哪几个方面？说明先发生关系，并说明在 LAMPORT 算法中怎样给事件分配时间。 （1）复杂性：相关信息分散在多台机器上 进程决策仅仅依赖于本地信息 系统中单点故障应避免 没有公用时钟和其他精确的全局时间资源存在 （2）先发生关系a 发生在 b 之前，记为：a b。存在两种情况：如果 a 和 b 是同一进程中两个事件，且 a 发生在 b 之前，则 ab 为真；如果 a 是一个进程发送消息的事件，b 为另一个进程接收这一消息的事件，则 ab 为真（3）Lamport 算法遵循的规则： 若在同一进程中 a 发生在 b 之前，则 C（a）C （b）; 若 a 和 b 分别代表发送消息和接

9、收消息，则 C （a）C （b） ； 对所有的 a 和 b，C （a ）C （b） 。 20.举例说明用私有工作空间实现事务处理时的基本思想。 在进程开始一个事务时给它分配一个包含了所有需要访问的文件的私有工作空间，在事务提交或中止前所 有的读写操作都是在私有工作空间而不是在真正的文件系统中进行的。存在的问题：所有内容拷贝到私有 工作空间，代价难以承受。 两种优化方法： （1）私有工作空间中只包含一个指向父辈工作区的指针。当事务处于最顶层时，它的工作区是真正的文 件系统。使用索引节点。 （2）索引是一个与判断文件所在磁盘块位置有关的数据块。该方法不将全部文件 拷入私有工作空间，而只是将其索引拷

10、入。 22.举例说明为什么使用集中式的死锁检测算法会产生假死锁，并给出一种解决办法。 (a)机器 0 初始资源图 (b)机器 1 初始资源图 (c)协调者对系统的观察 (d) 延迟信息后的系统情况 当 B 释放 R 并请求 T。机器 0 向协调者发送一条消息生命它释放 R，机器 1 向协调者发送消息声明 进程 B 在等待资源 T。若近机器 1 的消息先到达，这导致协调者生成（d） ，错误地得出死锁存在的结论， 并终止某个进程。 解决方法：LAMPORT 算法以提供全局时间。机器 1 导协调者消息的时间戳晚育机器 0 到协调者的 消息的时间戳，当协调者收到机器 1 发来的有导致死锁嫌疑的消息后，

11、它将给系统每台机器发一条消息询 问是否有更小时间戳的消息要发给它。每台机器响应后，协调者会看到从 R 到 B 已经消失，因此系统安 全。 24.说明 wait-die 和 wound-wait 分布式死锁预防方法。事务时间戳为 50 的进程申请事务时间戳为 100 的进程占用的资源。按以上两种策略，结果会如何? （1）Wait-die 算法 算法思想 当一个老进程想得到一个年轻进程占用的资源时，老进程等待。 当一个年轻进程想得到一个老进程占用的资源时，年轻进程终止。 （2）wound-die 算法 算法思想 当一个老进程想得到一个年轻进程占用的资源时，老进程抢占年轻进程的资源， 年轻进程终止。

12、 当一个年轻进程想得到一个老进程占用的资源时，年轻进程等待。 第四章. 知识点 25、叙述实现线程包的方法及其优缺点。 在用户空间中实现线程：是将线程包完全放到用户空间中去，内核对此一无所知。优点：在不支持线程的 操作系统中实现；线程切换比使用内核陷阱快一个数量级；允许每个进程有自己定制的调度算法。缺点： 阻塞调用怎样实现？系统调用改为非阻塞，SELECT。如何实现调度？旋转锁，时钟信号中断。 在内核中实现线程：当一个线程想去创建一个新线程或撤销已存在的线程时，它发出一个内核调用，由它 完成创建和回收工作。内核中每个进程都有一张包含线程信息（线程的寄存器、状态、优先权等）的表。 优点：容易实现

13、调度。缺点：系统开销大。 调度者行为：内核分配一定数量的虚拟处理机给每个进程，并且让（用户空间）运行期系统将线程分配给 处理机。优点：效率，很好地解决了控制权有阻塞线程传递给非阻塞线程。缺点：可能产生死锁，与分层 系统的内在结构相违背。 26、说明发送者发起的分布式启发算法和接收者发起的分布式启发算法及各自的主要缺点。 发送者发起的：当创建进程时，创建进程的机器将对一个随机选取的机器发送询问其负载是否低于某个阈 值。如果是，则发送进程。否则，选择另一台机器继续询问。如果在 N 次询问内还没有找到合适的机器， 算法将停止。新进程将在创建它的机器上运行。缺点：在负载非常重的情况下，所有机器都会不停

14、的毫无 意义的向其它机器发送询问。没有进程会减轻负载。引起系统大的额外开销。 接收者发起的：当一个进程结束时，系统将检查自己是否有足够的工作可做。如果不是，将随机向一台机 器申请工作。如果那台机器没有要给予的工作，系统将继续询问第二、三台机器。如果 N 次都没有申请 到工作，系统将暂时停止申请，开始处理系统队列中一个等待的进程。当这个进程结束后，开始下一轮的 申请。优点：该算法不会在系统非常繁忙的时候给系统增加额外的负载。缺点：在系统潜在时使系统开销 增大。 28、多处理机系统中，fail-silent 类型和 Byzantine 类型处理机错误各需要至少多少个处理机才能满足要求？说明理由。

15、对于第一种错误 fail-silent 类型，失效的处理机只是停止运行，对接下来的输入不作反应也不产生进一步 的输出。 对于 Byzantine 错误，出错的处理机继续运行，产生问题的错误答案，并可能和其它的出错的处理机一起 “恶意”地工作，给人一种正常工作的假象。 如果出错属于 fail-slient 型，那么有 k+1 个这样的部件足以满足 k 容错的要求。若 k 个处理剂简单停止工 作，那么可使用剩下的那个处理机的结果。 若错误是 Byzantine 型的，至少需要 2k+1 个处理机才能达到 k 容错。最会情况下，k 个失效处理机偶然地 产生相同的应答，剩下的 k+1 个未出错的也将产

16、生相同的应答，因此客户或表决器只要相信大多数 的应答就可以得到正确结果。 30、在实时分布式系统中，动态调度和静态调度的含义是什么？比较动态调度和静态调度 算法。 含义：动态算法是在运行期间进行调度。静态的调度算法是在运行前事先就调度好的。 比较：静态适合时间触发系统的设计，动态调度适合事件触发系统的设计。 在资源利用方面，动态调度比静态调度具有更大的潜力 若给定足够的处理能力，静态系统可事先获得一个最优或次优的调度策略。 33.举例说明采用图论确定性算法进行处理机分配的实现方法。 图论确定性算法算法要求进程知道它所要求的 CPU 和内存要求，并且知道系统中每对进程之间要求的平均通信量。如果系统的 CPU 数量 k 小于进程数，则将多个进程指派到同一个 CPU 上。算法的思想是使这种指派 能够使网络的通信量最小化。 在（a ）中，A E G 划分在一个处理机上，B、F 、H 划分在第二个处理机上，C D I 在第三个处理机上。整 个网络通信量等于与虚线橡胶的边的权值和，为 30. 在（b）中