一种基于优先级的网格调度算法

廖大强,邹 杜,印 鉴

(1.南华工商学院信息中心,广州510507;2.华南理工大学广东省计算机网络重点实验室,广州510640;

3.中山大学信息科学与技术学院,广州510275)

一种基于优先级的网格调度算法

廖大强1,邹 杜2,印 鉴3

(1.南华工商学院信息中心,广州510507;2.华南理工大学广东省计算机网络重点实验室,广州510640;

3.中山大学信息科学与技术学院,广州510275)

容错机制中基于任务数量的平均调度策略在处理跨度和服务质量方面存在不足,为此,提出一种基于优先级的网格调度算法,进而给出层次式集群系统的设计方案。在任务调度过程中引入任务剩余执行时间、任务价值密度、费用预算以及处理跨度的概念,以缩短任务处理跨度,提高服务质量。实验结果表明,与原机制调度策略和Max-Min算法相比,该算法在任务完成率、价值实现率和处理速率方面具有优势。利用该算法对原机制进行改进,能够有效提高系统的任务执行效率。

任务调度;价值密度;费用预算;处理跨度;高可用性;网格计算

1 概述

任务调度是集群系统的核心技术,其实质是对资源进行规则的分配。在分布式系统中,节点在大部分时间内都处于资源低利用状态,即使当系统负载较大,也有出现部分资源空闲的状态,若不对系统资源进行充分利用,势必没有充分发挥处理节点的运算能力。因此,对任务进行规则性的分配,提高负载均衡率是必要的[1]。对于系统而言,任务实时调度能够提高系统的运行效率,降低任务的错失率,从而一定程度地提高系统的可靠性与可用性[2]。在目前的实时调度算法中,根据系统分类,可分为单处理机调度、集中式多处理机调度和分布式调度;根据任务集种类分类,可以分为周期性任务调度算法、非周期任务调度算法与混合性任务调度算法。高可用集群系统的任务集属于偶发性的任务集,其特点在于任务的到达时间、到达数量都是突发性且无法预知的。在分布式调度算法中,网格调度算法是一种将资源通过互联网联合起来组成一台“超级计算机”进行任务处理的任务调度策略,其特点主要有面向异构资源、分布式的、不干预本地调度策略等。该算法的目标包括最优跨度、负载均衡、服务质量、经济原则等,其主要思想在于使任务集能够在最短时间内以最优的服务质量得到完成[3]。

通过网格调度算法的调度,能够保证系统处理节点随时处于最优的运算效率状态,使随时到达的任务集都可以在最短时间内以最优的质量得到完成,从而解决偶发性任务到达时间和数量无法预测的问题。因此,网格调度算法可以很好地应用于层次式集群系统,使系统实时性和可靠性得到进一步的提高。本文提出一种基于优先级的网格调度算法,该算法以网格调度原理为基础,在任务分配过程中,结合任务的剩余执行时间及价值密度对任务集进行排序,优先对剩余执行时间小且价值密度高的任务进行调度,并综合考虑资源处理速率和费用因素,通过加权运算对两者进行优先级计算,将任务分配至优先级较高的资源上。

2 网格调度

2.1 网格调度特点

网格计算是当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题之一,它通过Internet将分散在各地的各种资源通过Internet连接起来,构成一个巨型计算机,并为使用者提供存储、数据计算和资源访问等各种服务,这样将各地闲置的资源通过网络整合起来,减小了资源的孤独性,为使用者提供了方便的服务,也减小了计算的耗费[4]。目前许多科研机构都在对网格的各个方面进行研究,根据不同的项目,对网格的定义也不同,比如有些国外的学术杂志中成为“Internet2”或“第二代互联网”。同时这2个名词也是2个研究项目的名称,其所研究的内容与网格一致,只不过所研究的重点有所区别[5]。

2.2 网格调度目标

