云计算资源调度:策略与算法

摘要/Abstract

摘要： 资源调度是云计算的关键问题之一,它的调度策略与算法直接影响到云系统的性能及成本。首先,根据现有云计算资源调度中的各种策略和算法归纳出4大热点问题:本地性感知任务调度、可靠性感知任务调度、能量感知资源调度以及工作流调度。然后,根据不同的优化目标(性能和成本)将这4个问题划分成3大类型,并对每一类问题中的策略及算法进行了详细描述和比较分析。其次,对4个问题中的相关算法进行了总体比较。最后,对云资源调度的未来研究方向进行了展望。

关键词: 云计算,资源调度,数据本地性,可靠性,能源有效性,工作流调度

Abstract: Resource allocation and scheduling(RAS)are the key issue of cloud computing,and their policy and algorithm have a direct effect on cloud performance and cost．Firstly,four hot topics of cloud RAS,locality-aware task scheduling,reliability-aware scheduling,energy-aware RAS,and workflow scheduling,were presented．And then these fours were classified into three parts according to different optimization objectives(performance and cost),and various existing RAS policies and algorithms were discussed in details．In addition,a comparative analysis of four problems with their representative algorithms was made．Finally,some future research directions of cloud RAS were pointed out.

Key words: Cloud computing,Resource allocation and scheduling,Data locality,Reliability,Energy efficiency,Workflow scheduling

储雅,马廷淮,赵立成. 云计算资源调度:策略与算法[J]. 计算机科学, 2013, 40(11): 8-13. https://doi.org/

CHU Ya,MA Ting-huai and ZHAO Li-cheng. Cloud Computing Resource Scheduling:Policy and Algorithm[J]. Computer Science, 2013, 40(11): 8-13. https://doi.org/

参考文献

