主/副版本模型中预分配容错实时调度算法  

Fault-Tolerant Real-Time Scheduling Algorithm with Pre-Allocation in Primary/Alternate Model

作　　者：刘娴[1,2] 郭锐锋[2] 邓昌义[1,2] 

机构地区：[1]中国科学院大学,北京100049 [2]中国科学院沈阳计算技术研究所,沈阳110168

出　　处：《计算机研究与发展》2015年第3期760-768,共9页Journal of Computer Research and Development

基　　金："核高基"国家科技重大专项基金项目(2012ZX01029001-002)

摘　　要：实时系统中任务的超时完成可能导致灾难性后果,因此要求系统具备容错处理能力,以保证系统出错后的实时性及可靠性.主/副版本模型是提高实时系统容错能力的有效技术.传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错,为副版本预留的处理器时间在系统运行过程中需动态调整,增加了系统的容错调度开销.提出一种基于res-backwards-RM预分配子算法的容错实时调度算法BCE*,通过限制预分配过程中高优先级任务的抢占条件,在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整,降低系统的容错调度开销.仿真实验验证了BCE*算法的可行性及有效性,且在系统出错概率及主版本负载较低的环境下,BCE*算法对系统容错调度开销的优化效果更显著.A real-time system is supposed to provide fault tolerance to keep the system meeting its stringent timeliness and reliability requirements in the presence of faults.The primary/alternate model is an effective method for enhancing the capability to tolerate faults.Most fault-tolerant realtime scheduling algorithms based on this model at present reserve time intervals for the alternates to provide software fault-tolerance.However,these reserved time intervals need to be modified when their corresponding primaries are successfully completed at run-time,thereby increasing the scheduling overhead.To address this problem,a new fault-tolerant real-time scheduling algorithm,termed as BCE＊,is proposed in this paper.The major contribution of the algorithm is presenting a new pre-allocating scheme which imposes restrictions on the preemption of higher priority task while reserving time intervals for alternates.The theoretical performance analysis presented in the paper demonstrates that the proposed algorithm can avoid the modification of reserved time internals,and meanwhile keep the schedulability of the system.Finally,simulation experiments show that the proposed approach can effectively reduce the scheduling overhead of the system compared with the classic BCE algorithm,and the reduction is significant when both the processor utilization of the primaries and the software fault probability are low.

关 键 词：实时调度 软件容错 主/副版本模型 调度开销 预分配 

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