摘要：Many scientific workflow applications often have deadline constraint such that all tasks of application need to be finished within user-specified time. Though Grid systems have high performance, which provide an important infrastructure for executing scientific workflow, dynamic nature of Grid resources makes it very difficult to schedule workflow and satisfy the given deadline. For this issue, a M/M/C queuing model was adopted to model dynamic service capacity of grid resource. Under dynamic, unreliable grid environment, based on queuing system theory, a probability of meeting deadline for each task can be calculated. The detail analytic method and proof was given in the paper. Specifically, a novel probability evaluation based scheduling algorithm is proposed to address the problem of workflow’ deadline guarantee. The results of large scale simulation experiments with real Protein annotation workflow demonstrate that our algorithm can remarkably improve the predictability of workflow completion and guarantee user’s deadline requirements.
关键词：Scientific Workflow;Deadline;unreliable;Grid;Markov;queuing model
