等价类划分的粗粒度任务调度算法

刘东领, 袁景凌,2,陈旻骋

1(武汉理工大学 计算机科学与技术学院, 武汉 430070) 2(交通物联网技术湖北省重点实验室 (武汉理工大学)，武汉 430070)

1 引 言

随着信息技术的飞速发展,大量的数据进入人们的视野,数据的日益增加,使得传统的数据处理方式已不再适用,于是基于大数据的处理手段—云计算[1]应运而生.在对云计算数据中心的优化研究中,节能的绿色数据中心[2]及高效的任务调度[3]算法是当前研究的重要方向.研究表明,任务调度是NP完全问题,它从m个任务分配到n个资源上的nm种可能中寻找最优解,从而得到最佳的调度性能.

目前,关于任务调度的算法有传统的Min-Min、Max-Min算法[4]和遗传算法.合理有效的任务调度算法是保证用户QoS的关键,也是研究人员和技术人员共同关注的一个热点话题,如文献[5]以时间作为衡量数据传输的标准,提出了一种动态调整数据副本个数的数据放置与任务调度算法;文献[6]以异构环境下多目标优化调度为目标,运用Memetic局部搜索算子的局部优化能力来提高算法的收敛速度.文献[7-9]运用模糊聚类将资源进行划分,根据任务参数在不同的聚类中选择资源,使任务选择性能较好的资源簇;文献[10]提出了一种模糊商空间理论的资源调度算法,结合模糊商空间理论建立模糊等价类和距离函数,进行资源分配;文献[11]提出了一种融合粒子群和遗传算法的改进算法,根据云计算环境特点对资源进行分类,以遗传算法来克服粒子群的局部最优问题,扩展粒子的搜索空间,减少任务的完成时间.

本文结合粗糙集相关理论,根据任务与资源的特点,通过建立合适的任务和资源模型,提出了一种等价类划分的粗粒度任务调度算法,主要工作如下:

1)对云计算环境下的任务和资源特点进行分析,选取任务和资源的一些关键特征属性,对其进行量化.使用等价类划分思想,给定属性划分依据和划分区间,对多样性的任务和资源进行粒度划分.

2)计算任务组和资源组的平均指令长度和执行能力,将任务调度分为两级调度模式:粒度间每个任务组采用按能力匹配的方式进行调度;粒度内,即每个任务组内具体任务采用贪心调度,最后完成实验对比分析.

2 问题建模及等价类划分

2.1 任务和资源模型

任务调度是将指定任务分配给合适的资源,调度性能会因任务资源属性的差异而不同,所以在调度前应对任务和资源进行建模.我们用三元组TS=(T,V,R)来表示云计算环境下的任务调度模型,T={t1,t2,…,tm}表示m个相互独立、无优先关系的任务集合,第i个任务可对其进一步细化特征ti={lengthi,osTypei,inSizei,outSizei},各特征描述如下:

①length:表示任务指令长度.

②osType:表示了任务执行时最优匹配的系统类型.

③inSize:表示任务的输入文件大小.

④outSize:表示任务执行完成后输出文件大小.

V={v1,v2,…,vn}表示资源的集合.第i个资源可表示为vi={mipsi,osTypei,rami,storagei,bwi},各特征描述如下:

①mips:表示虚拟机的执行能力MIPS.

②osType:表示了该虚拟机对应的系统类型.

③ram:表示虚拟机的容量.

④storage:表示虚拟机的内存,即随机存取存储器.

⑤bw:表示虚拟机的带宽.

R=[rij](1≤i≤m,1≤j≤n)代表任务ti在虚拟机vj上的运行时间,此处时间计算公式为:

(1)

2.2 等价类划分

等价类能按照多种规则对数据集进行划分,如按区间划分、按数值划分、按处理方式划分等.云环境下的任务和资源经过量化后,任务和资源序列可以近似的用一个决策表表示,而异构的任务和资源适合用等价类按区间划分的方式进行处理.

IND(P)={(x,y)∈U×U|∀a∈P,f(x,a)=f(y,a)}

关系IND(P)构成了U的一个划分,用U/IND(P)表示,简记为U/P,则满足[x]p={y|∀a∈P,f(x,a)=f(y,a)}关系的元素构成U/P上的等价类[12].

2)等价类划分:等价类划分是在任务调度前对任务和资源的预处理.表1代表了原始任务序列,结合上述等价类定义,对该任务实例进行等价类划分.

设置任务长度length的区间梯度为100,输入文件大小inSize和输出文件大小outSize的区间梯度为10,并用0、1、2代表三种系统类型.按照上述区间划分及分类标准,可将以上10个任务划分成以下等价类:

{{t1,t5},{t4,t6,t8},{t3,t7},{t2,t10},{t9}}

表1 原始任务序列表
Table 1 Original task sequence

