Research And Implementation Of Optimized Load Balancing Algorithm In Task Scheduling System

In cloud computing environments, with dynamic computer node changing in cluster, the resource changing dynamically, and the demand for large-scale tasks, we will be faced with the issues of how to improve resource utilization of the task scheduling system, how to achieve load balancing and how to improve the performance and efficiency of the system.In the field of cloud computing, task scheduling has always been a typical NP-Hard problem. Many domestic and foreign researchers have been working on it, and several solutions have been prompted, but, there has not been any good solution yet. For most of the solutions, they find improving the load balance an effective solution to improve the overall performance of the system. In order to achieve a better solution, there is a need to continue improving the load balance algorithm.This thesis focuses on the study and improvement of a dynamic load balancing algorithm named Work-stealing algorithm. Tasks can be efficiently executed in parallel by using this algorithm, and then the resource utilization is improved. The basic idea of the algorithm is: as the processing capabilities of each computing node in task scheduling system are different and so are the speed of processing tasks, the light loaded node is chosen as a Thief according to a certain strategy, and then Thief goes to other heavy loaded node to steal some tasks to execute. By sharing the tasks with the heavy loaded node to complete all the tasks of the entire system as soon as possible, then overall time(Make Span) will be reduced and the overall efficiency of the system is improved.The research work of the thesis follows these steps. Firstly, this thesis studies the task scheduling, load balancing algorithms and relevant theory, focusing on the Work-stealing algorithm and related achievements. Then improved methods on two aspects including task number of stealing and time of stealing are proposed in this thesis and the analysis and comparison are presented. Finally, the Work-stealing algorithm is improved by combined strategies of the two proposed methods.This thesis designs and implements a prototype scheduling system and the system can distribute and forward tasks to other computers, which mainly consists of two types of components: the central task scheduling server and Worker. In this system model, the improved dynamic load balancing algorithm named Work-stealing is used to distribute and migrate task thread dynamically, which can reduce or eliminate the load imbalance situation in cluster system as far as possible.In the end, a set of simulation experiments have been performed to compare the improved dynamic load balancing algorithm with the classical load balancing algorithm and the unimproved Work-stealing algorithm. In the experiments, several indicators(Make Span, Throughput, Resource Utilization and the Degree of Load Balancing) are used. The results show that, the overall performance are improved by using Work-stealing algorithm, compared with other algorithms, improved by 11.7% in Make Span and Throughput compared with the original Work-stealing algorithm.