一种改进的实时任务调度算法

一种改进的实时任务调度算法

随着大量任务计算和处理的要求增加，大规模数据信号的处理能力越来越大，多处理器系统的应用也越来越广泛。实时异构系统已被广泛地应用在很多的高精准计算和高实时性要求的领域,如核反应控制、航天航空的控制、网络多媒体的实时传输等。但是目前来说无论是对于单机、双核、四核、多核还是集群系统的计算,大多数的实时任务调度是针对同构系统所提出来的,对于异构系统的实时任务调度研究还有待进一步的深入。有效的调度是能使任务取得高效的关键因素之一,算法的本质目标就是将任务映射至各处理器,在满足任务约束关系的前提下,对任务进行调度,尽可能地减少任务的调度长度,以提高任务的执行效率与成功率。通常对多处理器的任务调度采用的模型是DAG(directeda-cyclicgraph)图。其中节点表示任务,节点间的有向弧表示任务间的通信。在文献中提出了基于异构多处理器(real-timescalableduplicationbasedalgorithm,RTSDA)的实时任务调度算法,但是在分簇时选择处理器的策略却还是沿用基于同构多处理器,因而会引起任务调度的时间复杂度非常大,详细分析见第2章;文献中提出在异构多处理器的可靠性下调度任务,但文章只对处理器可靠性的异构性进行了综合考虑,而对任务的考虑就过于简单了,未考虑任务在异构处理器上执行时会引起执行时间的互异;文献中提出的TDS和文献中提出的HNPD主要侧重通过任务复制来优化任务调度,但是算法时间复杂度相当高;文献主要侧重于通过初始化分簇来改善任务调度的性能,分簇后并没有采用复制策略更好的利用处理器的空闲时间来提高任务的调度成功率;文献中提出了异构多处理器下HEFT和CPOP,并证明了其在调度长度和加速比上都优越于以往的调度算法,但是实质上HEFT和CPOP虽然采用的处理器选择策略是基于插入的方式,在满足前趋约束的前提下,尽可能地提高了处理器的资源利用率,但由于存在通信时延与节点间的约束关系,处理器存在空闲时间块是不可避免的,在这种情况下,应该与任务复制算法相结合,才能更好地降低通信时延和更大地提高处理器的利用率,以提高任务的实时性。综上所述,本文针对异构多处理器的实时任务的特点,结合各类算法的特点,提出一种新的低时间复杂度的异构多处理器的任务实时调度算法(heterogeneousreal-timetaskschedulingalgorithm,HRTSA)。本算法结合了RTSDA和TDS算法,以及负载均衡等算法的优点,对异构多处理器的任务进行了调度,通过实验对比,证明本文提出的算法HRTSA与文献中提出的算法具有更低的时间复杂度与更优的调度结果。1关于异结构实时多处理器任务的描述1.1任务的实时调度异构多处理器的任务模型采用带权有向无环图(DAG)来表示。通过数组表示为G=(V,E,P,C)。其中:V代表节点;E(Vi,Vj)是表示任务i和j的通信时间,E的值代表两任务间的通信时间,|E|代表边的个数;P是处理器集;C(Vi,Pm)是任务Vi在处理器m上的执行时间。Prep(Vi)指节点Vi所有的直接前趋节点。Succ(Vi)是指节点Vi的所有的直接后继节点。若Vi没有前趋节点,则称Vi为开始节点;若Vi没有后继节点,则称Vi为结束节点。任务必须在其前驱任务执行完成,并且任务间的通信全部完成后,任务才能开始执行。任务的实时调度就是使任务在指定的时间内(deadline)能执行完毕,若不能在指定时间内完成,则调度失败。在满足deadline的前提下尽量使整个DAG的执行时间最短,以达最优调度。与普通的同构多处理器任务模型不同的是,当处理器结构不是完全一样时,同一个任务在不同的处理器上执行,就会引起执行时间的差异性。在DAG模型上体现为如图1和表1所示。节点Vi(1≤i≤9)表示任务,带方向的弧表示任务间通信,每个弧上都有权值,分别表示任务间的通信时间。但是任务的执行时间因处理器结构的差异而有所不同,所以执行时间是一个n×p(n节点数×p处理器个数)的二维数组,如表1所示,且有V5.deadline=15,V9.deadline=30。1.2节点时间复杂度分析est(Vi,Pm)=max(eft(Vj),eft(Vk)+E(Vi,Vk),avil(Pm))(1)Vj与Vk都是Vi的前趋节点。式(1)表示Vj与Vi在同一个处理器(处理器Pm)上执行,所以无须考虑通信时间,而Vi与Vk不在同一处理器上执行,故需要考虑通信时间;avil(Pm)表示处理器的可用时间;est(Vi,Pm)表示Vi在处理器Pm上的最早可能开始时间。ect(Vi)=est(Vi,fproc(Vi))(2)其中:表示Vi的最早完成时间。式(2)所表示的意义是(最早开始时间+任务在最喜欢的处理器上的执行时间)=任务的最早完成时间。fproc(Vi)=min(C(Vi,Pm))(3)其中:表示Vi完成时间最早的处理器,即为RTSDA算法中提到的Vi最喜欢的处理器。fpred(Vi)=eft(Vj)>eft(Vk+E(Vk,Vi)(4)其中:Vk是Vi的前趋集合,Vj也是前趋集里的一个元素且表示Vi和Vj放在同一个处理器上执行,则可以忽略任务Vi和Vj间的通信时间。式(4)是找各个节点最喜欢的前趋节点。favo_proc[i](5)节点Vi最喜欢的处理器序列是按执行时间从小到大排序,HRTSA处理器选择策略中节点喜欢的处理器序列。通过上述分析可知,由于执行时间成了二维数据,对节点的调度时间复杂度也增大了非常多,如RTSDA算法采用的分簇算法是基于最短完成时间。对图1,找到节点V1执行时间最小的处理器时间复杂度为O(p);对于V2,需要考虑其本身考虑执行时间,还需要考虑通信时间,则需要在V1的基础上再进行边与处理时间的计算与排序,时间复杂度为O(p2);依此类推,对图的调度算法的时间复杂度为O(n×|E|×p3),即当对n个节点进行处理器,找最优处理器的时间复杂度为O(n×|E|×Plen)。其中len表示从开始节点到结束节点最长的路径的长度。这是一个与处理器呈指数级的时间复杂度,当处理器个数和任务长度增加时,算法的时间复杂度将大得可怕。本文针对RTSDA存在的时间复杂度过高问题,提出了一种基于最小执行时间分簇的算法,并为了使任务调度成功率增加,还采用了负载平衡和任务复制等策略以提高任务的调度成功率。2r算法2.1抗混叠序模型针对以往异构多处理器的实时任务调度时间复杂度过高的问题,HRTSA采用了两个策略,在降低时间复杂的同保障任务执行的效率,策略分别是最短执行时间分簇算法METC(minexecutetimeforclustering)、基于时间的负载均衡PLBA(processorsloadbalancedalgorithm)。根据DAG图的约束关系,将在同一处理器上拥有较小的执行时间的节点划分为一簇。这样可以使分簇后的节点,都是执行时间在同一处理器上执行时间较优的情况下选择出来的。从Vi=Vexit节点依次往前递归执行,就可以将任务初始化分成多个簇,并且分簇后每个任务簇都将附带一个拥有最短执行时间的处理器信息。METC算法的详细描述如下:2.2任务分簇的均衡步骤1初始化的时间复杂度,对所有节点按执行时间从小到大排序时间复杂度为O(n×p2);步骤4从前趋中选择一个最优秀的前趋加入本簇,时间复杂度为O(arc_num×n);通常情况下p2<<arc_num,算法的时间复杂度为O(arc_num×n)。METC策略仅仅在执行时间和节点的约束关系下将任务分簇,这样初始化形成的簇,但这是未考虑处理器负载。如果异构多处理器中存在个别处理器,对任务的处理其执行时间在性能上优于所有的其他处理器,那么初始化分簇与各簇关联的处理器将都是同一个处理器,如果直接将任务放置处理器上,势必形成性能较优的个别处理器过载,而其他大量的处理器处于空闲,这不但没有提高效率,相反给调度任务增加了难度。如何避免这种糟糕的情况发生,那么HRTSA在放置之前采用了PLBA。在放置之前,对处理器的执行时间进行相应的统计。如果放置的簇节点执行时间之和大于DAG的deadline,将处理器标志为过载,剩下未放置的簇,如果存在最优处理器是过载的处理器,则退而选择次优处理器进行放置。通过负载均衡处理,避免了大量任务簇聚集于个别处理器,而引起任务调度难度增大或调度失效。HRTSA算法如下:由上可知HRTSA算法的时间复杂度是=O(p×n)。3实验模拟与实验结果的分析3.1节点通信量的估计为了验证本算法的优点,对比HRTSA的性能,本文实现了文献中提出的算法RTSDA和文献中提出的HEFT算法,采用TGFF产生了大量在异构实时多处理器任务,对于每一组数据,给定节点个数与节点、通信时间和节点执行时间的比率CCR(communicationtocomputationratio)。CCR反映的是任务节点间通信量的平均值与节点计算量的平均值的比较,CCR越大,说明任务图中包含的通信量也就越大。模拟实验在CCR一定的情况下,处理器数目为2～25的随机数,任意产生大量的有向无环图;然后计算每个任务图的调度成功率,进行统计,求平均值。3.2结果实验数据图如图2～7所示。3.3最大执行时间的确定对于调度成功率分析:图2表示CCR=0.1时,随着节点个数的增加HRTSA算法在执行成功率比RTSDA越来越优。是因为对于一个DAG任务图来说,当CCR=0.1时,最主要的时间开销是节点的执行时间引起的,而基于METC的分簇策略最大程度地让程序的执行时间减少,所以随着任务个数的增加,采用METC策略的HRTSA算法将越来越优越。由于通信时间比率很低,HEFT算法没有采用复制策略,以HRTSA算法基本上优于HEFT算法。图3表示当CCR=1时,HRTSA与HEFT算法大部分都优于RTSDA,边的通信时间也是构成DAG执行时间内非常重要的一部分,HRTSA优于RTSDA的主要原因在于MECT策略,将最小执行时间的放在一起执行。HRTSA同样在调度时采用的复制策略能提高执行的效率,所以优于HEFT算法。同样对于CCR=10的图4来说,HRTSA的优势相对来说也没有前两者优越,因为在这种情况下,任务的主要执行时间来源于边的通信时间,而在HRTSA中,未考虑节点通信时间,所以相对考虑节点通信时间的HEFT算法来说HRTSA就逊色了,但其对于RTSDA策略的优越性还是同样存在的。对DAG图除了调度成功率,常用的方式还有加速比,即串行执行时间与并行执行时间的比率。串行执行时间是指把所有任务分配到一台处理器上执行,即任务间的通信时间恒为0,当整个DAG图执行完毕所需要的时间。对异构多处理器来说,本文选择能使整个DAG图执行时间最小的处理器。Speedup=min(DAG’sexecutetimeinPj)/(DAG’sactualfinishtime);同理,如图5所示,当CCR=0.1时,任务的主要时间开销是执行时间引起的,那么根据执行时间HRTSA最小化执行时间策略与复制调度算法,能让任务在加速比上优于RTSDA和HEFT算法。当CCR增加到1时,通信时间和任务执行时间相当,HRTSA由于采用了EMTC和PLBA策略,在加速比上明显优越于RTSDA。但是与HEFT算法相比,HRTSA在加速比上基本没有太大的优势,主要原因是HEFT充分考虑通信时间和执行时间的关系,而HRTSA算法主要的策略只是尽量地降低任务的执行时间。正是由于这一原因,当CCR=10时,如图7所示,HEFT算法在加速比上的优越性也就更加明显了,此时对于任务图的主要时间开销是通信时间开销。4基于负载因子更新策略本文提出了一种新的调度算法HRTSA,该算法采用基于METC最短执行时间与任务