云计算中任务调度研究的调查

doi:10.11896/j.issn.1002-137X.2019.03.001

摘要/Abstract

摘要： 云计算通过虚拟技术将各类计算资源从底层硬件中剥离出来并进行动态扩展,以按需付费的方式提供给用户使用。云平台由不同的硬件架构和巨大的数据资源组成,当用户所提交的任务数量逐步增长时,如何通过调度算法对其进行有效调度并合理分配资源成为云计算中的关键环节。首先对云计算及其任务调度进行概要介绍,描述调度流程、主要算法和评测指标;随后根据不同指标和算法对近年来的相关文献进行调研概述,归纳对比了一些算法的主要特点;在此基础上,提出了未来研究所面临的几个关键环节。在实际应用中,需要根据任务和资源的不确定性和动态变化情况灵活采取调度策略,并尽可能考虑多个性能指标,综合提高云计算的运行效率和服务质量。

关键词: 服务水平协议, 服务质量, 任务调度, 虚拟化, 云计算

Abstract: In cloud computing,virtualization technology separates various kinds of computing resources from the underlying infrastructure and expands them dynamically,and it allows users to pay on the basis of usage.Cloud platform is a heterogeneous system which consists of different hardware and huge data resources.With the increasing number of tasks,it is critical to schedule users’ tasks and allocate resources effectively through task scheduling algorithm.This paper illustrated a brief introduction of cloud computing,task scheduling algorithm and the core scheduling process including evaluation metrics with some figures.Then,it proposed an overview of the related literatures and algorithms in recent years.Finally,this paper presented some key aspects of the research.In realistic applications due to the varying si-tuation of tasks and uncertainty in resources,it is crucial to select the scheduling strategy accordingly,and taking more performance indicators into consideration can enhance the efficiency and quality of service in cloud computing.

Key words: Cloud computing, QoS, SLA, Task scheduling, Virtualization

中图分类号:

TP301

马小晋,饶国宾,许华虎. 云计算中任务调度研究的调查[J]. 计算机科学, 2019, 46(3): 1-8. https://doi.org/10.11896/j.issn.1002-137X.2019.03.001

MA Xiao-jin, RAO Guo-bin, XU Hua-hu. Research on Task Scheduling in Cloud Computing[J]. Computer Science, 2019, 46(3): 1-8. https://doi.org/10.11896/j.issn.1002-137X.2019.03.001

参考文献

