An efficient fault-tolerant scheduling algorithm for real-time tasks with precedence constraints in heterogeneous systems

Xiao Qin, Hong Jiang, D. R. Swanson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

83 Scopus citations


In this paper, we investigate an efficient off-line scheduling algorithm in which real-time tasks with precedence constraints are executed 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 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 Compared with the existing scheduling algorithms in the literature, our scheduling algorithm achieves an average of 16.4% improvement in reliability and an average of 49.3% improvement in performability.

Original languageEnglish (US)
Title of host publicationProceedings - International Conference on Parallel Processing, ICPP 2002
EditorsTarek S. Abdelrahman
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Electronic)0769516777
StatePublished - 2002
Externally publishedYes
EventInternational Conference on Parallel Processing, ICPP 2002 - Vancouver, Canada
Duration: Aug 18 2002Aug 21 2002

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918


OtherInternational Conference on Parallel Processing, ICPP 2002


  • Computer science
  • Costs
  • Distributed computing
  • Fault detection
  • Fault tolerance
  • Fault tolerant systems
  • Performance evaluation
  • Processor scheduling
  • Real time systems
  • Scheduling algorithm

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture


Dive into the research topics of 'An efficient fault-tolerant scheduling algorithm for real-time tasks with precedence constraints in heterogeneous systems'. Together they form a unique fingerprint.

Cite this