段 菊，于治国

(山东管理学院 信息化工作办公室,山东 济南 250357)

0 引 言

云计算是近年来分布式计算、并行计算、网格存储和虚拟化等技术相融合的产物[1]。作为一种新兴的商业模式,其蕴含着巨大的商业价值[2]。云计算主要是利用虚拟化技术将数据中心的各类资源虚拟化为资源池进行统一的管理和对外服务，而且云计算是面向普通大众提供服务的，其用户群庞大、种类多样，要处理的任务量也是非常巨大的，所以云计算资源的管理和作业调度成为了云计算中的关键技术，在提高资源的使用效率以及为客户提供优质的服务中起着举足轻重的作用[3]。

云计算利用虚拟技术等为用户提供资源，包括计算资源、存储资源等。用户虽然免去了购买物理处理机的费用，但是依然需要支付租借云资源的费用，租借费用主要是由租借资源的数量、类型及时间决定的，因此，如何提高任务的执行效率是降低执行费用的关键。

任务调度问题是关于云计算研究课题中的一个重要内容，众多研究学者也提出了很多算法，如遗传算法[4]、蚁群算法[5]、粒子群算法[6]等。这些算法都有各自的优缺点，后人也在这些算法的基础上做了相应改进，但是目前应用最广泛的是基于启发式的调度算法[7]。其中，由于基于任务复制的调度算法可以消除任务间的通信开销，大大降低任务的等待时间，从而提高任务的执行效率，使得基于任务复制的调度算法得到了广泛关注。

目前任务复制算法已经有很多，例如TDS[8](task duplication based scheduling)考虑join节点任务与前驱的关系，但是没有考虑处理机的优化问题；TANH[7](task duplication-based scheduling algorithm for network of heterogeneous systems)对TDS算法中的相关参数的定义做了改进，使得计算最晚前驱的方法更合理；OSA[9](optimal task duplication based scheduling algorithm)将尽量多的父节点与子节点分配到同一个处理机上，以减少任务间的通信开销，但是没有考虑处理机的负载均衡问题。

随着研究的不断深入，任务复制算法也得到了很多改进。DCPD[10](dynamic critical path duplication)先对任务划分优先级然后进行调度，优先级的划分是根据任务的执行时间和距离路径的出口长度来定义的，任务的优先级制约着整个任务的流程；TDICMA[11](task-duplication and insertion based clustering and merging algorithm)充分考虑了任务复制的连锁反应，多次迭代得到合理的任务复制策略，该算法更多地关注静态任务参数；TDMCP[12](task duplication multi critical path)主要考虑关键路径上的任务对整体任务调度的影响，该算法只复制首任务来影响后续任务的执行，达到提高整体任务调度效率的目的。

为了进一步提高云环境下任务的执行效率、降低执行费用，文中提出一种基于相关性的并行任务调度算法(parallel task scheduling algorithm based on correlation，PTSAC)。该算法在任务调度之前根据任务间的通信开销进行队列划分，以提高任务划分的效率，在此基础上，根据相关性进行任务复制，相关性由任务间的通信开销和计算开销来量化，在该过程中设置阈值，若相关性大于阈值则进行任务复制，否则不予复制。

1 问题模型分析

1.1 相关定义

一般来讲，多个任务协作完成一个工作流，任务之间是相互联系的，这种制约关系可以用DAG图表示，即G={V,E,M,C}，其中：V={ti|ti(i=1,2,…,n)是工作流中的任务}；E={eij|eij表示ti、tj间的边，ti是tj的父节点，表明ti、tj间有通信}；M={mij|mij表示ti与tj间的通信开销，ti是tj的父节点}；C={ci|ci表示ti的计算开销}。

定义1：参数statime(ti)、fintime(ti)分别表示任务ti的开始时间和完成时间，并且有：fintime(ti)= statime(ti)+ci。

定义2：tend表示结束任务，fintime(tend)表示整个队列的完成时间，如果结束任务不止一个，则maxfintime(tend)=max{fintime(tend)j|j=1,2,…}。

定义3：参数pred(ti)、maxpred(ti)分别表示任务ti的前驱节点和最晚到达的前驱节点，如果任务ti没有前驱节点，说明其可以作为一个队列的开始节点；如果任务ti有多个前驱节点，则maxpred(ti)=max{M(pred(ti))ij+ fintime(pred(ti))|j=1,2,…}。

定义4：参数statime(ti)、fintime(ti)分别表示任务ti的开始时间和完成时间，并且有：fintime(ti)= statime(ti)+ci，参数indegree(ti)表示任务ti的入度，如果indegree(ti)≥2，说明任务为关键任务。

1.2 任务初次划分

为了减少不同处理机上任务之间的通信开销，在分配任务时相互间通信开销大的任务分配到同一个处理机上以提高任务执行效率。这里因同一处理机上不同任务间的通信开销很小，可忽略不计。

任务划分的意义在于尽量使相互间通信开销大的任务划分到同一任务集队列，然后任务调度阶段分配合理的处理机，以减少由通信开销带来的任务的等待时间，极大地缩短了整体任务队列的执行时间，进而减少租借资源的时间，降低执行费用。

任务初次划分的算法如下：

步骤1：if(pred(ti)==∅){初始化statime(ti)=0；fintime(ti)=statime(ti)+ci；单独成为一个队列{ti}}。

else执行步骤2

步骤2：如果前驱只有一个tj，直接把任务ti加入到前驱tj所在队列，此时，statime(ti)=fintime(tj)，fintime(ti)=statime(ti)+ci；否则执行步骤3。

步骤3：计算pred(ti)的最晚到达时间并排序，找到maxpred(ti)并把任务加入到maxpred(ti)所在的队列，此时，statime(ti)=fintime(maxpred(ti))-M(pred(ti))，fintime(ti)=statime(ti)+ci。

步骤4：从总的任务集中删除已划分队列的任务。

步骤5：重复步骤1～4，直至结束。

步骤6：输出任务队列P。

下面通过图1说明任务初次划分算法的过程，系统任务间的关系图可用DAG图表示。图中圆圈表示任务顶点，在圆圈中的1～15表示任务t1～t15，顶点旁边的数字表示任务的计算开销，边上的数字代表任务间的通信开销。

图1 DAG图

根据步骤1可知，图1中t1、t2、t3都没有前驱，因此它们的初始时间都为0，各自加入队列为{t1}、{t2}、{t3}。t1的前驱只有t1，所以把t1加入到队列1{t1}，以此类推，把t7、t11也加入到队列1{t1，t4，t7，t11}，当出现多个前驱时，则比较fintime(ti)+mij的大小，加入到值最大的前驱所在队列，例如t12的前驱有两个t7、t8，fintime(t7)+m7,12=7+7=14，fintime(t8)+m8,12=5+6=11，所以t12加入队列1，最终的三个队列分别为P(1)={t1，t4，t7，t11，t12，t14}、P(2)={t2，t5，t8}、P(3)={t3,t6,t9,t10,t13,t15}。

任务初次划分的详细过程如表1所示，任务划分结果如图2所示。

图2 任务划分结果

任务maxpred(ti)cistatime(ti)fintime(ti)P(i)t1-202{t1}t2-202{t2}t3-404{t3}t4t1325{t1,t4}t5t2123{t2,t5}t6t3347{t3,t6}t7t4257{t1,t4,t7}t8t5235{t2,t5,t8}t9t6279{t3,t6,t9}t10t63710{t3,t6,t9,t10}t11t73710{t1,t4,t7,t11}t12t7279{t1,t4,t7,t11,t12}t13t92911{t3,t6,t9,t10,t13}t14t1131013{t1,t4,t7,t11,t12,t14}t15t1341115{t3,t6,t9,t10,t13,t15}

由图1可知，t10，t14，t15是结束任务，根据定义2可知maxfintime(tend)=fintime(t15)=15，即整个任务队列完成的时间为15，但实际完成时间为16，这是因为计算过程是按照理论上的最早完成时间计算的，程序运行的过程实际是寻找最长路径的过程，然后通过队列的划分缩短完成时间，在完全并行的情况下得到最早的完成时间，而实际执行时是按照次晚路径计算完成时间，即在图2中是按照c2+c5+c8+m8,12+c12+c14=16计算完成时间。

2 基于阈值的任务复制策略

2.1 任务复制算法

这一节的重点是通过任务复制提高任务的并行性，进一步提前次晚路径的完成时间。第一节通过队列的划分可以缩短最晚路径的完成时间，最晚路径的完成时间被提前之后如果依然大于次晚路径的完成时间，则这时整个队列的完成时间就是最后得到的时间maxfintime(tend)，如果最晚路径的完成时间被提前之后小于次晚路径的完成时间，则整个队列的完成时间就要大于最后得到的时间maxfintime(tend)，正如上面的例子就是第二种情况。

针对第二种情况，文中提出基于阈值的任务复制算法，解决计算完成时间与实际完成时间不一致的问题。由第一节可知，计算得到的完成时间是最早完成时间，比文献[13-14]中的最早完成时间还要早，因此如何使实际完成时间与计算完成时间一致，是提高任务执行效率的关键。

阈值由通信开销和计算开销共同决定：

结果有以下三种情况：

(1)TSV>0说明与tj不在同一队列中的前驱任务的计算开销总和和通信开销相加之和大于同一队列中的任务计算开销总和，则可以复制从队列的开始到ti所有的任务到tj所在的处理器上，减少任务的等待时间；

