基于优化负载均衡算法的任务调度系统的研究与实现

发布时间：2018-06-22 18:18

本文选题：云计算 + 任务调度　；参考：《电子科技大学》2014年硕士论文

【摘要】：在云计算环境下,随着计算机集群中的动态节点变化、节点中资源的动态变化以及大规模的任务需求接踵而来,我们将面临着如何提高任务调度系统的资源利用率、如何达到负载均衡以及如何提升系统的整体性能和效率等问题。在云计算研究领域中,任务调度问题一直是一个比较典型的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%。
[Abstract]:In the cloud computing environment, with the change of dynamic nodes in the cluster, the dynamic changes of resources in the nodes and the large-scale task requirements, we will be faced with how to improve the resource utilization of task scheduling system. How to achieve load balance and how to improve the overall performance and efficiency of the system. In the field of cloud computing, task scheduling is a typical NP-Hard problem. Although many researchers at home and abroad have devoted themselves to this problem, they have not put forward a good solution. Increasing the load balancing rate of the system is an effective method to improve the overall performance of the system. Up to now, many researchers have studied a lot of related results, but in order to achieve better, load balancing algorithm is still inadequate, need to continue to improve. The emphasis of this paper is to study and improve a dynamic load balancing (DLB) algorithm, Work-Stealing. which makes the tasks execute in parallel efficiently, makes each machine load balance, and improves the utilization ratio of parallel resources and the overall performance of the task scheduling system. The basic idea is: due to the different processing capacity of each computing node in a task scheduling system, the speed of processing tasks will also be different. The light load node can be selected as the third node according to a certain strategy, then steal the task execution on the heavy load node, share the task with the heavy load node, shorten the time span of the system make Span, and improve the overall efficiency of the system. In the research process of this paper, firstly, the related theories of task scheduling and load balancing algorithm are investigated, and the related results of Work-Stealing algorithm are studied, and three improved strategies (additive series) proposed in this paper for stealing the number of tasks are proposed. The multiplicative series, dichotomy) and two kinds of stealing task timing (free time theft and prefetching strategy) are analyzed and compared. Finally, the two aspects of Work-Stealing algorithm are comprehensively improved. In this paper, a prototype task scheduling system is designed and implemented, which mainly includes two kinds of components: the central task scheduling server and the executor worker, which can realize the task distribution, task theft and other related operations. In the system model, the improved dynamic load balancing algorithm, Work-Stealing, is used to dynamically distribute and migrate the tasks in the system, so as to eliminate and reduce the uneven load of each computing node in the cluster system. Finally, the improved Work-Stealing algorithm is compared with the classical load balancing algorithm and the original Work-Stealing algorithm in order to verify the performance and load balancing rate of the improved algorithm. In the process of the experiment, the final completion time of the task, such as make Span, throughput, comprehensive utilization of resources and load balance, is used. Experimental data show that compared with other algorithms, the overall performance of the improved Work-Stealing algorithm is improved, especially in the area of make span and throughput, compared with the original Work-Stealing algorithm, the performance of the improved Work-Stealing algorithm is improved by 11.7%.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP301.6;TP393.07

【参考文献】