容错系统中实时任务调度和负载均衡算法研究

论文摘要

容错系统担负关键控制系统角色,已经被广泛应用于国防、航空航天、核反应堆控制、通信行业、过程控制、医药行业等领域,容错计算技术也已经成为计算机科学技术一个重要的学科领域。近年来,随着实时应用和分布式应用兴起,容错系统一个新的发展趋势是不仅要求系统能够屏蔽故障,还要求系统中关键任务必须能够及时正确被调度完成,保证系统在故障发生前和故障发生后达到负载均衡的状态,从而扩展容错系统在实时计算和分布式计算领域中的应用,提高资源利用率及性能。本文深入研究容错系统中实时任务调度和负载均衡算法。目前容错系统中实时任务调度算法大多针对硬件容错,很少考虑软件的运行故障;并且在针对硬件容错时,具有过高的硬件冗余度。针对上述问题,提出软件容错模型中部分抢占实时任务调度算法和主/副版本容错模型中一个高效的实时任务调度算法。此外,由于目前缺少通用的可适用于分布式容错系统的负载均衡算法,因此提出主/副版本容错模型中一个通用的负载均衡算法,并将算法应用于分布式容错环境中一个全球股票集中撮合系统。总结上述,本文的主要贡献如下:1)提出软件容错模型中针对硬实时系统软件运行故障的部分抢占调度算法——RMPPA和EDFPPA算法。部分抢占调度算法不仅可以获得与以前算法近似调度性能,还可以在一定条件下大大减少抢占次数,降低系统运行开销。2)提出主/副版本容错模型中针对硬实时系统硬件故障的一个高效的任务调度算法——TPFTRM算法。TPFTRM不仅最大限度利用副版本重叠和分离技术减少硬件冗余度,还将任务集合和处理器集合划分调度,使TPFTRM调度算法便于理解、实现以及减少调度所需要的运行时间。3)提出主/副版本容错模型中静态负载均衡算法——RSA算法。RSA算法根据任务主/副版本的负载情况将进程集合分配到各个处理机,使处理机在发生故障前后都处于负载均衡的状态。4)将RSA算法应用于一个基于分布式数据划分模型的全球股票集中撮合系统,提高负载均衡能力。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 研究内容
• 1.4 论文结构
• 第2章 实时任务调度和负载均衡算法研究
• 2.1 容错系统概述
• 2.1.1 故障、错误及失效
• 2.1.2 容错技术
• 2.1.3 容错系统的起源和发展
• 2.2 容错系统中实时任务调度算法
• 2.2.1 实时任务调度
• 2.2.2 主/副版本容错模型
• 2.2.3 软件容错模型
• 2.2.4 非精确计算模型
• 2.2.5 （m，k）-firm deadline模型
• 2.3 容错系统中负载均衡算法
• 2.3.1 组件部署策略
• 2.3.2 负载均衡算法
• 2.4 本章小结
• 第3章 软件容错模型中部分抢占实时任务调度算法
• 3.1 研究背景
• 3.2 相关工作
• 3.3 形式化表述
• 3.4 部分抢占调度算法
• 3.4.1 EDFPPA算法
• 3.4.2 RMPPA算法
• 3.5 模拟实验和性能分析
• 3.5.1 评价标准
• 3.5.2 模拟实验1
• 3.5.3 模拟实验2
• 3.6 本章小结
• 第4章 主/副版本容错模型中高效实时任务调度算法
• 4.1 研究背景
• 4.2 相关工作
• 4.3 形式化表述
• 4.4 TPFTRM调度算法
• 4.4.1 任务分组和副版本状态的确定
• 4.4.2 处理器分组和任务的分配
• 4.4.3 可调度性条件
• 4.4.4 TPFTRM算法描述
• 4.5 性能测试
• 4.6 本章小结
• 第5章 主/副版本容错模型中静态负载均衡算法
• 5.1 研究背景
• 5.2 相关工作
• 5.3 形式化表述
• 5.3.1 系统容错模型定义
• 5.3.2 符号说明
• 5.3.3 问题描述
• 5.4 启发式进程调度算法
• 5.4.1 两阶段算法
• 5.4.2 RSA算法
• 5.4.3 算法复杂度
• 5.5 性能分析
• 5.6 本章小结
• 第6章 全球股票集中撮合系统的案例分析
• 6.1 项目背景
• 6.2 全球股票集中撮合系统
• 6.2.1 容错基础框架设计
• 6.2.2 系统中负载均衡算法
• 6.2.3 股票集中撮合系统架构
• 6.3 实验结果和性能分析
• 6.3.1 性能比较
• 6.3.2 负载均衡测试
• 6.4 本章小结
• 第7章 结束语
• 7.1 本文工作总结
• 7.2 本文创新成果
• 7.3 进一步的研究工作
• 参考文献
• 攻读博士学位期间主要的研究成果
• 致谢