Fault-tolerant real-time scheduling under execution time constraints

Abstract

The primary/backup with deallocation approach of [Ghosh 97] is a strategy for the fault-tolerant online scheduling of hard real-time tasks. In this scheme, tasks are either rejected within a short time after the request or guaranteed to be executed even in case of a processor failure. In this paper several heuristics for the guarantee algorithm are investigated. For the first time different processor selection strategies for guarantee algorithms with execution time constraints are compared. In addition, the concept of a decision deadline is introduced which then leads to an extension of the primary and backup checking routines. The thus modified checking routines are shown to achieve a lower rejection ratio for tight task deadlines and constrained scheduler execution times than the modification making use of task slack suggested in [Ghosh 97].