A new study for fault-tolerant real-time dynamic scheduling algorithms

Abstract

Many time-critical applications require predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. Failures can happen either due to processor faults or due to task errors. To tolerate both processor and task failures, the copies of every task have to be mutually excluded in space and also in time in the schedule. We assume that each task has two versions, namely, primary copy and backup copy. We believe that the position of the backup copy in the task queue with respect to the position of the primary copy (distance) is a crucial parameter which affects the performance of any fault-tolerant dynamic scheduling algorithm. To study the effect of dis- tance parameter, we make fault-tolerant extensions to the well-known myopic scheduling algorithm [Ramamritham et al. IEEE Trans. Parallel Distr. sys. 1 (2) (1990) 184] which is a dynamic scheduling algorithm capable of handling resource constraints among tasks. We have conducted an extensive simulation to study the effect of distance parameter on the schedulability of the fault-tolerant myopic scheduling algorithm.