基于关键区间可靠度的网格工作流资源分配算法

目前针对执行时间限制严格的网格工作流资源调度与分配的研究工作已经取得了进展,然而这些工作没有考虑关键路径和非关键路径上任务执行时间的相对差异对资源分配算法产生的影响,这些算法或者仅考虑关键路径任务的资源可靠度问题而降低工作流执行成功率,或者仅考虑所有任务的资源可靠度问题而造成算法的低效率.针对这些问题,提出了一些新的定义,如关键区间和关键区间可靠度;同时也提出了一个新的网格工作流资源分配算法.与现有的分配算法相比,新的分配算法能既能保证限定期限内网格工作流执行成功率,又能提高资源分配效率.仿真结果证明了算法的正确性.

A Resource Allocating Algorithm in Grid Workflow Based on Critical Regions Reliability

Many workflow applications often have the timing constraints such that each processing of a workflow needs to be finished within its deadline. There have been some work to improve the performance of time-constrained workflow processing. Previous work mainly considered to meet the execution time request of the critical path tasks or all of the tasks both on the critical path and on the non-critical path. Few of them, however, have taken into account the fact that successful execution of workflow within its deadline is also affected by "normal state" and "abnormal state" of grid resources occurring in successive turns and by the relative difference in execution time between tasks on the critical path and tasks on the non-critical path. To solve the problems, some new definitions, such as critical region and reliability of critical region are defined, and then a new resource allocating algorithm is proposed in terms of the finite-state continuous-time Markov process through selecting a resource combination scheme which has the lowest expenditure under certain credit level of the resource reliability in the DAG-based workflow. Compared with previous algorithms, this method is much more efficient in resource allocating, and almost no degrading in successful grid workflow execution rate. The simulation shows the validity of the new algorithm.