高级操作系统 一、分析比较所学的负载平衡策略或算法，指出它们的优缺点，并就 其中之一给出你的改进方法。 答：负载平衡算法可分为动态算法和自适应算法二大类。 ① 动态算法：根据系统状态，对可以接受任务的节点进行分析，如果处理机不空闲， 可以将任务迁移到空闲节点，甚至可以将正在进行的任务迁移到其他空闲节点。但是，信息 的收集、分析及作出决定要造成额外开销，不可小视。 ② 自适应算法：通过动态改变参数甚至策略来调整自身的行为,以适应正在改变的系统 状态,在无法通过任务迁移提高系统性能的情况下,自适应算法是很好的选择。 现有负载平衡算法比较 ① 发送者启动算法：该算法由发送者来触发负载分配。当一个节点机成为一个发送者 时，它主动寻找接收者来接收自己的一部分负载。显然，在系统轻载时，发送者能较容易地 找到接收者，因而该算法比较稳定有效。但在系统重载时，该算法会引起系统的不稳定，因 为此时发送者不仅不容易找到接收者，而且查询的开销还会增加系统的负载。 ② 接收者启动算法：该算法由接收者触发负载的分配，当一个节点机变成一个接收者 时，它便主动寻找发送者，以便从那里接收部分负载。该算法在系统重载的情况下，因多数 节点处于重载，所以不会引起系统的不稳定，它优于发送者启动算法。但接收者找到发送者 时，由于任务可能已经启动，因此，该算法需要对正在运行的进程进行迁移。 ③ 对称启动算法：对称启动算法是前两种算法的结合，因此它具有这两种算法的优缺 点。这种算法要求发送者和接收者均参与负载分配的活动。在系统轻载时，发送者启动算法 有效，而系统重载时，使用接收者启动算法比较合适。 ④ 接收者主动的渗透算法：接受者主动的渗透算法是通过相邻的重叠部分的场点扩散 负载而达到负载平衡的一类方法，负载信息是通过相邻场点进行交换的。这个算法中的参数 需要调整到系统出现最优性能，但找到最佳参数是非常困难的。 ⑤ 预约策略：预约策略的基本思想：一个轻载场点按一定方式查询系统的状态，请求 某个重载场点迁移到一个尚未开始运行的任务给自己。若此时重载场点尚无这样的负载存在， 则轻载场点同它进行一次“预约”，要求一旦有新创建的或到达的负载，就将它迁移给自己， 因为迁移一个正在运行的负载是比较困难的。 ⑥ 投标策略：投标策略的基本思想为：重载场点向系统广播一个“请求迁移出负载” 的请求消息，接收到这一请求消息的场点根据自己的状态决定是否参与投标：若参与，则它 向请求者发一标书（含可以接收的负载量）；该重载场点对接收到的标书进行筛选，选出其 中最少负载的场点并把其希望迁移的负载迁移给它。 ⑦ 广播策略：广播策略的基本思想为：每个场点都将自己当前的负载广播给系统中所 有其他的场点，因此，重载场点可将一定量的负载直接迁移到负载最少的场点，或者轻载场 点可直接从最高负载的场点请求接收一定量的负载给自己。 评价和比较：上述算法的缺点在于，它们不能适应系统状态的变化，而自适应算法则是根据 系统状态的变化，通过修改某些参数甚至策略来适应系统负载的变化。因而，自适应算法更 为有效，能适合各种情况下的负载分配。 

改进算法 ： ① 综述：改进算法主旨是尽量优化系统进行负载平衡时的性能。为此每个节点机只记 录相邻节点机的状态信息，每当节点机状况发生变化时发送消息给相邻节点机。同时去掉了 中立者表及中立者启动过程。改进算法由发送者启动及接收者启动两部分组成。当整个系统 处于重载时，抑制发送者启动过程，启动接收者启动过程，当整个系统处于轻载或适载时， 抑制接收者启动过程，启动发送者启动过程。这时每个节点机只存放两张表，分别为发送者 表和接收者表。当节点机为重载且整个系统处于轻载或适载时，若接收表不空则在接收表中 按照节点机之间的距离与任务通信量计算任务转移需要的代价，然后选择代价最小的作为接 收者，并发送消息给接收者。若此时的接收者仍为轻载,则返回消息，在任务未执行时进行 迁移。若接收者状况已经改变，则删除当前节点机中接收者表中的该节点机，选择通信量次 之的进行上述过程。当整个系统处于重载时，若某个节点机变成接收者，且发送者表不空， 则选择最近提出任务转移请求的节点机并发送消息准备接受任务迁移。若重载节点机的任务 已启动，则不进行迁移，当前节点机改变其发送者表并选择下一个节点机进行查询。选择最 近提出任务转移请求的节点机原因是其任务已迁移的可能性最小，从而减小重复轮巡的开销。 若当前节点机为重载且接收表空，任务只能在本机运行。当整个系统处于重载时，如果某个 节点机变成接收者，且发送者表空，则节点机等待。保证以上算法能够正常进行的条件是当 某一节点机状态改变时必须及时更新相邻节点机的两张表，这样可以避免当整个系统节点机 过多时，更新所有节点机的两张表所花费的资源，同样也能避免状态不同步更新，任务转移 时原接收者已变为重载，需再一次任务迁移或重新选择接收者所需耗费的资源的情况。为避 免任务在节点机之间迁移多次加重系统负担，规定任务转移次数上限，并规定探询次数上限 防止多次查找耗费系统资源。 ② 算法的控制策略：在算法运行过程中，当发送者启动时,若无接收者或探询次数未超 过上限，则在本机执行任务；若转移次数超过上限，则任务在最后一次转移的节点机上运行。 在接收者启动时，若探询次数超过上限或无接收者，则终止该过程,等待其余节点机的负载 变化再启动此算法。同时还应注意在接收者启动过程中，若对应的发送者的任务已经启动， 则不对该任务进行迁移，而应寻找下个发送者。当某节点机因故障而被删除，或有新节点机 加入时，要更新所有相关表中对应状态。 ③ 改进后算法的特点 1)重载的节点机可以将新任务转移到轻载节点机上； 2)可以根据系统状态信息,有选择地探询节点,适应系统状态的变化； 3)考虑任务间通信关系； 4)探询次数和任务转移次数均有上限,以防止系统崩溃，个别节点机故障时不影响其他节点 机的正常运行。 二、在实现 RPC 时，如何使调用者正确的绑定对应的被调用者，试 给出你的解决方案。 答：⑴当系统生成与调用者对应的 stub 时，可把该远程站点的地址也一同并入其中，不过 这种做法不太灵活。 ⑵在进行调用之前，与调用者对应的 stub 向系统中的其它场点进行广播，请求有关的 场点通报其地址，这必然引起一系列的消息转移。特别，当这种广播是在若干网络之间进行 

