基于多处理机的混合实时任务容错调度  

A Fault-Tolerant Scheduling Algorithm of Hybrid Real-Time Tasks Based on Multiprocessors

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

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

出　　处：《计算机学报》2003年第11期1479-1486,共8页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目 ( 2 0 0 2cb3 12 2 0 10 )资助

摘　　要：提出了一种混合实时任务容错调度算法 .该算法采用RateMonotonic (RM)算法完成周期任务的静态调度 ;采用预订处理机时间方法和EarlierDeadlineFirst (EDF)算法动态调度非周期任务 ;采用主 /副版本备份技术确保系统的容错能力 .通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数 .仿真结果证明了算法的有效性 .This paper proposes a fault-tolerant algorithm for scheduling periodic and aperiodic tasks based on multiple processors. Periodic tasks are assigned to the first-fit processor and scheduled statically following the Rate-Monotonic algorithm. Owing to the unpredictable arrival times and frequencies of aperiodic tasks, they are assigned to the first-fit processor and scheduled dynamically by the combined reservation-based strategy and earlier-deadline-first algorithm once they arrive in the system. A primary/backup approach is used to schedule copies of a task on different processors to tolerate faults. Due to the deterministic knowledge of periodic tasks, the assignment of periodic tasks to processors and the deriving of the least upper bound of reserved processor time are completed off-line, which greatly simplifies the algorithm's on-line implementation and reduces system overhead. This algorithm significantly decreases the number of required processors by integrating passive and active duplication and improves the processor utilization by exploiting the maximum available processing time for scheduling aperiodic tasks, which is left unused by periodic tasks. That is also demonstrated by the simulation results.

关 键 词：混合实时任务容错调度算法 多处理机系统 RB算法 SS算法 

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