Scheduling optional computations in fault-tolerant real-time systems

We introduce an exact schedulability analysis for the optional computation model under a specified failure hypothesis. From this analysis, we propose a solution for determining, before run-time, the degree of fault tolerance allowed in the system. This analysis will allow the system designer to verify if all the tasks in the system meet their deadlines and to decide which optional parts must be discarded if some deadlines would be missed. The identification of feasible options that satisfy some optimality criteria requires the exploration of a potentially large combinatorial space of possible optional parts to discard. Since this complexity is too high to be considered practical in dynamic systems, two heuristic algorithms are proposed for selecting which tasks must be discarded and for guiding the process of searching for feasible options. The performance of the algorithms is measured quantitatively with simulations using synthetic task sets