计算密集型与数据密集型混合网格作业调度算法*

郝永生，卢俊文，刘冠峰，温 娜

(1.南京信息工程大学网络信息中心,江苏 南京 210044;2.厦门理工大学，福建 厦门 361024；3.苏州大学先进数据分析研究中心，江苏 苏州 215006；4.南京信息工程大学大气科学学院，江苏 南京 210044)

计算密集型与数据密集型混合网格作业调度算法*

郝永生1，卢俊文2，刘冠峰3，温 娜4

(1.南京信息工程大学网络信息中心,江苏 南京 210044;2.厦门理工大学，福建 厦门 361024；3.苏州大学先进数据分析研究中心，江苏 苏州 215006；4.南京信息工程大学大气科学学院，江苏 南京 210044)

针对计算密集型作业与数据密集型作业混合情况，在一个作业有时间限制的动态环境中，对传统的网格作业调度方法进行扩展，提出了三种网格作业调度启发式算法:Emin-min、Ebest、Esufferage。并在一个由多个Cluster组成的、通过高速网络连接的网格模型上，对三种算法进行验证。与Min-min算法的比较结果显示：三种算法均优于Min-min算法。与ASJS算法比较结果显示：Emin-min减少了等待时间与作业的makespan; Esufferage算法以减少作业完成量为代价，减少了作业的等待时间及makespan; Ebest在完成作业数量上与ASJS基本保持一致，但却增加了作业的等待时间与makespan。总体上，Emin-min具有比较大的优势。

计算密集；数据密集；作业调度；平均执行时间

1 引言

传统的网格作业调度算法，或者是针对计算密集型作业[1,2]，或者是针对数据密集型[3,4]作业,只有少数网格作业调度算法同时考虑这两种作业[4,5]。

基于计算密集型的网格作业调度方法包括：Min-min、Max-min、Sufferage、Fast-fit、Best-fit等[1,2]。Min-min的思想是：计算参与映射事件的每个任务在各个机器上的期望完成时间，找到每个任务的最早完成时间及其对应的机器；从中找出具有最小最早完成时间的任务，将该任务指派给取最小完成时间的机器，直至所有作业完成。Max-min算法非常类似于Min-min算法，同样要计算每一任务在任一可用机器上的最早完成时间，不同的是Max-Min算法首先调度大任务，即选择最早完成时间最大的任务映射到所对应的机器上。Sufferage通过计算每个作业Sufferage值，再选择使Sufferage值最大时的作业-资源配对进行分配。一个作业的Sufferage值指这个作业最小完成时间与次小完成时间的差，其值部分反映了如果不进行这样分配带来的损失。Fast-fit试图将作业分配给最快的资源节点。Best-fit总是分配给最适合的作业，即在确保完成时间(Deadline)的情况下，尽量推迟作业的完成时间。

Venugopal S[3]针对数据密集型作业提出了一种基于集合覆盖问题(Set Covering Probelm)的调度算法。任务由若干作业组成，不同作业需要访问不同的数据块，通过不同策略复制这些数据块，达到提高执行速度的目的。Kolodziej J等人[4]从数据复制、数据分割、数据权限控制、数据传输等方面对数据密集型作业进行了分析，提出了数据感知模型(Data-Aware Schedulers)，并与传统的数据调度算法相结合，以适应数据密集型作业调度的要求。Chang R-S等[5]提出了一种自适应的评分机制ASJS(Adaptive Scoring Job Scheduling algorithm)，根据资源的特性及网络特性对资源评分，优先分配给得分高的资源。Valliyamma C[6]认为资源调度就是一种交易，交易双方既考虑资源本身的特性(处理器速度、内存、硬盘等)，又考虑网络特性(带宽、数据丢失率等)，双方依据这些特性进行资源分配。一些基于QoS(Quality of Service)[7]的网格作业调度算法既可用于计算密集型作业，又可用于数据密集型作业，他们往往将作业的指令数量和输入输出文件的大小、资源的处理速度及网络带宽当作不同的属性进行分配调度。

