ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (3): 760-768.doi: 10.7544/issn1000-1239.2015.20130677

Previous Articles     Next Articles

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

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

CLC Number: