（计算机软件与理论专业论文）网格环境下作业调度算法的研究.pdf

河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 摘要 网络的高速发展，使得分散的、异构的计算资源有机地结合到一起，并且 使其形成一个巨大的网格成为一种可能。相应的，网格中的作业调度也渐渐成为 一个比较重要的问题。作业调度算法的研究，直接关系到网格环境中调度的速度、 质量等方面，在网格计算技术的研究中，起着举足轻重的作用。 作为启发式算法中的经典算法，m i n - m i n 算法总是先执行具有最短完成时间 的作业，有着算法思路简单、总完成时间短的特点，是网格作业调度算法研究中 倍受关注的一个算法。 但是在考虑到带宽的情况下，各个作业对带宽有不同的要求，有的作业对 带宽没有任何要求，有的作业却需要比较好的带宽。因此，可能出现普通作业占 据着高带宽网格资源，而对带宽要求比较高的作业却得不到高带宽的网格资源的 情况。在这种情况下，m i n - m i n 算法已经不能满足调度的需求了，需要在算法中 将作业对带宽的要求考虑进去。因此，h ex i a o s h a n 等人在m i n r a i n 算法的基础 之上提出了q o sg u i d e dm i n - m i n 算法。 针对q o s g u i d e dm i n - m i n 算法本文具体做了以下几个方面的研究工作： 论述了网格作业调度算法的研究意义，介绍了网格作业调度目标、网格作 业调度算法、作业调度算法模拟器等相关内容的研究以及研究现状。 把q o s 的概念扩大化，考虑作业和资源的特殊性，使用资源标志和作业标 志对资源和作业进行标记，按照作业标志对所有的作业进行调度。在q o sg u i d e d m i n - m i n 算法的基础上进行改进。 根据改进后的算法，对g r i d s i m 模拟器进行相关修改，使用n e t b e a n s 和 g r i d s i m t o o l k i t - 3 3 对m i n - m i n 算法，q o sg u i d e dm i n - m i n 算法和改进后的q o s g u i d e dm i n - m i n 算法进行模拟。 通过几组对比实验，对这三种算法从多角度进行分析和比较。证明了改进 后的q o sg u i d e dm i n - m i n 算法比其他两种算法拥有更短地执行时间，更加适用 于网格环境。 关键词：网格，作业调度，服务质量( q o s ) ，g r i d s i m ，算法模拟 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 a b s t r a e t t h er a p i dd e v e l o p i n gn e t w o r km a k e si tp o s s i b l et oi n t e g r a t et h eg e o g r a p h i c a l l y d i s t r i b u t e da n dh e t e r o g e n e o u sc o m p u t i n gr e s o u r c e si n t ot r e m e n d o u sg r i d s ot h e t a s k ss c h e d u l i n gi ng r i dh a sb e c o m eaq u i t ei m p o r t a n tp r o b l e m a n dt h er e s e a r c ho f s c h e d u l ea l g o r i t h m s ，w h i c hd i r e c t l yr e l a t e dt ot h es p e e d , q u a l i t ya n do t h e rf a c t o r so f t h ec r i c kp l a y sad e c i s i v er o l ei nt h er e s e a r c ho f c o m p u t i n gg r i d m i n - m i na l g o r i t h m , ac l a s s i c sa l g o r i t h mi nh e u r i s t i ca l g o r i t h m , w h i e l aa l w a y s c o m p l e t e st h es h o r t e s tt o t a lc o m p l e t i o nt i m et a s kf i r s t , h a st h ec h a r a c t e r i s t i co f s i m p l e a n ds h o r t e s tc o m p l e t i o nt i m e s oi tc a t c h e sal o to f c l o s ea t t e n t i o n si nt h ef i e l do f s t u d y i n gf o r t a s k ss c h e d u l i n ga l g o r i t h m si nc t r i d b u ti f w et a k et h eb a n d w i d t hi nc o m i d e r i n g w cw i l lf i n dt h a te v e r yt a s kh a sa d i f f e r e n td e m a n df o ri t s o m et a s k sn e e dn o t h i n g ，w h i l eo t h e r sr e q u i r ec o m p a r a t i v e l y h i g h e rb a n d w i d t l la n d i tm a ye x i ts u c hs i t u a t i o n st h a ts o m eo r d i n a r yt a s k so c c u p yt h e r e s o u f c e sw i t hh i g hb a n d w i d t h , w h i l eo t h e rh j 【g hb a n d w i d t hr e q u i r e dt a s k se a r m o tg e t t h er e s o u r c e s t h e y n e e d i nr e s u l to f t h ep r o b l e mm e n t i o n e d j u s tn o 、玑t h em i n - m i n a l g o r i t h ma l r e a d yc a l ln o ts a t i s f yt h en e e df o rs c h e d u l i n g s ow es h o u l dc o n s i d e rn e w a l g o r i t h m st h a t t a k et h et a s k s d e m a n d sf o rb a n d w i d t h i na c c o u n t t h e r e f o r e ，h e x i a o s h a na n do t h e rr e s e a r c h e r sb r o u g h tf o r w a r dt h eq o sg u i d e dm i n - m i na l g o r i t h m b a s e d0 1 3 m i n - m i na l g o r i t h m s i n c ec o n s i d e r i n gt h er e q u e s tf o rq o s ，w h i c hi n e a l l st h e q u a l i t yo f s e r v i c e , t h i sa l g o r i t h ma p p l i e sb e t t e rt h a nm i n - m i na l g o r i t h mi nt h e d y n a m i cg r i de n v i r o n m e n t a c c o r d i n gt ot h eq o sg u i d e dm i n - m i ma l g o r i t h m , t h i sp a p e rf o c u s e so nt h e f o l l o w i n gr e s e a r c h e s ： d i s c u s s e st h em e a n i n gf o rt a s ks c h e d u l i n ga l g o r i t h m sr e s e a r c h i n g t h e n i n t r o d u c e st h er e s e a r c hs t a t u sf o rt a s ks c h e d u l i n go b j e c t s ，a l g o r i t h m s ，a n ds i m u l a t o r s o f t a s ks c h e d u l i n ga l g o r i t h m s e x p a n d st h ec o n c e p to f q o s ，a n dt a k e st h ep a r t i c u l a r i t i e so f t h el g s o u r c e $ a n d t a s k si ne o m i d e r i n g 。w ei l s er e s o u r c es i g na n dt a s ks i g nt oi n d i c a t ed i f f e r e n tk i n d so f l e s o u r c 嚣a n dt a s k s a l lt h et a s k sa r cs c h e d u l e da c c o r d i n gt ot h e i rt a s ks i g n s a n da l l t h e s ec h a n g e sa l eb a s e d0 1 3 q o sg u i d e dm i n - m i na l g o r i t h m t h eg r i d s i mt o o l k i ti sm o d i f i e da c c o r d i n gt ot h em o d i f i e dq o sg u i d e d m i n - m i na l g o r i t h m a n dw es i m u l a t em i n - m i na l g o r i t h m ，q o sg u i d e dm i n - m i n a l g o r i t h ma n d m o d i f i e dq o sg u i d e dm i n m i na l g o r i t h mo nn e t b e a n sa n d 河海大学硕士研究生毕业论文弼格环境下作业调度算法的研究 g r i d s i m t o o l k i t - 3 3 a n a l y z e sa n dc o m p a r e st h ea b o v et h r e ea l g o r i t h m s 丘o mm u l t i - a s p e c t st h r o u g h s e v e r a ls e t so f c o n t r a s t i n ge x p e r i m e n t s a tl a s t , i ti sp r o v e dt h a tt h em o d i f i e dq o s g u i d e dm i n - m i na l g o r i t h mh a ss h o r t e rc o m p l e t i o nt i m et h a nt h eo t h e rt w oa l g o r i t h m s s ow ec a l lc o n c l u d ei tf i t sf o rt h eg r i de n v i r o n m e n tb e t t e rt h a nt h eo t h e rt w o a l g o r i t h n m k e yw o r d s ：g r i d t a s ks c h e d u l i n g , q o s ( q u a l i t yo fs e r v i c e ) ，g f i d s i m , a l g o r i t h ms i m u l a t i n g i 一 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：燃2 。7 年3 月1 8 日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：2 0 0 7 年3 月1 8 日 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 1 1 研究背景 第一章绪论 随着h t c r n e t 的广泛应用，并行与分布式计算技术飞速发展，伴随着网络带 宽的不断增加，一种基于高速网络，实现网络内资源共享的并行与分布式计算技 术成为迫切的需要。这将成为下一代的互联网技术网格技术【”。这是利用互 联网或专用网将地理上广泛分布的、异构的、动态的资源互联起来实现资源高度 共享和集成，为用户提供高性能的计算、管理及服务等功能的一种新技术。 1 。1 1 网格简介 电网( e l e c t r i c p o w e r c , - r i d ) 是我们比较熟悉的一种“网络”，用户只需将 用电器连上电网，就能使用到电网提供的电，而不需要关心正在使用的电是由哪 个发电厂提供的。网格( g r i d ) 就是将互联网比拟成电网建立和发展的。网格一 词在2 0 世纪9 0 年代中期首次被用来描述用于科学和工程分布式计算的基础设 施。这种基础设施把计算资源、数据存储设施、广域网络、仪器设备等连成有机 的整体，方便用户使用这个基础设施中的任何资源田。 从本质上来讲，网格就是一个基于广域网构建的分布式计算系统，它与传统 的分布式系统的主要区别在于它具有广域性、异构性、动态性三个特点。它主要 应用于解决科学、工程、商业领域中规模庞大、计算复杂、需要使用多种异构资 源的计算闯题。这样的闯题大量存在，而且在任何一个单一的超级计算机上都无 法解决【3 1 。 网格的大小没有任何限制，根据不同的需要，我们可以建立企业网格、局 域网网格、校园网格、个人网格等等。虽然网格的大小不同，但是所有的网格都 实现了资源共享，消除了资源孤岛，提高了网格环境下所有资源的利用率。 在网格环境中的用户，只需将自己的电脑连上网格，就能使用到网格提供 的所有资源，包括各种计算资源、存储资源、信息资源、数据资源、知识资源、 设备资源等等，而不需要关心正在使用的资源的地理位置，也不需要关系这个资 源是由哪里提供的。 网格具有如下基本特征【4 1 ： 1 分布与共享 分布性是网格的一个最主要的特点。分布性首先是指网格的资源是分布的。 分布的网格涉及的资源类型复杂、规模较大、跨越的地理范围较广。在网格这一 河海大学硕士研究生毕业论文 网格环境下作业调度算法的研究 分布式环境下，需要解决资源与作业的分配和调度问题、安全传输与通信问题、 实时性保障问题、人与系统以及人与人之间的交互问题等。共享是网格的目的， 分布资源的共享问题是网格的核心问题。这里的共享不仅指计算机可以用来完成 来自其它地方的计算作业，也包括中间结果、数据库、专业模型库等各方面的内 容。分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上 的特征。 2 自相似性 网格的局部和整体之间存在着一定的自相似性，局部往往在许多地方具有 全局的某些特征，而局部的特征在全局也有一定体现。这种整体和局部的相似性 在网格的建造和研究过程中具有十分重要的意义。 3 动态性与多样性 网格的动态性包括网格的动态增加和动态减少。对于网格资源动态减少或 者网格出现故障的情况，要求熊及时实现作业的自动迁移，做到对高层用户透明 或者尽量减少用户的损失；网格资源的动态增加需要提高网格的扩展性，网格的 扩展性要求体现在规模、能力和兼容性几个方面。网格资源是异构和多样的。在 网格环境中可以有不同体系结构的计算机系统和类别不同的资源，因此网格系统 必须能够解决这些不同资源之间的通信和互操作问题。 4 自治性与管理的多重性 网格资源的拥有者对该资源拥有最高级别的管理权限，网格应该允许资源 拥有者对他的资源有自主管理的能力，这称为自治性。但是网格资源也必须接收 网格的统一管理，否则无法实现共享和互操作，因此网格的管理具有多重性。 1 1 2 国内外网格发展现状 目前，对网格的研究已经由美国和欧洲推广到了整个世界，各国都投入了 很大的资金和人力进行网格的研究和网格基础设施的建设。在各个国家、各个地 区相继出现了网格论坛，全球也成立了最大的网格联盟全球网格论坛 5 1 ，用 来指定和发布网格的最新标准。 美国开发的c o n d o r ，l e g i o n ，g l o b u s 【6 】等工具，成为了网格研究和开发的重 要软件和工具。利用g l o b u s ，可以把地理位置上分布的计算资源、信息资源等 资源集成起来，以建设网格基础设施。 欧洲数据网格( e u r o p e a n d a t a g r i d ) 【7 】是由欧洲联盟支持的一个项目，它的 目标是建设一个拥有超强计算强度、超高共享的大规模分布式数据库的网格基础 设施。 亚洲各国在政府的大力支持之下，也开始了对网格的研究，中日韩等国先 后举办了网格方面的国际论坛或会议，以促进网格在这些亚洲国家的研究和发 河海大学硕士研究生毕业论文 网格环境下作业调度算法的研究 展。 在我国，网格研究已经被列入国家“8 6 3 计划”。中国科学院计算机技术研 究所从1 9 9 6 年开始对网格技术进行研究。2 0 0 0 年，开发了连接国内8 个曙光计 算中心的网格。2 0 0 1 年提出了织女星网格计划，在此基础上取得了一定的成绩。 同时，国内很多大学也利用g l o b u s 等工具集构建校园网格，开展了对两格的研 究【9 】。 1 2 研究内容 在网格技术飞速发展的同时，网格中的作业调度算法也渐渐成为一个比较 重要的问题。作业调度算法的研究，直接关系到网格环境中调度的速度、质量等 各方面的因素，在网格计算技术的研究中，起着举足轻重的作用。 1 2 1 网格作业调度算法简介 在传统的并行和分布式调度问题中，所涉及的计算资源是同构的，因此不 必关心资源所具有的属性以及资源能否满足用户所提交作业的需要，而且，计算 资源通常在地理上是集中的，因此不用关心系统在运行过程中的通信所花费的开 销。网格中作业调度的目的就是将“合适”的作业分配到“合适”的资源上去运 行。因此，不同的网格作业调度算法就可能有不同的调度目标，有的是为了增大 系统的计算吞吐率，有的是为了使系统的利用率最大化，有的则是为了以最经济、 最节省的方式使用户的需求得到满足。由于网格资源所具有的特点以及网格应用 的复杂性，以前针对传统的分布式计算的调度算法已经不适用于网格环境中的作 业调剧嘲。 高效的作业调度算法可以充分利用网格系统的处理能力，从而提高应用程 序的性能。在一种调度算法被真正的应用到实际的网格环境之前，我们需要对它 进行研究和评估。由于网格中的所有资源总是不停地变化着的，在作业调度算法 的研究和实验中，我们需要的是一个可以重复实验，并且可以控制的环境【4 l ，在 真实网格环境中，这种要求是不可能达到的，而往往采用模拟器完成这一工作， 能对研究起着事半功倍的作用。 目前，网格计算已经在许多方面进行了应用，针对不同的应用，有许多网 格中的作业调度算法被提出。本文对其中一些算法进行了研究，并做了相关工作 1 2 2 国内外网格作业调度算法研究现状 通过上一节对网格作业调度算法的简介，可以看出，不同的网格作业调度 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 算法可能拥有不同的调度目标，具体目标包括：最优跨度、服务质量、负载均衡、 经济原则等1 8 。网格作业调度算法本身就是一个n p 难问题，围绕作业调度算法， 国内外都做了大量的研究，提出了一些比较成熟的调度算法，如下所示： 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 1 2 1 。 u d a ( u s e r - d i r e c t e da s s i g n m e n t ) ：任意地将每一个作业，分配到具有最 好预期执行时间的机器执行【1o j 。 f a s tg r e e d y ：任意地将每一个作业，分配到具有最小完成时间的机器执行 0 0 3 。 m i n - m i n ：在该算法中，先要算出每一个作业在每个机器上的最短完成时 间。所有作业中，拥有最小完成时间的作业将被选出来，分配到对应的机器执行， 将这个作业删除，重复上述工作，直至所有作业都被分配【l 2 1 。 m a x - m i n ：m a x - r a i n 算法与m i n - m i n 算法类似，还是要先算出每一个作业 在每个机器上的最短完成时间。在所有作业中，拥有最大完成时间的作业将被选 出来，分配到对应的机器执行，将这个作业删除，重复上述工作，直至所有作业 都被分配【1 2 , 3 6 。 g r e e d y ：贪婪算法是m i n - m i n 算法和m a x - m i n 算法的结合，通过使用某 种解决方案，将两个算法结合起来【l0 ，1 2 1 。 g a ( t h eg e n e t i ca l g o r i t h m ) ：遗传算法是用来寻找比较大的解决方案的一 个算法，它是对已给问题的染色体进行操作，而最初的染色体是随机产生的。一 个染色体可以由任何一个算法产生，当它由m i n - m i n 算法产生，它就被称之为以 m i n - m i n “播种” 1 3 , 1 4 。 s a ( s i m u l a t e da n n e a l i n g ) ：模拟退火算法是一种每次都考虑一个可能的解 决方案的重复技术，是广泛使用的解决优化组合问题的算法之一。它的最大优点 是能避免问题的解落入局部最小。模拟退火采用循环搜索来寻找问题的最优解 伍旧。 g s a ( t h eg e n e t i cs i m u l a t e da n n e a l i n g ) ：遗传模拟退火算法是遗传算法和 模拟退火算法的结合。总的来说与遗传算法相似，只是在选择过程中，使用模拟 退火算法来决定接受还是舍弃新的染色体，同时保留最好的解【2 ，蛳。 t a b u ：t a b u 算法是一种循环搜索技术，不同的是它在问题的解空间里记录 了已经搜索过的空间，以避免重复搜索邻近的区域 2 , t 4 , 1 6 1 。 a ：a 算法是经典的状态空间搜索算法，在许多作业分配问题中均有应用。 这是一种树搜索算法，根节点是空节点，而中间节点代表部分解，即作业组的一 个子集和节点的映射关系，这些节点表示完整点b 用。 从文献【1 8 】中的实验分析表明，一般情况下，o l b 、u d a 、m a x - m i n 、s a 、 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 g s a 和t a b u 算法的性能比不上m i n - m i n 、g a 和a + 算法，后三种算法在完成时 间上的差异不超过1 0 ，g a 正常都会比m i n - m i n 算法有很小的提高，因为g a 算法是以m i n - m i n 算法播种的。在后三种算法中，m i n - m i n 算法是最快的算法， g a 算法比m i n - m i n 要慢，a + 是最慢的。对一个1 6 个资源，5 1 2 个作业的网格 环境，m i n - m i n 算法的执行时间差不多是i s ，g a 算法的执行时问是3 0 s ，而a 算法的执行时间要1 2 0 0 s 。 m i n - m i n 算法是一个简单、快速的算法，并且性能比较好。g a 算法使用 m i n - m i n 算法来播种染色体，也是因为它有比较好的性能。m i n - m i n 算法的缺点 是只考虑到完成时间方面的要求，在算法目标的其它方面几乎没有考虑，因此这 种算法只是在理论情况下是比较好的。在文献 1 9 1 中，考虑到q o s ( 主要指带宽) 的情况下，算法显然不能合理地安排作业的调度，因此在文献 1 9 】中提出了q o s g u i d e d m i n - m i n 算法，在网格作业调度过程中，引入了q o s 这个评判标准，使 得在考虑算法m a k e s p a n 的同时，也要兼顾到带宽( q o s 的一个方面) 的影响。 但是文献 1 9 】中考虑的q o s 单指带宽这一方面，本文在此基础之上，扩展了原算 法对q o s 的要求，从更大的范围对q o s 的几个重要方面进行评估，使得该算法 更加适用于动态变化的网格环境。实验结果表明，优化后的算法的性能比文献f 1 9 1 中有了进一步的提高，并且更加适用于资源分布广、特性不一、作业要求不同的 网格环境。 1 3 本文的主要工作 本文从理论和实践方面对网格环境下作业调度算法进行了较为深入的研 究。论文的主要工作如下： 1 介绍网格和网格的发展现状，以及网格环境下作业调度的相关概念，并 且介绍了主要的作业调度算法。 2 对作业调度目标加以分析，对启发式和经济模型这两种算法进行介绍。 对网格环境下作业调度算法的模拟器进行分析和比较，最后确定使用由澳大利亚 墨尔本大学r a j k u m a rb u y y a 领导开发的g r i d s i m 工具集 2 0 1 来对算法进行模拟。 3 对网格作业调度算法的经典算法m i n - m i n 算法进行分析，在对h e x i a o s h a n 提出的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 sg u i d e dm i n - m i n 算法进行改进， 提出了算法的改进思想和具体的算法步骤。 4 按照对q o s g u i d e d m i n - m i n 算法的改进思想，使用j a v a 对原有的g r i d s i m 工具集进行修改，使用修改后的模拟器对m i n - m i n 算法、q o sg u i d e dm i n - m i n 算法和改进后的q o sg u i d e dm i n - m i n 算法进行模拟。 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 5 从三个方面对上述三种算法进行评估。验证了改进后算法的可行性以及 优越性，并且分析了这三个方面对这三种网格作业调度算法的影响。 1 4 论文结构 本论文的组织情况如下： 第二章：作业调度相关概念。介绍了作业调度的相关概念以及调度目标。 对各种算法进行了分析和比较。同时对网格作业调度算法的模拟工具进行了分析 和比较，对我们在本论文中要采用的模拟器g r i d s i m 进行介绍。 第三章：o o sg u i d e dm i n - m i n 作业调度算法。对网格算法中的经典算法 m i n - m i n 算法以及该算法中用到的相关概念进行了介绍和分析，从而提出了该算 法在网格环境中的一些不足之处。在此基础之上，分析了q o sg u i d e dm i n - m i n 算法的优越之处，并对这两种算法进行比较。 第四章：基于q o sg u i d e dm i n - m i n 改进后的作业调度算法。通过对q o s g u i d e dm i n - m i n 算法的分析，提出了该算法的不足之处，提出了基于q o sg u i d e d m i n - m i n 算法改进后的算法的思想和步骤。并且使用g r i d s i m 对改进后的q o s g u i d e dm i n - m i n 算法进行模拟。 第五章：改进后算法性能的评估。从三个方面对上述三种算法进行评估。 验证了改进后算法的可行性以及优越性，并且分析了这三个方面对这三种网格作 业调度算法的影响。 第六章：总结和展望。对本文的主要工作进行总结并提出进一步的工作展 望。 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 2 1 概述 第二章作业调度相关概念 在网格系统中，作业调度是其重要的组成部分，它采用适当的作业调度算 法把不同的作业分配到相应的资源节点上去运行。由于网格系统的异构性和动态 性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得作业调度变 得极其复杂，但是某一个作业调度算法并不可能适用于所有的环境，也不可能存 在一个绝对好的作业调度算法。因此针对不同的要求、不同的环境，需要有不同 的作业调度算法与之相对应。本章将介绍网格环境中作业调度的目标以及目前研 究比较多的算法，并对现有的网格调度算法模拟器进行分析和比较。 2 2 作业调度的目标 简单地说，网格环境中作业调度的目标就是要对用户提交的作业实现最优 调度。具体的目标包括：最优跨度( o p t t m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t yo f s e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、经济原n ( f _ c o n o m i cp r i n c i p l e s ) 等【2 ”。 最优跨度 跨度是网格作业调度最常见、最主要的调度目标。它指的是一个用户的所 有作业的调度时间，即从执行第一个作业开始，到所有作业执行完成所花的时间 的总和。跨度越短，证明该调度算法越好，拥有最短跨度的跨度称为最优跨度。 从节约时间、充分利用资源的角度来考虑，以最优跨度为目标是大多数资源拥有 者和网格用户的共同目标。 服务质量 网格用户在选择资源时，可能会对资源的某些方面( 如c p u 速度、网速、 存储空间等) 有特殊的要求，他们希望尽可能的有好的服务来满足需要。这些要 求都将包含在用户提交的作业中，并且以q o s 的形式显示出来。在作业调度时， 网格将根据作业中的q o s 要求，选择合适的资源进行调度，充分满足用户的需 求。 负载均衡 在开发并行和分布式计算应用时，负载平衡是一个关键问题。网格系统更 迸一步扩展了这个问题。网格作业调度是涉及交叉域和大规模应用的调度。解决 好系统的负载均衡是一个非常重要的问题。 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 经济原则 网格环境中的资源在地理上是广泛分布的，而且每个资源都归属于不同的 组织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原贝i j ，不同 资源的使用费用也应是不相同的。市场经济驱动的资源管理与作业调度必须使消 费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久地发展下去。 2 3 作业调度算法的分类 2 3 1 启发式( h e u r i s t i c ) 对于n p 难的网格作业调度算法，至今没有找到有效的算法，以求近似最优 解的启发式算法得到了极大的运用。因此也出现了很多启发式的调度算法，如 m i n - m i ，m a x - r a i n ，g a , s u f f r a g e 等算法均属于启发式算法，在第一章已经对这 些算法进行了介绍，国内外在这些算法的基础之上，都有了一些改进之后的算法 4 0 , 4 4 1 。 其中，m i - m i 是一个比较经典的作业调度算法【捌，它的主要调度原则就 是将具有最短完成时间的作业分配到对应的资源上，保证以最短的时间执行完所 有的作业。根据2 2 可以看到，这个算法是以最优跨度为目标的，在此基础上， 有人又将q o s 作为目标进行考虑，提出了q o sg u i d e dm i n - m i n 算法。 2 3 2 经济模型( e c o n o m i cm o d e l ) 随着网格的发展，网格中的资源不可能无偿的给网格用户提供服务，将资 源的拥有者看成生产者，网格中的用户看成涪费者，很自然地，可以将网格环境 下的资源使用看成是一种经济活动。用户如果需要使用某个资源，只需要支付一 定的“钱”，这个“钱”可以是网格中的一种特定的可流通的货币，也可以是现 实生活中的货币，在一定条件下，两者可以相互转换。在这种前提下，经济模型 2 4 1 的作业调度随即产生了 根据经济学理论，目前的网格经济模型可以包括一下几种模型嘲： 商品市场模型 标价模型 讨价还价模型 招标，合同网模型 拍卖模型 河海大学硕士研究生毕业论文 网格环境下作业调度算法的研究 基于投标的资源均衡共享模型 合作联合佼换模型 2 4 作业调度算法模拟器 网格中的所有资源总是不停地变化着的，但是在网格作业调度算法的研究 和实验中，我们需要的是一个可以重复实验，并且可以控制的环境。在真实网格 环境中，这种要求是不可能达到的，而往往采用模拟器完成这一工作，能对研究 起着事半功倍的作用【9 l 。 2 4 1 各种模拟器简介 目前，网格界有人利用模拟器来模拟动态的网格环境下的作业调度算法， 使用模拟器的目的是为了不用真正搭建整个网格系统就能够评估出作业调度算 法的性能。模拟越接近真实环境就越能测试出作业调度算法的性能，这对网格平 台或者网格应用有着指导性的作用。网格模拟器就是提供了这样一个框架来模拟 我们设计的作业调度算法，通过模拟来比较不同算法的性能，从而对作业调度算 法进行相应的改进。主要的模拟器有以下几种瞄1 ： b r i c k s 删 m i c r o g r i d 叨 s i m g r i d l m g r i d s i m t 4 1 其中，b r i c k s 模拟器用来研究分布在广域环境的调度算法、数据管理和调 度之间的优化关系。由b r i c k s 模拟出来的网格环境并不是真正的网格环境，它 只能模拟出客户端之间的交互。b r i c k s 是使用j a v a 语言写的一个离散事件的包， 所有的网络和资源都是模拟的f c f s ( f i r s tc o m ef i r s ts e r v e d ) ，所有的作业都 是由数据的传输和指令的执行来表示。而且，该模拟器没有提供下载，更没有公 开源代码。 m i c r o g r i d 基于l i n u x ，建立在g l o b u s 平台上，所有的程序都模拟在g l o b u s 的基础上运行。m i c r o c r r i d 工具创建的是一个虚拟的网格，而不是创建网格的模 拟，可以在这个虚拟的网格上运行g l o b u s 工具集。当一个应用程序向资源发出 使用请求时，m i c r o g r i d 的虚拟层会截取这个请求，将它发给虚拟资源，这样， 一个资源和虚拟网格中的资源就被连接在一起。通过将实际的口映射成虚拟网 格中的一个p ，每一个虚拟的资源都与实际的机器有一个映射关系。从而，在 这个虚拟网格中g l o b u s 的使用和在实际网格中的效果一样。这个模拟器被现在 河海大学硕士研究生毕业论文用格环境下作业调度算法的研究 比较多的研究算法的人采用。 s i m g r i d 也属于比较有名的一个工具集。它也是基于l i n u x 平台，使用c 来 开发的模拟器。s i m g f i d 的一个重要的特点是，它允许对网格中资源连接的拓扑 结构加以规范，也就是说，它对网格环境的模拟是最逼真的。s i m g r i d 在模拟计 算和数据传输的时候，并没有太大的区别，都是通过模拟资源执行作业来完成的。 它可以用来评估算法，也以此为基础，被用来开发另外一个模拟器d a g s i m ， 这个模拟器被用来评估d a g 结构的应用程序的算法。 g r i d s i m 由澳大利亚墨尔本大学r a j k u m a r b u y y a 领导开发的，它的首要目 标是通过模拟来研究基于计算经济模型的有效的资源分配方法。g - r i d s i m 通过资 源的“买”和“卖”来引入“经济模型”，从而达到控制网格资源的使用的目的。 g r i d s i m 是一个在w i n d o w s 和l i n u x 的平台上都可以运行的网格模拟器。这个模 拟器是用j a v a 编写的，以s i m j a v a 类为基础的工具集，所以具有跨平台特性。 它可以用来模拟异构的网格资源，以及作业对这些资源的使用情况。使用c r r i d s i m 模拟出来的网格环境中的资源，具有不同的计算能力、不同的时区、不同的负载 等等。网格中的应用程序通过作业集来表示，里面包括数量不等的作业( o r i d s i m 模拟出来的g r i d l e t ) ，通过设置不同的作业，来表示网格中运行的各种应用程序， 这些程序可以在网格中的资源上执行。使用g r i d s i m 可以模拟出多用户的情况， 每个用户都有自己的应用程序要执行，这样就可以模拟出应用程序对网格资源的 竞争，通过使用不同的算法，这种竞争的方式也不同。 2 4 2 模拟器的选择 这一节，我们将通过对上一节介绍的各种模拟器进行对比分析，以决定在 我们的实验中，到底使用哪个模拟器来模拟我们的算法，并对算法性能进行评估。 b r i c k s 包在进行模拟时，受到本身体系结构的限制，它的扩展性比较差。 资源调度过程需要以不同的方式来模拟，这对b r i c k s 来说是最大的不足了。 m i c r o g - r i d 是对真实的g l o b u s 体系结构下，资源竞争的模拟，因此该工具 集需要创建一个真实的g l o b u s 环境，用它来执行网格中的应用程序。使用 m i c r o g r i d 的优点是接近真实的境下的程序执行。但是这并不是我们想要的，我 们需要的是一个简单的抽象的模拟，它可以简单快速的比较不同的作业调度算 法，因此m i c r o g r i d 并不合适 s i m g r i d 包在模拟计算和数据传输时没有任何区别。如果一个作业通过网络 连接被提交给一个资源，则一个数据传输作业先被网络连接执行，然后这个资源 再执行计算作业。如果在用户和资源之间有多个网络连接，则第一个网络连接将 被用来传输数据，剩下的网络连接将被用来执行这个作业的计算。在s i m g r i d 包 的设计中，使用的是两个资源之间只有一个网络连接的拓扑结构。但是我们需要 河海大学硕士研究生毕业论文 网格环境下作业调度算法的研究 的是在资源之间有多个网络连接，在这种情况下，当第一个网络连接还在传输数 据的时候，第二个网格连接也可以传输数据。因此，使用c 编写的s i m g r i d 包 严重妨碍了网格的结构和使用。 g r i d s i m 使用j a v a 编写。容易修改，具有跨平台的特点。底层网络模型是 一个非常简单的资源之间多对多的连接，这些连接之间的带宽和反应时间都可以 指定g r i d s i m 是一个基于n i m r o d g 经济模型的调度算法实验工具，在调度研 究中被广泛应用。在使用g r i d s i m 模拟算法的过程中，不需要创建真实的网格环 境，通过提供的方法来编写模拟文件，从而完成模拟的过程。而且该模拟器具有 跨平台特性，支持可视化，与具体的作业有关系，调度算法用g r i d s i m 模拟比较 好。 通过分析对比，我们最终确定使用基于j a v a 的g r i d s i m 工具集来模拟网格 作业调度算法。 2 4 3g r i d s i m 简介 图2 - 1c , - r i d s i m 工具集体系结构 河海大学硕士研究生毕业论文网格环境下作业调度算法的研究 如图2 1 所示刚，为g r i d s i m 工具集的在进行网格作业调度算法模拟时的 分层体系结构。图中第一层( v i r t u a lm a c h i n e ) 是网格系统的所有资源和用户的 电脑中的虚拟机，用来运行j a v a 程序。第二层( b a s i cd i s c r e t ee v e n ts i m u l a t i o n i n f r a s t r u c t u r e ) 是基本的离散事务模拟结构，主要由g r i d s i m 的s i m j a v a 包中的 各种类组成，是在第一层的基础上进行算法模拟的最基本的基类。第三层 ( g r i d s i mt o o l k i t ) 就是我们在模拟算法时主要用到的一层，也是关键的一层。 这一层里面包括进行模拟时用到的各种类，如：资源、作业管理、资源分配、统 计技术等等。运用这些类，可以在第二层的一些基类的基础之上，进行作业调度 算法的模拟。第四层( g r i dr e s o u r c eb r o k e r so rs c h e d u l e