异构分布式系统混合型实时容错调度算法

摘要

The primary/backup process is commonly used in heterogeneous distributed systems with fault-tolerance.This paper proposed a heterogeneous distributed hybrid model with fault-tolerance. Compared with the traditional heterogeneous distributed scheduling models, this model can simultaneously schedule both periodical and aperiodical tasks.Three fault-tolerant scheduling algorithms based on this model were presented: SSA(schedulability Scheduling Algorithm) algorithm aimed at schedulability, RSA(Reliability Scheduling Algorithm) algorithm aimed at reliability and BSA(Balanced Scheduling Algorithm) algorithm aimed at load equalization. These algorithms can simultaneously process real-time tasks in demand of periodical or aperiodical fault-tolerance in heterogeneous systems. And they can guarantee that real-time tasks could complete befor the cut-off time even if some node of the system fails. Finally, this paper analyseds the algorithms in five ways: schedulability, reliability cost, load equalization, number of periodical and aperiodical tasks, cycle and granularity. Experiment results show that the algorithms have advantages and disadvantages respectively, so they should be chosen according to the characteristics of a specail heterogeneous system.%基/副版本技术是实现实时分布式系统容错的一个重要手段.提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务.在此基础上给出3种客错调度算法:以可调度性为目的SSA算法、以可靠性为目的RSA算法、以负载均衡性为目的BSA算法.算法能够在异构系统中同时调度具有周期和非周期容错需求的实时任务,且能够保证在异构系统中桌节点机失效情况下,实时任务仍然能在截止时间内完成.最后从可调度性、可靠性代价、负载均衡性、周期与非周期任务数及任务周期与粒度5个方面对算法进行了分析.模拟实验结果显示算法各有优缺点,所以在选择调度算法时应该根据异构系统的特点来选择.