英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料
负载均衡算法的性能分析
作者：Sandeep Sharma, Sarabjit Singh, and Meenakshi Sharma
摘要—负载均衡是一种通过在处理器之间重新分配负载来提高并行分布式系统性能的一种方法【1】【5】。本文考虑静态和动态两种典型的负载均衡方法，对基于不同参数的负载均衡算法进行了性能分析。分析表明，静态和动态两种算法都有各自的优缺点。采用何种算法取决于待实施的并行应用程序类型。本文的主要目的是通过研究各种已知算法的实际表现来为未来设计出新的算法做出贡献。
关键词—负载均衡（LB），工作量，分布式系统，静态负载均衡，动态负载均衡
1．简介
在并行分布式系统中有多个处理器在处理着并行程序。处理器执行分配给它的全部进程所需要的时间被称作处理器的工作量。一个拥有几百台以高速网络连接起来的计算机的分布式计算机系统【2】【3】，相比于拥有同等数量独立计算机的系统，有着巨大的优势。分布式系统将资源共享作为其主要优势之一，这使得在相同的条件下，其性能和可靠性优于其他任何传统系统。并行分布式系统的研究问题之一是开发有效的技术来将工作负载分布到多个处理器上。其主要目标是在处理器之间分配作业，以此来最大限度地提高吞吐量、保持稳定性和资源利用率，并有一定的容错率。操作系统的本地调度就是将进程分配到处理器的时间片上。另一方面，全局调度是在多处理器系统中决定在何处执行进程的过程。全局调度可以由单个中心（主）处理单元执行，也可以分布在多个处理单元之间。全局调度又分为静态调度和动态调度两大类。在静态调度中，进程在执行之前被分配给处理器。在静态调度中，进程在执行之前就被分配给处理器。另一方面，动态调度可以在执行过程中将处理器的进程进行重新分配。负载共享和负载均衡是动态调度的进一步分类。负载共享致力于避免处理器中的非共享状态（当其他处理器上的任务竞争服务时，这些处理器仍然是空闲的）。负载均衡也是做同样的事情，但是它比负载共享更进一步——它尝试在所有处理器上均衡负载。进行负载平衡是为了确保系统中的每个处理器在任何时间点都有大致相同的工作量。为了确保工作量相等，进程甚至会在执行过程中从一个节点迁移到另一个节点。负载平衡的算法必须依赖于这样的假设，即每个节点上的现有信息是准确的，以防止进程在没有任何进展的情况下在系统中不断循环迁移。负载均衡是充分利用并行分布式系统所有资源的先决条件之一。负载平衡可以集中在单个处理器中，也可以分布在参与负载平衡过程的所有处理单元中。
若干任务会根据每个CPU上当前的负载，被分配给不同的处理器。多年来，人们为了找到开销尽可能低的负载均衡算法，已经进行了很多研究。
2．论文结构
本文对六种负载均衡算法进行了研究，利用各种参数对结果进行了检验。本文首先给出简介，然后在第3部分简单介绍静态负载均衡算法，第4部分介绍动态负载均衡算法，在第5部分我们给出了用来分析算法的参数，最后在第6部分我们利用表格1对检验结果进行研究，并在第7部分给出最终的结论。
3．静态负载均衡
在这种方法中，处理器的性能在开始运行时就确定了【3】【6】。然后主处理器根据他们的性能在开始时分配工作量，从处理器处理它们分配的工作并将结果提交给主处理器。任务总是在分配给它的处理器上执行，即静态负载平衡方法是非抢占式的。静态负载均衡方法的目标是在减少通信延迟的同时减少并发程序的总体执行时间。所有静态模式都有一个普遍的缺陷，那就是进程最终被分配到的主机是在进程创建时决定的，不能通过在进程执行时更改处理器来改变系统负载。
- 循环和随机算法
在循环算法中，进程被平均分配到所有处理器中。每个新建的进程都会按照循环顺序被分配到新的处理器中。每个处理器本地都会保存进程分配的顺序，与远程处理器的分配无关。在进程工作量都相等的情况下，循环算法能很好地工作。在进程数远大于处理器数的情况下，循环和随机算法都有良好表现。
循环和随机算法的优点是不需要进程间通信。在所有负载均衡算法中，循环算法和随机算法都能在特定的特殊应用中展现出最佳的性能。一般情况下，这两种算法并不能取得普遍良好的性能。
- 中央管理器算法
在该算法中，中央处理器为新进程选择主机。在创建进程时，会根据总体负载选择最小负载的处理器。负载管理器为新进程选择主机，以便确保处理器的负载处于尽可能相同的级别上。中央负载管理器会根据现有的系统负载状态信息，进行负载均衡判断。此信息由远程处理器更新，每当其上的负载发生变化时，远程处理器就发送一条消息。
负载管理器根据系统负载信息做出负载平衡决策，并允许在创建进程时做出最佳决策。但频繁的进程间通信会产生瓶颈。该算法比并行应用程序的性能更好，特别是在不同的主机创建动态活动时。
- 临界算法
在该算法中，进程在创建时便立即分配给主机。新进程所依赖的主机直接在本地进行选择，而不发送远程信息。每个处理器都保存系统负载的私有副本。处理器的负载状态可以用三个负载级别中的一个来表示：负载不足、中等负载和过载。我们可以用两个阈值参数（tunder、tupper）来描述这些负载等级：
负载不足 ： 负载lt; tunder
中等负载 ： tunder le; 负载 le; tupper
过载 ： 负载 gt; tupper
最初，所有的处理器都被认为是负载不足的。当处理器的负载状态超过负载级别阈值时，它就会将关于新的负载状态的消息发送给所有远程处理器，定期将它们所保存的系统负载状态副本更新为整个系统的实际负载状态。
如果本地负载状态没有过载，则在本地分配进程。否则，将选择一个远程的负载不足处理器，如果不存在这样的主机，那么还将在本地分配该进程。临界算法具有较低的进程间通信和大量的本地进程分配，后者减少了远程进程分配的开销和远程内存访问的开销，从而提高了性能。该算法的一个缺点是：当所有远程处理器都过载时，所有进程都在本地分配，那么就可能导致一个过载处理器上的负载可能比其他过载处理器上的负载高得多，从而在负载平衡方面造成严重干扰，并增加应用程序的执行时间。
4．动态负载平衡
它与静态算法的不同之处在于，工作负载会在进程执行时在处理器之间进行分配。主处理器根据收集到的最新信息将新进程分配给从处理器。与静态算法不同，动态算法在一个处理器负载不足时动态地为其分配进程，进程都在中心主机上的缓冲队列中，并根据来自远程主机的请求动态分配。
- 中心队列算法
中心队列算法的工作原理是动态分布。它将新活动和未完成的请求作为一个循环FIFO队列存储在中心主机上。到达队列管理器的每个新活动都被插入到队列中。然后，每当队列管理器接收到对某个活动的请求时，它就从队列中删除第一个活动并将其发送给请求者。如果队列中没有现成的活动，请求将被存到缓冲队列，直到有新的活动可用为止。当新活动到达队列管理器时，如果队列中有未响应的请求，则从队列中删除第一个此类请求，并将新活动分配给它。
当处理器负载低于阈值时，本地负载管理器就会向中央负载管理器发送一个新活动的请求。如果在进程请求队列中发现就绪活动，或者需要在新活动到达之前进行排队，那么中央负载管理器将立即响应该请求。
- 本地队列算法
该算法的主要特点是支持动态进程迁移。本地队列算法的基本思想是在主机负载低于阈值限制时，利用该主机发起的进程迁移静态分配所有新进程。涉及到的阈值是算法的一个自定义参数，该参数定义了负载管理器应在每个处理器上提供的就绪进程的最小数量。
最初，在中心主机上创建的新进程被分配到所有负载不足的主机上。由中心主机上的第一个并行结构所创建的并行活动的数量通常足以在所有远程主机上进行分配。从这之后，在中心主机和所有其他主机上创建的所有新进程都只在本地分配。
当主机负载不足时，本地负载管理器尝试从远程主机获取若干个进程。它将包含本地就绪进程数量信息的请求随机发送给远程主机的负载管理器。当负载管理器接收到这样的请求时，它会将本地就绪进程数与接收到的进程数进行比较。如果前者大于后者，则将一些正在运行的进程传输给请求者，并返回带有传输进程数量的确认信息。
5．参数
各种负载均衡算法的性能通过以下参数进行检验。
- 过载抑制
如果负载平衡不可能实现，则需要额外的过载抑制措施。当过载情况结束时，应该首先停止过载抑制措施。经过短时间的保护，负载平衡也停止了。
- 容错
该参数表示该算法是否能够容忍故障。它使算法能够在出现故障时继续正常运行。如果算法性能下降，其下降程度与故障的严重程度成正比，即使是很小的故障也会导致负载均衡完全失效。
- 预测精度
预测精度是指计算结果与实际值的符合度，它在算法执行后才有实际意义。静态算法比动态算法提供了更高的准确性，因为前者的大多数假设是在编译时做出的，而后者则是在执行时做出的。
- 稳定性
稳定性可以用以下两点表示：
处理器之间信息传输的延迟
负载平衡算法在指定时间内获得更快速的性能
- 集中式或分布式
集中式方案将全局信息存储在指定的节点上。所有发送方或接收方节点都访问该指定的节点，以计算负载传输量，并检查是否要发送或接收任务。在分布式负载均衡中，每个节点分别执行负载均衡算法。空闲节点可以在运行时从全局共享的进程队列中获取负载分配。
- 负载平衡算法的本质
静态负载平衡以概率或确定的方式向节点分配负载，而不考虑运行时的事件。通常不可能预测负载的到达时间和未来处理负载所需的时间。另一方面，在动态负载均衡中，负载分配是在运行时根据当前的处理速率和网络条件进行的。一个动态负载平衡策略可以使用本地或全局信息。
- 协同性
此参数表明在执行过程中，处理器是否在它们之间共享进程分配决策中的信息。该参数定义的是每个处理器在决定如何使用自己的资源时所具有的独立程度。在合作的情况下，所有的处理器都有义务执行自己的那部分调度任务，但是所有的处理器都是为了达到更高的效率而共同工作的。在非合作系统中，单个处理器作为独立的实体，在不影响系统其他部分的情况下，决定如何使用其资源。
- 进程迁移
进程迁移参数表示系统何时决定迁出流程？它决定在本地创建它，还是在远程处理器单元上创建它。该算法是否能够在进程执行过程中决定需不需要改变负载分配。
- 资源利用率
资源利用率包括自动负载平衡。一个分布式系统可能会有许多需要更高处理能力的进程。如果算法能够有效利用资源，则可以更有效地将资源转移到负载不足的处理器上。
6．比较
各负载均衡算法在不同参数下的性能比较如表1所示。
表格1
负载均衡算法参数比较
|
参数 |
循环算法 |
随机算法 |
本地队列算法 |
中心队列算法 |
中央管理器算法 |
临界算法 |
|
过载抑制 |
无 |
无 |
有 |
有 |
无 |
无 |
|
容错 |
无 |
无 |
有 |
有 |
有 |
无 |
|
预测精度 |
偏高 |
偏高 |
偏低 |
偏低 |
偏高 |
偏高 |
|
稳定性 |
高 |
高 |
低 |
低 全文共6666字，剩余内容已隐藏，支付完成后下载完整资料 资料编号：[2908] |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
