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

Cloud Workflow Scheduling Based on Deadline Constraint and Critical Path

作　　者：刘雨潇[1] 王毅[1] 袁磊[1] 吴钊[1] LIU Yuxiao,WANG Yi,YUAN Lei,WU Zhao(School of Mathematical and Computer Science, Hubei University of Arts and Science, Xiangyang,Hubei 441053, Chin)

机构地区：[1]湖北文理学院数学与计算机科学学院,湖北襄阳441053

出　　处：《计算机工程》2018年第8期30-37,共8页Computer Engineering

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

摘　　要：为优化云工作流任务的调度过程,提出基于期限约束与关键路径的工作流调度算法WS-DCCP。结合云资源的异质与弹性特征对任务进行逻辑分层,在此基础上,正比例重分配工作流期限,通过改进的任务升秩与降秩值之和赋予任务优先级,并根据任务优先级构造工作流的约束关键路径,将约束关键路径上的任务集调度至同一资源以降低通信代价。在满足约束关键路径子期限的条件下寻找执行代价最小化的资源,进而获得满足期限约束的代价最小调度解。仿真结果表明,与IC-PCP算法和JIT算法相比,WS-DCCP算法可以在满足期限约束的同时降低工作流调度代价,提高调度成功率。To optimize the scheduling process of cloud workflow tasks,a workflowscheduling 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 workflowexecution 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 workflowscheduling cost and improve the scheduling success rate while meeting deadline constraints.

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

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