FTGS: Fault-Tolerant Fixed-Priority Scheduling on Multiprocessors

In this paper, we consider preemptive scheduling of a set of fixed-priority, sporadic tasks on multiprocessors from both real-time and fault-tolerant perspectives. We propose a fault-tolerant multiprocessor scheduling algorithm, called FTGS, exploiting time redundancy to tolerate both task errors and processor failures. The main contribution of this paper is the derivation of a feasibility test for our proposed FTGS algorithm. This feasibility test when satisfied guarantees that all the deadlines of the real-time tasks are met even in the presence of task errors and processor failures. The major strength of FTGS algorithm is the fault model it assumes; we consider a variety of software and hardware faults that may lead to task errors or processor failures. The novelty of our proposed feasibility test is that the resilience of resource constrained embedded real-time systems can be determined for different combinations of task errors and processor failures.