高级操作系统结课作业。
姓名：专业：
学号：1.验证lamport’s algorithm算法的正确性，即该算法是否能保证。
（1）在任何时刻，最多只有一个进程位于临界段（安全性）；
（2）若位于临界段的进程在有限时间内退出临界段，则其它请求进入临界段的进程总会进入（可用性）。
答：lamport算法利用前述的事件定序方案统一定序所有对临界段的请求，按先来先服务的原则让请求临界资源的进程进入其临界段，进/出临界段1次需要3×（n-1）条消息。lamport算法基本假定如下：
a. 进程pi发送的请求消息形如request(ti , i)，其中ti = ci是进程pi发送此消息时对应的逻辑时钟值，i代表消息内容。
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).
（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) &ti enter cs;
dequeue(qi,request(ti,i));
send release(ti,i) to pj,(j≠i);
endprocess 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));
end7.试对“合一-阈值”（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)。
9、何谓os的安全性？对分布式os而言，必须优先突破的安全技术是哪些。
答：os的安全性可以包括狭义安全概念即对外部攻击的防范，广义安全的概念主要是保障系统中数据的保密性、完整性和可用性。当前主要使用广义安全概念，主要内容包括：
物理安全（系统设备及相关设施受到物理保护，使之免遭破坏和丢失）、逻辑安全（指系统中信息资源的安全）和安全管理（各种安全管理政策和机制）三个方面的内容。安全操作系统（也称可信操作系统）是指计算机信息系统在自主访问控制、强制访问控制、标记、身份鉴别、客体重用、审计、数据完整性、隐蔽信道分析、可信路径、可信恢复等十个方面满足相应的安全技术要求。
对于分布式os而言，由于地域和数据的分散性，于是保证数据的机密性和完整性，避免在数据共享和通信过程中被拦截、中断、篡改、伪造，成为其主要的安全性问题。必须优先突破的安全技术主要有以下：加密技术、认证与访问控制技术。
此外，网路是分布式系统的基础，分布式系统是网络的高级发展形式，而网络发面的故障（带宽、信息丢失、通信延迟、网络负载趋于饱和、网络分割等），会抵消通过建立分布式系统所获得的的大部分优势。必须要突破的关键技术是隐藏信道分析、可信路径、可信恢复等安全技术。
数据加密和数字签名。加密算法按照其对称性，可把加密和解密分为对称加密算法（加密和解密算法都使用相同密钥）和非对称加密算法（两个密钥，一个公钥一个私钥）。现在最常用的公钥加密方法是rsa。
使用rsa有三个阶段。阶段一：确定公钥和私钥。每个用户必须完成下面6个步骤：1、选择两个大素数p和q，2、计算n=p*q，3、计算f(n) =p - 1)(q - 1).
4、选择 e，其中 1 <=e <=n-1 且 gcd (e, f(n)) 1.
5、计算d，其中 ed = 1 (mod f(n)) 使用扩展的欧几里德算法)
6、公开 d 和 n ； 这些值组成公钥。
阶段二：加密消息。为了使用rsa加密消息m (其中1 <=m <=n – 1)，必须进行下列下列计算。c=me (mod n) 其中 c 是密文。发送 c.
阶段三：解密密文。为了使用rsa解密密文c，必须进行下列计算。cd (mod n)=m 其中 m 是原始明文。
使用公钥加密的数字签名。用于数字签名的公钥加密使用rsa算法。 在这种方法中，发送者利用私钥通过摘要函数对整个数据文件（代价昂贵），或文件的签名进行加密。
私钥匹配的最主要优点就是不存在密钥分发问题。这种方法假定你信任发布公钥的**。然后接收者可以利用公钥来解密签名或文件，并验证它的**和/或内容。
由于公钥密码学的复杂性因此只有正确的公钥才能够解密信息或摘要。最后，如果你要将消息发送给拥有已知公钥的用户，那么你就可以使用接收者的公钥来加密消息或摘要，这样只有接收者才能够通过他们自己的私钥来验证其中的内容。
高级操作系统
分布式系统概念 一个分布式系统是若干个独立的计算机的集合，但是对该系统的用户来说，感觉该系统就像一台计算机一样。分布式操作系统 是对分布式系统提供资源管理的软件系统。通常表现为中间件形式。一 分布式系统的关键目标。分布式系统的4个关键目标 1 必须是资源共享的。要让用户方便地访问资源，并且以一种受控...
高级操作系统
目录。1.分布式操作系统透明性的含义是什么？课本8.5分布式系统的透明性 2 2.简述一种分布式操作系统的时钟同步算法 2 3.为什么需要动态负载平衡？影响其效率的3个主要因素是什么？3 4.论述windows操作系统的安全性 3 4.1 windows操作系统的安全性讨论 3 4.1.1 wind...
高级操作系统
一 解释。1 解释分布式系统概念。一个分布式系统是一些独立的计算机的集合，但是对该系统的用户来说，系统就像一台计算机一样，即 由大量cpu组成的计算机系统。这个定义有两方面的含义 第一，从硬件角度看，每台计算机都是自主的 第二，从软件角度看，用户将整个系统视为一台计算机。2 微内核的主要任务。微内核...