摘要
针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主/副版本调度算法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.
作者
朱永超
周川
崔玉伟
郭健
吴益飞
ZHU Yong-chao;ZHOU Chuan;CUI Yu-wei;GUO Jian;WU Yi-fei(School of Automation,Nanjing University of Science and Technology,Nanjing 210094;AVIC Xi’an Flight Automatic Control Research Institute,Xi’an 710077,China)
出处
《计算机工程与科学》
CSCD
北大核心
2019年第9期1534-1540,共7页
Computer Engineering & Science
基金
国家自然科学基金(61673219,61673214)
十三五装备预研共用技术(41412040101)
江苏省重点研发计划(BE2017161)
关键词
异构分布式系统
模拟退火
有向无环图
主/副版本技术
任务调度
heterogeneous distributed system
simulated annealing
directed acyclic graph (DAG)
primary/backup copy
task scheduling