ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇

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

于 炯1,3 田国忠2,5 曹元大1 孙贤和4   

  1. 1(北京理工大学计算机学院 北京 100081) 2(北京工业大学计算机学院 北京 100124) 3(新疆大学信息科学与工程学院 乌鲁木齐 830046) 4(美国伊立诺理工学院计算机系 美国芝加哥 60616) 5(新疆工业高等专科学校计算机工程系 乌鲁木齐 830091) (yujiong@xju.edu.cn)
  • 出版日期: 2009-11-15

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

Yu Jiong1,3, Tian Guozhong2,5, Cao Yuanda1, and Sun Xianhe4   

  1. 1(School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081) 2(School of Computer Science and Technology, Beijing University of Technology, Beijing 100124) 3 (School of Information Science and Engineering, Xinjiang University, Urumqi 830046) 4 (Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USA) 5 (Department of Computer Engineering, Xinjiang Polytechnial College, Urumqi 830091)
  • Online: 2009-11-15

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

关键词: 资源分配, Markov过程, 关键路径, 关键区间, 关键区间有效度

Abstract: 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.

Key words: resource allocating, Markov process, critical path, critical region, critical region reliability