高级操作系统题目及答案

1、在实现RPC时，调用者如何得知被调用者实际运行在哪个站点上，是一个必须要解决的问 题。当系统生成与调用者对应的stub时，可把该远程站点的地址也一同并入其中，不过这种 做法不太灵活。在进行调用之前，与调用者对应的stub向系统中的其它场点进行广播，请求有关的场点 通报其地址，这必然引起一系列的消息转移。特别，当这种广播是在若干网络之间进行 时，其转移速度是很慢的。由系统管理一个表，其表项的内容为站点地址；该场点上将运行的远程过程的名字。“愿意”产生一个可供其它场点引用的过程的那些场点就造一个表项到这个表中，该表项给 出了这些场点的地址和此远程过程的名字。希望引用远程过程的用户可通过查询此表获取

2、有 关信息。开发过程大致是这样的：调用者调用本地stub中的一个过程(开始远程过程调用请求).这个stub过程把有关的参数组装成一个消息包或一组消息包，形成一条消息.运行 此执行过程的远程场点的IP地址和执行该过程的进程ID号也包含在这条消息中.将这条消息发送给对应的RPC runtime(RPC运行库)子程序，由这个子程序将消息发 送到远程场点.在接收到这条消息时,server端的RPC runtime子程序引用与被调用者对应的stub中 的一个子程序，并让它来处理消息.与被调用者对应的stub中的这个子程序撤卸消息，解析出相关参数，并用本地调用 方式执行所指定的过程.返回调用结果，调用者对

3、应的stub子程序执行return语句返回到用户，整个RPC过 程结束.此3问针对集中分布式死锁检测方法何时或在什么情况下构造局部PWG才能反映系统资源的实际分配情况？(修改)1.每当从局部等待图中去掉一条边或向局部等待图插入一条新边时周期性的，当等待图中已经发生了若干改变时每当协调者需要引用环路检测算法时以下为死锁检测的基本假设进程在整个系统内统一命名每个结点有一个局部等待图：Gk=(Vk, Ek)，(p, q)Ek等价于p申请q占有结点k的资源; 显然，如果局部等待图中有环，则有死锁；所有的局部等待图的并有环是系统死锁的充要条 件。为什么不同站点上申请资源时要带上时戳？(增加)不同的站点的

4、请求消息附上唯一的标识(时戳)，可以避免报告假死锁解决接收消息的顺序与发送消息的顺序不一致问题时间戳及全排序保证了不会死锁。增加时间戳，防止回应的不及时(令牌丢失、令牌者故障)利用时间戳来标明申请资源的先后次序，以此来尽量消除对共享资源的竞争。当协调者故障时咋办？如国协调者进程由于所在的处理机故障而无法正常工作，系统只得通过在另一个处理机上重 新开始一个新的协调者副本才能运行。当协调者进程故障时，需要安排新进程代替它：选一个进程；通知其它进程；建立相应队列; 恢复工作。为了适应模块性、自治性和强健性的要求，系统设置了多个控制机构来管理，这样就形成了 多个资源与多个控制机构之间比较复杂的关系。当

5、协调者故障时，选择算法必须挑选具有最高优先数的某个活跃进程作为替换者，这个优先 数还必须告之系统中的每一活跃进程。此外，该算法还必须提供某种方式以便于已从故障中 恢复的进程去识别当前的协调者。具体的协调者选择算法有1.适用于共享通路结构系统的Bully选择算法，其中每个进程都可 以向系统中其他进程发送消息，2.适用于组织成一个环（物理环或逻辑环）结构系统的算 法（基于环的算法）怎样设计该算法（怎样设计死锁检测算法？）（层次式方法下面的思考题）层次式死锁检测算法分布式算法（修改）（1）开始时只有最低层的管理者，它们管理各自的PWG（2）检查每个管理者各自的PWG，如果存在环路，表示系统中存在死锁

6、，算法结束（3）若任一 2个管理者的PWG有公共节点出现，则在每一个这样的管理者之上构造一 个新的管理者，并将这些公共管理站点作为该新管理者所管理PWG的一部分，若节 点公共节点Pi，Pj出现在其中，且其下属之一的PWG中存在从Pi到Pj的路径，则 将Pi-Pj插入新的PWG中。（4）如果构造不出新的层次，则算法结束，返回系统无死锁，如果可以构造新的层次，则重复第2步。每个结点管理自己的局部等待图，其中一部分结点被指定为控制者，这些控制者构成一个树 型结构，树中每个非叶结点管理它的子树中的控制结点的局部等待图设A、B、C都是控制者（非叶结点），C是A和B的前辈结点，如果p同时出现 在A与B的局

7、部等待图中，则从C到A和从C至U B的路上的所有控制者结点的局部等待图中都含有p。如果p、q是C的局部等待图中的结点，且在C的某个后代结点的局部等待图中含有 边（p, q），则C的局部等待图中亦含此边。如果系统中某一个控制者的局部等待图中有环，则有死锁发生。为什么设计近者优先搜索算法？不难验证，采用由近及远算法搜索资源不会产生饥饿。被搜索到的每个结点几乎都接收到这 样的三条消息，即搜索消息，通知谁是后结点的消息和由前结点转发来的继续搜索消息。因 此，如果不考虑一个结点多次被搜索的情况，或者近考虑树形网络的情况，在最坏情况下需 要发4n条消息进行资源搜索工作。此外，还要加上搜索到资源后转发的成功

8、信。因而，看 起来由近及远算法比前两种算法通信量大得多。但是，当系统中有较多的结点拥有资源时， 采用这种算法往往很快就能获得资源。因此，对于“稀有”资源可能招标算法或回声算法比 较合适，而对于普遍拥有的资源，则由近及远算法可能更好些。算法让资源申请者由近及远地搜索，直至遇到具有所需要资源的结点为止。按照由近及远地 搜索资源，可使申请者总是在能够提供资源的结点之间，选择一个距离它最近的结点获得资 源。采用由近及远算法搜索资源不会产生饥饿，当系统中有较多的结点拥有资源时，采用这 种算法往往很快就能获得资源。上述算法略微改进就可以具有较强的强健性。我们规定，发搜索消息至一个下邻结点后，如 果在T时间

9、内无回答，则认为它已失效，然后向另外一个下邻结点发搜索消息或者向其后结 点转发继续搜索消息。不难验证，只要在算法执行过程中不产生新的失效结点，并且失效结 点不被恢复，则增加了如上规则后，由近及远算法是强健的。“合一一阈值”算法怎么实现，分析其算法复杂度。下面仅从算法的时空复杂性及算法的输出与最优解的差距等方面来简单地分析该算法。为 此，假定有n个模块等待分配给m个同构的处理机。我们可用一个矩阵表示1MC开销，由 对称性知，存贮这方面的数据只需n(n-1)/Z个单元。用另一矩阵存放当完成了一次成功的合 一后，修改相关模块的IMC开销后的信息，这也只需n(n-1)/ 2个单元。不难看出，合一过 程

10、采用的是一种局部性“贪心”策略，即每次查找一对这样的模块，它们经合一后不仅清除 最大的IMC开销，而且相应的处理机应满足应时和(或)存贮要求。若令T(n)为合一过程最 坏情况下的时间复杂性，则不难得到下面的递推式：T(n)=查找具有最大IMC开销模块对的时间+修改其它模块对的IMC开销的时间+ T(n-1)显然，T(n) = O(n3)。若经合一处理后剩下的模块数大于m，则认为合一失败(此时，不必进入“调整”阶段)。 为此，可假定经合一处理后的模块数小于等于m。“调整”阶段是“合一”阶段的继续。在 调整过程中，可用数组Tv1 . m存放各处理机的阈值，用Load1 . m存放各处理机上的实 际

11、负载。在合一过程中，由于一对模块合一后会引起相关模块对的IMC发生变更，因此， 在执行调整过程中，很难知道分离出哪个模块(或模块族)会使得处理开销最小，故此时采 用随机策略。在此，不妨把调整过程进一步描述为：计算各处理机的实际负载与其阈值之差Di，i = 1, 2,m；按Di的不增次序排序各处理机，并用j (j = 1, 2,，m)指称经排序后位于序号j处的 处理机；对于j = 1, 2,m-1执行下面的操作：若处理机j的Dj大于0，则用随机方法从处理机j上选定一模块(或模块族)并把它迁移到 处理机j+1上。重复此过程，直至处理机j的Dj不大于0。必要时，可对模块族进行分裂。 若处理机j的Dj

12、不大于0，则不做任何迁移工作。若处理机m的Dm大于0，则报告“失败”，否则调整成功。由上不难得知，调整过程的时间复杂性约为O(m3)。假定：系统中的处理机是相同的，且模块的优先级也是一样的。算法思想：该算法分成两个阶段：合一、调整。先将IMC (模块间通信)最大者合并在一 起(打算分给同一个处理机)，第二阶段看此分配是否超出“阈值”，对超出者进行调整。算法描述：设有n个模块，h个处理机：V= m1, m2,mn P= P1, P2,，Ph1、令 S= m1, m2, mn 2、 从S中寻找Si，Sj，它们之间存在最大的IMC，如果合并Si、Sj后满足内存和实时要求， 则a）合并 Si、Sj。即

13、用 SiU Sj 代替 Si, Sj；b）对于任取SkS & Sk尹Si & Sk尹Sj执行 用Sk与Si和Sj的IMC的和作为Sk与SiUSj的 IMC；3、重复2,直到找不到可以合并的；4、将S中未被合并的模块放入一个“族”5、如果S中现有模块族数Wh,则将它们分配给各个处理机，否则，对本次合一结果进 行调整；6、对于每一个处理机Pi,执行如下操作a）如果Pi分得的模块超过阈值，则选一个模块迁移到轻载者；7、如果对于每一个处理机，都没有超过阈值，则算法结束，否则，算法失败；8、以一定的策略将多出来的族放入其它族中，使|S|Wh，然后转6。（6）如何设计近者优先搜索算法？由近及远算法申请者向

14、其某个邻结点发一搜索消息，附上对资源的需求及参数p，p为申请者的结点编 号。接搜索消息后，将发来搜索消息的结点的编号和搜索消息中的参数p登记下来。我们定义 发来搜索消息的结点为它的上邻结点，搜索消息中的参数p所规定的结点为它的前结点。如 果接到搜索消息的结点具有所需要的资源，则向它的上邻结点发一成功消息，并附上自己的 结点编号，否则它先向其前结点发一消息，告诉自己是它的后结点。然后，发一消息给其上 邻结点，请求继续搜索，并附上参数p，p为自己的结点编号。上邻结点接继续搜索消息后，如果还有尚未搜索的下邻结点，那么就发一搜索消息给下邻 结点，附上参数p，p是从继续搜索消息中复制的。如果所有的下邻结点都已经搜索过，但 是它有后结点，则将继续搜索消息转发给它的后结点。如果既没有尚未搜索的下邻结点，又 没有后结点，则表示与它相连的所有结点都已经搜索过。此时，它向其上邻结点发一失败消 息。如果一个已经被搜索过的结点又接到搜索消息，则将搜索消息退回，发搜索消息的结点就 认为该下邻结点不存在。接成功或失败消息后，如果该结点非申请者，则将此消息转发给它的上邻结点，否则搜索 结束。申请者或者获得