一种基于任务执行时间的启发式独立任务调度算法

乔保军,张稼祥,左宪禹

(河南大学 河南省大数据分析与处理重点实验室;计算机与信息工程学院,河南 开封 475004)

随着技术的发展，互联网中的数据激增，大量的数据将人们带入了大数据时代[1].大数据时代的数据不仅数据量大，而且流动性强.为了获取数据中的价值所在，早期的单机计算已无法有效地进行处理.目前为了处理大量的数据获取其内在的价值，无论是在研究领域还是商业领域，云计算、网格计算等分布式技术已经成为人们的重点研究对象.通过这些分布式技术可以将大量的计算任务分配至多个资源上面同时计算，从而快速获取所需的结果.保证数据的时效性，提高人们对数据的利用率.在分布式计算中，任务调度问题始终是一个重难点问题.任务调度通常指的是在分布式、云计算环境中，根据用户的需求，合理地将N个任务分配至M个资源，实现整个计算系统的负载均衡,提高整体的资源利用率.从而提高任务的处理速度.在以往的研究中已经证明任务调度是一个NP难问题[2].通常任务调度的目标是提高系统资源的使用率，缩短任务完成时间.在目前大多数的研究中，都是对整体的任务完成时间进行优化，而对算法时间复杂度的研究偏少.本文提出一个基于任务执行时间的启发式独立任务调度算法，降低算法时间复杂度的同时，优化整体任务完成时间.

1 相关研究工作

任务调度作为分布式计算中一直存在的一个研究热点，目前已有大量的学者、专家对其做了大量的工作[3].根据任务之间依赖性，可以将任务调度分为独立任务调度与工作流调度[4-5].本文主要针对独立任务调度进行研究.有关任务调度的算法可以分为3类算法：启发式算法、元启发式算法[6-10]与混合式算法[11-13].相较于元启发式算法与混合式算法，启发式算法具有实现简单、幂等性、算法执行较快等优点.故本文提出一种新的启发式算法.

在启发式算法中，比较著名的两个算法是MIN-MIN算法[14]与MAX-MIN算法[15].在MIN-MIN算法中，第一步需要找到每一个任务的最小完成时间，然后再在这些具有最小完成时间的任务中找到具有最小最小完成时间的任务，将其分配至对应资源中.循环上述过程，直至所有的任务分配完成.在MIN-MIN算法的每次分配任务中，所有的资源的可用时间是一样的，任务越小，则完成时间越小.故MIN-MIN算法优先调度小任务.MAX-MIN算法与MIN-MIN算法极其相似，不同之处在于，MAX-MIN算法是从具有最小完成时间的任务中找到具有最大最小完成时间的任务，并将其分配至相应的资源.上述MIN-MIN算法优先小任务调度，MAX-MIN算法优先大任务调度.这就导致针对不同的任务类型，上述算法可能出现调度效果不理想的情况.为了解决上述问题，文献[16]提出了MIN-MAX算法.MIN-MAX算法类似MIN-MIN算法与MAX-MIN算法的结合体.在MIN-MAX算法中，第一步与上述两种算法相同.在第二步中，结合这两种算法，分别找到最小最小完成时间与最大最小完成时间.将两个任务进行捆绑分配.Sufferage算法[17]是对MIN-MIN算法的改进.在Sufferage算法中，不仅需要计算出每个任务的最小完成时间，还需计算出每个任务的次小完成时间，然后计算每个任务最小与次小完成时间的差值.选择具有差值最大的任务，将此任务分配到使其具有最小完成时间的资源上.ETSA算法[18]属于对Sufferage算法的进一步改进.不同之处在于，ETSA算法中，还需计算最小执行时间与第二小执行时间的差值.然后对完成时间的差值进行排序，根据完成时间的顺序相应对执行时间差值进行排序.如果完成时间的差值大于执行时间的差值则将任务进行分配.文献[19]提出了二阶段的MIN-MIN算法，此算法主要根据MIN-MIN算法的调度结果，进行二次分配，转移负载较高的资源中的任务至负载较低的资源，以此来达到负载均衡的目的.

上述算法在针对各自的问题上都取得了良好的效果,然而未能很好地平衡算法时间复杂度与调度结果，同时在面对某些类型的任务时调度效果不理想.本文提出的一种基于任务执行时间的启发式独立任务调度算法可以较好地平衡时间复杂度与调度结果，同时兼顾各种类型任务调度.

2 任务调度算法模型

在介绍本文算法之前首先对相关符号、概念进行说明.

