云环境下基于可靠性的均衡任务调度算法研究

摘要/Abstract

摘要： 云计算作为一种新兴的具有商业特性的计算模式,已经受到了广泛的关注。云计算中的关键问题——任务调度问题也成为了社会各界研究的热点。主要以云计算系统中的可靠性需求为优化目标,运用博弈论工具,将云计算的任务调度系统建模为一个合作博弈模型。合作博弈的参与者为计算节点,效用函数为计算节点在稳定状态下的提供能力,博弈策略为任务在计算节点上的速率分配策略。系统中的各计算节点相互合作,选择自己的博弈策略,以期使系统在稳定状态下的提供能力最大。将计算节点看作具有一般重试时间和服务器崩溃的M/G/1排队系统,根据M/G/1排队论,分析了计算节点在稳定状态的提供能力,并根据合作博弈理论知识,证明了纳什讨价还价解的存在性,从而给出了最优博弈策略的求解算法；在此基础上,给出了基于可靠性的均衡任务调度算法。

Abstract: As an emerging computing model with commercial properties,cloud computing has been widely concerned.In the research of cloud computing,task scheduling is a key issue.In this paper,we considered the requirements of reliability as the main target to optimize.Using game theory,we modeled the task scheduling system as a cooperative game.In the cooperative game model,computing nodes are participants,the ability that computing nodes can provide under steady state is the utility function and the strategy in the game is the task rate allocation strategy on computing nodes.To make the system provide max ability under steady state,computing nodes in the system cooperate with each other,choosing their own game strategy.We regarded the computing nodes as M/G/1 queues in this paper,and according to the M/G/1queuing theory we analyzed the ability that computing nodes can provide under steady state.We proved that Nash bargaining solution exists.On this basis,we proposed the balancing task scheduling algrithm based on reliability.

Key words: Cloud computing,Cooperative game,Task scheduling,Bargaining solution,Reliability

王勇,刘美林,李凯,任兴田,许荣强. 云环境下基于可靠性的均衡任务调度算法研究[J]. 计算机科学, 2015, 42(Z6): 325-331. https://doi.org/

WANG Yong, LIU Mei-lin, LI Kai, REN Xing-tian and XU Rong-qiang. Reliability-based Job Scheduling Algorithm in Cloud Computing[J]. Computer Science, 2015, 42(Z6): 325-331. https://doi.org/

参考文献

[1] 朱宗斌,杜中军.基于改进GA的云计算任务调度算法[J].计算机工程与应用,2011,2(9)
[2] 李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,1(1)
[3] 张春艳,刘清林,孟珂.基于蚁群优化算法的计算任务分配[J].计算机应用,2012,2(5):1418-1420
[4] 刘永,王新华,邢长明,等.云计算环境下基于蚁群优化算法的资源调度策略[J].计算机技术发展,2011,1(9)
[5] 华夏渝,郑骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报:自然科学版,2010
[6] 王永贵,韩瑞莲.基于改进蚁群算法的云环境任务调度研究[J].计算机测量与控制,2011,9(5):1203-1211
[7] Iyer R,Illikkal R,Tickoo O,et al.VM3:Measuring,Modeling and Managing VM Shared Resources[J].Computer Networks,2009,3(17):2873-2887
[8] Freeman T,Keahey K.Flying Low:Simple Leases with Workspace Pilot[C]∥Proc of the 14th International Euro-Par Conference on Parallel Processing.Berlin:Springer-Verlag,2008:499-509
[9] Buyya R,Yeoa C S,Venugopal S.Market-Oriented Cloud Computing:vision,hype and relaity for delivering IT services as computing utilities[C]∥Proc of the 10th IEEE International Conference on High Performance Computing and Communications.2008:1-12
[10] Buyya R,Yeoa C S,Venugopal S,et al.Cloud Computing and Emerging IT Platforms:vision,hype and relity for delivering computing as the 5th utility[J].Future Generation Computer Systems,2009,5(8):599-616
[11] He Xiao-shan,Sum Xian-he,vol L aseewski G.QoS Guided Min-Min Heuristic for Grid Task Scheduling[J].Journal of Compu-ter Science and Technology,2003,8(4):442-451
[12] Chanhan S S,Joshi R C.A Heuristic for QoS Based Independent Task Scheduling in Grid Environment[C]∥Proc of Internatio-nal Conference on Industrial and Information Systems.2010:102-106
[13] Xu Meng,Cui Li-zhen,Wang Hai-yang,et al.A Multiple QoSConstrained Scheduling Strategy of Multiple Workflows for Cloud Computing[C]∥Proc of IEEE International Symposium on Parallel and Distributed Processing with Applications.2009:629-634
[14] Prodan R,Wieczorek M,Fard H M.Double Auction-Based Sch-eduling of Scientific Applications in Distributed Grid and Cloud Environments[J].Journal Grid Computing,2011,9(4):531-548
[15] Mezmaz M,Melab N,Kessaci Y,et al.A Parallel Bi-objective Hybrid Metaheuristic for Energy-Aware Scheduling for Cloud Computing Systems[J].Parallel Distributed Computing,2011,1(1):1497-1508
[16] Wang Jin-ting.Reliability Analysis of M/G/1 Queues with General Retrial Times and Server Breakdowns[J].Progress in Natural Science,2006,6(5):464-473
[17] 孙荣桓,李建.排队论基础[M].北京:科学出版社,2002
[18] Nash J.The Bargaining Problem[J].Econometrica,1950,18(2):155-162
[19] Muthoo A.Bargaining Theory with Applications[M].Cam-bridge,UK:Cambridge University Press,1999
[20] 王勇,李凯,刘美林.基于可靠性和非合作博弈的计算网格任务调度方法[P].中国发明专利,2012
[21] Chow Y C,Kohler W H.Models for Dynamic Load Balancing in A Heterogeneous Multiple Processor System[J].IEEE Transaction on Computers,1979,8:354-361

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed