实时多处理机系统BEST-FIT启发式容错调度  

Fault-Tolerant Scheduling Based on the BEST-FIT Heuristics for Real-Time Multiprocessor Systems

作　　者：阳春华[1] 计莉[1] 沈德耀[1] 桂卫华[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《计算机工程与科学》2003年第5期61-64,85,共5页Computer Engineering & Science

基　　金：国家863计划资助项目(863-511-945-014)

摘　　要：本文从有效利用资源的角度出发,提出了一种以最小化处理机数目为优化目标的Best-Fit启发式容错调度算法。该算法采用主/副版本备份技术和副版本的主动运行方式与被运行方式相结合的方法,将实时任务的主版本和副版本调度到不同处理机上运行;并且按照Best-Fit启发式策略为实时任务主版本寻找“最佳满足”处理机,使尽可能多的实时任务副版本以被动方式运行。算法既保证了系统的实时性和容错性,也节约了处理机。分析和仿真结果均证明了算法的有效性。This paper proposes a fault-tolerant scheduling algorithm based on best-fit heuristics, which aims at minimizing the number of processors to achieve efficient utilization of resources. By the use of the primary/backup approach and the integration of passive backup and active backup, the primary copy and the backup copy of a realtime task are scheduled on two different processors. The best-fit heuristics try to find' best-fit' processors for scheduling primary copies such that as many backup copies as possible can be executed passively. This not only assures that real-time tasks complete before the deadlines even in the presence of processor failures, but also decreases the number of processors. Both analysis and simulation results show the effectiveness.

关 键 词：实时多处理机系统 BEST-FIT 启发式容错调度算法 单调速率调度算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]