任务特征属性lengthosTypeinSizeoutSizet1230112．716．8t2323023．226．9t3343224．127．4t4445130．835．6t5256114．819．3t6421132．237．5t7388222．525．8t8467134．839．1t9396132．538．3t10367021．125．0

3 等价类划分的粗粒度调度策略

3.1 粒度间能力匹配调度

设CGT(coarse-grain tasks)表示一个粗粒度任务组,CGV(coarse-grain vms)表示一个粗粒度资源组.则经过等价类划分后,任务模型和资源模型可表示为:

T={CGT1(t1,t2,…,ta),CGT2(t1,t2,…,tb),…,CGTm(t1,t2,…,tk)}

V={CGV1(v1,v2,…,vx),CGV2(v1,v2,…,vy),…,CGVn(v1,v2,…,vz)}

算法1. coarseGrainSchedule

输入:任务资源集合T={t1,t2,…,tm}、V={v1,v2,…,vn}

输出:任务组T={CGT1,CGT2,…,CGTm}调度方案

1.fortask←1toT.sizedo

2.CGTi←EqualClass_Algorithm(task)/*运用等价类,将任务序列划分成任务组CGTi(i = 1,2…m)*/

3.CGTi_avgLen←CGTLi/*计算CGTi平均长度*/

4.end

5.forvm←1toV.sizedo

6.CGVi←EqualClass_Algorithm(vm) /*等价类分组*/

7.CGVi_avgMips←CGVMi/*计算平均执行能力*/

8.end

9.sort_desc(CGT,CGTi_avgLen) /*任务组、资源组分别按平均指令长度和执行能力降序排列*/

10.sort_desc(CGV,CGVi_avgMips)

11.t,v←0 /*初始化任务组CGT和资源组CGV位置*/

12.whilet

13.STV(CGTt,CGVv)/*将CGTt分配给CGVv*/

14.v←(v+1)%CGV.Length/*循环遍历粒度任务组*/

15.t++/*任务组标识加一*/

16.end

3.2 粒度内贪心调度

贪心算法考虑到了任务和虚拟机之间配置不一样的情况,这样任务在不同虚拟机上执行的时间就不同.此时,根据贪心算法的思想,任务在选择虚拟机的时候使用贪心策略,确保每次选择的虚拟机都是最佳的.

结合文中实际任务及资源模型,运用贪心策略主要有以下几点合理性:贪心策略针对的是异构环境下的任务和资源,而文中设置的任务和资源模型是异构的;贪心算法的目标在于优化任务的执行时间,和任务的等价类调度目标一致;贪心算法具有灵活性,能根据具体不同的任务模型设置合适的贪心策略;贪心算法不仅能确保任务的总完成时间相对较优,也能兼顾每个资源组内的负载均衡[13].

在上述等价类划分的粒度间任务组调度中,假定任务组CGTm(t1,t2,…,tk)和资源组CGVn(v1,v2,…,vz)相匹配.用m=|CGTm|表示分解后任务的数量,ti表示第i个任务,各任务之间相互独立;用n=|CGVn|表示资源数量,vi表示第i个虚拟机资源.假设数据中心中的任务数量大于或等于虚拟机的数量(m≥n),一个任务只能分配给一个虚拟机执行,而且一个虚拟机在执行过程中,同时间段不能去执行其他任务.用上述定义的运行时间R[i][j]表示第i个任务在第j个虚拟机上的完成时间,则m个任务在n个虚拟机上的执行时间对应为一个m×n的矩阵,具体算法描述如下:

算法2.greedySchedule

输入:任务组CGTm(t1,t2,…,tk)和资源组CGVn(v1,v2,…,vz)

输出:任务组CGTm(t1,t2,…,tk)中每个任务的调度方案

1.CGTm←sortDescByLen(CGTm)/*按指令长度降序排序*/

2.CGVn←sortAscByMips(CGVn)/*按执行能力升序排序*/

3.R[m][n] /*初始化运行时间矩阵*/

4.vmLoad[i],vmTasks[i] /*记录虚拟机vi上任务运行总时间 及任务数*/

5.CGTm[0].setVm(CGVn[n-1])/*完成初始任务分配*/

6.fort1tomdo

7.bestLoc←n-1 /*记录当前最优虚拟机位置*/

8.minLoad←vmLoad[bestLoc]+R[t][bestLoc] /*记录最优分配值*/

9.forvn-2to0do

10.ifvmLoad[v] = 0then/*若当前虚拟机未分配任务*/

11.bestVm←CGVn[v] /*则直接分配*/

12.ifminLoad>vmLoad[v]+R[t][v]then

13.bestVm←CGVn[v] /*分配给负载少的虚拟机*/

14.minLoad←vmLoad[v]+R[t][v] /*更新minLoad*/

15.ifminLoad=vmLoad[v]+R[t][v]then