作为分布式系统的一种形式,网格的核心在于任务的调度,它可以描述为合理解决计算任务在地理分布的各种资源之间的动态调度,使各资源能够得到充分利用。由于任务调度为NP完全问题,因此现今对其的研究一般为寻找近似的最优解[6],其具体目标包括以下4个方面:

(1)最优跨度。跨度指完成一个任务集所需要的时间,也就是从第一个任务至最后一个任务完成的时间间隔,它是网格调度中最重要的目标之一。跨度越短就说明任务处理越快,表明调度策略效果越好[7]。对于用户来讲,调度的跨度必定是越短越好。可见,实现最优跨度是用户和网格系统的共同目标。

(2)服务质量(Quality of Service,QoS)。可以说,QoS为调度算法的共同目标,网格为用户提供的服务,其优劣是通过服务质量来衡量,好的服务质量能够保证用户提交的任务在高效率、低错误率的状态下完成,所以在任务管理与任务分配时,服务质量是其考虑的重点之一。

(3)负载均衡。在分布式系统中,其关键的问题在于各节点间的负载均衡率。网格系统在此方面的需求更加扩大化,由于网格环境的庞大与复杂性,对于调度的负载均衡性是一个非常重要的问题[7]。

(4)经济原则。网格的地理分布是广泛而且复杂的,并且有异构性的特点,对于这样的环境,其各节点所提供的服务与价格也存在较大的差异,根据经济原则,由于资源的异构性必定使各资源的价格产生差异[8],因此网格任务调度满足交易双方的利益,使消费双方互惠互利,这样才能使网格得到持久地发展。

2.3 经典网格调度算法分析

网格任务的调度属于NP完全问题,最优的调度算法在目前仍难以实现,所以,为取得一个好的调度策略,经常采用的方法为寻找接近于最优解的方式,其中比较经典的网格调度算法有 Min-Min算法、Min-Max算法、遗传算法等[9]。

(1)Min-Min算法:该算法首先计算任务集中所有任务在现有资源上的预期执行时间,然后选择具有最小值的任务将其分配到能最早完成它的机器上,分配完成后,将此任务从任务集中删除,并重复上述过程,直至任务集为空[10]。

(2)Min-Max算法:该算法类似于Min-Min算法,但由于Min-Min算法总是优先调度执行时间短的任务,因此对于长度比较长的任务来说,需要等待的时间也比较久,而Min-Min算法有个比较严重的缺点,那就是它的负载平衡性较差[11]。这里用它与Min-Max算法做一个理想化的比较。假定有如下3个任务和3个资源主机,各任务在各主机上期望执行时间如表1所示。

表1 任务对应资源的预期执行时间 ms

基于该资源列表,分别使用Min-Min算法和Min-Max算法进行调度,调度结果如图1所示。

图1 Min-Min算法与Min-Max算法调度示例

从图1中可以看出,Min-Max算法较Min-Min有更好的负载均衡性,其调度跨度方面的性能更优于Min-Min算法。

(3)遗传算法:该算法是一种生物进化论与遗传变异理论相结合的模拟生物进化的搜索算法。算法流程如图2所示。

图2 遗传算法流程

遗传算法优点在于具有与领域无关的群体性全局搜索能力,有效避免了算法陷入局部最优的情况发生;利用概率机制进行迭代,具有随机性;使用评价函数启发搜索,过程简单;可扩展性强,与其他的技术容易结合形成优化算法。而其缺点在于对系统的反馈信息没有充分利用,其搜索的随机性较高,并且算法的求解会产生大量的冗余迭代,从而延长了最优解收敛时间,影响到调度的效率[12]。

3 基于优先级的网格调度算法

针对系统偶发式任务模型,网格调度算法可以在一定程度上解决任务到达时间无法预知的问题,且能够保证任务完成的质量与速率,可以较好地应用于高可用集群系统中,因此,本文提出一种基于优先级的网格调度算法。

3.1 任务集与资源集描述

