计算机科学 ›› 2020, Vol. 47 ›› Issue (6): 252-259.doi: 10.11896/jsjkx.190400047

所属专题: 网络通信

• 计算机网络 • 上一篇    下一篇

云环境下基于HEDSM的工作流调度策略

孙敏, 陈中雄, 叶侨楠   

  1. 山西大学计算机与信息技术学院 太原030006
  • 收稿日期:2019-04-08 出版日期:2020-06-15 发布日期:2020-06-10
  • 通讯作者: 孙敏(476957266@qq.com)
  • 基金资助:
    国家自然科学基金项目(61872226);山西省自然科学基金计划资助项目(201701D121052)

Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment

SUN Min, CHEN Zhong-xiong, YE Qiao-nan   

  1. School of Computer & Information Technology,Shanxi University,Taiyuan 030006,China
  • Received:2019-04-08 Online:2020-06-15 Published:2020-06-10
  • About author:SUN Ming,born in 1966,master degree,is a member of China Computer Federation.Her main research interests include cloud computing,intrusion detection,and web collaboration.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61872226) and Natural Science Foundation of Shanxi Province,China (201701D121052)

摘要: 针对传统算法处理云环境中任务调度时出现的寻优性能差以及寻优方案不能满足用户多样性需求的问题,在考虑任务完成时间、完成成本以及资源闲置率3个优化目标的情况下,文中通过模拟启发式算法调度过程(初始化—适应度评估—任务调度—选择),建构了一种层次评估和动态选择模型(Hierarchy Evaluation and Dynamic Selection Model,HEDSM)。在初始化阶段,利用传统的表调度算法(Heterogeneous Earliest Finish Time,HEFT)对工作流任务模型进行预处理,保证任务具有一定的优先级。在适应度评估阶段,从云用户和云服务提供商两个层次构建不同的方案评估模型来同时满足两方面的需求。在任务调度阶段,设置两步调度:1)设置策略集,对任务进行预调度,保证生成的预调度方案继承各个策略的调度优势;2)设置任务迁移策略,对预调度方案进行处理,以此提升算法的寻优性能。在选择阶段,根据不同的评估模型在方案集中选择合适的调度方案。实验利用WorkflowSim仿真平台,采用科学工作流实例进行实验,将传统的Min-Min,Max-Min,FCFS调度策略以及目前存在的IMax-Min和LWRound_Robin调度策略作为对比算法,从用户多样性需求和策略改进比(Improve Ratio of Strategy,IROS)两个方面评估算法的调度性能。结果证明,所提算法在保证负载均衡的基础上,缩短了完成时间并降低了完成成本,更适用于复杂多变的云环境下的任务调度。

关键词: 多目标优化, 工作流, 任务调度, 任务迁移, 云计算

Abstract: The traditional algorithm has poor performance and its optimization solution cannot meet the diversity needs of users,when deals with the task scheduling in the cloud environment.Based on three optimization goals:task completion time,completion cost,and resource idle rate,this paper simulates the process of heuristic algorithm (the initialization,fitness assessment,task scheduling and selection stages) to construct a hierarchical evaluation and dynamic selection model(HEDSM).In the initialization phase,in order to ensure that tasks have a certain priority,the workflow task model is preprocessed using the traditional table scheduling algorithm (HEFT).In the fitness assessment phase,in order to meet the need of two aspects,the difficult solution evaluation modelsare constructed from two levels which are cloud users and cloud service providers.In the task scheduling phase,two-step scheduling is set.First,the policy set is setting,the task is pre-scheduled to ensure that the pre-scheduling scheme inherits the scheduling advantages of each strategy.Second,in order to enhance the performance of the algorithm,the task migration policy is setting to process the pre-scheduling plan.In the selection phase,the appropriate scheduling scheme is selected in the solution set according to the evaluation modle.The experiment uses WorkflowSim simulation platform and scientific workflow instance to make comparative analysis.Traditional Min-Min,Max-Min,FCFS scheduling strategies and existing IMax-Min and LWRound_Robin scheduling strategies are as comparison algorthms.The algorithms are evaluated from the diversity of user requirements and the IROS two aspects.The results show that the propsed algorithm improves the complete time and cost,therefore it is more suitable for the complex task scheduling in cloud environment.

