高级操作系统作业2003版

《高级操作系统作业2003版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高级操作系统作业三、我们讨论了资源管理中的“近者优先”策略，试设计具体实现该策略的算法并进行算法分析。答：“近者优先”策略算法设计过程如下：1、发出搜索消息申请者向其某个邻结点发出一个搜索消息，搜索消息中附上对资源的需求及参数X，X为申请者的结点编号。2、接到搜索消息接到搜索消息后，将搜索消息的结点编号和搜索消息中的参数X登记下来。定义发来搜索消息的结点为它的上邻结点，搜索消息中的参数X所规定的结点为它的前结点。如果接到搜索消息的结点具有所需要的资源，则向它的上邻结点发一成功消息，并附上自己的结点编号，否则它先向其前结点发一消息，告诉自己是它的

2、后结点。然后，发一消息给其上邻结点，请求继续搜索，并附上参数X，X为自己的结点编号。3、失败消息上邻结点接到继续搜索消息后，如果还有尚未搜索的下邻结点，那么就发一搜索消息给下邻结点，附上参数X，X是从继续搜索消息中复制的。如果所有的下邻结点都已经搜索过，但是它有后结点，则将继续搜索消息转发给它的后结点。如果既没有尚未搜索的下邻结点，又没有后结点，则表示与它相连的所有结点都已经搜索过。此时，它向其上邻结点发一失败消息。4、邻结点不存在如果一个已经被搜索过的结点又接到搜索消息，则将搜索消息退回，发搜索消息的结点就认为该下邻结点不存在。5、成功或失败

3、消息接到成功或失败消息后，如果该结点非申请者，则将此消息转发给它的上邻结点，否则搜索结束。申请者或者获得最近的能够提供所需要的资源的结点编号，或者系统中没有所需要的资源。6、强健算法如果发搜索消息到下邻结点后，在某个T时间内没有收到回复消息，则认为该下邻结点已经失效。然后，向另外一个下邻结点发搜索消息，或者向后结点发继续搜索消息。只要在算法执行过程中不产生新的失效结点，并且失效结点不被恢复，增加了上述规则后，由近及远算法是强健的采用“近者优先”算法搜索资源不会产生饥饿。被搜索到的每个结点几乎都接收到这样的三条消息，即搜索消息，通知谁是后结点的消

4、息和由前结点转发来的继续搜索消息。因此，如果不考虑一个结点多次被搜索的情况，或者近考虑树形网络的情况，在最坏情况下需要发4n条消息进行资源搜索工作。此外，还要加上搜索到资源后转发的成功信。因而，看起来由近及远算法比前两种算法通信量大得多。但是，当系统中有较多的结点拥有资源时，采用这种算法往往很快就能获得资源。因此，对于“稀有”资源可能招标算法或回声算法比较合适，而对于普遍拥有的资源，则由近及远算法可能更好些。算法让资源申请者由近及远地搜索，直至遇到具有所需要资源的结点为止。按照由近及远地搜索资源，可使申请者总是在能够提供资源的结点之间，选择一个

5、距离它最近的结点获得资源。采用由近及远算法搜索资源不会产生饥饿，当系统中有较多的结点拥有资源时，采用这种算法往往很快就能获得资源。六、试对“合一阈值”（merge-threshold）启发式任务分配算法进行详细设计，并对其进行时间和空间复杂性分析答：1、假定用户在软件设计阶段将提交给系统的任务已分解成m个模块；系统由同构的n个处理机互连而成，且m>n系统中的处理机是相同的，且模块的优先级也是一样的。2、算法思想分为两个阶段合一和调整合一即将用户提交的任务（一组模块）进行合一处理，过程如下A）查找“具有最大IMC的模块对”，B）将这对模块分配到同

6、一处理机（合一），以消除系统中当前的最大IMC开销，C）检测经“合一”后相应处理机是否满足实时和存储等方面的要求，若满足，则认定此次合一有效。否则，选择下一对“具有最大IMC的模块”，转B），直至完成一次有效的合一，D）继续上述过程，直至所有合适的模块对全部分配完毕，E）将剩余模块分配到同一处理机上。调整在第一阶段的基础上，根据给定的阈值，对各处理机上的负载进行调整，过程如下A）查看各处理机上的模块数是否已超过给定的阈值，B）若均未超过，则本阶段结束，算法终止。否则，C）将那些超过部分迁移到尚未超过其阈值的处理机上。1、算法描述设有n个模块，h

7、个处理机：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）对于每一

8、个处理机Pi，执行如下操作A)如果Pi分得的模块超过阈值，则选一个模块迁移到轻载者；B)如果对于每一个处理机，都没有超过阈值，则算法结束，否则，算法失