多处理器环境中基于节能及容错的实时动态调度算法  

Real-Time Dynamic Scheduling Algorithms for the Savings of Power Consumption and Fault Tolerance in Multi-Processor Computing Environment

作　　者：韩建军[1] 甘露[1] 阮幼林[2] 李庆华[1] Abbas A.Essa 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074 [2]南京大学计算机软件新技术国家重点实验室 [3]南京大学电子科学与工程系,南京210093

出　　处：《计算机研究与发展》2008年第4期706-715,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60503048,60673191);中国博士后基金项目(20070410280);南京大学计算机软件新技术国家重点实验室开放基金项目(A200608)

摘　　要：当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法: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.

关 键 词：实时系统 多处理器系统 调度算法 能量消耗 容错 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]