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 hard real-time tasks with duplication is studied. We first prove that the problem of scheduling a set of non-preemptive tasks on m greater-than-or-equal-to 3 processors to tolerate one arbitrary processor failure 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 right perpendicular m/2 left perpendicular processor failures, where m is the number of processors. Experimental data and analysis show that the performance of the algorithm is near-optimal.