考虑作业的时间(Deadline)[8,9]限制，使计算密集型与数据密集型作业混合情况下的调度问题变得更加困难。本文详细分析了计算密集型与数据密集型作业混合情况下的网格作业调度问题，通过对传统的网格作业调度算法进行扩展，提出了三种调度算法：Emin-min、Ebest、Esufferage。并在Gridsim平台上，与ASJS及Min-min算法进行了比较，分析了其各自的特点。选择这两个算法进行比较的原因是：Min-min算法在过去的验证中显示了比较好的性能，而ASJS算法适合于处理多种作业混合情况下的调用。

2 网格模型

我们采用的网格模型与文献[5]的基本相同。假设用户与路由器、Portal、Job Scheduler之间由高速网络互连(如图1所示)。图1中p是数据密集型作业的比率，则计算密集型作业的比率为1-p。对于数据密集型作业，根据其文件大小又可分为大数据密集型作业(简称大作业)及小数据密集型作业(简称小作业)。q是大作业的比率，则小作业的比率为1-q。就全部作业而言，大作业的比率为pq，小作业比率为p(1-q)。为讨论方便，做如下假设：

文件大小在[1 500 MB，3 000 MB]为大文件，其概率为q；

文件大小在[500 MB，1 500 MB]为小文件，其概率为1-q。

作业的文件大小是指输入输出文件大小之和。对于多个输入输出文件当作一个文件对待。

Figure 1 System model图1 系统结构

作业的描述如下:jobi(ini,fsize,deadline,avi)。jobi.ini、jobi.fsize、jobi.deadline、jobi.avi分别指作业的指令数量、作业输入输出文件大小、作业的时间期限及作业到达时间。对于计算密集型作业，其输入输出的文件大小为0。资源描述如下:rj(proc,bw,avai)。rj.proc、rj.bw、rj.avai分别指资源的处理速度、网络带宽及空闲的时间点。假设所有资源都是空间共享(space-shared)型,即同一时间内，一个资源只能被分配一个作业。

jobi若分配给rj，其执行时间Ext(i,j)为：

(1)

rj的开始空闲时间为rj.avai，若jobi分配给rj，则jobi的完成时间c(i,j)为：

c(i,j)=Ext(i,j)+rj.avai

(2)

为确保作业在时间期限(deadline)前执行完成：

(3)

如果jud(jobi,rj)的值为1，则jobi可以在rj上按照deadline要求执行；否则,不能执行。

若系统真正将jobi分配给rj，则资源rj再次可接收作业的时间rj.avai为:

rj.avai=Ext(i,j)+rj.avai

(4)

rj.avai表示资源分配作业后，下次可接收作业的时间。实际上，由于准确估计作业的执行时间是比较困难的，在实际系统中，这个值以作业完成时间为准。

作业数量为jend，所有作业集合为：

(5)

资源数量为rend，所有资源集合为：

(6)

更一般地描述，假设每个作业有l个属性(这里的属性可以包括带宽、内存、CPU速度等)，则J描述如下：

(7)

同样，资源也具有l个属性,资源描述如下：

(8)

RJ是一个l×l矩阵，若资源ri的所有属性均满足jobj的要求，则RJ(i,j)=1;若ri存在属性不能满足jobj的要求，则RJ(i,j)=0。jobj在ri上可以被执行的条件是：

(∀temp)ri.atttemp>jobj.atttemp,1

(9)

根据公式(3)，令：

RJ(i,j)=jud(jobi,rj)

(10)

3 具有截止时间的作业调度算法

在网格中，作业调度问题是一个NP问题，一般借助启发式算法解决。传统的以最小作业完成时间为目标的批处理启发算法包括Min-min、Max-min、Fast-fit、Best-fit、Sufferage等等。本节以Min-min、Best-fit、Sufferage算法为框架，提出了计算密集型作业和数据密集型作业混合情况下的三种启发式算法，即Emin-min、Ebest、Esufferage。

