• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 高性能计算 • 上一篇    下一篇

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

朱永超1,周川1,崔玉伟2,郭健1,吴益飞1   

  1. (1.南京理工大学自动化学院,江苏 南京 210094;2.航空工业西安飞行自动控制研究所,陕西 西安 710077)
  • 收稿日期:2018-09-18 修回日期:2019-01-25 出版日期:2019-09-25 发布日期:2019-09-25
  • 基金资助:

    国家自然科学基金(61673219,61673214);十三五装备预研共用技术(41412040101);江苏省重点研发计划(BE2017161)

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

ZHU Yong-chao1,ZHOU Chuan1,CUI Yu-wei2,GUO Jian1,WU Yi-fei1   

  1. (1.School of Automation,Nanjing University of Science and Technology,Nanjing 210094;
    2.AVIC Xi’an Flight Automatic Control Research Institute,Xi’an 710077,China)

     
  • Received:2018-09-18 Revised:2019-01-25 Online:2019-09-25 Published:2019-09-25

摘要:

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

关键词: 异构分布式系统, 模拟退火, 有向无环图, 主/副版本技术, 任务调度

Abstract:

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.
 

Key words: heterogeneous distributed system, simulated annealing, directed acyclic graph (DAG), primary/backup copy, task scheduling