论文研究-基于动态优先级和萤火虫行为的云任务调度算法.pdf

所需积分/C币:10 2019-07-22 21:48:30 1.09MB .PDF
25
收藏 收藏
举报

针对云环境下优先级任务调度容易出现的负载失衡问题,提出一种基于动态优先级和萤火虫行为的云任务调度算法(TS-PFB)。该算法根据任务价值密度与执行紧迫性计算出动态优先级;模拟萤火虫行为,结合吸引度(ECT)和荧光亮度(负载约束)给出决策变量ρ;再按优先级高低依次将任务调度到最大ρ值所对应的可行VM上。实验结果表明,相比于Min-Min、Max-Min、HBB-LB算法,该算法减少了总任务的完成时间,均衡了VM的负载,降低了任务截止期错失率。
1042 计算机应用研究 笃32卷 萤火虫 寻找 恼火虫猁 WⅥ资源排序;再按优先级高低依次调度任务,计算出任务在 各W上的最早完成时间ECT,依据任务带宽需求(1≤m) 可川资游表(Ms 子:「 MiInmips memory BWFI 和内有( t. sum)的要求,建立任务与可行W组的关 06791000①1 联;在计算出ETC2和虚拟机当前的荧光亮度F的基础上,计 |m-15069009 算任务与可行WM组内各m的调度决策变量p;将任务调度 到最大ρ值所对应的虚拟机上;更新虚拟机的起始执行时间 VM sI he,与荧光亮度F,删除已调度任务;如上开始下一个任务调 /焜拟化 度的调度,直至所有任务完成。 物堆机[物堆「初-物埋机 具体算法流程如下 图1任务调度流程框图 Notations:令CT:为任务l1的可行VM纽 Procedure:nit()初始化起始执行时间和荧光亮度 3.1萤火虫算法 for( int j=0; j<m; i++) 萤火虫算法( irelly algorithIm,FA)是受自然界中的萱火 虫通过荧光进行信息交流这种群体行为的启发演变而来的随 Procedure:DP(l2)//计算仟务的动态优先级 机优化算法。算法对蛋火虫生物发光特性炇趋光行为进行∫ set DP(t: based on formula(7) 理想化处理:萤火虫不分性别,它将会被吸引到所有其他比它 ocedure:Sort(T,WM)/降序排列任务和WM 更亮的萤火虫那去;萤火虫的吸引力和亮度成正比,对于任何 Sort t by DP(Li) in descending order Sort VM by omcanacity in descending order 两只萤火虫,其中只会向着比它更亮的另只移动,然而亮 Procedure: Gelato()∥/计算FTC 度是随着距离的增加而减少的;如果没有找到一个比给定的萤 for t in sorted t 火虫更亮,它会随机移动。 for um: in sorted vM 其仿生原理是:把搜索空间屮的点模拟为萤火虫个体,将 set ETC: based on formula(1); Procedure: Schedule() 搜索和优化过程模拟成萤火虫个体的吸引和移动过程,将求解 问题的目标函数度量成个体听处位置的优劣,将个体的优胜劣 for um; in sorted vm/(计算ECTa和CT 汰过程类比为搜索和优化过程中用好的可行解取代较差可行 set ect based on formula(2) 解的迭代过程1。 if( ECT stalline&&lin sum cT 3.2模仿萤火虫行为的决策变量 for um, in Cl /计算出p开始调度 在FA算法中,萤火虫彼此吸引的原因取决于两个要素 set pi based on formula(9); assign (, to the um in CT, with the max p 即自身亮度和吸引度。而任务调度时,任务和虚拟机也是一个 update 相互吸引的过程。在该过程屮,可以将所需要考虑的期望最早 完成时间和虚拟机的负载情况分别作为吸引度和亮度,模拟萤 火虫亮度吸引的行为对任务进行调度。 5实验仿真与结果分析 吸引度( attractiveness):期望最早完成时间ECT,共值5.1实验环境 小,吸引度越大。 为了检验 TS-PFB算法的性能,本文在 Cloudsim仿真平台 荧光亮度( uurescenIce intensity,F):初始时刻,每个虚拟 上进行了仿真实验。仿真开始时,用户的任务提交给代理后, 机亮度最亮,值为1,虚拟机负绂增加吋,亮度降低,以每个虚 代理依据在信息服务中心(CS)获取的注册的数据中心信息 拟机上负载的期望处理吋间(FPT)与初值1的和来作为萤火 开始了如图2所示的一系列仿真步骤。 虫的荧光亮度。 若分配给虚拟机m:的任务的总长度称为负载,记为L 数据中 CS注册数中心代理 则EPT7 用数据中心 eiFac 获取数据中心特征 m;的荧光亮度计算公式如式(8)所示。 创建虚拟机 任务调度 Fl=l+EPI 最后综合考虑吸引度和荧光亮度的决策变量p,如式(9) 销毁虚拟机 所示 图2 CloudSim仿真流程 Py ECT; FIj 在仿真实验中,模拟」50~450个独立任务在20个WM 资源上的调度,每个虛拟机含有一台处理器,处理能力范围为 显然,ECI和Ⅳ越小时,P越大。将任务t:调度到可行 [500,1000,存储能力范围为[1000,2000,带宽范围为[10 虚拟机组中最大P,值所对应的m上即可。 20],WM到hst的分配山 Cloudsim自带的 Time Shared算法实 4Ts-PFB算法描述 现。任务长度区间为[10000,400001,存储能力需求范围为 [800,1800,带宽需求范围为[8,15],截上时间范围为[50. 云计算中TSPB算法执行步骤如下:首先计算出所有任800],优先级权重囚子设置为ω1=ω2=0.5。实验运行在 务的优先级,依据任务的优先级和资源的性能,分别对任务和AMDX22152.7GHz,2.00GB的PC机上。 第4期 刘亚秋,等:基于动态优先级和萤火虫行为的云任务调度算法 1043 5.2结果分析 到调度。 在相同的测试糸件和坏境下,本文分别实现了Min-Min Max-Min、 HBB-LB和 TS-PFB算法,并在各类算法总任务平均6结束语 完成时间 Makespan、负载均衡程度和截止期内成功完成的任 本文提出了一种云计算环境下基于动态优先级和萤火虫 务率上进行了对比测试 行为的任务调度算法。实验结果表明,该算法能够有效地减小 实验1总任务平均完成时间 Makespan测试 总任务的完成时间,具有较好的负载均衡性,也能够保证大部 图3描述了以上四种算法在多组不同数日任务量下平均分任务在任务的截止期内完成。以后的工作中将进一步考虑 完成时间 Makespan的对比从图中可以看出,在不同任务量用户安全方面QS需求和更为复杂的任务的调度等问题。 下, TS-PFB算法的平均Men略优于 Max-Min算法,略长参考文献 于HR算法(HRB算法的半均 Makespan没有考虑任务[1wFsA. Compuling in the cIouds. NetWorker,07,114): 实际调度过程中仁务迁栘的时耗),这说明1S-PHB算法能够 6-25 有效地减小总任务的完成时间 [2 MISHRA A, JAIN R, DURRESI A Cloud computing net working and 实验2负载均衡程度测试 communication challenges[ J. IEEE Communications Magazine 令分配给虚拟机m的任务的总长度称为负载,记为L。 2012,50(9):24-2 虚拟机m上载有任务的期望处理时间EP1=。所有 [3 GHANBARI S, OTHMAN M. A priority based job scheduling algori- thm in cloud computing J 1. Procedia Engineering, 2012, 50: 778 虚拟机的期準处理时间的平均值为E=1EPT。本文用[41 GU L,Nm, XIE Guo-qi. The implementation of M 期望处理时间的标准差来判断虚拟机群的负载均衡程度.如式 Reduce scheduling algorithm based on priority[ C]//Proc of Parallel (10)所示。 Computational Fluid Dynamics. Berlin: Springer, 2014: 100-111 [5 LIU Gang, LI Jing, XU Jian-chao. An improved Min-Min algorithm in EPT,-EPT) (10) loud comp uting[ C]//Prmc of International Conferenre of Morern 依据式(10)计算出四种算法的半均负载均衡程度测试结 Computer Science and Applications. Berlin: Springer, 2013: 47-52. [6 LI Qi, BA Wei. A group priority earliest deadline first scheduling algo 果,如图4所示。从图4中可以看出,在四种算法中,Min-Min thm J. Frontiers of Computer Science, 2012, 6(5): 560-567 算法则出现了严重的负载失衡;动杰负载均衡算法 HBB-LB设[71夏家莉,陈糕,扬兵.一神动态优先级实时任务调度箅法J].计算 定阈值为30,可见触动负载均衡策略,之后σ值趋于平稳;而 机学报,2012,35(12):2685-2695 TS-PFB算法调度完后的WM负载均程度σ最低,这是因为81 MISHRA M,DASA, KULKARNI P,ta. Dynamic resource manage 在任务调度时考虑了MM的负载约束(荧光亮度)。该实验结 ment using virtual machine migrations[ J. IEEE Communications 果说明TS-PFB算法具有很好的负载均衡特性。 Magazine,2012,50(9):34-4 FO-HBB-LE [9 REN Xiao-na, lin Rong-heng, ZOU Hua. A dynamic load balancing strategy for cloud computing platform based on exponential smoothing P -tNPK forecast[ C]//Proc of IEEE International Conference on Cloud Com puling and Intelligence Syslems. Pisc alaway: IEF.F. Press, 2011: 220- 瑶40 [10] HU Jin-hua, GU Jian-hua, SUN Guo-fei, et al. A scheduling strategy 01001502002503003504045 5010015020025030350400450 on load balancing of virtual machine resourees in cloud computing en- 仟务数 仟务数 ronment[C]//Proc of the 3rd International Symposium on Parallel 图3总任务平均完成时间 图4平均负载均衡程度 Architectures, Algorithms and Programming. Piscataway: IEEE Press 实验3截止期内任务完成的成功率 2010:8996. 令截止期内成功完成的任务数量比上总任务的数量为成[1 I BABU I DD, KIRSHNA P V. Honey hee behavior inspired load ba 功率。四类算法的平均成功率测试结果如图5所示。 lancing of tasks in cloud computing environments[ J]. Applied Soft Computing,2013,13(5):2292-2303 三 M rr Min 12 LI Kun, XU Gao-chao, ZHAO Guang-yu, et al. Cloud task scheduling based on load balancing ant colony optimization[ C]//Proc of the 6th Annual Chinagrid Conference. [S1.]: IE EF. Press, 2011: 3-9 [13 MAO Ying-chi, CHEN Xi, LI Xie Max-Min task scheduling algorithm 0.8 for load balance in cloud computing[ C//Proc of International Con ference on Computer Science and Information Technology..S 1.] ,2014:457-465 14 CHEN Huan-kai, WANG F, HELIAN N, et al. User-priority guided Min-Min scheduling algorithm for load balancing in cloud computing 图5平均成功率 [C]//Proe of National Conference on Parallel CompIling Technolo 从图5中可以看出,TS-PFB算法截止期内任务完成的平 gies. Piscataway: IEEE Press, 2013: 1-8 均成功率最高,即截止期内锆失率最小,这是因为任务优先级[15 YANG Xin-she. Firefly algorithn[CJ// Proc of Engineering Optimiza 构建是考虑了任务执行的紧迫性,使得截止期短的任务优先得 tion.2010:221-23

...展开详情
试读 4P 论文研究-基于动态优先级和萤火虫行为的云任务调度算法.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于动态优先级和萤火虫行为的云任务调度算法.pdf 10积分/C币 立即下载
1/4
论文研究-基于动态优先级和萤火虫行为的云任务调度算法.pdf第1页

试读结束, 可继续读1页

10积分/C币 立即下载