关键词: 分布式控制系统, 双优先级队列, 容错调度算法

Abstract: In distributed control system (DCS), there are many kinds of tasks, such as hard real-time tasks, soft real-time tasks, non-real-time tasks, and so on. Among them, 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, considering the difference of execution times of primary copy and backup copy of a hard real-time task on a processor and combining task duplication technique and scheduling algorithm for uniprocessor, a new fault-tolerant scheduling algorithm is presented. The schedulability of the algorithm is analyzed. The condition that the tasks must meet when they are schedulable and the method for setting the deadlines of primary copies are 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. The algorithm may improve the utilization of every processor. The simulation experiments show that the algorithm is effective.

Key words: Distributed Control System, Dual Priority Queues, Fault-tolerance Scheduling Algorithm