(计算机应用技术专业论文)网格模拟器gridsim的研究及应用.pdf_第1页
(计算机应用技术专业论文)网格模拟器gridsim的研究及应用.pdf_第2页
(计算机应用技术专业论文)网格模拟器gridsim的研究及应用.pdf_第3页
(计算机应用技术专业论文)网格模拟器gridsim的研究及应用.pdf_第4页
(计算机应用技术专业论文)网格模拟器gridsim的研究及应用.pdf_第5页
已阅读5页,还剩50页未读 继续免费阅读

(计算机应用技术专业论文)网格模拟器gridsim的研究及应用.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 集群、网格和p 2 p 的出现将成为下一代并行分布式计算平台。人们 对网格的研究越来越感兴趣,但由于网格环境的限制研究者无法对研究 的结果进行评估和测试。因此网格模拟器的出现为人们对网格的研究带 来了很大的方便。本文所提及的模拟器是g r i d s i m 。 为使g r i d s i m 模拟器支持更多性能,本文对g r i d s i m 预留模块进行 了详细分析,提出并实现了在g r i d s i m 中引入优先级的预留策略;为使 系统在一定程度上支持优先级预留调度,提出了相应的系统修改方案。 在优先级预留系统中,对g r i d s i m 预留模块中已有的f c f s ( 先来先服务, f i r s tc o m ef i r s ts e r v e d ) 预留调度算法进行了改进,将优先级与先来 先服务相结合提出了一个新的预留调度算法a r w i t h p r i o r i t y p 0 1 i c y ,该 预留算法对已有的调度算法存在的问题进行了改正,尽可能减少拒绝的 预留请求数目。 在g r i d s i m 模拟工具包的基础上本文提出了g s d p ( g r i ds i m u l a ti o n d e v e l o pp l a t f o r m ) 网格模拟平台,利用j a v a 的接口特性设计并实现了 g s d p 模拟平台。在文中详细介绍了各模块的设计与实现方法,主要包括: 网格资源与文件的映射、网格作业与文件的映射、网格资源选择接口、 网格作业调度接口、网络环境自动构建。本文提出的g s d p 模拟平台可以 方便、快捷地对网格进行模拟,用户不必了解g r i d s i m 的原理,也不需 要编写大量的模拟代码,只需实现相应的接口来完成用户的算法模拟, 为进一步网格模拟技术的研究打下了良好的基础。 本文利用实现的g s d p 对新提出的预留调度算法和g r i d s i m 预留模块 中已有的预留算法进行了模拟比较。实验结果表明,新提出的预留算法 较好地减少了拒绝的预留请求数目。 关键词预留,网格模拟,优先级,g r i d s i m ,g s d p a b s t r a c t t h ee m e r g e n c eo fc l u s t e r , g r i da n dp 2 pw i l lb et h en e x tg e n e r a t i o no f p a r a l l e ld i s t r i b u t e dc o m p u t i n gp l a t f o r m p e o p l eb e c o m em o r ea n dm o r e i n t e r e s t e di nt h eg r i dr e s e a r c h b u td u et ot h eli m i to fg r i de n v i r o n m e n t p e o p l ec a nn o ta p p r a is ea n dt e s tt h er e s e a r c hr e s u l t 1n ea p p e a r a n c eo fg n d -,t s i m u l a t o rh a sb r o u g h tm u c hc o n v e n i e n tf o rt h ep e o p l et ot h eg r i dr e s e a r c h t h es i m u l a t o rm e n t i o n e di nt h i st h e s i si sg r i d s i m i no r d e rt om a k eg r i d s i ms i m u l a t o rs u p p o r tm o r ep e r f o r m a n c e ,t h i s t h e s i sa n a l y s e st h er e s e r v e dm o d e lo fg r i d s i mi nd e t a i l ,a n dp r o p o s e st h a t p r i o r i t yi si n t r o d u c e di n t h er e s e r v e dm o d e lo fg r i d si m s ot h a ta d v a n c e r e s e r v a t i o nc a ns u p p o r tt h ep r i o r i t y i no r d e rt om a k et h es y s t e ms u p p o r tt h e p r i o r i t y , c o r r e s p o n d i n gs y s t e mr e v i s i o ni sp r o p o s e di nt h i st h e s i s ,s ot h a tt h e s y s t e ms u p p o r t ss c h e d u l i n ga d v a n c er e s e r v a t i o n sw i t hp r i o r i t yt ot h ec e r t a i n e x t e n t h a v i n gi n t r o d u c e dt h ep r i o r i t y , t h i st h e s i sm a k e st h ei m p r o v e m e n ti n f i r s t c o m e f i r s t s e r v e ( f c f s ) s c h e d u l i n ga l g o r i t h mi nt h er e s e r v e dm o d e lo f g r i d s i m b yi n t e g r a t i n gt h ep r i o r i t yw i t ht h ef i r s t c o m e f i r s t s e r v e ,an e w s c h e d u l i n gr e s e r v a t i o na l g o r i t h m a r w i t h p r i o r i t y p o l i c yi sp r o p o s e d ,w h i c h c o r r e c t sm i s t a k e so f p r e v i o u sa l g o r i t h m ,a n dr e d u c e sa sf a ra sp o s s i b l e 。 t h i st h e s i sp r o p o s e sg s d p ( g r i ds i m u l a t i o nd e v e l o pp l a t f o r m ) b a s e do n g r i d s i mp a c k a g e id e s i g n e da n di m p l e m e n t e dt h eg s d pb yj a v al a n g u a g e i nt h et h e s i s ,a l lm o d u l e sa r ep r e s e n t e di nd e t a i l t h em a i nm o d u l e sc o n t a i n g r i d - j o b f i l em a p p i n g ,r e s o u r c e - f i l em a p p i n g ,i n t e r f a c eo fg r i ds c h e d u l ea n d a u t o - c o n s t r u c t i n go fg r i de n v i r o n m e n t t h eg s d pc a nc o n v e n i e n t l ys i m u l a t e s g r i de n v i r o n m e n t u s e r sd on o th a v et ou n d e r s t a n dt h ep r i n c i p l eo fg r i d s i m , d on o tn e e dt ow r i t eal a r g en u m b e ro fs i m u l a t i o nc o d e t h e yo n l yi m p l e m e n t c o r r e s p o n d i n gi n t e r f a c et oc o m p l e t et h es i m u l a t i o na l g o r i t h m t h eg s d p b o t t o m sf o rf u r t h e rs t u d yg r i ds i m u l a t i o nt e c h n o l o g y t h i st h e s i sc o m p a r e st h en e w l y p r o p o s e dr e s e r v e dd i s p a t c ha l g o r i t h m w i t hr e s e r v e da l g o r i t h mw h i c ha l r e a d ye x i s t si nt h er e s e r v a t i o nm o d e lo f g r i d s i mb yu s i n gg s dp t h e e x p e r i m e n t a lr e s u l ti n d i c a t e s t h a tt h e n e w l y p r o p o s e ds c h e d u l i n gr e s e r v a t i o na l g o r i t h mf u n c t i o n sb e t t e ri nr e d u c in g t h en u m b e ro fr e j e c t i o n sf o r r e q u e s t i n g r e s e r v a t i o n st h a nt h e p r e v i o u s a l g o r i t h m k e yw o r d sa d v a n c er e s e r v a t i o n ,g r i d s i m u l a t i o n ,p r i o r i t y , g r i d s i m ,g s d p 原创性声明 本人声明,所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知,除了论文中特别加以标注和致谢 的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名:塑竺竺日期:竺l 年二l 月2 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定,即:学校 有权保留学位论文,允许学位论文被查阅和借阅;学校可以公布学位 论文的全部或部分内容,可以采用复印、缩印或其它手段保存学位论 文;学校可根据国家或湖南省有关部门规定送交学位论文。 储繇型聊签趣垫期:4 兰月当 硕士学位论文 第一章绪论 1 1 课题背景 第一章绪论弟一早珀t 匕 随着互联网的飞速发展而发展,在2 0 世纪9 0 年代出现了一种新的技术网 格技术。它利用高速互联网把分布于不同地理位置的计算机、数据库、存储器和软 件等资源连成整体,就像一台超级计算机一样为用户提供一体化的信息服务。其核 心思想是“整个因特网就是一台计算机”n ,1 8 1 。网格技术充分实现了资源共享,具有 成本低、效率高、使用更加方便等优点,现在已成为计算机技术发展的一个热点, 具有很大的发展f j i 景和研究价值。在网格的发展中许多国家都有相关研究,美国开 发了l e g i o n 、g l o b u s 等比较有影响的软件和工具,德国联邦教育和研究部资助的一 个项目u n a c o r e ,r 本正在实施的全球计算基础设施项目n i n f ,韩国开展的n * g r , 中国教育科研网格计划c h i n a g r i d 等。在研究网格技术时大多数个人或团队很难有 真实的网格环境来做研究测试,因此网格的模拟器或仿真工具的出现对研究网格带 来了很大的帮助。 集群、网格和p 2 p 的出现将成为下一代并行分布式计算平台。它们能够共享、 选取、集合适当的计算和数据资源来解决在自然科学、工程学和商业中的大规模数 据处理问题乜6 。在网格和p 2 p 计算环境中,资源被分御在不同的地区被不同的组织、 机构用各种各样的方式管理。在一个大规模的分布式系统中管理和调度资源是相当 复杂的。要用一个好的工具来分析评估这方面的性能是不太可能的。模拟器的出现 使得这些分析能够进行。现在已经出现了一些模拟语言( 如p a r s e c ) 和模拟库( 如 s i m j a v a ) ,但是模拟网格计算环境的工具却不多。 要构建一个网格系统是一个非常复杂的系统工程,它需要考虑许多问题。例如, 资源广域共享带来的异构性、安全性和网络性能问题;网格中有效的资源管理和调 度也将是一个不容忽视的问题;此外,容错能力、可扩展性以及自适应能力都是网 格设计者需要考虑的内容。网格模拟器的出现给网格研究者带来了很大的方便,使 那些不能接触到真实网格环境和只能接触到很小规模的网格环境研究者能够进行网 格研究。研究者可以使用网格模拟器来对自己研究出的调度算法、资源监控等进行 测试、评估。 1 2 研究意义 网格资源大多是在地理上分布的各种资源,在网格环境下,作业的执行需要根 据计算环境的改变在运行期间动态地进行调整。由于网格环境的异构性和动态变化 等特性,网格系统的性能评估也随之变得非常复杂。要在真实的环境中进行测试就 存在很大的局限性,而且大多几乎不可能做到。由于网格系统的不可重复性,导致 硕士学位论文第一章绪论 了没有办法完全控制所有可用的资源和作业。此外,目前的实验网格通常规模较小, 并不能完全反映真实网格系统中的某些行为特性。因此,网格模拟器是一类评价网 格各方面性能的重要工具。一个好的模拟系统允许研究者有更多的使用配置空间, 能够被用来对多种不同的系统模型和应用模型进行模拟,并且能得到比较准确有效 的统计分析结果。 研究员和学生在研究网格计算环境中的资源管理和调度时需要一个可用于测试 的基础设施来实现、测试和评估他们的新调度算法或已有的调度算法乜1 。大多数人没 有现实可用的可测试基础设施,要构建这些设施是非常昂贵和耗时的。即使要实现 一个真实的可测试、可评估和为不同使用和资源模拟的执行调度机制环境是相当难 的。要在可重复的和可比较的方式下进行评估作为资源不同时间变化的有效性是不 可能的,最好的方法就是使用模拟技术来进行评估。因此,对网格模拟的研究是非 常有意义的。 1 3 国内外研究现状 1 3 1g rid sim 简介 1 g ri d s i m 模拟系统简介 g r i d s i m 是一个网格仿真工具包,该工具包是对网格资源管理、调度及并行和分 布式计算的网格环境的模拟。它是一个用j a v a 编写的跨平台的网格模拟器。”。 g r i d s i m 可以进行网格调度算法的模拟,可以通过提供的m e t h o d 来编写模拟文件, 从而完成模拟的过程。它能支持多用户环境的时间或空问共享、单一或多个处理器、 共享或分散内存计算机( 比如p c 、工作站、s m p 、计算机集群) 建模。g r i d s i m 提供 了一些资源和网络的建模和模拟工具,能模拟不同类型的并行和分布式计算基础构 件,比如集群、网格、p 2 p 系统。在集群情况下,所有的资源( 也叫节点) 被模拟在 一个单一的时间区内。节点可是单处理器机器或对称多处理器机器( 使用共享时间 的操作系统和使用高速网络互联) 。在网格情况下,节点分布在不同的时区,可以是 单处理器、s m p s 或集群,通过时间或空间共享资源管理器管理。 g r i d s i m 工具包的主要特征包括以下方面: ( 1 ) 允许不同类型的资源建模。 ( 2 ) 资源可被构建运行在时间或空间上共享的模式下。 ( 3 ) 可以定义资源性能。 ( 4 ) 资源可被定位在任何一个时问区。 ( 5 ) 依靠资源的本地时问周末和假同被映射,从而模拟非网格的工作量。 ( 6 ) 能模拟不同的并行应用程序。 ( 7 ) 请求的作业可以是不同种类的,并且它们可以是c p u 或i 0 。 2 硕士学位论文第一章绪论 ( 8 ) 没有限制提交给一个资源的请求作业的数量。 ( 9 ) 多个用户实体能提交在相同资源( 在时间或空间上共享的) 下同时执行的作 业。 ( 1 0 ) 这些特性可以帮助研究者在构建调度应用程序时使用不同的市场经济模 型。 ( 1 1 ) 明确了资源间的网络速度。 ( 1 2 ) 支持动态和静态调度程序模拟。 ( 1 3 ) 记录所有或经选择的作业统计表,并且能用g r i d s i m 的统计分析方法来分 析这些统计表。 用g r i d s i m 进行模拟应用调度步骤: ( 1 ) 第一,需要创建一个不同性能的网格资源,让这些资源像在不同时区、不同 策略的真实环境中一样。应用时也需要创建一些不同需求的用户。 ( 2 ) 第二,需要通过创建一些g r i d l e t 和定义所有的工作参数来模拟应用程序。 这些g r i d i e t 依靠应用程序模型组织在一起。 ( 3 ) 最后,需要实现资源监控。首先查询网格信息服务( g i s ) ,其次查询资源性 能包括成本,然后再依靠调度安排、网格策略或算法睁2 2 1 分配g r i d l e t 给资源执 行。 2 g r i d s i m 系统结构 ( 1 ) 系统结构 g r i d s i m 用的是层次化和模块化的结构来进行网格模拟。g r i d s i m 模拟平台结构 可分为五层如图1 1 ,第一层是g r i d s i m 的运行环境j v m ( j a v av i r t u a lm a c h i n e , j a v a 虚拟机) 。g r i d s i m 用j a v a 语言来实现的,而且它所使用的库s i m j a v a 也是用 j a v a 实现的,所以整个模拟器必须运行在j v m 上。第二层是g r i d s i m 所使用的基础 库s i m j a v a ,它是一个基本的离散事件组件。其中大部分类都是从t h r e a d 继承过来 的。第三层是建模和模拟网格实体,比如网格资源、信息服、用户等。构建设计用 户接口。第四层是资源监控n 1 和调度应用程序。最后一层用下层提供的服务和接口构 建特定的应程模型。 ( 2 ) s i m d a v a 离散事件模型 s i m j a v a 1 是一个用j a v a 离散事件模拟包。s i m j a v a 的模拟中包含许多实体,这 些实体通过运行自己的线程并行运行。在自己的b o d y0 方法中对一个实体的行为编 码。实体可以访问部分的原始接口,如s i m s h c e d u l e 0 通过端口发送一个对象给其 它的实体;s i m _ h o l d0 暂停一段时间;s i m w a i t0 等待一个事件对象的到达。 s i m j a v a 中使用的是一种连继的离散事件模拟算法。一个核心的对象s i ms y s t e m 硕七学位论文第一章绪论 维持着将来事件的时间序列。最初所有的实体被创建,并且让它们的b o d y0 方法处 于运行状态。当一个实体调用一个模拟函数时,s i m s y s t e m 对象暂停实体线程,并 放置一个事件在将来事件队列中表示处理函数。当所有的实体暂停时s i ms y s t e m 从 队列中弹出下一个事件,因此走动模拟时问,并重新启动实体。就这样连续直到没 有事件产生。 应用程序用户网格特定输入和结呆 虚拟机( j a v a c j v m r m i ) 图1 16 r i d s i m 系统体系结构 ( 3 ) 6 rid si m 实体 g r i d s i m 支持单处理器和多处理器实体、不同种类不同配置的资源系统。允许设 置资源为地理分布的不同时区的。眠们1 。它支持模拟网络实体在资源间的通信。在模拟 时,g r i d s i m l j 建一些多线程实体,这些实体并行运行。g r i d s i m 基本的模拟实体有 用户实体、b r o k e r s 、资源实体、信息服务实体、统计实体、基于i o 的网络实体等。 每一个用户实体代表了一个网格用户。每一个用户不同于其它用户,下面介绍 用户属性: a ) 创建的作业类型,比如作业完成时间,作业参数等; b ) 调度优先策略,比如最小成本、时间或全部; c ) 用户活动速度,如多久创建一个新作业; d ) 用户的时区; 每一个用户连接一个代理实体。用户的每个作业首先提交给代理,代理再根据 4 骂兰璺璺 硕+ 学位论文第一章绪论 用户的调度策略调度作业参数。在调度任前,代理动态的获得可用的资源列表。每 个代理尝试优化用户的策略,因此代理被用于获得资源的竞争。代理使用的调度算 法必须能很好的适应市场的供给和情形的需求。 每个资源实例代表一个网格资源。每个资源与别的资源可能不同。资源属性为 处理器数目、处理器价格、处理器速度、内部调度策略( 如时间共享或空间共享) 、 本地负载因素和资源所在时区。 资源处理速度和作业执行时间能用指令级别标准定义,如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 实体和它们的输入输出实体都是线程实体,它们都有b o d y 0 方法处理 事件。使用独立的实体来进行输入和输出使网络实体模型是双向的,并且多用户间 是并行通行的。缓冲器输入输出通道与每个g r i d s i m 实体联合为实体间通信提供了 一个简单机制。 3 g rid sim 包设计 g r i d s i m 的核心类在包g r i d s i m 中,该包包含的主要类如下: a c c u m u l a t o r :给一个串数据值提供占位符。 a d v a n c e dr e s e r v a t i o n :提供预留操作,如创建、修改、查询、取消。 a l l o c p o l i c y :处理资源分配策略的一个抽象类( 接口) 。所有的资源调度分配 策略都必须继承和实现该类定义的接口。 a r g r i d r e s o u r c e :支持预留功能的资源类,用提供的调度分配策略对象来处理 用户提交的预留操作。 a r o b j e c t :一个预留学生对像,包含有预留的各种属性值。a d v a n c e r e s e r v a ti 创建一个该类的对象并传给一个资源。 a r p o l i c y :支持预留功能的调度分配策略抽象类,在实现一个特定的分配策略 时必要性继承该类。 a r s i m p l e s p a c e s h a r e d :一个特定的资源调度分配方法的类。它支持预留功能。 g r i d i n f o r m a t i o n s e r v i c e :网格信息服务实体类,提供了网格资源的注册、索 引和发现等服务。 g r i d l e t :一个作业的实体类,包含了一个作业的基本信息,如执行所需的处理 器个数、用户i d 、作业长度等信息。 g r i d l e t l i s t :包含一组作业,组织多个作业管理。 g r i d s i m :该类主要功能就是初始化、运行,停止整个模拟系统。 硕十学位论文第一章绪论 g r i d s i m c o r e :该类从s i me n t i t y 继承基本的线程管理和线程特性,提供基本 的同步和异步功能。 g r i d s i m r a n d o m :为g r i d s i m 提供一些随机数据。 g r i d i m s h u t d o w n :在结束模拟系统时终止所有的g r i d s i m 用户实体。 g r i d s i m s t a n d a r d p e :为系统定义标准的m i p s ( m i l l i o ni n s t r u c t i o n sp e r s e c o n d ) 级别。 g r i d s i m t a g s :定义g r i d s i m 操作标志,以便传递信息时识别操作。 g r i d u s e r :g r i d s i m 模拟的用户实体类。 i n p u t :该类继承s i m _ e n t i t y 。它定义了一个段口用于模拟实体接收模拟网络上 的数据。该类维护了一个事件队列来序列化数据输入流,并将数据交付给它的父实 体。它接受来自o u t p u t 实体的消息。 o u t p u t :该类跟i n p u t 实体类似,只是它处理的是输出数据流,并将数据传输 给目的实体。 m a c h i n e :模拟单处理器或共享内存多处理器机器。 p e ( p r o c e s s i n ge l e m e n t ) :模拟处理器,定义处理器能力m i p s 级别。 r e s g r i d l e t :该类记录一个提交给资源的g r i d l e t 的信息,如g r i d l e t 到达的 时间、结束的时间、分配的机器i d 、处理器( p e ) i d 等信息。该类可以追踪g r i d l e t 分配到资源上的处理过程。 r e s o u r c e c h a r a c t e r i s t i c s :描述一个资源的静态属性。如0 s 、机器列表、资源 的调度分配策略等。 1 3 2 其它模拟器介绍 目前几个主流的模拟器有b r i c k s ,m i c r o g r i d ,s i m g r i d ,g r i d s i m ,c h i c s i m , e d g s i m ,g r i d n e t ,o p t o r s i m b r i c k s 口1 由日本t o k y oi n s t i t u t eo ft e c h n o l o g y 研究丌发。它提供了多客户机 和服务器资源分配模拟和一些调度算法的模拟。 m i c r o g r i d 由c o n c u r r e n ts y s t e m sa r c h i t e c t u r eg r o u p ( c s a g ) o fu n i v e r s i t y o fc a l i f o r n i a ,s a nd i e g 领导丌发。它可提供大规模的联机仿真,可以对现实的中 件设备和应用软件创建对应的虚拟网格环境,支持p e e r - t o - p e e r 和分布式应用。但 它的程序模拟必须基于g l o b u s 平台。 s i m g r i d 啤1 是一个提供各种异构的分布式环境模拟的工具包。由u n i v e r s i t yo f h a w a ia tm a n o a 、i dl a b o r a t o r y ( g r e n o b l e ,f r a n c e ) 和u n i v e r s i t yo fn a n c y ( f r a n c e ) 联合开发。目标是为在网格环境下进行分布并行应用调度研究提供一个合 适的模型和抽象并生成准确的模拟结果。s i m g r i d 在一个内核上提供几个编程环境。 它是一个用c 开发的模拟器,运行在l i n u x 平台上。 6 硕士学位论文 第一章绪论 c h i c s i m 由c h i c a g o 大学开发的组件化的、可扩展的离散事件数据网格系统。它 构建在p a r s e c 之上。用c h i c s i m 可实现模拟多种调度和复制算法。 e d g s i m 由e u r o p e a nd a t ag r i d 项目组开发。它基于p t o l e m yi i ,模拟计算工 作流h 6 1 、物理数据和信息。在该模拟系统中,任何状态的改变( 比如作业的产生、 文件开始传输、信息的更新) 都会作为一个有时问信息的事件放入一个队列中,这 些事件被顺序的执行。 g r i d n e t 是由i b mf e ll o w s h i pp r o g r a m 、i b ma l m a d e nr e s e a r c hc e n t e r 和t h e n a t i o n a ls c i e n c ef o u n d a t i o nu n d e rc o n t r a c ti t r 一0 0 8 6 0 4 4 ( g r i p h y n ) 联合支持 开发的。该模拟器是为了评估模拟数据网格中动态的数据复制策略而设计的。它提 供了一个组件化的模拟框架,可以模拟不同数据网格结构和特定资源。 o p t o r s i m 田1 由k u r ts t o c k i n g e r 等人开发的,是一个用j a v a 实现的基于时间的 网格模拟器。它的目的是评估不同优化算法的性能。 国内c g c l 实验室网格性能评估小组在g r i d s i m 基础上,研究开发了网格模拟器 j f r e e s i m 。 1 4 研究内容 1 阅读g r i d s i m 的相关文档和源代码,重点研究分析g r i d s i m 中预留( a d v a n c e r e s e r v a t i o n ,简称a r ) 的模拟实现,并对其不正确和不合理的代码实现进行 修正。 2 在g r i d s i m 中实现的预留调度算法用的是f c f s 方法来调度作业,可以对调 度算法进行改善。在g r i d s i m 的a r 算法中没有考虑a r 的优先级,对g r i d s i m 中的a r 部分引入优先级,研究出先来先服务( f c f s ) 与优先级相结合的预 留调度算法。 3 预留优先级的确定,找出预留属性与优先级的映射关系。 4 编写一个基于g r i d s i m 的模拟框架,使用该框架可以方便、快捷的对网格进 行模拟,用户不必了解g r i d s i m 的原理,也不需要编写大量的模拟代码。 5 编写测试代码,模拟带优先级的调度算法,执行资源预留的分配和调度,对 新的调度算法进行调试、维护和修改。 1 5 编程环境 1 g r i d s i m 选用4 0 版本,在官方网站b 圭主乜;么堕业:g ! i 鱼鱼堕墨:q ! g 么g ! i 鱼墨i 也上 可以下载。 2 开发语言选用j a v a ,版式本为j d k l 6 。 3 编程环境用e c l i p s e3 1 2 。 1 6 论文组织结构 7 硕十学位论文第一章绪论 本文共分为六章。第一章为绪论,介绍了课题的研究背景、研究意义、国内外 在此领域的研究现状以及本文的研究方向和研究内容,对网格模拟器g r i d s i m 作了 简单介绍,对g r i d s i m 模拟系统结构进行了简要分析。第二章对g r i d s i m 预留模块 进行了详细分析,对己存在的算法中的问题进行了测试分析和改正。第三章详细说 明了g r i d s i m 预留模块优先级的引入,并对已存在的算法的问题进行改正同时在已 有算法的基础上提出了优先级与先来先服务相结合的预留调度算法。第四章介绍了 g s d p 的体系结构和g s d p 的设计与实现,详细说明了g s d p 的模拟机制和过程。第五 章对调度算法的测试进行了说明,列出了测试步骤,并且对改进前后的两个调度算 法测试结果进行了比较。第六章为本文最后一章,该章对本文的特点和理论见解进 行了总结,并对未来的工作进行了简要晚明。 8 硕士学位论文第- 二章g r i d s i m 预留模块分析及问题改正 第二章g rid sjm 预留模块分析及问题改正 2 1g rid sim 预留模块分析 2 1 1g rid sim 预留模块简介 预留n 叫是在将来的特定时间里处理用户的资源请求。在非预留调度系统里,用 户提交一个作业是否被执行或什么时候被执行得不到保证。在预留系统里,用户创 建预留成功后提交的作业是能得到保证的。被预留的资源可以是c p u 、内存、磁盘空 间、网络带宽等。g r i d s i m 里的预留资源只是c p u ( p e ) ,而且只有支持预留的资源 ( a r g r i d r e s o u r c e ) 才能处理用户提交的预留请求。 2 1 2 预留状态 一个预留有9 个状态,状态之间的转换就是表示用户的预留操作或预留完成过 程。其状态定义如表2 1 ,预留各状态之间的转换如图2 1 所示。 表2 1 预留状态表 状态说明 r e q u e s t e d 预留的初始状态用户创建预留请求时的状态。 r e j e c t e d预留请求不成功,可能洲为找不剑空预留槽或已有预留完成终止 了。 a c c e p t e d一个新的预留请求被认可。 c o m m it t e d预留在终结前被川户确认提交。 c h a n g er e q u e s t e d在预留开始执行前,用户改变预留请求的条什需求。更改后预留 被重新提交,否则保持原值。 a c t i v e预留的起始时间钊达,开始执行预留。 c a n c e l l e d 川户不再需要预留,取消白己的预留请求。 c o m p l e t e d预留结束时问剑达,一个顶留完成。 t e r m i n a t e d 用户在预留完成前终j 卜预留。 2 1 3g r i d s i m 预留模块包设计 a d v a n c e dr e s e r v a t i o n :该类为一个用户实体类,处理所有预留功能,提供预 留操作,如创建、修改、查询、取消。 a r g r i d r e s o u r c e :支持预留功能的资源类,调用自己内部的私有方法,用提供 的调度分配策略对象来处理用户提交的预留操作。 a r o b j e c t :一个预留对像,包含有预留的各种属性值。a d v a n c e r e s e r v a t i o n 创 建一个该类的对象并传给一个资源。 a r p o l i c y :支持预留功能的调度分配策略抽象类,该类定义了一些处理预留分 配的接口,在实现一个特定的分配策略时必要性继承该类,实现在该类定义的接口。 a r s i m p l e s p a c e s h a r e d :一个特定的资源调度分配方法的类。它支持预留功能, 用先来先服务( f c f s :f i r s tc o m ef i r s ts e r v e ) 调度方法。 9 图2 1 预留状态转换图 图2 2g r i d s i m 预留模块类图 l o 硕士学位论文第二章g r i d s i m 预留模块分析及问题改正 2 2 问题分析 2 2 1 测试条件 为了说明问题,测试只创建一个资源和一个用户,一个用户向该资源提交4 个 预留请求。调度程序为a r s i m p l e s p a c e s h a r e d ( 先来先服务原则) 。 资源如表2 2 : 表2 2 资源属性列表 l 资源名l 系统结构与o sl 指令处理量c p u 数l 价格g $ p ei 时区i r e s o u r c e0s u nu 1t r a ,s o l a r i s 5 1 5m i p s 53 01 0 0g m t 用户提交的预留列表如表2 3 : 表2 3 预留属性列表 预留序号预留起始时间预留持续时间预留c p u 数 0t o = 1 14 8 0 3 3 4 6 2 9 8 31 0 分钟2 l t 1 = t o + 1 2 分钟1 0 分钟l 2 t 2 = t o + 1 3 分钟1 0 分钟 1 3t 3 = t o + 1 1 分钟3 0 分钟3 2 2 2 预期结果分析 用户提交0 号预留,此时资源没有任何预留,提交的预留p e 数符合要求,因此 该预留提交应该成功。 用户提交1 号预留,因跟o 号预留时间上没有冲突,当l 号预留丌始时0 号预 留已经完成,l 号预留所需p e 数为1 资源满足要求,所以1 号预留提交应提交成功。 用户提交2 号预留,2 号预留与0 号预留没有时间冲突,但与1 号预留有时间冲 突,因此必须检查资源是否符合用户需求。2 号预留与此1 号预留冲突情况如图2 3 所示。2 号预留与1 号预留的p e 总数为2 ,资源p e 总数为5 ,资源满足预留需求,2 号预留应该提交成功。 t l t 2 图2 32 号预留提交情况 用户提交3 号预留,3 号预留的时间与1 号、2 号预留都有时间冲突,与0 号预 留没有时间冲突。从图2 4 分析来看,3 号预留与0 号没有冲突,1 号、2 号、3 号 预留的总p e 数为5 ,刚好与资源p e 数相等,因此3 号预留应该提交成功。 图2 43 号预留提交情况 硕十学位论文 第二章g r i d s i m 预留模块分析及问题改止 2 2 3 测试结果 测试结果o 、1 、2 号预留请求被接收,3 号预留被拒绝,返回 a r c r e a t e f a i l r e s o u r c e f u l l _ i n _ 1 5 一m i n s 错误信息。测试结果与预期不符,预留 分配出错。从结果中发现应该被接收的预留被拒绝,原有的预留算法实现上存在问 题。 2 2 4 问题出现原因 在调度程序a r s i m p l e s p a c e s h a r e d 实现中有函数i n tc a l c u l a t e e m p t y s l o t ( i n t b e g i n ,i n te n d ,i n tn u m p e ,l o n gs t a r t t i m e ) 。该函数实现的功能是计算预留链表中 b e g i n 位置到e n d 位置预留的p e 数,再检查资源是否满足当前预留。该函数的执行 流程如图2 5 。 图2 5c a l c u l a t e e m p t y s l o t 流程图 1 2 硕七学位论文第二章g r i d s i m 预留模块分析及问题改正 该函数先将b e g i n 到e n d 段的预留叠加情况用插入排序放入一个数组中,数组 只记录预留在预留链表中的位置,如位置i 的预留,在数组中记录i 表示其预留开 始位置,一i 表示其预留结束位置。如图2 4 所示提交3 号预留时,数组中的记录应 为图2 7 所示内容。此时只有1 号、2 号预留有时间叠加,把l 号、2 号预留p e 数 加起来再加上新请求的预留与资源p e 数对比查看是否符合要求。在源程序代码实现 中,做完插入排序后找时间叠加段时从数组开始循环到第一个负数时结束,也就是 只找了数组最前面的一个时间叠加段。当出现不只一个时间叠加段时后面的检查被 忽略了,因此会导致结果不正确。按其实现代码检测e n d i n d e x 等于2 ,如图2 6 代 码中只计算0 、1 重叠预留的p e 总数。这样2 、3 、4 重叠部分没有计算到,当2 、3 、 4 重叠部分的p e 总数与新请求的预留p e 数总和超过资源p e 总数,新的预留应提交 不成功,但此时没有检测到以至处理新的预留请求时接收新的预留请求。处理图2 4 的预留请求情况时,e n d i n d e x 等于2 。在上述计算p e 总数代码处理中,i 从0 开始 循环2 次,计算第0 和第1 位置的预留p e 总数,但是此时应计算1 、2 号预留p e 总 数,但是代码中却计算到了o 、1 号预留p e 总数,l 、2 号预留p e 总数为2 ,0 、1 号 预留p e 总数为3 ,新提交的3 号预留p e 数为3 ,本应该接收3 号预留请求,因为此 时代码算法计算错误,导致3 号预留请求被拒绝。 1 f o r ( i = 0 :i a r r a y i n d e x :i + + ) 2 i f ( a r r a y i = = o t a i l = = t r u e ) ( 3 e n d i n d e x = i : 4b r e a k : 5 6 i f ( a r r a y i 0 ) 7e n di n d e x = i : 8 b r e a k : 9 1 0 i f ( a r r a y i = = 0 t a i l = = f a l s e ) 1 1t a i l = t r u e : 1 2 ) 1 3 1 4f o r ( i = 0 :i e n d i n d e x :i + + ) 1 5 i f ( a r r a y i = = ( e n d i n d e x 木一1 ) ) 1 6 c o n t i n u e : 1 7) 1 8

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论