计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (18): 115-118.

• 网络、通信、安全 • 上一篇    下一篇

基于资源状态可靠度的网格工作流调度算法

田国忠1,3,于 炯1,2,侯 勇1,邢 剑1,陈 阵1   

  1. 1.新疆大学 信息科学与工程学院,乌鲁木齐 830046
    2.北京理工大学 计算机学院,北京 100081
    3.新疆工业高等专科学校 计算机工程系,乌鲁木齐 830091
  • 收稿日期:2008-01-14 修回日期:2008-04-14 出版日期:2008-06-21 发布日期:2008-06-21
  • 通讯作者: 田国忠

Workflow scheduling algorithm on grid based on resource state reliability

TIAN Guo-zhong1,3,YU Jiong1,2,HOU Yong1,XING Jian1,CHEN Zhen1   

  1. 1.School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China
    2.School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China
    3.Dept. of Computer Engineering,Xinjiang Polytechnich College,Urumqi 830091,China
  • Received:2008-01-14 Revised:2008-04-14 Online:2008-06-21 Published:2008-06-21
  • Contact: TIAN Guo-zhong

摘要: 针对执行时间限制严格类型的DAG类型网格工作流提出一种新的基于资源状态可靠度的网格工作流调度算法。该算法根据用户提交的工作流执行时间要求,利用Chapman-Kolmogorov向后方程来计算出DAG图中关键路径上各资源在任务到达时刻均处于“闲状态”的概率大小,然后选择一组资源组合的状态可靠度大于用户要求的信任度置信水平α且总费用较低的一组资源。最后通过实验验证了该算法的有效性。

Abstract: To the workflow scheduling of DAG-based workflow in which time constraints are rigid,a new algorithm based on the model of resource state reliability is put forward.According to the requirement of the workflow execution time submitted by users,the algorithm calculates critical paths and obtains the probability for all resources being the idle state at the time when the task arrives by using Chapman-Kolmogorov backward equations,and then makes the choice of the resource system scheme with the lowest expenditure under the certain credit level of the state reliability for the resource combination on the critical path in DAG.The simulation shows the validity of algorithm.