在考虑到作业具有deadline的情况下，采用紧迫型作业优先调度原则，即如果能保证作业在deadline前完成的资源有限，那么立即调度这个作业。实际应用中，以可以按要求执行这个作业的资源比率rrat为准。如果小于这个比率，那么这个作业是紧迫型作业，立即执行。

3.1Emin-min

算法思想：首先根据公式 (1)和公式(2)，对每个作业计算在各个资源上的完成时间，取最小值的作业-资源对进行分配，更新被分配资源的下次可用时间Ext(i,j)，直至所有满足条件的作业被完成。这里满足条件是指先前能被执行的作业，有些作业因为有deadline要求，等待时间超过期限，导致不能被执行。

算法1Emin-min

输入：资源集合R及作业集合J;

输出：作业分配方案。

1.Do

2. minvalue=0;

3. selectr=-1;

4. selectj=-1;

5.Foreveryjobi∈J

6.Foreveryrj∈R

7. 计算 jud(jobi,rj)；

8.Ifjud(jobi,rj)==1

9. 计算Ext(i,j)；

10.If(minvalue> Ext(i,j))

11. selectr= rj;

12. selectj= jobi;

13. minvalue= Ext(i,j);

14.Endif

15.Endif

16.Endfor

17.Endfor

18. 将selectj分配给selectr；

19. 更新selectj.avai;

20. 对紧迫型作业进行调度；

21.While(所有适合要求的作业都被完成)

算法中，minvalue用于记录最小的完成时间，selectr和selectj分别记录最小完成时间时所选择的资源和作业。第2～第4行是算法初始化，第5～第7行寻找执行时间最小的资源-作业配对，第18～第20行完成资源分配。

3.2 Ebest

为了得到一个更好的调度效果，使更多的作业能被执行，我们优先考虑时间期限紧迫的作业。jobi若分配给rj，其执行完成时间为c(i，j)，其与jobi.deadline的差距ts(i,j)反映了这个作业的紧迫程度。

ts(i,j)=jobi.deadline-c(i,j)

(11)

若ts(i，j)<0，则说明这样分配不能保证作业在指定时间内完成，选择其值为非负且最小的作业-资源进行映射。算法描述如下:

算法2Ebest

输入：资源集合R及作业集合J;

输出：作业分配方案。

1.Do

2. minvalue=0;

3. selectr=-1;

4. selectj=-1;

5.Foreveryjobi∈J

6.Foreveryrj∈R

7. 计算ts(i,j)；

8.If((minvalue> ts(i,j) &ts(i,j)>=0) )

4. selectr= rj;

5. selectj= jobi;

6. minvalue= ts(i,j);

7.Endif

8.Endfor

9.Endfor

10. 将selectj分配给selectr；

11. 更新selectj.avai;

12. 对紧迫型作业进行调度；

13.While(所有适合要求的作业都被完成)

这里可以将作业的deadline当作作业一个属性处理，此作业在某个资源上的完成时间当作这个资源的一个属性对待。第2～第4行是算法初始化，第5～第7行寻找使公式(11)取最小值的资源-作业配对，第15～第17行完成资源分配。

3.3 Esufferage

算法思想：分别计算每个作业的最小完成时间和次小完成时间，选择两者值相差最大的作业-资源进行配对。

算法3Esufferage

输入：资源集合R及作业集合J;

输出：作业分配方案。

1.Do

2. maxvalue=0;

3. selectr=-1;

4. selectj=-1;

5. first(i)记录jobi最小完成时间；

6. second(i)记录jobi次小完成时间；

7.Foreveryjobi∈J

8.Foreveryrj∈R

9. 计算c(i,j)；

10.Endfor

11.Endfor

12. 计算first(i),i∈{1,2,…,jend}；

13. 计算second(i),i∈{1,2,…,jend}；

