（计算机应用技术专业论文）基于改进遗传算法的网格任务调度算法.pdf

山东大学硕士学侮论文 第1 章绪论 传统的任务调度和资源管理方法己经不能很好的适应分布式系统，特别是那 些用来进行大吞吐量计算的分布式系统。问题在于异构的资源使统一的分配算法 很难适用，资源的分布、归属等一系列问题导致需要很多的分配策略。对于上述 问题，我们需要开发和应用一种灵活的、通用的方法在分布式系统中进行资源管 理和任务调度。近几年兴起的网格计算( g r i dc o m p u ti n g ) 技术就是基于这种需 要应运而生的，这种技术不但具有传统的分布式计算所具有的优点，而且它还弥 补了许多的不足，是一个极具发展潜力的研究方向。可以说，因特网在2 0 世纪8 0 年代的诞生，9 0 年代初万维网技术的出现和迅速推广，2 1 世纪初网格计算技术 的提出，形成了互联网发展史上的三大里程碑。 1 1 研究背景和意义 网格计算是当今计算机科学领域最新兴起的一项有很高学术价值和应用价 值的研究课题。众所周知，高性能计算已经成为许多科学和工程实践的关键技术。 科学家们也越来越多地使用超级计算机来研究复杂现象，例如：可以用来预测复 杂的非线性现象，或者是在做实验之前，就可探索物理参数的变化规律，甚至还 可以用来模拟现实世界中所发生的某些事件。然而，尽管超级计算机的能力在不 断地增长，仍然有许多应用无法实现。因为这些应用往往需要处理能力强大的超 级计算机的支持，但是超级计算机造价极高，通常只有一些国家级的部门，如航 天、气象等部门才有能力配置这样的设备：另一方面，某些应用对计算的要求非 常高，即使是现在最大的超级计算机也无法提供它们所需的资源，这时就需要将 高性能计算依托i n t e r n e t 或其他高速网络，将遍布世界各个角落的能力千差万 别的计算资源联结在一起，形成大规模的可扩展的计算能力，因此，网格应运而 生。 任务调度是高性能计算中的一个重要组成部分，而随着网格的出现，在任务 调度中出现了很多新的特性，从而对传统的调度算法也提出了新的挑战。传统的 并行计算调度算法主要是调度一个应用程序的子任务到并行的计算机，主要目的 是减少计算时间；而对于网格环境，调度算法关心的主要问题是调度来自不同用 山东大学硕士学位论文 户的应用流到可用的计算资源上，从而最大限度地让网格系统得到最大的使用， 它追求的是调度的高吞吐率。作为目前网格计算事实上的标准，g l o b u s 并没有 具体实现任务调度算法，针对具体的应用网格，必须在高层设计出高效的任务调 度算法。然而现有的一些调度算法如b a c k f il 1i n g ，f c f s ( f i r s tc o m ef i r s t s e r v e ) 等并不能很好的适应网格资源的特性，如调度问题的n p 完全性，调度算 法的高效性，资源的异构性以及资源分配决策的并行性和分布性等，而遗传算法 因其自组织、自适应、自学习性和并行性等特点而非常适宜解决网格任务调度问 题。 如何使用网格资源高效地完成计算任务，是网格系统的研究重点之一。成熟 的网格管理系统首先解决了计算能力大小的限制，其次克服了地理位置的限制， 最后还打破了传统的共享或协作方面的限制。因此，网格系统研究的核心目的就 是突破以往强加在计算资源之上的种种限制，使人们可以以一种全新的更自由、 更方便的方式使用计算资源，解决更复杂的问题。这里首先要明确网格的使用模 式，即用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照 某种策略把这些任务分配给合适的资源。高效的调度算法或策略可以充分利用网 格系统的处理能力，从而提高应用程序的性能。网格任务调度问题属于n p 问题， 在网格计算系统中寻求较为切实可行的近似调度算法具有一定的难度。 1 2 国内外发展动态 网格计算源于美国和欧洲的研究计划，作为一种新兴的计算机技术，它正在 向世界其他国家和地区迅速传播，而且各国政府、相应的国际组织及大的企业己 经在网格研究领域投入了大量的资金。全球网格论坛( g l o b a lg r i df o r u l n ， g g f ) 、地区和国家的网格论坛也正在迅速的发展，学术交流活动正在积极地展 开，其中全球网格论坛已经成为网格标准制定与发布的主要机构。下面详细介绍 一下目前国内外网格的研究现状。 1 2 1 网格计算的研究现状 在美国，无论是政府部门还是商业机构，对网格的应用和发展都表现了极大 的兴趣。美国军方正规划实施一个宏大的网格计划，叫做“全球信息网格 2 山东大学硕士学位论文 ( g l o b a l i n f o r m a t i o ng r i d ) ”，预计在2 0 2 0 年完成。作为这个计划的一部分， 美国海军和海军陆战队已启动了一个耗资1 6 0 亿美元、历时8 年的项目，包括系 统的研制、建设、维护和升级。美国能源部的山地国家实验室的“先进战略计算 创新计划网格( a s c ig r i d ) 主要用于核武器研究。美国国防部和欧洲能源机 构等在两三年前先后采用了网格技术。美国能源部下属的国家能源研究科学计算 中心宣布，该中心近日与美国国际商用机器公司( i b m ) 达成协议，正式开始建 造美国能源部内部使用的计算机网格。据悉，美国能源部下属的阿贡、橡树岭等 国家实验室的超级计算机和存储资源都将陆续与该网格相连。国家能源研究科学 计算中心人士指出，把分布于这些国家实验室中的巨大信息资源进行有效整合， 将对基因组和天体物理等研究起到推动作用。 同时，随着网格研究在学术界的加速，信息产业界的大公司也相继公布了与 网格目标一致的研究开发计划。惠普、工明、微软、s u n 等公司最近取得共识， 支持x m l ，s o a p ，u d d i 等万维网标准，从而更有利于开发新一代的网络应用，即 万维网服务。其目的是将因特网上的资源和信息汇聚在一起，组合成企业和消费 者所需要的服务。i b m 最近宣布，将投资数亿美元，启动一个全公司的“网格计 算创新计划”；i b m 公司部署内部网格研究机构，以便于分散在美国、以色列、 瑞士等地的i b m 研究所人员共享计算资源。医药、化工、通信、电子、汽车等领 域的一些大公司，如辉瑞、爱立信、日立、宝马、联合利华、葛兰素威康、史可 必成等，都已经开始构造使用内部网格。 在国内，中国科技界已经开始向新一代互联网进军。科技部将通过8 6 3 计 划“高性能计算”专项的形式，在“十五”期间大力支持网格的研究和应用工作。 而中国科学院计算机研究所早已投入大量人力、财力从事网格研究，他们的网格 研究工作统称为“织女星网格”。中科院计算所六个研究室中四个研究室的研究 人员参与了“织女星网格”的工作。有关专家指出，与国外同行相比，我国目前 的研究成果已有很多独到之处。在迎接互联网第三次大浪潮的时代，我们不能再 错过时机，争取在网格技术研究中走在前面。我国的科学研究、国民经济和社会 发展也已对网格技术提出了很大需求，只是使用了不同的术语。比如，在银行界 叫“业务集中”，航空、船舶、汽车行业叫“广域虚拟设计环境 ，资源环境领 域叫“单一数据源”，电子商务和电子政务中叫“资源共享”与“协同工作”。 这些业务都感到目前的互联网技术已不够用，对网格技术建立起来的信息网格需 3 山东大学硕 j 学位论文 求是巨大的。 1 2 2 网格调度的研究现状 目前存在的网格任务调度相关研究中，大致可以分为网格资源管理与调度系 统的研究，及任务调度算法的研究，目前正在开发和研究的网格调度项目分别有： n i m r o d - g 网格资源代理。n i m r o d - g 允许在计算网格中管理和操纵任务。 它使用了一个经济模型来完成资源管理与调度。用户可以使用一种参数声明建模 语言或运行在网格中的g u i ( g r a p h i c a lu s e ri n t e r f a c e ) 接口来系统化参数。 n i m r o d - ( ；提供了网格节点的资源发现、资源交易、调度和资源分段运输、结果 收集、以及最终的结果演示给用户。n i m r o d - ( ；使用了g r a c e ( g r i da i c h i t e c t u r e f o rc o m p u t a t i o n a le c o n o m y ) 服务来动态地与资源拥有者代理交易，选出合适 的资源。g r a c e 使得n i m r o d - ( ；被用来在w w g ( w o r l dw i d eg r i d ) 中测试网上 调度参数扫描型应用任务。 n i m r o d - ( ；在资源管理上遵循的是分级的和计算的市场模型。它使用网格中 间件系统，如g l o b u s 等提供的服务来发现资源，并使用一个网络目录或者基于 数据组织的对象模型。它通过g r a c e 架构提供的计算经济服务支持资源预定和 o o s 。用户可以指定q o s 要求，如完成期限( d e a d l i n e ) ，预算( b u d g e t ) 和首 选的最优策略等。网格资源能力的估计是通过启发式和历史负载档案实现的。调 度策略是面向应用程序的，并且是按照用户定义的要求如d e a d l i n e ，b u d g e t 的 限制来驱动负载完成周期性的调度工作。 g l o b u s 盟1 网格计算工具箱。g l o b u s 提供了一个软件架构，使得应用程序可 以把分散的异类计算资源视为一个单个的虚拟机。g l o b u s 项目是一个美国的多 协会共同的研究工作，目的是为了建立计算网格。当前，g l o b u s 的研究者们正 与h i g h e n e r g y pp h y s i c s 和c 1 i m a t em o d e l i n gc o m m u n i t y 一起建造一个数据 网格。g l o b u s 系统中一个关键的元素就是g l o b u s 工具箱，它定义了构建计算 网格的基本服务和功能的实现架构。工具箱由一系列组件构成来实现基本服务， 如安全，资源定位，资源管理，数据管理，资源预定以及通信等。使用特定工具 的开发者或应用程序可以从中选择能够满足他们特定需要的服务。g l o b u s 是一 个典型的分层网格体系，高层的服务可以调用低层的核心服务来开发。它的重点 4 山东大学硕士学位论文 在于分级的集合网格组件和服务，鼓励使用低级的服务来开发高级的服务过程。 d a t ag r i d 项目集中在开发中间件服务来处理分布式的物理数据。其中核心 的中间件系统是扩展了数据网格能力的g l o b u st o o l k i t 。d a t ag r i d 项目有一 个分等级的机器组织，越低等级的机器，存储越少的数据。c e r n 是0 级，存储 了几乎所有与1 级相关的数据，而这些1 级的地区中心位于意大利，法国，英 国，美国和日本，它们存储了更少量的数据。此外，d a t ag r i d 有一个将资源模 型置于分等级的命名组织之上的可扩展体系。它并不支持任何的q o s ，所有资源 的信息存储在基于l d a p 的网络目录上。资源的分发是批量式的，并周期性的分 到网格的其他部分中。资源发现是分散式的和基于查询的。因而该调度程序使用 的是一个分级组织，并具有可扩展的调度策略。 在调度算法的研究方面，出现了以自然和人类社会的特征为基础的非传统网 格调度算法的研究，比如网格经济模型调度算法等啪。 基于市场供求关系的调度算法h 1 ，仿照日用品买卖市场调控策略来对计算资 源进行优化组合。具体的说，计算资源的“价格”被设定为介于资源的需求和提 供之间，当计算资源的“价格”确定后，对它们的分配过程就按照“先来先服务” 的原则进行，统一的由调度者进行调度。对于同一个计算资源，在实际的调度过 程中可能会由于所选的策略和所处的环境不同而被标上不同的“价格”，因而， 需要调度者进行策略级的全局优化。基于市场供求关系的调度算法利用了经济学 理论进行调度策略的分析，为其他调度算法提供了新颖的思路。 除此之外，还有一些算法思路比较新颖并且也具有较高的参考价值。如两阶 段( 2 - p h a s e ) 调度策略，是将一个计算任务的计算范围依次划分为l a n 间和 l a n 内两个阶段，并分别在l h n 间阶段和l a n 内阶段设立全局的、集中的任务 调度者，以负责制定该阶段的任务调度方案和监督任务执行情况。2 - p h a s e 式的 调度策略，的确在某种程度上反映了计算网格的网络组成，也为实施网络层次的 其他调度算法提供一定的支持。但是，由于仅用涉及l a n 的两层结构来刻画计算 网格是不准确的，所以，2 - p h a s e 调度策略还不能很好地描述计算网格的调度， 需要更深入的扩展。 国内外许多学者对网格任务调度的算法做了大量的研究工作，但是在网格计 算环境中，已有的任何调度模型、策略、调度目标函数和算法都不可能适宜一切 应用和环境；同一套调度机制在不同的条件下其表现性能不一定相同，因而，产 山东大学硕士学位论文 生的许多研究成果是近似的或者仅是具有启发性的方法。为了找到适宜的调度方 案，许多技术如图论，数学规划，排队论，遗传理论等等被用来解决这个问题。 人们在该领域进行了许多的研究，也取得了一些成果，但是要解决网格环境的任 务调度还需要进行大量的研究工作。 1 3 论文的组织结构 本文以介绍网格环境的概念和系统模型为起点，按照从理论到模型再到算法 应用的实现思路。首先根据现有网格中遗传调度算法的不足，提出了一个改进的 思路，并使用- j m a t l a b 算法作仿真，将现有的传统遗传调度算法同本文改进的算 法进行了比较，通过分析实验结果，验证了算法的有效性。按照研究工作完成的 顺序，本论文的组织结构和章节安排如下： 第1 章绪论，介绍本文的选题背景，研究的意义以及关于网格计算和网格调 度的研究现状，并对整个研究中所做的工作进行了说明。 第2 章网格计算任务调度概述，主要介绍了网格的本质和特点，网格的体系 结构，网格环境下任务调度的特点，组织模式，调度过程，评价标准，以及现有 任务调度算法介绍。 第3 章论述了基本遗传算法的基本原理、实现过程，以及云模型的原理、基 本概念，基本应用，针对遗传算法的缺陷，提出了一种改进的遗传算法，并给出 了改进思想与改进策略。 第4 章针对网格任务调度的特点，给出了改进遗传算法各部分实现过程，算 法执行流程，并通过编写算法进行模拟仿真，对本文提出的改进算法进行了对比 实验。最后给出了实现结果及分析。 第5 章对全文进行了总结，并提出了下一步的相关工作重点。 6 山东大学硕十学位论文 第2 章网格任务调度概述 2 1 网格计算 2 1 1 网格的本质和特点 关于网格的定义有很多，i a nf o s t e r 等人完善了网格定义，他们指出，网 格实际上是满足如下三个条件的系统咱1 ： 1 、协调非集中控制资源。网格整合各种资源，协调各种使用者，这些资源和使用者在 不同的控制域中。比如，个人电脑和中心计算机；相同或不同公司的不同管理单元；网格还 解决在这种分布式环境中出现的安全、策略、使用费用、成员权限等问题。否则，只能算本 地管理系统而非网格。 2 、使用标准、开发、通用的协议和界面。网格建立在多功能的协议和界面上，这些协 议和界面解决认证、授权、资源发现和资源存取等基本问题，否则，只算一个具体应用系统 而非网格。 3 、得到非平凡的服务质量。网格允许它的资源被协调使用，以得到多种服 务质量，满足不同使用者的需求，如系统响应时间、流通量、有效性、安全性和 资源复位，使得联合系统的功效比其各部分的功效总和要大得多。 网格是一个集成的计算与资源环境，它能够吸纳各种包括计算机、网络、数 据资料、仪器设备等在内的计算资源，并把它们转化成一种随处可得的、可靠的、 标准的同时还是经济的计算能力，它具有一些区别于其它计算系统的特性。以下 将从几个方面进行说明口1 ： 1 、异构性 网格涉及的资源类型多样，规模较大，分布在不同的地理位置。包括各类主 机、工作站甚至p c 机，它们是异构的，可运行在u n i x 和w i n d o w sn t 等各种操 作系统下，也可以是上述机型的机群系统、大型存储设备、数据库或其它设备。 2 、共享性 网格的共享性是指网格上的任何使用者都可以使用网格上的任何资源。网格 的根本特征就是分布资源的共享问题。此共享与以往所说的共享已有很大不同， 它更具有目的性，目的性体现在它已经不再是简单的资源互联和单一使用，而是 通过互联、组合、协作解决用户需要解决的问题，产生具有附加值的新服务、数 7 山东大学硕士学位论文 据、信息等资源，满足用户的新需求。 3 、动态性 网格的动态性是指网格资源不是一成不变的，使用者在某一时刻拥有的资源 和权限在下一刻都有可能发生变化。动态性包括动态增加和动态减少两个方面的 含义。 4 、可扩展性 网格的可扩展性要求体现在规模、能力、兼容性等几个方面。在网格的设计 与实现时必须考虑到新的资源能否很自然地加入到网格中，并和原来的资源融 合，共同发挥作用，而不降低网格计算的性能。 5 、安全性 由于开放了网络，提供了更多的工具和访问权限，必须确保它的安全性，安 全机制应该嵌入到网格软件最核心的层次上，包括登录认证、可信赖、完整性和 记账等方面的安全性，这是网格计算的难点，也是系统成败的关键。 2 1 2 网格的体系结构 1 、网格体系结构的概念 网格体系结构是关于如何建造网格的技术，包括对网格基本组成部分和各部 分功能的定义及描述、网格各部分相互关系与集成方法的规定、网格有效运行机 制的刻划。目前比较常见的网格体系结构可以归结为4 种形式：抽象层次结构、 积木块结构、概念空间结构和混合模式结构。 到目前为止，比较重要的网格体系结构有三个，第一个是l a nf o s t e r 在 1 9 9 8 年提出的五层沙漏结构，它是典型的抽象层次机构；第二个是在i b m 为代 表的工业界的影响下，考虑到w e b 技术的发展与影响，结合w e bs e r v i c e s 而 提出的开放网格服务结构田1 ，它是典型的混合模式结构；第三个是由g l o b u s 联 盟、i b m 和h p 于2 0 0 4 年共同提出的w e b 服务资源框架。 2 、五层沙漏结构 五层沙漏结构的主要特点是结构简单、层次清楚。该结构最重要的思想是以 “协议为中心，强调协议在网格资源共享与互操作中的地位。通过协议实现一 种机制，使得虚拟组织中的用户与资源之间可以进行资源使用的协商，建立共享 8 山东大学硕士学位论文 关系，并且可以进一步管理和开发新的共享关系。这一标准化的开放结构有利于 网格的扩展性、互操作性、一致性以及代码共享。如图2 1 所示，五层沙漏结 构自下而上分别为：构造层、连接层、资源层、汇聚层和应用层。该体系结构的 各层功能定义如下西1 ： 第一层为构造层( f a b r i c ) ：该层实现了基于底层特定资源的高层共享操作， 它提供了共享资源的本地控制接口。它关注的是与本地交互的控制接口，并提供 网格中可供共享的资源： 构造层 图2 - 1 五层沙漏结构图 第二层为连接层( c o n n e c t i v i t y ) ：该层定义了网格中网络处理的核心通信 与认证协议。通信协议使构造层资源间的数据交换成为可能；认证协议基于通信 服务提供了确认用户和资源身份的安全机制； 第三层为资源层( r e s o u r c e ) ：该层建立在连接层的通信和认证协议之上， 定义了一些关于安全协商、使用共享功能计费、监控等方面的协议； 第四层为汇聚层( c o l l e c t i v e ) ：这层的作用是将资源层提交的受控资源汇 聚在一起，供虚拟组织中的应用程序共享和调用； 第五层为应用层( a p p l i c a t i o n ) ：这层是网格用户的应用程序。应用程序通 过各层的a p i 调用相应的服务，再通过服务调用网格上的资源来完成任务。应用 程序的开发涉及大量的库函数，为便于网格应用程序的开发，需要构建支持网格 计算的库函数。 3 、开放网格服务结构( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ，o g s a ) 开放网格服务结构o g s a 是目前最新也最有影响力的一种网格体系结构，被 称作下一代的网格结构。在o g s a 中，一切事务都用服务来描述，如计算资源、 9 山东大学硕士学何论文 存储资源、网络资源以及其它逻辑实体都被描述成服务。为了使服务的概念更具 体化，o g s a 提出了网格服务( g r i ds e r v i c e ) 的概念，并撰写了网格服务的规 范文档来规范网格服务的命名、描述、创建、生命周期管理、通知、发现等与网 格服务管理、发现有关的机制。这种面向服务的模型统一了资源、信息、服务的 描述和使用，方便了系统的集成与管理。 o g s a 采用了网格和w e bs e r v i c e s 技术相结合的方法，取两者之长处。w e b s e r v i c e s 技术是目前流行的技术或集成解决方案，它的协议框架都经过标准化过 程，被各大主流i t 厂商所接受，并通过) ( m l 技术提供了很好的跨平台性和松散 耦合特性。网格要在一个动态的、跨管理域的、非集中控制的、广域分布式环境 下的虚拟组织里共享各种资源，网格思想是o g s a 的精髓，而o g s a 的外在表现 则是w e bs e r v i e e s 技术n 叫。这样，o g s a 平台能够和现有的各种技术很好的结 合，充分利用现有的各种技术和软、硬件资源，同时，能实现网格思想所提出的 目标。 4 、w e b 服务资源框架( w e bs e r v i c er e s o u r c ef r a m e w o r k ，w s r f ) o g s a 刚提出不久，g g f 及时推出了o g s i ( o p e ng r i ds e r v i c e s i n f r a s t r u c t u r e ，开放网格服务基础架构) n 草案，并成立了o g si 工作组，负 责该草案的进一步完善和规范化。o g s i 是作为o g s a 核心规范提出的，其1 0 版于2 0 0 3 年7 月正式发布。o g s i 规范通过扩展w e b 服务定义语言w s d l 2 1 和x m ls c h e m a 的使用来解决具有状态属性的w e b 服务问题。它针对网格服务 定义了一套标准化的接口，主要包括：服务实例的创建、命名和生命期管理、服 务状态数据的声明和查看、服务数据的异步通知、服务实例集合的表达和管理以 及一般的服务调用错误处理等。 o g s i 封装资源的状态，并将具有状态的资源建模为w e b 服务，这种做法引 起了“w e b n 艮务没有状态和实例”的争议，同时某些w e b 服务的实现不月p - 云撅, 4 4 1 足 网格服务的动态创建与销毁的需求。o g s i 单个规范中的内容太多，所有接口和 操作都与服务数据有关，缺乏通用性，而且o g s i 规范没有对资源和服务进行区 分。o g s i 使目前的w e b 服务和x m l 工具不能良好工作，因为它过多地采用了 x m l 模式，这可能带来移植性差的问题。另外，由于o g s i 过分强调网格服务和 w e b 服务之间的差别，导致了两者不能更好地融合在一起。上述原因促使了w s r f 的出现。 1 0 山东大学硕士学位论文 w s r f 草案规范于2 0 0 4 年年初推出，可以看作是o g s a 的进一步发展，但 目前对其标准的讨论仍存在一些争议。尽管如此，w s r f 中的一些思想还是值得 借鉴的。w e b 服务资源结构是表示有状态资源与w e b 服务之间关系的方法。w e b 服务资源框架是一组被提议的w e b 服务规范，这些规范使程序员可以声明和实 现w e b 服务与一个或者多个有状态资源之间的关联，它们描述了定义资源状态 的视图以及将它与w e b 服务描述相关联来形成w e b 服务资源总的类型定义的 方法。它们也描述了如何通过w e b 服务接口来访问w e b 服务资源的状态，并且 定义了与w e b 服务资源分组和寻址相关的机制。 2 1 3 网格计算与任务调度 网格计算是目前研究最深和实践最多的一种网格，主要针对前沿科学研究和 大型行业应用，可共享和整合地理上分布的计算资源n 引。作为一种为大型、复杂 应用而设计的新兴技术，计算网格需要能够很好地支持高性能需求和分布特性。 为了更好地为用户提供高质量、安全的计算服务，必须解决资源管理、任务调度、 安全、容错等一系列关键技术。 图2 - 2 网格任务调度过程 图2 - 2 4 1 是个简单的网格任务调度过程。任务提交者将任务提交给任务调 度者，任务调度者有一个任务序列和资源信息提供者，任务调度者可以从任务序 列和资源信息提供者那里得到相应的任务描述信息和资源信息。通过任务调度者 中的任务一资源匹配者来完成任务一资源对的匹配，然后通过g r a m ( g l o b u s 山东大学硕士学何论文 r e s o u r c ea 1l o c a t i o nm a n a g e r ) 和g a s s ( g l o b a la c c e s st os e c o n d a r ys t o r a g e ) 来将任务提交和传输到合适的远程节点。g l o b u sg a t ek e e p e r 进行相应的认证 后将任务提交给g l o b u s 任务管理者，任务管理者通过本节点调度者来调度这个 任务。任务完成以后，通过g a s s 将这个任务结果返回给任务提交者。 任务和资源的匹配是任务调度算法必须完成的。针对一个任务，从网格系统 中发现可满足该任务资源需求的可用资源集，满足该条件的计算资源可能不止一 个，但是该任务在这些资源上执行所获得的性能、付出的代价可能不一样。同样 都是满足条件的资源，但是提供给使用者的质量会存在差异。任务调度首先要根 据任务的需求，选择满足条件的资源，然后从满足条件的资源当中根据主要因素 和选择策略选择一个更加合适的资源分配该任务。任务获得满足条件的资源后， 可以在该资源上运行，并处在资源本地的任务管理机制的管理之下，任务在资源 上运行结束之后，把占用的资源还给网格管理机构，网格任务管理模块把任务执 行的结果和相关信息告诉任务的提交者，从而实现计算网格共享地理上分布的资 源协同完成某个任务的目标。 网格计算环境的强大能力最终是通过网格上任务的运行性能来体现的。为了 获得较高的运行性能，需要较优化的调度策略，以便在任务和资源之间做出合理 的匹配，并可以在运行过程中动态调整，达到对任务合理而高效的调度运行。网 格调度是极其复杂的问题，因为网格中包含大量异构资源，而且资源动态变化， 多个任务引起资源竞争，如何充分利用网格中计算资源进行高效率合理地使用是 调度的研究范畴，任务调度问题一直以来都是计算网格技术的关键技术和难点， 对它的研究在基础理论和系统开发等方面都具有很大意义。 2 2 网格环境下的任务调度 由于网格系统的异构性和动态性，以及运行于网格系统之中的应用程序对于 资源的不同需求，使得任务调度变得极其复杂，不好的任务分配策略，将会增加 任务的执行时间、降低整个网格系统的吞吐量。 2 2 1 任务调度系统的特点 网格环境下，构成调度问题的基本因素n 朝包括：网格用户的任务、网格资源 1 2 山东大学硕士学位论文 以及在这些资源上为网格用户的任务所提供的规则和策略。一般网格任务调度模 型可以简化如图2 - 3 ： 图2 - 3 网格任务调度模型 在网格环境下，任务和资源的数目巨大，任务和资源之间的匹配关系也比较 复杂。一个任务可能包含多个活动，各个活动之间可能存在依赖关系。因此，网 格任务调度系统也必须具有以下特点n 1 ： 1 、任务调度是面向异构平台的。由于网格的异构性导致网格环境下的任务 调度也必须是异构的。 2 、任务调度是大规模的、非集中式的。由于网格系统是一个大到整个 i n t e r n e t 的分布式系统。要实现一种全局的统一集中的任务调度管理是根本不 可能的。因此，网格的任务调度必须以分布、并行方式进行任务的管理与调度。 3 、任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点 的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要 的，也是不可能的。 4 、任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级 计算机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资源规 模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展性， 不致降低网格系统的性能。 5 、任务调度能够动态自适应。网格中的资源不但是异构的而且网格的结构 总是不停地改变：有的资源出现了故障，有的新资源要加入到网格中，有些资源 重新开始工作等。总之，网格的动态性是明显的，所以任务调度系统必须适应网 格的这种动态性，从可利用的资源中选取最佳资源为用户提供应用服务。 山东大学硕士学位论文 2 2 2 网格任务调度的组织模式 网格环境下的任务调度可以分为相互间存在通信的任务组的调度和相互独 立的任务组( m e t at a s k ) 的调度两类。资源管理使用调度策略来确定请求以及 任务调度的相关顺序。调度策略的分类如图2 4 所示n 副。 图2 - 4 调度策略的分类图 对于相互间存在通信的任务调度，现在常用的方法是沿用传统的d a g 图进 行调度，即将相互间存在数据通信的任务组看作一个有向无环图，针对这个有向 无环图做出调度策略。但对于大规模、多管理域的网格系统，d a g 图调度方式可 能相当困难，实际上经常采用预置与合作配置的方法来保证任务的执行在网格环 境下通常考虑的是一组相互独立、任务之间没有通讯和数据往来的元任务( m e t a t a s k ) 映射。由于任务调度是n p 完全问题，解决这类问题常用启发式算法，启 发式算法包括模拟退火算法、遗传算法、蚂蚁算法和禁忌算法等。针对异构计算 环境中的元任务调度，动态启发式算法又分为在线模式( o n - 1i n e ) 和批模式 ( b a t c h - m o d e ) 两种。在线模式是只要任务到来就加以映射，而批处理模式则是 把任务收集起来等映射事件到来后才对这些任务进行集中映射。相比而言，批模 式得到了大量的资源信息，从而可以做出更合理的任务映射策略。 2 2 3 网格任务的调度过程 一个典型的网格调度至少应包括作业提交、资源发现、资源预约、资源动态 信息查询、制订调度策略以及运行时监控这六个过程m 1 。 1 、作业提交 用户作业的执行通常会涉及到分布式数据、网络资源、存储资源和软件资源 等，另外，用户可能对服务的质量有一定要求，如任务必须在什么时间之前完成。 1 4 山东大学硕士学位论文 这些资源需求可以通过脚本语言描述( 如r s l ) 提交给网格调度系统。 用户或作业定义了需求以后就被提交给网格调度服务，网格调度服务负责 根据这一需求找到合适的资源。作业需求描述包含了必要的信息用来判断资源是 否能够满足这一需求。作业需求描述主要包含三个方面的信息，一是作业本身的 属性，如它包含多少子任务，相互之间的先序关系，一般被并行化理论抽象为d a g 图的形式；二是作业的约束条件，如完成的时间期限，服务质量等，可能还有在 网格经济模型中“费用”和“代价 的概念；三是对实际静态资源的需求，如作 业运行的操作系统、最小内存、网络带宽等。 2 、资源发现 网格调度系统目的就是为用户提交的“需求清单”找到合适的资源，包括为 作业进行资源调度、资源预约。无论是系统进行资源自动选择还是由用户参与的 交换选择，都需要考虑到用户和资源拥有者两方面的要求，在满足用户需求的条 件下节约资源的使用。这一过程主要是发现潜在资源的静态信息，即为用户的作 业需求找到匹配的资源组合。调度器收到用户作业的需求报告，并将其中的内容 解析出来，网格调度系统通过网格信息服务收集网络上可用的网格资源。此时， 调度系统仅仅进行简单匹配，并不判断这些资源是否处于可用状态。 3 、资源预约 经过资源发现阶段可能会得到针对一个作业的许多合适的网格资源，资源预 约n 印的任务就是进一步筛选，使得只有一部分合适的资源能够进行进一步地匹 配。这一过程可以通过许多启发式原则进行自动筛选或者在用户的干预下进行。 例如，用户可能需要在满足任务运行条件的网格资源中选择费用最小的资源等 等。 4 、资源动态信息查询 作业运行时调度系统需要收集当前的资源信息并依次进行资源使用情况的 预测，如当前资源是否是可用状态，若不可用，则需预测什么时候可用。如果当 前考查的资源不满足条件，则需要返回上一步对候选的下一个资源组合进行考 查。 5 、制订调度策略 基于资源可用情况、网络带宽和数据准备情况，调度服务判断哪个资源组合 对作业来说是最合适的。这一步骤需要用到一些评价模型来决定资源组合，制订 山东大学硕_ 1 学位论文 调度策略，发出资源预约请求，当某一个资源预约过程失败时，那么调度器会选 择后备的服务继续这一预约过程。 6 、运行时监控 复杂的作业运行时间一般比较长，用户应该有权利在任务提交后到执行完毕 的时间内查询任务的运行状态。这是通过作业运行时监控服务来管理的，监控服 务负责的另一个职责是当作业运行满足一定条件时调度其它服务引起作业的下 一个流程，在作业调度服务失败时重新初始化作业运行。 2 2 4 网格任务调度评价标准 网格任务调度方案的优劣可以从以下几个方面来衡量：最优跨度( o p t i m a l m a k e s p a n ) 、服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a d b 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 ) 等。 1 、最优跨度。跨度是一个最主要的最常见的目标，指的是调度的长度，也 是从第一个任务开始运行到最后一个任务运行完毕所经历的时间。跨度越短说明 调度策略越好。当用户向网格系统提交任务后，最大的愿望是网格系统尽快完成 自己的任务。可见，实现最优跨度是用户和网格系统的共同目标。 2 、服务质量。网格系统要为用户提供计算和存储服务时，用户对资源需求 情况是通过q o s 形式反映出来的，任务管理与调度系统在进行分配调度任务时， 保障网格应用的服务质量是完全应当的。 3 、负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题， 网格系统更进一步扩展了这个问题。 4 、经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都 归属于不同的组织，都有各自的资源管理机制和政策。根据现实生活中的市场经 济原则，不同资源的使用费用也应是不相同的。市场经济驱动的资源管理与任务 调度必须使消费双方( 资源使用者和资源提供者) 互惠互利，才能使网格系统长久 地发展下去。 2 2 5 现有任务调度算法介绍 网格任务调度就是将“合适”的任务分配到“合适”的资源上去运行，因此 1 6 山东大学硕士学位论文 不同的网格任务调度系统有不同的调度目标。有的是为了获得尽可能高的资源使 用率和吞吐量，如启发性智能任务调度n 引；有的是追求成本最低，如b u y y a 提 出的一种基于应用经济模型的优化调度模型，其目的是在资源的拥有者和使用者 之间建立一种“交易”，以尽可能低的费用满足资源使用者进行计算任务的最低 要求乜引。 1 、启发式算法 网格计算的任务调度是一个n p 完全问题。近几年来，人们提出了很多启发性 智能化算法，诸如神经网络、模拟退火胁3 、禁忌搜索、遗传算法乜别、蚂蚁算法 等，它们毫无争议地成为解决网格调度问题的锐利工具。下面简单介绍几种启 发式算法。 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 是一种基于金属退火的机理建立 的全局最优化方法，它能够借助随机搜索技术从概率的意义上找到目标函数的全 局最小点，具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解 啪2 引。它不同于一般局部搜索算法之处在于：它以一定的概率选择邻域中费用值 大的状态。在模拟退火算法中，每两个温度之间的状态点是无关的。从理论上说， 任何一个温度的马氏链都可逐渐达到平稳分布。即从一个状态到另一个状态随着 迭代步数的增加渐渐不依赖于起点状态，且在每一个状态的概率服从平稳分布。 这种特性可以用来克服遗传算法中因为过于强调两代之间的进化关系而导致最 优解遗失的缺点。 人工神经网络( a n n ) 是对人类大脑的一种物理结构上的模拟，即以计算机 仿真的方法，从物理结构上模拟人脑，以使系统具有人脑的某些智能。在众多的 a n n 模型中，多层前馈神经网络模型是目前应用最为广泛的模型。用反向传播学 习算法( 简称b p 算法) 可以实现多层前馈神经网络的训练，b p 算法具有简单和 可塑性的优点，但是b p 算法是基于梯度的方法，这种方法的收敛速度慢，且常 受局部极小点的困扰，通常采用遗传算法把神经网络的结构优化和权值学习合并 起来一起求解，以此克服该缺陷。 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是将问题的求解表示成染色体 ( c h r o m o s o m e ) ，从而构成种群。将它们置于问题的环境中，根据适者生存的原 则，从中选择出适应环境的染色体进行复制，通过交叉、变异产生出新一代更适 应环境的染色体群，这样一代一代地不断进化，最后收敛到一个最适合环境的个 【i i 东大学硕十学位论文 体上，求得问题的最优解瞳5 】。 蚂蚁算法( a n ta l g o i r t h m s ，从) 是一个比较新的启发算法，它是基于蚂蚁 的行为。当蚂蚁在寻找食物时，每个走动的蚂蚁都会在其经过的路上释放一些信 息素，那么在较短路径上的信息素会很快地增加，每条路径上信息素的数量，会 反映出其他蚂蚁选择该路径的概率最终，所有的蚂蚁将选择最短的路径蚂蚁算 法固有的并发性和可扩充性，使它非常适合用于网格计算的任务调度在同一时 间内，所有影响资源状态的因素都能由一个事情，即信息素描述。那么调度程序 就能非常简单、快速地获得预测结果。 2 、基于a g e n t 的任务调度 a g e n t 技术源自于人工智能，其概念在6 0 年代就已提出来，真正的发展在 9 0 年代，现在正向计算机领域的各方面渗透。面向a g e n t 技术是面向对象技术 的发展和飞跃，它为复杂、开放、分布系统的开发和实现提供了新途径。面向 a g e n t 技术的智能性、代理性、学习性、合作性、持续性使它非常适合网格计算 及其任务调度的实现。 基于a g e n t 的任务调度其基本设计思想是：将每个网格资源节点均封装成 为一个a g e n t ，把网格系统看成是一种多层次a g e n t 系统的集合。这样，所有分 布于网格系统中不同地方的网格资源节点( 如一个机群) 就构成了底层的a g e n t 系统，它们为基于网格的应用程序提供高性能计算能力，于是，调度问题被简化 成如何在各a g e n t 之间分配计算任务并随时根据a g e n t 的变化情况进行调整， 以及在各a g e n t 内如何进行子任务的继续分配。这样的层次结构具有高度的可 扩展性，便于在网格这样的庞大异构环境中运用。 多a g e n t 网格任务调度模型中，计算资源可以选择某个代理进行注册，每 个代理最终管理一组资源，响应用户的任务请求。由于可用带宽、主机性能等原 因，各个代理的资源利用率、负载等不尽相同，可能会出现某些代理服务器负载 过重，有些代理服务器处于轻负载运行状态。一个代理接收到一个新的计算任务 以后，如果自身负载过重，或者自身的可用资源难以满足新的计算任务的要求， 就会根据负载平衡算法，通过a c p ( a g e n tc o m m u n i c a t i o np r o t o c a l ) 把计算 任务交给其他代理完成乜副。 3 、基于成本的任务调度 在网格资源调度算法中，曾提出一种基于应用经济模型的优化调度模型乜引， 山东大学硕士学位论文 其目的是在资源的拥有者和使用者之间建立一种交易，以尽可能低的费用满足资 源使用者进行计算任务的最低要求。 在网格环境中，用户通过服务请求代理提交自己的任务，然后进行q o s ( 服 务质量) 请求解析，得出具体的资源需求，再交由调度器和状态估计器进行处理， 调度器在调用资源优化匹配模块进行检测及利用算法进行资源优化匹配后，再交 由交易代理处理，最后由发布代理将任务调度到选定资源上运行。该模型在经济 原则的基础上为调度问题引入了成本( c o s t ) 概念。其核心思想是把诸如c p u 、 存储器、带宽等不同类型资源的使用情况都转变成单一的成本，并按照总成本最 小化的目标，对网格系统中的任务进行调度1 。 4 、基于p e t r i 网的的任务调度 p e t r i 网理论是由德国的c a r l a d a mp e t r i 博士提出的，主要研究分布式系 统中并发、冲突现象的一种理论，它是描述和分析离散事件动态系统的一种模型 工具。它综合了数据流、控制流和状态转移，能自然地描述并发、同步、资源争 用等系统特性，而且本身自含执行控制机制，集规范表示与执行于同一模型。同 时，p e t r i 网是严格定义的数学对象，借助数学开发的p e t r i 网分析方法和技 术，既可用于静态的结构分析，又可用于动态的行为分析。 5 、其他任务调度算法 除了上述调度算法之外，人们还提出了很多异构系统的启发调度算法，有不 少论文试图把这些算法用于网格环境。c a s a n o v ahl e g a n d 等人提出了一个扩展 的s u f f e r a g e ，i l q x s u f f e r a g e ，可在网格环境中调度参数扫描应用昭引。t a k e f u s a 等人提出了一个期限调度策略，可适用于多客户多服务器( m u l t i c l i e n t m u l t i s e r v e r ) 方式，并增加了能够改进算法性能的负载纠错( l o a dc o r r e c t i o n ) 和退却( f a l l b a c k ) 机制乜引。s