基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。

Real-Time Scheduling with Fault-Tolerance in Heterogeneous Distributed Systems

Some real time fault tolerant scheduling algorithms have been studied in the literatures. These algorithms, however, are devised for homogeneous distributed systems, which have identical processors. The heterogeneous systems, on the other hand, consist of processors with various computation powers. Since the scheduling is a key factor in obtaining high performance in heterogeneous systems, scheduling algorithms play an important role in the efficiency of heterogeneous systems. This paper presents two real time scheduling algorithms, RTFTNO and RTFTRC, which are able to map tasks onto processors and order their execution so that tasks' real time requirements are satisfied and a minimum schedule length is abtained. We introduce the reliability cost into the scheduling algorithm in heterogeneous systems. The RTFTRC algorithm allocates each task to the processor, which gives rise to the minimum reliability cost. This scheme is able to enhance the reliability of the systems without any extra hardware. The RTFTNO algorithm, however, does not take reliability cost into account. Therefore, our simulation results indicate that under the same workload, the reliability cost generated by the RTFTRC is significantly less than that generated by the RTFTNO algorithm. In addition, we observe from the simulation results that the schedule length generated by the RTFTRC algorithm is shorter than that generated by the RTFTNO algorithm. This fact is the main reason that the RTFTRC algorithm has lower PMD(percentage of missing deadlines) than that of the RTFTNO algorithm. Further more, since the RTFTRC has a shorter schedule length, its schedulability is relatively higher than that of the RTFTNO algorithm. As the schedule threshold is a factor in our algorithms, this paper also discusses the impact of schedule threshold on systems performance. Our simulation experiments show that the schedule threshold has no effect on the RTFTNO algorithm. Schedule threshold has an unnoticeable impact, which is not meaningful, on the RTFTRC algorithm.