Real-Time Fault-Tolerant Scheduling for Distributed Systems Based on Improving Priority of Passive Backup

Fault-tolerant rate-monotonic first fit (FTRMFF) algorithm is a hard-real-time scheduling broadly used in distributed systems. This scheduling algorithm has the advantages of easy operation and low cost. However, the strategy of priority inheritance on the backup copy probably makes it hard to make full use of the slack located in the existing processors. To solve the problem and on the basis of analyzing the worst case response time of all types of task copies, the “improving priority for passive backup based scheduling (IPPBS)” algorithm is then proposed. When a passive backup copy could not be assigned to the existing processors and needs a new processor, IPPBS algorithm will improve its priority to a reasonable level to shorten the response time. Because its worst case response time becomes shorter, the passive backup copy is likely to be scheduled to the existing processor without breaking the scheduablity feasibility of other tasks with higher priority in the same processor. Moreover, the priority improving of factor searching algorithm is presented in detail. Finally, the adequate simulation experiments show that the IPPBS algorithm is feasible and effective. Compared with the classic FTRMFF algorithm, it can save the processors up to 13%.