（计算机应用技术专业论文）网格任务调度算法研究及校园计算网格建设.pdf

摘 要 i 网格任务调度算法研究及校园计算网格建设 作者简介：陈丽军，男，1980 年 12 月出生，师从成都理工大学罗省贤教 授，2009 年 7 月毕业于成都理工大学计算机应用技术专业，获得工学获硕士学 位。 摘摘 要要 网络的高速发展使得组建网格成为可能。网格是通过 internet 将分散的计 算机虚拟成一个超级计算机，将网络中闲置的资源（包括计算资源、存储资源 以及科学仪器等）有效地管理利用，方便地提供给网格用户使用。随着网格技 术的发展，以整合计算资源为目标的计算网格在国内外迅速发展。 网格任务调度即如何将网格任务映射到网格资源上运行，以达到最佳的调 度策略。但由于网格资源具有异构性、动态性、自治性以及分布性等特点，网 格环境下进行任务调度是一个很具挑战性的问题。网格任务调度算法直接关系 到调度的速度、质量等方面，在网格技术的研究中，起着举足轻重的作用。在 现有网格调度算法的基础上对其进行改进，尽可能好地满足不同的调度目标， 也具有重要意义。 本文从网格体系结构入手，分析了 gt4 的协议层次结构，并对网格环境下 资源的特点进行了研究，对比了网格调度与本地调度之间以及和分布式调度之 间的不同之处，着重讨论了网格调度系统结构以及评价指标，建立起网格任务 调度模型。 本文对比了几种已有经典网格调度算法，特别是深入研究了 min-min 算 法，针对 min-min 算法的不足，从几个方面提出了几种改进算法：由于 min-min 算法存在着资源利用率低和执行时间较长的缺陷，本文引入分段思 想，提出了 seg-min-min 算法，seg-min-min 算法把待调度任务按任务长度 分为几个队列，先对长任队列进行调度，可以节省总的执行时间。综合考虑执 行时间、执行费用以及网格用户优先等级三方面因素，提出了基于优先级的调 度算法 mmpri 算法,在其它条件相同时使用 mmpri 算法，用户优先等级高的 任务将会先被执行，由于考虑了执行费用对调度的影响，在一定程度上达到了 总的执行时间和执行费用之间的平衡。由于 min-min 算法可能出现负载不均 衡的现象，结合 max-min 算法，提出了循环调度算法 rmm 算法。rmm 算 法根据系统当前的负载均衡性动态地选择使用 min-min 算法或 max-min 算 法进行任务调度，能有效地改进系统的负载均衡性。 为了网格检验任务调度算法的有效性和优越性，需要在不同情况下对其进 成都理工大学硕士学位论文 ii 行测试，如任务的数量、资源的数量、用户的需求。此外，在网格任务调度算 法的研究和实验中，我们需要的是一个可以重复实验，并且可以控制的环境。 由于使用真实的网格环境来验证调度算法的有效性和性能是比较困难的，因此 采用网格模拟器完成这一算法实验工作。本文详细对比了几种常用的网格模拟 器，重点研究了 gridsim，探索出了使用 gridsim 进行任务调度算法的仿真技 术和调试分析方法。利用 java 编程技术在 gridsim 上实现了 min-min 算法以 及本文提出的改进算法，并进行了性能比较分析，实验证明本文提出的改进算 法是有效的。 成都理工大学校园计算网格 ucgrid3.0平台的核心技术是基于 gt4 开发的 计算网格分布式中间件，并以此为基础建立了校园计算网格门户，提供了作业 管理、资源管理、用户管理、vo 管理、插件管理、节点管理等功能。本文为 ucgrid3.0 增加了资源注册功能，进一步完善了该校园计算网格平台。 关键词：网格 任务调度 任务调度算法 网格模拟器 性能评价指标 abstract i research of the grid task scheduling algorithm and the improving of the campus computing grid introduction of the author: chen lijun, male, was born in december, 1980, whose tutor was professor luo shengxian. he graduated from chengdu university of technology in computer application major and was granted the master degree in july, 2009. abstract the rapid development of network makes it possible to form the grid. utilizing internet, grid organizes distributed computers into a virtual supercomputer, and manages idle resources (including computing resources, storage resources, and scientific instruments, etc.) effectively, makes it available to grid users. accompanying the development of grid technology, computing grid is developing rapidly all over the world. grid task scheduling is that, how tasks will be mapped to run on the grid resources in order to achieve the best scheduling strategy. however, because grid resources have the following characteristics: heterogeneity, dynamic, self-government, as well as the distribution, etc., grid task scheduling is a challenging problem. grid task scheduling algorithm is directly related to the scheduling of the speed, quality, etc., and plays an important role in the grid study. improving the existing grid scheduling algorithm to meet the objectives of different scheduling as well as possible, is also important. this thesis starts from the grid architecture, studies the protocol of gt4, and studies grid resource characteristics, compares of grid scheduling and local scheduling and distributed scheduling differences, focuses on the structure of the grid scheduling system as well as evaluating the goals, and establishes a grid task scheduling model. this thesis analyzes and compares a number of classic grid scheduling algorithms, in particular, studies of the min-min algorithm deeply, points out the lack of min-min algorithm, and proposes several improved algorithm in several ways. this thesis, aiming at min-min algorithm with the defect of a low utilization rate of resources and a long execution time, considering multiqueue thinking, proposes seg-min-min algorithm. seg-min-min algorithm divides 成都理工大学硕士学位论文 ii tasks into several queues by the length of tasks, and schedules the long task queue first, which can save the total execution time. considering the execution time and execution costs as well as grid users level three factors, this thesis proposes priority-based scheduling algorithm, mmpri algorithm. using mmpri algorithm, under the same conditions, the higher priority that the user owns, the earlier whose tasks will be scheduled. as considering the impact on scheduling of the cost, mmpri algorithm reaches a balance between total execution time and implementation costs to some extent. because min-min algorithm may lead to load imbalance, combining with max-min algorithm, this thesis proposes a cycle scheduling algorithm, rmm algorithm. rmm algorithm dynamically chooses to use min-min or max-min algorithm according to the balance of the current system, can effectively improve the systems balance. in order to test the effectiveness and performance of grid task scheduling algorithm, it needs to be tested in different situations. besides what we need is a repeat, and can be controlled environment. as a result of the use of real grid environment to do it is difficult, we use the grid simulator to complete task scheduling algorithms experiments. this thesis carries on a detailed comparison about several commonly-used grid simulators especially the gridsim, and explores the simulation technology and debugging analysis methods of task scheduling algorithms by using gridsim. using java programming technology, this thesis realizes the min-min algorithm and the improved algorithms proposed in this thesis on gridsim, compares and analysis of the performance. the result of experiment shows that the algorithms proposed in this thesis are valid. the core technology of chengdu university of technology (cdut) university computing grid 3.0 (ucgrid3.0) platform is a distributed computing grid middleware which is developed on the base of gt4. ucgrid3.0 builds campus computing grid portal, and provides the job management, resource management, user management, vo management, plug-in management, node management and so on. this thesis adds resource register function into the ucgrid3.0, improves the campus computing grid platform further. key words: grid task scheduling task scheduling algorithm grid simulator performance evaluation criteria 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果， 也不包含为获得 成都理工大学 或其他教 育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 成都理工大学 有关保留、 使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和 借阅。本人授权 成都理工大学 可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 （保密的学位论文在解密后适用本授权书） 学位论文作者签名： 学位论文作者导师签名： 年 月 日 摘 要 i 网格任务调度算法研究及校园计算网格建设 作者简介：陈丽军，男，1980 年 12 月出生，师从成都理工大学罗省贤教 授，2009 年 7 月毕业于成都理工大学计算机应用技术专业，获得工学获硕士学 位。 摘摘 要要 网络的高速发展使得组建网格成为可能。网格是通过 internet 将分散的计 算机虚拟成一个超级计算机，将网络中闲置的资源（包括计算资源、存储资源 以及科学仪器等）有效地管理利用，方便地提供给网格用户使用。随着网格技 术的发展，以整合计算资源为目标的计算网格在国内外迅速发展。 网格任务调度即如何将网格任务映射到网格资源上运行，以达到最佳的调 度策略。但由于网格资源具有异构性、动态性、自治性以及分布性等特点，网 格环境下进行任务调度是一个很具挑战性的问题。网格任务调度算法直接关系 到调度的速度、质量等方面，在网格技术的研究中，起着举足轻重的作用。在 现有网格调度算法的基础上对其进行改进，尽可能好地满足不同的调度目标， 也具有重要意义。 本文从网格体系结构入手，分析了 gt4 的协议层次结构，并对网格环境下 资源的特点进行了研究，对比了网格调度与本地调度之间以及和分布式调度之 间的不同之处，着重讨论了网格调度系统结构以及评价指标，建立起网格任务 调度模型。 本文对比了几种已有经典网格调度算法，特别是深入研究了 min-min 算 法，针对 min-min 算法的不足，从几个方面提出了几种改进算法：由于 min-min 算法存在着资源利用率低和执行时间较长的缺陷，本文引入分段思 想，提出了 seg-min-min 算法，seg-min-min 算法把待调度任务按任务长度 分为几个队列，先对长任队列进行调度，可以节省总的执行时间。综合考虑执 行时间、执行费用以及网格用户优先等级三方面因素，提出了基于优先级的调 度算法 mmpri 算法,在其它条件相同时使用 mmpri 算法，用户优先等级高的 任务将会先被执行，由于考虑了执行费用对调度的影响，在一定程度上达到了 总的执行时间和执行费用之间的平衡。由于 min-min 算法可能出现负载不均 衡的现象，结合 max-min 算法，提出了循环调度算法 rmm 算法。rmm 算 法根据系统当前的负载均衡性动态地选择使用 min-min 算法或 max-min 算 法进行任务调度，能有效地改进系统的负载均衡性。 为了网格检验任务调度算法的有效性和优越性，需要在不同情况下对其进 第章 引言 1 第第 1 章章 引引言言 在人们建设万维网的滚滚热潮中，一些信息领域的有志之士敏锐地觉察到 了互联网潜在的能力，开始了网格的研究和开发工作，他们希望把互联网建设 成为一个全面共享的基础设施网格。在网格上，人们可以方便地共享各种 资源，如同我们现在可以方便地利用电力网所提供的电力资源一样，只要用户 把电器插入插座，就可以使用不同发电厂、通过不同的传输网送到用户家中的 电力资源。 网格(grid)一词在 20 世纪 90 年代中期首次被用来描述用于科学和工程分 布式计算的基础设施。这种基础设施把计算资源、数据存储设施、广域网络、 仪器设备等连成有机的整体，方便用户使用这个基础设施中的任何资源。网格 从广义上说是一个集成的计算和资源环境1-6。作为一个分布式计算平台，网格 能够解决科学、工程和经济中的大规模计算问题和数据密集型问题，能够实现 地理上广泛分布的高性能计算资源、信息资源、应用系统、服务系统、组织、 人员等各种资源的共享与聚合。 网格计算(grid computing)是伴随着互联网技术而迅速发展起来的， 专门针 对复杂科学计算的新型计算模式。这种计算模式是利用互联网把分散在不同地 理位置的计算机组织成一个“虚拟的超级计算机” ，其中每一台参与计算的计算 机就是一个“节点” ，而整个计算网格是由成千上万个“节点”组成的“一张网 格” ，所以这种计算方式叫网格计算。这样组织起来的“虚拟的超级计算机”有 两个优势：数据处理能力超强；能充分利用计算机的闲置处理能力。简单 地讲，网格是把整个网络整合成一台巨大的超级计算机，实现计算资源、存储 资源、数据资源、信息资源、知识资源和专家资源的全面共享2。 由于各种资源、管理机制、用户和应用程序间存在大规模的异构性，网格 资源的高效管理和任务的有效调度已成为网格研究的重要内容之一。 1.1 选题依据 1.1.1 网格调度系统的复杂性 网格调度技术非常复杂5,34最主要的原因是网格具有一些独有的特征，例 如，网格资源的动态变化性、资源的类型异构性和多样性、调度器的分布和局 部管理性等。在网格调度中，还需要考虑移植性、扩展性、效率、可重复性以 及网格调度和本地调度的结合等一系列问题。 在传统的并行和分布式调度问题中，所涉及的计算资源是同构的，因此不 成都理工大学硕士学位论文 2 必关心资源所具有的属性以及资源能否满足用户所提交作业的需要，而且计算 资源通常在地理上是集中的，因此不用关心系统在运行过程中的通信所花费的 开销。 而对于网格环境，当前调度算法关心的主要问题是调度来自不同用户的应 用程序到可用的计算资源上，从而最大限度地让网格系统得到最大的使用，它 追求的是调度的高吞吐率。另一方面，网格调度在本质上比局部调度复杂，因 为网格调度要面向跨管理域的大范围的资源，而且在网格这样的动态分布式计 算环境，资源可用性变化常常出乎意料，所以网格环境中的调度很有难度。 1.1.2 网格调度研究的意义 任务调度首先根据某一任务的需求，发现满足条件的资源，然后从满足条 件的资源中根据选择策略选择合适的资源，分配给该任务；任务在该资源上运 行，并处在资源本地的任务管理机制的管理之下；任务在资源上执行结束后， 把占用的资源归还给网格管理机构，任务管理器把任务执行结果和有关信息反 馈给任务提交者。 在网格环境下，满足某个任务要求的计算资源可能不止一个，但是该任务 在这些资源上执行花费的时间和付出的代价（费用）可能不同，此外同样都是 满足条件的资源，但提供给使用者的服务质量也会存在差异。 对于一个网格调度系统，从用户的角度来说，用户希望在保证了服务质量 的前提下付出的代价最低、花费的时间最短；而从系统的角度来说，管理员则 更关注网格调度导致的系统吞吐率、负载平衡等指标。这两方面的指标有时候 并不能达到完全一致，这就给网格调度带来了多种可能性。 在网格环境中为了充分、合理、安全地利用网格资源以满足用户应用需要 的服务质量要求，为了给用户任务在远程节点上的运行提供透明支持，网格任 务调度系统有其存在的必要性和研究的重要性。 调度算法的优劣是实现高效使用共享资源的重要环节，直接关系到网格环 境中调度的速度、质量等各方面的因素，在网格计算技术的研究中，起着举足 轻重的作用。高效的任务调度算法可以充分利用网格系统的处理能力，从而提 高应用程序的性能。通过网格调度，可以把应用程序所需的计算隐藏于网格中， 降低了上层应用的复杂性，使用户不必关心任务所需的计算放在什么地方去执 行，从而把更多的精力投入到业务本身的开发中。 globus7作为目前网格计算事实上的标准，它对资源调度的支持很弱，提 供资源调度模块，但不提供资源调度策略。资源调度策略来自服务层，globus 中也没有提供再调度的功能。针对具体的应用网格，必须在高层设计出高效的 任务调度算法。 第章 引言 3 1.2 论文研究内容及创新点 本文研究网格的体系结构，并深入研究网格任务调度的本质、特点、模型、 组织结构和调度过程，对网格调度进行了详尽的分析和探讨，讨论了网格任务 调度算法的评价因素；深入研究现有的网格调度算法，并分析比较了它们之间 的优缺点，在此基础上提出针对经典调度算法的改进方法。另外，本文还研究 并完善成都理工大学校园计算网格 ucgrid3.0 平台相关功能。 1.2.1 论文研究内容 本文研究的主要内容是分析影响网格任务调度性能的因素，网格任务调度 性能的评价指标，以及对现有网格任务调度算法的改进，借助网格模拟器进行 算法仿真实验。本文主要的研究内容如下： （1）研究网格体系结构，研究目前事实上的网格标准 globus 的协议层次； （2）研究网格环境下资源的特点，分析网格调度与本地调度以及与分布式调 度的不同，讨论网格调度的组织结构，建立起网格任务调度的模型，并 研究了网格中任务调度的评价标准； （3）深入研究经典的网格任务调度算法，着重研究 min-min 算法； （4）针对经典网格任务调度算法的不足，研究对它的改进方法。并提出几种 改进算法：seg-min-min 算法，从总的执行时间和资源利用率两方 面对 min-min 算法进行改进；mmpri 算法，除了总执行时间外，为 min-min 算法增加了网格用户优先等级和执行费用的考虑； rmm 算 法，从系统的负载均衡性方面对 min-min 算法进行改进； （5）研究分析目前常用的网格模拟器，着重分析 gridsim8,18体系结构和 gridsim 中网格实体资源的模拟步骤、在 gridsim 上进行调度算法的仿 真实验的流程和实验结果分析方法； （6）研究并完善扩展成都理工大学校园计算网格 ucgrid3.0 平台的功能：实 现资源注册功能。 1.2.2 论文创新点 本文对计算网格调度原理以及现有调度算法进行深入分析，提出了几种基 于经典网格任务调度算法的改进算法；研究对比了常用的网格模拟器，并在网 格模拟器 gridsim 上实现了 min-min 算法以及文中提出的改进算法。具体内 容如下： （1）针对 min-min 算法总是优先调度短任务，可能导致资源利用率低、主 机负载不均衡的缺陷，在 min-min 算法的基础上提出了基于分段思想 成都理工大学硕士学位论文 4 改进算法（seg-min-min 算法） ； （2）考虑到网格环境的异构性、网格任务在不同资源上执行时间和执行费用 的不同，以及用户本身的权限级别的差异，提出了一种基于优先级的改 进算法（mmpri 算法） ； （3）由于网格环境的复杂性和网格调度本身的复杂性，利用某一种策略设计 的调度算法要在各种情况下都能取得良好的性能是难以做到的，因此结 合 min-min 算法和 max-min 算法，提出了一种循环调度算法（rmm 算法） ； （4）利用 java 编程技术，在网格模拟器 gridsim 上实现了改进的网格调度 算法，并分析和验证改进算法的有效性。 第章 网格调度技术基础 5 第第 2 章章 网格网格调度调度技术基础技术基础 2.1 网格技术 网络是把地理上分散的计算机系统通过网络设备连接在一起，相互独立的 计算机系统之间在遵循一定的通信协议的基础上实现资源共享。现代网络大致 经历了三次发展过程，从基于简单设备的相连，到基于 web 的资源共享，再 到更大范围内实现资源的共享（即网格技术） 。通过网格这种基础设施，用户不 需要了解网格环境的具体资源细节，就可以在网格环境中使用各种资源提供的 计算能力，完成相关的计算任务。 网格的目标是资源的共享与协作，要让加入到网格中的用户能够容易地访 问网格资源。在这种网格平台上，用户不需要使用远程登录（telnet） 、文件传 输协议（ftp）等工具就可以使用远程节点计算资源。现在这些计算资源主要 是指一些 pc 的资源节点、计算机集群环境、高性能计算机节点和各种高性能 的服务器。 用户在向网格提交作业或请求的时候，由网格来分配资源并控制其作业运 行和资源使用，包括把这些作业分配到哪些计算机上运行，作业提交之后，状 态如何收集，结果返回到哪台计算机，用户如何获得返回结果等等。这些工作 对用户来说是透明的，用户使用网格中的各种资源时，不需要关心是分布在哪 个地域的哪台计算机为自己提供了服务。总之，网格的目的就是不分地理位置 的远近、不管用户提交作业的类型和复杂程度，为用户提供一个统一且简单的 共享网格资源的接口。随着网格技术和 web 服务的结合，网格技术具有以下的 特点： （1）以成熟的网络技术、计算机技术、通信技术、电器技术为基础； （2）资源接入简单，不管是超级计算机、集群系统还是单个的 pc 计算池都 可以很容易地被接入到网格中，使得网格的扩展性很强； （3）网格为用户提供一个比它现有资源更强的计算力，但资源层的细节对用 户透明； （4）结合了最新的 web service 技术，提出并实现 wsrf 体系结构。 根据网格客体对象的不同，可以把网格分为数据网格、计算网格和服务网 格。数据网格中共享的基本单位是数据，主要解决数据的共享问题；计算网格 中共享的基本单位是计算资源，计算网格为用户提供共享资源的良好接口和机 制；服务网格中共享的对象是服务，以服务的形式提供共享的手段。计算网格 以给用户提供计算资源的计算力为目的，网格用户可利用这些计算资源为自己 成都理工大学硕士学位论文 6 解决大型计算任务问题321。 目前国外已有很多较为成熟的网格项目， 比如 globus项目， legion， condor， condor-g，nimrod，unicore 以及 nsf 等。 2.2 globus toolkit 简介 globus tookit7,36工具包来源于 globus 项目，globus 项目是国际上最有影 响力的与网格计算相关的项目之一，是由来自世界各地关注网格技术的研究人 员和开发人员共同努力的成果。globus tookit 是一个开放源码的网格的基础平 台，基于开放结构、开放服务资源和软件库，并支持网格和网格应用，目的是 为构建网格应用提供中间件服务和程序库。globus 的系统结构如图 2-1 所示。 图图 2-1 globus 的系统结构 globus 的网格计算协议建立在互联网协议之上，globus 的协议分为五层： 构造层、连接层、资源层、汇集层和应用层，globus 的五层沙漏型协议结构如 图 2-2 所示。 图图 2-2 globus 协议层结构图 grid 应用 globus 高层服务和工具 drm mpi grid cactus globusnun punch nimrod/g condor globus 核心服务 元目录 服务 复制目录 gass gridftp globus 安全界面 gram i/o 本地服务 con mpi lsf pbs tcp udp aix solar nqe linu 工具与应用 目录代理 诊断与监控等 资源与服务 的安全访问 应用层 汇聚层 资源与 连接层 构造层 各种资源 如计算机、存储 介质、网络、传感器等 第章 网格调度技术基础 7 （1）构造层（fabric）的功能是向上提供网格中可供共享的资源，它们是物 理或逻辑实体。常用的资源包括处理能力、存储系统、目录、分布式文件系统、 分布式计算机池、计算机集群等。toolkit 中相应组件负责侦测可用的软硬件资 源的特性、当前负荷、状态等信息，并将其打包供上层协议调用。 （2）连接层（connectivity）是网格中网络事务处理通信与授权控制的核心 协议。构造层提交的各种资源间的数据交换都在这一层的控制下实现。各资源 间的授权验证、安全控制也在这里实现。在 toolkit 中，相应组件采用基于公钥 的网格安全基础协议（gsi） 。在此协议中提供一次登录、委托授权、局域安全 方案整合、基于用户的信任关系等功能。资源间的数据交换通过传输、路由及 名字解析实现。 （3）资源层（resource）的作用是对单个资源实施控制，与可用资源进行安 全握手、对资源做初始化、监测资源运行状况、统计与付费有关的资源使用数 据。 在 toolkit 中有一系列组件用来实现资源注册、 资源分配和资源监视。 toolkit 还在这一层定义了客户端的 c、java 的 api 和 sdk。 （4）汇集层（collective）的作用是将资源层提交的受控资源汇集在一起， 供虚拟组织的应用程序共享、调用。为了对来自应用的共享进行管理和控制， 汇集层提供目录服务、资源分配、日程安排、资源代理、资源监测诊断、网格 启动、负荷控制、账户管理等多种功能。 （5）应用层（applications）是网格上用户的应用程序。应用程序通过各层 的 api 调用相应的服务，再通过服务调用网格上的资源来完成任务。应用程序 的开发涉及大量库函数。为便于网格应用程序的开发，需要构建支持网格计算 的库函数。 目前，globus 体系结构已为一些大型网格应用所采用。研究人员已经在天 气预报、高能物理实验、航空器研究等领域开发了一些基于 globus 网格计算的 应用程序，较果较好。虽然这些应用仍属试验性质，但它至少表明，网格计算 可以胜任不少用超级计算机难以胜任的大型应用任务。 目前 gloubs 的最新版本是 gt4，与 gt 以前的版本相比，gt4 包括很多 web 服务和标准。gt4 基于 web 服务实现了对各种资源类的标准接口，这一事 实可以显著简化设计，从而增加这些标准被接受的可能。gt4 还具有以下新特 性： （1）gt4 遵守最新的 web services interoperability organization（ws-i） web 服务标准，在不同环境之间提供了最大的互操作性； （2）gt4 包含对一些重要授权标准的初步支持，其中包括 security markup language（ saml） 和 extensible access control markup language 成都理工大学硕士学位论文 8 （xacml） ； （3）gt4 实现了 wsrf 和 ws-notification 规范； （4）gt4 具有复杂的授权和安全功能。globus 在网格安全性方面一直非常 努力，从安全性的观点来看，gt4 已经满足企业需求； （5）gt4 提供了高级的执行和数据管理功能7。 2.3 网格任务调度 在网格系统中，有大量的应用在运行，这些应用又共享网格的各种资源， 如何才能够使得这些应用获得最大的性能，这就是调度需要解决的首要问题。 网格全球论坛(global grid forum)公布了一系列网格草案， 其中将网格调度 分为低级调度和高级调度：低级调度实例实现计算系统的本地调度，高级调度 实例实现网格中的协同调度。通常，高级调度实例又称网格调度器，低级调度 实例又称本地调度器。网格调度器一般不直接控制计算系统中的资源，而是根 据网格任务的资源分配请求，为任务选择一个或一组计算系统，然后将分解后 的资源分配请求发送给这些计算系统上的本地调度器，由本地调度器完成最终 的资源分配21,22。 可见，网格调度器完成网格层次的调度，本地调度器完成本地层次的调度， 网格层次的调度主要完成任务到资源的映射，本地层次的调度主要完成任务的 资源分配与运行。网格中的任务调度分网格层次调度和本地层次调度两个阶段 进行，在逐层抽象的中间件中，网格层次调度位于聚合层。 在加入网格后，计算系统通常保留自己的本地调度器，只是增加本地调度 器与网格调度器的访问接口。因此，建立计算网格中的作业调度系统，主要是 设置（若干个）网格调度器，建立网格调度器之间、网格调度器与本地调度器 之间的联系，并在网格调度器上实现网格层次的一些调度方法。 计算网格中的任务调度主要指网格层次的调度。 2.4 网格任务调度研究现状 到目前为止，国际上很多的组织机构都对网格资源调度进行了深入研究， 并将其成果应用于各自的网格系统之中。现已在计算网格的资源管理和任务调 度中广泛使用的网格资源管理和任务调度系统有 condor、lsf、nimrod/g、 apples 和 legion 等。 2.4.1 condor condor10是一个资源管理和任务调度系统，用来管理计算密集型任务的批 第章 网格调度技术基础 9 处理队列，提供了传统的队列和调度功能，支持先来先服务、抢先调度和专用 调度策略。在典型的使用情景中，用户将任务提交给 condor，它会对任务进行 排队并监视，然后在任务完成时将结果表示出来。condor 不仅在这种环境中工 作得很好，而且它也可以通过利用这些资源空闲时的空闲周期有效地管理非专 用的资源。 2.4.2 lsf lsf14是一个资源管理和工作负载调度系统，由 platform computing corporation 开发。lsf 可以利用包括台式电脑、服务器和大型机等在内的计算 资源，来确保获取资源的优先权服务级。lsf v6 支持一系列的计算机体系结构 和操作系统，包括 ibm、hp、intel、sun、sgi 和 nec 等。一个 lsf 集群有一 个主控主机和若干个执行主机。主控主机是整个集群的中心协调者。它负责任 务的调度和分配； 执行主机用来执行任务； 提交主机负责将任务送至 lsf 集群， 提交主机也可以变成执行主机。一旦主控主机出现故障，集群中的另一个 lsf 服务器将变成主控主机。 2.4.3 nimrod/g nimrod/g11,12是一个网格化的资源管理和调度系统，它支持期限和参数扫 描应用的基于经济的计算， 也支持一种参数声明建模语言用于表达实验的参数。 包括 nimrod/g 客户端、参数引擎、调度者和分配者几个部分。 nimrod/g 在资源管理上遵循的是分级的和计算的市场模型。nimrod/g 与 网格中间件系统（如 globus 等）交互，提供了资源发现，资源交易，任务映射， 结果收集。用户可以指定 qos 要求，调度策略是面向应用程序的，并且是由用 户定义的要求如 deadline，budget 的限制驱动的。负载平衡由周期性的调度来 完成。 2.4.4 apples apples13是一个运用于网格上的自适应的应用级网格调度系统， 并不是一 个资源管理系统，每一个提交给网格的应用都有自己的 apples。apples 的设 计哲学是系统性能和利用的所有方面都起源于使用系统对应用的一种预见。 apples 包括了网络气象服务（nws） 、用户规范、模型、资源选择者、计划者、 性能评估者、协调者、执行者等组件。为了取得应用效果，apples 对特定资 源点上的应用性能进行度量，并利用这种信息来进行资源选择和调度安排。 apples 以并行的主-从式应用为目标。 成都理工大学硕士学位论文 10 2.4.5 legion legion15是弗吉尼亚大学的研究项目，是一个基于对象的网格操作系统。 其目标是提供一台具有可扩展性、站点自治，核心是一个单一并一致的虚拟机。 legion 通过类似 corba 和 dce 使用的遗留代码包装对象完成多重语言接口和 交互操作能力，其运行系统是一个“开放式系统” ，并且有相关的消息传递应用 程序接口，系统的内存被作为一个单一、永久的对象空间。legion 中定义了一 个 api 用于对象交互，但没有规定编程语言和通信协议。 legion 提供通信和同步管理，通过为并行构件提供对象包装，可运行并行 方法调用。在 legion 中调度数据并行构件是静态的，并且可以分成三个明显的 阶段：处理器选择、负载选择和布置。首先是识别候选处理器；其次，选择处 理器的数量与类型以及分解数据域；最后，任务被映射到选择的使通信时间最 少的处理器上。 legion 提供了一个控制主机负荷的机制，不做出资源分配决定，但是提供 在资源对象和执行映射决策间作出映射决策所必须的基本机制。legion 资源管 理是层次型的，使用分布式调度策略，也支持缺省的面向系统的调度策略，并 允许通过资源代理扩展其策略。同时，legion 将容错协议包装在基本类中，用 户可以扩展它。 第章 网格任务调度模型与评价 11 第第 3 章章 网格任务调度网格任务调度模型与评价模型与评价 3.1 网格任务调度 网格调度定义为将网格任务映射到多管理域的资源上的过程 23，就是将待 处理的任务按照用户指定的某种成本函数(性能或费用)或者按照网格系统性能 指标进行最优化映射到特定的物理资源上。这是一个 np 完全问题，可以使用 不同的算法来得到最优或近似最优解。 当前的调度方法主要分为两大类：以性能为中心的调度和以费用为中心的 调度。多数的网格系统调度属于第一类，它们是以最小化整体执行时间（例如， 性能的优化）为目标找到任务/资源的映射解。 3.1.1 网格环境中资源的特点 无论是简单的计算机系统还是复杂的分布式系统、并行系统、集群系统都 存在着不同的资源（如内存、硬盘等） 。但以往系统中的资源，无论是种类的多 样性方面，还是功能的多样性方面，都不能同网格系统中的资源相比，网格环 境中的资源具有一些较以往系统中资源所不具备的特点24： （1）异构性。网格中的资源种类繁多，功能各异，访问接口也不尽相同； 网格环境中存在不同体系结构的计算机系统，本地管理系统不同，共享规则不 同。 （2）动态性。某一时刻可用的资源可能在下一时刻就会出现故障或者变为 不可用；新的资源随时可能会加入进来；已有资源可以随时自由地离开网格系 统。网格资源的可获得性是随时间变化而动态变化的，一个网格资源贡献给网 格用户使用的能力是随时间的变化而变化的， 网格资源的负载也是动态变化的。 例如一个计算机系统，在资源所在地的白天工作时段，它只提供资源 20%的计 算能力给网格用户使用，80%由拥有者自己使用。晚上则提供资源 100%的计算 能力给网格用户使用。 （3）自治性。网格资源有自己的本地管理机构或处在本地管理机构的管理 之下，网格资源管理系统必须尊重资源所有者和本地管理者。但是网格资源也 必须接受网格的统一管理，不然资源之间就不能建立联系，实现共享和互操作。 （4）分布性。是指网格中的资源分布在地理上不同的地方，而不是集中在 一起的。网格资源虽然是分布的，但却可以充分共享。分布是网格硬件在物理 上的特征，而共享是在网格软件支持下实现的逻辑上的特征。 （5）二分特性。网格资源最终都是由具体的资源拥有者提供的，除了一部 成都理工大学硕士学位论文 12 分专用的网格资源是专门提供给网格用户使用的之外，大部分的资源都同时作 为网格用户可以使用的网格资源和资源拥有者自己使用的本地资源。因此，网 格用户远程使用资源不能损害资源拥有者和本地用户的利益。 3.1.2 网格调度与本地调度 由于网格环境计算资源本地自治的缘故，网格调度程序不可能全部拥有对 资源的控制权，而本地调度一般拥有对资源的完全控制权。这样，任务一旦提 交给本地管理机构管理，还需要本地任务调度的二次调度。在任务执行结束之 前，任务调度还需要服从本地调度，除非网格系统要求迁移任务或终止任务， 否则，任务执行时间还要看当时本地资源的具体状况，因为在本地需要调度的 任务既有网格任务也有本地任务。 计算网格的任务调度与单机操作系统的任务调度