基于模拟退火算法的改进主/副版本调度算法

An improved primary/backup scheduling algorithm based on simulated annealing algorithm

针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主/副版本调度算法SAPB。任务模型以有向无环图DAG表示,该算法共计调度主、副2个版本的任务。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主/副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果,并且采取多一重备份策略以解决处理器数量相对较少时任务优先级约束带来的副版本调度易失败问题。最后,通过随机生成的DAG图进行仿真实验,结果表明,相比eFRD等算法SAPB具有更优的副版本可调度性和更高的系统可靠性。

Aiming at the priority constraint oriented task scheduling in heterogeneous distributed systems, we propose an improved primary/backup scheduling algorithm based on simulated annealing algorithm called SAPB. The task model is presented by a directed acyclic graph(DAG) and the proposed algorithm schedules two copies(primary and backup) of each task. For task sorting, we adopt the HEFT task sorting method to avoid the limitation of the task model description in primary/backup scheduling strategies such as eFRD. In task processor selection stage, the simulated annealing algorithm is used to search the solution with higher reliability under the condition of meeting the deadline and it considers preparing one more backup copy to solve the likely scheduling failure caused by task priority constraints when scheduling backup copies have fewer processors. Finally, the simulation experiments based on randomly generated DAGs are carried out. The results show that the proposed algorithm outperforms the eFRD in terms of the schedulability of backup copies and system reliability.