计算机科学

计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 128-134.doi: 10.11896/jsjkx.180801591

• 网络与通信 • 上一篇    下一篇

云环境下基于优先级的多QoS约束工作流调度

杜艳明1, 肖建华2   

  1. (浙江工业职业技术学院 浙江 绍兴312000)1
    (南开大学现代物流研究中心 天津300071)2
  • 收稿日期:2018-08-29 修回日期:2019-01-19 出版日期:2019-10-15 发布日期:2019-10-21
  • 通讯作者: 杜艳明(1972-),男,硕士,副教授,主要研究方向为可信计算与云计算,E-mail:383128720@qq.com.。
  • 作者简介:肖建华(1979-),男,博士,副教授,硕士生导师,主要研究方向为智能计算、物流系统优化。
  • 基金资助:
    本文受国家自然科学基金项目(60903105)资助。

Workflow Scheduling Strategy with Multi-QoS Constraint Based on Priority in Cloud Environment

DU Yan-ming1, XIAO Jian-hua2   

  1. (Zhejiang Industry Polytechnic College,Shaoxing,Zhejiang 312000,China)1
    (Research Center of Logistics,Nankai Univeristy,Tianjin 300071,China)2
  • Received:2018-08-29 Revised:2019-01-19 Online:2019-10-15 Published:2019-10-21

PDF (PC)

1045

摘要： 为了实现云计算环境中工作流调度的执行时间与代价的均衡优化,提出了一种截止时间与预算双QoS约束条件下的工作流均衡调度算法。该算法将最优调度方案的求解过程划分为两个阶段:资源分级调度阶段和任务分级调度阶段。资源分级调度阶段中,算法通过任务升秩值定义任务优先级,并将任务按升秩值排序后为任务选择满足双QoS约束的适合资源集;进一步,在任务分级调度阶段,算法定义了4条满足时间/代价均衡的最优资源选择规则,进而得到最优工作流调度方案。通过设计算例,详细阐述了新算法的思想。最后,通过现实科学工作流的仿真测试,将所提算法与同类算法进行了性能比较。结果表明,在不同紧密程度的约束条件下,所提算法在调度代价、调度时间和调度成功率等指标上均表现出更优的性能,可以有效实现均衡调度。

关键词: 多QoS约束, 工作流调度, 任务优先级, 预算约束, 云计算环境

Abstract: For implementing the trade-off optimization between the execution time and cost of scientific workflow scheduling in cloud environment,this paper proposed a Time-Cost trade-off workflow Task Scheduling algorithm (TCTS) under bi-constrainted condition of deadline and budget.TCTS divides the solving process of the optimal schedu-ling scheme into two stages:the resource levelscheduling stage and the task level scheduling stage.In the resource level scheduling stage,the algorithm defines the priority of a task by the upward rank,and selects the suitable resource set satisfying bi-QoS constraints for tasks according to tasks’ rank.Further,in the task level scheduling stage,the algorithm defines four rules of selecting the optimal resource based upon Time-Cost trade-off,which can obtain the optimal workflow scheduling scheme.This paper elaborated the idea of the proposed algorithm by a designed example.Through the simulation tests of real-world scientific workflows,the proposed algorithm is compared with the same types of algorithms.The results show that under the constraint conditions with different tight degrees,the proposed algorithm has better perfor-mance on some indexes such as the scheduling cost,the scheduling time and the schedule success,which will effectively realize the balanced scheduling.

Key words: Budget constraint, Cloud computing environment, Multi-QoS constraint, Task’s priority, Workflow scheduling

中图分类号: 

  • TP393