设T={T1,T2,…,Tn}为网格作业的任务集,用一个五元组来表示Tj=＜IDj,aj,Lj,vj,Dj＞。其中,IDj表示任务Tj的标识;aj表示任务到达的时间;Lj表示任务的长度,其单位为百万指令(MI);vj表示任务的价值;Dj表示任务的截止期,即任务的完成时间期限。

设R={R1,R2,…,Rm}为网格环境中的资源集,其单个资源用一个3元组来表示:Rj=＜IDj,MIPSj,pricej＞。其中,IDj表示资源的编号;MIPSj表示资源rj的处理速率;pricej表示资源rj单位时间的价格。

3.2 优先级运算

根据上述任务集的描述,任务tj的价值密度VDj如式(1)所示。

VDj的大小决定任务的优先级,其值越大,则优先级越高。

设当前时间为t,由式(1)可得任务Tj的剩余执行时间Sj,如式(2)所示。

任务剩余执行时间越小,则表示其该任务越紧急。

考虑剩余执行时间与任务价值2个因素,根据式(1)与式(2)来定义本算法任务调度顺序的优先级Pj,如式(3)所示。

Pj表示任务Tj在其剩余执行时间内单位时间的价值密度,单位时间内任务价值率越大,则优先级越高,调度时对优先级大的任务进行优先调度,这样使得价值大且时间紧急的任务优先得到处理,从而减小任务的错失率并提高任务的价值实现率。

3.3 网格调度预算费用的选择范围

对于用户来说,任务调度的费用预算是其考虑的主要因素之一,这里给出一种费用预算区间的计算方法,其思想如下:从理论上讲,若任务集T中的任务能够绝对地负载均衡到资源集R上,也就是说资源集中所有的资源能同时并行工作并在同一时刻将分配到的任务完成,这样资源的运行效率达到最高,从而也使任务集处理时间跨度取得最优。设这种情况下每个资源的处理时间为T,资源集R可得处理整个任务集所需的总费用Price如式(4)所示。

由于每个资源的处理时间为t,而每个资源的处理速率已知,为MIPSj,则可以得出任务集T中所有任务的长度和L如式(5)所示。

由式(4)与式(5)综合可以得出,在理想状态下,任务集T的单位长度耗费如式(6)所示。

由于资源集中单个资源的价格与运行速率为已知,因此平均长度耗费Average为一个可以计算出的常数,这个值代表了理想状态也就是任务执行的最快速率下的任务耗费,而对于用户来说,费用预算越高,其任务的处理速率应该越快,故若用户的费用预算高出这个耗费是无意义的,所以这个费用的值应该为用户费用预算的最大值,设为Bmax。

在资源集R中,必定存在一个单位长度价格最低的资源,设为资源Rk,则若将任务集T中所有的任务全部都分配到该资源上,最终的调度结果则为该任务集调度的费用最优策略。则资源Rk的单位长度价格为用户预算费用的最低值,即Bmin如式(7)所示。

由以上定义得出,用户的预算费用选择区间为[Bmin,Bmax]。

3.4 任务调度费用优先级与速率优先级

假设任务Ti为任务集T中第i个被调度的任务,任务ti对应资源集中资源k的调度费用如式(8)所示。

而在此任务被调度之前有i-1个任务已经被调度,设之前被调度的任务其总耗费为Cbefore、任务总长度为Lbefore、调度跨度为Sbefore,则在此任务被调度以后,调度总耗费相应会增加,为Cbefore+Ci,k,任务总长度l增加为Lbefore+li,则此时的任务调度平均长度耗费Averagei如式(9)所示。

由于资源集中不同的资源其价格也不同,因此对于不同的资源,其对应的耗费也不同,也就是说在式(9)中Ci,k的值随着选择的资源不同而不同,因此,Averagei的值取决于任务Ti被分配到的资源价格,显然Averagei与用户预算费用越接近,用户则越满意,设Budget为用户费用预算,Costsim为任务Ti分配以后总体调度平均长度耗费与用户预算的近似度,设Costsim={Costsim1,Costsim2,…,Costsimm-1,Costsimm},综合式(9),可得Costsimk如式(10)所示。

