异构分布式系统的可靠性任务调度策略研究

作     者：朱永超 

作者单位：南京理工大学 

学位级别：硕士

导师姓名：周川

授予年度：2019年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：异构分布式系统 有向无环图 主副版本 任务调度 模拟退火算法 

摘      要：随着计算机和网络技术的飞速发展,分布式系统在飞行控制、自动驾驶、地震数据处理等关键领域被越来越广泛地运用,而异构分布式系统在提高计算性能和高可靠性方面具备着很大的发展前景。高效可靠的任务调度策略是异构分布式系统获取高性能的关键。本文针对异构分布式系统的可靠性任务调度策略问题,主要研究工作如下:首先,针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题,提出一种新型高可靠性主副版本调度算法HRPB。任务模型以有向无环图(Directed acyclic graph,DAG)表示,算法共计调度主、副两个版本的任务。在任务优先级排序阶段,根据任务执行时间及截止时限来制定新指标平均最晚开始时间ALST进行排序;在任务处理器分配阶段,采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题。其次,针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主副版本调度策略SAPB。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果。再次,针对异构分布式系统中混合任务的调度问题,提出一种兼顾可靠性的调度算法MRHS。混合任务分为周期性任务与非周期性任务,周期性任务以DAG图模型表示;非周期性任务以四元组模型表示。离线阶段仅调度周期性任务,采取模拟退火算法搜索满足具有更高指标值的调度结果;在线阶段调度随机进入的非周期性任务,利用处理器空闲间隔选择具有更高指标值的调度结果,并引入延迟原则和任务再分配原则解决空闲间隔不满足随机任务调度需求的问题。最后,针对上述提出的可靠性任务调度策略,利用随机生成的任务模型进行仿真测试,验证所提可靠性任务调度策略的性能。