(2)TSV=0说明两种开销和一样大，则不需要复制任务，此时若复制任务，不但不能减小时间开销，而且会增加空间开销；

(3)TSV<0说明与tj不在同一队列中的前驱任务的计算开销总和和通信开销相加之和小于同一队列中的任务计算开销总和，则不需要复制任务，此时若复制任务，不但不能减小时间开销，反而会增加时间开销和空间开销。

任务复制算法：

步骤1：计算P(i)中任务的入度indegree(tj)

步骤2：if(indegree(tj)≥2)

/*检查tj的所有前驱是否在同一队列*/

if在一个队列，执行步骤3；

else

/*计算TSV*/

if(TSV>0)

复制任务；

else不复制；

else执行步骤3

步骤3：j++；//直到队列任务结束

步骤4：i++；//直到队列任务结束

步骤5：重复步骤1～4

步骤6：输出任务队列

根据任务复制算法对上一小节中得到的任务队列进行处理。首先从队列P(1)开始，任务t12的入度为2，存在前驱任务t8不与其在同一队列，根据定义5计算阈值TSV=c2+c5+c8+m8,12-(c1+c3+c7)=2+1+2+6-(2+3+2)=4>0，即复制任务队列P(2)={t2，t5，t8}到队列P(1)，t14的前驱都在同一队列；查看队列P(3)，任务t13的入度为2，同t12的方法，TSV=10-9=1>0，复制任务队列P(2)={t2，t5，t8}到队列P(3)；经过任务复制后的队列如图3所示。

图3 任务复制结果

经过任务复制目前上述例子中的完成时间为15，达到了理想中的最早完成时间，任务复制算法降低了任务的等待时间，提高了任务的并行性。经过任务复制，每个处理机上的任务队列基本都是相互独立的，还有少数的有关联但对多个处理机进行并行处理没有太大影响。这样就可以在每个处理机上独立应用任务调度算法，只有在遇到个别任务时才需要与其他处理机进行通信，大大降低了通信开销，提高了任务执行效率。文中提到的处理机为处理机集群。

2.2 任务调度算法

通过任务初次划分及任务复制，对任务队列进行了合理的划分，得到了一个一个的任务集，任务集间的相关性大大降低，有的可以完全并行运行，为此，需要把任务集调度到合理的处理机上执行。任务集的数目决定了租借处理机的数目，通过对任务的复制，可以有效地减少任务集的数目，进而减少租借处理机的数目；另一方面，处理机数目的减少意味着处理机利用率的提高，合理利用处理机的空闲时间是提高处理机利用率的最佳途径，因此，任务调度算法的主要目的是为任务集查找合理的空闲时间，然后进行任务调度。

任务调度算法：

步骤1：初始化队列L，用于存放有空闲时间段的处理机，初始化变量count=0，用于记录处理机的数目；

步骤2：计算处理机空闲时间段的大小，并设置标记flag=0,按照空闲时间段升序排列，放入队列L；

步骤3：从队列L中查找合适的最小处理机空闲时间，若存在则把任务集调度至此处理机上执行，从任务队列中把此任务集删除，若flag=0，则count=count+1,并修改flag=1;

步骤4：重新计算flag=1的处理机的空闲时间段，如果还有空闲时间段，则根据时间段的大小插入到队列中；

步骤5：若不存在合适的空闲时间段则把任务集拆分，然后查找空闲时间段；

步骤6：输出count及flag=1的处理机的空闲时间。

3 实验与分析

为了验证文中提出的基于相关性的并行任务调度算法的有效性，对TDMCP算法、EOSWCA算法和文中算法从任务的完成时间、处理机的使用数目及利用率三个方面进行对比分析。

为了体现算法的公平性和有效性，采用前期实验仿真平台CloudSim[15]和参数设置，编程工具采用Myeclipse8.0[16]，任务数分别设为10、20、30、40、50、60、70、80、90、100等10种类型的任务队列，每种类型的任务队列产生10个，计算它们的完成时间maxfintime、处理机数目、处理机利用率。任务的计算时间ci和通信时间mij是在[1,20]中随机产生的。

由图4可以看出，TDMCP算法的完成时间要远远高于PTSAC算法，随着任务数的增加差距也越来越明显，TDMCP算法仅仅复制首任务而没有对后面的任务进行处理，在任务并行性方面明显处于劣势。EOSWCA算法也是采用任务复制的方法，缩短关键路径上任务的完成时间，其最早完成时间为次关键路径的完成时间。而PTSAC算法不仅缩短了关键路径上任务的等待时间，而且有效减少了次关键路径的完成时间。随着任务数的增加，PTSAC算法的优势越发明显。