ETC(n*m)：任务执行时间矩阵，二维矩阵，n个任务m个资源，每个任务在每个资源上面的执行时间矩阵，在任务调度前已知.

ETC1：ETC矩阵分解的第一个矩阵，此矩阵行列有序，由ETC中的部分行组成.ETC1[i,j]表示任务i在资源j上面的完成时间.

ETC2：ETC矩阵分解的第二个矩阵，此矩阵中的元素无固定规律，由ETC矩阵中的部分行组成.ETC2[i,j]表示任务i在资源j上面的执行时间.

CON：主要用于记录某个任务对应的行是否有序.CON[i]=true表示任务i在ETC矩阵中对应的行为有序.

CON_NUM：ETC1矩阵中包含的任务数.

TR：任务分配矩阵，二维矩阵.如果TR[i,j]=true，表明任务i分配至资源j上面.

CT：资源可用时间矩阵，表示当前资源在分配下一个任务时，需多长时间可执行到要分配的任务.为了简化模型，在本文中，每个资源的可用时间简化为分配在资源上面的任务的执行时间之和.CT[i]代表资源i的资源可用时间.

Rfrom,Rto：泛指需要进行任务调整的两个资源，拟将Rfrom中的任务调整至Rto中.

MAKESPAN:表示通过算法调度之后完成所有任务的时间,为所有资源完成时间的最大值.

Ti：表示任务i.

Rj：表示资源j.

任务完成时间：某个任务的完成时间为某个资源的可用时间与此任务的执行时间之和.某个资源的任务完成时间为分配至该资源所有的任务执行时间之和.

本文提出的独立任务调度算法主要由4个阶段组成.分别为预处理阶段、分解阶段、预调度阶段、调整阶段.算法的输入即为ETC矩阵，输出的结果为每个资源上面的任务完成时间矩阵以及任务分配矩阵.为了便于理解，本文将整个算法按照上述4个阶段分别进行介绍.第一个阶段的输入为整个算法的输入为ETC矩阵，接下来的每个阶段的输入分别为上一个阶段的输出.接下来分别介绍上述4个阶段.

2.1 预处理阶段

在预处理阶段，主要是对原始的ETC进行调整.调整的目的在于给下一阶段矩阵分解做准备.给定一个ETC矩阵，ETC矩阵中的每一行代表一个任务在每个资源上面的执行时间.每一列代表所有任务在某一个资源上面的执行时间.针对ETC矩阵中的第一行元素，从小到大对第一行元素进行排序处理，整个ETC矩阵的每一行排列的顺序与第一行元素的顺序相同.即根据ETC矩阵的首行元素的大小，从小到大对每一行进行排序处理.之后，根据首列元素的大小再次进行ETC矩阵的重组.经过两次重组后的矩阵即为分解阶段的输入，进行算法的下一步处理.预处理阶段伪代码如算法1所示.

算法1 预处理阶段算法

输入：(ETC,n,m)

输出：(ETC)/*预处理后的ETC*/

1.fori←1 tondo

2. forj←1 ton-i-1 do

3. ifETC[0,j]>ETC[0,j+1]

4. swap(j,j+1)/*交换ETC矩阵两列*/

5.fori←1 tomdo

6. forj←1 tom-i-1 do

7. ifETC[j,0]>ETC[j+1,0]

8. swap(j,j+1)/*交换ETC矩阵两行*/

2.2 分解阶段

在分解阶段主要的功能是将经过预处理阶段的ETC矩阵分解为ETC1和ETC2两个矩阵.在预调度阶段会对分解后的矩阵采取不同的调度策略.ETC1矩阵中，任意一行、一列都满足从小到大的排列顺序，即整个矩阵行列有序.而ETC2矩阵则没有限制.在分解阶段首先是将ETC矩阵中满足从小到大顺序的行标记出来，若此行有序则CON[i]=true，若无序则CON[i]=false.标记完成后，遍历整个CON矩阵，找到第一个标记为true的行.然后从标记的第二行开始与标记的第一行进行比较，如果在所有资源上，第二行的执行时间都大于第一行，接下来的比较行，则会变成标记的第三行与第二行进行比较，依次类推.如果第二行中有元素小于第一行中的元素，则将CON[i]设置为false.接下来的比较则会变成标记的第三行与第一行进行比较.按照上述规则，直至比较完成.接下来再一次遍历CON矩阵，如果CON[i]为true，则将任务Ti对应的行添加至ETC1中，否则添加至ETC2中.分解阶段伪代码如算法2所示.

算法2 分解阶段算法

输入：(ETC,n,m)

输出：(ETC1,ETC2)

1./*判断ETC的每一行是否有序*/

2.fori←1 tondo

3. ifi行有序

4.CON[i]=true

5.CON_NUM=CON_NUM+1

6. ifCON_NUM==1

7.TASKID=i/*记录第一个行有序的任务ID*/

8.fori←1 tondo

9. ifCON[i]

10. if 任务i在所有的资源上面的执行时间都大于TASKID的执行时间

11.TASKID=i

12. else if

13.CON_NUM=CON_NUM-1

14.CON[i]=false

15.fori←1 tondo

16. ifCON[i]

17. 将ETC[i]添加至ETC1中

18. else if

19. 将ETC[i]添加至ETC2中

2.3 预调度阶段

在预调度阶段，主要的任务就将按照不同的调度策略，分别将ETC1,ETC2矩阵进行调度.首先在对ETC1矩阵进行调度的时候，从ETC1最后一行开始，依次进行直至整个ETC1矩阵调度完成.找到最后一行任务的最早完成时间，然后将此任务分配至相应的具有最小完成时间的资源，更新资源可用时间，更新任务分配矩阵.根据更新的资源可用时间矩阵，继续计算寻找下一行的最小完成时间，直至ETC1矩阵中的任务全部分配完成.此时，资源可用时间与任务分配矩阵已得到更新.其次开始对ETC2进行任务调度.对ETC2矩阵进行调度时，直接按照每个任务的最小执行时间进行调度.即，遍历ETC2矩阵中的每一行，然后找到当前任务在所有资源中具有最小执行时间的资源，直接将当前任务分配至对应的资源，更新资源可用时间矩阵与资源分配矩阵.预调度阶段伪代码如算法3所示.

算法3 预调度阶段算法

输入：(ETC1,ETC2,CON_NUM,nm)

输出：(CT,TR)

1./*首先对ETC1矩阵进行调度*/

2.fori←CON_NUM-1 to 1 do

3. forj←1 tomdo

4.Ti在Rj上面具有最小完成时间

5. 更新CT矩阵CT[j]=CT[j]+ETC[i,j]

6. 更新TR矩阵TR[i,j]=true

7./*对ETC2矩阵进行调度*/

8.fori←1 ton-CON_NUMdo

9. forj←1 tomdo

10.Ti在Rj上具有最小执行时间

11. 更新CT矩阵CT[j]=CT[j]+ETC[i,j]

12. 更新TR矩阵TR[i,j]=true

2.4 调整阶段

调整阶段主要是根据预调度的结果对任务分配重新进行调整.在调整阶段可以分为如下3个阶段.

1)首先寻找两个需要调整任务的资源Rfrom与Rto，拟将资源Rfrom上面的任务重新调整至Rto中.在寻找这两个资源Rfrom与Rto时，最开始所找的是具有最大资源完成时间的资源为Rfrom，具有最小资源完成时间的资源为Rto，如果资源Rfrom中的任务可以分配至资源Rto中，那么下次进行寻找两个资源时依旧是以最大资源完成时间的资源为Rfrom，以最小资源完成时间的资源为Rto.如果Rfrom上面的任务无法分配至Rto，那么下一次寻找时Rfrom依旧为最大资源完成时间的资源，而Rto则变为具有第二小的资源完成时间，后续依次类推.如果在Rfrom为最大完成时间时，遍历了除Rto之外的所有资源依旧无法分配任务，再进行下一次寻找两个资源时，则Rfrom变为第二大资源完成时间，而Rto依旧从最小资源完成时间开始.只要发生一次Rfrom上面的任务可以调整至Rto，那么寻找这两个资源时，则Rfrom重新为最大完成时间资源，Rto为最小完成时间资源.

2)找到资源Rfrom中分配的任务在Rto中具有最小执行时间的任务T.

3)如果将任务T调度至Rto中，Rto的资源完成时间小于之前Rfrom中的完成时间，则将任务T分配至Rto中.更新对应资源的任务完成时间以及任务分配矩阵.如果无法进行重新调度，则回到1)继续寻找Rfrom与Rto.共进行n次循环即可结束.

调整阶段伪代码如算法4所示.

算法4 调整阶段算法

输入：(ETC,TR,CT,n,m)

输出：(CT,TR)

1.fori←1 tondo

2. forj←1 tomdo

3. 找到需要重新调度的资源Rfrom,Rto

4. fori←1 tondo

5. 找到资源Rfrom中任务在Rto中具有最小执行时间的任务Ti

6. if 任务Ti调整至资源Rto中,Rto的资源完成时间<资源Rfrom之前的资源完成时间

7. 更新资源可用时间CT

