基于改进遗传算法的网格任务调度分析
尽管超级计算机的能力在不断地增长，仍然有许多局限性。
一方面，超级计算机造价极高，通常只有一些国家级的部门，才有能力配置这样的设备;另一方面，某些应用对计算的要求非常高，即使是现在最大的超级计算机也无法提供它们所需的资源。
4]就成为当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题。
网格技术其核心思想是"整个因特网就是一台计算机"。
网格的提出将从根本上改变人们对计算的看法，因为网格提供的是与以往根本不同的计算方式。
网格的意义就如同互联网改变了人们传统的通信方式和通信手段一样，它将改变人们传统的计算方式和计算手段，网格技术将为人们提供更强大、更方便、更高级的问题求解手段。
在网格计算中，任务管理、任务调度和资源管理是网格必须具备的三个基本功能。
用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照某种策略把这些任务分配给合适的资源。
任务调度是网格计算中一个至关重要的问题，其算法将直接影响到网格环境中任务执行的效率以至成败。
但由于网格的新特性，使得必须研究新的算法来解决一些新出现的问题，如调度问题的NP安全性，资源的异构性以及资源分配决策的并行性和分布性等。
这对传统的调度算法提出了新的挑战。
传统的并行计算调度算法主要是调度一个应用程序的子任务到并行的计算机，主要目的是减少计算时间;而对于网格环境，调度算法关心的主要问题是调度来自不同用户的应用流到可用的计算资源上，从而最大限度地让网格系统得到最大的使用，它追求的是调度的高吞吐率。
具体的目标包括:最优跨度(Optimal Makespan)、服务质量Qos(Quality ofservice)，负载均衡(Load Balancing)、经济原则(Economic Principles)等。
然而由于网格计算任务调度面临的是一个NP完全问题，至今没有找到有效算法，而指数型算法对解决规模较大的问题又十分困难，以求近似最优解为目的的启发性算法自然就受到了极大的重视。
而遗传算法因其自组织、自适应、自学习性和并行性等特点而非常适宜解决网格任务调度问题。
虽然研究人员在网格任务调度领域进行了许多的研究，也取得了一些成果，但是要解决网格环境的任务调度问题还需要进行大量的研究工作。
网格作为一种建立在互联网上的新一代基础设施，目前网格计算处于快速发展期，很多正在开发的相关网格调度项目。
下面是一些具有代表性的系统。
中国国家网格( China National Grid)日开通的，是一个计算资源共享、数据共享以及协同工作的环境，已经开发了资源环境、科学研究、服务业和制造业四个领域的应用网格，由国家863 计划重大专项支持，是聚合了高性能计算和事务处理能力的新一代信息基础设施的试验床。
通过资源共享、协同工作和服务机– 1 –万方数据第一章 绪论制、有效支持科学研究，资源环境、先进制造和信息服务等应用。
中国国家网格环境构成与主要设备包括北京中科院主结点(联想深腾6800)、上海超算中心主结点(曙光4000A)、北京清华结点(清华探索3 号集群计算机)、北京应用物理结点(银河计算机)、西安结点(曙光3000 )、合肥结点(HP Integrity Superdome )、长沙结点(银河计算机)以及香港结点(集群计算机)。
chinaGrid):教育部"211工程"公共服务体系建设的重大专项。
由国内12所大学首批参与，配合网络计算机的使用，把在CERNET上自治的分布异构的海量信息资源集成起来，实现CERNET环境下资源的有效共享。
消除信息孤岛，提供有效的服务，形成高水平低成本的计算机服务平台。
Globus是美国多家研究机构的合作项目，Globus的核心是一个工具集，包括一组执行基本服务的组件。
Globus提供了调度组件作为其工具集的一部分，但没有提供具体的调度策略，依赖高层调度器执行任务调度，很多调度器中间件如Nimrod-G、AppleS和Condor都是基于Globus服务开发的。
Globus是一个典型的分层网格体系，高层的服务可以调用低层的核心服务来开发。
它的重点在于分级式的集合网格组件和服务，鼓励了使用低级的服务来开发高级的服务。
Condor是美国威斯康星大学开发的一个高吞吐量的计算环境，可管理分属于不同机构的大量PC机、工作站以及集群，以利用闲散CPU周期著名。
Condor可以被认为是具有平面组织的计算网格。
它使用了具有混合命名空间的可扩展体系。
它不支持QoS，信息存储在不使用X.500/LDAP(Lightweight Directory Access Protocol)技术的网络目录中。
资源发现是通过集中式的发布查询请求来实现的，因而属于集中式的调度程序。
Netsolve是一种基于客户-代理-服务器结构的服务网格，由代理执行信息存储与维护、资源发现和资源调度，客户端支持C、FORTRAN、METLAB和网页应用程序。
2003年，Spooner在沃里克大学首次提出了TITAN，认为基于该体系结构可以通过遗传算法得到最优调度。
国外重要网格应用研究项目还有:美国NASA网格IPG(Information Power Grid)，欧洲数据网格DATAGrid，全球信息网格GIG，美国NSF网格TeraGrid，等等。
可见，网格计算的应用已经引起了世界各国的高度重视。
这个称之为EGEE(Enabling Grids for E-science)的计算机网格，将数万台普通电脑组成一个超大型超级计算机，他们正利用EGEE寻找能够抑制流感病毒活性的新型分子，使用EGEE，已经发现了大约200个可能成为对抗禽流感的药物分子。
在匈牙利布达佩斯举行的EGEE2007会议上，EGEE应用于对抗禽流感的成功例子。
《美国化学会志》(JACS)上发表了在英国国家网格计– 2 –万方数据第一章 绪论算(computing grid)平台和美国TeraGrid系统的帮助下，伦敦大学学院(UCL)科学家有望揭示地球早期生命起源之谜的报道。
计算网格系统模拟形成在热液喷口附近的高温和高压环境，这将显示DNA分子植入分层矿石后所表现的稳定性，以及接触矿石和处于热降解作用下所形成的保护状态。
§1.2 任务调度算法的研究现状作为计算网格关键技术之一的任务调度算法，历来都受到国内外网格研究者的重视和关注。
它与传统的分布式系统的主要区别在于它具有广域性、异构性、动态性三个特点，它主要应用于解决规模庞大、计算复杂、需要使用多种异构资源的计算问题，因此以前针对传统的分布式计算的调度方法已经不适用于网格环境中的任务调度。
在传统的并行和分布式调度问题中，所涉及的计算资源是同构的，因此不必关心资源所具有的属性以及资源能否满足用户所提交的任务的需要，而且，计算资源通常在地理上是集中的，因此不用关心系统在运行过程中通信所花费的开销。
网格任务调度的目的就是将"合适"的任务分配到"合适"的资源上去运行。
网格的出现，对分布式任务调度研究提出了新的挑战。
围绕着网格计算中的任务调度算法，一般来说有静态和动态的调度算法。
静态调度算法是指所有的任务-机器映射策略在执行任务调度前就已经全部确定;动态调度算法是指一些任务-机器映射策略在执行任务调度期间根据实际情况进行确定。
静态调度算法是网格计算中最早被研究的算法。
相对较为简单、调度算法运行开销低、对数据的依赖性小。
常见的静态调度算法有:Min-min、Max-min、A*、Duplex、OLE、MET、蚂蚁算法、GA、借鉴市场经济原理的效益函数启发式任务调度算法等。
此外还有一些算法思路比较新颖:两阶段(2-Phase)调度策略: 将一个计算任务的计算范围依次划分为LAN间和LAN内两个阶段，并分别在LAN间阶段和LAN内阶段设立全局的、集中的任务调度者，以负责制定该阶段的任务调度方案和监督任务执行情况。
但是，由于仅用涉及LAN的两层结构来刻画计算网格是不准确的，所以，2-Phase调度策略还不能很好地描述计算网格的调度，需要更深入的扩展。
基于市场供求关系的调度算法: 仿照日用品买卖市场调控策略来对计算资源进行优化组合。
计算资源的"价格"被设定为介于资源的需求和提供之间，当计算资源的"价格"确定后，对它们的分配过程就按照"先来先服务"的原则进行，统一地由调度者进行调度。
基于市场供求关系的调度算法利用经济学理论进行调度策略的分析，为其他调度算法提供了新颖的思路。
在本论文中将采用遗传算法来设计网格任务调度策略。
研究者们也提出了一些动态算法。
对于自适应任务调度算法，国内代表性的研究成果有参数扫描应用的自适应调度算法、HowU网格自适应调度模型等最新的算法，国– 3 –万方数据第一章 绪论外的如美国伊利诺斯工业学院提出的GHS(Grid Harvest Service)自适应调度模型。
到目前为止，人们提出了很多网格系统的调度技术和算法。
但是在网格计算环境中，已有的任何调度模型、策略、调度目标函数和算法都不可能适宜一切应用和环境;同一套调度机制在不同的条件下其表现性能不一定相同，因此，该领域的研究还有待进一步发展和完善。
网格任务调度存在的问题主要是:(1)现有的各种网格任务调度方案很难满足资源提供者和用户对网格用户对网格环境的不同需求的矛盾;(2)为网格调度设计了各种各样的启发式算法，目前的研究还处于模拟仿真阶段，还需要在理论和实践中不断完善。
(3)缺乏真实的网格测试环境来准确验证改进的算法的性能收获。
§1.3 主要研究工作网格技术将所有可用于共享的资源通过网络连接起来，并为各种复杂的计算任务提供资源服务。
用户通过向网格系统提交计算任务来共享网格资源，网格调度程序再按照某种策略把这些任务在任务约束条件如网络带宽，资源节点性能等的基础上，采用适合于网格计算环境的任务调度算法，从而向用户提供最优性能。
本文的主要工作如下:(l)介绍网格的相关概念和基本原理，总结网格的特点及其体系结构等基本知识和研究的背景，阐述网格计算的发展现状和现有的应用情况。
(2)分析网格任务调度的原理和特点，将遗传算法应用于网格任务调度。
针对遗传算法可能出现的早熟收敛等缺点，提出了一种改进算法DNA遗传算法(DNA-GA)。
该方法中染色体编码采用DNA编码，在标准遗传算法选择、交换、变异基础上还引入倒位操作算子，并且增加了新的基因级操作(算子) :轮转算子，从而更加符合生物进化的规律。
另外，本文提出了一种改进的快速收敛的方法。
通过调整标准遗传算法结构，增加了对染色体的分割与重组操作，使标准遗传算法能快速收敛。
(3)在GridSim网格仿真环境下，针对改进的遗传算法的网格任务调度进行了详细的仿真实验，并对实验结果进行了分析。
§1.4 论文结构第一章为绪论，介绍本文的选题背景、研究意义和研究方法，并给出论文的组织结构。
第二章为网格计算的基础知识，介绍网格的基本概念和特点，并详细描述网格的体系结构，然后介绍目前国际上最有影响的网格计算项目GLOBUS。
同时还介绍了网格任务调度的基本知识，分析任务调度的特点，研究网格任务调度的原理和调度过程，并介绍和分析了现有任务调度算法。
– 4 –万方数据第一章 绪论第三章介绍了遗传算法的理论知识，遗传算法的基本思想和流程，遗传算法的数学理论基础，以及编码方式，适应度函数和三种基本的遗传操作等内容。
第四章为基于改进遗传算法的网格任务调度算法的设计，内容包括:计算模型的建立，在DNA遗传算法下染色体设计，初始种群生成，选择、交叉和变异操作以及倒位、轮换操作。
第六章为结束语，总结本文的工作，提出不足之处，并指出亟待解决的一些问题，并对进一步的研究进行展望。
网格就是一个集成为一台巨大的超级计算机，它可以实现全球范围的计算资源、存储资源、数据资源、信息资源、知识资源、专家资源、设备资源，甚至是人才资源等各种相关的广泛分布的资源的全面共享。
基于网格的问题求解就是网格计算(Grid Computing)。
以上给出的网格和网格计算的概念是广义的定义。
狭义的网格一般被称为计算网格(Computational Grid)，即主要用于解决科学与工程计算问题的网格。
全球网格研究的领军人物、美国阿岗(Argonne)国家实验室的资深科学家、美国Globus项目的领导人Ian Foster曾这样描述网格:"网格是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一体，为科技人员和普通老百姓提供更多的资源、功能和交互性。
"2002年7月，Ian Foster提出了限定网格必须同时满足的三个条件 :(1)在非集中控制的环境中协同使用资源。
网格整合各种资源，协调各种使用者，这些资源和使用者在不同控制域中，否则，只能算本地管理系统而非网格。
(2)使用标准的、开放的和通用的协议和接口。
网格建立在多功能的协议和界面之上，这些协议和界面解决认证，授权，资源发现和资源存取等基本问题。
否则，只算一个具体应用系统而非网格。
网格允许它的资源被协调使用，以得到多种服务质量，满足不同使用者需求。
使得联合系统的功效比其各部分的功效总和要大得多。
这三个条件非常严格，像P2P，SUN Grid Engine，Condor等都被排除在网格之外。
Randy Bramley认为网格提供的计算能力是以前所无法得到的，而且也是不能够通过其它的方式得到的。
网格概念的核心就是突破了以往强加在计算资源之上的种种限制，使人们可以以一种全新的更自由、更方便的方式使用计算资源，解决更复杂的问题。
最重要的一点就是网格打破了传统的共享或协作方面的限制，以前对资源的共享往往停留在数据文件传输的层次，而网格资源的共享允许对其它的资源进行直接的控制，而且共享资源的各方在协作时可以以多种方式更广泛地交流信息，充分利用网格提供的各种功能。
网格使得共享与协作的方式和方法更广泛了，而且为这种合作提供了各种控制策略与手段，可以根据需要，动态地与不同的组织与个人建立各种级别的工作关系。
网格技术研究范围迅速扩大，根据求解问题的特点可以分为:计算网格(Computational Grid)、数据网格(Data Grid)，信息网格(Information– 6 –万方数据第二章 网格环境下的任务调度Grid)、知识网格(Knowledge Grid)、语义网(Semantic Grid)、访问网格(Access Grid)等方向，其应用层面也大大扩展。
按照IanFoster和Globus项目组的观点，目前应用领域目主要有5类:分布式超级计算、分布式仪器系统、数据密集型计算、远程沉浸和信息集成等。
一般而言网格计算系统具有以下几个特征:1.10 分布性:分布性是网格的一个最主要的特点。
各种设备与资源，是分布在地理位置不同的多个地方，这些资源的类型复杂，规模较大，跨越的地理范围较广。
这就决定了网格的计算一定是分布式计算而不是集中式计算。
分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特征。
1.11 系统的异构性:构成网格计算系统的超级计算机有多种类型，不同类型的超级计算机在体系结构、操作系统及应用软件等多个层次上具有不同的结构。
1.12 结构的不可预测性:网格计算系统由于其地域分布和系统的复杂使其整体结构经常发生变化，这与一般的局域网系统和单机的结构不同。
1.13 自治性与管理的多重性:网格上的资源首先是属于某个组织或者个人的，因此网格资源的拥有者对该资源拥有最高级别的管理权限，网格允许资源拥有者对他的资源有自主的管理能力，这就是网格的自治性。
由于构成网格计算系统的超级计算机资源通常属于不同的机构或组织并且使用不同的安全机制，因此需要各个机构或组织共同参与解决多级管理域的问题。
因此网格的管理具有多重性，一方面它运行网格资源拥有者对网格资源具有自主性的管理，另一方面又要求网格资源接受网格的统一管理。
§2.2 网格的体系结构网格体系结构就是关于如何建造网格的技术。
它给出了网格的基本组成与功能，描述了网格各组成部分的关系，刻画了支持网格有效运转的机制。
到目前为止，比较重要的网格体系结构有三个:Ian Foster等提出的5层沙漏体系结构，结合Web Service的开放网格体系结构OGSA，以及可以看作是OGSA的进一步发展的WSRF规范。
本文主要介绍OGSA和WSRF。
开放网格服务体系结构(Open Grid Services Architec-ture，OGSA) 将Globus标准和商业的Web服务标准相结合，把资源统一以网格服务的形式提供给外界使用。
Global Toolkit3(GT3)是OGSA标准的第一个主要实现。
OGSA架构如图2.1所示– 7 –万方数据第二章 网格环境下的任务调度图 2.1 OGSA结构图如果说五层沙漏结构是以"协议"为中心的"协议结构"，那么OGSA就是以"服务"为中心的"服务结构"。
这里的服务是指具有特定功能的网络化实体。
这种抽象将资源、信息、数据等统一起来，十分有利于通过统一的标准接口来管理和使用网格。
OGSA结合Web Service提出了网格服务，用于解决服务的发现、动态服务的创建、服务生命周期的管理等与临时服务有关的问题。
1. 物理和逻辑资源层.资源的概念是OGSA以及通常意义上的网格计算的中心部分。
资源并不仅限于处理器。
通用的中间件，比如文件系统、数据库管理系统、目录和工作流管理系统，在物理层之上提供这些抽象服务。
2. Web服务层这里有一条重要的OGSA原则:所有网格资源(包括逻辑的与物理的)都被建模为服务。
OGSI(Open Grid Services Infrastructure)规范定义了建立在标准Web服务技术之上的网格服务。
OGSI利用诸如XML与WSDL这样的Web描述语言，为所有网格资源指定标准的接口、行为与交互。
OGSI进一步扩展了Web服务的定义，提供了动态的、有状态的和可管理的Web服务的能力，这在对网格资源进行建模时都是必需的。
– 8 –万方数据第二章 网格环境下的任务调度1.14 基于OGSA架构的网格服务层Web服务层及其OGSI扩展为上层提供了基础设施:基于OGSA架构的网格服务。
目前GGF正在致力于在诸如程序执行、数据服务和核心服务等领域中定义基于网格架构的服务。
随着这些新架构的服务开始出现，OGSA将变成更加有用的面向服务的体系结构(Service Oriented Architecture, SOA)。
1.15 网格应用程序层OGSA的诞生，标志着网格不仅仅局限于科学计算领域，还能够对各种商业应用进行广泛的、基础性的网格环境的支持，实现更方便的信息共享和互操作，从而对商业模式、人员的工作方式和生活方式产生深远的影响。
它致力于实现以下目标:跨分布式异构平台管理资源;交付无缝的服务质量;为自治管理解决方案提供公共基础;定义开放的、已公布的接口;利用行业标准的集成技术。
WSRF随着网格的应用领域扩展，在美国旧金山召开的Globus WORLD 2004会议，就Globus的下一步发展方向进行了探讨，由Argonne实验室和IBM联合提出了WSRF(Web Service Resource Framework)的概念。
图 2.2 OGSA与WSRF的关系WSRF是在Grid网格技术和Web技术发展到今天的结合产物，其意味着网格和Web能在共同的基础上前进。
WSRF针对OGSI的缺陷，提出了用无状态"stateless"服务来控制有状态"stateful"的资源。
其架构提供了表示有状态资源的状态的方法，并且在Web服务和有状态资源之间建立起编码关系，称之为"隐含的资源模型"，使用的是常规的Web服务技术，特别是XML、WSDL和WS-Addressing。
OGSI和WSRF关心如何处理有状态资源。
然而，虽然这两种方法用的是不同的建模方式:一个是Grid service，而另一个则是WS-Resource，但是其提供本质相同的功能，用语义上相似的WSDL接口定义。
Grid service和WS-Resource可以用同样的方法创建、访问、检测，以及销毁。
这两种方法在概念上的主要区别在于WSRF用不同的结构为有状态资源和Web服务建– 9 –万方数据第二章 网格环境下的任务调度模，而OGSI则用同样的结构将有状态资源建模为支持GridServicePortType的Web服务。
这样就使得Grid技术更加适用于服务网格。
Web服务资源(WS-Resource)结构是表示有状态资源和Web服务之间的关系的方法。
Web服务资源框架是一组被提议的Web服务规范，它根据特定的消息交换和相关的XML定义来定义Web服务资源方法的描述。
它们描述了定义资源状态的视图以及将它与Web服务描述相关联来形成Web服务资源的总的类型定义的方法。
它们也描述了如何通过Web服务接口来访问Web服务资源的状态，并且定义了与Web服务资源分组和寻址相关的机制。
图 2.3 WS-Resource结构示意图Web服务资源框架具有五个技术规范，它们根据特定的Web服务消息交换和相关的XML定义来定义了Web服务资源方法的标准化描述，包括:1. WS-ResourceLifetimeWeb服务资源的析构机制。
包括消息交换，它使请求者可以立即地或者通过使用基于时间调度的资源终止机制来销毁Web服务资源。
2. WS-ResourcePropertiesWeb服务资源的定义，以及用于检索、更改和删除Web服务资源特性的机制。
3. WS-RenewableReferences使用在端点引用变成无效的时候所需要的用来检索更新版本的策略信息对于Web服务寻址(WS-Addressing)端点引用的约定的修饰。
4. WS-ServiceGroup– 10 –万方数据第二章 网格环境下的任务调度连接异构的通过引用(by-reference)的服务集合的接口。
1.16 WS-BaseFaults当Web服务消息交换中返回错误的时候所使用的基本错误。
GLOBUSGLOBUS项目是目前国际上最有影响的与网格计算相关的项目之一，是美国国家实验室Argonne的研发项目。
它发起于九十年代中期，其最初的目的是希望把美国境内的各个高性能计算中心通过高性能网络连接起来，方便美国的大学和研究机构使用，提高高性能计算机的使用效率。
随着对GLOBUS项目的深入研究，针对它的目标也进一步扩展，希望通过GLOBUS项目可方便对地理上分布的研究人员建立虚拟组织，进行跨学科的虚拟合作。
目前，GLOBUS项目把在商业计算领域中WebService技术融合在一起，希望不仅仅局限于科学计算领域，而且能够对各种商业应用进行广泛的、基础性的网格环境支持，实现更方便的信息共享和互操作，从而对商业模式、人的工作方式和生活方式产生深远的影响。
GLOBUS系统中一个关键的元素就是GLOBUS工具包，它定义了构建计算网格的基本服务和能力。
工具箱由一系列组件构成来实现基本服务，如安全，资源定位，资源管理，数据管理，资源预定以及通信。
从总体上讲，GLOBUS工具包的实现主要有四方面的内容:(1)网格安全，这是网格计算环境正常运行的保证，GLOBUS主要是结合目前成熟的分布式安全技术，并进行一定的扩展，以适合网格计算环境的特点;(2)网格信息获取与分布，在网格计算环境中如何发布资源信息，如何查询、检索资源信息是有效使用各种资源的前提条件;(3)网格资源管理，由于网格环境中的资源主要分布在广域网环境中，采用目前常用的局域网资源管理技术不能有效地对其进行管理，为此GLOBUS在局域网资源管理之上实现了更高层次的资源管理技术，在信息服务的支持下，可有效地支持广域范围内的资源管理;(4)网格远程数据传输，实现广域网环境下的高速、可靠的数据传输和实现对应用程序基本透明的远程文件I/0访问是GLOBUS考虑的重要内容。
针对上述四个方面的内容GLOBUS项目实现的有以下主要组成部分:2.8 网格安全基础设施-GridSecurityinfrastructire(GSI):GSI负责在广域网络下的安全认证和加密通信，提供单点登录功能、远地身份鉴别功能、数据传输加密功能等，提供了基于GSI协议的GenerieSecurityServices API(GSS-API)接口。
它是保证网格计算环境安全性的核心部分。