14.Foreveryjobi∈J

15.If(maxvalue<(second(i)- first(i)) )

16. selectr= rj;

17. selectj= jobi;

18. maxvalue=max(second(i)-first(i));

19.Endif

20.Endfor

21. 将selectj 分配给selectr；

22. 更新selectj.avai;

23. 对紧迫型作业进行调度；

24.While(所有适合要求的作业都被完成)

maxvalue记录最小完成时间与次小完成时间差的最大值。first(i)、second(i)分别记录jobi最小完成时间及次小完成时间。第2～第4行是算法初始化，第5～第13行计算每个作业的最小完成时间和次小完成时间，第14～第20行寻找最小完成时间与次小完成时间的最大差值，第21～第23行进行资源分配并更新资源状况。

4 仿真实验

4.1 仿真环境

采用Gridsim[10]作为模拟器，Gridsim可以实现比较复杂的网格调度模拟。基于HaoY等人[8]先前的工作，对于Gridsim进行了关于时间期限的扩展。因此，采用Gridsim模拟数据密集型作业和计算密集型作业的混合调度。

作业数量为10 000，作业到达速率为20、22、24、26、28、30。数据密集型作业的比率(p)为0.30、0.50、0.70。大数据密集型作业比率(q)为0.30，0.50，0.70。作业需要传输的文件大小(jobi.ini)是[500，3 000](单位：百万条指令)的一个整数，大数据密集型作业的文件大小(jobi.fsize)是[1 500MB,3 000MB]的一个随机整数，小数据密集型作业的文件大小(jobi.fsize)是[500MB，1500MB]的一个随机整数。系统有50个资源节点。资源带宽(rj.bw)是[1.1，1.2，1.3，1.4，1.5]中的一个数值(单位Gs)，资源处理速度是[5，15]的一个随机整数。作业的deadline是[1，5]的一个随机整数。这些参数均服从均匀分布。模拟结果是10次模拟所得平均数。在实验中采用紧迫型作业优先调度原则，令rrat=20%。ASJS对于资源的带宽属性和计算能力属性分配不同的权重，根据ChangR-S[5]的模拟结果，其权重取值如表1所示。

Figure 2 Average makespan of different arrival rates图2 不同到达率下的平均makespan AMJ

p计算能力权重带宽权重0.30.30.70.50.50.50.70.70.3

在模拟实验中，考察的参数包括：未完成的作业数量(UFJ)、平均等待时间(AWT)、平均makespan(AMJ)。makespan指从作业进入等待队列开始到作业被执行的时间。

4.2 仿真结果与性能分析

图2～图4分别描述系统的UFJ、AWT、AMJ。总体上，AWT、AMJ都随着作业到达速率、p、q的增加而增加，这是因为随着到达速率、p、q的增加，系统负载也随着增加，使作业的makespan及等待时间增大。当到达速率小于22时，各个算法的完成数量总体保持相同；当到达速率超过26后，各个算法未完成作业数量的增加速度明显加快，这是因为系统趋于过载状态，不能在有效时间内完成的作业越来越多。

AMJ(图 2)与AWT(图 3)具有相同的趋势。总体上，平均等待时间与makespan随着到达率的增加而增加。这是因为系统负载的增加延长了作业的等待时间和执行时间。这五种算法的AMJ及AWT值从大到小的顺序是：Min-min、ASJS、Ebest、Emin-min、Esufferage。与Min-min相比、Ebest、Emin-min、Esufferage三种算法的执行时间分别减少了8.32%、15.51%、24.20%。

未完成作业的数量随着p、q及到达率(ArrivalRate)的增加而增加。Min-min算法具有最大的未完成作业数量(如图4所示)。与Min-min相比、Ebest、Emin-min、Esufferage三种算法的未完成作业数量分别减少了18.74%、22.18%、5.33%。这是因为Min-min没有考虑到资源的特性及作业的deadline，所以表现较差。Eminmin、Ebest、ASJS算法的未完成的作业数量基本保持一致且均小于Min-min及Esufferage。

