（计算机应用技术专业论文）网格模糊qos评价模型及应用研究.pdf

d i s s e r t a t i o ns u b m i t t e dt 0z h e j i a n gu n i v e 玮i 蚵o f 1 r e c h n o l o g y f o rt h ed e g r e eo fm a s t e r t h er e s e a r c ho ne v a l u a t i o nm o d e lo f g r mf u z z y q o s a n da p p l i c a t i o n c a n d i d a t e ：x u nz h i a d v i s o r ：p r o f e s s o rh u a n gd e c a i c o e g eo fc o m p u t e r s c i e n c ea n d1 b c h n o l o g y z h e j i a n gu n i v e r s i t yo f7 r e c h n o l o g y a p m 2 0 1 0 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究 工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其 他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其 它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名：日期：厶r 。年r 月- 多日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保秘 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 乒， 钎冬 气弋武 日期：加f 睥多弓日 日期：沙萨j 月眵 浙江工业大学硕士学位论文 网格模糊0 0 s 评价模型及应用研究 摘要 网格服务质量( q o s ) 是评价网格的三个基本准则之一，人们对网格q o s 的研究 一直没有间断，提出了网格q o s 协商管理系统以及分层的q o s 体系结构，但目前对 网格q o s 的测量与评价还没有较健全的方法，尤其对于q o s 存在不确定性的情况。 网格任务调度可以说是网格的核心工作，对它的研究渐渐走向成熟。人们不只提出基 于启发式的m i l l m i n 、负载均衡等的静态调度算法及在线模式和批模式的动态调度算 法，还提出用人工智能中的遗传算法、模拟退火算法等方法来处理任务调度。但是， 如何在任务调度中更好的保障网格服务质量，如何利用网格q o s 指导任务得到最好 的调度，仍然值得研究。 本文主要提出了三种网格q o s 评价模型，对传统的q o s 测量与评价做了改进： 1 、基于v a g u e 集的网格q o s 评价模型。用v a g u e 集描述用户q o s 模糊的表达 如“某数值左右 、“安全性较高 等，用证据理论e r 算法对其测量融合，将融合 后的综合q o s 加入到网格任务调度( 如经典的m i n m i l l 算法) 中，并对调度算法加 以改进，实验证明在v a g u e 集描述的q o s 指导下的网格任务调度新算法能在降低了 时间跨度的同时，更有效的利用网格资源。 2 、基于集对分析联系数的网格q o s 测量模型。用集对分析联系数处理网格q o s 属性中存在的不确定性，用联系数a + b i 中的b 来描述q o s 参数的浮动范围，并且利 用联系数的运算法则与全序关系来测量和评价网格q o s 的高低，最后将这种评价加 入到网格任务调度中，仿真实验表明，这种任务调度与实数形式描述的q o s 指导的 任务调度相比，在兼顾了调度时间跨度的同时，使资源与任务的匹配效用增加，提高 了资源的利用率，改善了网格资源“尽力而为之”的状况。 3 、网格混合多q o s 属性的评价模型。提出了实数、区间数与v a g u e 模糊表达同 时存在的网格q o s 体系结构，把各种网格参数都作为一个q o s 属性加入到体系中来， 包括逻辑参数、网络吞吐与时延、安全、信任、可用性、甚至执行时间和价格等。在 i 浙江工业大学硕士学位论文 此基础上利用e r 算法将各种q o s 进行综合测量和评价，并简要介绍了这种评价模型 在网格任务调度中的应用方向。 关键词：服务质量，调度算法，网格，e r ，联系数 浙江工业大学硕士学位论文 t h er e s e a r c ho ne v a l u a t i o nm o d e lo f g r i df u z z yq o sa n da p p l i c a t i o n a b s t r a c t q u a l 时o f s e n ，i c ei so n eo fm et l l r e eb 2 l s i cp r i l l c i p l e so f 酊d ，0 nw 1 1 i c ht 1 1 er e s e a r c h h a sn o tb e e ns t o p p e d 饼dq o sm a l l a g e m e n ta n dn e g o t i a t i o ns y s t e ma 1 1 dl a y e r e dq o s 蛐n l c t u r ew e r ep r e s e n t e d ，b u tt 1 1 e r eh a si l o tb e e nam a _ t u r em e t l l o df o rt l l ec o m p u t i n ga 1 1 d e v a 】u a t i o no f 酣dq o s ，e s p e c i a l l yf o rq o sw 曲p o t e n t i a lu i l c e n a i n 哆i na d d i t i o n ，鲥dt a s k s c h e d u l i n gi s t l l ek e yw o r ko f 面d ，a n dt h er e s e a r c ho ni ti ss t e p p i n gi n t 0m 删够n o t o n l yw e r e1 1 e 谢s t i cm i n m i i la l g o r i t l u na i l do p p o m l l l i s t i cl o a db a l a l l c i n ga 1 9 0 r i 如n ( o l b ) b a s e d 酣dt a s ks t a t i cs c h e d u l i n gp r o p o s e d ，b u t2 l l s om ed y n 锄i cs c h e d u l i n ga l g o n t l l m p r e s e n t e d ，i 1 1 c l u d i n go l l l i n em o d ea 1 1 db a t c hm o d e a l s ot h eg e n e t i ca l g o r i t l l m s ( g a ) a i l d s i m u l a t e da 彻e a l i n g ( s a ) a l g o r i t l l r nw e r eu t i l i z e dt 0p r o c e s s 面dt a s ks c h e d u l i n g b u th o w t ob e 钍e rg u a r a l l t e eq u a l i t ) ，o fs e r v i c ed u r i n gt a s ks c h e d u l i n ga i l dh o wt oe 街c i e n t l yg u i d e t a s ks c h e d u l i n g 诹m 酣dq o sa r es t i uo p e nt 0b er e s e a r c h e d t h r e ee v a l u a t i o nm o d e l so f 鲥dq o sa r ep r o p o s e da 1 1 dt h et r a d i t i o n a lc o m p u t a t i o n a n de v a l u a t i o no fg r i dq o si si m p r o v e d 1 ，v a g u es e tb a s e d 面dq o se v a l 伽i n gm o d e l v a g u es e ti su s e dt 0d e s c 曲e 廿1 e 吼c e r “ne x p r e s so fq o s ，s u c ha s a r o m l dav a l u e a n d s e c 戚t yi sh i 曲，a 1 1 dd st l l e o r ) r b a s e de r a l g o r i t l l i l li su s e dt oc o m p u t ea i l dc 咖b i n em u l t i p 王eq o sp 撒m e t e r s t h er e s u l t o fe rc o m p u t i n gi sa d d e di 1 1 t ot a s ks c h e d u l i n ga j g o r i t h ma n dt h ea l g o r i t h mi si n l p r o v e d t h ee x p e r i l n e n t a l lr e s u l th a sp r 0 v e dt h a t 妇1 en e wt a s ks c h e d u l i n ga l g o r i n 蚰g u i d e db y v a g u es e td e s c 曲堍q o sr e d u c e dt l l em a k e s p a no fs c h e d u l i n ga n dm a d et l l e 西dr e s o u r c e s u t i l i z e dm o r ee 箍c i e n t l y 2 ，c o i l i l e c t i v en u m b e r b a s e d 鲥dq o sc o m p u t i n gm o d e l c o 皿e c t i v en 啪b e ro fs e t l u 浙江工业大学硕士学位论文 p a i ra n a l y s i s ( s p a ) i su s e dt oc o p e 诚m 也eu 1 1 c e m i n t ) ，e x i s t m gi n 鲥dq o s n l e p a r a m e t e r b i nc o 如e c t i v em l m b e r a + b i i st 0 d e s c r i b et l l en u 删i n gr 锄g eo fq o s a 伉r i b u t e ，a l l dt l l ec o m l e c t i v en 啪b e ro p e r a t i o n a lr u l e sa i l dt o t a lo r d e rr e l a t i o na r es t u d i e dt 0 c o m p u t ea n de v a l u a t e 酣dq o s ，w m c hi sc o m b 硫di m ot a s ks c h e d u l i n g n u m 矗c a l e x p e r i m e n ti l l u s t r a t e dt l l a tb e i n gc o m p a r e d 谢t l lt l l es c h e d u l i n ga l g o r i t h mr e s 臼前n e db yr e a l n u i l 曲e rq o s ，t h i ss c h e d u l i n ga l g o r i t l l 】 i ln o to i l l ym a j n t a i n e dm a k e s p a l l 研t i l i nr e a s o n a b l e a r e 巩b u ta l s oi n c r e a s e dt l l eu t i l i t ) ro ft a s k - r e s o u r c em a t c l l i n g ，a 1 1 de n h a i l c e dm er a t eo f r e s o u r c eu t i l i 够 3 ，嘶dq o se v a l 删i n gm o d e lo f h y 嘶dm u l t i p l eq o s an e ws 仃u c t u r eo f 嘶dq o s 谢md e s c r i p t i o nb yr e a ln u m b e r ，i n t e a ln u m b e r 锄dv a g u eu i l c e r t a j n t yi sp r o p o s e d ，粒c h e m b r a c e sa 1 1l 【i 1 1 d so fq o sa t t r i b u t e si n c l u d i n gl o g i cp a r 锄e t e r s ，n 幽帕r kt l l r o u g h p u ta j l d l a t e r l c y ，s e c u r i t y ，t n j s t ，a v a i l a b i l i 劬a n de v e nm ee x e c 妇g 伯：i l ea n dp r i c e t h e nt l l eh y b r i d m u l t i p l eq o sp a r a m e t e r s a r ec a j c u l a t e d 觚de v a l 删e d 谢t l le ra l g o r i ，a 1 1 dm e a p p l i c a t i o no ft h i sc o m p o s i t ee v a l u a t i o ni i lg r i dt a s ks c h e 叫i n gi si n 们d u c e d k e yw b r d s ：q o s ，s c h e d u l i l l ga l g o r i t i m l ，舒d ，e rc o i l i l e c t i v en u m b e r 浙江工业大学硕士学位论文 摘要 目录 第一章绪论 i l 1 1 研究背景1 1 1 1 网格一1 1 1 2 网格服务质量2 1 1 3 网格任务调度2 1 2 研究现状一3 1 2 1 网格服务质量研究现状3 1 2 2 网格任务调度研究现状一5 1 3 研究意义6 1 4 论文结构与内容6 1 5 本章小结7 第二章基于e r 的v a g l l e 集多q o s 属性测量及网格任务调度 9 2 1 问题的提出9 2 2 研究现状9 2 3 网格模糊多q o s 1o 2 4 基于e r 算法的模糊多q o s 属性的合成。1 1 2 4 1 基于d s 理论的e r 算法1 1 2 4 2v a g u e 值表示的q o s 评价等级1 2 2 4 3v a 哩舢e 值多q o s 属性融合。l3 2 4 4q o s 期望效用函数值1 5 2 5 模糊多q o s 融合算例15 2 6 、垤u e 集多q o s 任务调度算法1 9 2 6 1 算法思想19 2 6 2 算法描述2 0 2 6 3 仿真实验与分析21 2 7 本章小结2 2 第三章基于联系数的网格q o s 测量及应用 3 1 问题提出2 3 3 2 联系数介绍2 4 3 2 1 联系数及其基本运算2 4 3 2 2 联系数的序一2 5 3 3 基于联系数的q o s 测量2 6 3 3 1q o s 测量模型。2 6 3 3 2q o s 参数测量2 7 v 浙江工业大学硕士学位论文 3 4 联系数q o s 任务调度2 9 3 4 1 调度算法描述2 9 3 4 2 计算实例。3 0 3 4 3 仿真分析3 4 3 5 本章小结3 6 第四章混合多属性q o s 的评价模型及应用3 7 4 1 问题提出3 7 4 2 研究现状。3 8 4 3 混合多属性q o s 模型3 9 4 4 混合多属性q o s 评价方法4 1 4 4 1 基于多属性决策的混合多属性q o s 评价4 1 4 4 2 基于e r 算法的混合多属性q o s 评价4 5 4 4 3 混合多属性q o s 评价与测量实例4 7 4 5 混合多属性q o s 评价模型的简单应用5 2 4 5 1 基于混合多属性q o s 评价的网格任务调度5 2 4 5 2 以多属性q o s 为目标的网格任务调度。5 3 4 6 本章小结5 4 第五章总结和展望 5 1本文总结5 6 5 2 现有研究成果存在的问题5 7 5 3 展望5 8 参考文献 致谢 作者读研期间参与的科研项目与发表的论文 v i 5 9 6 4 6 5 浙江工业大学硕士学位论文 1 1 研究背景 1 1 1 网格 第一章绪论 现代社会由于对大规模的科学和工程计算需求越来越强烈，这使得计算机不 得不提高其运行速率和存储容量。而为了达到这样更好的性能，除了提高系统硬 件处理能力外，还要不断改进系统的结构。但是硬件的处理速度很快便发展到了 极限，于是系统结构成了焦点，超级计算中心便成了复杂计算的主宰。但是超级 计算中心的造价非常昂贵，只有大的企业及国家级的部门才有能力配备，于是一 种全新的造价低廉的而数据处理能力却超强的计算模式诞生了，那就是网格计算 ( g r i dc o m p u t i n g ) 。网格的概念是从电力网格的概念借鉴而来的，它产生的目的 是希望用户在使用网格中的资源时，就像使用电力一样，只要能接触到，就可以 从中得到服务，而不用关心这种服务来自哪里。网格的正式定义一般以2 0 0 1 年工a n f o s t e r 与c a r lk e s s e l m a n 提出的定义为准，他们认为“网格计算关心的是在动 态的、多机构的虚拟组织中协调资源共享和协同解决问题”，可以从三个方面来 判断是否一个网格系统：协调非集中控制的资源；( 参使用标准的开放的通用 的协议和接口；( 9 获得非凡的服务质量( q o s ，q u a l i t yo fs e r v i c e ) 。 网格是一个集成的计算与资源环境，也就是说网格是一个计算资源池。从本 质上讲，网格把整个互联网整合成一个巨大的超级计算机，以实现计算资源、存 储资源、数据资源、信息资源、专家资源的全面共享胫1 。网格目的是在分布、异 构、自治的网络资源上构造动态的虚拟组织，并在其内部实现跨自治域的资源共 享与协作，进而有效地满足互联网的复杂应用对大规模计算能力和海量数据处理 的需求口1 。网格与传统的分布式系统的区别在于它具有广域性、异构性、动态性 三个特点。 浙江工业大学硕士学位论文 网格被誉为新一代的网络，它将引领互联网新的一波发展大潮。目前基于服 务的开放网格体系结构( o p e ng r i ds e r v i c e sa r c l l i t e c t u r e ，o g s a ) 已成为网格技术 发展的重要趋势。世界一些主要国家和公司已经在网格基础设施的建设上和网格 平台的开发应用上加大了投资力度。 1 1 2 网格服务质量 “提供非凡的服务质量 是网格的三个基本特性之一5 1 。网格q o s 的属性包 括两个方面：定性的属性和定量的属性。定性的服务质量属性描述了所需求的服 务的某些性能特点，它们以用户可理解的语言表述为一组参数，比如服务的可靠 性和用户满意度。定量的服务质量属性比较多，比如对于计算资源c p u 如何分 配，可以把占用c p u 的数目或比例作为服务质量的一个属性；对于存储资源的 q o s 属性有存储访问速度、存储容量等；使用成本或费用也是一个重要的q o s 属 性。 实际的网格应用都需要使用多样的、异构的资源，特别是要共享使用这些资 源，各个任务间需要更多的协作，这使得资源的调度分配与任务的执行变的复杂， 因而服务质量得不到保障，而网格基础设施只能建立在“尽力服务 的基础上， 在多个应用协作使用资源时，性能和效率极易降级。在网格的应用中，要保证服 务质量，就必须先描述网格用户的q o s 需求，确定网格服务质量的各个q o s 参 数【6 】。为解决以上问题，需要引入q o s 的测量评价机制。随着网格技术在各个领 域的不断推广应用，网格服务质量的测量与保证成为一个迫切需要解决的问题， 尤其是随着网格应用的商业化，q o s 将成为一个网格系统中的关键因素之一【7 】。 1 1 3 网格任务调度 任务调度是指把m 个任务映射到n 个机器上的处理过程，调度结果是将各任务 合理地分配在各机器上，使得某些性能达到最优拈1 。网格任务调度的主要目标是， 完成用户提交的任务并满足用户对任务运行的某些要求，把网格中所有的可用资 源，包括计算资源、存储资源、网络资源，与任务进行匹配，找到一种最合理的 2 浙江工业大学硕士学位论文 资源分配方式和调度策略，本质上就是一个组合优化问题。调度的具体目标包括： 最优化时间跨度( o p t i m a lm a k e s p a n ) 、满足服务质量( 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 ) 、遵循经济规则( e c o n o m i cp r i n c i p l e s ) 等钔。其中， 时间跨度是最主要、最常见的调度目标，它指的是调度的时间长度，跨度越短表 明调度策略越好n 们。 由于网格本身所固有的特性及网格应用的复杂性，网格对任务调度提出了新 的挑战1 ：网格任务调度算法必须是分布式的，因为网格中的资源分布在不 同的地理位置，要实现一种全局的统一的集中式调度是不可能的，必须采取并行 分布式的策略来进行任务的调度；网格任务调度策略必须具有自治性，网格 调度系统不能干涉节点内部的调度策略；网格任务调度是面向异构平台的； ( d 网格任务调度具有动态可扩展性，也就是说资源可以随时加人网格，或者离 开网格系统。 任务调度本身是一个n p h a r d 问题n 羽，再加上网格系统的分布性、自治性、 异构性和动态性，使得网格任务调度更加复杂。但是网格任务调度是网格应用的 基础与核心内容之一，是网格服务中所必须解决的一个关键问题。因此，网格任 务调度成为网格研究中一个热点问题。 1 2 研究现状 1 2 1 网格服务质量研究现状 随着网格应用的深入研究，人们不再满足于目前网格基础设施的基于“尽最 大努力 的服务，人们希望网格系统能够提供确切的有保证的服务质量，因此网 格q o s 问题被广泛研究。在研究的早期，为了保证计算密集型和数据密集型应用 的性能，资源预留和协同分配【1 4 】成为q o s 管理的主要研究重点。服务网格的概 念提出以后，网格q o s 研究工作重心开始转向面向服务的q o s 管理。一方面沿用 了网络q o s 中“服务级协定”( s e r v i c el e v e la g r e e m e m ，s l a ) 的概念，通过x m l 语言描述用户的q o s 需求；另一方面通过定义统一的服务接口扩展及服务间的交 浙江工业大学硕士学位论文 互协议实现服务的q o s 协商和管理。在网格q o s 系统和s l a 管理框架方面的两个 主要研究项目是g 朋认和g q o s m 州。g a ra ( g l o b u s 心c l l i t e c n l r er e s e n ，a t i o na 1 1 d a l l o c a t i o n ) 【1 6 】是由i a l lf o s t e r 等提出的网格q o s 体系结构，是一个分层的结构，支 持端到端的q o s 保障，是计算网格中最为人接受的q o s 框架。g q o s m ( 嘶dq o s m a i l a g e r ) 【1 7 】是一类在服务网格中支持q o s 的管理架构，它基于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 u r e ) ，可以实现：基于q o s 的服务发现，建立服务级协商( s l a ) ， 在中间件层和网络层提供q o s 保障机制；为分配的资源提供自适应调节。 网格q o s 具体的结构是分层的，q o s 参数在不同的层次上表现为不同的组成。 一般来讲，网格q o s 分为三层【1 8 】：( 1 ) 应用网格服务层。网格应用通过访问合适 的网格资源达到预定水平的q o s ，应用层利用服务质量曲线把q o s 参数与用户满 意度相互关联，来描述资源提供者的q o s 水平，它是v o 层q o s 测量的依据。( 2 ) 虚 拟组织层o 层) 。v o 层是中间承上启下的一层，它将用户提出的q o s 需求映射为 某一类网格q o s ，并且将物理层中相似的q o s 参数整合为这些类中的一类，这样 v o 层既屏蔽了物理资源的异构性，又降低了物理层q o s 的复杂性。v o 层中的q o s 属性主要分为逻辑资源类、系统类、安全类、信任类和记账类五种类型。其中， 逻辑资源类q o s 是虚拟组织直接提供给网格服务的物理资源的q o s 参数，是物理 资源服务性能在网格环境中的抽象，它是网格服务质量的主要决定因素。( 3 ) 资 源设备层。资源设备层捕获各个物理资源的q o s 属性来支撑v o 层的各类q o s ，物 理资源本身的服务性能是相对稳定的，但由于本地负载情况的不同，v o 层逻辑 q o s 属性是动态变化的。 对网格q o s 的具体方面的研究主要有：网格q o s 的多样性及复杂性、网格q o s 属性的测量与评价。关于前者，g ”i sv i l u t i s 等人总结了各种已知的网格q o s ，并 对其进行了分类1 6 j ，分类按照网格服务的不同而不同：极端服务，是指需要突 然做出反应的服务，对应的q o s 参数有可用性、可访问性、吞吐量、可操作备份 率( o p e r a t i o n a ls t a i l d b yr a t i o ，o s r ) 、气m 、节点、c p u 速率及簇负载；大规模 计算服务，是指需要大规模的计算资源与处理器周期的服务，对应的q o s 参数有 可用性、可访问性、可操作备份率、凡、节点、c p u 速率及安全；大数据量 存储服务，是指提供数据存储功能的服务，对应的q o s 参数包括可用性、可访问 性、吞吐量、安全、存储容量及可操作备份率；实时性服务，是指可以实时提 供的并对网络干扰延迟敏感的服务，对应的q o s 参数包括可用性、可访问性、吞 4 浙江工业大学硕士学位论文 吐量、延时、延时波动、簇负载及c p u 速率；信息服务，是指某些特定公司部 门之间共享资源的服务，相应的q o s 参数包括可用性、可访问性、吞吐量及安全。 从以上的分类中可以看到某些重要的q o s 属性不只存在于一个组中。另外，g 如s v i l u t i s 等人还指出q o s 属性中的某些参数对综合q o s 的影响之间是有相关性的，比 如当c p u 速率达到2 5 g h z 且凡气m 达到2 g 时，综合q o s 的变化率可达到o 8 以上。 关于网格q o s 的测量与评价，d a v i da l l e n o t o r 等人提出利用实物期权模型并加 入模糊逻辑推理来评价网格q o s 中的资源属性【1 9 1 。另外，d a v i da l l e n o t o r 等人用 模糊理论来评价网格q o s 水平【2 0 1 ，首先设定q o s 论域 d q d 墨脚s 朋跏s 三q d & 己，! 弘研，分别表示杰出的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 2 2 网格任务调度研究现状 网格任务可以分为独立的任务与相互之间存在通信的任务，调度算法可以分 为静态调度算法和动态调度算法f 2 l 】，不同任务的分类与不同的调度方法结合产生 了多种网格任务调度算法。 静态调度算法，是指所有待处理的任务均处于待处理状态，且待调度的任务 集合与任务的加工时间都是确定的，在进行一次调度后，各个任务的加工顺序被 确定下来，且在以后的处理过程中不再改变。在网格环境中，常见的静态调度算 法有：o l b ( o p p o m l i l i s t i cl o a db a l a l l c i n g ) 算法、m e t ( m i i l i m u me x e c u t i o nt i m e ) 算法、m c t ( m i l l i m 啪c o m p l e t i o nt i m e ) 算法、m n m i n 1 叼算法、m a ) 【m i i l 【e ，9 ，1 0 】 算：法、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 e da i l i l e a l i n g ) 算法、g s a ( g e n e t i c s i m u l a t e d 山m e a l i n g ) 算法等。 动态调度算法，是在任务运行过程中进行任务的调度与分配，任务的到达时 刻和计算时间不能事先确定。动态调度算法主要分为两类：批模式( b a t c hm o d e ) 和在线模式( 0 n 1 i n em o d e ) 【2 2 1 。在批模式下，任务到来后并不立即映射到机器，而 是先把一定的任务收集起来组成一个任务集合，等映射条件达到后才对该集合中 浙江工业大学硕士学位论文 的任务进行映射。在线模式是指任务一旦到达便映射到机器上，对每一个任务的 映射仅考虑一次，也就是说一旦任务被映射就不会被改变。常见的批模式启发式 调度算法有：m i n m i n 算法、m a x m i n 算法和s u 侬i r a g e 算法。在线模式下常见的启 发式调度算法有：o l b ，m c t ，m e t ，s a ( s w i t c l l i n ga l g o r i t h m ) 。另外，在批模式 调度算法中，每经过一个预定义的映射事件后才对任务开始映射，映射事件的定 义主要有两种方式：固定任务计数策略和时间间隔策略。 1 3 研究意义 网格是新一代的网络，是未来互联网的发展方向，它将成为未来网络的基础 设施。“提供非凡的服务质量”是判断网格的三个基本准则之一，服务质量( q o s ) 已经成为网格系统的一个重要性能指标。服务质量几乎渗透在网格应用中诸如资 源发现、任务调度、服务协商等每个方面。目前网格q o s 已成为网格研究的焦点 之一。然而，由于网格的动态性、异构性等复杂不确定性特征，以及网格用户对 网格服务质量需求的语义表达模糊性，使得网格q o s 变得更加复杂，这对网格模 糊q o s 合理的数学描述，以及准确的测量与评价提出了新的挑战。如何更合理地 描述丰富多样的且又具有不确定性的网格q o s 属性，如何更加准确的计算与评价 这些q o s 属性并更加有效指导网格计算与服务中的其它操作，这成为了网格亟待 解决的一个关键问题。 网格任务调度是网格应用中的另一大核心问题，在网格应用场景中，用户在 提交作业的同时总是伴随着对服务质量的要求，另外从网格系统资源的角度而 言，处理作业的过程中总是希望最大化系统吞吐率、最大化资源利用率，网格任 务调度承担了协调资源分配任务的重任，它是网格系统能否提供非凡的服务质量 的关键。因此，如何利用网格q o s 指导网格更有效的调度任务，更合理的利用网 格资源成为一项具有重要意义的研究。 1 4 论文结构与内容 论文的主要内容包括：( 1 ) 用v a g u e 集描述模糊的网格q o s 属性，并用e r 6 浙江工业大学硕士学位论文 算法将分层q o s 融合得到综合评价，以指导网格任务调度；( 2 ) 用集对分析联系 数来描述模糊网格q o s 属性，联系数的运算将网格q o s 合成为综合q o s 评价， 并应用于网格任务调度算法的研究；( 3 ) 对多数学形式的网格q o s 属性进行描述， 用t o p s i s 与e r 等多种方法进行测量与评价，并提出以混合多q o s 为目标的网 格任务调度策略。 论文结构组织如下： 第一章介绍了论文研究的背景、国内外在网格q o s 与网格任务调度方面的研 究现状，及论文的研究意义，最后给出了文章的组织结构。 第二章研究利用v a g u e 集来表示网格不确定性q o s 属性，用基于证据理论的 e r 算法将分层的q o s 参数融合为综合q o s 评价，并计算出综合效用值，给出了 详细的计算过程，并以实例演示；然后将该综合效用值加入到网格任务调度中， 提出了基于e r 算法的以v a g u 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 约束的m i n m i n 算法，给出 了计算实例，并做了仿真实验。 第四章研究了实数、区间数与v a g u e 模糊表达同时存在的混合多属性q o s 的 一种新的测量与评价方法，将实数、区间数与模糊表达分别映射到同样的评价等 级上，然后用e r 算法将分层的混合多q o s 参数融合为顶层的综合q o sv a g u e 集 等级评价，并转化为综合效用值，此综合等级评价或综合效用值可以作为约束条 件或调度目标应用到网格任务调度算法中，指导任务调度。 第五章对论文做出总结，并概括了现有研究成果存在的不足之处，展望了网 格研究的进一步工作。 1 5 本章小结 本章为论文的绪论，介绍了网格由来与概念、网格服务质量的含义与内容、 7 浙江工业大学硕士学位论文 网格任务调度的含义与目标等研究背景，并分别介绍了服务质量与任务调度在国 内外的研究成果及现状，然后介绍了论文的研究意义所在，最后阐述了本文的三 个方面的主要内容与各章节的组织构成。 浙江工业大学硕士学位论文 第二章基于e r 的v a g u e 集多q o s 属性测量及网格任务调度 2 1 问题的提出 服务质量( q o s ，q u a l 崎o fs e n ，i c e ) 作为网格技术研究的重要内容之一，已经 成为当前国内外研究的热点。在文献【3 】中，i a f lf o s t e r 提出判断网格的三个准则之 一就是“提供非凡的服务质量”。 网格系统本身有其固有的动态性与不确定性，主要表现在：a ) 资源的随时进 入和退出，导致资源数量的不确定性；b ) 计算资源性能的随时变化，导致资源质 量的不确定性；c ) 任务预期执行时间的不确定性，导致资源可用性的不确定；d ) 分配给任务的资源量与实际使用量的不同( 比如删，导致资源量的不确定性。 此外，还有很多诸如网络时延与资源负荷等的不确定性。这些网格系统固有的特 性使得网格q o s 变得更加复杂与多样化。在s l a ( s e r v i c el e v e la g r e 锄e n t ) 的协议 规则中会使用不确定性的描述，比如会出现接受“高q o s ”和拒绝“低q o s 的 情况，而“高、中、低”这种语义不易用准确的数值表达【2 0 】，用准确数值表达的 结果是资源提供者( g s p ，g r i ds e r v i c e sp r o v i d e r ) 无法准确预测未来资源的可用性， 而只能提供过多的资源以满足需要。 2 2 研究现状 针对网格q o s 的研究已有很多成果，有些从服务匹配与资源选择的角度加入 对的q o s 的研究。文献幽j 将多q o s 映射为一个服务质量数( s q ，基于此提出一 种可模糊匹配也可精确匹配的服务选择模型。文献【2 4 j 将网格q o s 几个属性量化， 以最大化系统服务性价比为目标，提出基于退火遗传算法的网格资源选择优化模 型。另外，更多的研究从网格资源调度的角度考虑q o s 属性的影响，文献【2 5 】通过 改进传统的m i n m i n 调度算法，提出一种自适应、性能q o s 驱动的m i m m i n 启 9 浙江工业大学硕士学位论文 发式任务调度算法。文献1 2 q 在保证性能q o s 要求的同时把节点可信度考虑进去， 提出了一种基于信任关系的网格服务调度算法；文献【2 7 】把任务完成时限作为q o s 参数加入到调度中，提出一种q o s 感知的批调度算法。 然而，上述这些研究都把网格各q o s 参数当作一个确定的量描述和处理，而 没有考虑网格环境的不确定性及q o s 参数的模糊性。概率统计法可以处理不确定 性，被用于网格参数测量与调度【2 羽，但是这种方法是用确定的实数描述存在的不 确定性，因而不能保留参数的不确定信息。文献【2 0 】采用模糊逻辑解决q o s 的不确 定性，设定论域 o q d 墨蝴鲋跏s 三跏s ，每个q o s 参数用论域上的隶 属度函数计算得到一个模糊的评价，