（通信与信息系统专业论文）基于执行时间方差的元任务网格调度算法研究.pdf

北 宝銮逼 太 堂亟 堂僮谂 塞虫塞撞墨 中文摘要 摘要：网格计算是一种特殊的具有重要创新思想和巨大发展潜力的分支网络计算。 从概念上讲，网格计算的目标是资源共享和分布协同工作。而任务调度作为网格 高性能计算的一个重要方面，它的性能好坏直接影响到网格计算的性能优劣。随 着网格方向逐步走向标准化、大型化和多技术融合化，对任务调度的性能提出了 更高的要求。网格任务调度算法成为网格研究的一个热点。 网格的任务调度问题一直是一个n p 问题，目前采用的大多是启发式调度算 法。网格任务调度一般分为静态调度和动态调度两大类。在动态调度中任务调度 又分在线模式和批模式两种，批模式具有动态在线模式算法的实时性，又具有静 态映射调度算法的高效性，在很多计算系统中得到了广泛应用，比在线方式更能 充分利用计算资源。但是对于传统的批调度算法如最小最短算法m i n - m i n 、最大 最短算法m a x - m i n 、最大间距算法m a x - i n t ，从负载均衡度和调度跨度这两个 重要的网格性能角度看，它们在调度跨度取得较好成果的同时，在负载均衡度上 并不尽如人意。针对网格的异构性，本文提出了一种改进的算法叫v a r i a n c e ( q u e u e dv a i l 锄c ea l g o r i t h m ) 。该算法在总结了经典算法优点及缺点的基础上，负 载均衡度有了显著提高，并且调度跨度也得到改善。 任务分配到各个机器上执行时间会有差异，方差是反映该差异的数学变量。 该算法首先将执行时间的方差作为任务执行优先级的评判基础。每个任务都存在 一个方差，将各个方差求得的期望作为任务分组的分界线，从而将批量任务分为 方差大组和方差小组。每一次任务分配以基数因子为基准分成几轮。每个轮次， 每个组按照相应比例进行任务调度，增强任务的负载均衡度，缩短任务的调度跨 度。然后以m i n - m i n 、m a x - i n t 算法为测评基准，利用网格调度的模拟工具包 g r i d s i m ，在n e t b e a n s 环境下，进行大量的仿真实验，结果证明：qv a r i a n c e 算法具有很好的调度性能，能够适用于网格异构偏差大条件下的网格任务调度， 并且能得到比m 矾m i n 、m a x - i n t 更优的调度结果。 论文最后除了对研究工作进行了相应的总结外，还对今后的研究方向进行了 展望。图1 4 幅，表1 9 个，参考文献3 3 篇。 关键词：网格调度；执行时间；方差分组；g r i d s i m 分类号：t p 3 9 3 a b s t r a c t a b s t r a c t ：g r i dc o m p u t i n gi so n es p e c i a lb r a n c h i n gn e t w o r kc o m p u t i n gw h i c hf s c o n t e n t e dw i t hi n n o v a t i v ei d e a sa n dh u g ep o t e n t i a l 1 1 1 eg o a tt o g i r dc o m p u t i n gi st h er e s o u r c e s h a r i n ga n dd i s t r i b u t e dt e a m w o r k t a s ks c h e c l u u n ga so n eo fi m p o r t a n ta s p e c t si ng r i dh i g h p e r f o r m a n c ec o m p u t i n gi n f l u e n c e st h ep e r f o r m a n c eo f g r i dc o m p u t i r 喈a st h eg r i dw o r k su pt o s t a n d a r d i z a t i o n ，u p s i z i n g ，m e r g i n gi nm u l t i - t e c h n i q u e ，h i g h e rr e q u i r e m e n t sa r en e e d e dt o t a s i s c h e d u i n 8 j o bs c h e d u t i n ga t g o r i t h mb e c o m e so n eo fh o t s p o t so nt h er e s e a r c ho fg r i d 1 1 1 s p a p e ri n t r o d u c e st h ep r o p e r t y , t h ea r c h i t e c t u r e ，c u r r e n ts t t u a u o n o ng r i d c o m p u t i n g ；a n a t y s e st h et a r g e t ，m a t h e m a u c a tm o d e t ，s t a t i co rd y n a m i ca t g o r i t h m b a s e do n t h eb a s i ct h e o r y , ir e v i e wt h ee x p e r i e n c eo fj o bs c h e d u t i n 8a t s o r i t h mm i n m i n ，m a x m i n ， m a x i n t , i nv i e wo fi s o m e r i s mo nt h eg r i d ；p u tf o r w a r dan e wi m p r o v e da t g o r i t h mq v a r i a n c e ， o nt h ea s p e c to fo p p o r t u n i s u ct o a db a t a n c i n ga n dm a k e s p a n f i r s t ，t h i sa l g o r i t h mt sb a s e do n m e t a - t a s k ；m a k e st h ev a r i a n c et ot h ee x e c u t i o nu m eo ne a c hh o s ta st h em e t e w a n d t h e n ，l u s em a t h e m a t i c a te x p e c t a t i o na st h eb o u n d a r yt ot h eg r o u p i n go ft a s k s 。t h eb i g g e rg r o u p0 1 1 v a r i a n c ea n dt h es m a t t e rg r o u po nv a r i a n c e d i v i d eb a t c ht a s k si n t oat o to ft u r n so nt h eb a s eo f o n ep a r a m e t e r so fb a s e t i n e t h en u m b e ro ft h et a s k se a c hg m u pa s s i g n e di sb a s e do ns o m e c o r r e s p o n d i n gp r o p o r t i o n 1 1 1 i sa t g o r i t h mi m p r o v e st h eb a t a n c eo ft h et o a da n dc u t sd o w nt h e m a k e s p a no ft a s k s u s et h ea l g o r i t h mo fm i n - m i na n dm a x i n ta st h ec o n t r a s t t h i sp a p e r s h o w st h ee x p e r i m e n t a tr e s u t t so nt h ec o m p a r i s o no ft h et o a db e a n c ea n dt h em a k e s p a n a m o n gq _ v a r i a n c ea n dt h r e er e t a t e da t g o r i t h m s ，i nt h eg r i d s i mu n d e rt h en e t b e a n s i tt u r n s o u tq _ v a r i a n c eh a sav e r yg o o dp e r f o r m a n c ea n di sa d e q u a t ef o rea r r a y su n d e ra n yk i n d s a n d t ta l s og e t sb e t t e rr e s u t t st h a nm i n - m i na n dm a x - i n l ： i nt h ee n d ，e x c e p tt h ec o n c t u s i o no fm yw o r k ，t h i sp a p e ra l s or o o k sf o r w a r dt ot h e d e v e t o p m e n t a id i r e c t i o no ft h i sr e s e a r c h p i c t u r e s14 ，t a b t e s19 ，r e f e r e n c e s3 3 k e y w o r d s ：g r i dd i s p a t c h ；e x e c u t i o nt i m e ；v a r i a n c eg r o u p e d ；g h d s i m c l a s s n o ：t p 3 9 3 图2 1 图2 2 图2 3 图2 4 图3 1 图3 2 图3 3 图3 4 图4 _ l 图4 2 图5 1 图5 2 图5 3 图5 - 4 图5 5 图目录 五层沙漏结构分层图1 6 网格服务示意图l7 网格系统下的应用程序调度模型1 9 元任务的组成2 l m i n - m i n 和m a x - m i n 算法方案2 8 m a x - m i n 和m i n - m 1 n 算法方案2 9 m a x - i n t 和q _ v a r i a n c e 算法方案。3 2 q _ _ v a r i a n c e 算法流程图3 6 g r i d s i m 平台及应用的多层次构架抽象。4 2 q _ v a r i a n c e 实现的各个模块之间关系图4 5 m i n m i n 、m a x - i n t 和q _ v a r i a n c e 三种方法的调度跨度4 9 q _ v a r i a n c e 和m a x - i n t 两种算法对比一5 l q _ v a r i a n c e 和m a x - i n t 两种算法对比二。5 2 在不同任务量的情况下各个资源的负载情况。5 4 在工作量很大的情况下各个算法的负载情况5 5 表目录 表3 1 执行时间分布情况1 2 8 表3 2 执行时间分布情况2 2 9 表3 3 执行时间分布情况3 3 0 表3 4 实例分析中的任务实例n = 2 0 3 7 表3 5 网格各个资源的情况列表3 7 表3 6qv a r i a n c e 各个资源的负载情况3 8 表3 7m 玳m i n 算法各个资源的负载情况3 8 表5 1 表5 2 表5 3 表5 4 表5 5 表5 6 表5 7 表5 8 表5 9 表5 1 0 表5 1 1 表5 1 2 仿真资源列表4 7 qv a r i a n c e 与m 玳m i n 调度跨度表现一。4 8 qv a r i a n c e 与m i n - m i n 调度跨度表现二4 8 qv a r i a n c e 与m a x - - i n t 调度表现。4 9 在任务数变动的情况下qv a r i a n c e 在各个资源上的表现情况。5 0 qv a r i a n c e 与m a x - v a r 调度表现5 2 任务量为2 0 的时候各个资源的负载情况5 3 在任务量为5 0 的情况下各个资源的负载情况5 3 在任务量为7 5 的情况下各个资源的负载情况5 4 在任务量为1 5 的情况下各个资源的负载情况。5 6 在任务量为5 0 的情况下各个资源的负载情况。5 6 在任务量为1 0 0 的情况下各个资源的负载情况5 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：嫩卿 签字日期： 如口序6 月8 日 导师虢伪锨 签字日期：z 时年二月f 阳 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：嗣叩 签字日期：砌g 年占月，p 日 致谢 本论文的工作是在我的导师张有根、陈常嘉教授的悉心指导下完成的，在此 衷心感谢两年来张有根老师对我的关心和指导。在论文选题、研究和撰写过程中， 陈老师经常沟通交流，对于论文的编写起到了极大的推动作用。 胡师舜悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予了 我很大的关心和帮助，在此向胡师舜老师表示衷心的谢意。 在p l a t f o r m 的实习期间，是柳沛杉、童涛、刘继峰等同事的大力帮助才让 我不断深入到研究领域中去。特别是柳沛杉和童涛，对于我的学习工作和生活给 予莫大的帮助，我取得的一点一滴的进步与他们的指导是密不可分的。在此表示 衷心的感谢。 另外，还要非常感谢北京师范大学的梁雪芳和杨广进同学，在论文撰写和仿 真编码期间，给予我极大的帮助、鼓励和支持，特别是在仿真编码阶段，对于算 法的编写提出了重要意见，是仿真顺利进行的保证，使我从毫无头绪到现在的顺 利完成课题。这里再次向两个好朋友表示我深深的感谢。 而且也要感谢共处了两年的同学们，感谢你们无论在生活还是学习中给我的 莫大鼓励和热情帮助。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。感 谢他们无私的爱和充分的信任，感谢他们对我永远的支持和鼓励，感谢他们的养 育之恩。 序 本文是笔者在专业从事网格技术的p l a t f o r m 公司实习时，接触到网格这一 新兴领域背景的启发下写就的。通过大量阅读关于作业调度的经典论文，获得比 较扎实的网格理论基础。配合平日在公司对负载均衡产品l s f 的实际操作，增强 对网格的实际认识，提出了一种网格任务调度的改进算法。 负载均衡和调度跨度是衡量网格性能的一个重要指标，网格任务调度是公认 的n p - h a r d 问题，因此网格的任务调度一向是业界研究的热点。负载均衡和调 度跨度有时是两个相互对立的性能，两者很难都同时达到最优状态。通过对现阶 段经典算法的研究分析比较，特别是对作为测评标准的m i n - m i n 、m a x - i n t 算 法的仔细分析，笔者发现以下问题： ( 1 ) m m 玳算法只是追求局部最优，对全局的掌控不足，负载均衡度不 好。相比之下，m a x - i n t 有不错的负载均衡性和调度跨度。那么如何 提出一种算法与m a x - - i n t 比较，性能更好，甚至优于m a x i n t 。 ( 2 ) 对于异构的网格环境，当任务在各个机子上的执行时间差距很大的情 况下，如何更好地将批量任务进行调度，缩短执行时间，更加适应异 构的网格环境。 ( 3 ) 对于网格的任务调度，分组与不分组的异同，怎样分组可以达到比较 好的效果，更加提高任务调度算法的性能。 本文就是针对这三方面的问题进行研究和改进，引用随机过程的基础理论， 以经典的m 烈m i n 、m a x i n t 作为仿真的测评标准，进行算法流程的设计，用 j a v a 编写算法，用网格仿真器g r i d s i m 进行仿真。通过一百次的仿真得到可靠数 据，同时，应用l i n u x 中的s h e l l 的文本处理工具对数据进行处理，用m a n a b 进行 趋势分析，论证该改进算法的性能。最终的仿真结果验证了该算法具有较好的性 能。在老师、同事、同学的支持帮助和协作下最终完成了该研究工作。 本文在算法的性能改进上，对于调度跨度这一性能指标与m a x - i n t 比较只是 稍有提高，但是负载均衡度提高很大。同时g r i d s i m 网格仿真器需要大量地编程才 能模拟特定的环境，因此大量的编程是得以将网格的经典算法和自己提出的算法 在g r i d s i m 上顺利实现的保障。在数据处理的过程中，熟练应用处理复杂程序的脚 本语言进行文本处理，以及用m a u a b 实现数据的规律性分析。这些都付出了巨大 的劳动，希望读者给予适当的评价。 1 引言 1 1 研究背景 网格是一种新兴的分布式计算技术，是信息社会的网络基础设施，被称为继 传统的因特网、万维网之后的第三代因特网的应用。网格的目标是把整个因特网 整合成一台巨大的超级计算机，实现互联网上所有资源的互联互通，完成计算资 源、存储资源、通信资源、软件资源、信息资源、专家资源的共享。随着计算机 科学技术的发展，网格已成为当前国内外研究的一个热点和前沿领域【l 】。 在网格计算中，任务管理、任务调度和资源管理是网格必须具备的3 个基本 功能。网格计算的大体流程就是用户通过任务管理系统向网格提交任务、为任务 指定所需的资源、删除任务并监测任务的运行状态。用户提交的任务通过任务调 度系统按照任务的类型、所需资源、可用资源等情况安排运行的日程和策略。而 资源管理系统监测网格资源状况，收集任务运行时的资源占用数据等【1 4 】。网格计 算任务调度面临的是一个n p 完全问题，它引起众多学者的关注，成为目前网格计 算研究领域的一个焦点。 任务调度是集群和网格计算等分布式计算系统的核心组件，它为作业分配适 当的处理器和资源。任务调度目的是合理地安排处理器，维持系统的正常运转， 最大限度发挥网格系统的作用1 4 1 。 1 2 研究现状 1 2 1网格计算的研究现状 网格研究起源于2 0 世纪9 0 年代初由美国政府资助的分布式超级计算机项目 i - w a y 。从1 9 9 3 年开始，高性能计算技术和互联网技术进一步融合，产生了继 i n t e m e t 、w e b 之后的第三次技术浪潮网格计算【5 1 。 目前，在网格计算领域的研究工作主要集中在网格计算环境中的基础研究和 建立专用的应用网络两条线路上。前者主要被国外以g l o b u s 同盟为代表的研究组 织所领导，而对于后者，在国外主要集中在欧洲和美国。美国国家航空和宇宙航 1 0 行局( n a s a ) 的i p g ( 1 n f o r m a t i o np o w e rg r i d ) 项目，目的是让人们使用计算资源和 信息资源就像使用电力网提供的电力资源一样方便快捷。美国能源部开发的a s c i g r i d 已经投入生产性使用，其主要用途是核武器的研究。欧洲共同体的e u r o g r i d 和d a t a g r i d 主要用于包括高能物理、生物计算、气候模拟等多个领域的应用。m m 、 c o m p a q 、s u n 、l s f 和b o e i n g 等大型公司开始进入g r i d 计算领域。g l o b u s 和l e g i o n 是g r i d 计算领域的两个比较著名的g r i d 支撑软件系统 6 1 。 我国中科院计算技术研究所从1 9 9 6 年开始了网格技术的研究开发工作。2 0 0 0 年，开发了连接国内8 个曙光计算机中心的网格。中国科学院计算技术研究所2 0 0 1 年提出了织女星网格计划，目前已取得相当的进展，实现了网格资源的虚拟化， 屏蔽使用网格资源的技术细节嘲。 为了将有限的资金投入到建设庞大的网格系统，国际与地区间的研究机构和 商业机构开展有效的合作是非常必要的。全球网格论坛、地区网格论坛、国家网 格论坛、网格协作组织纷纷出现，用来协调成员间的合作关系、开发标准和协议。 全球最大的网格联盟全球网格论坛已经成为事实上的网格标准的制定和发布 机构嘲。 1 2 2网格任务调度的研究现状 要实现高效的网格计算需要处理许多复杂的问题。其中，任务调度问题是网 格研究中所必须解决的一个关键问题，也是网格应用的基础。高效的任务调度策 略和算法可以充分利用网格系统的处理能力，从而提高网格应用程序的性能，以 便更好地利用网格资源。目前，网格环境下的独立元任务的调度问题是一个n p 完 全问题【5 l ，人们已经提出了很多启发式调度算法，都以获得尽可能短的任务完成时 间作为调度目标。如经典的m i n - m i n 、 m a x - m i n 、m a x - - i n t 、 g a ( g e n e t i c a l g o x i t h m ) 、s a ( s i m u l a t e da n n e a l i n g ) 等等，这些都成为解决调度问题的有效方法。 启发式任务调度算法可以分两大类：静态调度算法和动态调度算法。而动态 调度算法可进一步分为在线模式和批模式两种。静态调度在调度前就确定了调度 方案，脱离了任务实际运行时的动态信息，盲目性大而且效率低，难以取得较好 的性能。动态调度则是根据系统当前状态平衡各节点【6 1 【7 1 。实验表明在通常情况下， 动态负载平衡较静态负载平衡有3 0 - 4 0 的性能提高【1 0 1 。动态调度中的在线模式 是任务刚到来就加以映射，而批模式则是把任务收集起来等映射事件到来后才对 这些任务进行集中映射。相比而言，批模式比在线模式更能充分利用计算资源。 典型的在线模式调度算法包括o l b ( o p p o r t u n i s t i cl 0 a db a l a n c i n g ) 算法， m e t ( m n i m u me x e c u t i o nt i m e ) 算法，m c t ( m i n i m u mc o m p l e t i o nt i m e ) 算法1 6 1 。在 上述几类在线模式算法的基础上，研究者还提出了其他一些在线模式算法，大多 为上述几种算法的变形或组合。 批模式调度算法中m i n - m i n 算法是应用最为广泛的一种算法。其思想是，对 于任务集合中的每个任务，算法求得单个任务最小预期完成时间。然后把所有任 务中具有最小该时间的任务分配给对应的资源，并从任务集合中删除。该过程重 复进行直至所有的任务调度完毕。m a x - m i n 算法与m 矾m i n 算法不同，它是将 最小预期完成时间最大的任务分配给对应的资源执行，当任务集中的短任务远远 多于长任务时，该算法优于m 矾m i n 算法【砌。m a x - i n t 算法计算任务在各个可 用资源上的预期完成时间，用次小的预期完成时间减去最小的预期完成时间，得 到一个差值i ，系统优先调度i 值大的任务【1 2 】。 1 2 3存在的问题 尽管众多研究者对网格计算做了大量的工作，在很多方面取得了巨大的成就， 但还是存在着一些问题和缺陷，尤其对于异构网格计算环境下大吞吐量的任务调 度应用效果不理想。大部分的算法都只侧重于考虑算法的某个方面，这在特定的 网格中，确实能得到很好的应用。但是由于网格系统的庞大、情况的复杂、操作 系统平台的多样、涉及技术的多样，使得人们还有很多探索和研究的必要。任务 的调度划分目前还是一个n p 难解问题，没有有效的方法进行解决。什么样的任务 调度算法可以使系统具有更高的计算执行效率，什么样的任务调度可以让系统有 更好的负载平衡度，这些闯题都还有待进一步地研究。 1 3 研究内容和研究方法 1 3 1 研究内容 网格的特点包括节点的数量大，节点之间的平等性，每个节点具有高度的自 治性。具体到网格异构环境的任务分配问题，优化方案主要分两方面：( 1 ) 分配 任务到处理机使得执行费用和通信费用的总和为最小；( 2 ) 考虑如何调动任务到 处理机，以使总任务集合执行完的时间最短【1 3 1 1 4 1 。于是，将以上两步结合起来考 虑，根据网格调度的基本结构，提出一个对任务调度进行优化的模型，并通过编 1 2 写算法，系统仿真证明该模型有利于网格平均性能的提高。因此，本文的研究内 容主要包括以下两点： 1 ) 通过网格计算任务调度算法的研究，提出一个改进算法 一个运算量巨大的任务能否在网格环境下正确、快速和高效地运行并执行成 功，高效的任务调度算法不可或缺。良好的负载均衡性和较短的调度时间跨度是 每个任务调度算法的追求，因此本文重点研究了网格计算任务的调度算法。首先 对经典的调度算法进行研究，找出其优点和缺陷，然后再设计出一种改进的网格 计算任务调度算法，该算法在调度跨度和负载均衡性都有提高。 2 ) 实验结果验证该算法的性能 网格计算任务调度算法的目的是要寻找在某一或某些性能上更好的调度算 法，但如何评价算法的优劣，需要对算法进行形式化分析和仿真的网格环境下的 模拟比较。在调度仿真环境下，对算法进行模拟和仿真，以实验数据为基础和已 有的一些经典算法比较，用实验数据说明提出算法的优越性。 1 3 2研究方法和实验内容 在研究本课题时，采取理论研究和实证相结合的方法。理论研究主要是分析 现有的调度模型和调度算法，比较各种方法的优缺点，从全局的角度考虑网格调 度的负载均衡、调度跨度和算法效率。另外也研究了一些不同类型的算法如静态 任务调度中的遗传算法、模拟退火算法，动态任务映射中的m 矾m i n 、m a x - m i n 、 m a x - i n t 、启发式算法、贪心算法、动态规划算法等。以这些算法为基础，并通 过对随机过程、排队论等原理的参照，综合经典算法的优点，针对其缺点进行改 进，提出一种基于执行时间方差的分组网格任务调度算法qv a r i a n c e ( q u e u e d v a r i a n c ea l g o r i t h m ) 。 实证主要采用流行的网格模拟工具对我们的算法进行模拟和仿真，对其运行 效率和运行结果进行分析。主要采用g r i d s i m ( g r i d s i m 是一个j a v a 开发的工 具包，它提供了丰富的函数库以支持模拟网格环境中异构资源、用户、应用程序 和调度器) 进行任务调度模拟。模拟不同的算法与该算法进行对比，利用仿真产 生的大量数据的进行分析，通过这些数据结果最终证明该算法的性能优势。 1 3 韭塞交通太堂亟 堂盈 论塞 呈l直 1 3 3文章结构 论文按照如下线索组织内容：网格计算的背景一网格的任务调度及经典算法 - - q _ v a r i a n c e 调度算法的研究一实验环境介绍及数据仿真，最后以结论和展望 结尾。共分6 章，其具体内容概括如下： 第一章引言。主要介绍了研究背景，任务调度研究现状以及存在的主要问题。 本文主要的研究对象、研究方法、实验方法，大概介绍了文章的结构。 第二章主要概括地介绍了网格的基本特征，网格的基本体系结构模型和应用 现状。介绍了网格的任务调度的目标，应用程序网格调度的基本模型， 网格中任务调度的数学模型，比较详细地论述了一些比较经典的网格 调度算法。 第三章针对m i n - m i n 算法只追求局部最优，而忽略全局的缺陷。由负载均衡 原则和高吞吐率原则，提出了一种通过方差决定调度的总优先级，用 分组微调的方式进行负载和执行时间平衡的调度算法。 第四章介绍了网格仿真重要的模拟器g r i d s i m 。说明了该仿真器的主要特征、 体系结构、主要实体和使用步骤，介绍了qv a r i a n c e 算法的实现过 程。 第五章对qv a r i a n c e 算法进行实验仿真。通过实验仿真，分析该算法的应 用特性，优点与不足。 第六章研究和展望，对本文的工作做出总结，为进一步的工作提出展望。 1 4 本章小结 本章为全文交代了研究的背景，说明了当前网格计算尤其是网格任务调度的 研究现状，分析了现在网格任务调度存在的问题。阐述了本次研究的研究内容和 研究方法，同时为全文勾勒了一个整体的框架。 1 4 2 网格的任务调度 2 。l 网格的概念 2 1 1网格的特性 一个计算网格是一个硬件和软件基础设施。网格计算的本质是动态的，它在 多机构的虚拟组织中协调资源共享和协同地解决问题【1 6 1 。按照这种提法，网格的 概念涉及两个方面。一方面，网格的目的是资源共享和协同解决问题，另一方面 网格环境是动态的、跨组织的。网格需要解决跨机构的资源管理、安全、数据访 问等问题【5 1 。 虽然网格系统具有分布式的一些特征，但是作为一种新的计算基础设施，网 格还具有一些重要的特点。这些特点对于网格构建、网格研究和网格应用有着重 要的影响。 网格的特点包括五个方面【3 0 1 3 2 3 ： ( 1 ) 分布性。组成网格的资源可能是计算资源、存储资源、数据资源、仪器 资源等，它们的分布在地理位置上差异大，因而网格工作流等关键技术 研究并不是集中在一起的。在这种分布环境下，需要解决任务的分配和 调度问题，传输和通信问题，人与系统以及人与人之间的协同问题，网 格应用在分布环境中自动执行和协作问题。 ( 2 ) 异构性。组成网格的资源是异构的。对于计算资源，有不同的类型的计 算机，不同的计算方式，不同的计算接口，不同的系统构架。同样，对 于存储资源和其他资源，也面临着这样的问题。因此，网格既要具有利 用资源的异构特点进行处理的能力，同时又要具有提供一致资源管理的 能力。 ( 3 ) 自治性。网格上的资源首先是属于某一本地的个人或者组织，网格资源 的拥有者对资源具有最高级别的管理权限，网格应该允许资源拥有者对 其资源有自主的管理能力。因此，网格具有自治性。 ( 4 ) 动态性。由于网格中的资源具有自治性，因此网格资源可能动态地加入 或退出网格，也可能出现故障而导致该资源不可用。 ( 5 ) 自相似性。网格的局部和整体之间存在着一定的相似性，局部在许多地 方具有全局的某些特征，而全局的特征在局部也有一定的体现，网格的 1 5 构建通过小的局部网格可以形成更大的网格，其构成方式具有相似性。 2 1 2网格的体系结构 五层沙漏结构是一种早期的抽象层次结构，主要特点是以“协议”为中心，强调 协议在网格资源共享和互操作中的地位，其结构简单、层次清楚。通过协议实现 一种机制，使得虚拟组织的用户与资源之间可以进行资源使用的协商，建立共享 关系，并且可以进一步管理和开发新的共享关系。这一标准化的开放结构对网格 的扩展性、互操作性、一致性以及代码的共享都很有好处【2 7 j 。 五层沙漏结构的一个最重要的思想是以“协议”为中心，也十分强调服务与a p i 和s d k 的重要性。在五层沙漏结构中，共享的概念不仅仅是交换文件，而是更强 调对计算机、软件、数据以及其他资源的直接访问。并且共享关系又是十分灵活 的，存在三种基本形式，即客户端与服务器( c s ) 的共享、端到端( p 2 p ) 的共 享以及代理( p r o x y ) 共享。该结构中的共享还是一种随时间变化的动态的共享， 而不是静态的共享【2 1 | 。 五层沙漏结构中的另一个重要内容是互操作，而前面将共享定义为对各种资 源的直接访问，目的就是为了支持互操作。共享关系需要在任意的组织、团体之 间一开始就建立，可以动态地增加新的成员，并且可以跨越不同的平台、语言和 编程环境。而要实现互操作就是以五层沙漏这一协议结构为基础的。【2 州 五层沙漏结构图的划分如图2 1 所示，从上至下划分为五层，分别为应用层、 汇聚层、资源层、连接层和构造层【z 引。 | 、 ，。t5 引”叫；，厂 应用层 聪戎代蟆! 谚；拆 3 剃i 挖簿 汇聚层 j 唆躲，j 越务。一l 资源与连接层 安仑游n 名争f m 、? i 溺i ，c 七扛；li ，i l jl f j ：s 了r 顼，p q 2 鼻，。? 构造层 图2 一l 五层沙漏结构分层图 f i g u r e2 - 1f i v el a y e r so fs a n d g l a s ss t r u c t u r e 网格的本质是支持动态虚拟组织中各种资源的共享和协作，即通过建立和组 织各种各样的分布式组件来创建并充分整合能提供各种q o s 服务的虚拟计算机系 统。2 0 0 2 年6 月，美国a r g o n n e 国家实验室的i a nf o s t e r 等人结合w 曲s e r v i c e 技 术提出开放网格服务体系结构o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 。在o g s a 1 6 中，一切都是服务，计算资源、存储资源、网络、程序、数据库等都用服务来表 达，从而使网格技术的共享特性在o g s a 中表现为对服务的共享。【1 4 l 相对于以协议为中心的五层沙漏结构，o g s a 是以服务为中心的j 眼务结构”。 f o s t e r 将服务定义为：具有特定功能的网络化实体。在五层沙漏结构的中心是被共 享的物理资源或者是这些资源所支持的服务，而在o g s a 中，服务所指的概念更 广，包括各种计算资源、存储资源、网络、程序、数据库等o g s a 最突出的思 想就是以“服务”为中心，在o g s a 框架中，将一切抽象为服务，包括计算机、程 序、数据、仪器设备等。这种观念有利于通过统一的标准接口来管理和使用网格。 服务数据的访问 撼嬲一黼 较麸态生命周期q 黜妣 绑定特性 叼嚣激髓 认迸 羰_ 豫i 龟媳l1 标准接订 通知 授枚 戬务俄建 驻势逢册 管理 开发 诵向转嬲应甩 的接口 图2 2 网格服务示意图 f i g u r e2 - 2c o n v e n t i o n a ld i a g r a ma b o u tg r i ds a i o e 8 网格服务通过定义接口来完成不同的功能，服务数据是关于网格服务实例的 信息，因此网格服务可以表示为网格服务= 接口行为+ 数据服务。如图2 2 。 2 1 3网格的应用现状 网格的应用领域目前有四类：分布式超级计算、分布式仪器系统、数据密集 型计算和远程沉浸。 1 4 1 分布式超级计算( d i s t r i b u t e ds u p e r c o m p u t i n g ) 是指将分布在不同地点的 超级计算机用高速网络连接起来，并用网格中间件“粘合”起来，形成比单 台超级计算机强大得多的计算平台。主要应用于军事、科学等高端计算的 需求。 分布式仪器系统( d i s t r i b u t e di n s t r u m e n t a t i o ns y s t e m ) 是指用网格管理分 布在各地的贵重仪器系统，提供远程访问仪器设备的手段，提高仪器的利 用率，大大方便用户的使用。例如，远程医疗、远程访问贵重仪器等。 1 7 数据密集型计算( d a t ai n t e n s i v ec o m p u t i n g ) 对应的数据网格更侧重于数 据的存储、传输和处理，而上面的计算网格更侧重于计算能力的提高。例 如欧洲的d a t a g r i d ，可用于物理、生物、医学、地球观察等学科海量数据 的分析。 远程沉浸( t e l e - i m m e r s i o n ) 是一种特殊的网络化虚拟现实环境。这个环 境可以对现实或历史逼真反映，可以实现高性能计算结果或数据库的可视 化，也可以是一个纯粹虚构的空间。“沉浸”的意思是人们可以完全融入其 中，各地的参与者通过网络聚在同一个虚拟的空间里，既可以随意漫游， 又可以相互沟通，还可以与虚拟环境交互，使之发生改变。 2 2 网格任务调度的目标 网格计算资源具有多方面的异构性，非常适合具有多种内在并行性的应用执 行。计算网格主要目标之一就是为用户提供高效的应用程序执行环境。将应用程 序调度到异构的计算节点上运行。获得最优或近优的性能指标是应用调度模型研 究的目标和方向【l l 】。 对于复杂异构的网格计算环境，任务调度由两部分组成。首先是资源匹配，即 找到最合适任务运行的资源；其次是次序调度，即决定哪个任务执行在先，哪个 任务执行在后。网格任务调度的目标与多处理机群系统的任务调度目标是类似的， 衡量调度性能的标准也基本吻合。就是要对用户提交的作业实现最优调度，并设 法提高网格系统的总体吞吐率。具体的目标包括：最优跨度、服务质量、负载均 衡、经济原则等【冽。 最优跨度。跨度是一个最主要、最常见的目标，它指的是调度的长度，也就是 从第一个作业开始到最后一个作业运行完毕所经历的时间。跨度越短就说明调 度策略越好。这一调度目标可以解释如下：假设有m 个任务t = t l , t 2 ，k ) 需要 调度到n 个资源节点m _ m l ，n 1 2 ， i i l n ) 上运行，任务t i 在m j 上的执行时间为q ， 在t i 开始执行之前的等待时间为锄。那么，任务调度的最优跨度目标就是求得 这样的一种资源匹配模式和一种任务执行次序，使得所有任务总的完成时间最 短，可表示为如下公式： 弋弋 、 m i n ? 乙( c u + 吩) ) ( 2 - 1 ) i e i a - ，j ，1 ) 胀 l ，k 棚 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题。网格系 统更进一步扩展了这个问题。网格作业调度是设计交叉域和大规模应用的，解 决好系统负载均衡是一个非常重要的问题。 服务质量。网格系统要为用户提供计算和存储服务时，用户对资源需求情况是 通过服务质量的形式反映出来的。作业管理与调度系统在进行分配调度作业时， 保障网格应用的服务质量是完全应当的。 经济原则。网格环境中的资源在地理上广泛分布的，而且每个资源都归属于不 同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原则， 不同资源的使用费用也应是不同的。市场经济驱动的资源管理与作业调度必须 使消费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久地发 展下去【1 8 1 。 网格的最终目的是要为用户提供一个高效的计算环境。本论文的研究重点放 在了最优跨度和负载均衡这两个面向用户，面向应用的性能标准上。 2 3 应用程序的网格任务调度模型 网格计算资源具有多样性、异构性、广域分布性和多管理域性。如果将全部 网格资源作为一个应用程序的调度和执行目标，可能因为通信延迟等问题，使得 调度变得十分昂贵和困难，而且执行效率也会下降。在网格计算系统下，应用程 序调度模型需要考虑应用程序的特性和机器特性。为不同的应用程序匹配不同的 计算资源，可以提高计算资源的利用率和应用程序的执行效率。图2 3 示出了网格 计算系统下的应用程序调度模型结构。 网格资源 图2 3 网格系统下的应用程序调度模型 f i g u r e2 - 3s c h e d u l i n gm o d e lo fa p p l i c a t i o np r o g r a m o ng r i d l ， 应用程序分析模块【2 1 】 应用程序分析模块有两大功能：应用类型分析和应用类度分析。通过对 1 9 应用程序的类型进行分析，可以确定应用程序的特点。粗略地可以将网格环 境下的应用程序分成三大类型，即计算密集型应用、通信密集型应用和计算 通信相对均衡型应用。通过对应用程序的类度分析，可以确定应用程序中并 行化任务的多少以及并行化任务的特点。应用程序分析模块的结果需要定时 地发布到“应用特性描述表”中。 2 ， 资源特性分析模块【2 l j 资源特性分析模块主要通过典型应用来分析机器对不同代码的执行效 率，得到机器对具有不同内在并行性任务的运行效率。另外，还可以通过检 测和分析机器使用的处理器结构、存储器性能和高速缓存特性得到机器特性 信息，并把它作为资源特性的一部分。 3 ，应用程序分解模划2 l 】 在网格计算环境中，要实现应用的透明执行，应用程序分解就变得非常 重要。在网格计算系统中，应用程序的分解涉及到任务并行粒度分析和应用 特性分析这两方面的结果。它是