enter cs; dequeue(qi,request(ti,i));send release(ti,i) to pj,(j≠i); end process pj: begin: recieve request(ti,i) enqueue(**,request(ti,i));send reply(tj,j) to pi; waiting; recieve release(ti,i); dequeue(**,request(ti,i));end 7.
6. 试对“合一-阈值”（merge-threshold）启发式任务分配算法进行详细设计，并对其进行时间和空间复杂性分析。
答：任务分配策略的核心就是设法减少系统中各处理机间的通信开销（ipc）和运行模块所需要的开销（imc） 。所谓“合一”是根据一定条件，将两个模块分配到同一处理机，这里的“阈值”是指处理机能接收的最大模块数。
合一-阈值”算法思想：分为两个阶段：
第一个阶段为“合一”阶段：即对用户提交的一组模块进行合一处理。具体过程是：
先查找其中这样一对模块，即把它们合一后将消除最大的 imc 开销，然后检查经这种合一处理后， 相应的处理机是否满足实时或存储方面的要求，若满足，则认为此次合一成功，否则，选择下一对具有最大 imc 开销的模块，重复前面的过程。 直至完成一次成功的合一， 再将合一后的模块对用模块族的形式表示， 以准备参加下一轮迭代， 继续这个过程直到所有合适的模块对全部分配完毕或剩下的模块不能按此方式分配为止，最后将剩下的模块分配到同一处理机上。
第二阶段为“调整”阶段。它在第一阶段基础上，根据各个处理机上规定的阈值， 对各处理机上的实际负载做必要的调整，即查看各处理机上的模块数是否超越预定的阈值，若未超过，则该算法终止，若有超过，则将那些超过阈值的处理机上的模块迁移到尚未超过阈值的处理机上。
算法描述 ： 假设有 ｍ 个模块 ， n 个处理机 ： v= ，p=。
1、令 s=，，
2、从 s 中寻找 si，sj,他们之间存在最大的 imc,如果合并 si,sj 之后满足内存和实时要求，则合并，用 si∪sj 代替 si,sj;对于任意 sk(k≠i 且 k≠j)执行用 sk 与 si 和 sj 的 imc 的和作为 sk 与 si∪sj 的 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。
“调整”阶段是“合一”阶段的继续。在调整过程中，可用数组 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)。
10.设计和实现分布式 os 的主要问题或困难是什么 ?如何解决它们试谈谈你的思路。
答：分布式操作系统在多机环境下，并行性不再只是宏观上的概念，在微观上也得到了体现，系统中个处理机不仅要执行自身接收的任务，还可能相互联系、请求服务或封锁， 而所有这些都要通过通信机制进行，这种通信机制专门负责系统中各进程及处理机之间的相互通信。因此在设计和实现分布式 os 时主要考虑一下问题：
1、分布式操作系统是为分布式多机系统设计的，因此，它不仅对于在各场。
点上分别执行的任务及相关的资源有管理和控制的职责， 而且还要负责协调各场点间的交互关系， 它不仅要保证在不同场点上执行的进程彼此互不干扰并严格同步，而且还必须避免或妥善解决因各处理机对某些资源的竞争而可能引起的死锁、饥饿及公平性问题。 2、分布式操作系统的基本调度单位不再是单机操作系统的进程，而是一种任务队列。 而这种队列是位于多个场点上的并发进程所组成的任务队列，并且同一任务队列中的并发进程可能分布在不同处理机上， 同一场点上也可执行多个不同任务队列中的并发进程。
所以在设计分布式系统时任务调度、处理机分配成为急需考虑的一大难题。 3、分布式操作系统由于地域和数据的分散性，所以在运行过程中怎样保持数据的安全性与完整性成为设计分布式操作系统时必须慎重考虑的问题。 用什么样的机制去保证系统的安全性以避免数据遭在共享和通信过程中被拦截、中断、 篡改、伪造。
4、分布式操作系统必须要具有探测任意处理机停机或发生故障的能力，并且包含适当的措施，如自动重构、降级使用、错误恢复等一系列保证在某一处理机发生故障时整个系统依然可以正常运行。 对于分布式操作系统中的通信与同步，大多都是在处理机发送、接收、回复等传达消息机制中建立连接以达到通信传输的目的， 但是由于分布式操作系统中各处理机的物理位置比较分散， 甚至物理距离相隔很远，所以目前在分布式操作系统中远程过程调用（rpc） ，将调用的过程运行在一个与调用者所在场点不同的场点上。至于分布式的协同处理，不要是引入时间戳，主要是优化分布式的互斥算法， 目前集中式算法、 lamport 算法， 以及相对于 lamport 的改进算法 ricart算法，令牌传递算法等都是目前比较理想的互斥算法。
对于分布式的安全性问题， 我认为在设计系统时应该根据应用的需求恰当的设计。 比如在设计设计国家高度信息的系统时，当然应该不计成本的采用高度安全的用户识别身份验证技术（如：声纹识别、视网膜虹膜识别、静脉识别、ｄｎ识别等高级生物识别技术） ，当然加密算法也应该是独特高度机密的技术。
在数据传输过程中当然也应该要有特殊的网络， 反正普通用户或者恶意分子进行破坏。 但是如果是一个应用于普通的企业级的分布式操作系统，以上那么高级身份验证技术相对而言就是大材小用了，而且考虑成本很高，所以只需要考虑使用普通的口令、指纹识别等就可以达到安全要求。 至于容错与恢复技术。
解决方法无非就是硬件冗余和软件恢复，也可以从文件系统设计的角度来加强容错和恢复技术，如 google 的 gfs，用廉价的物理硬件设备布置高性能可靠的文件系统，同时实现监控、错误检测、自动恢复等。硬件冗余如服务器镜像， 即使用两个以上的完全相同的服务器，其中一个出现故障后， 可以用另一个来提供对用户的服务，软件恢复则是根据备份和备份后的操作日志将数据恢复到故障前的状态，数据库的故障恢复系统就是一个典型的例子。
2019高级OS试题
武汉大学。2007年攻读博士学位研究生入学考试试题。注意 所有的答题内容必须答在答题纸上。科目 740科目名称 高级操作系统。1.分布式os与单机os的主要区别是什么？与网络os有和异同？你认为设计分布式os的主要困难是什么？如何解决它们，试述你的思路。15分 2.分布式操作系统面临的安全性威胁是什...
OS平时作业
一 单项选择题部分 共10题，每题5分，共50分。1.死锁的预防是通过破坏产生死锁的四个必要条件来实现的。下列方法中，破坏了 循环等待 条件。a银行家算法 b一次性分配策略 c资源有序分配策略 d spooling技术。你的答案是 c正确答案是 c 2.从下面预防死锁的论述中，选出一条正确的论述。a...
第二章作业 OS
第二章作业。一 教材p81 83 二 有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号 姓名，读者离开时要注销登记信息 假若阅览室共有100个座位。试用信号量和pv操作来实现用户进程的同步算法。三 吸烟者问题。三个吸烟者在一个房间内，还有一个香烟 者。为了制造并抽...