（计算机应用技术专业论文）基于wsrf的网格资源调度系统的研究.pdf

华北电力大学硕士学位论文摘要 摘要 本文在对网格调度系统结构、服务网格资源描述方法、网格工作流技术和启发 式调度算法的研究基础上，提出了基于工作流的网格服务资源的调度过程模型，设 计实现了基于w s r f 的网格资源调度系统。采用语义描述方法实现了网格任务不同 层面需求之间的映射，向用户屏蔽了网格资源动态、异构的特性；对遗传算法和决 策路径选择算法进行了改进，并通过实验分析确定两种算法在系统中互补使用；实 现了服务在任务执行时的动态绑定，最大程度减少了网格资源动态性对系统调度的 影响；实现了调度过程中的异常处理，并对流程级异常和服务级异常区别处理。实 验结果表明，系统实现了网格服务资源的动态调度，具有一定的理论和实用价值。 关键词：w e b 服务资源框架，服务网格，网格工作流，网格调度，调度算法 a b s t r a c t a c c o r d i n gt 0m er e s e a r c ho n 鲥d d i n ga t t 锄p c rs y s t 锄蛐m c t u r c ，m ed e s c r i p t i o no f s e r v i c e 鲥d d i n gr e s o u i e ，鲥d d i n gp u r s u i tt e c t m i c a la n de l i c i t a t i o na t t e m p e ra l g o r i t h m i c ，t h e t e x tb u i l d st l l ea t t 锄p e r - 】p r o c e s sm o d e lb a s e do nt 1 1 ep u r s u i t 鲥d d i n gs e r v i c er e s o u r c e 锄d r e a l i z e sn l e 鲥d d i n gr e s o l 】r c ea t t 伽p e r e ds y s t e i l lb yw s i 也i tr e a l i z e st h em a p p i n g 锄o n gm e d i f f 打e n t 舒d d i n 哥t a s kl a yb y m ea r t i 6 c i a l d e s c r i p t i o n m e m o d锄ds m e l d st 1 1 e 鲥d d i n g r e s o u r c ed y l l 锄i ca n di s o m e r o u sc h a r a c t e rt 0m eu s e 硪t bi m p r o v et h ei 1 1 l l 甜t 锄c e a r i t l l l n e t i c 锄dd e c i s i o n p a mc h o o s e 撕t 1 1 r i l e t i ca i l dm a l 【em et 、o 撕t l l i l l e t i cu s e de a c ho m i tr e a l i z e st h ed y l l 锄i cb i n dw r h i c hd e c r e a s e st h ei n n u 饥c et 0t h es y s t e i i l a t t 锄p e rw h e i i e x e c u t i n gm et a s k na l s o r e a l i z 铬t h ea b n o 砌i t yd e a li l lm ea t t e i t l p e r - 】p r o c e s sa n d d i s t i n g u i s h e st h ed e a lb 出v e e nt l l en o wa b n o m i t ya n dt h es e r v i c ea b n o m i t y a c c o r d i n gt o t l l ee x p 嘶m e n tr e s u l t ，t l l es y s t 锄r 阻l i z e st h ed y n a m i c a t t 锄p e rf o rt h e 鲥d d i n gs e r v i r e s o u r c e i th a ss o m et l l e o 巧a i l dp r a c t i c a l i t yv a l u e s um i n g ( c o m p u t e ra p p l i e dt 色c h n o l o g y ) d i r e c t e db yp r o f z h u1 r o u c h a n k e yw o r d s ：w s r f ，s e r v i c eg r i d ，g r i d 、r k l f i o w ，g r i ds c h e d u l j n g ，s c h e d u n g a i g o r i t h ms e r v i c eo r g a n i z i n gm o d e i 华北电力大学硕士学位论文摘要 摘要 本文在对网格调度系统结构、服务网格资源描述方法、网格工作流技术和启发 式调度算法的研究基础上，提出了基于工作流的网格服务资源的调度过程模型，设 计实现了基于w s r f 的网格资源调度系统。采用语义描述方法实现了网格任务不同 层面需求之间的映射，向用户屏蔽了网格资源动态、异构的特性；对遗传算法和决 策路径选择算法进行了改进，并通过实验分析确定两种算法在系统中互补使用；实 现了服务在任务执行时的动态绑定，最大程度减少了网格资源动态性对系统调度的 影响；实现了调度过程中的异常处理，并对流程级异常和服务级异常区别处理。实 验结果表明，系统实现了网格服务资源的动态调度，具有一定的理论和实用价值。 关键词：w e b 服务资源框架，服务网格，网格工作流，网格调度，调度算法 a b s t r a c t a c c o r d i n gt 0m er e s e a r c ho n 舒d d i n ga t t 锄p e rs y s t 啪s t m c t u r e ，t h ed e s c r i p t i o no f s e r v i c e 鲥d d i n gr e s o u i e ，鲥d d i n gp u r s u i tt e c t m i c a la n de l i c i t a t i o na t t e m p e ra l g o r i t h m i c ，t h e t e x tb u i l d st l l ea t t 锄p e r - 】p r o c e s sm o d e lb a s e do nt 1 1 ep u r s u i t 鲥d d i n gs e r v i c er e s o u r c e 锄d r e a l i z e sn l e 鲥d d i n gr e s o l 】r c ea t t 伽p e r e ds y s t e i l lb yw s i 也i tr e a l i z e st h em a p p i n g 锄o n gm e d i f f 打e n t 舒d d i n 哥t a s kl a yb y m ea r t i 6 c i a l d e s c r i p t i o n m e m o d锄ds m e l d st 1 1 e 鲥d d i n g r e s o u r c ed y l l 锄i ca n di s o m e r o u sc h a r a c t e rt 0m eu s e 硪t bi m p r o v et h ei 1 1 l l 甜t 锄c e a r i t l l l n e t i c 锄dd e c i s i o n p a mc h o o s e 撕t 1 1 r i l e t i ca i l dm a l 【em et 、o 撕t l l i l l e t i cu s e de a c ho m i tr e a l i z e st h ed y l l 锄i cb i n dw r h i c hd e c r e a s e st h ei n n u 饥c et 0t h es y s t e i i l a t t 锄p e rw h e i i e x e c u t i n gt h e t a s _ k i ta l s or e a l i z e st h e a ：b n o m i t ) r d e a li i lt h e a t t e m p e r - p r o c e s sa n d d i s t i n g u i s h e st h ed e a lb 出v e e nt l l en o wa b n o m i t ya n dt h es e r v i c ea b n o m i t y a c c o r d i n gt o t l l ee x p 嘶m e n tr e s u l t ，t l l es y s t 锄r 阻l i z e st h ed y n a m i c a t t 锄p e rf o rt h e 鲥d d i n gs e r v i r e s o u r c e i th a ss o m et l l e o 巧a i l dp r a c t i c a l i t yv a l u e s um i n g ( c o m p u t e r a p p l i e dt 色c h n o l o g y ) d i r e c t e db yp r o f z h u1 r o u c h a n k e yw o r d s ：w s r f ，s e r v i c eg r i d ，g r i d 、r k l f i o w ，g r i ds c h e d u l j n g ，s c h e d u n g a l g o r i t h ms e r v i c eo r g a n i z i n gm o d e l 声明户明 本人郑重声明：此处所提交的硕士学位论文基于w s i 强的网格资源调度系统 的研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作 和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：笾：皇鱼 日期：圣里皇! ：鱼：1 3 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：矗掐 华北电力大学硕士学位论文 1 1 课题的背景及意义 第一章引言 随着电子商务、b 2 b ( b u s i n e s st 0b u s i n e s s ) 等应用的发展和需求的加深，企业应 用系统要求能够依据新的需求，快速、灵活地集成各种已有的和新增的业务应用系 统，并使得它们可以有机地协同提供服务【l 】。像i b m 公司的o nd e m a i l d 策略、h p 公司的效用计算( u t i l i t yc o m p u t i n g ) 以及s u n 公司的s u ng r i d 技术等正是对这种商 业需求的工业解决方案。而用于实现在分布、异构、自治的网络资源环境上动态构 建虚拟组织与跨自治域的资源共享和协同工作的网格计算【2 】技术正是这些解决方案 的技术引擎。i n t e m e t 实现了计算机系统与网络设施的互联，w e b 实现了网页的互通， 使得信息的共享与获取不受时空限制，而网格则试图实现在全球i n t e m e t 范围内按 需共享和整合各种i t 资源，除了通常的信息与设备资源共享外，计算资源、数据资 源和服务资源的有效聚合与广泛共享是网格区分于以往共享技术的本质特征。 企业不仅要面对多种多样的硬件平台、操作系统、编程语言、软件技术和数据 管理系统等技术因素，还要面对不断变化的企业运作环境。为了提供能够进行交互 以及可扩展的基础设施环境，对于网格技术而言，采用开放性的标准是十分重要的。 服务概念的提出使得服务提供者可以将自己的资源以服务的形式提供给用户，用户 可以在分布的环境下根据自己需求选择想要使用的服务；同时，通过将不同层次的 应用和资源抽象成统一形式并提供标准的访问方法，可以简化复杂软件的应用方 式，为分布环境下资源共享与协同工作提供了良好的支持。为此，需要提供一种一 体化的描述、管理、共享服务机制，由a r i b a 、i b m 和m i c r o s o r 提出的w 曲服务( w 曲 s e r v i c e s ) 作为日益广泛使用的国际标准使得人们可以以统一的方式来描述共享资 源，实现应用互操作，它可以满足企业间的应用集成需求，使得分散于因特网的 w 曲服务可以互相调用来协同完成商务活动。将w e b 服务技术引入网格研究领域， 有助于解决网格研究所面临的应用集成、资源共享、系统互操作和标准化等问题。 然而，、e b 服务一般面对的都是永久性服务，在万维网这种比较松散联合的环境中， 、e b 服务无疑是可行的；而企业间的协同作业存在大量临时性短暂服务，要求资源 之间的联系更加紧密，必须利用网格技术对服务交互过程中的状态资源进行建模。 w s r f ( w e bs e r v i c e sr e s o u r c ef r a m e w o r k ，w e b 服务资源框架) 例的出现，标志着网 格计算和企业计算在目标、理念和实现等方面走向融合，这种融合是实现按需计算 模型的发展趋势，形成了面向服务的新一代网格，即服务网格( s e r v i c e 鲥d ) 【4 1 。 因此，研究基于w s i 强的网格资源调度系统具有非常重要的意义。 华北电力大学硕士学位论文 1 2 课题国内外研究现状 网格研究始于美国，各个国家和地区目前都投入了大量的资金进行网格技术研 究和网格基础设施建设。目前网格调度研究中的大部分工作都集中在理论研究、标 准讨论以及建立定制的解决方案上，有关标准组织主要有g g f ( g 1 0 b a lg r i d f o r u m 全球网格论坛) 、o a s i s 、w 3 c 、i e t f 。在实践中，主要有两个方面：一 方面是旨在提供网格基础设施的网格中间件( 以下称为网格系统) ，典型的有 g l o b u s 【5 】，l e g i o n 【6 】，c o n d o 卜g i7 1 ，u n i c o r e 【8 1 等；另一方面是利用网格技术开发的 应用( 以下称为网格项目) ，如美国能源部的d o es c i e n c eg r i d 、欧盟的e u r o g r i d 计划、中国教育科研网格c h i n a g d 等。 1 2 1 网格调度系统的国内外研究现状 美国作为网格研究的发源地，是目前网格研究走在世界最前列的国家，用于网 格技术基础研究经费已超过5 亿美元。 美国的网格研究最初是从科研机构开始的，有多家研究机构开展了与网格相关 的研究工作，开发了c o n d o r ，l e 酉o n ，g l o b u s 等比较有影响的软件和工具，开展了 应用层调度( a p p l e s ) 、d o c t 、p u n c h 、e n t r o p i ap c 等几个著名的网格项目。近年， 美国多家大公司纷纷宣布各自网格战略计划。i b m 和g l o b u s 提出开放网格服务体 系结构已赢得大家认可，对未来网格研究将产生重大影响。微软正在开发一个名为 “b i 或o p ”的网格计划【9 】，以使开发人员能够相对快捷的创建一套松耦合分布式操作系 统组件。微软在该项目中没有把少数几台高性能系统紧密连接在一起，而是通过松 散连接大量性能适中的计算机系统来达到同样效果。o r a c l e 将网格技术融入其最新 版本的数据库中，并将其数据库命名为o r a c l e1 0 g ，其中g 表示支持网格的意思。 美国军方目前正在实施“全球信息网格”计划，预计2 0 2 0 年完成。作为该计划的一部 分，美国海军陆战部队启动了一个耗资1 6 0 亿美元、历时8 年的项目，包括系统的 研制、建设、维护和升级等方面。 欧洲也是网格研究和建设非常活跃的地区，已经启动了多个网格研究项目，其 中最著名的“欧洲网格”和“欧洲数据网格”是由多个国家联合参与的研究项目。 欧洲网格的基本目标是建立一个给用户提供安全、简单、透明访问欧洲范围内 信息资源的平台，为欧洲科学研究服务。欧洲数据网格( e u r o p e a nd a t ag r i d ) 是欧盟 支持的一个项目，目标是建设提供计算强度大、共享超过1 0 1 4 b 数据的大规模分布 式数据库的下一代计算基础设施。除此之外，欧洲比较有名的网格项目还有德国的 u n i c o r e 、英国国家网格、荷兰网格、爱尔兰网格、欧洲网格计算数据库、俄罗斯 科学网格、n o r d u 网格等，投资力度以英国政府最大，已投资超过l 亿英镑用于建 2 华北电力大学硕士学位论文 设英国国家网格。 日本是在亚洲开展网格研究比较早的国家之一，n i n f 是日本正在实施的全球计 算基础设施项目。它允许用户访问包括硬件、软件和数据在内，分布在广域网上的 资源。b r i c h s 是日本另一个研究项目，它是一个性能评价系统，允许在典型的高性 能全球计算环境上分析和评价不同调度策略。它能够模拟不同全球计算系统的不同 行为，尤其是网络行为和资源调度算法行为。此外，韩国、泰国、印度的国家也积 极开展了多项网格研究工作。 近年来，我国在网格研究上也得到了迅速发展。国家在九五期间就资助了“8 6 3 ” 重点项目“国家高性能计算环境”【l0 1 。该项目由中科院计算所联合了十几家科研单位 共同参与，其目标是建立一个分布式环境下支持异构平台的计算网格示范系统，把 我国8 个高性能计算中心通过i n t e m e t 连接起来，进行统一的资源管理、信息管理 和用户管理，并在此基础上开发了多个计算型的网格应用系统，取得了一系列研究 成果。十五期间，国家又设立了“8 6 3 ”重大专项“高性能计算及其核心软件”，国家、 地方政府、应用部门和产业界已向其注入了专项经费数亿元。 目前，正在进行的比较大的网格项目有四个【： 中国国家网格专项由国家8 6 3 高技术研究发展计划资助，主要任务包括：建设 中国国家网格实验床( c n g r i d ) ；采用自行研制的、面向网格的高性能计算机建立具 有4 万亿次以上计算能力的网格主节点；开发支持网格应用以及维护网格系统运行 的网格软件；开发具有代表性的网格生产性应用。 中国教育科研网格c h i n a g r i d 计划是教育部“十五”2 1 l 工程公共服务体系建设的 重大专项，受国家高技术研究发展计划( 8 6 3 计划) 项目支持。该项目由1 2 所大学联 合推出，其目标是将广泛分布在中国教育科研网c e r n e t 和各大高校中异构的、海 量的资源集成起来，实现c e r n e t 环境下资源的有效共享，消除资源孤岛，提供有 效服务，形成为国家科研教学服务的大平台。 e s c i e n c e 网格研究计划是国家基金委员会投资1 5 0 0 万的大型网格项目。该项 目建设以网络为基础的科学活动环境，目标是利用网络技术将地理上位置不同的计 算设施、存储设备、仪器仪表等集成在一起，建立面向网络服务的通用基础支撑环 境，实现i n t e m c t 上计算资源、数据资源和服务资源的有效聚合和广泛共享，从而 建立一个能够实现区域或全球合作或协作的虚拟科研和实验环境，支持以大规模计 算和数据处理为特征的科学活动。 中国空间信息网格是国家投资2 0 0 0 万建立的又一大型网格项目。空间信息网 格( s p a t i a l i n f o n n a t i o ng r i d ，s i g ) 是汇集和共享地理上分布的海量空间信息资源，对 其进行一体化组织与处理，从而具有按需服务能力的、强大的空间数据管理和信息 3 华北电力大学硕士学位论文 处理能力的空间信息基础设施。连接空间数据资源、计算资源、存储资源、处理工 具和软件以及用户，能够协同组合各种空间信息资源，完成空间信息的应用与服务。 用户可以提出多种数据和处理的请求，系统能够联合地理上分布的各种资源，协同 完成多个用户的请求。 1 2 2 网格调度技术的国内外研究现状 目前网格调度技术方面的研究主要包括以下几个方面，一是有关网格调度体系 结构；二是网格调度模型的研究。其中网格调度体系结构定义了多个跨域资源调度 实例相互交互的框架，确定“网格调度系统”的功能需求；而网格调度模型从网格资 源组织模型出发，分析网格应用模型，从而确定相应的调度策略。 ( 1 ) 网格调度体系结构。 n a b r z y s k i j 等指出，网格环境下的调度系统必须采用分层的结构形式，需要多 个调度实例相互协调，一个完整的调度执行过程应包括三个阶段【1 2 】：资源发现阶 段、系统选择阶段、作业执行阶段。g g f 6 ( g l o b a lg d df o m m ) 提出了服务网 格调度体系结构的草案，阐述了基于开放网格服务体系结构o g s a ( o p e ng r i d s e r v i c ea r c h i t e c t l l r e ) 的调度服务和其他核心网格服务( 如数据管理服务、记账付费 服务、信息服务等) 之间的交互以及调度过程的描述，提出完整网格调度系统应包 括四个功能模块：资源选择、调度队列的产生、i o 传输和副本的数据管理和监测【l3 1 。 目前网格调度体系机构研究仅从功能需求、执行过程方面进行描述，还没有对调度 过程中的接口和交互协议进行定义。 ( 2 ) 网格资源组织模型。 目前网格计算中所用的资源组织模型主要有如下几种：分层模型( h i e r a r c h i c a l m o d e l ) 【1 4 】：采用分层模型的网格项目有g l o b u s 、l e g i o n 、a p p l e s 等；计算市场 ( 经济) 模型( c o m p u t a t i o n a lm a r k e t e c o n o m ym o d e l ) 【6 】：网格计算市场提供了合适 的工具和服务允许资源请求者和资源提供者表达他们的需求，它可以和分层模式结 合使用来实现更有效的资源管理；资源池模型f 7 】：在这种模型中，一台中心服务 器记录计算环境中所有资源信息，资源池中对资源的描述是无序的，只支持工作级 调度，不支持任务级并行和任务间的通信。网格资源空间的e v p 模型【”】：在织 女星网格中提出的e v p 模型包括三个层次：有效资源层( e ) 、虚拟资源层( v ) 和 物理资源层( p ) ：o g s a 资源服务模型【1 3 l ：一切资源都以服务的形式存在，服务 分布在不同环境中，可以通过通用资源标识( u r i ) 访问。 与资源组织模型相对应，网格中的调度系统一般使用分布式调度策略，主要有 如下几种调度模型：基于“超级调度者”的方法、基于市场的方法、基于发现的方法、 4 华北电力大学硕士学位论文 以及由这几种方法组合的混合技术。在基于“超级调度者”的方法中，网格环境下存 在分层的多个调度器，它们互相协作执行资源管理，该方法难以解决协作配置问题。 基于市场方法的资源管理使用源于人类经济的原则执行。使用较多的场景是拍卖和 多商品市场。资源发现模型在一个分布式的数据库中维持资源属性和状态信息，需 进一步研究具有容错和可扩的高度分布式的发现技术。混合技术使用一个双层机 制，结合多重技术实现可扩和容错方法，需进一步研究不同方案的组合。 ( 3 ) 网格应用模型与性能预测模型。 将网格应用分解为多个子任务，每个子任务有各自的资源需求，然后提交到网 格调度系统执行调度，是目前网格调度系统采用的通用方法。网格应用模型对于网 格调度和任务分配产生重要的影响，不同类型应用的约束条件不一样，尤其是网格 环境中由于没有完全集中的控制，在资源分配和调度上对不同应用模型的任务处理 方式是不一样的。主要有两种不同类型任务：相互独立的任务( m e t a t a s k s ) ；相互 间存在依赖和时序关系、因果关系的任务。 调度中预期任务运行时间是一个关键部分，可以通过两种方法计算：短期预 测模型：在调度的第一轮，调度器进行初步猜测所有任务的执行时间。当任务完成 后，调度器使用观测的执行时间提高预测算法的准确性。如n w s 【1 6 】。长期预测 模型：用来在非专用计算环境预测任务执行时间。如g r i dh a r v e s ts e n ，i c e ( g h s ) 预测模型。 ( 4 ) 调度算法。 j 。 目前在网格调度算法研究中，引入并行处理方面的研究成果，其目标主要是增 加吞吐率，增加系统的使用率，实现经济系统和用户的约束条件，实现在整个系统 中网格应用任务的完成时间最小，即使m a k e s p a n 最小，找到一个这样的m a k e s p 姐 是n p 完全问题。 网格调度可以根据任务间是否存在通信关系分为对相互间存在通信任务的任 务组的调度以及对相互独立的任务组( m e t a t a s k s ) 的调度。在算法的实现中都假定 资源的信息是可以获取的，并利用不同的预测模型对资源的动态信息进行预测。 对于m e t a t a s k s ，由于这些任务之间没有依赖关系，因此在调度过程中，任务 执行次序不会产生逻辑上错误，系统在考虑调度的时候，可以根据m a k e s p a n 的要 求任意考虑执行过程。根据任务调度的时问频度，启发式调度可以分成两类：联机 在线模式和批处理模式。联机在线模式是当任务到达调度器后尽量使他尽快匹配一 个任务，通常采用先来先服务的策略，不考虑整个任务集合的特点和要求，只是考 虑目前到达的任务。批处理模式当任务到达之后并不立即分配，而是收集一个集合， 根据一定的时间周期或系统事件触发，然后对于这个任务集合，再按照预先调度方 华北电力大学硕士学位论文 法进行处理。这两种方法各有优缺点，联机在线模式的优点是反应快，任务延迟时 间短，但是可能导致资源分配不够优化，如要求低的任务占用处理能力强的节点， 而要求高的任务分配到处理弱的节点或者处于等待状态。而批处理方式则能够考虑 更多的请求和资源状况，能得到更有效的网格资源利用率，但对于单个任务来说， 延迟时间可能较长。 对于关联任务的调度算法，通常根据任务的时序或者因果关系建立一个调度列 表，然后重复以下步骤直到所有任务被调度完成【1 7 】。 从调度列表中移出第一个任务； 将该任务分配到允许最早开始时间的机器。 称为表调度法，具体如下：通过有向无环的相关任务图d a g = r 巧习来描述并发 执行的任务，其中矿是任务的集合，i 明= y ；e 是边的集合，它反映了任务之间的相 关关系，i e l = e 。以f ，刀，儿如果伽f ，z 印，则说明疗，必须在，l f 执行结束之后才能开 始执行，用m 来表示任务节点刀f 的运算量，用c f ，来表示胁与万，之间的通信量( 如 果刀f 和，z ，之间不存在边，那么c f ，= 。其目标是要将d a g 的各任务结点调度到多 个处理结点上并使得任务图的调度长度最短，所谓调度长度是指任务图中的各任务 被调度完毕后静态模拟执行的时间。表调度的主要思想是重复执行下面两个步骤直 到所有任务都已被调度到合适的处理结点上为止。目前已提出了很多表调度算法， 这些算法的主要区别在于任务结点的权值如何设定以及相应处理结点的选择，如文 献 1 7 】中提到的两个算法m c p 算法和e t f 算法。 目前用于网格环境的主要调度策略有：a p p l e s 【1 8 】的调度算法集中高效的数据协 同定位，具有一定的适应性，另外采纳了预测模型；n i m r o d g 【1 9 】中的调度侧重与时 间期限和经济模型；c o n d o r - g 7 】处理高吞吐率计算来处理可控的局部网络环境，其 匹配调度器( m a t c l m l a k e r s c h e d u l e r ) 的目的是处理单个任务并且是无关调度；基于 知识的元调度器( k bm e t a s c h e d u l e r ) 【2 0 】利用基于人工智能的多约束条件搜索技术 来实现调度决策，该调度器是建立在g l o b u st o o l k i t 的基础上，利用了g l o b u s 的一 些高级基础服务如资源预留和信息服务；p b s 、l s f 与s i l v e r m a u i 【2 1 】主要用于集群 系统，要求对资源具有完全的控制。如果以g r a m 作为底层协议，也可以将p b s 、 l s f 部署在网格层次上；s i l v e r 利用m a u i 实现了作业在多个集群间进行调度。 所有网格调度系统工作在这样的基础上，要执行的新任务必须要使资源选择器 知道，在当前的系统中，资源选择器扮演网格系统的网关，它将从全局目录中( 例 如g l o b u sm e t a d i r e c t o r ys e i c e ) 选择资源然后分配工作给可用的网格节点。典型地， 任务分配在两个场景，第一是任务被分配给网格中的一个特殊节点，第二是任务被 调度到一个处理器。实际上第一个是资源分配，而第二个是任务调度。 6 华北电力大学硕士学位论文 1 3 本文的主要工作 本文研究网格环境中的资源调度机制，在遵循o g s a 的核心规范w s r f 的前提 下，对服务描述、资源组织模型进行语义支持研究，为实现服务动态调度提供支持， 研究服务调度过程的建模和调度算法问题，开发一个能够实现网格服务动态调度的 系统。 本文主要工作如下： ( 1 ) 研究课题背景及意义，在分析了网格资源调度国内外研究动态的基础上， 研究并设计基于w s r f 的网格资源调度系统的执行过程、组成结构和功能。 ( 2 ) 研究w 曲服务资源描述规范w s d l 及其x m l 语言描述方式。 ( 3 ) 研究网格调度工作流模型，对服务资源的组合优化、选择、动态绑定、 语义支持、可靠性保障、异常处理、q o s 约束进行深入分析。 ( 4 ) 研究和改进遗传算法、动态决策路径选择算法，并对两种算法进行对比， 分析两种算法的优缺点，根据用户q o s 的不同互补使用两种调度算法。 ( 5 ) 实现动态服务绑定，即子任务运行时绑定服务，回避网格资源动态变化、 自治性强的特点。 ( 6 ) 实现调度过程执行时的监控和异常处理。 7 华北电力大学硕士学位论文 2 1 网格概述 第二章网格相关技术研究 2 1 1 网格的发展阶段 第一阶段：网格萌芽期第二阶段：网格的早期实验!第三阶段：网格发展期 以千兆网试验床与元计算 代表性项目： f a f n e r 、l w a y 开创性和奠基性工作： 支持大规模数据计算 与应用的中间件开放 代表性项目： g l o b u s 、l e g i o n 标志性工作： o g s a 标准的制定 w s r f 规范的出台 一1 9 9 5 年1 9 9 5 2 0 0 0 年2 0 0 肛年 图2 1 网格发展的三个阶段 网格是在2 0 世纪9 0 年代中期为构建先进科学和工程分布式计算而引入的概 念。它的发展经历了三个阶段，如图2 1 所示。 连接超级计算中心为一定范围内的高性能应用提供计算资源，这是网格发展的 第一个阶段，f a f n e t 和i w a y 是这一时期的两个代表性项目。 随着技术的进步和应用的普及，网格被看作全球范围内为各种大规模计算和数 据密集型应用提供分布计算环境的基础设施，网格发展从此进入第二个阶段。这一 时期代表性项目有g l o b u s 和l e 西o n 等，关注的主要问题包括：网格环境下的分 布性、异构性、可扩展性和动态性；基于i n t e m e t 在多种异构计算机系统和资源 之间建立通用、分布式计算环境，让不同节点和资源可以有效地共享与协同工作。 当时以计算网格( c o m p u t i n g 鲈i d ) 来称谓网格技术，1 9 9 8 年i a nf o s t e r 给出的定义 为：计算网格是一个硬件和软件基础设施，它提供对高端计算能力可靠、一致、普 遍和不昂贵的接入。这一时期的网格技术主要关注网格中间件的研究与开发。 2 0 0 2 年以开放网格服务体系结构( o p e ng r i ds e r v i c e s 肖j c h i t e c t l l r e ，o g s a ) 为 标志，网格发展进入第三阶段，网格演化成为一种受管理的共享虚拟系统。这一时 期，网格从“计算网格”演变为“网格计算”，称谓的改变反映了人们对网格技术的内 涵理解的深化。i a nf o s t e r 在“网格剖析”一文中指出：网格计算关注的是在动态、多 机构的虚拟组织( v i n l l a lo r g a n i z a t i o n ，v o ) 中协调资源共享和协同解决问题，其 关键是在一组参与节点( 资源提供者和消费者) 中协商资源共享与管理，并利用协 8 华北电力大学硕士学位论文 商得到的资源池共同解决问题。 2 1 2 服务网格 早期不同的网格中间件系统，由于其核心协议具有独立性，因此存在互操作性 问题。而将w e b 服务技术引入网格研究领域，有助于解决网格研究所面临的应用集 成、资源共享、系统互操作和标准化等问题。通过对网格系统的本质功能进行定义、 描述和分解，采用面向服务的体系结构，g g f 于2 0 0 2 年提出了一个全新的网格标 准开放网格服务体系结构o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 。它把g l o b u s 与w e bs e r v i c e s 技术相结合，统一以网格服务的方式对外界提供服务。确立了w e b 服务作为网格资源新的抽象形式和构造基础，即服务网格，目前o g s a 已成为网格 事实上的标准。o g s a 网格体系结构模型如图2 2 所示【2 2 1 ，该模型的每一层都清晰 地定义了相应的功能，其核心层是o g s i 和o g s a 服务层，o g s i 后来发展成为w e b 服务资源框架( w s r f ) ，这些都标志着侧重科学活动的网格计算开始转向面向服 务的信息网格( i n f o 肌a t i o ng r i d ) 。 图2 2o g s a 网格体系结构模型 o g s i w s r f 主要用于解决现有的w e b 服务标准所不能解决的有关基本服务语 义问题，例如服务是怎样创建的，存活多久，怎样管理长期状态等。o g s i w s r f 为网格系统提供包括描述和发现服务属性、创建服务实例、管理服务生命周期、管 理服务组以及发布和订阅服务通知等标准接口及其相关行为，支持创建、管理网格 服务以及网格服务间的信息交换。o g s a 服务层基于o g s i w s r f 创建了一套标准 服务，包括策略服务、注册服务、服务级别管理以及其它网格服务，从而在构建网 格系统时可以实现代码重用和组件互操作。网格用户可以使用这些底层的平台核心 9 华北电力大学硕士学位论文 组件构建用于共享资源与协同工作的网格应用。 g t 3 【2 3 】是基于o g s a 的核心规范o g s i 实现的，它标志着网格技术开始从学术 研究领域逐步向i n t e m e t 和企业服务基础设施领域渗透。目前网格中间件g t 4 【2 3 】是 基于w s r f 的实现，w s r f 是o g s i 的重构和发展，目的是利用新的w e b 服务标准。 o g s i 和w s r f 的本质目的并没有差别，w s r f 是在结合新的w e b 服务标准基础上 对o g s i 的重新整合，这种整合使得w s r f 与现有w e b 服务标准相兼容，从而利用 现有服务开发工具构建网格计算设施。 综上所述，服务网格是网格计算和分布式计算相互融合形成的新一代网格。面 向服务的体系结构使得网格系统中所有组件实现虚拟化，将多逻辑资源映射为相同 的物理资源，在进行复杂的服务组合时不必考虑具体服务的实现。以底层资源聚合 与配置为基础，在虚拟组织中有效利用各种资源进行协作。 2 1 3 语义网格与知识网格 在英国的e s c i e n c e 计划研究中，人们发现，网格的现有努力和e s c i e n c e 设想 之间存在差距，于是在2 0 0 1 年提出了语义网格的构想，并且于2 0 0 2 年在全球网格 论坛g g f 成立了语义网格研究组s e m g r d 。语义网格构想的关键是把所有资源， 包括服务，都用一种机器可处理的方式来描述，目标是实现语义的互操作性。达到 该目标的一种实现方法是把语义w e b 技术应用到网格计算开发中，下至基础设施上 至网格应用。值得注意的是“语义”是从下到上弥漫在整个网格中而不是仅仅在其上 增加了一个语义( 知识) 层。中国科学院计算技术研究所知识网格研究组通过采用 新的计算模式、资源组织和管理模型，有效地辅助用户进行资源获取、共享、管理、 协同工作和决策等，为人们提供更深层、更全面、更智能的服务。重点解决三个科 学问题：资源的规范组织、语义互联和智能聚合。 对嵌入在开放网格体系结构( o g s a ) 中的灵活、动态的中间件来说，知识是 至关重要的，形成虚拟组织的目的是为了解决问题，问题的解决最终演变为知识的 运用与产生。服务的动态发现、虚拟组织的动态创建都要求网格中间件能够运用、 处理一些知识，这些知识包括服务的可用性，服务的功能以及服务连接、配置和替 代方式，还有如何被发现、调用和演化等都存在于协议和服务描述之中( 如o g s a 的服务资源属性) 。英国学者j e f f e r y 等将网格计算环境的资源共享拓展到信息和知 识层次，提出了信息网格和知识网格( k n o w l e d g e 鲥d ) 的概念。它们都以计算网格 和数据网格( d a t a 斫d ) 为基础。计算网格和数据网格致力于对计算资源、数据资 源的存储、访问和管理等，知识网格则是对数据的分析、挖掘、推理和知识发现， 是前者之上的问题解决环境。语义网格( s e m a n t i c 鲥d ) 提供对计算网格与数据网格、 信息网格以及知识网格三个层次的支持。计算网格和数据网格的语义是隐含的，而 l o 华北电力大学硕士学位论文 语义网格的信息和服务具有明确的形式化语义定义，能够有效地促进人与计算机之 间的交流和协作。 网格系统中的语义和知识分为两类。一类用于动态发现、管理虚拟组织的资源， 包括对服务语义、资源分类、事件通知主题和起源跟踪等的描述与处理，从语义层 次上解决分布式环境的异构问题。另一类是支撑知识密集型的网格应用，主要用于 协同问题解决环境中领域知识挖掘。本文着重考虑从语义层次上解决服务调度过程 中的异构问题。 图2 3 是面向服务的知识网格体系结构示意图，它说明了基础服务、语义信息 服务和知识服务的关系【2 2 1 。其中基础服务包括数据和计算服务，例如网络访问和数 据管理等。基础服务使用网格实体元数据，这些元数据的语义是隐含的，机器不能 理解和处理。语义信息服务显式地声明网格服务的目的和目标，可以被机器理解与 处理。知识服务一般包括本体服务、注释服务和推理服务等，这些服务支持智能化 和个性化的网格应用。 l 协作工具ii 问题解决ll 应用门户l l一 仝 。l 1 ， 知识服务 1 ， ， 语义信息服务 1 ，lll 、 r 基础服务：数据服务，计算服务 图2 3 面向服务的知识网格体系结构 语义网格代表性的研究项目如m y g r i d 、g e o d i s e ( g r i de n a b l e do p t i m i z a t i o n a n dd e s i g n s e a r c hf o re n g i n e e r i n g ) 、s c e c ( s o u t h e mc a l i f o m i ae a n h q u a k ec e n t e r ) 、 g e o n ( g e o s c i e n c e sn e t w o r k )、c o a k t i n g ( c o l l a b o r a t i v ea d v a n c e dk n o w l e d g e t e c h n o l o g i e si nt h eg r i d ) 等。 目前语义网格主要是利用语义w e b 服务技术，针对某一应用领域( 如m y g r i d 面向生物实验) 引入本体，对网格资源进行语义描述和匹配，从而达到“语义”级别 上的共享与协作。但由于语义网格项目的发布早于w s r f 规范，大多数语义网格中 间件并不符合w s r f 规范；另一方面语义网格中缺乏对实时动态变化的q o s 进行语 义描述和匹配，没有一个可扩展的动态服务调度模型。本文对基于w s r f 的网格服 l l 华北电力大学硕士学位论文 务资源进行了语义扩展，为实现服务的动态调度提供前提。 2 1 4 网格资源的特点 传统的“资源”术语定义为某种物理实体，例如计算机、网络或存储系统。我们 使用其通用含义