Optimal and fault-tolerant scheduling algorithm for multi-tasks in distributed control systems

In distributed control system (DCS), hard real-time tasks must be finished before their deadlines, otherwise the catastrophes occur. Therefore, fault-tolerance must be offered for DCS. In order to schedule many kinds of different real-time tasks, dual priority queues scheduling algorithm is given for uniprocessor and the schedulable condition of the tasks is investigated. For DCS, combining task duplication technique and scheduling algorithm for uniprocessor, a new fault-tolerant scheduling algorithm is presented. The schedulability of the algorithm is analyzed and the schedulable condition is investigated. Basing on this, a heuristic static algorithm for assigning tasks to processors that can guarantee the load of every processor to be balanced is given. In the case that the deadlines of all real-time tasks are met, the non-real-time tasks are scheduled in the spare resource of real-time tasks and the deadlines of primary copies are optimized, so as to improve utility of processor. The simulation experiments show that the algorithm is effective.