时，其转移速度是很慢的。 ⑶由系统管理一个表，其表项的内容为：① 站点地址；② 该场点上将运行的远程过程 的名字。“愿意”产生一个可供其它场点引用的过程的那些场点就造一个表项到这个表中， 该表项给出了这些场点的地址和此远程过程的名字。希望引用远程过程的用户可通过查询此 表获取有关信息。 开发过程大致如下: 1、调用者调用本地 stub 中的一个过程(开始远程过程调用请求). 2、这个 stub 过程把有关的参数组装成一个消息包或一组消息包, 形成一条消息. 运行此执 行过程的远程场点的 IP 地址和执行该过程的进程 ID 号也包含在这条消息中. 3、将这条消息发送给对应的 RPC runtime(RPC 运行库)子程序, 由这个子程序将消息发送到远 程场点. 4、在接收到这条消息时, server 端的 RPC runtime 子程序引用与被调用者对应的 stub 中的一 个子程序, 并让它来处理消息. 5、与被调用者对应的 stub 中的这个子程序撤卸消息, 解析出相关参数, 并用本地调用方式 执行所指定的过程. 6、返回调用结果, 调用者对应的 stub 子程序执行 return 语句返回到用户, 整个 RPC 过程结 束. 三、分布式 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 算法。在这种方法中，发 送者利用私钥通过摘要函数对整个数据文件（代价昂贵），或文件的签名进行加密。私钥匹 配的最主要优点就是不存在密钥分发问题。这种方法假定你信任发布公钥的来源。然后接收 者可以利用公钥来解密签名或文件，并验证它的来源和内容。由于公钥密码学的复杂性因此 

只有正确的公钥才能够解密信息或摘要。最后，如果你要将消息发送给拥有已知公钥的用户， 那么你就可以使用接收者的公钥来加密消息或摘要，这样只有接收者才能够通过他们自己的 私钥来验证其中的内容。 认证技术。分布式系统中的认证第一步就是鉴别或验证一个用户的身份，通常方法是使 用口令、钥匙，或者通过用户本身所具有的的某些特征进行验证如：指纹或者视网膜，这也 是目前最安全可靠同时成本最高的方式。这些方法都可以应用在集中式系统中，在分布式系 统中还必须考虑一下几点： 1、偷听。我们如何阻止别人在通信线路上进行偷听？ 2、多口令管理。如果我们正在访问多个系统，每个系统是否都保留了用户ＩＤ和口令 的副本？每个存储认证信息的数据库都是系统安全漏洞的目标。而且，在每次我们需要作些 什么的时候，是否都需要提供口令呢？ 3、重放。有人可以在认证信息在网络中传输的时候对它进行复制，即使这些信息经过 了加密，然后在以后进行重放，从而获得不正当的访问。 4、信任。认证是否应该是单方面的呢？或者用户是否也应该检验和相信使用的服务是 合法的？集中系统信任它自己；分布式系统必须寻找一个方法来信任其他系统。 为了解决备受关注的通用方案可以使用一种证书管理系统。证书是一种由计算机生成并 在一段时间内有效的经认证的信息包，可以用它在分布式系统中方便的访问各种资源。时间 有效特性有助于避免以后的重放攻击。该特性通过时间戳或现时来实现。 四、你认为本课程的内容和云计算、大数据有何关联，如何理解这样 一些关联？ 答：云计算和大数据其底层架构依然是分布式系统，云计算和大数据是分布式操作系统发展 的趋势和结果，同时也促进着分布式系统的进一步发展，其紧密联系，互相促进。 大数据必然无法用单台的计算机进行处理，必须采用分布式架构。它的特色在于对海量数据 进行分布式数据挖掘。但它必须依托云计算的分布式处理、分布式数据库和云存储、虚拟化 技术。  云计算是分布式计算、并行计算和网络计算的发展，或者说是这些计算机科学概念的商 业实现。其基本原理是通过使计算分布在大量计算的分布式处理器上，而非本地计算机 和远程服务器上。 分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的 问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算 结果综合起来得到最终的结果。  大数据是一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具 能力范围的数据集合，具有海量的数据规模、快速的数据流转、多样的数据类型和价值 密度低四大特征。如此巨大的数据量无法用单台的计算机，则必须使用分布式的架构。 所以分布式架构是大数据的基础，必不可少。