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

五邑大学硕士学位论文 捅斐 随着计算机技术的飞速发展，人们为了充分利用广域网上的分布式资源，提出 了网格计算的概念。网格计算是分布式计算的一种，其目的是建立大规模计算和海 量数据处理的通用基础支撑结构，将网络上的各种高性能计算机、服务器、p c 、信息 系统、海量数据存储和处理系统、应用模拟系统、虚拟现实系统、仪器设备和信息 获取设备集成在一起，为用户提供一个统一的、整合的、虚拟的计算环境，实现跨组 织的资源共享、管理与访问。在网格系统中，任务调度系统是重要组成部分，它根 据任务信息采用适当的策略把不同的任务分配到相应的资源节点上去运行。由于网 格系统的异构性和动态性，以及运行于网格系统之中的应用程序对于资源的不同需 求，使得任务调度变得极其复杂，它在一般形式下是一个n p 完全问题。 量子遗传算法是一种新的优化算法，是由量子计算和遗传算法相结合而产生的。 量子遗传算法建立在量子态矢量表示的基础之上，将量子比特的概率幅表示为应用 于遗传算法中染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量子 逻辑门代替遗传操作，实现染色体的更新，从而实现目标的优化求解。通过分析量 子遗传算法，本文提出了改进的量子遗传算法，提高了量子遗传算法的搜索效率， 并通过多峰值函数求解问题证明了其正确性和优越性。 本文通过量子遗传算法及其改进算法在网格任务调度中的应用，以减少任务调 度时间为主要目标，增加资源利用率为次要目标，提出了基于量子遗传算法及其改 进算法的网格任务调度算法。算法采用量子比特间接编码的方式，通过有向无环图 ( d a g ) 来描述子任务之间的依赖关系，根据深度值来给子任务的执行顺序进行排 序。本文在研究了仿真软件s i m g r i d 之后设计了模拟程序对算法进行了性能评估和验 证。通过与基于遗传算法的任务调度算法比较分析，验证了本文算法的正确性。仿 真结果显示，本文中的算法不仅缩短了任务完成时间，而且改善了资源利用率，提 高了任务调度性能。 关键词：网格；量子遗传算法；任务调度；遗传算法；s i m g r i d 五邑大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , p e o p l ep r e s e n tac o n c e p to fg r i dc o m p u t i n g t om a k ef u l lu s eo ft h ed i s t r i b u t e dr e s o u r c e si nw o r l dw i d ew e b g r i dc o m p u t i n gi sat y p eo f d i s t r i b u t e dc o m p u t i n g ，w i t ht h ep u r p o s et oe s t a b l i s hau n i v e r s a lf o u n d a t i o n a ls t r u c t u r eo fc o s m i c a l l y c o m p u t i n ga n dm a s sd a t ap r o c e s s i n g a c c o r d i n gt oi n t e g r a t eh i g hp e r f o r m a n c ec o m p u t e r s ，s e r v e r s ， p e r s o n a lc o m p u t e r s ，i n f o r m a t i o ns y s t e m s ，d a t as t o r a g ea n dp r o c e s s i n gs y s t e m s ，y i r t u a ls y s t e m s ， a p p a r a t u sa n ds oo nw h i c hi sd i s t r i b u t e dr e s o u r c ei nt h en e t w o r k ，i tp r o v i d e st oau n i f o r m ，i n t e g r a t e d a n dv i r t u a l i z e dr e s o u r c ef o ru s e r sa n dr e a l i z e st h er e s o u r c e ss h a r e i n g ，m a n a g e m e n ta n da c c e s sa c r o s s d i f f e r e n to r g a n i z a t i o n s t a s k ss c h e d u l i n gb e t w e e nr e s o u r c e si so n eo ft h em o s ti m p o r t a n tp a r t si ng r i d c o m p u t i n g a c c o r d i n gt ot a s k si n f o r m a t i o na n ds u i t a b l es c h e d u l i n gp o l i c y , i ts u b m i t st a s k st ot h e d i f f e r e n tr e s o u r c e s b e c a u s eo fd y n a m i ca n dh e t e r o g e n e o u sc h a r a c t e r so fg r i d ，a n dt h ed i f f e r e n t r e q u i r e m e n t so fr e s o u r c e si nt h eg r i da p p l i c a t i o n s ，g r i dt a s k ss c h e d u l i n gb e c o m e sm o r ec o m p l i c a t e d ， a n di ti sat y p i c a ln p p r o b l e m 。 q u a n t u mg e n e t i ca l g o r i t h m ，w h i c hi sb a s e do nt h es t a t ev e c t o rd e n o t a t i o no fq u a n t a ，i st h e c o m b i n a t i o no fq u a n t u mc o m p u t a t i o na n dg e n e t i ca l g o r i t h m 。q u a n t u mg e n e t i ca l g o r i t h mu s e sq u b i t s t od e n o t ec h r o m o s o m ei n s t e a do fb i n a r yo rd e c i m a lc o d i n gi ng e n e t i ca l g o r i t h m ，a n dq u a n t u mu p d a t e g a t ea st h eg e n e t i co p e r a t i o n i nt h i sp a p e r , am o d i f i e dq u a n t u mg e n e t i ca l g o r i t h mi sp r e s e n t e d u s i n g m o d i f i e dq u a n t u mg e n e t i ca l g o r i t h mo b t a i n st h eg o o ds o l u t i o n si ns o m eo p t i m i z a t i o no fm u l t i - p e a k f u n c t i o n s t h et e s tr e s u l t sf o rs o m ei m p o r t a n tf u n c t i o n ss h o wt h a tm o d i f i e dq u a n t u mg e n e t i c a l g o r i t h mi sm o r ee f f e c t i v ea n df e a s i b l e 。 t h i sp a p e rp r e s e n t ss c h e d u l i n ga l g o r i t h m sb a s e do nq u a n t u mg e n e t i ca l g o r i t h ma n dm o d i f i e d q u a n t u mg e n e t i ca l g o r i t h m ，w h o s ep r i m a r ya i mi st og e tt h es h o r t e s tm a k e s p a n ，a n dt h es e c o n d a r y a i mi st oi m p r o v et h er e s o u r c e su s ef a c t o r i n d i r e c tq u a n t u mb i tc o d i n gm e t h o di sa d o p t e di nt h e s e a l g o r i t h m s i tu s e st h ed a gt od e f i n et h er e l a t i o n s h i pb e t w e e ns u b t a s k s ，a n dr a n k st h es u b t a s k s a c c o r d i n gt ot h ed e p t h - v a l u e 。s o m es i m u l a t i n gp r o g r a m sa r ed e s i g n e dt ov a l i d a t ea l g o r i t h m sa f t e r f i n i s h i n gt h es i m g r i ds t u d y i tc o m p a r e st h e s ea l g o r i t h m sw i t hs c h e d u l i n ga l g o r i t h mb a s e do ng e n e t i c a l g o r i t h mt os h o wt h e i rc o r r e c t n e s s s i m u l a t i o nd e m o n s t r a t e st h a tt h e s ea l g o r i t h m sn o to n l yg e tt h e s h o r t e rm a k e s p a nb u ta l s ot h eh i g h e rr e s o u r c eu t i l i z a t i o n k e yw o r d s ：g r i d ；q u a n t u mg e n e t i ca l g o r i t h m ；t a s ks c h e d u l i n g ；g e n e t i ca l g o r i t h m ；s i m g r i d i l 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成，完成论文所用的 一切资料均已在参考文献中列出。 作者：李贵海 签字：馘海 2 0 0 8 年4 月1 5 日 五邑大学硕士学位论文 1 1 研究背景及意义 第一章绪论 今天，i n t e r n e t 的普及和高性能计算机的利用，以及低成本的高速网络正在改 变着我们使用计算机的方式。这些新技术已经使得利用不同地域分布资源来解决大 规模的科学、工程、商业问题成为可能。通过这样的研究导致了一个为大家熟悉的 网格计算的产生。网格计算是指在动态的、异构的、广域的虚拟组织中进行的资源 协同共享和问题求解【l 捌。 在现代科学研究和应用领域，有海量的重要数据资源，例如生物计算、全球气 候模拟、高能物理、大规模的信息和决策支持系统等，数据量达到几十t e r a b y t e 至 p e t a b y t e 的级别，与此同时，地理上广泛分布的各个领域的用户都希望能够访问这 些数据。虽然互联网的出现和广泛使用使得人们能够大范围的共享各种信息，但是 这并不能满足用户的需求，因为用户的需求不仅仅是单纯的共享浏览信息，而是要 进行大量的数据分析和处理。要分析这些庞大的数据，其分析方法往往比较复杂并 且计算量大，需要万亿次、甚至更大规模的计算能力。如此庞大的计算量和数据量， 即使是计算能力强大的超级计算机也无法胜任。另一方面，随着信息技术的飞速发 展，各个组织都部署了相当多的信息处理设备和仪器，而其中相当多的资源在大部 分时间是闲置的，没有被充分利用，在这种背景下，人们提出了网格的构想，希望 通过基于互联网的网格计算来解决上面应用中所面临的问题【3 】。 1 1 1 网格概述及特点 网格是借鉴电力网的概念提出来的，网格的最终目的是希望用户在使用网格计 算能力时，就如同现在使用电力一样方便。人们在使用电力时，不需要知道它是从 哪个地点的发电站输送出来的，也不需要知道该电力是通过什么样的发电机产生的， 人们使用的是一种统一形式的“电能。网格也希望给最终的使用者提供的是与地理 位置无关、与具体的计算设施无关的通用的计算能力。网格和电力网都有各自资源 的消费者和资源提供者，对于电力网来说资源提供者就是发电站，对于网格来说资 源提供者是高性能中心、高性能计算机等：对于电力网来说资源消费者就是各种消 1 五邑大学硕士学位论文 耗电能的设备，对于网格来说资源消费者就是使用网格计算能力求解问题的用户。 不管是电力网还是网格，他们都有覆盖范围广泛，而且组成资源多样的特点。正同 电力网中需要有大量的变电站等设施对电网进行调控一样，网格中也需要大量的管 理结点来维护网格正常运行。与电力网相比，网格的结构更复杂，需要解决的问题 也更多，但是它也会给我们带来更大的便利和帮助。 网格( g r i d ) 是一个集成的计算与资源环境，或者说是一个计算资源池【4 1 。网格能 够充分吸纳各种计算资源，并将它们转化成一种随处可得的、可靠的、标准的同时 还是经济的计算能力。除了各种类型的计算机，计算资源还包括网络通信能力、数 据资料、仪器设备、甚至是人等各种相关的资源。基于网格的问题求解就是网格计 算( g r i dc o m p u t i n g ) 。这里给出的网格和网格计算的概念是相对抽象的，而且是广义 的定义，网格计算还有狭义的定义。狭义网格定义中的网格资源主要是指分布的计 算机资源，而网格计算就是指将分布的计算机组织起来协同解决复杂的科学与工程 计算问题。狭义的网格一般被称为计算网格( c o m p u t a t i o n a lg r i d ) ，即主要用于解决 科学与工程计算问题的网格。根据求解问题的特点，人们又提出了多种名称的网格， 比如以数据密集型问题的处理为核心的数据网格，以解决科学问题为核心的科学网 格【5 】，以全球地理系统模型问题求解为主要目的的地理系统网格等等。此外还有地 震网格、军事网格、n a s a ( n a t i o n a la e r o n a u t i cc sa n ds p a c ea d m i n i s t r a t i o n ) 的i p g 等行业网格。 不管是狭义还是广义的网格，其目的不外乎是利用互联网把分散在不同地理位 置的计算机组织成一台“虚拟的超级计算机”，实现计算资源、存储资源、数据资源、 信息资源、软件资源、通信资源、知识资源、专家资源等的全面共享。在网格上做 计算，就像下围棋一样，不是单个棋子完成的，而是所有棋子互相配合形成合力完 成的。传统互联网实现了计算机硬件的连通，w e b 实现了网页的连通，而网格试图 实现互联网上所有资源的全面连通。 网格计算系统与分布式系统和并行系统相比有很多相同的特征，但与二者又有 着非常重要的区别。与分布式系统类似，位于多个管理域中的超级计算机通过不可 靠的网络进行连接，并且需要对广域分布的动态资源进行集成，但是网格计算系统 对高性能的要求使其编程模型及接口与分布式系统有极大的差别。网格计算系统作 为并行系统还需要进行超级计算机之间的通信调度以满足应用对性能的要求，然而 由于网格计算系统的异构性以及动态性，现有的并行计算技术不能很好的适应这种 2 五邑大学硕士学位论文 需求。 一般而言网格计算系统具有以下几个特点6 1 ： ( 1 ) 分布性 组成网格的资源可能是计算资源、存储资源、数据资源、仪器资源等，它们分 布在地理位置不同的许多地方，而网格工作流中的关键技术研究并不是集中在一起 的。在这种分布环境下，需要解决网格资源针对任务的分配和调度问题，传输和通 信问题，人与系统以及人与入之间的交互协同问题，网格应用在分布环境中的自动 执行和协作问题。 ( 2 ) 异构性 组成网格的资源是异构的，对于计算资源，有不同类型的计算机，不同的计算 方式，不同的计算接口，不同的系统架构；同样，对于存储资源和其他资源，也面 临着这样的问题。因此，网格既具有利用资源的异构特点进行处理的能力，也具有 提供一致资源管理的能力。 ( 3 ) 共享性 网格的共享性是指网格上的任何使用者都可以使用网格上的任何资源。网格的 根本特征就是分布资源的共享问题。此共享与以往所说的共享已有很大不同，它更 具有目的性，目的性体现在它已经不再是简单的资源互联和单一使用，而是通过互 联、组合、协作解决用户需要解决的问题，产生具有附加值的新服务、数据、信息 等资源，满足用户的新需求。 ( 4 ) 自治性 网格上的资源首先是属于某一个本地的个人或组织，网格资源的拥有者对资源 具有最高级别的管理权限，网格应该允许资源拥有者对其资源有自主的管理能力。 因此，网格具有自治性。同时这些资源根据一定的约束和规则接受网格的统一管理， 实现资源的共享和操作，这使得网格管理比一般的分布式系统更为复杂，具有管理 的多重性。 ( 5 ) 动态性 由于网格中的资源具有自治性，因此网格资源可能动态的加入或者退出网格， 也可能出现故障而导致不可用；另外，资源的性能情况也可能发生较大的变化，使 得供网格使用的资源也会发生相应的变化。由于网格没有集中控制能力，因此，对 于动态性需要一种机制来保障网格应用的运行不会遭受较大的影响。 3 五邑大学硕士学位论文 ( 6 ) 自相似性 网格的局部和整体之间存在着一定的相似性，局部在许多地方具有全局的某些 特征，而全局的特征在局部也有一定的体现，通过小的局域网格可以形成更大的网 格，其构成方式具有相似性。 1 1 2 研究任务调度的意义 网格环境是由大量的异构资源组成的，因此网格系统必须解决由于各个资源之 间的结构不同和类别不同带来的诸多问题，如资源之间的通信、资源合理分配以及 任务的调度等问题。正是由于网格环境中资源的异构性才为网格的设计提出了更高 的要求，只有解决好了这些问题，才能充分发挥出网格技术的作用。 网格环境下的任务调度主要分为“面向网格资源的调度和“面向网格应用的 调度 两大问题。面向网格资源的调度是从网格资源的提供者角度提出的，这种调 度的原则是强调如何最大限度的发挥网格环境中的各个资源的使用效率。面向网格 应用的调度是从网格用户角度提出的，它的原则是如何使应用程序的执行能够最大 限度的适应网格资源性能的动态性，从而保证应用程序的性能要求。 一般而言，网格资源是由多个资源提供者提供的，并且每个提供者又有一套本 地的调度策略与机制。这些“本地资源调度就是每一个面向网格资源的调度的具 体实现者。另一方面，对于面向网格应用的调度，它要与这些本地资源调度者合作， 一起完成一个面向应用的调度。通常面向网格资源的调度者往往没有为面向应用的 调度提供必要的接口，以帮助实现一个面向应用的调度过程，而面向应用的调度者 往往没有权利来干预本地网格资源调度者的工作方式，这就使面向应用的调度问题 变得非常困难。目前针对这些问题已经提出了一些相应的机制，如资源预留机制、 资源性能动态预测机制、资源调度信息公布机制、资源同步配合机制以及计算机迁 移机制等，对于这些机制的研究和实现现在还没有达到实际应用的要求。因此研究 并提出一个好的任务调度策略将会在很大程度上提高网格资源的利用率，推动网格 技术的进一步发展。 1 2 主要研究工作 本文在广泛阅读了国内外关于量子遗传算法、遗传算法等启发式算法和网格计 4 五邑大学硕士学位论文 算的文献后，基于量子遗传算法及其改进算法原理提出了适合于网格计算环境的任 务调度算法。 本文的主要工作如下： ( 1 ) 介绍了网格任务调度的基本原理，分析和总结了网格任务调度的各种常见 算法及其特点( 本工作相关内容将在网络安全技术与应用2 0 0 8 年第l o 期上发表) 。 ( 2 ) 分析了量子遗传算法原理，提出了一种改进量子遗传算法( m o d i f i e d q u a n t u mg e n e t i ca l g o r i t h m ，m q g a ) ，提高了量子遗传算法的搜索效率和收敛速度， 并在多峰值函数求解问题中证明了其正确性和优越性( 本工作相关内容已发表在计 算机工程与应用2 0 0 8 ；4 4 ( 7 ) ：4 1 4 3 ) 。 ( 3 ) 提出了一种基于量子遗传算法的网格任务调度算法，使用量子遗传算法及 其改进算法来解决网格环境中多个子任务在异构资源之间的调度问题。采用量子比 特位给任务一资源间接编码，d a g 图来描述子任务间的依赖关系，根据深度值来给 子任务执行顺序排序，缩短了任务完成时间并提高了资源利用率，有效改善了网格 系统的总体性能( 本工作相关内容将在计算机工程与应用上发表) 。 ( 4 ) 通过s i m g r i d 搭建了网格仿真环境，编码实现了基于遗传算法、量子遗传 算法及其改进算法的网格任务调度算法。针对以上算法进行了详细的仿真实验，并 对结果进行了分析。 1 3 论文的内容安排 本论文正文共分六章。 第一章是论文的绪论，叙述工作的研究背景、主要的研究工作内容，介绍论文 的总体结构安排。 第二章的内容给出网格计算环境中任务调度的一般模型，介绍了网格任务调度 的原理、特点、过程以及目前的研究情况。 第三章介绍量子遗传算法的原理。主要包括量子计算概述、量子遗传算法的产 生与发展、量子旋转门等基本原理，提出了一种改进量子遗传算法并通过多峰值函 数求解证明了其可行性。 第四章为基于量子遗传算法的网格任务调度算法，将量子遗传算法及其改进算 法运用到网格任务调度中。内容包括：任务调度问题描述，染色体设计，适应度函 5 五邑大学硕士学位论文 数，深度值计算及其算法的流程和源码。 第五章的内容是对调度算法的仿真实验。首先介绍了s i m g r i d 仿真环境，运用c 语言实现了论文所提出的基于量子遗传算法及其改进算法的网格任务调度算法，与 传统的基于遗传算法的调度算法进行分析与比较。 第六章是对论文工作的总结，并指出亟待解决的一些问题，以及对未来工作的 展望。 论文的最后是参考文献、发表论文和科研情况的说明以及致谢。 6 五邑大学硕士学位论文 第二章网格环境下的任务调度 在网格环境中，任务调度系统是其重要的组成部分，它要根据任务信息采用适 当的策略把不同的任务分配到相应的资源结点上去运行。由于网格系统的异构性和 动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得任务调度 变得极其复杂，不好的任务分配策略，将会增加任务的执行时间、降低整个网格系 统的吞吐量。简单的说网格计算任务调度的目标是要对用户提交的任务实现最优调 度，并设法提高网格系统的总体吞吐率。由于网格计算任务调度面临的是一个n p 完全问题，它引起了众多学者的关注，成为目前网格计算研究领域的一个焦点。本 章主要讲述任务调度系统的原理、架构和一些适应性算法。 2 i网格任务调度原理 目前，主要有两种途径来提供高性能的计算能力，用于满足人们日益增长的大 规模应用程序的需求。一种是通过提高单个主机的计算能力，另一种是构建由多个 计算机组成的分布式系统。前者是通过改善计算机的硬件来实现的，与前者相比， 后者显然要复杂得多。现在已经存在了一些由异构资源组成的分布式系统，例如： c o n d o r t 7 8 】，n e t s o v l e o 10 1 ，n i m r o d 【1 1 1 射，g l o b u s l l 3 1 及其它网格计算系统。以上系统 在提供强大的计算能力的同时，也提出了一些新的问题。其中最重要的问题是如何 调度应用程序到各种异构资源中去。也就是说，如何在一个分布式系统中调度应用 程序，迄今为止，仍然是一个非常棘手的问题。网格系统与传统的分布式系统不同， 因此，在网格系统下的任务调度也不同于传统模式下的调度。 下面，我们首先来了解网格调度和传统分布式系统调度的区别【1 4 】： ( 1 ) 两者的有效范围不同 网格调度器的有效范围是整个广域网，网格环境下资源全局状态对调度系统而 言是不确定的，对一般分布式系统而言，其有效范围是局域网，其调度器是可见的。 ( 2 ) 两者的操作对象不同 传统调度系统面对的是组织内部的，执行实际任务的计算单元、存储单元。而 网格调度面对的是不同系统之间的调度实例，本身不涉及具体的资源。因此，网格 调度器又被称为是元调度器，它是建立在现有的调度系统之上的一层中间层，任务 7 五邑大学硕士学位论文 是为不同系统之间的调度实例的协同工作提供标准的系统服务和协议。 ( 3 ) 两者标准的开放性不同 由于不同的系统需要通过网格调度系统来通信，所以势必要求通信协议的标准 性和开放性，如o g s a 、w e bs e r v i c e s 、x m l 等。而对于系统内部的调度器，可以 根据自身的需要，综合考虑性能等方面的因素，定制自己的通信协议。 对网格资源的访问通常需要遵循资源管理者定义的访问权限、记账、优先级和 安全机制，这些机制是由资源所在的不同系统来自主管理的。因此，支持自主系统 之间交互的高层调度服务( s c h e d u l i n gs e r v i c e ) 是进行网格调度的技术关键。同时，调 度系统也需要根据作业的实际情况( 批处理作业或实时作业) 定义不同的调度策略 以满足服务质量( q o s ，q u a l i t yo f s e r v i c e ) ，这些将是网格调度系统设计的基本原则。 有效的使用网格资源需要强大和灵活的网格调度机制。网格技术之所以能够成 功，在很大程度上取决于网格平台是否能够根据网格作业的内在联系、用户需求自 动进行从网格资源发现到任务分解以及作业运行监控等一系列过程。网格调度中有 一个关键问题是当分配子任务的资源出现异常时，如何保持程序的性能不受大的影 响，一个成功的调度策略往往取决于对系统状态信息的准确预测，而这些状态信息 预测又往往只能从资源的历史信息中推理出来。资源出现异常状态时，它根据历史 信息表现出不同的使用模式，所以，为了建立一个在动态变化的环境中能正常工作 的健壮的网格任务调度器，我们必须引入一种自适应的调度算法，它可以监视长期 性的应用程序进程，从而检测出可能出现的资源异常，然后选择合适的资源，把处 于异常机器上的任务重新调度到这些选择好的资源上。 2 2网格任务调度特点与目标 2 2 1 网格任务调度的特点 网格计算任务调度系统具有以下几个特点【1 5 】： ( 1 ) 任务调度是面向异构平台的。 由于网格系统是由分布在互联网上的各类资源组成的，包括各类主机、工作站 甚至p c 机，它们是异构的，可运行在u n i x ，w n i d o w s n t 等各种操作系统下，也 可以是上述机型的机群系统、大型存储设备、数据库或其他设备，因此网格系统中 8 五邑大学硕士学位论文 的任务调度必须面向异构平台，并在这些平台上实现网格任务的调度。 ( 2 ) 任务调度是大规模的、非集中式的。 由于网格系统是一个非常大的分布式巨型系统。要实现一种全局的统一集中的 任务调度管理是根本不可能的。因此，网格的任务调度必须以分布、并行方式进行 任务的管理与调度。 ( 3 ) 任务调度不干涉网格节点内部的调度策略。 在网格系统中，各网格节点的内部调度策略是自治的，网格任务调度系统干预 其内部的调度策略是没有必要的，也是不可能的。 ( 4 ) 任务调度必须具有可扩展性。 网格系统初期的计算规模较小，随着超级计算机系统的不断加入，系统的计算 规模也必将随之扩大。因此，在网格资源规模不断扩大、应用不断增长的情况下， 网格系统的任务调度必须具有可扩展性，不致因规模扩大而降低网格系统的性能。 ( 5 ) 任务调度能够动态白适应。 网格中的资源不但是异构的，而且网格的结构总是不停地改变：有的资源出现 了故障，有的新资源要加入到网格中，有些资源重新开始工作等。总之网格的动态 性是明显的，所以任务调度系统必须适应网格的这种动态性，从可利用的资源中选 取最佳资源为用户提供应用服务。 2 2 2 网格任务调度的目标 在网格计算中，主要有两部分实体，一种叫做资源消费者( 提交各种各样的应 用程序) ，另一种叫做资源提供者( 分享自己的资源) ，各自具有不同的目的。这 些动机在调度中通过目标功能来体现。在网格计算中，大部分目标功能是继承于传 统的并行分布式系统。网格用户基本上都关心他们程序的执行效率，例如运行一个 应用程序的总的代价，而资源提供者更注意他们资源的绩效，例如在特定时期内的 资源利用率。因此目标功能可以被分为两类：以应用为中心和以资源为中心。 ( 1 ) 以应用为中心 调度算法采用一种以应用为中心的目标是为了最优化每个应用程序的执行效 果。目前的大多数网格应用程序关注的主要是时间，例如总执行时间( m a k e s p a n ) ， 它是指从应用程序中的第一个任务开始到最后一个任务结束被花费的时间。 9 五邑大学硕士学位论文 m a k e s p a n 是一个主要的、常见的任务调度的目标。 当经济模型【1 9 1 被引入到网格计算的时候，经济成本( 指一个应用程序需要为 资源利用支付的费用) 变成一些网格用户所关心的目标。这个目标被网格经济模型 广泛采用。除了这些单一的目标，许多应用都使用复合的目标，例如，些网格应 用既想要得到最短执行时间也想要最小的经济代价。要采用复合目标功能所面临的 主要困难是两种度量( 即时间和费用) 的标准化。这样使得在网格中进行调度变得 更加复杂。需要网格任务调度器对处理这样的复合任务有足够的适应性。 网格基础设施的发展已经展示出了一个面向服务的趋势，所以o o s 变成许多网格 应用所关注的一个热点。特别是在如此非专一的动态环境的应用中。服务质量q o s 是高度依赖于明确的应用，从硬件能力到软件需求。o o s 的包含经常会影响调度过程 中的资源的选择，并对最终目标的优化产生影响。 ( 2 ) 以资源为中心 调度算法采用以资源为中心的目标，主要是为了最优化资源的绩效。以资源为 中心的目标经常与资源利用率( r e s o u r c e su t i l i z a t i o n ) 、资源吞吐量( r e s o u r c e s t h r o u g h p u t ) 相关。资源吞吐量，是指在一定时间内，一个资源处理确定数目应用 程序的能力；资源利用率，是指一个资源使用的百分比。低资源利用率意味着一个 资源是空闲的。对于一个多处理器资源，多个处理器之间的利用率区别也表现了系 统的负载和吞吐量。c o n d o r 是一个非常有名的以吞吐量作为调度目标的系统7 。8 】。 当经济模型被引入到网格计算中时，经济利润( 是指资源提供者通过给网格用 户提供资源所得到的费用) 也被引入到任务调度的策略范围内。 在网格计算环境中，由于网格用户和资源提供者的自治性，以应用为中心的目 标和以资源为中心的目标经常是不一致的。l e g i o n 2 0 】提出了一种方法，其允许每个 组织发出各自的要求，然后由l e g i o n 系统作为中间者来找出一个资源分配策略，使 得两个组织都可以接受。 除此之外，还有一些其他的网格调度的标准及目标，例如文献【2 1 】所提出的总 的处理器消费周期( t p c c ，t 0 t a lp r o c e s s o rc y c l ec o n s u m p t i o n ) ，是指网格从调度的 开始时间到结束时间所用的总的指令数。t p c c 表示了一个应用程序所花费的总的计 算量。 l o 五邑大学硕士学位论文 2 3网格任务调度模型 通过网格调度器( g s ，g r i ds c h e d u l e r ) 的位置，可以将调度模型分为两种：具 有中心调度器的调度模型( 中心式网格调度模型) 和具有分布式调度器的调度模型 ( 无中心式网格调度模型) 2 2 - 2 3 】。在单一管理域的超级计算系统、工作站机群和集 群上，通常采用中心式调度器。因为它设计简单，也能满足一般高性能计算的需求。 但是仅有中心式调度器是不够的，对于广域网络下的网格计算环境，需要具有分布 结构的非中心式调度器。分布式调度模型由若干个中心式调度模型协同完成的。 ( 1 ) 中心式网格调度模型 如图2 一l 所示，在中心式调度模型中，只有一个网格调度器，这个调度器跟踪 所有计算资源上的负载信息，独立的在计算资源范围内为任务找到合适的节点集合。 中心式调度模型分为两层，一个网格调度器自成一层，虚机群中的代理( a g e n t ) 组成另一层。中心式网格调度框架很容易修改为分布式调度模型，以适应资源动态 增加的情况，从而提高网格的可用性。中心式调度模型的网格调度器通过代理与所 有计算节点进行通信。代理在中心式网格调度模型中扮演着重要角色。在这里，代 理负责接收调度器的请求信息，接收调度器分配的任务，负责任务的启动执行，信 息收集。此外，代理还负责监测各个计算节点，收集资源特性信息。 n 个用户 1 个调度器 k 个虚机群 图2 1 中心式网格任务调度模型 由于网格调度器是网格系统的单一中心，必须保证其安全和可靠，以防止单点 失效。建立双网格调度器( 如采用热备份方法) 是解决单点失效的一种有效方法。 五邑大学硕士学位论文 在中小规模、单管理域的网格计算系统中，适合采用中心式网格调度模型。用户可 以通过w e b 入口，来访问网格调度器。 ( 2 ) 分布式网格调度模型 在分布式( 或非中心式) 网格调度模型中，每个网格调度器( g s ) 仅维护本管 理域的负载信息，通过调度器之间的协作，才能为任务选择到适合的节点。当网格 规模不受限制的扩大，让一个网格调度器去跟踪所有的节点的负载信息是困难的， 所以，网格使用无中心式调度框架更具有一般性。 图2 2 显示了树形结构的非中心式网格调度模型。图中带箭头的双虚线表示任 务t a 由枝节点迁移到根的过程。 图2 2 树形结构网格调度模型 2 4网格任务调度结构与过程 在网格任务的调度过程中，主要是由任务调度器来进行控制。如图2 3 ，任务 调度器可以包括以下几个主要组件：授权认证模块、作业提交模块、资源查询模块、 任务映射算法、任务分配控制等。其中任务映射算法和任务分配控制是关键部分。 任务映射算法是指在选定的机器集合上，为应用程序的各个任务匹配机器的算 法。任务映射算法主要是对程序分解产生的任务进行机器匹配，匹配是逻辑过程， 不进行任何的传输。根据任务映射后的结果，任务分配控制模块将任务发送到指定 的机器上的执行队列内。 ： 根据任务调度器的组件功能，可以看出一个典型的网格任务调度至少应该包括 1 2 五邑大学硕士学位论文 用户应用服务提 。l 授权认任务分供者 证模块 配控制 jl i 服务提】 r 7 j 供者 作业提 ii 任务映 交模块 1 7 i 射算法 1 服务提 资 7 i 供者 l 源 信 息 服 资源查询模块服务提 务 器 供者 图2 3 任务调度器的结构 作业提交、收集可用的资源静态信息、资源预留、资源动态信息查询、制定调度计 划和资源初始化以及作业运行及监控几个过程【2 4 乏5 1 。 ( 1 ) 作业提交 用户作业的执行通常会涉及到分布式数据、网络资源、存储资源和软件资源等， 另外用户可能对服务的质量有一定的要求，如任务必须在什么时间之前完成。这些 资源需求可以通过脚本语言描述( 如r s l ) 提交给网格调度系统。用户或应用定义需 求被提交给网格调度服务后，网格调度服务负责根据这一需求找到合适的资源。作 业需求描述脚本包含了必要的信息足以判断资源是否能够满足这需求。作业描述脚 本应该包含三个方面的信息，一是作业本身的属性，如可以分成几个部分，相互之 间的顺序关系，一般被并行化理论抽象为d a g 图的形式：第二是作业的约束条件，如 作业完成的时间限制，服务质量等，可能还有在网格经济模型中的“费用 ，“代价 的概念：第三是对实际静态资源的需求，如程序运行的操作系统，最小内存、网络带 宽等。 ( 2 ) 收集可用的资源静态信息 网格调度系统负责为用户提交的“需求清单 找到合适的资源，包括为作业进 行资源调度、资源预留。无论是系统进行资源自动选择还是由用户参与的交换选择， 都需要考虑到用户和资源拥有者方面的要求，在满足用户需求的条件下节约资源的 使用。这一过程主要是发现潜在资源的静态信息，即为用户的作业需求找到匹配的 资源组合。调度器收到用户作业的需求报告后将其中的内容解析出来，之后，网格 1 3 五邑大学硕士学位论文 调度系统通过网格信息服务收集网络上可用的网格资源。此时，调度系统仅仅进行 简单匹配，并不判断这些资源是否处于可用状态。 ( 3 ) 资源预选 经过资源发现阶段可能会得到针对一个作业的许多合适的网格资源，资源预留 的任务就是进一步筛选，使得只有一部分合适的愤源能够进一步的进行匹配【2 6 1 。这 _ 过程可以通过许多启发式原则进行自动筛选或者在用户的干预下进行。例如，用 户可能需要在满足任务进行条件的网格资源中选择费用最小的资源等。 ( 4 ) 资源动态信息查询 作业运行时调度系统需要收集当前的资源信息并依次进行资源使用情况的预 测。如当前资源是否是可用状态，否则预测什么时候可用。如果当前考查的资源不 满足条件，则需要返回上一步对候选的下一个资源组合进行考查。 ( 5 ) 制订调度计划和资源预留初始化 基于资源可用情况、网络带宽和数据准备情况，调度服务判断哪个资源组合对 作业来说是合适的。这一步骤需要用到一些评价模型来决定资源组合，制订调度策 略，发出资源预留请求，当某一个资源预留过程失败，那么调度器会选择后备的服 务继续这一预约过程。 ( 6 ) 作业运行时监控 复杂的作业运行时间一般比较长，用户应该有权利在任务提交后到执行完毕的 时间内查询任务的运行状态。这是通过作业运行时监控服务来管理的，监控服务负 责的另一个职责是在作业运行满足一定条件时调度其它服务引起作业的下一个流程： 在作业调度服务失败时重新初始化作业运行。 2 5网格任务调度算法研究现状 网格任务调度策略大致可以分成两类：静态调度策略和动态调度策略。在调度 之前，了解了全部的调度所需信息，调度策略在任务执行之前已经确定，这样的调 度是静态调度。动态调度可以分为两种模式：在线模式和批模式。对于在线模式， 一旦任务到达调度器，立即进行调度。对于批模式，当到达调度器的任务累积到一 定数量或某个调度事件发生后，再进行调度，所以在这种情况下，可以收集到足够 多的任务和资源信息，进行综合考虑，制定出合理的调度算法。可以看出，批模式 1 4 五邑大学硕士学位论文 具有在线模式的实时性和静态模式的高效性。一般的，批模式策略可以作为静态策 略使用，只是它们考虑的资源和任务的范围有所区别【2 7 。2 8 】。 由于任务调度是一个n p 完全问题【2 9 】，所以人们在该领域进行了大量的研究， 同时也取得了一些成果，提出了很多优化算法，下面介绍当前的一些任务调度算法 及其特点。 1 o l b 算法 。 在任务调度算法中，o l b 3 0 】( o p p o r t u n i s t i c l o a db a l a n c i n g ) 算法是最简单 的调度算法，它将每个任务分配到下一个准备好的可用的机器，不考虑任务在这个 机器上的执行时间。如果有几个机器同时可用，则随机选择一个。该算法的目的是 要尽可能的使所有的机器都处于工作状态，优点是简单，容易实现。但是如果某一 个任务在某台机器上执行时间很长，这时会拖延整体任务的完成时间，这是该算法 最显著的缺点。 2 m i n - m i n 算法 m i n m i n 算法【3 1 】首先分别计算每个任务在所有机器上的最小执行时间，选择最 小执行时间最短的那个任务并将其分配到相应的机器上，然后这个最近被映射的任 务从任务集合中删除，重复执行这个过程直到任务集合为空。算法流程如图2 4 图2 4m i n m i n 算法流程 m i n - m i n 算法的思想是尽可能把每一个任务分配到最早可用且执行最快的机 器，但是在运行过程中，m i n m i n 算法可能引发负载不平衡。 3 m a x m i n 算法 1 5 五邑大学硕士学位论文 m a x m i n l 2 8 1 跟m i n m i n 算法相似，不同的是选择任务集合中最小执行时间最大 的任务并将其首先分配到相应的机器上，尽可能早的完成执行时间长的任务。 m a x m i n 调度算法可以给出一个具有更好的负载平衡和更好的任务完成时间的任务 与机器之间的映射，但是缺点是运行时间较长。 4 d u p l e x 算法 d u p l e x 调度算法是m i n m i n 算法与m a x - m i n 算法的结合。d u p l e x 调度算法对一 个任务调度问题分别使用m i n - m i n 算法与m a x - m i n 算法同时执行，然后进行比较， 使用结果较好的解决方案。因此，d u p l e x 调度算法可以用在m i n