（计算机软件与理论专业论文）基于遗传算法的网格任务调度研究.pdf

摘要网格技术是近几年研究较为热门的一项技术，它利用互联网把分散在不同地理位置的计算机组织成一个虚拟的超级计算机，未来互联网的发展方向是将网络中众多闲置的计算资源、存储资源以及科学仪器等可用资源充分合理的加以利用。如何设计一个好的任务调度算法是网格技术研究的重点之一。任务调度算法的目的是在包含大量不同的计算机网络中，同时考虑各网格节点的计算性能、任务量大小、任务优先关系等参数，最优分配任务，实现最佳的调度策略，从而高效地完成计算任务。由于任务调度问题是众所周知的n p 完全问题，如何在现有调度算法的基础上提出一个好的调度算法，尽可能提高网格计算的效率，是一个很重要也很现实的问题。本文提出了一种基于改进遗传算法的网格任务调度算法，该算法根据各网格节点的计算性能、任务量大小、任务优先关系等，为用户提供最优性能，不仅考虑到传统的时间跨度最短，还考虑到满足任务的时间期限、最小化运转时间和最小化资源的空闲时间。在基本遗传算法基础上，通过d a g 图获取任务的优先关系，采用资源一任务的间接编码方式，提出新的适应度函数，设计了很好的选择算子、交叉算子和变异算子。最后，在g r i d s i m 基础上对该模型和算法进行了仿真，通过实验结果比较获得最佳参数，并与常见的其他网格任务调度算法进行了对比，仿真结果表明，该遗传算法改善了任务调度时间，提高了任务调度性能。关键词：网格计算，任务调度，遗传算法，g r i d s i ma b s t r a c tt h e 鲥dc o m p u t i n gi sah o tt e c h n o l o g yd e v e l o p e di nr e c e n ty e a r s ，i tm a k e sf u l lu s eo fa l lk i n d so fa v a i l a b l er e s o u r c e sw h i c hs c a r e ri nd i f f e r e n tg e o g r a p h yp o s i t i o nt of o r mas u p e r c o m p u t e r i nt h ef u t u r e ，t h ei n t e m e tt e c h n o l o g yw i l lc o l l e c ta l lk i n d so fi d l er e s o u r c e ss u c ha sc o m p u t i n gr e s o u r c e s ，s t o r a g er e s o u r c e sa n da p p a r a t u sr e s o u r c e se t c i ti sv e r yi m p o r t a n tt od e s i g na ne f f i c i e n tt a s ks c h e d u l i n ga l g o r i t h mi ng r i dr e s e a r c h t a k i n gi n t oa c c o u n tp a r a m e t e r ss u c ha sc o m p u t i n gp e r f o r m a n c e ，t a s kl e n g t ha n dt a s kp r i o r i t yr e l a t i o n si nt h el a r g e - s c a l en e t w o r k ，t h eg o a lo ft a s ks c h e d u l i n gi st o仃yi t sb e s tt od i s t r i b u t ea n ds c h e d u l et a s k so p t i m a l l y ，s ow ec a nc o m p l e t ec o m p u t i n gt a s k se f f i c i e n t l y h o w e v e r ，t h et a s ks c h e d u l i n gp r o b l e mi st h ew e l l k n o w nn p c o m p l e t ep r o b l e m s i ti sv e r yi m p o r t a n ta n dr e a l i s t i ct op u tf o r w a r dab e t t e rs c h e d u l i n ga l g o r i t h mb a s e do ne x i s t i n ga l g o r i t h mw h i c hc a ni m p r o v et h ec o m p u t i n ge f f i c i e n c y t h i sp a p e rp r o v i d e sam e t h o do f 鲥dt a s ks c h e d u l i n gb a s e do na l li m p r o v e dg e n e t i ca l g o r i t h m a c c o r d i n gt op a r a m e t e r ss u c ha sc o m p u t i n gp e r f o r m a n c e ，t a s kl e n g t ha n dt a s kp r i o r i t yr e l a t i o n s ，t h i sa l g o r i t h mp r o v i d e so p t i m a lp e r f o r m a n c e ，w h i c hn o to n l yc o n s i d e r st h em a k e s p a nb u ta l s ot h ed e a d l i n e ，t u r n - a r o u n dt i m ea n di d l et i m e o nt h eb a s i so ft h eb a s i cg e n e t i ca l g o r i t h m ，t h er e l a t i o n s h i pb e t w e e nt a s k sc a l lb eo b t a i n e dt h r o u g ht h ed a g w eu s et h ei n d i r e c tc o d i n go fr e s o u r c e - t a s k ，d e v e l o pan e wf i t n e s sf u n c t i o na n dd e s i g nn e wo p e r a t o r so fs e l e c t i o n ，c r o s s o v e ra n dm u t a t i o n f i n a l l y ，w eo b t a i no p t i m a lp a r a m e t e r sb a s e do ne x p e r i m e n t a lr e s u l t s b yc o m p a r i n gw i t ho t h e rg r i dt a s ks c h e d u l i n ga l g o r i t h m s ，t h es i m u l a t i o nr e s u l t ss h o wt h a tt h eg e n e t i ca l g o r i t h ms h o r t e n st h et i m eo fm a k e s p a na n di m p r o v e st h ep e r f o r m a n c eo ft a s ks c h e d u l i n g k e y w o r d s ：g r i dc o m p u t i n g ，t a s ks c h e d u l i n g ，g e n e t i ca l g o r i t h m ，g r i d s i mi i原创性声明本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本论文使用授权说明期：本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。( 保密的论文在解密后应遵守此规定)签名：髯迭新签名：丝业日期：丛堕三堂j ：海大学硕士学位论文1 1 研究背景第一章绪论网格计算( g r i dc o m p u t i n g ) 川是当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题之一，它把计算资源、数据存储资源、广域网络、仪器设备等连成有机的整体，方便用户使用网格中的任何资源。网格有两个优势，一个是数据处理能力超强，另一个是能充分利用网上的闲置处理能力。它将改变传统的c l i e n t s e r v e r 和c l i e n t c l u s t e r 结构，形成新的p e r v a s i v e g r i d系统结构，这种体系结构将使得用户把整个网络视为一个巨大的计算机，并从中享受一体化的、动态变化的、可灵活控制的、智能的、协作式的信息服务 2 】。众所周知，高性能计算已经成为许多科学和工程实践的关键技术。科学家们也越来越多地使用超级计算机来研究复杂现象，例如可以用来预测复杂的非线性现象，或者是在做实验之前，就可探索物理参数的变化规律，甚至还可以用来模拟现实世界中所发生的某些事件。然而，尽管超级计算机的能力在不断增长，仍然有许多应用无法实现。因为这些应用往往需要处理能力强大的超级计算机的支持，但是超级计算机造价极高，通常只有一些国家级的部门，如航天、气象等部门才有能力配置这样的设备：另一方面，某些应用对计算的要求非常高，即使是现在最大的超级计算机也无法提供它们所需的资源，这时就需要将高性能计算依托i n t e m e t 或其他高速网络将遍布世界各个角落的能力千差万别的计算资源联结在一起，形成大规模的几乎可以无限扩展的计算能力。因此，对网格计算的研究具有很强的现实意义。任务调度是高性能计算中的一个重要组成部分，而随着网格的出现，在任务调度中出现了很多新的特性，从而对传统的调度算法也提出了新的挑战。传统的并行计算调度算法主要是调度一个应用程序的子任务到并行的计算机，主要目的是减少计算时间；而对于网格环境，调度算法关心的主要问题是调度来自不同用户的应用流到可用的计算资源上，从而最大限度地让网格系统得到最大的使用，它追求的是调度的高吞吐率。作为目前网格计算事实上的标准，上海大学硕士学位论文g l o b u s 4 】并没有具体实现任务调度算法，针对具体的应用网格，必须在高层设计出高效的任务调度算法。然而现有的一些调度算法如b a c k f i l l i n g 、f c f s ( f i r s tc o m ef i r s ts e r v e ) 等并不能很好的适应网格资源的特性，如调度问题的n p 完全性，调度算法的高效性，资源的异构性以及资源分配决策的并行性和分布性等，而遗传算法因其自组织、自适应、自学习性和并行性等特点而非常适宜解决网格任务调度问题。1 2 研究现状1 2 1 网格计算的研究现状目前，在网格计算领域的研究工作主要集中在网格计算环境中的基础研究和建立专用的应用网格两条线路。前者主要被国外以g l o b u s 5 】同盟为代表的研究组织所领导，而对于后者，在国外主要集中在美国和欧洲。如英国政府己投资超过1 亿英镑，建设英国国家网格( u kn a t i o n a lg r i d ) ；美国政府用于网格技术基础研究经费已超过5 亿美元；美国军方正在实施全球信息网格( g l o b a li n f o r m a t i o ng r i d ) 计划，预计在2 0 2 0 年完成。作为该计划的一部分，美国海军陆战队已启动了一个将耗资1 6 0 亿美元、历时8 年的项目，包括系统的研制、建设、维护和升级等多方面的工作；亚洲的中国、日本、泰国、韩国、马来西亚等国也开始了网格的研发和建设工作。n i n f 是日本正在实施的全球计算基础设施项目，它允许用户访问包括硬件、软件和数据在内，分布在广域网上的资源：韩国的情报和通信部与韩国科学技术情报研究院于2 0 0 1 年5 月开展了国家网格基本计划；泰国网格计划将重点放在资源共享，增加资源利用率、提高合作能力方面；印度也开发了一个称为1 - g r i d 的网格 7 8 】。中国科学院计算技术研究所从1 9 9 6 年开始了网格技术的研究开发工作。2 0 0 0 年，开发了连接国内8 个曙光计算机中心的网格。中国科学院计算技术研究所把网格研究当作一个长期、重要、具有发展潜力的研究方向，2 0 0 1 年提出了织女星网格计划【1 4 2 2 ，目前已取得了相当的进展，实现了网格资源的虚拟化，屏蔽使用网格资源的技术细节。2 0 0 2 年底，上海市宣布将投入两个多亿，建设2上海大学硕1 ：学位论文e - i n s t i t u t e ，其中网格是重点，将把上海交大、复旦、华东理工等多所重点高校用网格整合起来，共享资源，协同教学科研。2 0 0 2 年启动的8 6 3 信息领域高性能计算机及其核心软件专项就是一个网格计算项目，它以“需求牵引、技术跨越、多方协作、聚焦网格 为指导思想，以实现高性能计算机及其核心软件技术跨越为目标，研制能有效支持科学工程计算、新一代因特网信息服务和数据库应用，具有资源共享、协同工作能力的国家高性能计算机环境( 亦称网格) ，将高性能计算服务送到科教、企业、政府等各方用户的桌面上。除此之外，国内的一些大学和研究所也开展了网格技术的研究，其中包括清华大学、华中科技大学、国防科技大学、江南计算技术研究所等【6 】。这些项目的启动和研究工作的开展使我国的网格研究迅速向世界水平迈进。1 2 2 网格任务调度研究现状目前，已有许多科研组织对网格任务调度进行了研究，其中包括将传统的分布式计算中的任务调度算法应用到网格计算中来，常用的调度算法包括：m i n m i n 算法【9 1 、m a x m i n 算法【9 1 、s u f f e r a g e 算、法【1 0 、x s u f f e r a g e 算法【1 l 】、贪婪算法、遗传算法、蚂蚁算法等。网格中几个常用的调度模型有c o n d o r g 1 1 2 1 3 、a p p l e s 1 5 , 1 6 1 和n i m r o d g t l 7 】，下面简单介绍一下这几个模型：c o n d e rc o n d e r 是有美国威斯康星大学开发的一个高吞吐量计算环境，用来管理集群系统，已被扩展到网格环境c o n d o r - g 。在c o n d o r 中，用户代理管理由应用程序描述所组成的队列负责向匹配器发出请求，资源代理实现资源所有者策略，并向收集器提供资源信息。匹配器接受用户代理请求并向收集器查询资源信息，完成资源请求与资源提供者之间的匹配，由匹配的用户代理在相应的资源启动计算。其采用平面结构的机器组织、c l a s s a d 语言1 8 1 的资源描述、分层关系的命名空间、集中式查询的资源发现机制、以及定期p u s h 资源信息的方式进行集中式调度，但不提供q o s 保证。a p p l e sa p p l e s ( a p p l i c a t i o nl e v e ls c h e d u l i n g ) 是圣地亚哥加利福尼亚大学开发的应3卜海大学硕十学位论文用层调度系统。准确的说应用层调度系统a p p l e s 不是资源管理系统而是一个中间件，它与g l o b u s 和l e g i o n 1 9 等网格系统相互作用。它主要目标是用于调度，是通过调度代理a g e n t 为每个独立的网格应用程序调度，p a r a m e t e rs w e e pt e m p l a t e 是a p p l e s 项目中套用户级的中间件，它所针对的主要应用是p a r a m e t e rs w e e pa p p l i c a t i o n 。它的丰要目标就是将任务以最有效的方式调度到资源上去运行，使得应用以比较高的效率被完成。为了实现这个目标，p a r a m e t e rs w e e pt e m p l a t e 提出了一个自适应的任务调度算法，在这个算法中，w o r k q u e u e 、m i n m i n 、m a x m i n 、s u f f e r a g e 等调度策略都可以被使用。n i m r o d由于网格的异构性，其资源可能被不同的个人或者组织拥有，从而具有不同的管理策略、访问成本以及动态变化的性能。n i m r o d g 系统是利用经济模型来管理任务的调度，其中任务的执行费用也作为是一个很重要的q o s 参数而被考虑进来。n i m r o d g 系统的主要目的就是在保证用户需求得到满足的条件下为用户提供最经济的计算模式。n i m r o d g 有两个最重要的q o s 参数，分别是任务的执行时间和执行费用。该系统中为任务的调度提供了一套调度策略d e a d l i n ea n db u d g e tc o n s t r a i n e d 2 0 1 ，这套策略中主要包括3 个调度算法：时间优化算法，费用优化算法，费用时间优化算法，用户可以按照自己的需求选择合适的策略进行调度。在网格系统中，用户在使用资源时并不是无偿的，需要以购买的方式来获得资源的使用权，同时资源的提供者可以通过出售自己的计算资源而获得利益。这种资源的供需关系与现实生活中的商品经济模型类似，所以用经济模型来刻画资源的供求关系和管理任务的调度必然得到广泛的使用。1 2 3 存在的问题尽管众多的研究者对网格调度做出了大量的研究工作，并且在很多方面取得了开创性的成果，但仍然存在一些问题，这些调度算法大都在某些特定条件下进行研究，只适合应用于特定的网格任务调度模型之中。大部分的调度算法都侧重于考虑算法的某个方面，在特定的网格中，确实能得到很好的应用。但4j ：海大学硕十学位论文是由于系统自身的庞大性和涉及技术的多样性，使得人们还有很多探索和研究需要继续，如任务的划分目前还是一个n p 问题【2 1 1 ，尚没有有效的方法解决。什么样的调度模型可以适用于复杂的系统? 什么样的任务调度算法可以使系统具有更高的计算效率? 这些问题都还有待进一步的研究。1 3 本文的主要工作在网格技术飞速发展的同时，网格计算中的任务调度问题也变得越来越重要。任务调度的目的是在包含大量不同的计算机网络中，同时考虑各网格节点的计算性能、任务量大小、任务优先关系等参数，最优的分配任务，实现最佳的调度策略，从而充分利用网格资源，高效地完成计算任务。由于在网格环境中各处理器的运行速度、主机的负载、网络通讯的时间等是动态变化的，因此任务调度问题同时也是一个非常困难的n p 完全问题，这对于研究先进的调度算法将是一个挑战。好的任务调度策略将会在很大程度上提高网格资源的利用率和网格计算的有效性，推动网格技术的迸一步发展。因此，对于网格计算中的调度算法，如何优化数据依赖对计算有效性的影响，满足较高调度效率、网格计算环境动态性、计算有效性和任务q o s 需求等要求，这将会是今后的一个发展方向。本文基于基本遗传算法原理提出了适合网格环境的遗传算法，并将其作为网格任务调度的核心算法来更合理的调度网格任务。本文的工作丰要包括以下几方面：( 1 ) 解析网格计算环境，归纳网格计算环境下任务调度的特征，总结了网格任务调度的常见算法。( 2 ) 根据网格任务调度的特征，提出一种用d a g 限制任务优先关系的任务调度模型，设计并实现了一种遗传算法的改进算法。( 3 ) 基于g r i d s i m 上搭建网格仿真环境，并对本文所提出的任务调度算法进行了仿真。5上海大学硕十学位论文1 4 文章结构本文以介绍网格环境的概念和系统模型为起点，按照从理论到模型设计再到算法应用的实现路线，根据现有网格中任务调度算法的不足，本文提出了一种改进的遗传算法，仿真结果表明该算法能更有效解决网格任务调度问题。论文的组织结构和章节安排具体如下：第一章是论文的绪论，叙述工作的研究背景、主要的研究工作内容及创新之处，介绍论文的总体结构安排。第二章为全文的理论基础，详细给出了网格计算及其任务调度的定义、特点、体系结构，列举并分析了一些现有的任务调度算法。第三章介绍了遗传算法的基本原理，特点，简单流程和具体实现过程。第四章的内容是网格任务调度算法的详细设计。首先提出算法的模型，后面分步对他进行详细设计。第五章的内容是对网格任务调度算法的具体实现。首先介绍了g r i d s i m 仿真环境，并基于该仿真环境实现了算法，最后对算法结果进行了分析与评价。第六章对整篇论文进行总结，并对未来工作进行展望。6上海大学硕士学位论文第二章网格计算中的任务调度2 1 网格的定义随着高性能计算应用需求的迅猛发展，单台高性能计算机已经不能很好胜任某些超大规模应用问题的解决，同时，大量已存在的计算资源和设备的利用率不高，这就需要将地理上分布的、系统异构的多种计算资源通过高速网络连接起来，以共同解决科学计算等大型应用问题，即需要广域的高性能的网格技术。网格有时也称为网格计算或元计算( m e t a c o m p u t i n g ) 。网格是近年来在学术界和产业界逐渐兴起的一个研究领域。当前的i n t e r n e t 技术实现了计算机硬件的连通，w e b 技术实现了信息的共享，而网格技术目的是把整个i n t e m e t 整合成一台巨大的超级计算机，实现资源的全面共掣2 一】。简单地说，网格就是将计算资源、信息资源、数据资源、知识资源、专家资源等互连网上的所有资源连通、互操作，而达到真正的共享。网格是一个集成的计算资源环境，或者说是一个计算资源池。网格能够充分吸纳各种计算资源，并将它们转化成一种随处可得的、可靠的、标准的同时还是经济的计算能力。除了各种类型的计算机，计算资源还包括网络通信能力、数据资源、仪器设备、以至人等各种相关的资源【2 】。而基于网格平台的问题求解就是网格计算，这是网格和网格计算的广义定义。狭义的网格一般称为计算网格( c o m p u t a t i o n a lg r i d ) ，即主要用于解决科学与工程计算问题的网格，其中的网格资源主要是指分布的计算机资源；狭义的网格计算是指将分布的计算机组织起来协同解决复杂的科学与工程计算问题。当然，网格并不一定非要多么大。我们也可以构造地区性的网格( 如中科院计算所网格) 、企事业内部网格、局域网格。网格的根本特征不是它的规模，而是资源共享，消除了资源孤岛。2 2 网格的特性由于网格计算技术是基于分布式计算技术发展而来，因此两者具有许多公7上海大学硕士学位论文共特性，例如，它们都支持异构性，以屏蔽底层平台的差异；但网格计算又与分布式系统和并行系统有着重要的区别。由于网格计算是解决动态、异构的多管理策略虚拟组织中的协同资源共享问题，因而网格计算具有和分布式计算不同的如下特性：( 1 ) 分布与共享特性：分布性是网格的一个最主要的特点。分布性是指资源类型复杂、规模庞大、跨越的地理范围较广。网格资源虽然是分布的，但却是可以充分共享的。即网格上的任何资源都可以提供给网格上的任何使用者。这里共享的含义非常广泛，不仅指一个地方的计算机可以用来完成其它地方的任务，还可以指中间结果、数据库以及人才资源等各方面的内容。分布是网络硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特征。( 2 ) 自治的多策略组织：网格计算环境支持采用不同策略的多个组织之间的互操作，同时保留各个组织的自治性。一方面，网格中的各个资源都是属于提供者的，因此提供者拥有对资源的最高级别的管理权限，这体现了网格的自治性：另一方面，资源又必须接受网格系统的统一管理，否则不同的资源就无法建立相互之间的联系，无法实现共享和互操作，无法作为一个整体为更多的用户提供方便的服务。这是网格计算和分布式计算最本质的区别之一。( 3 ) 动态性与多样性：网格的动态性包括动态增加和动态减少两个方面的含义。动态性是网格资源管理的一个重要研究问题。当资源动态变化时，要求网格能够及时采取措施，实现任务的自动迁移，做到对高层用户透明和尽可能减少用户的损失。网格资源的动态性还带来了扩展性问题，就是说在网格的设计与实现时，必须考虑新资源与原有资源的融合。( 4 ) 适应性：各自治组织提供的资源往往已经在遗留系统中，因而网格计算要大规模商用还必须提供适应性支持，即必须在尽量不破坏遗留系统的前提下为应用提供单一的分布资源全局视图并汇聚各种分布的自治资源成为一个统一的环境。适应性的另一体现是可演化性，即整个环境可随着网格计算技术的发展而更新。( 5 ) 容错性：随着网格环境中参与协同任务的资源数目的增加，系统出错的概率也随之增加。和单服务的分布计算环境不同，网格计算环境中的协同任务8上海大学硕十学位论文往往要使用多个共享的相关服务，当其中某个服务失效会导致其它服务的状态异常，因而仪仪恢复失效的服务状态还不足以保持协同任务的顺利完成。( 6 ) 安全性：在真正进入日常的商业领域之前，网格计算的安全问题必须引起足够的重视。和仪限于单一组织范围的分布式计算环境不同，网格计算环境的安全系统必须支持高度灵活的共享关系定义和对共享资源的高级复杂控制，以支持细粒度的访问控制和单点登录等安全要求。在帮助客户和服务相互确定对方是否可信赖等方面，网格计算环境必须扮演一个关键角色。这个角色在存在着大量入侵机会的开放环境中起着关键的作用，这些入侵机会既可能来自于具有欺诈性的服务，也可能来自于行为不端的客户。2 3 网格体系结构2 3 1 五层沙漏结构五层沙漏结构【2 3 1 解决了通用的网格平台所面临的异构性、扩展性以及适应性等问题。在这一时期网格主要是针对大规模数据与计算问题的解决展开研究的，研究问题的重点主要是在科研领域。它是以协议为中心的“协议结构”，该结构的基本思想是：共享需要的互操作，而实现互操作需要定义协议，五层沙漏结构特别重视协议的定义。服务是由它使用的协议和实现的行为定义的，标准协议还得使用标准服务更加容易。标准服务的定义( 如对计算的访问，存取数据，资源发现，协同调度，数据重复等) 可以进一步提供增强能力，使虚拟组织参加者得到更多的服务。五层沙漏结构分为：构造层、连接层、资源层、汇聚层和应用层【2 4 1 ，结构如图2 一l 所示。( 1 ) 网格构造层的基本功能是控制局部的资源，向上提供访问这些资源的接口；( 2 ) 连接层的基本功能是实现相互的通信。它定义了核心的通信和认证协议，用于网格网络事务处理；( 3 ) 资源层的重要功能是实现单个资源的共享：9上海大学硕士学位论文( 4 ) 汇聚层的主要功能是协调“多种 资源的共享，即如何将下面以单个资源形式表现出来的资源集中起来，协调解决多个资源之间的问题；( 5 ) 应用层关系的是有什么样的资源可以提供给虚拟组织，解决不同虚拟组织的具体问题。、工具与戍用- i目录代理?j 诊断与监控等?：资源与服务：的安令访问：?各种资源j比如计算机、存储器i ，网络、仪器等、应用层汇聚层资源与连接层构造层图2 - 1 五层沙漏结构图五层结构的另一个重要特点就是沙漏形状。其含义就是：因为各部分协议的数量是不同的，对于最核心的部分，要能实现上层各种协议向核心协议的映射，同时实现核心协议向下层其它各种协议的映射，核心协议在所有支持协议的地点都应该得到支持，因此核心协议的数量不应该太多，这样核心协议就成了协议层次结构中的一个瓶颈，在五层结构中，资源层和连接层组成这一核心的瓶颈部分。2 3 2 开放网格服务体系结构开放网格服务体系结构( 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 ) 2 5 2 6 】是g l o b a lg r i df o r u m h t t p 的重要标准建议，是继五层沙漏结构之后最重要，也是目前最新的一种网格体系结构，被称为是新一代的网格结构。它是以服务为中心的“服务结构”。这里的服务是指具有特定功能的网络化实体。o g s a 中服务所指的概念很广，包括各种计算资源、存储资源、网络、程序和数据库等。简而言之，o g s a 中一切都是服务，实现的是对服务的共享，这样将资源、信息和数据等统一起来，十分有利于灵活的、一致的、动态的共享机制的实现p 】。1 0上海大学硕上学位论文o g s a 定义网格服务( g r i ds e r v i c e ) 2 7 1 为一种w e bs e r v i c e ，该服务提供了一组接口，这些接口定义明确并遵守特定的惯例，解决服务发现、动态服务创建、生命周期管理和通知等问题。以网格服务为中心的模型优点在于：方面，网格环境中所有的组件都是虚拟的，因此，通过提供一组相对统一的核心接口，并基于这些接口实现所有的网格服务，易于构造具有层次结构的、更高级别的服务。这些服务可以跨越不同的抽象层次，以一种统一的方式来看待。另一方面，虚拟化使得将多个逻辑资源实例映射到相同的物理资源上成为可能，在对服务进行组合时不必考虑具体实现，可以以底层资源组成为基础，在虚拟组织中进行资源管理。通过网格服务的虚拟化，可以将通用的服务语义和行为无缝地映射到本地平台的基础设施之上。2 3 3 网格服务g rids e r vic ew 曲s e r v i c e 被定义为可以被u r i ( u n i f o r mr e s o u r c ei d e n t i f i e r ) 识别的软件应用。它的接口和绑定可以用x m l 描述与发现，并且可以通过基于i n t e m e t的协议直接与其他基于x m l 消息的软件应用交互。o g s a 符合标准的w e bs e r v i c e 框架，并对其进行了扩展，提出了网格服务的概念，使得o g s a 可以支持临时服务实例，并且能够动态创建和删除。o g s a 定义了所谓的g r i d 服务：提供一套良好定义接口和遵循一定规范的w e b 服务。接口解决发现、动态服务创建、生命周期管理、通知和可管理性等问题；规范解决命名和可升级能力的问题。o g s a 现在还没有能够实现授权和并发控制。另外两个重要的问题，认证和可靠调用，被认为是一种服务协议绑定，因此不属于核心g r i d 服务定义的范围，但一个完整的o g s a 实现必须解决上述两个问题。这种对关键问题的分解增加了体系结构的通用性，同时又不损失其功能性。在o g s a 中，主要关注于服务：计算资源、存储资源、网络、程序、数据库以及其他类似资源都表示为服务。面向服务的观点使得如下一些特性成为可能：标准接口定义机制、本地远程透明性、对本地操作系统服务的适应以及统上海大学硕士学位论文一的服务语义。面向服务的观点还简化了虚拟化一即将不同实现封装成一个通用接口。虚拟化允许跨多个异构平台对资源进行一致地访问，并提供本地或远程定位的透明性，还可以将多个逻辑资源实例映射成同一物理资源，以及在一个v o 内基于更低级的资源组合进行资源管理。虚拟化允许服务组合，形成更复杂的服务无论正在被组合的服务是如何实现的。g r i d 服务的虚拟化也支持将通用服务语义行为无缝地映射到本地平台设施的能力。在o g s a 里，以一种标准格式w s d l ( w e bs e r v i c e sd e s c r i p t i o nl a n g u a g e )【2 胡来表示服务，服务的任何实现都以同样的方式被调用，虚拟化将变得更容易。w s d l 支持独立于服务调用的协议绑定的服务接口定义。w s d l 允许一个接口的多重绑定，包括分布式通讯协议( 例如h t t p ) 和同一主机上请求者与服务进程之间交- 瓦采用的本地优化绑定( 例如本地i p c ) 。其他绑定的属性可能包括可靠性( 和其他形式的q o s ) 、认证和信任状委派。就服务调用语义而言，绑定的选择应该总是对请求者透明的，但就其他方面而言，是不透明的：例如，请求者能够基于性能原因而选择个特殊的绑定。服务接口定义和访问绑定也独立于服务的功能实现。一个服务可以支持不同平台上的多种实现，不仪实现对本地平台设施的无缝覆盖，还可以通过服务实现的嵌套对虚拟的资源组合体进行无缝覆盖。简单地说，网格服务= 接口行为+ 服务数据。图2 2 是对网格服务的简单描述。1 2上海大学硕上学位论文一服务数据的访问一显示撤销一软状态生命周期一绑定特性一可靠激活g r i ds e r v i c e( 必要的)- - - - 啼其他接口( 可选的)i - - - _ - _ -标准接口：一通知一授权一服务注册一管理一开发+ 面向特别应用图2 2 网格服务示意图2 4 网格计算任务调度的特点网格计算任务调度系统具有以下几个特点：( 1 ) 任务调度是面向异构平台的。由于网格系统是由分布在互联网上的各类资源组成的，包括各类主机、工作站甚至p c 机，它们是异构的，可运行在u n i x ，w i n d o w sn t 等各种操作系统下，也可以是上述机型的机群系统、大型存储设备、数据库或其他设备。因此网格系统中的任务调度必须面向异构平台，并在这些平台上实现网格任务的调度。( 2 ) 任务调度是大规模的、非集中式的。由于网格系统是一个大到整个i n t e m e t 的分布式巨系统。要实现一种全局的统一集中的任务调度管理是根本不可能的。因此，网格的任务调度必须以分布、并行方式进行任务的管理与调度。( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要的，也是不可能的。( 4 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级计算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资源规模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展上海大学硕上学位论文性，不致降低网格系统的性能。( 5 ) 任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结构总是不停地改变：有的资源出现了故障，有的新资源要加入到网格中，有些资源重新开始工作等。总之网格的动态性是明显的，所以任务调度系统必须适应网格的这种动态性，从可利用的资源中选取最佳资源为用户提供应用服务。2 5 网格计算任务调度的主要目标简单地说，网格计算任务调度的目标就是要对用户提交的任务实现最优调度，并设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、经济原则( e c o n o m i cp r i n c i p l e s ) 等。( 1 ) 最优跨度。跨度是一个最主要、最常见的目标，指的是调度的长度，也就是从第一个任务开始运行到最后一个任务运行完毕所经历的时间。跨度越短说明调度策略越好。当用户向网格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可见，实现最优跨度是用户和网格系统的共同目标。( 2 ) 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题。网格系统更进一步扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的调度。解决好系统的负载均衡是一个非常重要的问题。( 3 ) 服务质量q o s 。网格系统要为用户提供计算和存储服务时，用户对资源需求情况是通过q o s 形式反映出来的。任务管理与调度系统在进行分配调度任务时，保障网格应用的q o s 是完全应当的。( 4 ) 经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都归属于不同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使用费用也应是不相同的。市场经济驱动的资源管理与任务调度必须使消费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久地发展下去。1 4上海大学硕士学位论文2 6 网格任务调度的体系结构网格被认为是能够对远程资源进行透明和高效访问的。网格调度服务则是对多样化的网格资源访问进行协调不可缺少的，这些资源包括可执行单元( 集群、工作站) 、网格带宽、数据、存储资源和软件。网格资源从属于不同的组织，而且通常它们都有自己属地的调度策略和管理方式，网格调度体系结构必须对调度提供不同层次的支持。即使是对网格上单一的资源，对资源的使用进行协调也是非常有必要的。例如一个计算单元和可视化设备互联，这需要在任务执行中对这两者进行协调，使计算单元和可视化设备能够协同工作。网格管理中实际上数据才是在使用网格资源时的连接件( c o n n e c t i n ge l e m e n t ) ，数据存在形式可以作为输入输出元素或者贯穿于资源使用的整个过程。因此，同步性和数据备份对网格调度系统而言是非常重要的。将网格作业分派到网格资源需要在网格调度阶段完成一系列的处理步骤，如资源选择、制订调度计划( 即调度过程) 、数据复制管理和i 0 传输、作业运行时监控。这些任务必须由一个建立在当前网络标准和规范之上的通用的网格调度系统支持。同时，网格调度系统也为上层应用提供其它基本的服务。对资源的使用情况可以被分成几种情况：( 1 ) 并行资源使用当一个作业运行在不同系统中并且需要同步的使用网格资源。( 2 ) 串行资源使用典型的，一个作业被分成若干相互关联的步骤，这些步骤可以分散在网格上不同的资源上执行。例如数据分析和分析结果显示就可以分布在两个计算网络上并行执行。( 3 ) 相互独立的作业对同一数据的访问指一个组织的多个研究者共享一个网格数据资源。例如，在高能物理研究领域，一个非常庞大的数据集往往为一个极大的研究群体所共享。显然，为了启动远程的一个工作实例，将这样的一个庞大的数据集传送过去不仅是耗时和i ：海大学硕士学位论文低效的，同时也要求远程结点有庞大的存储设备。一种替代的做法是可以适当的将数据复制到特定的位置上，从而使得多个网格应用能够就近取得必要的数据而受益。这和我们比较熟悉的w e b 缓存策略是相类似的。在此基础上，g g f( g l o b a lg r i df o r u m ) 提出了网格调度平台的核心网格服务：作业监控服务、记帐服务、网络服务、信息服务和数据管理服务等，它们之间相辅相成，构成了调度这一有机整体。如上2 3 所示。图2 3 网格调度平台结构2 7 现有任务调度算法介绍现有的任务调度算法可以分为在线模式( o n 1 i n e ) 和批模式( b a t c h m o d e ) 两种【2 9 】。在线模式是指任务- - n 来就映射到机器，该模式对每一个任务的映射只考虑一次，也就是说一旦任务被映射就不会再改变。批模式下，任务到来并不立即映射到机器，而是把任务收集起来组成一个任务集合，等映射事件到来后才对该集合中的任务进行集中映射。这个独立任务的集合称之为元任务。因此，批模式下的元任务包括新到达的任务( 也就是在最后一个映射事件之后到达的任务) 和已经映射但还没有开始执行的任务。批模式对独立任务的集合中每一个还没有开始执行的任务，在每一次映射事件中都进行考虑直到该任务开始执行为止。因此，批模式可以得到整个元任务的资源需求信息和更多任务的执行1 6卜海大学硕士学位论文时间，从而可以做出更合理的任务映射策略。本文介绍的任务调度算法为批模式的。现在大量的启发式算法被用于批模式的网格任务调度，常见的启发式算法有：o l b 、m e t 、m c t 、m i n - r a i n 、m a x m i n 、d u p l e x 、g a 、s a 、g s a 、t a b u 、a 木等1 1 种，下面对这1 1 种静态调度算法进行介绍。现在大量的启发式算法被用于分布式系统的任务调度，下面我们将常用的1 1 种启发式调度算法介绍如下：( 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 )o l b ( 随机负载均衡算法) 例的思想是：随机把一个任务分配给下一个可使用的机器，而不考虑任务在该机器上的期待执行时间。该算法的目的是要尽量使所有的机器处于工作状态，其优点是算法实现简单。但由于没有考虑任务的期待执行时间，因此利用该调度算法产生的匹配策略可能会导致一个比较差的m a k e s p a n 。( 2 ) m e t ( m i n i m u me x e c u t i o nt i m e )m e t ( 最小执行时间调度算法) 的思想是：以任意顺序把每一个任务分配给具有最小期待执行时间的机器，而不考虑该机器的可用性。m e t 的目标是把每一个任务分配给对其而言是最好的机器( 最小期待执行时间的机器) ，其缺点是可能导致机器之间严重的负载不均衡。该算法明显不适用于以一致的e t c 矩阵为特征的异构计算环境。( 3 ) m c t ( m i n i m u mc o m p l e t i o nt i m e )m c t ( 最小完成时间调度算法) 的基本思想是：以任意的顺序把每一个任务分配给具有最小期待完成时间( 机器可用时间+ 任务期望执行时间) 的机器。该算法可能导致一些任务没有办法调度给具有最小执行时间的机器，但其结合了o l b 算法和m e t 算法的优点，避免了使o l b 算法和m e t 算法运行得很差的环境出现。( 4 ) m i n m i nm i n m i n 调度算法的思想是尽可能把每一个任务分配给最早可用且执行最快的机器，m i n m i n 算法是基于最小完成时间( m c t ) 的。但m i n - m i n 算法在1 7上海大学硕士学位论文每一次映射中考虑的是全部未分配的任务，而m c t 算法在次映射中只是考虑一个任务。( 5 ) m a x r a i nm a x m i n 算法的思想与m i n m i n 算法的思想恰恰相反，它是将最好的资源分配给最大的作业，从而获得总体作业的最小完成时间。( 6 ) d u p l e xd u p l e x 调度算法是m i n m i n 算法与m a x m i n 算法的结合。d u p l e x 调度算法对一个