计算机工程 ›› 2018, Vol. 44 ›› Issue (8): 30-37.doi: 10.19678/j.issn.1000-3428.0047754

所属专题: 云计算专题

• 云计算专题 • 上一篇    下一篇

基于期限约束与关键路径的云工作流调度

刘雨潇,王毅,袁磊,吴钊   

  1. 湖北文理学院 数学与计算机科学学院,湖北 襄阳 441053
  • 收稿日期:2017-06-29 出版日期:2018-08-15 发布日期:2018-08-15
  • 作者简介:刘雨潇(1982—),男,讲师、硕士,主研方向为云计算、大数据;王毅,副教授、硕士;袁磊,教授;吴钊,教授、博士。
  • 基金项目:

    国家自然科学基金面上项目(61272296,61172084);湖北省自然科学基金面上项目(2014CFB634);湖北省襄阳市科技计划项目(2015zd26)。

Cloud Workflow Scheduling Based on Deadline Constraint and Critical Path

LIU Yuxiao,WANG Yi,YUAN Lei,WU Zhao   

  1. School of Mathematical and Computer Science,Hubei University of Arts and Science,Xiangyang,Hubei 441053,China
  • Received:2017-06-29 Online:2018-08-15 Published:2018-08-15

摘要:

为优化云工作流任务的调度过程,提出基于期限约束与关键路径的工作流调度算法WS-DCCP。结合云资源的异质与弹性特征对任务进行逻辑分层,在此基础上,正比例重分配工作流期限,通过改进的任务升秩与降秩值之和赋予任务优先级,并根据任务优先级构造工作流的约束 关键路径,将约束关键路径上的任务集调度至同一资源以降低通信代价。在满足约束关键路径子期限的条件下寻找执行代价最小化的资源,进而获得满足期限约束的代价最小调度解。仿真结果表明,与IC-PCP算法和JIT算法相比,WS-DCCP算法可以在满足期限约束的同时降低 工作流调度代价,提高调度成功率。

关键词: 云计算, 工作流调度, 期限约束, 任务优先级, 约束关键路径

Abstract:

To optimize the scheduling process of cloud workflow tasks,a workflow scheduling algorithm based on deadline constraint and Critical Path(CP) is presented,which named WS-DCCP.Firstly,combined with the heterogenous and elastic features of cloud resources,all tasks are partitioned into different logic levels.Based on this logic levels,the workflow deadline is proportionally re-distributed.Then,tasks are prioritized by the improved sum of task upwark rank and downward rank,and the Constrainted CP(CCP) are constructed based on task priority.Finally,the tasks set on the CCP are scheduled on the same resource so as to reduce the communication cost.The next is to find the resource minimizing the workflow execution cost under meeting the sub-deadline constraint of the CCP,which can obtain the scheduling solution minimizing the execution cost under meeting deadline constraint.Through the simulation experiments,the performance evaluations are conducted compared with IC-PCP and JIT.The results show that WS-DCCP can reduce the workflow scheduling cost and improve the scheduling success rate while meeting deadline constraints.

Key words: cloud computing, workflow scheduling, deadline constraint, task priority, Constrainted Critical Path(CCP)

中图分类号: