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

华南师范大学硕士学位论文 任务优先级和q o s 约束的m i n - m i n 算法，并通过几组对比实 法比前面两种算法具有更短的时间跨度，同时网格资源负载 ，任务调度，g r i d s i m ，q o s ，时间跨度 1 膏 j 1 - 一 网格计算中任务调度算法的研究 a b s t r a c t r e s e a r c ho ft a s ks c h e d u l in ga l g o rlt h m ing ridc o m p u tin g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：g a o q i a n g s u p e r v i s o r ：l i u b o g r i dc o m p u t i n gb u i l d i n go ni n t e r a c ti sak i n do fw i d ea r e an e t w o r kc o m p u t i n gt e c h n o l o g y , i t i n t e g r a t e s a l ls o r t so fr e s o u r c e st h a t d i s p e r s eo ng e o g r a p h ye f f i c i e n t l y , s u p p o r t i n g a n e n v i r o n m e n to fh i g hp e r f o r m a n c ec o m p u t i n ga n di n f o r m a t i o ns e r v i c et os h a r er e s o u r c e t h e r e s e a r c ho ft a s ks c h e d u l ea l g o r i t h mw h i c hi sv e r yi m p o r t a n ti nt h er e s e a r c ho fg r i dc o m p u t i n g t e c h n o l o g yh a sd i r e c t l yr e l a t i o n s h i pw i t ht h ee f f i c i e n c ya n dq u a l i t yo fs c h e d u l ei ng r i dc o m p u t i n g t e c h n o l o g y s i n c et h ec h a r a c t e r so fd y n a m i s m ，h e t e r o g e n e i t ya n da u t o n o m o u so fag r i dr e s o u r c e ； f u r t h e r m o r e ，i ti sw e l lk n o wt h a tt h et a s ks c h e d u l i n gi san p - c o m p l e t ep r o b l e m ，h o wt od e s i g na n e x c e l l e n tp e r f o r m a n c es c h e d u l ea l g o r i t h ma n di n c r e a s et h ee f f i c i e n c yo f g r i dc o m p u t i n ga sf a r a s p o s s i b l ei sas u b j e c tt h a ti sw o r t h yt or e s e a r c h h e u r i s t i ca l g o r i t h mi sae f f e c t i v em e t h o dt os o l v et h en p c o m p l e t ep r o b l e m m i n m i n a l g o r i t h m ，ac l a s s i ch e u r i s t i ca l g o r i t h m ，h a st h ea d v a n t a g eo fr e a l i z a t i o ne a s i l ya n ds h o r tt i m es p a n ， a n di ta l s oh a st h ed i s a d v a n t a g eo fi m b a l a n c eo fm a c h i n e q o sg u i d e dm i n - m i na l g o r i t h md i v i d e s t a s k si n t oh i g hq o st a s ka n dl o wq o st a s k , a n dt h eh i i g hq o st a s ki sp r i o rt ol o wq o st a s kt o s c h e d u l eu s i n gm i n - m i na l g o r i t h m ，w h i c hc a l li m p r o v et h em i n - m i na l g o r i t h mi ns o m ew a y , b u t t h e r ei sd e f i c i e n c yo fq o sg u i d e dm i n m i na l g o r i t h ma n di th a st h es p a c et oi m p r o v e b a s eo n t h i s ，t h i sp a p e rf o c u s e so nt h ef o l l o w i n ga s p e c t ： 1 i ti n t r o d u c e dt h eb a s i cc o n c e p t ，c h a r a c t e r , a r c h i t e c t u r ea n ds c h e d u l i n gm o d e lo fg r i d c o m p u t i n g a n dr e s e a r c h e dt h et y p ea n dc h a r a c t e ro ft a s ks c h e d u l i n ga l g o r i t h mi ng r i dc o m p u t i n g 2 i ta n a l y z e dt h ec h a r a c t e ra n dt a r g e to ft a s ks c h e d u l i n ga n dr e s e a r c h e ds o m ec l a s s i cg r i d i i i 华南师范大学硕士学位论文 s i m u l a t o r s ，a n dt h es i m u l a t i o nt o o ln a m e dg r i d s i mw i l lb eu s e di nt h es i m u l a t i o ne x p e r i m e n to f t h i sp a p e r 3 t h e r ei ss o m ed e f i c i e n c yo fm i n - m i na l g o r i t h ma n dq o sg u i d e dm i n - m i nb yt h ea n a l y s i s a n dr e s e a r c ho ft h e m ，a n dp r o p o s i n gt h eb a s e do nt a s kp r i o r i t ya n dq o sg u i d e dm i n - m i n a l g o r i t h ma i m i n ga tt h ed e f i c i e n c y 4 i ta n a l o gr e a l i z e dt h 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 na l g o r i t h ma n db a s e do n t a s kp r i o r i t ya n dq o sg u i d e dm i n - m i na l g o r i t h mu s i n gp r o g r a mb a s e do ns i m u l a t o rg r i d s i m ，a n d p r o v e dt h a tt h ea l g o r i t h mi m p r o v e dh a ss h o r t e rt i m es p a na n d b e t t e rb a l a n c eo f g r i dr e s o u r c eb y s e v e r a ls e t so fc o m p a r a t i v ee x p e r i m e n t s k e yw 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 r i d s i m ，q o s ，t i m e s p a n i v 网格计算中任务调度算法的研究 目录 摘要i a b s t r a c i i i e jj i t 、， 第1 章绪论。l 1 1课题的研究背景与意义1 1 1 1 研究背景1 1 1 2 研究意义2 1 2 网格调度算法研究现状2 1 3 本文的主要工作4 1 4 本文结构安排。5 第2 章网格任务调度模型及算法。6 2 1网格基本理论。6 2 1 1 网格的概念。6 2 1 2 网格的特点6 2 1 3网格体系结构。7 2 2网格任务调度的特点和目标1 1 2 2 1网格任务调度的特点l l 2 2 2 网格任务调度的目标1 2 2 3 网格调度模型1 3 2 3 1g l o b u s 1 3 2 3 2 l e g i o n 1 3 2 3 3 c o n d o r 1 4 2 3 4n i m r o d 4 3 1 4 2 4 经典启发式调度算法简介1 4 2 4 1 随机负载均衡算法1 4 2 4 2 模拟退火算法1 5 2 4 3 遗传算法15 2 4 4 蚁群算法1 6 2 4 5m i n m i n 算法17 2 5 本章小结。1 7 第3 章网格模拟器的研究1 8 3 1 网格模拟环境的必要性1 8 3 2 几种网格模拟器简介1 9 3 2 1b r i c k s 1 9 3 2 2m i c r o g r i d 19 3 2 ：；g r i d s i m 2 0 3 2 4s i m g r i ( 1 ：! ( ) 3 3 网格模拟器的选择2 1 3 4g r i d s i m 的体系结构和任务调度机制2 1 3 4 1g r i d s i m 的体系结构2 2 3 4 2g r i d s i m 的任务调度机制。2 3 v 华南师范大学硕士学位论文 3 5 第4 章 4 1 4 2 4 3 4 4 4 5 第5 章 5 1 本章小结2 4 m i n m i n 调度算法的改进2 5 相关定义2 5 m i n - m i n 算法的基本原理2 6 q o sg u i d e dm i n m i n 算法的基本原理2 7 基于任务优先级和q o s 约束的m i n - m i n 算法的提出2 9 4 4 1 问题的提出2 9 4 4 2p r iq o sg u i d e dm i n m i n 算法3 0 本章小结31 改进的m i n m i n 算法的实现3 2 实验环境的搭建3 2 5 1 1 网格任务( g r i d l e t ) 的创建3 2 5 1 2 网格资源的创建3 3 实验设计3 4 5 2 1 总体设计思想3 4 5 2 2 调度算法的实现3 4 实验结果分析和结论3 6 5 3 1 实验数据3 6 5 3 2 结果分析和结论3 7 5 4 本章小结4 0 第6 章总结与展望4 l 参考文献4 3 攻读硕士学位期间公开发表的学术论文4 7 致 射4 8 v i 网格计算中任务调度算法的研究 第1 章绪论 1 1 课题的研究背景与意义 1 1 1 研究背景 网格试图连通地理上广域分布的各种资源，将这些资源通过高速网络大规模 集成，形成一台巨大的超级计算机，实现计算资源、存储资源、通信资源、软件 资源、信息资源、知识资源等的全面共享。通过提供可扩展的大规模的各种种类 的资源，网格不仅突破了计算能力、存储能力大小的限制，而且突破了资源地理 位置的限制，能够对资源消耗非常大的问题进行求解，进而可以求解极其复杂， 甚至以前无法解决的问题。网格计算提供的这种资源共享模式，将给人们带来便 捷、经济且极其丰富的资源。因此，网格技术的发展对于各行各业，尤其是科学 研究、经济建设等领域，都将产生极大的推动作用和深远的影响。 网格虽然提供了强大的功能，但也在理论研究和应用实现上遇到了巨大的挑 战，即便如此，在网格计算所能产生的巨大利益的驱动下，网格计算在理论和实 践中不断取得进展和突破。国内外许多国家都对网格计算投入了巨大的人力物 力，不断启动大型的网格研究项目，其中国外具有代表性的研究项目主要有 g l o b u s 、l e g i o n 嘲、n i m r o d g 嘲嘲、a p p l e s 5 3 和c o n d o r 嘲等。我国在网格方面起 步比较晚，现正加大研究力度，投入了大量的人力和物力，已经完成的网格研究 项目主要有先进计算基础设施a c i ( a d v a n c e dc o m p u t a t i o n a li n f r a s t r u c t u r e ) 和国家高性能计算环境n h p c e ( n a t i o n a lh i g hp e r f o r m a n c ec o m p u t i n g e n v i r o n m e n t ) ；目前正在进行的网格项目主要有：中国网格( c h i n ag r i d ) ，上 海教育科研网格和织女星网格盯1 等。 在网格计算领域的诸多研究方向中，任务调度问题是关键问题之一，也是最 有挑战性的研究方向之。m i n m i n 算法是一个简单、快速的算法。并且性能比 较好。m i n - m i n 算法是任务调度经典算法之一，许多算法都是在它的基础上进行 优化和改进的。它通过两次计算最小值完成启发选择，目的是将大量的任务映射 给完成它最早而且执行它最快的计算资源，以使得全部任务完成时间最小。由于 l 华南师范大学硕士学位论文 m i n - m i n 算法总是优先调度短任务，只有当机器空闲时间很长时，长任务才能得 以执行，这样便容易导致资源利用率低、主机负载不均衡的问题，尤其是当任务 集中长任务的比例很大的时候，上述问题就更为严重。q o sg u i d e dm i n m i n 算 法国1 对m 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 s 约束的m i n - m i n 网格任务调度算法，该算法根据任务优先级和对资源的q o s 要求为其提供合理有 效的调度。 1 1 2 研究意义 网格任务调度是网格的核心技术之一，随着网格技术的不断发展，网格平台 对任务调度提出了新的要求。网格由大量分布共享的异构资源组成，这些资源协 同提供了巨大的计算能力。由于网格计算中资源具有分布性、动态性、异构性、 多样性、自治性等特征，使得网格环境下的任务调度所面临的问题比传统分布式 环境要复杂得多，如何对任务进行调度以满足用户的需求是一个极具挑战的问 题，一个良好的调度策略能高效地协调和分配网格资源，使资源利用率较高，并 且能有效降低网格计算的总执行时间和总耗费，从而使网格达到最佳性能。因此， 设计一个网格环境下的高效合理的任务调度算法对促进网格计算的发展和提高 网格计算的实用性具有十分重要的意义。 1 2 网格调度算法研究现状 在网格计算中，任务调度的实质就是将n 个相互独立的任务分配到m 个异构 可用资源上，使得总任务的完成时间最小以及资源得到充分利用。网格计算的任 务调度已经被证明是一个n p 完全问题。 网格任务调度作为网格计算的关键技术之一，长期以来得到了国内外研究者 的广泛重视，提出了多种调度算法。以下列出几种具有代表性的算法。 ( 1 ) 基于市场供求关系的任务调度 基- f 市场供求关系的任务调度阳1 ：其核心思想是仿照日用品买卖市场调控策 2 网格计算中任务调度算法的研究 略来对计算资源进行优化组合。具体的实现如下：把计算资源的标上“价格”， “价格 被设定为介于资源的需求和提供之间，当计算资源的“价格”确定后， 它们就按照“先来先服务 的原则进行分配，统一地由调度者进行调度。对于同 一个计算资源，由于所选的策略和所处的环境不同，在实际的调度过程中可能会 被标上不同的“价格”，因而需要调度者进行策略级的全局优化。 ( 2 ) 基于资源预留的任务调度 基于资源预留的任务调度口是用来解决在f i r s t f i t ，b e s t f i t ，g r e e d y 等任 务调度算法中的对资源要求较大的任务长时间不能得到运行的问题。对于长时间 不能运行的任务，可以采取资源预留的策略，即当一个任务在队列中等待的时间 超过一定的值，对它所需要的资源进行预留，即这些资源中的一部分成为可用时， 不再分配给其它的任务，一直到预留的所有资源都已得到满足时，将该任务投入 运行。预留策略对于调度并行和串行混合的任务队列显得尤其重要。由于并行任 务需要较多的c p u 资源，它要等到几个c p u 同时空闲时才能运行。如果系统中有 很多串行任务，当有少数c p u 空闲时，它也不能被执行，而此时空闲的c p u 很容 易被其它串行任务或需要c p u 数目少的并行任务所使用。资源通过预留策略，就 可以解决这个问题。但它导致了少量的资源空闲时间，牺牲了系统资源的利用率。 对于该策略还可以基于优先级和b e s t f i t 机制进行扩展，形成“联合预留 ( c o r e s e r v a t i o n ) ，即当计算请求被提出时，应用和计算网格系统之间将签订 一个资源预留协议，只有当q o s 的要求发生冲突时，调度者才会检查计算请求， 同时如果在整个计算请求中有一个需要的资源不可得，那么整个计算请求将被全 部抛弃。 ( 3 ) 基于a g e n t 的任务调度 基于a g e n t 的任务调度1 2 3 的基本思想是将每个网格资源节点均封装成为一 个a g e n t ，把网格系统看成是一种多层次系统的集合。这样，所有分布于网格系 统中不同地方的网格资源节点( 如一个集群) 就构成了底层的系统，它们为基于网 格的应用程序提供高性能计算能力，于是，调度问题被简化为如何在各a g e n t 之 间分配计算任务并随时根据的a g e n t 变化情况进行调整，以及在各a g e n t 内如何 进行子任务的继续分配。这样的层次结构具有高度的可扩展性，便二r 在网格这样 的庞大异构环境中运用n 羽。 华南师范大学硕士学位论文 ( 4 ) 基于p e t r i 网的任务调度 p e t r i 网是信息处理系统描述和建模的有力工具之一，它具有并行性、不确 定性、异步及分布描述和分析能力，在描述如工作流系统等模型和分析方面， p e t r i 网显示出其强大的模型描述和性能分析能力。而网格应用可分解成在网格 资源上执行的任务的组合，与工作流系统类似，也常用p e t r i 网来描述网格应用 1 4 1 。文献 1 5 提出了考虑子任务之间通信的调度模型( e t p n 模型) 。 ( 5 ) 基于启发式方法的任务调度 任务调度问题在许多情况下非常难以处理，需要使用启发式算法才能在合理 时间内完成。但使用启发式算法又不一定能够求得最优解，一般只能求得相对满 意解。所谓启发式算法，是指某种算法所求解的最优化问题是n p 完全的，只能 寻求一个在多项式时间内运行的近似算法，并且对于所有的实例，其近似解与理 论最优解值之比接近于1 这种近似算法常常是基于一些直观的启发，在可行解 的基础上再逐步优化，逼近最优解。虽然启发式算法在数学理论上还不能令人满 意，但在实际应用时确实有效、可行的n 6 1 。 1 3 本文的主要工作 本文从理论和实践方面对网格环境下m i n - m i n 算法及其改进算法进行了较 为深入的研究。论文的主要工作如下： ( 1 ) 了解网格环境下任务调度的相关概念，并且分析了主要的任务调度算 法和任务调度目标，重点研究了启发式算法，并对网格模拟器进行了分析和比较。 ( 2 ) 对网格任务调度算法中的经典算法m i n m i n 算法进行了研究，重点分 析了q 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 算法的 不足，并在此基础之上对m i n m i n 算法进行改进。 ( 3 ) 基于m i n m i n 算法的改进思想，以g r i d s i m 为网格环境模拟工具，使 用j a v a 语言编码实现m i n m i n 算法、q o sg u i d e dm i n - m i n 算法和改进后的 m i n - m i n 算法，从任务执行跨度和资源负载均衡两方面验证改进后算法的可行性 及优越性。 4 网格计算中任务调度算法的研究 1 4 本文结构安排 全文总共分为6 章 第1 章绪论。主要概述了网格任务调度算法的研究背景、意义及研究现状。 第2 章网格任务调度模型及算法。主要阐述了网格的特点和体系结构，网 格调度的特点、目标以及网格调度模型，最后介绍了典型的网格调度算法。 第3 章网格模拟器的研究。主要对典型的网格模拟器进行了分析和研究， 指出了网格模拟器的必要性，并分析和比较了几种模拟器，选择g r i d s i m 作为实 验平台，并对其体系结构和调度过程进行了介绍。 第4 章m i n m i n 算法的改进。主要分析了m i n - m i n 算法和q o sg u i d e d m i n - m i n ，然后指出了它们的不足并在其基础上提出了基于任务优先级和q o s 约 束的m i n m i n 算法。 第5 章改进m i n - m i n 算法的实现。利用g r i d s i m 实现了m i n m i n 算法、q o s g u i d e dm i n - m i n 算法和基于任务优先级和q o s 约束的m i n m i n 算法，然后对实 验结果进行了分析和比较。 第6 章总结与展望。总结全文，指出了自己所做的工作以及本文需要完善、 改进的地方。 华南师范大学硕上学位论文 第2 章网格任务调度模型及算法 2 1 网格基本理论 2 1 1 网格的概念 网格( g r i d ) 产生于上世纪九十年代中期，它的概念来源于电网，人们试图实 现类似于家用电器能够方便的从电网中使用电力资源，用户能够从广域分布的资 源池中获得所需的资源。网格有着多种不同的定义，1 9 9 8 年美国计算机专家 i f o s t e r 和c k e s s l e m a n 在网格：一种未来计算基础设施蓝图n 7 1 一书中把 网格定义为：网格是构筑在互联网上的一组新兴技术，它将互联网、计算机、大 型数据库、传感器、远程设备等融为一体，为科技人员和普通老百姓提供更多的 资源、功能和服务。随着w e bs e r v i c e 的兴起，f o s t e r ，k e s s l e m a n 和t u e c k e 于2 0 0 1 年将网格重新定义为“在动态的，多机构的虚拟组织中协调资源共享和 协同解决问题n 引。因此，网格就是一个集成的计算与资源环境，它能够把这个 互联网集成为一台虚拟的巨大的超级计算机，实现全球范围的计算资源、存储资 源、数据资源、信息资源、知识资源、专家资源、设备资源等广泛分布的资源全 面共享。网格是继万维网之后出现的一种新型网络计算平台，属于分布式计算技 术中的种。 2 1 2 网格的特点 网格作为一种先进技术和基础设施，和其他的系统相比，具有如下几个重要 特点1 钉： ( 1 ) 分布与共享性。分布性是指网格资源是分布在不同地理位置，而不是 集中在一起，这决定了基于网格的计算一定是分布式计算而不是集中式计算。分 布性是网格的最主要的一个特点。网格资源虽然是分布的，但是它们却是可以充 分共享的，即网格上的任何资源都可以提供给网格上的任何用户使用。共享是网 格的目的，解决分布资源的共享问题是网格的核心内容。分布性是网格资源在物 6 网格计算中任务调度算法的研究 理上的特征，而共享是在网格软件下实现的逻辑上的特征，这两者对于网格来说 都是非常重要的。 ( 2 ) 自相似性。自相似性是指网格的局部和整体之间存在着一定的相似性， 局部往往在许多地方具有全局的某些特征，而全局的特征在局部也往往有一定的 体现。 ( 3 ) 多样性。多样性是指网格资源是异构和多样的，即在网格环境中允许 有不同体系结构的计算机系统和不同类别的资源，因此网格系统必须能够解决这 些不同结构、不同类别资源之间的通信和互操作问题。 ( 4 ) 动态性。动态性是指网格并不是一成不变的，原来拥有的资源或者功 能，在某个时刻可能会出现故障或者不可用；而原来没有的资源，可能在某个时 刻会加进来。网格资源的动态变化特点要求网格管理必须充分考虑并解决好这一 问题，它决定了网格一定要具有很高的可扩展性和自适应性。 ( 5 ) 自治性与管理的多重性。自治性是指网格资源的拥有者对该资源具有 最高级别的管理权限网格应该允许资源拥有者对他的资源有自主的管理能力；网 格的管理具有多重性，一方面网格资源的拥有者对网格资源具有自主性的管理权 限，另一方面有要求网格资源必须接受网格的统一管理。 2 1 3 网格体系结构 网格体系结构就是关于如何建造网格的技术描述。它给出了网格的基本组成 与功能，描述了网格各组成部分的关系以及它们集成的方式或方法，刻画了支持 网格有效运转的机制。合理的网格体系结构是建立良好网格的核心，只有建立合 理的网格体系结构，才能够设计和建造好网格系统，才能够使网格更加高效更加 有效地发挥其作用。 目前网格技术流行的三个网格体系结构主要有三个：第一个是i a nf o s t e r 等 人早些时候提出的五层沙漏结构( f i v e l e v e ls a n d g l a s sa r c h i t e c t u r e ) ；第二个是 以i b m 为代表的工业界的影响下，考虑w e b 技术的发展与影响后，i a nf o s t e r 等结合五层沙漏结构和w e bs e r v i c e 提出的开放网格服务体系结构( o p e ng r i d s e r v i c e sa r c h i t e c t u r e ，o g s a ) ；第三个是由g l o b u s 联盟、i b m 和h p 于2 0 0 4 年 初共同提出的w e b 服务资源框架( w 曲s e r v i c e sr e s o u r c ef r a m e w o r k ，w s r f ) 7 华南师范大学硕士学位论文 ( 1 ) 五层沙漏结构。 五层沙漏结构【1 9 】是一种具有代表性的网格体系结构，其影响十分广泛，它的 特点就是简单，主要侧重于定性的描述而不是具体的协议定义，容易从整体上进 行理解。在五层沙漏体系结构中，最基本的思想就是：以协议为中心，强调服务 与a p i 和s d k 的重要性。该结构的设计原则就是要保持参与的开销最小，即作 为基础的核心协议较少，类似于o s 内核，以方便移植。另外，沙漏结构管辖多 种资源，允许局部控制，可用来构建高层的、特定领域的应用服务，支持广泛的 适应性。五层沙漏结构模型的结构如图2 1 所示。 二二二二二至 二二二二二i 图2 1 五层沙漏模型 五层沙漏模型由构造层、连接层、资源层、汇聚层和应用层构成。 第一层是构造层( f a b r i c ) 。构造层的基本功能就是控制局部的资源，包括查 询机制( 发现资源的结构和状态等信息) 、控制服务质量的资源管理能力等，并 向上提供访问这些资源的接口。构造层资源提供的功能越丰富，则构造层资源可 以支持的高级共享操作就越多，否则在高层实现这样的服务就会有较大的额外开 销。 第二层是连接层( c o n n e c t i v i t y ) 。连接层的基本功能是为下层的物理资源提 供安全的数据通信能力。连接层为各个孤立的单个资源之间建立了联系，这是资 源之间进行互操作的前提。该层定义了网格中网络处理的核心通信协议和认证协 议。通信协议使构造层的资源间的数据转换成为可能。认证协议基于通信服务提 供确认用户和资源身份的安全机制。 第三层是资源层( r e s o u r c e ) 。资源层的主要功能就是实现对单个资源的共 享。资源层建立在连接层的通信和认证协议之上，定义的协议包括安全初始化、 监视控制单个资源的共享操作、4 f 计、计费等。资源层的l 办议只考虑单个的局部 资源，忽略了全局状态和跨越分布式资源集合的原子操作，其协议实现调用构造 8 网格计算中任务调度算法的研究 层的功能以访问和控制本地资源。 第四层是汇聚层( c o l l e c t i v e ) 。汇聚层的主要功能是协调多种资源的共享。 汇聚层组件建立在资源层和连接层形成的协议瓶颈之上，它们能够在不对资源强 加新的要求的情况下实现广泛的和多样化的共享行为，如目录服务，协同分配， 调度和代理服务等。 第五层是应用层( a p p l i c a t i o n ) 。应用层的主要功能是确定提供什么样的资 源给虚拟组织，以解决不同虚拟组织所面临的具体问题。 五层结构的一个重要特点就是沙漏形状。其内在的含义就是：因为各部分协 议的数量是不同的，对于最核心的部分，要能够实现上层各种协议向核心结构的 映射，同时实现核心协议向下层其它各种协议的映射，核心协议所有支持网格计 算的地点都应该得到支持，因此核心协议的数量不应该太多，这样核心协议就形 成了协议层次结构中的一个瓶颈，在五层结构中，资源层和连接层共同组成这_ 核心的瓶颈部分。 ( 2 ) 开放网格体系结构。 开放网格体系结构o g s a l 2 0 1 是继五层沙漏结构之后最重要、也是最新的一种 网格体系结构，被称为是下一代网格结构。五层沙漏结构是以协议为中心的“协 议结构 ，而o g s a 是以服务为中心的“服务结构”。在o g s a 框架中，将一切 抽象为服务，包括各种计算资源、存储资源、网络、程序、数据库等等，简而言 之，一切都是服务。这种观念，有利于通过统一的标准接口来管理和使用网格。 网格技术( 如g l o b u s 软件包) 和w e bs e r v i c e 是o g s a 的两大核心技术。 g l o b u s i z l 】是一种基于社团的、开放结构、开放源码的服务的集合，也是支持网格 和网格应用的软件库，是被科学和工程计算领域广泛接受的网格技术解决方案。 该工具包解决了安全、信息发现、资源管理、数据管理、通信、错误检测以及可 移植等问题；w e bs e r v i c e 是一种标准的存取网络应用的框架。x m l 协议相关 的工作是w r e bs e r v i c e 的基础。 w | e bs e r v i c e 中几个比较重要的协议标准犯2 1 是s o a p ( s i m p l eo b j e c ta c c e s s p r o t o c o l ，简单对象访问协议) 、w s d l ( w e bs e r v i c ed e s c r i p t i o nl a n g u a g e ，网络 服务描述语言) 、w s i n s p e c t i o n ( w e bs e r v i c ei n s p e c t i o n ，w 曲服务探测) 、l d a p ( l i g h tw e i g h td i r e c t o r ya c c e s sp r o t o c o l ，轻量级目录访问协议) u d d i ( u n i v e r s a l 9 华南师范大学硕士学位论文 d e s c r i p t i o nd i s c o v e r ya n di n t e g r a t i o n ，统一描述发现和集成) 。 o g s a 结构从下到上依次是资源层、w e b 服务层、基于o g s a 架构的服务 层、网格应用程序层( 如图2 2 所示) 【2 3 】 i 应用( a p p l i c a t i o n s ) i l o g s a 体系结构的服务( o g s ah r c h i t e c t e ds e r v i c e s ) l 回国圉围困圉 图2 2 基于w 曲服务的o g s a 架构 第一层是资源层。资源层的概念是o g s a 以及通常意义上的网格计算的中 心部分，它包括物理资源和逻辑资源，物理资源之上是逻辑资源，它们通过虚拟 化和聚合物理层的资源来提供额外的功能，通用的中间件，比如文件系统、数据 库、目录、工作流管理和安全认证等，在物理网格之上提供这些抽象服务。 第二层是w e b 服务层。所有网格资源( 逻辑的与物理的) 在这一层都被理解为 服务。它为所有网格资源指定标准的接口、行为与交互，提供动态的、有状态的 和可管理的w | e b 服务的能力。 第三层是基于o g s a 架构的网格服务层。它定义基于网格架构的核心服务， 这些核心网格服务包括：服务管理、服务通信、策略服务、安全服务等。这些服 务的提供，使得o g s a 变成更加有用的面向服务的架构。 第四层是网格应用层。网格用户可以使用其提供的可视化工具或环境开发各 种应用系统，是用户需求的具体体现。 ( 3 ) w e b 服务资源框架。近年来的实践证明，o g s i 存在明显的不足乞主 要表现在：过份强调网格服务和w e b 服务的差别，导致两者之间不能更好地融 合在一起；单个规范中的内容太多，所有接口和操作都与服务数据有关，缺乏通 用性，而且o g s i 规范中没有对资源和服务进行区分；封装资源的状态，将具有 l o 网格计算中任务调度算法的研究 状态的资源建模为w e b 服务，这种做法引起了“w e b 服务没有状态和实例”的 争议，同时某些w e b 服务的实现不能适应网格服务的动态创建和销毁。正是在 这种情况下，w e b 服务资源框架被提了出来。 w e b 服务资源框架( w e bs e r v i c er e s o u r c ef r a m e w o r k ，w s i 碍) 提供了一种 利用w e b 服务建模和访问有状态资源的通用开放框架，它对o g s i 的进行了重 构和发展，w s r f 可以看做是结合新的w e b 服务标准( w s a d d r e s s i n g ) 基础上 对o g s i 的重新整合，这种整合使得w s r f 与现有w e b 服务标准兼容，从而可 以利用现有的服务开发工具构建网格计算设施，避免对扩展工具的要求。 w s r f 框架包括w e b 服务资源特性( w sr e s o u r c ep r o p e n i e s ) 、w e b 服务资 源生命期( w sr e s o u r c el i f e t i m e ) 、w e b 服务可更新引用( w sr e n e w a b l e r e f e r e n c e ) 、w e b 服务基本错误( w sb a s ef a u l t s ) 和w e b 服务服务组( w ss e r v i c e g r o u p ) 五个规范。w s r f 规范是针对o g s i 规范的主要接口和操作而定义的， 它保留了o g s i 中规定的所有基本功能，只是改变了某些语法，并且使用了不同 的术语进行表述。 w s r f 作为o g s a 最新的核心规范，它的提出加速了网格和w | e b 服务的融 合，以及科研界和工业界的接轨，对推动网格应用程序走向实际的桌面应用也很 有帮助。 2 2 网格任务调度的特点和目标 在网格环境中，任务和资源的数目都比较大，任务和资源之间的匹配关系也 比较复杂。任务与任务、任务与资源、资源与资源之间的相互关系最终都会影响 任务的调度顺序和任务与资源之间的匹配。 2 2 1 网格任务调度的特点 网格计算任务调度具有以下几个特点：瞳钔 ( 1 ) 任务调度是面向异构平台的。由于网格系统是由分布在i n t e r n e t 上的各 类资源组成的，包括各类主机、工作站甚至p c 机，它们是异构的，可运行在u n i x 、 l i n u x 、w i n d o sn t 等各种操作系统下，也可以是上述机型的机群系统、大型存 储设备、数据库或其他设备。因此网格系统中的任务调度必须面向异构平台，并 l l 华南师范大学硕士学位论文 在这些平台上实现网格任务的调度。 ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统是一个大到整个 i n t e r n e t 的分布式巨系统。要实现一种全局的统一集中的任务调度管理是根本 不可能的。因此，网格的任务调度必须以分布、并行方式进行任务的管理与调度。 ( 3 ) 任务调度不干涉网格节点内