一种基于GridSim的网格任务调度算法，冯美来，李春林，在网格环境中调度用户的作业，并把作业分配给适当的网格资源去执行，调度策略起着非常重要的作用。一个好的任务调度算法必须减少
国科技论文在线 http://www.paper.edu.cn 度则有107MI,长度则超过所选取的资源的处理能力(99MI)。当前4个用户任务组成个 粗粒度的仁务时,调度程序将分配给这个粗粒度任务一个唯一的标识号(D)。然后将选择另 外一个资源并且重复以上同样的成组过程。这个过程只到用户任务都组成一些粗粒度的任务 后才结東。最后,调度程序把这些组成组的粗粒度任务送到所选取的资源上去进行计算 2算法实现 假设网格环境中有四个资源R1~R4,它们的处理速率分别为:200MIPS、160MIPS、 210MIPS、480MIPS,而每秒的处理成木分别为:100、200、300、210(单位: CostEr Second) 任务的平均长度为200M,任务成组的间隔时间为30秒67。在 Gridsin13网格仿真平台上 设法在间隔时间内完成最大的150个作业。如果有25个作业需要调度完成,用任务成组算 法把作业打包成个粗粒度任务,则R1资源的处埋能力为6000(200*30)MI,因此,任务 完成时间为64秒,其中额外时问开销为规定的10秒,任务成组、调度和分配作业的时问开 销为54秒。在无任务成组算法的前提下,25个任务在资源R1上同步的执行,则总的额外 的时间开销为250秒(25*10),从而总的任务完成时间为280秒。具体的调度结果如图2.1 所示。 表2任务成组与非任务成组算法实现 任务数日 任务成组 非任务成组 作务组数 处理时间 处理成本 处理时间 处理成本 25 64 4979 280 933 50 15992 561 38946 75 35904 838 73485 100 4 136 55332 l112 97741 125 186 72332 1388 115673 l50 90124 1662 l34843 仟务平均长度:200任务长度偏差:20%时间间隔:30scc资源处坦速率:200、160、210、480额外时间 开销:10sec 由表2可以看出,不同的任务数可以组成不同的任务组(粗粒度任务),但是最多只能 组成四个仟务组,因为假设的前提条件只有四个资源。组成的四个任务组(粗粒度仟务)可 以分别送交到四个资源上去进行计算,这样可以节省任务的完成时间。 3性能分析 由图3可知,随着作业数目的增加,因为作业间交互的时间丌销的增加,非任务成组(细 粒度任务)的调度策略使得任务的处理时间直线上升。与之相对应的是仁务成组(粗粒度任 务)的调度策略,作业之间交互的时间开销保持在一个常数的范围内,上要的时间开销用在 资源在任务的计算上。如表2中的任务数为150时,按照任务成组的调度策略可以分为四个 仟务组(粗粒度任务),而每个资源可以分型到一个粗粒庋的仟务,因此,总的仟务处理的 时间开销之中的1.48%用在任务的传输上,而在仿真试验中,非任务成组的调度策略中,90.3 %的任务处理时间被用在冋样的任务送交的传输上。 对」任务的计算成木,如图4,总的计算成木开销也要考虑到每个任务在资源上的处理 吋间丌销。在对任务成组的模拟中,只有数目很少的任务(粗粒度任务)被送到资溟上去进 行计算,从而减少了额外的时间开销。同样的对于非仁务成组的调度略,每个细粒度的任 务在资源上都有一定的额外的时间开销,因此随着细粒度任务的增多,就造成了资源在处理 国科技论文在线 http://www.paper.edu.cn 细粒度仼竻的额外时间廾销的增加,也造成了资源的处理成本的增高,这样就是资源的利用 率没有达到最优,造成了对资源的浪费。比如说,当25个任务分别各自送到资源上去进行 计算时,总的处理成本为9333个单位成本,而对于任务成组的计处成本却只有4979个单位 成本 任务成组/非成组调度策略的时间开销 任务成组/非成组调度策略成本开销 150000 把 一粗粒度任务 100000 粗粒度任务 1000 细粒度任务 50000 一细粒度任务 作业数 作业数 图3任务成组/非成组调度策略的时间开销 图4任务成组/成组调度簧略成本开销 4总结 在用户作业都是大量细粒度的任务(长度小,对资源的计算能力的要求不是很高)时, 任务成组的调度策略在降低任务的计算时间和计算成本方面可以得到很大的提高。发送每个 细粒度的任务到资源上,从资源接收任务,都会增加总的传输时冋廾销和成木。另外,当资 源接收到一个细粒度的任务时,它的处理能力总是达不到最优的利用。任务成组的调度策略 就是针对这种情况的不足之处提出来的,它根据有效資源的处理能务扣用户绀粒度的仼务组 成数目少的粒粒度任务,目的是为了减少任务的额外传输时间开销和每个用户作业的额外处 理时间开销,从而提高资源的利用率。 参考文献 [1]. Abramson, D, Buyya R and Giddy, J. (2002): AComputational Economy for Grid Computing, and its Implementation in the Nimrod-G Resource broker Journal of Future Generation Computer SystemS(FGCS) I8(8):1061-1074. [2]. Berman, F, Fox, G. and Hey. A.(2003): Grid Cumpnutling-Making the Globul Infruslruclure a Reality London, Wilcy [3]. Buyya, R and Murshed, M. (2002): GridSim: A Toolkit for the Modeling, and Simulation of Distributed Resource management, and Scheduling for (irid Computing. ournal of Concurrency and Computation: Practice and Experience(CCPE), 14(13-15): 1175-1220 [4]. Buyya, R, Date, S, Mizuno-Matsumoto, Y, Venugopal, S and Abramson, D(2004): Neuroscience Instrumentation and Distributed Analysis of Brain Activity Data: A Case for eScience on Global Grids Journa of' Concurrency and Compulation: Pracice and Experience,(accepted in Jan. 2004 and in print) [5]. Fostcr, I and Kcssclman, C(1999): The Grid: Blueprint for a New Computing Infrastructure. San Francisco. Morgan Kaufmann Publisher, Inc 16]. Giray,J(2003): Distributed Computing Economics. Newsletter of the /E Task Force on Cluster Computing, 5(1), July/August [7]. James, H. A, Hawick, K. A. and Coddington, P. D(1999): Scheduling Independent Tasks on Metacomputing Systcms. Proc. of Parallel and Distributed Computing(PDCS 99), Fort Laudcrdalc, USA [8]. Logendran, R, Carson, S and Hanson, E (2002): Group Scheduling Problems in Flexible Flow Shops. Proc Of the Annual Conference of Institute of Industrial Engineers, USA 国科技论文在线 http://www.paper.edu.cn Algorithm for Task scheduling based on gridsim Feng Meilai, Li Chulin Wuhan Univ of Tech, Wuhan (430063) Abstract Scheduling strategy plays an important role in the grid environment to schedule the user jobs, and dispatch them to appropriate Grid resources. A good taskscheduling method is needed to reduce the total time taken for job execution in the Grid. The main purpose of this project is to use the GridSim Toolkit to model coarse-grained grid application by developing an efficient, and effective task scheduling method. The performance of this new scheduling algorithm, achieving lower job completion time and satisfying user's Qos demand, is demonstrated by its implementation on Gridsim. Keywords: coarse-grained, Gridsim, Scheduling 作者简介: 冯美来,1975年生,女(汉族),湖北武汉人,武汉理工大学讣算机学院研究生,主婁从事刈 格计算与研究; 李春林,博士,副教授,矶究方向为网格计算与研究。 5-