Research On Loop-structure Grid Workflow Scheduling Based On Economic Benefit Model

Following the parallel computing, net computing, distribute computing and high performance computing, grid computing is the inevitable development trend and one of the most important research areas. Grid workflow is one of the most important research areas in grid computing. Regarding the workflow scheduling in grid computing, the most researches consider the model of directed acyclic graph. The workflow with the more complex structure can't be expressed by DAG. In this paper, we consider the more complicated workflow structure (e.g. loop, parallel and pipeline) and propose a scheduling algorithm.The utility function can show satisfaction of resource providers and users, because in the task scheduling in every level, according to the rule of the economical utility model, resource providers and users have their own benefit. Based on it, this paper proposes a priority task strategy. On one hand, the tasks with high QoS have the high priority, resulting in that the high QoS resources were occupied by tasks with low QoS, and tasks with high QoS waste time and cost for waiting. On the other hand, the system load is unbalance and the utility of all resources is low, and the most normal resources are idle for a long time. Regarding those reasons, this paper proposes a method called loop-parallel algorithm and solves the grid workflow task scheduling with the loop structure. The algorithm satisfies the user's QoS requirements, balances the system load, enhances the quality of the system, and fits the complicated grid environment. The simulation shows the validity of the algorithm.