Fault-tolerant scheduling on a hard real-time multiprocessor system
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 775-782
- https://doi.org/10.1109/ipps.1994.288216
Abstract
Fault-tolerance is an important issue in hard real-time systems due to the critical nature of the supported tasks. One way of providing fault-tolerance is to schedule multiple copies of a task on different processors. If the primary copy of a task cannot be completed due to a fault, the scheduled backup copy is run and the task is completed. In this paper, we propose a new algorithm for fault-tolerant scheduling on multiprocessor systems. The algorithm guarantees the completion of a scheduled task before its deadline in the presence of processor failures. Our algorithm schedules several backup tasks overlapping one another and dynamically deallocates the backups as soon as the original tasks complete executions, thus increasing the utilization of processors. Simulation results show that our method achieves higher task schedulability compared to using a spare processor as a backup to be invoked in the event of a failure. Further, we show that the cost, in terms of schedulability, of guaranteeing fault tolerance for dynamic systems is quite lowKeywords
This publication has 7 references indexed in Scilit:
- Workload redistribution for fault-tolerance in a hard real-time distributed computing systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A systematic approach to designing distributed real-time systemsComputer, 1993
- Experimental evaluation of a real-time scheduler for a multiprocessor systemIEEE Transactions on Software Engineering, 1991
- Scheduling processes with release times, deadlines, precedence and exclusion relationsIEEE Transactions on Software Engineering, 1990
- A fault-tolerant scheduling problemIEEE Transactions on Software Engineering, 1986
- On Scheduling Tasks with a Quick Recovery from FailureIEEE Transactions on Computers, 1986
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973