论文研究-基于随机模型的动态调度算法研究.pdf

所需积分/C币:9 2019-09-20 18:35:57 744KB .PDF

论文研究-基于随机模型的动态调度算法研究.pdf,  针对多资源云环境中虚拟机放置问题,提出了一种在随机模型下综合利用率较高的动态调度算法MIUS (maximize integrated utilization scheduling). 首先,在调度中心建立一个虚拟的中央队列缓存用户任务,然后利用随机路由算法对用户任务进行服务器快速选择,最后在服务器上建立虚拟等待队列并利用MIUS算法进行
增刊 肖逸飞,等:基于随机模型的动态调度算法研究 167 量从左到右依次为标准,MEM密集,CPU密集可放 入PM的数量) 表1EC2中3种典型实例 S={(2.0,0),(1,0,0),(1,0,1).(0,1,1)} 类型 CPU/ECU MEM/ GB Storage/GB 15 定义2若向量N满足 标准 MEM密集 6.5 420 naS-N CPU密集 20 1690 则N为S中的一个最大配置 在例1中,(2,0,0),(1,0.,1),(0,1,1)均满足定义2,而(1.0,0)不满足,因为它被(2,0,0)所包含,由 此,可求出例1中的最大配置集={(2,0,0),(1,0,1),(,1,1)} 由于本文出现多种符号,用表2作归纳 表2主要符号及其含义 符号 含义 PM为空时的所有可行配置集 Qm(t)在时间片t的开始阶段,任务m的WQ的长度 NPM上一种可行的ⅤM配置,是一个M维的向量,Nm表示N中第m维对应的值,即VMm的数量 N?(t)为t时段选择的VM配置,N(0()为上一时间片未完成的任务的集合 C1k第讠台PM中资源k的数量. amk vM需要资源k的数量 2PM2为空时的最大配置集 一个PM1的综合利用率,pk表示PM中k资源的利用率 WT所有任务的平均等待时间,WTm表示任务m在PM1中的平均等待时间.Wm0S表示m类任务 要求的响应时间 入mm类任务到达PM2的平均速率 Wn(t)在时间片t新到达的m类任务的任务数 2.4问题陈述 在本文的云系统中,时间片到达之后,假设m类任务到达PM的平均速率为Am,设p为一个PM1的 综合利用(因为采用 Power- of-two routing算法,任务到达各个PM概相同,所以考虑系统综合利用率, 只需考虑单个PM的综合利用率),则pk表示PM2中k资源的利用率将WT设为任务的平均等待时间 则WTm表示任务m在PM1中的平均等待时间.如此,本文希望通过一个算法使得无论任务产生的速度有 多快(Am有多大),都能理想地解决下面的线性问题 考虑在一个超级时间段(t.T为正整数)内,假设可以找出一个最小的时间片数n,当经过m个时间片 t之后,WQS为空(即vm,Qm=0) n个时间片会产生m个ⅤM配置N={Nm,m=1,2,…,M},=1,2,…,m(N表示N中包含k 资源的数量,Nm表示N中m任务的数量) 使得 P F ∑ 0≤pk≤1 ∑ Pk mIki=1 (5) ∑ im ank ∑ WTm< WTO 168 系统工程理论与实践 第34卷 n∝WTm 如文献[1],本文没有考虑资源之间的权重关系,所以将所有资源的平均利用率作为系统的综合利用率 (公式(3),公式(5)表示进行m次VM配置所得到的k资源利用卒的平均值,并将此作为最终的pk 本文的日标是在不影响QoS的情况下,最大化地利用资源,即在满足(8)的情况下,求出(2).然而,由 (8),(9)可知,越小,等待时间越短,但是考虑到Ck有限,一次性无法处理太多的任务,所以,若m增大, n会增大,由公式(3)(5)可知若n减小,N增大,则ρ会增大,并且由(6)可知,若需要N增大,那么 Nm和αmk都需要增大,即需要每·次都选择任务数量和任务对资源的需求乘积最大的配置 3MIUS调度算法 31MIUS算法核心公式 由2.2节的分析可知需在PM上每次选择综合利用率最大的VM配置,即若一个配置N(t),使得资 源综合利用率最大,则将该N(t)作为t时段开始时被选中的配置方案 本文提出的算法公式如下 () (t)∈arg max N:N+N2(t-)∈S2z k>∑ (10) Qm-l)=Qm(t)+Wm(t)->(Nm(t)+Nm(t) Nm = min(Nm, Qm(t)) (12) 其中,Nn(t-)表示m类任务在上一时间片内未完成的数量.Qm(t)表示在时间片t任务m的WQ长度, Wn(t)表示在时间片t新到达的m类任务的任务数.Nn(t)表示N(t)中m类任务的数量.Nm为N 中VMm对应的值(因为N为M维向量,所以Nm就是第m维对应的值) 公式(10)体现了MIUS最核心的思想:在进行VM创建时,本文首先会确定可行的备选配置N,由于 本文的调度属于非抢占式调度,在进行调度时,可能PM中已有任务正在运行,因此N:N+N(t-)∈9 其次,N中的Nm表示配置为N时,m类任务一次性可放入的数量,但WQ中也许任务数量根本没有达到 Nm,因此,需要选择实际可放入的数量,公式(12)对此进行了处理 公式(11)会在每一个时间片到达之后.进行一次更新式中Nn(t-)体现的思想是,若某类任务长期在 PM中执行,则表示该类任务所需要的执行时间很长,这会严重影响其他队列中任务的执行,因此,需要相应 缩减该类的队列长度,以免该类任务一直被选中 然而,以上公式没有考虑到QoS.从公式(12)可以看出,只要Nm<Qm(t),选择的Mn(t-)就与Qm(t) 无关若N()中Nn()的数量小于m类任务的平均到达数即m类任务的完成率小于到达率则Qm() 会不断增大,导致后米的m类任务长时间得不到执行,从而影响了QoS.由此,本文需要对任务的负载进行 处理 32MIUs对负载的处理 如前所述,本文需要对负载严重的队列进行处理.为此,本文采用了两种策略解决这一问题. 1.路由选择 由于本文采用文献[13]针对异构环境下提出的 Power- of-Two Routing算法从SC对任务进行PM选 择,而该算法是加入最短队列算法( Join-the-shortest-queue,JSQ)的改良算法,对新到的任务会选择包含该 类任务较少的PM,因此能够平衡各个PM之间的队列长度,使得各个PM之间的WQs趋于相同,进而实 现PM之间的负载均衡 2.阈值处理 前面所提到路由选择只能延缓WQ长度的增加,不能从根本上解决问题.于是本文对于负载达到某 阈值进行如下处理 假设Nmx为PM处理VMm的最大数量,若Qm>2Nm3x,则 Nm(t)=(N1, N2 inax 将此时的N(t)作为t时段的ⅤM配置这样处理之后,WQ中 Qm=Q rmax 增刊 肖逸飞,等:基于随机模型的动态调度算法研究 169 通过一次的处理可以最大程度地降低VMnm的工作负载.若WQ中有多个队列超过阈值,则依次进行处 理 如此,本文的算法实现如下所示 Algorithml Power-of-Two Routing + Maximize Integrated Utilization Scheduling npu c:负载强度因子,从0.5变化到3 chosen config:所选ⅤM配置.一个M维数组 1: jobs- getRandJobs(a) 2: plIst= power OfTwoRouting(jobs)//t时间片时,针对任务随机选择PM 3:/对 fInaList中的每一个pm*/ 4://若某一队列达到阈值,返回该队列最大VM配置 5: if one WaitQueue Threshold do 6: return max Weight Config For Queue (one Wait Queue) 7: end if 8: max Weight +MIN-DOU BLE for one config in pm do 10: tempW'eight +(cpu Share(one Config)+ mem Share(oneCon fig))/2 11: if temp Weight> max Weight do 12: max Weight= temp wcight 13: chosen Config oneConfig 14: end if 15: end for 16: return chosen Config 33MIUs与 Myopic Maxweight的综合利用率比较 在例1中假设目前WQs中,Q1-1,Q2-1,Q3-1.最大配置集!;-{(2,0,0)、(1,0,1).(0,1,1)} 为了简化,综合利用率只考虑MEM和CPU. Δ.利用 Myopic Maxwcight算法获得综合利用率 假定 Weight为目标值, Weight Qm(t)Nm,N∈g,则 max Wcight=Q1N1+Q2N2+Q3N3=1*2+1*0+1*0=2 求得最佳M配置N()为(2,0,0 2*82*15 综合利用率=( cpu share+ mem Share) ≈0.7667. 30 B.利用MIUS算法获得综合利用率 利用公式(10),(12),由于资源的维数K=2,VM类型为3,则 max Weight=>a∑ 1/a11N1+a21N2+a31N 12N1+a22N2+024v 8*0+6.5*1+20*115*0+17.1*1+7*1 ≈0.8433. 求出最佳的VM配置N”()为(0,1).此时,综合利用率= max weight=0.843 由此可知,MIUS算法在理论上比 Myopic Maxweight算法对系统的综合利用率更高.而且由于本文算 法每次都考虑多维资源综合利用率最高的配置,经过多次调用之后,利用率会增加得更加明显 4仿真实验 为了验证本文调度算法的优势,本文通过 Clouds1仿真实验平台进行仿真实验对比,考虑模拟异构 环境,并为了控制单一变量与 Myopic Weight算法作对比,本文的实验环境与文献(13]一致,PM配置如表 3所示 VM类型如表1所示,共有3种类型为了任务大小存在变化(即任务所需求的时间片t有变化),参考 文献[13,本文设定任务的大小如下分布:当新任务生成时首先按照入=(1,3,吉的概率产生三种任务 170 系统工程理论与实践 第34卷 (CPU密集,MEM密集标准),然后,按照0.7的概率,任务统一分布在[1,50区间;0.15的概率,任务统 分布在[250,300区间;最后0.15的概率,任务统一分布在A451,500区间因此,平均任务大小为130.5,最 大任务为500接着,进步假设任务在每个时间片开始时到达的概率满足二项分布(a105,100),c从 05逐渐变化到3,负载强度随着α而变大.每次仿真时间为50000个时间片 本文将MIUS与 Myopic Maxweight算法以及2种比较典型的调度算法:随机调度( Random)和轮询 调度(Pol)算法纳入实验,从三个方面对比4种算法的优劣:实验1,比较4种算法在不同工作负载下的仟 务平均等待时延,从而了解4种算法对QoS的影响;实验2.比较4种算法在不同工作负载下系统的综合利 用率,从而比较4种算法对多维资源的利用情况;实验3.比较4种算法在不同工作负载下的不平衡度(利用 文献111-不平衡度公式),从而对比4种算法对负载均衡的影响 60000.0 s Mop 表3PM配置 4500.0 类型 PMI CPU/ECU 起3000 MEM/GB 15000.0 Storage/ GB 4000 数量/台 100 0.50.550.60.650.7C.750.80.850.90.951 图1不同负载强度下的任务等待时延 实验中的超级时段T=∞,并且根据文献[13的研究表明,当α=1时,负载强度仍然处于系统的能力 范围以内,正如图1所示,系统的平均时延都有一个上限 实验1结果表明,本文提出的算法MIUS与 Myopic算法在不同负载强度下平均时延基本相同:在低强 度(0.5~0.75)下,由于产生任务少,系统可以从容地处理,两种算法都是考虑ⅤM的最大配置,所以任务完成 率相当,从而平均吋延相近;在高强度(0.75~1)下,由于任务产生速率增大,当等待任务量达到阈值,MIUS 算法会尽量处理某一类任务,而 Myopic算法从一开始就考虑了wQ的长度.在WQ激增时,能够更好地保 证低时延.所以MIUS算法的平均时延略高于 Myopic算法,但是仍然可以接受 Pll和 Random算法与α大致呈正比关系,然而Po'算法的平均时延相比其他三种算法高出很多,这 是因为Poll算法釆取的是轮询策略,每次都从第一个主机开始检测资源可用性,而其他三种算法都具有随机 的思想能够更髙效地处理请求,对于每一个主机来说,任务到达数量的增长率大致相同,因而能够更高效的 利用多维资源 实验2对比了处于不同负载强度下4种算法的系统的综合利用率,在负载较低情况(a=0.5)下,由 于任务量较少,同一时间处于运行的VM占用资源少,因此4种算法利用率均不高,而随着负载逐渐增大 (α-0.65),MIUS和 Myopic算法使得系统利用率逐渐升高.随着负载继续增大(a-9.5),当任务的到达率 与任务的完成率相似时,MIUS和 Myopic算法使得系统的利用率达到最大值,而随着任务达到率继续增大 (α=1.5)、由于采用的是基于负载均衠的路由算法,所以对于单一PM,任务量不会一直增加,会有一段缓冲 时间,等到任务负载再次增大时(a=30),系统的利用会明显卜降.对比不同负载卜的利用率可知,MUS 算法可较明显提高系统利用率 0.75JU 0. 2500 0.0000 0. MIUS Myopic D Random Poll Rendon 图2不同负载强度下的系统综合利用率 图3不同负载强度下的系统不平衡度 Random和Po算法对a的变化几乎没有受到影响,但Poll算法利用率最低这与实验1的结果相符 实验3表明,4种算法的不平衡度都非常低(<0.04),但Rand和Pol算法实现了更好的负载均衡,从 增刊 肖逸飞,等:基于随机模型的动态调度算法研究 171 实验数据上分析,这是因为这两种算法的CPU利用率以及mem利用率都不高(如图2),导致综合利用率较 低,三者进行求差平方(不平衡度计算)的结果也较低 5结束语 本文从保证QoS和负载均衡的角度出发,以最大化地利用多维资源为目标,进行VM放置.通过研究 前人的调度算法以及对利用率最大化问题的分析提岀在基于随机模型下最大化利用多维资源的策略,并通 过改进 Myopic Maxweight算法实现了本文的调度算法MIUS.本文不仅从理论上分析了MIUS相比 Myopic会产生更高的综合利用率,同时通过仿真实验,验证了本文算法相比于 Myopic Maxweight,随机调 度算法和轮洵调度算法是有优势的 在未来的工作中,本文将在PM异构的环境下进行实验,探究本文算法在PM异构环境下对任务调度的 影响、并通过实验验证设置的阈值对算法的影响,并找出最佳的阈值.为了进一步测试算法的实际可用性,算 法将会被使用在诸如XEN等虚拟化技术的真实云计算环境中 参考文献 1 Mell P, Grance T. The nist definition of cloud computing R National Institute of Standards and Technology, 2011 2 Gulati A, Holler A, Ji M, et al. VMware distributed resource management: Design, implementation and lessons learned J. VMware Technical Journal, 2012, 1(1):15-64 3Ec2.http://aws.amazoncom/ec2 4appenginE.http://code.googlecom/appengine/ 5Azure.http://www.microsoft.comwindowsazure/ 6 Nguyen Van H, Dang Tran F, Menaud J M. Autonomic virtual resource management for service hosting plat- forins(Cl// Proceedings of the 2009 ICSE Workshop onl Software Engineering Challenges of Cloud CoInputing IEEE Computer Society, 2009: 1-8 7 Menascc D, Bennani N. Autonomic virtualized environments[C//2006 International Confcrcncc on Autonomic and Autonomous Systems, 2006. IEEE, 200G: 28 8 Carrera D, Steinder M, Whalley I et al. Enabling resource sharing between transactional and batch workloads Ising dynamic application placement C// Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware. Springer-Verlag New York, Inc, 2008: 203-222 9 Karve A, Kimbrel T, Pacifici G, et al. Dynamic placement for clustered web applications[cl// Proceedings of the 15th International Conference on World wide web. ACm. 2006: 595-604 10 Tang C, Stcindcr M, Sprcitzor M, ct al. A scalable application placement controller for cntcrprisc data con ters[Cl// Proceedings of the 16th International Conference On World Wide Web. ACM, 2007: 331-340 [I1 Tian W H, Diao Y, Zhong Y L, et aL. Dynamic and integrated load-balancing scheduling a..hm for cloud data centers. China Communications, 2011, 8(6): 117-126 12 Wang X, Xie Il, Wang R, et al. Design and implementation of adaptive resource co-allocation approaches for cloud service environments[Cl// 3rd International Conference on Advanced Computer Theory and Engineering ( ICACTE),2010:484488. 13 Maguluri S T, Srikant R, Ying L Stochastic models of load balancing and scheduling in cloud computing cl ters[Cl//INFOCOM, 2012 Proceedings IEEE IEEE, 2012: 702-710 [14 Ca.Iheiros R N, Ranjan R, Beloglazov A, et a.L. CloudSim: A toolkit for modeling and simu lation of cloud com- puting environments and evaluation of resource provisioning algorithms[J. Software: Practice and Experience 2011,41(1):23-50

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