在调度过程中,优先将任务调度至此近似度值大的资源上,最终所获得的任务调度平均长度耗费将是一个与用户费用预算近似的值,从而很好地满足用户的需求。对于优先级的计算如下:根据资源集中资源的数量m,设置m个优先级,每个任务调前,按照式(10)进行计算,得到m个近似值,按照近似值的大小排序,近似值最小的赋予最小的优先级,然后资源优先级的大小按照顺序依次递增。

若仅考虑用户预算方面的因素,以上的优先级调度可以很好地满足用户的需求,但是一般来说,对于一个任务集的调度,用户所关注的并不仅仅是费用一个方面的因素,任务集处理的时间跨度也是其考虑的重点因素之一。本文以上述定义为基础,设资源集中各资源处理所分配到的任务所需的时间集为ProcessTime,ProcessTime={Proc1,Proc2,…,Procm},设在任务Ti被调度前,资源处理时间集为ProcessTimei-1,则此时的调度跨度Sbefore应该为ProcessTimei-1中的最大值max(ProcessTimei-1),在任务Ti被调度后,其对应的调度主机上的运行时间会相应增加,从而对跨度的大小产生影响。设Ti调度到资源上后对应的跨度集为Span,Span={Span1,Span2,…,Spanm},对跨度集合进行大小排序,然后根据其顺序来为资源分配跨度优先级,设优先级为Ps,若跨度值大小一样,则处理时间较小的资源优先调度。

由上文可知,对于任务Ti,其调度到资源的费用优先级为Pc,跨度优先级为Ps,则将2个优先级进行加权运算,得到任务的实际调度优先级p如式(11)所示。

其中,0＜a＜1为加权系数。则当a=0时,该算法为完全考虑调度跨度的策略,当a=1时,该算法变为仅考虑调度费用的调度策略,当a去中间值时,则为综合考虑2个因素的调度策略。本文取a的值为5.2,表示调度过程中,任务分配优先考虑费用预算,其次考虑跨度。

3.5 算法调度流程

基于以上定义,算法的具体调度过程的步骤如下:

Step 1 对任务集中的任务按式(3)进行优先级计算,并对所有任务按照优先级值的大小进行排序;

Step 2 取出队首也就是优先级最高的任务;

Step 3 根据式(11)计算资源优先级;

Step 4 将任务分配给优先级最高的资源;

Step 5 从任务集中删除该任务;

Step 6 判断任务集中是否还有任务,若有则返回Step2,否则,调度完成。

4 仿真实验与结果分析

本文对上述基于优先级的网格调度算法,结合Min-Min算法以及原机制所采用的调度策略进行实验,在此节中对这3种策略的调度结果进行展示并作出对比和分析。

4.1 实验环境

操作系统:Windows xp 32 bit;

内存:4.0 GB;

处理器:Intel(r)Core(tm)2Duo CPU,2.53 EHz;

集成开发工具:Eelipse6.5;

jdk版本:1.5;

仿真工具:Girdsim4.1;

数据库:Oracle9i。

4.2 GridSim仿真工具简介

GridSim由澳大利亚墨尔本大学Rajkumar Buyya领导开发,它用Java语言开发,是一种模拟网络资源的仿真工具,其主要用于研究基于计算经济模型的有效资源分配方法。是网格计算研究中使用最为广泛的工具之一。

4.3 仿真环境配置

4.3.1 资源的建立

使用GridSim建立5个价格和处理速率都不同的资源,对资源的处理能力、网络带宽,以及资源单位时间的价格进行初始化。将本地资源调度策略设置为SPACE_SHARED,这种策略的思想为先到达的任务先处理,后到达的任务等待前面的任务完成以后再开始处理。资源的相关配置如表2所示。

