负载平衡策略研究.doc

负载均衡策略的研究 概述 随着计算机性能的不断提升和高速计算机网络的发展，分布式系统具备了强大的计算能力。优良的负载平衡策略是合理充分利用这种能力的必要条件。负载平衡是分布式系统要解决的核心问题之一，具有重大的理论和实际意义。随着系统的运行，某些节点被分配到很多任务，而另外一些节点的任务却相对较少，产生系统负载不平衡现象。负载均衡是指对系统中的负载情况进行动态调整，以尽量消除或减少系统中各站点负载不均衡的现象。具体实现方法是将重载站点上的任务转移到其他轻载的站点上，尽可能的实现系统中各站点的负载均衡，从而提高系统的吞吐量。 算法分类 负载平衡算法分为：动态算法和自适应两大类。动态算法是根据系统状态，对可以接受任务的站点进行分析，可以将任务迁移到空闲站点，甚至可以将正在执行的任务迁移到其他空闲站点。动态负载平衡算法可以根据集中的程度加以区分，分为集中、分散、组合三种。自适应算法是通过动态改变参数甚至策略来调整自身的行为，以适应正在改变的系统状态。即能够根据系统状态的变化选择合适的算法。 动态负载平衡策略的组成 动态负载平衡策略包含四个组成部分：转移策略、选择策略、定位策略和信息策略。 3.1转移策略 决定一个站点是否处于合适的状态来参与任务转移。一个普遍认可的转移策略是阈值策略。 3.2选择策略 在转移策略决定了一个站点是发送者之后，选择策略要从本地选择一个任务来转移。选择策略要考虑以下几个因素：（1）转移的额外开销尽量小。（2）被选择的任务应该足够大，值得花额外开销去处理它。转移一个任务有两种方式：抢先式的(preemptive)和非抢先式的(nonpreemptive)。抢先式可以转移一个正在运行的任务，而非抢先式只能转移那些还未被启动执行的任务。 3.3定位策略 为准备转移的负载选择合适的“转移伙伴”。非集中式算法中定位接收站点有下述三种方案：（1）、随机：任务被随机地选择发送到一个站点，是最简单的定位策略。（2）、阈值：为避免没必要的转移，先要查看转移到某站点上是否会造成该站点负载超过某个阈值，如果没有，就将任务转移到该站点。（3）最短：选择具有最短任务队列的站点作为转移对象。 3.4信息策略 决定系统中其他站点的状态信息如何收集、从哪里收集、收集哪些信息等。有三种类型的信息策略：要求驱动策略：集中式算法中，一个站点只有在成为接收者或者发送者时才收集其他站点的信息。周期策略：定期地收集信息。状态改变驱动策略：在自身状态改变到一定程度时，站点向外发布它的状态信息。 4.常见的负载平衡策略 4.1接收者驱动策略 接收者驱动策略由空闲结点逐个向邻接结点请求任务，如果请求到任务，则终止请求，否则继续询问下一个相邻结点。如果所有相邻结点都没有满足请求，则请求结点等待，过一段时间后再向相邻结点发出任务请求。该策略不需要相互交换负载信息；对于大规模并行计算问题，当每个结点均处于忙状态时，几乎不需要额外调度开销；负载均衡的许多工作由空闲结点来完成，没有给忙结点增。加许多额外担。但是在开始和结束阶段时任务数相对较少，许多任务请求会延迟忙结点的执行，而且逐个地请求任务会给相邻结点一定的打扰。  图1接收者主动算法 4.2 发送者驱动策略 由创建任务的结点来执行结点间的任务调度分配。至于分配给哪个邻接结点，则主要取决于邻接结点的负载状态，因此，该策略需要交换处理器的负载信息。使用该策略时，没有过重负载的忙结点。不会被空闲邻接结点所打扰。这一点在系统整个负载较低时尤其重要。但是负载过重的忙结点还要额外增加处理负载平衡调度的负担，就这一点来说显然不太合理。 图2发送者主动算法 4.3自索取策略 若干结点以其中一个结点作为信息中心，各结点时刻监听信息中心结点，只要负载状态发生变化。各结点就向该信息中心结点汇报各自负载状态信息，并从信息中心结点接收其他结点负载状态信息。超载的负载消息也被作为任务请求由信息中心结点记录下请求任务的结点号，由空闲结点根据信息中心结点的记录主动调入执行。这样就避免了接收者驱动策略中的反复请求，从而减少了通讯开销，也不会给忙结点增加额外的负担与打扰。 4.4动态负载均衡星型模型调度算法 4.4.1星型模型的定义： Star=(D，R)其中：D 是具有相同特性的数据元素的集合；若D 只含有一个数据元素，则R 为空集，否则R是D 上某个二元关系H 的集合，即R={H)。H 为如下描述的二元关系： (1)在D中存在唯一的称为核心的数据元素center，它在关系H 下无前驱； (2)若D={center)≠? ，则存在D={center)的一个划分D1，D2