An Efficient Fault-tolerant Scheduling Algorithm for Real-time Tasks with
Precedence Constraints in Heterogeneous Systems

Xiao Qin     Hong Jiang     David R. Swanson

Department of Computer Science and Engineering
University of Nebraska-Lincoln
Lincoln, NE 68588-0115,
{xqin, jiang, dswanson}@cse.unl.edu

In this paper, we investigate an efficient off-line scheduling algorithm in which real-time tasks with precedence constraints in a heterogeneous environment. It provides more features and capabilities than existing algorithms that schedule only independent tasks in real-time homogeneous systems. In addition, the proposed algorithm takes the heterogeneities of computation, communication and reliability into account, thereby improving the reliability. To provide fault-tolerant capability, the algorithm employs a primary-backup copy scheme that enables the system to tolerate permanent failures in any single processor. In this scheme, a backup copy is allowed to overlap with other backup copies on the same processor, as long as their corresponding primary copies are allocated to different processors. Tasks are judiciously allocated to processors so as to reduce the schedule length as well as the reliability cost, defined to be the product of processor failure rate and task execution time. In addition, the time for detecting and handling of a permanent fault is incorporated into the scheduling scheme, thus making the algorithm more practical. To quantify the combined performance of fault-tolerance and schedulability, the performability measure is introduced. Simulation results show that the proposed scheduling algorithm significantly improves the schedulability, the reliability, and performability over existing, comparable algorithms in the literature.

in Proceedings of the 31st International Conference on Parallel Processing (ICPP 2002), August 18-21, 2002, Vancouver, British Columbia, Canada

---