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

西南交通大学硕士研究生学位论文第页 摘要 网格计算是高性能计算的一种方式，是近年来兴起的热门信息技术之一，它结合了传统 的分布式计算，高性能计算等多种计算方式于一体。网格计算将网络上空余的多台计算机转 化为自己的工作站，并克服了异构环境下协调管理难以实现的问题，能有效地协同多个q o s 约束指标，并将计算任务分散到各个工作站并发执行完成计算任务。网格计算有效地解决了 在较短时问内计算运算量庞大的计算任务，如天气预报、地震预测、导弹运行轨迹、卫星发 射等大规模计算任务。 在网格计算的众多研究热点中，任务调度算法显得格外的重要。网格计算环境从本质上 讲是构建在多个工作站上的虚拟计算网络，不同的工作站具备自己各方面的特性，如不同的 操作系统，不同的运算处理能力，不同的网络环境等。在这样的异构环境中设计出一套适合 的任务调度算法不是一件容易的事情，因此良好的任务调度算法设计将在很大程度上决定了 网格计算任务的优良表现。研究表明网格计算任务调度算法属丁n p h a r d 问题，针对此类问 题难以得到最优解，甚至根本就不存在最优解的特点。本文研究了在网格计算任务调度中如 何寻找任务调度的满意解。 本文综述了网格计算任务调度算法和满意优化的发展现状，深入地研究了多q o s 约束满 意优化问题，提出一种针对网格计算任务调度算法的多q o s 约束满意优化模型。将该模型作 为优化方案的评价体系，分别采用m i n - m i n 算法，m a x m i n 算法和遗传算法作为寻优方法来 找寻潜在的优化方案，将这二者统一在一起形成了完整的多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 约束 西南交通大学硕士研究生学位论文第1 i i 页 ab s t r a c t i nr e c e n ty e a r s ，g r i dc o m p u t i n gh a sb e c o m eo n eo ft h em o s tp o p u l a rt e c h n o l o g i e so fi n t e r n e t g r i dc o m p u t i n gi so n eo ft h eh i g hp e r f o r m a n c ec o m p u t i n gw h i c hc o m b i t e st h ed i s t r i b u t e d c o m p u t i n ga n dt h et r a d i 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 i tc a l lc o n q u e rt h ed i f f i c u l t y o f m a n a g e m e n tu n d e r t h eh e t e r o g e n e o u se n v i r o n m e n t ，a n dc o l l a b o r a t em u l t i p l eq o s ( q u a l i t yo fs e r v i c e ) c o n s t r a i n s g r i dc o m p u t i n gt a k e st h ea d v a n t a g eo fm a n yi d l ec o m p u t e r sa si t so w nr e s o u r c e sa n d u s e st h e mt oc o m p u t es o m el a r g e - s c a l et a s kl i k ep r e d i c t i o nt h ew e a t h e r , p r e d i c t i o nt h et r a c ko f m i s s i l e e t ce f f i c i e n t l y a m o u n tt h em o s th o t e s tp o i n tr e s e a r c h e so fg r i dc o m p u t i n gr e s e a r c ha r e a , t a s ks c h e d u l i n g a l g o r i t h m si sv e r yi m p o r t a n t t h eq u a l i t yo ft a s ks c h e d u l i n ga l g o r i t h m sd e t e r m i n e st h eq u a l i t yo ft h e w h o l eg r i dc o m p u t i n ge n v i r o n m e n tb e c a u s et h e r ea r es om a n yd i f f e r e n tt r a i t sa m o n gw o r k s t a t i o n s ， n a m e l yp e r f o r m a n c e ，o p e r a t i o ns y s t e m , e n v i r o n m e n t e t c , s od e s i g nag o o da l g o r i t h m st os o l v et h e a b o v eq u e s t i o ni st h ep r i m a r yt a s k r e s e a r c hr e s u l t ss h o wt h a tt a s ks c h e d u l i n ga l g o r i t h mi san p - h a r d q u e s t i o n i t sh a r dt og e tt h e b e s ts o l u t i o nt ot h i sk i n do fp r o b l e m , e v e nt h e r ei s n tt h eb e s ts o l u t i o nt ot h e m s of i n d i n gt h e s a t i f r a c t i o ns o l u t i o ni n s t e a do f t h eb e s to n ei st h em a i nt a s kw h a tt h i st h e s i sf o c u s e so n t h i st h e s i sd e s c r i b l e st h ed e v e l o p m e n to ft h eg r i dc o m p u t i n ga n dr e s e a r c h e st h ep r o b l e mo f m u r i p l eq o sc o n s t r a i ni nt h et a s ks c h e d u l i n ge n v i r o n m e n td e e p l y at a s ks c h e d u l i n gm o d e lu n d e r m u l t i p l eq o sc o n s t r a i nw i t hu s e rs a t i s f a c t i o ni nt h eg r i dc o m p u t i n ge n v i r o n m e n ti sd e s i g n e d t h ef i r s tt a s ki sp u t t i n gt h i sm o d e li n t om a x - m i n , a n dm i n - m i na l g o r i t h m s t h i st h e s i sp r o p o s e s am e t h o du s i n gt h ea b s o l u t en u m b e ro ft h em a r g i nb e t w e e nt h ep r e d i c t e ds a t i s f a c t i o nv a l u ea n dt h e u s e r ss a t i s f a c t i o nv a l u ei n s t e a do ft h em i n i u mm a k e s p a no rm a x i u mm a k e s p a n t h e na n a l y z ef o r t h er e s u l to ft h ee x p e r i m e n ta n dc o m p a r et h ed e f f e r e n c eb e t w e e nt h em o d e lh a sp r o p o s e di nt h i s t h e s i sa n dt r a d i t i o n a lm a x m i na n dm i n m i na l g o r i t h m si sp e r f o r m e d t h es e c o n dt a s ki st h e i m p l e m e n tm q o s g aw h i c hc o n t a i n st h i sm o d e la n db a s e do nt r a d i t i o n a lg e n e t i ca l g o r i t h m s t h e f i n a lt a s ki sa n a l y z i n gt h er e s u l tb e t w e e nd i f f e r e n ti n i t i a ln o o fp o p u l a t i o n t h e r ea r es om a n yq o sc o n s t r a i ns p e c i f i c a t i o n si nt h eg r i dc o m p u t i n ge n v i r o n m e n t ，b u tt h e a u t h o rt a k e st h em a k e s p a n , p r i o r i t ya n dc r e d f fa st h em o s ti m p o r t a n ts p e c i f i c a t i o n sa n du s e st h e ma s t h em u l t i p l eq o sc o n s t r a i n g i v i n gt h es a t i s f a c t i o nf u n c t i o ni sa s s i g n e dt oe a c hi n d e xa n da s y n t h e s i c a ls a t i s f i c a t i o nf u n c t i o ni sc o n s t r u c t e da c c o r d i n gt ot h e s ei n d e x a n dt h e nt h et a s k s c h e d u l i n ga l g o r i t h mi sd e s i g n e da n di m p l e m e n t e db a s e do ns a t i s f i c a t i o no p t i m i z a t i o nm o d e l 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 i sa l g o r i t h mc a nc o l l a b o r a t em u l t i p l eq o sc o n s t r a i n e f f i c i e n t l ya n dt a k et h ea d v a n t a g eo fg e n e t i ca l g o r i t h m st os o l v em u l t i p l et a r g e to p t i m i z a t i o n p r o b l e mu n d e rt h er e q u i r e m e n t & u s e r ss a t i s f a c t i o n 西南交通大学硕士研究生学位论文 第1 v 页 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 ，s a t i s f a c t o r yo p t i m i z a t i o n , g e n e t i ca l g o r i t h m , m u l t i p l eq o s c o n s t r a i n s 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大 学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密回，使用木授权书。 ( 请在以上方框内打“4 ”) 学位论文作者签名：奄眠诲 日期：2 0 f t7 指导老师签名： 日期 谭觏呜 函1 呼悯- 国 西南交通大学硕士研究生学位论文第1 页 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 在m i l l m i l l 和m a x m i n 算法中提出了用预测满意度值与期望满意度值之差的绝对值 替代完成时间( m a k e s p a n ) 的方法，使得基于多q o s 约束满意度评价可以基于传统启发式算法 来实现。 ( 2 ) 在任务执行时间满意度函数中融入了计算任务规模的概念。由于不同的工作站有不 同的计算处理能力，不同的计算任务又拥有不同的计算规模，而任务执行时间与计算任务的 规模和工作站的处理能力是密切相关的。所以作者认为不能孤立地只把任务运作时间作为时 间满意度函数的全部，而应该考虑当前工作站的处理能力和计算任务的规模大小。 ( 3 ) 传统的优先级是指一个任务是否能被优先执行，或者说它的优先执行性能够有多高。 然而这种概念是基于单机环境的。在网格计算中我们所面向的是工作群。本文提出了一种新 的测量优先级的方法。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除 文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成 果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。本人完全了解违反上 述声明所引起的一切法律责任将由本人承担。 学位论文作者签名：商睨歼 日期：文，p 多夫t 西南交通大学硕士研究生学位论文第1 页 1 1 课题背景 第1 章绪论 伴随着科学技术的迅速发展，越来越多的科学探索不断涌现。相应的科学计算对计算机的 处理能力要求也越来越高。如地震预测，天气预报，导弹运行轨迹，卫星发射轨迹等计算任 务均包含了非常庞大的计算量，在当前单个计算机计算能力有限的现实情况下，难以在规定 时问内完成大规模的计算任务。以此同时伴随着信息技术的不断发展，特别是互联网运用的 口益普及，使得人类的生活方式发生了前所未有的巨大转变。根据统计，早在2 0 0 0 年互联网 就已经连接了1 0 0 万个网络，l 亿台计算机，拥有1 0 亿个用户，近几年这个数字还在飞速增 长。为了在互联网上寻找一种廉价的而数据处理运算能力强的计算模式，网格计算( g r i d c o m p u t i n g ) l 2 i 这一概念因此而诞生。 1 1 1 网格计算 网格计算是一种专门针对复杂科学计算的新型计算方法。它是将分散在不同地理位置上空 闲的计算机组合起来，形成一个虚拟的，庞大的，拥有超强计算能力的计算机网络系统。单 个计笄机是这个系统的一个工作站，成千上万的工作站形成一张“网，网格计算也因此而得 名。按照这种模式组建的虚拟“超级计算机 在两方面具备自己的优势：( 一) ，数据处理运 算能力较强；( 二) ，网络卜所有的工作站的利用率得到了极大地提高。 网格计算的应用实际上是互联网应用的又次新突破，这一次突破使得各个计算机实现了 不仪被其它计算机所服务，同时也服务于其它计算机。对整个巨联网应用来说足一次历史性 的转折，它使得整个互联网拥有了协同计算的处理能力。 网格计算的关键技术主要包括了以下几个方面： ( 1 ) 网格计算工作站：即计算资源的提供者，如服务器，集群系统，大规模存储系统等， 这些物力资源可以分布在世界各地。 ( 2 ) i p 网络系统：需要将各个资源有效地组合在一起，适当的网络连接是必不可少的。 由于网格计算任务町能有较大的数据量，所以网络传输质昂的保障也是非常有必要的。 ( 3 ) 工作站管理和任务调度算法：工作站管理主要负责保存，组织计算资源的相关信息； 任务调度算法决定了网格计算任务的分配，以求做到负载均衡。 ( 4 ) 监测工具：由于计算资源的分布性，难以做到单一的集中管理。所以需要可靠的， 多级的监测t 具负责监测自己所管辖范围内，各计算资源的运作情况。 西南交通大学硕士研究生学位论文第2 页 1 1 2 网格计算中的任务调度算法 任务调度算法从一个工作站的单机操作系统到分布式计算，再到网格计算都无处不再，并 且都占据了核心应用的地位。任务调度算法的优劣性直接决定了系统的运行处理效率。 网格计算任务调度算法是将用户所提交的任务，分配到恰到的资源上，并协调仟务在该资 源上的处理过程。在调度的过程中需要考虑如何才能最大化提高系统的吞吐量。具体的指标 主要包括：完成时间( m a k e s p a n ) ，负载均衡( l o a db a l a n c i n g ) ，优先级( p r i o r i t y ) ，信任度( c r e d i o 等因素。网格计算中的工作站管理是网格计算的核心部分，是连接各个工作站的核心基础部 分。在网格计算中，对任务的调度管理是工作站管理的核心内容。与传统的机群任务调度不 同，网格计算的任务调度算法需要面对如下问题： ( 1 ) 网格计算环境中存在分布性与异构性：网络上的各个工作站都属于网格计算中的资 源，并且各个资源分布在不同的地理位置，也存在于不同的网络环境中，拥有各自不同的操 作系统。 ( 2 ) 网格计算环境具有资源的伸缩性：网格计算环境的工作站管理是灵活的，各个工作 站可以在任意时刻动态的加入资源集合，也+ 町以在任意时刻离开资源集合。工作站管理系统 必须及时更新当前的资源集合。以此保证任务调度算法的可靠性。 ( 3 ) 为用户提供q o s ( q u a l i t yo f s e r v i c e ) 服务：当前的网格计算中，用户对自己所提交到 网格计算环境的任务会提出各自的个性化需求，向用户提供o o s 服务是必要的。网格计算环 境中的q o s 有一系列指标，包括了：响应时间，完成时间，优先级，信任度，吞吐量等，以 多元化的q o s 约束设置以满足复杂的用户需求。将q o s 引入网格计算中，使得任务调度系统 能够最大化的满足用户的需求。当前以q o s 约束指导网格计算任务调度算法成为了一个研究 热点。 1 2 国内外研究现状 1 2 1 网格计算任务调度算法研究现状 从本质上说网格计算任务调度算法是一个优化算法，网格环境中的资源是有限的，而用户 所提交的任务是无限的。研究表明网格计算中的任务调度算法属于n p h a r d 问题1 3 l ，对于 n p h a r d 问题到口前为止还没有一个算法能够解决其最优化问题，也冈此受到广大学者的关 注。 就网格计算任务调度算法的研究历程来说可以分为两个主要阶段，第阶段，研究者主要 关注在网格计算中不同的工作站的异构性问题；第二阶段，研究者主要关注在服务质量上， 这一阶段又分为两个小的阶段。早期研究者主要关注在单一的q o s 约束指标上进行调度算法 西南交通大学硕士研究生学位论文第3 页 的优化研究；后期则融入了多个q o s 约束指标。 第阶段的代表算法丰要有以下几种： m c t 4 1 ( m i n i m u mc o m p l e t i o nt i m e ) 算法来源于s m a r t n e t 中的启发式算法，该算法以仟务 的最早完成时间作为判定的标准进行仟务调度，可以保证多处理机之间的负载均衡，但是网 格计算任务的实际执行时间并非最优。 m e t l 4 1 ( m i n i m u me x e c u t i o nt i m e ) 算法以任务的最少执行时间为判定的标准进行任务调 度，该算法会导致大量的任务集中到某些计算处理能力较高的工作站上，使得其它工作站空 闲，造成系统的负载不均衡。 o l b l 4 1 ( 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 a x m i n l 5 l 算法是m c t 的改进算法。该算法优先选择最早完成时间最人的任务进行调度。 在短任务较多、大计算量任务较少的情况下，可以使计算量较大的任务优先被调度，使之与 多个计算量较小的任务并行执行，从而达到较好的性能。 m i n m i n l 6 1 算法也是m c t 的改进算法。该算法优先选取最早完成时间最小的任务进行调 度。在同类算法中，m i n - m i n 算法具有较好的性能，一般用作为调度算法的评测基准。 第二阶段的算法主要是在第。阶段的算法的基础上融入了单q o s 约束指标或者多个 q o s 约束指标。 文献 7 】提出了一个基于单q o s 约束的m i n m i n 启发式任务调度算法，该算法采用了一个 简单的q o s 模型：所有的任务只有高、低两种q o s 需求，通过优先调度具有高q o s 需求的任 务来满足用户的需求。这种过于简单的模型使得这一算法的应用效果不佳。 文献 8 】将仟务的响应率( r e s p o n s er a t i o ) 作为q o s ，基于s u f f e r a g e 算法的思想提出了 q s u f f e r a g e ；b r a u n 等人采用具有依赖关系、优先级、最迟完成时间和多种版本的q o s 约束任 务模型，并通过实验比较了m i n m i n ，g a 和g e n i t o r - s t y l eg a 等调度算法 9 1 ，并验证了 g e n i t o r s t y l eg a 能够获得最好的效果，时间开销最小的m i n m i n 算法也获得了比较好的结 果。 文献【1 0 】同时从用户和系统的角度定义了基于q o s 的任务调度，提出了q s m t s _ i p ，根据 用户提出的各种q o s 约束进行调度，最大化各个q o s 维度卜的效益函数，从而满足用户的 q o s 约束。 综上所述，第二阶段的现有研究算泫主要存在以下几方面的缺陷： ( 1 ) 引入单一的q o s 约束，此类算法由于只考虑了单一的q o s 约束，只追求某一个q o s 约束指标的最大化，缺忽略了其它q o s 约束指标。因此有可能造成运行效率不能达到预期效 果。 ( 2 ) 引入单一的q o s 约束，此类算法企图寻找最优解，但是对于n p h a r d 问题，很难找 西南交通大学硕士研究生学位论文第4 页 到最优解，甚至没有最优解。 ( 3 ) 现有的引入多维q o s 约束指标的算法，往往是将多个约束模型通过简单的加权组合 在一起，此类方法灵活性差，不能适应复杂多变的用户需求。 1 2 2 满意优化理论研究现状 1 9 7 8 年，诺贝尔经济学奖获得者h t a s i m o n 在经济组织实际决策的研究中，首先提出了 “令人满意准则”的概念来代替微观经济学的最大化原则，并同时提出了用满意决策代替最 优决策的思想i l 。他举出一个例子来阐述满意解的优越性：假如您想要在地里摘取一个乐米。 想要找到一个最大的乐米是非常困难的，您需要把地里所有的乐米都进行测量一次，再通过 比较才能确定。并且，这个问题的工作量和玉米地的玉米产量成正比，产量越人，工作越困 难。但是，如果要求找到的不是最大的那一个玉米，而是一个比较大的，即按通常的说法， 到地里去摘一个大玉米，6 i j 题就简单多了。这时产量的多少和工作量基本无关。满意准则的 提出把人们从纯理性思维的研究方式带到一个有限理性的状态，为今后的科学研究提供了新 的研究方法。 任平教授首先利用了模糊数学里面的相关知识，将满意解的解集定义为某一论域在一定的 约束条件构成的子集的限制下所形成的截集。提出了采用模糊集合论的方法来研究满意解集 0 2 1 o 上世纪9 0 年代，靳蕃教授通过比较冯若依曼计算机与人脑的结构特点，运转机制后发现， 人脑之所以在高级信息处理方面远胜过电脑，主要有两个因素：( 1 ) 人脑的巨型并行分布结 构；( 2 ) 人脑遵循寻求满意解的运算法则。由此，靳蕃教授提出了“神经计算的满意解原理 1 1 3 1o 金炜东教授研究了评价满意解性能的满意度函数，针对复杂问题提出了“多目标满意优化 模型和“局部一全局型满意优化模型，并将它们用于列车操纵优化方法研究中f 1 4 l 。姚新胜 将满意优化用于机械的优化设计中，取得了良好的效果1 1 5 】。 寻求满意解的满意优化方法之所以可以得到迅速发展，主要是因为它具有以下几方面特 点： ( 1 ) 满意优化方法具有人类智能信息处理方式的基本特征之一，即在巨大的搜索空间中 迅速地找到满意解的能力。 ( 2 ) 传统优化方法采用描述问题的数学模型。因为模型本身是实际问题的简化，或多或 少忽略了一些因素。另外，数据采集的不精确以及参数估计的不准确都可能导致得到的“最 优解一比采用满意优化方法得到的满意解产牛的误差更大。 ( 3 ) 对于一些计算复杂程度较大的优化问题，现在并未找到行之有效的最优化方法，但 是采用某种按满意解原则所设计的满意优化方法却能得到满意的优化效果。 西南交通大学硕士研究生学位论文第5 页 1 艺：3 现有研究工作存在的问题 任务调度是网格计算的基木功能，它面临的问题是一个n p h a r d 问题。到日前为止，很多 学者提出了许多网格计算系统的调度技术和算法。但是，不少调度算法还没有完整的理论依 据、一些调度技术的结论仅仅是来自仿真结果，至今还没有形成网格计算的任务调度理论。 所以，该领域的研究还有待进一步发展和完善。具体地说，网格任务调度研究还需要做的工 作包括： ( 1 ) 针对1 2 1 节所提到的现有算法的f ：足之处，将q o s 约束指标与用户的需求相结合， 形成用户满意度指导的多q o s 约束指标任务调度算法。 ( 2 ) 启发性智能化方法将足刚格计算任务调度的一个重要研究领域。将遗传算法引入到 网格汁算任务调度算法中，必定会为算法带来巨大的优化效果。 ( 3 ) 面向a g e n t 技术将是网格计算及其任务调度的一个重要的软件开发方法i ”i ，在该领 域同样还有很多工作要做。 1 3 本文主要研究内容 本文主要是针对上述现有研究工作存在的问题而开展的，主要研究工作包括： ( 1 ) 研究现有网格计算任务调度算法，分析其不足之处，并进行相应的改进，以提高效 率。 ( 2 ) 选取了运行时间、优先级、信任度作为主要指标进行网格计算任务调度算法的多q o s 约束满意优化。对每一维的q o s 约束指标通过研究给出满意度函数，并最终将各满意度函数 相结合得到网格计算任务调度算法模型，通过该模型得到任务的综合满意度。结合任务发起 者预先指定的满意度要求，确定网格计算任务的调度方案。 ( 3 ) 将得到的数学模型引入m i n m i n 算法，m a x m i n 算法求解，并运用用户满意度值与 综合满意度函数计算值之差的绝对值替换传统的m i n m i n ，m a x - m i n 中运用运行时间求解的方 式。 ( 4 ) 运用遗传算法求解e 述模型，设汁染色体编码方案、初始化种群生成方法以及选择、 交叉和变异等遗传算子。 ( 5 ) 完成了大量的仿真实验，并对仿真结果进行分析。 根据以上研究工作并与之相呼应，本论文分为5 章： 第l 章为绪论，简要介绍了网格计算和网格计算中的任务调度算法的研究现状，阐明r 厂目 前的网格计算任务调度算法存在的1 i 足。随后对满意优化的概念做+ j ，简要说明，并介绍丫满 意优化理论的发展现状。 第2 章给出了所研究的问题的定义，以及所选取的q o s 约束指标的定义。简要地介绍了 西南交通大学硕士研究生学位论文第6 页 满意优化理论，给出了满意度与满意解的定义，介绍了几种常用的满意度函数的形式。同时， 介绍了满意优化问题的求解步骤，最后提出了多目标满意优化的问题以及数学模型的一般形 式。 第3 章通过研究对三个q o s 约束指标进行建模，并给出了各自的基于满意度函数的模型。 结合满意优化理论得到基丁多q o s 约束的网格计算任务调度算法满意优化模型。 第4 章研究了以满意优化理论为指导的多q o s 约束启发式任务调度算法。根据前面所得 到的任务调度模犁修改最为经典的两个常见算法，即m i n m i n 和m a x m i n 算法。新得到的算 法定义为m q o s m i n - m i n 和m q o s m a x - m i n ，并提出了用用户期望满意度与预测满意度之差 的绝对值来替换传统的预测执行时间的方式来指导m i n m i n 和m a x m i n 算法的选取任务并分 配任务的过程，并根据仿真结果分析算法优劣性及其取得的效果。 第5 章研究基于多目标组合满意优化方法的调度算法。基于遗传算法，结合网格计算任务 调度问题的特点，设计染色体编码方案、初始种群生成方法以及选择、交叉和变异等遗传算 子，提出了基于多目标组合满意优化方法的调度算法m q o s g a 。并根据仿真结果分析算法优 劣性及其取得的效果。 西南交通大学硕士研究生学位论文第7 页 2 1 问题的定义 第2 章问题定义与满意优化方法 网格计算任务调度模型根据其调度的方式可以划分为两个大类，第一类为在线模式 ( o n l i n em o d e ) ，即每当有一个新的计算任务到达时，立刻根据该任务的自身特性，以及用户 的要求，在网格计算资源巾为其寻找一个适当的资源，进行调度。第二类为批处理模式( b a t c h m o d e ) ，即当多个网格计算任务到达后，根据其各个任务自身的特性和用户的需求，一次性对 多个任务进行调度分配，且批与批之间存在一定的问隔时问。由于批处理模式可以获得更多 的处理信息，更好地对任务调度分配进行决策分析，更加有利于我们的理论研究，所以本文 主要研究的是批处理模式下的网格计算任务调度模型。 针对批处理模式下的网格计算任务调度可以做以下定义： n 个需要被调度的计算任务将要分别分配到m 个可用的工作站或主机群中。由于数据的传 输量与任务的计算规模成正比，而本文所提出的模型在很大程度上，密切关注计算量，所以 数据的传输时间町以忽略不计，而改在模犁中体现。在此网格计算环境下将n 个任务 t = 五，兄，丐，r 4 ，巧，乙 以达到用户满意的方式分配到m 个主机日= 何1 ，日2 ，h 3 ，h 4 ，日”，h 用 上 去执行计算任务，调度目标是尽可能地达到用户满意度。 针对全体工作站资源集合，需要划分为子集合，其子集合为域，即网格计算环境中把所有 的工作站资源归属到不同的域中，域与域之问相互关联。其物理结构如图2 1 所示。 用户对所调度任务的各项指标也具备相应的要求： ( 1 ) 设用户对任务7 ：的完成时间满意值为u 写e r l n p u t t i m e ( i ) ( 2 ) 设用户对任务z 的优先级满意值为u s e r l n p u t p r ，d ( f ) ( 3 ) 设用户对任务z 的信任度满意值为u s e r l n p u t c r e d i t ( i ) 由于不同的用户，不同的任务对不同的指标有不同的重要程度，所以对各个满意度值应该 存在一定的加权等级。设置其加权为w t ，w t ，w t ，且w t ，+ w t ，+ w t 3 = 1 。 本论文的研究工作所要解决的问题即：在此异构的网络环境中，将用户所提交的任务，最 大限度的达到用户所提出的满意度。 2 2q o s 约束指标 通过对网格计算中的任务调度算法的特性进行研究发现，在众多的q o s 约束指标，如运 行时问( m a k e s p a n ) 、负载均衡( l o a db a l a n c i n g ) 、信任度( c r e d i t ) 、优先级( p r i o 嘶) 中，有三 西南交通大学硕士研究生学位论文第8 页 罅骠取“ 耐 喇譬 繁。墨。匣驿 譬。黔曼：馨 。譬警 i 图2 - i 嘲格计算环境物理结构圈 个指标对于叫格计算任务调度算法魁争笑重型f j ，即任务的执行时f h j 、任务的优先缎、对所 分配资源的信任度。本文将此二三个度量标准作为调度算法研究的约束指标并展开研究。帽对 而占，如负载均衡( l o a db a l a n c i n g ) n 可通i = 上完成时问f m a k e s p a n ) 和优先级( p r i o r i t y ) 得到体现。 阑为完成时间决定了在不考虑任务处于队列排队的情况下的运算时问，而优先级则融入了等 待时间的概念。这两个指标同时考虑进入后，必然不会使得某些工作站长期高运转负荷，而 部分工作站缺闲置。因晰造成严重的负载1 i 均衡。 221 运行时间 网格计算任务的运行时问0 0 s 约束包括厂如下几个参数： ( 1 ) 可以接受的最k 任务执行时间n m q 删。 现实牛活中有非常多的仆务对时效忡足存在要求的，其它的仆务虽然没有严格的物理意 义使得它必须在多长时问内汁算完毕，但是实际上我们是不可能无休【l 地等待的，对每一个 任务虑该有个人概的标准，表明此计算仟务船长许可的远行时间。此参数由任务的提交肯 指定。 ( 2 ) 预测的任务执行时问n m r 啪， 由1 ：网格计算环境存在异构性，小刚的工作站之间有荇不同的处理能力，在某个任务分 配到某个工作站执行完毕以前，我们无法得到准确的运行时间，只能通过数学方法进行预测。 为，预测任务的执行时问，本文结合了l i n g u og o n e 枷，嵌静波1 2 , 1 等人提出的方法进行预测。 ( 3 ) 仟务蛀快完成时问7 抽p 州，) 假设任务的执 r 时问低于某一个值，我们使认为该任务的运f i i t f ir l ，已经最人限度的满 ) 西南交通大学硕士研究生学位论文第9 页 足了用户的需求，此数据由任务的提交者指定。 ( 4 ) 用户对时问的期望值u s e r l n p u t t i m e ( i ) 网格计算任务的提交者对其所提交的计算任务，必然存在一个期望值，该期望值表明了 用户对运行时间指标的要求。此参数由任务的提交者指定。 此外，由f 不同的计算任务存在不同的计算规模，同样不同的工作站也具备不同的运算 处理能力。所以不能简单地将某一个任务在某个工作站上的运行时间作为单一的时间效益评 判标准，还应该加上该任务的计算规模与所分配到的工作站的计算处理能力之间的天系作为 其时间效益的评判标准的一部分。 为此我们需要将以下几个参数融入到我们的研究范围： ( 1 ) 网格计算任务的计算规模t a s k s c a l e r e a i ( f ) 每一个计算任务均存在自己的计算规模，计算规模直接决定了任务的执行时间。此参数 由任务的提交者指定。 ( 2 ) 各个工作站资源的最大处理能力h o s t s c 砒妇枷 不同的工作站存在不同的计算处理能力，计算能力的强弱决定了网格计算任务的处理效 率。此参数由网格计算环境预先指定。 ( 3 ) 各个工作站资源的最小处理能力h o s t s c a l e n 任何一个工作站均可以空闲，不做任务处理，所以此参数约定为零。 2 2 2 任务优先级 不同的刚格计算任务具备不同的优先级，优先级的高低在单q o s 约束单工作站的环境下， 直接决定了该任务被调度的次序。然而在多q o s 约束多工作站的网格计算环境下，优先级的 概念完全有别于传统的单机环境下单约束条件的优先级。优先级作为我们的评判标准的一部 分，虽然不能如同在单q o s 约束单工作站环境下起到决定性的作用，但也能使得优先级高的 计算任务在一定程度上可以优先占用计算效率更高的网格计算工作站。 针对多q o s 约束，多工作站环境，对其优先级做以下定义： 在某一个工作站日。上存在一待执行任务队列q 。，q 。的单位为计算量，设置其计算量为 c o 。，r o c q 。朋缸( 线) 。同时可以得知当前任务队列中所分配的任务计算量总和必然小 于m a x ( q 。) ，由于任务执行的先后顺序是按照队列巾的顺序进行，所以网格计算任务在队列 中的序号是一个评价优先级的重要因素，但并不是绝对因素。由于同一台工作站上计算处理 能力恒定，所以其运算量所占队列区问的位置同样重要，有可能某任务所处序列号相对靠后， 但是先前任务计算量小，所以可能很快就会被调度；相反某一个网格计算任务在队列中所处 序列号靠前，但是先前任务计算量大，所以需要等待较长时间。由此可见计算任务的计算量 所占据区间的位置将决定其在某台工作站上的优先级。 本文对优先级的定义主要包括以下几个参数的定义： 西南交通大学硕士研究生学位论文第l o 页 ( 1 ) 网格计算任务的计算规模f 砸豇& 口如喇蛔) 每一个计算任务均存在自己的计算规模，计算规模直接决定丁任务的优先级。此参数由 任务的提交者指定。 ( 2 ) 单个工作站的任务队列中允许的最大处理规模胁，舭嵋。唰) 本论文研究环境设定每个工作站卜在队列中的待处理任务有最大的运算规模，如果某一个 任务的前面的任务的计算规模已经达到了最大计算规模，则该任务分配到此资源上的满意度 为零。 ( 3 ) 单个工作站的任务队列中允许的最小处理规模凰刎q ”p 比p 咧订 任何一个工作站均可以空闲，不做任务处理，所以此参数约定为零。 ( 4 ) 单个工作站的任务队列中的所有待执行任务的计算规模之和胁肋删删，) 此参数可以对所有队列中的单个任务的计算规模求和得到。 2 2 3 任务对资源的信任度 不同的网格计算工作站具备不同的信任度级别1 2 7 1 ，文献 2 8 提出同样不同的网格计算任 务也要求具备有相应的信任度的工作站执行。根据网格实体所属组织以及地理位置的不同， 我们把网格划分成若干个独立的管理域，每个管理域包含若干个网格实体，有自己的管理策 略、安全策略，域之间通过网络连接。通过把网格划分为不同的管理域，可以很容易地解决 可扩展性、站点的自治性以及异构性问题。 网格计算环境中不同的管理域可能采用不同的安全策略对域内各自所管辖的工作站资源 进行安伞管理，域之间很难建立一种伞局的管理策略。针对网格环境特点，根据实体所处管 理域的不同，将网格实体间的信任关系分为域间信任关系和域内信任关系。域内信任关系包 括实体间的相互评价和域管理者对域内实体的行为进行监控、评估。域间信任关系包括域间 直接评价和推荐信任关系的建立和修改。资源提供者可以根据域问信任关系和域内实体的信 誉度来确定两个实体之间的信任关系，从而接受或拒绝用户的申请。网格信任关系结构如图 2 2 所示。 每个管理域有+ 一个信任代理，它负责维护张域内实体信誉表和一张域间直接信任表， 记录和更新域内每个实体的信誉度以及所有与之有过直接交易的域的域间直接信任度。每个 实体有一张直接信任表，记录对与其交易过的实体的评价。 西南交通大学硕士研究生学位论文 第1 1 页 域内实体信 域间实体信 任表任表 tt ( = ! 竺 一一下一 管理域 实体实体 j r 严晶j r l 直擎l | 直警任i 2 3 满意优化方法 2 3 1 满意优化的基本概念 图2 - 2 网格信任关系 “在现实世界中，我们一般不能在满意解和最优解之间进行选择，因为我们只有有限种 寻找最优解的方法 n l 。研究表明，在许多决策过程中，无法找到其最优化的目标，或者难 以找到其最优化的解。 基于经典数学理论的优化理论得到了长期的系统的发展，并且形成了一套相对完善的理 论体系。最优准则，优化模型，优化算法分析是优化理论的核心。伴随着科学技术的发展和 人们对自然科学的认识的加深，人们发现传统的优化理论和优化技术对许多问题无能为力。 包括一些多目标优化问题、组合优化问题、离散优化