（计算机软件与理论专业论文）基于市场经济的多目标资源分配方法研究.pdf

摘要 网格是一种新兴的基于i n t e r n e t 的分布式并行处理框架。它能跨 多个管理域组织或企业进行资源发现、资源管理、信息交换和资源共 享。网格资源管理系统是网格计算的重要组成部分。由于市场机制经 济学理论对资源分配代价进行了精确描述，而网格强调了用户需求的 异构性，因此，采用以经济理论为基础的多目标线性规划模型来分析 和讨论网格资源分配是非常具有研究意义的。 本文在市场经济模型的基础上，利用网格的多任务多目标特性进 行资源分配，建立了具体的线性规划模型。该模型不但满足了用户要 求，而且还提高了资源分配效率。与此同时，本文还在任务调度中使 用了组合优化模型。根据不同任务的要求和代价，用组合优化算法动 态组织任务在资源端的分布，充分利用网格资源，提高资源利用率。 最后，本文总结了资源管理的分配策略和定价策略。把线性规划 模型与博弈论相结合，在组合优化模型中应用福利经济学来提高系统 的工作效率，优化系统模型。本方法在保证了服务质量的前提下，进 一步提高了系统利润，是运筹学和经济学在现代网格资源分配研究中 的一个典型应用。 关键词网格资源分配，市场经济模型，线性规划，组合优化，博弈论 a b s t r a c t g r i d ，b a s e do np a r a l l e la n dd i m i b u t e dc o m p u t i n g 也e o r ) r ，e m e r g e sa sa n e wi i l 触s t m c t u r eo fi n t e m e tc o m p m i l l g t l l l o u 曲d i s c o v e r i n g 卸d m a i l a g i n gd i 脆r e n tr e s o u r c e si i lt h e 鲥d ，i tc a ns h a r ea i l de x c h a n g em e s e d i s t r i b u t e dr e s o u r c e sb e t w e e n m u l t i p l e 弛i n i s t r a t i v ed o m a i n ， o 唱a n i z a t i o n s a i l de n t e r p r i s e s m e a n w h i l e ，鲥dr e s o u r c ed i s t r i b u t i o nm o d e l p l a ya i li m p o r t a j l tr o l ei nt h es y s t e m f o rm e a c c u r a t ed e s c r i p t i o no f 鲥d s r e s o u r c ed i s t r i b u t i o ni nm a r k e tm e c h a i l i s me c o n o m i c s 协e o 哆a n dm e e m p h a s e so fu s e r s d i f 托r e n tr e q u e s t sm a t a r eg i v e ni n 鲥dt h e o 哆，hw i l l b es i g n i f i c a n tt os t u d yt h em u l t i - g o a li i n e a rp r o 乒籼i n gm o d e lb a s e do n t h et h e o 搿o f m a r k e t e c o n o m y t h el i n e a rp m 伊a m m i n gm o d e ld e s c r i b e di i lt l l i s p 印e rm a i n l y d i s c u s s e dh o wt os a t i s 8u s e r s m u l t i t a s ka n dm u h i g o a lr e q u i r e m e mi i l m a r k e te c o n o m ye n v i r o 啪e n t t h i sm o d e lc 锄o to i l l ys a t i s 匆u s e r s r e q u e s t s ，b u ta l s or a i s er e s o u r c ed i s t 曲u t i o ne m c i e n c yo f 鲥ds y s t e m a t t h es 锄et i m e ，m i sp 印e ra l s od i s c u s s e d 协s ks c h e d u l i n gp r o c e s sw i t h c o m b i n a t i o no p t i m i z em o d e li nt h i sw a y ，w ec a nd i s t r i b u t et h e s et a s k st o m e 西da c c o r d i n gt a s k s r e q u i r e m e ma n dc o s t ，w h i c hi m p r o v et h e r e s o u r c eu s a g ei na ne m c i e n tw a y a tl a s t ，n l i sp 印e r 西v e sm er e s o u r c ed i s 仃i b u t i o np o l i c ya n dt h e r e s o u r c e p r i c ep o l i c y i nas u m m 撕z a b l e w a y i ti n t r o d u c e dm e c o m b i n a t i o nm o d e lo fl i n e a rp r o g r 锄m i n gt h e o 哆a n dg a m ep l a y i n gt h e o r y t h r o u g hi n t e g m t i n gt h e w e l f h r ee c o n o m i c sm o d e lw i t l lc o m b i n a t i o n o p t i m i z em o d e l ，w ec a i lg e tab e t t e rm o d e lo fr e s o u r c ed i s t r i b u t i o na n d i i n p r o v em es y s t e me f f i c i e n c y i nt h ee n d ， w ec a np r o v i d es o m en u m e r i c r e s u l t t o p r o v e t h a t w ec a n b r i n g m o r e p r o f i t i l l l e g r i d a n de n s u r ea b e t t e r q u a l 埘o fs e r v i c e k e yw o r d s黟i dr e s o u r c ed i 嘶b u t i o n ，m a r k e te c o n o m ym o d e l ， l i l l e a r p r o g m m m i n g ，c o m b i n a t i o no p t i m i z i i i g ，g 锄ep l a y i n gt i l e o r y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：i 螫亟豳日期：述年上月卫日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 名：觚糯名删吼龇月上 硕士学位论文第一章绪论 1 1 研究背景 第一章绪论 今天，人类正在以空前的热情对自然、宇宙和生命进行探索，探索的规模也在 不断地扩大。随着高性能应用需求的迅猛发展，单台高性能计算机已经不能胜任一 些超大规模应用问题的解决。这就需要将地理上分布、系统异构的多种计算资源通 过高速网络连接起来，共同解决大型应用问题，即广域高性能的元计算技术，也称 为网格技术【l 】。目前国内外研究机构对网格技术的研究已取得了重大进展。已提出 了体系结构、协议标准，开发了网格中间件，并以此搭建了许多实验平台。许多部 门正研究开发适合本行业的应用网格，如信息网格、制造网格、医疗网格等。总的 来说，网格正从基础理论研究阶段逐步走向应用开发阶段。 网格资源分配在网格中起着重要作用，它为其它的网格中间件提供必要的与资 源有关的性能数据，是资源发现和任务分配的基础，是网格系统进行性能调整和错 误发现的依据。但是，在网格步入应用阶段的今天，网格资源分配暴露出诸多不足， 如【2 】：( i ) 分配资源的种类和目标比较单一，主要包括主机性能和网络状态的信息等， 缺乏用户的任务对资源的具体要求，资源的利用率比较低；( 2 ) 主要的服务对象是网 格系统本身，缺乏对用户的服务，缺乏有质量保证的任务的执行。据此，本文进行 了一系列的研究，弥补了网格资源分配的以上不足之处，适应了网格应用开发阶段 的新要求。 1 2 研究现状 1 2 1 网格资源管理系统的研究状况 网格资源管理系统作为网格系统的重要组成部分，正日益得到广泛而深入的研 究。目前国际上许多著名网格系统的资源管理系统一般在体系结构模型上可归结三 类：层次模型、抽象所有者模型和市场经济模型，在具体的资源管理实现和任务调 度策略方面却各不相同，此处简单介绍其中比较突出的几例： 硕七学位论文 第一章绪论 ( 1 ) g l o b u s 【2 均资源管理系统：由美国a r g o n n e n a t l o n a ll a b o 翔t o f y 开发的网格计 算工具，由一系列实现基本服务的组件构成，包括安全、资源定位、资源管理、数 据管理、资源预留和通信等。它的资源管理体系结构采用典型的层次模型，实现了 层次模型的大部分被动组件和宅动组件；资源描述与访问采用可延展模式模型、层 次名空间、软q o s ( q u a l t y o f s e r v i c e ) 、网络目录存储、分布式基于查询的发现、周 期性推送分发等；在任务调度方面，提供较低级服务，支持上层资源分配或协同分 配( 其中包括资源预留) ，提供高级工具执行调度等。g i o b u s 系统对任务监控的支持 不够，缺乏对任务状态及运行惰况的报告，缺乏友好的客户端。 ( 2 ) r o n d 【2 】的资源管理系统：由美国普渡大学开发的面向对象的网格计算中间 件系统。其资源管理体系结构也是采用层次模型；资源描述与访问采用可延展对象 模型、图式名空间、硬q o s 、基于语言的对象存储与通信、基于代理的发现、周期 性推送分发等；在任务调度方面采用分布式调度器、可预测价格模型、在线重调度 方法、固定的面向应用的调度策略等。 ( 3 ) n i m r o d 【2 l 的资源管理系统：由澳大利亚的m o n 嬲h 大学开发的针对参量研究 的用来管理资源和调度应用自动执行的网格资源代理。它的资源管理体系结构采用 典型的市场经济模型；资源描述与访问使用由底层g l o b u s 或l e g i o n 中间件服务所 提供的资源模型、依赖于计算结点的可用性、提供软和硬q o s 等；在任务调度方面 采用由计算经济和截止期限所驱动的应用级调度策略，遵循层次的、分布式的调度 模型等。 ( 4 ) l e g i o n 【2 】的资源管理系统：提交任务的l c g i o n 工具可监测任务对象，但是 它们返回给用户的信息很有限。只有当用户指定特定的任务运行在特定的主机上， 并且用户正好拥有那台机器的帐户，则用户可以登录到那台机器，使用传统系统可 提供的工具来监控任务的执行过程。如果用户提交任务，但不指定该任务该在哪台 机器上执行，则用户不能获得任何与该任务有关的信息。 ( 5 ) 欧洲d a t ag r i d 【3 l 的资源管理系统：在网格资源分配研究方面，d a t ag r i d 可 以说走在前列，主要体现在：它将网格资源分配理论网格分配结构得以实现， 使用起来更灵活。d a t ag f i d 研究开发的l b ( l o g g i n g 锄db o o k k e e p i n 曲为用户提供 了对任务的有效管理服务。l b 提供的服务包括三方面：l 0 9 9 i n g 是为任务调度系 统存储长期信息的网格服务；b o o k k e e p i n g 是为当前的活动任务存储短期信息的 网格服务；a c c o u n t i n g 即记帐，提供对资源消耗统计的网格服务。 在对用户的服务方面各个系统的资源管理系统也有所区别： g l o b u s 【3 l ：用户可通过命令方式或使用l d a p ( l i g h td i r e c t o r y a c c e s sp r o t o c o i ) 浏 2 硕士学位论文第一章绪论 览器获取并查看资源信息，但是这些查看方式死板且不直观，还不能满足用户的需 要。并且只有在安装了g l o b u s 的计算机上才能查看。总之，g l o b 峭缺乏对用户友 好的信息服务方式。 d a t ag r i d 【4 】( 欧洲) ：也是通过命令的方式查看资源信息。对资源的分配也是使 用g l o b u s 的技术实现的，所以也只能使用l d a p 命令或l d a p 浏览器查看资源信 息。 n i m r o d j ：该系统提供了图形工具能帮助用户查看任务的执行过程，如有必要 还可以停止任务。但该系统没有提供方法以访问中间文件或者提供传统意义上的输 入文件，这些功能必须用户直接登录到系统并使用传统工具。 织女星网格【5 】：为用户开发了图形界面的客户端程序，可实现对多种节点类型， 例如网格系统、网格服务器进行选择性查看。该客户端程序可运行于w i n d o w s ，l i n 吼 等多种操作系统之上。 目前，对资源分配研究还处于起步阶段，还没有形成一个公认的行之有效的解 决方法。一些网格系统对资源分配和任务得调度进行了尝试，在一定程度上能实现 部分功能。 1 2 2 基于市场经济模型的资源分配模型研究状况 由于当前网格用户社区和网格技术仍然处于发展初期，商业性的网格还没有被 很好地接受和建立。网格能实现多种分布式计算资源的虚拟化，如处理过程、存储 容量、数据和网络带宽，从而创建一个单一的虚拟系统，进而为用户和应用提供对 大量i t 功能的无缝访问。迄今为止，使用网格来解决大规模计算问题的思想还局限 于科学领域，远远没有走入寻常社会生活中。我们需要合适的方法使得这个虚拟组 织的各个成员能够有效地共享各种资源，经济模型是帮助他们管理和评价资源分配 的一个有效手段。 在经济学中，术语“经济学”被定义为社会科学的一个分支，用来处理货物的 生产、分配、消费、服务以及它们的管理。经济领域存在大量的经济学理论包括微 观经济学和宏观经济学原理，可以在网格计算环境里进行服务价格协商、出售货物 和服务以实现资源分配的，常用经济模型主要包括【6 】： ( 1 ) 议价模型 ( 2 ) 招标合同网模型 ( 3 ) 拍卖模型 ( 4 ) 经济学理论在网格环境中的模型 3 硕十学位论文第一章绪论 ( 1 ) 议价模型嘲：资源需要者( r r ) 和资源代理服务器( r s p s ) 进行议价以获得双 方都满意的交易价格。r r 和资源提供者( r s p ) 都有他们自己的目标函数，只要目标 吻合，他们就互相协商。r r 可以以一个十分低的价格开始协商，而r s p 从一个较 高的的价格开始协商，直到他们到成一个相互满意的价格，或者其中之一不愿意任 何更进一步的协商。当市场供求关系和服务价格没有清晰地建立时，经纪人和r s p 往往使用议价模型来建立贸易关系。人类社会中劳资、房屋市场等往往也采用议价 模型来进行交易。 议价模型的缺点：一但价格在一定的时期内固定下来，它就保持不变无论服务质 量如何变化，也即它对供求变化不敏感，而在市场经济模型中，价格变化一般取决 于供求变化，应用范围比较窄。 ( 2 ) 合同网模型m l ：它是分布式问题解决环境里服务协商采用的比较广泛的模 型之一。它模拟商业上常用的制定合同的机制来控制货物和服务的交换，为给定的 任务寻找一个合适的r s p 。在合同网模型里，要求任务被分配的用户或r r 一般称 为称为经理人，能够运行任务的资源或r s p 被称为潜在的承包人。 用于公告的交易样板的内容包括：收信人( 用户) 、合格的需求定义( 例如，需要 w i n d o w s 操作系统、l g 存储空间和1 2 8 m b 内存) 、任务与服务抽象、用户愿意投 资的可选价格、投标定义( 定单应该包含什么) 、期满时间( 接收投标的最终期限) 。该 协议存在一个限制是经理人没有义务通知潜在的承包商已有人中标，这就使得某些 情况下，承包人会向已制定合同的经理人回应投标。 该模型也存在一些缺点，一个经理人有时候接收不到投标，因为如下原因： 有潜在的r s p 忙于其它任务； 潜在的r s p 是空闲的但是优先级较低，不在考虑中； 没有r s p 有提供服务的能力，比如说资源是基于w i n d o w s n t 想要l i n u x 。 虽然有解决的方法，但是还不够完善。 ( 3 ) 拍卖模型：是最为广泛使用的资源分配经济模式，近年来电子商务、自动交 易系统等的迅速发展使得拍卖理论得到了广泛的研究和使用【8 】。拍卖人设置消费者 和供应者能接受的拍卖规则。基本上，拍卖使用市场力为服务协商一个出清价格。 在现实世界中，拍卖被广泛使用。三个与拍卖有关的关键角色是：资源所有者、拍 卖人( 即仲裁入) 和购买者。在网格环境中，供应者可以使用拍卖协议来决定服务的 质量与价格，拍卖过程的步骤是： r s p 宣布他们的服务并且邀请投标； 经纪人提供他们的投标( 开放或是封闭式拍卖决定了他们是否能了解其它消 4 硕士学位论文第一章绪论 费者的投标) ； 步骤继续，直到没有人愿意支付更高的的价格，或者由于最低价格线或所 有者任何其它具体要求没有达到，拍卖人停止拍卖； r s p 将服务提供给胜利者； 消费者使用资源。 拍卖模型有许多要完善的问题，比如： 要多大的频度重复拍卖过程； 多个相关商品如何被售出； 哪些人会出价； 是否某些出价人能得到特殊对待； 出价人是否有多个机会提交出价； 拍卖过程中价格应如何移动； 哪些信息可以在出价人公布； 获胜的出价人如何付费等。 ( 4 ) 经济学理论在网格环境中的模型：目前的一些研究项目基于这些早期成果对 于在网格中使用经济学原理进行资源管理进行了进一步的探讨。一些研究倾向于设 计一些可扩展的市场模型或者是市场机制，其中包括各种相关的经济学模型，为分 布式系统中的资管理提供一整套可行方案。 n r b o g 柚唧中使用市场机制行处理器时间分配，并提出了基于每个时间单元的 处理器租用协议。f u l b 在基于现实中的自由竞争市场、期货市场、现货市场建立了 提供q o s 支持的机制用于分布式资源分配，并且在此基础上提出了对网络带宽进行 交易的带宽市场机制和一个用于资源查找的算法。s e m r e t 在基于期货市场和现货市 场设计了一整套市场机制用于网络资源拍卖和许可证管理。这些研究在理论和模型 方面研究十分深入，但是缺乏具体实现。 g o m m e o 是美国田纳西大学的研究项目，使用市场经济学在网格中进行动 态资源分配。项目负责人提出，资源的相对价值是根据供需变化而变的，给出了c p u 资源和磁盘资源的价格公式，并讨论了关于价格调整的问题。g c o m m e r 只是给 出了模拟结果，并没有具体实现。 g r i d b 吣是澳大利亚m o n 船h 大学的b u y y a 基于早期对市场机制在分布式系统中 的应用研究成果，深入探讨了网格环境中的基于经济学的分布式资源管理和调度问 题，并设计了一系列应用组件构架的一个网格经济学框架g i 认c e 。 g l 认c e 是一个基于多种经济学模型之上的分布式的、可计算的经济学体系框 硕七学侍论文第一章绪论 架，用于在网格环境中进行资源交易。由于目前的一些网格系统如g 1 0 b 吣、b 瞎i o n 等已经提供了大量的、成熟的、可重用的中间件，例如资源协同分配服务d u r o c 、 认证和安全服务g s i 等等，所以g r a c e 没有重新搭建一个网格平台，而是在g l o b 喁 之上进行了扩展，补充了一些负责资源交易的中间件如网格市场目录g m d 、网格 交易服务器g t s 和用于电子支付的g b a n k 等等。 影响经济模型的因素很多，在竞争的国际市场中，影响价格的设置有多种因素。 供求关系是最普通的一个，但是实际的计算市场里，资源往往具有多个参数，消费 者对资源的请求一般附带有必须满足的参数，这些参数对资源的价格会产孛影响。 在经济学方法中，采用经济模型分配资源有着许多独特的优点，动态的资源配置提 高了系统的自适应性，采用经济原则能够鼓励资源拥有者贡献他们的空闲资源并从 中获利，有助于建立大规模的网格系统。 1 3 研究内容 本文主要研究如下内容： ( 1 ) 进行网格资源分配方法与策略的研究，在原有基础上增加了经济学理论； ( 2 ) 研究面向网格用户的市场经济资源管理服务系统，用线性规划模型进行资 源分配服务； ( 3 ) 研究组合优化模型在资源端的应用，提高资源端的利用率。 1 4 研究意义 在人类迈入知识经济时代的今天，如何将网络上分散的局部自治的众多资源有 效聚合起来，形成巨大合力，达到现代创新设计新体系是一项具有重大战略意义的 工作目的。如何将网络上分散的局部自治的众多资源有效聚合起来，形成巨大的合 力，使人们在任何地方、任何地点、任何时间都可以获得高效的设计服务和信息服 务，对于构建现代创新设计模式，乃至提高一个国家在知识经济时代综合竞争力都 具有特别重要的战略意义【m 】。 建立国家现代刨新设计新体系，构建资源的合理有效分配环境必不可岁。只 有构建基于网格的需求资源的合理分配才能将网络中分布的各种资源聚合起来，形 成巨大的综合效力，实现各种独立资源的广泛共享，才能有效协调各个资源，达到 各个资源之间的合理分工，最终保证网络客户的工作的顺利进行。 硕士学位论文 第一章绪论 网格是下一代的i n t 哪e t ，是当前国内外的研究热点。美国福布斯【1 2 1 曾预测， 网格将在2 0 0 9 年至2 0 1 1 年成熟，届时万维网将升华为网格。国家。8 6 3 ”1 1 3 1 计划 为此成立了专项，由中科院计算所牵头，联合曙光等国内知名企业着手研究网格的 关键性技术，包括网格结点、宽带网络系统、资源管理和任务调度工具以及应用层 的可视化工具等方面。有了网格计算，那些没有能力购买价值数百万美元的超级计 算机的机构，也能利用其巨大的计算能力。因而以现代网格系统设计作为应用目标， 研究网格在各个方面的应用需求，对现代科技有重大的意义。 1 5 论文章节设置 本论文简单介绍了网格、网格的发展，重点介绍了基于市场经济模型下线性规 划模型中的应用研究。全文正文主要分为六个章节。 第一章主要介绍本论文的研究背景和国内外在网格资源管理方面的研究现状， 以及论文的研究意义。 第二章着重介绍网格资源管理系统的工作流程，同时对网格技术和资源管理的 基本理论以及市场经济模型的网格资源管理模型组件的功能做了清晰的解释。 第三章主要分为两大部分。第一部分提出了一种新的资源分配方法，通过组建 多目标线性规划模型来解决基于用户多个目标函数的问题，适应网格中多任务多目 标的资源分配方式，该模型不但可以满足用户的要求而且提高资源分配的效率。第 二部分提出了在资源端运用组合优化模型来组织执行任务，加快任务执行的速度， 提高资源的利用率。 第四章为本文的核心，首先介绍了基于市场经济模型下的线性规划模型的体系 结构，然后进一步进行线性规划模型的研究，提出线性规划模型和博弈经济学理论 得综合应用，以及福利经济学理论在组合优化模型中的应用。 第五章通过模拟实验，分析实验数据，通过和拍卖模型的对比证明线性规划模 型的优越性。 第六章对所作研究做了总结并提出了未来的工作方向。 硕士学位论文第_ 章网格计算与资源管理概论 第二章网格计算与资源管理概论 2 1 网格计算概论 随着人们日常工作中遇到的计算越来越复杂，如计算机仿真、建模、分析等， 人们越来越需要数据处理能力更强大的计算机，而超级计算机的价格显然阻止了它 进入普通人的工作领域。于是，人们开始寻找一种造价低廉而数据处理能力超强的 计算模式。在计算机网络飞速发展的今天，人们自然会想到通过网络来着子解决问 题。目前因特网上存在着严重的资源浪费现象，据估计，有7 5 的c p u 时间和8 0 的服务器资源处于闲置状态。所以说，有难以数计的闲置资源等待着我们去开发利 用。但是，网络上纷乱复杂的各种资源和系统缺乏高效率的组织，处于一种混乱无 序的状态，没有结合成一个整体，资源的潜在能力未能得到充分的发挥与利用，未 能提供各种高效的计算服务和信息服务。如何将网络上分散的局部自治的众多资源 有效聚合起来，形成巨大的合力，并充分释放出来，使人们在任何地方、任何地点、 任何时间都可以获得高效的计算和信息服务，这正是从上个世纪9 0 年代中期开始， 计算机界着于研究和开发的基础结构，称之为计算网格( c o m p u 协t i o n a lg r i d ) ，这种 新型的计算模式称为网格计算( g r i dc o m p u t i n g ) 【。 2 1 1 网格计算概念 计算网格或简称为“网格”是指一个基础结构，它能使得综合、协调地使用被 不同组织所占有或管理的计算机、网络、数据库和科学手段成为可能。它将因特网 上闲置的资源以灵活的方式组织起来，形成虚拟的超级计算机。术语“网格”( g r i d ) 来源于对供电系统的称呼。称供电系统为“电力网格”，意指它分布广泛普遍和持续 稳定的能量供应。计算网格也具有以上类似的特点，它“供应”的是计算能力和其 他的服务。 网格计算是从元计算( m e t a c o m p 嘶n 曲的概念发展来的【1 5 1 。元计算被定义为通过 网络连接强力计算资源，形成对用户透明的超级计算环境。网格计算更系统化地发 展了最初元计算的概念，它通过网络连接地理上分布的各类计算机，包括机群、数 硕 学位论文第二章网格计算与资源管理概论 据库、各类设备和存储设备等，形成对用户相对透明的虚拟的高性能计算环境。其 应用包括分布式计算、高吞吐量计算、协同工程和数据查询等诸多功能。网格计算 被定义为一个广域范围的无缝的集成和资源管理计算环境。网格计算模式已经发展 为连接和统一各类不同远程资源的一种基础结构。 2 0 0 2 年7 月，i 锄f o s t 盯发表文章，就如何看一个系统是不是网格提出了三点 判断标准【1 6 1 ；第一，不带集中控制的资源共享和协同工作；第二，使用标准、通用、 开放的协议和接口；第三，高服务质量，包括响应时间、流量、可用性和安全性。 基于因特网的计算网格支持属于不同管理域的计算机节点参与计算和资源共 享。因此，一个性能优良的网格计算系统必须具备以下特点： ( 1 ) 具有单一映像空间：单一映像空间可以屏蔽硬件边界，实现异构数据的格式 转换，提供虚拟文件服务，把分散在各地的主机节点映射成一个统一入口的虚拟机 器。 ( 2 ) 支持节点自治：参与计算的节点可能属于不同的管理域，计算网格必须保证 各个节点的自主权。 ( 3 ) 支持高效安全与容错：网络安全包括信息安全与系统安全两个方面；网络容 错支持例外处理、软件调试与排错。 ( 4 ) 包含统一的资源管理：计算网格通过中间件来保证异构硬件和软件的互操作 性，进行资源的统一管理和调度。 ( 5 ) 协同工作：很多网格结点可以共同处理一个项目，能够自动进行计算、优化、 组织、协调。而这对于用户是透明的，用户的感觉像是在使用一台机器处理事务。 2 1 2 网格系统的组成与基本功能 网格计算环境的构建层次从下至上依次为： ( 1 ) 网格结点：由分布在1 1 1 t e m e t 上的各类资源组成，包括各类主机、工作站甚至 p c 机，它们是异构的，可运行在u n i x 、n t 等各种操作系统下，也可以是上述机型的 机群系统、大型存储设备、数据库或其他设备。 ( 2 ) 中间件：是网格计算的核心，负责提供远程进程管理、资源分配、存储访问、 登录和认证、安全性和服务质量( q o s ) 等。 ( 3 ) 开发环境和工具层：提供用户二次开发环境和工具，以便更好地利用网格资 源。 ( 4 ) 应用层：提供系统能接受的语言。可配置其他一些支持工程应用、数据库访 问的软件，还可提供w e b 服务接口，使用户可以使用w 曲方式提交其作业并取得计 9 硕l = 学位论文第一二章嘲格计算与资源管理概论 算结果。 最根本的要求，网格计算至少需要具备三种基本功能，任务管理、任务调度和 资源管理【l ： ( 1 ) 任务管理：用户通过该功能向网格提交任务、为任务指定所需资源、删除任 务并监测任务的运行状态。 ( 2 ) 任务调度：用户提交的任务由该功能按照任务的类型、所需资源、可用资源 等情况安排运行日程和策略。 ( 3 ) 资源管理：确定并监测网格资源状况，收集任务运行时的资源占用数据，而 且，网格计算环境要求不影响各结点本地的管理和自辛性，不改变原有的操作系统、 网络协议和服务，保证用户和远程结点的安全性，允许远程结点选择加入或退出系 统，尽量使用己存在的标准的技术，以便与已有的应用兼容，并能提供可靠的容错 机制。即：一个理想的网格计算应构建在当前所有硬件和软件平台上，给用户提供 完全透明的计算环境。对用户而言，它把众多同、异构的资源变成了同构的虚拟计 算环境。为此，网格计算环境设计需要考虑以下功能： ( 1 ) 管理层次：确定管理层次体系，管理域按区域层次划分，决定管理信息流的 流向。 ( 2 ) 通信服务：随应用目的的不同提供不同的服务，包括可靠的点对点和不可靠 的组播通信，支持各种通信协议，提供通信链路延迟、带宽和可靠性等指标。 ( 3 ) 信息服务：提供方便可靠的机制，获得不断变化的各结点信息和状态。 ( 4 ) 名字服务：提供全局统一的名字服务，典型的有国际通用的x 5 0 标准或 i n t e r n e t 上d n s 标准。 ( 5 ) 文件系统：提供一个分布式文件系统机制、全局存储和缓存空间。 ( 6 ) 安全认证：应包括登录认证、可信赖、完整性和记账等方面的安全性，这是 网格计算的难点，也是系统成败的关键。 ( 7 ) 监视系统：提供监视系统资源和运行情况的工具 ( 8 ) 资源交易机制：为鼓励不同组织或资源拥有者加入系统，应提供一种计算资 源的交易机制，允许提供资源者获得利益，使系统能动态地取得最好的性价比资源。 2 2 网格资源管理模型 网格模型主要是资源管理与调度子系统。资源管理与调度子系统应具有多级调 度的思想，每个资源有自己的调度子系统。用户只需把作业提交给资源请求代理， l o 硕学位论文 第= 章网格计算与资源管理概论 而代理后有多少资源提供者，以及该作业分配到哪台处理机对用户都是透明的。资 源提供者可以是单个p c 机，可以是单个集群或多个集群，也可以是某个组织的一 个中小型局域网，它们都有一个共同点，就是都有一个管理者局部资源管理器。 单个p c 机本身就是一个管理者，而对集群和局域网来说，一般都有一台服务器专 职管理集群中各结点，所以用户作业在资源请求代理上进行一级调度，在局部资源 管理器上进行二级调度，如果下面存在更多的集群或局域网，则存在三级、四级等 多级调度【1 8 j ，这里只考虑二级调度模型，多级调度模型以此类推。 ( 1 ) 资源请求代理：整个网格的资源管理者，负责接收用户任务，根据其特点发 送给域资源管理器，动态监视任务的运行情况，根据需要将结果提交给用户或进行 再调度。主要功能有1 18 】： 对服务提供方提供注册功能，对其加入和退出等动作进行控制。 建立网格资源信息库并周期性刷新，对全局资源进行统一管理和分配。 接收用户提交的作业，并根据作业类型和要求( 如c p u 速度、内存大小和 截止期等) 形成作业调度参数。 根据作业调度参数调度作业，分派资源，并随时监视作业的执行情况。 若作业执行有误，则能对其进行再调度，保证用户作业的安全运行。 ( 2 ) 域资源管理器：域内资源管理和动态调度的中心，负责本工作域的创建，属 性的收集，接收从资源请求代理提交的任务并根据其特点进行处理机的分配。主要 功能有： 监听从本域结点发送来的信息，建立域成员信息资料库并周期性刷新。 周期性接收从资源请求代理提交的作业，并判断其可行性建立本域的任务 队列。 从任务队列中选取作业，根据提交的参数和资源情况合理分配作业。 定时将作业执行情况返回给资源请求代理，维持与上级数据库的一致性。 监视各组员执行状况，根据情况进行作业调整( 域内调整或再调度) 。 确保用户作业的安全运行，并将结果通知资源请求代理并直接返还给用户。 ( 3 ) 网格工作结点：任务执行的基本单位，一旦申请加入资源提供方，便由域资 源管理器直接调度，资源请求代理间接调度。主要功能有： 向上级管理器提出申请，请求加入资源提供方。 收集本结点的状态和负载信息，并周期性提交给域资源管理器。 产生服务进程，随时接收上级管理器提交的任务并执行。 ( 4 ) 组件间的联系：鉴于各实体间的联系比较多，可将其分为作业提交和资源汇 硕+ 学位论文第章嘲格计算与资源管理概论 报两部分。 作业提交部分，用户向资源请求代理提交作业任务；资源请求代理根据用 户参数将作业转交给域资源管理器；域资源管理器根据各结点负载情况分派作业给 合适的资源工作结点，任务执行完毕保存作业结果，域资源管理器直接将结果返回 给用户。 资源汇报部分，网格工作结点向域资源管理器提供各结点的状态和负载情 况；域资源管理器将该域的负载信息汇总并送给资源请求代理供查询和管理结点； 域资源管理器周期性刷新资源请求代理中的作业状态，工作结点执行完毕。 2 3 资源管理与调度工作过程概述 首先启动资源请求代理的服务，i n t e m c t 上的任何一台p c 机、集群或局域网都 可以向它提出申请加入网格资源提供方。然后资源请求代理通过对申请的确认和招 标来收集资源，形成资源提供方簇。获批准的网络结点下载服务程序，与资源请求 代理形成劳资关系，随时向资源请求代理提供资源与服务。用户利用提交程序将作 业任务和要求的环境属性( 如c p u 速度，内存等) 提交给资源请求代理，资源请求代 理分析环境属性形成参数文件，根据任务性质、通信状况和各资源负载情况进行作 业调度，寻求最佳分配方案将作业及参数文件提交给选中的域资源管理器。域资源 管理器与资源请求代理时时刻刻保持联系。当域资源管理器接收到新任务或调度周 期到来时，新任务被赋予任务优先级插入作业队列。从结点机列表中获取该域内所 有结点信息和负载情况，同时更新资源请求代理上全局数据库中相关的信息表，确 定各结点的优先权，每次从最高优先权结点开始查询，选择合适的处理机，并将作 业队列首的任务映射到该结点机上执行。有相应的作业线程周期性监视该作业的执 行状态，并向上一级( 资源请求代理) 汇报，以便进行全局管理与调度( 或用户查询) 。 当任务途中异常中断或执行性能比预期要差时，资源请求代理可进行再次调度，重 新安排其他资源，而当任务完成时，资源请求代理会要求域资源管理器直接将作业 结果返还给用户。 2 4 基于市场经济管理模型下网格计算资源分配概论 目前大多数网格计算环境下的调度和资源管理问题一般仍使用传统形式，即由 调度构件根据确定的花费函数来决定任务应在哪里执行( 如g l o b u s 、l e g i o n 、c o n d o r 、 硕士学侥论文第一：章刚格计算与资源管理概论 a p p l c s 、n e t s 0 1 v e 、p u n c h 等) 。但这些花费函数一般都是以系统为中心的，不能由 用户的服务质量( q o s ) 参数如存取价格、服务传送时间片等驱动。大多数系统将资源 看作可以花费同样的价格来存取，而事实当然不是这样。同时终端用户也并不一定 想要支付最高的价格来获得最有效的资源利用，而是有可能基于需求、价值、优先 权和可供使用的预算协商一个特定的价格。在经济学方法中，调度决定不是静态地 由单个调度实体来完成而是由终端用户的要求直接驱动。一个常规的经济模型一般 关注的是运行应用的软件和硬件花费，而经济模型主要对最终用户的服务收费。在 竞争的经济市场中，基于用户需求和可供使用资源的贸易是主要驱动力，因此，我 们值得重视的是单个用户在网格中与其它用户以及网格服务提供者和资源拥有者的 竞争。通过对网格体系结构的分析，可以看到基于市场的网格模型根据功能可以分 为网格资源管理与调度和市场经济贸易两个模块，基于市场经济模型多目标规划模 型的框架组件如图2 1 所示： 资源信息 八鸭 i 作 暮 _ ，s 信息圭 业 训 结点域 应 控 卜他， 贸易服务 用 制 s 贸易多 i 程 代 v i 价格政策l 理 序 。厂 飞 l 7 i 1 分配代理 卜 一 c 作业 - l 资源分配 v 用户资源请求代理中间件资源提供者 图2 一l 市场经济模型的网格资源管理模型 ( 1 ) 网格资源代理【1 9 1 ：用户资源请求代理利用中间件服务连接用户和网格资源。 它包括：作业控制代理、作业调度、网格信息浏览、贸易管理和分配代理五大模块。 作业控制代理接收用户的作业和要求，同时检测该作业能否在它所代理的网格结点 中完成；作业提交给调度模块，网格浏览器从网格中间件数据库获取资源提供方的 信息；贸易管理模块通过市场中间件与资源提供方协商价格问题；作业调度模块根 硕士学何论文第_ 二章网格计算与资源管理概论 据前两项返回的结果及作业控制代理输出的用户要求分派最优资源给作业；最后作 业分配代理模块把作业调度到选定资源上运行，并随时把资源提供方反馈的作业状 态或结果返回给作业控制代理。 ( 2 ) 网格市场中间件：市场中间件包括资源的分配和管理、认证和安全服务、网 格信息服务、交易模板四大模块。资源的分配和管理模块对全局的资源进行统一的 管理和调度分配；认证和安全服务模块对服务提供方提供注册功能，对客户提供认 证访问全局数据库的功能，同时保证用户作业在资源提供方安全运行；网格信息服 务器动态收集资源提供方的信息，并反映到全局数据库中；交易模板提供用户请求 代理和局域资源管理、协商价格的功能。 ( 3 ) 网格域资源管理：域资源管理包括资源管理和贸易服务两大模块。资源管理 模块动态监测本局域网资源，对本局域网的资源进行调度并动态地向市场中间件的 网格信息服务模块传送本局域网格资源信息。贸易服务模块能通过市场中间件的交 易模板模块和用户资源请求代理的贸易管理模块通信，使用贸易协议来决定交易结 果。 2 5 使用经济模型分配资源的优点 在我们人类社会，资源的分配往往是通过市场来执行的。人类社会市场机制的 成功促使人们也希望用相似的概念来解决在多代理系统领域里的资源分配问题，即 通过资源提供者出售资源、资源需求者购买所需资源的方法来实现资源分配。资源 作为一种商品，其价格主要由该商品的供求状况所决定，对一种资源高的需求将抬 高它的价格，低的需求将降低它的价格。采用经济模型来管理系统资源至少有以下 优点【1 9 j ： ( i ) 可以动态配置资源，自适应性更强，应用能根据实际情况随时请求资源； ( 2 ) 分散决策，通过协商，资源拥有者和资源请求者能够达成一致意见，避免了 集中的权威机构； ( 3 ) 分布式决策和通信，能够开发以用户而非系统为中心的调度策略，并有助于 建立一个高度可扩的系统； ( 4 ) 基于价值的分配，对于所有资源采用一致的衡量方法，用户可以交易任意资 源，包括计算力、存储设备、网络带宽延迟、各种设备等，并提供了任何用户公平 存取网格资源的基础： ( 5 ) 内嵌入经济原理，鼓励资源拥有者贡献他们的空闲资源并能从中获利，有助 l 垂 一 硕士学位论文 第_ 章网格计算与资源管理概论 于建立大规模的网格系统： ( 6 ) 将外部市场经济和系统低层连接在一起，现实世界中，对资源的使用往往也 不是免费的，经济机制固有地存在于人类社会，资源请求者和提供者能根据自己的 实际情况作出决策，最大化各自的效用和利益。 传统上来说，生产者基于生产费用和期望边际利润给他们的货物和服务定价 刚。然而从消费者观点来看，价格取决于资源耗费、维护费用、需求等诸多参数。 在这里我们定义网格经济的资源价格如下： 资源价格：包括物理资源费用，服务费用，需求量，用户感知的价值，偏好， 最后三个参数实际上很难表现出来，而且对于不同的应用往往是变化的。消费者能 够付费存取各种各样的资源包括c p u 、内存、存储设备、软件和网络等。 网格计算环境必须提供合适的低层，包括安全、信息、远程资源的透明存取和 信息服务等使我们能够将资源提供者和资源需求者联系在一起。资源提供者通过运 行软件系统( 诸如g l o b 岫或者l e g i o n ) 以及网格资源交易服务使他们的资源能够在 网格中使用。资源交易期间资源需求者和资源提供者之间可以使用各种经济模型和 交互协议来进行资源交易和服务存取，这些协议由网格市场驱动来决定服务存取价 格。价格不是模型中唯一的因素，但是它是最重要的因素之一。在经济的模型中， 我们主要关注的是网格资源价格的变化情况。由于资源市场中的每个交易人都只关 心自身利