Research On Task Scheduling Algorithms Based On Computational Grids

In recent years, the high-speed networks develop very fast, which makes it possible to integrate the distributed and heterogeneous computing resources into Computational Grid. It provides an ideal platform to solve large-scale computing problems in scientific and engineering area. Because the resources in Grid are distributed, heterogeneous and dynamic, how to schedule tasks in Grid to meet users' requirements is a challenging problem.In AppLeS Parameter Sweep Template, an adaptive scheduling algorithm is used for task scheduling. In the algorithm, XSufferage heuristic based on Sufferage heuristic is proposed for the fact that tasks in PSA always share input files. In order to reduce scheduling overhead, the algorithm will pick a subset of tasks from the whole task set before scheduling, which makes some tasks scheduled early and the others scheduled late. If there are many input files shared and the algorithm uses XSufferage for scheduling, different sequence for tasks to be scheduled can produce different results. In order to improve the performance of algorithm, a method for task subset selection is proposed. A simulation experiment based on Simgrid platform is made and the comparison between the original algorithm and the algorithm with task selection shows that the latter is better.With the proliferation of the Grid, quality of service (QoS) has become an important factor that needed to be considered in the procedure of scheduling. In this situation, QoS guided Min-Min heuristic based on Min-Min heuristic is proposed. But the heuristic is running on batch mode, which makes it possible to cause waste of computing resources. In order to overcome this shortcoming, Extended QoS guided Min-Min heuristic is proposed by import "bidding-for-task" policy. The result of simulation experiment shows that the extended heuristic is better.At the end, we discuss the application of fault tolerance in Grid task scheduling. On the basis of a existing Grid fault-tolerant scheduling policy, we import the concept of "availability" and propose a new policy.