（计算机科学与技术专业论文）基于虚拟计算环境的元调度器研究.pdf

摘要网格技术的提出为互联网络中资源共享、大规模计算应用的解决提供了很好的支撑平台，但是网格环境本身固有的动态性、异构性等特点，又给网格作业的调度带来了不小的难度，因而网格调度问题研究是当今世界网格技术研究的一个重点和难点。本文依托大规模科学和工程计算，研究设计了适合地震资料处理的网格资源调度平台系统，目的是为用户提供稳定、透明、方便的网格任务提交环境，使网格作业快速、高效的运行在合适的网格资源中。通过对虚拟计算环境理论和网格技术的研究，本文提出了一种自适应的层次型分级调度模型架构，这种模型具有高度可扩展性，能够适应资源动态变化。另外结合网格调度的具体功能需求，设计出了一种网格元调度器，并对其各个组成模块进行了详细的设计和阐述。在调度策略的选取上，针对复杂的地震资料处理流程，专门就关联任务调度进行研究，提出了一种基于d a g 图划分的调度算法，可以有效地减少资源选择时问以及作业执行时间，经过实验验证，该算法具有较高的调度性能。关键词：虚拟计算坏境理论，网格，关联任务，元调度器，d a gr e s e a r c ho nm e t a - s c h e d u l e rs y s t e mb a s e do nv i r t u a lc o m p u t i n ge n v i r o n m e n tx i n gc h a n g z h e n ( c o m p u t e rs c i e n c ea n dt e c h n o l o g y )d i r e c t e db ya s s o c i a t ep r o fl i a n gh o n ga b s t r a c tt h eg r i dt e c h n o l o g yh a sp r o v i d e dag o o dp l a t f o r mf o rr e s o u r c e ss h a r i n ga n dl a r g e - s c a l ec o m p u t a t i o na p p l i c a t i o n ，b u tg r i de n v i r o n m e n ti sd y n a m i ca n di s o m e r i cw h i c hg a v et h eg r i ds c h e d u l i n gs o m ed i f f i c u l t y , t h u st h eg r i ds c h e d u l i n gp r o b l e mi so n ek e ya n dt h ed i f f i c u l t yo fg r i dt e c h n o l o g yi nt h ew o r l d b a s e do nt h el a r g e s c a l es c i e n c ea n dt h ee n g i n e e r i n gc a l c u l a t i o n ，t h i s a r t i c l ed e s i g n sag r i ds c h e d u l i n gp l a t f o r ms y s t e mw h i c hs u i t e dt h ee a r t h q u a k ed a t ap r o c e s s i n g ，t h eg o a li st op r o v i d es t a b l y , t r a n s p a r e n ta n dc o n v e n i e n tg r i ds u b m i s s i o ne n v i r o n m e n tf o rt h eu s e r , t or u nt h et a s k si nt h ea p p r o p r i a t eg r i dr e s o u r c e sf a s ta n de f f e c t i v e l y b yr e s e a r c h i n gt h ev i r t u a lc o m p u t i n ge n v i r o n m e n tt h e o r y ( i v c e ) a n dt h eg r i dt e c h n o l o g y , t h i sa r t i c l ep r o p o s e dak i n do fa u t o a d a p t e ds c h e d u l i n gm o d e lc o n s t r u c t i o nw i t hl e v e lg r a d u a t i o n i th a sh i g he x t e n d i b i l i t y , a n dc a l la d a p tt h er e s o u r c e sd y n a m i cc h a n g e s m o r e o v e r , b a s e do nt h ed e m a n do f 西ds c h e d u l i n gf u n c t i o n , w ed e s i g n e dak i n do fg r i dm e t a - s c h e d u l e r , a n dh a sc a r r i e do nd e t a i l e dd e s i g na n de l a b o r a t i o nt oi t se a c hm o d u l e w h i l es e l e c t i n gt h ed i s p a t c hs t r a t e g y , i nv i e wo ft h ec o m p l e xe a r t h q u a k ed a t ap r o c e s s i n gf l o w , w es p e c i a l l yr e s e a r c h e dt h em i m e dt a s k ss c h e d u l i n g ，a n dp r e s e n t e dar e l a t e dt a s ks c h e d u l i n ga l g o r i t h m ，w h i c hb a s e do nv i r t u a lc l u s t e r sa n dt h ed i v i s i o no ft a s k t h i sa l g o r i t h mh a sf u l l yc o n s i d e r e dt h ei n f l u e n c eo fh e t e r o g e n e o u s 鲥de n v i r o n m e n ta n do b t a i n e db e t t e rs c h e d u l i n ge f f e c t s k e yw o r d s ：i v c e ，g r i d ，r e l a t e dt a s k s ，m e t a - s c h e d u l e r , d a g关于学位论文的独创性声明本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外，本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对研究所做的任何贡献均己在论文中作出了明确的说明。若有不实之处，本人愿意承担相关法律责任。学位论文作者签名：煎童亟同期：w f 。年r 月叩r学位论文使用授权书本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手段保存学位论文。保密学位论文在解密后的使用授权同上。学位论文作者签名：前霉狄指导教师签名：鎏! !同期：枷口年皇月叼同只期：p f o 年1 -月研同中国征油人学( 华东) 颂t 学位论文第一章前言1 1 课题研究背景、目的及意义1 1 1 课题研究背景网络作为现代社会一种重要的信息基础设施汇集了大量的资源，这些资源是信息时代国家资源的重要组成部分。随着i n t e m e t 和w e b 技术的出现，人们可以有效地共享利用网络资源，但是从总体上讲，网络资源的共享利用率不高的问题仍旧比较明显乜1 。首先，互联网资源分布不均匀，有的地方供大于求，而有的地方供不应求；其次，网络基础设施不够完善，网络传输、管理域之间的通信交流仍然是网络应用的瓶颈。上世纪6 0年代l i c k l i d e r 所设想的网络计算环境目标瞌1 ，仍未实现。另一方面，网络应用不断发展，经济、行政、教育、科研、军事等各个领域都对网络资源的共享和综合利用提出迫切需求。比如在地震勘探领域，随着三维地震勘探等新技术的应用和推广，地震勘探的精度越来越高，地震资料采集的数据量较以往也有了大大增加。此时，传统的地震处理和解释系统平台以及集中式的计算机处理方式( 如高性能计算机、集群等) 已无法满足地震勘探数据处理的需求。因此从上个世纪8 0 年代开始，人们开始把注意力集中到现实的问题当中，开始研究分布式计算环境。8 0 年代中后期，a m o e b a g l m a c h 等人1 提出了建立分布式操作系统，试图在分布的网络环境中建立统一的全局视图，但是失败了。进入9 0 年代，i a nf o s t e r和c a r lk e s s e l m a n 等人曲1 提出了网格的概念，立志于将互联网上的所有资源进行共享，经过几十年的研究，提出了许多适合互联网特性的架构和协议。在国内，卢锡城旧1 院士等人提出了一种基于按需聚合与自主协同的虚拟计算环境理论，从基础理论和系统机制入手，对网格计算技术不能解决的问题进行理论突破，从而促进网格和其他网络技术的发展。虚拟计算环境还试图共享多个网格应用系统的计算资源和信息资源，实现大范围的资源聚合和协同。本文利用比较成熟的网格技术，采用虚拟计算环境理论按需聚合、自主协同的理念，研究在动态的、异构的网格环境中如何有效的管理、调度网格任务，以达到比较理想的计算要求，满足油田等行业对计算能力不断增长的需求。1 1 2 课题研究目的及意义网格技术的发展极大的推动了并行以及分布式计算的发展，但是随着并行及分布式应用的发展，再加上网格本身资源不稳定等特性，使得网格任务调度成为当今网格研究第一章前言的重点和难点。网格任务调度系统根据适当的调度策略把网格作业调度到合适的网格资源当中，从而减少网格用户使用网格资源的复杂性、提高作业执行的效率和资源使用率。好的调度系统可以充分利用网格资源的并行能力，保证用户作业按质按量的完成；相反，不好的调度系统将会增加任务执行时间，降低资源利用率。通过对网格环境下调度器的研究将基于机群的地震处理任务移植到计算网格环境中，使地震资料处理高效地利用网格的超强计算力。本课题是基于中国石油天然气集团公司石油科技中青年创新基金项目“基于地震资料数据处理的应用网格技术( 0 7 e 1 0 2 4 ) 以及中石化胜利油罔物探院项目“地震勘探软件集成开发环境及应用研究之网格系统构建技术探索 进行的。石油勘探领域已拥有丰富的高性能计算系统。但是，随着勘探技术的发展和进步，地震资料处理的数据量呈“指数级 难以想象的速度增长，原有的系统已不适应和不能满足要求。本课题就是利用网格技术有效地综合利用已有的高性能计算资源，提供更高更强的处理能力，同时节约成本、增产增效，以空前的规模效益提供更为经济的资源。1 2 论文研究目标及内容本文将通过分析目前网格环境的特点，利用虚拟计算环境理论，提出一种适合异构网格环境的、高效的、适用于地震资料处理的元调度器系统，使其能够很好的适应网格动态性、异构性特点，支持复杂的地震处理作业，获得较好的调度效果。主要研究内容有：( 1 ) 分析研究虚拟计算环境理论与网格技术。虚拟计算环境理论从理论研究的角度提出了很多互联网发展的技术，而网格则在具体应用、实现层次上为我们提供了很好的借鉴和实现的平台，因此需要深入研究这两个技术，从总体上把握系统开发的背景和目的。( 2 ) 分析现有的网格调度模式，结合虚拟计算理论的层次结构，提出合理的调度模型，并设计实现该调度架构的实体。( 3 ) 针对复杂的网格应用，对关联任务调度进行深入研究，提出关联任务调度算法存在的问题及改进方法，设计适合地震资料处理的关联任务调度算法。1 3 论文组织结构安排本论文共分为六个章节，其中：第l 章为前言，主要介绍了论文的研究背景及意义、论文的主要研究内容。2中国石油大学( 华东) 硕士学位论文第2 章是全文研究的理论基础，主要介绍虚拟计算环境相关的基础理论知识和元调度器的研究情况，分析虚拟计算环境和网格的异同，以及元调度器的研究现状。第3 章根据网格资源管理和调度方式的特点，结合虚拟计算环境中按需聚合的理论，提出了基于虚拟聚类的自适应调度模型。采用分级式调度管理，设计了元调度器的框架与组成，并对模型中各实体的功能及工作流程进行了介绍。第4 章介绍了基于d a g 划分的网格关联任务调度算法，并对该算法进行试验及性能评测。第5 章详细介绍了网格元调度器原型系统的构建，对前面提出的理论和方法进行了验证。第6 章是全文工作总结以及进一步的工作展望。3第二章虚拟计算环境理论j 兀调度器第二章虚拟计算环境理论与元调度器2 1 虚拟计算环境理论2 1 1 虚拟计算环境介绍相比传统集中式资源管理模式，互联网中的资源管理具有以下几个特点：动态性，互联网的资源规模是不断变化的，包括资源的数目、他们之间的关联性都是不断变化的。互联网是一个开放的系统，其覆盖的地域是变化多样的，异构资源可以随时加入和退出互联网的管理，相应的资源信息也是不断变化的，这一特性将导致网络资源的不确定性。自我管理性，网络资源具有局部自治、自我管理的特性，比如，网络中很多资源都是专属于某个组织或者个人的，其使用的规则往往是事先制定的一些安全法则，全局化的资源控制不再适用。异构性，随着互联网的发展，连接在网络上的资源也在不断的增加，种类也不尽相同，这些资源可以包括各种软件、数据，也可以包括各种计算设备和可以联网的设备。无论在类型还是各种属性方面，他们都是多种多样的，很难找到一种统一的描述来形容他们，这将导致资源管理方面的困难。为实现互联网资源的有效共享和综合利用，在分析互联网资源的自然特性的基础上，卢锡城院士等人提出了一种基于按需聚合与自主协同的虚拟计算环境理论协1 。聚合是指获取、分析、融合互联网络中的各类资源，最终能够为应用提供简洁、统一的资源视图，方便用户使用。协同：多个资源在共同完成同一个任务的时候能够相互协作、互相配合，有效地减少执行时间。虚拟计算环境是指建立在复杂的互联网络或者网格之上，以按需聚合和自主协同为机制，有效地融合各类资源，为互联网用户提供统一、透明、可靠的计算环境，实现资源共享。构建虚拟计算环境和核心问题是如何有效获取、组织互联网络资源信息并使他们协同工作。第一个关键问题就是如何根据用户需求，查找整个网络，发现、组织、汇聚可用资源信息，形成一个能够满足用户需求的近乎同构的资源视图。由于网络资源的动态性、自治性和异构性等特点，几乎不可能获得一个始终稳定、统一的任务执行环境，那么在这样的环境下，可以寻找一种相对的、暂时的稳定环境。所以根据用户提出的作业4中田“* 学( 十) i ：￥* 女执行请求，查找适合的资源，建立一个适合当前应用的资源视图成为构建虚拟计算环境的首要任务：第二个关键问题是当任务分配到多个网络资源的时候，如何建立一种协同t ：作环境，保证任务执行的持续性、稳定性、高教性。资源的动态性特点决定了任务执行过程中可能会发牛各种各样的突发事件，另j l - 多个资源共同执行一个任务时还会面临执行同步、任务通信等因素，因此实现一种动态、灵活、全局的协同机制，时刻监控资源运行状态、作业执行情况是十分必须的，这也是构建虚拟计算环境的关键所在。212 虚拟计算环境的组成与体系架构为了很好的解决上节所提到的关键问题，需要从以下三个方面进行：首先要对资源信息分析建模，构建资源自治模型体现自治性；其次构建属性共同体，进行资源聚合；最后创建任务分布执行机制支持资源自主协同”1 。与此对应。分别引入自主元素、虚拟共同体和虚拟执行体三个概念。( 1 ) 自主元素自主元素是虚拟计算环境中的基本资源管理单位，是具有自主行为能力的资源管理肯，辟 柬反映网格资源的自治性特点。从其内部组成来看。自主元素可以由感知组件、行为驰动组件和执行组件构成。感知组件是自主元素同外界进行交互的接口，用于获得外问环境及资源运行状态的变化：行为驱动组件主要根据自主元素的行为策略来进行动作决策；动作的具体实旆由执行组件完成。三者共同构成了自主元素的控制环路，是实现资源自主化的核心。图2 - l 显示的是自主元素的示意图。i 嵩雨二_ _否蓄词曾j图2 - 1 自主元素示意匿f i g2 - 1s c h e m a t i cd i a g r a m o f a u t o n o m i c e l e m e n t s通过创建自主元素，网络中动态、异构的资源被抽象和封装，既能够反应网络资源的自制特性，也有效遮掩了网络资源多样性和异构性，对用户来说，他们都是透明的。复镕一$ m m # # 环# g 。，m *自主元素足资源虚拟化的过程，为资源的聚合和协同提供基础。在实际的应用中，一个自主元素可以是一台网络主机，也可以是一组集群主机，通过安装特定的服务组件可以实现自主元素的功能。自主元素可以自由组合，对外提供资源聚合信息，并支持通过一致的接口实现资源的访问和交互。( 2 ) 虚拟共同体网格资源动态变化，任务需求也多种多样，很难提供一种适合所有任务需求的资源环境，但是可以根据用户需求获得一个可靠的执行环境，因此面向用户需求，利用资源信息进行资源聚合构建虚拟共同体。虚拟共同体是指一组符合用户任务执行需求、满足一定原则的自主元素的集合。尽管在一个共同体内部，自主元素间是不尽相同的，但是他们都是满足一定条件的资源集合，从这个层次上讲，他们近乎同构。一个自主元素可以同时属于多个共同体，虚拟共同体提供资源发布和发现机制，符合一类任务执行需求。虚拟共同体是动态的，自主元素可以根据实际情况，随时的加入或者退出共同体。图2 2 所示是一个虚拟共同体的示意图。图2 - 2 虚拟共同体示意图h g2 - 2s c h e m a t i cd i a g r a mo f t h e v i r l u mc o m m u n i t y( 3 ) 虚拟执行体任务提交到虚拟计算环境中之后，根据用户需求，选择符合条件的自主元素来麸同完成任务，那么就需要对这些自主元素进行管理和协调所以引入虚拟执行体的概念。虚拟执行体是指共同执行同一个任务的自主元素集合，这是网络资源协同过程的抽中目“k 学( 十末) f 岸忸论文象是虚拟计算环境的基本运行管理单位。一个虚拟执行体对应一个网络应用，通过虚拟执行体可以有效管理、佛同执行该任务的自主元素。虚拟执行体与自主元素阃的关系如图2 3 所示。图2 - 3 庄拟执行体示意圈f k2 - 3s c h m a f i c d l l q l mofmvirtualb r上述三个概念是虚拟计算环境的核心，是其重要组成因素，因此虚拟计算环境的搭建也是围绕上述三个因素进行的。虚拟计算环境由七层组成，其结构示意图如图2 - 4 所：i 。一毒叠管磐图2 4 虚拟计算环境层次结构图f 2 - 4h i e r a r c h y c h a r to f v i r t u a lc o m p u t i n ge a v i r o n m e n t资源层：由各种异构、多样的网络资源组成，可以是各种单机节点，也可以是集群站点，还可以是存储器、数据和信息等虚拟计算环境支持的资源。虚拟层：该层用于自主元素的创建，提供了自主元素创建和管理的基础服务支持将资源封装为自主元素，完成对资源层中各种资源的虚拟化和自主化。聚合层：该层创建和管理虚拟共同体，在各虚拟共同体范围内分别组织和管理自主萝否面一俞墓一鎏第一章虚拟计算环境理论与元调度器元素，并按照任务需求对自主元素进行有效地聚合，面向任务形成相对稳定的资源空间和视图。自主协同层：根据任务需求生成相应的虚拟执行体，通过虚拟执行体绑定相关自主元素，并通过自主协同来完成任务。安全管理：为虚拟计算环境中资源聚合与协同提供安全保证，以创建一个安全和谐的计算环境。编程丌发环境：提供各种支持虚拟计算环境开发、部署和运行的程序设计语言设施与环境。应用层：为用户提供各种应用开发支持。2 1 3 虚拟计算环境理论的特色虚拟计算环境理论试图通过自主元素、虚拟共同体和虚拟执行体等概念，支持开放环境下资源的按需聚合和自主协调，为终端用户或应用系统提供和谐、可信、透明的一体化服务，具有以下几个特点：采用资源按需聚合的理念有效地回避了网络资源动态性、异构性带来的全局资源控制难的问题，支持面向q o s 的资源动态聚合机制。支持资源的自治性，提出实现资源封装并具有信息感知和一定决策控制能力的“自主元素概念和模型，突破了传统资源集中管理的局限性，适应网络资源信息不确定性等特点。虚拟执行体的提出为资源协同工作机制建立了动态、可配置的运行基础。2 1 4 虚拟计算环境与网格网格是继传统因特网、w e b 之后的第三次互联网浪潮，可以称之为第三代因特网应用m 1 。传统因特网实现了计算机硬件的连通，而网格则试图实现互联网上所有资源的全面连通，其中包括计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等。网格从理论层次上提出了一种互联网络资源的组织方式和发展方向，经过十几年的研究，网格计算项目在全世界范围内获得了不小的进步。迄今为止，欧美以及中国的很多高校以及研究机构相继启动了t e r a c n i d 、t a c n i d 、c h i n a g r i d 等新型计算环境旧，并可以进行一些商业和科研方面的应用。尽管如此，网格计算技术在针对开放的、不确定环境下的大规模资源信心的发布与组织、按需资源动态获取与管理、协同行为的自主化和智能化以及动态地服务组合与服务选择方面尚存在不足岫1 。8中国石油人学( 华东) 硕上学位论文虚拟计算环境是指建立在开放的互联网基础设施之上，以网络资源的按需聚合与自主协同为核心机制，为终端用户或应用系统提供和谐、可信、透明的一体化服务环境，实现有效资源共享。它的提出从基础理论和系统机制入手，对网格计算技术不能解决的问题进行理论突破，从而促进网格和其他网络技术的发展。虚拟计算环境还试图共享多个网格应用系统的计算资源和信息资源，实现大范围的资源聚合和协同。这也是本文研究的出发点。2 2 元调度器2 2 1 元调度器简介实现网络资源的有效共享，屏蔽分布、异构的网格资源，为用户应用提供透明、统一、稳定的资源视图，保证用户任务高效完成，是网格计算需要解决的核心问题。在现实的网格应用中，一个网格应用可以包括多个独立或者有内在联系的作业集合，这些作业共同完成了一个应用任务。当一个作业被提交到网格上，网格首先选择一个可以运行该作业的网格资源，然后将作业提交到该资源上运行，如果这些操作由用户来完成的话，非常不利于网格使用与推广，而且有违透明网格的初衷，最好的解决方式是在网格上层构建一个网格应用代理或者资源中介n 们，它可以作为网格用户的客户端，负责接收用户提交的作业，为用户选择合适的资源并提交作业、管理监控作业的执行，这种代理就是网格元调度器。网格元调度器系统主要包括资源管理、任务管理和调度策略三部分1 ，资源管理主要实现资源的定义、发现、评估以及访问等功能；任务管理包括任务解析、分解、调度、状态监控等功能；调度策略主要提供一些资源与作业的匹配方式，以获得更短的完成时间，除此之外，网格元调度器还应该包括容错、记账等功能。2 2 2 元调度器与传统调度器的比较在网格环境当中，小到一台单机p c ，大到包含上千节点的计算机集群，只要涉及到任务资源映射问题的，都要考虑调度问题，在集群系统当中，调度被定义为将操作分配到资源，同时考虑某些性能的度量标准，并满足一定的约束条件n 引：同样，网格调度是任务到网格资源的映射，性能优化标准包括性能负载、q o s 等，从这个角度上看，网格调度同集群系统的调度具有很多相似点，但是由于两者面临的资源环境、任务特点不同，相应的，调度也有显著的不同点。从资源角度来看，传统的集群调度系统属于集中式管理系统，其调度管理的资源往9第_ 二章虚拟计算环境理论与元调度器往属于一个管理域，管理节点对集群内部资源具有绝对的控制权，这样的设计使得调度策略更加简化，容易执行。在调度架构上，集群的管理节点可以维护一个实时的全局资源、任务视图，采用简单的一对多式调度即可；而在网格环境中，资源属于不同的管理域，调度系统并不具备资源的管理权限，这就需要一种机制来使用其他管理域中的资源，同时，不同的调度者、资源代理也可通过协商的方式完成各自的资源分配，分散式调度往往采用树形层次型结构。从资源管理软件方面来看，一个集群资源是由某种集群管理软件通过专属的资源访问协议、集群文件系统以及专门的安全认证服务实现资源的统一管理。而在网格环境中，每个管理域会根据自身的需要选择不同的集群管理软件，因此，元调度器必须考虑资源访问的异构性，必须采用一种开放式、兼容性强的跨域访问协议( 如g r a m n 3 1 ) ，另外基于安全考虑，在访问不同的管理域时，需要提供某种安全管理措施。网格环境的动态不确定性也给网格调度提出了一个不小的难题。网格环境中充满了不可预知的意外事件，如资源使用者收回资源的使用权、新作业的加入等等，任务处理时问无法进行提前预测，从而无法指定有效地调度计划。2 2 3 元调度器研究现状网格初期，由于研究重点不在调度方向，所有网格任务往往都是经过手动方式提交、采用固定的调度策略，但是随着应用和网格技术的发展，这种传统的作业提交方式已经不能满足要求。许多组织和企业开始开发元调度器系统。由于构建网格环境的基础设施是多种多样的，所以各个元调度器的功能和特点也不尽相同，例如c o n d o r o g 1 侧重于网格系统的高吞吐量；a p p l e s n 5 1 则关注于容错性能；s i l v e r m a u i 引关注于系统的负载平衡等等。上述的调度系统有的是在原有集群调度器系统基础上整合网格基础设施服务获得的，有些则是大型网格项目的一个子系统。它们或者对特定的集群系统有较强的依赖性，或者只是针对某些专业的项目应用，它们在处理特定应用时具有很好的效率，但是通用性比较差，应用范围较窄。时至今日，元调度器面临的更多问题是来自不同领域的应用需求，如并行作业、工作流、组作业等等：另外，一个好的调度系统必须保证不同完成时间的任务集合在异构资源上的执行时间最短，即保证调度性能比较好，同时还要兼顾扩展性、用户界面等方面的要求。本章主要从资源管理系统和任务管理系统以及扩展性、用户界面等方面对6种网格调度器进行比较。( 1 ) g i r d w a y 元调度器1 0中国石油人学( 华东) 硕上学位论文g r i d w a y ”7 是由西班牙一个分布式系统研究组开发的开源的元调度器系统，其基于g l o b u s 网格服务中间件，管理网格内共享、异构的资源。g r i d w a y 支持多种网格中间件，可以是基于p r e w s 的，也可以是基于w s 的，提供中间件访问驱动器来屏蔽底层网格中间件的差异，在资源发现方面，支持m d s 2 和m d s 4 两种协议，在资源管理层次，支持g r a m 和d r m a a 两种协议引，用户可以编写标准的d r m a a 程序提交给g r i d w a y 。g r i d w a y 架构降低网格中间件和应用程序开发者之间的距离，使得网格资源更加有用而且更容易被访问。g r i d w a y 架构可以让用户掌控地理上分布的动态资源，当作业提交之后，首先根据资源选择策略将其分配到一个执行资源上，在执行的过程中，如果作业的需求发生了改变或者更好的资源被发现了，或者与远程资源的连接失败了或者远程资源计算性能下降到规定值以下了，作业可以被迁移到其他的可用资源上。其最突出的特点就是他的模块化设计还有策略的可扩展性上。g r i d w a y 给用户提供了一种“提交后不管的方式引，并实现了基于动态网格环境的任务迁移，方便了广大用户对网格资源的使用，主要特色有：表2 - 1g r i d w a y 特色t a b l e2 - 1g r i d w a yf e a t u r e s特色描述资源管理支持多种协议，如g r a m 、d r m a a 、m d s l 2 0 1 等调度策略中心式调度。r o u n d r o b i n 策略，可扩展式策略作业管理支持作业提交、监控作业类型多样支持单一、组、工作流、弗行作业等错误检测与恢复支持检测和恢复远程错误( 2 ) c s f 元调度器c s f 他是由p l a t f o r m 公司与吉林大学合作的项目，c s f 是与w ，e b 服务资源框架相兼容的元调度器，并利用g l o b u s 提供的基本服务，如代理服务、可靠文件传输服务、信息检索服务与作业管理工厂服务等，开发了作业服务队列服务和资源管理服务等有状态的w e b 服务提供给用户使用。利用c s f ，网格用户可以通过g l o b u s 的g r a m 协议与各种本地资源管理器进行协作。除了支持基本的作业管理服务外，c s f 还支持可配置的作业调度机制、有限的资源预留机制、兼容p r e w s g r a m 和w s g r a m ( g r a m 的w e bs e r v i c e版本) 协议等。提供以下基本服务：作业服务：为用户提供一个接口，用以创建、控制和监视作业。镕一 m m * # 口。j “度#资源预帘服务：允许用户提6 l 在将要运行用户作业的站点上预留资源，确保当作业提交到浚站点上时，资源是可获得的。队列服务：一个队列代表一个具体的调度策略，管理员可以为对了服务配置多个队列，一旦某个队列被实例化，则用户可以将作业请求或者资源预留请求提交给该队列。资源管理服务：包括资源管理工厂和资源管理实例服务，通过资源工厂，c s f 获得比较高的扩展性，能够适应多种网格资源管理协议，它负责根据作业类型为资源管理实例服务创建作业资源；资源管理实例即针对某种资源管理协议所实现的接口。( 3 ) f a l k o n 轻量级任务执行架构为了使作业能够尽可能快的在计算资源上运行，增加系统的吞吐量，l o a nr a i c u “2 等人丌发了一种轻量级的任务执行架构- f a l k o n 。为了达到上述目的它将多层调度和流水线分配方式结合起来尽可能快的将作业分配给资源。它主要是由三部分组成：d i s p a t c h e r 、e x e c u t o r 、p r o v i s i o n e r ，结构如图2 - 5 所示：囤2 - 5f i i k o l 系统集构图f i 9 2 - 5s y s t e m a r c h l t e c h r e o f f a l l m n( 4 ) c o n d o r - gc o n d o r 是由美国戚斯康辛大学研究开发的一个计算密集型作业资源管理系统，是目自目集群环境中使用较多的管理系统之一。它e q 造了一个大吞吐量的计算环境可以有效地利用网络中互相通信的集群站点的计算能力。c o n d o r 本身支持网格特性，当所有的资源都运行c o n d o r 时，它就会建立一个网格环境。使用c o n d o r 的网格特性时它可以经过g l o b u s 将作业提交到其他的网格资源上t 这些都得益于g l o b u s 提供的网格基础设施服务。c o n d o r - g 是在g l o b u s 基础服务之上，利用c o n d o r 的作业管理工具实现作业的提交、中国石油人学( 华东) 硕士学位论文监控等操作。它使用g l o b u s 的安全管理及资源访问特性，同远程的网格资源建立连接进行数据传输、远程执行环境管理等操作，使用c o n d o r 自身的作业管理工具，简化了作业管理的过程。c o n d o r - g 可以在同时提交多个任务，并可以通过一个用户窗口监视任务的执行状况，提供任务成功或失败的通知，还具有容错功能。c o n d o r - g 结合了g l o b u s 技术，整个c o n d o r - g 由s c h e d u l e r 响应用户的请求，通过创建一个g r i d m a n a g e r 守护线程来提交和管理这些任务，该线程为了传输任务的执行表、标准输入文件、提供一个实时的标准输出流和错误流，通过g a s s 同o r i d m a n a g e r 相连。c o n d o r - g 在数据管理和传输方面虽然使用了g a s s 和g r i d f t p ，但是在传输不同数据文件上，以及海量数据传输上没有做到自适应传输。与c o n d o r o g 类似的还有a p p l e s 、n i m r o d g 、i l a b 等等拉3 。，他们都提供了对组作业和依赖任务的支持，功能得以加强。c o n d o r - g 是在c o n d o r 集群管理系统的基础上开发出来的，它仅适用于c o n d o r 管理的集群系统，而对于其他集群管理系统( 如l s f 、p b s 旺3 1 1 等) 建立的管理域则不能进行任务调度。j 下是网格的这种跨管理域的资源管理调度特性注定了网格资源调度的复杂性。( 5 ) m i c h i g a na d v a n c e dr e s o u r c es c h e d u l e r ( m a r s )m a r s l 2 引是密歇根大学安娜堡分校开发一种网格资源调度系统。利用了g l o b u s 的g r a m 服务组件和安全机制，通过启发预测的方法来评估资源性能、查看资源队列长度、任务的执行情况及其调度性能等。m a r s 采用集中式调度，采用优先级调度策略，通过比较任务的优先级，优先调度级别高的任务到性能好的资源上执行，高优先级任务也可以抢占低优先级任务的资源，它还提出了一种采用遗传算法的启发式进化调度算法。m a r s 采用了c o n d o r - o 中c l a s s a d s 的思想来做资源和任务的匹配，其调度框架是可扩展的，但是没有考虑调度策略的动态装载、多个调度策略的协同问题。( 6 ) n i m r o d gn i m r o d g 位引是由澳大利亚蒙纳士大学开发的，源l ! l n i m r o d 集群调度系统。它是在g l o b u s 和l e g i o n 基础服务组件基础上开发出来的，可以同c o n d o r 等集群管理软件进行协同工作，使用启发式的资源评估算法；在资源监控方面，支持通过资源访问历史对其进行评价的技术；支持数据的预先拷贝：开创性地将经济学的思想引入网格元调度器系统他 ，调度算法基于任务预算和最后期限进行资源任务的匹配工作，但是，协商过程需要资源代理双方都支持某种商业协议，如s n a p 等，协商过程是在对其他资源代理未1 3第二二章虚拟计算环境理论1 j 元调度器知的情况下进行的，因此协商结果不易预测。2 3 本章小结本章首先对虚拟计算环境的概念、特点以及体系结构等理论知识进行了叙述，然后比较了集群环境下与网格环境下的调度系统，进而引出元调度器的概念，并介绍了6 种当前国内外比较有名的元调度器，并从资源管理系统和任务管理系统以及扩展性、用户界面等方面对它们进行比较，为后面章节的研究工作打下基础。1 4中国石油人学( 华东) 硕上学位论义第三章基于虚拟聚类的自适应调度模型网格环境是建立在计算机网络基础上的，与传统的集中式资源管理不同，网格资源具有非独占性、动态性、异构性等特点，这些特点决定了网格管理资源时需要注意：一是屏蔽资源的异构特性，为用户提供透明化、稳定的资源视图；二是保证网格环境的稳定性，保证用户作业按时按质的完成；三是在满足用户需求的前提下，要尊重资源本地管理策略，不能超越权限使用网格资源1 。这就要求我们设计的网格调度管理系统能够实时的获取网格资源信息，具有动态适应的能力，因此，研究设计网格调度系统模型的时候要充分考虑网格资源的异构性和动态性，使其能够适应网格环境、提高调度效率、满足用户需求、保证资源使用者的权益。基于上述目标，本章对网格资源管理模型进行研究，结合虚拟计算环境理论中按需聚合和自主协同的思想，提出了一种基于虚拟聚类的自适应调度模型。3 1 网格资源组织与调度方式介绍网格资源本身是多种多样的，但是其组织连接方式即网格拓扑结构却不外乎下面几种“：星型拓扑结构层次型拓扑结构对等拓扑结构混合型拓扑结构图3 - 1 网格拓扑结构f i g3 - 1m e s ht o p o l o g y( 1 ) 星型拓扑结构又称作集中式结构，此时，所有资源信息都存储在一个节点上，叫做信息中心，其负责所有资源信息的注册，以及用户的查找操作。该种方式减少了请求者和信息中心的通信开销，不会影响其他节点的的运行，复杂度较低。但是如果网络规模比较大，网格资源信息注册、更新和查找的请求都有信息中心完成，这样会加重信息中心的负担，而其更坏的是当信息中心出现故障的时候，整个网络将瘫痪。1 5第三牵基十虚拟聚类的自适应调度模型( 2 ) 对等式网格拓扑结构：该种结构中，网格节点之间都是对等的，每个节点上都保存有网格环境中所有资源的属性信息，在调度上也处于平等的地位。( 3 ) 层次型结构：也就是树形结构。网络是层次型分布的，同层节点没有关联，上层节点与下层节点可以是多对多的关系，资源信息采用汇聚的方式向上层节点注册信息。( 4 ) 混合式结构：是对等结构和层次型结构的组合，网络中每一层的节点是对等的，有一定的拓扑相连，下层的节点对应一个或者多个上层节点，一个上层节点对应一个或者多个下层节点。在实际的网格环境中，网格资源的加入与退出是随时都有可能发生的，层次型拓扑结构可以方便的实现资源的加入与退出，扩展性好，另外上层节点可以作为下层节点的管理节点，利于资源信息的获取与任务的调度，所以本文在构建网格环境的时候采用树状层次型拓扑结构。网格资源的拓扑结构在一定程度上决定了资源被调度的方式，但是，网格调度还需要网格资源信息对其提供支持，它与网格资源的多少和构成方式是息息相关的，不同的调度模式对应不同的拓扑结构。常用的调度模式有以下三种n ：( i ) 集中式调度对于单个组织或者个人使用的计算资源，它们分布相对集中，结构相对同构、网络连接相对稳定，可以通过集中管理的方式进行调度，比如集群、高性能计算机等。这种情况下，调度策略比较单一，具有固定的集中式资源管理系统，如c o n d o r 、l s f 等等。( 2 ) 分散式调度在整个互联网络中，资源是成分散分布的，资源之间管理方式也是多种多样，不同资源提供者可以选择不同的调度策略。这时没有统一的中央管理单元来调度管理所有的资源，资源间的协作往往是通过分散的本地调度单元间的通信实现的，所以这种模式扩展性高、不容易出现性能瓶颈。但是组织困难，实现比较复杂，不适合网格研究。( 3 ) 分级式调度类似于层次型拓扑结构，该种调度方式由多层调度系统组成，在分散的多种本地调度系统之上，引入更高层的全局范围的调度中心，负责统一协调各种本地调度器的工作，这种方式保证从系统全局的角度进行作业分配，资源监控等工作，可以更加高效的执行任务。但是随着系统规模的增大，全局的调度中心成为系统的瓶颈，很容易制约整个系统的运行，改进方法是增加多个全局调度中心，采用数据备份与恢复技术等。1 6中 ( 末) m i t 基于上述分析，本文结合实验室的环境，决定采用分级式调度模式，分为两层调度：阿格厄调度器层和本地调度器层。网格元调度器相当于全局调度中心，负责网格范围内的资源崖现和调度。木地调度器相当于调度于代理，负责本域范围内的调度。用户提交的作业在元调度中心进行一缴调度，在调度子代理上进行二缎调度。32 自适应层次型调度框架321 层、欠调度框架介绍虚拟计算环境从构建资源的主体化模型、利益共同体和分布执行机制的角度提出了3 个重要的概念：自主元素、虚拟共同体和虚拟执行体，井在此基础上提出了以资源层、虚拟层、聚合层、自主协同层和应用层为核心的网络计算系统体系结构。根据虚拟计算环境的理论我们在构建网格调度环境时，采用分层管理、按绒调度的方式。网格资源节点调度框架如图3 2 所示，主要元素有：网格计算节点、本地调度单元、逻辑共同体以及元调度执行体。图3 - 2 网格层次图f i 9 3 - zg r i d l e v e ld| 叫格计算节点是虚拟计算环境的资源层，司以是同构的集群资源也可以是彼此差异帕网格单机节点，通过互联网或者高速总线连接，彼此共享计算资源，可以相互交换用户提交的任务。本地调度单元是虚拟计算环境中自主元素的具体表现，通过统一的资源描述接口，将加入虚拟计算环境的网格资源封装为一台虚拟计算机，它位于虚拟计算环境的虚拟层，由调度中心和信息中心构成。调度中心负责接收上层调度器的任务调度请求，进行* m e 一$ * m e 一镕b第三章基于虚拟聚类的自适应调度模型任务分发、监控和执行结果收集；信息中心负责网格资源注册、资源信息维护与更新，为上层逻辑共同体的创建提供必要的信息。逻辑共同体对应于虚拟计算环境的虚拟共同体，位于虚拟计算环境的聚合层，是具有并发作业协同能力的本地调度单元的集合。在本文模型中，逻辑共同体是模型的核心，通过建立逻辑共同体，可以在复杂的网格环境中查找性能相近的计算节点，给作业集合提供一个平等的计算环境，保证所有任务能够按时完成。本文通过虚拟聚类的方式对将本地调度单元收集的资源进行分组产生逻辑共同体，并把它们作为元调度器调度的直接对象，具体方法将在3 2 2 讲述。元调度执行体是虚拟计算环境中的虚拟执行体，也是整个层次框架的核心，主要目的是协调系统各个调度器的工作，用于接收用于请求，采用一定的调度策略将作业调度到各共同体上进行执行，达到降低资源负载、提高资源利用率、系统吞吐量的效果。3 2 2 自适应调度模型层次型分级调度框架，从物理架构层次上对网格资源进行有序的组织，可以有效屏蔽资源的异构特性，有利于网格资源的动态加