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

浙江工业大学硕士学位论文 基于0 0 s 的网格任务调度模型与算法研究 摘要 网格因其潜在的巨大的应用前景而成为当今国际上研究的热点问 题。由网格系统的实现技术以及网格自身的定义可知，高性能的网格任 务调度算法是网格的核心技术，服务质量( q o s ：q u a l i t yo f s e r v i c e ) 是网格 任务调度过程必须考虑的一个重要指标。因此，对基于服务质量的网格 调度模型和调度算法的研究是网格研究中的主要内容，更是重点内容。 文中主要提出了三个网格任务调度模型，并在这些调度模型上对传 统的网格任务调度算法做出了改进： 信任驱动网格任务调度模型。信任也是一种q o s 需求，信任度的 计算采用线性补偿方法。将传统的几种调度算法改进成为以信任度为唯 一调度目标的调度算法，并采用数据仿真方式可得出，随着具有强信任 关系的任务数目的增加，改进的t d m a x - m i n 算法会优于t d m i n m i n 算 法。同时，在此模型的基础上，提出一种双匹配的任务调度算法( t d b m ) ， 将单目标调度改为双目标调度，即在优化信任值同时，优化任务的完成 时间。仿真结果表明，在任务、机器高异构的环境下，改进的双匹配t d b m 算法要优于t d m i n m i n 任务调度算法。 基于证据推理( e r ：e v i d e n t i a lr e a s o n i n g ) 的网格任务调度模型。用 e r 方法合成的服务质量，较之线性补偿方法可以实现对不确定信息的处 理。同时，将服务质量作为调度算法的约束条件，提出一种以基于证据 推理和多q o s 约束的网格任务调度算法，跟传统的调度算法比较起来可 缩短调度的时间跨度。 浙江工业大学硕士学位论文 基于联系数的网格任务调度模型。用联系数研究和处理网格调度 中的综合不确定性问题。在简单介绍集对分析概念和应用情况基础上， 引入联系数概念、运算规律和全序关系，提出了基于联系数的不确定网 格调度算法，仿真结果表明，改进后的调度算法能较好地描述网格任务 预期执行时间的动态性和不确定性。同时，用联系数的形式表示服务质 量参数，其合成初步采用线性补偿方法，并提出调度的目标函数。以此 为调度目标的改进后的调度算法的性能如何，还有待进一步的研究。 关键词：调度算法，服务质量( q o s ) ，网格，信任，e r ，联系数 l i 浙江工业大学硕士学位论文 t h er e s e a r c ho ng r i dt a s ks c h e d u l i n g m o d e l sa n da l g o r i t h m s b a s e d o n q o s a b s l r a c t t h eg r i dr e s e a r c h , i nt h ec u r r e n ti n t e r n a t i o n a l ，i sah o t s p o ta n df r o n t a l f i e l df o ri t sh u g ei m p l e m e n t a t i o n a c c o r d i n gt ot h ei m p l e m e n tt e c h n o l o g yo f g r i ds y s t e ma n dt h ed e f i n i t i o no ft h eg a d ，w ec a l lc o n c l u d et h a th i g hp o w e r e d g r i dt a s ks c h e d u l i n ga l g o r i t h mi sak e yt e c h n o l o g yf o rt h eg a d ，a n dg r i d q u a l i t yo fs e r v i c ei sa i li m p o r t a n tf a c t o rw h i c hm u s tb ec o n s i d e r e di nt h e p r o c e s so ft a s ks c h e d u l i n g t h e r e f o r et h er e s e a r c h i n go fg a ds c h e d u l i n g m o d e lb a s e do nq u a l i t yo fs e r v i c ea n dt a s ks c h e d u l i n ga l g o r i t h mi sn o to n l ya m a i nc o n t e n t sb u ta l s oak e yc o n t e n t sf o rt h e 舒d 。 t h r e eg a dt a s ks c h e d u l i n gm o d e l sp r o p o s e da n ds e v e r a lt a s ks c h e d u l i n g a l g o r i t h m si m p r o v e db a s e do nt h i sp r o p o s e dm o d e l s t r u s t - d r i v e ng r i dt a s ks c h e d u l i n gm o d e l t r u s ti sa l s oaq o s r e q u i r e m e n t a d o p t i n gt h em e t h o do fh n e a rc o m p e n s a t i o nc a l c u l a t e st h eg r i d t r u s tv a l u e s e v e r a lk i n d so ft a s ks c h e d u l i n ga l g o r i t h m sh a v ei m p r o v e di n t o t a k i n gt r u s ta st h eo n l ys c h e d u l i n gg o a l t h r o u g ht h ee m u l a t i o nr e s u l tw e c o n c l u d e dt h a tt h ei m p r o v e dm a x - m i na l g o r i t h m ( t d - m a x m i n ) i sb e r e rt h e n 1 1 1 浙江工业大学硕士学位论文 t h ei m p r o v e dm i n r a i na l g o r i t h m ( t d m i n - m i n ) a st h ei n c r e a s eo ft h es 2 0 n g r e l a t e dt a s k sn u m b e ls i m u l t a n e i t y , p r o p o s e dad o u b l em a t c hs c h e d u l i n g a l g o r i t h mw h i c hc h a n g e dt h es i n g l eg o a li n t oad o u b l eg o a lb a s e do i lt h e f o r m e rm o d e l t h ep u r p o s eo ft h i sc h a n g ei st oo p f i m i zt h et r u s tg o a la n d m a k e s p a na tt h es a m et i m e t h ee m u l a t i o nr e s u l ts h o w st h a tt d b mi sb e t t e r t h a nt d m i n m i n g r i dt a s ks c h e d u l i n gm o d e lb a s e do ne rt h e o r y t h eq o s v a l u ei s c a l c u l a t e db ye rt h e o r yw h i c h , c o m p a r e dw i t ht h el i n e a rc o m p e n s a t i n g m e t h o d e a r ld e a lw i n lt h eu n c e r t a i n t yi n f o r m a t i o n p r o p o s e dap r i o r i t ya n d m u l t i p l eq o sr e s t r a i n e dt a s ks c h e d u l i n ga l g o r i t h mo nt h eb a s i so fe rt h e o r y c o m p a r e d1 ) l ，i m t h et r a d i t i o n a ls c h e d u l i n ga l g o r i t h m s ，i tc a l ls h o r t e nt h e m a k e s p a n o r i dt a s ks c h e d u l i n gm o d e lb a s e do l lc o n n e c t i v e - n u m b e r u s i n g c o n n e c t i v en u m b e ro fs e tp a i ra n a l y s i s ( s p a ) t oe x p r e s sa n dp r o c e s st h e s y n t h e t i cu n c e r t a i n t yi nt a s ks c h e d u l i n go ft h eg r i d a f t e ri n t r o d u c i n gs p aa n d i t s a p p l i c a t i o nb r i e f l y , p r e s e n t t h ed e f i n i t i o no fc o n n e c t i v e n u m b e r , o p e r a t i o n a lr u l e s a n dt o t a lo r d e rr e l a t i o ns u i t a b l ef o rc o m p u t i n g 鲥d s c h e d u l i n g s e v e r a la l g o r i t h m sa l ep r e s e n t e df o rt h eu n c e r t a i n 鲥d t h e o r y a n a l y s i sa n dn u m e r i c a le x p e r i m e n ti l l u s t r a t et h a tt h e s ea l g o r i t h m sc a ne x p r e s s t h ed y n a m i c sa n du n c e r t a i n t yo fe x p e c t e dt i m et oc o m p u t eo ft a s k si nt h e c o m p u t i n gg r i de n v i r o n m e n t s i m u l t a n e i t y , c o n n e c t i v en u m b e ru s e dt o d e s c r i b et h eq o sp a r a m e t e r s t a s ks c h e d u l i n gf i m c t i o nw a sp r o p o s e d t h e i v 浙江工业大学硕士学位论文 c a l c u l a t i o no f t h eq o s v a l u ea l s oa d o p t e dt h em e t h o do f l i n e a rc o m p e n s a t i o n h o w e v e r , i ti sn e e daf l - t h e rr e s e a r c hi nc o m p a f n go fe a c ha l g o r i t h m s p e r f o r m a n c e k e yw o r d s ：s c h e d u l i n ga l g o r i t h m , q o s ，g r i a ，t r u s t , e r , c o n n e c t i v e - n u m b e r v 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究 工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其 他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其 它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名：漱丽君日期：如四年p 月鹚日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“奶 作者签名： 导师签名： 日期：阳0 7 年f 月硝日 日期：川年，2 - 月 浙江工业大学硕士学位论文 1 1 研究背景 1 1 1 网格 第一章绪论 网格( g r i d ) 概念产生于2 0 世纪9 0 年代中期，是从电力网的概念借鉴过来的，其最 终目的是希望用户在使用网格资源时，就如同现在使用电力一样方便，即只要你能够 接触到网格，就可以根据自己的需要，从网格获取各种资源与服务，而不必关心资源 与服务所在的具体位置1 1 1 【2 】。对于网格的定义现在还不统一，最有影响力的是2 0 0 1 年 l a nf o s t e r 与c a r lk e s s e l m a n 在t h ea n a t o m yo f t h eg r i d ) 中对网格的定义，认为可以 从三个方面判断一个系统是否为网格系统：协调非集中控制的资源；使用标准的、 开放的、通用的协议和接口； 获得非凡的服务质量( q o s ，q u a l i t yo fs e r v i c e ) 【3 1 。从本 质上来讲，网格是把整个互联网整合成一台巨大的超级计算机，实现计算资源、存储 资源、数据资源、信息资源：知识资源、专家资源的全面共享 4 1 。它主要应用于解决 科学、工程、商业领域中规模庞大、计算复杂、需要使用多种异构资源的计算问题， 这样的问题大量存在，而且在任何一个单一的超级计算机上都无法解决。网格就是一 个基于广域网构建的分布式计算系统，它与传统的分布式系统的主要区别在于它具有 广域性、异构性、动态性三个特点 5 1 。网格技术将成为引领互联网进入下一波发展大 潮的主线，由于网格巨大的前景，世界上一些主要的国家和主要的公司在网格基础设 施的建设和网格平台的开发和应用上加大了投资力度。我国8 6 3 网格专款拨款超过 5 0 0 0 万构建国家高性能建设环境h p c e 6 。网格是未来i n t e r n c t 的发展方向，也就是说， 网格会成为未来的网络基础设施，几乎所有的应用都将基于网格，其应用领域将是十 分宽广的。 1 1 2 网格任务调度 所谓任务调度，即m 台机器( m a c h i n e ) 对j 个任务( j o b ) 的处理过程，调度算法为各 l 浙江工业大学硕士学位论文 任务分配在各机器上的加工时间，使某些性能达到最优 7 1 。网格任务调度的主要目标 就是为了完成用户提交的任务和满足用户对任务运行的要求，把网格中所有可用资源 ( 计算资源、存储资源和网络资源) 与任务进行匹配，找到最好最合理的资源分配方式 和资源调度策略，其本质就是一个组合优化问题。具体的调度目标包括：最优跨度 ( o p t i m a lm a k e s p a a ) 、服务质量( 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 ) 、经济 原n ( e c o n o m i cp r i n c i p l e s ) 等隅】。其中时间跨度( m a k e s p a n ) 是一个最主要、最常见的目 标，指的是调度的长度，跨度越短说明调度策略越好【引。由于网格其本身所具有的特 性以及网格应用的复杂性，以前针对传统的分布式计算的调度方法己经不适用于网格 环境中的任务调度了。因此，网格的出现对分布式任务调度研究提出了新的挑战。新 的挑战要求f 8 】【1 0 】：网格任务调度算法必须是分布式的，网格中的资源在地理上分布， 在规模最大的全球性网格中，资源分布在全世界，要实现一种全局的统一集中式的调 度是不可能的，必须采取一种并行分布式的策略来进行任务的管理与调度；网格任 务调度策略必须具有自治性。网格中的资源可以被网格作业和资源所属节点的内部任 务所利用，网格调度系统不能干涉节点内部的调度策略。网格任务调度是面向异构 平台的。由于网格系统包括的资源是连接在i n t e r n e t 上的所有节点上的资源，包括各类 主机、工作站甚至p c 机，可能使用不同硬件和软件，它们都是异构的，因此，任务 调度必须面向异构平台。网格任务调度具有动态可扩展性。网格中的资源不仅是异 构的而且是动态改交的。随时都有新的资源加入网格。也有资源随着节点的离开或因 资源故障而消失于网格系统。调度系统必须从不断变化的可利用资源中选择出最佳资 源以满足用户的需要。随着网格资源的不断增加和应用任务的增长，任务调度必须具 有可扩展性才不至于降低这个网格系统的性能。任务调度本身是一个n p 难问题【】。 又加之网格的动态性、分布性、异构性和自治性，使得网格下的任务调度更加复杂。 但是由于网格任务调度问题是网格研究中所必须解决的一个关键问题，也是网格应用 的基础【1 2 】。高效的任务调度策略和算法可以充分利用网格系统的处理能力，从而提高 网格应用程序的性能，以便更好地利用网格资源。因此，网格任务调度引起众多学者 的关注，成为网格中一个热点研究的问题【8 】。 i i 3 网格服务质量 “提供非凡的服务质量”是判断网格的三个准则之一”3 1 【1 4 1 。网格服务质量要能 2 浙江工业大学硕士学位论文 满足以下需求：支持不同特征混合留，提供可靠传输；统一的资源预留和分配， 实现联合分配；预留策略，提高预留的灵活性；协定协议，保证用户的提前预留 状态及期望的资源质量，形成协定并得到监控；安全性，遵从网格系统的安全机制； 精简性，不影响网格系统的整体性能；可扩展性，网格q o s 机制应能适应动态 变化【b l 。网格q o s 的属性包括两个方面：定性的和定量的。定性的服务质量属性它 描述了所需求的服务的某些性能特点，这些性能特点是用户可见的，它以用户可理解 的语言表述为一组参数，这些参数是对服务者服务水平的一种测量和评价，比方说服 务的可靠性和用户满意度。定量的服务质量属性比较广泛，如计算q o s 指定计算资 源c u p 如何使用、分配，可以把占用c p u 的比例或数目做为服务质量属性；存储资 源q o s 属性有访问速度、存储能力等；经济上使用成本或费用( c o s t ) 也是一个重要的 q o s 属性；还有其他特定需求的可能q o s 参数等。实际的网格应用都需要使用异构 的、多样的资源，特别是要对这些资源共享使用，各个任务间更多的是需要协作，使 得资源的调度分配、任务执行变的复杂，而目前的网格基础设施又都是建立在“尽力 服务”的基础上，因而服务质量得不到保障，在多个服务协作使用资源时，性能和效 率也容易造成降级，而且用户的需求也具有多样性。在网格的应用中，要想保证服务 质量，就必须首先描述应用的q o s 需求，确定网格服务质量的q o s 参数【1 3 】。解决以 上问题，需要引入q o s 的计算机制。随着网格技术在个领域的不断应用和推广，网 格服务质量的保证成为了一个迫切需要解决的问题，尤其是将网格应用推向商业化， q o s 将成为一个网格系统中的一个关键因素【3 j 。 1 2 网格任务调度研究现状 1 2 1 现有的网格任务调度模型 网格中的调度系统一般使用分布式调度策略，主要有以下几中调度模型：基于 “超级调度者”的方法；基于市场的方法；基于发现的方法以及由这几种方法组 合的混合技术。在超级调度者的方法中，网格环境下存在分层的多个调度器，他们相 互协作执行资源管理，该方法难以解决协作配置问题( 1 5 】【1 6 1 。对于基于市场的方法， 资源管理使用源于人类经济的原则执行，使用较多的技术是拍卖机制旧。资源发现模 型需要进一步研究具有容错和可扩展的高度分布式的发现技术。混合技术使用一个双 浙江工业大学硕士学位论文 层机制，混合可以结合多重技术实现扩展和容错方法，目前还需要进一步研究权衡不 同方案的组合。 1 2 2 现有的网格任务调度算法 现有的网格任务调度算法根据不同的任务分类，就会产生不同的任务调度算法。 网格任务可以分为相互独立的任务和相互之间存在通信的任务。调度算法一般可以分 为静态调度算法和动态调度算法f m 。 ( 1 ) 静态调度算法；静态调度算法是指所有的待处理的任务均处于待处理状态， 且被调度的任务集合和任务的加工时间都是确定的，在进行一次调度后，各任务的加 工顺序被确定，而且在以后的处理过程中不再更改。在网格计算环境中，常见的静态 调度算法有：o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g - 随机负载均衡算法) 、m e t ( m i n i m u m e x e c u t i o nt i n l e 最小执行时间调度算法) 、m c t ( m i n i m u mc o m p l e t i o nt i m e - 最小完成 时间调度算法) 、m i n m m 用 8 】阴、m a x _ m l a 用l s | 9 j 、d u p l e x ( d u p l e x 调度算法是m i n - m i n 算法与m a x - r a i n 算法的结合) 、g a ( g e n e t i ca l g o r i t h m s 一遗传算法) 、s a ( s i m u l a t c d a n n e a l i n g - 一模拟退火算法) 、g s a ( g c n e t i cs i m u l a t e da n n e a l i n g - 遗传模拟退火算法) 、 t a b u ( 禁忌调度算法) 、a ( a 算法是一种基于u 叉树的方法) 等【嘲。 ( 2 ) 动态调度算法：动态调度算法是任务运行过程中进行任务的分配与调度，任 务的到达时刻和计算时间特性不能事先确定。动态调度算法可以分为两类：在线模式 ( o n 1 i n em o d e ) 和批模式m a t c hm o d e ) 。在线模式是指任务一到来就映射到机器，该模 式对每一个任务的映射只考虑一次，也就是说一旦任务被映射就不会再改变。批模式 下，任务到来并不立即映射到机器，而是把任务收集起来组成一个任务集合，等映射 事件到来后才对该集合中的任务进行集中映射。这个独立任务的集合称之为元任务， 因此，批模式下的元任务包括新到达的任务( 也就是在最后一个映射事件之后到达的 任务) 和已经映射但还没有开始执行的任务。批模式对独立任务的集合中每一个还没 有开始执行的任务在每一次映射事件中都进行考虑直到该任务开始执行为止，因此， 批模式可以缛到整个元任务的资源需求信息和更多任务的执行时间? 从而可以做出更 合理的任务映射策略。常见的在线模式启发式调度算法有：o l b ，m c t ，m e t ， s a ( s w i t c h i n ga l g o r i t h m 一开关调度算法) ，k p b ( k - p r e c e n tb e s t - k 最优调度算法) 。批模 式下常见的启发式调度算法有：m i n - m i n 算法、m a x r e i n 算法和s u f f e r a g e 算法。在 4 浙江工业大学硕士学位论文 批模式调度算法中，元任务是每经过一个预定义的映射事件后对任务开始进行映射， 映射事件的定义主要有两种方式：规则时间间隔策略和固定任务计数策略。 静态调度算法相对较为简单，运行开销小，对数据的依赖性小，因而静态调度算 法是网格计算中最早被研究的算法。但在网格计算环境中，由于各处理器运行速度不 同而带来负载平衡的困难，且难以设计和实现，在异构平台上，静态调度策略已遇到 很多问题：设计最优化调度算法是一个n p 完全问题；准确评价任务执行时间和 通信延迟是困难的，例如在编译期估计通信延迟是不可行的，因为运行期网络争用延 迟；静态方法不能解决处理器速度的多样性，由于它们的负载可变。动态调度方法 能够有效地解决以下问题：负载评估、效应测定、作业传输、矢量计算、任务选择和 任务迁移。因此，对于异构平台，动态调度带来的负载均衡优势更加明显。动态调度 算法多种多样，除了上述介绍的外，还有d f p l 瞪、w q 、s u f f r a g e - c 、蚂蚁算法、自 适应调度、局部搜索，以及近似最佳的动态调度方法、基于计算节点能力的任务调度 算法等。算法有的利用了反馈机制，对网格中的参数进行预测、反馈、修正，从而得 到网格系统的自我平衡。但是动态调度最明显的缺点是运行期的开销，包括：处理器 问负载信号的传输，选择进程和处理器，作业相互调度带来的延迟( 这可能引起高代 价的数据重分配) 。 1 2 3 网格任务调度研究方法 当前热门的网格任务调度算法的研究多是在下列范围之中： ( 1 ) 基于启发式规则法：启发式调度方法就是将人们在生产实践中所总结、提炼 出的很多行之有效的经验和规则( 通常称其为调度规则) 应用于调度问题中解决之，因 为任务调度是n p 难问题，很难找到最优的解，因此用启发式调度方法找到接近最优 的解是十分行之有效的。很多人的研究属于此范围【刀。 ( 2 ) 系统仿真的方法：大多数系统非常复杂，很难用一个精确的解析模型来进行 描叙和分析，而通过仿真模型来收集数据，即可对实际系统进行性能、状态方面的分 析，从而对系统采用合适的控制调度方法。基于仿真的方法不单纯追求系统的数学描 述，尤其是离散系统仿真，侧重于对系统运行过程中逻辑关系的描述。仿真技术不仅 能对调度方案进行评价与选择，分析系统的动态性能，而且能够选择系统的结构参数。 现在已经有很多的仿真网格环境，很多的人采用仿真网格环境来测试自己的调度算法 5 浙江工业大学硕士学位论文 性能的好坏。 ( 3 ) 基于人工智能的方法：网格是一个复杂的、动态的、多边的网络环境，存在 很多的不定因素。如果将某些条件设定为已知或已确定是很不符合实际的。人工智能 的方法是一个很好的解决动态问题的方法，根据条件的改变而最优解也随之发生改 变当前已在调度中有所研究的的人工智能方法有神经网络、遗传算法、模拟退火法、 蚂蚁算法等。 ( 4 ) 组合算法：由于每一种调度方法都有各自的优缺点，将两种算法相结合取长 补短，是一种很好的思路，所以，除了传统的启发式规则外，近来人们开始把各种近 似算法的组合应用研究作为热点，各种各样的混合算法层出不穷 ( 5 ) 探索新的调度算法：针对于现有生产调度算法所存在的局限性，应与生物工 程及应用数学等交叉学科相结合，探索新的实用算法。 总之，对于调度问题的研究，随着应用数学理论进一步的发展，必然朝着集成化、 动态实用化、多目标化、高度次优化方向深入 1 3 网格服务质量研究现状 1 3 1 现有的主要的网格0 0 $ 体系结构 ( 1 ) g l o b u s 预留与分配体系结构( g a r a ) t z o ：g l o b u s 预留与分配体系结构 g a r a ( g l o b u sa r c h i t e c t u r ef o r r e s e z v a t i o ha n d a l l o c a t i o n ) 是i a a f o s t e r 等人提出的网格 q o s 体系结构。g a r a 是个分层的结构，由各级应用编程接口a p i 、g l o b u s 网格安全体 系框架( g s i ) 和各种资源管理器r m 组成，通过统一的接口，对不同类型的网格资源执 行提前和立即预留、控制和监视的操作，保证端到端q o s 。 ( 2 ) 网格q o s 管理体系结构( g q o s v o 口l 】：开放网格服务体系结构o g s a ( o p e n g r i ds 6 a v i c ea r c h i t e c t u r e ) 是继五层沙漏结构之后新的网格体系结构，网格q o s 管理体 系结构( g - q o s m ，g r i dq o sm a n a g e m e n ta r c h i t e c t u r e ) 是英国c a r d i f 移( 学r a s h i da 1 - a i i 等人提出的o g s a 环境下进行资源预留和自适应调节的q o s 管理体系结构。它提供三 个主要功能；基于q o s 属性的服务发现：建立服务等协议( s l a ，s e r v i c el e v e l a g r e e m e n t ) ，在中间件层和网络层提供q o s 保证机制；为分配的资源提供自适应调节。 浙江工业大学硕士学位论文 1 3 2 网格o o s 层次结构模型 q o s 对不同的对象可以有不同的描述，q o s 参数在不同的层次上表现为不同的组 成单元。所以，对所考虑的q o s 参数一定要指明其所处的层次圈脚1 。图1 n n 格q o s 的层次结构模型，虚拟组织层v o ( 最中间的一层) ，是网格特性得以体现的关键，根据 q o s 参数所表达的q o s 特性的不同，在v o 层将网格q o s 参数分成了逻辑资源类、系统 类、安全类、信任类、和记账类5 种类型。v o 层的q o s 分类如图3 1 所示a 图1 1 网格q o s , 层次模型 2 2 1 ( 1 ) 应用网格服务层：网格应用通过访问合适的网格资源来达到预定水平的 q o s 。它们不关心如何达到预定水平的q o s ，也不关心在达到这一水平的过程中其他 应用的情况。对于网格应用是由子服务工作流组成的情况，服务提供者在确定网格应 用的q o s 参数时，需要从各子服务相关参数定义的语义出发进行统一抽象，确保高层 服务能够获得一致的服务质量。因此，应用层需要抽象出网格应用的模型，以表达网 格应用的结构及其分配资源的最小单元。另外，应用层利用服务质量曲线将q o s 参数 与用户满意度相关联，以描述资源提供者的q o s 水平，它是v o 层q o s 测量的依据。 ( 2 ) 虚拟组织层( v o 层) ：中间层是承上启下的v o 层。v o 层将用户提出的q o s 需求映射到某一类的网格q o s ，并将物理层中相似的q o s 参数整合为一类，这样，v o 层不仅屏蔽了物理资源的异构性，还降低了物理层q o s 的复杂性。为此，我们对v o 层网格o o s 的分类进行了研究。由于v o 是连接网格服务和物理资源的纽带，是网格 特性得以体现的关键，因此，从v o 层对网格q o s 参数进行分类，一方面可以很详细 地表达网格q o s 参数的特性，另一方面可以很方便地将v o 层的q o s 参数分别映射转换 成网格应用层和物理资源的q o s 参数。 根据q o s 参数所表达的q o s 特性的不同，我们在v o 层将网格q o s 参数分成了逻辑 7 浙江工业大学硕士学位论文 资源类、系统类、安全类、信任类和记账类5 种类型。 逻辑资源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 应当是一个多维向量，分量可以包括：数据的保密性级 别数据的完整性级别用户身份的合理性以及用户权限的级别等。 信任o o s ：为了保证网格用户的q o s 需要，要求虚拟组织中网格服务的信息是 准确可靠的，但由于网络性能和网格资源的动态变化以及可能存在的少数服务提供者 故意虚报信息的情况，使得虚拟组织中由服务提供者提供的信息与实际信息有一定的 偏差。偏差的大小将直接影响网格服务的健壮性和对q o s 的保证能力，因此，需要对 服务提供者提供的信息进行可信性评价。 信任q o s 就是用来评价服务信息可信度的o o s 参数，它是由服务提供者和虚拟组 织共同提供和维护的。服务提供者可以根据那些不确定的动态因素对信息的可能偏差 作出估计，并依此向虚拟组织主动提供信任q o s 。为了防止用户故意虚报信任q o s 的 情况发生，虚拟组织需要对用户提供的信任q o s 进行评价并拥有最终的决定权和奖惩 措施，从而确保信任q o s 能够准确反映服务信息的真正可信程度。当然，虚拟组织也 8 浙江工业大学硕士学位论文 可以根据不同管理策略的需要，主动设置服务提供者的信任q o s ，并根据信任信息的 统计情况对信任q o s 进行修改。 记账q o s ：为了构建大规模的网格系统，就必须存在一种激励机制，以促进 资源提供者贡献自己的资源并从中获利。记账q o s 就是用来描述服务代价及其管理策 略方面的q o s 参数，它由服务提供者提供。当然，不同的服务提供者对服务代价的管 理策略不尽相同，如对不同类型的用户收取不同的费用对不同韵q o s 需求收取不同的 费用，对不同时间段提供的服务收取不同的费用等。网格用户在选择服务时也会考虑 到服务代价的问题，他们试图选择性能价格比最高的服务。所以，当构建大规模的网 格环境时，甚至当网格真正成为公共设施时，记账q o s 必将成为不可或缺的要素。图 3 - 2 是虚拟组织层网格q o s 参数的分类示意图。 l f 防螂 p 臣 图1 - 2 虚拟组织层q 1 0 s 分类田j 吲 在这5 种类型的q o s 参数里，逻辑资源q o s 和系统q o s 对网格服务的服务能力产生 决定性的影响，因此，我们又把这两种类型的q o s 参数称为功能性q o s 参数。而安全 q o s 信任q o s 和记账q o s 这3 种类型的q o s 参数都属于网格服务属性方面的q o s ，它们 对网格服务的服务能力没有产生决定性的影响，只是向用户提供一些必须的q o s 信 息，用户也没有办法决定这些q o s 参数的具体值，因此，我们又将这3 种类型的q o s 参数称为描述性q o s 参数。 ( 3 ) 资源设备层：最底层为资源设备层。该层捕获各个物理资源的q o s 属性以支 撑虚拟组织层的各类q o s 。逻辑资源的服务性能是随着对应物理资源的本地任务负载 情况的变化而动态变化的，但物理资源本身的整体服务性能是相对稳定的。因此，物 理资源的q o s 特性并不能直接代表v o 中逻辑资源的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 0 s 被映射到信任信息统计模块，记账q o s 被映射到本地 9 浙江工业大学硕士学位论文 记账模块。 由于物理资源对网格用户是透明的，用户只能在应用层网格服务层或者虚拟组 织层提妇q o s 需求。在层次结构模型中，我们用虚线表示用户可以根据自己的需要选 择在不同的层次上提出q o s 需求。其中：在应用层网格服务层，用户在功能性q o s 方 面可以提出简略的q o s 请求；而在虚拟组织层，用户只能提出具体的q o s 参数请求 1 4 研究意义 网格是未来i n t e r n e t 的发展方向，也就是说，网格会成为未来的网络基础设施， 几乎所有的应用都将基于网格，其巨大的应用前景使得许多国家和地区纷纷设立网格 的研究项目，对网格进行研究。在网格系统中，它的一块核心部分就是网格任务调度， 调度本身是个n p 难问题，又加之网格的动态性、分布性、异构性和自治性，使得网 格下的任务调度更加复杂。人们对网格任务调度的研究从未间断过，大量的研究成果 对网格的进一步发展做出了十分巨大的贡献。从网格的定义可知，“提供非凡的服务 质量”是判断网格的三个准则之一，服务质量q o s 成为网格系统的一个重要的性能 指标，目前网格q o s 的研究还属于一个前言性的研究。将网格的核心问题综合起来 就是要求网格系统要在拥有最好最合理的资源分配方式和资源调度策略的同时还要 保证服务质量。因此，如何提高网格系统中的调度算法的性能，如何保证网格任务调 度过程中的服务质量都是网格发展道路上需要解决的关键问题。本文对基于q o s 的 网格任务调度模型与算法的研究正是为解决一个关键问题而开展的。文中所得出仿真 结果、实验分析及引入的新的数学理论知识，都可作为以后网格的继续研究的参考依 据和理论基础，具有十分重要的意义。 1 5 研究内容 本文旨在对网格的关键技术任务调度算法进行深入的研究，同时考虑到在真实的 网格环境中，用户对网格任务调度有了更高的服务质量( q o s ) 需求，将q o s 需求作为 一个性能指标，因此在研究调度算法的设计实现过程中，不仅要考虑任务调度算法的 调度性能，还要考虑调度的结果是否满足用户的服务质量需求。在某些特定的网格环 境下，提出网格服务质量的测量模型，并在此基础上提出新的网格任务调度算法，并 对这些新的算法的性能做出比较和分析，因此，本论文的研究内容主要包括以下几点： 1 0 浙江工业大学硕士学位论文 ( 1 ) 基于信任驱动的网格任务调度研究 网格的提出是基于资源全面共享的思想，但由于在真实世界中存在着欺骗，人们 之间需要相互信任，在网格这个虚拟的世界中同样也是如此，如果网格中存在欺骗， 那么用户对这种共享的服务存在着安全性和可靠性上的怀疑，因此为使人们更放心的 使用网格中的广大资源，为使任务调度系统更好地在开放、异构和动态的真实网格环 境中有效运行，为使网格提供的服务质量满足用户需求，将研究出基于信任驱动的网 格任务调度算法。根据一种信任机制的计算模型，提出适应这个模型的网格任务调度 新算法，并对这些新算法的性能做出比较和分析。对增加调度的目标维数上也做了一 些研究，将传统的单目标任务调度改成满足多目标调度的任务调度算法，这样能更好 的从多方面、多角度来满足当前用户对网格环境的需求，并对这种多目标任务调度算 法与单目标任务调度算法的性能做出比较和分析。 ( 2 ) 基于证据推理的多q o s 约束的网格任务调度算法研究 在基于服务质量需求的网格任务调度算法中，提出一种有效的网格服务质量的测 量模型，良好正确的反映出用户的对服务质量的需求，是本文的另一个研究重点。引 入证据推理的e r 理论，来测量由于实际问题的复杂性和用户主观判断的不确定性， 用户对自己所得的主观判断信息常以模糊子集形式给出的对服务质量需求的数据，这 种模糊的信息就要求网格q o s 参数度量方法能够处理模糊不确定性信息，而正是在 这一点上，基于d s ( d e m p s t e r - s h a f e r ) 理论的e r ( 证据推理) 算法在处理模糊不确定性 信息问题上具有明显的优势，研究基于证据推理的网格服务质量测量模型，同时在此 模型之上，对传统的算法做出改进，对改进后的算法的性能与原有的算法做出比较， 分析比较结果。 ( 3 ) 基于a + b i 型联系数的不确定网格调度模型与优化研究 由于网格环境中存在大量的不确定因素，导致传统网格调度算法和调度系统 不能在开放、异构和动态的真实网格环境中有效运行。将新的数学理论集对分 析(