Fault-tolerant scheduling on a hard real-time multiprocessor system

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 low