（计算机应用技术专业论文）网格计算中启发式任务调度算法的研究.pdf

浙江工业大学硕士学位论文 网格计算中启发式任务调度算法的研究 摘要 网格是高性能计算和信息服务的战略性基础设施，而网格技术已成 为下一代互联网应用的关键技术。网格可分为多种类型，但不论什么样 的网格，网格调度系统都是其发挥潜在性能和优势所共有的核心系统， 而任务调度模型及其优化算法则是网格调度系统必须解决的核心基础问 题和关键技术。 由于任务调度闯题是n p 完全问题，因此启发式调度算法得到了学术 界的高度重视。针对网格中传统的启发式调度算法，本文主要工作包括 以下几部分： 1 首先介绍了网格计算的概念和目的、体系结构、网格计算的关键技 术及主要的应用领域并指出任务调度的重要性；然后引入了任务调度的 模型，在此基础上详细阐述了网格调度的过程，并对目前调度算法研究 现状进行了总结。 2 采用了不同与传统算法设计的思维模式，提出基于禁忌思想的网 格调度新算法叻b l lm a x l o a d 。该算法通过禁止任务被分配到计算资源 上，直到每个任务都只有一个可用资源，仿真结果表明，与经典的优秀 算法m i n - m i n 、m a x - m i n 相比，该算法明显地降低了调度的时间跨度。 3 通过对m i l l - m i n 算法的分析和研究，针对m i n - m i n 算法的缺陷， 提出基于最小偏差的网格调度算法( d e vm i n - m i n ) ，该算法构造了任务 偏差矩阵，根据偏差矩阵分配任务到计算资源上。d e vm i n m i n 算法不 仅取得较小的调度时间跨度，并且具有良好的机器负载平衡性。 4 基于网格调度中安全性和可靠性这两个重要因素，改进了现有的 信任驱动的网格调度算法，取得较高的效益值和算法稳定性。 5 在同构环境下d a g 任务图调度算法一图解重构算法的基础上， 浙江工业大学硕上学位论文 提出了基于任务复制和时间一费用优化的d a g 任务调度算法。算法考虑 任务之间的通信、用户的时间期限和费用限制，更符合实际的网格环境， 该算法缩短了调度跨度、降低了调度费用，取得了较好的调度性能。 最后，对本文的研究工作进行了总结，对目前调度算法存在的问题 进行了分析，提出了迸一步的展望。 关键词：网格计算，任务调度，禁忌，偏差，信任，任务复制 i i 浙江工业大学硕士学位论文 t h er e s e a r c ho fh e u r i s t i ct a s k s c h e d u l i n g a l g o r i 印mf o rg r i dc o 口u t 玎呵g a b s t r a c t g r i di st h es t r a t e g i ci n f r a s t r u c t u r eo fi n t e n s ec o m p u t i n ga n di n f o r m a t i o n s e r v i c e s ，w h i c hh a sb e c o m et h ek e yt e c h n i q u eo ft h en e x tg e n e r a t i o no f i n t e r a c t t h e r ea r em a n yd i f f e r e n tk i n d so fg r i d ；h o w e v e r , t h eg r i ds c h e d u l i n g s y s t e mi st h ec o r es y s t e mt om a k eg r i dar e a l i t y a n dt h et a s ks c h e d u l i n g m o d e la n di t so p t i m i z a t i o na l g o r i t h mo ft h eg r i ds c h e d u l i n gs y s t e mi st h e b a s i ca n dk e yp r o b l e mn e e dt ob ef i g u r eo u t s i n c et a s ks c h e d u l i n gp r o b l e mi sn p - c o m p l e t e ，a n dt h u sa c a d e m i cp u ta l o ta t t e n t i o no nh e u r i s t i ct a s ks c h e d u l i n ga l g o r i t h m t h i sp a p e rh a st h e f o l l o w i n gc o n t r i b u t i o no i lh e u r i s t i cs c h e d u l i n ga l g o r i t h mo f g f i d ： 1 t h ec o n c e p t , o b j e c t i v e ，a r c h i t e c t u r e ，a p p l i c a t i o na n ds i g n i f i c a n c eo f g r i dc o m p u t i n ga r ep r e s e n t e d ；a n d t h e nt h et a s k s c h e d u l i n gm o d e li s i n t r o d u c e d a n do nt h eb a s i so fa b o v e ，t h ed e t a i l so f 鲥ds c h e d u l i n ga n dt h e c u r r e n tr e s e a r c hs i t u a t i o na r ea n a l y z e d 2 a ni n n o v a t i v ea l g o r i t h mi sp u tf o r w a r dw h i c ha d o p t sam o d et h a t d i f f e r sw i t ht r a d i t i o n a la l g o r i t h m sm o d e l 一- t a b u m a x l o a d ：i ti sb a s e do n m 浙江工业大学硕士学位论文 p r i n c i p l e so ft h et a b u t om a k eo n l yo n er e s o u r c 尼a v a i l a b l et oe a c ht a s k , s o m et a s kt ob ed i s p a t c h e dt os o m ec o m p u t i n gr e s o u r c ei sp r o h i b i t e d t h e e x p e r i m e n t a lr e s u l ts h o w st h a t i t g e t ss h o r t e rm a k e s p a nt h a nt r a d i t i o n a l a l g o r i t h ms u c ha sm i n - m i n , m a x - m i no b v i o u s l y 3 a f a ra n a l y s i so f m i n - m i n , t oa v o i dt h ed e f e c to f m i n - m i n , am i n i m a l d e v i a t i o nb a s e d 鲥ds c h e d u l i n ga l g o r i t h m ( d e vm i n - m i n ) i sp u tf o r w a r d a d e v i a t i o nm a t r i xi sc o n s t r u c t e d ，a n dt h e nt h ed i s t r i b u t i o no ft a s ki sb a s e d0 1 1 t h em a t r i x d e v m i n - m i nc a no n l ym a i n t a i nas m a l l e rs p a nb u ta l s om a i n t a i n a ne x c e l l e n tl o a db a l a n t e 4 c o n s i d e r i n gs e c u r i t ya n dr e l i a b i l i t yo fg d ds c h e d u l i n g ，t h ec u r r e n t t r u s t - b a s e d 班ds c h e d u l i n ga l g o r i t h m i s i m p r o v e d , r e s u l t s i nab e t t e r e f f i c i e n c ya n ds t a b i l i t y 5 u n d e rt h eb a s i si s o m o r p h i s me n v i r o n m e n td a gt a s ks c h e d u l i n g a l g o r i t h m , at a s k - d u p l i c a t i o na n dt i m e c o s to p t i m i z a t i o nb a s e dd a g t a s k s c h e d u l i n ga l g o r i t h mi sp u tf o r w a r d b yt h i sw a y , t h ec o s to fc o m m u n i c a t i o n b e t w e e nt a s k s ，u s e rd e f i n e dd e a d l i n ea n dc o s tc o n s t r a i n ti sc o n s i d e r e d t h e a l g o r i t h m r e s u l t si nab e t t e rp e r f o r m a n c ew h i c hl o w e rt h et i m es p a na n dc o s t h 1t h ee n d t h ec o n c l u s i o ni sm a d ea n dt h ep r o b l e me n c o u n t e r e di s a n a l y z e d ，a n dt h ef u t u r er e s e a r c hi sp u tf o r w a r d k e y w o r d s ：西dc o m p u t i n g ，t a s k ss c h e d u l i n g , t a b u ，d e v i a t i o n ，t r u s t , t a s kd u p l i c a t i o n i v 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名： 日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“寸) 日期：斫年岁月声日 a 努：瑚尹f 具；d 日 争。斟 王莆 - 名名签签者师作导 浙江工业大学硕士学位论文 1 1 研究背景 第一章绪论 随着人类探索自然活动的深度、广度不断拓展，迫切需要获得功能更强、速度更 快的计算机系统。同时，制造技术与工艺、体系结构设计在不断提高着单个计算机设 备的能力，另一方面，网络技术的进步已经使以一种支持有效并发执行的方式汇聚地 理上分散的计算资源成为可能。针对此现状，目前高性能计算正处于重要的转折期， 如何用好摩尔定律下的硬件进步和网络带来的汇聚效能，提高计算的效率和生产力， 这成为了业界研究的重中之重。 1 1 1 网格计算概念和目的 网格计算u 】是一种基于动态的、异构的和跨域的协同资源共享和问题求解的分布 式计算。计算机系统总体结构的演变历史表明：目前正在进入一个新的“分”体系的 发展阶段，即服务器聚集物理上分散到各地，但仍然保持虚拟的单一系统映像。在这 个网络计算时代，孤立的计算机系统、软件和应用将被网络化的产品和服务取代。世 界将被互连成为一个开放的、一体化的、资源共享的全球电脑网络，即用全球大网格 以满足人类日益增强的计算性能的需求。 网格计算4 5 】是当今计算机科学领域最新兴起的一项有很高学术价值和应用价 值的研究课题。网格计算的直接起源为元计算( m e t a - c o m p u t i n g j 嘲，它最早是由s m a r r 和c a t l e t t 引入的。网格计算的研究已经有了很大的进步，但是到目前为止，关于什 么是网格计算，还没有一个普遍接受的定义。1 9 9 8 年，在网格：一种未来计算基 础设施蓝图1 7 1 中提出：计算网格提供了可靠的、一致的、普遍的和不昂贵的高端计 算能力接入的硬件和软件的基础设施。在2 0 0 1 年的一篇题为“网格剖析”【1 】的文章 中，提出社会和策略问题，指出网格计算关心的是：在动态的，多机构的虚拟组织中 协调资源共享和协同解决问题。其核心概念是：在一组参与节点( 资源提供者和消费 者) 中协商资源共享管理的能力，利用协商得到的资源池共同解决一些问题。i a nf o s t e r 浙江工业大学硕士学位论文 等人进一步完善网格定义，认为网格实际上是满足如下三个条件的系统【8 】： 1 协调非集中控制资源。网格整合和协调不同控制域中的各种资源与使用者， 比如，个人电脑和中心计算机；相同或不同公司的不同管理单元；网格还解决在这种 分布式环境中出现的安全、策略、管理等阀题。否则，就只能算本地管理系统。 2 使用标准、开放、通用的协议和界面。网格建立在多功能的协议和界面之上， 这些协议和界面解决认证、授权、资源发现和资源存取等基本问题。否则，只能算一 个具体应用系统。 3 得到非平凡的服务质量。网格允许它的资源被协调使用以满足不同使用者的 需求，如系统响应时间、流通量、有效性、安全性，及资源重定位，使得联合系统的 功效远大于其各部分功效总和。 因此，网格就是一个集成的计算与资源环境。它能够把整个互联网集成为一台巨 大的超级计算机，实现全球范围的计算资源、存储资源、数据资源、信息资源、知识 资源、专家资源、设备资源甚至是人才资源等各种相关的广泛分布的资源全面共享。 可以认为网格存在如下三方面的含义： 1 从概念上，网格的目标是资源共享和分布协同工作。网格可以清晰地指导各 个部门的资源进行所有行业或企业的统一规划、部署、整合和共享，而不仅仅是行业 或大企业中的各个部分自己规划、占有和使用资源。 2 网格是一种技术。为了达到多种类型资源的分布共享和协作，网络计算技术 必须解决多个层次的资源共享和合作问题，制定网格标准将i n t c m e t 从通讯和信息交 互的平台提升到资源共享的平台。但是目前并行计算、分布计算、中间件等现行技术 远远没有解决多组织之间资源的共享问题，以及广域范围的多系统之间联合处理和计 算等网格计算所面临的关键问题。医院，网格计算技术研究具有独特性、紧迫性和挑 战性。 3 网格是基础设施，是通过各种网格整合计算机、数据、设备和服务等资源的 基本设施。这种设施的建立将使用户如同我们按需使用电力一样，无需在用户端配置 大量的全套计算机系统和复杂软件，而简便地得到网格提供的各种服务。这样，设备、 软件投资和维护开销将大大减少。 网格概念将根本地改变人们对“计算机应用”的看法，这是一种全新的、更方便 的计算方式，轻松实现目前解决不了的复杂问题。网格是借鉴电力网概念提出来的， 其最终目标是希望用户在使用网格时，就如同现在使用电力一样方便。建设网格的意 2 浙江工业大学硕士学位论文 义有： 首先，解决计算能力的限制，网格可以联合并放大全社会的计算能力。 其次，解决地理位置的限制，把“全社会的计算能力”送到你的桌面。 再次，节约资源，目前的计算机资源利用率远不充分，而很多应用又缺乏资源。 网格不仅可以把“资源”送到你的桌面，更能把“应用”放到网格中完成，连“桌面” 都可以节省。 最后，网格打破了传统网络共享与协作方面的限制，以“虚拟组织”的方法，实 现了全社会范围的资源共享与服务协作。 1 1 2 网格计算体系结构 网格体系结构是关于如何建造网格的技术，包括对网格基本组成部分和各部分功 能的定义和描述，对网格各部分相互关系与集成方法的规定，以及有效运行机制的刻 画。显然，网格体系结构是网格最核心的技术，只有建立合理的网格体系结构，才能 够设计和建造好网格，才能使网格有效地发挥作用。 网格体系结构主要有抽象层次结构、积木块结构、概念空间结构、混合结构和 o g s a ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ) 结构5 种形式。到目前为止，比较重要且有 影响的网格体系结构：即五层沙漏结构、开放网格服务结构o g s a 。 1 五层沙漏结构【l 】 五层沙漏结构是基于美国国家实验室的网格研发项目g l o b u s 提出来的，是一种 早期得抽象层次结构，以协议为中心，强调协议在网格的资源共享和互操作中的地位。 通过协议实现一种机制，使得虚拟组织的用户与资源之间可以进行资源使用的协商， 建立共享关系，并且可以进一步管理和开发新的共享关系。这一标准化的开放结构对 网格的扩展性、互操作性、一致性以及代码共享都很有好处。图1 1 所示为五层沙漏 结构的典型结构图。 构造层连接底层的本地资源和上层，为上层访问本地资源提供统一接口，屏蔽各 地资源的异构性；连接层定义了核心网格事务处理所需的通信和认证协议，提供了加 密的安全机制，用于识别用户和资源；资源层的协议调用构造层的功能以访问和控制 本地资源；汇聚层建立在资源层和连接层形成的协议瓶颈之上，主要负责多种资源的 共享；应用层存在于虚拟组织中，是根据任一层次定义的服务构造的。 3 浙江工业大学硕士学位论文 1 乳j ，廊“1 j ：, ：i l j b ： 、嘲i 皇断j o 瞧蔓等 f 驯7 ，铱j 上： 镑源o j 搬务的 瓷源j 在个访 d 琏毽蜣 j 如i 纬机办端弁 构诸以 压、眄维、f 堪器等 图1 - 1 五层沙漏的典型结构 沙漏形状是由于各部分协议的数量的不均匀引起的，考虑到移植、升级的方便性， 核心部分的协议数量相对比较少。该部分协议要实现上层各种协议向核心协议的映 射，同时实现核心协议向下层的映射。按照定义，核心协议的数量不能太多，这样就 形成了协议层次结构中的一个瓶颈。在五层结构中，资源层和连接层共同组成这一核 心部分，它促进了单独的资源共享。 五层沙漏结构根据各组成部分与共享资源之间的距离，将对共享资源进行操作、 管理和使用的功能分散在五个不同的层次。越往下层就越接近于物理的共享资源，因 此该层与特定资源相关的成分比较多；越往上层越感觉不到共享资源的细节特征。 2 开放服务网格体系结构o g s a l 9 j o g s a 是继五层沙漏结构之后的一种新型网格体系结构，被称为“下一代的网格 体系结构”。这种结构的目的是将网格的一些功能融合到w e bs e r v i c e 框架中。o g s a 是面向服务的结构，将所有事务都表示成一个服务，计算资源、存储资源、网络、程 序、数据等都是服务，所有的服务都联系对应的接口，所以，o g s a 被称为是以服务 为中心的“服务结构”，通过标准的接口和协议支持创建、终止、管理和开发透明的 服务。结合目前的w e bs e r v i c e 技术，支持透明安全的服务实例，o g s a 有效地扩展 了w e bs e r v i c e 架构的功能。它将网格从以科学与工程计算为中心的学术研究领域， 扩展到更广泛的以分布式系统服务集成为主要特征的社会经济活动领域，包括各种计 算资源、存储资源、网络、数据库等。 o g s a 还提供了一种网格安全机制来确保服务问所有的通信都是安全的。所有的 服务都是用g l o b u s t o o l k i t 构建的。所以，o g s a 的基本思想等于网格结构加w e b 服 务再加工具箱( t o o l k i t ) 。o g s a 中解决了两个重要的问题，即标准服务接口的定义 4 浙江工业大学硕士学位论文 和协议的识别。 图1 2 开放服务阿格体系结构o g s a o g s a 的主要层次如图1 2 所示，从下到上各层的涵义如下： ( 1 ) 物理和逻辑资源层：该层是网格计算的中心部分，其中物理资源是构成网 格能力的资源，包括处理器、服务器、存储器和网络。逻辑资源位于物理资源之上， 它们通过虚拟化和聚合物理层的资源来提供额外的功能。 ( 2 ) w e b 服务以及定义网格服务的o g s i ( o p e ng r i ds e r v i c e si n f i a s u u c t u r e ) 扩 展：o g s a 中所有网格资源( 包括逻辑的与物理的) 都理解成为服务。o g s i 利用诸 如x m l 与w e b 服务描述语言( w e bs e r v i c e sd e s c r i p t i o nl a n g u a g e ，w s d l ) 这样的 服务机制，为所有的网格资源指定了标准的接口、行为与交互方法。o g s i 还进一步 扩展了w e b 服务的定义，提供了动态的、有状态的和可管理的w e b 服务的能力。 ( 3 ) 基于o g s a 架构的服务：w 曲服务层及其o g s i 扩展为基于o g s a 架构的 网格服务提供了基础设施。g g f 目前正在致力于在诸如程序执行、数据服务和核心 服务等领域中定义基于网格架构的服务。随着这些新架构服务的出现，o g s a 将变成 更加有用的面向服务的架构( s e r v i c eo r i e n t e da r c h i t e c t u r e ，s o a ) 。 ( 4 ) 网格应用程序层：随着时间的推移，一组丰富的基于网格架构的服务将不 断被开发出来，使用一个或多个基于网格架构服务的新网格应用程序也将出现。这些 应用程序构成了o g s a 架构的第四层。 5 浙江工业大学硕士学位论文 1 1 3 网格计算的关键技术 随着网格研究和实际应用的深入，面临的挑战性问题越来越多地突显出来，为实 现网格的广泛应用，必须解决网格中的关键技术。网格计算的关键技术如下： ( 1 ) 管理层次化：管理层次化是网格将自身划归层次以适应全球的范围。例如， 管理层次化决定信息如何在网格中流动。 ( 2 ) 通信服务：通信服务要适应不同的环境，从可靠的点对点到不可靠的多播。 通信体系结构需要支持大量数据传输，流数据，组传输以及用于分布式对象的协议。 同时网络服务需提供重要参数，如响应时问、带宽、可靠性、容错性及抖动控制等 q o s 质量保证。 ( 3 ) 信息服务：采用注册和目录机制来满足网格的地点及服务类型的变化。它 提供了结构、资源、服务、状态及环境特征的注册和目录服务。 ( 4 ) 名字服务：名字服务提供了一个全局的统一名字空间。名字服务一般采用 x 5 0 0 和d n s 的命名机制。 ( 5 ) 分布式文件系统与缓存：复杂的网格环境都是在分布式文件系统基础上构 建起来的，分布式可以极大地提高底层存储设备的吞吐量，并减小总体数据库事务的 瓶颈。分布式文件系统是网格计算系统中的关键部件，因为网格中的分布式程序需要 多次访问分布在多个服务器中的文件。 ， ( 6 ) 安全与认证：网格计算环境对安全的要求比i n t e r n e t 的安全要求更为复杂。 具体包括支持在网格计算环境中主体之间的安全通信，防止主体假冒和数据泄密；支 持跨虚拟组织的安全；支持网格计算环境中用户的单点登录，包括跨多个资源和地点 的信任委托和信任转移等。这是网格计算的难点，也是系统成败的关键。 ( 7 ) 系统状态与容错：为保证整个系统的健壮性，网格计算系统应提供可靠的 监视系统资源和运行情况的工具。 ( 8 ) 资源管理( 含调度) ：对任何异构资源提供有效的管理、透明的资源调度， 高效地利用可利用的资源是系统的核心； ( 9 ) 任务管理( 含调度) ：任务管理是网格计算研究必须解决的另一个关键问题， 网格计算的目标是分解一个应用为几个任务( 或子任务) ，并为每个任务匹配一个最适 合执行的机器，任务调度的作用是根据当前系统的负载情况，对系统内的任务进行动 态调度，提高系统的运行效率，即按照用户提交的任务类型、所需资源、可用资源等 6 浙江工业大学硕士学位论文 情况安排运行计划和策略。 ( 1 0 ) 其它高级服务：如知识发现、索引，推理；推理任务的服务；可视化服务等。 在上述关键技术中，任务管理、任务调度和资源管理是网格计算必须具备三种基 本功能。 1 1 4 网格的主要应用领域 网格技术凭借其独特的计算力联合和分布式计算模式，在众多领域都拥有广泛的 应用前景。网格计算利用分布式计算机网络处理大计算量的任务，可以最大限度地利 用现有网络的计算力，而不必为增加信息处理能力而添置新的设备；通过租用网格网 络的计算力，可以实现许多因为计算力不够或者因为增加计算力导致成本过高的商业 应用。其应用领域归纳起来主要有以下几个方面： ( 1 ) 学科研究：复杂科学领域的计算通常以超级计算机作为数据处理中心，虽 然超级计算机处理能力强大，但是其本身的造价极其高昂，并不是所有的研究机构都 有能力配备。网格技术的出现，最大程度地提高了现有网络计算资源的利用率。 ( 2 ) 企业信息处理：网格为企业提供了一个强大的可租用虚拟系统，可以让用 户完成以前难以承担的任务，而生产成本却不会有明显的增长。 ( 3 ) 电子政务：网格技术可以整合和管理分散在各部门的信息化资源，实现各 个政府部门之间数据的无缝交换，消除“信息孤岛”，打破电子政务资源共享的瓶颈。 另一方面，网格技术的分布式工作模式，可以有效地实现在网络虚拟环境下的协同办 公，提高政府的工作效率、增强为公众服务的能力。 ( 4 ) 个人娱乐：使用网格可以为游戏开发商和服务供应商提供可扩展的、高弹 性的基础设施以运行大型多人游戏。而对于个人用户来说，网格服务器则意味着更安 全、更快捷的游戏体验。例如可以利用网格造价低廉而数据处理能力超强的计算模式， 将虚拟现实技术运用于网络游戏中，让参与游戏的人可以真切地感受虚拟环境所带来 的游戏快感。 7 浙江工业大学硕士学位论文 1 2 研究内容 1 2 1 本文研究重点 本文旨在对网格计算应用的关键技术之一一计算任务调度算法进行深入研究， 但是考虑到任务调度算法的实施设计过程中的众多技术环节，特别是任务调度、调度 之后调度成果的性能评价等，本文在特定的网格环境中进行算法研究，研究内容主要 包括以下几点： ( 1 ) 基于m a k e s p a n 的计算任务调度算法研究 一个运算量巨大的任务能否在网格环境下正确、快速和高效的运行和运行成功， 高效的任务调度算法是不可或缺的，因此本文重点研究了基于m a k e s p a n 的计算任务 调度算法。 ( 2 ) 基于多目标的网格调度算法的研究 计算任务调度算法研究的目的是在传统算法的基础上提出更适用于实际网格任 务调度的调度算法。结合多种调度因素如网格安全性、计算节点的可靠性、负载平衡 性等，寻找在某一或某些测度上更好的调度算法，并对算法进行形式化分析、仿真的 网格环境下的作模拟比较。 ( 3 ) 基于任务复制和费用时间优化的相依性任务调度算法的研究 在计算经济模型下，研究基于费用限制和时间最小的相依性任务调度算法，算法 在异构环境下并考虑任务之间的传输时间，更适用于实际的网格环境。其目标是在用 户提供的预算费用内，尽可能快地完成任务执行，追求时间最优化。 1 2 2 研究的网格环境 本文的研究聚焦于计算网格，因为计算网格的研究起步较早，其结构和功能的研 究比较成熟，而且计算网格是网格环境的基础。 以计算资源的共享和协同工作为目标建构的网格计算环境通常称为计算网格。计 算资源共享和协同工作是网格计算研究的最初动因，也是网格计算发展的持续推动 力，是网格环境的基础。它在各种网格环境中都无一例外地得到了支持。 计算网格为用户提供了可靠的、一致的、统一的访问分布在各地的资源的手段， 这些资源包括计算机、数据存储系统、科学仪器和高端显示设备等。计算网格通过在 8 浙江工业大学硕士学位论文 自主的计算机系统之上构建中间件层而成为一种新的计算资源，构成了一个基于 i n t e r n c t 的大规模分布计算环境，成为一种新的进行大规模科学和工程计算的平台。 计算网格的应用包括分布超级计算，知识合成，在线仪器设备控制以及远程沉浸等。 尽管当前网格与w e bs e r v i c e 相互融合，采用面向服务的构建方式融合了更多的 网络资源和服务，将计算资源同样封装成服务，但是计算资源的共享和协同仍旧是网 格的基础。在面向o g s a 开发的g l o b u st o o l k i t t m3 x 版本中，仍然继承并完善了面 向计算网格的运行方式的工具。而且，目前仍然有大量的研究工作是针对计算网格环 境的，例如g g f 中的多个研究组和工作组的大量研究工作是面向计算网格的。这是， 因为，一方面计算网格中的许多关键技术的研究仍很不完善，例如计算网格环境下的 作业调度、应用开发、性能评价等等：另一方面，计算网格已经暴露了网格计算中的 本质性的挑战问题，诸如异构性、可扩展性、自适应性等等，这些关键问题的深入研 究无论对计算网格还是服务网格都非常重要。 1 3 论文结构 论文按照如下线索组织内容：网格计算相关背景一网格任务调度概述一任务调度 算法研究一多目标任务调度算法研究，最后以全文结论结尾。共分7 章，其具体内容 如下： 第一章首先介绍了网格计算的背景知识，即网格计算概念和目的、网格体系结 构、网格关键技术以及研究现状等，接着简述了网格任务调度的重要性，最后提出本 文的研究课题和创新点，给出了本文的创新点及全文的组织结构。 第二章介绍任务调度的特点和主要目标，然后介绍了任务调度相关的模型、任 务调度过程以及对现有网格调度算法的研究。 第三章提出一种不同于传统思维模式的元任务调度算法：t a b um a x l o a d 。该算 法通过禁止任务分配到某些计算资源上，直到每个任务只有一个可用资源。算法取得 了良好的调度结果，并为网格调度研究提供了一个新思想。 第四章针对独立任务调度的负载均衡和高吞吐率原则，提出基于m i n - m i n 算法 的最小完成时间偏差调度算法( d e v _ m i n - m i n ) ，算法构造了调度完成时间的偏差矩 阵，根据任务的偏差进行调度。克服了m i n - m i n 算法追求局部最优的贪心算法思想 而存在的局限性。 9 浙江工业大学硕士学位论文 第五章介绍现有信任模型下信任值的量化方法，并针对目前网格资源管理中信 任机制与作业调度机制分离的缺陷，在现有信任模型与信任效益函数的基础上，改进 了信任驱动的网格调度算法t dm i n - m i n 算法。改进的算法取得更高的平均信任效益 和调度成功率。 第六章在计算经济模式下提出的调度算法基础上，考虑到目前研究主要关注时 间优化算法，提出了基于d a g 图和费用时间优化的调度算法，该算法是针对异构环 境中考虑任务之间通信时间的相依性任务调度算法。算法目标为：在用户提供的费用 预算内，尽可能快的完成任务执行。算法追求时间最优化，采用了任务复制的方法。 第七章是论文的结论，展望了任务调度研究的进一步工作。 1 4 本章小结 了解网格的基础知识是进行网格调度算法研究的前提条件。本章首先简单介绍了 网格计算的概念和目的、网格计算体系结构，然后重点介绍网格计算的关键技术，为 全文提供了研究的背景，接着阐述了本文要研究和解决的问题以及采用的研究环境， 最后勾画了本文的组织结构。 1 0 浙江工业大学硕士学位论文 第二章网格中的任务调度研究 2 1 网格计算任务调度的特点和主要目标 在网格系统中，任务调度系统是其重要的组成部分，它要根据用户提交的任务信 息采用适当的策略把不同的任务分配到相应的资源节点上去运行。由于网格系统的异 构性和动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得任务 调度变得极其复杂，不好的任务分配策略，将会增加任务的执行时间、降低整个网格 系统的吞吐量。 2 1 1 任务调度的特点 在网格环境中，任务和资源的数目都比较大，任务和资源之间的匹配关系也比较 复杂。任务与任务、任务与资源、资源与资源之间的相互关系最终都会影响任务的调 度顺序和任务与资源之间的匹配。 网格计算任务调度具有以下几个特点【1 0 】： ( 1 ) 任务调度是面向异构平台的。由于网格系统是由分布在各地的各类资源组 成的，包括各类主机、工作站、甚至p c 机，它们是异构的，可以运行在u n i x 、l i n u x 、 w i n d o w s 等各种操作系统下，也可以是上述机型的机群系统、大型存储设备、数据库 或其他设备。因此，网格系统中的任务调度必须面向异构平台，并在这些平台上实现 网格任务的调度。 ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统是一个大到整个地球的 分布式系统。要实现一种全局的统一集中的任务调度管理是根本不可能的。因此，网 格的任务必须以分布、并行方式进行任务的管理与调度。 ( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点的 内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要的，也 是不可能的。 ( 4 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级计 浙江工业大学硕士学位论文 算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资源规模不断 扩大、应用不断增加的情况下，网格系统的任务调度必须具有可扩展性，不致降低网 格系统的性能。 ( 5 ) 任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结构总 是不停地改变：有的资源出现了故障，有的新资源要加入到网格中，有些资源重新开 始工作等。总之，网格的动态性是明显的，所以任务调度必须适应网格的这种动态性， 从可利用的资源中选取最佳资源为用户提供应用服务。 2 1 2 任务调度的主要目标 网格调度的主要目的就是：为了完成用户提交的任务和满足用户对任务运行的要 求，把网格中所有可用资源( 计算资源、存储资源和网络资源) 与任务进行匹配，找到 最好最合理的资源分配方式和资源调度策略。在网格系统中，有大量的应用在运行， 有高性能计算方面的应用，也有针x 寸- b 性消费的个性化应用需求( 不需要强大的计算 能力和存储能力) ，而且随着商业化趋势的加强，后者占的比例将增加。另外，随着 网格技术向商业领域的逐渐延伸，网格服务市场的形成，网格的调度应充分考虑经济 因素，即要引入市场经济的规律。因此网格的调度设计必须在传统高性能计算和分布 式系统中的调度策略和技术的基础上，结合网格的具体特征。 调度问题一般可分为两大步： 第一步是在空间上对计算和数据进行分配，包括选取给定任务所需要的资源组， 将任务交给这些资源去执行，并分配相关的数据和计算等； 第二步就是在时间上和空间上为计算和通信进行排序，包括在计算资源上为不同 的任务进行排序，同时为不同任务之间的通信进行排序。 具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、服务质量q o s ( q u a l i t yo f s e r v i c e ) 、 负载均衡( l o a db a l a n c i n g ) 、经济原n ( e e o n o m i cp r i n c i p l e s ) 等。 ( 1 )最优跨度 跨度是一个最主要、最常见的目标，指的是调度的长度，也就是从第一个任务开 始运行到最后一个任务运行完毕所经历的时间。跨度越小说明调度策略越好。当用户 向网格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可见，实现最 优跨度是用户和网格系统的共同目标。 1 2 浙江工业大学硕士学位论文 ( 2 )服务质量 网格系统要为用户提供计算和存储服务时，用户对资源需求情况是通过服务质量 的形式反映出来的。任务管理与调度系统在进行分配调度任务时，必然需要保障网格 应用的服务质量。 ( 3 )负载均衡 在开发并行和分布式计算应用时，负载平衡是一个关键问题。网格系统更进一步 扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的调度。解决好系统的负 载均衡是一个非常重要的问题。 ( 4 )经济原则 网格环境中的资源广泛分布在地理上的，而且每个资源都归属于不同的组织，都 有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使用费 用也应是不相同的。市场经济驱动的资源管理与任务调度必须使消费双方( 资源使用 者和资源提供者) 互惠互利，才能使网格系统长久地发展下去，因此，任务调度还需 要考虑网格运行的经济问题。 本文算法研究涉及的目标包括时间跨度、负载均衡和经济原则。 2 2 网格调度模型 网格可以充分利用集成的资源形成一个大规模的计算池，在分布、异构、自治的 网络资源环境上构造动态的虚拟组织，并在其内部实现跨自治域的资源共享与资源协 作，有效地满足面向互联网的复杂应用对大规模计算能力和海量数据处理的需求。网 格计算的理想目标是网络上的所有资源易于协同工作，服务于不同的网格应用，实现 资源在跨组织( 自治域) 之间应用的共享与集成。o g s a i n 作为目前网格事实上的标 准，将w e b 服务的互操作模型引入网格研究中，利用w e b 服务作为网格资源新的抽 象形式和构造基础，使网格系统在虚拟组织层中形成一个以资源服务、共性服务和应 用服务构成的统一服务计算环境，即服务网格。无论是早期的计算网格还是目前的服 务网格，都面临着如何有效地管理和调度网格资源问题。 2 2 1 网格资源组织模型 网格利用互联网把分散在不同地理位置的计算机组织成一个“虚拟的超级计算 浙江工业大学硕士学位论文 机”，其中每一台参与计算的计算机就是一个“节点”，成于上万个这种节点纵横交织 成“一张网格”，相当于一部超级计算机无论是五层沙漏还是o g s a ，都距这种要 求很远，具体存在的问题有： ( 1 ) 标准化程度低，抽象性不足。 五层沙漏结构中，中间小，通用性较强，但是面向具体问题的，由于不同的网格 计算问题，其构成也不同，非标准化的成分太多；在o g s a 中，具体应用的实现是 服务的集成( 分布对象系统) ，服务的管理与互操作是标准化的，但具体的服务都是由 用户按规范根据具体应用提供的，因而o g s a 抽象出来的标准化成分太少 ( 2 ) 动态性不足。 这两种结构都没有提供关于网格基本资源的冗余结构的标准化支持，也没有提供 对大粒度的上层计算实体的冗余支持模型，因而，不论是底层设施还是高层的服务， 它们的动态加入和撤离都很困难。 ( 3 ) 应用开发困难。 困难来自两方面：一是上面所指的透明性差和标准化低，这两种体系结构下的网 格环境只提供少量功能，具体的网格应用还需编写大量代码；二是开发架构不兼容， o g s a 开发环境是基于服务的水平框架，这两种环境下的网格应用开发方式与普通应 用开发相差较大 ( 4 ) 基于服务，依赖服务。 0 g s a 网格支持的是“基于服务”的应用开发，网格应用的性能密切依赖于服务， 包括服务本身的性能、服务调度的性能，特别是服务本身的性能的影响，是直接关系 到具体服务( 用户开发或第三方产品) 的质量，这也相当于又一次将困难抛给了用户。 因此，有必要提出合理的网格资源组织模型，在一定程度上弥补目前流行的五层沙漏 结构和o g s a 存在的问题 目前网格计算环境中所使用的网格资源组织模型主要有如下几种： ( 1 ) 分层模型( h i e r a r c h i c a lm o d e l ) 【1 1 ，喝1 3 1 。目前采用分层模型的网格项目有 g l o b u s l 9 1 ，l e g i o n 1 4 1 ，d a t a g r i d 1 5 1 ，a p p l e s 1 6 1 。 ( 2 ) 抽象所有者模型( a b s t r a c to w n e rm o d e l ) 1 1 7 1 。目前还很少有实际的网格项 目采用该模式。 ( 3 ) 计算市场( 经济) 模型( 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 4 1 。网 格计算市场提供了合适的工具和服务允许资源请求者和资源提供者表达他们的需求， 1 4 浙江工业大学硕士学位论文 它可以和前两种模式结合使用来实现更有效的资源管理。 ( 4 ) 混合模型是以上几种模型的组合，如在计算市场模型里可以采用分层模型 的结构来组织分层的市场，抽象所有者模型里也可以采用市场的某些概念来协商资 源。 ( 5 ) 资源池模型i l 司。这种模型在一台中心服务器上记录计算环境中所有资源的 信息，资源池中对资源的描述是无序的，因此在c o n d o r 环境中只支持工作级调度， 不支持任务级并行，也不支持任务之间的通信。 ( 6 ) 网格资源空间的e v p 模型【1 9