SCHEDULING ALGORITHMS FOR FAULT-TOLERANCE IN HARD-REAL-TIME SYSTEMS

Many time-critical applications require predictable performance in the presence of failures. This paper considers a distributed system with independent periodic tasks which can checkpoint their state on some re liable medium in order to handle failures. The problem of preemptively scheduling a set of such tasks is discussed where every occurrence of a task has to be completely executed before the next occurrence of th e same task can start. Efficient scheduling algorithms are proposed wh ich yield sub-optimal schedules when there is provision for fault-tole rance. The performance of the solutions proposed is evaluated in terms of the number of processors and the cost of the checkpoints needed. M oreover, analytical studies are used to reveal interesting trade-offs associated with the scheduling algorithms.