[1] Phan L,Zhang Zhuo-yao,Zheng Qi,et al．An Empirical Analysis of Scheduling Techniques for Real-time Cloud-based Data Processing [C]∥Proceedings of 2011IEEE International Confe-rence on Service-Oriented Computing and Applications．2011:1-8
[2] Fischer M J,Su Xue-yuan,Yin Yi-tong．Assigning tasks for effi-ciency in hadoop:extended abstract [C]∥Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures．2010:30-39
[3] Jin Jia-hui,Luo Jun-zhou,Song Ai-bo,et al．Bar:an efficient data locality driven task scheduling algorithm for cloud computing [C]∥Proceedings of the 11th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing(CCGrid)．2011:295-304
[4] Seo S,Jang I,Woo K,et al．HPMR:Prefetching and Pre-Shuff-ling in Shared MapReduce Computation Environment [C]∥Proceedings of IEEE International Conference on Cluster Computing and Workshops(CLUSTER)．2009:1-8
[5] Hammoud M,Sakr M F．Locality-Aware Reduce Task Scheduling for MapReduce [C]∥Proceedings of IEEE Third International Conference on Cloud Computing Technology and Science(CloudCom)．2011:570-576
[6] Zaharia M,Borthakur D,Sarma J S,et al．Delay scheduling:asimple technique for achieving locality and fairness in cluster scheduling [C]∥Proceedings of the 5th European Conference on Computer Systems．2010:265-278
[7] Jin Jia-hui,Luo Jun-zhou,Song Ai-bo,et al．Adaptive delayscheduling algorithm based on data center load analysis [J]．Journal on Communications,2011,32(7):47-56
[8] Zaharia M,Konwinski A,Joseph A D,et al．Improving mapreduce performance in heterogeneous environments [C]∥Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation(OSDI)．2008:29-42
[9] Chen Quan,Zhang Da-qiang,Guo Min-yi,et al．SAMR:A Self-adaptive MapReduce Scheduling Algorithm in Heterogeneous Environment [C]∥Proceedings of IEEE 10th International Conference on Computer and Information Technology(CIT)．2010:2736-2743
[10] Kumar S K S,Balasubramanie P．Dynamic Scheduling for Cloud Reliability using Transportation Problem [J]．Journal of Computer Science,2012,8(10):1615-1626
[11] Wang Wei,Zeng Guo-sun,Tang Dai-zhong,et al．Cloud-DLS:Dynamic trusted scheduling for Cloud computing [J]．Expert Systems with Applications:An International Journal,2012,39(3):2321-2329
[12] Mezmaz M,Melab N,Kessaci Y,et al．A parallel bi-objective hy-brid metaheuristic for energy-aware scheduling for cloud computing systems [J]．Journal of Parallel and Distributed Computing,2011,71(11):1497-1508
[13] Huang Qing-jia,Su Sen,Li Jian,et al．Enhanced Energy-Effi-cient Scheduling for Parallel Applications in Cloud [C]∥Proceedings of the 12th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing(CCGrid)．2012:781-786
[14] Duy T V T,Sato Y,Inoguchi Y．Performance Evaluation of a Green Scheduling Algorithm for Energy Savings in Cloud Computing [C]∥Proceedings of IEEE International Symposium on Parallel & Distributed Processing,Workshops and Phd Forum．2010:1-8
[15] Mazzucco M,Dyachuk D．Optimizing Cloud Providers Revenues via Energy Efficient Server Allocation [J]．Sustainable Computing:Informatics and Systems,2012,2(1):1-12
[16] Younge A J,Laszewski G,Wang L Z,et al．Efficient Resource Management for Cloud Computing Environments [C]∥Proceedings of International Green Computing Conference．2010:357-364
[17] Beloglazov A,Buyya R．Energy Efficient Resource Management in Virtualized Cloud Data Centers [C]∥Proceedings of the 10th IEEE/ACM International Conference on Cluster,Cloud and Grid Computing(CCGrid)．2010:826-831
[18] Beloglazov A,Abawajy J,Buyya R．Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing [J]．Future Generation Computer Systems,2012,28(5):755-768
[19] Beloglazov A,Buyya R．Adaptive threshold-based approach forenergy-efficient consolidation of virtual machines in cloud data centers [C]∥Proceedings of the 8th International Workshop on Middleware for Grids,Clouds and e-Science．2010:1-6
[20] Kim N,Cho J,Seo E．Energy-credit scheduler:An energy-aware virtual machine scheduler for cloud systems [J]．Future Generation Computer Systems,2012,In Press,Corrected Proof,Available online
[21] Garg S K,Yeo C S,Anandasivam A,et al．Environment-con-scious scheduling of HPC applications on distributed Cloud-oriented data centers [J]．Journal of Parallel and Distributed Computing,2011,71(6):732-749
[22] Yu J,Buyya R,Ramamohanarao K．Workflow Scheduling Algorithms for Grid Computing [J]．Metaheuristics for Scheduling in Distributed Computing Environments,Studies in Computational Intelligence,2008,146:173-214
[23] Bittencourt L F,Madeira E R M．HCOC:a cost optimization algorithm for workflow scheduling in hybrid clouds [J]．Journal of Internet Services and Applications,2011,2(3):207-227
[24] Abrishami S,Naghibzadeh M．Deadline-constrained workflowscheduling in software as a service Cloud [J]．Scientia Iranica,2012,19(3):680-689
[25] Abrishami S,Naghibzadeh M,Epema D H J．Deadline-constrainedworkflow scheduling algorithms for Infrastructure as a Ser-vice Clouds [J]．Future Generation Computer Systems,2013,29(1):158-169
[26] Genez T A L,Bittencourt L F,Madeira E R M．WorkflowScheduling for SaaS / PaaS Cloud Providers Considering Two SLA Levels [C]∥Proceedings of IEEE Network Operations and Management Symposium(NOMS)．2012:906-912
[27] Pandey S,Wu L,Guru S M,et al．A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments [C]∥Proceedings of the 24^th IEEE International Conference on Advanced Information Networking and Applications(AINA)．2010:400-407
[28] Wu Zhang-jun,Liu Xiao,Ni Zhi-wei,et al．A market-oriented hierarchical scheduling strategy in cloud workflow systems [J]．The Journal of Supercomputing,2013,63(1):256-293
[29] Zeng Ling-fang,Veeravalli B,Li X L．ScaleStar:Budget Con-scious Scheduling Precedence-Constrained Many-task Workflow Applications in Cloud [C]∥Proceedings of the 26th International Conference on Advanced Information Networking and Applications(AINA)．2012:534-541
[30] Oliveira D,Ocaa K A C S,Baio F,et al．A Provenance-based Adaptive Scheduling Heuristic for Parallel Scientific Workflows in Clouds [J]．Journal of grid Computing,2012,10(3):521-552
[31] Varalakshmi P,Ramaswamy A,Balasubramanian A,et al．AnOptimal Workflow Based Scheduling and Resource Allocation in Cloud [C]∥Proceedings of the First International Conference on Advances in Computing and Communications(ACC)．2011:411-420
[32] Babu L D D,Krishna P V．Honey bee behavior inspired load ba-lancing of tasks in cloud computing environments [J]．Applied Soft Computing,2013,13(2):2292-2303
[33] Bosschce R,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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed