（计算机软件与理论专业论文）基于qos的网格调度算法研究.pdf

摘要 网格( g r i d ) 技术是近年来国际上兴起的一种重要信息技术，其目标是实现对 地理上广泛分布的大量异构资源进行共享。任务调度是网格技术的一个重要组成部 分，它要根据任务信息采用适当的策略把不同任务分配到相应的资源结点上去运行， 主要包括资源发现、资源匹配和任务执行三个部分。由于网格系统的异构性和动态 性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得任务调度变得 极其复杂。不好的资源发现方法和任务分配策略，将会增加任务的执行时间、降低 整个网格系统的吞吐量。 为此，本文对当前常用的资源发现和管理模型进行了研究，针对层次模型中的 “层层传递”导致的效率低下问题，提出一种基于资源类型的资源发现和管理模型， 该模型大大提高了资源查找和更新的速度；对当前国内外比较优秀的静态和动态调 度算法进行分析，着重讨论了比较经典的m i nm i n 算法以及q o sg u i d e dm i nm i n 算 法，在此基础上考虑到任务对服务质量要求的差异对调度算法的影响，提出了一个 较为合理的改进算法来有效地均衡负载、提高系统吞吐量。最后，采用g r id s i m 工 具包对所提出的算法进行了实验仿真，通过与m i n m i n 算法和q o sg u i d e dm i n m i n 算法的结果比较，表明改进后的调度算法更加高效。 硕士研究生张慧敏( 计算机软件与理论) 指导教师许日滨教授 关键词：网格计算；资源发现；任务调度；o o s ；仿真 r e s e a r c ho i ls c h e d u l i n ga l g o r i t h mb a s e do nq o s a b s t r a c t g r i di sa l li m p o r t a n ti n f o r m a t i o nt e c h n o l o g yr a i s e do ni n t e r n a t i o n a li nr e c e n ty e a r s w i t ht h ea i mo fm a k i n gp l e n t i f u lh e t e r o g e n e o u sr e s o u r c e sd i s t r i b u t e do nb r o a dg e o g r a p h y s h a r e db ya l lu s e r s t a s ks c h e d u l i n gi sa r ti m p o r t a n tp a r to fg r i dw h i c hu s i n ga p p r o p r i a t e s t r a t e g yt od i s t r i b u t ed i f f e r e n tt a s k st op r o p e rr e s o u r c en o d e sa c c o r d i n g t ot h ei n f o r m a t i o n o ft a s k t a s ks c h e d u l i n gi n c l u d e st h r e ep a r t s ：r e s o u r c ed i s c o v e r y , r e s o u r c em a t c ha n dt a s k p e r f o r m a n c e s i n c et h e 鲥ds y s t e mi sh e t e r o g e n e o u s ，d y n a m i ca n dt h ea p p l i c a t i o n s r u n n i n go nt h eg r i dn e e d sd i f f e r e n tr e s o u r c e s ，t a s ks c h e d u l i n gb e c o m e sv e r yc o m p l e x a b a dr e s o u r c ed i s c o v e r ym e t h o da n dt a s ka l l o c a t i o ns t r a t e g yw i l li n c r e a s et h e i m p l e m e n t a t i o nt i m eo f t a s k sa n dr e d u c et h et h r o u g h p u to f t h ew h o l eg r i ds y s t e m t h e r e f o r e ，t h ea u t h o rr e s e a r c h e di n t ot h ec u r r e n tc o m m o nr e s o u r c ed i s c o v e r ya n d m a n a g e m e n tm o d e la n dp u tf o r w a r da r e s o u r c ec l a s s i f i c a t i o nb a s e dg r i dr e s o u r c e s d i s c o v e r ym o d e lt o s o l v et h ep r o b l e mo fi n e f f i c i e n c yc a u s e db ys t a c kt r a n s f e ri n h i e r a r c h i c a lm o d e l ，w h i c hw i l li m p r o v et h es p e e do f r e s o u r c ef i n d i n ga n du p d a t i n gg r e m l y s h ea l s oa n a l y z e dt h ee x c e l l e n ts t a t i ca n dd y n a m i cs c h e d u l i n ga l g o r i t h m si nt h ew o r l d ， e s p e c i a l l y t h ec l a s s i c a lm i n - m i na l g o r i t h ma n dq o sg u i d e dm i n m i n a l g o r i t h m c o n s i d e r i n gt h ei n f l u e n c eo fd i f f e r e n tr e q u i r e m e n t so ft a s ko ns c h e d u l i n ga l g o r i t h m ，t h e a u t h o rp u tf o r w a r dap r o p e ra l g o r i t h mt ob a l a n c et h ec h a r g ea n di n c r e a s et h et h r o u g h p u t e f f i c i e n t l y f i n a l l y , t h ea u t h o ru s e dg f i d s i mt o o l st om a k es i m u l a t i n ge x p e r i m e n tt ot e s t t h ea l g o r i t l m as h ep r o p o s e d t h er e s u l to ft h e s i m u l a t i o ns h o w e dt h a tt h ei m p r o v e d s c h e d u l i n ga l g o r i t h mi sm o r ee f f i c i e n tc o m p a r e dw i t ht h em i n m i na l g o r i t h ma n dq o s g u i d e dm i n m i na l g o r i t h m p o s t g r a d u a t es t u d e n t ：h u i m i nz h a n g ( c o m p u t e rs o f t w a r e & t h e o r y ) d i r e c t e db yp r o f e s s o r ：y u e - b i nx u k e yw o r d ：g r i dc o m p u t i n g ；r e s o u r c ed i s c o v e r y ；t a s ks c h e d u l i n g ；q o s ；s i m u l a t i o n 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：讯数敬日期：跏年s 月哆目 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密一 ( 请在以上方框内打“”) 论文作者签名：；长酸埏日期：w q 年3 - 月化日 导师虢。0 之 眺闻年州妒日 ( 本声明的版权归青岛大学所有，未经许可，任何单位及任何个人不得擅自使用) 4 8 第一章绪论 第一章绪论 本章首先简单介绍了网格计算的应用和研究背景，然后重点针对网格资源发现 管理模型和任务调度这两个网格计算的关键技术，讨论了当前的研究现状和存在的 问题，阐述了本文要研究和解决的问题，并在本章最后部分勾画了本文的组织结构。 1 1 研究背景 随着信息技术的不断发展，超级计算机已经成为复杂科学计算领域的主宰。超 级计算机虽然是一台处理能力强大的巨无霸，但它造价极高，只有一些国家级的部 门，如航天、气象等部门才有能力配置超级计算机这样的设备。超级计算机的价格 显然阻止了它进入大众的工作领域。然而随着人们日常工作遇到的商业计算越来越 复杂，人们越来越需要数据处理能力更强大的计算机。于是，人们开始寻找一种造 价低廉而数据处理能力超强的计算模式。近年来，i n t e r n e t 技术、高性能计算机技 术和高速网络技术都有快速的发展，使地理上分布广泛的各种异构资源作为一个统 一的计算系统来使用成为了可能。由此构成了统一的计算系统，即网格计算。 网格计算【l 】的概念最早出现于1 9 9 5 年的i w a y 项目中，其中网格一词是借鉴于电 力网格【3 】的概念而提出的。人们在使用电力时，根本不需要知道它是水力发电、火 力发电，还是核能发电，也不需要知道这些电站位于何处。网格计算也希望当用户 接入网格后，就如同电力用户将插头插入电力网那样，根据需要得到计算与信息资 源的供应，而不必知道计算与信息资源来自何处，为用户提供与地理位置无关、与 具体的计算设施无关的通用计算能力。即网格计算的最终目的就是希望用户在使用 网格计算能力时，就如同使用电力一样方便。 网格计算是伴随着互联网而迅速发展起来的，专门针对复杂科学计算的新型计 算模式。这种计算模式是利用互联网把分散在不同地理位置的电脑组织成一个“虚拟 的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计算是由成 千上万个“节点”组成的“一张网格”。这样组织起来的“虚拟的超级计算机”有两个优 势，一个是数据处理能力超强；另一个是能充分利用网上的闲置处理能力。随着计 算机科学的发展，网格计算技术已经成为当前国内外研究的一个热点和前沿领域， 被称为是下一代的i n t e r n e t i l l 。 1 2 研究现状 近年来，网格研究取得了很大进步，并出现了许多与网格相关的研究领域。对 网格的这些研究领域，从不同的角度出发，可以有多种分类方法，例如，按所关注 的技术问题划分网格曾被划分为计算网格、数据网格、信息网格、知识网格、服务 网格等种类。而按应用问题划分网格又可被归类为科学计算网格、商务计算网格和 】 青岛大学硕士学位论文 个人计算网格。虽然不同的网格在体系结构和需要解决的问题类型等方面不尽相同， 但为了达到网格计算的目标，网格计算至少需要具备三种基本功能：任务管理、任 务调度和资源管理。任务管理：用户通过该功能向网格提交任务、为任务指定所需 资源、删除任务并监测任务的运行状态。任务调度：用户提交的任务由该功能按照 任务的类型、所需资源、可用资源等情况安排运行日程和策略。资源管理：确定并 监测网格资源状况，收集任务运行时的资源占用数据。 一个理想的网格系统应可以构建在当前所有硬件和软件平台上，给用户提供完 全透明的计算环境，它把众多同、异构的资源变成统一的虚拟计算资源提供给用户。 为实现这个目标，必须对资源发现和管理、计算任务的调度等方面进行更深入的研 究，提出更有效的模型、算法以及解决方案。 1 2 1 资源发现和管理 资源发现和管理的任务是在短时间内高效率的找到资源所在的节点，并对这些 计算资源动态变化带来的信息进行管理。在传统的单计算机系统和机群系统中，计 算资源的分布比较集中，计算在使用资源之前可以快速、可靠的进行资源定位，资 源的查找操作对计算性能的影响很小。在网格计算中，由于资源的广域分布以及现 有i n t e r n e t 存在的带宽和延迟限制以及网络的不可靠性，广域范围内的资源定位将 在很大程度上影响计算的性能。因此需要一种有效的资源发现机制解决广域资源的 快速定位问题。从资源的组织、发现和管理方式来看，目前国内外对网格资源管理 基本模型的研究主要体现为集中式、分布式、层次式和基于多a g e n t 式等四种形式。 集中式发现管理模型：在集中式的环境中，中心服务器存储共享资源可检索的 索引，所有可用系统的状态信息被聚集在该中心机上，每当客户机连接到服务器时， 它把其共享的资源索引和元数据传送给服务器。除此之外，它还可以通过询问服务 器找到任一可用资源。服务器接着会返回可匹配该询问的当前共享资源列表。当客 户机下载完它查找的可用资源列表后，客户机直接和列表中的节点连接以得到资源。 中央服务器不提供共享资源，资源也没有经过服务器。从概念上讲这种发现调度模 式是非常有用的，例如在计算中心，因为所有的资源在相同的目标之下被使用。在 这种情况下，即使缺乏网络带宽也可以被忽略。但是集中式发现管理模型实施的前 提是所有资源的状态信息必须是确定的，然而网格中的资源是以“动态的虚拟组织” 形式存在的，所以这种静态的约束严重影响了网格的自适应性和高扩展性。另外， 集中式发现管理模型所采取的是全局统一的管理策略，这又与不同的虚拟组织中各 自不同的本地管理策略相悖。所以全球规模的网格系统并不适合这种模式。 分布式发现管理模型【1 5 1 9 】：在分布式的系统中，没有一个中央服务器负责资源 的发现及调度，所有系统的状态信息也没有被集中在单个的结点上。该模型强调各 2 第一章绪论 个系统之间是对等的，过多注重系统内部资源的状况，忽视了系统间的配合，因此 虽然具有高度的可扩展性，但是却缺少了全局性的宏观调控能力。更重要的是，这 种分布式发现管理模型恰恰与网格发展的初衷一一大规模、大范围服务资源共享相 悖。 层次式发现管理模型：一种混合模型( 集中式和分布式模型的结合) ，即根据管理 域( 地域) ，以及具体应用因素，资源的数量和类型等因素，以站点资源为单位组成 树型结构，为资源的联合分配提供了一种管理机制。对于所有子树，父节点相当于 它们的联合分配器。与树型结构的资源信息服务相配合，在实际的资源调度过程中， 只要管理本节点所“拥有”的资源即可。这样，当在某一个子节点上提交了大型资 源请求的应用时，即需要联合分配时，该子节点可将请求快速地上传至父节点，而 父节点作为联合分配器，它拥有各个子节点的系统状态信息，从而可以快速判断自 身拥有的资源集合是否能满足应用程序的资源请求，并将资源请求分割开来，定位 和分配资源，将最终的资源组作为一个整体来操作，同样，如果这个父节点自身拥 有的资源仍不能满足需求时，它可以继续向上一层父节点传送请求，直到能够满足 应用需求并定位好资源。这种拓扑结构平衡了集中式搜索的效率和分布式搜索的自 治，负载平衡，健壮。但是，层次式发现管理模型需要将资源的动态更新信息一层 一层地由叶结点反溯到根结点，而这样的反溯过程需要较长的时间完成，因此，在 资源动态性很强、经常发生变化并且变化的频率较快的环境下，层次式发现管理模 型的这种层层反溯过程将不能很及时地反映计算网格资源的变化。 多a g e n t 式发现管理模型h ：通过将代理( a g e n t ) 小程序“释放”在所管辖的网络 内，进行计算资源的发现和管理。和上述三种资源发现管理模型相比，基于a g e n t 的发现管理模型具有快速、准确、可配置性和可控性强的优点，但是这种模型本身 对用来发现资源和汇报资源信息的代理( a g e n t ) 要求较高，同时对所辖网络中支持 该代理的计算节点上的s t u b 要求也比较苛刻。 1 2 2 网格任务调度算法 从本质上来说，调度是一个优化问题，原因是在网格中只有有限的资源可以使 用，而任务请求的数量可能会远远超出这些资源所能承受的能力。而且，优化可以 以多种形式进行。有时在所有网格资源之间的资源利用率非常重要，有时作业的吞 吐量则会非常重要。通常，许多组织机构都希望能平衡这些相互竞争的目标。由于 网格计算任务调度面临的是一个n p 完全问题【2 】，它引起了众多学者的关注，成为目 前网格计算研究领域的一个焦点 围绕着网格中的任务调度算法，国内外已做了大量的研究工作，先后提出了各种 调度算法。在这些调度算法中，对异构计算系统上的独立任务调度算法研究相对成 3 青岛大学硕士学位论文 熟，一些启发式映射策略已被用来调度独立任务到异构机器集合上，而异构机器集 合上的依赖任务调度算法贝研究较少。根据任务机器的映射策略在任务执行前是 否可以调整，可将这些启发式任务调度算法分为静态调度算法和动态调度算法两大 类： 静态调度算法1 3 0 , 3 2 是指所有的任务一机器跌射策略在执行任务调度前就已经全 部确定。由于该类调度算法有充足的时间投入调度计算，因而在实时性要求不高的 计算系统中，使用该类算法可能更好。但在异构环境中，由于资源的多样性，资源 的负载具有可变性，而静态调度算法不能随着负载的变化进行调整，可能会导致某 些资源负载过重问题。 动态调度算法【3 0 3 1 1 是指，部分任务一机器映射策略在执行任务调度期间根据实 际情况进行确定。动态调度算法能够有效的解决负载评估、作业选择和迁移等问题。 因此，在异构平台中，动态调度带来的负载均衡优势更加明显。但是动态调度算法 解决上述问题时需要付出较高的系统开销。 在众多的任务调度算法中，其调度目标就是要对用户提交的任务实现最优调度， 并设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( 0 p t i i i l a l m a k e s p a n ) 、服务质量q o s ( q u a l i t yo fs e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、 经济原则( e c o n o m i cp r i n c i p l e s ) 等。 ( 1 ) 最优跨度 跨度是一个最主要、最常见的目标，指的是调度的长度，也就是从第一个任务 开始运行到最后一个任务运行完毕所经历的时间。跨度越短说明调度策略越好。当 用户向网格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务。可见， 实现最优跨度是用户和网格系统的共同目标。 ( 2 ) 服务质量o o s 网格系统要为用户提供计算和存储服务时，用户对资源需求情况是通过o o s 形式 反映出来的。任务管理与调度系统在进行分配调度任务时，保障网格应用的o o s 是完 全应当的。 ( 3 ) 负载均衡 在开发并行和分布计算应用时，负载平衡是一个关键问题。网格系统更进一步 扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的调度。解决好系统的 负载均衡是一个非常重要的问题。 ( 4 ) 经济原则 网格环境中的资源在地理上是广泛分布的，而且每个资源都归属于不同的组织， 都有各自的资源管理机制和政策。根据现实生活中的市场经济原则，不同资源的使 用费用也应是不相同的。市场经济驱动的资源管理与任务调度必须使消费双方( 资源 4 第一章绪论 使用者和资源提供者) 互惠互利，才能使网格系统长久地发展下去。 1 3 存在的问题 尽管众多的研究者对网格计算做出了大量的研究工作，但是仍然存在以下问题， 制约了网格计算的执行效率： ( 1 ) 缺少有效的资源发现和管理模型以提供的宏观调控手段、快速响应资源 变动能力和快速查找能力：虽然集中式、分布式、层次式和基于多a g e n t 式等四种 资源发现和管理模型为我们提供了多种形态的发现和管理资源的策略，但是却没有 为我们提供一种对宏观调控、快速响应资源变动和快速查找等需求的整合。集中式 虽然具有较高的宏观调控能力，但它形成了一个瓶颈，妨碍了计算网格的可扩展性； 分布式虽然对网格计算的可扩展性提供了很好的支持，但是却过多地集中于局部， 缺少大局观；层次式是集中式与分布式的折衷，以树结构管理资源发现资源变动， 但是更新的资源信息需要一层一层地汇报给上层管理节点直至根节点，因此很难达 到快速响应的要求：多a g e n t 以可移动的a g e n t 方式收集资源变动信息，扩展性高、 自由性强，但是这种方式a g e n t 本身的要求比较高，对a g e n t 所需要附驻的s t u b 的要 求也比较苛刻。 ( 2 ) 缺少有效的任务调度算法将高效的调度效率和满足任务的q o s 需求等进行 整合：目前大部分调度算法的目标仍然是追求高执行效率，而没有考虑任务提出 的q o s 要求；有些调度算法虽然考虑了任务的q o s 要求，但其执行效率却不是很好。 1 4 本文的研究内容 本文对网格计算的核心之一一一任务调度算法进行研究。考虑到资源发现是 进行任务调度的基础，因此，本文对资源发现和管理模型也进行了研究。本文的创 新内容主要概括为以下几点： ( 1 ) 提出了一个资源发现模型 网格计算的基石是众多的计算资源，但是由于网格计算的根本特性是随机的共 享，众多的计算资源存在着种类繁多、服务不确定，能力不统一等性质。因此，针 对这个问题，本文提出了一个基于“资源类型”的三层资源发现和管理模型。 ( 2 ) 提出了一个改进的算法 一个运算量巨大的任务能否在网格环境下正确、快速和高效的运行和高效的任 务调度算法密不可分的。本文对已有的q o sg u i d e dm i n - m i n 算法进行研究，提出一 种改进的q o sg u i d e dk i l n m i n 任务调度算法，并进行了仿真实验，实验结果表明， 该算法在满足任务提出的q o s 要求的基础上，进一步提高了调度的效率。 5 青岛大学硕士学位论文 1 5 文章结构 第一章首先简单介绍了网格计算的应用和研究背景：然后重点针对网格计算中 的资源发现和管理模型、任务调度算法这两个关键技术，讨论了当前的研究现状和 存在的问题：接着阐述了本文要研究和解决的问题。 第二章提出了一种基于资源分类的资源发现和管理模型，并针对其核心模块进 行了详细的说明，最后定性地论述了该模型的优点。 第三章对任务调度定义、调度过程、常用的调度模型和性能预测模型进行简单 的介绍。 第四章对当前常见的各种静态和动态调度算法进行了分析和比较。 第五章提出了一种考虑任务q o s 要求的任务调度算法，并给出了该算法的类c 语 言描述和相应的分析。 第六章利用g r i d s i m 环境对上一章的算法进行了实验模拟，通过实验结果对多 种算法进行了分析。 第七章对整篇论文进行总结，并对未来工作进行展望。 6 第二章一种基于资源类型的资源发现模型 第二章一种基于资源类型的资源发现模型 我们在结合集中式、分布式和层次式等三种资源发现模型的基础上，提出了一 种改进的基于资源类型的资源发现模型( r e s o u r c ec l a s s i f i c a t i o nb a s e dg r i d r e s o u r c e sd i s c o v e r ym o d e l ，r c ) 。本章首先图文并茂地介绍了模型的总体结构，然 后对模型的核心模块进行详细分析描述，最后，通过定性比较揭示出模型的优点。 2 1r c 模型总体结构 r c 模型( 如图2 1 ) 采用三层管理结构，第一层是网格计算中的资源，这些资 源可按结点所分布的地理区域、连通性以及结点之问的相关性等因素进行分簇 ( c l u s t e r ) 。第二层是在每个簇中按照资源的类别设置的多个管理节点，每个管理节 点仅管理注册到该节点的资源和簇中的某一类资源，实现对资源的分类管理。第三 层是在每个簇中的管理节点之上设置的功能节点，每个功能节点在对簇中的管理节 点进行管理的同时还对簇中资源的请求进行转发。本模型通过基层计算资源的汇报， 及时发现新计算资源的加入和原有计算资源的退出。 图2 1r c 模型总体结构 由上图可以看到，在模型中有三种角色的节点：资源节点p e e r 、管理节点 m p ( m a n a g e rp e e r ) 、功能节点f p ( f u n c t i o n a lp e e r ) 。每个p e e r 都必须连接一个管理 节点咿，若干卿连接到一个功能节点f p 。若干个功能节点以全连接或者其他方式形成 一个在管理节点之上的第三层，也就是功能节点层。 7 青岛大学硕士学位论文 普通节点p e e r ( 即虚拟组织) 既可以是资源提供者( r e s o u r c ep r o v i d e r s p ) ，也 可以是资源请求者( r e s o u r c er e q u e s t o r s r ) 。当p e e r 为s p 时，它必须首先将自己 的资源信息注册到m p 上，并定时向h i p 发送资源更新信息。 管理节点m p 的作用是接受p e e r 或其它m p 的请求并在必要时通过功能节点f p 向其 它簇中的m p 节点转发，并定时将注册资源的更新信息向同簇中其他m p 转发。 f p 负责管理与它相连的m p 并接收其它f p 转发的资源请求信息，在自身管理的m p 中进行查询，并把查询结果发送给请求者。功能节点f p 是改进的管理节点，也可以 叫做“管理节点的管理节点”。 2 2r c 模型的几个定义和假设 r c 模型是一个不考虑资源节点拓扑动态变化情况下的资源发现模型，为了更好 的分析r c 模型，现给该模型作以下定义和假设： 定义1 网格资源信息组织模型 g = ( r ，m ，e ，d ，r f ) 其中，r 为网格中的所有资源节点集合；m 为网格中所有 管理节点集合；e 表示管理节点间的邻接关系：e ( m ) 为节点m 的邻节点集合，e ( m ) m ；d 表示资源信息在非注册管理节点上的转发，d ( r ) 为资源r 的感知节点。r f 为资 源注册函数，r f ：r - m 。 为方便表示，定义l r ( m ) 为管理节点m 上通过转发得到的资源集合：l r ( m ) = rl r r ，r f ( r ) = d 。l r ( m ) c r ，i 净u 。m l r ( m ) 。对于任意m l ，m z e m ，m 1 m 2 ，l r ( m i ) n l r ( m 2 ) = 西一 定义2 网格资源信息更新传播模型u u = ( g ，u p d a t e ( r ) ，p ，d ( r ) ) 。其中，u p d a t e ( r ) 表示g 中资源r 的变化，p 表示该 资源信息的更新在g 中管理节点间的传播策略，资源r 的变化会引起其注册节点上信 息的更新，并传播到r 的所有感知节点d ( r ) 。对于更新信息的产生节点m ( 即资源r 的 注册节点) ，p ( u p d a t e ( r ) ，m ) 表示资源更新信息转发的邻节点。 定义3 网格资源发现请求处理模型 ( g ，r e q u e s t ( r ( a ) ) ，s ，f ) - - l 其中，r e q u e s t ( r ( a ) ) 为查找请求，定义了资 源的各种属性要求a ；s 为查找起始信息节点集合；f 表示g 中信息节点间的查找请求 转发策略；l 表示在资源发现过程中找到的匹配资源集合。对于接收到的资源查找请 求，管理节点m 做以下操作：若请求资源与本地管理的资源类型相同，则在本地管理 节点进行查找，若满足停止条件则结束，否则根据资源类型和转发策略转发到相应 邻节点。 假设1 存在网格资源分类t ，且对于每一个网格资源，r r ，都有惟一的类型 t ( r ) ，t ( r ) t 。 8 第二章一种基于资源类型的资源发现模型 假设一个网格资源只有惟一的类型是为了表述的方便。一般的分类体系通常是 树形的，我们只考虑其中某个层次上的类型划分，不考虑类之间在概念上的层次关 系。 假设2 资源发现请求r e q u e s t ( r ( a ) ) 包含了对所请求资源类型的说明，记为 t 。( r ( a ) ) ，t 。( r ( a ) ) t ，或者t 。( r ( a ) ) 可以从资源属性描述a 中进行推断。 一般而言，对于一个特定的网格应用，需要将不同类型的资源组织成虚拟组织 ( v o ) 来满足应用的要求，整个资源发现的过程在逻辑上可视为多个单一类型资源发 现过程的组合。在存在标准资源分类的情况下，即便在资源请求中未做出显式的说 明，资源类型也易于从资源属性的描述当中进行推断。 2 3 资源发现过程 资源发现是由用户请求( r e q u e s t ) 发起的。也就是从p e e r 进行发起。该请求首先 被发送到该p e e r 的管理节点m p 。如果所需资源正是本m p 管理的一类资源，则在此m p 中进行查找，如果找到合适资源则返回查找结果给请求p e e r ；否则，就将请求转发 给同簇中存放此类资源的肝，并在其中进行查找。若仍未找到，则将该请求发给该 簇的功能节点f p ，由f p 将此请求转发给其他簇的f p ，并在其他簇中相应的m p 中进行 查找。算法如下： i f ( m p i 收到一个节点的资源请求) i f ( i p ，未存储此类资源) 发送请求给该簇中存储此类资源的m p i ； i f ( 在押i 中未发现合适的资源) 发送请求到f p ，由f p 将请求发送给其他簇的f p ： ) e l s e 在本地资源库中进行查找； i f ( 查找成功) 返回资源信息给请求者，查找结束； e 1 s e 发送请求到f p ，由f p 将请求发送给其他簇的f p ： 9 青岛大学硕士学位论文 e l s ei f ( m p i 收到m p j 的资源请求) 在本地库中进行查找； i f ( 查找成功) 返回资源信息给请求者，查找结束； e 1 s e 返回查找不成功给请求者； 2 4 资源信息更新过程 为了实现这种分层的资源发现机制，首先应该对资源信息很好地维护。新资源 加入，以及资源退出是资源维护的主要工作。在这里，节点位置有两层含义：一是 物理层：即资源节点在实际物理连接关系上形成的关系，对系统中的机器来说，按 照实际网络拓扑特性进行构建：另一层是逻辑层：即从所有计算资源的物理现状映 射得到的系统程序的数据结构。 信息更新包括注册该资源信息的m p 节点和感知该资源信息的归节点的更新两个 方面。注册该资源信息的m p 节点的更新是由连接m p 的p e e r s 定时向m p 发送自身资源信 息的变更情况，m p 收到更新信息后更新本节点资源注册信息，同时定时向感知此节 点中资源信息的m p 节点转发资源的更新情况。 2 5r c 模型的优点 如上文所述，在四种资源发现和管理模型中，集中式虽然具有较高的宏观调控 能力，但是却妨碍了网格的可扩展性；分布式虽然对网格的可扩展性提供了很好的 支持，但是却过多地集中于局部，缺少大局观；层次式是集中式与分布式的折衷， 以树结构管理资源和发现资源变动，但是更新的资源信息需要一层一层地汇报给上 层管理节点直至根节点，因此很难达到快速响应的要求；多a g e n t 以可移动的a g e n t 方式收集资源变动信息，扩展性高、自由性强，但是这种方式对a g e n t 本身的要求比 较高，对a g e n t 所需要附驻的s t u b 的要求也比较苛刻，尤其对于网格这种大型的、全 球规模的、或者是并不太安全的环境。 r c 模型虽然采用了层次结构，但由于对资源的管理是通过资源的分类来进行的， 因此，对资源的管理只需上报到管理节点，然后由管理节点进行相应的转发，从而 提高了其更新速度。与层次模型相比，该模型具有以下的优点： ( 1 ) 层次化资源管理结构，方便资源信息的基本管理； ( 2 ) 在一个簇内，由多个管理节点根据簇中资源的类型对资源进行集中管理， 1 0 第二章一种基于资源类型的资源发现模型 在进行资源查找时也是根据资源的类型迸行，大大提高了查找的响应速度； ( 3 ) 不在注册节点管理的本地资源中查找，而是根据资源的类型在簇中进行查 找，这大大扩大了资源查找的范围，也减小了查找不成功的概率； ( 4 ) 查找先在簇内的管理节点按照资源类型进行，当查找不成功时才通过功能 节点在簇间查找，这种查找方式大大减少了查找时付出的系统开销。 2 6 本章小结 本章对层次式资源发现和管理模型存在的问题进行了改进，提出了一种基于资 源类型的资源发现和管理模型r c ，并对r c 模型的系统结构、资源发现过程、资源更 新过程和模型的优点进行了详细的描述。 青岛大学硕士学位论文 第三章网格任务调度技术 在网格系统中，任务调度系统是其重要的组成部分，它要根据任务信息采用适 当的策略把不同的任务分配到相应的资源节点上去运行。由于网格系统的异构性和 动态性，以及运行于网格系统之中的应用程序对于资源的不同需求，使得任务调度 变得极其复杂，不好的任务分配策略，将会增加任务的执行时间、降低整个网格系 统的吞吐量。 3 1 网格任务调度技术概述 网格任务调度通常由三个部分组成【。”，分别是资源发现、资源匹配和任务执行。 其中资源发现部分是在所有可用的资源中找出满足任务要求的资源；资源匹配部分 是从发现的资源中找到一个最合适的资源分配给任务；任务执行部分是把任务传送 到资源匹配部分找到的资源上去执行。由于网格系统具有动态、异构、广域的特点 哆】，e 网恪计算系统下，任务调度需要考虑任务特性、机器特性，为不同任务匹配 不同的资源，从而提高系统资源的利用率和任务的执行效率。由于网格计算中任务 调度是一个n p 完全问题，它引起了众多学者的关注，成为目前网格计算研究领域的 一个焦点【9 ，1 0 , n 。 网格中的作业调度分网格层次调度和本地层次调度两个阶段进行。在网格全球 论坛( g l o b a lg r i df o r u m ) 公布的草梨5 】中，低级调度实例实现计算系统的本地调度， 高级调度实例实现网格中的协同调度。通常，高级调度实例又称网格调度器，低级 调度实例又称本地调度器。网格调度器一般不直接控制计算系统中的资源【3 3 1 ，而是 根掘刚格作业的资源分配请求，为作业选择一个或一组计算系统，然后将分解后的 资源分配请求发送给这些计算系统上的本地调度器，由本地调度器完成最终的资源 分配。可见，网格调度器完成网格层次的调度，本地调度器完成本地层次的调度， 网格层次的调度主要完成作业到资源的映射，本地层次的调度主要完成作业的资源 分配与运行。 在加入网格后，计算系统通常保留自己的本地调度器，只是增加本地调度器与 网格调度器的访问接口。因此，建立计算网格中的作业调度系统，主要是设置( 若 干个) 网格调度器，建立网格调度器之间、网格调度器与本地调度器之间的联系， 并在网格调度器上实现网格层次的一些调度方法。计算网格中的作业调度主要指网 格层次的凋度。论文中，如不特别声明，作业调度均指网格层次的调度。 3 2 网格任务调度过程 将网格应用分解为多个子任务( 每个子任务有各自的资源需求) ，然后将予任务 提交到网格调度系统执行调度，是目前网格调度系统采用的通用方法。根据任务间 1 2 第三章计算网格任务调度技术 是否存在通信和数据依赖，可将任务分为两种类型相互之间独立的任务，即元任 务( m e t a t a s k ) ( 3 8 1 ；相互之间存在依赖和时序关系、因果关系的任务，即依赖任 务，它们之间的依赖关系可用d a g 图进行描述。独立任务调度算法是依赖任务调度算 法的基础，由于现在对于d a g 任务映射的研究一般都集中在单管理域的异构集群模 式，并且必须采用各种启发式对映射闯题进行简化2 8 捌，因此，目前在网格环境下 主要考虑的是一组相互独立的任务的映射。图3 1 对网格任务调度的过程进行了描 述。 大型应用程序 i l 划 任务划分 分 l 模 块 l 子任务i i 子任务il 子任务l i 、- 任务调度算法 调 l 度 模 任务分配 块 l 、 网 主机节点主机节点 主机节点 格 ， 资 源 i 一。 _m l j d l o 图3 1 典型的任务调度流程图 其中资源监控与发现服务加s 2 3 ( m o n i t o r i n ga n dd i s c o v e r ys e r v i c e ) 的作 用是收集和发布系统状态信息，该服务主要用于获得主机节点的信息，如主机节点 的处理器类型，处理器速度，可用的处理器数量等。 3 3 网格任务调度模型 在网格任务调度中，资源匹配和任务执行统称为任务调度器，它可以位于网格 系统的某个或几个计算结点上。在某些文献中，也将资源发现模块和任务调度器统 称为网格调度器( g r i ds c h e d u l e r ，g s ) 。根据网格调度器的位置，可以将作业的调 】3 青岛大学硕士学位论文 度模型分为两种：具有中心调度器的调度模型【1 2 , 1 6 , 1 7 , 1 8 ( 中心式网格调度模型) 和具 有分布式调度器的调度模型阱，2 5 1 ( 无中心式网格调度模型) 。 1 、中心式网格调度模型 在中心式网格调度模型中，只有一个网格调度器，这个调度器跟踪所有计算机 资源上的负载信息，独立地在计算资源范围内为任务找到适合的结点集合。 n 个用户 1 个网格调度 器 k 个虚机群 图3 2 中心式网格调度模型 中心式调度模型分为两层，一个网格调度器自成一层，虚机群中的代理( a g e n t ) 组成另一层。代理在该调度模型中扮演重要角色，它负责接收调度器的请求信息和 调度器分配的任务，负责任务的启动执行和结果收集，此外，还负责检测各个计算 结点，收集资源特性信息。网格调度器就是通过代理与所有计算结点进行通信。 中心式调度框架方便了网格调度器在所有计算系统中为任务选择适合的计算系 统。另一方面，网格调度器为任务优化计算系统选择的开销与计算系统总数成正比， 当计算系统总数很大时，网格调度器的工作开销就很大，故应限制一个网格调度器 可整合计算系统的数目。可见，中心式调度框架的可扩展性较差，只适用规模不大 的网格。 2 、分布式网格调度模型 在分布式( 或非中心式) 网格调度模型中，每个网格调度器仅维护本管理域的 负载信息，通过调度器之间的协作，才能为任务选择合适的结点。当网格规模不受 限制地扩大，让一个网格调度器去跟踪所有结点的负载信息是困难的，所以，网格 中使用无中心式调度框架更具一般性。 1 4 第三章计算网格任务调度技术 g s ：网格调度器一：计算系统 作业 实线箭头：提交作业虚线箭头：作业迁移虚线：相邻关系 图3 3 无中心式调度框架 分布式网格调度模型可以采用以下四种方法来实现。 第一种方法是，将工作站网络分为两层，即w a n 和l a n 。每个l a n 实现一个内部调 度器和一个外部调度组件。当一个外部调度组件收至一个计算请求，它基于“闭标拍 卖”选择一个l a n ，并将该计算请求的作业发送给中标的l a n ，再有l a n 内的内部调度 器进行调度。 第二种方法是，设置多个网格调度器和一个中心管理节点。当一个网格节点收 到作业时，中心管理节点根据搜索开销，确定作业迁移到周围那些网格调度器是可 行的，并从中选择最合适的网格调度器。 第三种方法是，将所有节点构成一棵树，根节点的性能最强大，其它任一节点 的性能都不大于其父节点，为了方便节点的搜索，根节点需要掌握网格全局的调度 信息，任意中间节点需要了解其子树包含的计算能力。根据树结构的特点可知，任 一个中间节点的失败，均会导致该结构分解成2 个独立的调度空间。 第四种方法是，构造非完全分布的无中心网格调度模型。所谓非完全分布的无 中心网格调度模型是指一个网格调度器只和若干个网格调度器相邻，而不是和所有 青岛大学硕士学位论文 的网格调度器相邻。在大规模的网格系统中，建立一个完全分布的无中心网格调度 模型是困难的，但在现实的网格系统中，非完全分布的无中心网格调度模型是合理 的。 在无中心式调度框架下，即使一个计算系统或网格调度器失败，计算系统之间 的多条路径使调度框架仍不致于分裂，故无中心式调度框架有很好的健壮性。另一 方面，一个计算系统与哪些计算系统相邻通常是任意的，这使无中心式调度框架有 很好的可扩展性。 3 4 资源性能预测模型 调度中预期任务运行时间是一个关键部分，c “是预期执行时间，c “可以被计 算或者可以从数据库中得到，可以通过两种方法计算c t i i 的值【5 4 ，5 5 】 ( 1 ) 短期预测模型。在调度的第一轮，调度器对于所有任务的执行时间进行初始 化猜测；当任务完成后，调度器使用观