表2 资源配置

4.3.2 任务集的建立

生成5个任务集进行实验,其任务集中包含的任务数量依次为200,500,1 000,1 500,2 000。在GridSim中对于任务生成,其最主要的初始化元素为任务长度,实验中在区间[5,20]内随机取一个值作为任务的长度,单位为MIP(兆指令)。仿真基于这5个任务集,对基于优先级的调度算法、Min-Max算法和原机制的调度策略进行对比实验。

4.4 实验结果及分析

根据表2所示的资源配置,结合式(6)与式(7)可得出预算费用的区间应为[0.5,0.567]。实验中以0.002为间隔在费用预算区间内取样作为预算费用进行调度仿真。

图3为基于特定预算费用下平均长度耗费的均值。可以看出,最终耗费与费用预算基本上呈线性关系,且两者的值极为接近,其精确度达到1‰,所以,经过算法的调度,其最终的调度费用将会得到用户较好的认可。

图3 费用预算下的最终调度费用平均值

图3数据表明,本文算法在费用预算方面具有不错的性能,能够很好地满足用户的需求,而用户对于其费用需求得到满足的情况下,任务处理的速率也是其关注的重要因素之一。

在不同费用预算下任务的调度跨度结果如图4所示。可以看出,随着费用预算的增大,本文算法对任务的调度跨度随之减小。当接近最小费用预算时,其任务处理跨度值较大,从而任务被较快地执行。

图4 不同费用预算下的调度跨度

而当费用预算为0.567时,本文算法得到最优速率执行跨度,将其与Min-Max算法和原机制调度策略进行对比实验,结果如图5所示。

从以上结果可以看出,本文算法在跨度方面具有较好的性能,而且与原机制的调度策略相比,它在跨度方面优势较为明显,将本文算法应用与该容错机制中,能明显提高系统的运行效率,在任务到达时,能够以更快的速率得到处理。

由图6可以看出,本文算法的错失数量明显低于其余两者,这是由于本算法考虑到任务剩余执行时间的调度结果所致,而Max-Min算法在此之后的任务错失率在三者中为最高,这种结果产生的原因在于Max-Min算法优先对任务长度较大的任务进行调度,以致占用了大量的任务处理时间,使得同一时间内被处理的任务数量减少,并且算法完全未考虑服务质量方面的因素,故使得其在任务完成率方面表现较差。

图5 3种算法的调度跨度

图6 3种算法任务错失数量占总价值比例

从任务实现价值占总任务价值的比例结果来看,3种算法对200个任务的任务集的总价值实现率都在100%,本文算法随着任务错失率的增加,其价值的实现率较其他两者明显要高,从而表明优先对价值密度大的任务进行调度,进一步提高了算法的服务质量,具体如图7所示。

图7 3种算法任务实现价值占总价值比例

从以上的仿真实验结果可以看出,较原机制的调度策略而言,本文算法在任务完成率、价值实现率、任务处理速率等多方面均有较大改善,故利用此算法对原机制进行改进,系统将具有更好的可用性。

5 结束语

针对传统基于任务数量的平均调度在跨度、服务质量等方面存在的缺陷,提出基于优先级的网格调度算法对原机制进行改进。通过对本文算法、原机制调度策略以及Max-Min算法的三者进行对比实验及分析,证明算法在服务质量、任务处理速率方面具有较好的性能,能够有效提高系统任务执行的效率。下一步可针对算法在费用预算方面的特性做进一步的应用,若根据系统负载的情况,动态调整费用预算,在负载较低时,降低费用预算,将任务优先分配到成本较低的节点上,使成本高、速率快的节点能节省更多的资源来处理其他事务。反之,增加费用预算,保证任务的完成率。

[1] Rosenberg A L,Yurkewych M.Guidelines for Scheduling SomeCommon Computation-dagsforInternet-based Computing[J].IEEE Transactions on Computers,2005, 54(4):428-438.

