2022年武汉大学高级操作系统试题 .pdf

高级操作系统试题1、验证 Lamport s Algorithm算法的正确性，即该算法是否能保证（1）在任何时刻，最多只有一个进程位于临界段（安全性）；（2）若位于临界段的进程在有限时间内退出临界段，则其他请求进入临界段的进程总能进入（可用性）；Lamport 算法利用前述的事件定序方案统一定序所有对临界段的请求，按先来先服务的原则让请求临界资源的进程进入其临界段，进/出临界段1 次需要 3 （n-1） 条消息。 Lamport算法基本假定如下：（1）进程 Pi 发送的请求消息形如request(Ti , i)，其中 Ti = Ci是进程 Pi发送此消息时对应的逻辑时钟值，i 代表消息内容。（2）每个进程保持一个请求队列，队列中的请求消息根据=关系定序，队列初始为空。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). （4）、当退出临界段时，进程Pi从自己的队列中撤销请求消息，并发送一个打上时间戳的释放消息release 给其他进程；（5）、当进程Pj收到 Pi的 release 消息后，它撤销自己队列中的原Pi的 request(Ti , i)消息。不难证明该算法是正确的，因为：由(3)-B 及消息是按其发送的次序接收的假定，就保证了进程Pi已经知道先于它的当前请求的所有请求。由于用关系 =定序了所有的请求消息，因此在任何情况下，(3)-A 允许一个且只一个进程进入临界段。当 Pi 退出临界段释放临界资源后，根据其他请求消息的时序关系，总可以找到一个Ps，使它满足 （3）的两个条件，从而进入进入临界段。下面是实现该算法的伪代码：Process Pi: Begin: Send request(Ti,i) to Pj,(j i); enqueue(Qi,request(Ti,i); for(j=1;j=n;j+) Recieve reply(Tj,j); If(queuehead(Qi)=request(Ti,i) & Titj) p= Enter CS; dequeue(Qi,request(Ti,i); Send release(Ti,i) to Pj,(j i); End Process Pj: Begin: Recieve request(Ti,i) enqueue(Qj,request(Ti,i); Send reply(Tj,j) to Pi; Waiting; Recieve release(Ti,i); dequeue(Qj,request(Ti,i); End 2、请求驱动式令牌传递方法中，若Pi 发出 request消息后久未获得token，该怎么处理？若引入时戳，该算法应做何修改？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 在请求驱动式令牌传递方法中，或 pi发出的request消息后久未获得Token ，应该决定是站点故障还是Token 丢失，需要有对应逻辑环重构方法和Token 生成方法。可以引入时时戳增加算法的强健性，具体如下: (1) 当 request消息后久未获得令牌，则向其它进程发询问消息；若其它进程无反对消息到达，则重新生成令牌，否则继续等待。(2) 若接收到询问消息的进程是令牌的持有者，或已发出一样Request消息，且自已Request消息的时戳先于询问进程Request 消息的时戳，则立即发回一条反对消息。(3) 令牌持有者传递令牌时，若发现接收者故障，需要调用逻辑环重构算法进行环重构，再重新选择接收者。3、在分布式死锁处理过程中，何时或在什么情况下构造局部或全局进程等待（PWG ）图才能反映系统的实际情况？在构造局部进程等待图时为什么不同站点提出资源申请时需要加上时戳？第一问：（1）每当从局部等待图中去掉一条边或向局部等待图插入一条新边时（2）周期性的，当等待图中已经发生了若干改变时（3）每当协调者需要引用环路检测算法时第二问：不同的站点的请求消息附上唯一的标识（时戳），可以避免报告假死锁。解决接收消息的顺序与发送消息的顺序不一致问题。时间戳及全排序保证了不会死锁。增加时间戳， 防止回应的不及时（令牌丢失、令牌者故障）。利用时间戳来标明申请资源的先后次序，以此来尽量消除对共享资源的竞争。4、详细设计“合一阈值”（merge-threshold ）启发式任务分配算法，并对其进行算法复杂性分析。任务分配策略的核心就是设法减少系统中各处理机间的通信开销（IPC ）和 运行模块所需要的开销（ IMC） 。所谓“合一”是根据一定条件，将两个模块分配到同一处理机，这里的“阈值”是指处理机能接收的最大模块数。“合一阈值”算法思想：分为两个阶段：第一个阶段为“合一”阶段：即对用户提交的一组模块进行合一处理。具体过程是：先查找其中这样一对模块，即把它们合一后将消除最大的IMC 开销，然后检查经这种合一处理后，相应的处理机是否满足实时或存储方面的要求，若满足，则认为此次合一成功，否则，选择下一对具有最大IMC 开销的模块，重复前面的过程。直至完成一次成功的合一，再将合一后的模块对用模块族的形式表示，以准备参加下一轮迭代，继续这个过程直到所有合适的模块对全部分配完毕或剩下的模块不能按此方式分配为止，最后将剩下的模块分配到同一处理机上。第二阶段为“调整”阶段。它在第一阶段基础上，根据各个处理机上规定的阈值，对各处理机上的实际负载做必要的调整，即查看各处理机上的模块数是否超越预定的阈值，若未超过，则该算法终止，若有超过，则将那些超过阈值的处理机上的模块迁移到尚未超过阈值的处理机上。假定：系统中的处理机是相同的，且模块的优先级也是一样的。算法描述：假设有个模块，n 个处理机： V=V1,V2,V3,.Vm ，P=P1,P2,P3,.Pn 。1、令 S=V1 ，V2，.Vm。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 2、 从 S中寻找 Si，Sj,他们之间存在最大的IMC,如果合并Si,Sj之后满足内存和实时要求，则合并，用SiSj代替 Si,Sj; 对于任意Sk(ki 且 kj) 执行用 Sk 与 Si和 Sj的 IMC 的和作为Sk与 SiSj的 IMC。3、 重复2，直到找不到可以合并的。4、 将 S 中未被合并的模块放入一个“ 族” 。5、 如果S 中现有模块族数h，则将它们分配给各个处理机，否则，对本次合一结果进行调整。6、 对于每一个处理机Pi，执行如下操作a) 如果 Pi分得的模块超过阈值，则选一个模块迁移到轻载者。7、 如果对于每一个处理机，都没有超过阈值，则算法结束，否则，算法失败。8、 以一定的策略将多出来的族放入其它族中，使|S| n，然后转6。下面从时空复杂性来分析该算法：假定有 n 个模块等待分配给m 个同构的处理机，我们可用一个矩阵表示IMC 开销，所以存储这些数据需要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。“ 调整 ” 阶段是 “ 合一 ” 阶段的继续。在调整过程中， 可用数组Tv1 ,. m存放各处理机的阈值，用 Load1 . m存放各处理机上的实际负载。在合一过程中，由于一对模块合一后会引起相关模块对的IMC 发生变更，因此，在执行调整过程中， 很难知道分离出哪个模块（或模块族）会使得处理开销最小，故此时采用随机策略。在此，不妨把调整过程进一步描述为：计算各处理机的实际负载与其阈值之差Di，i 1, 2, .,m ； 按 Di 的不增次序排序各处理机，并用j（j 1, 2, .,m ）指称经排序后位于序号j 处的处理机；对于 j 1, 2, ., m-1 执行下面的操作：若处理机j 的 Dj大于 0，则用随机方法从处理机j 上选定一模块（或模块族）并把它迁移到处理机j1 上。重复此过程，直至处理机j 的 Dj 不大于 0。必要时，可对模块族进行分裂。若处理机j 的Dj 不大于 0，则不做任何迁移工作。若处理机m 的 Dm 大于 0，则报告 “ 失败 ” ，否则调整成功。由上不难得知，调整过程的时间复杂性约为O(m3)。5、在实现 RPC时，如何使调用者正确绑定对应的被调用者？试给出你的解决方法？当系统生成与调用者对应的stub 时，可把该远程站点的地址也一同并入其中，不过这种做法不太灵活。在进行调用之前，与调用者对应的stub 向系统中的其它场点进行广播，请求有关的场点通报其地址，这必然引起一系列的消息转移。特别，当这种广播是在若干网络之间进行时，其转移速度是很慢的。由系统管理一个表，其表项的内容为： 站点地址； 该场点上将运行的远程过程的名字。“愿意” 产生一个可供其它场点引用的过程的那些场点就造一个表项到这个表中，该表项给出了这些场点的地址和此远程过程的名字。希望引用远程过程的用户可通过查询此表获取有关信息。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 开发过程大致是这样的: 1、调用者调用本地stub 中的一个过程(开始远程过程调用请求). 2、这个stub 过程把有关的参数组装成一个消息包或一组消息包, 形成一条消息. 运行此执行过程的远程场点的IP地址和执行该过程的进程ID 号也包含在这条消息中. 3、 将这条消息发送给对应的RPC runtime(RPC运行库 )子程序 , 由这个子程序将消息发送到远程场点 . 4、在接收到这条消息时, server 端的 RPC runtime 子程序引用与被调用者对应的stub 中的一个子程序 , 并让它来处理消息. 5、与被调用者对应的stub 中的这个子程序撤卸消息, 解析出相关参数, 并用本地调用方式执行所指定的过程. 6、返回调用结果, 调用者对应的stub 子程序执行return 语句返回到用户, 整个 RPC过程结束. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -