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

TLDR

The paper proposes an efficient offline scheduling algorithm for real‑time tasks with precedence constraints in heterogeneous systems. The algorithm models heterogeneity in computation, communication, and reliability, employs a primary‑backup copy scheme that allows overlapping backups on the same processor when primaries are on different processors, and allocates tasks to minimize schedule length and reliability cost while incorporating fault detection time. Compared with existing algorithms, the proposed method improves reliability by 16.4 % and performability by 49.3 % while offering additional features for heterogeneous real‑time scheduling.

Abstract

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.