[2] 蒲 英,马满福,牛增轩.网格调度中的QoS参数容错[J].计算机工程,2011,37(7):44-46,49.

[3] 张海宾,唐琳莎,刘立祥.网格调度综述[J].计算机工程与设计,2009,30(9):89-94.

[4] Shu Wanneng,Wang Jianqing.Min-Min Chromosome Genetic Algorithm for Load Balancing in Grid Computing[J].International Journal of Distributed Sensor Networks,2009,5(1):157-163.

[5] van Peteghem V,Vanhoucke M.A Genetic Algorithm for the Preemptive and Non-preemptive Multi-mode Resource-constrained Project Scheduling Problem[J]. European Journalof OperationalResearch,2010, 201(2):409-418.

[6] Sulistio A,Cibej U,Venugopal S,et al.A Toolkit for Modeling and Simulating Data Grids:All Extension to GridSim[J].Concurrency and Computation:Practice and Experience,2008,20(13):1591-1609.

[7] 罗宇平.基于Min-Min改进后的网格调度算法[J].微电子学与计算机,2009(3):71-75

[8] 田生伟,吐尔根·依布拉音,禹 龙.基于动态预测和任务流整形的网格调度算法[J].计算机工程,2008, 34(8):120-122.

[9] He Xiaoshan,Sun Xianhe,Laszewski G.QoS Guided Min-Min Heuristic for Grid Task Scheduling[J].Journal of Computer Science and Technology,2003,(4):249-253.

[10] 徐奕奕,唐培和,郑庆华.基于多目标权衡的数据网格作业调度算法[J].广西工学院学报,2013,(4): 61-63.

[11] 莫 赞,谢 娜,贾功祥,等.基于多QoS需求驱动的网格资源调度研究[J].计算机应用研究,2012, 29(10):3904-3925.

[12] 刘刚国,罗省贤.基于指标体系的网格调度算法研究与实现[J].计算机工程与应用,2012,48(15):97-101.

编辑 金胡考

A Grid Scheduling Algorithm Based on Priority

LIAO Da-qiang1,ZOU Du2,YIN Jian3
(1.Information Center,Nanhua College of Industry and Commerce,Guangzhou 510507,China;
2.Guangdong Key Laboratory of Computer Network,South China University of Technology,Guangzhou 510640,China;
3.School of Information Science and Technology,Sun Yat-Sen University,Guangzhou 510275,China)

The average scheduling strategy based on task numbers in fault-tolerant has shortcoming such as processing span and Quality of Service(QoS).Aiming at this problem,this paper proposes a grid scheduling algorithm based on priority,and then puts forward the design scheme of the hierarchical cluster system.The algorithm introduces the task in the process of task scheduling,task execution time remaining concept value density,cost budget and span,to make up for the task scheduling in the treatment of two span and QoS.Experimental results show that the algorithm has better effect in the completion rate,value realization rate,treatment rate compared with the original mechanism of scheduling strategy and Max-Min algorithm.The original mechanism is improved by using this algorithm.It can effectively improve the efficiency of system task execution,and the availability of system.

task scheduling;value density;cost budget;processing span;high availability;grid computing

1000-3428(2014)10-0011-06

A

TP393

10.3969/j.issn.1000-3428.2014.10.003

广东省教育研究院教育研究课题基金资助项目(GDJY-2014-B-b243)。

廖大强(1984-),男,讲师、硕士,主研方向:高性能计算,并行分布式计算;邹 杜,副教授、博士;印 鉴,教授、博士、博士生导师。

2014-01-22

2014-03-17E-mail:liaodaqiang@gmail.com

中文引用格式:廖大强,邹 杜,印 鉴.一种基于优先级的网格调度算法[J].计算机工程,2014,40(10):11-16.

英文引用格式:Liao Daqiang,Zou Du,Yin Jian.A Grid Scheduling Algorithm Based on Priority[J].Computer Engineering,2014,40(10):11-16.