期刊文献+

异构集群系统中具有QoS需求的实时任务容错调度 被引量:11

Fault-Tolerant Scheduling for Real-Time Tasks with QoS Requirements on Heterogeneous Clusters
下载PDF
导出
摘要 容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段.目前已有很多集群系统中实时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS需求问题.提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ(fault-tolerant QoS-based scheduling).该算法采用主版本/副版本(primary/backup,简称PB)技术,综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调度性和资源的利用率.对系统的可靠性进行了定量分析,并将其引入到容错调度算法中,提高了系统的可靠性.同时,在调度过程中尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者使任务主版本和副版本的重叠部分尽量少,提高了资源的利用率.此外,采用了副版本重叠技术,并分析了副版本的最晚开始时间及其约束条件,提高了任务的调度成功率.通过大量的模拟实验,对FTQ,NOFTQ和DYFARS算法进行了比较.实验结果表明,FTQ算法的性能优于其他方法,具有更好的调度质量. Fault-Tolerant scheduling, an effective means of improving a system's performance, plays a significant role in scheduling research. Despite the fact that fault-tolerant scheduling has been extensively proposed for real-time tasks on clusters, QoS (quality of service) requirements for some tasks have not been considered. This paper proposes a fault-tolerance scheduling algorithm FTQ (fault-tolerant QoS-based scheduling) for real-time tasks with QoS needs on heterogeneous clusters. FTQ adopts the primary/backup model and takes the timing constraints of tasks, QoS requirements of tasks, reliability of systems, and system resource utilization into account. FTQ can adjust the QoS levels of real-time tasks and the execution schemes of backup copies to improve system flexibility, reliability, schedulability, and resource utilization. The system reliability is quantitatively measured and combined into FTQ, which improves the system performance. Meanwhile, FTQ strives to advance the start time of primary copies and delay the start time of backup copies to make backup copies adopt passive execution scheme, or decrease overlapping sections of primary and backup copies as much as possible to improve resource utilization. FTQ adaptively adjusts the QoS levels of tasks and the execution schemes of backup copies to attain a higher flexibility. The overlapping technology of backup copies is employed. The latest start time of backup copies and its constraints are analyzed. Compared with NOFTQ and DYFARS, FTQ shows obvious superiority with a higher scheduling quality proven by a considerable number of simulated experiments.
出处 《软件学报》 EI CSCD 北大核心 2011年第7期1440-1456,共17页 Journal of Software
基金 国家安全重大基础研究计划(973)(6136101) 国家高技术研究发展计划(863)(2008AA7070412)
关键词 异构集群 实时 调度 容错 启发式 heterogeneous cluster real-time scheduling fault tolerance heuristic
  • 相关文献

参考文献6

二级参考文献83

  • 1Zheng K, Wang J, Huang L, Decarreau G. Open wireless software radio on common PC. In: Proc. of the 17th Annual IEEE Int'l Symp. on Personal, Indoor and Mobile Radio Communications. Helsinki: IEEE Press, 2006.707-716.
  • 2Pyndiah R, Glavieux A, Picart A, Jacq S. Near optimal decoding of product codes. In: Proc. of the IEEE Global Telecommunications Conf. San Francisco: IEEE Press, 1994. 339-343.
  • 3Yu NY, Kim Y, Lee PJ. Iterative decoding of product codes composed of extended hamming codes. In: Samir T, Mehmet U, eds. Proc. of the 5th IEEE Int'l Symp. on Computers and Communications. Antibes-Juan Les Pins: IEEE Press, 2000. 732-737.
  • 4Chi Z, Song L, Parhi KK. A study on the performance, complexity tradeoffs of block turbo decoder design. In: Proc. of the IEEE Int'l Symp. on Circuits and Systems. Sydney: IEEE Press, 2001,4:65-68.
  • 5Atdelzater TF, Atkins EM, Shin KG. QoS negotiation in real-time systems and its application to automated flight control. IEEE Trans. on Computers, 2000,49(11):1170-1183.
  • 6Qin x, Jiang H. A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters. Journal of Parallel and Distributed Computing, 2005,65(8):885-900.
  • 7Garey MR, Johnson DS. Strong NP-completeness results: motivation, examples, and implications. Journal of Association for Computing Machinery, 1978,25(3):499-508.
  • 8Subramani V, Kettimuthu R, Srinivasan S, Johnston J, Sadayappan P. Selective buddy allocation for scheduling parallel jobs on clusters. In: Gropp B, Pennington R, Reed D, Baker M, Brown M, Buyya R, eds. Proc. of the IEEE Int'l Conf. Cluster Computing. Chicago: IEEE Press, 2002. 107-116.
  • 9Vallee G, Morin C, Berthou JY, Rilling L. A new approach to configurable dynamic scheduling in clusters based on single system image technologies. In: Proc. of the Int'l Parallel and Distributed Processing Syrup. Nice: IEEE Press, 2003.22-26.
  • 10Braun TD, Siegal H J, Beck N, Boloni LL, Maheswaran M, Reuther AI, Robertson JP, Theys MD, Yao B, Hensgen D, Freund RF. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems. In: Prasanna VK, ed. Proc. of the 8th Heterogeneous Computing Workshop. San Juan: IEEE Press, 1999. 15-29.

共引文献66

同被引文献128

引证文献11

二级引证文献58

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部