异构分布式系统中一种新型主副版本调度算法

doi:10.3778/j.issn.1002-8331.1808-0012

计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (21): 93-98.DOI: 10.3778/j.issn.1002-8331.1808-0012

异构分布式系统中一种新型主副版本调度算法

朱永超，周川，郭健，吴益飞，崔玉伟

1.南京理工大学自动化学院，南京 210094
2.中航工业西安飞行自动控制研究所，西安 710065

出版日期:2019-11-01 发布日期:2019-10-30

New Primary/Backup Scheduling Algorithm in Heterogeneous Distributed Systems

ZHU Yongchao, ZHOU Chuan, GUO Jian, WU Yifei, CUI Yuwei

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

Online:2019-11-01 Published:2019-10-30

摘要/Abstract

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

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

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

朱永超，周川，郭健，吴益飞，崔玉伟. 异构分布式系统中一种新型主副版本调度算法[J]. 计算机工程与应用, 2019, 55(21): 93-98.

ZHU Yongchao, ZHOU Chuan, GUO Jian, WU Yifei, CUI Yuwei. New Primary/Backup Scheduling Algorithm in Heterogeneous Distributed Systems[J]. Computer Engineering and Applications, 2019, 55(21): 93-98.

[1]	张驰，王宇新，冯振，郭禾. 双层虚拟化云架构下任务调度能耗优化算法[J]. 计算机工程与应用, 2021, 57(3): 103-111.
[2]	田倬璟，黄震春，张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用, 2021, 57(2): 1-11.
[3]	向敏，戴柯宇，周恩，刘榆，雷儒杰. 面向物联网终端的任务相关性调度策略[J]. 计算机工程与应用, 2020, 56(23): 95-102.
[4]	于巧玉，吴耀华，王艳艳. 跨层穿梭车双提升机系统料箱拣选任务调度[J]. 计算机工程与应用, 2020, 56(20): 270-278.
[5]	吴波，许道强，邹云峰，王甜甜，李鑫. 阶段感知的跨域数据分析作业保障机制[J]. 计算机工程与应用, 2019, 55(23): 78-85.
[6]	汤琳煜，蒋加伏，谷科. 基于雾计算的计算资源分配方案[J]. 计算机工程与应用, 2019, 55(19): 96-104.
[7]	孙贤明，樊晓光，禚真福，丛伟，陈少华. 综合时频域及核判别分析的两级特征提取新方法[J]. 计算机工程与应用, 2018, 54(3): 115-119.
[8]	贾丽云，张向利，张红梅. 分布式系统下的启发式任务调度算法[J]. 计算机工程与应用, 2017, 53(12): 63-69.
[9]	王向华1，陈特放1，张必明2，颜剑1. 基于时间序列和任务调度的Web数据聚类算法[J]. 计算机工程与应用, 2016, 52(9): 159-163.
[10]	林若男，李强. 云计算环境下基于模板的任务调度策略与算法[J]. 计算机工程与应用, 2016, 52(19): 48-52.
[11]	李岩，崔浩鑫，杜永斌. μC/OS-II二级调度算法的硬件实现[J]. 计算机工程与应用, 2016, 52(12): 1-4.
[12]	王波，张晓磊. 基于粒子群遗传算法的云计算任务调度研究[J]. 计算机工程与应用, 2015, 51(6): 84-88.
[13]	孙凌宇1，冷明1，2，朱平1，李金忠1. 基于赋权有向超图的云计算依赖任务调度研究[J]. 计算机工程与应用, 2015, 51(24): 34-39.
[14]	王振超. 融合DEA和田口方法的云计算多任务调度方案[J]. 计算机工程与应用, 2015, 51(2): 140-145.
[15]	李静梅，张大虎，吴艳霞. 基于异构CMP的改进蚁群优化任务调度策略[J]. 计算机工程与应用, 2015, 51(18): 47-51.

异构分布式系统中一种新型主副版本调度算法

New Primary/Backup Scheduling Algorithm in Heterogeneous Distributed Systems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics