Abstract: A new high reliability primary/backup scheduling algorithm called HRPB is proposed to solve the issue when scheduling backup copies with fewer processors where tasks have precedence constraints in heterogeneous distributed systems. The tasks can be modelled as a Directed Acyclic Graph（DAG） and the proposed algorithm schedules two copies of each task. When sorting tasks, it adopts a new index called ALST based on tasks’ execution time and deadline. When selecting processor, it considers preparing one more backup copy to solve the issue when scheduling backup copies with fewer processors where tasks have precedence constraints. Also, it changes the method of calculating the reliability of backup copy schemes. Finally, the simulation experiment is based on randomly generated DAGs. The results show that the proposed algorithm performs better than eFRD in terms of the scheduling success rate of backup copy and system reliability.

Key words: heterogeneous distributed systems, precedence constrained tasks, Directed Acyclic Graph（DAG）, primary/backup copy, task scheduling

摘要： 针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，提出一种新型高可靠性主副版本调度算法（HRPB）。任务模型以有向无环图（DAG）表示，该算法共计调度主、副两个版本的任务。在任务优先级排序阶段，根据任务执行时间及截止时限来制定新指标平均最晚开始时间（ALST）进行排序；在任务处理器分配阶段，采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试，实验结果表明，HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。

关键词: 异构分布式系统, 优先级约束任务, 有向无环图, 主副版本, 任务调度