A least upper bound on the fault tolerance of real-time systems

Abstract

This paper presents a method to deal with the reexecution of tasks in a hard real-time system subject to temporary faults. The set of tasks follows the Liu and Layland model: they are periodic, independent and preemptible. Time is considered to be slotted. The system is said to be ki-schedulable if it is schedulable in spite of the fact that in the interval between its release and its deadline, every task admits that ki slots are devoted to uses other than its first execution. In this case, the ki slots are used to reexecute tasks subject to temporary faults. Since the value of ki can be easily determined, a least upper bound on all the possible combinations of faults that the system can tolerate while meeting the hard time-constraints, follows immediately. The method is bandwidth preserving and the expression of the bound is a diophantic inequality relating ki, the execution time and the period of each task. The method is compared to methods proposed by other authors to solve the same problem and it is evaluated through extensive simulations performed on random generated sets of tasks.