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