（电路与系统专业论文）网格计算中任务调度算法研究.pdf

重庆大学硕十学何论文中文摘要 摘要 网格计算是借鉴电力网的概念提出来的。利用网络把分散在不同地理位置的 计算机组织成一个“虚拟的超级计算机”，其中每一台参与计算的计算机就是一个 “节点”，而整个计算环境是由“节点 组成的一张“网格”。最终目的是希望给 用户提供可靠的、协调的、无处不在的和低廉的高端计算能力。网格计算为解决 科学和工程领域一些大规模计算问题提供了理想的平台。 资源调度是网格计算中一个关键性的研究课题。在网格环境中，任务从提交 给网格系统到任务处理完成，都一直处于网格任务管理系统的管理之下。良好的 资源调度能有效地协调和分配网格资源，有效降低网格计算的总执行时间和总耗 费量，从而使网格达到最大性能。由于网格具有大规模、异构、动态、分布和自 治等特性，如何调度任务以满足用户的需求是一个极具挑战性的问题。 本文基于遗传算法原理提出了适合网格计算环境的网格资源调度策略，并将 其作为网格资源调度技术的核心策略来更合理的调度网格资源，本论文主要工作 为： 对当前常用的资源发现和管理模型进行了研究，针对层次模型中的“层层 传递”导致的效率低下问题，提出一种基于资源类型的资源发现和管理模型，该 模型大大提高了资源查找和更新的速度。 网格计算系统融合了多种计算资源，一方面这些计算资源可能存在很大的 性能差异，另一方面由于它们的工作负载也是动态变化的，因此计算资源能够向 用户提供的计算能力也会动态地变化。因此本论文提出了自适应遗传算法、线性 变换遗传算法、量子遗传算法三种不同的任务调度算法，根据网格系统各个计算 模块的计算能力、负载及网络状态进行自适应调度，从而向用户提供最优的性能。 对当前国内外比较优秀的静态和动态调度算法进行分析，着重讨论了比较 经典的m i n - m i n 算法以及q o sg u i d e dm i n m i n 算法，在此基础上考虑到任务对服 务质量要求的差异对调度算法的影响，提出一个较为合理的改进算法来有效地均 衡负载、提高系统吞吐量。 采用g 订d s i m 工具包对以上提出的算法进行了实验仿真，仿真结果表明改 进后的调度算法更加高效。 关键词：网格计算，任务调度，遗传算法，自适应，线性变换 a b s t r a c t g r i dc o m p u t i n gi sb a s e do np o w e r 鲥d i to r g a n i z e sd i s t r i b u t e dc o m p u t e r sa sa “v i m l a ls u p e rc o m p u t e r b yn e 觚o r k e v e qc o m p u t e ri sc a l l e dan o d e ，a i l da l lm e n o d e sf o 珊a “g “d ”t h et a 玛e to f 鲥di st om a k et h eu s e r sf e e lt l l eu s eo f g r i di s 嬲 c o n v 砌e n t 邪u s i n gp o w e r 鲥d g r i dc 0 m p u t i n gp r o v i d e sd 印e n d a b l e ，c o n s i s t e n t ， p e r v a s i v e ，a 1 1 di n e x p e n s i v ea c c e s st ol l i g l l - e n dc o m p u t a t i o n a lc 印a b i l i t i e s np r o v i d e s a ni d e a lp l a t f o n l lt os o l v e1 鹕e s c a l ec o m p u t i n gp r o b l 锄si ns c i e n t 谲ca j l de n 西n e “n g a r e a r e s o u r c e ss c h e d u l i n gi sa k e yi s s u ei nc o m p u t a t i o n a l 鲥d i n 鲥de i l v i r o n m e n t s ， f 沁mj o bs u b m i s s i o nt or e s u l tp r o c e s s i n g ，a l le v e n t sa b o u t j o b sa r eu n d e rt h ec o n t r 0 1o f j o bm a n a g 锄e n t o n eg o o dr e s o u r c e ss c h e d u l i n gc a ne 疏c t i v e l yi m p r o v ea d j u s t i n ga n d a s s i g n i n g 酣dt a s k s ，a i l dd e c r e a s e 鲥dc o m p u t i n gt o t a lt i m e ，g r i dc o m p u t i n gc a i l p 柏彻p e r f e c t l y r e s o u r c e ss c h e d u l i n gi s 伊e a ti m p o r t a j l ti n 鲥dc o m p u t i n g b e c a u s e 鲥d e n v i r o l l l l l e n t sa r e l a r g e s c a l e ， h e t e r o g e n e o u s ，d y i l 锄i c ， d i s t r i b u t e da l l d a u t o n o m o u s ，鲥dj o bm a n a g e m e n t i sc o m p l e xa 1 1 dc h a l l e l l 百n g b a s e do nt h e 研n c i p l eo fg e l l 鲥c a l g o r i t h m s ，虹1 i sp a p e rp r e s e n t e dt h e 鲥d r e s o u r c e ss c h e d u l i n gs t r a t e g ya d a p t e df o r 鲥dc o m p u t i n ge n v i r o n l e n t ，w 1 1 i c hw a sa s 嬲t l l ec o r es t r a t e g yo f 鲥dr e s o u r c es c h e d u l i n gt e c h n i c a l ，t om a k em er e s o u r c e s c h e d u l i n gm o r er e a s o n a b l e t h e r ew e r et h em a i n 、r k so fm i sp a p e r ： 1 t m sp a p e rr e s e a r c h e di n t ot h ec l m - e n tc o m m o nr e s o u r c ed i s c o v e n ，a n d m a n a g 锄e n tm o d e la 1 1 dp u tf o n a r dar e s o u r c ec l a s s i f i c a t i o nb a s e d 西dr e s o u r c e s h i e r a r c h i c a lm o d e l ，w 1 1 i c hw i l li m p r o v et h es p e e do fr e s o u r c ef i n d i n ga n du p d a t i n g g r e a t l y 2 t h e 鲥dc o m p u t i n gs y s t e m sa r cc o n s i s t e do fv a r i o u sl ( i n d so fd i f f 打e m r e s o u r c e s ，b e c a u s et h e s er e s o u r c e sn o to n l yd i 行- e r 伊e a n yi nr a wp e 而锄a n c ea 1 1 da l s o t h e i rl o a db a l a n c i n gi sd y n 锄i c ，t h e i ra v a i l a b l ec o m p u t i n gp e r f o n t l a n c e st om e u s e r s v a r y 伊e a t l y ，t o o s ot l l i sp a p e rp m p o s e st h r e ea d 印t i v es c h e d u l i n ga l g o r i t h m s ，s u c ha s s e l f a d j u s t e dg e n e t i ca l g o t 1 1 1 1 1 ，l i n e a r 乜a 1 1 s f o r m a t i o ng e n e t i ca l g o 打t h m ，q u a n m m g e n e t i ca l g o r i t h m 、 3 t h i sp a p e ra i l a l y z e dt h ee x c e l l e n ts t a t i ca n dd ”锄i cs c h e d u l i n ga l g o r i t l l i l l si n n l ew o r l d ，e s p e c i a l l yt h ec l a s s i c a lm i n m i na l g o t h ma n d q o sg u i d e dm i n m i n a l g o r i m m c o n s i d 嘶n gt h ei n n u e n c eo fd i 矗h e n tr e ( 】u i r 锄e i l t so ft a s ko ns c h e d u l i n g 4 重庆大学硕+ 学位论文英文摘要 a l g o r i t l l i i l ，t h ea u t h o rp u tf o 刑a r dap r o p e ra 1 9 0 r i t l l i i lt ob a l a n c em ec h a 略ea n di n c r e a s e t h e 俯o u 曲p u te 币c i e n t l y f i n a l l y ，t l l ea u m o ru s e dg r i d s i mt o o l st om a k es i m u l a t i n ge x p e r i m e n tt ot e s tt 1 1 e a l g o r i t h l n sp r e s e n t e db e f o r e t h er e s u l to fm es i m u l a t i o ns h o w e dt h a tt h ei m p r o v e d s c h e d u l i n ga l g o r i t h mi sm o r ee f f i c i e n t k e y w o r d s ： g r i dc o n l p u t i n g ，g e i l e t i ca l g o r i t h m ，协ks c h e d u l i n g ，s e l f a d j u s t e d ， l i n e a rt i 肌s f o m a t i o n 5 学位论文独创性声明 菡丝赵盂盔蛰矗鲞蓝爹是焘毒师螽轰意研妻 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人己经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 导师签名： 签字日期：岬多r 签字日期： ”| | 学位论文使用授权书 本人完全了解重庆大学有关保留、使用学位论文的规定。本人完全同意中 国博士学位论文全文数据库、中国优秀硕士学位论文全文数据库出版章程，( 以 下简称“章程”) ，愿意将本人的盈士学位论文困丝盥竺鱼至塑鱼丝丝垄 提交中国学术期刊( 光盘版) 电子杂志社( c n k i ) 在中国博士学位论文全文数 据库、中国优秀硕士学位论文全文数据库以及重庆大学博硕学位论文全文 数据库中全文发表。中国博士学位论文全文数据库、中国优秀硕士学位论 文全文数据库可以以电子、网络及其他数字媒体形式公开出版，并同意编入c n l 【i 中国知识资源总库，在中国博硕士学位论文评价数据库中使用和在互联 网上传播，同意按“章程”规定享受相关权益和承担相应义务。本人授权重庆大 学可以采用影印、缩印或其他复制手段保存论文，可以公开论文的全部或部分内 容。 作者签名：导师签名： 备注：审核通过的涉密论文不得签署。授权书一， 该论文属于涉密论文，其密级是，涉密期限至年一月一日。 说明：本声明及授权书! 逝装订在提交的学位论文最后一页。 重庆火学硕士学位论文 l绪论 1绪论 1 1 研究背景和现状 1 1 1 研究背景 网格的思想早在1 9 6 0 年就被提出，但是对网格的大规模研究于近十几年前开 始，而网格的概念提出于9 0 年代中期，用于表达在高端科学和工程上分布式计算 的一种基础构造形式。从此，在相关基础上，取得了相当大的成就，简单的讲， 网格就是把整个因特网整合成一台巨大的超级计算机，实现计算资源、存储资源、 数据资源、信息资源、知识资源和专家资源的全面共享。这种计算模式是利用互 联网将分散在不同地理位置的计算机组织成一个“虚拟的超级计算机”，其中每一 台参与计算的计算机就是一个“节点”，而整个计算机系统由若干个“节点 组成 一张“网格”。所以这种计算模式叫做网格计算。这种构建在互联网上的新兴技术 为科技人员和普通用户提供了更多的资源功能和交互性，提供大家方便的使用各 种计算资源的能力。 目前网格处于高速发展时期，美国开发了c o n d o r 、l e 酉o n 、g l o b u s 等比较有 影响的软件：在欧洲有欧洲数据网格、荷兰网格、爱尔兰网格等；亚洲有亚太网 格( 亚洲和太平洋地区网格研究的基础设施) ；n i n f 是日本正在实施的全球计算 基础设施项目；印度将开发一个称为i 鲥d 的网格。 在我国，网格的研究列入国家“8 6 3 计划，中国科学院计算机技术研究所从 1 9 9 6 年开始网格技术的研究，2 0 0 0 年开发了连接国内8 个曙光计算机中心的网络， 2 0 0 1 年提出了织女之星网格计划。国内其它一些大学和研究所也开展了网格技术 的研究。目前已经丌始用g l o b u s 工具集构建和使用网格【l 】。 1 1 2 研究现状 网格的核心服务是连接网格底层和高层功能的纽带，是协调整个网格系统有 效运转的中枢，资源调度技术是网格核心服务之一。一个良好的资源调度能有效 地协调和分配网格资源，有效降低网格计算的总执行时间和总耗费量，从而使网 格达到最大的性能。资源调度技术对网格系统的应用是至关重要的。目前网格环 境下的资源调度主要在改进调度算法上。著名的g l b o u s 网格环境着重处理了资源 发现和标识问题，但在任务的提交和调度算法方面不是很完善。采用命令行手动 对任务进行提交，采用轮循方法对资源进行调度，容错性差，没有考虑负载平衡。 经典算法有m i n - m i n 【2 3 4 1 ，s u 侬髓g e 【5 1 等。根据网格计算资源调度系统具体的特点， 传统调度算法不能很好的适应网格资源调度的要求。目前，已有许多科研组织对 网格资源调度进行了研究。下面进行简单介绍： 重庆人学硕士学位论文 l绪论 c o n d o m 【6 ，7 ，8 1 ：为了充分利用网格资源的空闲时间来为用户服务，因此c o n d o m 使用的调度算法相对简单一些，定义了数据模型c l a s s f i l e d a d v e n i s e m e n t 来描述资 源特性和表达用户需求。调度分为匹配和声明，在匹配期间，m a t c h m a l 【e r 获得最 适合任务的资源，之后通知用户及服务提供者，二者之间再次进行声明以确立它 们的关系。c o n d o m 被设计用于高吞吐率计算。 n i m r o d 【9 】：此系统主要为用户在需求满足的情况下提供经济计算模式，目前， n i n l r o d 主要的算法为d e a d l i n ea n db u d g e tc o n s n a i n e d ( d b c ) s c h e d u l i n g a l g o r i t ，其能够根据任务完成时间以及花费预算进行资源调度，根据问题的侧 重点不同，还有d b ct i m eo p t i m i z a t i o n 、d b cc o s to p t i m i z a t i o n 和d b cc o s t t i m e o p t i m i z a t i o n 三种分支。 a p p l e s 【l o 】：a p p l i c a t i o nl e v e ls c h e d u l i n g 简称为a p p l e s ，p a r 锄e t e rs w e 印 t e m p l a t e 是a p p l e s 中一用户级的中间件，主要目标为将资源以最有效形式调度到 任务上，使得任务以较高效率完成，p a r 锄e t e rs w e 印t e m p l a t e 提出了一个自适应 算法来实现此目标，在此算法中w 6 r kq u e u e 、m i n m i n 、m a ) 【m i n 、s u f j 衙a g e 等 调度策略都可使用，所针对的应用主要是p a r 锄e t e rs w e 印a p p l i c a t i o n ，针对 p a r a m e t e rs w e e pa p p l i c a t i o n 中存在任务共享输入文件的情况，c a s a n o v a 等对 s u 胁a g e 算法进行了改进，提出了新的调度策略x s u 行e r a g e ，经实验表明，随着 共享文件的增大，x s u 脓a g e 的优越性越明显。 随着网格的不断发展在资源调度领域不断有新的挑战出现在一些网格应用 中，有些应用要求在能够提供一定服务质量( q o s ) 的资源上进行，而有些应用 则在资源能提供的q o s 方面没有要求。 本文在参考了大量经典算法和网格调度特点的基础上，针对资源调度中的最 优跨越度问题，将网格结构特点和调度算法相结合，提出了基于遗传算法的一种 新的资源调度策略，用于提高网格资源调度性能。 1 2 研究方法及其可行性说明 1 2 1 研究方法 与传统的分布式计算一样，资源管理和任务调度是网格计算研究的核心问题。 网格计算是一个由广域网连接大型设备形成的并行计算环境，计算节点的处理能 力远大于传统的分布式计算环境中的计算节点，而节点间的通信代价比传统的基 于局域网的分布式计算环境要高许多，所以可以将网格计算环境看作是一个大的 计算池，适合处理相互间几乎没有通信的粗粒度并行任务，所有被提交的任务放 进这个计算池就会被根据资源管理方法分配适当的资源，并以一定的调度方法进 行调度和执行。每个资源可根据自己的调度策略对分配给自己的任务进行进一步 9 重庆人学硕十学位论文1 绪论 的调度1 6 j 。 现有的g 1 0 b u s 网格环境着重处理了资源发现和标识问题，而任务的提交和调 度方法都不完善，其中任务的提交采用命令手动方式，任务的调度采用轮询算法， 容错性差，没有考虑负载均衡【7 】。 为了集中研究网格计算中的资源管理和任务调度问题，本文根据网格环境的 特点，设计了一种网格计算任务调度仿真模型。主要思想是通过不断调整服务器 间处理请求的分配比例，来避免有些服务器超载时依然收到大量请求，从而提高 整个系统的吞吐率。在设计过程中吸收了遗传算法的设计思路，同时引入模拟退 火，量子算法等机制，充分考虑到系统的负载均衡，从而使得整个网格系统的任 务调度模块具有更高的效率和更好的质量，具有一定的智能性。 1 2 2 研究可行性说明 遗传算法是目前三种典型的拟生态算法之一( 其它两种为蚁群算法和免疫算 法) 。遗传算法来源自然进化思想，是一种分布式、启发式搜索算法。 遗传算法主要用于解决诸如t s p 问题( t r a v e l i n gs a l e s m a i lp r o b l e m ) ，j s s p 问题( j o ps h o p p i n gs c h e d u l i n gp r o b l 锄) ，g c p ( g r a p hc o l o d n gp r o b l e m ) 等组合 优化问题。而网格计算中的资源调度在本质上也是组合优化问题。因此从解决问 题的角度讲遗传算法适合于解决资源调度问题。 遗传算法具有很强的并行性和天生的分布式特性。而网格资源具有很强的分 布式特征，并且将作业分配给资源执行总是并发进行的，遗传算法的这些特性为 解决网格计算中的资源调度问题提供了便利。 遗传算法具有较强的健壮性，对初始化条件要求不高，运行过程中无须干预 的特点，这些特点使得遗传算法在复杂的网格环境下更容易控制。 因此遗传算法适合于解决网格计算环境下的资源调度问题。 1 3 论文的主要工作 基于遗传算法原理提出了适合网格计算环境的基于遗传算法的网格任务调度 模型，并在其基础上对诸多基于遗传算法的任务调度算法进行了改进和优化，最 后通过网格仿真环境g r i d s i m 对其进行了性能测试和分析，论文主要工作为： 解析网格计算环境，明确网格计算特点及分析网格体系结构，归纳网格计 算中的资源调度原理、特点、组织模式、体系结构和调度过程。 提出了一个资源发现模型。网格计算的基石是众多的计算资源，但是由于 网格计算的根本特性是随机的共享，众多的计算资源存在着种类繁多、服务不确 定，能力不统一等性质。因此，针对这个问题，本文提出一个基于“资源类型 的资源发现和任务调度管理模型。 1 0 重庆人学硕士学位论文 1 绪论 提出了自适应遗传算法( s g a ) ，线性变换遗传算法( l t g a ) ，量子遗传 算法( q g a ) 三种任务调度模式，旨在有效提高任务调度的效率。这些调度技术 有效地考虑到各个资源的动态特性，为解决网格环境下任务调度提出了新的思 路。最后通过对不同调度算法的实验比较，分析了不同算法的性能。 对已有的q o sg u i d e dm i n m i n 算法进行研究，提出一种改进的q o sg u i d e d m i n m i n 任务调度算法，并进行了仿真实验，实验结果表明，该算法在满足任务 提出的q o s 要求的基础上，进一步提高了调度的效率。 1 4 论文的组织结构 本文以介绍网格环境的概念和系统模型为起点，按照从理论到模型设计再到 算法应用的实现路线，根据现有网格中任务调度算法的不足，首先设计了一个简 要但功能完备的任务调度仿真环境，然后引入调度算法。最后把现有的调度算法 同本文改进的算法做比较，分析实验结果，验证了算法的有效性。按照研究工作 完成的顺序，论文的组织结构和章节安排如下： 第l 章为绪论，介绍本文的选题背景，研究工作的基础，并对整个研究使用 的方法与流程做简单的说明。 第2 章为网格计算任务调度及仿真模型设计，主要介绍了网格的体系结构， 并详细给出了任务调度仿真模型的设计思路。 第3 章分析了网格计算中任务调度的基本特征及问题一般性描述，并详细介 绍了现有的任务调度算法。 第4 章根据现有网格计算任务调度方法的不足，分别设计出基于自适应遗传 算法的任务调度方法，基于线性变换遗传算法的任务调度方法，基于量子遗传算 法的任务调度方法。 第5 章结合q o s 理论对q o sg u i d e dm i n m i n 算法进行了改进。 第6 章对整篇论文进行总结，并对未来工作进行展望。 1 5 本章小结 本章主要介绍了网格计算的背景，网格计算研究的发展和现状，网格计算系 统的特点，指出了本文的研究方法及其研究可行性，最后说明了以及全文的组织 结构。 重庆大学硕+ 学位论文 2 网格计算任务调度及仿真模型 2 网格计算任务调度及仿真模型 2 1 网格计算体系结构 网格体系结构【1 1 】是划分网格系统基本组件、指定系统组件的目的与功能、以 及说明组件之间如何相互作用的技术。到当前为止，比较重要的网格体系结构有 两个，一个是f o s t e r 等人在早些时候提出的五层沙漏结构，另一个是f o s t e r 等人 在以i b m 为代表的工业界的影响下，并结合w 曲s e r v i c e 提出的开放网格服务结 构0 g s a ( 0 p e i lg 耐s e r v i c e 心c h i t e c t u r e ) 【1 2 1 。 2 1 1 五层沙漏结构 五层沙漏结构【1 3 】的主要特点是结构简单、层次清楚。此结构侧重于定性的描 述而不是具体的协议定义，这有助于从整体上理解网格计算。五层沙漏结构并不 提供严格的规范，不是对全部所需协议的完整罗列，是对该结构中各部分组件的 通用要求进行定义，结果是一个开放的、可扩展的体系结构，提供虚拟组织结构 的解决方案。 五层沙漏结构是从g l o b u s 系统中抽象出来的，对网格的初步形成影响十分广 泛。五层沙漏结构一个很重要的思想就是以“协议”为中心，同时强调服务和a p i ， s d k 等的重要性。它类似于传统的t c p i p 网络协议栈，将网格分为五个互相关 联而不等的层次。在五个层次中，资源层和汇聚层拓展了网络应用层的功能，对 传统网络中的许多应用层问题进行了封装，因而功能进一步强大，并为用户提供 更加透明的使用手段，下面分别介绍五层沙漏结构各层的功能及其特点【l 】： 晖 网 络 协 议 体 系 结 构 图2 1 五层沙漏结构与i n t e m e t 协议的对比 f i g u r e 2 1t h ec o m p a r eo ff i v e - h o u 曙1 嬲ss n l j c t u ：r ew i ln l eh t 锄e tp r o t o c o l 五层沙漏模型按照模型中各组件中与其共享资源的距离远近，将对共享资源 进行操作、管理和使用的功能分散在五个不同的层次中，越向下层就越接近物理 1 2 器回 重庆人学硕十学位论文2 网格计算任务调度及仿真模型 层的共享资源，与特定资源相关的成分就比较多；越向上层就越感觉不到共享资 源的细节特征，也就是说上层是共享资源的更加抽象表示，因此就不需要关心与 底层资源相关的具体实现问题。上述模型在网格底层( 即构造层) 和网格高层( 即 应用层) 对网格行为和状态作了较少规定，从而形成了沙漏的中间部分。 2 1 2 开放网格服务体系结构 开放网格服务体系结构o g s a 是继五层沙漏结构之后最重要，也是目前最新 的一种网格体系结构。o g s a 架构的四个主要的层构成如图所示。从下到上依次 为：资源层：资源层的概念是o g s a 以及通常意义上的网格计算的中心部分， 包括物理资源和逻辑资源。物理资源包括服务器、存储器和网络。逻辑资源通过 虚拟化和聚合物理层的资源来提供额外的功能；w 曲服务以及定义网格服务的 o g s i ( o p e ng ds e i c e si n l j r a s t r u c t u r e ，o g s i )【1 0 】扩展：o g s a 中所有网格资 源( 逻辑的和物理的) 都被理解成服务。o g s i 规范定义了网格服务并建立在标 准w 曲服务技术之上。o g s i 利用诸如x m l 和w 曲服务描述语言( w 曲s e r v i c e s d e s 嘶p t i o nl a n g u a g e ，w s d l ) 【1 4 这样的w 曲服务机制，为所有网格资源制定 标准的接口、行为与交互。o g s i 进一步扩展了w 曲服务的定义，提供了动态的、 有状态的和可管理的w 曲服务的能力，这对网格资源进行建模都是必须的；基 于o g s a 架构的服务：w e b 服务层及其o g s i 扩展为下一层提供了基础设施：基 于架构的网格服务。g g f 目前正在致力于在诸如程序执行、数据服务和核心服务 等领域中定义基于网格架构的服务。随着这些新架构的服务的丌始出现，o g s a 将变成更加有用的面向服务的架构( s e r v i c e0 e n t e da r c h i t e c t u r e ，s o a )； 网格应用程序：随着时间的推移，一组丰富的基于网格架构的服务不断被开发出 来，使用一个或多个基于网格架构的服务的新网格应用程序亦将出现。这些应用 程序构成了o g s a 架构的第四个主要层。 构建o g s a 的两大支持技术是g l o b u s 和w e bs e r v i c e 。g l o b u s 是己经被科学 与工程计算领域广泛接受的网格技术求解方案。w 曲s e r v i c e 是一种标准的存取网 络应用框架。目前，网格服务提供的接口还比较有限，下一步o g s a 主要考虑扩 充管理、安全等方面的内容。 重庆人学硕十学位论文 2 网格计算任务调度及仿真模犁 应用程序层 基于o g s a 构架的网络服务层 o g s l 扩展 w e b 服务层 安仝性ll 工作流 l 数据库| | 文件系统li 目录i | 消息l 服务器 l i 存储器 i | 网络 图2 2 开放网格服务体系结构 f i g u r e 2 2o p e i l 例ds e r v i c e s r c h i t e c t u r c 2 2 网格计算中任务调度仿真模型 本章在结合集中式、分布式和层次式等三种资源发现模型的基础上，提出一 种改进的基于资源类型的资源发现模型( r e s o u r c ec l a s s i f i c a t i o nb a s e dg d d r e s o u r c e sd i s c o v e r ym o d e l ，r c ) 。首先介绍模型的总体结构，然后对模型的核心 模块进行详细分析描述，最后，通过定性比较揭示出模型的优点。 2 2 1 资源发现模型总体结构 r c 模型( 如图2 3 ) 采用三层管理结构，第一层是网格计算中的资源，这些 资源可按结点所分布的地理区域、连通性以及结点之间的相关性等因素进行分簇 ( c l u s t e r ) 。第二层是在每个簇中按照资源的类别设置的多个管理节点，每个管理 节点仅管理注册到该节点的资源和簇中的某一类资源，实现对资源的分类管理。 第三层是在每个簇中的管理节点之上设置的功能节点，每个功能节点在对簇中的 管理节点进行管理的同时还对簇中资源的请求进行转发。本模型通过基层计算资 源的汇报，及时发现新计算资源的加入和原有计算资源的退出。 1 4 重庆人学硕+ 学位论文 2网格计算任务调度及仿真模型 图2 3r c 模犁总体结构 f i g u r e 2 3t l l eo v e n n s 仉l c n h eo fl m o d e l 由上图可以看到，在模型中有三种角色的节点：资源节点p e e r 、管理节点 m p ( m a n a g e rp e e r ) 、功能节点f p ( f u l l c t i o n a lp e e r ) 。每个p e e r 都必须连接一个 管理节点m p ，若干m p 连接到一个功能节点f p 。若干个功能节点以全连接或者 其他方式形成一个在管理节点之上的第三层，也就是功能节点层。 普通节点p e e r ( 即虚拟组织) 既可以是资源提供者( r e s o u r c e sp r o v i d e rs p ) ， 也可以是资源请求者( r e s o u r c e sr e q u e s t o rs r ) 。当p e e r 为s p 时，它必须首先将 自己的资源信息注册到m p 上，并定时向m p 发送资源更新信息。 管理节点m p 的作用是接受p e e r 或其它m p 的请求并在必要时通过功能节点 f p 向其它簇中的m p 节点转发，并定时将注册资源的更新信息向同簇中其他m p 转发。 f p 负责管理与它相连的m p 并接收其它f p 转发的资源请求信息，在自身管 理的m p 中进行查询，并把查询结果发送给请求者。功能节点f p 是改进的管理 节点，也可以叫做“管理节点的管理节点”。 2 2 2 资源发现模型的几个定义和假设 r c 模型是一个不考虑资源节点拓扑动态变化情况下的资源发现模型，为了 更好的分析r c 模型，现给该模型作以下定义和假设： 定义1 ：网格资源信息组织模型 g = ( r ，m ，e ，d ，r f ) 。其中，r 为网格中的所有资源节点集合；m 为网格 中所有管理节点集合；e 表示管理节点间的邻接关系：e ( m ) 为节点m 的邻节 1 5 重庆人学硕+ 学位论文2 网格计算任务调度及仿真模犁 点集合，e ( m ) g m ；d 表示资源信息在非注册管理节点上的转发，d ( r ) 为资 源r 的感知节点。r f 为资源注册函数，mr 专m 。 为方便表示，定义l r ( m ) 为管理节点m 上通过转发得到的资源集合：l r ( m ) = r | r r ，1 1 f ( r ) = d ) 。l r ( m )r ，r = u m 。m l r ( m ) 。对于任意m 1 ， m 2 m ，m l i n 2 ，l r ( m 1 ) n l r ( i i 也) = 中。 定义2 ：网格资源信息更新传播模型u u = ( g ，u p d a t e ( r ) ，p ，d ( r ) ) 。其中，u p d a t e ( f ) 表示g 中资源r 的变化， p 表示该资源信息的更新在g 中管理节点间的传播策略，资源r 的变化会引起其 注册节点上信息的更新，并传播到r 的所有感知节点d ( r ) 。对于更新信息的产 生节点m ( 即资源r 的注册节点) ，p ( u p d a t e ( r ) ，m ) 表示资源更新信息转发的 邻节点。 定义3 ：网格资源发现请求处理模型 ( g ，r e q u e s t ( r ( a ) ) ，s ，f )专l ，其中，r e q u e s t ( r ( a ) ) 为查找请求， 定义了资源的各种属性要求a ；s 为查找起始信息节点集合；f 表示g 中信息节 点间的查找请求转发策略；l 表示在资源发现过程中找到的匹配资源集合。对于 接收到的资源查找请求，管理节点m 做以下操作：若请求资源与本地管理的资源 类型相同，则在本地管理节点进行查找，若满足停止条件则结束，否则根据资源 类型和转发策略转发到相应令节点。 假设1 ：存在网格资源分类t ，且对于每一个网格资源，r r ，都有惟一的 类型t ( r ) ，t ( r )t 。 假设一个网格资源只有惟一的类型是为了表述的方便。一般的分类体系通常 是树形的，现在只考虑其中某个层次上的类型划分，不考虑类之间在概念上的层 次关系。 假设2 ：资源发现请求r e q u e s t ( r ( a ) ) 包含了对所请求资源类型的说明， 记为t r e q u 鼬( r ( a ) ) ，钿。e s t ( r ( a ) ) 任t ，或者t r e q u e s t ( r ( a ) ) 可以从资源属 性描述a 中进行推断。 一般而言，对于一个特定的网格应用，需要将不同类型的资源组织成虚拟组 织( v o ) 来满足应用的要求，整个资源发现的过程在逻辑上可视为多个单一类型 资源发现过程的组合。在存在标准资源分类的情况下，即便在资源请求中未做出 显式的说明，资源类型也易于从资源属性的描述当中进行推断。 2 2 3 新的任务调度模式的提出 资源管理和任务调度是网格计算研究的核心问题，现有的g l o b u s 网格环境着 重处理了资源发现和标识问题，而任务的提交和调度方法都不完善，其中任务提 交采用命令手动方式，任务调度采用轮询算法，容错性差，没有考虑负载均衡。 1 6 重庆大学硕士学位论文2 网格计算任务调度及仿真模型 由于现在网格技术还不是很成熟，没有比较成熟的网格环境来进行实验，而 且由于经济等多方面的原因，在实际的网格环境上进行科学实验不太可能。在仿 真环境里测试调度算法的有效性是目前对网格进行研究的主要方式之一。 从商业过程到工厂流水线，再到计算机系统设计等诸多领域，仿真己被广泛 用于对实际系统的建模和评估中。现有的网格仿真软件有b r i c k s 仿真系统、 m i c r o g r i d 仿真器、s i m g r i d 工具包和g 订d s i m 工具包。但是这些现有的仿真系统 都非常庞大，不适合单纯研究网格环境中的单个模块，特别是网格任务调度算法。 为了集中研究网格计算中的资源管理和任务调度问题，排除复杂因素的影响， 本文根据网格环境的特点，设计了一种简单且功能齐全的网格仿真模型。其主要 思想是通过不断调整服务器间处理请求的分配比例，来避免有些服务器超载时依 然收到大量请求，从而提高整个系统的吞吐率。图2 4 显示了该设计框架，在调 度管理器上运行负载信息管理进程l i m ，在资源节点上运行客户程序a g e n t ，在 任务分配器上运行任务分配管理进程t s m ，在实时监测器上运行信息适时提交进 程m s 【5 1 。 用户1用户m tt 任务解析器 士 调度管理器 tjt 。 任务分配器实时监测器 千千 。i ，1r、 资源ll ” l 一资源n 图2 4 网格计算任务调度仿真模型 f i g u r e 2 4t i l es i m u l a t i o nm o d e lo fg r i dt a s ks c h e d u l i n g 这是一个较通用的仿真系统的结构，其分为用户、资源、以及调度中心三个 主要部分。而调度中心又包含4 个模块： 任务解析器：用户向任务解析器提出应用需求，包括应用的计算负载、通 信负载和时间限制等。任务解析器维护一个未调度任务队列，记录提交应用的用 户名和具体要求，并生成x m l 文件发送给调度管理器。同时任务解析器按任务 的优先级别将任务排队，并选取队列的第一个任务送往调度管理器。 调度管理器：根据资源节点a g e n t 的请求，完成资源节点及其运行服务 ( h 婶，却，s m t p 等) 的注册、注销等功能，并启动负载信息管理进程l i m ，然 1 7 重庆人学硕+ 学何论文 2网格计算任务调度及仿真模型 后根据实时监测器上的周期性反馈信息，计算出每个资源节点的动态负载权值。 然后根据x m l 文件和当前资源节点的状态按照一定的调度方法选取一种最优的 分配策略，并将相应任务送到任务分配器。这是此结构中最复杂的一个模块，可 在其中设置多种调度方法。 实时监测器：实时监测器上运行信息适时提交进程i r s 。瓜s 进程将资源 节点中a g e n t 进程收集到的各节点当前负载信息( c p u 利用率c ( i ) ，内存利 用率m( i ) ，当前网络流量n ( i ) ，磁盘i o 访问率i o ( i ) ，进程总数p ( i ) ) 实时反馈给调度管理器。 任务分配器：任务分配器启动任务分配管理进程t s m ，并根据调度算法， 将接收的任务送到资源节点，并将传送结果反馈给调度管理器。 2 2 4 资源发现过程 资源发现是由用户请求( r e q u e s t ) 发起的。也就是从p e e r 进行发起。该请求 首先被发送到该p e e r 的管理节点m p 。如果所需资源正是本m p 管理的一类资源， 则在此m p 中进行查找，如果找到合适资源则返回查找结果给请求p e e r ；否则， 就将请求转发给同簇中存放此类资源的m p ，并在其中进行查找。若仍未找到， 则将该请求发给该簇的功能节点f p ，由f p 将此请求转发给其他簇的f p ，并在其 他簇中相应的m p 中进行查找。算法如下： i f ( m p i 收到一个节点的资源请求) i f ( 御i 朱存储此类资源) 发送请求给该簇中存储此类资源的m p j ； i f ( 在m p j 中朱发现合适的资源) 发送请求到f p ，由f p 将请求发送给其他簇的f p ： ) e l s e 在本地资源库中进行查找： i f ( 查找成功) 返同资源信息给请求者，查找结束； e l s e 发送请求到f p ，由f p 将请求发送给其他簇的f p ； ) 重庆人学硕七学位论文2 网格计算任务调度及仿真模型 ) e l s ei f ( m p i 收剑m p j 的资源请求) 在本地库中进行查找： i f ( 查找成功) 返回资源信息给请求者，查找结束； e l s e 返同查找不成功给请求者； ) 2 2 5 资源信息更新过程 为了实现这种分层的资源发现机制，首先应该对资源信息很好地维护。新资 源加入，以及资源退出是资源维护的主要工作。在这里，节点位置有两层含义： 一是物理层：即资源节点在实际物理连接关系上形成的关系，对系统中的机器来 说，按照实际网络拓扑特性进行构建；另一层是逻辑层：即从所有计算资源的物 理现状映射得到的系统程序的数据结构。 信息更新包括注册该资源信息的m p 节点和感知该资源信息的m p 节点的更 新两个方面。注册该资源信息的m p 节点的更新是由连接m p 的p e e r s 定时向m p 发送自身资源信息的变更情况，m p