硕士学位论文-基于云计算的集群扩展中的调度算法研究.pdf

中国科学技术大学 硕士学位论又 基于云计算的集群扩展 中的调度算法研究 作者姓名： 学科专业： 导师姓名： 完成时间： 葛新 管理科学与工程 陈华平教授 二。一一年五月三十一曰 U n i v e r s i t yo fS c i e n c ea n d T e c h n o l o g yo fC h i n a Ad i s s e r t a t i o nf o rm a s t e r Sd e g r e e A u t h o r SN ame：XinG e s p e c i a l i t y ： M a n a g e m e n tS c i e n c ea n dE n g i n e 硎n g 一 S u p e r v i s o r ：P r o f H u a p i n g C h e n F i n i s h e dt i m e ： M a y31 t h ，2 0 11 nD g 凹 n 甜 嘶翟 例旧帅 n 扎山 讲C b 孙屿甜 色n j鼬M 划链附： ：瞿训珧R蚪盼 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：葛堑 签字日期：丝! f ：鱼：堕 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口公开口保密( 年) 作者签名： 葛薹丘 签字日期：2 望! ! ：笪：! 兰 导师签名： 签字日期： 摘要 摘要 作业调度算法一直是集群系统中的一个非常重要的研究课题，是决定一个集 群性能好坏的前提和基础。良好的调度算法可以帮助提高集群处理能力，有效地 分配资源，加速作业运行。 随着业务的不断发展，集群压力越来越大，企业不得不扩展其内部集群。但 是传统的购入大量服务器的做法会消耗大量的资金和成本。在这样的环境下，云 计算灵活的使用方式为企业集群扩展提供了新的集群扩展方式，解决了企业面临 的两难局面。基于研究背景的转变，集群环境的变化，传统的作业调度算法己然 不能适应新的集群环境。为了顺应了企业发展的需要，我们迫切需要探索基于云 计算的集群扩展中的作业调度算法。这对于企业节约成本，提高用户满意度等都 具有重要意义。 由于基于云计算的集群扩展中的调度算法研究刚刚起步，目前并没有详细的 研究资料和参照算法。因而，本文采用逐步深入的方式设计了多种基于云计算的 集群扩展中的作业调度算法。首先，提出了两种简单调度算法作为我们的参照调 度算法。接着，针对这两种算法中作业分配不合理性，利用集群计算能力不同的 特点，提出了一种基于计算强度的调度算法。该算法提出使用集合U 代替整个 等待队列对作业筛选，这种方式不但减少了作业完成总时间和总成本，而且兼顾 作业调度的公平性。随后，本文提出一种等体积预留回填E V - R B ( E q u a l V o l u m e R e s e r v a t i o nB a c k f i l l i n g ) 调度算法，该算法认识到基于计算强度的调度算 法存在资源利用率低、超时作业数量多的问题，创造性地将B a c k F i l l i n g 算法中 的二维时空表转变成三维的方式，将原本只能在传统集群中运行的B a c k F i l l i n g 算法成功引入到云环境扩展的集群中。同时，该算法为了解决B a c k F i l l i n g 算法 回填作业不足的缺点，使用体积变换的方式代替单一的时间比较，进一步提高了 资源利用率。最后，本文又提出一种改进的等体积预留回填I E V - R B ( I m p r o v e d E q u a lV o l u m e R e s e r v a t i o nB a c k f i l l i n g ) 调度算法，该算法基于对E V - R B 算法的改 进，放宽了需求C P U 数量不可变这一限制，进一步增加了可回填作业数量。 之后，本文进行了仿真实验。设计了9 类子问题，每个问题随机生成多个实 例，从成本和超出时间约束的作业数量两个方面对我们所设计的算法的有效性进 行了验证。实验结果与算法思想基本一致，表明算法设计合理有效。最后，对几 种算法的适用性进行了分析。 关键词：作业调度算法；集群扩展；云计算；B a c k F i l l i n g 算法 l 摘要 A b s t r a c t A B S T R A C T J o bs c h e d u l i n ga l g o r i t h mi sa l w a y sav e r yi m p o r t a n tr e s e a r c ht o p i ci nc l u s t e r s y s t e m ，w h i c hi St h ep r e m i s ea n df o u n d a t i o nt od e t e r m i n et h ep e r f o r m a n c eo fac l u s t e r i sg o o do rn o t G o o ds c h e d u l i n ga l g o r i t h mc a nh e l pi m p r o v et h ec l u s t e rp r o c e s s i n g ， a l l o c a t er e s o u r c ee f f e c t i v e l ya n da c c e l e r a t ej o br u n n i n g W i t ht h ec o n t i n u o u sd e v e l o p m e n to fb u s i n e s s ，t h e r ei Sm o r ea n dm o r ep r e s s u r e o nc l u s t e r , e n t e r p r i s e sh a v et oe x p a n dt h e i ri n t e r n a lc l u s t e r s B u tt h et r a d i t i o n a l p r a c t i c eo fp u r c h a s i n gl a r g en u m b e ro fs e r v e r sw i l lc o n s u m eh u g ea m o u n to fm o n e y a n dc o s t I ns u c ha ne n v i r o n m e n t ，c l o u dc o m p u t i n gp r o v i d e san e ww a yf o rt h e e n t e r p r i s ec l u s t e re x p a n s i o ni naf l e x i b l eu s em a n n e r , s o l v e st h ep r o b l e mw h i c h e n t e r p r i s ef a c e d O w i n g t ot h e c h a n g eo fr e s e a r c hb a c k g r o u n da n dc l u s t e r e n v i r o n m e n t ，t h et r a d i t i o n a lj o bs c h e d u l i n ga l g o r i t h mc a nn o ta d a p tt ot h en e wc l u s t e r e n v i r o n m e n ta l r e a d y I no r d e rt oa c c o m m o d a t et h en e e do fe n t e r p r i s ed e v e l o p m e n t ， w e u r g e n t l yn e e dt oe x p l o r et h ej o bs c h e d u l i n ga l g o r i t h mo fc l u s t e re x p a n s i o nb a s e d o nc l o u de n v i r o n m e n t ，w h i c hh a v ea ni m p o r t a n ts i g n i f i c a n c ef o re n t e r p r i s e st os a v e c o s t s ，i m p r o v ec u s t o m e rs a t i s f a c t i o na n dS Oo n A st h er e s e a r c ho nj o bs c h e d u l i n ga l g o r i t h mo fc l u s t e re x p a n s i o nb a s e do nc l o u d e n v i r o n m e n th a sj u s ts t a r t e d ，t h e r ei Sn od e t a i l e dr e s e a r c hd a t aa n dr e f e r e n c em e t h o d S ot h i sp a p e rd e s i g n e dv a r i e t i e so fj o bs c h e d u l i n ga l g o r i t h m so fc l u s t e re x p a n s i o n b a s e do nc l o u de n v i r o n m e n tb yt h ew a yo fg r a d u a ld e e p e n i n g F i r s t ，w ep r o p o s et w o s i m p l es c h e d u l i n ga l g o r i t h m sa s0 1 1 1 “ r e f e r e n c e T h e n ，w ef o c u so nt h eI r r a t i o n a l i t yo f t h et w oa l g o r i t h m s ，t a k ea d v a n t a g eo ft h ef e a t u r e so fd i f f e r e n tc o m p u t i n gp o w e ri n t w oc l u s t e r s 。d e s i g na s c h e d u l i n ga l g o r i t h mb a s e do nc a l c u l a t i o n T h ea l g o r i t h mu s e sa s e tUi n s t e a do ft h ee n t i r eq u e u et os o r tj o b s ，w h i c hn o to n l yC a nr e d u c et h et o t a l o p e r a t i n gt i m ea n dc o s t ，b u ta l s oc o n s i d e rt h ef a i r n e s so f j o bs c h e d u l i n g S u b s e q u e n t l y , t h i sp a p e rp r e s e n t sa nE V - R B ( E q u a lV o l u m e - R e s e r v a t i o n B a c k f i l l i n g ) s c h e d u l i n g a l g o r i t h m ，w h i c hr e c o g n i z e st h el o wr e s o u r c eu t i l i z a t i o na n dt h el a r g eq u a n t i t yo f o v e r d u et a s k si ns c h e d u l i n ga l g o r i t h mb a s e do nc a l c u l a t i o n ，c r e a t i v e l yt r a n s f o r m st h e t w o - d i m e n s i o n a l s p a c et a b l e o fB a c k F i l l i n ga l g o r i t h mi n t ot h et h r e e d i m e n s i o n a l s p a c et a b l ea n ds u c c e s s f u l l yi n t r o d u c e st h eB a c k F i l l i n ga l g o r i t h mo n l yr u ni nt h e t r a d i t i o n a lc l u s t e ro r i g i n a l l yt oc l u s t e re x p a n s i o nb a s e do nc l o u de n v i r o n m e n t M e a n w h i l e ，i no r d e rt os o l v et h es h o r t c o m i n go ft h ei o bc o u l d n tb eb a c k f i l l e di n B a c k F i l l i n ga l g o r i t h m ，t h en e wa l g o r i t h mu s e st h ew a yo ft r a n s f o r m i n gv o l u m e i n s t e a do ft h ew a y o n l yc o m p a r e dt h r o u g ht i m e ，f u r t h e ri m p r o v er e s o u r c eu t i l i z a t i o n F i n a l l y , w e a l s o p r o p o s e d a n I E V - R B ( I m p r o v e dE q u a l V o l u m e R e s e r v a t i o n B a c k f i l l i n g ) s c h e d u l i n ga l g o r i t h m ，w h i c hi sb a s e do nt h ei m p r o v e m e n to fE V - R B a l g o r i t h m ，r e l a x e st h er e s t r i c t i o no fn e e d e dC P U n u m b e rw h i c hc a nn o tb ec h a n g e d ， f u r t h e ri n c r e a s e st h en u m b e ro f j o b sw h i c hC a nb eb a c k f i l l e d A R e n v a r d s w ec o n d u c ts i m u l a t i v ee x p e r i m e n t s D e s i g n9k i n d so fs u b 。p r o b l e m s ， m u l t i p l e i n s t a n c e sa r eg e n e r a t e d f o re a c hp r o b l e mr a n d o m l y , w ev e r i f y t h e e f f e c t i v e n e s so ft h ea l g o r i t h mf r o mt w oa s p e c t s ：c o s ta n dt h ej o bn u m b e r so v e r d e a d l i n e T h er e s u l to fe x p e r i m e n tb a s i c a l l yc o n s i s t e n tw i t ht h ei d e ao ft h ea l g o r i t h m ， w h i c hs h o wt h a tt h ea l g o r i t h md e s i g n i sr a t i o n a la n de f f i c i e n t F i n a l l y , t h e a p p l i c a b i l i t yo fs e v e r a la l g o r i t h m si sa n a l y z e d K e yW o r d s ：J o b s c h e d u l i n ga l g o r i t h m ；c l u s t e re x p a n s i o n ；c l o u dc o m p u t i n g ； B a c k F i l l i n ga l g o r i t h m 目录 目录 摘要I A B S T R A C T I I I 第1 章绪论1 1 1引言1 1 1 1 作业调度及作业调度算法1 1 1 2 论文研究背景及意义2 1 2 国内外相关研究3 1 2 1 作业调度算法相关研究3 1 2 2 云计算相关研究4 1 3 论文主要工作4 1 4 论文组织结构5 第2 章云计算技术与作业调度算法概述7 2 1云计算相关内容简介。7 2 1 1 云计算发展历程一7 2 1 2 云计算的定义和特点8 2 1 3 云计算主要技术1 l 2 1 4 云计算主要产品1 l 2 2 作业调度算法介绍l3 2 2 1 作业调度概念1 3 2 2 2 作业调度过程1 4 2 2 3 作业调度算法的设计原则1 5 2 2 4 传统的作业调度算法介绍1 5 2 2 5 B a c k F i l l i n g 作业调度算法介绍1 6 2 3 本章小结1 9 第3 章基于云计算的集群扩展中的调度算法设计2 l V 目录 3 1问题描述2 1 3 2 研究思路2 2 3 3 简单的调度算法2 3 3 3 1简单的调度算法研究背景2 3 3 3 2 本地优先算法2 3 3 3 3 云环境优先算法2 4 3 3 4 简单调度算法的特点与意义2 4 3 4 基于计算强度的调度算法设计2 4 3 4 1基于计算强度的调度算法研究背景2 4 3 4 2 基于计算强度的调度算法坡计目标2 5 3 4 3 基于计算强度的调度算法主要思想2 5 3 4 4 基于计算强度的调度算法流程2 6 3 4 5 基于计算强度的调度算法的特点与意义2 9 3 5E V - R B 调度算法设计2 9 3 5 1 E V - R B 算法研究背景一2 9 3 5 2E V - R B 算法设计目标3 0 3 5 3 E V - R B 算法主要思想3 0 3 5 4 E V - R B 算法流程一3 3 3 5 5E V - R B 算法特点与意义3 7 3 6I E V - R B 调度算法设计3 7 3 6 1I E V - R B 算法研究背景3 7 3 6 2I E V - R B 算法设计目标。3 7 3 6 3 I E V - R B 算法主要思想3 7 3 6 4I E V - R B 算法流程3 9 3 6 5I E V - R B 算法特点与意义4 1 3 7 算法回顾与比较4 l 3 8 本章小结4 3 第4 章实验与结论4 5 4 1 实验环境设计4 5 4 2 实验参数设置4 7 4 3实验结果分析4 8 目录 4 3 1 算法有效性分析4 8 4 3 2 算法适川性分析5 2 4 4本章小结5 3 第5 章总结与展望5 5 5 1工作总结5 5 5 2 展望5 5 参考文献5 7 致谢6l 在读期间发表的学术论文与取得的其他研究成果6 3 V I l 目录 V I I I 第一章绪论 第一章绪论 一个合理的作业调度算法在集群的管理和运行中有着重要的地位，是集群管 理系统是否有效的关键，关系着企业集群的稳定性和健壮性，进而影响到企业的 成本和竞争力，因而是一个值得深入研究和讨论的问题。然而随着云计算技术的 兴起，传统的作业调度算法已经不能适应云环境下的集群扩展。基于云计算的集 群扩展免去了放置服务器的场地费用和维护服务器的费用，而且由于可以随时随 地方便的使用避免了需求较低时闲置服务器资源的浪费，比起传统的企业集群扩 展方式有着更大的优势。因此，对于基于云计算集群扩展中的作业调度算法研究 是当前迫切需要解决的问题。 本章简要介绍了作业调度及作业调度算法、论文研究背景及意义，国内外相 关研究，以及论文的主要工作，最后简述了论文的组织结构。 1 1引言 1 1 1 作业调度及作业调度算法 作业调度是指集群利用作业自身包含的属性和信息，从作业后备队列中选择 一部分作业投入运行并决定如何完成这些作业。在作业调度问题中，主要有两个 实体：集群和作业。集群中包含多个计算结点，为作业运行提供计算资源，一般 认为系统的计算结点性能是相同的。作业的属性根据不同的研究内容会有所不 同，一般情况包括：1 作业长度，作业长度的大小决定了作业的运行时间。2 作 业需求的结点数量，指作业运行时需求的结点数量。作业在调度前先在等待队列 中，按照一定规则排序并往集群中调度。作业在系统中运行必须满足作业需求的 结点数量小于等于集群当前空闲结点数，若不满足则无法进行调度，作业继续在 等待队列中等待。作为集群管理系统的核心功能，作业调度期望通过充分有效的 利用系统中的资源达到缩短生产周期，降低生产成本，提高Q o S 的目标。 作业调度算法是为作业分配资源的方法，是作业调度的关键。它可以依照不 同用户的需求，动态的调度分配集群内的各种有价值的资源。在运行过程中，作 业调度算法根据用户提交的作业请求，利用相应的调度规则，为作业分配合适的 资源，保证集群系统的计算能力得到充分有效的利用，使得作业能够运行并且快 速高效率的得到计算结果。 因此，作业调度算法性能的合理与否直接影响集群的服务质量，关系着系统 第一章绪论 资源利用的有效性、网络负载的平衡以及系统的整体性能状况。探寻合理有效的 作业调度算法实现系统资源的有效利用对于降低企业生产时间和成本，提高用户 满意度等方面有着重要的意义。 1 1 2 论文研究背景及意义 当前的作业调度算法一般是在传统的集群环境中研究的。随着企业内部信息 的膨胀和外部需求的增加，许多公司的I T 设施已经显得力不从心，特别是对I T 技术依赖较强的公司，很有可能因此而失去大量的客户。为了满足服务的需要， 以往唯一的做法就是增加I T 设施的投入，购买大量的服务器，扩大公司内部集 群，以提高处理信息的能力。但是这样做的弊端是显而易见的，购买新的服务器 需要大量资金，同时需要为新增的服务器租用场地安放，每年还要为管理服务器 投入大量预算，这些都大大的增加了公司的经济负担。对于需求峰值与J 下常水平 相差很大的企业，为了满足峰值时对计算资源的需求，企业必须大量购买服务器 扩大自己的内部集群，而在正常水平时，这些服务器得不到充分利用造成闲置， 这种使用巨额资金投入满足偶尔出现的峰值的需求，实属得不偿失；但如果不投 入资金扩大内部需求，一旦需求超过企业集群所能承载的能力的时候，大量客户 将因得不到服务而逐渐流失，这种流失会持续进行，直到新的峰值等于企业集群 所能提供的计算能力为止，这种情况严重影响了企业的竞争能力，阻碍了企业的 正常发展。由此可见，对于是否扩展集群企业经常陷入两难的境地。 近年来，云计算技术的兴起，为公司集群扩展提供了一种新的选择。云计算 是一种新的计算模式，它的出现将极大的改变人们使用计算机和网络的方式。云 计算可以使客户根据自己的需求定制构建在物理机上的虚拟环境【l 】。使用云计 算，人们不再需要购买昂贵的个人计算机，企业不需要搭建复杂的服务器，只要 连接上互联网，就可以得到无穷的、价格低廉的计算资源【2 】。在这种观点的指引 下，众多国际公司都开始研发各种云计算平台和相关服务。例如，A m a z o n 的E C 2 产品【3 】、G o o g l e 的a p pe n g i n e 产品【4 1 、M i c r o s o f t 的A z u r e 产品【5 】等都在不同层次 对云进行了抽象，提供了不同的云服务。但都是以一种p a y - a s y o u g o 的方式为 用户提供资源。 由于云计算拥有按需分配和规模经济的特点，非常适合用来扩展企业的集 群。在需求平稳的时候，使用企业内部的集群处理，而在需求负荷较大的时候， 使用云服务扩展本地集群。这样，不但节省了购买服务器的大量的开支，免去了 放置服务器的场地费用和维护服务器的费用，而且避免了需求较低时闲置服务器 资源的浪费。因此，可以看到，企业逐渐开始从使用传统的手段扩展内部集群向 使用云计算的方式扩展内部集群转变。使用云计算扩展集群是现代企业集群扩展 2 第一章绪论 的必然趋势。 由于研究背景的逐渐转变，集群环境产生的复杂变化，传统环境下的作业调 度算法已无法在云计算扩展的集群环境中正常使用，即使通过简单修改使其可以 在新环境中使用，也可能无法达至U 预期的效果。这主要体现在以下几个方面： ( 1 )云计算资源不能合理利用。传统作业调度算法研究背景是单一集群 环境，其中的小作业优先、作业回填等技术可以有效的提高传统集群的资源利用 率。而在云计算扩展的集群环境中，传统作业调度算法无法有效的利用云计算资 源，从而造成云计算资源的利用率较低，甚至无法利用。 ( 2 )集群运行成本提高。传统作业调度算法不能识别两种集群的特点， 不能够根据作业的不同属性将作业调度到不同集群中运行。这种情况会导致作业 分配的不合理性，从而增加作业的总运行时间和成本。 ( 3 )调度的公平性无法得到保证。多种传统作业调度算法在传统集群的 背景下提出了很多保证调度公平性的方法，例如，资源预留、设置优先级等方法， 但这些方法不能够直接运用在云计算扩展的集群环境中。 综合以上所述，一方面，需要使用云计算扩展集群的企业越来越多；另一方 面，传统的调度算法无法适应新的集群环境。这两方面的矛盾随着云计算的发展 越来越突出。面对这样一个局面，我们势必要探索和研究基于云计算的集群扩展 中的调度算法，以适应当今现代企业发展的要求，这对于现代企业有效的扩展集 群，合理利用云计算资源，节约集群运行成本和提高用户满意度，都具有重大的 意义。 1 2 国内外相关研究 1 2 1 作业调度算法相关研究 在启发式规则方面，R a d u l e s c uA 等人提出先进先出集群调度算法【6 1 。 W e i s s m a nJB 等人提出短作业优先调度算i 去【7 1 。K a v a sA 等人研究了资源预留算 法【8 】。L i f k a 等人提出了B a c k f i l l i n g 调度算法【9 】。在启发式算法方面，李建峰和彭 舰基于M a p R e d u c e 模型，提出了一种双适应度的遗传基因算法D F G A ，这种算 法比较注重作业的平均完成时间【1 0 】。孙瑞锋和赵政文基于云计算虚拟化技术，提 出了一种租借理论和动态资源池相结合的调度策略，减少资源空闲时间，提高了 资源的利用率【l 。汤小春和刘健针提出了种基于元区间的分配决策算法【1 2 】。 华夏渝等人提出一种基于蚁群优化的资源分配算法【1 3 1 。在背景扩展方面，M e n g X u 等人提出了一种云计算环境下的多作业流多Q o S 约束的调度策略【1 4 】。王晓川 3 第一章绪论 等人提出一种基于分布式调度机制的集群体系结构【l5 1 。张震晓等人提出了一种基 于任务类型的集群调度策略【1 6 】。在与云计算相集合方面，D e e l m a nE 等人分析了 云计算解决大规模数据处理应用的成本问题【1 7 】，没有考虑复杂的调度策略，没有 考虑启动、停止虚拟机消耗的成本。M a r c o s 等人分析了使用云计算扩展本地集 群的成本问题【1 8 】，该沦文考虑了虚拟机启动时消耗的成本，但做了一个假设：云 中的资源可以按秒为单位进行申请，配置、测试运行环境的时间和成本不予考虑。 1 2 2 云计算相关研究 G o o g l e 公司作为云计算的首创者，以两篇文章奠定了云计算的技术基础： M a p R e d u c e ：S i m p l i f i e dd a t ap r o c e s s i n g o nl a r g ec l u s t e r s 【”J 和T h eG o o g l ef i l e s y s t e m 2 0 1 。前者介绍了g o o g l e 集群中处理大规模数据的M a p R e d u c e 1 9 1 算法，也 就是现在云计算中谈论m a p r e d u c e 调度算法；后者介绍了g o o g l e 集群中的文件系 统，该论文中的很多思想，被现在很多云计算提供商采用，作为其文件系统设计 的基本要求。开源社区的h a d o o p 系统【2 l 2 2 1 ，模仿了G o o g l e 的M a p R e d u c e 算法 和G o o g l e 文件系统，设计了自己的云计算平台，由于它的开源性，现已成为广 大科研人员的研究云计算的一个重要工具。伯克利云计算白皮书中，对云计算的 概念、云计算面临的挑战、云计算中关键的问题、云计算的商机等【l 】方面进行了 详尽的介绍，并得到了商业界以及学术界的赞同。B u y y aR 利用虚拟化的思想提 出了面向市场的云计算的概念，以及面向市场的云计算的构加【2 3 】，并畅想了全球 化的云计算交易市场。虚拟化技术，作为云计算中最为关键的技术之一，极大影 响着云计算的发展。只有通过虚拟化技术，云计算资源才能够实现按需分配【2 引， 云计算才能够得到蓬勃发展。P a u lB a r h a m 等，介绍了使用虚拟机x e n 虚拟化计 算资源【2 5 】，该方法被各大公司广泛应用于云计算资源虚拟化中，例如，A m a z o n 的E C 2 就是使用x e n 虚拟化其计算资源【2 6 2 。7 1 ，整个集群使用虚拟机管理器进行 管理，例如，虚拟机管理器N e b u l a 2 8 1 、虚拟机管理器E u c a l y p t u s t 2 9 1 ，为用户提供 弹性云的服务。L a g a r - C a v i l l aH A 提出一种快速克隆虚拟机的系统【3 0 】，这种方法 能够让本来需要几十秒的资源虚拟化过程减少到不到1 秒的时间，极大的节约了 时问和成本。虚拟机管理器作为管理集群虚拟资源的软件，在云计算中的作用越 来越大，E u c a l y p t u s 作为虚拟机管理器的一种，被广泛应用于学术研究中。 1 3 论文主要工作 ( 1 ) 将作业调度算法的研究背景从传统的集群环境转变到云计算扩展的集 群环境，提出了基于云计算的集群扩展中的调度算法。由于传统作业调度算法只 、 4 第一章绪论 考虑了单一的集群环境，对于云计算扩展的集群环境显得无能为力。因而，本文 结合传统的作业调度算法，提出了适合在云计算扩展的集群环境中的调度算法。 ( 2 ) 设计了两种简单的调度算法，包括：本地优先算法和云环境优先算法。 算法类似于传统作业调度中的F C F S 算法，其意义在于：1 ) 提出了基于云汁算 的集群扩展中的F C F S 算法，作为之后研究的参照比较算法；2 ) 算法简单灵活， 易于修改，方便在今后的研究中移植到仿真模拟器中。 ( 3 ) 设计了基于计算强度的调度算法。为了减少简单调度算法作业运行成 本，我们设计了基于计算强度的调度算法。其意义在于：1 ) 分析并解决简单调 度算法中存在的问题，从而减少作业完成总成本。2 ) 提出将计算强度( 参考C P U 性能) 作为作业分配的一种标准，为之后的研究提供了一种思路。 ( 4 ) 设计了E V R B 调度算法和I E V R B 调度算法。为了进一步减少作业运 行成本，同时控制超出约束的作业数量，我们设计了E V R B 算法和I E V R B 算 法。其意义在于：1 ) 提出基于云计算的集群扩展中的B a c k F i l l i n g 思想的算法。 2 ) 将传统集群中最成功的B a c k F i l l i n g 算法引入到云计算扩展的集群环境中；3 ) 将二维的时空图变成三维，使得研究更符合实际情况；4 ) E V R B 算法通过使用 等体积变化的方式代替B a c k F i l l i n g 算法的单一时间比较的方式，增加了可回填 作业数量，从而减少了作业调度时间和成本；5 ) I E V R B 算法通过使用放宽参考 C P U 数量的限制，进一步增加了可回填作业数量，从而进一步减少了作业调度 时间和成本。 ( 5 ) 设计实验从成本和超出约束的作业数量两方面研究所提出算法的有效 性，并分析了算法的适用性。此外，在试验环境中收紧M a r c o s 等人的假设，在 传统云计算试验中，作业可以立刻获得所需求的资源，但实际中云资源并不能够 按秒进行分配、按秒释放，比如使用亚马逊的I a a S 需要提前申请。同时，刚申 请完资源并不能立刻整合到私有服务器中，需要进行相应的配置和测试，花费相 当的一段时问，在一段时间内使用新的资源是不容易的。因而，我们在试验设计 中固定云计算的资源数量。 1 4 论文组织结构 本文在分析了传统集群调度算法相关内容的基础上，利用云计算技术的优 势，从经济的角度考虑，讨论了基于云计算的集群扩展中的调度算法，其中调度 算法的设计和实验分析是本文的重点。 各章内容如下： 第一章为绪论，对于作业调度以及作业调度算法、论文研究背景及意义进 5 第一章绪论 行简要的说明，概述了作业调度算法和云计算相关技术的国内外研究现状以及论 文的主要工作，最后，介绍了论文的组织框架。 第二章介绍了云计算技术和作业调度算法。其中，云计算技术主要包括： 云计算的发展历程、定义和特点、云计算的主要技术以及现今云计算的主要产品 等。作业调度算法主要包括：作业调度算法的概念、设计原则和几种经典算法等。 第三章对问题进行了详细描述、介绍了算法的研究思路，并循序渐进的设 计了五种基于云计算的集群扩展中的作业调度算法。首先，讨论了问题描述和研 究思路。随后，设计了两种简单调度算法：本地优先策略和云所：境优先算法，作 为参考调度算法。接着，总结了简单调度算法中存在的问题，设计了一种基于计 算强度的调度算法。之后，分析了基于计算强度的调度算法的缺陷，结合 B a c k F i l l i n g 算法设计了一种E V - R B 调度算法，该算法使用预留资源、体积回填 的方式插入作业。然后，通过对E V - R B 进行改进，设计了I E V - R B 调度算法。 最后，对各个算法进行了回顾与比较。 第四章设计实验环境，并对实验结果进行分析。从算法有效性分析、以及 算法适用性两个方面进行了讨论。 第五章对全文进行总结，提出未来研究方向。首先将本文进行了总结，然 后对基于云计算的集群扩展中的调度算法进一步的研究方向进行了思考，从问题 的拓展和算法的深入研究等方面对后期的研究进行展望。 6 ， 第二章云计算技术作业调度算法概述 第二章云计算技术与作业调度算法概述 本篇论文主要讨论的是基于云计算的集群扩展中的调度算法，其中包涵了云 计算技术和作业调度算法两个方面的内容。为了能够更加深入地理解本文的研究 内容，本章简略的介绍了云计算技术和作业调度算法的相关知识，作为后面基于 云计算的集群扩展中的调度算法设计的理论铺挚。 2 1 云计算相关内容简介 2 1 1 云计算发展历程 ( 1 ) 集中式的计算 在计算机发展的初期，使用计算机的模式基本是服务器客户机的形式。所 有软件、数据都是存放在一个大型主机中的，所有的控制也都是针对这一大型主 机的，这个大型主机被称为服务器。用户想要得到一定的数据，使用计算机计算 一个方程式都必须连接到主机，并获得相应的权限，否则无法进行操作。 用户连接到服务器的计算机终端称为客户机。这种服务器和现在的计算机大 有不同，他不能够提供大量的计算能力、内存和存储空间，他的作用仅仅是连接 服务器和客户端，以及简单的输入输出功能。 这种计算模式形成的原因主要是由于技术条件的限制。由于当时无法制造出 性能较高的计算机，同时制造成本很高，使用服务器客户机的计算模式最有利 于更多的用户使用计算资源、存储资源。 ( 2 ) 对等计算 在集中式的计算中，所有的计算机都是通过服务器进行连接，这种模式下所 有客户机间的通信都要先通过服务器，导致服务器的压力很大。为了解决这一问 题，对等( P 2 P ) 计算的模式被提了出来。在这种模式下，每台计算机在网络中 的地位都是平等的，这种构架和集中式的计算结构完全不同。 P 2 P 是一个平等的概念，在网络中的计算机既是客户端又可以充当服务器。 这样，每个计算机之间的通信可以直接进行，不需要经过中央服务器。这样的好 处是显而易见的，在P 2 P 网络中的任何一台计算机都可以方便的和另一台计算 机直接传递资源，不需要其他计算机参与，极大的减轻了计算机的负担和网络负 担。 现在的因特网就是P 2 P 网络最好的实现。早期的因特网来源于A R P A n e t 网 7 第二章云计算技术与作业调度算法概述 络，被用来共享美国各地的资源。现在的因特网已经遍及全球，连接因特网的用 户可以方便的从音乐网站上下载音乐；两台电脑间可以随心所欲的传递信息；文 件共享在因特网网络中也是轻而易举。 ( 3 ) 分布式计算 有一些科学研究和商j I k 应用需要大规模的计算资源，如果为了这些需求提供 能力足够强的单台计算机耗费的成本是非常巨大的；同时，人们拥有的计算机并 不是每台2 4 小时完全使用，在闲置的时候，这些资源不能得到利用造成浪费。 为了解决这些问题，分布式计算的思想被提了出来。 分布式计算是将多台计算机连接起来，组成一个能够提供巨大计算资源的计 算机组。