论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　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
　　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)。