[1]KEAHEY K,FIGUEIREDO R,FORTES J,et al.Science
clouds:Early experiences in cloud computing for scientific applications[C]∥Proceedings of Cloud Computing and Its Appllications.2008:825-830.
[2]TSAI J T,FANG J C,CHOU J H.Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm[J].Computers & Ope-rations Research,2013,40(12):3045-3055.
[3]LIN W W,QI D Y.Survey of Resource Scheduling in Cloud Computing[J].Computer Science,2012,39(10):1-6.(in Chinese)
林伟伟,齐德昱.云计算资源调度研究综述[J].计算机科学,2012,39(10):1-6.
[4]VIJINDRA,SHENAI S.Survey on Scheduling Issues in Cloud Computing[J].Procedia Engineering,2012(38):2881-2888.
[5]ZHAN Z H,LIU X F,GONG Y J,et al.Cloud Computing Resource Scheduling and a Survey of Its Evolutionary Approaches[J].Acm Computing Surveys,2015,47(4):1-33.
[6]PANWAR N,RAUTHAN M S.Analysis of various task sche-
duling algorithms in cloud environment:Review[C]∥International Conference on Cloud Computing,Data Science & Engineering-Confluence.IEEE,2017:255-261.
[7]ISRAR H.Architecture level mapping of Cloud Computing with Grid Computing[J].International Journal of Engineering Scien-ces & Emerging Technologies,2013,5(1):7-11.
[8]FOSTER I,ZHAO Y,RAICU I,et al.Cloud Computing and
Grid Computing 360-Degree Compared[C]∥Grid Computing Environments Workshop.IEEE,2009:1-10.
[9]KOMARASAMY D,MUTHUSWAMY V.Adaptive Deadline
Based Dependent Job Scheduling algorithm in cloud computing[C]∥Seventh International Conference on Advanced Computing.IEEE,2016:1-5.
[10]BUYYA R,GARG S K,CALHEIROS R N.SLA-oriented re-
source provisioning for cloud computing:challenges,architecture,and solutions[C]∥International Conference on Cloud and Service Computing.IEEE Computer Society,2011:1-10.
[11]WU Q W,ISHIKAWA F,ZHU Q S,et al.Deadline-Constrained Cost Optimization Approaches for Workflow Scheduling in Clouds[J].IEEE Transactions on Parallel & Distributed Systems,2017,28(12):3401-3412.
[12]BIN X L.Research on The Scheduling Technology of Tasks in Real-Time Systems[D].Changsha:National University of Defense Technology,2004.(in Chinese)
宾雪莲.实时系统中的任务调度技术研究[D].长沙:国防科学技术大学,2004.
[13]DORIGO M,CARO G D.Ant colony optimization:a new meta-heuristic[C]∥Proceedings of the 1999 Congress on Evolutiona-ry Computation,1999(CEC 99).IEEE,2002:1470-1477.
[14]王小平,曹立明.遗传算法:理论、应用与软件实现[M].西安:西安交通大学出版社,2002:10-50.
[15]BRATTON D,KENNDEY J.Defining a standard for particle
swarm optimization[C]∥IEEE Swarm Intelligence Symposium.Honolulu,2007:35-46.
[16]RODRIGUEZ F J,GARCIA-MARTINEZ C,LOZANO M.Hybrid Metaheuristics Based on Evolutionary Algorithms and Simu-lated Annealing:Taxonomy,Comparison,and Synergy Test[J].IEEE Transactions on Evolutionary Computation,2012,16(6):787-800.
[17]JIA Y,BUYYA R.Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms[J].Scientific Programming,2006,14(3-4):217-230.
[18]ORGERIE A,LEFVRE L,GELAS J P.Save Watts in Your Grid:Green Strategies for Energy-Aware Framework in Large Scale Distributed Systems[C]∥IEEE International Conference on Parallel and Distributed Systems.IEEE Computer Society,2008:171-178.
[19]WANG X L,WANG Y P,ZHU H,et al.Energy-Efficient Multi-Job Scheduling Model for Cloud Computing and Its Genetic Algorithm[J].Mathematical Problems in Engineering,2014,2012(6):152-170.
[20]BOSSCHE R V D,VANMECHELEN K,BROECKHOVE J.
Cost-Optimal Scheduling in Hybrid IaaS Clouds for Deadline Constrained Workloads[C]∥IEEE International Conference on Cloud Computing.IEEE Computer Society,2010:228-235.
[21]ABRISHAMI S,NAGHIBZADEH M.Deadline-constrained work-
flow scheduling in software as a service Cloud[J].Scientia Iranica,2012,19(3):680-689.
[22]OPRESCU A M,KIELMANN T.Bag-of-Tasks Scheduling under Budget Constraints[C]∥IEEE Second International Confe-rence on Cloud Computing Technology and Science.IEEE Computer Society,2010:351-359.
[23]BOSSCHE R V D,VANMECHELEN K,BROECKHOVE J.
Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds[J].Future Generation Computer Systems,2013,29(4):973-985.
[24]LIU Z P,WANG S G,SUN Q B,et al.Cost-Aware Cloud Servi-
ce Request Scheduling for SaaS Providers[J].Journal of Beijing University of Posts & Telecommunications,2013,57(2):291-301.
[25]SU S,LI J,HUANG Q J,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,39(4-5):177-188.
[26]SINGH A,JUNEJA D,MALHOTRA M.Autonomous Agent
Based Load Balancing Algorithm in Cloud Computing[J].Procedia Computer Science,2015,45:832-841.
[27]FAN Z Q,SHEN H,WU Y B,et al.Simulated-Annealing Load Balancing for Resource Allocation in Cloud Environments[C]∥International Conference on Parallel and Distributed Computing,Applications and Technologies.IEEE,2014:1-6.
[28]SINGHAL U,JAIN S.A New Fuzzy Logic and GSO based Load balancing Mechanism for Public Cloud[J].International Journal of Grid & Distributed Computing,2014,7(5):97-110.
[29]ARON R,CHANA I.Bacterial foraging based hyper-heuristic for resource scheduling in grid computing[J].Future Generation Computer Systems,2013,29(3):751-762.
[30]CHAWLA Y,BHONSLE M.Dynamically Optimized Cost Based
Task Scheduling in Cloud Computing[J].International Journal of Emerging Trends & Technology in Computer Science,2013,2(3):38-42.
[31]RAHMAN M,HASSAN R,RANJAN R,et al.Adaptive workflow scheduling for dynamic grid and cloud computing environment[J].Concurrency & Computation Practice & Experience,2013,25(13):1816-1842.
[32]MARZOLLA M,MIRANDOLA R.Dynamic power manage-
ment for QoS-aware applications[J].Sustainable Computing Informatics & Systems,2013,3(4):231-248.
[33]MA Y,GONG B,SUGIHARA R,et al.Energy-efficient deadline scheduling for heterogeneous systems[J].Journal of Parallel & Distributed Computing,2012,72(12):1725-1740.
[34]YASSA S,CHELOUAH R,KADIMA H,et al.Multi-objective approach for energy-aware workflow scheduling in cloud computing environments[J].The Scientific World Journal,2013,2013(3-4):1-13.
[35]CHEN C B,HE B S,TANG X Y.Green-aware workload sche-
duling in geographically distributed data centers[C]∥IEEE,International Conference on Cloud Computing Technology and Scien-ce.IEEE,2013:82-89.
[36]WANG X,YEO C S,BUYYA R,et al.Optimizing Makespan and Reliability for Workflow Applications with Reputation and Look-ahead Genetic Algorithm[J].Future Generation Computer Systems,2012,27(8):1124-1134.
[37]LIU H,XU D,MIAO H K.Ant Colony Optimization Based
Service Flow Scheduling with Various QoS Requirements in Cloud Computing[C]∥First ACIS International Symposium on Software and Network Engineering.IEEE Computer Society,2011:53-58.
[38]CAO J F,CHEN J J,ZHAO Q S.An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm[J].Cybernetics & Information Technologies,2014,14(1):25-39.
[39]WANG S Y,QIAN Z Z,YUAN J B,et al.A DVFS Based Energy-Efficient Tasks Scheduling in a Data Center[J].IEEE Access,2017,5(99):13090-13102.
[40]XU X L,CAO L L,WANG X H.Adaptive Task Scheduling
Strategy Based on Dynamic Workload Adjustment for Heterogeneous Hadoop Clusters[J].IEEE Systems Journal,2017,10(2):471-482.
[41]LIN W W,WANG W Q,WU W T,et al.A Heuristic Task Scheduling Algorithm Based on Server Power Efficiency Model in Cloud Environments[J／OL].https://doi.org/10.1016/j.suscom.2017.10.007.
[42]KESHANCHI B,SOURI A,NAVIMIPOUR N J.An improved genetic algorithm for task scheduling in the cloud environments using the priority queues:Formal verification,simulation,and statistical testing[J].Journal of Systems & Software,2017,124(2017):1-21.
[43]CHEN W H,XIE G Q,LI R F,et al.Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems[J].Future Generation Computer Systems,2017,74(C):1-11.
[44]GABI D,ISMAIL A S,ZAINAL A,et al.Orthogonal Taguchi-based cat algorithm for solving task scheduling problem in cloud computing[J].Neural Computing & Applications,2016(1):1-19.
[45]PENG Z P,CUI D L,ZUO J L,et al.Random task scheduling scheme based on reinforcement learning in cloud computing[J].Cluster Computing,2015,18(4):1595-1607.
[46]DU Y H,VECIANA G D.Scheduling for Cloud-Based Computing Systems to Support Soft Real-Time Applications[C]∥IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications.IEEE,2016:1-9.
[47]YUAN H T,BI J,TAN W,et al.Temporal Task Scheduling
With Constrained Service Delay for Profit Maximization in Hybrid Clouds[J].IEEE Transactions on Automation Science & Engineering,2017,14(1):337-348.
[48]BELLAVISTA P,CINQUE M,CORRADI A,et al.GAMESH:A grid architecture for scalable monitoring and enhanced dependable job scheduling[J].Future Generation Computer Systems,2016(71):192-201.

