（计算机应用技术专业论文）基于计算经济模型的网格任务调度策略研究.pdf

硕+ 学位论文 摘要 网格计算是分布式高性能计算的发展产物。利用网格技术，人们可以将原本毫无关 系的服务器、存储系统与网络联合在一起，组成一个超级计算系统，为用户提供高质量 的计算与信息服务，但是，在网格环境中进行资源管理和调度是个非常复杂的问题。 在网格系统中，大量地理上分布的各种资源为不同的组织拥有，这些组织具有不同 的使用规则、不同的计费模型、不一样的负荷能力和不同的使用模型；资源拥有者和资 源使用者各自具有不同的目标、目的、策略和需求，因此一些传统的资源管理和调度方 式在网格系统中并不适用。而将经济学引入到网格体系中，研究经济学的方法在网格任 务调度中的应用，是近年来网格任务调度领域的一个研究热点。 本论文对基于计算经济模型的网格任务调度框架进行了比较深入的研究。通过分析 现有框架的特点和不足，设计了一种层次型的基于虚拟市场概念的网格任务调度框架。 该框架利用树型分层结构解决同一网格体系中容纳多种经济模型的问题；在该框架的资 源代理中设计了一种价格调节器，资源负载的高低动态利用价格反应出来，同时价格的 浮动也动态影响资源的负载量，依此来解决资源负载平衡和传统网格任务调度器调度过 程中资源价格不可变的问题；并分析了信誉策略对调度的影响和该框架下任务调度的可 扩展性与自适应性。 在研究传统计算经济网格体系结构中的任务调度算法的基础上，本论文设计了一种 自适应的动态网格任务调度算法。该算法通过不断监测系统的负载平衡度，动态改变调 度策略，旨在同样的预算和完成期限约束下获得更高的任务调度成功率。通过在网格模 拟器c t r i d s i m 中的模拟试验，证明了该算法在同种条件下与传统的费用最优调度算法相 比能获得更高的任务调度成功率。 关键词：网格；经济模型；任务调度；g r i d $ i m 基于计算经济模型的网格任务调度策略研究 a b s t r a c t g i r dc o m p u t i n gi st h ep r o d u c to fd i s t r i b u t e da n dh i g h - p e r f o r m a n c 君c o m p u t i n g u s eg r i d t e e l m o l o g y , p e o p l ec o u l df o u n das u p e rs y s t e mo fn u m e r a t i o na f t e rc o n n e c t i n gw i t hs e r v e r , m e m o r ys y s t e ma n di n t e m e t r e s p e c t i v e l y t h i ss u p e rs y s t e mp r o v i d e sh i g h - q u a l i t ys e r v i c e a b o u tc o m p u t i n ga n di n f o r m a t i o n h o w e v e r , i ti sac o m p l e xu n d e r t a k i n gt 0m a n a g ea n d s c h e d u l er e s o u r c ei nt h e 鳓 i ng r i dc o m p u t i n gp l a t f o r m s ，t h eg e o g r a p h i cd i s t r i b u t i o no f1 e $ 0 u r c e so w n e db yd i f f e r e n t o r g a n i z a t i o n sw i t hd i f f e r e n tu s a g ep o l i c e s ，c o s tm o d e l sa n dv a r y i n gl o a da n da v a i l a b i l i t y p a t t e r n si sp r o b l e m a t i e t h ep r o d u c e r s ( r e s o u r c eo w n e r s ) a n d ( ：o n s u m e l s ( r e s o u r c eu s e r s ) h a v e d i f f e r e n tg o a l s ，o b j e c t i v e s ，a n dr e q u i r e m e n t ss ot h a ts o m et r a d i t i o nr e s 0 1 1 r c em a n a g e sa n d f o r m o fs c h e d u l i n gi sn o ts t t i t a b l eh e r e t ob r i n ge c o n o m yt og r i ds y s t e m ，a n dd or e s e a r c ho n h o wt ou t i l i z ee c o n o m yi n 鲥dj o bs c h e d u l i n g ，i sar e s e a r c ha t t r a c t i o ni nt h e 鲥dj o b s c h e d u l i n ga r e a 1 1 1 i sp a p e rd oad e e ps t u d ya b o u tg r i aj o bs c h e d u l i n ga r c h i t e c t u r eb a s e d0 1 1e c o n o m y m o d e l a n a l y s i so fc h a r a c t e r i s t i ca n ds c a r c i t yb yc u r r e n ta r c h i t e c t u r es e to u tah i e r a r c h i c a l g r i dj o bs c h e d u l i n ga r c h i t e c t u r eb a s e d0 1 1t h ec o n c e p to fv i r t u a lm a r k e t t h i sa r c h i t e c t u r et o s o l v et h ep r o b l e mo fk i n d so fe c o n o m i c a lm o d e l sm i x e di n0 1 1 1 e 鲥da r c h i t e c t u r eb yu s i n g h i e r a r c h i c a le o u e c - t i o no ft r e e s a u t h o rd e s i g nak i n do f p r i c ea d j u s t o ri nt h er c s o u l c , eb r o k e r a r c h i t e c t u r e u s ep r i c et or e f l e c tt h er e s o u r c el o a dd y n a m i cw h i c hh i g l lo rl o w a tt h es a m e t i m e , t h ec h a n g eo f t h ei e s o u i c ep r i c ea l s od y n a m i ci n f l u e n c el o a do f r e s o u r c e t h eu s eo ft h i s s o l u t i o nt ob a l a n c et h er e s o u r c el o a da n dt os o l v et h ep r o b l e mo f r e s o u r c ep r i c el l l e v e l c h a n g e d i nj o bs c h e d u l i n gp r o c e s so ft r a d i t i o n 鲥da r c h i t e c t u r e a u t h o ra l s oa n a l y s i st h es c h e d u l i n g i n f l u e n o f c r e d i t a b l es t r a t e g ya n dt h ea b i l i t yo f e x p a n da n da d a p t i v eu n d e rt h i sa r c h i t e c t u r e o nac l o s es t u d yo fs c h e d u l i n ga l g o r i t h mi nt r a d i t i o n a l 蛳dj o bs c h e d u l i n ga r c h i t e c t u r e b a s e de c o n o m y , t h i sp a p e rd e s i g na na d a p t i v ea n dd y n a m i cg r i dj o bs c h e d u l i n ga l g o r i t h m t h i sk i n do fa l g o r i t h md y n a m i cm o n i t o rl o a db a l a n c ed e g r e eo ft h i ss y s t e mi nt h ep r o c e s so f s c h e d u l i n gs ot h a tt og e th i g h e rr a t eo fs u c c e s so i lj o bs c h e d u l i n g t h r o u g ho u rs i m u l a t i o n t r i a lp r o v et h a tt h i sk i n do fs c h e d u l i n ga l g o r i t h mi m p r o v et h es c h e d u l i n gs u c c e s sr a t i oo f j o b s c o m p a r e dw i t ht r a d i t i o n a ld b c_costa l g o r i t h mi nt h es a l l l ec o n d i t i o n s k e yw o r d s ：g r i dc o m p u t i n g ；e c o n o m ym o d e l ；j o bs c h e d u l i n g ；g r i d s i m 硕十学位论文 插图索引 图2 1g l o b u s 调度系统设计6 图2 2c o n d o r - 6a g e n t 的实现7 图2 3n i m r o d - g 体系结构9 图3 1v m 框架结构1 6 图3 2 叶虚拟市场组成结构1 9 图3 3 虚拟市场资源代理架构2 0 图3 4 价格调节器相关实体事件图2 l 图3 5 价格调节启发式2 2 图3 6 虚拟市场服务代理结构2 3 图3 7 虚拟市场间的联系2 4 图5 1g r i d s i m 平台体系结构3 l 图5 2 资源性价比对调度成功率的影响3 4 图5 3 任务截止期对任务调度成功率的影响3 5 图5 4 预算对任务调度成功率的影响3 5 基于计算经济模型的网格任务调度策略研究 附表索引 表3 1 经济模型和分布式计算调度系统对照表1 4 表5 1 模拟资源参数表3 4 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成 果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：1 司年f 月p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权兰 州理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“4 ”) 作者躲 导师签名： 圜 日期：- ：滓 日期：噼 ，月p 日 ，月日 硕士学位论文 1 1 研究的背景和意义 第1 章绪论 网格( g r i d ) 是一种新兴的基础设施，它将从根本上改变我们思考和使用计算的方 式。网格这个词来源于可随时随地提供电能的电力网格( e l e c t r i cp o w e rg r i d ) ，人 们相信通过使信息技术基础设施中的所有成分，包括计算能力、数据库、传感器和人， 灵活共享成为真正的协作工具，导致新类型应用的出现。网格计算研究的问题与传统分 布式计算研究的问题很相似，但网格计算环境的资源分布共享、自治统一管理、异构和 强动态性等特性使得它与传统的分布式计算相比还有很多需要解决的问题。目前较成熟 的网格环境( 如g l o b u s ) 基本解决了异构资源支持、资源发现与协同管理以及网格上 的安全通信等最基本的问题。但保障网格性能的优化和服务质量的提高还有待进一步研 究。 网格任务调度与负载平衡“1 是提高网格性能和服务质量的关键问题，n i m r o d - g 、 a p p l e s 和c o n d o r - ( 等都是目前应用较广泛的网格任务调度器，但他们都基于特定的 调度策略，适用于特定情况的任务调度。所以至今对适应资源动态变化、能提高网格服 务质量的分布、快速、可扩展的网格任务调度方法的研究仍然是网格计算领域的研究热 点。 计算经济模型将经济的概念引入网格资源管理中，它应用了市场经济中的供求原则 来对资源的所有者和使用者进行调节以保证双方均获取最大利益。 网格环境中的资源管理和调度是个复杂的问题。在网格中，大量地理上分布的资源 为不同的组织拥有，这些组织具有不同的使用规则、不同的计费模型、不一样的负荷能 力和不同的使用模型，这些都是问题所在；此外生产者( 资源拥有者) 和消费者( 资源使 用者) 各自具有不同的目标、目的、策略和需求，这也会对网格中的资源共享产生影响。 由于网格的这些特点，一些传统的资源管理和调度方式在网格中并不适用。在网格环境 中使用经济学原理进行资源管理和调度是网格从理论研究向实际应用所必须跨越的一 步。 “基于经济模型的网格任务调度策略研究”这一课题就是在这种背景下确立的，旨 在探索一种能够适应多种经济模型并能很好的协调各方利益的网格任务调度策略。网格 任务调度问题属于网格资源管理中的一个重要问题，同时网格资源管理与具体的网格体 系结构又是紧密相关的。通过对这一课题的实施，对相关网格系统的结构和网格任务调 度器的结构进行了总结，对计算经济模型下基本调度算法进行了分析，同时提出了一个 基于计算经济模型的网格任务调度框架和一种自适应的网格任务调度算法，笔者认为本 基于计算经济模型的网格任务调度策略研究 课题的确立和完成将在网格调度领域做出一些有益的探索。 1 2 国内外研究与发展现状 网格作为一种异构计算环境，根本任务之一是根据各个资源节点的状态、网络通信 性能等参数，把不同的任务以合理的方式分配到相应的资源结点去完成，这也就是所谓 的任务调度，其任务调度决策直接影响网格应用的性能。任务调度在操作系统等领域进 行过很多研究，但由于网格环境中资源的多样性、自治性和动态性，使得网格环境下的 任务调度比传统环境下的调度要复杂得多，对传统的调度算法提出了新的挑战。 围绕着网格中的任务调度，国内外已做了许多研究工作，网格任务调度策略的研究 一种是针对元任务或者批任务开展，这种研究方式并不考虑任务间的数据关联与优先约 束关系【2 】；另种来源于传统的并行计算与处理中，针对有向无环图d a g ( d i r e c ta c y c f i c g r a p h ) 来表示的并行任务在多处理机上的调度研究，目前的研究不仅包含任务之间的通 信关系及代价，还要考虑调度环境的异构性带来的影响、链路竞争、网络拓扑结构的松 散易变性等问题。 当前，国内外的文献中，已经出现了很多关于网格任务调度的算法。这些算法按照 调度策略可以分为静态调度( s t a t i cs c h e d u l i n g ) 和动态调度( d y n a m i cs c h e d u l i n g ) 两种1 3 1 。静 态调度是把任务收集起来，等映射事件到来后才对这些任务进行集中映射。按网格调度 的度量依据主要有基于时间、经济【4 】以及其他度量指标( 如公平性、稳定性、健壮性等) 的调度，而动态调度是任务一到来就加以映射。静态调度算法主要有m i n m i n 5 - s ， m a x m i n i s - 7 ，s u i h g e | 5 1 ，x s u f f r a g e l 9 ，t c r ( w a n s f e rc o m p u t a t i o nr a t i o ) t l o 】等。静态调度 算法需要花费大量时间计算任务调度表，算法缺少灵活性，任何变化，如任务添加、删 除或任务特征变化，都需要重新计算调度表。而且静态调度算法每隔一定周期进行次 调度，因此，越早到达的任务等待的时问越长，从丽使得任务的响应时间过长；常见的 动态调度算法有m e t ( m i n i m u me x e c u t i o nt i m e ) t 5 】，m c t ( m i n i m u mc o m p l e t i o nt i m e ) 5 1 ， s a ( s w i t c h i n ga l g o r i t h m ) 川，k p b ( k - p e r c e n tb e s o ，o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g ) 1 ”。 相比之下，动态调度算法的环境适应性好，在多种环境下操作性能良好，算法灵活。因 此，动态调度算法更适合于网格环境。许多网格中间件，如c h i n a g d d 支撑平台 c g s p ( c h i n a g r i ds u p p o r tp l a t f o r m ) ，v e g a i 1 j ，c r o w n ( c h i n ar e s e a r c ha n dd e v e l o p m e n t e n v i r o n m e n t o v e r w i d e r - a r e a n e t w o r k ) h 2 ，g l o b u s t o o l k i t 等，也采用的是一种动态调度模 式。此外，还有将多种调度准则综合在一起的调度方法，如q o s ( q u a l i t yo f s e r v i c e ) 1 1 2 - 1 6 1 等。另外，根据调度算法所应用于任务调度的阶段，调度算法可分为应用于预处理阶段 的算法和调度及重调度阶段算法【1 7 1 。 在基于计算经济模型的网格任务调度算法中，最著名的是澳大利亚m o n a s h 大学 b u y y a 提出的基于两项经济学中最重要的q o s 需求，即任务截止期( d e a d l i n e ) 和预算 ( b u d g e t ) 的网格任务调度算法，这种算法在他提出的基于分布式、可计算的经济学的 硕士学位论文 g r a c e 4 1 网格资源框架下使用经济学模型进行资源调度和协同分配的工具集 n i m r o d g 【1 8 1 中运行。 1 3 计算经济模型在网格技术中的应用 1 3 1 计算经济模型在网格技术中的引入 在网格环境中进行资源管理和调度是个非常复杂的问题。在网格系统中，大量地理 上分布的各种资源为不同的组织拥有，这些组织具有不同的使用规则、不同的计费模型、 不一样的负荷能力和不同的使用模型：资源拥有者和资源使用者各自具有不同的目标、 目的、策略和需求阁，因此一些传统的资源管理和调度方式在网格系统中并不适用。而 在网格系统中采用层次型或分布型策略进行资源管理是比较好的方法1 1 9 1 ，在这种体系结 构中可以应用一些经济学模型进行管理并规范资源的需求1 4 j 在网格中引入计算经济模型主要基于以下理由【4 l 网：( 1 ) 现有的网格系统大多是为 了一些学术研究目的而开发的，在这些系统中强调资源的共享和协同工作，但是却没有 考虑到资源的价格因素。在实际应用中，大量的资源并不是无偿使用的，要吸引资源的 拥有者加入网格，就必须保证他们的利益。( 2 ) 网格是一个异构的、动态的分布式环境， 对资源的使用和资源的供应都是在不断地变化之中。通过引入经济学，特别是基于价格 的市场机制，由价格浮动来反映资源供需情况的动态变化，通过供需均衡实现资源优化 分配，能够很好地表现网格的动态特征( 3 ) 网格环境下的资源分配涉及到消费者( 资 源使用者) 、生产者( 瓷源拥有者) 的个体行为，使用微观经济学中的一些经济模型可 以与在其中的资源调度策略相配合。 1 3 2 计算经济模型在网格任务调度中的应用 在基于计算经济模型的网格任务调度策略中，围绕者资源的使用，一般都有两个重 要实体：资源拥有者和资源使用者。在经济环境下，资源拥有者会提供各种有竞争的服 务来吸引资源使用者递交自己的任务来使用自己的资源，因此在网格任务调度问题研究 中，资源拥有者又可称为服务提供者，而资源使用者也可称为任务提交者 基于经济模型的网格任务调度的实现侧重于将具体的资源管理和任务调度情境抽 象为数学模型，然后依据一定的经济学理论进行分析和模拟。如果从经济学的角度去看， 在计算网格的环境下，资源拥有者和资源使用者之间实际上是一种买卖关系，资源使用 者暂时的购买资源的使用权，资源拥有者暂时的出卖资源的使用权，也就是说，实际在 进行买卖的商品是资源的使用权。在这个过程中，服务提供者的目标是获取最大的利益， 而资源使用者的目标则是在自己的一些约束条件下( 例如完成时间、预算等) 获取尽可能 多且好的资源来满足自己的需求。因此通过类比实际生活中的某些经济行为，研究各种 经济模型的运行机制，然后结合计算网格资源分配和任务调度的特点进行一定的选择， 就可以帮助我们找出适合的，高效的经济模型以便应用到计算网格资源调度中去。 3 网格是一个异构的、动态的分布式环境，资源的使用和资源的供应都是在不断地变 化之中，通过引入经济学，特别是基于价格的市场机制进行网格资源分配有如下好处【2 1 l ： 首先，经济活动中的市场是一种基于分布自主决策的资源分配机制，即每个市场参 与方根据市场价格和自身偏好自主决策，而计算网格的资源分配恰好需要实现类似的分 布自主决策； 其次，关于市场机制的经济学理论给出了计算网格资源分配效率的精确刻画。计算 网格通常强调用户需求的异构性，此时以经济理论为基础的市场效率观点对于计算网格 的资源分配非常重要； 最后，市场机制通过价格浮动反映资源供需状况的动态变化，通过供需均衡实现优 化分配。这种动态协调的资源分配机制恰恰适合计算网格的动态特性，并且在此基础上 市场机制还能支持资源的联合分配。 1 4 论文所作的主要创新 在整个硕士论文期间，重点在基于计算经济模型的网格体系结构下，针对网格任务 调度策略方面做了一定的探讨，本文所作的主要创新在以下几个方面： ( 1 ) 提出了一种基于计算经济模型的网格任务调度框架，详细论述了框架的组成结 构和功能 c 酚设计了一种网格资源调度代理器。引入了价格浮动机制。 ( 3 ) 设计了一种自适应的动态网格任务调度算法，并给予了仿真实现和论证。 1 。5 论文的主要研究内容与组织 本文共分五章，结构如下： 第1 章，绪论。分析了关于网格任务调度策略研究的背景和意义，介绍了当前相关 领域的研究现状，介绍了本文的主要工作和章节安排。 第2 章，网格技术相关知识。从介绍网格的起源与基本概念开始，接着论述了网格 与相关网络技术的异同和通用的两大网格体系结构特点。然后介绍了在网格技术中引入 经济模型的技术，详细说明了七大经济模型和基于计算经济模型的网格任务调度问题， 并分析了网格任务调度中引入计算经济的特点和优势，同时对已存在的典型网格任务调 度器进行了分类和分析，介绍了它们采用的结构和技术 第3 章，一种基于计算经济模型的网格任务调度的策略。介绍了基于计算经济框架 下的著名网格资源管理器n i m r o d g ，并分析了不足之处，同时提出了一种基于计算经 济模型的网格任务调度框架，包括一个以虚拟市场为中心的网格体系结构，并详细介绍 了各个部分的结构和功能，提出了一种基于计算经济模型使用代理进行网格任务调度的 策略，并分析了调度的特点。 硕士学位论文 第4 章，基于计算经济模型的网格任务调度算法。分析了计算经济模式下，传统网 格任务调度算法的特点和不足，提出了一种自适应的动态网格任务调度算法。 第5 章，仿真试验。针对第五章提出的网格任务调度算法在g - r i d s i m 下进行了模拟 试验，分析、论证了算法的试验结果，对该算法进行了评价。 总结与展望。总结本文的工作，同时对未来的工作提出了一定的展望。 基1 二计算经济模鹊的网格任务调度策略研究 第2 章典型网格任务调度器与基本经济模型研究 2 1 典型网格任务调度器分析 2 1 1g i o b u s 中的调度设计 g l o b m 嘲项目是美国a r g o n n e 实验室等科研单位的研发项目。g l o b 哪对信息安 全、资源管理、信息服务、数据管理以及应用开发环境等网格计算的关键理论和技术进 行了广泛的研究，并开发出能在多种平台上运行的网格计算工具包软件( g l o b 璐 t o o l k i t ) ，能够用来帮助规划和组建大型的网格实验和应用平台，开发适合大型网格系 统运行的大型应用持续。g l o b 哪环境中包含的资源分配管理器g r a m ( g r i d u r c e a l l o c a t i o nm a n a g e r ) 和动态协同分配代理d u r o c 用来提供与系统相关的调度。 在o l o b 璐思想中，一个资源管理者提供一个访问界面来把任务提交到特定的物理 资源上，g r a m 负责远程应用的资源请求处理、远程任务调度处理、远程任务管理等 工作，负责对资源描述语言r s l ( r c s o u r s p e c i f i c a t i o nl 锄g u a g c ) 信息的解析工作，是网 格计算环境中的任务执行中心。如果要执行需要分布式资源的服务，则需要一个动态协 调分配代理( d u r o c ) 负责各个资源管理者之间的协同交互，而协同调度器必须提供 一个方便的界面来获得资源并在多个管理者之间执行任务。 g l o b m 调度设计如图2 1 所示。 圃 圃 圃 图2 1g i o b u s 调度系统设计 2 1 2c o n d o r - - 6 调度代理 c o n d o r - g 是威斯康星一麦迪逊大学的研究项目，是分布式计算环境c o n d o r 和网 格的结合。 c o n d o r 是一个高吞吐量计算环境，采用周期窃用技术能够有效地利用空闲的计算机 c p u 周期，c o n d o r 环境使用一种层次机器架构，为各种应用提供了强劲的、灵活的资 源管理服务。c o n d o r 环境中最重要的是c o n d o r 池，c o n d o r 池中存放的是资源，当用户 硕士学位论文 申请使用某些资源时，可以直接从c o n d o r 池中进行分配，不用再进行资源寻找、资源 定位等过程。 而c o n d o r - g 利用一个健壮的多功能的计算管理a g e n t 负责资源的发现、任务提交、 任务管理和错误发现，它的一个主要目的就是保存局部资源管理者的所有信息。 c o n d o r - ga g e n t 利用g l o b u s 相关网格协议( g r a m 、g a s s 、m d s 2 、g s i 等) 同网 格上计算机进行交互，利用c o n d o r 提供的机制去维护计算任务的整体信息。这样 c o n d o r - g a g e n t 可以代表用户的需求，在远程资源上进行客户所需要进行的计算任 务。a g e n t 为终端用户使用分散的资源提供了统一视图和一个熟悉可靠和简单的访问途 径，允许用户把整个网格当成一个完整的本地资源。 用户可以利用a p i 和命令行工具执行下列相关操作： 1 提交任务，为任务指定一个执行的名字、输入输出文件、相关协议等。 2 查询一个任务的状态，或取消某任务的执行。 3 通过诸如e - m a i l 的异步机制获悉任务的终止或其它问题。 4 能够访问提供任务详细历史情况的日志。 c o n d o r - g a g e n t 的实现如下面结构图2 2 所示。 c o n d o r - gs c h e d u l e r 对用户请求( 在网格资源上运行任务的请求) 做出反应，并为 用户创建一个新的g r i d m a n a g e r 进程负责提交和管理任务。一个g r i d m a n a g e r 进程负责 处理一个用户的所有任务，一旦该用户所有的任务都执行完成则终止该进程。每一次 g r i d m a n a g e r 任务请求( 经过修改后的两阶段提交g r a m 协议) 都会导致建立一个 g l o b u sj o b m a n a g e r 新进程，这个新进程必须与原g r i d m a n a g e r 进程应用g a s ss e r v e r 建立连接，以便传输任务的可执行程序和标准的输入文件、提供实时的标准输出流和执 行程序的错误。接下来，j o b m a n a g e r 提交任务给执行结点上的本地调度系统，本地调度 系统可能是基于 图2 2c o n d o r - ga g e n t 的实现 基于计算经济模型的网格任务调度策略研究 | ii 置鼍詈量曼曼曹量e 詈詈詈詈曼曼芭目曹奠量一 p b s 、c o n d o r 、l s f 、l o a d l e v e r 、n q e 等等。任务状态的更新通过j o b m a n a g e r 送回到g r i d m a n a g e r ，g r i d m a n a g e r 接着去更新c o n d o r - gs c h e d u l e r ( s c h e d u l e r 存储了 任务的连续状态信息) 。当一个任务开始执行的时候，建立了一个过程环境变量指向一 个含有监听( a s ss e r v e r 的地址的文件。如果g a s ss e r v e r 的地址要改变，有可能是 提交机器需要重启，g r i d m a n a g e r 请求j o b m a b a g e r 去用新地址更新文件。这就允许在 故障恢复后，任务能继续执行。 2 1 3a p p l e s 调度器 由加州大学圣迭戈分校开发的a p p l e s ( a p p l i c a t i o nl e v e ls c h c 训i n g ) 刚系统是一个 计算网格，它的侧重点是对于网格上具体应用的调度。a p p l e s 使用静态的和动态的应用 软件以及系统信息来选择一系列的可用资源，并进行资源配置。它可以与其它的资源管 理系统如g l o b u s ，l e g i o n 和n e t s o l v e g r i d s o l v e 互动，共同实施应用任务。a p p l e s 并没 有自行开发中间件，而是以o l o b u s , l e g i o n 和n e t s o l v e g r i d s o l v e 等系统提供的网格中 间件为基础进行开发。在一个a p p l e s 应用中居于核心地位的是a p p l e s 调度器，负责将 作业与资源匹配，应用单元的实际执行是由本地资源调度器来负责的。a p p l e s 调度器提 供的是“尽力服务”，没有服务质量保证。它具有启发式预测状态估计以及在线重调度 功能，同时具有固定的面向应用的调度策略，采用应用程序级的调度方法，一个a p p l e s 调度程序对应用程序来说是集中式的，用网络气象服务监测资源性能的动态改变情况作 为任务调度的依据，信息维护代价较高，且要求各节点间的连接都具有监测机制。 2 1 4n i m r o d - g 网格资源代理 n i m r o d - g 【2 5 】阴作为m o n a s h 大学研究的一个网格系统项目，引入了经济学模型用 于资源管理和调度，基于一个网格经济学架构g r a c e 动态地与资源拥有者代理进行交 易，以此选择合适的资源。n i m r o d g 是在g l o b u s 、l e g i n 等网格中间件系统提供的服 务的基础上建立的，这些中间件系统为安全和统一访问远程资源提供了一系列底层协 议，并且提供了访问资源信息和存储管理的服务。n i m r o d - g 采用应用程序级的基于微 观经济模型的调度方法，适用于各个资源的定价机制都很完整的情况，是这一类网格调 度的典型代表。 n i m r o d - g 模块和分层体系如图2 3 所示。 硕士学位论文 n i m r o d - g b r o k e r m i d d l e w m 图2 3n i m r o d g 体系结构 n i m r o d - g 体系遵循了沙漏型的设计模型，得以在其他中间件系统上面实现，并可 以使多用户应用程序使用它的服务。由图可见，n i m r o d - g 系统关键组件有嘲： 1 n i m r o d - g 客户机程序( n i m r o d - gc l i e n t s ) ，可以是： 创建参数扫描型应用的工具； 操纵与控制监控程序； 定制的用户应用程序( 如a c t i v es h e e t s | 2 8 ) 2 n i m r o d - ( 资源代理( n i m r o d - gb r o k e r ) 包括： 一个t a s kf a r m i n g 引擎； 一个实现资源发现，交易，调度的调度程序； 一个分配和激活程序，管理在资源上执行任务的代理。 n i m r o d - g 资源代理负责确定一个应用程序的具体要求，完成资源发现，调度，分 配任务给远程网格节点，开始并管理任务的执行，收集结果返回给用户节点。资源代理 的子模块有t a s kf a r m i n g 引擎，包含一个发现资源的网格浏览器的调度程序，还包含调 度算法的调度顾问程序，以及管理在网格资源上执行任务的代理。资源代理的子模块还 包括分配和激活模块，调度模块。运行代理的机器称为根节点，面对网格资源并且把用 户任务传递给排队系统执行的机器( 如集群的m a s t e r 节点) 称为看门节点，执行用户任务 的机器( 如集群的w o r k e r 节点) 称为计算节点。n i m r o d - g 网格资源代理是该系统的最关 键部分，而在资源代理模块中，至关重要的是交易管理程序( t r a d i n gm a n a g e r ) 和调度程 序( ( s c h e d u l ea d v i s o r ) 它的调度策略是面向应用程序的，并且是由用户定义的要求 d e a d l i n e 。b u d g e t 的限制驱动的。 2 2 七种基本经济模型 在网格市场，服务提供者( 资源拥有者) 和资源使用者( 用户) 各有他们自己的期 望和策略，并且可以在市场环境里初始化一个资源交易或参加一个协商。反映在微观经 基于计算经济模型的网格任务调度策略研究 济学理论中，不同的应用环境下有与之适应的不同的经济模型捌，消费者代理和服务者 代理一般存在以下七种相互关系： 2 2 i 商品市场模型 在这种经济模型下，资源拥有者指定资源的价格，并对用户按照使用资源的总量进 行收费。定价的策略可以基于多种参数，可以是固定价格的，也可以根据供求关系动态 变化价格。资源拥有者可以在网格市场目录上公布自己的资源信息。资源的信息可以包 括在不同时间对不同用户的价格等，例如比较简单的定价说明可以包括以下几个参数： 用户名，高峰期间价格，非高峰时间价格，午休时间价格，负载小于5 0 时的折扣，平 均负载高于5 0 时的价格等。 从传统经济学角度来讲，计算服务的定价应该基于生产的成本( 设备的价格) 和期 望边际利润( d e s i r e d p r o f i t m a r g i n ) 。但是，资源使用者对价值的直觉是供求关系，使用 的优先级和服务质量等。因此，在计算经济环境中，资源的价格应基于多个参数。 r e s o u r c ev a l u e = f u n c t i o n ( r e s o u r c es t r e n g t h , c o s to fp h y s i c a ll 镪o u r s s e r v i c e o v e r h e a d , d e m a n d ，v a l u ep e r c e i v e db yt h eu s p r e f e r e n c e s ) ) 其中包括资源的处理能力，设备的价格，需求等等。 这种货物市场模型中，网格资源代理主要完成以下几个任务： 1 识别出服务提供者。 2 识别出适合应用程序执行的资源，并确定它们的价格( 通过与网格市场目录和网 格交易服务交互) 。 3 选择能满足应用程序执行条件和用户目标的最优资源( 即满足预算和作业完成期 限的要求) 。选择资源时使用启发式算法和以往经验。把作业分配给选择好的资源。 4 使用资源完成作业并按照事先商定好的价格进行付费。 2 2 2 标价模型 标价模型( p o s t e dp r i c e ) 这种经济模型类似于商品市场模型，只不过资源拥有者广 播特定的报价以吸引消费者建立市场共享或者激发用户考虑较便宜的货位d o 。资源拥有 者这么做的目的是一方面可以在资源使用的低峰增加资源的利用率，另一方面可以用低 价吸引更多的新的使用者。此时，资源使用者不需要和网格资源提供者商议价，而是按 照标价来进行交易。这种经济模型的优惠价格是有使用条件的，但他们有可能会对某些 用户有吸引力。例如在假日期间，资源的需求可能减少，而网格资源提供者能够广播， 张贴优惠的标价来吸引消费者以提高资源利用率。标价模型的有关活动是： ( 1 ) 服务提供者在资源市场目录中公布他们的服务标价和条件等； ( 2 ) 资源使用者查看资源市场目录，识别任何这些标价服务是否可用并且符合其要 求； ( 3 ) 资源使用者代理询问这些标价服务是否可利用。 硕士学位论文 ( 4 ) 其它的步骤和商品市场模型相类似。 2 2 3 议价模型 在前两个模型中，都是资源服务提供者制定价格，资源使用者按照资源提供者制定 的价格来付费。而在议价格模型里面，网格资源代理和网格资源拥有者可以共同商议资 源的价格。通常网格资源代理会以一个比较低的价格开始，资源拥有者会以一个比较高 的价格开始，双方不断协商直到互相达成一个共识或有一方不愿继续协商为止。前提条 件是资源使用者的任务的完成期限( d e a d l i n e ) 很宽裕，此时网格资源代理就可以大胆的放 弃一些较贵的资源，而把时间花费在价格的协商上面。这种模型中的协商是在使用者要 求的引导下进行的，代理可以尽可能为更便宜的价格进行协商，它们可以丢弃昂贵的机 器，这将会降低资源的使用率，会造成资源利用率的下降，而资源拥有者为了提高资源 利用率，往往会降低一些价格。当市场的供求关系和服务价格都不明朗时，资源使用者 代理和资源服务提供者通常通过会使用这种经济模型。 2 2 4 投标合同模型 投标，厶同模型是分布式问题解决环境里服务协商采用的最广泛的模型之一【3 1 1 。它 模拟商业上常用的制定合同的机制来控制货物和服务的交换，帮助寻找最适合于任务执 行的资源。资源使用者或网格资源代理在这里充当了经理的角色，而资源拥有者或者服 务提供者则被叫做投标者。 从资源使用者的角度来看，投标的过程是： 1 资源使用者( 或网格资源代理) 使用一个交易模版宣布自己的需求并从资源拥有 者当中邀请投标者； 2 有兴趣的资源拥有者评估资源使用者的需求，并且通过提交他们的投标作出回 应； 3 网格资源代理评估合同并把任务分配给最合适的资源； 4 网格资源代理和资源拥有者单独通信，并使用资源。 从资源提供者的角度来看，投标的过程是： 1 从网格市场目录那里接收招标广告； 2 评估自身服务能力以及是否满意该合同； 3