分布式实时系统的容错调度算法

Algorithms of Fault-Tolerant Scheduling in Distributed Real Time Systems

提出了两种分布式实时容错调度算法 :副版本后调度算法 (BKCL )及无容错需求后调度算法 (NFRL ) ,并研究了算法的时间复杂度 .这两种容错调度算法能同时调度具有容错需求的实时任务和无容错需求的实时任务 .BKCL和 NFRL所产生的调度可保证 :在分布式系统中一个节点机失效的情况下 ,具有容错需求的实时任务仍然可在截止时间内完成 .在描述了两个实时容错调度算法之后 ,分别证明了这两个算法的容错调度正确性 .接着 ,阐述了算法性能模拟方法并对 BKCL和 NFRL算法的性能进行了分析 .实验结果表明 ,两种算法在不同的负载情况下具有不同的优势 .当无容错需求的实时任务的个数远大于具有容错需求的实时任务的个数时 ,NFRL 的性能要比 BKCL的优越 ;当无容错需求的实时任务的个数远小于具有容错需求的实时任务的个数时 ,NFRL的性能比BKCL

This paper proposes two fault tolerant scheduling algorithms for real time tasks and proves the correctness of these two scheduling algorithms. One is called backup copies scheduled last (BKCL) and another is called tasks without fault tolerant requirements scheduled last (NFRL). These two scheduling algorithms can schedule the tasks with the fault tolerant requirements together with those without fault tolerant requirements. For the tasks with fault tolerant requirements, BKCL and NFRL can generate schedules that can tolerate one processor failure. Performance analysis of these two algorithms are presented, each algorithm has advantage under different workload. NFRL is better than that of BKCL when the number of tasks with fault tolerant requirements is far smaller than that of the tasks without fault tolerant requirements. And on the other hand, when the number of tasks with fault tolerant requirements is far greater than that of the tasks without fault tolerant requirements, the performance of BKCL is better than that of NFRL.