一种新的异构实时分布式系统的容错调度算法

Novel Fault-Tolerant Scheduling Algorithm for Heterogeneous Real-Time Distributed Systems

一般来说,异构分布式实时系统中任务的周期并不完全相同且任务的时限不等于它们的周期,同时系统中还有一些无容错需求的任务.因此现有的任务调度算法一般不能满足这些要求.针对这类系统,在结合基版本/副版本技术和EDF算法的基础上,给出了一种新的容错调度算法.该算法由两部分组成:任务分配调度算法和单处理器调度算法.对于单处理器调度算法,本文采用了EDF算法;在此基础上,给出一种启发式静态任务分配算法.分析了系统的可调度性,给出了任务可调度条件和基版本/副版本时限的设置方法.仿真结果表明,这种算法是有效的.

In general, the periods of tasks in heterogeneous distributed real-time systems are not the same and the deadline of task is not equal to its period. At the same time, in the system there are some tasks that do not require fault-tolerance. Therefore, the scheduling algorithms that have studied do not meet these conditions. For the system, a novel fault-tolerant scheduling algorithm is presented based on primary copy/backup copy technique and EDF algorithm. The algorithm is divided into two parts ： one is task-assigning algorithm, the other is scheduling algorithm for uniprocessor. For scheduling algorithm for uniprocessor, EDF algorithm is adopted because it can make best use of processor. Basing on this, a heuristic static task-assigning algorithm is presented. The algorithm assigns the tasks onto processor before system runs and do not change after system runs, so the offset of the algorithm is smaller. The sehedulability of tasks in the system is analyzed and the condition, which the tasks must meet when they are schedulable, is investigated. The method for setting the deadlines of primary copy and backup copy is given. The result of simulation experiments shows that the fault-tolerant scheduling algorithm presented in this paper is effective.