《(完整word版)分布式系统中负载平衡算法分析.doc》由会员分享，可在线阅读，更多相关《(完整word版)分布式系统中负载平衡算法分析.doc（8页珍藏版）》请在金锄头文库上搜索。
1、摘要：该文简单描述了负载平衡算法提出的原因，负载平衡算法的分类以及动态平衡算法的需求。详细分析了动态负载平衡中的接受者驱动、发送者驱动和双向驱动算法以及双向驱动算法的改进算法，并对各算法的优缺点进行了分析。关键词：分布式系统 动态负载平衡1引言分布式系统是由多台分散的计算机连接而成的系统，其中各个资源单元（物理的或逻辑的）既互相协同又高度自治，能在全系统范围内实现资源管理，动态地进行任务分配或功能分配，并能并行地运行分布式程序。分布式系统具有良好的可用性、 可扩展性、 可靠性和健壮性，并为用户提供透明方便的用户界面。因此，近年来随着一些高速网络的兴起，分布式计算机系统日益得以广泛的应用并受到人
2、们的重视。经过研究发现，影响处理系统性能的因素包括处理机间的通信开销和分配的负载平衡等，但减少处理机的通信开销和均衡负载是相互冲突的两个因素，它们左右着任务分配策略。如负载均衡可以提高整个系统的吞吐量，因为它试图将模块尽可能均等地分配给处理机，但减少处理机的通信开销又迫使分配策略不得不尽可能地把较多的模块分配给尽可能少的处理机。由于一些并行任务之间的互相依赖关系和通讯量的大小很难在编译时就进行确定，所以人们更多地倾向于动态负载平衡的研究。随着研究的深入进行，人们注意到在一个由网络所连接起来的多个计算机系统环境中，在某一时刻，一些计算机系统的负载很重而另外一些计算机系统的负载却很轻，影响了整个系
3、统资源的利用率。由此，我们应该采用有效的负载平衡策略，即在减少处理机通信开销的基础上，提出行之有效的算法，提高整个系统资源的利用率。1.1 减少处理机通信开销系统管理站设计一个信息区，各模块每通信一次，节点累加器自动累加一次，最终将通信的模块信息和累加的次数一起存储到系统管理站的信息区。待系统下次运行时，系统管理站会根据信息区中以前模块信息通信的高低次数排序，按信息区的记录情况将通信频繁的模块安排到同一个节点，从而减少处理机的通信开销。1.2 负载平衡算法1.2.1概述负载平衡也称负载共享，是指对系统中的负载情况进行动态调整，以尽量消除或减少系统中各站点负载不均匀的现象。因此，如何准确地评估各
4、节点的工作负载能力并且分配新的请求任务到每个节点，成为分布式系统取得负载平衡的关键。1.2.2 负载平衡算法的需求（1）最小化客户请求的派发时间，使客户请求能够迅速地被派发给相应的服务副本，而不会因为低效的副本选择导致延迟。（2）最小化客户请求响应时间和最大化系统的吞吐量，使系统能够获得最高的性能和最大的资源利用率，最小化资源的空闲时间。（3）客户请求的响应时间具有可预期性。（4）保证副本间负载分配的平衡，从而降低发生过载的可能性，确保服务的可用性和系统的可靠性，同时能够在一定程度上抵御负载峰值的冲击。（5）具有好的可扩展性，不依赖于某种特定的资源或结构，也不对系统中结点或副本的数目做出任何假
5、设。（6）最小化系统的通信开销。1.2.3 负载平衡算法的分类负载平衡算法可分为动态算法和自适应算法两大类。动态算法是根据系统状态对可以接受任务的站点进行分析，可以将任务迁移到空闲站点，甚至可以将正在执行的任务迁移到其他空闲站点，但要注意的是，信息的收集、分析及作出决定要造成额外开销，不可小视。自适应算法是通过动态改变参数甚至策略来调整自身的行为，以适应正在改变的系统状态。如，某种负载平衡算法在A情况下的性能优于其他算法，而另一种算法在B情况下更优，自适应算法能够根据系统状态的变化选择合适的算法。在无法通过任务迁移提高系统性能的情况下，自适应算法是很好的选择。对按一次局部负载平衡调度的启动者来
6、说，又可分为接收者主动和发送者主动两种。其中，在发送者主动算法中，当一个站点超载时，它就尝试将任务发送给一个轻载站点，整个算法的思想是负载较重的节点试图甩掉超额的工作。接收者主动算法与发送者主动算法相反，当一个站点的任务队列长度小于阀值时，它就尝试从重载站点接收一个任务。综合以上算法，本文针对考虑节点工作负载能力、请求负载差异的和配置相对简单的因素，在减少处理机的通信开销基础上提出了双向主动均衡算法。2. 动态负载平衡算法2.1发送者主动算法发送者主动算法的思想是：当进程被创建时，它就运行在创建它的节点上，除非该节点过载了。过载节点的度量可能涉及太多的进程、过大的工作集或者其他度量。如果过载了
7、，该节点任意选择另一个节点并询问它的负载情况（使用同样的度量）。如果被探查的节点负载低于某些阀值，就将新的进程发送到该节点上。如果不是，则选择另一个机器探查。该策略需要交换处理器的负载信息，一个节点有多种方法 向邻接节点通知它的负载情况，如定期询问、每当任务数发生变化、接收到执行任务请求、响应请求或者当任务数超过一定阈值时。启动时，所有节点开始执行任务。在一段时间以后，节点开始检查自身是否是重载节点，如果是，它就试图在相关域中均匀的分布任务。具体来说，设该重载节点的负载为lp，相关域中有K个节点，其负载分别为l1，l2，lk，则平均负载Lavg为： Lavg=(1/(K+1)(lp+l1+l2
8、+lk)为达到任务的均匀分布，应求得重载节点传递给每个相关域中节点的负载量，因此引入权值hk以避免任务被迁移到负载更重的重载节点。如果Lavglk，则hk=Lavg-lk，否则hk=0。因此mk为：mk=(lp-Lavg)hk/(h1+h2+hk) 然后该节点就可以按照向各个相关节点发送任务。下图为发送者主动算法流程。图2-1 发送者主动算法（OL为任务队列长度，OLi为站点i的任务队列长度，T为阀值） 2.2接收者主动算法接收者主动算法与发送者主动算法相反，把所有节点按照阀值M划分为轻载节点和重载节点，所有当前负载tM的节点称为重载节点，tM的节点称为轻载节点。当一个站点的任务队列长度小于阀
9、值时，它就尝试从重载站点接收一个任务。在这个算法中，只要有一个进程结束，系统就检查是否有足够的工作可做。如果不是，它随机选择某台机器并要求它工作。如果该台机器没有可提供的工作，会接着询问第二台，然后第三台机器。如果在N次探查后，还没有找到工作，该节点暂时停止询问，去做任何已经安排的工作，而在下一个进程结束之后机器会再次进行询问。如果没有可做的工作，机器就开始空闲。在经过固定的时间间隔之后，它又开始探查。启动时，所有节点开始执行任务。在一段时间以后，节点开始检查自身是否是重轻载节点，如果是，它就试图在相关域中找到重载节点，并请求该节点上的任务。具体来说，设该轻载节点的负载为lp，相关域中有K个节
10、点，其负载分别为l1，l2，lk，则平均负载Lavg为：Lavg=(1/(K+1)(lp+l1+l2+lk)为达到任务的均匀分布，应求得相关域中重载节点应该传递给该节点的负载量mk，因此引入权值hk以避免任务从负载更轻的轻载节点迁移过来。如果Lavglk，则hk= lk -Lavg，否则hk=0。因此mk为：mk=( Lavg -lp)hk/(h1+h2+hk) 然后该节点就可以按照mk向各个相关节点发送接受任务请求。下图为接受者驱动算法流程。图2-2 接受者主动算法（OL为任务队列长度，OLi为站点i的任务队列长度，T为阀值） 2.3双向主动算法在双向主动算法中，发送者和接收者都能转移任务。
11、在系统负载较低时，本算法中的发送者主动容易发现轻载站点，在系统负载较高时，接收者主动容易找到重载站点。所以，在系统中，我们应该合理地设置均值，在系统高负载时采用接收者主动，在系统低负载时采用发送者主动。在系统中，每个节点根据自身的硬件配置不同而具备不同的负载能力。另外，系统管理站会根据各个节点的负载能力值统计出整个系统的负载总能力值，并设置一个系统负载能力均值。由于系统管理站是在采集时刻进行负载计算的，经过实验证明，以此反映出来各个节点的负载信息会出现剧烈的抖动，从而无法准确地捕捉各节点真实的负载变化趋势。因此解决这些问题，要适当地调整采集负载信息的周期，一般控制在五秒至十秒。还有，每个负载都
12、存在一个负载上限值和负载下限值，如果实时负载值计算结果大于或等于负载上限值（即LOADmax），则说明此节点开始处于负载超载状况；如果实时负载值低于负载下限值（即LOADmin），说明此节点开始处于空闲状态。当然在实际使用中，我们会发现所有节点的实时负载值都大于或等于它们的负载上限值，则说明当前整个系统处于超载状态，这时需要加入新的节点到集群中来处理部分负载；反之，若所有节点的实时负载值低于负载下限值，则说明当前系统的负载都比较轻。若系统管理站确认系统处于高负载时期则采用接收者主动，即在系统处于高负载时期时，各节点在执行完负载数处理算法之后根据自己的负载上限值和负载下限值判别自己的负载情况，当
13、自己的负载低于下限时，该节点就会按一定方式查询系统的状态，请求某个重载节点迁移一个尚未开始运行的任务给自己。若此时该重载节点尚无这样的任务存在，则轻载节点同它进行一次“预约”，要求一旦有新创建的或到达的任务，就将它迁移给自己。若系统管理站确认系统处于低负载时期则采用发送者主动，即在系统处于低负载时期时，各节点在执行完负载数处理算法之后根据自己的负载上限值和负载下限值判别自己的负载情况，当自己的负载高于上限时，该节点向系统广播一个“请求迁移出负载”的请求消息。接收到这一请求消息的节点根据自己的状态决定是否参与投标。若参与，则向请求者发送一个标书（含可以接收的负载量），该重载节点对接收到的标书进行
14、筛选，选出其中负载最少的节点并把其希望迁移的负载迁移给它。综上所述，双向主动算法的步骤分析如下：第一步骤：查询系统任务接收器，查看是否有新任务，若无新任务，且各节点负载为空，则系统为初始状态，处于等待情况；若有新任务提交，转到第二步骤；第二步骤：系统管理站分析系统负载状况，此时情况讨论如下：（1）若系统管理站确认系统处于高负载时期则采用接收者主动。（2）若系统管理站确认系统处于低负载时期则采用发送者主动。所以以下几步骤根据第一步骤的分析分为高负载时期和低负载时期情况进行。当系统处于高负载时期时，转到以下第三步骤；第三步骤：此时轻载节点按一定方式查询系统的状态，请求某个重载节点迁移一个尚未开始运
15、行的任务给自己。若此时重载节点迁移一个未开始运行的任务给轻载节点，则转入第四步骤；如果该重载节点尚无这样的任务存在，则转入第五步骤；第四步骤：轻载节点运行迁移的负载，完成重载节点迁移的所有任务转入第五步骤。第五步骤：轻载节点对重载节点进行“预约”，一旦有新创建的或到达的任务，就将它迁移给自己，然后转入第四步骤，否则直到系统节点完成所有任务转入第六步骤；第六步骤：退出程序。当系统处于轻负载时期时，转到以下第三步骤；第三步骤：此时重载节点向系统广播一个“请求迁移出负载”的请求消息，转入第四步骤；第四步骤：接收到这一请求消息的节点根据自己的状态决定是否参与投标；若参与，则向请求者发送一个标书（含可以
16、接收的负载量），转入第五步骤；第五步骤：该重载节点对接收到的标书进行筛选，选出其中负载最少的节点并把其希望迁移的负载迁移给它。第六步骤：轻载节点完成重载节点迁移的负载，若还有重载节点向系统广播一个“请求迁移出负载”的请求消息，转入第四步骤，否则直到系统节点完成所有任务转入第七步骤；第七步骤：退出程序。以上各个步骤是在各个节点上并行同步进行的，负载空闲与否的判断，负载数处理算法的执行等都是动态进行的。因为在该平衡算法中，各个节点根据系统的负载状况选择发送者主动还是接收者主动，所以该算法命名为双向主动算法。 3算法性能分析3.1 算法特点发送者主动的主要优点是：没有过重负载的忙节点，不会被空闲邻接节点所打扰。这一点在系统整个负载较低时尤为重要。 发送者主动的主要缺点是：负载过重的忙节点还要
