实时任务在实际应用中通常需要以独占方式访问共享资源, 但是由于资源的独占性导致高优先权任务运行时往往被低优先权任务阻塞, 从而产生优先权反转, 难以满足任务的实时性；同时当前处理器由于较高的能量消耗,导致处理器热量散发提高及系统可靠性降低, 已经成为目前计算机领域较为关心的问题。提出一种基于任务同步及节能的实时调度算法CSSFA,有效地解决了上述难题。CSSFA在满足任务实时可调度性及任务同步的条件下,固定临界区的运行速度,使更多的空闲时间用于非临界区部分,有效地降低了整体系统的能耗；同时也能避免高优先权
第3期 韩建军,等:基于任务同步及节能的实时调度算法 ·689 即 x-y「v/(y+z)12≤y+xx/(x+z)12 在 CSSFA中e)计算T;非临界区部分的速度nm(r;)时, 经过化简可得到 首先对每个S,∈S计算n,USF算法中同一任务的临界 (x-y):+3(x-y)xyx2+2(x2-y2)z3≤0 区部分与非临界区部分的速度均相同。在满足实时性条件下 由于x>y且x,y,>0,上面不等式左边各项都大于0,导给出的n计算公式如下: 致矛盾,故命题成立。 (C,m.)S:/71)+(B1+∑CnS2/Tn1)/=3(1) 推论1假设任务T的临界区z,的WCET为y,2,阻塞 CSSFA固定任务临界区部分的运行速度,囚而n的计算 任务r,r被阻塞的wCET为x,且x>y。存在一个空闲时式如下 间,其长度为z,则空闲时间全部用于临界区z.,时所产生的能 耗大于空闲时间全部均匀用于T4被阻塞部分时所产生的 ∑[Cn(r)/n(T,)+∑C(x1,k)/(xn,)J「S,Tn1+ 能耗。 ∑Cn(T,)-∑C(x)]/n,+C(,)n(2,)「S。/71+ q≤P≤i 证明证明过程与定理1一致。 max] max nolde fined ix, ,,Ce(z,, )/mi,i, max defined('s,///CesCo,/ 2.1算法描述 mes (3r,) i CSFA在满足可调度性及同步协议的基础上,固定任多其中:2,有可能阻塞任务T;,末定义;m,已定义;7非临界 临界区部分的运行速度,使得非临界区部分获得更多的空闲 区部分的速度m(T)=min,(m)。 时间,以降低系统能耗。同时,在任务实际运行中,临界区无 式(2)与(1)的区别在于,每次求得中断点任务后,有些低 须继承被阻塞任务的运行速度,避免了处理器电压开关的频 优先权任务有可能阻寒非临界区部分速度巳确定的任务,那 繁切换,以降低调度成本。在CSFA中,任一任务T的非临 么这些低优先权任务的临界区部分的速度若未定义,则其速 度为中断点任务临界区部分的速度(算法j)~1)和p)~r)) 界区部分的速度n()相同,而任一临界区部分x.的速度 因而在式(2)中区分开已定义的临界区部分及未定义的临界 n(z)不尽相同,但是都不小于x,有可能阳塞的任务的非临 区部分。USF算法(式(1))中同一仟务的临界区及非临界区 界区部分的速度(见性质1)。 部分具有相同的运行速度,以B/(T:)作为低优先权任务 首先给出算法描述 对任务r1的最大阻塞时间,且低优先权任务的执行速度不大 a)任务集中的任务按RM算法进行优先权排序,T1具有最高优先 权,T具有最低优先权 于高优先权任务的执行速度。在任务实际运行中,当任务 h)初始化:q=1; 被阻塞时,临界区的运行速度必须继承被阻塞的高优先权任 c)while (q<=n)do 务的执行速度,以满足实时可调度性。式(2)则区分开已定义 d) for (i=g l<=n:1++ 的临界区部分及木定义的临界区部分,在计算中已考虑实际 e)计算r1非临界区部分的速度nn、(T1) f)end for 运行时低优先权任务对高优先权任务的最大阻塞时间,因而 满足任务运行时的实时性要求(见定理2)。 g)ηm=ax:nn(;)|,初始化临时资源集合TSR为空 式(2)的求解分两种情况讨论,即 max nctdefiaed,C h) for(i=g: i<=m: i ++)do (xn;)/n≥ maxdefined(,C.(x,)/n。(z,)}或 )i(n。(z,)未定义(1≤j≤N(T))) naxnetdefined(.I Ce(z,, )/m. i max defined(, i Ce,(z,)/. k)n(21,)=nm (xn,)}。两种情况下求出的速度应满足分类条件的要求,不 Else 将s(x.)无重复地添加到TSR中 符合则舍去;若同时满足则选择最小值作为非临界区部分的执 m)end if 行速度。 n en 性质1 CSSFA中任一任务的非临界区部分的速度均不 )for(j=m+1;j<=n;j++) 大于有可能阻塞它的临界区部分的速度。 )i(3s(z1,)∈ TSR Hud,k天定义)or(3.(x;)∈ TSR aud 证明 CSSFA每次求出一个中断点任务后,算法h)-s) 21已定义adq(x1,k)<nn) q)m…(;)=n 对目前有可能阳塞r,…,Tm的临界区部分的速度进行了处 r)end if 理。若临界区的速庋未定义,则将其定义为中断点任务的非 s)end for 临界区部分的速度;若临界区的速度已定义而其速度小于当 前中断点任务的非临界区部分的速度时,则调整其速度使之 u end while y)重新计算任务Tn的非临界区部分的速度。 等于当前中断点任务的非临界区部分的速度,故命题成立 CSFA中d)~s)的每次循坏中,定义τ。为中断点任务。 由CsFA可知,当其执行完毕后,对于每个任务T,至少 其中rn的非临界区部分的速度为Tn(算法g)。 cSsFa d)~ 存在某一个S,∈S,使得 s)中称临界区x(i≥q)的速度未定义( notdefined(x,)),当 ∑[Cn(r)/n,(T,)+∑C(2n,k)/m、(zn,k)]「S:,/T1+ 且仅当不有在某一5(x.,)=5(x,)(其中x<q),即任务临界 C(x.y)/n(x1,)≤S 区z不阳塞所有优先权高于T:的任务;香则称,的速度已其中x,有可能阻塞任务T。 定义( defined(2,))。 由于已定义的临界区速度在算法屮可能会被修改(算法 依照本文假设的计算模型,定义任务r的调度点集合p)和q),在v)步按式(3)重新计算任务T,非临界区部分的 为S={T=1,…,i;k=1,…,T/T。 速度。τ。非临界区部分的速度调整之后,其他仟务T(1≤i< 690 计算机应用研究 第25卷 n)的非临界Ⅸ部分的速庋不可能再降低;杏则会导致rn不满次数比CSFA最多多出(n-1)c次。因 CSSA的动态调度 足式(3),因而使得τ。非临界区部分的速度进一步下降,按照成本优于USF算法 定理1则更有可能降低系统的能耗。 定理2 CSSFA能保证所有任务在实际运行中的实时可3试验结果 调度性。 本章测试CSFA和IsH算法的调度性能,性能指标为能 证明CSFA执行完毕后,对每个任务T,式(3)均成立。耗。测试采用模拟仿真,设任务集合有10~15个周期性任务 证明方法类似文献[12],采用反证法。若在运行中任务τ的为使测试更加全面,考虑了不同任务粒度,任务周期分别为 某一实例在其截止期内无法完成,其绝对截止期为t,则假设:[90,200],200,2000],[2000,5000。对于这三个区间,任 为小于时间点t且在t以前没有优先权大于T的任务实例到务的WFT分别为[10,20],[10,100],[10,500]。共享资源 达的最晚时间点。若这样的时间点不存在,则令t=0。对的数量为[0,4],任务临界区的数量为[0,4],临界区部分在 任务T的每个调度点S=S,令A为在[t,+S,到达且优任务中的位置随机选取。任一任务T,的临界区WCET为 先权不小于T的任务实例集合,B为在[t’,t+S,]到达且优0.2cCN(r),1.8aC/N(T)]。其中a为临界区执行时间 先权小于T的任务实例集合,则根据PCP,集合B中的任务实与C比例,其值为3%~30%,步长为3%。利用率U为0.1~ 例在[t,+S阻塞r的时间至多为mxC.(x,)m。0.7。测试中的随机数均采用均匀分布。每次模拟测试中,任 (z,)}。其中z.,有可能阳塞任务。集合A中的任务实例在务集合运行时间为200该模拟程序采用GNUC,并在 Linux os2.4.18,512 MB RAM,2.0 CHz AMD CPU的单机上 r',r'+S,]执行时间至多为∑[Cn(T)/mn(T,)+∑C 模拟测试。 z,k)/nn(zx.)]「S,/们。根据假设,任务T错失其截止期,3.1综合测试结果 则对每个S.在时间长度为S.,内有∑[C=(T)/nm(T,)+ 图1显示CSFA比UsFI性能提高的百分比,横坐标代表 ∑C(2)/n(2)]「S/71+mxC.(x,)/n,(2,)>利用率U本次测试中除利用率外,其他参数均随机选取 S,与式(3)矛盾,故命题成立 CSSFA除了在任务运行前计算其静态的运行速度,在实际 运行时针对特殊情况给出了其动态执行速度。 定义任务T;在时间t时的剩余执行时间为R(T,4),即尚 未完成的临界区及非临界区部分的剩余执行时间(按照它们 的静态速度计算而得)。 定理3假设在时间t时只有任务τ的实例在运行,其他 任务的实例均已完成。若所有任务的下一实例最早到达时间 图综合性能比较 为P且R(T,t)+t<P,则任务T实例未完成部分(包括临界 从图1可以看出, CSSFA在调度性能上明显优于USFI。 区)的速度可调整为R(T,t)/(P-t)。 当利用率U较小,即任务能允分利用空闲时间降低其运行速 证明由丁除的实例外所有任务的已到达实例在时间度时,CSTA较之USH的度性能提高的比例越高。这充分 t时均已完成且R(T,1)+t<P,表明在其他任务实例到达前, 表明(SFA固定临界区速度使得非临界区部分利用更多的空 任务τ的实例按静态速度完成时依然冇在空闲时间,而这些闲时间,能有效地降低系统能耗。同时,定理3给出的方法在 空闲时间可以用于T,的实例以更小的速度运行。当速度调整实际运行中进一步降低了能耗。随着U的提高,即可用空闲 为R(r,)/(P-t),任务的实例在所有任务的下一实例最时间的减少,两种算法的调度性能趋于一致。同时由2.2节 早到达时间之前可以完成,因而不会抢占或阻塞其他任务的的分析可知,CSFA的动态调度成本明显优于USF算法,在 实例,满足实时可调性的条件。 实际应用中能进一步提高调度性能。 3.2c对调度性能的影响 2.2调度成本分析 图2给出当U为0.3时,α对调度性能的影响;其他参数 算法的讲度成本包括静态利动态湖度成本两个方面。静随机选取,横坐标代表值。 态调度成本是指计算静态速度的时间复杂度;动态调度成本 是指任务实例运行时速度调整时的开销。 假设每个任务调度点的最大数目为m,每个仟务临界区的 最大数日为c,则USFI算法的静态时间复杂度为O(mn2); CSFA中d)-f)的时间复杂度为O(m),h)-t)的时间复杂 度为0(cn),则CSFA的静态时间复杂度为O(m+c)n2)。 两种算法具有相近的时间复杂度。 图对词庋性能的影响 定义算法的动态调度成本为任务运行时速度调整的次数。 从图2可以看出,随着a的提高,即临界区执行时间比 对于非临界区部分, CSSFA与USFI速度调整的次数相同;US-例的提高,CSFA较之USH在调度性能上提高的比例越大,表 F的频率继承导致USF对每个任务临界区部分的速度调整明固定临界区速度使得非临界区部分利用更多的空闲时间 第3期 韩建军,等:基于任务同步及节能的实时调度算法 ·691· 能有效地降低系统能耗。但是,α提高到一定的程度, CSSA[2] CHANDRAKASAN A, SHENG S, BRODERSEN R. Low-power 较之ISFI在调度性能上提高的比例反而呈下降趋势。其原因 CMOS digital design[J. IEEE J Solid-State Circuit, 1992, 27(4) 在于临界区执行比例到达一定程度时,意味着被其阻塞的任务 473-484 的剩余执行时间大于临界区扒行时间的概率随之下降。出推 13 ZHU Da-kai, MELHEM R, CHILDERS B R Scheduling with dynamic oltage/speed adjustment using slack reclam ation in multiproces sor 论1可知,能耗下降的比例也随之下降。 real-time systems[ J. IEEE Trans on Parallel and Distributed 3资源数量对调度性能的影响 Systems,2003,14(7):686-699 图3给出当U为0.3时,资源数量对调度性能的影响;其[4] YaN Le, LUO Jiong, JHA NK. Joint dynamic voltage scaling and 他参数随机选取,横坐标代表资源数量。由于资源数量为0 daptive hody biasing for hetergeneous distributed real-time embed ded systems[J. IEEE Trans on Computer Aided Design of Inte- 即无须任务同步)时两种算汰的调度性能一样,仅考虑资源 grated Circuits and Systems, 2005, 24(7): 1030-1041 数量大丁0的情况。 [5 CHABINI N, WOLF W. Unification of scheduling, binding, and reti 图3表明随着资源数量的增加, CSSFA较之USFI在调度 Illing lu reduce po wer consuinlpLiOil under Linings and resouree con 性能提高的比例逐渐下降。原因在于根据PCP,每个任务在实 straints J. IEEE Trans on Very Large Scale Integration Sys 际运行中最多只被低优先权任务阻塞一次,因而任务被阻寒 tems,2005,13(10):1113-1126 的概率随之下降,而 CSSFA中任务临界区部分执行速度固定[6] STANKOVIC J A, SPURIM S, NATALE M D. Implications of classi 且不小于被阻塞的任务非临界区部分速度,因而导致能耗提 cal scheduling results for real-time systems J]. IEEE Trans on 高。从试验数据发现,当资源的数量及α都相对较大时,CSs- Computers,1994,28(6冫:16-25 [7] ZHANG Fang, CHANSON S T. Blocking-aware processor voltage FA在调度性能上逊于USFI算法。 scheduling for real-time systems[J. ACM Trans on Embedded Computing Systems, 2004. 3(2): 307-335 [8 JEJURIKA R, GUPTA R Energy aware task scheduling with task syn chronization for embedded real-time systems[J. IEEE Trans on Computer Aided Design of Integrated Circuits and Systems 2006,25(6):1024-1037 [9] LIU C L, LAYLAND J W. Scheduling algorithms for multi-program ming in a hard real-Lime environment[ J]. Journal of the ACM 图资源数量对调度性能的影响 1973,20(1):46-61 [10 SHA Lu, RAJKUMAR R, LE HOCZKY J. Priority inheritance proto- 致谢:感谢美国 University of Delaware高光荣教授对本文 ols: an approach to real-time synchronization[ J]. IEEE Trans on 提出的宝贵建议。 Computers,1990,39(9):1175-185 [11] LEHOCZKY J, SHA Lu, DING Ye. The rate monotonic scheduling al 参考文献: gorithm: exact characterization and average case behavior[C//Proc I BURD T D, BRODERSEN R W. Energy efficient CMOS micro-pro of ieeE Real-time Systems Symposium. 1989 cessor design[ C//Proc of Hawaii Int'I Conf on System Science. [ 12] BAKER T P. Stack-based scheduling of real-time processes[J] 1995:288-297. Journal of Real-time Systems, 1991, 3(1): 67-99 上接第686页)GA和PO算法,证明了QPSO算法在求解JSSP[2] KENNEDY J, EBERHART R C. Particle swarm optimization [C1 时的有效性,并且计算速度更快,同时取得了比GA和PO算 Proc of ieee international conference an Neural networks. pisca 法更好的调度效果。从图1可以看出,QFSO算法的收敛速度 tawas: IEEE Press, 199541942-1948 更快,全局收敛能力更强,由此证明了QFSO算法在收敛性能 [3 SHI Y, EBERHART R C. A modified particle swarm optimizer[C]// 及解决JSP上的优越性。 Proc of IFFE, International Conference on Fvolutionary Computatin Piscataway: IEEE Press, 1998: 69-73 5结束语 [4 CLERC M. The swarm and queen: towards a deterministic and adap tive particle swarm optimization[ C]//Proc of CEC. Piscataway: IEEE Press,1999:1951-1957. 本文在讨论共型JSP的基础上,提出了将一种目前最新 的群体智能优化算法QPO用于解决JSP。QSO算法相比51 suN Jun, FENC Bin, XU Wen-bo, Particle swarm optimization with particles having quantum behavior[C]//Proe of Congress on Evolu GA、PSO算法计算更简单、收敛速度更快,并可以防止算法早 tionary Computation. 2004: 325-331 熟,有利于发现更优解,从而具有更好的全局收敛性能。其搜[6]曾建潮,介婧,崔志华。微粒群算法[M].北京:科学出版社, 索成功率远远高于其他算法,这对于求解大规模的JSSP是十 2004 分有利的。仿真实例将QPSO算法应用于求解复杂的JssP,调[7] sUN Jun, XU Wen-o, FENG Bin. A global search strategy of quan 度结果显示了它具有良好的调度效果,证明了其有效性。 Lull- behaved particle swall oplinizaliun [C]// Prve of IEEE Conle rence on Cybernetics and Intelligent Systems. 2004: 111-116 参考文献: 18 CLERC M, KENNEDY J. The particle swarm: explosion, sta bility, and [1]王凌.车间调度及其道传算法[M].北京:清华大学出版社, convergence in a multi-dimensional complex space[J. IEEE Journal 2003 of Evolutionary Computation, 2002, 6(1): 58-73