（计算机软件与理论专业论文）基于gridsim的模拟框架设计与实现.pdf

摘要 网格计算作为并行和分布式计算的研究主流，在各个科学领域 的大规模应用中共享、聚合各种分散异构的资源。由于网格的异构 性和动态性，研究人员很难有效评价网格系统的性能。同时，由于 高性能网格节点较少且使用受限制，在网格资源管理和调度算法的 研究过程中，越来越多的研究者使用网格模拟器对研究的结果进行 评估和测试。 为了给网格研究者提供一个良好的模拟实验环境，使其从繁琐 的仿真模拟工作中解脱出来，通过对现有的网格模拟器实现机制的 深入分析，本文提出使用x m l 语言来描述网格资源属性、作业属性 和用户q o s 。在此基础上，使用g r i d s i m 工具包设计并实现了一个 模拟框架g s s f ( g r i d s i ms i m u l a t i o nf r a m e w o r k ) 。g s s f 提供x m l 分析模块，完成从x m l 描述到g r i d s i m 实体的映射，并提供网格调 度器模块来模拟各种网格环境下的复杂调度算法。针对工作流作业， 定义了一个简单的工作流描述语言g s w d l ( g r i d s i mw o r k f l o w d e s c r i p t i o nl a n g u a g e ) ，实现了一个分布式调度的工作流模拟引擎 ( w o r k f l o ws i m u l a t i o ne n g i n e ，w f s e ) ，该引擎使用消息驱动机制来 管理作业间的依赖关系和数据传递。为了给用户提供一个可选的实 验数据，本文以g r i d g 和g w a 为基础使用p y t h o n 语言设计了一个 网格生成器g r i d s i m g ，它生成g s s f 可使用的网格资源和独立作业。 实际应用表明，g s s f 为研究者提供了一个易用的、可扩展的网 格模拟环境，并为网格模拟技术的进一步研究打下了良好的基础。 关键词网格模拟器，g r i d s i m ，网格工作流，x m l ，网格生成器 a bs t r a c t g r i dc o m p u t i n gi sn o wam a i n s t r e a mt e c h n o l o g yo fp a r a l l e la n d d i s t r i b u t e dc o m p u t i n g i ti sa ne m e r g i n gt e c h n o l o g yt h a tf o c u s e so n u n i f o r m l ya g g r e g a t i n ga n ds h a r i n gd i s t r i b u t e dh e t e r o g e n e o u sr e s o u r c e s f o r s o l v i n gl a r g e s c a l ea p p l i c a t i o n s i n s c i e n c e ，e n g i n e e r i n g a n d c o m m e r c e b e c a u s eo ft h e s p e c i a l f e a t u r e so ft h e d y n a m i c h e t e r o g e n e o u sg r i de n v i r o n m e n t ，t h e r e s e a r c h e r s h a r d l y e v a l u a t e p e r f o r m a n c eo fl o t so fg r i ds y s t e m s t h ea c c e s sg r i dn o d e sa r en o t w i d e s p r e a d t h e r e f o r e ，m o r ea n dm o r er e s e a r c h e r su s eg r i ds i m u l a t o r s f o r i m p l e m e n t i n g ，t e s t i n g ，a n de v a l u a t i n g t h e i ri d e a si nr e s o u r c e m a n a g e m e n ta n ds c h e d u l i n ga l g o r i t h m s m o t i v a t i o na n dg o a lo ft h i st h e s i si sp r o v i d i n gb e t t e rs i m u l a t i o n e n v i r o n m e n t st h a ta l l o wr e s e a r c h e r st of o c u so nt h e i rt h e o r e t i c a lr e s e a r c h a f t e ra n a l y z i n gg r i ds i m u l a t i o nt o o l si nd e p t ht h a tc u r r e n t l ye x i s t ，a n i d e a rt h a tu s ex m i ，t od e s c r i b eg r i dr e s o u r c e s 。t a s k sa n du s e r sq o si s p r o p o s e d t h e n ，t h e g r i d s i ms i m u l a t i o n f r a m e w o r k ( g s s f ) i s p r e s e n t e d i tp r o v i d e sax m ，p a r s e rm o d u l et om a px 几d e s c r i p t i o nt o g r i d s i me n t i t y g s s fa l s op r o v i d e sag r i ds c h e d u l e rm o d u l et oe n a b l e s e a s y t o u s ee x p e r i m e n t a l s t u d i e so fv a r i o u sg d da n dl o c a ll e v e l s c h e d u l i n ga l g o r i t h m s i no r d e rt oa l l o wu s e r st od e s c r i b et a s k sa n dt h e i r d e p e n d e n c i e s as i m p l ea n df e x i b l ex m l b a s e dg r i d s i mw o r k f l o w d e s c r i p t i o nl a n g u a g e ( g s w d l ) i sd e f i n e d t h e n ，a d i s t r i b u t e d s c h e d u l i n gw o r k f l o ws i m u l a t i o ne n g i n e ( w f s e ) t o g e t h e rw i t hg s w d l i s d e s i g n e d am e s s a g e d r i v e ns c h e d u l i n ga r c h i t e c t u r e f o rm a n a g i n g d e p e n d e n c ea m o n gt a s k sa n dc o m m u n i c a t i n gb e t w e e nt a s k si ss h o w ni n w f s e i no r d e rt ou s eg s s fe a s i l y , ag r i dg e n e r a t o rc a l l e dg r i d s i m g t h a tb u i l to ng r i d ga n dg w ai sp r o p o s e d i ti sw r i t t e ni np y t h o n3 0 g r i d s i m gi su s e dt og e n e r a t ex m l b a s e dr e s o u r c e sa n dt a s k s a p p l i c a t i o n s s h o wt h a tg s s fp r o v i d e sa n e a s y - t o - u s e a n d e x t e n s i b l eg r i ds i m u l a t i o ne n v i r o n m e n t i tm a k e sag o o df o u n d a t i o nf o r t h ef u t u r er e s e a r c hi ng r i ds i m u l a t i o n k e yw o r d sg r i ds i m u l a t o r , g r i d s i m ，g r i dw o r k f l o w , x m l ，g r i d g e n e r a t o r 玎 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：丛日期：4 年月生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 名：盟翩签趔嗍导年上月旦日 硕十学位论文第一章绪论 第一章绪论 1 1 研究背景 网格是构筑在i n t e m e t 基础上的一组新型技术，对于由地理分布、组织独立 的计算资源、存储资源、数据资源、信息资源、知识资源、专家资源等组成的 动态虚拟组织的资源实现共享和协作问题的求解。作业调度和数据管理技术是 网格资源管理的重要部分。资源管理主要解决资源的定位、分配、认证、进程 创建以及其他使用资源的准备活动；作业调度主要解决任务分解、指派和安排 任务执行顺序的问题；数据管理主要解决数据网格中的数据文件的移动、复制 和删除等工作。由于网格固有的异构性和动态性，很难对网格系统的性能进行 评价，因此在网格资源管理和调度算法的研究过程中，越来越多的人采用网格 模拟器对提出的算法进行分析和比较。使用网格模拟器不需要搭建真实的网格 系统，它可以为用户提供一个可重复的和可控的实验环境。 网格模拟器的出现给网格研究者带了很大的方便，使那些不能接触到真实 网格环境的研究者也能够进行网格研究。在网格的研究过程中，网格模拟的必 要和重要性包括： 1 ) 在研发的起始阶段，并不存在真实的网格环境，各种网格的理论、技 术、算法等必须在非网格环境下进行模拟，在分析可行后才开发部署真实的网 格环境和应用。 2 ) 在网格技术成熟并大范围普及之前，大部分研究者都是在没有真实网 格环境下进行网格研究的，因此必须通过模拟来开展工作。 3 ) 真实网格环境的部署需要大量的人力、物力和财力，这对于大部分研 究者而言是不可得的；相对而言，模拟所需的资源容易具备。 4 ) 真实网格中的资源分布在世界各地，分属于不同的组织，在不同的安 全和共享策略下运行。因此，使用真实的资源使得研究各种各样的资源配置很 困难。而在模拟中，研究者可根据研究需要进行设置。 5 ) 在真实的网格环境下，资源的可用性、负载、安全和共享策略等随时 间动态变化，这使得试验无法重复，因而无法对各种调度算法等研究者关心的 对象作有意义的比较。而在模拟中，采用相同的设置就可以使实验重复。 6 ) 在真实网格环境下，系统可能要长时间运行，因此进行足够多的试验 是很耗时的。而在模拟中可以使同等规模的问题在短时间内完成。 由此可见，在网格研究中，不管真实的网格环境是否可得，模拟都是重要 的和必要的。 硕士学位论文 第一章绪论 1 2 国内外研究现状 1 2 - 1g r i d s i m 简介 g r i d s i m t l 。1 0 l 由澳大利亚墨尔本大学r a j k u m a rb u y y a 领导开发，它的首要目 标是通过模拟来研究基于计算经济模型的有效资源分配方法。g r i d s i m 通过资 源的“买”和“卖”来引入“经济模型”，从而达到控制网格资源的使用的目的。 g r i d s i m 能支持多用户环境的时间或空间共享、单一或多个处理器、共享或分 散内存计算机( 比如p c 、工作站、s m p 、计算机集群) 建模。g r i d s i m 提供了 一些资源和网络的建模和基本的模拟工具【1 1 1 3 1 ，能模拟不同类型的并行和分布 试计算基础构件，比如集群、网格、p 2 p 系统。在集群情况下，所有的资源( 也 叫节点) 被模拟在一个单一的时间区内。节点可是单处理器机器或对称多处理 器机器( 使用共享时间的操作系统和使用高速网络互联) 。在网格环境下，节点 分布在不同的时区，可以是单处理器、s m p s 或集群，通过时间或空间共享资 源管理器管理。 g r i d s i m 可以模拟不同能力、配置不同域的网络状况，支持应用程序组合， 资源发现信息服务，将作业映射到资源并且控制他们的运行等。这些特色可以 模拟资源b r o k e r 的运行和评估调度算法的性能。g r i d s i m 的开发小组也在不断 的添加新的功能使其更全面更完割3 h j l l 5 】。 g r i d s i m 工具包提供了全面的工具模拟不同种类的资源和用户。其主要特 征包括以下方面： 1 ) 允许不同类型的资源建模。 2 ) 资源可被构建运行在时间或空间上共享的模式下。 3 ) 可以定义资源性能。 4 ) 资源可被定位在任何一个时间区。 5 ) 依靠资源的本地时间周末和假同被映射，从而模拟非网格的工作量。 6 1 能模拟不同的并行应用程序。 7 ) 请求的作业可以是不同种类的，并且它们可以是c p u 或i o 。 8 ) 没有限制提交给一个资源的请求作业的数量。 9 ) 多个用户实体能提交在相同资源( 在时间或空间上共享的) 下同时执 行的作业。 1 0 ) 这些特性可以帮助研究者在构建调度应用程序时使用不同的市场经济 模型。 1 1 ) 明确了资源间的网络速度。 1 2 ) 支持动态和静态调度程序模拟。 1 3 ) 记录所有或经选择的作业统计表，并且能用g r i d s i m 的统计分析方法 2 硕士学位论文第一章绪论 来分析这些统计表。 1 4 ) 根据建模的资源，g r i d s i m 可以仿真各种类型的并行分布式计算体系， 如集群，网格，p 2 p 系统等。仿真网格时，所有的资源( 称为节点) 分布在不 同的时区，可以是单处理器，对称多处理器( s m p ) 或集群，由分时或分空间 共享的资源管理系统管理【1 6 1 8 】。 本文从以下几个方面对g r i d s i m 进行具体介绍： ( 1 ) g r i d s i m 体系结构 g r i d s i m 采用了分层的和模块化的体系结构来进行网格模拟，以充分利用 现有的技术，管理时也是当作分开的组件来管理。g r i d s i m 模拟平台结构可分 为五层，如图1 1 。 应用程序、用户、网格特定输入和输出 圆匡司亘叵曰 图1 1g r i d s i m 系统体系结构 第一层是g r i d s i m 的运行环境j a 、，a 虚拟机( j a 、，av i r t u a lm a c h i n e ，j v m ) 。 g r i d s i m 用j a v a 语言来实现的，而且它所使用的库s i m j a v a 也是用j a 、，a 实现 的，所以整个模拟器必须运行在j v m 上。 第二层是g r i d s i m 所使用的基础库s i m j a v a ，它是一个基本的离散事件组 件。其中大部分类都是从t h r e a d 继承过来的。 第三层包括核心网格实体模拟资源、信息服务等，应用程序模型，统 硕十学位论文第一章绪论 一访问接口，应用模拟原语和建立更高层次实体的框架。主要利用第二层的离 散事件服务模拟系统实体。 第四层是资源监控和调度应用程序。 第五层是利用第三层和第四层提供的服务对不同情境下的资源和应用建 模，并评估调度算法和资源管理策略。 ( 2 ) s i m j a v a 包 g r i d s i m i 具包是以s i m j a v a 为基础开发的。s i m j a v a l w 】是一个用j a v a 离散事件 模拟包。s i r n j a v a 的模拟中包含许多实体，这些实体通过运行自己的线程并行运 行。在自己的b o d y ( ) 方法中对一个实体的行为编码。s i m j a v a 中使用的是一种离散 事件模拟算法。一个核心的对象s i ms y s t e m 维持着将来事件的时间序列。最初所 有的实体被创建，并且所它们的b o d y ( ) 方法处于运行状态。当一个实体调用一个 模拟函数时，s i ms y s t e m 对象暂停实体线程，并放置一个事件在将来事件队列中 表示处理函数。当所有的实体暂停时s i ms y s t e m 从队列中弹出下一个事件，因此 走动模拟时间，并重新启动实体。就这样连续直到没有事件产生。 ( 3 ) g r i d s i m 实体 g r i d s i m 支持单处理器和多处理器实体、不同种类不同配置的资源系统。允 许资源被设置为地理分布的不同时区的【2 叭。它支持模拟网络实体在资源间的通 信。在模拟时，g r i d s i m 仓e 建一些多线程实体，这些实体并行运行。g r i d s i m 基本 的模拟实体有用户实体、b r o k e r s 、资源实体、信息服务实体、统计实体、基于i o 的网络实体等。 每一个用户实体代表了一个网格用户。其属性有作业的类型、调度优化策略、 活跃度、时区、截止时间和预算、d 和b 因子。每一个用户连接一个代理实体。用 户的每个作业首先提交给代理，代理再根据用户的调度策略调度作业参数。在调 度任前，代理动念的获得可用的资源列表。每个代理尝试优化用户的策略，因此 代理被用于获得资源的竞争。代理使用的的调度算法必须能很好的适应市场的供 给和情形的需求。 每个资源实体代表一个网格资源。每个资源与别的资源可能不同。资源属 性有处理器数目、处理器价格、处理器速度、内部调度策略、本地负载因素、 资源所在时区。资源处理速度和作业执行时问能用指令级别标准定义，如m i p s 和s p e c 。资源信息服务提供资源注册服务和可用资源信息保存列表。 输入输出实体用于g r i d s i m 实体之间的信息传输。每一个g r i d s i m 网络实 体都有i o 传输通道端口，这些通道和端口用于在实体间的输入和输出实体建 立连接。这些g r i d s i m 实体和它们的输入输出实体都是线程实体，它们都有 4 硕十学位论文第一章绪论 b o d y ( ) 方法处理事件。使用独立的实体来进行输入和输出使网络实体模型是双 向的，并且多用户间是并行通行的。缓冲器输入输出通道与每个g r i d s i m 实体 联合为实体间通信提供了一个简单机制。 ( 4 ) 模拟步骤 用g r i d s i m 进行模拟需要以下三个步骤： 1 ) 需要创建一个不同性能的网格资源，让这些资源像在不同时区、不同 策略的真实环境中一样。应用时也需要创建一些不同需求的用户。 2 ) 需要通过创建一些g r i d l e t 和定义所有的工作参数来模拟应用程序。这 些g r i d l e t 依靠应用程序模型组织在一起。 3 ) 需要实现资源监控。首先查询网格信息服务( g r i di n f o r m a t i o ns e r v i c e ， g i s ) ，其次查询资源性能包括成本，然后再依靠调度安排、网格策略或算法分 配g r i d l e t 给资源执行。 1 2 2 其它模拟器介绍 其它几个主流的模拟器有b r i c k s 、m i c r o g r i d 、s i m g r i d 、o p t o r s i m 、c h i c s i m 、 e d g s i m 、g r i d n e t 、j f r e e s i m 。 【1 ) b r i c k s b r i c k s l 2 i 】是由同本o c h a n o m i z u 大学和东京工业大学等在1 9 9 9 年发布的基 于1 a v a 的通用网格仿真工具，主要用于对高性能全局计算系统中的不同调度算 法和框架进行评估。在设计思想上，b r i c k s 采用了客户机网络服务器的体系结 构，它由全局计算环境和调度单元组成。全局计算环境包括客户端、网络和服 务器三个部分，分别表示用户、网络和服务资源，其中网络和服务器资源表示 为排队系统，整个b r i c k s 作为一个排队系统离散事件仿真器运行。计算任务模 型由通信时的数据量和计算时的指令数量表示：网络通信模型除了带宽、时延 之外还包括网络拥塞状态的模拟。调度单元可以根据对当前服务器和网络状态 进行监测，将监测结果存储到资源数据库中。该单元还包括了性能预测功能， 能够仿真和比较各种调度机制。 b r i c k s 采用的组件化结构使之能够灵活地替换和增加新的仿真模块。它作 为通用的网格仿真工具，已经用于多客户机多服务器的网络计算环境中，对作 业完成期限的调度算法、数据网格中的不同的调度和复制算法的性能进行仿真， 增加了对存储资源( 本地磁盘i o 开销、存储队列) 和复制管理机制的仿真。 由于现在不开放源代码，其他研究者不便于对此仿真工具进行更进一步的分析 和改进。 5 硕士学位论文第一章绪论 ( 2 ) m i c r o g r i d m i c r o g r i d 【2 2 】是由美国加州大学圣地亚哥分校u c s d 于2 0 0 0 年发布的一个 虚拟的网格计算环境，主要用于网格资源管理和应用程序适应性问题的研究。 m i c r o g r i d 是用c 语言开发的，运行于u n i x 操作系统。和其他网格仿真工具不 同的是，m i c r o g r i d 的一个重要的设计目标是通过对g l o b u st o o l k i t 的模拟，使 运行在g l o b u s 上的应用程序能够不加修改地直接运行在m i c r o g r i d 之上。通过 可重复和可控制的模拟实验对动态资源管理技术进行科学研究和评估。通过截 获应用对g l o b u s 的调用并模拟它在实际资源上的运行和性能特征，实现对所用 动态资源管理技术的评价。为了实现虚拟的g l o b u s 运行环境，m i c r o g r i d 提供 了对网格资源和网格信息服务的模拟，其中网格资源分为网络资源和计算机资 源，分别通过网络在线仿真器m a s s f ( m i c r o g r i dn e t w o r ko n l i n es i m u l a t o r ) 和 c p u 控制器来模拟。支持对g l o b u st o o l k i t 的虚拟化，支持用c 、c 抖、p e r l 、 p ”h o n 等语言开发的应用，支持消息传递界面m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 并行程序。目前m i c r o g r i d 的开发目标主要包括实现最新的g l o b u st o o l k i t 虚拟 计算环境，开发磁盘i o 仿真器来模拟存储系统行为。 通过对g l o b u s 环境的应用程序进行模拟，m i c r o g r i d 一方面能够很精确地 模拟一个网格应用程序在不同运行环境中的行为和性能，并对不同的运行环境 设置对应用性能的影响进行评价；另一方面，作为仿真工具能够对相同的环境 设置在运行不同应用程序时的性能进行评估。m i c r o g r i d 主要用作替代真实的网 格环境对应用程序的性能进行评估的工具，而不是作为研究各种网格资源管理 和调度技术的通用仿真工具。 ( 3 ) s i m g r i d s i m g r i d l 2 3 】1 2 q 是由美国加州大学圣地亚哥分校u c s d 于2 0 0 1 年发布的一个 分布式异构环境中的分布式调度和并行调度仿真工具。它用c 语言丌发，运行 于l i n u x 、i r i x 和a i x 操作系统，最新版本发布于2 0 0 7 年3 月。此程序由底 层s g ( s i m g r i d ) 和上层m s g ( m e t a s i m g r i d ) 组成。s g 是一个低级的、提 供了分布计算环境应用程序仿真核心功能的离散事件仿真工具，它提供了基本 的功能抽象和调用接口，包括建立网络连接、t c p 路由和主机等的资源模型， 可以建立数据传输或者计算任务的任务模型，建立网络拓扑结构，以及指定任 务之间的依赖关系和任务调度过程。在s g 的基础上，m s g 提供了更高级的 功能抽象，采用了a g e n t 、l o c a t i o n 、t a s k 、p a t h 和c h a n n e l 五种核心抽象，a g e n t 包括要完成的任务和任务的调度过程；l o c a t i o n 是a g e n t 运行的地方；t a s k 是 计算或数据传输任务；p a t h 是连接不同的l o c a t i o n ( 可能包括多个物理链路的 6 硕士学位论文第一章绪论 逻辑通道) ；而c h a n n e l 为a g e n t 之间进行通信的端口。仿真过程如下：定义主 机、链路、路由表等资源，定义a g e n t 并将a g e n t 分配到l o c a t i o n 然后进行仿 真。与g r i d s i m 所采用的离散事件仿真工具s i m j a v a 相比，s i m g r i d 的很多功能 是对s i r r d a v a 的重复开发，并借鉴了许多s i m j a v a 的设计思想。s i m g r i d 试图实 现n w s 的监测和预测功能，一方面它通过将n w s 的跟踪文件直接作为资源参 数，使资源在仿真过程中按照跟踪文件记录的状态而动态变化；另一方面 s i m g r i d 还提供了资源预测a p i 来修正预测误差对调度算法的影响。通过实现 分布式环境中的离散事件仿真功能，s i m g r i d 可以用作从工作站网络到计算网 格的分布式环境的仿真功能。通过引入n w s 相似功能，可以在一个具体的环 境中执行一个实际的网格应用程序之前，使用n w s 对运行环境中的资源进行 监测，将跟踪文件作为s i m g r i d 的建模参数，通过仿真评估一个应用程序在一 个实际计算环境中的性能。到目前为止s i m g r i d 已用于多个项目的研究，开发 者还在不断地对此工具进行完善。 相对于其他的网格仿真工具，s i m g r i d 提供了较强的网格拓扑模拟功能， 包括网络拓扑结构、带宽共享模式等。通过与其他网格状态监测工具的结合， 可以生成更逼真的网格运行环境。考虑到j a v a 的可移植性和面向对象的优势， 和基于j a v a 的仿真系统相比，l i n u x ( 或a i x 、i 刚x ) 加c 语言的组合方式可 能会对s i m g r i d 的后续开发和应用范围带来影响。 ( 4 ) o p t o r s i m o p t o r s i m l 2 5 j 是一个基于e ud a t a g r i d 体系结构的网格仿真工具，最初发布 于2 0 0 2 年，用j a v a 语言编写，目前的最新版本为2 0 0 4 年1 1 月发布的2 o 版， 主要用于对大规模广域分布式数据网格中的各种数据复制算法进行评估。数据 复制是通过将一个数据文件的多个副本放在多个位置从而提高系统吞吐量的重 要方法。如何创建、删除和使用副本文件由数据复制策略定义，不同的数据复 制策略会对系统性能产生不同影响。o p t o r s i m 假定每个网格节点可同时包括计 算单元和存储单元，分别提供计算和数据存储服务。各个节点通过网络链路连 接，每条链路有相应的带宽。计算单元在处理作业时需要使用存储单元中的数 据文件，作业到计算单元的调度由资源代理( r e s o u r c eb r o k e r ) 负责。数据文 件副本的选择、创建和删除由复制管理器( r e p l i c am a n a g e r ) 中的复制优化服 务( r e p l i c ao p t i m i s a t i o ns e r v i c e ) 负责。资源代理通过对各个候选调度方案的 性能进行评估来决定如何调度。在此过程中需要综合考虑所需文件副本的分布、 网络状态、计算单元的队列长度、处理能力等。复制优化服务由各个站点自行 负责，主要用于对本地副本的优化，包括复制决策、副本选择和文件替换等功 能，而实现这些功能是所采用的算法的不同组合就构成了复制优化策略。目前 7 硕士学位论文第一章绪论 已有的复制优化策略包括基于最近最少使用l r u ( l e a s tr c e n t l yu s e d ) 算法和 二种基于经济学的算法。为了对不同优化策略的性能进行评估，o p t o r s i m 采用 了平均作业执行时间、网络利用率、计算单元利用率和存储单元利用率四种评 价标准。 ( 5 ) c h i c s i m c h i c s i m t 2 6 】是一个基于p a r s e c 的用于对数据网格的动态复制策略进行仿真 的工具，与o p t o r s i m 的功能和设计目标相似。c h i c s i m 是在2 0 0 1 年由c h i c a g o 大学i a nf o s t e r 等人开发的。c h i c s i m 采用了层次化分布式结构，主要包括对网 格站点、用户和传输网络三种网格实体模拟，其中用户生成待处理的作业，每 个作业还需要一组数据文件才能执行；网格站点包括了一定数量的计算单元和 存储单元，站点之间的网络链路带宽有限。作业到站点的调度过程由外部调度 器e s ( e x t e r n a ls c h e d u l e r ) 决定，站点内的作业到不同处理单元的调度由本地 调度器l s ( l o c a ls c h e d u l e r ) 决定，而站点内的文件副本的复制、删除等操作 由数据集调度器d s ( d a t a s e ts c h e d u l e r ) 负责。c h i c s i m 主要考虑外部调度器 和数据集调度器中的调度算法，而本地调度器采用了简单的先进先出f i f o ( f i r s t i nf i r s to u t ) 算法。为了对各种调度策略进行评估，c h i c s i m 的评价标准为：每 个作业的平均数据传输量、作业的平均完成时间和处理单元的平均空闲时间。 由于到目前为止c h i c s i m 没有公开源代码，所以不便于其他研究者对此工具进 行研究和改进。 ( 6 ) e d g s i m e d g s i m 2 7 】由e u r o p e a nd a t ag r i d 项目组开发。它基于p t o l e m yi i ，模拟计 算工作流、物理数据和信息。在该模拟系统中，任何状态的改变( 比如作业的 产生、文件开始传输、信息的更新) 都会作为一个有时间信息的事件放入一个 队列中，这些事件被顺序的执行。 e d g s i m 由欧洲数据网格项目组开发。它是在p t o l e m yi i 基础上丌发的， 模拟欧洲数据网格并研究其性能的软件。主要研究任务调度和算法优化而注重 后者，任务主要用于数据密集型文件传输，可归到数据局部性原理在调度决策 过程中的重要性问题上。目标是比较不同调度算法性能；检测仿真性能的可信 性。e d g s i m 用户接口产生大量作业，分布到各站点上执行。作业的执行需要 数掘文件，这些文件随机分布在不同站点s e ( s t o r a g ee l e m e n t ) 上且在各自的 r c ( r e p l i c ac a t a l o g ) 上注册。每个站点的c e ( c o m p u t ee l e m e n t ) 管理w o r k e r 机器，所有可用资源都在其r b ( r e s o u r c e b r o k e r ) 上注册。n i c 实现用户接口 与站点的连接，并跟踪数据文件。作业在站点上执行时，首先被发送给r b ， 8 硕士学位论文 第一章绪论 r b 传递所需文件逻辑名表l f n ( l o g i c a lf i l en a m e ) 到r c ，r c 将l f n 翻译 成物理文件名p f n ( p h y s i c a lf i l en a m e ) 并将其发回r b ，r b 只选择原始备份 数据文件而不是已存在的任何副本作为新副本。然后，r b 确定合适的算法，发 送作业到所选的c e 。同时，s e 接到需求将所需的数据文件发往目的地。c e 分 配作业到闲置机器或排队。执行结果及相关信息以文本的形式输出。 ( 7 ) g r i d n e t g r i d n e t l 2 8 】模拟器是为了评估模拟数据网格中动态的数据复制策略，该项目 是由i b m 奖学会项目、i b m 阿尔马登研究中心以及美国国家科学基金联合支持 开发的。该项目提出了一种智能的副本策略，即基于代价估计( c o s t e s t i m a t i o n ) 模型的副本决策( r e p l i c a t i o nd e c i s i o n s ) 。g r i d n e t 基于模块化的设计，建立在 网络模拟器n s 2 的基础上。它允许用户指定不同的网络配置，不同的节点类型， 不同的网络资源，一个复制算法( 策略) 和一个计算代价的函数以及其参数。 g r i d n e t 的模拟环境主要有以下三类节点：客户端、服务端和缓存节点。客 户端负责产生数据访问的请求；服务端代表一个主要的存储节点；缓存节点代 表一个中间存储节点，用来复制一部分存储在服务器上的数据。这三者之间通 过n s 模拟器构建的网络拓扑来互连和通信。 ( 8 ) j f r e e s i m j f r e e s i m l 2 9 】由华中科技大学c g c l 实验室的网格性能评估小组开发。它提 供了通用的、模块化、可扩展的模拟库，通过多种不同的实体建模以及实体间 通信交互，使系统模拟更加符合网格环境的特点。j f r e e s i m 的执行流程如下： 1 ) 首先，系统接收用户实体的全局配置参数，初始化模拟系统的各个实 体并启动模拟过程；与此同时，全局信息实体接收来自各个可用资源的注册信 息。 2 ) 应用任务实体将任务通过消息机制传递给调度器实体；调度器查询全 局信息目录并根据调度策略将任务指派到合适的计算资源上执行。 3 ) 每一个资源都维护着一个本地的任务队列，当有多个任务都准备要执 行时，资源根据本地的调度策略模拟这些任务的执行。当一个任务的执行完成 后，任务的状态将在全局的信息实体中被更新。 4 ) 通过查询全局信息实体，调度器动态决定任务的执行情况。 5 ) 不断重复以上的执行过程，直到所有的任务都执行完毕。 在对当前主流模拟器进行详细介绍以后，表1 1 对这些模拟器作了个简 单比较阻3 2 1 。 9 硕士学位论文 第一章绪论 表1 1 几大主流模拟器的比较 很多网格研究者使用上述的模拟工具进行模拟实验【3 3 。3 8 】。用户在使用这些 模拟工具进行网格模拟实验时需要分析工具示例代码和阅读大量的文档，然后 通过编程来实现资源、作业、用户的建模。这需要用户花一定的时间去熟悉模 拟工具提供的接口和使用方法。当用户对模拟器的接口使用不正确时，模拟程 序产生许多让用户头痛的b u g s 和e r r o r s ，以至于用户不得不花大量的时间 去调试修改这些b u g 和e r r o r s 。然而对于某个模拟器的所有使用者来说， 这些过程都是一些重复性的过程。并且这些模拟器大多都不开放源码或不对外 提供使用，这使得一些网格研究者可用的模拟工具受到限制，也不便研究者对 模拟工具进行研究和改进使得其模拟实验更符合自己的要求。在这几种模拟工 具中，本文选择以g r i d s i m 模拟工具为基础，因为g r i d s i m 工具为网格资源调 度算法的研究提供了良好的基础。 1 2 3g r i d s i m 的扩展 为了使模拟更符合用户自己的要求，许多用户对g r i d s i m 进行了扩展f 1 5 】【3 9 1 。 本节介绍以下几个基于g r i d s i m 的扩展软件( 或框架) ： ( 1 ) g r i ds c h e d u l i n gs i m u l a t o r g r i ds c h e d u l i n gs i m u l a t o r ( g s s i m ) 【4 0 】是由波兹南工业大学基于g r i d s i m 开发的。g s s i m 作为一个易使用、易扩展的模拟框架，它易于进行各种调度算 法的模拟实验，并且支持多级调度。g s s i m 的特点是通过模拟真实的网格负载 来模拟计算网格环境。它的目标是使模拟环境尽可能地接近于真实网格系统。 ( 2 ) g r i dn e t w o r kb u f f e r g r i d n e t w o r kb u f f e r ( g n b ) 1 4 1 j 由卡斯帝旱亚拉曼查大学主导以g r i d s i m 为 基础丌发的一个网格元任务调度器。它以网络q o s 作业网格任务调度的目标， 支持网络预留。在g n b 的结构中有资源调度器和输入控制两个部分。 ( 3 ) a i e ag r i ds i m u l a t o r i o 硕士学位论文第一章绪论 a l e ag r i ds i m u l a t o r 4 2 】是由捷克马萨里克大学进行扩展，以g r i d s i m4 1 为 基础。它被用于设计和测试不同网格环境下的复杂调度算法。它可用于动态调 度和静态调度。 ( 4 ) g r i da g e n t sp l a t f o r m g r i da g e n t sp l a t f o r m s ( g a p ) 1 4 3 】由卡塔尼亚大学对g r i d s i m 进行扩展开发。 它主要提供了对计算网格中的移动介质的模拟。g a p 主要包括了 a g e n t p l a t f o r m 、a g e n t s i t e 和a g e n t 这三类。g a p 它模拟了各种a g e n t 在网格中 的移动、a g e n t 之间的通信和a g e n t 与网格资源之间的通信。 ( 5 ) v i s u a lm o d e l e r v i s u a lm o d e l e r ( v m ) 【7 】是由美国墨尔本大学的网格计算和分布式系统实验 室编写的一个基于g r i d s i m 模拟器的g u i 的网格模拟环境建模工具。v m 用一 个简单的j a 、，a 图形界面来生成网格模拟环境构建的g r i d s i m 代码。虽然v m 在一定程度上减少了编程的代码，但是v m 无法模拟用户自定义的调度算法， 对资源属性、网格用户、网格作业以及用户q o s 也无法扩展。 ( 6 ) w e b - b a s e dg r i ds c h e d u l i n gp l a t f o r m w r e b b a s e dg r i ds c h e d u l i n gp l a t f o r m ( w g r i d s p ) 4 4 j 由韩国安东国立大学用 g r i d s i m 工具包研发。使用g r i d s i m 工具包实现了一个基于w e b 的网格模拟调 度平台，支持用户自定义调度算法。它允许用户自己构建资源、测试自己的调 度算法性能。它隐藏了使用g r i d s i m 进行网格模拟时的烦琐细节。 1 3 研究意义 g r i d s i m 工具可以建立完整的网格系统模型，同时也简化了模型的某些环 节，因此在网格调度模拟开发时可能需要对g r i d s i m 工具进行扩展或改进。 g r i d s i m 在模拟网格环境时需要用户编写代码调用a p i ，不像s i m g r i d 模拟器只 需要通过x m l 文件进行配置然后调用a p i 载入相应的数据即可。在做模拟时 用户最需要了解的就是模拟的网格资源数目和能力，还有资源的负载以及模拟 的网格用户数目和用户的作业参数。为了让用户减少对g r i d s i m a p i 熟悉时间， 也为了方便网格研究者模拟自己的算法时提供方便，减少编程量，使研究者更 多的关注于调度算法的模拟1 4 5 1 ，因此对g r i d s i m 模拟环境的搭建进行改进有着 很重要的应用价值。， 同时，网格工作流【4 甜8 1 是解决需要多个组织协同工作的大规模科学计算如