（计算机应用技术专业论文）动态免疫算法在网格任务调度中的应用.pdf

中文摘要 网格计算是近些年来国际上兴起的一项重要技术，目标是要实现网络虚拟环 境下高性能的资源共享与协同工作。任务调度是网格计算中的一项关键技术，目 标是要在满足一定的性能指标和优先关系约束的前提下将可并行执行的任务按 照一定的分配策略分派到网格中的各个资源中运行，以达到总的执行时问最小的 目的，从而提高网格的服务质量。 论文首先对分布式网格调度系统进行了分析研究，针对分布式调度的特点， 对调度系统进行了面向对象的总体架构，明确了调度系统中各实体所承担的角色 以及调度算法的输入和输出等情况。 其次，论文对基本的免疫算法进行了改进，提出了适合于网格任务调度的动 态免疫算法( d i a ) 。根据网格任务调度的特性重新设计了编码机制、亲和度函数、 复制算子、交叉算子以及变异算子。与此同时，对算法中的各参数如种群大小， 记忆细胞的规模进行了重新设置，以便调度器能够根据网格系统各服务节点的计 算能力及网格资源的状态进行动态调度，从而向用户提供最优性能：不仅使总的 完成时间最短，还尽量满足了每个任务的截止时间的要求。 最后，在g r i d s i m 环境下对基于动态免疫算法的网格任务调度模型进行了仿 真模拟，并且与其他比较常见的调度算法如遗传算法、先来先服务算法、最小最 小算法进行了比较分析，结果显示动态免疫算法具有良好的优化能力和自学习、 自适应的能力，从而能够为用户提供比较好的服务质量。 关链删：网格计算任务调度动态免疫算法g r i d s i m a b s t r a c t g r i dc o m p u t i n gi sak e yt e c h n o l o g yw h i c ha i m st oa c h i e v er e s o u r c es h a r i n ga n d c o o p e r a t i v ew o r k t a s ks c h e d u l i n g ，a sa l li m p o r t a n tt e c h n o l o g yf o rg r i dc o m p u t i n g ， i t sg o a li st oa l l o c a t et a s k st og r i dr e s o u r c e sb yc e r t a i ns t r a t e g yu n d e rc e r t a i nc o n d i t i o n a n dm a k es u r et h a tt o m le x e c u t i o nt i m er e a c h e sm i n i m u m f i r s t l y ，w ea n a l y z e dt h ed i s t r i b u t e dg r i ds c h e d u a l i n gs y s t e ma n dc o n s t r u c t e da d i s t r i b u t e ds c h e d u l i n gm o d e la c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h e 酣db y o b j e c t - o r i e n t e da p p r o a c h t h r o u g ht h i ss t e p ，w em a k ec l e a rt h ef e a t u r eo fe a c h c o m p o n e n to ft h es y s t e m ，t h ei n p u ta n do u t p u to ft h es c h e d u l i n ga l g o r i t h m s s e c o n d l y ，w ei m p r o v e dt h eb a s i ci m m u n ea l g o r i t h ma n dp r o p o s e dd y n a m i c i m u n n ea l g o r i t h m ( d l a ) t om a k ei ts u i t a b l et ot a s ks c h e d u l i n gf o rg r i dc o m p u t i n g f o re x a m p l e ，w er e d e s i g n e dt h ec o d i n gm e c h a n i s m , f i t n e s sf u n c t i o n ，r e p r o d u c t i o n o p e r a t o r ，c r o s s o v e ro p e r a t o r , m u t a t i o no p e r a t o ra n dt h ep a r a m e t e r so ft h es c h e d u l i n g s y s t e m b yc a l l i n gd y n a m i ci m m u n ea l g o r i t h m ，s c h e d u l i n gs y s t e mc o u l da l l o c a t e t a s k st or e s o u r s e sf o rp r o s e s s i n gi na no p t i m a lw a yc o n s i d e r i n gt h ec h a r a c t e r i s t i so f t h er e s o u r c e ss u c ha sc o m p u t i n gp o w e ra n dt h el o a d f i n a l l y ，w er e a l i z e dt h es c h e d u l i n gm o d e lw h i c hb a s e do nd i ai ng r i d s i m a l s o ， w ec o m p a r e dd i aw i t ho t h e rc o m m o ns c h e d u l i n ga l g o r i t h m ss u c ha sg e n e t i c a l g o r i t h m , f i r s t c o m e f i r s t - s e r v i c ea l g o r i t h ma n dm i n - m i na l g o r i t h m t h er e s u l t s s h o wt h a td y n a m i ci m m u n ea l g o r i t h mi sag o o do p t i m i z a t i o na l g o r i t h ma n dh a s s e l f - l e a m i n ga b i l i t ya n da d a p t i v ec a p a c i t y ，t h u sa b l et op r o v i d eu s e rw i t hab e t t e r q u a l i t yo fs e r v i c e k e yw o r d s ：g r i d c o m p u t i n g ，t a s ks c h e d u l i n g ，d i a ，g r i d s i m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞苤堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名衅 签字日期文叼 年6 月眄日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：哗 签字日期：& 叼年石月5 日 导师签名：匙7 朗 。 签字日期：跏7 年月f f 日 第一章绪论 1 1 研究背景 第一章绪论 随着科学的发展和科技的进步，计算机作为人们重要的计算和通讯设备在各 个领域得到了广泛地运用。而i n t e m e t 的产生和发展，更是改变了人们传统的思 维方式，工作模式以及生活理念。以e m a i l 为主要应用的第一代i n t e m e t 把分布 在世界各地的计算机通过t c p i p 协议连接起来。第二代i n t e m e t 则通过w e b 信 息浏览及电子商务应用等信息服务，实现了全球网页的连通。第三代i n t e m e t 将 “试图实现互联网上所有资源的全面连通，包括计算资源、存储资源、通信资源、 软件资源、信息资源、知识资源等”这就是网格计算( g i r dc o m p u t i n g ) u j 。网格计 算是伴随着复杂性的科学计算发展起来的，大型的科学与工程往往迫切需要高性 能的计算。比如全球的天气预报，大气污染处理，新型材料的研究，图像处理等 是2 l 世纪具有重大挑战意思的主要科学工程计算问题，直接促使高性能计算研 究和飞速发展。所以，网格计算的目标是要实现网络虚拟环境下高性能的资源 共享于协同工作，消除信息孤岛和资源孤岛，而网格就是能够对高端计算能力提 供独立、一致、普遍且廉价访问的硬件和软件体系结构。网格系统由大量异构资 源组成，具有复杂、动态、自治、可扩展等特点。用户通过向网格系统提交计算 任务来共享网格资源，网格调度程序再按照某种策略把这些任务分配给合适的资 源。高效的调度策略或算法可以充分利用网格系统的处理能力，从而提高应用程 序的性能。在网格环境里如何有效地进行任务调度是影响网格计算是否成功的最 重要因素之一。 一般而言网格计算系统具有以下几个特征： ( 1 ) 扩展性：网格计算系统初期的规模较小，随着超级计算机系统的不断加入， 系统的规模随之扩大。 ( 2 ) 异构性：构成网格计算系统的超级计算机有多种类型，不同类型的超级计 算机在体系结构、操作系统及应用软件等多个层次上具有不同的结构。 ( 3 ) 结构的不可预测性：与一般的局域网系统和单机结构不同，网格计算系统 由于其地域分布和系统的复杂使其整体结构经常发生变化。 ( 4 ) 动态性：在传统的高性能计算系统中，计算资源是独占的，因此系统的行 为是可以预测的，而在网格计算系统中，由于资源的共享造成系统行为和 第一章绪论 系统性能经常变化。 ( 5 ) 多级管理域：由于构成网格计算系统的超级计算机资源通常属于不同的机 构或组织并且使用不同的安全机制，因此需要各个机构或组织共同参与解 决多级管理域的问题。 目前国内外在网格计算方面的研究十分活跃，研究范围跨度很大。目前呈现 这样的趋势，一是网格计算标准化的呼声越来越高，目的就是为了规范和统一现 在大量的网格计算研究，g l o b u s 在一定程度上成为事实上的标准【2 】。二是专用网 格的研究与开发成为一个重要的方向，因为网格是面向具体问题的应用的，而专 用网格在这一方面具有独特的优势，可以为通用网格技术提出最直接最具体的需 求。三是开放的面向w e b s e r v i c e 的框架结构和与商业界应用的结合是网格技术 研究的一个重要趋势，原来的网格计算主要集中在科学计算等学术领域，而e t 前 正在走向实用并与市场结合，直接服务于生产和各种商业活动。 1 2 主要研究工作 网格任务调度是网格计算中一个至关重要的问题，其算法将直接影响到网格 环境中任务执行的效率以至成败。用户向分布式调度控制器来提交计算任务，调 度器根据某种调度策略把这些任务分配给网格中合适的资源去执行。高效的调度 算法可以充分利用网格系统的处理能力，从而提高应用程序的性能。 本论文的主要工作如下： ( 1 ) 对分布式网格调度模型进行了面向对象的架构，对网格调度环境中的各个实 体进行了建模，从而为动态免疫算法的应用搭建了一个平台。 佗) 本文对基本的免疫算法进行了改进，重新设计了一种用于网格任务调度的免 疫算法的改进算法一动态免疫算法d i a ( d y n a m i c i m m u n ea l g o r i t h m ) ，重 新设计了适用于网格任务调度的各个算子，并且吸取了遗传算法的优点，在 原有免疫算法的基础上加入了遗传算子，设计并实现了根据网格系统各服务 节点的计算能力、负载及网络状态进行动态调度，从而向用户提供较优性能。 ( 3 ) 在g r i d s i m 环境下实现了基于d i a 的分布式代理的网格模型，很好地解决了 分布式任务调度的问题。 ( 4 ) 将动态免疫算法与遗传算法、m i n - m i n 算法、f c f s 等其他调度算法进行了 比较分析。 第一章绪论 1 3 论文结构 本文正文共分六章。 第一章是论文的绪论，介绍了论文的总体结构安排，例如工作的研究背景、 主要的研究内容及工作。 第二章探讨了网格计算以及免疫算法的产生、发展以及研究现状。 第三章对分布式网格调度系统进行了分析和架构，包括各个模块的设计和分 析。 第四章详细设计了动态免疫算法在网格任务调度中的应用。 第五章的内容是对基于动态免疫算法的分布式网格任务调度的实验仿真。首 先介绍了仿真环境g r i d s i m ，利用该仿真包设计仿真了基于动态免疫算法的分布 式网格调度模型并对实验结果进行了分析与评价。 第六章是对论文工作的总结，并指出亟待解决的一些问题以及对未来工作的 展望。 论文的最后是参考文献、科研情况的说明以及致谢。 第二章网格计算与免疫算法的研究现状 第二章网格计算与免疫算法的研究现状 2 1 网格的产生与发展 随着计算机的不断发展，它已经成为复杂科学计算领域的主宰。但以超级计 算机为中心的计算模式存在明显的不足，而且目前正在经受挑战。超级计算机虽 然是一台处理能力强大的“巨无霸”，但它造价极高，通常只有一些国家级的部门， 如航天；气象等部门才有能力配置这样的设备。而随着人们日常工作遇到的商业 计算越来越复杂，人们越来越需要数据处理能力更强大的计算机，而超级计算机 的价格显然阻止了它进入普通人的工作领域。于是，人们开始寻找一种造价低廉 而数据处理能力超强的计算模式，最终科学家们找到了答案g r i d c o m p u t i n g ( 网格计算) 。 网格计算是伴随着互联网而迅速发展起来的，专门针对复杂科学计算的新型 计算模式。这种计算模式是利用互联网把分散在不同地理位置的电脑组织成一个 “虚拟的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计 算是由成千上万个“节点”组成的“一张网格”，所以这种计算方式叫网格计算。这 样组织起来的“虚拟的超级计算机”有两个优势，一个是数据处理能力超强；另一 个是能充分利用网上的闲置处理能力。 实际上，网格计算是分布式计算( d i s t r i b u t e dc o m p u t i n g ) 的一种【3 】，如果说 某项工作是分布式的，那么，参与这项工作的一定不只是一台计算机，而是一个 计算机网络，显然这种“蚂蚁搬山”的方式将具有很强的数据处理能力。今年年中， n t t d a t a 计划与i n t e l 和s g i 联合进行一项为期三个月的网格计算试验，届时将 有包括家庭、企业和学术机构的1 0 0 万台计算机相联，其总处理能力将比现有的 最快的超级计算机还要快五倍。 网格技术提供了共享和协调使用各种不同资源的机制，因此使得我们能够从 地理上、组织上分布的组件中创建出一个虚拟计算系统，这个虚拟计算系统充分 集成了各种资源以获得理想的服务质量。这些技术包括：当计算跨越多个机构时， 支持管理证书和策略的安全解决方案；资源管理协议和服务，支持安全的远程访 问计算和数据资源以及协同分配多种资源；信息查询协议和服务，提供关于资源、 组织和服务的配置信息和状态信息；还有数据管理服务，在存储系统和应用之间 定位和传输数据集。 第二章网格计算与免疫算法的研究现状 当在跨越异构和动态的资源集上根据服务质量提供服务时，虚拟组织应用程 序开发者面临着一些共同需求：服务质量是否根据共同的安全语义、分布式工作 流和资源管理、协同故障恢复、问题确定服务来评估或者根据其他机制来度量。 资源共享通常是有条件的，共享关系是随着时问的变化而动态变化的，通常不是 简单的客户服务器方式，而是p 2 p 方式。同一资源可能在不同的上下文中以不 同的方式被使用，需要考虑资源使用的优先级。除了安全和策略这类问题之外， 网格用户通常更关心在虚拟系统中获得各种服务质量。从许多方面来看，这种需 求可以简单的认为是需要一种基础设施，这种基础设施方便了跨组织边界资源的 控制共享，它就是网格【4 】。信息技术及其基础设施的根本目的是让人们处理日常 任务变得更加高效或有效。这些任务的完成在某种程度上依赖于和其他人的协 作。网格不仅仅是一种应运而生的技术，更是我们的基础设施必须发展的方向。 网格的发展经历了以下四个发展阶段： 第一个阶段是萌芽期：2 0 世纪9 0 年代初期，以千兆网的实验床以及一些元 计算实验。 第二个阶段是实验期：2 0 世纪9 0 年代中晚期，比如i - w a y 项目，学术性研 究项目g l o b u s ，l e g i o n 以及一些应用。 第三个阶段是2 1 世纪初，主要是开放式的网格服务体系结构，如w e b 服务等。 第四个阶段是2 0 0 5 年至今，主要研究方向是受管理的共享虚拟系统。 2 2 网格的应用前景 在科学计算领域，网格计算可以在以下几个方面得到广泛应用【5 】： ( 1 ) 分布式超级计算。网格计算可以把分布式的超级计算机集中起来，协同解决 复杂的大规模的问题。使大量闲置的计算机资源得到有效的组织，提高了资 源的利用效率，节省了大量的重复投资，使用户的需求能够得到及时满足。 ( 2 ) 高吞吐率计算。网格技术能够十分有效地提高计算的吞吐率，它利用c p u 的周期窃取技术，将大量空闲的计算机的计算资源集中起来，提供给对时间 不太敏感的问题，作为计算资源的重要来源。 ( 3 ) 数据密集型计算。数据密集型的问题的求解往往同时产生很大的通讯和计算 需求，需要网格能力才可以解决。网格可以药物分子设计、计算力学、计算 材料、电子学、生物学、核物理反应、航空航天等众多的领域得到广泛的需 + 求 ( 4 ) 网格的出现更加突破了人与人之间地理界线的限制，使得科技工作者之间的 交流更加的方便，从某种程度上可以说实现人与人之间的智慧共享。 第二章网格计算与免疫算法的研究现状 ( 5 ) 更广泛的资源贸易。随着大型机的性能的提高和微机的更加普及，及其资源 的闲置的问题也越来越突出，网格技术能够有效地组织这些闲置的资源，使 得有大量的计算需求的用户能够获得这些资源，资源的提供者的应用也不会 受到太大的干扰。需要计算能力的人可以不必购买大的计算机，只要根据自 己的任务的需求，向网格购买计算能力就可以满足计算需求。 早期的网格体系结构是五层沙漏结构【6 】。在五层沙漏结构中，最重要的思想 是以“协议”为中心，它侧重于外部的行为而不是内部的特征，通过协议可以实现 一种机制，使得虚拟组织的拥护与资源之间可以进行资源使用的协商，建立共享 关系，并且可以进一步管理和开发新的共享关系。这一标准化的开放结构对网格 的扩展性、互操作性、一致性以及代码的共享都有好处。 在2 0 0 2 年的2 月，i b m 与g l o b u s 共同发表了o g s a t7 j ( 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 ) ，勾勒了g l o b u st o o l k i t 3 0 的蓝图。o g s a 主要是将w e bs e r v i c e s 、 数据库存取、j 2 e e 等技术规范纳入网格计算。初步的规范已经公布在网络上供 大家评估建议。- 五层沙漏模型中，强调的是被共享的物理资源( 或者是这些资源所支持的服 务) 在o g s a 中，服务所指的概念更广，包括各种计算资源、存储资源、网络、 程序、数据库等等，一切都是服务。五层模型实现的是对资源的共享，而在o g s a 中，实现的对服务的共享。在o g s a 中一切都看作是网格服务，网格是可扩展 的网格服务的集合，即网格= 网格服务) 。 以网格服务为中心的模型的好处有以下几点： 网格中所有组建都是虚拟的，通过提供一组相对统一的核心接口，所有的网 格服务都基于这些接口的实现，就可以很容易地构造出具有层次结构的、更高级 别的服务，这些服务可以跨越不同的抽象层次，以一种统一的方式来看待。 虚拟化也使得将多个逻辑资源实例映射到相同的物理资源上成为可能，在对服务 进行组合时不必考虑具体的实现，可以以底层资源组成为基础，在虚拟组织中进 行资源管理。通过网格服务的虚拟化，可以将通过的服务语义和行为，无缝地映 射到本地平台的基础设施之上【8 】。 “蓝色巨人”i b m 正在构筑一项名为“g r i dc o m p u t i n g ”的计划，旨在通过因特 网，向每一台个人电脑提供超级的处理能力。i b m 公司副总裁、也是这项计划 的总设计师欧文吖白杰说，“g r i dc o m p u t i n g ”是一种整合电脑资源的新手段，它通 过因特网把分散在各地的个人电脑连接起来，不仅可使每台个人电脑通过充分利 用相互间闲置的电脑能源，来提升各自的电脑处理能力，还可使成千上万的用户 在大范围的网络上共享电脑处理功能、文件以及应用软件。正如网络技术总是从 科学开发领域转向企业商务领域一样，我们也希望看到g r i dc o m p u t i n g 能取得这 第二章网格计算与免疫算法的研究现状 样的进展。 另一个业界巨人s u n 也推出新软件促进网络计算的发展。2 0 0 1 年1 1 月， s u n 推出了s u ng r i de n g i n e 企业版软件的、，继续提升它的网络技术计算水平。 该软件自推出以来，s u ng r i de n g i n e 企业版软件的用户已经增长了2 0 倍。今 天，全球有1 1 8 0 0 0 多颗c p u 都是采用s u ng r i de n g i n e 软件管理的。 一 除此之外，一批围绕网格计算的软件公司也逐渐壮大和为人所知并成为受到 关注的新商机，如：e n t r o p i a 、a v a k i 、n o e m i x 、d a t as y n a p s e 等等。有业界专家 预测，网格计算将成为未来网络市场发展的热点。据( ( f o r b e s a s a p ) ) 预测，网 格技术将在本年度达到高峰，并带来因特网的新生。如果网格技术能促使市场按 预期的1 7 年增长率持续成长的话，那么在2 0 2 0 年将会形成一个年产值2 0 万亿 美元的大产业。 2 3 免疫算法的基本原理和研究现状 智能优化算法发展至今，已取得长足进展，新的优化技术不断涌现，应用领 域也在不断拓宽。免疫学的机理被f a r m e r 于首次引入到人工智能领域。 免疫算法是继神经网络算法，遗传算法之后的又一类通过人工方式构造的智 能优化搜索算法。免疫算法是受生物免疫系统中抗体基因快速高效的克隆进化 以快速消除外来侵害物( 抗原) 的启发，虽然起步比较晚，但它强大的数据处理能 力在计算、网络、控制、学习等方面都有不少的应用实例，具有很大的应用潜力。 目前，基于人工免疫系统的基本原理已出现了处理最优化问题的大量算法。 这些算法可分为两大类：免疫特征与进化算法结合的免疫进化算法及基于免疫学 原理的算法 9 1 。 随着人工免疫系统不断被深入研究，基于免疫机理的算法不断出现且纷繁复 杂，这些算法引用的免疫机理大致相同，不同之处在于免疫特征的应用及算子模 块的设计，那么如何设计一种既包括已有免疫优化算法引用的免疫机理，又有自 身独特结构、独特设计、应用有效及便于理论分析的般性免疫算法便是人工免 疫系统中探讨免疫算法的研究者关注的热点。 从已有基于免疫机理的最优化算法设计分析看，这些算法利用了体液免疫理 论中浓度机制j 免疫概念或克隆选择原理的部分特征，因此若提取这些算法的有 益免疫特征并引入体液免疫中相关的其它免疫机制，设计独特的算子模块并有机 组合即可获得处理最优化问题的一般性免疫算法。 免疫算法将待求解问题抽象成免疫系统的抗原，将问题的可行解抽象为抗 体，通过抗体和抗原的结合力来反映可行解与最优解的逼近程度，抗体之间通过 第二章网格计算与免疫算法的研究现状 相互抑制来维持抗体的多样性，从而提高算法的搜索能力。下面给出免疫算法中 常用的一些名词解释1 0 1 。 1 免疫 在生物系统中免疫( i m m u n i t y ) 是生物体对“自己”和“异己( 非己) ”的识别以及 应答过程中所产生的生物学效应的总和。 在免疫算法中，免疫表示免疫算法产生的抗体( 可行解) 对抗原( 问题约束) 的识别能力。 2 抗原 在生物系统中，抗原表示非己的部分，即外来侵害物。 在免疫算法中，抗原表示待求问题，即把所要求解问题的目标函数抽象为抗 原。 3 抗体 在生物系统中，抗体表示生物体内产生的针对有害抗原的特异性物质，可以 和抗原匹配以消除抗原。 在免疫算法中，抗体表示待求问题的可行解。 4 记忆细胞 在生物系统中，记忆细胞表示可记住对某种抗原的特异性反应，并在机体以 后再次遇上类似抗原时，迅速作出响应。 在免疫算法中，记忆细胞表示待求问题较好的解。 5 亲合力 在生物系统中，抗原的表位与抗体的受体之问的结合力。 在免疫算法中，亲和力表示抗体与抗原的识别程度。 6 匹配 抗原与抗体之间的结合越紧密，则匹配越好 第三章分布式网格调度系统架构 第三章分布式网格调度系统架构 3 1 网格任务调度的基本模式 网格任务调度系统的一般主要分为以下四部分【1 l 】： ( 1 ) 组织层：包括计算机，网络，科学设备，及其管理系统。 ( 2 ) 核心中间件：包括安全和访问管理，远程作业提交，存储，资源信息等服务，使 得安全一致透明的访问远程资源。 ( 3 ) 用户中间件：提供高级工具，如网格资源b r o k e r ，应用开发，自适应运行时环境。 ( 4 ) 应用程序：可以是基于网格开发的程序，也可以使用用户中间件将传统的程序转 化成网格的应用程序。 网格任务调度的基本模式如图3 1 所示： 图3 - 1 网格调度系统的基本模式 用户主要和用户资源代理( 分布式调度器) b r o k e r 交互，从而隐藏了复杂的 网格计算结构。b r o k e r 的功能是发现用户可以访问的资源；把作业映射到资源上； 准备处理的程序和数据；开始执行作业以及收集结果。b r o k e r 同时负责监测和跟 踪作业完成的进度，自适应于网格运行时环境的变化或资源缺失。 调度器( b r o k e r ) 通过调用动态免疫算法而获得任务和资源的映射关系，即把 哪些任务分配给哪些资源。调度器按照调度序列所代表任务一资源映射关系把任 第三章分布式网格调度系统架构 务发送到网格中的各个资源中去执行，一次调度完成，然后调度器继续接收用户 发送过来的任务，直到所有任务都调度完毕。下面将对网格调度系统进行详细的 分析和设计。 3 2 网格调度系统总体设计 3 2 1 网格调度系统的功能分析 网格的使用者和调度系统进行交互。用户向网格调度系统提交作业，调度系 统负责任务调度并接收返回的结果，如图3 2 所示： 图3 - 2 网格系统用例图 网格的使用者包括用户以及应用程序等。他们通过用户代理使用网格中的资 源来完成自己的各项工作。网格的每个用户有各自不同的需求，有的用户利用网 格系统来完成复杂的科学计算，有的用户则利用网格完成数据的存取工作。而在 网格任务调度中的研究中，网格中的资源是主要是计算资源，负责计算和处理用 户作业。对每个用户来说，用户代理( 调度器) 是网格中间件，它的功能就像操作 系统，屏蔽了网格的复杂结构，所以用户感觉就像使用一台虚拟的超级计算机， 只需告诉用户代理做什么，而不必了解具体怎么做。 网格调度系统的核心就是设计用户代理，即调度器。所有的分派调度工作全 是由用户代理完成的。下面就网格调度系统各部分的组成和交互来整体架构一个 网格任务调度系统。 q 人嘲 第三章分布式网格调度系统架构 3 2 2 网格调度系统的构成 “调用 f 一一一一一一一一一一一一一一一一一一专) 二二二二丑i l - - - - - j i 图3 3 网格调度系统类图 如图3 3 所示，网格调度系统主要由用户( u s e r ) 、调度器( b r o k e r ) 、网格信息 服务实体( i n f o s e r v i c e ) 、调度算法( d i a ) 、网格资源组成( r e s o u r c e ) ，每个用户对 应一个分布式调度器，用户负责创建任务，并将任务发送给调度器，调度器通过 调用调度算法来获得任务调度的较优策略并将任务按照这个策略发送给网格中 的资源去执行，执行完毕后将结果返回给调度器，调度器把结果再返回给用户。 3 3 网格调度系统模块化设计 3 3 1 用户模块的分析与设计 用户是调度系统的使用者，也是任务调度的发起者。可以设计一个通用类 ( u s e r ) 来表示用户，设计一个任务类( t a s k ) 表示用户发送给调度器的任务。具体设 计如下： 每一个u s e r 实体实例对应一个网格用户，有以下性质： 用户i d ； 用户代理； 第三章分布式网格调度系统架构 待发送的任务； 返回的任务： 对用户建模如图3 4 所示 u s e r l d ：i n t b r o k e r ：b r o k e r t a s i d o s e n d ：t a s k r e c e i v e d t a s k ：t a s k + u s e r 0 - e x p d e v o ：d o u b l e + c r e a t e t a s k 0 ：t a s k + s e n d o ：v o i d + r e c e i v e 0 ：v o i d + b o d y o ：v o i d 图3 _ 4 用户类图 其中各部分字段解释如下： 表3 1 用户属性方法表 u s e r i d 用户i d b r o k e r 用户代理 t a s k t o s e n d返回的结果 s e n d o 发送任务 r e c e i v e o 接收任务 e r e a t e t a s k o 创建任务 b o d y ( )多线程机制，实现实体问的通信 在创建一个用户对象时，系统会自动调用它的构造函数。我们重载了它的构 造函数。在初始化用户对象之前首先创建一个它的用户代理对象。在创建了用户 对象后，用户对象将运行在他的多线程通信函数b o d y o 中，在b o d y o q b 用户将创 建所要执行的任务，然后把任务发送给他的用户代理以及最后接收用户代理返回 的执行结果。下面是创建一个任务的过程。 每一个t a s k 实体实例对应一个任务，有以下性质： 任务的归属者； 任务的长度； 任务的开始时问； 1 2 第三章分布式网格调度系统架构 任务的结束时间； 任务的截止时间 对任务的建模如图3 5 所示： t a s k t a s k l d ：i n t s t a r r r i m e ：d o u b l e e n d t i m e ：d o u b l e d e a d l i n e ：d o u b l e l e n g t h ：d o u b l e u s e r l d ：i n t + s e t t a s k l d o ：v o i d + g e 仃a s k l d o ：i n t + s e t l e n g t h o ：v o i d + g e t l e n g t h o ：i n t + s e t d e a d l i n e o ：v o i d + g e t d e a d i i n e o ：d o u b l e 其中个字段解释如下： 图3 5 任务类图 表3 2 任务属性方法表 s t a r t t i m e 记录该任务处理的开始时间 e l l d t i m e 记录任务处理完毕的时间 l e n g t h 任务长度 t a s k i d 任务号 d e a d l i n e 任务的截止时间 s e t 0s e t 方法，设置属性值 g e t 0g e t 方法，获得属性值 3 3 2 网格资源模块的分析与设计 网格中的每个资源代表了网格中的一个节点，网格资源负责提供给用户一个 可靠的，可透明访问的虚拟计算机环境，使用户感觉就像使用一台超级计算机。 资源的属性应该包括资源的即时处理速率，资源的结构属性，资源的负载等。本 文设计了资源类( r e s o u r c e ) 来表示网格中的资源。具体设计如图3 - 6 所示： 第三章分布式网格调度系统架构 r e s o u r c e 1 d ：i n t c a l e n d a r ：r e s o u r c e c a l e n d a r 0 s ：s t r i n g l o a d ：d o u b l e - s p e e d ：d o u b l e - a l l o c p o l i c y ：s t r i n g + g e l t o t a l m i p s 0 ：d o u b l e + g e t a v a i l a b l e m i p s 0 ：i n t + g e t l d 0 ：i n t + g e t l o a d 0 ：d o u b l e + g e t t i m e z o n e 0 ：s t r i n g 其中各字段解释如下： 图3 - 6 资源类图 表3 3 资源属性表 i d 资源号 c a l e n d a r 日志 o s操作系统 l o a d 资源负载 s p e e d 资源处理速度 a l l o c p o l i c y 资源内部调度策略 g e t t o t a l m i p s o 资源空载每秒所能处理的m i g e t l o a d o 得到资源负载 g e t t i m e z o n e o 获得资源所在的地理位置( 时区) g e t l d ( ) 获得资源号 g e t a v a i l a b l e m i p s ( ) 获得可用m i 3 3 3 调度算法模块的分析与设计 算法模块包括算法的接收模块，处理模块和输出模块三部分组成，接收模块 负责接收控器模块( b r o k e r ) 的输入，比如说当前网格节点数，每个资源负载以及 每个资源的即时处理速率等参数。处理模块负责根据这些参数按照预先设定的算 法流程计算出一个任务的调度的次序序列，然后通过输出模块输出，把结果返回 第三章分布式网格调度系统架构 给控制模块。具体流程如图3 7 所示： 图3 - 7 算法模块流程 根据上述分析，可以看到算法模块与任务调度控制模块之间是相互影响，相 互制约的。算法模块的初始化需要调度控制模块提供一系列的系统参数。其中算 法编码的长度也就是控制模块提供的网格资源的数目，每次批调度的编码长度是 动态变化的。此外，调度控制模块还需要向算法模块提供网格各节点的即时处理 速率以及负载等情况，以便算法模块进行编码的有效性的检查。在系统控制模块 向算法模块提供了必要的系统参数后，由于免疫算法具有自适应和自学习性，它 将根据这些即时信息进行分析处理，最终找到一个最优或者接近最优的调度序 列，并把调度序列返回给任务调度控制模块，由控制模块进行任务的映射与调度。 在算法模块的建模中，本文将为免疫算法中的抗体设计一个抗体个体类 ( i n d i v i d u a l ) ，并且把免疫算法也抽象成为一个算法类( d i a ) ，其中属性包括了两 部分信息，一部分是系统信息，由控制模块传入；另一部分是算法内部信息，包 括抗体种群，各种操作和算子等。具体设计如图3 - 8 所示： 图3 8 算法类图 第三章分布式网格调度系统架构 其中各部分字段解释如下 表3 - 4 d 1 a 属性方法图 n种群大小 p o p 】 当前种群 r e s i n f o 网格资源信息 b e s t 种群最优个体 i n i t p o p o 初始化抗体种群 e o m p u t e f i m e s s o 计算抗体亲和度 c o m p u t e d e n s i t y o 计算抗体浓度 s e l e c t ( ) 复制算子 c r o s s o v c r ( ) 交叉算子 m u t a t i o n ( ) 变异算子 g e n e r a t i o n ( ) 产生下一代种群 g e t b e s t ( ) 获得最优解 3 3 4 调度控制模块的分析与设计 调度模块是整个算法的控制模块，它用来负责接收任务，调用算法模块，映 射任务，分配任务，接受数据结果并把结果返回给用户。调度模块结构虽然非常 简单，但实现的功能却非常复杂，是整个调度系统的控制核心。它实现了调度的 业务逻辑，把网格系统中的各个实体通过信息的发送与接收联系了起来。调度器 的具体结构如图3 - 9 所示： b r o k e r - t a s k s t o s e n d - r e c e i v e d t a s k s - r e s i n f o 】 + b r o k e r 0 + 1 ) o d y o - s e n d t a s k o - r e c e i v e t a s k o - s e r c h o 图3 - 9 调度器类图 第三章分布式网格调度系统架构 其中属性部分主要是作业缓冲池，包括作业发送缓冲池和接收缓冲池。此外， 调度器还要保存有关网格可用资源的信息，所以我们给它设计了一个用于保存资 源信息的数组r e s i n f o 。调度模块的流程控制主要在b o d y o q 丁完成。具体的调度 时序可以用一时序图来表示，如图3 1 0 所示： 甲i u s e r i 甲b r o k e r i i早grid i n f os e r v i c e 回i 甲 图3 1 0 调度时序 用户( u s e r ) 创建需要网格系统执行的任务( t a s k ) ，并把任务发送给自己的用 户代理( b r o k e r ) ，由用户代理负责分派调度。 用户代理通过与网格信息服务实体交互来获得网格中的资源信息，如可用 资源数目以及每个资源的特性等等。 用户代理调用算法模块，把网格资源的信息传入算法的输入模块，经过算 法的处理模块进行处理分析，然后由算法输出模块产生输出( 调度策略) 并把结果返回给用户代理。 用户代理按照调度策略进行任务的分配调度。 接收处理完毕后的结果并返还给用户。 、，、，、， )、， l 2 3 4 5 - ， ( ( ( ( 第四章动态免疫算法在网格任务调度中的应用 第四章动态免疫算法在网格任务调度中的应用 4 1 网格任务调度的基本问题 在分布系统中，一个程序可以看作是一个任务集，这些任务可以串行或并行 地执行。任务之间一般是有优先次序约束的。调度问题的目标是要在满足一定的 性能指标和优先约束关系的前提下，将可并行执行的任务按适当分配策略确定一 种分派和执行顺序，合理分配到各处理机上有序地执行，己达到减少总的执行时 间的目的。 性能和效率是评价调度系统的两个基本特征。在实际中应以任务分派( 调度) 的质量和调度算法( 调度程序本身) 的效率为基础来评价调度系统。调度质量以 产生的优化调度的性能为基础来衡量；调度算法的效率以时间复杂性为基础来衡 量。例如，如果以优化一个程序的完成时间来衡量，显然完成时问越短越好。如 果两个调度算法产生相同的调度质量，则调度算法越简单越好。 任务调度的相关定义如下【1 2 】： 在有m 个处理单元和任务图g = ( t ，e ) 之上的调度是一个函数，厂将每个 任务以某个特定的开始时间映射到某个处理单元。 从形式上，一个调度可描述为： f ：t 一 1 ，2 ，坍) 【o ，】 公式( 4 - 1 ) 如果存在，丁，i ( v ) = ( f ，t ) ，则表示任务1 ，被调度到处理单元只上，且从时 间t 开始执行。 函数厂可以表示成如下定义的g a n t t 图。 g a n t t 图用于直观地表示所有任务的开始时间和完成时间。在一个g a n t t 图 中，有一个分布系统的处理单元表，对于表中每个处理单元都有一个任务分配表， 即将分配到这个处理单元的所有任务按执行时间排列成表，其中包括开始时间和 结束时间，分别用s t ( t j ，p ) 和f t ( t j ，只) 表示。 实际上，g a n t t 图是一个四元表： 、 g a n t t ( p i ，t y ，s r ( t - f ，鼻) ，刀( o ，只) ) 公式( 4 - 2 ) 其中， 只( i = l ，2 ，m ) 为处理单元； f ，( j = l ，2 ，珂) 为分配到只上的任务； 第四章动态免疫算法在网格任务调度中的应用 s t ( t j ，只) 为t j 在p 上的开始时间； r r ( t ，p ) 为t j 在只上的结束时间； 一个任务调度系统的最大调度长度观( s c h e d u l el e n g t h ) 定义为所有处理 机只中的 m a x f r ( t j ，只) 公式( 4 3 ) 调度的目标就是要将任务适当分配到处理机并协调任务之间的执行顺序，使 得并行执行时满足并行任务之间的优先约束关系，而且乩最小。 任务调度问题属于n p 完