Research On Task Scheduling Algorithms In Grid Computing Environment

In recent years,grid technology has been one of the hotspots in the field of computer.Grid computing is one of the most important network technologies.Grid task scheduling is the core issue in grid computing,the task scheduling algorithm will directly affect the system's makespan.It has been proven to be an NP hard problem to schedule tasks in grid environment.An efficient grid task scheduling algorithm can balance the workload in the grid system and shorten the execution time.Therefore,it is meaningful to study the task scheduling algorithm under grid computing.The following two parts are mainly studies in this thesis.Firstly,OLB,MET and MCT algorithms are three basic grid task scheduling algorithms,and each algorithm performs differently in different grid environments.Therefore,how to select the best algorithm according to the existing grid environment is an urgent problem to be solved.Secondly,in the above three algorithms,the MCT algorithm is a highly adaptable and relatively efficient task scheduling algorithm.But the MCT algorithm can only get the local optimal solution.There is still room for improvement for MCT algorithm.In view of the above research contents,the research results are obtained as follow.The performance of OLB,MET and MCT algorithms varies in different grid environments.In order to get the best performance algorithm in each scenario based on the known grid environment and task condition,an IASM intelligent algorithm selection mechanism is proposed.Firstly,task length,task distribution and the difference of resource execution capability are defined as three factors of affecting the performance of the algorithms.Then the influence of the three factors above on the completion time of the three basic algorithms OLB,MET and MCT algorithm is analyzed theoretically.Last the analysis conclusion is applied to the IASM algorithm selection mechanism,so that once the grid scene is input into the mechanism,the algorithm with the shortest completion time in this scenario is output from the IASM.The Grid Sim simulator is used as the simulation platform of grid experiment.Through the grid simulation experiment,the influence of various grid environment factors on the basic algorithm is verified,and the applicability of the IASM mechanism is verified.The MCT algorithm is an algorithm with stable performance and short completion time.However,under the scene that the resource processing capacity is different,the MCT algorithm is easy to cause the resource load imbalance.The resource with strong processing power has more tasks while the less processing resources have fewer tasks.The unbalanced resource load will cause the increase of makespan.In order to balance the load between resources and reduce the total completion time of the grid system,an AMCT algorithm is proposed.Based on the scheduling strategy of MCT algorithm,the AMCT algorithm redispatches a task from the larger loaded resource to the less loaded resource.Simulation experiments on the Grid Sim simulation platform show that the AMCT algorithm can effectively shorten the total completion time.Summarize these two innovation points: the IASM mechanism achieves the aim of choosing the algorithm with the shortest makespan in different conditions.The AMCT algorithm balances the load between resources and reduces the total completion time of the system on the basis of the MCT algorithm.Both of the two algorithms achieve the minimization of the completion time.