基于云计算的集群扩展中的调度算法研究.pdf

《基于云计算的集群扩展中的调度算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国科学技术大学硕士学位论又基于云计算的集群扩展中的调度算法研究作者姓名：学科专业：导师姓名：完成时间：葛新管理科学与工程陈华平教授二。一一年五月三十一曰UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeAuthor’SName：XinGespeciality：ManagementScienceandEngine硎ng一‘Supervisor：Prof．HuapingChenFinishedtime：May31th，2011nDg．㈣凹n甜Ⅲ嘶翟例旧帅n扎山讲Cb孙屿甜色nj鼬M划链

2、附：{：瞿训珧R蚪盼中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：葛堑签字日期：丝!f：鱼：堕中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据

3、库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。口公开口保密(——年)作者签名：葛薹丘签字日期：2望!!：笪：!兰导师签名：签字日期：摘要作业调度算法一直是集群系统中的一个非常重要的研究课题，是决定一个集群性能好坏的前提和基础。良好的调度算法可以帮助提高集群处理能力，有效地分配资源，加速作业运行。随着业务的不断发展，集群压力越来越大，企业不得不扩展其内部集群。但是传统的购入大量服务器的做法会消耗大量的资金和成本。在这样的环境下，云计算灵活的使用方式为企业集群扩展提供了新

4、的集群扩展方式，解决了企业面临的两难局面。基于研究背景的转变，集群环境的变化，传统的作业调度算法己然不能适应新的集群环境。为了顺应了企业发展的需要，我们迫切需要探索基于云计算的集群扩展中的作业调度算法。这对于企业节约成本，提高用户满意度等都具有重要意义。由于基于云计算的集群扩展中的调度算法研究刚刚起步，目前并没有详细的研究资料和参照算法。因而，本文采用逐步深入的方式设计了多种基于云计算的集群扩展中的作业调度算法。首先，提出了两种简单调度算法作为我们的参照调度算法。接着，针对这两种算法中作业分配不合理性，利用集群计算能力不同的特点，提出了一种基于计算强度的调度算法。该算法

5、提出使用集合U代替整个等待队列对作业筛选，这种方式不但减少了作业完成总时间和总成本，而且兼顾作业调度的公平性。随后，本文提出一种等体积预留回填EV-RB(EqualVolume．ReservationBackfilling)调度算法，该算法认识到基于计算强度的调度算法存在资源利用率低、超时作业数量多的问题，创造性地将BackFilling算法中的二维时空表转变成三维的方式，将原本只能在传统集群中运行的BackFilling算法成功引入到云环境扩展的集群中。同时，该算法为了解决BackFilling算法回填作业不足的缺点，使用体积变换的方式代替单一的时间比较，进一步提高了

6、资源利用率。最后，本文又提出一种改进的等体积预留回填IEV-RB(ImprovedEqualVolume．ReservationBackfilling)调度算法，该算法基于对EV-RB算法的改进，放宽了需求CPU数量不可变这一限制，进一步增加了可回填作业数量。之后，本文进行了仿真实验。设计了9类子问题，每个问题随机生成多个实例，从成本和超出时间约束的作业数量两个方面对我们所设计的算法的有效性进行了验证。实验结果与算法思想基本一致，表明算法设计合理有效。最后，对几种算法的适用性进行了分析。关键词：作业调度算法；集群扩展；云计算；BackFilling算法l摘要Abstra

7、ctABSTRACTJobschedulingalgorithmisalwaysaveryimportantresearchtopicinclustersystem，whichiSthepremiseandfoundationtodeterminetheperformanceofaclusterisgoodornot．Goodschedulingalgorithmcanhelpimprovetheclusterprocessing，allocateresourceeffectivelyandacceleratejobrunning．Wit