分布式实时系统任务容错调度优化算法研究

摘要

随着计算机应用的日益流行，分布式实时系统的应用范围越来越广。实时系统具有严格的实时性和可靠性要求，确保实时系统的实时性和可靠性已经成为实时系统研究中亟待解决的问题。实时系统容错调度算法是确保实时性和可靠性的有效方法。任务容错调度是分布式实时系统的一个关键问题，有效的分布式实时系统任务容错调度算法对发挥系统的性能、保证实时系统任务可调度性及可靠性都具有非常重要的意义。分布式实时系统调度首先要确保单机中任务在瞬时性故障发生情况下能够在截止时间内完成，同时也要确保在系统中节点永久性故障发生情况下任务能够在截止时间内完成。
　　目前实时系统容错调度算法虽然已经得到了大量研究，但是仍有一些问题未解决，这些问题限制了现有容错调度算法的应用。因此本论文综合分析目前实时系统任务容错调度算法的研究状况，对分布式实时系统中单机容错调度算法的优化及分布式实时系统任务容错调度算法进行深入研究。本文主要贡献可归纳为以下几点:
　　针对实时系统卷回恢复容错模型只能容忍一次故障发生及单机容错调度算法大多是基于一次故障情况或者是固定故障次数情况下的优化检查点间隔的缺陷，提出了任务局部优化检查点间隔求解算法，使故障发生次数由任务实际响应时间和系统故障发生间隔决定，且最小化任务的响应时间。提出了任务集检查点间隔全局优化算法，对任务集中所有任务的检查点间隔进行优化，以进一步减少多个任务并发执行时的响应时间，提升实时系统容错能力和可调度性。
　　基于卷回恢复容错模型中的局部优化检查点间隔，推导了容错优先级混合策略下的任务最坏响应时间计算公式。依据可调度性分析，提出了基于局部优化检查点间隔的容错优先级混合策略下的容错优先级配置搜索算法，使受故障影响的任务抢占其他任务的空闲时间，以进一步减少任务的响应时间，提高系统可调度性。
　　依据任务可调度性分析，推导了全局优化检查点间隔和容错优先级混合策略下的任务最坏响应时间计算公式。设计了通过检查点间隔全局优化和容错优先级搜索来最小化任务最坏响应时间的优化模型。基于混合PSO算法，提出了检查点间隔全局优化和容错优先级搜索算法，求解所建立的优化模型，进一步减少了任务的响应时间，提高了系统的可调度性。
　　针对异构分布式系统中基于多副本技术的容错调度算法忽略调度Makespan、任务间依赖与系统链路失效及严格调度方式调度Makespan较长问题，提出了通用调度方式下同时考虑节点和链路失效的可靠性计算方法;建立了能够描述该通用调度问题的0-1整数规划模型;基于遗传算法的种群进化机制，提出了可靠性意识多副本任务通用调度算法，来搜索副本映射节点和开始执行时间以求解该0-1整数规划模型，在满足可靠性要求的同时，进一步减小了任务的调度Makespan。
　　通过仿真实验表明，检查点间隔局部优化能够减少单任务执行时的响应时间，检查点间隔全局优化能够进一步减少包含多个任务的任务集的响应时间。任务容错优先级混合策略能够进一步优化任务响应时间。与基于局部优化检查点间隔的容错优先级混合策略相比，结合全局优化检查点间隔的容错优先级混合策略在大多数任务配置属性时能够进一步优化任务的响应时间。基于通用调度的分布式系统任务容错调度算法与严格调度方式相比可在满足任务可靠性要求的同时进一步减少任务的响应时间。

目录

声明

摘要

第1章 绪论

1．1 课题背景及意义

1．2 基础知识及理论

1．2．1 检查点设置与卷回恢复技术

1．2．2 任务多副本复制技术

1．2．3 智能优化算法

1．2．4 实时系统任务容错调度算法

1．3 分布式实时系统任务容错调度算法的研究难点

1．4 本文的主要工作

1．5 论文的组织结构

第2章 分布式实时系统单机任务容错调度检查点间隔优化算法

2．1 引言

2．2 容错调度模型

2．3 检查点间隔局部优化算法

2．4 检查点间隔全局优化算法

2．4．1 基于任务集合的检查点间隔全局优化算法

2．4．2 基于混合粒子群优化的检查点间隔全局优化算法

2．5 实验结果与分析

2．5．1 实验环境及参数设置

2．5．2 基于任务集合的检查点间隔全局优化算法实验结果

2．5．3 基于混合粒子群优化的检查点间隔全局优化算法实验结果

2．6 本章小结

第3章 分布式实时系统基于局部优化检查点的单机任务容错优先级配置搜索算法

3．1 引言

3．2 容错优先级混合策略下任务的最坏响应时间

3．2．1 外部故障响应时间

3．2．2 内部故障响应时间

3．3 容错优先级配置搜索算法

3．4 实验结果与分析

3．4．1 实验环境及参数设置

3．4．2 实验结果分析

3．5 本章小结

第4章 分布式实时系统单机任务容错调度检查点全局优化和容错优先级搜索算法

4．1 引言

4．2 全局优化检查点间隔

4．3 任务最坏响应时间

4．3．1 容错优先级混合策略

4．3．2 最坏响应时间

4．4 任务最坏响应时间优化问题

4．5 检查点间隔全局优化和容错优先级搜索算法

4．5．1 编码方式

4．5．2 适应度函数

4．5．3 交叉操作

4．5．4 变异操作

4．5．5 算法步骤

4．6 实验结果与分析

4．6．1 实验环境及参数设置

4．6．2 实验结果分析

4．7 本章小结

第5章 分布式实时系统任务多副本容错调度算法

5．1 引言

5．2 任务调度模型

5．3 基于任务多副本技术的通用调度可靠性模型

5．3．1 任务副本开始执行时间

5．3．2 可靠性模型

5．4 可靠性意识多副本任务通用调度算法

5．4．1 任务优先级

5．4．2 任务集调度算法

5．4．3 任务多副本通用调度算法

5．4．4 基于遗传算法的任务多副本通用调度算法

5．5 实验结果与分析

5．5．1 实验环境及参数设置

5．5．2 可靠性对比

5．5．3 调度Makespan对比

5．5．4 调度资源开销对比

5．6 本章小结

结论

参考文献

攻读博士学位期间发表的论文和取得的科研成果

致谢