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

doi:10.19678/j.issn.1000-3428.0047754

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

所属专题：云计算专题；

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

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

湖北文理学院数学与计算机科学学院,湖北襄阳 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

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

摘要/Abstract

摘要：

为优化云工作流任务的调度过程,提出基于期限约束与关键路径的工作流调度算法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)

中图分类号:

TP393

刘雨潇,王毅,袁磊,吴钊. 基于期限约束与关键路径的云工作流调度[J]. 计算机工程, 2018, 44(8): 30-37.

LIU Yuxiao,WANG Yi,YUAN Lei,WU Zhao. Cloud Workflow Scheduling Based on Deadline Constraint and Critical Path[J]. Computer Engineering, 2018, 44(8): 30-37.

https://www.ecice06.com/CN/Y2018/V44/I8/30

参考文献

［1］KASHLEV A,LU S.A system architecture for running big data workflows in the cloud［C］//Proceedings of IEEE International Conference on Services Computing.Washington D.C.,USA:IEEE Press,2014:51-58.br/ ［2］MADDURI R,CHARD K,CHARD R,et al.The Globus Galaxies platform:delivering science gateways as a service［J］.Concurrency and Computation:Practice and Experience,2015,27(16):4344-4360.br/ ［3］WU F,WU Q,TAN Y.Workflow scheduling in cloud:a survey［J］.Journal of Supercomputing,2015,71(9):3373-3418.br/ ［4］CALHEIROS R N,BUYYA R.Meeting deadlines of scientific workflows in public clouds with tasks replica-tion［J］.IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1787-1796.br/ ［5］SAKELLARIOU R,ZHAO H,TSIAKKOURI E,et al.Scheduling workflows with budget constraints［M］//GORLATCH S,DANELUTO M.Integrated Research in Grid Computing.Berlin,Germany:Springer-Verlag,2012:34-43.br/ ［6］CHARD K,BUBENDORFER K,KOMISARCZUK P.High occupancy resource allocation for grid and cloud systems,a study with drive［C］//Proceedings of ACM International Symposium on High Performance Distributed Computing.New York,USA:ACM Press,2013:73-84.br/ ［7］YU J,BUYYA R,RAMAMOHANARAO K.Workflow scheduling algorithms for grid computing［M］//XHAFA F,ABRAHAM A.Metaheuristics for Scheduling in Distributed Computing Environments.Berlin,Germany:Springer-Verlag,2012:173-214.br/ ［8］TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing［J］.IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.br/ ［9］MAHESWARAN M,ALI S,SIEGEL H J,et al.Dynamic mapping of a class of independent tasks onto heterogeneous computing systems［J］.Journal of Parallel and Distributed Computing,2012,59(2):107-131.br/ ［10］WU C Q,LIN X,YU D,et al.End-to-end delay minimization for scientific workflows in clouds under budget constraint［J］.IEEE Transactions on Cloud Computing,2015,3(2):169-181.br/ ［11］MIRZAYI S,RAFE V.A hybrid heuristic workflow scheduling algorithm for cloud computing environ-ments［J］.Journal of Experimental and Theoretical Artificial Intelligence,2015,27(6):721-735.br/ ［12］YU J,KIRLEY M,BUYYA R.Multi-objective planning for workflow execution on grids［C］//Proceedings of the 8th IEEE/ACM International Conference on Grid Computing.Washington D.C.,USA:IEEE Press,2013:10-17.br/ ［13］马俊波,殷建平.云计算环境下带安全约束的工作流调度问题的研究［J］.计算机工程与科学,2014,36(4):607-614.br/ ［14］杨玉丽,彭新光,黄名选,等.基于离散粒子群优化的云工作流调度［J］.计算机应用研究,2014,31(12):3677-3681.br/ ［15］王月,刘亚,郭继峰,等.基于离散粒子群优化的云计算QoS调度算法［J］.计算机工程,2017,43(6):111-117.br/ ［16］ABRISHAMI S,NAGHIBZADEH M,EPEMA D H.Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds［J］.Future Generation Computer Systems,2013,29(1):158-169.br/ ［17］CALHEIROS R,BUYYA R.Meeting deadlines of scientific workflows in public clouds with tasks replication［J］.IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1787-1796.br/ ［18］BYUN E K,KEE Y S,KIM J S,et al.Cost optimized provisioning of elastic resources for application workflows［J］.Future Generation Computer Systems,2012,27(8):1011-1026.br/ ［19］MALAWSKI M,JUVE G,DEELMAN E,et al.Cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds［C］//Proceedings of International Conference on High Performance Computing,Networking,Storage and Analysis.Washington D.C.,USA:IEEE Press,2012:1-11.br/ ［20］SAHNI J,VIDYARTHI D.A cost-effective deadline-constrained dynamic scheduling algorithm for scientific workflows in a cloud environment［J］.IEEE Transactions on Cloud Computing,2018,6(1):2-18.br/ ［21］GOYAL T,SINGH A,AGRAWAL A.Cloudsim:simulator for cloud computing infrastructure and modeling［J］.Procedia Engineering,2012,38(4):3566-3572.br/

