ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (3): 760-768.doi: 10.7544/issn1000-1239.2015.20130677

• 软件技术 • 上一篇    下一篇



  1. 1(中国科学院大学 北京 100049); 2(中国科学院沈阳计算技术研究所 沈阳 110168) (
  • 出版日期: 2015-03-01
  • 基金资助: 

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

Liu Xian1,2, Guo Ruifeng2, Deng Changyi1,2   

  1. 1(University of Chinese Academy of Sciences, Beijing 100049); 2(Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168)
  • Online: 2015-03-01

摘要: 实时系统中任务的超时完成可能导致灾难性后果,因此要求系统具备容错处理能力,以保证系统出错后的实时性及可靠性.主/副版本模型是提高实时系统容错能力的有效技术.传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错,为副版本预留的处理器时间在系统运行过程中需动态调整,增加了系统的容错调度开销.提出一种基于res-backwards-RM预分配子算法的容错实时调度算法BCE\+*,通过限制预分配过程中高优先级任务的抢占条件,在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整,降低系统的容错调度开销.仿真实验验证了BCE\+*算法的可行性及有效性,且在系统出错概率及主版本负载较低的环境下,BCE\+*算法对系统容错调度开销的优化效果更显著.

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

Abstract: 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 real-time 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.

Key words: real-time scheduling, software fault-tolerance, primary/alternate model, scheduling overhead, pre-allocation