异构集群系统中实时任务若干调度问题研究

摘要

异构集群系统由于其卓越的性能价格比、良好的可扩展性和高可用性,逐渐成为当今计算机体系结构和并行处理研究的热点和主题。与此同时,实时应用范围在不断扩大,系统复杂性不断提高,集群计算技术已经成为解决计算密集型和数据密集型实时应用的有效手段。在集群系统的设计中,性能是一个关键问题,而调度又是性能之根本所在。本文致力于研究异构集群系统中实时任务的若干调度问题以满足某些重要实时应用的需求,提高系统的性能。具体地讲,本文在如下3个方面进行了深入的研究:
　　1.研究了异构集群系统中安全关键实时任务的调度问题。在集群系统中,为具有安全需求的实时应用提供安全服务得到了广泛的关注,但将实用应用的安全需求与调度算法相结合的研究并不多。本文提出一种2阶段的调度策略TPSS。该策略在任务的调度过程中综合考虑了任务的安全需求与时间限制。在TPSS的第1阶段,提出了一种自适应调度算法DSRF,当系统负载较重时,DSRF算法能在保证系统具有基本安全保证的基础上,通过降低新到任务和等待队列中任务的安全级别来提高任务的调度成功率。相反,当系统负载较轻时,DSRF算法能在保证系统具有较高调度成功率的基础上充分利用任务在截止期前的空闲时间提高新任务的安全级别。在TPSS的第2阶段,提出一种新的算法FMSL用来为所接收任务提供公平的安全服务,同时进一步提高任务的整体安全级别。文中通过大量的模拟实验对TPSS策略与DSRF算法、SAEDF算法和RF算法进行了比较。实验结果表明,TPSS策略优于其它方法,具有很强的灵活性和可靠性。
　　2.研究了异构集群系统中实时任务的多目标调度问题。目前,很多实时系统如多媒体数据处理系统、信号处理系统等除了需要满足时间限制外,还需要有多种性能得到保证。但是,大多数传统的调度算法通常只考虑实时任务的调度成功率,而忽略了许多其它方面的需求,本文提出了一种异构集群系统中为软实时任务提供多个性能保证的动态调度策略MDSS。该策略综合考虑了任务的实时性、服务质量、系统吞吐率、负载均衡和服务的公平性。通过将实时控制器、QoS控制器和均衡控制器整合在调度器模型中,实现了多个性能的保证。MDSS包括3个步骤。第1步可以采用任何已有或新提出调度算法以满足任务的时间要求,这极大的提高了系统的灵活性和可扩展性。本文在MDSS的第1步采用了Qin等人提出的DASAP算法。另外,本文提出了2种启发式算法MQFQ和ITLB,分别用在MDSS策略的第2步和第3步中。MQFQ是一种采用公平策略的算法,使得所有分配在同一个节点上的任务具有较高的QoS级别,同时QoS级别的差异较小。此外,本文提出了QoS收益的概念,所采用的QoS级别提升方法有效地避免了局部极值问题。ITLB算法通过最小化节点完成时间的标准差来达到系统的负载均衡,提高系统的吞吐率。文中通过大量的模拟实验对MDSS、MDSR、DASAP和DALAP算法进行了比较,实验结果表明MDSS的性能优于其它方法,具有很强的适应性。
　　3.研究了异构集群系统中具有QoS需求的实时任务容错调度问题。容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段。目前已有很多集群系统中实时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS需求问题。本文提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ。该算法采用主版本/副版本(Primary/Backup,PB)模型,综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调度性和资源的利用率。本文对系统的可靠性进行了定量的分析并将其引入到容错调度算法中,提高了系统的可靠性。同时在调度过程中,尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者任务的主版本和副版本的重叠部分尽量少,以提高了资源的利用率。此外,本文采用了副版本重叠技术,并分析了副版本的最晚开始时间和其约束条件,提高了任务的调度成功率。文中通过大量的模拟实验对FTQ、NOFTQ和DYFARS算法进行了比较。实验结果表明FTQ算法的性能优于其它方法,具有更好的调度质量。

目录

摘要

Abstract

第1章 绪论

1.1 研究背景

1.1.1 高性能计算机分类及发展趋势

1.1.2 集群系统定义及特点

1.1.3 实时应用的发展

1.2 本文动机与研究内容

1.3 本文组织结构

第2章 集群系统中实时任务调度概述

2.1 实时任务定义及分类

2.2 实时调度定义及分类

2.3 常用实时调度策略

2.4 集群系统中实时任务调度研究进展

第3章 安全关键实时任务调度研究

3.1 引言

3.2 相关工作

3.3 调度器模型和任务模型

3.3.1 调度器模型

3.3.2 任务模型

3.4 TPSS策略

3.4.1 DSRF算法

3.4.2 FMSL算法

3.5 实验测试

3.5.1 模拟方法与参数

3.5.2 节点对性能的影响

3.5.3 任务达到速度对性能的影响

3.5.4 节点异构性对性能的影响

3.6 小结

第4章 多目标实时任务调度研究

4.1 引言

4.2 相关工作

4.3 调度器模型和任务模型

4.3.1 调度器模型

4.3.2 任务模型

4.4 MDSS策略

4.4.1 MQFQ算法

4.4.2 ITLB算法

4.5 实验测试

4.5.1 模拟方法和参数

4.5.2 节点数对性能的影响

4.5.3 节点异构性对性能的影响

4.5.4 任务截止期对性能的影响

4.5.5 任务粒度对性能的影响

4.6 小结

第5章 基于QoS需求的实时任务容错调度研究

5.1 引言

5.2 相关工作

5.3 容错调度模型

5.3.1 前提假设

5.3.2 调度器模型

5.3.3 任务模型

5.3.4 可靠性模型

5.4 容错调度算法FTQ

5.5 实验测试

5.5.1 模拟方法和参数

5.5.2 节点数对性能的影响

5.5.3 节点异构性对性能的影响

5.5.4 任务异构性对性能的影响

5.5.5 任务到达速度对性能的影响

5.5.6 任务截止期对性能的影响

5.5.7 节点出错率对性能的影响

5.6 小结

第6章 总结与展望

6.1 论文工作总结

6.2 未来工作展望

参考文献

致谢

攻读博士学位期间发表论文情况