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

　　【摘要】：可靠性与节能是实时系统研究中的重要内容，为此，提出一种基于随机任务的可靠性约束与节能调度算法(RCERT)。按相同的电压/频率执行任务，当某些任务不能满足截止期限时，则调高处理器的执行电压/频率，当处理器执行电压/频率被调低时，在任务就绪队列中插入任务恢复时间以保证系统的可靠性。考虑到系统实际运行时产生瞬时错误的概率非常小，设计多个任务共用一个错误恢复时间的算法，将任务的执行电压/频率调至更低水平以节省能耗。基于德州仪器的TIOMAP5912和IntelPXA270处理器进行仿真实验，结果表明，与EDF和MEG算法相比,RCERT算法在保证系统可靠性的前提下可更高效地实现节能。

　　【关键词】：随机任务;可靠性约束；动态电压/频率调节;节能;调度

　　1概述

　　随着处理器性能的不断提升，能耗也变得越来越大，节能已成为一个亟待解决的重要问题ra。目前，已有许多处理器具备动态电压/频率调节

　　(DynamicVoltage/FrequencyScaling,DVFS)功能,允许应用程序执行时动态调整电压/频率以降低能耗。近年来，有很多学者基于DVFS研究了节能调度算法，如文献2-3]提出一种多核系统中基于GlobalEDF的在线节能硬实时任务调度算法，同时，在考虑处理器切换开销的情况下提出了基于帧任务模型的节能调度算法。文献4]基于自适应阈值的任务复制策略计算最佳阈值，利用阈值获取近似最优的任务分组,然后将各分组任务调度到支持DVS的处理器上以节能。文献5]基于多处理器计算机系统的并行任务调度，应用DVFS技术平衡系统的性能和能耗。文献6]针对非周期独立任务提出一种弹性节能调度算法。文献7]基于异构计算系统提出了多种动态节能调度算法。文献8]研究了周期性实时任务节能调度并证明多处理器系统中满足任务截止期限的最优能耗调度是NP难问题。目前，多数节能调度都是通过关闭处理器或降低相关任务执行电压/频率的方式实现节能。但是，已有研究表明，随着CPU运行频率的降低，系统的瞬时错误会增加9,而瞬时错误增加会降低系统的可靠性。由此，有些学者研究了任务调度过程中可靠性与节能的问题，如文献[10]提出了实时周期性任务静态和动态RA-PM(Reliability-warePowerManagement)调度，证明了静态RA-PM是NP难问题。文献11]在保证系统可靠性的前提下通过调节处理器的速度和关闭处理器以节省能耗。文献12]设计了基于帧的实时任务集调度算法，在保证系统可靠性的前提下使能耗最小化。现有同时考虑可靠性和节能的算法多是基于周期性任务或帧任务，要求已知任务的相关属性和周期，不适合处理随机任务。基于以上分析，本文提出一种基于随机任务的可靠性约束与节能调度算法（SchedulingAlgorithmofReliabilityConstraintandEnergy-efficientbasedonRandomTasks,RCERT),在保证系统可靠性的前提下实现高效节能。

　　2系统模型及问题定义

　　2.1任务模型

　　考虑_个随机到达的任务集T={^,t2，…，tn},t,用一个三兀组{a,,w,,d,}表示，其中，a,表示t,的到达时间；w,表示t,的最坏计算时间（Worst~caseExecutionTime,WCET)表示t,的截止期限，任务

　　到达时，三元组的信息即可被获取。当处理器的运行电压/频率可调时，设w,是处理器以最大频率/_运行时的时间，若处理器以频率f运行，则其运算时

　　间为w'/^。

　　2.2处理器能耗模型

　　根据文献1-5],处理器以频率/运行时,其功耗函数可表示为：

　　P/)=a/3+yS,a>0,彡0(1)

　　考虑到实际处理器的频率一般为离散可调，本文沿用文献13]中的功耗数据，分别采用德州仪器的TIOMAP5912处理器和IntelPXA270处理器进行仿真实验,其运行频率和功耗关系如表1所示。

　　2.3错误模型

　　系统运行时发生的错误一般包括瞬时错误和永久错误，但瞬时错误更加常见&4，因此，本文只考虑瞬时错误，假设系统发生的瞬时错误服从泊松分布,处理器以频率/(对应的电压为V)执行任务时的瞬时错误率为11041:

　　A(f)=A0g(f)⑵

　　其中，A。是处理器以最大频率执行时的平均错误率，随着处理器执行频率的降低，错误率变大，因此，当/</mJ时有g/)>1。

　　2.4问题定义

　　给定一个随机到达的任务集T和一个DVFS可调的处理器，为使系统满足可靠性，要求执行任务时的瞬时错误率保持在A。的水平并尽量节能。

　　3RCERT算法

　　3.1设计思想

　　假设处理器上的任务按最早截止期优先(EarliestDeadlineFirst,EDF)调度算法执行，为使系统满足可靠性要求，如果某个任务以最高电压/频率执行,则其错误率为A。，满足系统可靠性要求。为达到节能的目的，在任务满足截止期限的前提下，可以调低一些任务的执行电压/频率，但任务的执行电压频率被调低时，则会导致可靠性达不到要求，这时发生错误的任务必须被重新执行。因此，需要在被调低的任务后面安排一个错误恢复时间，以便当任务发生错误时可恢复，为使错误恢复执行时满足可靠性,本文设定被恢复执行的任务使用最大电压/频率执行。

　　3.2算法描述

　　当任务t,到达时，立即获取三元组{a,,w,，,}的信息，根据3.1节所述设计思想，算法描述如下（为表示方便，算法中的t,，,,。,/),直接写成t"C,，D,的形式）：

　　RCERT(ti)/*若ti可调度则返回1,否则返回0*/

　　1.EDFInsert(ti)/*将ti插入到处理器的任务队列*/

　　2.recoveryTime=wi/MaxSpeed/*构造错误恢复时

　　3.iflist.length==1then/*如果处理器空闲*/

　　4.s=wi/(di-ai^ecoveryTime)/*计算插入recoveryTime

　　之后的速度*/

　　5.ifs>MaxSpeedthens=wi/(di-Ai),recoveryTime=0;

　　6.ifs>MaxSpeedthenreturn0/*调度到该处理

　　器不能满足截止期限要求*/

　　7.s=GetSpeed(s)/*获得大于等于s的最小执行

　　频率*/

　　8.else/*如果处理器队列上已有任务*/

　　9.total_W=处理器上还未执行的任务的总计算量time=

　　10.上还未执行的任务的可用计算时间

　　11.s=total_w/(time-total_recoveryTime)

　　12.ifs>MaxSpeed&&IsTaskAllMaxSpeed()==truethen

　　13.return0;

　　14.else

　　15.minspeed=GetMinSpeedGrade(list)/*取任务队列中的最小执行电压/频率*/

　　16.whiles>MaxSpeed級IsTaskAllMaxSpeed()==false

　　17.ifminspeed小于第3级then

　　18.将所有任务的执行电压/频率升高至minspeed+1级

　　19.重新计算s

　　20.Minspeed++

　　21.else

　　22.从第一个未执行的任务开始将执行电

　　压/频率逐个调至最大，释放对应的recoveryTime

　　23.重新计算s

　　24.endwhile

　　25.ifs>MaxSpeedthenreturn0

　　26.endif

　　27.endif

　　28.return1