1 引言
云计算为用户提供一种超强计算能力和高效数据存储能力[1-3],云资源动态调度是按需分配或释放虚拟机资源[4].如何调度资源保证负载均衡,提高利用率是当前云计算技术的研究热点之一.文[5-7]主要从云资源提供商收益角度出发,平衡供应商与用户之间的费用;文[8-10]主要考虑云资源利用率,通过合理管理资源达到资源最大化利用.
根据资源实体的离散特性,本文作者最近提出了一种基于离散事件系统(DES)监控理论的云资源分配控制模型及相应的分配算法,实现了云资源利用率的最大化[11].分布式DES[12]已广泛应用于计算机网络、通信网络、军事系统、机器人技术、柔性制造等应用领域,文[13]有这方面较详细的介绍.本文作者也对分布式DES进行了较深入探讨,分别提出了分布式DES的监控机制[14-15].
本文运用分布式DES监控理论研究云资源动态调度问题,将文[11]的工作拓展至分布式情形,建立一种基于分布式DES监控理论的云资源动态调度模型和调度算法.实验表明,在任务量不断增加的情况下,与传统云资源调度策略相比,本文提出的调度策略在资源利用率和任务执行时间等方面都具有较明显的优势.这种将DES监控理论应用于云资源调度是一种尝试与创新,为进一步深入研究云资源动态调度最优化算法等相关问题奠定基础.
2 云资源分配模型分析根据云资源实体的离散特性构造可量化的云资源模型,对云资源系统参数化,并将资源池中的资源按类型记为R={R1,…,Rn},其中Ri表示系统第i类型资源,i=1,…,n.将任务子系统状态集表示为Tlt={T1,…,Tn},其中Tx={RTx,Vi}为第x个请求任务,这里RTx={CR1Tx,…,CRnTx}为任务的资源需求量,而CRiTx表示在第x请求任务中所需要Ri类资源的容量,若请求中无该类资源,则将CRiTx置为0. Vi⊂Vli∪{0}表示为该任务提供服务的虚拟机,取值为0表明暂未资源分配.
将虚拟机子系统的状态集表示为Vli={V1,…,Vn},其中每个Vy={RVy,Mi,Tj}表示系统第y个虚拟机,这里RVy={CR1Vy,…,CRnVy}表示第y个虚拟机中的资源量分配:CRiVy表示第Ri类资源的分配量,若无该类资源,则CRiVy置为0,任务执行完毕后所占资源量都置为0;Mi表示支持该虚拟机的物理服务器,Mi为0时表明该虚拟机已经被销毁;Tj表示该虚拟机服务的任务,Tj为0时表示当前虚拟机空闲.
物理服务器子系统的状态集可表示为Mli={M1,…,Mn},其中Mk={RMk,token}表示第k个物理节点;RMk={CR1Mk,…,CRnMk}表示第k个物理服务器的资源占有量;CRiMk表示第Ri类资源的占有量,若无该资源CRiMk置为0;token表示该物理服务器挂载虚拟机状态,token为1表示已经挂载虚拟机,token为0表示没有挂载.资源模型标记每一类资源的不同状态,为资源动态分配提供基础.
同时,将云资源分配模型分为用户任务子系统、虚拟机子系统和物理节点子系统,如图 1所示,物理节点层m1,…,mn为分布在各地的物理服务器,各服务器可按需划分出多个虚拟机,每个虚拟机都是一个具有计算能力的资源提供点[16].
在云资源分配的调度过程中,先按需申请虚拟机,服务完毕后回收资源,保留常用的虚拟器配置.本文优先将可拆分的大任务分解为多个子任务,分发到不同的服务器来保障负载均衡.目前,Hadoop技术能有效实现任务拆分[17],服务器负载态可从系统响应时间t是否超出预算及性能参数是否低于阀值来判断,其中响应时间为
(1) |
其中,k表示时钟周期个数,g表示机器周期的个数,N表示当前虚拟机所分配的内存容量,I为当前任务的平均指令数.
本文引入欧氏距离来表示参数间的贴近度. 2个资源载体Tx与Py之间的资源欧氏距离为
(2) |
为求出最大贴进度,需找出使得多参资源体的欧氏距离D(x,y)最小的y值.当云资源分配时,本文优先利用碎片资源最大化资源利用率U:
(3) |
在不超过系统性能阀值情况下,缩短完成所有任务的执行时间之和t:
(4) |
在分布式云资源DES系统中,任务子系统状态转移如图 2所示,t0,…,t5⊂Tli表示某任务的各种状态,t0表示任务初始化,t1表示任务进入等待队列,t2表示任务得到分配,t3表示任务被拆解后的状态,t4表示任务执行完毕;a,b,c,d,e,f,g⊂Σ表示事件,a表示任务由初始状态进入等待状态,b表示由等待状态获得资源分配,c表示存在满足条件的虚拟机资源,d表示将任务Ti分解为多个子任务Ti1,…,Tin并进入子任务状态,e表示执行任务的划分,g表示为子任务重新分配虚拟机资源,f表示任务正常执行完毕.因正在执行的任务不一定可划分,所以当出现任务执行超负荷时,事件e的发生与否是不可控的.因此,系统的可控事件集为Lc={a,b,c,d,g,f}.
虚拟机的状态从创建到销毁共有7个状态,如图 3所示.其中,v0表示虚拟机的初始化,v1表示虚拟机失效状态,v2表示虚拟机扩容后状态,v3表示虚拟机正在执行任务,v4表示虚拟机超负荷,v5表示虚拟机迁移后状态,v6表示虚拟机被销毁.各事件分别为:i表示当前虚拟机不能满足任务Tx,j表示将扩容的虚拟机分配给任务,k表示超负荷运行事件,h表示为虚拟机分配任务,w表示虚拟机正常提供服务至任务完成,o表示虚拟机迁移,q表示虚拟机在新宿主上提供正常服务直至任务完成,x表示虚拟机失效事件,y表示虚拟机人为或非人为的重启事件,u表示虚拟机销毁事件因虚拟机是否将失效是不因人为改变,所以属于不可控事件.同理,因为某种原因导致任务执行出现超负荷运算也属于不可控事件.因此,系统可控事件集为Lc={i,j,h,w,o,q,u},而不可控事件集为Luc={x,y,k}.
物理服务器子系统主要有初始化、死机、分配虚拟机等状态,其状态转移如图 4所示.其中,m0,…,mn⊂Mli表示物理服务器的各种状态,m0表示初始化的物理服务器,m1表示物理服务器失效状态(如死机故障),m2~mn表示物理服务器上挂载的虚拟机;α,β,χ,η⊂Σ表示系统事件,α表示物理服务器故障事件,β表示人为或非人为的物理服务器恢复事件,χ、γ表示资源分配事件(如创建虚拟机),η表示资源回收事件(如虚拟机销毁事件).同理,物理服务器的失效是不可控的,因此可控事件集Lc={χ,γ,η}.
根据云任务动态配置虚拟机资源,如图 5所示,系统中存在任务和资源全局控制器Cg和局部控制器Ct、Cv、Cm,在各局部控制系统中,当子系统处于不可接受状态时,通过控制可控事件的发生使子系统到达可接受状态,若子系统中出现不可控事件,局部控制器向全局控制器反馈,由全局控制器协调控制其它子系统控制器,使整个系统最终到达可接受状态.
基于分布式DES云资源动态调度策略主要作用为:
(1) 保障资源利用率.先通过全局控制器Cg计算空闲状态的虚拟机的各类资源量与任务的各类资源量之间的贴近度,通过对比找出最合适的虚拟机,再由局部控制器Ct控制事件c的发生;若监测到任务处于等待状态,则局部控制器Ct需要将消息传给全局控制器Cg,全局控制器控制局部控制器Cv,监控是否符合扩容条件:若符合,则控制事件i发生;否则,全局控制器Cg控制局部控制器Cm,控制事件x产生,生成新的虚拟机,局部控制器Ct控制事件b发生,实现资源分配.
(2) 提高服务性能.当监控到任务执行出现超负荷状态,判断任务是否可划分为子任务:若可分,则局部控制器Ct控制事件eg的产生划分子任务,并分配新虚拟机;若不可分,则将消息传递给全局控制器Cg,由Cg控制局部控制器Cv,控制事件o发生,将虚拟机迁移到性能较好的物理服务器.
4 云资源调度的算法实现云资源动态调度流程图如图 6所示,图中“VM”表示“虚拟机(virtual machine)”.
云资源动态调度算法描述如下:
输入:任务请求队列Tlt、资源池中物理服务器Mlm、虚拟机Vlv;
输出:资源分配表A、资源利用率、任务执行时间之和.
执行:
(1) 初始化资源分配:
初始化Tlt、Vlv、Mlm;
根据式(2) 求D(x,y);
then 将Vy分配给Tx,并修改资源载体状态,
(2) 资源动态调度调整:
∀Tx={RTx,0}
∀Vy={RTx,Mi,0}⊂Vli|∃Ri⊂R,CRiTx>CRiVy
if ∃Mk={RMk,1}{
for {∀Vy={RVy,Mk,Tj∪0}
标记资源碎片R′={CR1Mk-CR1Vy,…,CRiMk-CRiVy}
if ∀Ri⊂R(RTx+τ < R′)∧min D(X,Y)
then建立新虚拟机并修改状态
Vnew={RTx+τ,Mk,Tx},Mk={RMk-RTx-τ,1}
else break;}
else ∀Mk={RMk,1}{
for ∀Vy= RVy,Mk,Tj∪0
if ∀Ri⊂R,
while ∀Ri⊂R,∃RTx < R′k,建立虚拟机并修改状态,
Vnew={RTx+τ,Mk,Tx},Mk={R′k-RTx-τ,1}
}
else新建虚拟机,分配任务并调整状态
Mnew={RMnew,1},Vnew={RTx+τ,Mnew,Tx}.
}
(3) 优化调整:
∀Vy={RVy,Mk,Tx}⊂Vli,由式(1) 得响应时间t;
for执行时间T>t
if ∃R′满足need
then扩容虚拟机并修改状态,
Vy=Vyenlarge={RVy+need,Mk,Tx};
else Tx={Tx1,Tx2,Tx3…Txi}可拆分标识,
then ∀Txi={Rxi,0},转至第1步;
else ∃Mj,j≠k,∀Ri|CRiMj<CRiVy,
then Vy迁移至Mj,Vy={RVy,Mj,Tx}.
(4) 返回任务资源分配并计算资源利用率:
Tx={RTx,Vy},由式(3) 求得资源利用率U.
(5) 全局资源回收调整:
回收扩容的虚拟机Vyenlarge=(RVy,Mk,0)=(0,0,0).
5 仿真实验实验采用墨尔本大学云计算与分布式系统实验室研发的CloudSim[18]框架模拟云环境中的资源分配.本文首先初始化数据中心1和数据中心2,每个数据中心共有20台物理服务器,每个数据中心预先初始化4台物理服务器,一个虚拟机节点.初始化任务队列中有200个任务,每个任务的长度区间为[500,2 000]条指令数.依次以20个任务递增的形式采集实验结果,并将本文的调度算法实验结果与目前较为成熟且广泛应用的Min-Min调度算法[19]及FCFS(first come first service)调度算法[20]的实验结果进行对比,3种算法执行200个任务的完成时间和资源利用率的对比如图 7和图 8所示.
从图 7可以看出,本文提出的分布式DES动态调度算法在任务量较小时,执行时间并没有表现出优势,但随着任务量的增加,其执行时间增速缓慢,平均执行时间维持在3 s以内,较Min-Min算法和FCFS算法都有明显优势.在资源利用率方面,从图 8可知,Min-Min算法由于性能强的资源可能会一直被占用,FCFS算法也由于先到任务可能占用大量资源而导致其它任务响应超时,而本文提出的分布式DES动态调度算法则通过获取资源载体状态,能动态申请和调度资源,因此,随着任务数和资源节点数的不断扩大,其资源利用率曲线上升并维持在80%左右,具有较明显优势.
6 结语本文提出了一种基于分布式离散事件系统监控理论的云资源动态调度方法,能从全局角度动态对虚拟机进行合理扩充、迁移及释放,并通过局部控制器与全局控制器之间的信息交互,实现了云资源的动态调度.实验表明,随着任务数量的不断递增,该调度方法在提高资源利用率及缩短任务执行时间上都具有较明显优势.在后续的研究中,本文将从云资源的价格收益及分配代价的角度出发,结合启发式算法,通过丰富资源属性对该动态调度方法进一步优化.
[1] | Mell P, Grance T. The NIST definition of cloud computing[J]. Communications of the ACM, 2010, 53(6): 50. |
[2] |
刘鹏.
云计算[M]. 北京: 电子工业出版社, 2010.
Liu P. Cloud computing[M]. Beijing: Publishing House of Electronics Industry, 2010. |
[3] |
于雷.
一种基于协作博弈的虚拟网络嵌入策略[J]. 信息与控制, 2016, 45(4): 449–455.
Yu L. Virtual network embedding strategy based on cooperative game theory[J]. Information and Control, 2016, 45(4): 449–455. |
[4] |
龚素文, 艾浩军, 袁远明.
基于迁移技术的云资源动态调度策略研究[J]. 计算机工程与应用, 2014, 50(5): 51–54, 78.
Gong S W, Ai H J, Yuan Y M. Research of cloud resource dynamic scheduling strategy on migration technology[J]. Computer Engineering and Applications, 2014, 50(5): 51–54, 78. |
[5] |
肖鹏, 胡志刚.
云环境中基于混合博弈的虚拟资源定价模型[J]. 计算机集成制造系统, 2014, 20(1): 198–206.
Xiao P, Hu Z G. Hybrid game based virtual resource pricing model in cloud environment[J]. Computer Integrated Manufacturing Systems, 2014, 20(1): 198–206. |
[6] | 孙佳佳, 王兴伟, 高程希, 等.云环境下基于神经网络和群搜索优化的资源分配机制[J].软件学报, 2014, 25(8):1858-1872. Sun J J, Wang X W, Gao C X, Huang M. Resource allocation scheme based on neural network and group search optimization in cloud environment[J]. Journal of Software, 2014, 25(8):1858-1872. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=rjxb201408018&dbname=CJFD&dbcode=CJFQ |
[7] | Li K, Liu C, Li K, et al. A framework of price bidding configurations for resource usage in cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(8): 2168–2181. DOI:10.1109/TPDS.2015.2495120 |
[8] | Xiao Z, Song W, Chen Q. Dynamic resource allocation using virtual machines for cloud computing environment[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1107–1117. DOI:10.1109/TPDS.2012.283 |
[9] |
匡桂娟, 曾国荪.
一种基于时分复用的云资源管理方法[J]. 同济大学学报, 2014, 42(5): 782–789.
Kuang G J, Zeng G S. Time-division multiplexing-based cloud resource management methods[J]. Journal of Tongji University, 2014, 42(5): 782–789. |
[10] |
师雪霖, 徐格.
云虚拟机资源分配的效用最大化模型[J]. 计算机学报, 2013, 36(2): 252–262.
Shi X L, Xu G. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252–262. |
[11] |
胡芹, 刘富春.
基于离散事件系统的云资源分配优化控制[J]. 广东工业大学学报, 2016, 33(1): 29–35.
Hu Q, Liu F C. Optimization control of cloud resource allocation based on DES[J]. Journal of Guangdong University of Technology, 2016, 33(1): 29–35. |
[12] | Cassandras C, Lafortune S. Introduction to discrete event systems[M]. New York, USA: Springer Science+Business Media LLC, 2008: 199-211. |
[13] | Schmidt K, Breindl C. Maximally permissive hierarchical control of decentralized discrete event systems[J]. IEEE Transactions on Automatic Control, 2011, 56(4): 723–737. DOI:10.1109/TAC.2010.2067250 |
[14] | Liu F, Lin H. Reliable supervisory control for general architecture of decentralized discrete event systems[J]. Automatica, 2010, 46(9): 1510–1516. DOI:10.1016/j.automatica.2010.06.011 |
[15] |
刘富春.
非确定型离散事件系统双模拟控制的实现[J]. 控制理论与应用, 2015, 32(1): 75–79.
Liu F C. Realization of bisimilarity control of nondeterministic discrete event systems[J]. Control Theory & Applications, 2015, 32(1): 75–79. |
[16] |
向洁, 丁恩杰.
基于虚拟机调度的数据中心节能优化[J]. 计算机应用, 2013, 33(12): 3331–3353.
Xiang J, Ding E J. Energy-saving optimization in datacenter based on virtual machine scheduling[J]. Journal of Computer Applications, 2013, 33(12): 3331–3353. |
[17] |
马汉达, 郝晓宇, 马仁庆.
基于Hadoop的并行PSO-kmeans算法实现Web日志挖掘[J]. 计算机科学, 2015, 42(6A): 470–473.
Ma H D, Hao X Y, Ma Y Q. Parallel PSO-kmeans algorithm implementing web log mining based on Hadoop[J]. Computer Science, 2015, 42(6A): 470–473. |
[18] | Humane P, Varshapriya J N. Simulation of cloud infrastructure using CloudSim simulator:A practical approach for researchers[C]//International Conference on Smart Technologies and Management for Computing, Communication, Controls, Energy and Materials. Piscataway, NJ, USA:IEEE, 2015:207-211. |
[19] | Miriam D D H, Easwarakumar K S. A double Min-Min algorithm for task metascheduler on hypercubic P2P grid systems[J]. International Journal of Computer Science Issues, 2010, 7(4): 8–18. |
[20] | Hsieh S Y, Chen C T, Chen C H, et al. Novel scheduling algorithms for efficient deployment of map reduce applications in heterogeneous computing environments[J]. IEEE Transactions on cloud Computing, 2016. |