基于随机任务的可靠性约束与节能调度算法(2)

　　RCERT算法在调整处理器电压/频率时，为提高算法效率并使各任务的执行频率尽量_致，如果处理器的频率小于第3级时，则一次将低电压执行的任务调高_级，否则将任务逐个提高至最大电压/频率执行。为保证系统的可靠性，算法为每一个低电压/频率执行的任务构造了_个错误恢复时间，是_种非常保守的算法，因为系统实际运行时产生瞬时错误的概率非常小，所以可使2个甚至多个任务共用_个错误恢复时间。本文设计了i个任务共用-个错误恢复时间的算法，具体如下：

　　AdjustRecoveryTime(list,i)/*将任务队列list上的

　　i个任务调整为共用_个recoveryTime*/

　　1.curtask=list.GetFirsttTask

　　2.while任务队列未结束

　　3.k=0;

　　4.maxRTTI=curtask的recoveryTime

　　5.whilek<i&&list未结束

　　6.curtask=list.GetNextTask

　　7.tmpRTTI=curttask的recoveryTime

　　8.iftmpRTTI>maxRTTIthen

　　9.deletemaxRTTI

　　10.maxRTTI=tmpRTTI

　　11.else

　　12.deletetmpRTTI

　　13.endif

　　14.k++;

　　15.endwhile

　　16.curtask=list.GetNextTask

　　17.endwhile

　　3.错误恢复时间经过合并后，能将任务的执行电压频率调节到一个更低的水平，当发生瞬时错误时,又有足够的时间使任务恢复，能保证系统的可

　　靠性。

　　4RCERT算法评估

　　4.1最坏情况的时间复杂度

　　RCERT算法执行的最坏情况是当最后一个任务到达时第一个任务还没有执行完。当第k(1矣k矣n)个任务到达时，任务队列中有k-1个任务需要考虑,算法第1,9,10,12,15行的计算量都为k-1;16行~24行为while循环,17行~20行最多执行3次，单次计算量为2(k-1),所以17行~20行的总计算量为为6(k-l);while循环中的22行~23行，因为有k-1个任务,所以计算量为(k-1)2;其余语句的计算量为1;AdjustRecoveryTime算法因为只需扫描队列一次，计算量为k-1。由此可得第k个任务到达时RCERT算法的计算量为5(k-1)+6(k-1)+(k-1)2+(k-1)=12(k-1)+(k-1)2,因此，考虑n个任务,总计算量为EL112(k-1)+(k-1)2,化简后可知RCERT算法的时间复杂度为O(n3)。

　　4.2实验分析

　　为验证算法的性能，分别应用TIOMAP5912处理器和IntelPXA270处理器的频率与功耗数据，将RCERT算法与EDF(EarliestDeadlineFirst),MEG(MinimumEnergyGreedy)算法进行比较。为体

　　现系统发生的瞬时错误，如表1所示，假设2个处理器的电压/频率为第4级时瞬时错误率都为A。（根据问题定义，瞬时错误率为A。时系统满足可靠性要求，实验中设定A。=0),第3级到第0级的错误率分别为0.1%,0.4%,1%,2%,当调低电压时设定4个任务共用一个错误恢复时间。因为2个处理器的频率差异较大，实验中任务的最坏计算时间w为对应处理器以最高频率执行的时间，能耗用处理器对应频率的功耗乘以时间单位表示。为便于观察能耗差异，各算法产生能耗以EDF为参考进行归一化处理。类似于文献10],本文将系统的可靠性定义为任务在截止期限内被正确执行的概率，在调度过程中如果有任务不能满足截止期限要求，则也认为会降低系统的可靠性。

　　实验1随机产生1〇〇〇个任务，前后2个任务到达的时间间隔为1~20之间的随机数，任务的计算时间w分别为1~4,1~6,1~8,1~10,1~12之间的随机数，任务的截止期限为到达时间加4倍计算时间，RCERT,EDF,MEG算法基于处理器TIOMAP5912和IntelPXA270完成的任务数和相对能耗如图1和图2所示。

　　从图1(a)和图2(a)可知，针对2种不同的处理器，在保证系统可靠性的前提下，RCERT算法完成的任务数和EDF相同。MEG算法因为总是试图以较低的电压执行任务，导致后续到达的任务不能满足截止期限要求,且随着任务计算时间w增加，会出现更多的任务不能满足截止期限，所以MEG算法不能满足系统可靠性要求。RCERT算法则会因任务计算时间w的增加而调高电压/频率,使任务能满足截止期限要求。实际上当RCERT算法把所有任务的频率调至最高的时候,RCERT算法将退化成EDF算法。由图1(b)和图2(b)可以看出，MEG算法相对能耗最低，但完成的任务数少于EDF和RCERT算法。当EDF和RCERT算法完成相同数量的任务时,RCERT产生的能耗总是低于EDF产生的能耗。运用RCERT算法在2个不同的处理器上调度任务时,TIOMAP5912处理器相对于IntelPXA270处理器的节能效果更明显。

