摘要
当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法:STFBA1及STFBA2(shortest taskfirst based algorithm)..通过实验与目前所知的有效算法相比,算法具有更好的性能(调度长度及能量消耗)及较低的通信时间复杂度.
Saving energy consumption of modern processors has recently become popular due to the fact that high power consumption increases heat dissipation, which leads to decreased reliability of systems. This paper aims to generate a task schedule that can fully exploit the dynamic scheduling support （as well as the underline voltage/frequency scaling capability） of the target machines such that the real-time constraints can be met with as minimum as possible energy consumption. The algorithm STFBA （shorted task first based algorithm） proposed utilizes the policy of shortest-task-first and other efficient techniques, such as shared slack reclamation, to save energy in homogeneous systems for independent task set and task set with relationship constraints, respectively. STFBA comprises static part and dynamic part to lower time complexity of algorithm. Furthermore, a dynamic fault-tolerance algorithm based on STFBA is proposed, which is combined with the policy of shortest-task-first and checkpoint, to tolerate transient faults during the executions of tasks, while meeting the requirement of timing constraints and reducing energy consumption efficiently. The feasibility condition of checkpoint placement and lower bound of static processing speed is given to reduce the fault-tolerance scheduling costs. Compared with the efficient algorithms presented so far, simulation results indicate that proposed algorithms have much better scheduling performance trade-off in terms of makespan and energy savings when the slack generated by tasks is sufficient.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第4期706-715,共10页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60503048,60673191)
中国博士后基金项目(20070410280)
南京大学计算机软件新技术国家重点实验室开放基金项目(A200608)
关键词
实时系统
多处理器系统
调度算法
能量消耗
容错
real-time system
multiprocessor system
scheduling algorithm
energy consumption
fault tolerance
