分布式网格作业调度模型研究

分布式网格作业调度模型研究

0网格资源调度问题的提出网格技术有效整合了广泛、分散和异构资源，提供了大量的计算资源、数据资源、信息资源、存储资源、硬件资源等，用于处理科学计算、电子商务、工程制造等领域的应用问题。面对巨大的网格计算资源,我们需要有效加以利用,因此我们将要面临并研究的主要问题之一就是如何对广域范围内分布、异构、动态的资源进行合理调度。作为调度的目标之一,负载平衡是计算网格的重要特性。我们知道,简单的负载平衡策略可以有效提高计算性能。对网格资源调度进行的研究中,通常涉及到资源发现、资源监控、资源聚类、任务分配,任务调度。这里主要讨论的是在资源聚类基础上,进行的调度模型和负载平衡调度的研究。文献提出了一种面向网格计算的机器选择算法,用于主机资源的聚类,为网格资源组织和管理提供了一种有效的方法,提出了异构环境下基于通信密集应用和计算密集应用的聚类算法。根据此类算法生成的虚拟集群作为我们将要研究的调度问题的节点。文献提出的网格计算资源调度的三层模式试图解决网格计算中的资源调度问题。但是它的三级调度模式层次间的通信会影响到调度系统的整体性能,并且第一级的集中式调度节点可能形成单故障点。这也是本文要解决的问题之一。文献中的传统扩散算法,每个节点只能与其周围直接连接的节点平衡负载,通过多次循环迭代实现系统的负载平衡,这样的负载平衡如果用于网格环境是不合适的,因为面对广域分布的网格,迭代的次数将极大降低负载平衡的效率,增强负载扩散速度也在本文中给出了一个解决方案。本文首先说明了负载平衡的相关概念,并描述本文需要的计算网格模型,负载信息采集策略,和负载转移策略。然后提出了基于负载平衡的调度系统模型,以及相应组件功能,给出了负载平衡算法。最后总结了以上工作并说明将继续进行的工作。1负载负荷平衡1.1负载平衡的实现在计算网格中,当经过一段时间运行后,某些结点分配的任务很多(重载节点),而另外一些结点却相对空闲(轻载节点),产生负载不均衡现象。在一些计算网格的应用中,尤其是在异构资源的网格环境中,负载的不平衡性越发明显,本文的应用中,会出现1:50的负载不均衡。负载不均衡导致系统严重的低效运行,因此,实现负载平衡是保证整个计算网格效率的前提。负载平衡问题是一个经典的组合优化难题,一般分为静态负载平衡和动态负载平衡两种。静态负载平衡由于本身局限性,不适用于网格的动态变化环境,因此本文主要研究动态负载平衡。动态负载平衡通过分析系统各节点实时负载信息,动态地将任务在各个结点之间进行分配和转移以调整系统中各节点负载分布不均匀性,所以动态负载平衡更能反映分布式系统的实际情况,适用于计算网格。1.2以资源聚类产生的广域节点为中心的网络化分布式调度为了建立我们需要的网格系统模型,我们可以使用基于网络性能的主机资源聚类。它的思想是根据网格应用对链路状态(带宽、延迟等)的QoS要求进行资源划分,要求资源集合内部主机间连接为高带宽、低延迟,而不同资源集合主机间的连接是相对低速的。通过此类资源聚类方法,在全局范围内,我们可以将网格抽象为若干个广域节点组成的分布系统,进行资源的管理和调度。每一个广域节点是资源聚类产生的一个节点集合。定义1广域节点,指通过资源聚类产生的一个资源节点集合。所有广域节点集合组成网格计算系统定义2每一个广域节点内部都有自己的资源管理和调度节点,我们称之为广域节点的作业管理调度节点,文中简称为调度节点.。调度节点之间存在直截通信连接的我们称之为临近节点。通过这种方式,网格系统被分为两层,底层是通过资源聚类产生的一个节点集合Ni,是一个局域网格,高层是将各个局域网格连接起来形成一个整体的网格系统G。每个局域网格系统的调度方法可以根据自身特点使用传统的分布式调度方法进行任务分配和调度,本文讨论的是更高层次的负载平衡问题,即在各个局域网格之间负载不均衡的情况下,进行负载平衡。负载平衡主要涉及3个方面的问题:(1)信息采集策略;(2)负载转移策略;(3)负载平衡算法。负载平衡算法是我们研究的重点,将在后面章节中重点讨论。1.3pu利用的假设在进行负载平衡的调度中,需要了解各广域节点的负载信息,作为衡量负载转移目标节点的负载轻重状况的参数。因此定义3负载信息定义:{,}={CPU总体性能,CPU利用率}。假设:轻负载<%30R中等负载=%60R重负载>80%R。在广域网络进行信息传输网络延迟相对较大,为了减少网络通信所带来的负载,本文的信息采集策略采用负载变化时采集负载信息的方式。当广域节点负载波动超过一定范围,它的调度节点才将采集到的负载信息传输给主调度节点,这样可以大量减少负载信息传递开销。所以,各调度节点的负载信息发送方式描述如下if(系统负载利用率<=中等负载and负载波动大于5%)发送系统负载信息给负载平衡调度系统负载信息采集节点;1.4采用作业转移算法负载平衡过程需要进行负载转移,由于进程迁移不仅难以在网格环境中的异构结点间实现,而且其开销也十分庞大,甚至抵消负载平衡所带来的性能提高。因此,采用作业转移算法,即只对已经分配给广域节点但未开始执行的作业进行再分配,并且所有作业最多进行一次再分配,这样有效减轻负载平衡系统可能产生的“颠簸”现象。该方法可以自动适应Internet环境下的资源不确定性,可以不借助进程迁移而实现低开销的任务再分配。2资源规划模型2.1从调度节点的监控在各个广域节点的作业管理调度节点之间,通过选举算法产生一个主调度节点,主要用于收集全局范围的负载信息,监控其它调度节点有效性。主调度节点产生以后,它指定一个从调度节点,并监控从调度节点的有效性,以便在从节点失效时,重新指定从调度节点。从调度节点的任务是,周期性监控主调度节点,并和主调度节点交换全局负载信息,在主调度节点发生故障的情况下快速接替主调度节点的位置并实施主调度节点的功能。主从节点之间的这种互相监控的机制,有效保证了动态负载平衡系统中的全局负载信息收集的有效性,增强系统的可靠性。网格系统模型G={1,2,…,,…,,…,},表示主调度节点,表示从调度节点。如图1所示,其中,

