分布式系统负载平衡调度模型研究

分布式系统负载平衡调度模型研究

分布式系统可以方便地处理大型计算问题。它的优点是系统资源的可用性、规模的可扩展性和共存性。如何有效地实现分布式系统资源的管理和调度是充分挖掘系统并行潜力的关键因素。通常，一个分布式系统需要同时处理多个任务，而每个计算结点需要同时处理多个进程，这就需要通过调度与分配算法来实现任务的优化分配，以有效地减小平均响应时间，降低执行时的额外开销等。因此，负载平衡就成为改善分布式系统性能的重要手段，它的一个重要目标是提高系统性能，缩短用户任务的平均响应时间；它的另一个重要目标是均匀地、充分地利用整个系统的资源。这两个目标是一致的，资源的使用越平衡，任务的响应时间就越短。通常，负载平衡调度方法分为静态调度和动态调度两种。国内外对此已进行了许多研究，出现了多种算法。解决静态负载平衡的方法主要有：模拟退火算法、遗传算法、启发式方法、基于图论的方法等。解决动态负载平衡的方法主要包括以下几种：基于随机选择任务移动结点的概率调度算法、根据负载变化而基于梯度模型的调度算法、自适应的近邻契约算法等。影响负载平衡调度问题的因素很多，各个调度算法的实现方法也各不相同。Kim提出的调度模型将负载平衡调度过程分为以下四个阶段：负载估算、负载平衡收益性决策、任务转移和任务选择。文献中的调度模型考虑了以下因素：调度时间、调度的源结点和目标结点、调度任务的选择。文献研究了基于多处理机的任务调度模型Pk|fix|Cmax，并在此基础上提出了一个更接近实际的负载平衡调度模型，该模型是以下五个元素的集合：处理机系统、任务集实例、处理机约束集、任务之间的约束集和调度的评价指标，但是该文献并没有对各元素作详细的描述。本文在深入研究各种负载平衡调度算法和调度模型的基础上，综合考虑影响负载平衡调度问题的各个因素，给出了一个负载平衡调度问题的一般模型的形式化描述，即将负载平衡调度问题的一般模型用四元组<E,T,L,S>来表示。其中：因子E(Environment）：表示分布式系统的网络环境；因子T(Task）：表示用户提交的任务属性；因子L(Load）：表示系统的负载评价；因子S(Strategy）：表示系统所采用的调度策略。1分布式系统结构设计定义1分布式网络调度环境因子E是一个三元组（DS,SE,SG）。其中：分布式系统DS(DistributedSystem）：表示分布式系统的物理网络结构；负载平衡调度环境SE(SchedulingEnvironment）：表示负载平衡调度结点的逻辑拓扑结构；调度组SG(SchedulingGroup）：参与某项调度活动的计算结点所组成的集合。1.1同构性和拓扑结构分布式系统DS(DistributedSystem），是由一组根据通讯协议物理联接、地理分布工作站组成的相互协作、资源共享的网络系统，组成DS的工作站称为节点。节点很难做到必须是同构的，从功能上可以区分为图形工作站、科学计算工作站、I/O工作站、数据库工作站、WEB工作站等，从性能上可以区分为单处理机工作站、多处理机工作站、r-处理机工作站等。但是同构DS由于其便于调度、便于管理的优点，在某些场合常常得到特殊应用。DS除了需要描述各节点的功能与性能特性之外，还要描述节点之间物理意义上的拓扑结构。不同的拓扑结构对负载平衡调度算法有很大的影响，文献讨论了2维网格、4维超立方、线性阵列等不同结构对梯度策略、发送者驱动策略、接收者驱动策略、集中式调度策略和基于预测的调度策略等不同负载平衡调度算法的影响。1.2载平衡调度环境在负载平衡调度过程中，根据节点之间的协作协议、任务性质与功能对应关系（例如，WEB服务类任务通常由WEB工作站处理）以及负载平衡调度策略的差异，分布式系统重新构成逻辑意义上的图的拓扑结构，即负载平衡调度环境SE(SchedulingEnvironment）,SE上的节点称为结点。负载平衡调度环境的拓扑结构是一个无向图SE=（N,E），其中N为结点集，E为SE的逻辑边集。若将DS也表示成无向图，则图SE满足下面性质：(1）无向图SE是无向图DS的子图；(2）无向图SE是连通图。所有负载平衡调度策略均在负载平衡调度环境SE上进行讨论，典型的SE图结构有普通无向图、Mesh图、Hypercube图和层次结构图等。在参考了以上几种经典的分布式系统模型的基础上，综合静态和动态两种负载平衡策略，提出了一个基于层次结构的混合调度策略模型，如图1所示，该模型具有更优越的性能。1.3参与调度活动的程序负载平衡调度活动（即执行一次负载平衡调度算法）称为调度事件S＿Event，调度事件S＿Event是一个二元组（SG,SA）。其中，调度组SG(SchedulingGroup）是由参与调度事件S＿Event的所有SE结点组成的集合，SA为调度事件S＿Event执行的调度算法（SchedulingAlgorithm）。调度组中的结点充任两类角色（角色指结点在参与调度活动过程中所承担的责任和该发挥的作用），即一个调度服务器SS(SchedulingServer）和若干调度成员SM(SchedulingMembers），调度服务器SS是负载平衡调度事件S＿Event的启动者，调度成员SM是S＿Event的参与者。调度组是负载平衡调度活动的基本单位，根据每次调度活动动态生成，负责处理具体的调度事件。由于对于同一个分布式系统，不同的调度策略会得到不同的负载平衡调度环境拓扑结构，与此同时，在调度过程中，参与负载平衡调度活动的工作站类型与数目也各不相同，因此上述节点、结点与角色三个概念之间具有如下关系：(1）节点是物理上的概念，表示分布式系统中的工作站。结点与角色都是逻辑上的概念，指在负载平衡调度问题空间中（表示成图的拓扑结构），参与负载平衡调度活动的实体（On-tology）。(2）节点、结点和角色都是静态的概念。结点担任一定的角色，使用相关资源和信息协作完成各项调度活动。角色是结点在完成一项调度活动时所具有的权利与责任集合。(3）角色和结点之间的绑定是动态的。同一个结点在不同调度事件中可以担任不同的角色。在同一个调度事件中，一个角色（指调度成员）可以由多个结点担任，一个结点也可以同时担任多个角色（既是调度服务器又是调度成员）。2任务提交方式定义2用户任务因子T是一个三元组（TT,TM,TC）。其中：任务类型TT(TaskType）：表示由用户提交的任务的类型；任务提交方式TM(TasksubmittingManner）：表示用户提交任务的方式；任务约束TC(TaskConstaints）：表示任务的结构特征与求解性能要求。2.1静态多媒体数据用户提交的服务请求类型是多种多样的，按照对处理器、网络和I/O的资源要求，可以简单的将它们分为两个不同类别，以便应用不同的处理策略：(1）静态请求：例如普通的文本、图像等静态多媒体数据，它们对处理器负载影响不大，造成的磁盘I/O负载与文档的大小成正比，主要对网络I/O造成压力。(2）动态请求：更为常见的请求常常需要结点进行预处理，例如搜寻数据库、压缩解压多媒体文件等，这些请求需要相当大的处理器和磁盘I/O资源。2.2动态迁移任务转移在结点收到任务请求后，根据某种连接调度算法，将任务尽可能均匀地分配到各个结点，实现前期的负载平衡。但结点的负载往往无法通过单一的指标（如连接数或响应时间等）来静态地确定，只有任务被结点执行之后负载的大小才能实际地显现出来，故上述的平衡往往是某种形式上的平衡，不能作为负载平衡的最终目标，这就需要动态地将某些结点（如负载较重的结点）上的任务转移至另外一些结点（如负载较轻的结点）上去执行，使各个结点的负载进一步在实际环境中尽可能均匀。通过分析结点的实时负载信息，动态地将任务在各结点之间进行调整或转移，如果结点可以接受任务，就将任务转移到该结点，甚至可以将正在执行的任务转移到其他相对空闲的结点（此时称为迁移）。该思路又分为抢占式和非抢占式两类：(1）抢占式：转移一个已经部分执行的任务，该操作的代价通常是非常昂贵的，因为收集任务的状态信息非常困难。这些状态信息包括：虚拟内存的映像、进程控制块、I/O缓冲区、文件指针等。故抢占式任务迁移开销较大。(2）非抢占式：进行任务转移时只针对还未执行的任务，不涉及任务状态信息的搜集、转移。2.3子任务的分解分布并行计算任务一般分为两种模式：一种是基本模式，即将一个大计算量的任务分解为一些相互独立的子任务，在一组工作站上并行执行，最后将子任务结果汇集为总的结果；另一种为协作模式，即在计算过程中，子任务间需要同步，交换中间结果，因而要求基本上同时开始，并以同样速度执行。3负载状态的修正定义3负载评价因子L是一个五元组（LP,fl,LT,LS，α）。其中：负载参数LP(LoadParameter）：表示影响系统或工作站结点负载的因素；负载函数fl(LoadFunction）：表示系统或工作站结点负载大小的计算函数；负载阈值LT(LoadThreshold）：表示系统或工作站结点的负载阈值；负载状态LS(LoadState）：表示系统或工作站结点的负载状态；负载状态修正因子α（loadstatemodifyingfactor）：表示调节系统或工作站结点的负载状态的因子。设R为实数集，则它们满足：L：(fl(LP）,LT）→LS。3.1负载指标比较负载平衡调度工作的一个重要目标是提高系统性能，缩短用户任务的平均响应时间。而一个作业的响应时间依赖于其所运行的主机上的负载。负载越重，其运行时间越长。因而，理想的负载指标应与作业响应时间有一种单调关系。一个可以正确反映当前系统负载情况的负载指标对一个成功的动态负载平衡系统来说至关重要。理想的、真正能够体现系统负载情况的负载指标应当满足以下条件：(1）测量开销低，这意味着可以频繁测量以确保信息最新；(2）能体现所有竞争资源上的负载；(3）各个负载指标在测量及控制上相互独立。Ferrari建议使用各种资源队列长度的线性组合作为负载指标，但其条件是假定系统处于稳定状态，并且要求资源的排队规则是FCFS。不过实际系统往往难以完全满足这些条件。Zhou建议使用各种CPU队列长度作为负载指标，他发现CPU队列长度和磁盘队列长度分别与CPU类作业和I/O类作业有密切关系，但资源队列长度与资源利用率并没有紧密的关系。Bonomi等人使用处理机上活动的进程数的瞬时信息和周期搜集到的平均CPU运行队列等信息的组合作为负载指标，并且进行了实际测量，性能上有所改进，但仍不能正确反映资源利用率。Kunz通过实验比较了运行队列任务数、系统调用的速率、CPU进程切换率、CPU利用率、空闲内存大小和1min内负载平均值6个单项指标，以及它们的”或”及”与”组合，发现其中效果最好的是单项指标中的运行队列任务数，任何其它单项指标或其组合都不比它好。综上所述，影响负载的因素非常复杂，衡量分布式系统或工作站结点的负载的参数包括任务到达数、任务离开数、瞬时队列长度、平均队列长度、平均响应时间、平均伸展系数（任务从到达到离开的时间与在此阶段收到的服务时间之比）、CPU利用率、未完成的工作量、可用资源（如内存等）情况、交付任务的要求等，分别用x1,x2,x3,x4,x5,x6,x7,x8,x9，…表示，则LP可表示如下：在上述这些参数中，有些信息是得不到或不准确的。国际上现有的负载平衡系统多使用运行队列任务数作为负载指标，因为它比较容易获得，而且它与多数作业响应时间有密切的关系。为简单起见，大多数负载平衡系统将任务队列中的任务数作为描述负载的唯一参数，事实上，如果采集过多参数，则会因增加额外开销而得不到所希望的性能改善。3.2负载函数的描述负载函数fl:LP→R。将任务队列中的任务数作为描述负载的唯一参数时，负载函数可以简单地描述成该式中，x表示系统或工作站结点，既可以是一台计算机，也可以是一个分布式系统，函数TQ(x）表示x的任务队列，|TQ(x）表示任务队列TQ(x）中的任务数。3.3系统或工作站点负载状态负载阈值LT是一个序偶<β1，β2>，其中，β1，β2∈R,0<β1≤β2。负载状态集LS={‘NL’，‘LL’，‘SL’，‘HL’}，‘NL’、‘LL’、‘SL’、‘HL’分别表示空载（NullLoad）、轻载（LightLoad）、适载（SuitableLoad）和重载（HighLoad）。根据两个阈值β1与β2，可以将系统或工作站结点的负载状态划分为空载、轻载、适载和重载等四种类型。用下列的函数表示：当β1=β2时，表示只有一个负载阈值，此时负载状态集不再设置适载状态，往往将非重载称为适载。3.4动态调整负载阈值负载状态修正因子α∈R用来修正负载阈值LT，表示参与调度的工作站结点的一种自主性，它可以根据环境负载情况动态调整负载阈值，当α≠0时，它表示一种自适应负载平衡调度策略。设序偶集即Ω={<β1-α，β2-α>，<β1-α，β2>，<β1-α，β2+α>，<β1，β2-α>，<β1，β2>，<β1，β2+α>，<β1+α，β2-α>，<β1+α，β2>，<β1+α，β2+α>}，则LT∈Ω。4分布式调度环境定义4调度策略S是一个四元组（SD,ST,SF,SC）。其中：调度域SD(SchedulingDomain）：表示分布式网络调度环境；调度类型ST(SchedulingType）：表示负载平衡调度策略的类型；调度构架SF(SchedulingFramework）：表示调度策略的基本构架；调度约束SC(SchedulingConstraint）：表示调度策略的约束条件。4.1网络计算服务在分布式网络环境中，对于用户来说，参与负载平衡调度工作、为用户提供网络计算服务的工作站资源是透明的，通常情况下，为用户提供服务的只是部分工作站资源，它们通过负载平衡策略共同为用户提供网络计算服务，以达到均衡资源、最短时间内响应用户的目的。称这部分工作站为调度域SD。4.2动态负载平衡调度模型调度类型区分为静态调度和动态调度两种。静态负载平衡问题就是将任务均匀分配给各工作站，此时工作站的任务量、任务间的通信量都为定值，不随时间变化。静态负载平衡调度策略的优点是可以得到最优负载平衡结果，其缺点是在现实网络环境中很难做到。另外，因为静态调度服务器需要掌握各工作站的实时负载变化情况，所以它适于处理工作站故障等异常情况，但随着系统规模的增大，静态负载平衡调度效率快速下降。动态负载平衡通过分析系统的实时负载信息，动态地将任务在各个结点之间进行分配和调整以适应实时分布式系统中负载分布的不均匀性，所以动态负载平衡更能反映分布式系统的实际情况。但其缺点也十分明显，动态负载平衡调度结果只能得到部分的平衡，并且参与调度的系统也是局部的。另外，动态调度策略通常忽略了工作站可能出现故障的情况，而在大规模分布式系统中，系统的不稳定是难以避免的。此外，动态负载平衡调度也往往忽略了任务之间的通信量，这样在通信量较大的分布式系统中将增大整个系统的负载，进而造成整个系统的不稳定。按照负载平衡调度活动的启动者划分，动态负载平衡调度可以分为发送者驱动算法、接收者驱动算法和双向驱动算法三种类型。在发送者驱动算法中，当一个结点超载时，它作为发送者尝试将任务发送给一个轻载结点（接收者）。与发送者驱动算法相反，接收者驱动算法是当一个结点的负载状态变成轻载时，它作为接收者尝试从重载结点接收一个任务。双向驱动算法兼有上述两种算法的优点，当系统整体负载较轻时，调用发送者驱动算法容易发现轻载结点；当系统整体负载较重时，调用接收者驱动算法则容易发现重载结点。它的不足在于，如果在系统负载较重时使用发送者驱动算法容易造成系统不稳定。一个较好的解决办法是采用自适应算法，合理设置阈值，及时掌握系统的负载状态信息。根据静态负载平衡调度与动态负载平衡调度的这些特点，在文献中提出了一种分层负载平衡调度模型。此模型是静态调度与动态调度的混合模型，也是一种通用模型，当层次结构自底向上缩为单层扁平结构时，它退化为静态调度模型，当层次结构自顶向下塌为单层扁平结构时，它退化为动态调度模型，如图1所示。实验结果表明，与传统的动态调度与静态调度相比，分层负载平衡调度系统具有较好的问题求解效率。4.3配置框架f调度构架指负载平衡调度算法的四个组成部分：转移策略、选择策略、定位策略和信息策略，它们组成负载平衡调度活动的整个生命周期。(1）阈值设置位置在调度活动的生命周期中，转移策略决定调度组中的结点是否处于合适的状态来参与任务转移工作，充当任务转移的发送者或者接收者角色。一种普遍认可的转移策略是阈值策略：参照3.3节，当某结点完成一个任务使其负载小于阈值β1时，就将该结点确定为接收者；当某结点从用户或者其它结点接收新任务，使其负载大于阈值β2时，就将该结点确定为发送者。此时称β1为接收阈值，β2是发送阈值。阈值设置要适当，如果阈值设置过低，负载量被人为提高；如果阈值设置过高，结点事实上已经支持过重的计算，但表面上仍显得空闲。这种方法也称绝对转移策略，与之相对的为相对转移策略，即在调度组中，确定相对于其它结点负载最轻的结点为接收者，相对于其它结点负载最重的结点为发送者。(2）选择合适的转移任务在调度活动的生命周期中，选择策略在转移策略之后启动。一旦转移策略确定了发送者之后，选择策略负责从该结点选择一个待转移任务，如果选择策略找不到合适的转移任务，则该结点就不再被认为是发送者。最简单的选择策略方法是选择导致该结点成为发送者的新任务作为转移任务，此时任务转移的开销较小。选择策略要考虑以下几个因素：转移的额外开销尽量小，被选择的任务应该足够大，以值得花去额外开销。(3）共享负载的轮询策略定位策略主要选择待转移任务的接收者。在静态调度算法中，由调度服务器负责定位、收集系统信息，发送者从调度服务器获得系统信息来确定接收者。在动态调度算法中，一