高级操作系统作业.docVIP

高级操作系统结课作业 姓名： 专业： 学号： 1.验证Lamport’s Algorithm算法的正确性，即该算法是否能保证 （1）在任何时刻，最多只有一个进程位于临界段（安全性）； （2）若位于临界段的进程在有限时间内退出临界段，则其它请求进入临界段的进程总会进入（可用性）。Lamport算法基本假定如下：A. 进程Pi发送的请求消息形如request(Ti , i)，其中Ti = Ci是进程Pi发送此消息时对应的逻辑时钟值，i代表消息内容。　　 B. 每个进程保持一个请求队列，队列中的请求消息根据关系定序，队列初始为空。　Lamport算法描述当进程Pi请求资源时，它把请求消息request(Ti,i)排在自己的请求队列中，同时也把该消息发送给系统中的其他进程； 当进程Pj接收到外来消息request(Ti,i)后，发送回答消息reply(Tj , j)，并把request(Ti , i)放入自己的请求队列。 Pi才允许进入临界段： A. Pi自身请求访问该资源的消息已处于请求队列的最前面；　B. Pi已收到从所有其他进程发来的回答消息，这些回答消息的时间戳均晚于(Ti, i). ，Pi从自己的队列中撤销请求消息，并发送一个打上时间戳的释放消息release给其他进程；　当进程Pj收到Pi的release消息后，它撤销自己队列中的原Pi的request(Ti , i)消息。 试对“合一-阈值”（merge-threshold）启发式任务分配算法进行详细设计，并对其进行时间和空间复杂性分析。 显然：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)。 何谓OS的安全性？对分布式OS而言，必须优先突破的安全技术是哪些。 计算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. Cd (Mod N)=M 其中 M 是原始明文。用于数字签名的公钥加密使用RSA算法。 在这种方法中，发送者利用私钥通过摘要函数对整个数据文件（代价昂贵），或文件的签名进行加密。私钥匹配的最主要优点就是不存在密钥分发问题。这种方法假定你信任发布公钥的来源。然后接收者可以利用公钥来解密签名或文件，并验证它的来源和/或内容。由于公钥密码学的复杂性因此只有正确的公钥才能够解密信息或摘要。最后，如果你要将消息发送给拥有已知公钥的用户，那么你就可以使用接收者的公钥来加密消息或摘要，这样只有接收者才能够通过他们自己的私钥来验证其中的内容。 每个存储认证信息的数据库都是系统安全漏洞的目标。而且，在每次我们需要作些什么的时候，是否都需要提供口令呢？ 3、重放。有人可以在认证信息在网络中传输的时候对它进行复制，即使这些信息经过了加密，然后在以后进行重放，从而获得不正当的访问。 4信任认证是否应该是单方面的呢？或者用户是否也应该检验和相信使用的服务是合法的？集中系统信任它自己；分布式系统必须寻找一个方法来信任其他系统。 为了解决备受关注的通用方案可以使用一种证书管理系统。证书是一种由计算机生成并在一段时间内有效的经认证的信息包，可以用它在分布式系统中方便的访问各种资源。时间有效特性有助于避免以后的重放攻击。该特性通过时间戳或现时来实现。 设