Esufferage以丢弃部分作业为代价获得了最小的makespan和等待时间(图2和图3中，Esufferage的AMJ和AWT均保持最小值)。Ebest由于总是尽量推迟作业的执行时间，导致了作业的等待时间与makespan值最大，但同时也保证了系统完成的作业数量增加(图2和图3中，Ebest具有较大的AWT和AMJ。图4中，Ebest具有较小的UFJ)。

Figure 3 Average waiting time of different arrival rates图3 不同到达率下的平均等待时间AWT

Figure 4 Unfinished job number of different arrival rates图4 不同到达率下的平均未完成作业数量UFJ

ASJS采用最高评分的方式选取资源，这在计算密集与数据密集型作业情况下选择“最快”的策略基本相同。所以，Emin-min与ASJS在各个参数上均有近似的表现(如图2～图4所示)。 Emin-min与ASJS的平均等待时间AWT、平均执行时间AMJ、未完成作业的平均比值分别为：0.9645∶ 1，0.9828∶1，1.0155∶1。ASJS的评分虽然具有动态性，但并没有考虑资源的特性，评分高的资源，并不能保证所有作业都适合执行。如果一个具有大的输入输出文件的作业被分配到一个带宽小却具有快速处理能力(资源评分高)的资源节点上，那么这个作业也不能在很短的时间内完成，导致了作业执行时间增加。采用紧迫型作业优先调度的Emin-min算法，则在各个方面均表现出色。

5 结束语

本文提出了Esufferage、Ebest及Emin-min算法，用于混合作业的调度，并在模拟网格上对三个算法进行验证。仿真实验表明，Esufferage以少完成部分作业为代价，减少了等待时间及makespan；Ebest虽然具有比较大的等待时间及makespan，但却减少了未完成作业数量；Emin-min与ASJS相比，在保证完成作业的同时，减少了作业的平均等待时间和makespan。实验显示，这三种算法均优于传统的Min-min算法。

本文在动态环境下，对计算密集型作业和数据密集型作业进行了分析,但缺少对QoS[9]的研究。由于不同的用户对QoS有不同要求，对用户的QoS偏好[12]选择，也是一个需要进一步研究的课题。

[1] Maheswaran M,Ali S, Siegel H J, et al. Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop,1999:30-44.

[2] Braun T D,Siegel H J,Beck N,et al. A comparison study of static mapping heuristics for a class of metatasks on heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop, 1999:15-29.

[3] Venugopal S, Buyya R. An SCP-based heuristic approach for scheduling distributed data-intensive applications on global grids[J]. Journal of Parallel and Distributed Computing,2008, 68(4):471-487.

[4] Kolodziej J, Xhafa F,Barolli L, et al. A taxonomy of data scheduling in data grids and data centers:Problems and intelligent resolution techniques[C]∥Proc of 2011 International Conference on Emerging Intelligent Data and Web Technologies (EIDWT),2011:63-71.

[5] Chang Ruay-Shiung, Lin Chih-Yuan, Lin C F. An adaptive scoring job scheduling algorithm for grid computing[J]. Information Sciences,2012,207:79-89,DOI:10.1016/j.ins.2012.04.019.

[6] Valliyamma C,Somasundaram T S. A grid resource brokering strategy based on resource and network performance in grid[J]. Future Generation Computer Systems,2012, 28(3):491-499.

[7] Wang W, Luo J Z,Song A B. A GQoP guaranteed grid QoS adaptive scheduling algorithm[J]. Journal of Computer Research and Development, 2011,48(7):1168-1177.(in Chinese)

[8] Hao Yong-sheng,Liu Guan-feng,Wen Na. An enhanced load balancing mechanism based on deadline control on GridSim[J].Future Generation Computer Systems,2012.28(4):657-665,DOI:10.1016/j.future.2011.10.010.

