计算机科学 ›› 2020, Vol. 47 ›› Issue (6): 252-259.doi: 10.11896/jsjkx.190400047
所属专题: 网络通信
孙敏, 陈中雄, 叶侨楠
SUN Min, CHEN Zhong-xiong, YE Qiao-nan
摘要: 针对传统算法处理云环境中任务调度时出现的寻优性能差以及寻优方案不能满足用户多样性需求的问题,在考虑任务完成时间、完成成本以及资源闲置率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)两个方面评估算法的调度性能。结果证明,所提算法在保证负载均衡的基础上,缩短了完成时间并降低了完成成本,更适用于复杂多变的云环境下的任务调度。
中图分类号:
[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 |
|