（计算机应用技术专业论文）基于qos的网格任务调度模型与算法研究(1).pdf

东北大学硕士学位论文摘要 基于q o s 的网格任务调度模型与算法研究 摘要 高速网络的发展使得将分散的、异构的计算资源有机地整合到一起形成计算网 格成为可能。计算网格为解决科学和工程领域一些大规模计算问题提供了理想的平 台。由于网格所具有的广域性、动态性、异构性的特点，如何对任务进行调度以满 足用户的需求是一个极具挑战性的问题。 随着网格的飞速发展，服务质量( q o s ) 成为网格任务调度过程中必须要考虑 的一个重要因素。有些任务需要在能够提供一定q o s 的计算资源上运行，而有些任 务对计算资源没有q o s 方面的要求。在这种情况下，一些传统的任务调度算法不能 很好满足用户的需求。为解决网格任务调度领域的不足，本文主要进行基于多维q o s 的网格任务调度算法和基于随机高级p e t r i 网的网格调度模型两个方面的研究。 网格任务调度的目标是取得高的系统吞吐量和将应用映射到可用的计算资源。 在非专有的共享异构网格环境中，资源映射需考虑服务质量。因此，本文在传统调 度算法的基础上进行了一些扩展，引进多维q o s ，提出了基于多维q o s 的网格调度 启发式算法，通过g r i d s i m 平台进行模拟实验，模拟实验结果表明，扩展后的算法 比原算法性能更高、稳定性更好。 同时本文将p e t r i 网理论引入网格调度领域，提出了一种基于随机高级p e t r i 网 的网格调度模型，能够较好地对基于q o s 的网格调度策略进行性能分析。同时利用 p e t r i 网性能分析技术对模型进行了精化设计以简化模型求解的复杂性；通过s p n p 软件包对提出的网格调度模型进行性能分析，验证p e t r i 网模型能够有效地对采用不 同网格调度策略的网格系统进行建模。 总之，本文在研究和分析现有网格任务调度算法与模型相关研究工作的基础 上，提出了自己的一些想法，给出一定分析并进行了模拟实验，实验表明本文的方 法在某些方面具有优越性。本课题提出的p e t r i 网模型是一个在网格任务调度领域的 有益尝试，使我们对将来的研究方向更为明确。 关键词：任务调度，服务质量，随机高级p e t r i 网，性能分析 i i 东北大学硕士学位论文a b s t r a c t t h er e s e a r c ho nq o sb a s e dg r i dt a s ks c h e d u l i n g m o d e l sa n d a l g o r i t h m s a b s t r a c t i nr e c e n ty e a r s ，t h eh i g hs p e e dn e t w o r k sd e v e l o pv e r yf a s t ，w h i c hm a k e si tp o s s i b l e t oi n t e g r a t et h ed 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 oc o m p u t a t i o n a l g r i d i tp r o v i d e sa ni d e a lp l a t f o r mt os o l v el a r g e s c a l ec o m p u t i n gp r o b l e m si ns c i e n t i f i c a n de n g i n e e r i n ga r e a b e c a u s et h er e s o u r c e si ng r i da r ed i s t r i b u t e d ，h e t e r o g e n e o u sa n d d y n a m i c ，h o wt os c h e d u l et a s k si ng r i dt om e e tu s e r s r e q u i r e m e n t si s ac h a l l e n g i n g p r o b l e m w i t ht h ep r o l i f e r a t i o no ft h eg r i d ，q u a l i t yo fs e r v i c e ( q o s ) h a sb e c o m ea n i m p o r t a n tf a c t o rt h a tn e e d e dt ob ec o n s i d e r e di nt h ep r o c e d u r eo fs c h e d u l i n g t h eg o a lo f g r i dt a s ks c h e d u l i n gi st oa c h i e v eh i g hs y s t e mt h r o u g h p u ta n dt om a t c ht h ea p p l i c a t i o n w i t ht h ea v a i l a b l ec o m p u t i n gr e s o u r c e s t h i sm a t c h i n go fr e s o u r c e si nan o n - d e d i c a t e d s h a r e dh e t e r o g e n e o u se n v i r o n m e n tl e a d st oc o n c e r n so nq u a l i t yo fs e r v i c e ( q o s ) u n d e rt h i ss i t u a t i o n ，i no r d e rt oo v e r c o m et h i ss h o r t c o m i n g ，m u l t i ! c ) l ed i m e n s i o nq o s b a s e dm i n - m i nh e u r i s t i ci sp r o p o s e di nt h i sp a p e r as i m u l a t i o ne x p o r i m e n tb a s e do n g r i d s i mp l a t f o r mi sm a d e a n dt h ec o m p a r i s o nb e t w e e nt h eo r i g i n a la l g o r i t h ma n dt h e m u l t i p l ed i m e n s i o nq o sb a s e da l g o r i t h m s h o w st h a tt h el a t t e ra c h i e v e sb e t t e r p e r f o r m a n c e as t o c h a s t i ch i g h l e v e lp e t r in e tm o d e li sg i v e nt or e a l i z et h eq u a l i t yo fs e r v i c e ( q o s ) b a s e ds c h e d u l i n go fg r i dr e c o u r s e s b a s e do nt h ep e r f o r m a n c em o d e l i n ga n d a n a l y s i st e c h n i q u eo fs t o c h a s t i ch i g h l e v e lp e t r in e t s ( s h l p n ) ，t h i sp a p e rp r o p o s ea s h l p nm o d e lf o rs c h e d u l i n go fg r i dr e s o u r c e s ；t h es h l p nm o d e li sf u r t h e rr e f i n e dt o r e d u c et h ec o m p l e x i t yo ft h em o d e l ；t h ep e r f o r m a n c eo fg r i dr e s o u r c e ss c h e d u l i n gp o l i c y i sa n a l y z e da n de v a l u a t e du s i n gt h ep e r f o r m a n c ea n a l y s i st e c h n i q u eo ft h es h l p n i nc o n c l u s i o n ，a f t e ri n v e s t i g a t i n go nt h et a s ks c h e d u l i n gm o d e la n da l g o r i t h m s r e s e a r c hi ng r i d ，t h i sp a p e rp r o p o s eas h l p nb a s e dm o d e lf o rg r i dt a s k ss c h e d u l i n ga n d m u l t i p l ed i m e n s i o nq o sb a s e da l g o r i t h m w ee v a l u a t ea n da n a l y z ea d v a n t a g eo ft h e n o v e lm o d e la n da l g o r i t h m ，s i m u l a t i o ne x p e r i m e n t sa l s od o n eo i lt h e ms h o wt h a to u r m o d e ia n da l g o r i t h ma c h i e v e sb e a e rp e r f o r m a n c et h a nt h eo t h e r sr e l a t e d k e yw o r d s ：t a s ks c h e d u l i n g ，q o s ，s t o c h a s t i ch i g h l e v e lp e t r in e t ，p e r f o r m a n c ea n a l y s i s i i i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果 除加以标注和致谢的地方外，不包含其他人已发表或撰写过的研究成果，也不包括 本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 本人签名： 鹚穆 日期：寥卯6 年i 目，日 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据 库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名 签字日期 导师签名 签字日期 东北大学硕士学位论文 第一章引言 第一章引言 网格自从9 0 年代中期被提出以来，得到了迅速的发展，被称为是“因特网的第 三次革命”。网格最重要的特点就是资源的全面共享并利用这些共享的资源来协同解 决问题。网格最初是由大规模的并行计算发展过来的，因此最初被称为计算网格眦】， 计算网格在科学和工程计算及应用方面取得了巨大的成就。 任务调度是网格资源管理中的重要组成部分。本章首先介绍了网格、网格计算 的概念以及网格任务调度的产生，然后综述了网格任务调度及网格q o s 的研究现 状，并在此基础上论述本文研究工作的主要内容及意义。 1 1 研究背景 1 1 i 网格与网格计算 网格是继传统因特网( i n t e r n e t ) 、万维网( w w w ) 之后的新一代因特网环境的 集成及应用。传统因特网实现了计算机硬件的连通，w e b 实现了网页的连通，而网 格则试图实现因特网上所有资源的全面连通，形成对用户相对透明的虚拟的高性能 计算环境，最终实现网络虚拟环境上的资源共享和协同工作，消除信息孤岛和资源 孤岛。因此，网格是信息社会的网络基础设施，是把整个因特网整合成一台无形的 超级虚拟计算机，实现因特网上所有资源的互联、互通，完成各类资源智能共享的 一种新型的分布式计算技术。 在2 0 0 1 年，i a nf o s t e r 和s t e v et u e c k e 给出一个更进一步确切的关于网格的定 义【l j ，“网格计算关心的是在动态的、多机构的虚拟组织中协调资源共享和协同解决 问题”。其核心概念是：网格是一个集成的计算与资源环境，也就是说网格是一个计 算资源池。除了必要的各种类型的计算机、网络通信平台之外，也涵盖了计算资源、 存储资源、通信资源、软件资源、信息资源、知识资源等，甚至还包括与人文相关 的专家资源的集合。因此网格计算( g r i dc o m p u t i n g ) 就是基于网格对问题求解的 过程。网格资源主要是指分布的计算机资源，而网格计算是指将分布的计算机组织 起来协同解决复杂的科学与工程计算问题。 网格计算技术的巨大应用前景促使国内外很多的研究机构和企业投入了相当 大的人力、物力和财力进行网格计算技术的研究。当前，网格计算研究已经获得了 很大的发展，取得了很多有重要价值的成果，国内外有很多网格计算项目，其中许 多项目都是由政府资助的国家级项目。 t e r a g r i d l 3 i 项目由美国国家科学基金于2 0 0 1 年8 月发起，当时用5 3 0 0 万美元资 助四个超级计算中心，构建计算网格，目标是为开放的科学研究建立和部署一个世 东北大学硕士学位论文 第一章引言 界最大的、最全面的分布式计算基础设施。当前，该项目聚集了分布在9 个地点的 计算和存储资源，提供了2 0t e r a f l o p s 的聚合计算能力，也开发了大量的网格计算 工具。2 0 0 3 年9 月该项目宣称将增加更多的科学设备、大规模数据集、计算资源和 存储资源。该项目使用了g l o b u s t o o l k i t 、c o n d e r 等面向计算网格环境的软件，使得 登陆到该计算网格环境的用户可以透明的使用其中的计算、存储资源，进行大规模 科学计算和数据处理。 i p g ( i n f o r m a t i o np o w e rg r i d ) 4 1 。美国n a s a 构建了该网格计算实验床，它 可以将n a s a 分布在各地的计算和存储资源通过网络( 包括无线网络) 连接起来， 解决了n a s a 目前无法解决的科学与工程计算和数据管理等问题。 p a c i ( p a r t n e r s h i p f o r a d v a n c e d c o m p u t a t i o n a l i n f r a s t r u c t u r e ) 。该项目由美国国 家科学基金资助，目标是通过将学术界、政府部门和工业界的计算基础设施联合起 来，建立一个网格计算基础设施的伙伴联盟，促进科学发现、知识刨新和工程开发。 教育部的中国教育科研网格项目( c h i n a g r i d ) 。该项目是“十五”国家“2 1 1 工程”一公共服务体系“c e r n e t ( 中国教育科研网) 高速地区网和重点学科信息 服务体系建设”项目中的重要建设内容，目标是在2 0 0 5 年建立聚合计算能力超过 1 5 万亿次量级的教育科研网络，形成世界上最大的超级网格之一，并争取在网格计 算的基础研究和应用研究方面走在世界前列。 另外，国内还有一些行业应用网格和地区性网格研发项目，如中国气象网格、 空间信息网格、上海城市网格等。国内多个大学、科研单位也已经开始了网格计算 技术的研究，中国科学院计算所研究开发了v e g a 网格【5 】，清华大学、国防科技大 学、华中科技大学等单位在网格技术研究中都取得了一定的成果。 这些项目围绕网格中间件、网格调度、网格性能监测和预报、网格资源选择、 网格编程环境、网格门户、网格环境下的数据管理和服务等方面开展了丰富的研究， 也构建了多个网格计算实验床。 1 1 2 网格任务调度简介 网格就是基于i n t e m e t 构建的分布式计算系统，它除具有广域性、异构性、动 态性三大特点，同时还具有管理复杂的特点。与因特网的域管理机制类似，网格系 统中的各种资源属于不同的机构与组织，网格资源应具有自治性。但网格资源也必 须能提供统一管理，具有互操作特征，因此，管理网格系统的管理机制尤其是任务 调度机制更为复杂。当前网格应用多集中于解决科学、工程、商业领域中规模庞大、 计算复杂、需要使用多种异构资源的计算问题，这样的问题大量存在，而且在任何 个单一的超级计算机上都无法解决。由于网格资源所具有的这些特点以及网格应 用的复杂性，以前针对传统的分布式计算的调度方法已经不适用于网格环境中的任 务调度。在传统的并行和分布式调度闯题中，所涉及的计算资源是同构的，因此不 2 东北大学硕士学位论文第一章引言 必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且，计算 资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。 网格任务调度的目的就是寻找最佳的任务一资源匹配。因此，不同的网格任务调度 系统就可能有不同的调度目标，有的是为了增大系统的计算吞吐率，有的是为了使 系统的利用率最大化，有的则是为了以最经济、最节省的方式使用户的需求得到满 足。 1 2 研究现状综述 1 2 1 网格任务调度的研究现状 目前，网格计算已经在许多方面进行了应用，针对不同的应用，有许多网格任 务调度模型和算法被提出。网格的出现，对分布式任务调度研究提出了新的挑战。 目前，已有许多科研组织对网格任务调度进行了研究。以下为当前网格计算中几个 主要的调度模型以及相关的调度算法。 c o n d o r c o n d o r 系统是面向高吞吐率计算( h i g h t h r o u g h p u t c o m p u t i n g ) 而设计的，它 的主要目的就是利用网络中工作站的空闲时间来为用户服务。针对这种应用，c o n d o r 使用的调度方法相对简单。它的调度分为两部分：匹配( m a t c h i n g ) 和声明( c l a i m i n g ) ， 在匹配阶段，m a t c h m a k e r 在可获得资源中找到最适合任务的资源，然后通知用户和 服务提供者，随后用户和服务提供者再进行声明，以此确立两者之间消费与服务的 关系。 n i m r o d 由于网格的异构性，其资源可能被不同的个人或者组织拥有，从而具有不同的 管理策略、访问成本以及动态变化的性能。n i m r o d 系统的主要目的就是在保证用户 需求得到满足的条件下为用户提供最经济的计算模式。为了达到这个目的，n i m r o d 系统中采用了根据用户任务完成时间以及花费预算的要求的算法来对任务进行调 度。 a p p l e s 6 a 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 的简称，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 r s 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 等调度策略都可以被使用。 随着网格研究的延伸，服务质量q o s 成为任务调度研究中需要考虑的新因素。 在网格环境中，有些应用可能对计算资源能够提供的q o s 有要求，这就使得调度算 3 东北大学硕士学位论文第一章引言 必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且，计算 资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。 网格任务调度的目的就是寻找最佳的任务一资源匹配。因此，不同的网格任务调度 系统就可能有不同的调度目标，有的是为了增大系统的讨算吞吐率，有的是为了使 系统的利用率最大化，有的则是为了以最经济、最节省的方式使用户的需求得到满 足。 1 2 研究现状综述 1 2 1 网格任务调度的研究现状 目前，网格计算已经在许多方面进行了应用，针对不同的应用，有许多网椿任 务调度模型和算法被提出。网格的出现，对分布式任务调度研究提出了新的挑战。 目前。已有许多科研组织对网格任务调度进行了研究。以下为当前网格计算中几个 丰要韵调度模型以及相关的调度算法。 c o n d o r c o n d o r 系统是面向高吞吐率计算( h i g ht h r o u g h p u tc o m p u t i n g ) 而设计的，它 的主要目的就是利用网络中工作站的空闲时间来为用户服务。针对这种应用，c o n d o r 使用的调度方法相对蕙单。它的调度分为两部分：匹配( m a t c h i n g ) 和声明( c l m m i n g ) ， 在匹配阶段，m a t c h m a k e r 在可获得资源中找到最适合任务的资源，然后通知用户和 服务提供者，随后用户和服务提供者再进行声明，以此确立两者之间消费与服务的 关系。 n i m r o d 由于网格的异构性，其资源可能被不同的个人或者组织拥有，从而具有不同的 管理策略、访问成本以及动态变化的性能。n i m r o d 系统的主要目的就是在保证用户 需求得到满足的条件下为用户提供最经济的计算模式。为了达到这个目的，n i m r o d 系统中采用了根据用户任务完成时间以及花费预算的要求的算法来对任务进行调 度。 a p p l e s 【6 】 a 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 的简称，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 r s 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 等调度策略都可以被使用。 随着网格研究的延伸，服务质量q o s 成为任务调度研究中需要考虑的新因素。 在网格环境中，有些应用可能对计算资源能够提供的q o s 有要求，这就使得调度算 在网格环境中，有些应用可能对计算资源能够提供的q o s 有要求，这就使得调度算 3 东北大学硕士学位论文第一章引言 必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且，计算 资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。 网格任务调度的目的就是寻找最佳的任务一资源匹配。因此，不同的网格任务调度 系统就可能有不同的调度目标，有的是为了增大系统的计算吞吐率，有的是为了使 系统的利用率最大化，有的则是为了以最经济、最节省的方式使用户的需求得到满 足。 1 2 研究现状综述 1 2 1 网格任务调度的研究现状 目前，网格计算已经在许多方面进行了应用，针对不同的应用，有许多网格任 务调度模型和算法被提出。网格的出现，对分布式任务调度研究提出了新的挑战。 目前，已有许多科研组织对网格任务调度进行了研究。以下为当前网格计算中几个 主要的调度模型以及相关的调度算法。 c o n d o r c o n d o r 系统是面向高吞吐率计算( h i g h t h r o u g h p u t c o m p u t i n g ) 而设计的，它 的主要目的就是利用网络中工作站的空闲时间来为用户服务。针对这种应用，c o n d o r 使用的调度方法相对简单。它的调度分为两部分：匹配( m a t c h i n g ) 和声明( c l a i m i n g ) ， 在匹配阶段，m a t c h m a k e r 在可获得资源中找到最适合任务的资源，然后通知用户和 服务提供者，随后用户和服务提供者再进行声明，以此确立两者之间消费与服务的 关系。 n i m r o d 由于网格的异构性，其资源可能被不同的个人或者组织拥有，从而具有不同的 管理策略、访问成本以及动态变化的性能。n i m r o d 系统的主要目的就是在保证用户 需求得到满足的条件下为用户提供最经济的计算模式。为了达到这个目的，n i m r o d 系统中采用了根据用户任务完成时间以及花费预算的要求的算法来对任务进行调 度。 a p p l e s 6 a 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 的简称，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 r s 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 等调度策略都可以被使用。 随着网格研究的延伸，服务质量q o s 成为任务调度研究中需要考虑的新因素。 在网格环境中，有些应用可能对计算资源能够提供的q o s 有要求，这就使得调度算 3 东北大学硕士学位论文 第一章引言 法有必要对资源进行甄选，将任务分配到符合其要求的资源上去运行。因此，在这 种情况下，任务调度程序在做出调度决定前需要考虑到其中涉及到的q o s 因素。然 而，现在已有的网格任务调度模型，如a p p l e s 、n i m r o d 和c o n d o r ，都未考虑q o s 因素。针对以上的情况，有人提出了q o sg u i d e dm i n - m i n 算法，这些算法大多是在 m i n m i nh e u r i s t i c 的基础上改进而来。 1 2 2 网格q o s 的研究现状 q o s 概念首先出现于i p 网络，在早期计算机网络及分组交换网络中，网络一般 只为业务提供尽力传送( b e s t e f f o r t ) 服务，业务量尽快传送，没有明确的时间和可 靠性保障。在这样的网络系统中，所有业务竞争的共享网络资源，业务之间没有明 确的区分。近年来，随着i p 技术以及高速以太网技术的飞速发展，i m e r n e t 上的多 媒体应用层出不穷，单一的服务类型已不能满足业务发展的需要，于是提出了服务 质量( q o s ：q u a l i t yo f s e r v i c e ) 的概念。一般而言q o s 是指网络在传输数据流时要 求满足的一系列服务请求，强调端到端或网络边界到边界的整体性。具体可以量化 为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标。q o s 控制技术的基本目标 是为i n t e r n e t 应用提供性能保证和服务区分。 为了适应网络应用的进一步发展，i n t e r a c t 2 工作组提出了i n t e r a c t 2 的草案。 i n t e r n e t 2 的草案对q o s 的要求如下： ( 1 ) 支持高级应用，如：双向交互音，视频，远程设备控制，虚拟的协同工作 环境等。 ( 2 ) 良好的可扩展性。 ( 3 ) 可管理性。 ( 4 ) 提供可计量的服务。 ( 5 ) 能与端用户操作系统和中间件协同工作。 伴随着网络服务质量( q o s ) 技术研究和网格技术的兴起，近期更多研究将q o s 引入网格领域并且在国际上得到越来越多的学者和业界的瞩目，成为网格技术的一 个新的研究领域。 网格系统如何能及时有效地响应用户请求，如何能实时地获得服务实例运行状 态以及如何保证用户应用的服务质量，并进行动态组合的服务质量保障逐渐成为网 格的本质问题。网格的功能与性能评价将不只是采用传统计算机的评价标准( 如速 度、加速比、性价比等) ，而以用户满意度为目标，用服务质量来衡量。目前在网格 q o s 的研究上尚处于起步阶段，没有对网格q o s 的特性进行系统化的研究与归纳。 有些研究将网格资源的分配划分为两阶段进行，即首先在网格这个宏观环境下。 分配，然后再由具体的资源管理者在资源所在系统进行微观分配，它指出了网格环 境下资源分配的特点，但没有结合q o s 要求进行考虑。有些则提出并建立了一个通 4 东北大学硕士学位论文 第一章引言 用的支持资源预留和分配的体系架构g a r a 。g a r a 为不同种类的资源提供了统一 的q o s 预留机制，向用户和应用开发者提供了方便的e n d t o e n d 的q o s 控制机制。 在g a r a 的基础上，a r o y 等学者提出了一种新的消息传递架构m p i c h ，g q ，它 综合了q o s 描述、预留和实现技术，从基于消息传递编程的角度给出了网格q o s 的一些实现机制。虽然在m p i c h g q 中，a r o y 涉及到了网格q o s 层次的问题， 但没有对网格q o s 的层次结构进行深入研究，也没有对以服务为中心的网格q o s 的特性进行系统分析。图1 1 为提出的基于q o s 的网格资源分配管理模型。 图1 1 基于q o s 的网格资源分配管理模型g r a m q o s f i g i i q o sb a s e dg r i dr e s o u r c e sa l l o c a t i o na n dm a n a g e m e n tm o d e lg r a m q o s g r a m q o s 主要由网格服务市场、网格中间件服务、网格资源代理和网格资源 节点等四部分组成。其中网格服务市场位于网格系统的网格服务层，该模块一方面 为网格用户提供查询网格服务的功能，另一方面为网格服务提供者提供注册、发布 网格服务的功能。当网格服务提供者进行服务注册、发布时，要根据资源管理系统 的要求提供身份证明和服务的相关描述，如服务的资源需求、q o s 不同级别的参数 要求等。网格中间件服务模块主要负责网格系统的登录、安全控制、用户信息管理 和用户资源使用的记账功能等。网格资源代理位于网格系统的虚拟组织层，它是物 理资源在v o 中的逻辑表现，代表物理资源与用户进行交互。网格资源节点位于网 格系统的物理资源层，它向网格用户提供具体的网格服务，但它的物理特性对用户 是透明的，用户只能通过网格资源代理与物理资源进行交互。 国内一些研究人员将网格q o s 的层次结构一般归纳为以下层次结构： 5 东北犬学硕士学位论文 第一章引言 图1 2 网格q o s 层次结构 f i g 1 2 g r i dq o sh i e r a r c h ys t r u c t u r e 最上层是网格服务q o s 层，该层描述了网格服务的q o s 要求，如服务响应时 间、系统传输速率、参与服务的资源质量和性能要求等。第二层为虚拟组织q o s 层， 它包括系统q o s 和逻辑资源q o s ，描述了满足网格服务层q o s 参数的系统需求和 逻辑资源需求。其中系统q o s 主要指在通信和逻辑资源所在资源节点的支撑环境等 两方面的q o s 需求，逻辑资源q o s 主要指直接提供网格服务的逻辑资源在性能、 安全等方面的q o s 需求，如逻辑资源的质量等级、信任度、安全级别等。最底层是 物理资源q o s 层，包括网络q o s 和资源节点q o s 两个方面。其中网络q o s 描述了 网络性能的具体q o s 参数要求，如延迟、带宽、丢包率等；资源节点q o s 包括提 供网格服务的物理资源q o s 和它所在节点的支撑环境q o s ，物理资源q o s 是逻辑 资源q o s 在物理资源层的映射，它描述了实际提供服务的物理资源的q o s 要求， 如物理资源的共享策略、可负载能力、质量等级、可使用时间、任务中断率、要求 的访问权限等，节点支撑环境q o s 是指资源所在节点的其他辅助设备的q o s ，如资 源节点的操作系统环境、内存大小等，它是虚拟组织层系统q o s 在资源支撑环境方 面的q o s 要求的映射。 1 3 研究的意义 网格计算是互联网的第三次浪潮，是未来网络发展的方向。网格计算的最大特 点就是在广泛分布的、异构的、动态的资源上实现全面、动态的共享和协同的计算。 o g s a 的五大目标中的跨分布式异构平台管理资源、交付无缝的服务质量、为自治 管理解决方案提供公共基础三大目标都与网格服务的服务质量q o s 密切相关。因 此，在面向服务的网格环境下，服务质量q o s 便成为网格系统的一个重要的性能指 6 - 东北大学硕士学位论文 第一章引言 标。而用户q o s 需求的保证情况取决于执行服务时系统将任务分配到相应等级的最 佳资源。因此，在面向服务的网格环境下，就很必要进行基于q o s 的网格任务调度 的研究。 如何使用网格资源，高效地完成计算任务是网格系统的研究重点之一。网格的 使用模式是用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按 照某种策路把这些任务分配给合适的资源。高效的调度算法或策略可以充分利用网 格系统的处理能力，从而提高应用程序的性能。这些都是本文研究工作的重点。 本课题源于高等教育学校博士学科点专项科研基金项目“基于分布式哈希表的 网格应用基础设施构建技术”。本文在此课题研究的基础上进行了网格任务调度的研 究工作。在原有网格任务调度中加入多维q o s 概念，同时将p e t r i 网理论引入网格 调度领域。提出更具有服务质量保障的网格随机高级p e t r i 网调度模型与改进的基于 多维q o s 的调度算法。 1 4 存在问题与研究内容 现有的网格理论也有诸多不足，主要表现在： ( 1 ) 缺乏调度模型，理论研究困难 由于网格的广域性、多样性和异构性特点，目前大多网格任务调度研究主要是 针对某个问题设计启发式算法，而不是基于某种模型从理论上推导算法特性和性能， 这种情况下，为分析算法性能，需要大量仿真工作，由于缺乏理论支持，在不同的 拓扑结构和业务特性下，算法性能可能差异较大，而且仿真得到的结果缺乏说服力。 ( 2 ) 平台技术复杂，缺乏实用性 繁琐冗长的w s d l 文档的编写导致网格支撑开发工具使用复杂，目前都只能由 手工编写。这必然阻碍网格研究工作的发展，同时也使网格技术与今天的计算机技 术的发展不相协调，离实际的应用还有一定距离。 ( 3 ) 安全性设计不足 网格作为一个“复杂巨系统”，缺乏相应的安全性设计，现有设计未根据复杂 巨系统自身的特点，从网格整体出发，缺乏新的安全理念与安全措施，很难确保网 格整体的可靠性。 网格理论许多概念现在大都是建筑在主观认识的基础之上的，欠缺理论基础。 尤其是网格任务调度领域的理论基础更是薄弱，如何使用网格资源，高效地完成计 算任务是网格系统的研究重点之一。成熟的网格管理系统首先解决了计算能力大小 的限制，其次克服了地理位置的限制，最后还打破了传统的共享或协作方面的限制。 因此，网格系统研究的核心目的就是突破以往强加在计算资源之上的种种限制，使 人们可以以一种全新的更自由、更方便的方式使用计算资源，解决更复杂的问题。 高效的调度算法或策略可以充分利用网格系统的处理能力，从而提高网格系统的性 7 东北大学硕士学位论文 第一章引言 能。因此，本文着重进行网格调度领域的理论研究，同时采用模拟器验证调度算法 的正确性及性能。为更好地研究和解决网格问题，必须探讨新的认识论工具和理论 分析方法。基于随机高级p e t r i 网的网格调度模型就是本文在这一方面所进行的探 索。 为解决网格任务调度领域的不足，本文重点研究的是基于多维q o s 的网格任务 调度策略和基于随机高级p e t r i 网的网格调度模型这两个方面，在这两个方面中提出 了自己的方法，并在一定程度上验证了方法的优越性。 网格任务调度是网格研究中的一个重要课题，它对提高网格系统的服务质量起 着至关重要的作用，本文首先介绍了网格计算和网格任务调度的产生，综述了网格 任务调度以及网格q o s 的研究现状，并在此基础上对网格任务调度展开研究，主要 研究网格任务调度算法和网格调度模型两个方面。在现有的网格调度算法基础上考 虑多维q o s ，提出改进的基于多维q o s 的网格任务调度算法：同时将p e t r i 网理论 引入网格任务调度领域，提出了一种基于随机高级p e t i i 网的网格任务调度模型，能 够较好地对基于q o s 的网格任务调度策略进行性能分析。最终提出了能提供更好的 分析q o s 性能的随机高级p e t r i 网调度模型。 采用的技术方面，主要采用g r i d s i m 这一网格建模与仿真平台，针对真实网格 环境的特点，实现了本文提出的基于多维q o s 的网格调度算法仿真。同时通过s p n p 软件包对提出的网格调度模型进行性能分析，验证p e t r i 网理论能够有效地对采用不 同网格调度策略的网格系统进行建模，从而为网格任务调度奠定了理论基础。 8 东北大学硕士学位论文 第一章引言 1 5 研究思路和论文结构 1 5 1 研究思路 本文开展研究工作所遵循的基本思路如图1 3 所示。 问题的提出 确定研究的对象，阐述研究的意义 厂 、 基于多维q o s 的 基于p e t r i 网理 调度策略论的调度模型 l 最终形成一个能提高网格服务质量的网格任务调度框架 l 结论和展望 图1 3 本文的研究思路 f i g1 3 r e s e a r c hi d e ao f t h i st h e s i s 1 5 ，2 论文的结构安排 本文讨论了网格任务调度及所涉及到的相关技术，根据研究过程所涉及的内 容，分为以下几个部分： 第一章：引言：介绍网格计算以及任务调度和q o s 的产生、研究现状和存在的 - 9 - 东北大学硕士学位论文第一章引言 问题及研究思路等。 第二章：介绍网格任务调度方法相关知识。 第三章：介绍本文所需的p e t r i 网理论的基础知识。 第四章：介绍现有的网格调度算法，提出了一种改进的基于多维q o s 的启发式 调度算法，比较了本文提出的算法与传统算法，指出算法的优越性；同时采用 g r i d s i m 这一网格建模与仿真平台，针对真实网格环境的特点，实现了本文所提出 的基于多维q o s 的网格任务调度算法的仿真。 第五章：提出了一种基于随机高级p e t r i 网理论的网格环境下的调度模型，并利 用s p n p 软件包对网格任务调度策略进行性能分析。 第六章：总结本文的研究内容，指出进一步的研究方向。 1 0 东北大学硕士学位论文 第二章网格任务调度方法简介 第二章网格任务调度方法简介 由于计算网格的目标是利用网络上一切可利用的、空闲的计算资源来对计算量巨 大的、高度复杂的任务进行计算求解，因此，如果要提高计算网格的计算效率，那么 必须对网格任务的调度进行更深入的研究，提出更有效的模型、算法以及解决方案。 本章在介绍网格体系结构的基础上，介绍了当前研究界对网格任务的调度方法。 2 1 支持任务调度的网格体系结构 网格体系结构就是构成网格的各层及其协议的集合，关于如何建造网格的技 术，包括对网格基本组成部分和各部分功能的定义和描述，网格各部分相互关系与 集成方法的规定及网格有效运行机制。目前网格体系结构的设计已有了一定的研究， 提出的模型有：五层沙漏模型【l 】、开放网格服务体系结构( o o s a ) 、模型组件模型、 计算池模型、c p u 模型、神经网络模型、节点模型等。其中五层沙漏是经典的模型。 2 1 1 五层沙漏模型 五层沙漏模型是在g l o b u s 项目中提出的具有一般性的网格体系结构，它是以协 议为中心的“协议结构”，侧重定性的描述，强调被共享的物理资源以及这些资源所 支持的服务，突出服务与应用编程接口( a p i ) 和软件开发工具( s d k ) 的重要性。 它建立在互联网协议之上，以互联网协议中的通信、路由、名字解析等功能为基础， 图2 i网格五层沙漏结构的模型 f i g 2 1 t h ef i v e - l a y e rh o u r g l a s sm o d e lf o rg r i da r c h i t e c t u r e 自下而上分为五层：构造层、连接层、资源层、汇集层和应用层。每层都有自己的 服务、a p i 和s d k ，上层协议调用下层协议的服务。网格内的全局应用都通过协议 提供的服务调用操作系统。这里的描述是抽象度较高的、偏于定性的，对设计和实 现约束较少。没有完全详细介绍协议各层中的协议模块及相关的各种服务、a p i 和 1 1 器囤 东北大学硕士学位论文 第二章网格任务调度方法简介 s d k 。一般用和描述t c p i p 协议相似的原理描述网格体系结构，即众所周知的“沙 漏模型”，如图2 1 所示。 ( 1 ) 构造层。构造层控制局部的资源，并向上提供网格中可供共享访问的资 源，它们是物理或逻辑实体，如高性能计算资源、