[9] Li X, Hu Z G, Hu Z J, et al. Grid workflow scheduling algorithms based on deadline Satisfaction[J]. Journal of Computer Research and Development, 2011,48(5):877-884.(in Chinese)

[10] GridSim Toolkit 5.0,GridSim:A toolkit for modeling and simulating grid computing environments [EB/OL].[2013-05-01]. http://www.buyya.com/gridsim/.

[11] Albodour R, James A, Yaacob N. High level QoS-driven model for grid applications in a simulated environment[J]. Future Generation Computer Systems,2012, 28(7):1133-1144.

[12] Xiong Run-qun, Luo Jun-zhou, Song Ai-bo, et al. QoS preference-aware replica selection strategy in cloud computing[J]. Journal on Communications, 2011,32(7):93-102.(in Chinese)

附中文参考文献:

[7] 王巍,罗军舟,宋爱波.一种具有GQoP保证的网格QoS自适应调度算法[J].计算机研究与发展,2011,48(7):1168-1177.

[9] 李玺,胡志刚,胡周君,等.基于截止时间满意度的网格工作流调度算法[J].计算机研究与发展,2011,48(5):877-884.

[12] 熊润群,罗军舟,宋爱波,等.云计算环境下QoS 偏好感知的副本选择策略[J].通讯学报,2011,32(7):93-102.

HAOYong-sheng,born in 1980,MS,engineer,his research interest includes grid computing, and cloud computing.

卢俊文(1983-),男，福建厦门人，硕士，讲师，研究方向为网格计算和云计算。E-mail:swordmenstory@163.com

LUJun-wen,born in 1983,MS,lecturer,his research interests include grid computing, and cloud computing.

刘冠峰(1983-),男，山东青岛人，博士，副教授，研究方向为网格计算和云计算。E-mail:gfliu@suda.edu.cn

LIUGuan-feng,born in 1983,PhD,associate professor,his research interests include grid computing, and cloud computing.

Threegridjobschedulingmethodsheuristicsfordata-intensiveandcomputing-intensivejobs

HAO Yong-sheng1,LU Jun-wen2,LIU Guan-feng3,WEN Na4

(1.Network Center,Nanjing University of Information Science & Technology,Nanjing 210044；2.Xiamen University of Technology,Xiamen 361024;3.Soochow Advanced Data Analytics Lab,Soochow University,Suzhou 215006;4.College of Atmospherics Science,Nanjing University of Information Science & Technology,Nanjing 210044,China)

Most of the existing grid job scheduling methods focus on either data-intensive jobs or computing-intensive jobs.In the dynamic environment where every job has its deadline,we extend the traditional grid job scheduling methods to propose three new grid job scheduling methods:Emin-min,Ebest and Esufferage.The three methods are validated on the Grid model with clusters that are connected by the high speed network.Simulation results demonstrate that our proposed methods are better than Min-min.The comparison between the three methods and ASJS shows that,Emin-min reduces the waiting time and makespan,Esufferage reduces the waiting time and the makespan greatly with the sacrifice of some jobs,and Ebest gives the same performance in unfinished jobs but has a larger value in waiting time and makespan than ASJS. In general,Eminmin has a better performance than Min-min and ASJS.

computing-intensive;data-intensive;job scheduling;average makespan

1007-130X(2014)08-1423-07

2013-03-20;

：2013-05-20

福建省教育厅科技项目B类(JB09199)；国家自然科学基金资助项目(41005048)；科技部资助项目(GYHY201106037，GYHY200906023)

TP391.9

：A

10.3969/j.issn.1007-130X.2014.08.001

郝永生(1980-),男，安徽怀宁人，硕士，工程师，研究方向为网格计算和云计算。E-mail:hyslove@163.com

通信地址：210044 江苏省南京市南京信息工程大学网络信息中心

Address:Network Center,Nanjing University of Information Science & Technology,Nanjing 210044,Jiangsu,P.R.China