Design And Implementation Of The Pipeline Virtual Service Scheduling Algorithm In Grid Environment

The scheduling of tasks with DAG-structure is a classic but challenging problem in Grid environment. Based on SOA, this thesis abstracts the DAG tasks as Pipeline Virtual Service (PVS). Taking HSDC telescope data process as the application example, this thesis pays main attention on design and implementation of the Pipeline Virtual Service scheduling algorithm.By analyzing the application characterizations and Grid environment, a PVS pre-scheduling model with the relevant SOD algorithm and the Triangular Pyramid Scheduling (TPS) model with TPS algorithm are provided in this thesis. In the first model, scheduling policies generation and execution are separated and run in parallel. It can utilize the free computing abilities in Grid and hide the time of scheduling policies generation. The second model solves the scheduling problem by considering more general Grid characters. Rather than being limited in the two-dimension matching relationship (task-resource), it classifies the factors which affect the scheduling in details and establishes the new match relationship according to different structures of different PVSs. Therefore, it can find more and better scheduling solutions. The analytic simulation results show that two scheduling models and algorithms match the open and dynamic Grid environment. They have the advantages in balancing the scheduling cost and scheduling precision, saving the scheduling time and improving the resource utility. Moreover, the design and implementation of HSDC prototype also shows the practicability and efficiency of scheduling models and algorithms discussed in this thesis.