Real-time Distributed Fault-tolerant Scheduling Algorithm

Task scheduling in Real-time Distributed Computer System(RTDCS) is an issue that is full of challenge, also a hot research subject nowadays. Because task scheduling problem is a typical NP problem and a critical aspect which directly impacts the system performance, to study task scheduling scheme in RTDCS is of great significance.But in recent result, the fault-tolerant scheduling algorithm almost requires that all task's periods are the same and equal to their deadlines, but in fact the periods are not the same in many cases. According to the characteristics of distributed control systems and the technique of primary/backup copies, based on EDF algorithm the novel fault-tolerant scheduling algorithm is proposed in this paper.The algorithm can deal with the different periods of all tasks. By using setting their deadlines the problem that execution times of primary and backup copies are not overlap can be controlled. The method for setting deadlines of primary and backup copies is given and the schedulability of task set is analyzed.The maximal utilization of task set and the minimal number of processor are investigated. The result of simulation shows that the algorithm is effective.