8. 更新任务分配矩阵TR

3 算法调度实例

现有3个资源R1，R2，R3，6个任务T1，T2，T3，T4，T5，T6.每个任务在每个资源上面的执行时间已知.首先开始进行第一阶段进行ETC矩阵的预处理.ETC矩阵如表1所示.

表1 ETC矩阵

按照ETC矩阵的第一列进行排序，排序后的矩阵如表2所示.按照ETC矩阵第一行进行排序，排序后的矩阵如表3所示.

表2 按照第一列排序后的ETC矩阵

表3 按照第一行排序后的ETC矩阵

第二阶段将ETC矩阵分解为两个矩阵.由表3可知，T1,T4,T6满足从小到大排列.T2,T3,T5不满足.故所对应的CON矩阵如表4所示.

表4 CON矩阵

遍历CON矩阵，第一个为true的任务为T1，第二个为true的任务为T4.任务T4对应的行与任务T1对应的进行比较.经过比较可知，在每一个资源上面，任务T4的执行时间都要大于任务T1的执行时间.故，将任务T1，T4添加至ETC1中.第三个标记为true的任务为T6.T6与任务T4进行比较.经过比较可知，任务T6在每个资源上面的执行时间都要大于T4.故将T6加入ETC1中.遍历完成后，原始的ETC矩阵即可分解为ETC1，ETC2分解后的矩阵如表5、表6所示.

表5 ETC1矩阵

表6 ETC2矩阵

第三阶段首先将ETC1矩阵进行调度，对ETC1矩阵进行调度的时，从T6任务开始调度.T6任务具有最小的完成时间为100，对应的资源为R1，故将T6分配至资源R1中.T6任务分配完成后，任务T4开始分配，T4在R3具有最小完成时间45 ms，将T4分配至R3.T1在R2中具有最小完成时间6 ms，故将任务T1分配至R2.ETC1矩阵调度完成后.开始对ETC2矩阵进行调度.ETC2中的矩阵，按照任务执行时间的大小进行分配，任务T2，T3，T5都在R1中具有最小执行时间.故将任务T2，T3，T5都分配至R1.第三阶段分配完成后，任务分配结果图如图1所示.

第四阶段为调整阶段.第一轮的调整，具有最大完成时间的资源为R1，具有最小完成时间的资源为R2，现在将分配至R1中的任务调整至R2中.R1中的任务在R2中具有最小执行时间的任务为T2，T2在R2上的执行时间为2.若将T2分配至R2，则R2中的完成时间为8，而R1之前的完成时间为166.8 ms(小于166)，故将任务T2调整至R2.第一轮调整后的任务分配图如图2所示.在本次实例中共进行6轮调整，最终R1任务完成时间为100 ms，R2完成时间为100 ms，R3完成时间为97 ms.最终任务分配图如图3所示.

4 仿真与结果分析

在文献[20]中，根据资源与任务的异构性，将模拟仿真的ETC矩阵分为低任务异构-低资源异构、低任务异构-高资源异构、高任务异构-低资源异构、高任务异构-高资源异构4种.同时，根据整个ETC矩阵的一致性，将ETC矩阵分为非一致性、半一致性、一致性矩阵.共计12种ETC矩阵.在本文中的仿真实验中，除了应用上述12种ETC矩阵外，还增加了另外八种不同的ETC矩阵.这8种ETC矩阵中，每个任务的执行时间主要由任务大小除以资源处理能力得到.低异构资源处理能力的大小在[1,100]均匀分布随机产生，高异构资源处理能力的大小在[1,1 000]均匀分布随机产生.低异构任务大小在[1 000,10 000]均匀分布随机产生，高异构任务大小在[1 000,300 000]均匀分布随机产生.在这8种ETC矩阵中根据ETC矩阵的一致性分为，特殊一致性矩阵与特殊半一致性.特殊一致性主要是与一致性矩阵进行区分.特殊半一致性矩阵主要与半一致性矩阵进行区分.一致性矩阵主要指的是，如果任务Ti在资源Rn中的执行时间小于Rm中的执行时间，那么所有的任务在Rn中的执行时间要小于Rm的执行时间.在模拟的ETC矩阵中表现为行有序.本文中所提的特殊一致性，指的是不仅满足一致性的条件，还要满足，如果任务Ti在某一资源上的执行时间小于任务Tj执行时间，那么在所有的资源上面任务Ti执行时间小于Tj执行时间.在ETC矩阵中，特殊一致性矩阵表现为行列有序.特殊半一致性矩阵，指的是，ETC矩阵中，一半任务满足本文所提的特殊一致性，一半不满足特殊一致性.在构造特殊半一致性矩阵时，通过随机打乱特殊一致性矩阵中一半的行来实现.

