|
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)。 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所示。 |
|
核心期刊网（www.hexinqk.com）秉承“诚以为基，信以为本”的宗旨，为广大学者老师提供投稿辅导、写作指导、核心期刊推荐等服务。 核心期刊网专业期刊发表机构，为学术研究工作者解决北大核心、CSSCI核心、统计源核心、EI核心等投稿辅导咨询与写作指导的问题。 投稿辅导咨询电话：18915033935 投稿辅导客服QQ： 投稿辅导投稿邮箱：1003158336@qq.com |
| 你好，欢迎来到！ 设为首页 ｜收藏本站 | ||
|
