论文部分内容阅读
在云计算环境下,随着计算机集群中的动态节点变化、节点中资源的动态变化以及大规模的任务需求接踵而来,我们将面临着如何提高任务调度系统的资源利用率、如何达到负载均衡以及如何提升系统的整体性能和效率等问题。在云计算研究领域中,任务调度问题一直是一个比较典型的NP-Hard问题。尽管国内外许许多多的研究学者致力于研究这个问题,但是仍然没有提出一个很好的解决方案。其中,提高系统的负载均衡率是提高系统整体性能的一个有效方法,至今也有很多研究者研究出许多相关成果,但是以求达到更好,负载均衡算法尚存在不足,需要继续改进。本论文的重点是研究并改进一个动态负载均衡(Dynamic Load Balancing,即DLB)算法Work-stealing,使得任务能够高效并行执行,使得各台机器的负载均衡,提高任务调度系统的并行资源利用率和整体性能。其基本思想是:由于一个任务调度系统中各个计算节点的处理能力不同,处理任务的快慢也会有差别,轻载节点可以按照某种策略被选为Thief,然后去重负载的节点上窃取任务执行,与重载节点分担任务,缩短系统的时间跨度Make Span,提高系统的整体效率。在论文的研究过程中,首先对任务调度和负载均衡算法的相关理论进行调研,对Work-stealing算法的相关成果进行研究,并对本文提出的三种窃取任务数量方面的改进策略(加法级数、乘法级数、二分法)和两种窃取任务时机(空闲时窃取和预取策略)进行分析对比,最后针对Work-stealing算法的这两个方面综合改进。本文中还设计并实现了一个原型任务调度系统,主要包含了中心任务调度服务器和执行器Worker两类组件,可以实现任务分发、任务窃取等相关操作。在系统模型中,使用改进的动态负载均衡算法Work-stealing实现对系统中的任务进行动态分发和迁移,尽量消除和减少集群系统中各个计算节点负载不均匀的现象。最后,论文使用实验模拟的方式把改进的Work-stealing算法与比较经典的负载均衡算法以及原有的Work-stealing算法进行对比,来验证改进算法的性能和负载均衡率。实验过程中,使用了任务的最终完成时间Make Span、吞吐率、资源综合利用率和负载均衡度等技术指标。实验数据表明,改进的Work-stealing算法与其他算法相比,整体性能都有所提高,尤其是在Make Span和吞吐率方面,与原有的Work-stealing算法相比,提高了11.7%。