（计算机应用技术专业论文）基于思维进化计算的网格资源分配研究.pdf

墓t 思堆进化计算的月格黉! 自e 分二研究 基于思维进化计算的网格资源分配研究 摘要 网格是继万维网之后出现的一种新型网络计算平台，支持各种资源的 共享和广泛的协同工作，消除因地理位置造成的对计算资源的访问限制。 网格的最终目的就是提供给用户与地理位置无关、与具体的计算设施无关 的通用的计算能力，使人们在使用网格计算能力时就像现在使用电力一样 方便。 在网格环境下，由于资源具有广域分布、异构、动态等特| 生，要把这 样一个环境里的各种分散的资源管理起来，满足不同应用程序的需要，是 一项十分复杂而具有挑战性的工作，网格资源管理和资源调度机制会对网 格应用程序的执行效果产生重要影响。因此，在网格技术的众多问题中， 资源调度成为研究最集中的问题之一。 本文研究了网格环境的特点和当前主要网格项目的资源管理和调度模 型，考察了已有的网格资源调度算法在目前网格资源调度中应用的优缺点， 完成了以下工作： 1 、对思维进化计算的优缺点进行分析，通过将其和禁忌搜索算法相结 合，优势互补，提高思维进化计算的效率，并将改进后的算法应用于解决 网格资源的静态分配问题，通过模拟实验对其有效性进行了验证。 2 、进一步将改进的思维进化计算与蚂蚁算法相融合，针对蚂蚁算法运 行初期信息素缺乏，算法速度慢的缺陷，利用思维进化计算的快速寻优能 l 于思镕t # 月格瓷9 0 习| 究 力产生信息素的初始分布，并将该融合算法应用于解决网格资源的动态分 配问题，通过模拟实验验证了该算法的有效性。 关键词：网格思维进化计算禁忌搜索蚂蚁算法资源静态分配 资源动态分配 ，1 r 大掌q l 士掌位诧丈基于思维进化 q - ：l l g 的, m 格翊! 嚣分e 研究 g r i dr e s o u r c ea l l o c a t i o nr e s e a r c hb a s e do n m 【i n de v o l u t l o n a r yc o m p u t a t i o n a b s t r a c t g r i da p p e a r sa f t e rw o r l dw i d ew e ba san e wn e t w o r kc o m p u t i n gp l a t f o r m i ts u p p o r t st h es h a r i n ga n de x t e n s i v ec o o r d i n a t e dw o r ko fd i v e r s er e s o u r c e sa n d a v o i d sa c c e s s i n gl i m i t a t i o nt oc o m p u t a t i o n a lr e s o u r c e sw h i c hi sg e n e r a t e d b e c a u s eo fg e o g r a p h i c a ll o c a t i o nd i f f e r e n c e t h eu l t i m a t eg o a lo f 鲥di st o p r o v i d et h eu n i v e r s a lc o m p u t i n gp o w e ri n d e p e n d e n to fg e o g r a p h i c a ll o c a t i o n a n dc o m p u t i n gi n 仔a 鼬m c t i e ，s ot h a tp e o p l eu s e 鲥d ，sc o m p u t i n gp o w e ra s c o n v e n i e n t l ya sp e o p l eu s ee l e c t r i cp o w e r n o w a d m i n i s t r a t i n g a l lk i n d so fd i s p e r s i v er e s o u r c e st os a t i s f yd i f f e r e n t a p p l i c a t i o nn e e d si sac o m p l e xa n dc h a l l e n g i n gj o bi ng r i de n v i r o n m e n t ，b e c a u s e 鲕dr e s o u r c e sh a v ed i s t r i b u t e d ，h e t e r o g e n e o u sa n dd y n a m i cc h a r a c t e r i s t i c s g r i d r e s o u r c em a n a g e m e n ta n dr e s o u r c es c h e d u l i n gm e c h a n i s mw i l lh a v eag r e a t i n f l u e n c eo nt h ee x e c u t i o nr e s u l t so f 鲥da p p l i c a t i o n s s o 鲥dr e s o u r c e s c h e d u l i n gb e c o m e so n eo ft h em o s ta r r e s t i v er e s e a r c hp r o b l e m sa m o n g 鲥d t e c h n o l o g i e s i nt h i s t h e s i s ，t h e c h a r a c t e r i s t i c so f 鲥de n v i r o n m e n ta n dr e s o u r c e m a n a g e m e n ta n dr e s o u r c es c h e d u l i n gm o d e l so fc u r r e n tm a i ng i r dp r o j e c t sa r e s t u d i e d t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fe x i s t i n gg i r dr e s o u r c es c h e d u l i n g g - i 大掌硬士掌t 诗丈 基于思维进化- v l - 算的罔格冒! 嗣【分簟e 研究 a l g o r i t h m sa r ea n a l y z e d t h em a i nr e s u l t so f t h er e s e a r c ha r ea sf o l l o w s 1 i n t e g r a t i n g m i n de v o l u t i o n a r yc o m p u t a t i o na n dt a b u s e a r c ha n d d e v e l o p i n g e a c hs t r o n g p o i n t sf u l l yt oi m p r o v et h ee f f i c i e n c yo fm i n d e v o l u t i o n a r yc o m p u t a t i o nb a s eo na n a l y z i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e s o f r n i n de v o l u t i o n a r yc o m p u t a t i o n t h ei m p r o v e da l g o r i t h mi sa p p l i e dt os o l v i n g t h es t a t i ca l l o c a t i o np r o b l e mo f 鲥dr e s o u r c ea n de x p e f i m e n tr e s u l t ss h o wt h a t t h ea l g o r i t h mi se f f e c t i v e 2 t h ei m p m v e dm i n de v o l u t i o n a r yc o m p u t a t i o na n da n ta l g o r i t h ma le c o m b i n e du l t e r i o r l y t h es p e e da tw h i c ht h ea n ta l g o r i t h mg i v e st h es o l u t i o ni s s l o w , b e e a n s et h e r ei s l i t t l ei n f o r m a t i o np h e r o m o n eo nt h ep a t he a r l y m i n d e v o l u t i o n a r yc o m p u t a t i o nh a st h ea b i l i t yo fs e a r c h i n gt h eo p t i m a ls o l u t i o n q u i c k l y s ot h ec o m b i n a t i o na l g 耐l r nu t i l i z e sm i n de v o l u t i o n a r yc o m p u t a t i o nt o g i v e i n i t i a ld i s t r i b u t i o no ft h ei n f o r m a t i o np h e r o m o n e t h ec o m b i n a t i o n a l g o r i t h mi sa p p l i e dt os o l v i n gt h ed y n a m i ca l l o c a t i o np r o b l e mo f 鲥d r e s o u r c e a n de x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f e c t i v e k e yw o r d s ： g i r d ；m i n de v o l u t i o n a r yc o m p u t a t i o n ；t a b us e a r c h ；a n t a l g o r i t h m ；r e s o u r c e s t a t i ca l l o c a t i o n ；r e s o u r c ed y n a m i c a l l o c a t i o n 基于思维堪e 化计算的用格费嗣i 分珊究 1 1 引言 第一章绪论 网格是继万维网之后出现的一种新型网络计算平台，能够充分吸纳各种计算资源， 并将它们转化成一种随处可见的、可靠的、标准的、同时还是经济的计算能力。这里的 计算资源不仅包括各种类型的计算机，还包括网络通信能力、数据资料、仪器设备甚至 是人等各种相关的资源。网格忽略了各种具体计算资源的外在形式，而把它们的内在本 质计算能力抽取出来，使人们在使用网格计算能力时就像现在使用电力一样方便。 目前，国内外的政府、研究机构、r r 企业等都在网格领域进行了大量的资金投入、 理论研究和项目实践，网格基础设施的理论与技术研究得到了飞速的发展，已成功应用 于分布式超级计算、分布式仪器系统、数据密集型计算和远程沉浸等四个领域，网格正 逐渐走入人们的生活，必将成为人们生活不可缺少的一部分。 在网格环境下，由于资源具有广域分布、异构、动态等特性，要把这样一个环境里 的各种分散的资源管理起来，满足不同应用程序的需要，是十分复杂的一项工作，网格 资源管理和资源调度机制会对网格应用程序的执行效果产生重要影响。因此，在网格技 术的众多问题中，资源调度成为研究最集中的问题之一。 本文课题是在上述背景下确立的，通过对网格环境的特点和当前网格项目的资源管 理和调度模型进行分析，考察了已有的网格资源调度算法在目前网格资源调度中应用的 优缺点，将思维进化计算引入网格资源调度中，通过对其进行改进，提出了网格资源静 态和动态两种调度算法，并通过模拟实验证明了算法的有效性。 1 2 网格概述 1 2 1 网格的界定和三个发展阶段 1 、网格的界定 被称为现代数据网络之父的因特网发明者l e nk l e i n r o c k 教授在1 9 6 9 年曾预言，“我 们也许将看到一个计算机公用事业( c o m p u t e r u t i l i t i e s ) 普及的时代，就像用电话那样， 服务到每个家庭和办公室”。随着网格技术的产生和发展，这个时代已经到来。究竟什 么是网格? 这个问题一直以来存在争议，美国阿岗( a r g o n n e ) 国家实验室的资深科学 家、美国g l o b u s 项目的领导人、网格之父i a nf o s t e r 曾在1 9 9 8 年出版的网格：2 1 世纪信息技术基础设施的蓝图一书中这样描述网槲1 1 ：“网格是构筑在互联网上的一组 新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一 体，为科技人员和普通用户提供更多的资源、功能和交互性。互联网主要为人们提供电 囊 - e - 西大掌司e 士掌位论文基于思雉进化计算的网格资崩瞪尹己研究 子邮件、网页浏览等通信功能，而网格功能则更多更强，让人们透明地使用计算、存储 等其他资源”。这个定义强调网格作为“公用事业”，意味着透明的、安全的访问，有效 的资源管理和利用，而互联网算不上这样的“公用事业”。 其实，从不同的角度和侧重点不同，对网格的定义也会不同。2 0 0 2 年7 月2 2 日， i a n f o s t e r 又指出了判断网格的三点判断标准【2 】：第一，不带集中控制的资源共享和协同 工作；第二，使用标准、通用开放的协议和接口；第三，高服务质量，包括响应时间、 流量、可用性和安全性。 2 、网格的三个发展阶段 从2 0 世纪9 0 年代中期，i a nf o s t e r 提出“网格”这个术语以来，网格已经从最初只 是表示先进的科学和工程的分白式计算框架，发展成为包含了从先进的网络到人工智能 的方方面面。网格的发展经历了三个阶段【3 1 ，第一阶段是网格的萌芽阶段，开始于2 0 世纪9 0 年代早期，这个时期的网格是把超级计算机节点连接起来，为高性能应用提供 计算资源。“元计算”的概念就是在这个时期提出的，它源于c a s a 项目，该项目是为 分布式超级计算建立测试环境。有人将元计算看成是“通过网络环境使用的强大的、对 用户透明可用的计算资源”【4 1 ，这也是网格计算的最初称呼。第二阶段的网格，时间大 致从2 0 世纪9 0 年代中期到晚期，这个时期出现了比较重要的开创性和奠基性的研究项 目，如i - w a y 、g l o b u s 、l e g i o n 等，它们被提到了很高的高度。这个时期主要的工作是 支持大规模数据和计算的中间件的开发，建立了面向协议和模块的网格体系结构。目前 是网格发展的第三阶段，也是蓬勃发展的阶段，涌现出大量的关于网格研究、开发和应 用的项目。这个阶段的主要特点是面向服务的网格结构，2 0 0 2 年2 月发布的开放网格服 务结构( o g s a ) 把万维网服务和计算网格结合起来，建立了以服务为核心的网格结构。 1 2 2 网格的特点和分类 网格是一个地理位置上广泛分布的基础设施，它要为大量不同的用户提供不同种类 的高质量服务，这要求网格必须具备以下基本特点： l 、虚拟性 网格中的资源和用户经过抽象，把实际的用户和资源虚拟化为网格用户和网格资 源。网格用户使用标准、开放、通用的协议和界面，可以访问网格中的各种资源，但实 际的用户和物理资源是互不可见的，资源对外提供的只是一个虚拟化的接口。 2 、共享性 网格是一个提供资源共享的场所，网格中的各种资源都可以破共享使用。多个用户 可以共同使用网格中的一个资源，一个用户也可以同时使用多个网格资源。 3 、集成性 网格把地理位置上分布的、来自不同管理域的功能各异的各种资源集成在一起，成 为一个有机的整体，并协调分散在不同地理位置的用户使用这些网格资源。用户不仅可 以使用单个资源提供的功能，而且能够联合使用多个资源的合成功能。 4 、协商性 2 雪 l 一 广西大掌q 【士掌位论文 | i 于思维造化计算的网格资鞠t 分：研究 网格支持资源的协商使用，资源请求者和提供者之间可以通过协商得到不同质量的 服务，满足不同的实际需求。 从不同的角度，网格有不同的分类，最为广泛采用的分类方式即按照网格的客体进 行分类。 按照网格客体的不同层次，网格可以分成三个层次，由低到高分别为：资源网格、 信息网格和知识网格，如图1 - 1 所示。资源网格，包括计算网格和数据网格，直接构建 于互联网之上，为上层应用提供数据层面的连通和共享。信息网格位于网格操作系统之 上，为上层应用提供信息的无缝共享，包括数据库的构建和信息的发现、连通、处理等。 更高层次的知识网格，从底层的数据和信息中发掘、处理和应用知识。由于每一层都有 与1 幺层提供的功能一致的用户接口，网格应用可以直接基于网格操作系统，也可以处于 信息网格或知识网格之上。 网格应用 知识网格 信息网格 资源网格( 计算网格、数据网格) 网格物理基础( 国际互联网、各种局域网) 图1 - 1 网格的层次分类结构9 l f i g u r e1 1t h eh i e r a r c h i c a lc a t e g o r ys t r u c t u r eo f g r i d f 3 】 按照网格客体对象不同，网格分为数据网格、计算网格、服务网格。数据网格解决 数据的共享问题；计算网格为用户提供共享资源的良好接口和机制；服务网格以服务的 形式提供共享的手段，即人们可以把不同的资源加以封装用服务的形式提供给网格主体 使用。 1 2 3 网格研究的目的和意义 目前，世界上计算机的利用率很低，而许多应用领域都需要很强的计算能力，但是 从事这一应用领域研究的单位或个人拥有的计算资源却根本不能够提供实际所需要的 计算能力。这一计算机的实际使用情况和人们对计算能力的需求表明，一方面，有大量 的计算资源处于空闲状态，没有得到有效利用；另一方面，又有很多的应用问题由于没 有足够的计算资源可供使用而无法求解。 一直以来，人们在努力解决上述问题，产生了并行计算技术、集群技术、分布式计 算技术等，但是这些技术只是解决了一定管理域范围的有限资源共享。 今天，网络的普及、高性能计算机和高速网络作为低价商品组件的可用正在改变我 们使用计算机的方式。这种技术机遇使得使用计算机网络作为单独、统一的计算资源成 为可能。将地理上分布的广泛多样的资源包括超级计算机、存储系统、数据源和特殊种 t # i j 0 广西大掌司e 士掌位论文 l 于思雉避化计算的用格资嗣t 分配研究 类的设备组织连接起来，并且作为单独、统一的资源使用，这就形成了当今流行的“网 格”。网格的最终日标就是希望用户在使用网格计算能力时，如同现在使用电力一样方 便。用户使用的是与地理位置无关、与具体的计算设施无关的通用的计算能力。这样， 人们可以以一种全新的、更自由的、更方便的方式使用计算资源，解决更复杂的问题p j 。 首先，用户不再受到计算能力大小的限制。对于大多数用户来说，网格提供给他们的计 算能力足以满足其计算的需求，甚至可完成以前无法想象和无法完成的工作。其次，突 破地理位置的限制。用户不用花费很多钱购买设备，只要能够接入网格，足不出户，就 可以使用网格中遍布在世界各地的从便宜到昂贵的各种资源。突破了在使用资源时对位 置的限制，是网格最具突出意义的功能。最后，网格打破了传统的共享或协作方面的限 制。传统的资源共享只是允许数据文件的传输，网格资源的共享允许直接控制其他资源， 共享资源的各方在协作时可以以多种方式交流信息，充分利用网格提供的各种功能。 1 2 4 网格的体系结构 网格体系结构是关于如何建造网格的技术和规范的定义，包括划分和定义网格基本 组成部分、定义各部分的功能、描述不同部分之间的关系以及把这些部分集成在一起的 方法。可以看出，网格体系结构贯穿着两条主线，一个是“分”，即要清楚地说明网格 整体是由那些关键部分结合而成以及各个组成部分的作用机理、作用方式，另一个是 “和”，即要在“分”的基础上，将各组成部分按照某种机制组织和集成，形成一个具 有特定功能的整体对外提供服务。 目前影响比较广泛的网格体系结构是五层沙漏结构和开放网格服务体系结构 o g s a ( o p e n g r i ds e r v i c e a r c h i t e c t u r e ) ，下面分别加以介绍。 1 、五层沙漏结构 如图1 。2 所示，五层沙漏结构由下至上分别为构造层、连接层、资源层、汇聚层、 应用层。 构造层通过对局部的物理或逻辑资源的管理，向连接层提供对这些资源的管理和控 制界面。 连接层实现下层物理资源的相互通信，定义核心通信与认证协议，这是资源间互相 操作的前提。 资源层主要反映抽象的局部资源的特征，实现和监控单个资源的共享。 汇聚层协调解决多个资源的共享，实现多个资源的联合调度。 上述五层沙漏结构是f o s t e r 教授等在早期提出的【6 l ，最重要的思想就是以“协议” 为中心。由于各层协议数量不同，资源层与连接层作为最核心的部分，协议集应该尽量 小而且尽量标准化，这样，它们形成了沙漏模型的瓶颈部分。 4 j 女 ； - 基于思维进化计算的网格资葛e 分t t 研究 工具与阙 应用层 l 诊断与监控等， 汇聚层 l资源与服务资源与 i的安全访问连接层 i 裴糕篡k 构造层 图1 - 2 五层沙漏结构5 l f i g u r e1 - 2t h ef i v el e v e l sh o u r g l a s sm o d e la r c h i t e c t u r e l 目 2 、开放网格服务体系结构o g s a 0 g s a 是f o s t e r 教授等人在结合g l o b u s 网格计算工具包和w e bs e r v i c e 的基础上提 出的一种新的网格体系结构【7 】，是一种以服务为中心的“服务结构”。o g s a 定义了“网 格服务”( g r i ds e r v i c e ) 的概念，将一切都抽象为服务，实现服务的共享。这种抽象将 资源、信息、数据等统一起来，有利于灵活、一致、动态的共享机制的实现，使得分布 式系统管理有了标准的接口和行为。 w e bs e r v i c e 是为了解决异构平台上的应用集成而出现的，一个w e bs e r v i c e 就是一 个可以被u r l 识别的软件应用【8 】，它的接口和绑定可以被x m l ( e x t e n s i b l em a r k u p l a n g u a g e ) 描述和发现，并且可以通过基于i n t e m e t 的协议直接支持与其他基于x m l 消息的软件应用的交互。网格服务是一种w e bs e r v i c e ，具备了原来w e bs e r v i c e 的所有 有利因素，能够解决发现和激活永久服务的问题，但是在网格中，大量的是临时服务， 因此o g s a 对w e bs e r v i c e 进行了扩展，使得网格服务可以支持临时服务实例，并且能 够动态创建和删除。 由于在整个异构网络上工作，存在许多诸如操作系统之间的通信、需要访问基于不 同文件系统的文件等复杂问题，当前的w e bs e r v i c e 标准还没有解决这些问题，因此需 要下层的网格软件提供服务支持。g l o b u s 网格计算工具包是一种基于社团的、开放结构 及源码的服务的集合，解决了安全、信息发现、资源管理、数据管理、通信、错误检测 以及可移植等问题。g l o b u s 可以被看成基于底层服务之上的元计算框架，并且可以以 a p i 方式提供对外的接口，以便其他研究人员在其基础上开发各种应用执行环境。目前， g l o b u s 工具包在世界上的许多网格项目中被使用。 w e bs e r v i c e 提供了基于x m l 的组件式开放标准化软件，而网格计算则满足了海量 5 广西大掌硪士掌位餐 ，： 基于思维进化计算的用格资嗣t 分曩二研究 商业数据分析所需的c p u 资源要求，因此，o g s a 将原来主要在科技领域应用的网格 技术进一步转移到工商业领域。 1 3 网格资源管理和分配 网格资源管理系统( g r m s ) 是网格计算系统的重要组成部分，要实现包括资源的 组织、定位、发现、调度、分配、确认、进程创建以及准备所需资源的其他活动。由于 网格资源具有许多传统系统中的资源所不具备的特点，使得网格资源管理系统面临以下 挑战：要隐藏网格资源的异构性，为用户提供统一的访问接口；要屏蔽网格资源的动态 性，保证用户请求的访问质量；要尊重资源的本地管理机制和策略，使资源更好地为网 格用户服务；要仔细审查网格用户的请求，确保网格资源的安全和资源拥有者的权益。 资源调度是资源管理的核心部分，它的重要性显而易见，无论是特定任务的执行性 能，如时间、费用等，还是整个系统的吞吐率、资源利用率都受到资源调度质量的决定 性影响。 由于网格系统的异构和动态属性，以及运行于网格系统之中的应用程序对于资源的 不同需求，使得资源调度成为很复杂的设计问题。 1 3 1 网格资源 网格资源是网格中所有可以被主体请求使用的实体的总称，包括计算机软件、计算 机硬件、设备和仪器等。计算机软件资源包括系统软件、应用程序、数据等；计算机硬 件资源包括处理器、存储器、硬盘以及其他计算机设施：设备和仪器包括通信介质、天 文望远镜、显微镜、传感器等。除了上述物理资源外，还有在网格设备旁工作的人类资 源，人类资源包括人的知识、能力等多种因素，是网格上最具有伸缩性的资源。 网格资源种类很多，功能差异也很大，从不同的角度可以分成不同的类别。 根据资源能否移动可以分成可移动资源和不可移动资源。 可移动资源指使用网格的命令、操作可以从一个位置移动到另一个位置的资源，如 数据、程序、代码等。不可移动资源是需要使用机械力量才能移动的资源，如硬件、设 备等。 可移动资源会引起诸如备份管理、一致性等许多不可移动资源没有的问题，资源的 移动管理是网格资源管理的基本功能之一。 根据资源是否可重复使用的特性可以将资源分成可重复使用的资源和不可重复使 用的资源。 可重复使用的资源指可以被多次使用的资源，如内存、存储介质等。不可重复使用 的资源是消耗性资源，只能使用一次，如计算周期、通信带宽等。 根据资源是否可复制的特性可将资源分为可复制资源和不可复制资源。 可复制资源可以通过指令或服务请求，生成一个资源的多个副本，用同一个名字或 相同的属性访问该类资源，可以找到多个相同的物理实体，如数据、应用程序、服务等 6 ，t，。#vi _ 南 | i 于思翊。进化计算的用格资嗣【分衙完 是可复制资源。不可复制资源不能通过指令或服务请求产生副本，如设备、仪器等。按 名称访问不可复制资源，找到的物理实体是唯一的。 网格资源和以往的集群系统、并行系统、分布式系统中的资源相比，资源的种类和 功能多样性都大大增加，所以网格资源具有一些以往系统中的资源不具备的特点： 第一，异构性。网格资源种类繁多，功能各异，访问接口不尽相同，本地管理系统 不同，共享规则不同。同样是计算机资源，操作系统可能不同，即使相同的操作系统， 版本、语言也可能不同。 第二，动态性。网格中的资源可以自由地随时加入和离开网格系统，网格资源的可 获得性、资源贡献给网格用户使用的能力、网格资源的负载都是不确定的，随着时间的 变化而变化。 第三，自治性与二分性。网格资源有自己的本地管理机构，网格管理系统必须尊重 本地管理者，不能把网格的意愿强加给资源。正是由于网格资源最终都是由具体的资源 拥有者提供，除了一部分专用的网格资源是专门提供给网格用户使用之外，大部分的资 源都是同时作为网格用户可以使用的网格资源和资源拥有者自己使用的本地资源。资源 的使用原则是网格作业所能进行的操作和拥有的权限要保证资源本身的安全工作和资 源拥有者的合法权益以及使用该资源的其他网格用户的安全。 1 3 2 网格资源管理系统模型 目前，网格资源管理系统模型主要包括分层模型【9 1 ( h i e r a r c h i c a lm o d e l ) 、抽象所有 者模型( a b s t r a c to w n e r m o d e l ) 、计算经济( 市场) 模型【1 1 1 2 1 ( c o m p u t a t i o n a le c o n o m y m a r k e tm o d e l ) ，还有上述三种模型的混合模型。 l 、分层模型 分层模型是在网格论坛的第二次会议中提出来的，现有的网格项目大多数采用这种 模型结构，该模型包括调度器、信息服务器、域控制器、监控器、作业控制器等网格服 务组件，这些组件能够协调工作，适应网格环境的特点，较好地解决了网格计算环境给 资源管理所带来的一些挑战性问题，如：站点的自治性、底层的异构性以及联合分配问 题等。 按照逻辑功能划分，分层模型主要包括被动组件与主动组件两部分。 被动组件包括： ( 1 ) 资源：资源具有所有者、消费者、共享特性以及具体的描述形式，典型的资 源如c p u 时问、磁盘空间、网络带宽等。 ( 2 ) 任务：是资源的消费者，包括传统的计算任务和非计算任务。 ( 3 ) 作业：是分层的实体，可能有递归的结构，由予作业或任务组成，此结构的 叶子是任务。 ( 4 ) 进度表：是在时间约束下，一个作业中所有任务到资源的映射集合。一个作 业有一个或多个进度表。 7 一 连 ， j _ * 广西大掌习l 士掌位论文 | i 于思堆避化- f r 算的用格资源分蕾二研究 主动组件包括： ( 1 ) 调度器( s c h e d u l e r s ) ：根据定义好的优化目标，为用户提交的作业制定一个 或多个进度表，调度的单元是作业，即一次映射作业中的所有任务。 ( 2 ) 信息服务：描述与资源管理系统相关的信息，如资源、作业、调度程序等， 它不需要特别的访问策略。 ( 3 ) 领域控制代理：也称为局域资源管理器，控制局域的一部分资源，负责提供 自己的状态信息，可能包含内部调度程序。控制域外的调度者对资源是不可见的，不能 够控制资源，控制域内的内部管理对于超级调度者( 称为m e t a s c h e d u l e r s 或 s u p e r h e d u l e r s ) 来说是一个黑盒，超级调度者不干涉控制域内的内部调度。 ( 4 ) 分配代理：通过与领域控制代理协商的方式获得资源，按照进度表的安排执 行调度、运行任务。 ( 5 ) 用户：负责提交作业给资源管理系统进行处理。 ( 6 ) 访问控制代理：负责决定是否接受额外的作业，若系统已饱和工作，则拒绝 或延迟作业的执行。 ( 7 ) 监控器：负责跟踪作业的进程，获得作业的运行状态并决定是否需要重新调 度。 ( 8 ) 作业控制代理；负责管理整个作业的执行过程，能够作为用户的代理人和作 业的持久控制点，负责在资源管理系统的不同组件之间进行协调。 具体操作步骤为； 用户将作业提交给作业控制代理，作业控制代理再调用访问控制代理来检查作业的 资源请求，判断添加此作业到系统当前的工作池中是否安全，若安全则把作业传递给全 局调度器，调度器利用网格信息服务进行资源发现，并和领域控制代理协商来确定当前 资源的状态和可用性，然后，由调度器计算出资源映射集合并将这些资源映射传递到分 配代理。分配代理根据进度表中的资源计划与领域控制代理进行协商，有时可能需要进 行资源预约，领域控制代理通过本地资源调度器分配具体资源。分配代理协调多个领域 控制代理负责任务的执行。监控器跟踪作业的进程，若性能低于预期标准，则决定是否 需要重新调度。 2 、抽象所有者模型 实际上，网格用户使用资源时，并不关心谁是资源的所有者，他们所真正关心的是 资源使用的机制、条件和付费等。通常，与用户交涉的实体并不是真正的资源所有者， 而是与资源所有者交涉的经纪人，但用户可以抽象地把它们当作资源的所有者。任何网 格资源都能被一个或多个“抽象所有者”( a o s ) 所代表，客户和a o 之间以协商的方 式对获取和使用资源进行安排，但在实际使用时还有许多尚待解决的问题，如用户如何 发现拥有合适资源的a o 。该模型目前还没有具体的网格计算系统采用。 a o 的一般结构就像快餐店，为了从a o 处获取访问资源，客户与a o 在订购窗口 就资源是否可用、价格如何以及获取资源时所使用的协议进行协商。若客户对协商结果 8 | i 于思维进化计算的网格资鞠【分：研完 满意，则进行预订，否则终止协商。预定后，客户可在规定的时间通过交货窗口从a o 处获取资源。 该模型中定义的资源分为三类：即工具( i n s t r u m e n t s ) 、管道( c h a n n e l s ) 和复合 体( c o m p l e x e s ) 。其中，工具是逻辑上某时某地都存在的资源，管道是负责在两个工 具之间传输数据和信息的资源，而复合体则是二者的组合。a o 并不是完全调度者，因 为一个调度程序应该能够获得资源，并在该资源上分配任务和监管任务的执行，而a o 的主要功能仅仅是获取资源，将资源利用率最大化等其他问题都交给客户来解决。 3 、计算经济( 市场) 模型 网格环境中的资源是广域分布的，并且属于不同的资源所有者，它们有自己的管理 机制和策略，对不同的用户收取不同的资源使用费用。这样，计算经济模型自然就成了 有效的资源管理方法之一，它能够使资源所有者更积极地提供资源的共享与更新，实现 资源的供需平衡。在计算经济环境中，资源用户希望最小化费用，而资源所有者希望最 大化他们的投资回报。这就需要一个网格资源管理系统提供合适的工具和服务来使资源 用户和所有者表达他们的要求，并且协调二者的关系。网格资源管理体系结构的计算经 济模型综合了上述分层模型和抽象所有者模型的实质。 计算经济模型的主要组件包括用户应用程序、网格资源代理、网格中间件和局部资 源管理者( 本地调度器) 下面简要介绍一下这些组件： 网格资源代理使用中间件进行服务，协调用户资源需求和网格资源之间的矛盾。它 的工作是负责资源发现、资源选择、应用软件绑定、数据和硬件资源、初始化计算、适 应网格资源的变化并且以一个单一、整体的资源形式把网格呈现给用户。 网格资源代理的组件有： 作业控制代理、调度器、网格探测器、交易管理器和执行代理。其中，作业控制代 理是系统中的一个重要组件，负责管理系统的作业，如调度的产生、作业的实际创建和 作业状态的保持，并与客户、调度器和分派器进行交互；调度器负责发现和选择资源以 及进行作业分配；调度器的资源发现是通过网格探测器来实现的，网格探测器通过网格 信息服务、鉴别授权主机和跟踪资源状态信息来进行资源的发现；交易管理器在资源选 择算法的指导下制定资源访问费用；执行代理负责作业在所选择的资源上的执行，并定 期更新作业控制代理中作业的执行状态。 网格中日j 件通过资源代理来对网格用户和资源间的匹配服务提供帮助。网格中间件 提供的核心服务包括：远程进程管理、资源的合作分配、存储访问、信息、安全和授权 等。 网格中间件的组件包括： 交易服务器、价格算法和收费系统。其中，交易服务器是负责与资源用户进行协商 以出售资源的访问权的资源所有者代理，它的目标是最大化资源的利用率和资源所有者 的利润；价格算法描述资源所有者向用户收取费用的方式；收费系统负责记录资源使用 情况，并根据资源代理和交易服务器达成的协议向用户收取费用。 9 墓于思缱进化计算的用柏鞠! 嗣t 分配研究 局部资源管理者负责通过局部资源来管理和安排计算，并提供数据库、存储设备等 资源。 基于供求原则的计算经济模型提供了对资源的分散管理能力，能够适应环境和用户 需求的变化，目前，已有很多网格项目采用基于计算经济模型的资源管理系统为网格用 户提供服务。 1 3 3 网格资源分配 l 、资源调度的目的 资源调度是为了完成用户提交的任务和满足用户提出的要求，把网格中的所有可用 资源，包括计算资源、存储资源和网络资源等等，进行匹配，以找到最好最合理的资源 分配方式和资源调度策略。为用户的任务选择合适的资源对该任务的执行效率具有决定 性的影响，在网格这样一个分布、动态、管理权分散的环境中，资源调度是十分困难的 问题，所以它是网格技术研究中最关键的问题之一。 2 、资源调度的方式 资源调度的方式分为集中式调度、分层式调度和分布式调剧”l 。 集中式调度在网格中只有一个调度中心，负责调度网格中的所有资源。这样，资源 调度系统知道网格中的所有资源的信息，对于一个应用可以更高效地产生资源调度方 案，比较容易实现系统负载平衡。但是，当整个系统比较大时，该调度系统很难掌握所 有资源的状况，并且调度系统会成为瓶颈，如果由于错误使得调度系统出现故障，就会 影响整个网格系统，所以集中式调度比较适合小型网格，在已有的网格系统中，属于这 种类型的系统有c o n d o r 、l s f 、n i m r o d 等等。 分层式调度方式由两层乃至更多层的调度系统组成。对两层系统来说，处于上层的 调度系统称为全局调度系统，处于下层的调度系统称为局部调度系统或本地调度系统。 这种结构的优点是比较容易从全局范围进行系统调度，位于高层的调度系统可以绝对地 控制低层系统，但它同时也带来一些问题，当系统规模较大时，全局调度系统会成为系 统瓶颈，一旦瘫痪，系统就无法继续运行。改进的办法之一是使用多个全局调度系统， 每个系统都可以独立向下层节点发送命令。目前，大部分网格系统都采用这种结构，如 g l o b u s 、l e g i o n 等等。 分布式调度在网格中有多个调度中心，各个中一心是平等的。该种方式的优点是具有 很强的可扩展性和容错能力，系统内任何一个节点发生故障都不会对整个系统造成太大 影响，缺点是调度中心之间的通信量比较大，由于不能掌握网格中的所有资源的信息， 所以很难找到全局最优的资源分配方案，这种调度结构在实际应用中很少被采用。 3 、资源调度策略的分类 从不同的视角可以把网格中的资源调度策略分成不同的种类，下面介绍一下常用的 分类【1 4 】。 根据调度策略的目的，资源调度分为面向应用的调度策略、面向系统的调度策略和 面向资源市场的调度策略。 1 0 墓于思维避化计算的网格翻! 嗣t 分蕾研究 面向应用的调度策略从特定任务的角度来衡量每个可能的调度方案，从中选择能够 最大程度满足特定任务要求的调度方案。当然，不同的任务，要求可能不尽相同，通常 的要求是尽量缩短任务的执行时间，其他要求诸如在使用收费资源时最小化费用或要求 优先使用某个资源等。目前，网格中大部分资源调度策略都属于这一类，由于该类策略 完全不考虑调度方案对整个系统的影响，所以，如果网格中仅采用这一类策略，会影响 整个网格的性能。 面向系统的调度策略是从整个系统的角度来衡量每个可能的调度方案，从中选择能 够最大程度提高整个系统的性能，如吞吐率、资源利用率、负载平衡的调度方案。由于 大规模的网格包含多个管理域并且任务种类繁多，如果把整个网格作为一个系统，它的 性能将无法衡量。所以，可以把整个网格划分成多个系统，每个管理域作为一个系统， 由域中的管理者来进行系统级的资源调度。在系统内采用面向系统的调度策略，在客户 端采用面向应用的调度策略能在一定程度上取长补短，同时兼顾应用任务和系统整体的 性能。 面向资源市场的调度策略是由澳大利亚m o n a s h 大学的r a j k u m a rb u y y a 最早提出 的，它的主要思想是把网格环境和市场环境进行类比，用户作为买方，而资源的拥有者 作为卖方，资源调度的过程就是买卖双方的交易过程，并把宏观经济学和微观经济学的 各种模型应用到网格资源调度过程中，如拍卖模型、邮件广告模型等。 按照调度阶段，可以将网格资源调度分为静态调度和动态调度两种，这两种调度都 是目前研究的热点【”】。 静态调度是在调度执行前做出所有的决定，这需要事先知道资源相关信息和性能参 数，虽然它没有考虑到网格资源动态变化的特性，但是，静态调度在资源调度的研究中 也很重要。我们可以采用静态调度来为将束某一时刻要运行的一组作业设计一个有效的 调度，可以用静态调度来分析异构计算系统，得出去掉( 或增加) 一个特定的硬件或者 网格中的一个子网有什么样的影响，还可以用静态调度来评估一个动态系统运行后的性 能，检验系统对可用资源的利用率。 动态调度是在调度执行期间做出部分或所有的决定，在任务运行过程的各个阶段 中，不断地根据运行时各计算节点的负载情况，将任务动态地分配到各个计算节点上， 并对其上的任务数进行动态调整，尽可能使系统中各计算节点的负载达到基本平衡。在 网格环境中，由于资源的动态性，例如，资源利用率在不时变化，动态调度更能适用于 这样的环境，满足应用的性能要求。但是，虽然动态调度比静态调度灵活、有效，但实 现起来复杂度相对较高。 目前，对于网格资源调度并没有一个明确的最好方法。由于在网格这样的环境中把 用户的任务最优地映射到异构的机器上已经表明通常是n p 难问题，所以通常的方法是 采用一些启发式方法来找到一个近似最优解。启发式方法借用自然、社会的方法解决非 确定、并行结构、自适应性问题，在本地搜索的基础上通过一定措施避免落入局部优化， 已成功地解决了各种组合优化问题，是目前最通用的网格资源调度方法。但是，大多数 在这个领域中现存的研究都还是很理论化的，因为即使是采用启发式搜索，对于大规模 ，“ 基于思维避化计算的用格翻峙曩分i 研究 的搜索空间来说也是需要昂贵代价的。所以，在网格环境中，我们应该继续探索出实际 而且有效的启发式搜索算法来满足应用的需求。 1 3 4 现有的网格资源管理和资源分配分析 网格的研究已经从美国和欧洲推广到了世界各个国家和地区，各国政府投入大量资 金支持网格项目的研制和开发，已经取得了大量的研究和应用成果。 在国外，有很多网格项目致力于网格资源调度方面