（管理科学与工程专业论文）基于支持向量机性能预测的量子遗传网格任务调度研究.pdf

摘要 摘要 网格计算是构筑在i n t e r n e t 上的一种新兴技术，其利用共享网络将分散在不 同地理位置的计算资源、存储资源和数据资源等组织成一台虚拟的超级计算机， 由此提供强大的计算能力。随着网格技术的迅速发展，网格的应用越来越广泛， 受关注和重视的程度越来越高。网格的大规模应用对有限的网格资源提出了挑 战，即如何在有限的网格资源下运行更多的网格任务。解决该问题的核心在于调 度算法，一个优良的调度算法可以使网格节点执行更多的任务，从而增大网格系 统的吞吐率。本文的研究正是围绕改进任务调度算法这一现实的问题而展开的。 本文研究了网格任务调度总体框架，分析了传统的网格任务调度算法，并且 针对以往任务调度模型任务执行时间冗长和任务丢弃数量过多等不足之处，提出 了一种新的的网格任务调度模型。该调度模型首先利用支持向量机技术对网格各 节点性能进行预测，这种方法大大提高了网格调度的有效性，从而提高了任务调 度的效率；然后提出量子遗传算法；继而把用支持向量机得出预测的结果与网格 任务数据同时输入基于量子遗传算法的调度执行系统中，通过该模型得出任务调 度方案；最后利用s i m s n o w 平台对上述模型得出的任务调度方案进行验证，表 明基于量子遗传算法的调度模型比以往的基于m i n m i n 算法与传统遗传算法的 调度模型要优越。 本文共分六章：第一章为绪论部分，对论文的研究背景和研究思路进行了简 要的论述，提出了本文的研究对象、课题的研究意义，阐述了本文所采用的研究 方法和章节构造；第二章是网格和g i r d g a i n 概述，对网格概念进行了阐述，概 述了g i r d g a i n 平台和安装与调试；第三章是网格任务调度框架研究，对网格任 务调度框架进行了阐述，分析了经典网格任务调度算法，提出了基于支持向量机 性能预测的量子遗传算法的网格任务调度框架，并对这种新的调度框架进行了初 步的总思考，引出了研究主题；第四章是基于支持向量机网格节点性能预测研究， 讲述了支持向量机的基本原理，并且利用支持向量机对网格节点性能进行了预 测；第五章是基于量子遗传算法的网格调度任务研究，简介了量子遗传算法和量 子计算原理，进行了基于量子遗传算法的网格任务调度实验；最后第六章是调度 算法整合研究，进行s i m s n o w 系统设计，并且利用s i m s n o w 平台对前面形成网 广东t ! i k 大学硕十学位论文 格任务调度算法进行测试，最后得出基于量子遗产算法的网格任务调度模型比传 统遗传算法任务调度模型更加优越，可以达到提高网格资源利用效率的效果，对 指导现实工作有指导性意义。 关键字：性能预测；支持向量机；网格任务调度；量子遗传算法 a b s t r a c t a bs t r a c t g r i dc o m p u t i n gi s ak i n do fn e wt e c h n o l o g yt oe m e r g ec o m p u t i n g r e s o u r c e s ，s t o r a g e r e s o u r c e s a n dd a t er e s o u r c e si n t oav i r t u a l s u p e r c o m p u t e r w i t h p o w e r f u l c a l c u l a t i o n c a p a b i l i t i e s t o d a y g r i d t e c h n o l o g yd e v e l o p sr a p i d l y g r i di sa p p l i e dm o r ea n dm o r ew i d e l y t h e d e g r e eo fa t t r a c t i n g a t t e n t i o ni s g e t t i n gh i g h e ra n dh i g h e r l a r g e 。s c a l e a p p l i c a t i o n so fg r i dp o s eas e v e r ec h a l l e n g et ol i m i t e dg r i dr e s o u r c e st h a t r u n sm o r eg r i dt a s k sw i t hal i m i t e d g r i dr e s o u r c e s t a s k s c h e d u l i n g a l g o r i t h mi s t h ek e yo fs o l v i n gt h ep r o b l e m ，ae x c e l l e n tt a s k s c h e d u l i n g a l g o r i t h m m a k e sg r i dn o d ee x e c u t em o r et a s k s ，s oa st oi n c r e a s et h e t h r o u g h p u to fg r i dn o d e t h eg r i dt a s k ss c h e d u l i n gi st h ef o c u so f t h i sp a p e r f o rs o l v i n gt h i sp r o b l e m o nt h eb i s i so fa n a l y s i n gt h eo v e r a l lf r a m e w o r k sa n dt h ep r e v i o u s c l a s s i c a la l g o r i t h mo fg r i dt a s k ss c h e d u l i n g ，f o rt h es h o r t c o m i n g sw h i c hi s s u c ha st o o l e n g t h yt i m e i n e x e c u t i n gt a s k s a n de x c e s s i v en u m b e ro f d i s c a r d e dt a s k sa b o u tp r e v i o u st a s k s c h e d u l i n gm o d e l s ，t h i sp a p e rp r e s e n t s an e wm o d e lo fg r i dt a s k ss c h e d u l i n g t h en e wg r i dt a s k ss c h e d u l i n gi st h a t t h ep r e d i c t i o n sa b o u tt h ep e r f o r m a n c eg r i dn o d e su s i n gs u p p o r tv e c t o r m a c h i n e st e c h n o l o g ya tf i r s t ；a n dt h e n ，s c h e d u l i n gp r o g r a mi sd r e wi n p u t t i n g a n dr u n n i n gt h ep r e d i c t i o no u t c o m ei n t oq u a n t u mg e n e t i ca l g o r i t h m t o o b t a i n st h es c h e m eo ft a s ks c h e d u l i n g ；a tl a s t ，u s i n g s i m s n o wp l a t f o r m v e r i f i e st h ec o r r e c t n e s so f t h es c h e m eo ft a s ks c h e d u l i n g t h en e wm o d e l o fg r i dt a s k ss c h e d u l i n gi ss u p e r i o rt om i n m i na l g o r i t h ma n dt h ec l a s s i c a l g e n e t i ca l g o r i t h m t h ep a p e ri sd i v i d e di n t o6c h a p t e r s ；t h ef i r s tc h a p t e ri st h ei n t r o d u c t i o n c h a p t e r ，d e s c r i b i n gt h eb r i e fe x p o s i t i o n o f ，r e s e a r c h b a c k g r o u n d ，r e s e a r c h a p p r o a c h ，r e s e a r c ho b j e c t ，r e s e a r c h s i g n i f i c a n c e a n dt h es t r u c t u r eo f p a p e r ；t h e s e c o n d c h a p t e r i sa s u m m a r y o f g r i da n dg r i d g a i n ，t h e 广东t 业人学硕l ：学位论文 i n t r o d u c t i o no fg r i d c o n c e p t a n dt h ei n s t a l l a t i o na n d d e b u g g i n go f g r i d g a i n ；t h et h i r dc h a p t e ri s t h e r e s e a r c ho f g r i d t a s k s c h e d u l i n g f r a m e w o r k ，d e s c r i b i n gt h eg r i d t a s k s c h e d u l i n gf r a m e w o r k ，a n a l y s i n gt h e c l a s s i cg r i dt a s k s c h e d u l i n ga l g o r i t h m ，p r e s e n t i n gt h em o d e lo fg r i dt a s k s s c h e d u l i n g w i t h q u a n t u mg e n e t i ca l g o r i t h mb a s e d o n p e r f o r m a n c e p r e d i c t i o nu s i n gs u p p o r tv e c t o rm a c h i n e ；t h ef o u r t hc h a p t e ri st h er e s e a r c h o f p e r f o r m a n c e o f g r i d n o d e p r e d i c t i o n u s i n gs u p p o r t v e c t o r m a c h i n e ，d e s c r i b i n gt h eb a s i cp r i n c i p l eo fs u p p o r tv e c t o rm a c h i n e ，u t i l i z i n g s u p p o r t v e c t o rm a c h i n et o p r e d i c tp e r f o r m a n c eo fg r i dn o d e ；t h ef i f t h c h a p t e ri s t h er e s e a r c ho fg r i dt a s k s c h e d u l i n gw i t hq u a n t u mg e n e t i c a l g o r i t h m ，d e s c r i b i n gt h eb a s i cp r i n c i p l eo fq u a n t u mg e n e t i ca l g o r i t h ma n d q u a n t u mc o m p u t a t i o n ，a n a l y s i n gt h ee x p e r i m e n to fg r i dt a s ks c h e d u l i n gw i t h q u a n t u mg e n e t i ca l g o r i t h m ；t h es i x t hc h a p t e ri si n t e g r a t i o no fg r i dt a s k s c h e d u l i n ga l g o r i t h m ，t e s t i n gt h en e wg r i dt a s ks c h e d u l i n ga l g o r i t h mb y s i m s n o wp l a t f o r m a tt h ee n d ，e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wg r i d t a s k s c h e d u l i n ga l g o r i t h m i s s u p e r i o r i n t h ec l a s s i c g e n e t i c a l g o r i t h m ，i m p r o v i n gt h ee f f i c i e n c yo fg r i d ，w h i c hh a sg u i d a n c em e a n i n go f r e a lg r i d k e yw o r d s ：p e r f o r m a n c ep r e d i c t i o n ；s u p p o r tv e c t o rm a c h i n e ；g r i dt a s k s c h e d u l i n g ；q u a n t u mg e n e t i ca l g o r i t h m v 独创忭声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字：慰菱 指导教师签字： 是爻 2 0 0 9年0 4月19 日 第一章绪论 第一章绪论 1 1 网格概念 网格( g r i d ) 是目前新兴的一种计算模式。网格充分吸纳各种计算资源，并 将它们转化成一种随处可得的、可靠的、标准的、经济的计算能力。网格概念最 早于9 0 年代中期提出，用于表述在高端科学和工程上分布式计算的一种基础构 造形式。近年来，网格技术得到了迅速的发展。全球网格研究的领军人物i a n f o s t e r 在网格：2 1 世纪信息技术基础设施的蓝图一书中这样描述网格：“网 格是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算机、大型数 据库、传感器、远程设备等融为一体，为科技人员和普通用户提供更多的资源、 功能和交互性。互联网主要为人们提供电子邮件、网页浏览等通信功能，而网格 功能则更多的强调让人们透明地使用计算、存储等各种资源”1 ；1 1 2 1 。 2 0 0 0 年，i a nf o s t e r 在网格的剖析一文中把网格进一步描述为“在动态 变化的多个虚拟机构间共享资源和协同解决问题”。至此，人们仍然就什么是网 格而争论不休。2 0 0 2 年7 月，i a nf o s t e r 在什么是网格? 判断是否网格的三个 标准一文中，限定网格必须同时满足三个条件：( 1 ) 在非集中控制的环境中协同 使用资源；( 2 ) 使用标准的、开放的和通用的协议和接口；( 3 ) 提供非平凡的服务 3 】。 这三个条件非常严格，像p 2 p 、s u ng r i de n g i n e 、c o n d o r 、e n t r o p i a 、m u l t i c l u s t e r 等都被排除在网格之外。但并不是所有人都同意他的观点，例如，有许多人赞同 另一个网格概念广义的网格，它称作巨大全球网格g g g ( g r e a tg l o b a lg r i d ) ， 它不仅包括计算网格、数据网格、信息网格、知识网格、商业网格，还包括一些 已有的网络计算模式，例如对等计算p 2 p ( p e e rt op e e r ) 、寄生计算等。可以这 样认为，i a nf o s t e r 所赞成的是一种狭义的“网格观”，而g g g 是一种广义的“网 格观”。 不管是狭义还是广义的网格，其目的不外乎是要利用互联网把分散在不同地 理位置的电脑组织成一台“虚拟的超级计算机”，实现计算资源、存储资源、数据 资源、信息资源、软件资源、通信资源、知识资源、专家资源等资源的全面共享。 广东t 业大学硕l j 学位论文 由上，我们可以得出网格的基本特点：分别为异构性、共享性、动态性和可 扩展性【3 】。 1 异构性 网格涉及的资源类型多样，规模较大，分布在不同的地理位置。包括各类主 机、工作站甚至p c 机，它们是异构的，可运行在u n i x 和n t 等各种操作系统下， 也可以是上述机型的机群系统、大型存储设备、数据库或其他设备。 2 共享性 网格的共享性是指网格上的任何使用者都可以使用网格上的任何资源。网格 的根本特征就是分布资源的共享问题。此共享与以往所说的共享已有很大不同， 它更具有目的性，目的性体现在它已经不再是简单的资源互联和单一使用，而是 通过互联、组合、协作来解决用户需要解决的问题，产生具有附加值的新服务、 数据、信息等资源，满足用户的新需求。 3 动态性 网格的动态性是指网格资源不是一成不变的，使用者在某一时刻拥有的资源 和权限在下一刻都有可能发生变化。动态性包括动态增加和动态减少两个方面的 含义。 4 可扩展性 网格的可扩展性要求体现在规模、能力、兼容性等几个方面。在网格的设计 与实现时必须考虑到新的资源能否很自然地加入到网格中，并和原来的资源融 合，共同发挥作用，不降低网格计算的性能。 对于网格提供的计算能力，有4 个基本要求：可靠性、标准化、易用性和廉 价性： 1 网格的可靠性是指网格提供的计算能力必须保证是持续、稳定和安全的， 不应该因为网格内部个别资源的变化而对网格应用造成影响，即网格内部局部资 源的变动对网格应用应该是透明的。 2 网格的标准化一方面是指网格资源之间应该有一个统一的可以相互访问 的接口或者协议标准，另一方面是指网格对用户提供的计算能力应该满足一定的 标准，从而便于以一种统一的方式进行访问。 2 第一章绪论 3 网格的易用性是指用户可以在任何时间、任何地点，以自己习惯的统一的 形式访问和使用各种资源，网格计算能力可以通过网格系统输送到任何角落，随 处可得，如同人们通过电力网使用电力一样方便。 4 网格的廉价性是指通过将资源充分共享，最大限度的发挥资源的使用价 值，不仅可以将原来闲置和浪费的资源收集起来供网格用户使用，而且可以避免 以前由于地理位置限制所带来的各种额外开销，降低用户使用资源的费用。 1 2 研究现状 1 2 1 网格研究现状 网格技术源于美国，美国是目前网格研究技术世界领先的国家。网格研究最 初是从科研机构开始的，美国的多家研究机构开发了g l o b u s 、l e g i o n 、n i m r o d g 、 c i n d o r 等比较有影响力的网格软件和工具【s 】。 近年来，国际上从美国、欧洲、日本等发达国家到印度这样的发展中国家， 都启动了大型网格计划，并得到了产业界的大力支持。目前，已有许多网格研究 的组织和项目。世界信息技术大国认识到网格对当前网络技术巨大的拓展功能和 宏伟的发展前景，都把发展网格技术放到战略高度，纷纷投入巨资，争相发展网 格技术，力图抢占高点，获取竞争新优势。 美国政府用于网格技术的基础研究经费己达5 亿美元。美国自然科学基金会 资助的网格项目有n p a c ig r i d 和t e r a g r i d 等美国军方对网格技术更为重视，正 规划实施名为“全球信息网格( g l o b a li n f o r m a t i o ng r i d ) ”的巨型网格计划，此外 还有美国宇航局( n a s a ) 支持的i p g 网格项目等。美国各大i t 公司如s u n 、i b m 、 o r a c l e 、h p 等也纷纷投入巨资进行网格研究。欧洲的数据网格e u r o p e a nd a t ag r i d ( e d g ) 一个国际性大型研究和技术发展项目，该项目由c e r n( e u r o p e a n o r g a n i z a t i o nf o rn u c l e a rr e s e a r c h ，欧洲粒子物理实验室) 领导，另外包括e s a ( e u r o p e a ns p a c ea g e n c y ) 、法国c n r s ( c e n t r en a t i o n a lr e c h e r c h e s c i e n t i f i q u e ) 、意大利i n f n 、荷兰n i k h e f 、英国p p a e c 共5 个主要合作伙伴 以及欧洲各国的1 5 个相关研究机构。e u r o p e a nd a t ag r i d 主要针对c e r n 的高能 物理应用，解决海量数据的分解存贮和处理问题，并且提供突破地理局限，允许 分布在世界各地的工作者交互、共享数据和设备，共同开展科学研究的合作环境。 3 广东t 业大学硕f ：学位论文 在欧洲，关于网格还有著名的欧洲网格( e u r o p e a ng r i d ) 项目，其基本目标 是建立一个为用户提供安全、简单、透明地访问全欧洲资源的信息资源平台，为 欧洲的科学研究服务。该项目主要从网格基础设施、应用开发、基本技术三个方 面去开展研究。研究机构有法国、德国、英国、瑞士、波兰以及挪威的主要大学 和计算中心，以及天文、航天、高能物理等应用领域的机构和组织参加。欧洲还 建成了欧洲网格计算数据库，包括查找数据库和计算机数据库。另外，英国政府 已投资l 亿英镑，研制“英国国家网格”( u kn a t i o n a lg r i d ) 。法国也启动了国 家网格计划。荷兰国家网格计算计划将使5 个大学的研究人员能够更有效地在生 物信息、粒子物理等科研项目方面进行合作，这一网格计算计划包含5 台l i n u x 群集系统( 每个大学各一台，通过荷兰大学的高性能网络s u r f n e t 连接在一 起) 。 在亚太地区，亚太地区网格a p g r i d ( a s i ap a c i f i cg r i d ) 是亚太地区的合伙 网格计算项目。2 0 0 4 年5 月底，已有来自15 个国家( 包括澳大利亚、加拿大、 中国、日本、美国等) 共4 9 个组织加入a p g r i d 。a p g r i d 主要支持两大应用： 地球科学( 如气候模拟、流体模拟、地震工程等) 和生物信息( 如基因科学等) 。 日本是亚洲开展网格研究比较早的国家之一，日本的d a t af a r m 网格项目，主 要用于p e t a b y t e 数据量的高能物理实验数据的分析和处理，并与欧洲数据网格相 连。日本还制定了包括科学计划( 构架超级计算机网络) 、国际研究网格计划 ( n a g e g i 、商务网格计算机等计划，并逐年拨经费推动网格技术研究) 在内的 一系列发展网格计算的计划，并且还成了了i t 基础实验室( i t b l ) 、东京大学 网络、大阪大学生物网格中心等发展网格计算的机构。 韩国的网格计划是ng r i d ，这是韩国信息通讯部支持的一个项目，ng r i d 的 目标是建立韩国国家网格，该项目包括计算网格、数据网格、访问网格和应用网 格。它将韩国的超级计算机和高性能机群连接在一起，建成为应用试验床、应用 门户和用于开发具体的应用程序。 印度在其第十个五年发展计划期间，开发了ig r i d 项目，其主要是由高级计 算机开发中心把印度技术研究所、印度科学研究所等7 个著名的学术机构连接在 一起，以网格的理念令其发挥资源共享等作用。 在国内，网格计算的研究始于19 9 8 年，起步并不晚，在关键技术研究方面与 国外差距不大。在19 9 9 - 2 0 0 0 年期间我国设立了“国家高性能计算环境”重大项 4 第一章绪论 目，研制了网格系统软件和一批网格应用软件，形成了国家高性能计算环境即网 格的雏形。2 0 0 2 年，中国政府在“8 6 3 ”计划中也设立了网格专项，并开始筹建中 国国家网格( c n g r i d 【s j ) 、8 6 3 空间信息网格、中国教育科研网格( c h i n ag r i d t t 】) 、 上海信息网格( s h a n g h a ig r i d ) 等网格项目。目前上述网格和其他一些行业网格 已投入使用。 中国国家网格c n g r i d ( h t t p ：w w w c n g r i d o r g ) 目前包含8 个节点，其中2 个为主节点，一个是北京中科院网络中心；另一个是上海超级计算中心，6 个 普通节点分别位于北京、合肥、西安、长沙、成都等地。中国国家网格将提供高 性能计算、资源共享、协同协作的能力；在科学研究、环境资源、制造业、服务 业中建设若干大型行业应用网格；研制面向网格计算的高性能计算机，装备网格 节点，促进我国高性能计算机的研究产业化；研究以网格软件为代表的网格核心 技术。现在，我国已经在网格体系结构和网格软件、网格应用技术、网格服务模 式、网格安全以及网格管理和运行机制等方面突破一批关键技术，推动了网格的 产业化进程。 网格节点的性能取决于节点服务器的性能，因此高性能计算机的研制是提高 网格节点性能的关键。联想集团研制的“深腾6 8 0 0 ”超级计算机已在北京中科院 网络中心投入使用。曙光公司承担研制的“曙光4 0 0 0 a ”超级计算机目前已在上海 超级计算中心投入使用。可以说是专为网格设计制造的专用机。“曙光4 0 0 0 a ” 和“深腾6 8 0 0 ”两者同为科技部8 6 3 计划“中国国家网格”专项的具体内容。 目前已建成的应用网格有国家地质调查网格、航空制造网格、科学数据网格、 中国气象应用网格、新药研发网格、生物信息应用网格、林业应用网格等网格项 目。 1 2 2 网格任务调度研究现状 本文的研究重点是网格任务调度。目前在网格调度算法研究方面，其目标主 要是增加吞吐率，增加系统的使用率，以及在经济系统和用户的约束条件下实现 在整个系统中网格应用任务的完成时间最小，即使m a k e s p a n 最小，找到一个这 样的任务调度方案是n p 完全问题。 网格环境下的任务调度按照任务间的通信关系可以分为：相互间存在通信的 任务组调度和相互独立的任务组( m e t a t a s k ) 调度两类。调度系统使用调度算法 s 广东t _ , i k 大学硕i 。学位论文 来确定请求以及任务调度的相关顺序。图1 1 显示了调度算法的分类。对于相互 间存在通信的任务调度，最常用的方法是沿用传统的d a g 图( d i r e c t e da c y c l i c g r a p h ，无回路有向图) 调度，即将相互间存在数据依赖的任务组当作一个有向 无环图，根据此有向无环图作出调度决策。但对于大规模、多管理域的网格系统， d a g 图调度方式执行可能有相当的困难，实际上经常采用预置和合作配置方法 来保证任务的执行 6 1 1 7 1 。 其中m e t a t a s k 调度根据调度的频度可分为周期性调度以及事件驱动的联机 在线调度。周期性调度方法将资源请求和系统事件分为组，间歇地处理它们。调 度的间隔可以是周期性的或者也可以被一定的系统事件触发，关键在于任务调度 是成批处理的而不是针对单个请求或者事件，事件驱动的联机调度在g r m s ( g e n e r a l i z e dr a n d o mm a n u f a c t u r i n gs y s t e m g r m s ，广义随机制造系统) 收到 资源请求或者系统事件时执行调度。批调度能得到更有效的网格资源利用率，因 为能够考虑到更多的请求，利用周期性或者批调度，对状态可以进行更好的预测 估计。但是由于服务层的问题不一定能立刻引发任务调度，使用该方法很难实现 硬q o s 支持，但对于联机方式其对任务的反应更快，减少了任务的延迟时间， 但很难对于不同类型的网格系统执行一个通用的联机g r m s 方案。 大多数的调度算法都是面向系统的。面向系统的调度算法以最大化系统吞吐 率为调度目标；而面向应用的调度算法则尽力优化某些特定的参数如应用完成时 间。在实际的网格应用中，系统可以执行调度组织、系统状态估计和调度算法的 不同组合，以致改变调度系统的一部分而不影响其它g r m s 构件或其它调度构 件。下面是一部分现有重要网格项目的调度系统分析： 一竺塑量竺竺些f 岍而丽 图1 1 调度算法分类图 f i g u r e1 1t h ec l a s s i f i c a t i o no fs c h e d u l i n ga l g o r i t h m 6 第一章绪论 1 c o n d o r g t 8 】1 9 】 c o n d o r 是一种广泛使用的高吞吐率的批处理作业调度器，它与g l o b u s 项目 合作开发了c o n d o r g ，它是一种访问远程批处理系统的应用网格代理，利用 c i a s s a d s 进行资源的发现和匹配，并采用抢先式再继续调度方法( p r e e m p t i v e r e s u m es c h e d u l i n g ) 来实现资源的动态变化。c o n d o r 拥有明确的管理客户和管 理系统之间的任务服务等级协议( t s l a ) ，这使得调度可以顺利执行。运行一 个c o n d o r g 作业需要六个步骤：( 1 ) 用户提交作业；( 2 ) 用户身份验证；( 3 ) 分析作 业；( 4 ) 数据传输；( 5 ) 作业提交到作业队列；( 6 ) 作业执行。 2 p b s ，l s f 与s i l v e r m a u i t l o 】 p b s ( p o r t a b l eb a t c hs y s t e m ) 是由n a s a 开发的灵活的批处理系统。它被用 于集群系统、超级计算机和大规模并行系统，支持批处理作业、串行作业和m p i p v m 并行作业，提供了f i f o 等多种作业调度策略，具有一定的作业监控能力和 安全机制，但没有解决单一故障点问题，不提供检查点操作和进程迁移，要求对 资源具有完全的控制。l s f 是p l a t f o r m 公司开发的负载分担设施( l o a ds h a r i n g f a c i l i t y ) ，作为本地调度系统其功能同p b s 一样，即可作为网格调度体系结构 中的底层调度用于完成批处理作业，实现负载平衡。如果以g r a m 作为底层协 议，也可以将p b s ，l s f 部署在网格层次上。而m a a i 则为本地集群提供高性能 作业调度，它作为现存资源管理的一个功能扩充模块，可以实现抢先式作业、公 平调度、优先级管理、调度优化和q o s 支持，它可以与p b s ，l s f 等进行集成。 s i l v e r 利用m a u i 实现了作业在多个集群间进行调度，能够提供负载平衡、协同 分配和网格一级的q o s 保证。 3 基于知识的元调度器( k bm e t a s c h e d u l e r ) k bm e t a s c h e d u l e r 利用基于人工智能的多约束条件搜索技术来实现调度决 策，它将作业的花费时间、用户要求、负载平衡、内存要求、缓存要求等信息用 到专家系统中。该调度器是建立在g l o b u s 的基础上，利用了g l o b u s 的一些高级 基础服务，如资源预留和信息服务，来执行任务调度。 4 a p p l e s t l 2 儿1 3 i t 】【1 5 】 a p p l e s 是一个多用户分布异构环境下的高性能调度器，它关注应用的优先级， 是一个多代理系统，每个代理负责一个特殊的任务。a p p l e s 代理利用异构应用程 序模板，允许用户指定应用的结构、特征和设备，而用户指示( u s e rs p e c i f i c a t i o n ) 7 广东t 业大学硕f j 学位论文 提供关于用户的性能、时间和其它标准的信息。a p p l e s 考虑的是应用级的调度， 应用是在基于主机系统的反馈基础上进行调度的。当系统发生变化时，a p p l e s 会重新考虑应用的调度过程，从而适应应用性能的变化。a p p l e s 包含的许多元素 在基于性能信息的情况下支持资源分配，但是没有一个组件通过监控性能调整任 务来支持反馈机制。 5 n i m r o d g e 1 6 i i t n i m r o d g 是澳大利亚m o n a s h 大学网格调度系统。它是一个模拟仿真系统， 采用g l o b u s 中间件作为网格接口，执行系统对分布式参数的计算优化，n i m r o d g 基于经济模型提供了一系列计算资源方案，能够基于最迟期限和预算( d e a d l i n e a n db u d g e t ) 进行调度工作。n i m r o d g 的计算经济目前还不是十分充分，它缺乏 一种定义资源费用的全面策略。 6 v e g ag r i d 织女星网格( v e g a ) 是由中国科学院计算开发的网格操作系统，引入服务 网格的思想，在资源调度中对于功能和性能的评价不只是采用传统计算机的评价 标准( 速度、加速比、性能价格比等) ，还有以用户满意度为目标，用类似s l a ( s e r v i c el e v e la g r e e m e n t ) 的服务质量尺度来衡量。其作业管理机制对服务的 使用仅限于单个的、孤立的服务的调用，缺乏动态地、易用地把多个服务组合起 来，并且v e g a 并不符合o g s a 规范。 1 2 3 网格性能预测研究现状 在网格性能预测方面主要有两种方法，它们分别为网络气象服务( t h e n e t w o r kw e a t h e rs e r v i c e ，n w s ) 和网格产量服务( g r i dh a r v e s ts e r v i c e ，g h s ) 。 n w s 是一个短期网格性能资源预测器，通过采用上一周期的最准确的方法去 预测下一周期。n w s 方法能够对网络c p u 和内存进行预测，由于其采用的是数 值方法其执行效率很高但只能进行短期的预测_ 般预测时间小于5 m i n 。现在 n w s 的预报算法有：l a s tv a l u e ，r u n n i n gm e a n ，v a nj a c o b s o n ，m e d i a n ，t r i m m e d m e d i a n ，s l i d i n gw i n d o wm c a n ，a d j u s t e dm e d i a n 和a a j u s t e dm e a n 。n w s 为了 提高预报精确度，把以上各种预测算法综合起来，即系统中维护着每一种算法的 精确度记录，根据精确度记录在各种算法之间动态选择在整个历史纪录中，哪 种算法的预报精确度最好，在下一次预报中就采用哪种算法。该系统已在l e g i o n 8 第章绪论 和g l o b u s n e x u s 上应用，并取得了很好的效果。虽然n w s 只提供可用于l i n u x 操作系统的版本，但是经过学者们的研究现在的n w s 已经可以提供可用于 w i n d o w s 操作系统的版本【1 3 】。 g h s 采用的是一种基于任务的预测方法，g h s 将资源看成是一个m g 1 类 型的队列系统，本地任务的到达概率符合泊松分布，这样就可以预测指定任务在 这个资源上的运行时间。由于目前大多数系统是分时系统很难使用m g 1 模型 同时g h s 是基于任务预测的，所以其计算量比较大 1 9 1 。 因此本文主要使用n w s 模型，假设网格节点资源是呈周期性变化的并且根 据不同的周期，网格节点的性能是可以预测的。 1 3 研究意义 随着网格技术的不断发展，网格的种类也越来越多元化，总体可以分为两大 类，分别为数据网格与计算网格。其中在计算机网格被广泛的运用在科研与商业 领域中。而对网格技术的研究大部分都集中在其任务以及资源的调度上，由于其 为n p 完全问题，增加了学者对此进行研究的难度。对任务调度算法的研究可以 直接改善网格系统的性能，所以本文的研究重点也放在这一方面。利用数据挖掘 技术，对网格节点服务器资源进行挖掘，以改善过去任务调度算法对网格节点的 错误估计而导致任务执行失败的问题。这个任务调度方法比过去的自适应任务调 度算法具有更良好的节点资源估计能力，可以对动态的网格节点进行有效的任务 调度。这也使网格系统可以更加有效的运行。与此同时，随着网格应用需求的扩 展以及网格面向服务架构的提出，如何在网格系统中为用户提供q o s 支持也成 为当前网格研究中的个热点问题，而本文所提出的任务调度算法也考虑到了 q o s 的影响，对高q o s 任务实行优先调度的原则，以达到用户对任务的q o s 要 求。 本文利用数据挖掘与量子遗传算法结合作为网格任务调度算法，是研究在任 务调度过程中的网格资源预测的一个新方向( 在研究任务调度过程中网格节点资 源预测是一个新方向) 。由于网格节点的数目远比要实时运行的网格任务要小， 所以它比起以往只预测执行任务的完成时间的方法更具有可操作性，网格管理者 9 广东t 业大学硕f j 学位论文 只需要通过程序接口查看网格节点的资源负载状态，就可以对该服务器进行预 测，这也使得网格任务调度可以更加顺利的进行。 1 4 研究内容与创新点 本文的研究工作是在两个科研项目的基础上进行的，一个是广东省哲学社会 科学规划项目( 项目名称：基于角色管理的远程教育网格资源管理研究，项目编 号：0 7 s j y 0 2 0 ) ；另一个是广东省自然科学基金项目( 项目名称：面向现代远 程教育的智能体网格应用研究，项目编号：6 3 0 0 2 7 8 ) 。 1 4 1 研究内容 本文从传统的调度算法入手，在其基础上加入了资源预测的思想，从而使调 度算法有较好的自适应度。本文主要的研究内容有： 1 利用s v m ( 支持向量机) 对网格节点进行资源预测，以确定该节点的工作 状态，利用输出的数据修正调度算法。 2 利用量子遗传算法实现网格任务调度。量子遗传算法在种群数量与进化代 数相同的情况下，其性能与算法准确度比普通的遗传算法要高，而且能够更有效 地避免普通遗传算法的“早熟 问题，因此利用量子遗传算法对网格任务调度系 统进行改造，使系统有更好的调度效果。 3 整合s v m 与量子遗传算法。利用网格软件g r i d g a i n 的m a p r e d u c e 机制对 调度算法进行修整，引入多线程技术进行算法整合，使其成为一个可以独立运行 的网格任务调度器。 4 构建新的网格测试平台。为了测试本文的网格任务调度算法，以s i m j a v a 为基础，开发出一个新的网格测试平台s i m s n o w ，该平台可以在模拟过程中有效 地对网格节点的性能进行更改，而且用户可以对时间费用函数进行重写，从而提 高系统的可扩充性。 1 4 2 创新点 1 利用s v m 技术研究任务调度系统，使得调度算法可以有自适应的功能。 在过去的研究当中，要使得算法有自适应能力就要求对任务的上次运行时间进行 1 0 第一章绪论 记录，以推断出当前的任务时间，但是这种做法有他本身的缺陷，如网格节点不 是连续运行的，这就使得任务的间隔太大，从而导致系统偏差。而且对于节点的 性能突然下降，从而导致上次的任务运行时间增大，而之后系统的预测时间就会 变大，从而导致资源的浪费。加入s v m 技术后，整个网格任务调度系统能有效 地增加其自适应功能，使任务调度更加合理化。 2 将量子遗传算法应用到网格任务调度系统中。在利用支持向量机对网格节 点的性能进行预测的基础上，把量子遗传算法应用到网格任务的调度中去，是网 格任务调度研究中一个比较新颖的探索，撰写这方面内容的论文比较少。实验结 果表明，这样改进后的调度算法可以使系统获得比传统遗传算法与m i n m i n 算法 获得更高的效率。 3 研究g r i d g a i n 网格软件，把其框架从应用的高度上升到研究高度。对 g r i d g a i n 框架进行重点研究，并且对m a p r e d u c e 模型进行分析，最后让新的调 度算法与m a p r e d u c e 模型进行有机整合。 4 开发出新的网格测试平台s i m s n o w 。此平台是为修正g r i d s i m 的缺陷而开 发的。 1 5 文章结构 本文主要分