计算机科学 ›› 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, Task scheduling, Workflow, Task immigration, Multi-objective optimization

中图分类号: 

  • 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] 张恺琪, 涂志莹, 初佃辉, 李春山. 基于排队论的服务资源可用性相关研究综述[J]. 计算机科学, 2021, 48(1): 26-33.
[2] 马堉银, 郑万波, 马勇, 刘航, 夏云霓, 郭坤银, 陈鹏, 刘诚武. 一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法[J]. 计算机科学, 2021, 48(1): 40-48.
[3] 雷阳, 姜瑛. 云计算环境下关联节点的异常判断[J]. 计算机科学, 2021, 48(1): 295-300.
[4] 徐蕴琪, 黄荷, 金钟. 容器技术在科学计算中的应用研究[J]. 计算机科学, 2021, 48(1): 319-325.
[5] 李彦, 申德荣, 聂铁铮, 寇月. 面向加密云数据的多关键字语义搜索方法[J]. 计算机科学, 2020, 47(9): 318-323.
[6] 张龙信, 周立前, 文鸿, 肖满生, 邓晓军. 基于异构云计算的成本约束下的工作流能量高效调度算法[J]. 计算机科学, 2020, 47(8): 112-118.
[7] 张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284-290.
[8] 郑友莲, 雷德明, 郑巧仙. 求解高维多目标调度的新型人工蜂群算法[J]. 计算机科学, 2020, 47(7): 186-191.
[9] 马潇潇, 黄艳. 大属性可公开追踪的密文策略属性基加密方案[J]. 计算机科学, 2020, 47(6A): 420-423.
[10] 赵松辉, 任志磊, 江贺. 软件升级问题的多目标优化方法[J]. 计算机科学, 2020, 47(6): 16-23.
[11] 夏春艳, 王兴亚, 张岩. 基于多目标优化的测试用例优先级排序方法[J]. 计算机科学, 2020, 47(6): 38-43.
[12] 金小敏, 滑文强. 移动云计算中面向能耗优化的资源管理[J]. 计算机科学, 2020, 47(6): 247-251.
[13] 胡锦天, 王高才, 徐晓桐. 移动边缘计算中具有能耗优化的任务迁移策略[J]. 计算机科学, 2020, 47(6): 260-265.
[14] 梁俊斌, 张敏, 蒋婵. 社交传感云安全研究进展[J]. 计算机科学, 2020, 47(6): 276-283.
[15] 田宇立, 李宁. 云环境下的系统使用模式与故障分析[J]. 计算机科学, 2020, 47(12): 50-55.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .