实时分布式容错调度算法研究

论文摘要

实时分布式系统的任务调度问题是一个富有挑战性的课题,也是当前的一个研究热点。由于任务调度是一个典型的NP问题,同时它又是直接影响分布式系统性能的关键因素,因此,研究实时分布式计算机系统的任务调度策略具有重要的理论意义和实际意义。但是现有的分布式实时系统的容错调度算法大多要求系统中所有任务的周期相同并且等于其时限,而在实际应用中,任务的周期常常互不相同,这就使现有的容错调度算法的实用性有所欠缺。本文根据控制系统中任务的特点,结合任务分配算法与处理器的调度算法,给出了一种新型的基于基版本/副版本技术和EDF算法的容错调度算法。该算法的优点主要在于在调度时并不要求所有任务的周期都相同,任务可以根据其自身情况定制符合要求的任务周期。这样就较好的解决了在一个实时调度系统中对所调度任务的任务属性要求过于严苛,使得容错系统实用性大大降低的问题。为了证明该实时容错调度算法具有很好的实用性,本文在对容错调度算法进行研究的同时,还对实时任务集的可调度性进行了分析总结,并通过设置基版本/副版本的任务时限控制它们的执行时间不重叠,给出了基版本/副版本任务时限的设置方法。最后在综合考虑了影响实时容错调度系统性能的各方面因素之后,建立模型,定制了一个运用本文提出的容错调度算法的原型系统,并进行了模拟实验,给出了仿真结果。最终的结果表明了该算法的有效性与实用性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 容错，实时和分布式概述
• 1.2.1 容错技术概述
• 1.2.2 实时系统概述
• 1.2.3 分布式系统概述
• 1.3 分布式实时系统中容错技术的研究现状
• 1.4 本课题的主要工作
• 第二章 分布式实时容错系统及其调度算法
• 2.1 容错技术
• 2.1.1 以冗余为基础的容错技术
• 2.1.2 其他容错技术
• 2.2 软件容错技术
• 2.2.1 恢复块技术（RB）
• 2.2.2 多版本编程结构（NVP）
• 2.2.3 版本自检系统（ NSCP）
• 2.2.4 分布式恢复块（ DRB）
• 2.2.5 异常处理（EH）
• 2.3 分布式系统
• 2.3.1 分布式系统的特点
• 2.3.2 分布式系统的优势
• 2.4 实时系统
• 2.4.1 实时系统的特点
• 2.4.2 实时系统的分类
• 2.5 实时分布系统与容错技术
• 2.6 容错系统可靠性评估技术
• 2.6.1 计算机容错系统的评价指标
• 2.6.2 系统可靠性评价模型
• 2.7 实时容错调度算法
• 第三章 一种基于基版本/副版本技术和EDF 算法的容错调度算法
• 3.1 实时调度系统
• 3.1.1 基于优先级的实时调度
• 3.1.2 EDF 算法
• 3.2 实时分布容错调度算法
• 3.3 基于基版本/副版本技术和EDF 算法的容错调度算法
• 3.3.1 系统模型及设计思想
• 3.3.2 调度算法设计
• 3.3.3 任务分配算法
• 3.3.4 最小处理器个数求解算法
• 3.4 负载均衡策略
• 3.4.1 轮转调度
• 3.4.2 加权轮转调度
• 3.4.3 最小连接调度
• 3.4.4 加权最小连接
• 3.4.5 基于剩余负载权值的动态均衡策略
• 第四章 算法的性能分析及其模拟实验
• 4.1 任务可调度性证明
• 4.2 实时容错调度算法的评价体系
• 4.2.1 算法性能分析
• 4.2.2 调度算法的评价参数
• 4.2.3 算法稳定性分析
• 4.3 原型系统的实现
• 4.3.1 基础体系结构
• 4.3.2 系统的容错设计
• 4.4 实验结果和数据分析
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 致谢
• 参考文献