高级操作系统试题

高级操作系统试题

2．请求驱动式令牌传递方法中，若pi发出request消息后久未获得Token，该怎么处理？若引

入时戳，该算法应做何修改？

答：

在请求驱动式令牌传递方法中，或pi发出的request消息后久未获得Token，应该决定是站点故障还是Token丢失，需要有对应逻辑环重构方法和Token生成方法。

可以引入时时戳增加算法的强健性，具体如下:

(1)当request消息后久未获得令牌，则向其它进程发询问消息；若其它进程无反对消息到达，则重新生成令牌，否则继续等待。

(2)若接收到询问消息的进程是令牌的持有者，或已发出一样Request消息，且自已Request消息的时戳先于询问进程Request消息的时戳，则立即发回一条反对消息。

(3)令牌持有者传递令牌时，若发现接收者故障，需要调用逻辑环重构算法进行环重构，再重新选择接收者。

3.我们讨论了资源管理中的“近者优先”策略，试设计具体实现该策略的算法并进行算法分析。

由近及远算法设计过程如下：

⑴申请者向其某个邻结点发一搜索消息，附上对资源的需求及参数p，p为申请者的结点编号。

⑵接搜索消息后，将发来搜索消息的结点的编号和搜索消息中的参数p登记下来。我们定义发来搜索消息的结点为它的上邻结点，搜索消息中的参数p所规定的结点为它的前结点。如果接到搜索消息的结点具有所需要的资源，则向它的上邻结点发一成功消息，并附上自己的结点编号，否则它先向其前结点发一消息，告诉自己是它的后结点。然后，发一消息给其上邻结点，请求继续搜索，并附上参数p，p为自己的结点编号。

⑶上邻结点接继续搜索消息后，如果还有尚未搜索的下邻结点，那么就发一搜索消息给下邻结点，附上参数p，p是从继续搜索消息中复制的。如果所有的下邻结点都已经搜索过，但是它有后结点，则将继续搜索消息转发给它的后结点。如果既没有尚未搜索的下邻结点，又没有后结点，则表示与它相连的所有结点都已经搜索过。此时，它向其上邻结点发一失败消息。

⑷如果一个已经被搜索过的结点又接到搜索消息，则将搜索消息退回，发搜索消息的结点就认为该下邻结点不存在。

⑸接成功或失败消息后，如果该结点非申请者，则将此消息转发给它的上邻结点，否则搜索结束。申请者或者获得最近的能够提供所需要的资源的结点编号，或者系统中没有所需要的资源。

为了算法的强健性，我们增加下列规则：

⑹如果发搜索消息到下邻结点后，在某个T时间内没有收到回复消息，则认为该下邻结点已经失效。然后，向另外一个下邻结点发搜索消息，或者向后结点发继续搜索消息。

不难看出，只要在算法执行过程中不产生新的失效结点，并且失效结点不被恢复，增加了上述规则后，由近及远算法是强健的不难验证，采用由近及远算法搜索资源不会产生饥饿。被搜索到的每个结点几乎都接收到这样的三条消息，即搜索消息，通知谁是后结点的消息和由前结点转发来的继续搜索消息。因此，如果不考虑一个结点多次被搜索的情况，或者近考虑树形网络的情况，在最坏情况下需要发4n条消息进行资源搜索工作。此外，还要加上搜索到资源后转发的成功信。因而，看起来由近及远算法比前两种算法通信量大得多。但是，当系统中有较多的结点拥有资源时，采用这种算法往往很快就能获得资源。因此，对于“稀有”资源可能招标算法或回声算法比较合适，而对于普遍拥有的资源，则由近及远算法可能更好些。

算法让资源申请者由近及远地搜索，直至遇到具有所需要资源的结点为止。按照由近及远地搜索资源，可使申请者总是在能够提供资源的结点之间，选择一个距离它最近的结点获得资源。采用由近及远算法搜索资源不会产生饥饿，当系统中有较多的结点拥有资源时，采用这种算法往往很快就能获得资源。

上述算法略微改进就可以具有较强的强健性。我们规定，发搜索消息至一个下邻结点后，如果在T时间内无回答，则认为它已失效，然后向另外一个下邻结点发搜索消息或者向其后结点转发继续搜索消息。不难验证，只要在算法执行过程中不产生新的失效结点，并且失效结点不被恢复，则增加了如上规则后，由近及远算法是强健的。

5．试设计层次式死锁检测方法的具体算法并进行算法分析。

答：

层次式死锁检测算法将这些信息分散给各个进程来管理，是一种分布式死锁检测算法。

全局等待图的每个站点管理自己的局部等待图，被分散给若干控制者管理，这些控制者组织成树型结构，其中树中的叶子结点包含单个站点的局部等待图，每个非叶子结点控制着它下面子树的控制者管理的等待图。

令A，B，C是控制者，C是A和B的唯一的父亲。若结点Pi出现在控制者A和B的局部等待图中，那么把Pi插入到下面的等待图中：

控制者C的等待图中；

从C到A的路径中每一个控制者的等待图中；

从C到B的路径中每一个控制者的等待图中

此外，如果进程Pi和Pj出现在控制者D的等待图中，而且在D的孩子之一的等待图中存在从Pi

到Pj的路径，那么边(Pi，Pj)也必须在D的等待图中出现。

如果，这些等待图中任何一个存在环路那么该系统发生死锁需引用死锁解除算法。

例如，考虑图中的系统，该系统的树形结构如下图所示。由于Pi和Pj都在A和B中出现，所以它们也出现在C中。由于在A中存在从P2

到P3的路径，因此，C中包含边(P2，P3)。类似地，因为B中存在从P3

到P2的路径，所以C中也包含边(P3，P2)。注意，C的等待图中存在环路，从而隐含该系统已出现死锁。

7.试对“合一阈值”（merge-threshold）启发式任务分配算法进行详细设计，并对其进行时间和空间复杂性分析

解答过程如下：

假定：系统中的处理机是相同的，且模块的优先级也是一样的。

算法思想：该算法分成两个阶段：合一、调整。先将

IMC（模块间通信）

最大者合并在一起（打算分给同一个处理机），第二阶段看此分配是否超出“阈值”，对超出者进行调整。

算法描述：

设有

n

个模块，h

个处理机：

V={

m1,m2,…,mn

}

P={

P1,P2,…,Ph}

1、令S=

{{

m1},{

m2},…,{

mn

}

}

2、从S中寻找Si，Sj，它们之间存在最大的IMC，如果合并Si、Sj后满足内存和实时要求，则

a)

合并Si、Sj。即用Si∪Sj代替Si，Sj；

b)

对于任取Sk∈S

&

Sk≠Si

&

Sk≠Sj

执行

用Sk与Si和Sj的IMC的和作为Sk与Si∪Sj的IMC；

3、重复

2，直到找不到可以合并的；

4、将

S

中未被合并的模块放入一个“族”

5、如果

S

中现有模块族数≤h，则将它们分配给各个处理机，否则，对本次合一结果进行调整；

6、对于每一个处理机Pi，执行如下操作

a)

如果Pi分得的模块超过阈值，则选一个模块迁移到轻载者；

7、如果对于每一个处理机，都没有超过阈值，则算法结束，否则，算法失败；

8、以一定的策略将多出来的族放入其它族中，使|S|≤h，然后转

6。

下面仅从算法的时空复杂性及算法的输出与最优解的差距等方面来简单地分析该算法。为此，假定有n个模块等待分配给m个同构的处理机。我们可用一个矩阵表示1MC开销，由对称性知，存贮这方面的数据只需n(n-1)/2个单元。用另一矩阵存放当完成了一次成功的合一后，修改相关模块的IMC开销后的信息，这也只需n(n-1)/

2个单元。不难看出，合一过程采用的是一种局部性“贪心”策略,即每次查找一对这样的模块，它们经合一后不仅清除最大的IMC开销，而且相应的处理机应满足应时和（或）存贮要求。若令T(n)为合一过程最坏情况下的时间复杂性，则不难得到下面的递推式：

T(n)

＝

查找具有最大IMC开销模块对的时间

+

修改其它模块对的IMC开销的时间

＋

T(n-1)

显然，T(n)

=

O(n3)。

若经合一处理后剩下的模块数大于m，则认为合一失败（此时，不必进入“调整”阶段）。为此，可假定经合一处理后的模块数小于等于m。“调整”阶段是“合一”阶段的继续。在调整过程中，可用数组Tv[1

..m]存放各处理机的阈值，用Load[1

..m]存放各处理机上的实际负载。在合一过程中，由于一对模块合一后会引起相关模块对的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不大于0，则不做任何迁移工作。

⑷若处理机m的Dm大于0，则报告“失败”，否则调整成功。

由上不难得知，调整过程的时间复杂性约为O(m3)。

8.何谓OS的安全性？对分布式OS而言，必须优先突破的安全技术是哪些。

答：

OS的安全性指信息的保密性，完整性和可用性。安全操作系统，是指计算机信息系统在自主访问控制、强制访问控制、标记、身份鉴别、客体重用、审计、数据完整性、隐蔽信道分析、可信路径、可信恢复等十个方面满足相应的安全技术要求。

网络是分布式系统的基础，分布式系统是网络的高级发展形式。而网络方面的故障（带宽、信息丢失、通信延迟、网络负载趋于饱和、网络分割等等），会抵消通过建立分布式系统所获得的大部分优势。

若允许用户很方便地存取整个系统，则他们同样也就能很方便地存取与其无关的数据，从而导致对保密数据的访问，破坏了安全性。此外。分布式系统在地域、资源、功能方面地分散性，也带来了系统的安全隐患。

所以对于分布式OS应该首先突破隐蔽信道分析、可信路径、可信恢复等安全技术。