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

提出了两种分布式实时容错调度算法：副版本后调度算法（ＢＫＣＬ）及无容错需求后调度算法（ＮＦＲＬ），并研究了算法的时间复杂度，这两种容雕工算法能同时调度具有容错需求的实时任务和无容错需求的实时任务，ＢＫＣＬ和ＮＦＲＬ所产生的调度可保证：在分布式系统中一个节点机失效的情况下，具有容错需求的实时任务仍然可在截止时间内完成，在描述了两个实时容错调度算法之后，分别证明了这两个算法的容错调度正确性。接着，阐述

Algorithms of Fault-Tolerant Scheduling in Distributed Real-Time Systems

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.