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

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

作　　者：秦啸[1] 韩宗芬[1] 庞丽萍[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机学报》2002年第1期49-56,共8页Chinese Journal of Computers

摘　　要：目前文献中研究的实时容错调度算法都是基于同构分布式系统 ,系统中的所有处理机完全相同 .该文首先建立了一个基于异构分布式系统实时容错调度模型 ,异构分布式系统中的各个处理机均不相同 .基于该异构分布式系统模型 ,该文引入了可靠性代价 (reliability cost)概念 ,并提出两种静态实时容错调度算法 (RTFTNO和RTFTRC)用于调度周期性实时容错任务 .算法 RTFTRC在调度任务时 ,尽量使系统的可靠性代价最小 ;而算法RTFTNO在调度实时任务时 ,没有考虑系统的可靠性代价 .该文详细讨论了两种调度算法的性能 .性能模拟实验分别比较了两个算法的可靠性代价 ,超时比率和可调度性 ;并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系 .实验结果表明 ,算法 RTFTRC的性能优于算法 RTFTNO.Two real time scheduling algorithms, RTFTNO and RTFTRC are presented, 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 obtained. The reliability cost into the scheduling algorithm in heterogeneous systems are introduced. 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. 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, the simulation results show 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 above algorithms, the impact of schedule threshold on systems performance is also discussed. 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.

关 键 词：异构分布式系统 模拟实验 实时容错调度算法 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]