表示调度节点。立方体表示广域节点,云状图表示其它的广域节点。2.2主调度节点信息搜寻算法主调度节点:初始化时,主调度节点组播信息给系统中各个调度节点,表明自己是主调度节点,告知其它调度节点将负载信息按照信息采集策略发送给自己。根据各调度节点返回信息指定一个从调度节点,并启动后台进程,监控从节点的有效性。系统运行时,在负责本地作业管理调度工作的同时,接收其它调度节点传来的当前负载信息数据,并将全局范围调度节点的负载信息周期性发送给从节点,以便从结点在适当时机作为主调度节点工作;如果有其它调度节点因本地负载过重,发出资源请求到主调度节点,主调度节点根据算法1选择当前全局负载最轻的节点位置和负载信息给请求节点。算法1主调度节点信息查找算法从调度节点:从调度节点作为调度节点,它本身也具备同其它调度节点一样的本地作业管理调度功能。在被指定为从调度节点时,从调度节点主要负责监控主调度节点的有效性,并接受主调度节点传递的全局范围负载信息。当发现主调度节点失效时,从节点向系统中所有调度节点组播信息,通知主调度节点失效,自己已经接替成为新的主调度节点,并接受全局范围调度节点传送来的各地负载信息。同时指定新的从调度节点,行使主节点职能。其它调度节点:调度节点通过取得相关节点负载信息,判断任务转移的目的节点,完成全局负载平衡调度任务,具体算法在下一节中给出。3调度节点负载重负载当广域节点负载过重时,其调度节点同时向临近节点和主调度节点发出负载转移请求后,根据算法2描述的负载转移方法,根据返回信息的到达顺序,检查相关调度节点的返回信息(一般临近节点有较短网络延迟),确定这些广域节点是否可以减缓本地负载压力,并且在其接受负载转移后自身负载维持在正常负载状态。如果满足条件,则进行负载转移调度;否则继续等待,直到满足要求的调度节点返回信息,系统进行负载转移,将负载向周围扩散,或者转移到负载最轻的位置。算法2调度节点负载平衡算法调度节点负载过重时通过获取相关广域节点的负载信息,判断并决定负载转移的目标节点。通过采用这样的方式,主调度节点作为一个全局负载信息采集节点,存储着各广域节点的实时负载信息,并负责查找最轻负载节点。负载平衡的功能则分别由各个调度节点自身来完成,相对于一般集中式调度节点负责调度信息收集以及进行任务调度,我们可以效减少了一般集中式调度节点的负载平衡调度负担。在一般的分布式调度算法中,收集其它广域节点实时负载信息的通信复杂度为O(n(n-1)),而这个算法的通信复杂度为O(n+1),和集中式调度算法的O(n-1)有相同的数量级,却通过主从调度节点的实现机制,具有了和分布式负载平衡算法类似的可靠性。由于临近广域节点网络延迟小,有效保证负载优先转移至临近节点;而且在临近节点重负载的情况下,负载快速扩散至全局最轻负载节点。通过这种方式,系统负载扩散到更大范围,更快转移到全局最轻负载的广域节点,加速负载平衡速度,是一种有效的负载平衡方法。4负载平衡调度算法本文提出了一种分布式调度模型,通过主从调度节点之间的互相监控,保证全局负载信息收集的有效性,使负载平衡系统具有一定的可靠性,更