Scheduling hard real-time tasks with tolerance of multiple processor failures

Real-time systems are used extensively in applications that are mission-critical and life-critical, such as space exploration, aircraft avionics, and robotics. Since these systems are usually operating in environments that are non-deterministic, and even hazardous, it is extremely important that hard deadlines of tasks be met even in the presence of certain failures. To tolerate processor failures, the problem of scheduling a set of real-time tasks with duplication is studied. We first prove that the problem of scheduling a set of non-preemptive tasks on m ≥ 3 processors to tolerate one arbitrary processor is NP-complete even when the tasks share a common deadline. A heuristic algorithm is then proposed to solve the problem. The schedule generated by the algorithm can tolerate, in the worst case, one arbitrary processor failure, but in the best case [m/2] processor failures, where m is the number of processors. Experimental data and analysis show that the performance of the algorithm is near-optimal.