The Research Of Grid Task Scheduling Algorithm Based On Critical Path

With the rapid development of the network technologies, the Internet can be filled with more available cheap resources. Solving large-scale, complex problems is important to use such resources. Grid system consists of a wide of geographically distributed resources and these resources are heterogeneous, geographically distributed and dynamically available. Many complex problems need to be addressed to implement effective grid computing, where task scheduling is a critical problem to be solved.Resources' dynamic concludes the increase or decrease of the resource capacity, and joining or withdrawing of the resource. Basing on the analysis of the various task scheduling algorithms find that many previous scheduling algorithms always pay attention to TSPF, and directly insert the task into the task sequence of the resource, but neglect whether it can be implemented. Declining of the resource capacity from the TSPF time to the TSPE time, makes the task high priority occupies a low-performance resource, increases the task execution time, and maybe delays the Makespan. On the contrary, enhancement of the resource capacity from the TSPF time to the TSPE time, decreases the task execution time, maybe advances the Makespan. Because the task has occupied a resource, the one will not easily give up the old resource and catch a new, the new resources will not influence the Makespan.In order to abate the influence of decrease of the resource capacity on task scheduling, and increase the influence of new excellent resources on the Makespan, the task scheduling is divided into two stages according to BT—TSPF and TSPE in this dissertation. A group of features, which include Latest Begin Time (LBT), Begin Time (BT) and the edge weight in a DAG, are defined in this dissertation. We analyze the impact on DAG by freezing elimination and implementing elimination and task scheduling accuracy by the gap between TSPF time and TSPE time.Critical Path Algorithms (CPA) holds that completion time of each task in a DAG critical path should be advanced as much as possible, thus Makespan can be shorten, i.e. tasks on critical path have the highest priority. But compared to ETF, it is found that the earliest begin time also influences Makespan and ETF surpasses CPA under certain conditions.Currently most scheduling algorithms mainly address resources rob by preventing from robbing, i.e. Resources rob is not allowed in any case. The BTTS defines task priority, considers the earliest begin time's influence on Makespan and allows that tasks which has not assigned for resources rob the resources held by other tasks according to the length of critical path (CP) on the basis of CPA. Resources rob and Min-DAG are defined, several conditions that resources rob may occur the influences on DAG and scheduling results are analyzed and two heuristic principles to decide whether resources rob is allowed for a kind of resources rob situation.Finally, the BTTS algorithm is proposed. Focused on analyzing a toolkit for modeling and simulating grid environment—GridSim, the ETF algorithm, CPA algorithm and BTTS algorithm are implemented on the platform. By comparison with ETF algorithm and CPA algorithm, the BTTS algorithm is better than the others, and reduces the impact on the result of Task Scheduling by resources' dynamic.