　　实验2随机产生1000个任务，前后2个任务到达的时间间隔为1~18,1~20,1~22,1~24,1~26之间的随机数，任务的计算时间w为1~10之间的随机数，任务的截止期限为到达时间加4倍计算时间，RCERT,EDF,MEG算法分别基于处理器TIOMAP5912和IntelPXA270完成的任务数和能耗如图3和图4所示。

　　从图3和图4可知，随着任务到达时间间隔不断变大，EDF和RCERT算法始终能完成所有任务，MEG算法完成的任务数也逐渐增多，但当任务到达的最大时间间隔达到26时,MEG算法仍不能完成所有任务。在相对能耗方面，MEG算法相对能耗最低，但有很多任务没有完成，降低了系统的可靠性。RCERT在和EDF算法能完成所有任务，但RCERT产生的能耗低于EDF产生的能耗，且随着任务到达时间间隔变大，RCERT相对EDF能耗更低。和实验1类似，算法在TIOMAP5912处理器上的节能效果更为明显。

　　综合以上2组实验可知，在考虑系统可靠性的前提下,MEG算法虽然节能效果好，但没有考虑任务截止期限，会导致很多任务不能完成，降低了系统的可靠性。RCERT在满足任务截止期限方面和EDF相同，但RCERT算法更为节能。在实际系统中，处理器的特性的差异也使节能效果存在差异。

　　5结束语

　　本文分析了随机任务调度过程中系统可靠性与节能的问题，提出_种可靠性约束下的节能调度算法，尽量使所有任务按相同的电压/频率执行以实现节能，当某些任务不能满足截止期限时，则调高处理器的执行电压/频率使之满足截止期限要求。为保证系统的可靠性，当处理器执行电压/频率被调低时，算法在任务就绪队列中插入任务恢复时间使发生错误的任务能被正常恢复。最后在2种不同型号的处理器上进行了实验，验证了算法的性能。下一步将基于多处理器系统研究随机任务的可靠性约束与节能调度。

　　参考文献

　　[1]吴小东，韩建军，王天江种基于VFD多核系统的硬实时任务节能调度算法J.计算机研究与发展，

　　2012,49(5):10184027.

　　[2]张冬松，吴彤，陈芳园，等.多核系统中基于GlobalEDF的在线节能实时调度算法J].软件学报,2012,23(4)：996-1009.

　　[3]张冬松，吴飞，陈芳园，等.开销敏感的多处理器最优节能实时调度算法J].计算机学报,2012,35(6):12974312.

　　4刘伟，尹行,段玉光，等.同构DVS集群中基于自

　　适应阈值的并行任务节能调度算法J].计算机学报，2013,36(2)：393-407.

　　[5]LeeYC,ZomayaAY.EnergyConsciousSchedulingforDistributedComputingSystemsUnderDifferentOperatingConditions[j].IEEETransactionsonParallelandDistributedSystems,2011,22(8):13744381.

　　[6]朱晓敏，贺川，王建江，等.异构计算系统中弹性节能调度策略研究J].计算机学报，2012,35(6):13134326.

　　[7]KimJK,SiegelHJ,MaciejewskiAA,etal.DynamicResourceManagementinEnergyConstrainedHeterogeneousComputingSystemsUsingVoltageScalingJ].IEEETransactionsonParallelandDistributedSystems,2008,19(11)：1445-4457.

　　[8]LeeWY.Energy-efficientSchedulingofPeriodicRealtimeTasksonLightlyLoadedMulticoreProcessorsJ].IEEETransactionsonParallelandDistributeSystems,2012,23(3)：530-537.

　　9ZhuDakai,MelhemR,MosseD.TheEffectsofEnergyManagementonReliabilityinReal-timeEmbeddedSystems[C]//ProceedingsofIEEE/ACMInternationalConferenceonComputerAidedDesign.WashingtonD.C.,USA:IEEEComputerSociety,2004:35~40.

　　10]ZhuDakai,AydinH.Reliability-awareEnergyManagementforPeriodicReal-timeTasksJ].IEEETransactionsonComputers,2009,58(10)11382-1397.

　　11]LinMan,PanYongwen,YangLT,etal.SchedulingCodesignforReliabilityandEnergyinCyber-physicalSystems［J].IEEETransactionsonEmergingTopicsinComputing,2013,1(2)1353-365.

　　12]LiZheng,WangLi,LiShuhui,etal.ReliabilityGuaranteedEnergy-awareFrame-basedTaskSetExecutionStrategyforHardReal-timeSystems［J].TheJournalofSystemsandSoftware,2013,86(12)：3060-3070.

　　13]ZhuoJianli,ChakrabartiC.Energy-efficientDynamicTask

　　SchedulingAlgorithmsforDVSSystems［J].ACMTransactionsonEmbeddedComputingSystems,

　　2008,7(2).

　　14]CastilloX,McConnelSR,SiewiorekDP.DerivationandCalibrationofaTransientErrorReliabilityModel［J].IEEETransactionsonComputers,1982,100(7):658-671.