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

作者：朱永超; 周川^*; 崔玉伟; 郭健; 吴益飞

来源：计算机工程与科学, 2019, 41(09): 1534-1540.

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

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

• 单位
  南京理工大学; 自动化学院