相关文章 15

[1]	田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[2]	高诗尧, 陈燕俐, 许玉岚. 云环境下基于属性的多关键字可搜索加密方案 Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing 计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[3]	杨玉丽, 李宇航, 邓岸华. 面向个性化需求的云制造服务可信评价模型 Trust Evaluation Model of Cloud Manufacturing Services for Personalized Needs 计算机科学, 2022, 49(3): 354-359. https://doi.org/10.11896/jsjkx.210200116
[4]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载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
[5]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[6]	姚娟, 邢镔, 曾骏, 文俊浩. 云制造服务组合研究综述 Survey on Cloud Manufacturing Service Composition 计算机科学, 2021, 48(7): 245-255. https://doi.org/10.11896/jsjkx.200800173
[7]	孙明玮, 司维超, 董琪. 基于多维度数据的网络服务质量的综合评估研究 Research on Comprehensive Evaluation of Network Quality of Service Based on Multidimensional Data 计算机科学, 2021, 48(6A): 246-249. https://doi.org/10.11896/jsjkx.200900131
[8]	王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[9]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[10]	潘瑞杰, 王高才, 黄珩逸. 云计算下基于动态用户信任度的属性访问控制 Attribute Access Control Based on Dynamic User Trust in Cloud Computing 计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013
[11]	陈玉平, 刘波, 林伟伟, 程慧雯. 云边协同综述 Survey of Cloud-edge Collaboration 计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109
[12]	蒋慧敏, 蒋哲远. 企业云服务体系结构的参考模型与开发方法 Reference Model and Development Methodology for Enterprise Cloud Service Architecture 计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044
[13]	陆懿帆, 曹芮浩, 王俊丽, 闫春钢. 一种基于微服务的检察业务服务封装方法 Method of Encapsulating Procuratorate Affair Services Based on Microservices 计算机科学, 2021, 48(2): 33-40. https://doi.org/10.11896/jsjkx.191100152
[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]	蒋建峰, 尤澜涛. 基于MPLS-TE的数据中心网络QoS优化 QoS Optimization of Data Center Network Based on MPLS-TE 计算机科学, 2021, 48(11A): 485-489. https://doi.org/10.11896/jsjkx.210900190

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed