（通信与信息系统专业论文）网格中任务调度与负载均衡问题研究.pdf

西北工业大学硕士学位论文 摘要 摘要 随着科学技术的快速发展，很多科学计算和复杂应用系统的计算薰越来越 大，需要由多种机器组成、多个系统合作、多个科学仪器设备相连的网络虚拟超 级计算机来进行处理。这种将地理上分布、异构的多种计算资源通过高速网络连 接起来，共同完成计算闯题的技术被称为网格计算或者无缝、可扩展计算。网格 计算为解决超大规模、超级复杂的计算密集或者数据密集的问题提供了十分有效 的途径。 然而，对于复杂的网格系统，其性能因资源和任务的不确定性等因素而实时 变化，因此网格的资源发现与管理、负载平衡是网格计算中需要解决的关键性问 题。针对网格的资源发现机制，任务分配和负载均衡等问题，本文进行了研究。 论文首先分析了网格历史、研究现状和网格的体系结构。给出了一种新的资 源发现模型，该模型不仅保留了层次式管理模型的“层层传递”和基于多a g e n t 式管理模型的“移动a g e n t 搜寻”这两种信息收集策略，而且还提供了常规通道、 上访通道和下查通道三种特殊通道以及相关的“上访下查”策略。其次研究了一 种基于预测的动态负载平衡策略，对各种预测算法进行研究分析，找出一种最合 适于预测网格结点的指数平滑预测算法，并且使用该预测算法的动态负载平衡策 略在网格试验床上进行了试验，通过与其它的策略的比较，验证了该策略的优越 性。文中对以f o 为主的网格，也给出了一种负载平衡的解决方法。 最后针对飞机维修与故障诊断的实际需求，设计了一个飞机维修信息网格系 统，并对维修信息网格中的信息融合、数据挖掘方法进行了研究和初步设计。该 网格系统可以实现各种维修信息资源的充份共享，提高飞机维修效率。 综上所述，本文对网格系统的资源发现、负载平衡等问题做了深入的研究， 并完成了一个飞机维修信息网格系统的初步设计，为开展网格计算技术的下一步 工作，建造网格系统奠定了基础。 关键词：网格计算，负载平衡，任务调度，飞机维修信息网格 西北工业大学硕士学位论文 a b s t r a c t a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y ，m a n ys c i e n t i f i c c o m p u t i n ga n dc o m p l e xa p p l i c a t i o ns y s t e mn e e dm o 豫a n dm o r ec o m p u t a t i o n b u t f o rn o w a d a y ss i n g l ec o m p u t e r ，e v e nt h es u p e rc o m p u t e rh a sn os u c hc a p a c i t yt o h a n d l et h i sc o m p u t i n gt a s k w es t i l ln e e dt h ev i r t u a ln e t w o r ks u p e rc o m p u t e r c o n s i s t e do fm a n yd i s t r i b u t e dc o m p u t e r s , m a n yk i n d so fc o r p o r a t es y s t e m s ，e v e u s c i e n c ei n s t m m c o t so r e q u i p m e n t s 。t h i s n e w a p p r o a c h a b o u tc o n n e c t i n g g e o g r a p h i c a l l yd i s t r i b u t e d , h e t e r o g e n e o u sr e s o 懒t o g e t h e rb yt h eh i g h - s p e e d n e t w o r kt os o l v et h en u m e r i c a l l yo rd a t ai n t e n s i v ep r o b l e m si sk n o wb ys e v e r a l n a m e s 。s u c ha ss e a m l e s ss c a l a b l ec o m p u t i n g , # o b a lc o m p u t i n g , a n dm o r er e c e n t l y g r i d - c o m p u t i n g t h eg r i ds y s t e m s c a ng i v eu s e r st h ev i r t u a lu n i f i e dr e s o u r i n t e r f a c ea n de x e c u t e 氇et a s ks u b m i t t e db yt h eu s f r so nt h ef i t t e s tf c s o u r c en o d d y n a m i c a l l y h o w e v e r , 鲥畦p e r f o r m a n c et h a tc a nb ed e l i v e r e dv a r i e sd y n a m i c a l l yd u et o r e s o u r c e sc o m p u t i n g , t a s ku n c e r t a i n t y , a n ds oo n t h e r e f o r e ，r e s o u r c ed i s c o v e r i n g a n ds c h e d u l i n g , l o a d b a l a n c i n ga r ek e yi s s u e s 。 t h i sp a p e rf i r s ts t u d yt h e h i s t o r yo fg d dc o m p u t e r , o u t l i n et h es y s t e ms t r u c t u r eo f g r i dc o m p u t i n gs y s t e m ；r e f e r r i n gc u r r e n tr e s e a r c hr e s u l t so nc o m p u t a t i o n a l r e s o u r c e d i s c o v e r ya n dm a n a g e m e n tm o d e l ，c o n s t r u c t af e e d b a c ka n d i n v e s t i g a t i o nb a s e dr e s o u r c e sd i s c o v e r ym e t h o d 。l o a db a l a n c i n gh a sae f f e c t i v e e f f e c ti ng r i d p r e d i c t i n gt h ea b i f i t yo fe a c hp r o c e s s o ri st h ek e yo fd y n a m i cl o a d b a l a n c i n g , f i r s t , i n t r o d u c et h ep r e d i c t i o nm e t h o do fe x p o n e n t i a ls m o o t h i n g , t h e n d i s c u s st h es e l e c t i o no fp a r a m e t e r 口al o a db a l a n c i n ge x p e r i m e n ti sd e s i g n e d ， w h i c hd e m o n s t r a t et h a td y n a m i cl o a db a l a n c i n gb a s e do nf o r e c a s t sv i ae x p o n e n t i a l s m o o t h i n gh i g h l ye f f e c t i v ec o m p a r e dw i t hs t a t i cl o a db a l a n c i n ga n dn ol o a d b a l a n c i n g a tl a s td e s i g naa i r c r a f tm a i n t a i ni n f o r m a t i o ng r i d ( a m i g ) ，t h i sp a p e r g i v ed e t a i l sa b o u tt h ed e s i g no fa m i g 【w h i c hc a ns h a r et h er e s o u r c eo fa i r c r a f t m a i n t a i ni n f o r m a t i o n i nc o n c l u s i o n ，t h i sp a p e rs t u d yt h er e s o u r c ed i s c o v e r ya n dl o a db a l a n c i n go fg r i d c o m p u t e r , t h e nd e s i g naa m i gs y s t e m ，w h i c hp r o v i d el o t so fu s e f u lt h e o r yf o r a d v a n c e dr e s e a r c h 1 释 西北工业大学硕士学位论文 a b s t r a c t k e yw o r d s ：g r i dc o m p u t e r ，l o a db a l a n c e ，t a s ks c h e d u l i n g ，a i r c r a f tm 洳t a i l l i n f o r m a t i o ng r i d i v 西北工业大学硕士学位论文 1 1 研究背景 第一章绪论 网格计算( g r i dc o m p u t i n g ) 是当今计算机科学领域新兴起的一个具有很高 学术价值和应用价值的研究领域。高性能计算已经成为许多科学和工程实践的关 键技术。科学家们也越来越多地使用超级计算机来研究复杂问题，例如可以用来 预测复杂的非线性现象，或者是在做实验之前，就可探索物理参数的变化规律， 甚至还可以用来模拟现实世界中所发生的某些事件。然而，尽管超级计算机的能 力在不断的增长，仍然有许多应用无法实现。因为这些应用往往需要处理能力强 大的超级计算枫的支持，但是超级计算机造价极高，通常只有一些国家级部门， 如航天、气象等部门才有能力配置这样的设备；另一方面，某些应用对计算的要 求非常高，即使是现在最大的超级计算机也无法提供他们所需的资源，这时就需 要将高性能计算依托i n t e m e t 或其它高速网络将速布世界各个角落的能力千差万 别的计算资源联结在一起，形成大规模的几乎可以无限扩展的计算能力；制造技 术与工艺、体系结构设计在不断提高着单个计算设备的能力：网络技术的进步已 经可以使一种支持有效并发执行的方式，汇聚地理上分散的计算资源成为可能。 这种新的网络计算模式基于动态的、异构的和跨区域的协同资源共享问题求 解的计算模式就是网格计算。在这个网络计算时代，孤立的计算机系统、软件和 应用将被网络化的产品和服务取代。世晃将被互联成为一个开放的、一体化的、 资源共享的全球电脑网络，即用全球大网格( g r e a tg l o b a lg r i d ) 以满足人类的 需求。 1 1 i 网格计算的概念和目的 网格计算的直接起源为元计算( m e t a c o m p u t i n g ) ，它最早是由s m a r t 和 c a t l e t t l 引入的。网格计算的概念是在i - w a y 项目中提出来的。虽然对网格计算 的研究已经有了很大的进步，但是到目前为止，关于什么是网格计算，还没有一 个普遍接受的定义，关于网格的概念的分歧和争议依然存在。那么究竟何谓网格 计算，1 9 9 8 年网格：一种未来计算基础设施蓝图一书中写到：一个计算网 格是一个硬件和软件基础设旌，此基础设施提供对商端计算能力可靠的、一致的、 普遍的和不昂贵的接入。2 0 0 0 年一篇“网格剖析”的文章中，提出社会和策略 西北工业大学硕士学位论文 问题。指出网格计算关心的是：在动态的，多机构的虚拟组织中协调资源共享和 协同解决问题，其核心概念是：在一组参与结点( 资源提供者和消费者) 中协商 资源共享管理的能力，利用协商得到资源池共同解决一些问题。随后，协议标准 化在使异构系统间交互操作和使其成为公共基础设施的重要性被人们逐渐认识。 由此，i a nf o s t e r z 等人进一步完善网格定义，认为网格是满足以下三个条件的系 统： 1 、协调非集中控制资源。网格整合各种资源，协调各种使用者，这些资源和使 用者在不同的控制域中，比如，个人电脑和中心计算机；相同或不同公司的 不同管理单元：网格还解决在这种分布式环境中出现的安全，使用费用。成 员权限等问题。否姗j ，只能算本地管理系统两替网格。 2 、使用标准、开放、通用的协议和界面。两格建立在多功能的协议和界面之上， 这些协议和界面解决认证，授权，资源发现和资源存取等基本问题。否则， 只算一个具体应用系统而非涮格。 3 、得到非平凡的服务质量。网格允许它的资源被协调使用，以得到多种服务质 量，满足不同使用者的需求，如系统相应时阊，流通量，有效性，安全性， 及资源定位。使得联合系统的功效比其备部分的功效总和要大得多。 因此我们可以这样认为：+ 阿格就是一个集成的计算与资源环境，它能够把整 个互联网集成为一台巨大的超级计算机，实现全球范围的计算资源、存储资源、 数据资源、信息资源、专家赉源、设备资源甚至是人才资源等的各种相关的分散 分布的各种资源的全面共享。我们可以认为网格存在如下的含义： l 、从概念上，网格韵目标是资源共享和分布协同工作。网格的这种概念可以清 晰地指导行业私企业中各个部门的资源进行行业或企业整体上的统一规划、 部署、整合和共享，而不仅仅是行业或大企业中的各个部分子自己规划、占 有和使用资源。 2 、网格是一种技术，为了达到多种类型的分布资源共享和协作，网格计算技术 必须解决多个层次的资源共享和合作问题，制定网格的标准，将i n t e r n c t 从 通讯和信息交互的平台提升到资源共享的平台。但是目前并行计算、分布计 算、中间件等现行技术远远没有解决多组织之间资源的共享问题，以及广域 范围的多系统之间联合处理和计算等网格计算所面临的关键问题。因此，网 格计算技术研究具有独特性、紧迫性和挑战性。 3 、网格是基础设施，是通过各种网格综合计算机、数据、设备和服务等资源的 基本设施。这种设施的建立，将使用户如同今天我们按需使用电力一样，无 需在用户端配套大量的全套计算机系统和复杂的软件，就可以简便地得到网 格提供的各种服务。这样，设备、软件投资和维护开销将大大减小。 西j b 工业大学硕士学位论文 网格的概念将根本的改变人们对“计算机应用”的看法，这怒一种全新的、 雯方霞懿谤葵方式，轻松赛瑷理今勰决苓了鹃受翔复杂豹翊莲。潮貉是黛熬耄力 喇概念提出来的，网格的最终目标是希望用户在使用网格时，就如同现在使用电 力一撵方便。建设阚格兵蠢翔下戆意义： 首先怒解决计算能力的限制，网格可以联合并放大社会的计算能力；藏次是 辩决遮理能置豹黢测，把谤冀能力送裂你夔桌垂；焉次是第药资源，瑰今驰计算 机资源利用率远不充分，很多应用又缺乏资源。礴格不仅可以把“资源”邀到你 的察瑟，瑟可以把“应用”放到蹦接中完成。最蘑是网搐据破了健统共事与捺锋 方面的限制。网格以“虚拟组织”的方法，实现了全社会瓤围的资源共享妁服务 协谁。 1 1 2 网格计算的发展过程 网格燎以电网作为比拟的对象而开始建立和发展的，也就是说，类电阚的使 麓状况羲兔疆辂计算懿嚣标所求，繇靖，掰户哭燮把设备的插头耩强秘稽麴“插 座”就可以使用网格中的资源。虽然现在的网格计算离此嗣标还将甚远，假它在 翊耀专应麓瓣摆动下已经不蓊发麓、丰富秘完善，院起最裙豹并彳予寝羧藕、元计 算婷，可以说是发展迅猛。一般认为它缀历了三个阶段： 第一除段耱芽羯：2 0 整纪粥年代警鬻，囊蘩楚予毙瓣静蜜验蒎戳及一些嚣诗算 实验； 第二戆段实验蘩：2 0 藿笼年代孛宠攒，篦魏i - w a y 璞鼙，学术往磷究顼髫 g 1 0 b u s 、l e g i o n 以及一些应用； 第三殓段发震絮：本毽纪激来，爨蕊了太爨豹弱臻诗算矮瓣，峦鬻了影嫡缀大豹 组织一全球网格论坛g g f ( g l o b a lg r i df o r u m ) ，同时网格计算也不再仅仪局限 于辩学硬炎，工业爨与学拳器联羹援致力手使瘸格谤篓在凳广泛瓣领域褥劐接广 和应用。 网掇按照技术的发震鬏痔霹以如下划分；1 9 9 5 冬戳翦戆弱辏把怒级诗算援萤 点涟接起寐以提供高性能计算服务，代表项目有f a f n e r 和i w a y ；1 9 9 5 - - 2 0 0 0 年的网格以开发支特大规模数据穰计算的中闯馋势莓标，淡梅建嚣起骆议秘模块 的网格体系结构为中心，代表项目g l o b u s ，l e g i o n ；2 0 0 0 年至今的嗣格已建立面 向服务的嘲格结构为特征，代表体系结构为开放网楱服务终橱o g s a ( o p e ng r i d s e r v i c e sa r c h i t e c t u r e ) ，典型基础设施为o g s i ( o p e ng r i ds e r v i c ei n f r a s t r u c t u r e ) _ 手e i w s r f3 ( w e bs e r v i c e sr e s o u r c ef r a m e w o r k ) 。 翟前，网格已经成为全球的研究热点，发展潮格被认为是下一代i n t e r n e t 的 核心任务之。从网格技术发展的总体来嚣，其趋势如下： 3 蹶北= c 业大学硪士学位论文 1 、标准化趟势。2 0 0 4 年1 月，w e bs e r v i c e s 标准与o g s a 标准的融合一、s r f 框架毅提爨来了，将发震袋为未采鹣鼹臻赫振准 2 、技术融合趋势。g l o b u s 项目看到tw e bs e r v i c e s 的巨大潜力，在2 0 0 2 年迅速 将g l o b u st o o k i t 瓣嚣发转寓tw e bs e r v i c e s 乎套，试圈麓o g s a 在隧掺瞧赛 一统天下。基于o g s a 之胼，网格的一切对外功能都以网格服务( g r i ds e r v i c e ) 来体现，势借助一魑瑷成戆、与乎台无关瓣技本，如x m l ，s o a p ，w s d l ， u d d i 等，来实现这些服务的描述、查找、访问和信息传输等功能。这样，一 切平台及历使用技术的异掇性郝拔羼菠。髑声谤越网辏服务畦，援本裁无瓣关 心该服务燎c o r b a 提供的，还怒n e t 提供的。 3 、大型化趋势。美国政府攀在网接技术的基础研究上，每擎投入蚣经费藏懿这 5 亿美金；i b m 在2 0 0 1 年8 月宣布，经投入4 0 多亿美元进行“网格计算创新 计划”( g r i dc o m p u t i n g i n i t i a t i v e ) ，全恧支持网格计算。i b m 成为g l o b u s 的首 席合作伙伴，还怒o g s a 标准的制定者乏一。英阑政府投资1 亿英镑，用以 研发“英豳国家嬲接”( u k n a t i o n a lg r i d ) 。我雷也拨出上亿元用予c h i n ag r i d 糨荧的研究。 1 1 3 国内外网格计算项目简介 网格计算的重要战略意义及其广阔应用前景，使其成为当今吸引众多研究人 员耨基大资众授入豹骚究熬赢。继学零赛之瓣，各国竣麝襄巍盈赛毽分豢窝韵了 一系列的研究项目。 攀兹蚕繇主旁影糖夔凭令网牾诗舞磅究瑗嚣魏芩； 1 、g l o b u s o g s a 6 ，1 3 1 0 b u s 熄美国阿岗国家实验室的研发项日，全球1 2 所大学 翻嫒究规撼参与了该瑗嚣。g l o b u s 豹主癸耩究爨拣骞秀令，一令楚秘格按术 的研究，涉及资源管理、安全、信息服务投数据管理等网格计算的关键理论： 二楚挺应约软馋野发积标壤鹃铡定，其钵成暴是毙在套耱擎台上运行麴鼹擦诗 算工具软件( t o o l k i t ) ，开发适合大型系统运行的大型应用程序。g l o b u s 项目 还涉及到蚓接应用豹开发及实验瘴翁建立，帮助掇划窥组建大型静鄹接实黢平 台。 g l o b u s 的最新发展是由g l o b u s 缎织和i b m 在2 0 0 2 年1 2 翅子多幸忿多举移懿 g g f ( g l o b a lg r i df o r u m ) 会议上发布的开放网格服务体系o g s a ，o g s a 汇聚 了万缎网服务秘网格计算的成果，它将服务定义为一个网终功能的实体，提供对 计算资源、存储资源、网络、程序和数据库等的访问。 2 、l c g i n7 ，l c g i n 是弗吉尼亚大学的研究项髓，是面向对象技术在嗣格计算领域 西北工业大学硕士学位论文 应用的重要实例，支持透明的调度、数据管理、容错、站点自治和各种安全选 项。它将网格计算视为一个世界范围的抽象计算机，其设计目标是让用户在 l e g i o n 环境中资感觉到“一台”大的计算机，而网格计算用户在这台大计算机 上进行程序设计。在l e g i o n 中，一切都是对象，l e g i o n 规定了对象交互的消 息格式和高级协议、对象的一组方法描述其接口，但是对编程语言和具体的通 信协议没有规定。l e g i o n 的体系结构支持反省，允许用户提供自己的类对象来 改变系统级的对象支持体制，它也定义了核心对象的接口和基本的功能，用于 支持系统的基本服务。然而，面向对象方法也面临一些问题，例如很难支持预 留应用和服务的交互。 3 、c o n d o r 。，c o n d o r 项目开发、部署和评估支持在大规模分布资源集合上进行 高吞吐计算的机制和策略。c o n d o r 环境采用分层体系，支持串行和并行应用。 c o n d o r 中的资源提议和请求通过其分类公告语言c l a s s a d 描述。c l a s s a d 使用 平板结构化数据模型描述资源，提供相应的查询语言以允许公告发布方在资源 提议或请求中说明约束条件。c o n d o r 可视为平板结构的计算网格。它使用采 纳了混合名字空间的可扩展模式，其存储信息的网络目录采用x 5 0 0 或l d a p 技术。资源发现基于资源信息周期性的发布和集中式的查询，其调度器是集中 式的。c o n d o r 不支持质量服务。 4 、n i m r o d g ，n i m m d - g 是一个网格资源代理，由四个关键构件组成：任务管理 引擎、调度器、分派器和智能主体。任务管理引擎支持插入用户自定义的调度 器、定制应用或问题解析环境。分派器使用g l o b u s 服务将n i m r o d - g 智能主体 部署到远程资源上以管理分派任务的运行。n i m r o d g 调度器则可根据用户服 务质量需求中说明的能力、费用和可用性等租借适合的资源和服务。n i m r o d g 支持资源的发现、选择、调度与用户任务在远程资源中的透明运行。n i m r o d - g 相关的研究成果还包括一个成为g r i d s i m 的工具集，提供复杂的设旌以支持网 格资源和应用调度的建模和模拟，可用于评估调度算法的性能。 5 、a p p l e s 9 ，应用级调度项目a p p l e s ( a p p l i c a t i o nl e v e ls c h e d u l i n g ) 着重研究 和开发在计算网格中调度单个应用的智能主体。a p p l e s 智能主体根据应用和 系统信息选择一组可行的资源集，并通过其它资源管理系统运行应用任务。 a p p l e s 框架包含有支持参数化类型应用和m a s t e r w o r k e r 类型应用模板，允许 在智能主体中应用相关的调度器。a p p l e s 智能主体嵌入到应用中以在网格计 算环境中进行资源调度，因而对应用而言将作业映射到资源的调度是集中式 的，但实际运用的各个任务则由本地的资源调度器负责。 6 、n e t s l o v e ”，n e t s l o v e 是一个网格应用工具，提供基于远程过程调用的数值计 算编程环境。它有三个部分组成：服务的请求者，服务调度与维护者，以及服 西北_ = ：c 业大学硕士学位论文 绪论 务的提供暂。n e t s l o v e 提供了独立于实现语言的计算表达语言，客户端使用该 滔富表达请求共掇交绘n e t s l o v e 餐疑圭髂，该管辘主俸将该请求突给会逶熬 计算资源熹处理，相应的负载平衡策略支持尽可能高效地使用计算资源以确保 巍，睦能。 7 、d a t a g r i d “，d a t a g r i d 项嗣基本思想是把生成的海艇数据分散到垒球的计算机 上进行处理，劳囱全球懿物理学家共同遴孬分叛。其核心孛瓣 孛系绞罄手 g l o b u s 构造。d a t a g r i d 的裳要功能包括：负载调度和管理，以适威数据的幼态 繁新分配、高并发的任务数和不阏国家娥翅瓣不鞫管理攘臻：数据管理，淡 支持统一韵名字空阔和统一的数据格式、数据的高速移动和复制、远程数据复 制实铡豹一致性；系缝检摭，以协助制定谴度蓑略，调整应用程序躲运行性娆； 构造层管瑷，对数爨众多奇臼基础构件提供灵活和有弹性的臀理，满足严格的时 闯约束条件，保迸蹙个系绕的容错性；海爨存储管理，震统一的接霜羼薮琴隧 蛄点豹数掰存储方式和处趣方式乏闯的差异，无缝融合分布的存储资源。 8 、u n l c o r e ，德国联邦教育秘研究部的u n i c o r 基项目，蔓要舍豫者为德圈的 嚣家磺究机构。它的露酌怒提供一襄软件，允许瑙户给远程高性煞计算机提交 自已的作业，而不嚣要知谳远程机器的操捧系统、数据存储格式、管理策龌和 过程。它最大胃煞鹣使用自己已有的万维湖技术。它为终端用户和计算中心都 提供了强大的运行随格的功能，具体有：简单方便地作业创建和控制；支持多 系统帮多赢俸盈；瀚态流豢控翻；遥过x 。5 0 9 证书榘成安余：访闻远程文彳申存 储和档案；支持科研和商业应用。用户接姻语言用j a v a ，工具用浏览器，授 权翔户哥滋遥过按秘访闻撩露遣穷豹u n i c o r e 资源。对那些重要和经常穰用 的腹用软件，u n i c o r e 的插件机制允许集成易使用的接口。 9 、s e t i h o m e ，麴髑大学稔宠程分授静s e t i h o m e 顼秘是对等计算静一个 成功典范。s e t i h o m e 照“s e a r c h f o r e x t r a t e r r e s t r i a l i n t e l l i g e n c ea t h o m e ” 懿缝写，该矮嚣在1 9 9 9 年裙舞始耱分毒予整赛各速翡2 0 0 万台个入毫藏缀成 计辫机阵列，用于搜索射电魍远镜信号中的外星文明迹象。项目正式启动以来， 已经窍三露万志愿尝参掇。媳爨麸据定熬键轰下栽瓣电羹运镜枝集熬谊惑片 断，并用自已的计算机在空闲时间运行分析，从中铎找宇宙中生命的迹象。项 星缀残，褒不到鼹每戆时阉霆，这静计篓方法基经宠戏了攀台诗冀瓿3 4 5 0 0 0 年的计算量。可见这种“蚴蚁搬山”式的对等计算的处理熊力十分强大。 l o 、e - s c i e n c e ，英国e - s c i e n c e 网格拔认为楚矮先逮豹翳辏续梅。应瓣主要集中 在科学研究类应用；整体缨构还远来调整成o g s a ，但已宵o g s a 的初步共 识。露前的状况是：每个应惩有一个p o r t a l 入墨，底层资源采鼹g t 2 、c o n d o f 、 数据库、文件w 曲s e r v i c e 等形式，p o r t a l 服务器端软件直接调用物理资源。 西北工业大学硕士学位论文 绪论 1 1 4 网格计算面临的挑战 网格随着研究和实际的深入，面临的挑战性问题越来越多的突显出来，下面 介绍一些网格计算面临的关键性问题： 1 、异构性( h e t e r o g e n e i t y ) ：网格环境中的资源是分布广泛的；从局域网到广域 网、从有线环境到无线环境等；网格资源的架构是差异的；从硬件体系机构、 操作系统到应用软件平台等不尽相同。这些具有多样性的网格资源从本质上看 是异构的。 2 、扩展性( s c a l a b l i t i t y ) ；互连网格可能从几个到数百万个。这可能造成随着网 格节点数量的增加而引起的性能下降。 3 、适应性( a d a p t a b i l i t y ) ：网格资源本身是动态变化的，有其可用性、性能、访 问策略等是根据应用需求和资源的实际使用情况等因素不断变化的，在虚拟组 织中，资源的部署也具有动态性，即资源是可能随时加入和撤销的。因此，资 源管理需要动态地调节以获得最佳的性能。 4 、自治性( a u t o n o m o u s ) ：网格资源没有也不可能有个集中的并且完全的控 制中心，不同豹资源有不同的组织机构所拥有，并有各自的负载管理、访问控 制等策略，节点整体动态加入或退出系统。网格资源的这些特征给网格作业管 理带来了实现上的困难和不可控性。 5 、安全性( s e c u r i t y ) ：由于有很多节点及用户，信息的安全是一个非常重大的 问题。 1 2 研究内容 为了充分、合理和安全利用网格资源以满足应用所需要的服务质量的要求， 网格任务管理、任务调度有着重要的作用，本文关注网格管理的问题研究，任务 管理包含内容众多而且复杂，限于时间和条件，本文主要针对网格环境中的任务 调度，任务在网格中的负载均衡加以研究。 1 2 1 网格任务调度 在网格环境中，满足某个任务的资源可能不止一个，但是该任务在这些资源 上执行获得的性能，付出的代价可能不一样，任务调度首先根据任务的需求，发 现满足条件的资源：然后从满足条件的资源中选择合适的资源，分配该任务：任 务获得这些资源后，可以运行，并且在任务管理机制的管理下运行；任务在资源 西北二 业大学硕士学位论文 绪论 上执行结束质，把占用的资源还给网格管理机构。在进行任务调度时必须对网格 资深豹壤援傣惠及辩掌握，掰骧营炎黎要研究获取瓣揍资源静方法，瑟资源鹣发 现，掌握资源信息后才能根据任务的需求进行任务调度，资源匹配。 1 2 2 负载平衡 对于一个实际的网格系统，由于任务到达的随机性，以及各处理节点处理能 力上的差异，当系统遁行一段时间盛，就会如现某些络点上还有缀多任务未究成 ( 称为超载) ，而另为一些缩点却已经处于空闲状态( 称为辍载) 酌情况。一个 网格系统要求各个结点机上所分配的任务可以尽可熊短的时间内并行完成，这样 才能有效趣秘用系统瓷源，提高系统豹稍用率。所以当系统巾出现严疆地轻载和 超载并存的情况，一方面超载结点上的任务蠛特处烈，另一方面轻载结点的空阂 是一耱瓷源滚费。如褥尽可熊豹避免这种空闲与超载并存酌情况，飘丽有效穗提 高系统的资源利用率，减少任务的平均相应时间。怒负载平衡研究的原因。 1 3 本文的主要工作 l 、分析研究了网格的体系结构，然后对在网格环境中的任务分配进抒深入研究。 曾先对资源的发现管瑾进杼研究，糖出了上访下蠢的方案来获取阏格资源驹信 息。接着分析任务调度算法进行，并对不间盼算法进行模拟比较其优劣；最后 磷究多级诵发葬法，着重毒尊论了三缀谣疫，并给出其实现算法。 2 、对静态负载均衡、动态负载均衡：谶行了深入研究，尤其娥基于预测的动态负 载殇衡。分析颈灏盼方法，寻我出一释台遥手网格环境酶颥测算法，预凋计算 网格结点的性能，并以此为依据进行负载平衡的任务调度。在一个试验网格平 台上进窍了验证试验，涯戮该方法懿有良葑效莱。滁了在计算两格酌负载平衡 研究，本文还对以为主的文件网格的负载平衡避 行了探讨，提出一些解决 方絮。 3 、设计一个飞机维修信息网格，将网格技术应用子实际的工程应用。着重研究 飞捉售惠黢会，跨数撵瘴戆数据挖攥方法等逡容。 1 4 论文的组织缝构 本文大 零上分受三令主要部分：第一部分是理论骄究，镦括第一第二章；第 二部分是针对网格环境研究任务分配与负载平衡，包括第三第四章；第三部分是 西北工业大学硕士学位论文 设计一个网格实现包括第五章。最后为第六章对本文进行总结。具体内容安排如 下： 第一章绪论 介绍网格的基本构成、概念、目的，目前的研究情况以及面临的主要挑战并 简要介绍了本文的内容。 第二章网格体系结构研究 本章对网格体系结构进行研究，按照网格技术的发展过程，讨论五层沙漏结 构、开放服务体系结构o g s a 。然后研究目前影响最为广泛的网格中间件g l o b u s ， 以及目前的发展趋势w e bs e r v i c e s 技术。 第三章网格结构下的任务调度方法研究 本章主要研究在网格环境下的任务调度方法，首先讨论“上访下查”的资源 发现方法；然后研究任务调度的算法，最后给出多级的调度策略并给出算法。在 对算法研究的过程中使用仿真模拟技术对不同算法的效率加以比较，并给出性能 曲线图。 第四章网格环境中负载均衡的研究 详细的讨论了网格环境中负载均衡的问题。动态负载均衡、静态负载均衡比 较讨论其优缺点。在计算网格环境中，研究了一种基于预测的负载平衡方法，并 进行了试验，获得较为满意的效果。对以i ( 3 为主的文件网格的负载平衡，本章 也加以研究，提出了一些解决方法。 第五章飞机维修信息网格的设计 本章主要将网格应用于飞机维修做设计研究，使用网格技术将飞机维修的各 种信息进行融合，初步设计出一个飞机维修信息网格，并针对数据挖掘技术做了 深入的研究。 第六章总结 本章总结了本文的主要成果，对未来工作进行展望。 9 蓖北工业犬学硕士学位论文 网格体系结构研究 第二章网格体系结构研究 2 。1 网格体系结构 霹格体系结祷就是关警搬秘建途隧接瓣技拳。窀给出? 题掺懿基本缝残毒功 能，描述了网格各组成部分的关系以及它们集成的方式或方法，刻画了网格有效 运转的枫越。到嚣裁鸯止，毯：较蘩要的鼹摄体系绪鞠主要燕两令，一令是f o s t e r 在2 0 0 1 年提出的赢层沙瀚结构；弱一个怒在m m 为代表的工业界的影响下，在 考虑到w e b 技术的发展与影响居，f o s t e r 等人结合了w e bs e r v i c e 提出数弹放慰 格服务结构( o p e ng r i ds e r v i c e a r c h i t e c t u r e ，o g s a ) 。 2 重立五瀑汐瀵缝梅 五瑶沙满结 鸯是释彩穗+ 努广泛豹缝构，该结梅的一个最黧臻静愚憨就是 以“协议”为中心，也十分强调服务与a p l ( a p p l i c a f i o np r o g r a m m i n gi n t e r f a c e ) 积s d k ( s o i t w a r cd e v e l o p m e n tk i t s ) 戆蘩要经，不过该臻擒主要侧重手定经静 描述而不烧具体的协议定义。 沙濑模鍪l 是l a nf o s t e r 簿久在簸裙静辩镁撵窭豹，叁筑淘上分潮是稳谶层、 连接层、汇聚层、威用层。构造层连接底层的本地资源和上层，主骚是用来为上 层访逸零蟪蜜滚搀供统一按日，羼薮各逮瓷添瓣雾梅牲；逡攘层定义了棱，豁阕穆 事务处理所需的通信和认诫协议，搬供了加密的安众机制，用于识别用户和资源； 资源层的爨议调蹋捧造瑟懿功能戬渗溺亵控潮本懿瓷源；凝聚瑟建立窿姿潆爱窝 连接层形成的协议瓶颈之上，主要负责多种资源的麸享；成用层存在于虚拟组织 中，是根攒任一层次定义的鼹务梅选戆。每一层夔a p i 都霹皴番传与特定瑟务 交换协议储息实现，应用可以调用厦高层的框架和a p i 库。 五层沙漏结梅掇握各缀成部分与共享炎源之闯戆距离，憋对共攀囊漂遴孬操 作、管理和使用的功能分散在五个不同的鼷次。越被下层就越接近于物理的共享 资源，因此该层与! | 毒殊资源耀关的成分藏比较多；越往上层就越感键不到共事资 源的细节特征。 五层沙漏结构的另外一个重要特征就怒沙漏形状( 如图2 1 1 ) 。冀悫在的含义 就怒因为各部分协议的数量是不同的，基于其最核心的部分，就能够实现上层各 西j e 工业大学硕士学位论文 阐格体系结构研究 种协议向核心协议的映射，同时实现核心协议向下层其它各种协议的映射。核心 协议在所有支持网格计算的地点都应该得到支持，因此核心协议的数量不应该太 多，这祥核心协议就形成了协议层次结构中的一个瓶颈。沙漏核心构思想可以和 。一觑。一 一、， 、 目录代理 ? ! 诊断与监控等；汇聚层 # ， i 羽安全访问 i 艨 ! !i !i !； !； ! i ! i ! ； ! i ! ! o i ，各韩资源比如计算机、存储、 、 ， 介质、网络、构造层 传感器等、 一一， 图2 1 微内祓的操作系统进行类比，邵操作系统只实现一些关键的基本功能，而把大最 与特定设备有关和与应焉有关的部分交给其它部分来完成。一个小的核心是有利 于移植的，也可以致较容易地实现和得到支持。资源是多种多样蘧，应用需求更 是复杂多变，飘此定义好这样一个核心部分的意义是很大的。 2 1 2 开放网格服务体系结构o g s a 开放网格服务体系结构( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ，o g s a ) 是继五层 沙漏结构之后最重要，也是目前最新的一种网格体系结构。o g s a 架构的四个主 要的层构成如豳2 - 2 。从下到上依次为：1 、资源层：资源的概念是o g s a 以及 通常意义上的网格计算的中心部分，包括物理资源和逻辑资源。物理资源龟括服 务器、存储器和网络。逻辑资源通过虚拟化和聚合物理层的资源来提供额外的功 堕i ! 三些查堂堡主堂垡笙奎 旦堡堡墨堕塑堑壅 能。2 、w e b 服务以及定义网格服务的o o s i ( o p c 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 ) 扩 展：o g s a 中所有网格资源( 逻辑的和物理的) 都被理解成服务。o g s l 规范定 义了网格服务并建立在标准w e b 服务技术之上。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 ) 这样的w 曲服务机制， 为所有网格资源制定标准的接口、行为与交互。o g s i 进一步扩展了w e b 服务的 定义，提供了动态的、有状态的和可管理的w e b 服务的能力，这在对网格资源 进行建模都是必须的。3 、基于o g s a 架构的服务：w e b 服务层及其o g s i 扩展 为下一层提供了基础设施：基于架构的网格服务。g g f 目前正在致力于在诸如 程序执行、数据服务和核心服务等领域中定义基于网格架构的服务。随着这些新 架构的服务的开始出现，o g s a 将变成更加有用的面向服务的架构( s e r v i c e o r i e n t e d a r c h i t e c t u r e ，s o a ) 。4 、网格应用程序：随着时间的推移，一组丰富的 基于网格架构的服务不断被开发出来，使用一个或多个基于网格架构的服务的新 网格应用程序亦将出现。这些应用程序构成了o g s a 架构的第四个主要层。 o g s l 扩展 w e b 服务层 圈围围困困回 堕 至 三 图2 2 构建o g s a 的两大支持技术是g l o b u s 和w e bs e r v i c e 。g l o b u s 是已经被科学 与工程计算领域广泛接受的网格技术求解方案，w e bs e r v i c e 是一种标准的存取 网络应用框架。 西北工业大学硕士学位论文 网格体系结构研究 2 2g l o b u s 网格中间件 高性能计算领域中，客户朋匣务器( g s ) 模型已经得到广泛的应用。对于单 一、固定的用户来说，c s 模型是一种成功的结构，它在各客户之间有效的实现 了服务器资源的共享。然而，c s 模型一样要求资源集中在服务器上，不能完全 支持分布资源的应用。同时，在客户端，每一个应用都必须开发特定的客户端程 序，不利于客户端应用程序的共享。在分布式环境中，无论是硬件平台还是软件 平台也做不到统一。 随着对c s 模型及其缺陷认识的深入，人们在客户端和服务器之间插入了一 个中间层，成为“中间件”。中间件是在计算机硬件和操作系统之上，支持应用 软件开发和运行的系统软件，它能够使应用软件相对独立于计算机硬件和操作系 统平台，为当今的大型分布式应用搭起了一个标准的平台，把大型企业分担的系 统和技术结合在一起，实现大型企业应用软件系统的集成，它提供的服务包括定 位、解析、授权、同步、数据格式转换等等。其体系结构如图2 3 图2 3 中间件的加入使得客户端不再直接与某个特定的主机或进程联系，而是与一 个一般的抽象的服务器进行交互。对于客户而言，真正的服务器和中间件提供的 服务是一致的。 2 2 1g l o b u s 的基本功能 g l o b u s 是美国a r g o n n e 国家实验室的研发项目，全美有1 2 所大