第31卷第1期
2011年1月
文章编号:1001-9081(2011)01-0184-03
计算机应用
JournalofComputerApplications
Vo.l31No.1
Jan.2011
do:i10.3724/SP.J.1087.2011.00184
云计算环境下基于改进遗传算法的任务调度算法
李建锋,彭 舰
(四川大学计算机学院,成都610065)
(jianpeng@scu.edu.cn)
摘 要:在云计算中面对的用户群是庞大的,要处理的任务量与数据量也是十分巨大的。如何对任务进行高效
的调度成为云计算中所要解决的重要问题。针对云计算的编程模型框架,提出了一种具有双适应度的遗传算法(DFGA),通过此算法不但能找到总任务完成时间较短的调度结果,而且此调度结果的任务平均完成时间也较短。通过仿真实验将此算法与自适应遗传算法(AGA)进行比较,实验结果表明,此算法优于自适应遗传算法,是一种云计算环境下有效的任务调度算法。
关键词:云计算;遗传算法;双适应度;任务调度
中图分类号:TP393 文献标志码:A
Taskschedulingalgorithmbasedonimprovedgeneticalgorithmincloudcomputingenvironment
LIJian feng,PENGJian
(CollegeofComputerScience,SichuanUniversity,ChengduSichuan610065,China)
Abstract:Thenumberofusersishugeincloudcomputing,andthenumberoftasksandtheamountofdataarealso
huge.Howtoscheduletasksefficientlyisanmiportantissuetoberesolvedincloudcomputingenvironment.ADouble FitnessGeneticAlgorithm(DFGA)wasbroughtupfortheprogrammingframeworkofcloudcomputing.Throughthisalgorithm,thebettertaskschedulingnotonlyshortenstotal task completiontimeandalsohasshorteraverage completiontime.ThereisacontrastbetweenDFGAandAdaptiveGeneticAlgorithm(AGA)throughsimulationexperiment,andtheresultis:theDFGAisbetter,itisanefficienttaskschedulingalgorithmincloudcomputingenvironment.
Keywords:cloudcomputing;GeneticAlgorithm(GA);double fitness;taskscheduling
0 引言
近几年云计算[1-2]成为了人们讨论的热点。目前IBM、Google、Amazon、Microsoft等纷纷涉足云计算,提供了众多基于云计算的服务,如Gmail、GoogleEarth、GoogleAnalytics、Google搜索、Google文档[3];Amazon的弹性云计算(EC2)服务和存储服务(S3);Microsoft的WindowsLiveWeb应用套件及Hotmail等[4]。
云计算是并行计算、网格计算[5-6]的发展,是分布式计算的一种,其最基本的思想是透过网络将庞大的计算处理程序自动分拆成无数个较小的子程序,再交由多部服务器所组成的庞大系统,经搜寻、计算分析之后将处理结果回传给用户,提供这些资源的网络被称为 云 。云计算所提供的服务面向的用户群是庞大的,因此 云 中的任务数量是巨大的,系统每时每刻都要处理海量的任务,所以任务调度[7]是云计算中的重点与难点。本文对如何充分利用 云 中的资源使其中的任务进行高效合理的调度进行了研究,提出了一种基于双适应度遗传算法(Double FitnessGeneticAlgorithm,DFGA)的任务调度算法,并通过了仿真实验,验证了其良好的性能。
中采用的编程模型,都是采用基于Map/Reduce的思想开发的编程工具,它特别适用于产生和处理大规模的数据集。其执行过程如图1所示。
图1 Map/Reduce的具体执行过程
从图1可以看出,Map/Reduce有6个过程,可分为两个主要阶段。
Map阶段 把一个较大的任务通过Map/Reduce函数分割为M个较小的子任务,然后配给多个worker(被分配为执行Map操作的worker)并行执行,输出处理后的中间文件;
1 云计算中的编程模型
目前的云计算环境中大部分采用Google提出的Map/Reduce的编程模式[8],大部分信息技术厂商提出的 云 计划
收稿日期:2010-07-15;修回日期:2010-09-06。 基金项目:四川省科技支撑计划项目(06KJT 013;2009GZ0153)。 作者简介:李建锋(1987-),男,河南项城人,硕士研究生,主要研究方向:网格计算、云计算; 彭舰(1970-),男,四川成都人,教授,博士,

云 计算 环境 下基 于 改进 遗传 算法 的任 务调度算法 李建锋 ,彭舰 (川 大学 计算机学院,都606)四成105 (ipn@SUeuo)jnegC.d.na 摘 要: 在云计算 ...
00184 云计算环境下基于改进遗传算法的任务调度算法李建锋, 彭舰 ( 四川大学 计算机学院 , 成都 610065 ) ( jianpeng@ scu. edu . cn ) 摘要 : 在云计算中...
第 1期 李建锋等: 云计算 环境下基于改进遗传算法的任务调度算法 185 R educe阶段 将 M ap 阶段处 理后的 结果进行 汇总分 析 处理, 输出最后的结果: R ...
云计算环境下基于改进遗传算法的任务调度算法 云计算 遗传算法 任务调度云计算 遗传算法 任务调度隐藏>> 分享到: X 分享到: 使用一键分享,轻松赚取财富值, ...
云计算环境下基于遗传蚁群算法的任务调度研究_数学_自然科学_专业资料。ComputerEngineering andApplications 计算 机 工程 与应用 2014,50( ...
3.3. 云中任务调度的具体步骤在云计算环境中, 在采用基于 “分裂” 思想的 ... 采用了 CloudSim[8]做模拟,并将其与标准 PSO 算法、 遗传算法和蚁群算法进行...
云环境下基于改进遗传算法的虚拟机调度策略_互联网_IT/计算机_专业资料 暂无评价
聚类环境下的密集型任务〔〕. 第4期 刘 愉等:云计算环境中优化遗传算法的...了基于最优 跨度和负载均衡准则改进遗传算法的资源调度算法 . 由于云计算环境 ...
云计算环境下基于改进遗传... 3页 1财富值喜欢此文档的还喜欢 遗传算法及其...快速有效的任务分配和调度是分布式 系统中一个关键的问题, 其实质是将任务合理和...
基于改进免疫遗传算法的网格任务调度_信息与通信_工程科技_专业资料。第3 0卷... 遗传算法在网格任务调度... 12人阅读 4页 2.00 网格环境下独立任务调度...
热门文档