高级操作系统作业

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

1、高级操作系统结课作业姓名：专业：学号：1.验证Lamport’sAlgorithm算法的正确性，即该算法是否能保证(1)在任何时刻，最多只有一个进程位于临界段(安全性)；(2)若位于临界段的进程在有限时间内退出临界段，则其它请求进入临界段的进程总会进入(可用性)。答：Lamport算法利用前述的事件定序方案统一定序所有对临界段的请求，按先来先服务的原则让请求临界资源的进程进入其临界段，进/出临界段1次需要3X(n-1)条消息。Lamport算法基本假定如下：A.进程Pi发送的请求消息形如request(Ti,i)，其中Ti=Ci是进程Pi发送此消息吋对应的逻辑时钟值，i代表消

2、息内容。B.每个进程保持一个请求队列，队列屮的请求消息根据==〉关系定序，队列初始为空。Lamport算法描述(1)、当进程Pi请求资源时，它把请求消息request(Ti,i)排在自己的请求队列中，冏时也把该消息发送给系统中的其他进程；(2)、当进程Pj接收到外來消息request(Ti，i)后，发送回答消息reply(Tj,j),并把request(Ti，i)放入自己的请求队列。(3)、当下面两个条件都成立时，Pi才允许进入临界段：A.Pi自身请求访问该资源的消息已处于请求队列的最前面；B.Pi己收到从所有其他进程发来的冋答消息，这些冋答消息的吋间戳均晚于(Ti,i).(

3、4)、当退出临界段时，进程Pi从自己的队列中撤销请求消息，并发送一个打上时间戳的释放消息release给其他进程；(5)、当进程Pj收到Pi的release消息后，它撤销自己队列中的原Pirequest(Ti,i)消息<>不难证明该算法是正确的，因为：由(3)-B及消息是按其发送的次序接收的假定，就保证了进程Pi己经知道先于它的当前请求的所有请求。由于用关系二〉定序了所有的请求消息，因此在任何情况下，(3)-A允许一个II只一个进程进入临界段。当Pi退出临界段释放临界资源后，根据其他请求消息的时序关系，总可以找到一个Ps,使它满足(3)的两个条件，从而进入进入临界段。下面是实

4、现该算法的伪代码：ProcessPi:Begin:Sendrequest(Ti，i)toPj,(j^i);enqueue(Qi,request(Ti，i));for(j=l;j<=n;j++)Recievereply(Tjj);If(queuehead(Qi)==request(Ti，i)&&Ti

5、j）toPi;Waiting;Recieverelease（Ti，i）;dequeue（Qj，request（Ti，i））;End7.试对“合一•阈值”（merge-threshold）启发式任务分配算法进行详细设计，并对其进行时间和空间复杂性分析。答：任务分配策略的核心就是设法减少系统中各处理机间的通信开销（1PC）和运行模块所需要的开销（IMC）。所谓“合一”是根据一定条件，将两个模块分配到同一处理机，这里的“阈值”是指处理机能接收的最大模块数。“合一-阈值”算法思想：分为两个阶段：第一个阶段为“合一”阶段：即对用户提交的一组模块进行合一处理。具体过程是：先查找其中这样一

6、对模块，即把它们合一后将消除最大的1MC开销，然后检查经这种合一处理后，相应的处理机是否满足实时或存储方面的要求，若满足，则认为此次合一成功，否则，选择下一对具有最大IMC开销的模块，重复前面的过程。直至完成一次成功的合一，再将合一后的模块对用模块族的形式表示，以准备参加下一轮迭代，继续这个过程直到所有合适的模块对全部分配完毕或剩下的模块不能按此方式分配为止，最后将剩下的模块分配到同一处理机上。第二阶段为“调整”阶段。它在第一阶段基础上，根据各个处理机上规定的阈值，对各处理机上的实际负载做必要的调整，即查看各处理机上的模块数是否超越预定的阈值，若未超过，则该算法终止，若冇超过

7、，则将那些超过阈值的处理机上的模块迁移到尚未超过阈值的处理机上。算法描述：假设有m个模块，n个处理机：V={V1，V2，V3，...Vm},P={P1,P2,P3,...Pn}o1、令S={{V1}，{V2},...{Vm}}o2、从S中寻找Si,Sj,他们之间存在最大的IMC,如果合并Si，Sj之后满足内存和实时要求，则合并，用SiUSj代替Si,Sj;对于任意Sk（k#i且k类j）执行用Sk与Si和Sj的IMC的和作为Sk与SiUSj的IMC。3、重复2,直到找不到可以合并的。4、将S中未被合并的模