[1]FARD H M,PRODAN R,BARRIONUEVO J,et al.A Multi-objective Approach for Workflow Scheduling in Heterogeneous Environments[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.Ottawa:ACM,2012:300-309.
[2]SU X,LIU Y J,YANG J,et al,Application of grid workflow scheduling based on chaos-genetic algorithm[J].Application Research of Computers,2013,30(9):2645-2647.
[3]SAKELLARIOU R,ZHAO H,TSIAKKOURI E,et al.Scheduling Workflows with Budget Constraints[M]//Gorlatch S,Danelutto M,eds.Integrated Research in GRID Computing.Germany:Springer,2007:189-202.
[4]MALAWSKI M,JUVE G,DEELMAN E,et al.Cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[C]//International Conference for High PERFORMANCE Computing,Networking,Storage and Analysis.Edinburgh:IEEE Computer Society,2012:1-11.
[5]ABRISHAMI S,NAGHIBZADEH M,EPEMA D H J.Dead-line-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds[J].Future Generation Computer Systems,2013,29(1):158-169.
[6]CHOPRA N,SINGH S.HEFT based workflow scheduling algorithm for cost optimization within deadline in hybrid clouds[C]//4th International Conference on Computing,Communications and Network Technology.Tiruchengode:IEEE,2013:1-6.
[7]BOSSCHE D.Online cost-efficient scheduling of deadline-con-strained workloads on hybrid clouds[J].Future Generation Computer Systems,2013,29(4):973-985.
[8]VERMA A.Deadline and Budget Distribution based Cost- Time Optimization Workflow Scheduling Algorithm for Cloud[C]//IJCA Proceeding of International Conference on Recent Advances and Future Trends in IT.India,2012:1-4.
[9]CAO B,WANG X T,XIONG L R,et.al,Searching method for particle swarm optimization of cloud workflow scheduling with time constraint[J].Computer Integrated Manufacturing Systems,2016,22(2):372-380.
[10]VERMA A,KAUSHAL S.Deadline constraint heuristic-based genetic algorithm for workflow scheduling in cloud[J].Journal of Grid & Utility Computing,2014,5(2):96-106.
[11]VERMA A,KAUSHAL S.Budget constrained priority based genetic algorithm for workflow scheduling in cloud[C]//Communication and Computing.Bangalore:IET,2013:216-222.
[12]ZHOU A,QU B Y,LI H,et al.Multiobjective evolutionary algorithms:A survey of the state of the art[J].Swarm & Evolutionary Computation,2011,1(1):32-49.
[13]FARD H M,PRODAN R,BARRIONUEVO J,et al.A Multi-objective Approach for Workflow Scheduling in Heterogeneous Environments[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.Ottawa:IEEE,2012:300-309.
[14]SU S,LI J,HUANG Q,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,39(4／5):177-188.
[15]BÉNYI A,DOMBI J D,KERTESZ A.Energy-aware VM Sche-duling in IaaS Clouds using Pliant logic[C]//International Conference on Cloud Computing and Services Science.Bangalore:IEEE,2014:519-526.
[16]CHEN A G,WANG L,REN J S,et al.Multi-constrained scheduling algorithm of cloud workflow based on resource grouping[J].Journal of University of Electronic Science and Technology of China,2017,46(3):562-568.
[17]MA X H,HAN Q,XIN K.Cloud workflow scheduling optimization algirthm based on quality of service[J].Computer Engineering and Design,2018,23(1):151-158.
[18]ZHENG W.Budget-Deadline Constrained Workflow Planning for Admission Control[M]//Economics of Grids,Clouds,Systems,and Services.Springer,2012:105-119.
[19]JUVE G,CHERVENAK A,DEELMAN E,et.al,Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[20]GOYAL T,SINGH A,AGRAWAL A.Cloudsim:simulator for cloud computing infrastructure and modeling[J].Procedia Engineering,2014,38(4):3566-3572.
[1] 林潮伟, 林兵, 陈星.
边缘环境下基于模糊理论的科学工作流调度研究
Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment
计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[2] 雷阳, 姜瑛.
云计算环境下关联节点的异常判断
Anomaly Judgment of Directly Associated Nodes Under Cloud Computing Environment
计算机科学, 2021, 48(1): 295-300. https://doi.org/10.11896/jsjkx.191200186
[3] 马堉银, 郑万波, 马勇, 刘航, 夏云霓, 郭坤银, 陈鹏, 刘诚武.
一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法
Multi-workflow Offloading Method Based on Deep Reinforcement Learning and ProbabilisticPerformance-awarein Edge Computing Environment
计算机科学, 2021, 48(1): 40-48. https://doi.org/10.11896/jsjkx.200900195
[4] 张龙信, 周立前, 文鸿, 肖满生, 邓晓军.
基于异构云计算的成本约束下的工作流能量高效调度算法
Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems
计算机科学, 2020, 47(8): 112-118. https://doi.org/10.11896/jsjkx.200300038
[5] 李廷元, 王博岩.
QoS约束云环境下的工作流能效调度算法
Workflow Energy-efficient Scheduling Algorithm in Cloud Environment with QoS Constraint
计算机科学, 2018, 45(6A): 304-309.
[6] 王国豪,李庆华,刘安丰.
多目标最优化云工作流调度进化遗传算法
Evoluation Genetic Algorithm of Multi-objective Optimization Scheduling on Cloud Workflow
计算机科学, 2018, 45(5): 31-37. https://doi.org/10.11896/j.issn.1002-137X.2018.05.005
[7] 陈赣浪,颜飞龙,潘家辉.
云计算环境下高复杂度动态数据的增量密度快速聚类算法研究
Study on Fast Incremental Clustering Algorithm for High Complexity Dynamic Data in Cloud Computing Environment
计算机科学, 2018, 45(2): 287-290. https://doi.org/10.11896/j.issn.1002-137X.2018.02.049
[8] 杜艳明,肖建华.
云环境中基于混合多目标粒子群的科学工作流调度算法
Scientific Workflow Scheduling Algorithm Based on Hybrid Multi-objective Particle Swarm Optimization in Cloud Environment
计算机科学, 2017, 44(8): 252-259. https://doi.org/10.11896/j.issn.1002-137X.2017.08.043
[9] 范菁,沈杰,熊丽荣.
混合云环境中数据敏感工作流调度
Scheduling Data Sensitive Workflow in Hybrid Cloud
计算机科学, 2015, 42(Z11): 400-405.
[10] 储雅,马廷淮,赵立成.
云计算资源调度:策略与算法
Cloud Computing Resource Scheduling:Policy and Algorithm
计算机科学, 2013, 40(11): 8-13.
[11] 刘勇,乔秀全,李晓峰.
云计算环境下基于Mashup的一种电信网络能力服务提供模式
Telecommunications Network Capability Services Model Based on Mashup Technology in Cloud Computing Environment
计算机科学, 2012, 39(1): 32-36.
[12] 姚磊,戴冠中,张慧翔,任帅.
QoS约束下基于双向分层的网格工作流调度算法
QoS-constrained Workflow Scheduling Algorithm for Grid Computing Based on Two-way Stratified
计算机科学, 2009, 36(9): 24-27.
[13] 颜昕 李腊元.
多QoS约束的层次多播路由算法框架

计算机科学, 2007, 34(2): 27-34.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发