[1]	孙毅, 王会梅, 鲜明, 向航. Kubeflow异构算力调度策略研究[J]. 计算机工程, 2024, 50(2): 25-32.
[2]	李浩阳, 贺小伟, 王宾, 吴昊, 尤琪. 基于改进Informer的云计算资源负载预测[J]. 计算机工程, 2024, 50(2): 43-50.
[3]	刘志彬, 黄秋兰, 胡庆宝, 程耀东, 胡誉, 田浩来. Kubernetes异构资源细粒度调度策略的设计与实现[J]. 计算机工程, 2023, 49(2): 31-36,45.
[4]	王恩旭, 王晓红, 张坤, 张冬雯. 基于双重注意力机制的云计算负载预测模型[J]. 计算机工程, 2023, 49(11): 40-48, 69.
[5]	奚智雯, 蔡晶晶, 阳文敏, 柴志雷. 基于微服务架构FPGA云平台的并发请求调度机制[J]. 计算机工程, 2022, 48(7): 206-213.
[6]	贺小伟, 徐靖杰, 王宾, 吴昊, 张博文. 基于GRU-LSTM组合模型的云计算资源负载预测研究[J]. 计算机工程, 2022, 48(5): 11-17,34.
[7]	施凌鹏, 朱征, 周俊松, 李鑫, 李静. 面向微服务架构的云系统负载均衡机制[J]. 计算机工程, 2021, 47(9): 44-50,58.
[8]	赵宇峰, 雷晟, 张国钢, 耿英三. 基于容器技术的电力设备仿真云平台设计与开发[J]. 计算机工程, 2021, 47(9): 171-177,184.
[9]	倪思源, 扈红超, 刘文彦, 梁浩. 基于轮换策略的异构云资源分配算法[J]. 计算机工程, 2021, 47(6): 44-51,67.
[10]	李凌书, 邬江兴. 面向云网融合SaaS安全的虚拟网络功能映射方法[J]. 计算机工程, 2021, 47(12): 30-39.
[11]	朱嵩, 王化群. 基于Paillier算法的智能电网数据聚合与激励方案[J]. 计算机工程, 2021, 47(11): 166-174.
[12]	王妍, 葛海波, 冯安琪. 云辅助移动边缘计算中的计算卸载策略[J]. 计算机工程, 2020, 46(8): 27-34.
[13]	张继炎, 郑汉垣. 云环境下基于预算分配的科学工作流调度研究[J]. 计算机工程, 2019, 45(9): 40-48.
[14]	徐云涛, 许武军, 翟梦琳. 基于B/S架构的高并发虹膜识别系统[J]. 计算机工程, 2019, 45(8): 102-106,112.
[15]	刘彪,王宝生,邓文平. 云环境下支持弹性伸缩的容器化工作流框架[J]. 计算机工程, 2019, 45(3): 7-13.

选择文件类型/文献管理软件名称

选择包含的内容

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

Cloud Workflow Scheduling Based on Deadline Constraint and Critical Path

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Cloud Workflow Scheduling Based on Deadline Constraint and Critical Path

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价