4.1 实验环境

实验环境：CPU主频3.40 GHz，硬盘：1 T，内存：16 GB，操作系统：Windows10 64位.

开发环境：开发平台为Eclipse，开发语言为Java.

4.2 结果分析

本文实验是在上述模型与实验环境下进行的，选择16个资源，256个任务产生的ETC矩阵.在上述基础上比较MIN-MIN算法、MAX-MIN算法、本文算法.比较的结果为完成所有任务的时间MAKESPAN.每一种ETC矩阵产生4种最后求得4种调度结果的平均值为算法在某一ETC矩阵下的调度结果.图4至图7为根据文献[20]提出的模拟数据实验的结果.图8至图11为本文添加的8种ETC矩阵的调度结果.

与MIN-MIN算法进行比较.观察图5与图7，由一致性矩阵、半一致性矩阵与高任务异构-高资源异构、低任务异构-高资源异构所组合成的4种条件下，本文算法MAKESPAN明显高于MIN-MIN算法的MAKESPAN，由此可以得出结果，在上述条件下MIN-MIN算法明显优于本文所提出的算法.观察图4与图6，由半一致性矩阵与低任务异构-低资源异构、高任务异构-低资源异构组合的两种条件下，本文算法与MIN-MIN算法相差无几.观察图4至图11，除上述6种情况外，在余下的14种情况下，本文MAKESPAN均低于MIN-MIN算法的MAKESPAN.

与MAX-MIN算法进行比较，观察图8至图11.矩阵为特殊一致性矩阵条件下，无论异构性大小，本文算法的MAKESPAN与MAX-MIN算法的MAKESPAN相同.由此可以得出结论，在特殊一致性矩阵的4种条件下本文算法与MAX-MIN算法调度结果相同.观察图10，在特殊半一致性-高任务异构-低资源异构条件下，本文算法的MAKESPAN高于MAX-MIN算法的MAKESPAN，说明在此条件下，MAX-MIN算法要优于本文算法.观察图4至图11，除上述5种情况，其余15种条件下，本文算法调度结果都要优于MAX-MIN算法调度结果.

除上述之外，观察图4至图11可以发现，本文提出的算法无论在那种情况下都不会出现极差的结果，相比MIN-MIN,MAX-MIN调度结果更加平稳，表明本文算法的适应性也要优于上述算法.

4.3 时间复杂度分析

在本文算法中，预处理阶段需要对行与列进行排序，预处理阶段的时间复杂度为O(n2).分解阶段包含双重迭代，时间复杂度为O(n*m).预调度阶段包含双重迭代时间复杂度为O(n*m).调整阶段包含双重迭代，时间复杂度为O(n2).因此本文算法时间复杂度为MAX(O(n2),O(n*m)).在MIN-MIN,MAX-MIN算法中包含三重迭代，他们的时间复杂度都为O(n2m).本文算法时间复杂度要优于上述两个算法.

图12展示了模拟10 000个任务分别在16,32,64,128,256节点下的算法执行时间.MIN-MIN,MAX-MIN的计算时间几乎相当，这是因为其时间复杂度均为O(n2m).在本节的实验中本文算法的计算时间分别是MIN-MIN或者MAX-MIN的计算时间的50.4%，32.0%，25.7%，18.0%，15.0%，与算法复杂度的理论结果MAX(O(n2),O(n*m))/O(n2m)并不一致.因为时间复杂度主要反映了程序执行时间随输入规模增长而增长的量级.但从图12中可以发现，本文算法随着节点个数的增加，算法执行时间的增长幅度明显弱于MIN-MIN与MAX-MIN算法. 图13展示了模拟128个节点分别在2 000,4 000,6 000,8 000,10 000任务下的算法执行时间.从图13中也可发现，本文算法随着任务个数的增加，算法执行时间的增长幅度也要明显弱于MIN-MIN与MAX-MIN算法.

5 结束语

MIN-MIN,MAX-MIN算法是独立任务调度中常见的算法.针对上述算法时间复杂度高以及调度结果不理想的等问题,本文提出了一种基于任务执行时间的启发式独立任务调度算法.在降低分配算法时间复杂度的前提下，改善任务调度结果，缩短整体的任务完成时间.在本文提出的20种任务类型下，大多数条件下本文算法调度结果要优于上述两种算法.此外,优化分解阶段和调整阶段，解决个别条件下本文算法劣于上述两种算法的情况，将是下一步工作的重点.