Key words: Cloud computing, Multi-objective optimization, Task immigration, Task scheduling, Workflow

中图分类号: 

  • TP393
[1]NETJINDA N,SIRINAOVAKUL B,ACHALAKUL T.Cost optimal scheduling in IaaS for dependent workload with particle swarm optimization[J].The Journal of Supercomputing,2014,68(3):1579-1603.
[2]VAQUERO L M,RODERO M L,CACERES J,et al.A break in the clouds:Towards a cloud definition[J].ACM SIGCOMM Computer Communication Review,2008,39(1):50-55.
[3]CHEN H,ZHU X,GUO H,et al.Towards energy-efficient scheduling for real-time tasks under uncertain cloudcomputing environment [J].Journal of Systems and Software,2015,99(2):20-35.
[4]RAJ A,KAUR K,DUTTA U,et al.Enhancement of Hadoop Clusters with Virtualization Using the Capacity Scheduler[C]//Third International Conference on Services in Emerging Markets.IEEE,2013.
[5]YADAV R K,MISHRA A K,PRAKASH N,et al.An improved round robin scheduling algorithm for CPU scheduling[J].International Journal on Computer Science and Engineering,2010,2(4):1064-1066.
[6]TRIPATHY B,DASH S,PADHY S K.Dynamic task scheduling using a directed neural network[J].Journal of Parallel and Distributed Computing,2015,75:101-106.
[7]JENA R K.Multi objective task scheduling in cloud environment using nested PSO framework[J].Procedia Computer Science,2015,57:1219-1227.
[8]ALEBRAHIM S,AHMAD I.Task scheduling for heterogeneous computing systems[J].Journal of Supercomputing,2017,73(6):2313-2338.
[9]ATEF A,HAGRAS T,MAHDY Y B,et al.Lower-bound complexity algorithm for task scheduling on heterogeneous grid[J].Computing,2017.
[10]CHITRA D D,RHYMEND U V.Load Balancing in Cloud Computing Environment Using Improved Weighted Round Robin Algorithm for Nonpreemptive Dependent Tasks[J].The Scientific World Journal,2016,2016:1-14.
[11]KAUR N,KAUR K.Improved max-min scheduling algorithm [J].IOSR Journal of Computer Engineering (IOSR-JCE),2015,17(3):42-49.
[12]PANDA S K,JANA P K.Uncertainty-based QoS min-min algorithm for heterogeneous multi-cloud environment[J].Arabian Journal for Science and Engineering,2016,41(8):3003-3025.
[13]ALI S A,ALAM M.Resource-Aware Min-Min (RAMM) Algorithm for Resource Allocation in Cloud Computing Environment[J].arXiv:1803.00045,2018.
[14]BABU L D D,GUNASEKARAN A,KRISHNA P V.A decision-based pre-emptive fair scheduling strategy to process cloud computing work-flows for sustainable enterprise management[M].Inderscience Publishers,2017.
[15]GUPTA I,KUMAR M S,JANA P K.Transfer time-aware workflow scheduling for multi-cloud environment[C]//2016 International Conference on Computing,Communication and Automation (ICCCA).IEEE,2016.
[16]GUO F,YU L,TIAN S,et al.A workflow task scheduling algorithm based on the resources' fuzzy clustering in cloud computing environment[J].International Journal of Communication Systems,2015,28(6):1053-1067.
[17]MAHAJAN K,MAKROO A,DAHIYA D.Round robin with server affinity:a VM load balancing algorithm for cloud based infrastructure[J].Journal of Information Processing Systems,2013,9(3):379-394.
[18]WANG X,YEO C S,BUYYA R,et al.Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm[J].Future Generation Computer Systems,2011,27(8):1124-1134.
[19]CHOUDHARY A,GUPTA I,SINGH V,et al.A GSA based hybrid algorithm for bi-objective workflow scheduling in cloud computing[J].Future Generation Computer Systems,2018,83:14-26.
[20]RODRIGUEZ M A,BUYYA R.Deadline based resource provisioningand scheduling algorithm for scientific workflows on clouds[J].IEEE transactions on Cloud Computing,2014,2(2):222-235.
[21]LEE Y C,WANG C,ZOMAYA A Y,et al.Profit-driven scheduling for cloud services with data access awareness[J].Journal of Parallel and Distributed Computing,2012,72(4):591-602.
[22]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[23]BHARATHI S,CHERVENAK A,DEELMAN E,et al.Characterization of scientific workflows[C]//Third Workshop on Workflows in Support of Large-Scale Science.IEEE,2008:1-10.
[24]TOPCUOGLU H,HARIRI S,WU M.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[25]GUO P,LI T,LI Q L.A load scheduling algorithm in cloud computing environment[J].System Engineering Theory and Practice,2014,34(s1):269-275.
[26]ZHOU Z,HU Z G.Research on Scheduling Algorithms for Integrating Greedy Strategies in Cloud Computing[J].Small Microcomputer System,2015,36(5):1024-1027.
[1] 孙刚, 伍江江, 陈浩, 李军, 徐仕远.
一种基于切比雪夫距离的隐式偏好多目标进化算法
Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance
计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[2] 李浩东, 胡洁, 范勤勤.
基于并行分区搜索的多模态多目标优化及其应用
Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application
计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[3] 柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟.
混合云工作流调度综述
Survey of Hybrid Cloud Workflow Scheduling
计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303
[4] 彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰.
视频缓存策略中QoE和能量效率的公平联合优化
Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos
计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[5] 高诗尧, 陈燕俐, 许玉岚.
云环境下基于属性的多关键字可搜索加密方案
Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing
计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[6] 田冰川, 田臣, 周宇航, 陈贵海, 窦万春.
减少Hadoop集群中网络队头阻塞的调度算法
Reducing Head-of-Line Blocking on Network in Hadoop Clusters
计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[7] 林潮伟, 林兵, 陈星.
边缘环境下基于模糊理论的科学工作流调度研究
Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment
计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[8] 谭双杰, 林宝军, 刘迎春, 赵帅.
基于机器学习的分布式星载RTs系统负载调度算法
Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning
计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[9] 沈彪, 沈立炜, 李弋.
空间众包任务的路径动态调度方法
Dynamic Task Scheduling Method for Space Crowdsourcing
计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[10] 窦帅, 李子扬, 朱家佳, 李晓辉, 李雪松, 米琳, 杨光, 李传荣.
基于jBPM的科学试验管理系统的设计与实现
Design and Implementation of Scientific Experiment Management System Based on jBPM
计算机科学, 2021, 48(6A): 658-663. https://doi.org/10.11896/jsjkx.200600158
[11] 王政, 姜春茂.
一种基于三支决策的云任务调度优化算法
Cloud Task Scheduling Algorithm Based on Three-way Decisions
计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[12] 潘瑞杰, 王高才, 黄珩逸.
云计算下基于动态用户信任度的属性访问控制
Attribute Access Control Based on Dynamic User Trust in Cloud Computing
计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013
[13] 陈玉平, 刘波, 林伟伟, 程慧雯.
云边协同综述
Survey of Cloud-edge Collaboration
计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109
[14] 王文娟, 杜学绘, 任志宇, 单棣斌.
基于因果知识和时空关联的云平台攻击场景重构
Reconstruction of Cloud Platform Attack Scenario Based on Causal Knowledge and Temporal- Spatial Correlation
计算机科学, 2021, 48(2): 317-323. https://doi.org/10.11896/jsjkx.191200172
[15] 蒋慧敏, 蒋哲远.
企业云服务体系结构的参考模型与开发方法
Reference Model and Development Methodology for Enterprise Cloud Service Architecture
计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!