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

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

作　　者：于炯[1,3] 田国忠[2,5] 曹元大[1] 孙贤和 

机构地区：[1]北京理工大学计算机学院,北京100081 [2]北京工业大学计算机学院,北京100124 [3]新疆大学信息科学与工程学院,乌鲁木齐830046 [4]美国伊立诺理工学院计算机系,美国芝加哥60616 [5]新疆工业高等专科学校计算机工程系,乌鲁木齐830091

出　　处：《计算机研究与发展》2009年第11期1821-1829,共9页Journal of Computer Research and Development

基　　金：国家“八六三”高技术研究发展计划基金项目(2009AA012437);国家自然科学基金项目(60563002,60863003);教育部春晖计划基金项目(Z2005-1-65009);北京市自然科学基金项目(4072004,4092006);新疆工业高等专科学校科研基金项目( WGZ2008K05)~~

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

关 键 词：资源分配 MARKOV过程 关键路径 关键区间 关键区间有效度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]