/*若同时最优,选任务数较少虚拟机*/

16.bestVm←min(vmTasks[v],vmTasks[bestLoc])

17.end

18.end

3.3 等价类划分的粗粒度调度模型

等价类划分的粗粒度任务调度算法采用了等价类对任务和资源进行粒度划分分组,每组任务按其平均指令长度分配给计算能力相匹配的资源组,同时在每组任务的内部调度过程中使用贪心算法.如图1所示,整个调度流程可分为三个步骤:

步骤1.运用等价类划分思想,对用户任务请求和云计算资源进行粒度划分;

步骤2.粒度间能力匹配调度,任务组和资源组按平均指令长度和执行能力匹配调度;

步骤3.粒度内贪心调度,指定每组任务内单个任务具体调度策略.

图1 整体调度流程图Fig.1 Overall scheduling process

4 实验设计及结果分析

4.1 实验环境

为验证基于等价类划分的粗粒度任务调度算法的可行性,本文选用了CloudSim云计算仿真平台.CloudSim是一个基于事件的仿真器,实体和实体间基于消息进行通讯,它使用户可以在一台主机上对大规模的集群进行仿真.实验基础环境包括:1)硬件:2.6GHz双核CPU、4GB内存、500G硬盘;2)软件:windows8.1操作系统、Eclipse开发环境、java编程语言.

4.2 任务及资源设置

本算法是基于异构环境下的算法,实验中我们假设数据中心主机的数量为100,且每台主机上只有唯一的一台虚拟机,任务的总数随实验次数动态设置.为了模拟不同的任务需要调度到特定的虚拟机上执行,我们对CloudSim中的Cloudlet类和Vm类进行了改写,为它们添加一个新的字段:系统类型(OS),表明任务需提交到和其OS类型相同的虚拟机上执行,否则会增加额外的时间开销.以下为虚拟机、任务参数设置:

虚拟机的MIPS(执行能力)和Bw(带宽)的范围是400-1000,OS类型考虑到三种情况:Linux、Windows和Mac,Ram和Storage设置为固定值.

任务长度的范围为20000-80000,OS类型同虚拟机有三种取值,inSize(输入文件大小)和outSize(输出文件大小)的范围为200-800.

4.3 仿真实验流程

步骤1.指定任务和虚拟机的数目及参数的取值范围,使用随机函数构建虚拟机和任务的参数列表文件.

步骤2.在CloudSim主流程中读取上述虚拟机和任务参数文件,创建虚拟机列表和任务列表并提交到数据中心,准备对任务进行调度.

步骤3.改写DatacenterBroker类,增加自定义调度方法bindCloudletToVmByOsCapacity(),该方法对接收到的虚拟机列表和任务列表进行等价类划分,并以Map的形式存放.其中value为每一个粒度任务组或资源组,key对应该任务组的平均指令长度或资源组的平均执行能力.

步骤4.把所有任务组和资源组分别按平均指令长度和执行能力降序排序,使排序后的任务组轮询分配到资源组,实现按能力匹配调度策略.同时每个任务组内具体任务采用贪心算法,实现两级调度模式,提升调度性能.

步骤5.根据任务完成时间公式,计算任务执行总时间之和及任务完成时间,进行实验对比分析.

4.4 实验结果分析

1)图2展示了贪心算法和CloudSim自带的顺序调度算法在任务总执行时间和任务完成时间上的对比图,实验是将40个参数配置不同的任务分配到10个不同的虚拟机上.从五次的实验结果可以看出,贪心算法在任务的总执行时间和完成时间上比普通的顺序调度算法有明显的效率提升,同时也证明了粒度内部使用贪心算法的可行性.

图2 贪心算法实验结果Fig.2 Result of greedy algorithm experiment

2)等价类划分的粗粒度调度实验.实验中根据任务总数的不同,分别做了五次实验,任务总数分别2000、2500、3000、3500、4000.采用了三种调度方案对任务进行调度,并以任务总执行时间和任务完成时间作为参考.

图3 等价类划分的任务调度实验结果Fig.3 Result of coarse-grain scheduling experiment

从图3中可以看出,将任务和虚拟机进行等价类划分后,再使用贪心算法进行任务的调度,能明显减少任务执行的总时间和任务的完成时间.一方面是因为运用等价类进行粗粒度划分后,降低了每一组任务在选择资源上的时间开销;另一方面是因为等价类划分后的任务组和资源组的匹配调度,确保了任务在资源选取上的合理性,降低了任务的执行时间.而Kmeans聚类调度,因聚类的模糊性,致使部分影响调度性能的属性不能很好进行分类,导致任务总执行时间较长;同时,因聚类后的部分簇任务数量较多,也会导致任务完成时间较长,甚至比顺序调度更长.综上,通过上述的实验对比,我们可以得出,任务和资源的等价类划分调度能有效的将任务和资源进行归类,对于优化任务的执行时间具有可行的意义.

5 结束语

本文针对云计算环境下任务和资源的异构性,提出了等价类划分的粗粒度任务调度算法.该算法将任务分成两级调度模式:粒度间,运用等价类将异构的任务和资源进行划分分类,使任务组和资源组按能力匹配进行调度;粒度内,每个任务组内具体任务采用贪心进行调度,进一步优化任务的执行时间.同时,运用CloudSim进行模拟仿真实验,验证了本文算法的合理性与正确性.

[1] Botta A,De Donato W,Persico V,et al.Integration of cloud computing and Internet of things[J].Future Generation Computer Systems,2015,56(C):684-700.

[2] Yuan Jing-ling,Zhong Luo,Yang Guang,et al.Towards filling and classification of incomplete energy big data for green data centers[J].Chinese Journal of Computers,2015,38(12):2499-2516.

[3] Salot P.A survey of various scheduling algorithm in cloud computing environment[J].International Journal of Research and Engineering Technology,2013,2(2):131-135.

[4] Panda S K,Bhoi S K,Khilar P M.A semi-interquartile min-min max-min(SIM2)approach for grid task scheduling[C].Proceedings of International Conference on Advances in Computing,Springer India,2013:415-421.

[5] Wang Qiang,Li Xiong-fei,Wang Jing.A data placement and task scheduling algorithm in cloud computing[J].Journal of Computer Research and Development,2014,51(11):2416-2426.

[6] Li Zhi-yong,Chen Shao-miao,Yang Bo,et al.Mutil-objective memetic algorithm for task scheduling on heterogeneous cloud[J].Chinese Journal of Computers,2016,39(2):377-390.

[7] Li Wen-juan,Zhang Qi-fei,Ping Ling-di,et al.Cloud scheduling algorithm based on fuzzy clustering[J].Journal on Communications,2012,33(3):146-154.

[8] Guo Feng-yu,Yu Long,Tian Sheng-wei,et al.Workflow task scheduling algorithm based on resource clustering in cloud computing environment[J].Journal of Computer Applications,2013,33(8):2154-2157.

[9] Hu Meng,Yuan Ying-chun,Wang Xue-yang.Cloud task scheduling algorithm based on improved fuzzy clustering[J].Computer Engineering and Design,2015,36(9):2437-2441.

[10] Qi Ping,Li Long-shu.Task scheduling algorithm base on fuzzy quotient space theory in cloud environment[J].Journal of Chinese Computer Systems,2013,34(8):1793-1797.

[11] Wang Bo,Zhang Xiao-lei.Task scheduling algorithm based on particle swarm optimization genetic algorithms in cloud computing environment[J].Computer Engineering and Applications,2015,51(6):84-88.

[12] Xu Zhang-yan,Liu Zuo-peng,Yang Bing-ru,et al.A quick attribute reduction algorithm with complexity of max max(O(|C||U|),O(|C2|U/C|))[J].Chinese Journal of Computers,2006,29(3):391-399.

[13] Zhou Zhou,Hu Zhi-gang.Incorporate greedy strategy into scheduling algorithm for cloud computing[J].Journal of Chinese Computer Systems,2015,36(5):1024-1027.

附中文参考文献：

[2] 袁景凌,钟 珞,杨 光,等.绿色数据中心不完备能耗大数据填补及分类算法研究[J].计算机学报,2015,38(12):2499-2516.

[5] 王 强,李雄飞,王 婧.云计算中的数据放置与任务调度算法[J].计算机研究与发展,2014,51(11):2416-2426.

[6] 李智勇,陈少淼,杨 波,等.异构云环境多目标Memetic优化任务调度方法[J].计算机学报,2016,39(2):377-390.

[7] 李文娟,张启飞,平玲娣,等.基于模糊聚类的云任务调度算法[J].通信学报,2012,33(3):146-154.

[8] 郭凤羽,禹 龙,田生伟,等.云计算环境下对资源聚类的工作流任务调度算法[J].计算机应用,2013,33(8):2154-2157.

[9] 胡 蒙,苑迎春,王雪阳.改进模糊聚类的云任务调度算法[J].计算机工程与设计,2015,36(9):2437-2441.

[10] 齐 平,李龙澍.云环境下结合模糊商空间理论的资源调度算法[J].小型微型计算机系统,2013,34(8):1793-1797.

[11] 王 波,张晓磊.基于粒子群遗传算法的云计算任务调度研究[J].计算机工程与应用,2015,51(6):84-88.

[12] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(|C||U|),O(|C2|U/C|))的快速属性约简算法[J].计算机学报,2006,29(3):391-399.

[13] 周 舟,胡志刚.云计算中融入贪心策略的调度算法研究[J].小型微型计算机系统,2015,36(5):1024-1027.