从图5可以看出，在处理机使用数目方面，EOSWCA算法和PTSAC算法要绝对优于TDMCP算法。EOSWCA算法和PTSAC算法在任务划分之后，都进行了相当于任务聚簇的操作，也就是合并任务队列的过程，在任务调度阶段任务集的个数，决定了处理机的数目，因此，有效减少任务集的数目对降低租借处理机个数显得尤为重要。TDMCP算法没有进行此类操作，由图也可以看出，EOSWCA算法和PTSAC算法在处理机使用数目方面变化趋势相似，但PTSAC算法仍有优势，尤其是在任务数增长到60以后，优势明显。

图4 任务的完成时间

图5 处理机使用数目

处理机利用率的对比采用比值的方式，TDMCP算法的处理机总空闲时间作为基数，即TDMCP算法的处理机利用率作为单位“1”，EOSWCA算法和PTSAC算法的处理机总空闲时间分别与TDMCP算法的处理机总空闲时间作比，比值作为处理机利用率。由图6可以看出，随着任务数的增加，比值在减小，说明随着任务数的增加，EOSWCA算法和PTSAC算法的处理机利用率不断提高。任务数增加到60之后，PTSAC算法的处理机利用率明显高于EOSWCA算法。

图6 处理机利用率

综合以上三个方面，PTSAC算法整体要优于TDMCP算法和EOSWCA算法。

4 结束语

针对云环境下任务调度的问题，在前期研究的基础上，从执行时间、处理机数目及利用率方面作了进一步的研究，提出一种基于阈值的任务复制策略。该策略对复制任务的方法做了优化，通过设置阈值的方式，判断是否需要进行任务复制以减少任务的等待时间；然后对得到的任务集进行合理调度。实验结果表明，该算法在提前任务的完成时间、降低处理机的使用数目及提高处理机利用率等方面有很大的改善。下一步将对云环境下科学工作流的数据复制策略进行研究。

参考文献:

[1] CHEN Wanghu,ALTINTAS I,WANG Jianwu,et al.Enhancing smart re-run of kepler scientific workflows based on near optimum provenance caching in cloud[C]//IEEE world congress on services.Anchorage,AK,USA:IEEE,2014:378-384.

[2] 李 强,郝沁汾,肖利民,等.云计算中虚拟机放置的自适应管理与多目标优化[J].计算机学报,2011,34(12):2253-2264.

[3] ALI M,KHAN S U,VASILAKOS A V.Security in cloud computing:opportunities and challenges[J].Information Sciences,2015,305:357-383.

[4] ZHU Nuo,SHAO Chunfu.Vehicle routing problem with simultaneous delivery and pick-up based on the improved genetic algorithm[C]//Fourth international conference on genetic and evolutionary computing.Shenzhen,China:IEEE,2010:312-316.

[5] CHAHARSOOGHI S K,KERMANI A H M.An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)[J].Applied Mathematics & Computation,2008,200(1):167-177.

[6] TAGHIYEH S,XU Jie.A new particle swarm optimization algorithm for noisy optimization problems[J].Swarm Intelligence,2016,10(3):161-192.

[7] BAJAJ R,AGRAWAL D P.Improving scheduling of tasks in a heterogeneous environment[J].IEEE Transactions on Parallel & Distributed Systems,2004,15(2):107-118.

[8] RANAWEERA A,AGRAWAL D P.Task duplication based scheduling algorithm for heterogeneous systems[C]//Proceedings of 14th international parallel and distributed processing symposium.Cancun,Mexico:IEEE,2000:445-450.

[9] PARK C I,CHOE T Y.An optimal scheduling algorithm based on task duplication[C]//Eighth international conference on parallel and distributed systems.[s.l.]:IEEE,2001:9-14.

[10] LIU Chun-Hsien,LI Chia-Feng,LAI Kuanchou,et al.A dynamic critical path duplication task scheduling algorithm for distributed heterogeneous computing systems[C]//Proceedings of the 12th international conference on parallel and distributed systems.Washington,DC,USA:IEEE,2006:365-374.

[11] 潘志舟.基于任务复制和插入的分布式任务调度算法研究[D].武汉:华中科技大学,2015.

[12] 李静梅,尤晓非,韩启龙.基于任务复制的多关键路径任务调度算法[J].计算机工程与设计,2014,35(5):1639-1645.

[13] 段 菊,陈旺虎,王润平,等.云环境下基于聚簇的科学工作流执行优化策略[J].计算机应用,2015,35(6):1580-1584.

[14] 陈旺虎,段 菊,俞茂义.允许违反局部时间约束的科学工作流调度策略[J].计算机工程与科学,2016,38(11):2165-2171.

[15] 何婧媛.云计算仿真工具CloudSim的研究与应用[J].科技资讯,2016,14(2):32-33.

[16] 刘彦君,金飞虎.JavaEE开发技术与案例教程[M].北京：人民邮电出版社，2014.