学位论文 > 优秀研究生学位论文题录展示

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

作　者: 朱晓敏
导　师: 陆佩忠
学　校: 复旦大学
专　业: 计算机应用技术
关键词: 异构集群实时调度安全关键服务质量 QoS收益截止期调度跨度吞吐率容错可靠性裕度主版本/副版本主动模式/被动模式
分类号: TP338
类　型: 博士论文
年　份: 2009年
下　载: 403次
引　用: 3次
阅　读: 论文下载

内容摘要

异构集群系统由于其卓越的性能价格比、良好的可扩展性和高可用性,逐渐成为当今计算机体系结构和并行处理研究的热点和主题。与此同时,实时应用范围在不断扩大,系统复杂性不断提高,集群计算技术已经成为解决计算密集型和数据密集型实时应用的有效手段。在集群系统的设计中,性能是一个关键问题,而调度又是性能之根本所在。本文致力于研究异构集群系统中实时任务的若干调度问题以满足某些重要实时应用的需求,提高系统的性能。具体地讲,本文在如下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算法的性能优于其它方法,具有更好的调度质量。

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

内容摘要

全文目录

相似论文