On fault-sensitive feasibility analysis of real-time task sets

In this paper, we consider the problem of checking the feasibility of a set of n aperiodic real-time tasks while provisioning for timely recovery from (at most) k transient faults. We extend the well-known processor demand approach to take into account the extra overhead that may be induced by potential recovery operations under earliest deadline first scheduling. We develop a necessary and sufficient test using dynamic programming technique. An improvement upon the previous solutions is to address and efficiently solve the case where the recovery blocks associated with faults of a given task do not have necessarily the same execution time. Further, we provide an on-line version of our algorithm that does not require a priori knowledge of release times. The on-line algorithm runs in O(m/spl middot/k/sup 2/) time where m is the number of ready tasks. We also show how to quickly adjust the recovery-related parameters of the algorithm for the remaining part of the execution when a fault is detected.