An improved feasible shortest path real-time fault-tolerant scheduling algorithm

Fault tolerance is an important aspect of real time computer systems, since timing constraints must not be violated. For a real time single processor environment, S. Ghosh et al. (1995) proposed two queue based scheduling techniques: an FSP (feasible shortest path) algorithm and LTH (linear time heuristics). Even though the FSP algorithm can produce optimal fault tolerant schedules, it is not practical due to its time complexity. The LTH algorithm is a greedy heuristics that closely approximates the optimal. However, since Ghosh´s algorithm assumes that there is at most one fault within time interval Δf and does not consider inter-fault time, it can deteriorate real time scheduling performance due to unnecessary backup scheduling. The authors propose an improved FSP algorithm based on the more realistic assumption that there is no additional fault during minimum inter-fault time ΔF after one fault occurs. The proposed algorithm can improve system performance by including more primary tasks in a fault tolerant schedule and can also reduce time complexity in generating backup schedules