Probabilistic scheduling guarantees for fault-tolerant real-time systems

Abstract

Hard real time systems are usually required to provide an absolute guarantee that all tasks will always complete by their deadlines. We address fault tolerant hard real time systems, and introduce the notion of a probabilistic guarantee. Schedulability analysis is used together with sensitivity analysis to establish the maximum fault frequency that a system can tolerate. The fault model is then used to derive a probability (likelihood) that, during the lifetime of the system, faults will not arrive faster than this maximum rate. The framework presented is a general one that can accommodate transient 'software' faults, tolerated by recovery blocks or exception handling; or transient 'hardware' faults dealt with by state restoration and re-execution.