The Sdudy On Grid Task Scheduling Algorithm And Its Modeling And Simulation With Colored Petri Net

Grid task scheduling has been an important part of grid computing due to the heterogeneity, dynamic and autonomy of resource and the diversity of the task under grid computing environment. Therefore, the efficiency of task scheduling algorithm determines the efficiency of grid computing, the scheduling algorithm should be designed perfectly. Using graphical math tools to complete formal description, correct testing, performance evaluation and testing of the algorithm and system is an important working method. Establishing the model of task scheduling algorithm is for the purpose of running the model to simulate the actual algorithm, we can study the properties of the actual algorithm through the analysis of the model. According to the analysis, an improved scheduling algorithm is designed. The main contents are as follows:(1) In this paper, two classical grid scheduling algorithms (Min-Min and Max-Min algorithm) were analyzed, and then simulation experiment was done using the modeling tool CPN Tools. The simulation result is that the maximum completion time (makespan) is relatively long and the loads are obviously unbalanced in Min-Min algorithm, but Max-Min algorithm has a smaller makespan.(2) Based on the above study, there is a need to improve the grid scheduling algorithm, making that the task scheduling algorithm has a smaller makespan and balanced load between the entire system machines. Therefore, this paper designs a priority-based grid scheduling algorithm P-M-M. In order to solve the problem of load balancing between machines, the algorithm uses the group method by the average expected execution time; to make a smaller makespan of the algorithm, each group runs in accordance with the Max-Min algorithm. Prior tasks in the algorithm are firstly assigned to the fastest executed machine; the average expected execution time of independent tasks which have no priority should be calculated, and then scheduling tasks are sorted in descending order based on the average expected execution time, which are set to equal groups. Each group is scheduled in accordance with Max-Min algorithm. (3) Simulation experiment was done using the modeling tool CPN Tools in the improved scheduling algorithm P-M-M. Simulation results show that P-M-M algorithm has a smaller makespan and better load balancing.