（计算机科学与技术专业论文）信任约束下的网格工作流任务调度算法.pdf

je 。，：im st h e s i sr e s e a r c ho ng r i dw o r k f l o ws c h e d u l i n ga l g o r i t h mu n d e rt h ec o n s t r a i n t so ft r u s ts p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rd e g r e ec a n d i d a t e ：h a nj u a ns u p e r v i s o r ：p r o f h uz h i g a n g s c h o o lo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n gc e n t r a ls o u t hu n i v e r s i t yc h a n g s h ah u n a ne r c原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。作者签名一蕴竭日期：五! 旦年猎日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。作者签名：轻蠲导师签名必日期：型l 年月型日摘要网格是一个分布、异构、开放的互联网并行环境。网格环境中的资源筛选和调度策略是网格研究的关键问题之一。目前很多网格系统考虑了资源节点的身份验证，但是身份验证不足以有效保证网格的安全和可靠。将任务调度到不可靠、失效资源会增加任务的执行时间，有可能引发重调度。目前很多研究将信任机制和调度机制相分离，网格管理策略中将信任机制融入工作流任务网格调度算法的研究较少。本文在分析网格研究现状和网格工作流调度关键技术的基础上，对具有时间q o s 和信任q o s 约束的网格工作流任务的调度问题进行了深入的研究，提出了一种将信任机制和调度机制相结合的调度机制及基于任务执行状况的直接信任度和基于推荐因子的推荐信任度相结合的信任计算模型，并设计了信任约束下基于关键路径的工作流任务调度算法。该调度算法通过计算工作流任务的逆向深度，按照任务在候选资源上的完成时间确定关键任务，并通过资源实体的直接信任度和推荐信任度综合计算该资源的信任度，最后根据任务的逆向深度从大n d ,依次为任务分配满足综合效益函数的资源，优先调度关键任务。若是关键任务则选择满足执行时间和信任综合函数的资源，若为非关键任务选择完成时间和信任综合函数最小的资源。实验表明，本文提出的调度算法可减少工作流的完成时间、提高任务执行成功率5 1 5 ，能有效保证网格调度中的资源优化和提高调度执行效率。关键词网格，工作流调度，信任约束，关键任务a bs t r a c tg r i di sad i s t r i b u t e d ，h e t e r o g e n e o u s ，o p e nn e te n v i r o n m e n t r e s o u r c es e l e c t i o na n ds c h e d u l i n gs t r a t e g yi so n eo ft h ek e yi s s u e si ng r i de n v i r o n m e n t a tp r e s e n t ，o n l yt h er e s o u r c en o d ea u t h e n t i c a t i o ni sc o n s i d e r e di nm a n yg r i ds y s t e m s ，w h i c hi si n s u f f i c i e n tt oe n s u r et h es a f e t ya n dr e l i a b i l i t yo ft h eg r i d s c h e d u l i n gt a s ko nu n r e l i a b l e ，d i s a b l e dr e s o u r c e sm a yi n c r e a s et a s ke x e c u t i o nt i m ea n dl e a dt or e s c h e d u l i n g t r u s tm e c h a n i s ma n dg r i ds c h e d u l i n gm e c h a n i s ma r er e s e a r c h e ds e p a r a t e l yi nm a n yp r o j e c t ，i ti sv e r yf e wt ob l e n dt r u s tm e c h a n i s mi ng r i dw o r k f l o wt a s ks c h e d u l i n ga l g o r i t h m o nt h eb a s i so fa n a l y z i n gt h ec u r r e n ts t a t u sa n dt h ek e yt e c h n o l o g yo fg r i dw o r k f l o ws c h e d u l i n g ，d e e pr e s e a r c ho ng d dw o r k f l o ws c h e d u l i n ga l g o r i t h mu n d e rt h er e s t r a i n to ft i m eq o sa n dt r u s tq o si sd o n ei nt h ep a p e r aw o r k f l o ws c h e d u l i n gs c h e m ec o m b i n i n gt r u s tm e c h a n i s ma n ds c h e d u l i n gm e c h a n i s mi sp r o p o s e d ，a n da l s oat r u s tc o m p u t i n gm o d e lc o m b i n i n gd i r e c tt r u s tb a s e do nt h et a s ke x e c u t i o ns t a t u sa n dr e c o m m e n d a t i o nt r u s tw i t hr e c o m m e n d a t i o nf a c t o r , a n daw o r k f l o ws c h e d u l i n ga l g o r i t h mb a s e do nc r i t i c a lt a s k su n d e rt h ec o n s t r a i n t so ft r u s ti sd e s i g n e d f i r s t l y , b a c k w a r dd e p t ho ft a s k si sc a l c u l a t e di nc t s a ，a n dc r i t i c a lt a s k sa r ea s c e r t a i n e da c c o r d i n gt oe x e c u t i o nt i m eo nc a n d i d a t er e s o u r c e a n ds e c o n d l y , t h et r u s to fg r i dr e s o u r c ei sc o m p u t e db a s e do nd i r e c te x p e r i e n c ea n dr e c o m m e n d a t i o ne x p e r i e n c es y n t h e t i c a l l y l a s t l yt a s k sa r es c h e d u l e db yd e c r e a s i n gb a c k w a r dd e p t ha n dr e s o u r c e sa r ec l o s e dt om e e ti n t e g r a t e df u n c t i o no fe x e c u t i o nt i m ea n dt r u s ta n da l l o c a t e df o rc r i t i c a lt a s k sa sap r i o r i t y r e s o u r c e sw h i c hh a v em i n i m u mf u n c t i o nc o m b i n i n ge x e c u t i o nt i m ea n dt r u s ta r ea l l o c a t e dt oc r i t i c a lt a s k sa n dm i n i m u mf u n c t i o nc o m b i n i n gc o m p l e t et i m ea n dt r u s tr e s o u r c ea r ea l l o c a t e dt on o n c r i t i c a lt a s k s e x p e r i m e n t ss h o wt h a t ，t h ew o r k f l o wc o m p l e t i o nt i m ei sr e d u c e da n dt h es u c c e s sr a t eo ft a s ke x e c u t i o ni si n c r e a s e db y5 t o15 a n dt h ec t s aa l g o r i t h mc a ne f f e c t i v e l yg u a r a n t e eg r i ds c h e d u l i n gr e s o u r c eo p t i m i z a t i o na n di m p r o v et h es c h e d u l i n ge f f i c i e n c y hk e yw o r d sg r i d ，w o r k f l o ws c h e d u l i n g ，t r u s tq o s ，c r i t i c a lt a s ki i i目录摘要ia b s t r a c t i i第一章绪论11 1 研究背景11 2 网格研究现状21 2 1 网格工作流21 2 2 网格调度的研究31 2 3 网格q o s 研究41 2 4 研究意义51 3 研究内容51 4 论文组织6第二章网格工作流调度关键技术研究82 1 网格资源调度82 1 1 网格调度过程82 1 2 网格调度目标92 1 3 网格调度算法一lo2 2 网格工作流系统1 12 2 1 网格工作流管理系统1 22 2 2 网格工作流存在的问题132 2 3 网格工作流调度算法1 32 2 4 网格调度模型1 52 3 网格q o s 模型1 52 3 1 网格q o s 的分层模型1 62 3 2q o s 的量化1 72 4 本章小结l8第三章网格资源信任计算方法1 93 1 信任l93 1 1 信任定义193 1 2 信任的特点1 93 1 3 信任的分类2 03 2 网格中的信任模型2 03 2 1 基于模糊逻辑的基本行为信任模型2 03 2 2 基于主观逻辑的信任模型2 li v3 2 3 基于信任域的信任模型2 l3 3 网格资源信任计算2 23 3 1 网格信任研究中的问题2 23 3 2 信任度的计算2 33 3 3 信任的更新2 53 4 本章小结2 5第四章信任约束下的网格工作流任务调度算法2 64 1 问题的提出2 64 2 网格工作流2 64 2 1 网格工作流的体系结构与执行过程2 74 2 2 工作流的任务类型2 74 3 问题描述j 2 84 3 1 任务模型2 84 3 2 资源模型2 84 3 3 调度原则2 94 4 信任约束下的网格工作流任务调度算法3 04 5 本章小结3 5第五章实验及性能分析3 65 1 网格仿真工具3 65 1 1 常用仿真工具3 65 1 2g r i d s i m 介绍3 75 2 实验及结果分析3 85 2 1 相关算法介绍3 85 2 2 实验环境配置3 95 2 3 实验结果分析4 05 3 本章小结4 2第六章结束语4 36 1 工作总结4 36 2 研究展望4 4参考文献4 5致谢5l攻读学位期间主要的研究成果5 2v硕士学位论文第一章绪论1 1 研究背景第一章绪论弟一早三百了匕本文是国家自然科学基金项目“约束条件下基于随机服务模型的网格任务协同调度策略研究 ( 编号：6 0 9 7 0 0 3 8 ) 的一个研究方向，网格环境下基于信任的工作流任务调度算法是本文的研究重点。网格技术是九十年代以后迅速兴起的- i q 新技术，现在已成为国内外的研究热点问题。网格的初衷是将不同的超级计算机通过互联网整合起来来解决大型的复杂科学计算中的问题。现在网格的目标是将分布在世界各地的不同类型的各种计算资源，如超级计算机、p c 机、各种大型数据库、通信设备、传感器等资源通过i n t e m e t 粘合成“虚拟的超级计算机 ，实现这些资源的共享和协同工作【l 】。作为一门新兴技术，无论是现在还是未来，网格必将对人类的生产生活产生深远巨大的影响。目前网格的定义尚不统一，公认的是i a nf o s t e r 提出的网格标准，他认为网格系统必须同时满足三个条件【l j ：协调使用非集中控制的资源；使用标准的、开放的、通用的协议和接口；提供非凡的服务质量( q o s ，q u a l i t yo fs e r v i c e ) 。第一代i n t e r n e t 用t c p i p 协议实现了计算机硬件资源的连通；第二代i n t e m e t 通过w e b 实现了全球网页的连接；第三代i n t e r n e t 将试图实现网络上所有资源的全面连通，不仅包括计算机硬件和网页，还包括“计算资源、存储资源、通信资源，信息资源、知识资源、软件资源等，这就是网格计算【2 】。网格的发展主要分为以下三个阶段【4 j ，具体发展过程如图1 1 所示：第一阶段：元计算。网格最初是把分布在不同地理位置的超级计算中心通过互联网连接起来，提供更大规模和级别的计算能力。这个时期的代表性研究项目是i - w a y 5 】和f a f n e r 6 1 。i - w a y 项目用1 0 个异构网络将美国1 7 个不同地理位置的计算设备和数据资源连接起来组成超级计算环境。第二阶段：计算网格。工作主要是利用中间件和标准化接口技术解决了资源的异构问题。这一阶段的主要研究项目有g l o b u s l 7 】( 3 0 以下版本) ，n i m o n d g t 8 1 ，l e g i o n l 9 】等。第三阶段：服务网格。这一阶段主要提出了服务的概念，面向服务的模型和元数据构成开放网格服务体系结构o g s a l l 0 ( o p e ng r i ds e r v i c e a r c h i t e c t u r e ) 的核心思想。硕士学位论文第一章绪论自治多域服体系结构务体系结构2 ) 技术体系o g s aw s r fb ) 技术体系o g s i图1 - 1 网格发展历程网格技术的应用已从高性能科学计算发展到商业应用、军事、社会经济生活等各个领域，如高性能物理实验、气象预报、金融数值模拟分析、海陆空统一指挥系统等。网格技术具有重大的研究价值和广阔的应用。1 2 网格研究现状网格技术的主要目标是跨组织实现资源的共享和协同利用。目前网格的标准组织主要有全球网格论坛( g l o b a lg r i df o r u m ) 、w 3 c 等。网格研究主要包括两个方面，一是提供网格基础设施的网格中间件，如g l o b u s 、l e g i o n 、u n i c o r e 、c o n d o r - g 等；另一类是利用网格开发的应用项目，如欧盟开发的e u r o g r i d 、美国能源部开发的d o es c i e n c eg r i d 、中国的教育科研网格计划c h i n a g r i d 等。这些研究项目对网格的发展和应用发挥了巨大作用。1 2 1 网格工作流网格最初的应用领域比较简单，任务相对独立，任务之间的依赖较少。随着网格的不断发展，越来越多的网格应用，如协同工作，任务过程复杂，涉及不同时间和空间的资源的协作工作。这时若使用一般的方法效率低下，需要根据网格工作流的方式对网格应用进行管理，具体过程包括工作流的构建、执行、监控，来提高网格效率。网格工作流是任务的自动执行过程。当前针对网格工作流的主要规范有g s f l ( g r i ds e r v i c ef l o wl a n g u a g e ) 、g g f ( g l o b a lg r i df o r u m ) 的g r i dw o r k f l o w t l o 】和g w a ( g r i dw o r k f l o wa r c h i t e c t u r e ) 、o g s a 中的g r i dw o r k f l o ws e r v i c e s 。g s f l 基于x m l 语言，它将工作流定义成一系列用于服务交互的规则，可以描述网格服务工作流的过程定义。g s f l 主要包括服务提供者、活动模型、组合模型和生命周期模型i l l l 。g g f提出了工作流的推荐规范，利用x m l 定义工作流的属性和内容【1 2 】。比较著名的网格工作流项目有d a g m a n 、g r i d p h y n 、m y g r i d 、g r i d a n t 、j i s g a等。d a g m a n 1 3 】是用于c o n d o r 的元调度器，根据d a g 图调度具有依赖关系的2硕士学位论文第一章绪论任务。g r i d p h y n 是美国的网格工作流项目，包括g r i d p h y n 虚拟数据工具包、c h i m e r a 虚拟数据系统、p e g a s u s 规划系统和c o n d o r 工作流执行系统【1 4 】。m y g r i d是e s c i e n c e 支持的生物网格项目，提供网格中间件框架，结合w s f l ( w 曲s e r v i c ef l o wl a n g u a g e ) 产生新的基于x m l 的工作流描述语言s c u f f ( s i m p l ec o n c e p t u a lu n i f i e df l o wl a n g u a g e ) ，使得工作流可以在f r e e f l u o 系统中执行【l5 1 。g r i d a n t 是g l o b u s 开发的简单但功能强大的网格工作流管理系统，根据工作流协议和描述语言映射复杂工作流，而且可以测试不同网格的性能。j i s g a b 6 】是英国的网格工作流项目，它定义了基于x m l 的工作流描述语言s w f l ( s e r v i c ew o r k f l o wl a n g u a g e ) ，规定了o g s a 环境下的应用程序的工作流模型，提供一个执行环境。目前国内很多高校开始针对网格工作流展开研究，如华中科技大学负责的基于服务的网格工作流应用开发项目，国防科技大学负责的网格工作流描述语言和机制等。网格工作流的生命周期包括网格工作流建立和执行阶段。目前常用的网格工作流系统有g r i d f l o w 1 7 1 、g a l e b 8 l 、m c r u n j o b 1 9 1 、p e g a s u s 2 0 、c o n d o rd a g m a n 2 1 】等。g r i d f l o w 包括全局管理系统和局部子工作流系统。全局系统负责模拟、执行和监控工作流，局部系统负责处理子工作流的调度。全局和局部工作流系统协同管理，能有效优化工作流的执行。g a l e 是美国能源部研究的网格工作流系统，主要对网格中的计算和数据传输进行处理，但是没有考虑任务的条件、分解、合并、循环等关系，不能复杂复杂工作流。m c r u n j o b 是高能物理中应用的工作流管理器，将元数据转换成表单、工作流描述、控制步骤以及数据源，实现工作流的建模。p e g a s u s 是g r i p h y n 虚拟数据系统中的工作流系统，它从c h i m e r a 接受相关的抽象工作流描述，产生具体的工作流，交给c o n d o r - g 执行。c o n d o r 是针对计算密集型、高吞吐量计算环境的工作流管理系统。d a g m a n 用d a g 图表示工作流任务，只有父任务完成，才能执行子任务。1 2 2 网格调度的研究网格调度是在满足一定q o s 指标和任务优先约束关系的条件下，将任务按照一定策略分配到不同的资源节点上执行的过程。网格调度的一般目标是m a k e s p a n ，即使网格应用的完成时间最小。网格任务调度需要对网格资源进行统一管理。目前的网格资源管理系统主要分为三类：层次模型、抽象所有者模型、计算经济市场模型【2 2 1 。层次模型( h i e r a r c h i c a lm o d e l ) 是当前大部分网格系统采用的资源模型，如g l o b u s 、l e g i o n 、a p p l e s 等。抽象所有者模型( a b s t r a c to w n e rm o d e l ) 是指网格资源者不关心资源拥有者，而仅关心资源的使用方法和使用条件，目前很少有实际的网硕士学位论文第一章绪论格项目采用该模型。计算经济市场模型( 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 )综合了层次模型和抽象所有者模型，既可以利用层次模型的成熟技术，又明确以经济为基础进行资源管理和调度，如n i m r o d g 系统。不同的资源数目和组成结构构成不同的任务调度模式，常用的网格任务调度模式有三种：集中式、分散式、分级调度f 矧。集中式调度是指一台计算机资源统一分配调度任务，统一管理一个或多个域中的资源，如集群系统的l s f 、n i m r o d等。这种集中式的调度不适合网格系统。分散式调度模式没有统一的资源管理者，具有一定的扩展性和容错性，但在网格系统中的实现非常困难，如m o s i x 。分级调度模式包括全局调度和局部调度，如图1 2 所示。全局调度使用集中式调度，局部调度中允许自调度策略，适用于网格系统，目前被广泛采用，如a p p l e s 、l e g i o n 、c o n d o r 、n i m r o d g 等。图l - 2 分级调度模式网格调度算法一般分为静态调度算法和动态调度算法。静态调度算法是指所有的任务的执行顺序和匹配的资源被确定后在处理过程中不再改变。动态调度算法是考虑到网格中的动态特征，资源可能动态加入和退出，以及资源性能不稳定，任务在调度中的计算时间和到达时间不能预先确定。调度中的任务执行时间是个关键问题，某些调度系统中包含预测模型，主要有两种：短期预测模型，调度器初步预测任务的执行时间，如n w s ；长期预测模型，用于非专用计算环境中任务执行时间的预测，如g h s 。1 2 3 网格o o s 研究网格的标准之一是“提供非凡的服务质量”。q o s 是一个综合指标，衡量用户对网格服务的满意程度。q o s 的保证是网格中的关键问题，也是难点问题。网格q o s 包含定性的和定量地属性。定性的服务质量描述了服务的某些性能特点，可以表述为一组参数，如可靠性和用户满意程度。定量的服务质量是直观可知的属性，较为广泛，如c p u 数目，存储资源的存储能力、访问速度，经济成本费用c o s t 等。在网格应用中，要保证服务质量，就要引入q o s 机制。4硕士学位论文第一章绪论当前主要的网格q o s 体系结构包括两种：g l o b u s 预留与分配体系结构( g a r a ) 和网格q o s 管理体系结构( g q o s m ) 【2 4 1 。g a r a ( g l o b u s a r c h i t e c t u r ef o rr e s e r v a t i o na n da l l o c a t i o n ) 是目前网格中最广为接受的q o s 框架，是由i a nf o s t e r 提出的分层的网格q o s 体系结构，由应用编程接e la p i 、g l o b u s 安全体系框架g s i 和资源管理器r m 组成。g a r a 通过对资源的提前执行、预留和监控等措施保证端到端的q o s 服务质量。g q o s m 是o g s a 环境下能实现资源预留和自适应调节机制的q o s 管理体系结构，该系统可以提供基于q o s 的资源服务发现、建立服务等级协议s l a 、保障网络层和中间层的q o s 、资源自适应调节等功能。当前的调度算法中，常用的q o s 指标是满足时间和价格约束，即在一定的时间和成本范围内保证资源和任务的映射与执行。由于网格资源的动态性，不可靠资源可能引发任务的重调度，并使整个网格系统的等待和完成时间增多，因此越来越多的网格研究关注信任q o s 对调度的影响。1 2 4 研究意义网格资源由各种异构的p c 机、工作站以及超级计算机等组成，各种资源分散在不同地方，资源内部具有自治性，可以被节点内部任务及网格使用，且网格资源可以随时动态加入或退出网格系统。网格资源的这些特性使得网格环境下的调度问题变得非常复杂，因此成为网格研究的重点和难点问题。共享的网格环境中可能会存在恶意资源扰乱网格系统的正常运行。更多的大型网格应用需要多个资源实体共同参与、协同完成。资源实体之间的信任尤为重要，信任度高的协作资源可以有效提高网格的效率。为了使网格更好地满足用户的服务质量需求，将信任度机制融入网格任务调度机制中，在进行网格调度前对资源进行信任评估，选择信任度高的资源以提高网格作业完成的成功率和减少任务完成时间已成为网格热点问题。因此，信任约束下的网格工作流任务调度算法具有重要的理论价值和现实意义。1 3 研究内容本文的主要针对网格工作流任务的资源调度进行深入的研究，并在调度策略中引入信任机制，提出了信任约束下基于关键路径的网格工作流任务调度算法。本文的研究工作主要包括以下几个方面。( 1 ) 确定网格工作流的关键任务。工作流中的关键任务的执行时间决定整个工作流的m a k e s p a n 。当前工作流研究中包括静态关键任务和动态关键任务两种。静态关键任务是在假设资源的性5硕士学位论文第一章绪论能稳定，在调度之前可以预测资源的执行情况，从而在映射前确定关键路径。动态关键任务考虑了资源的动态性和不确定性，是指在调度过程中任务的执行时间和资源的可用性是会发生变化的，从而使得关键任务动态变化。( 2 ) 将信任机制融入网格资源调度。本文的研究中将信任q o s 引入工作流调度，网格调度是在满足相应q o s 约束下进行的资源调度和任务分配，本文主要针对时间q o s 和信任q o s 。( 3 ) 分析了网格资源信任的计算和更新方法。网格资源信任度包括直接信任度和间接信任度两方面，并随时间动态变化。实体直接信任度由资源执行网格任务的成功次数、失败次数、延迟次数以及相应的时间衰减函数共同决定，推荐信任度则和推荐资源实体本身的直接信任度以及推荐路径的推荐信任度相关。( 4 ) 提出了信任约束条件下基于关键路径的网格工作流任务调度算法( ag r i dw o r k f l o ws c h e d u l i n ga l g o r i t h mu n d e rt h ec o n s t r a i n t so ft r u s t ) ，简称c t s a算法。该算法首先计算工作流任务的逆向深度，根据任务在候选资源上的平均执行时间确定工作流的关键任务，然后根据资源实体的直接信任度和推荐信任度综合计算出该网格资源的信任值，最后根据子任务的逆向深度从大到小依次为任务分配满足效益函数的资源，优先调度关键任务，选择满足执行时间和信任综合函数的网格资源，为非关键任务选择完成时间和信任综合函数最小的资源。( 5 ) 采用网格模拟器g r i d s i m 来仿真网格环境，并将本文提出的c t s a 算法与h e f t 算法、c p o p 算法进行对比分析。实验结果表明：该算法不仅缩短了工作流的完成时间，而且提高了调度的成功率。c t s a 算法可以有效地改善网格资源调度的性能，值得进一步研究和推广。1 4 论文组织论文内容具体如下：第一章介绍了网格的研究现状。首先介绍了网格的的定义以及发展历程，然后重点介绍了网格工作流、网格调度以及网格q o s 的研究现状，包括网格工作流的起因和常用的工作流规范和管理系统，调度中的资源组织模型、调度模式和网格应用类型，q o s 分类和q o s 管理系统，以及信任约束下的网格工作流任务调度算法的研究意义。然后给出了本文的主要研究内容和论文的组织结构。第二章分析了网格工作流调度的关键技术。首先介绍了网格资源调度的过程，常见的调度目标和算法，然后着重介绍了网格工作流系统的相关知识，如网格工作流管理系统，网格工作流存在的问题以及常用的工作流调度算法，最后介6硕士学位论文第一章绪论绍了网格q o s 的分层模型以及网格中常用的q o s 的量化。第三章主要介绍了网格资源的信任计算方法。该章节首先介绍了网格信任的定义、相关特点和常见的分类方法，然后介绍了网格中的信任模型，最后给出了网格资源信任度的具体计算和更新方法，为第四章信任约束下的网格工作流任务调度算法做好了准备。第四章提出了信任约束下的网格工作流任务调度算法。首先阐述了将信任机制融入网格工作流调度的必要性，描述了网格工作流的执行过程，然后给出了调度过程中的任务模型，资源模型以及调度原则，最后结合第三章提出的信任度的计算详细描述了信任约束下基于关键路径的网格工作流任务调度算法的具体步骤和相关计算过程。第五章描述该算法的实验和性能分析过程。首先介绍了网格常用的方针工具，包括s i m g r i d ，g r i d s i m ，m i c r o g r i d ，g r i d n e t ，b r i c k s 等，详细介绍了g r i d s i m的结构和原理。然后介绍了该算法的实验环境配置，将该算法和h e f t 算法、c p o p 算法进行对比分析，实验证明，本文提出的算法能缩短工作流任务的完成时间，并提高任务的执行成功率。第六章是论文的总结，并展望了网格工作流任务调度研究的进一步工作。7硕士学位论文第二章网格资源调度关键技术研究第二章网格工作流调度关键技术研究网格环境下的调度机制是影响网格计算成功的重要因素。网格调度是根据一定的调度策略将任务分配到合适的资源节点执行的过程。由于网格资源的异构性、自治性和动态性，网格调度相当复杂，是一个n p 完成问题，并成为网格研究领域的热点和难点。本章主要介绍网格工作流调度的关键技术，包括网格调度的过程，目标，相关调度算法，工作流管理系统和工作流研究的难点问题，以及网格q o s 的分层模型与q o s 的量化。2 1 网格资源调度资源管理和任务调度是网格计算的核心。网格资源主要包括计算资源、通信资源、存储资源【2 5 1 。网格任务调度系统主要研究在异构的环境下寻求资源与任务的最佳匹配，管理和调度的任务执行，提高系统资源的利用率。影响调度的因素包括计算机类型、应用的特点、处理器数量和存储能力、输入输出的位置、网络带宽和延迟等等，如何合理地调度资源，已成为网格项目的研究重点。网格环境下的任务调度有如下特点【2 6 】：面向异构平台；网格调度是大规模的，非集中式的；网格任务调度不干涉网格节点内部的调度；随着资源节点的不断加入调度必须可以扩展；调度系统有一定的容错性，能自适应网格资源的动态性。2 1 1 网格调度过程网格调度主要分为三个阶段：资源发现，系统选择和作业执行【2 1 7 1 。具体步骤如图2 1 所示。资源发现依靠底层的资源发现和传播机制决定哪些资源可用，如g l o b u s 中的m d s 2 ，主要用来采集操作系统、c p u 个数、处理器类型和速度等系统资源信息。资源发现包括授权认证过滤、应用需求定义、筛选满足最小需求的资源过滤三个阶段。系统选择是对第一阶段筛选的资源采集进一步的详细信息，并进行决策，包括动态信息采集和系统选择阶段。网格信息服务g i s 中的网络天气服务n w s 可以监测当前c p u 可用时间片、可用内存、带宽等实时网格条件。系统选择也叫资源调度，是根据相应的资源信息和任务信息进行匹配决策的过程，是经典的n p 完全问题。作业执行时系统进行调度决策后将任务分配到相关资源节点上执行的过程，包括资源预留、作业递交、准备任务、过程监测、作业完成和清除任务等阶段。8硕士学位论文第二章网格资源调度关键技术研究2 1 2 网格调度目标图2 1 网格调度过程网格调度有如下四个常见的目标：最优跨度、服务质量、负载均衡、经济原n t 2 甜。这些目标从不同的角度反映调度的性能。( 1 ) 最优跨度( o p t i m a lm a k e s p a n )跨度指的是从第一个任务到最后一个任务完成经历的时间。跨度是最常见的目标，跨度越短调度策略越好，最优跨度是网格系统和用户的共同目标。假设有n 个作业v = v l ，v 2 ，v n ，需要调度到z 个资源m = m l ，m 2 ，m z 上运行，任务v i 在m k 的执行时间为t i k ，v i 的等待时间为t w ，那么实现最优跨度的目标就是找到一个合理的调度，使得m b 。寸公式( 2 - 1 )( 2 ) 服务质量q o s ( q u a l i t yo fs e r v i c e )服务质量q o s 是一个综合指标，描述用户对资源的某些性能要求，反应用户的满意程度。调度时必然保证网格应用的某些服务质量。常见的有信任q o s 、费用q o s 、计算资源q o s 、网络资源q o s 等。( 3 ) 负载均衡( l o a db a l a n c i n g )分布式和并行系统中，负载均衡是一个关键问题，网格具有分布式和不同资源并行运行的特点，因此，有效地解决负载均衡可是一个很重要的问题，并能优化时间跨度。9硕士学位论文第二章网格资源调度关键技术研究( 4 ) 经济原则( e c o n o m i cp r i n c i p l e s )网格中的资源地理上分布，且属于不同的组织和机构，不同性能，不同地域的资源的使用费用也是不同，网格中的用户使用网格资源时需要付费，更希望得到“物美价廉”的资源。因此网格系统在调度时必须考虑双方的价格需求，使资源提供者和资源使用者互惠互利。本文算法研究涉及的目标包括时间跨度、服务质量q o s 和负载均衡。2 1 3 网格调度算法网格调度就是将“合适 的任务分配到“合适 的资源上执行的过程【2 9 】。网格应用主要两种不同的任务类型【3 0 1 ，一种是独立任务，即m e t a t a s k s ，另一种是任务之间存在控制依赖和数据依赖的工作流任务，本文的研究工作主要针对后一种，即工作流任务。独立任务的执行次序不会影响调度的进行。独立任务的调度分为两类：在线模式和批模式。在线模式是采用先来先服务的思想，优先调度匹配已经到达的任务。批模式是任务到达后并不立即分配资源，而是任务到达一定数量或等到一定周期和事件触发，对到达的任务进行统一分配和调度。对于工作流任务，一般根据依赖关系建立调度列表，然后重复调度直至所有任务执行完成。网格调度一般分为两步：( 1 ) 空间上对资源和任务进行匹配，为任务选择合适的资源，并将相关的数据和任务传递给资源；( 2 ) 时间上和空间上为任务的计算和通信进行排序，包括不同任务之间的通信排序和同一计算资源上的任务的排序。网格中常见的独立任务的调度算法有：o l b 算法【3 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 c t 算测3 2 1 ( m i n i m u mc o m p l e t i o nt i m e 一最小完成时间调度算法) 、m e t 算法( m i n i m u me x e c u t i o nt i m e 一最小执行时间调度算法) 、m i n m i n 算法、m a x m i n 算法、s u f f e r a g e 算法、d u p l e x 算法、t a b u 算法( 禁忌调度算法) 、s a 算法( s i m u l a t e da n n e a l i n g 一模拟退火算法) 等。o l b 算法o l b 算法是网格调度中最简单的算法，主要思想是将任务集中的任务随机分配给可用的资源。该方法简单，容易实现，但是可能会将任务分配到执行时间长的资源上，从而增加完成时间，因此该算法效率不高。m i n - m i n 算法m i n - m i n 算法主要针对独立任务，将任务分配给开始时间最早且执行时间最短的资源，使总的任务完成时间最小。基本思想是反复执行如下操作直至为空：1 0硕士学位论文第二章网格资源调度关键技术研究( 1 ) 对于需要调度的非空任务集中s 的每一个任务待分配v i ，计算出该任务分配到z 个资源上不同的完成时间t i k o( 2 ) 选出具最小完成时间t i l 【的任务v i ，将任务分配到相应的资源上。( 3 ) 从s 中将任务v i 删除，同时更新各个资源的最早开始时间。( 4 ) 反复执行( 1 ) 至( 3 ) ，直至任务集s 为空。假设m i n m i n 算法的执行情况如表2 1 ，调度后的结果如图2 2 所示。表2 1 调度前的执行时间矩阵1 572图2 2m i n - m i n 算法的调度结果从上图可以看出，m i n m i n 算法的主要缺点是极容易出现负载不均衡，性能高的资源上任务数量很多。目前已提出了很多基于m i n - m i n 的改进算法。m a x m i n 算法m a x m i n 算法与m i n m i n 算法比较类似。区别之处是m a x m i n 算法优先将具有时间最长最早完成时间的任务分配给相应的计算资源。例如，在表3 1 中，m a x m i n 算法优先调度任务v 3 。2 2 网格工作流系统由于资源的分布性、异构性、自治性和动态性导致服务资源的稳定性、可用性、性能和服务质量不一样，所以如何将工作流任务合理地调度到资源节点上并有效保证服务质量和时间期限是网格工作流任务调度中的重点和难点问题。硕士学位论文第二章网格资源调度关键技术研究2 2 1 网格工作流管理系统网格工作流管理系统包括如下几部分：工作流定义、监控、工作流调度、数据传输和容错管理【3 3 】。( 1 ) 工作流定义工作流是多个具有依赖关系的任务组合而成。任务之间的控制关系包括顺序、并行、选择和循环四种结构。一般简单的工作流任务常用d a g 图表示，但是d a g 图不能表示任务的循环。此外，常见的工作流建模方法还包括基于形式化语言的建模、基于事务过程的建模以及基于p e t r i 网的建模方式。工作流定义包括定义工作流的任务和结构，包括两种类型的工作流：抽象工作流和具体工作流。抽象工作流没有指定具体的网格资源。而具体的工作流任务绑定了具体的网格资源。工作流执行前定义抽象工作流，根据当前的资源动态特征产生具体的工作流。( 2 ) 工作流调度工作流调度是工作流管理的重点问题和难点问题，也是本文的研究重点。工作流系统映射和管理共享资源的任务执行，调度结构分为集中式、分层式和分布式三种。集中式调度器为工作流的所有任务统一调度决策，任务、资源不容易扩展。分层式有一个中央调度器和多个子调度器，中央调度器和低层子调度器可以有不同的调度策略，但是中央调度器若出现错误将影响整个系统。分布式调度没有中央调度器，调度器可以相互通信，具有较好的扩展性。如何根据当前资源和任务情况做出最佳匹配一直是任务调度的难点。当前的调度中，一般是以某些目标作为调度策略的依据，如最小化任务完成时间，满足成本限制，优先考虑资源可靠性，系统负载均衡等。( 3 ) 数据传输工作流任务的执行需要前驱任务的数据传输到该资源节点才能执行，且当前任务的数据需传递给后继任务使用。因此，数据传输是保证网格工作流的重要内容。工作流系统中自动数据传输机制包括以下三种：集中式、调解式以及点对点式。集中式是指通过中央点管理数据，实现资源通信，易于实现，适合于小规模数据流。调解式是指中间数据由专用的分布式数据管理系统存储和转发，易于扩展。点对点式是指资源之间直接进行数据传输，节省了数据传输时间，适合大规模的中间数据流。( 4 ) 容错管理由于资源负载过重、网络失效等原因网格工作流可能会执行失败，这时网格工作流管理系统需要一定的错误处理机制来保证网格的可靠执行。常见的容错机制有任务复制、迁移和重调度等。1 2硕士学位论文第二章网格资源调度关键技术研究2 2 2 网格工作流存在的问题目前网格工作流的研究中存在以下重点和难点问题：1 工作流建模和描述语言网格工作流不仅具有异构、分布性，而且网格服务是动态并且由周期的，使得复杂工作流应用的描述和定义更加困难。建模语言需满足不同层次的抽象能力，屏蔽掉资源的底层细节问题。2 网格资源管理网格资源广域分布并且动态变化，抽象工作流映射成具体的服务时，工作流在不同的计算资源上运行，任务运行过程中资源动态变化，不同广域资源需要进行数据传输和通信，这些都为网格工作流的调度和执行增加了困难。3 网格工作流动态调度网