（计算机软件与理论专业论文）基于有色petri网的网格任务调度模型研究.pdf

摘要 任务调度是网格计算中最基本、最关键，也是最具有挑战性的 问题之一，是影响网格计算执行效率的一个关键因素。因此，调度 算法的设计要精益求精。在算法设计过程中，必须通过对算法进行 建模和分析，发现算法中的不足之处，并且对算法进行优化。 本文分析和比较了几种常见的用于网格研究的建模技术。由于 有色p e t r i 网有机地结合了数据结构和层次分解，可用于验证系统的 正确性和评估系统性能，它的并行、并发、资源共享描述特征非常 适合网格资源管理、调度模型和算法的研究。因此，本文使用有色 p e t r i 网作为网格任务调度系统的建模工具。 本文中的c p n 模型充分利用c p n 的分层特性，将调度器的调 度过程和任务在资源上的执行过程进行抽象，因而适用于各种不同 的调度算法和资源类型。 为了验证网格任务调度系统c p n 模型的有效性，本文设计了一 种新的任务调度算法i s u f f e r a g e 。该算法在s u f f e r a g e 算法基础上， 从两个方面进行了改进：( 1 ) 考虑执行开始前输入数据以及执行完 成后输出数据的存取和传输时间对调度决策产生的影响；( 2 ) 在算 法中考虑用户的q o s 要求，在追求最小的任务完成时间的同时兼顾 用户q o s 要求。为了对改进算法进行性能分析和评价，使用有色p e t r i 网对i s u f f e r a g e 算法进行了建模和仿真。结果表明，i s u f f e r a g e 比 s u f f e r a g e 算法更适合于实际的网格环境，能更好的满足用户的q o s 要求。 关键词网格，调度模型，有色p e t r i 网，i s u f f e r a g e ，q o s a b s t r a c t t a s k ss c h e d u l i n gi sak e yf a c t o rt h a ta f f e c t st h ee f f i c i e n c yo fg r i d c o m p u t i n g a sw e l l a so n eo ft h em o s tf u n d a m e n t a la n de s s e n t i a l p r o b l e m st h a tc h a l l e n g eu sm o s t c o n s e q u e n t l y , i tn e e d sm o r ec a u t i o nt o d e s i g ng r i d - s c h e d u l i n ga l g o r i t h m s 。w h e nd e s i g n i n ga na l g o r i t h m ，i t s n e c e s s a r yt om o d e lt h ea l g o r i t h m ，a n a l y z ei t ，a n do p t i m i z ei t s e v e r a lc o m m o nm o d e l i n gt e c h n i q u e su s e di ng r i dr e s e a r c ha r e a n a l y z e da n dc o m p a r e d f o rc o l o r e dp e t r in e t ( c p n ) i n t e g r a t e sd a t a s t r u c t u r ew i t hh i e r a r c h i c a la p p r o a c h ，i tc a nb eu s e df o rt h ev a l i d a t i o n a n dp e r f o r m a n c ee v a l u a t i o no ft h es y s t e m c p nc a nd e s c r i b es u c h c h a r a c t e r i s t i c sa sp a r a l l e l i s m ，c o n c u r r e n c ea n dr e s o u r c es h a r i n g ，s oi ti s v e r y s u i t a b l ef o r g r i d r e s o u r c e m a n a g e m e n t a n dt a s k s s c h e d u l i n g r e s e a r c h t h e r e f o r e ，c p ni sa d o p t e da st h em o d e l i n gt o o lo fg r i d s c h e d u l i n gs y s t e mi nt h i sp a p e r t h ec p nm o d e li nt h i sp a d e rt a k e sf i l l la d v a n t a g e so ft h ec p n s h i e r a r c h i c a lf e a t u r e ，a b s t r a c t i n gt h es c h e d u l i n gp r o c e s so ft h es c h e d u l e r a n dt h ee x e c u t i o no ft a s k so nr e s o u r c e s ，s oa st of i tw i t hd i f f e r e n tt y p e s o fr e s o u r c e sa n ds c h e d u l i n ga l g o r i t h m s t op r o v et h ee f f e c t i v e n e s so ft h ec p nm o d e l ，an e ws c h e d u l i n g a l g o r i s mi s u f f e r a g eb a s e do ns u f f e r a g ei sd e s i g n e d ，w h i c hi n c l u d e st w o e n h a n c e m e n t s ：i t ( 1 ) c o n s i d e r st h ei n f l u e n c eo ft h et i m eu s e dt oa c c e s s a n dt r a n s f e rt h ei n p u t o u t p u td a t ab e f o r e a f t e rt h ee x e c u t i o no nt h e d e c i s i o no fs c h e d u l i n g ；a n d ( 2 ) c o n s i d e r st h eq o sr e q u i r e m e n t so fu s e r s w h i l ep u r s u i n gt h em i n i m u mc o m p l e t i o nt i m e ac p nm o d e lo ft h e i s u f f e r a g ea l g o r i t h mi sb u i l t ，t h e ns i m u l a t i o na n dp e r f o r m a n c ea n a l y s i s a r ep e r f o r m e d t h er e s u l ts h o w st h a ti s u f f e r a g ei sm o r es u i t a b l ef o rt h e p r a c t i c eg r i de n v i r o n m e n t ，a n db e a e rt om e e tt h eq o sr e q u i r e m e n t so f u s e r st h a ns u f f e r a g e k e yw o r d s g r i d ，s c h e d u l i n gm o d e l ，c o l o r e dp e t r in e t ，i s u f f e r a g e ， q o s i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：地 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：嗵：堑篁导师签名剑匿唑日期：丝尘年旦月笪日 硕士学位论文第一章绪论 1 1 研究背景 第一章绪论 计算机和网络通信技术1 捌的迅猛发展，i n t e m e t 技术【3 , 4 1 的兴起和广泛应用， 有力地促进了网络环境下的商业应用发展和科学应用研究，当前的应用需求正 朝着高性能、多样性、多功能发展，许多大规模科学计算应用不仅仅需要一台 超高性能的计算机，它需要的更是由多种机器、多个系统合作、多个科学仪器 设备相连的网络虚拟超级计算机。这些应用要求将地理上分布、异构的多种计 算资源通过高速网络连接起来，共同完成计算问题。 广域高性能的网格技术 5 - 8 1 的研究正是在这样的背景中提出来的，它的目标 是将地理和组织上分布、异构的各种高性能计算机、数据服务器、大型检索存 储系统和可视化、虚拟现实系统等，通过高速互连网络连接并集成起来，共同 完成一些缺乏有效研究方法的重大应用研究问题，并实现资源的共享。通过利 用全球网络的庞大计算资源，丰富的开发工具和友好的人机界面，以及各种不 同性能的计算机系统，进行高性能的并行和分布式计算，解决核模拟、生物学、 宇宙学、工程学、材料和环境等重大科学应用领域的计算问题，它不仅对国防 建设具有重要意义，也会对国民经济、各行各业产生重大影响，同时对i n t e m e t 的应用将是一次新的革命。 任务调度【9 】是并行和分布式计算o o , g , 不可少的一部分。在此领域已经有了 广泛的研究，无论在理论上还是实践上都取得了一定的成果。而在网格计算领 域，任务调度仍然是最基本、最关键、也最具有挑战性的问题之一，是影响网 格计算执行效率的一个关键因素。 在网格计算环境下，任务调度主要可以分为两级：高层任务调度和低层任 务调度。高层任务调度是一个广域范围内的任务调度过程，也称为资源匹配， 高层调度的目的是为了完成用户提交的任务和满足用户提出的要求，把网格中 所有可用资源( 计算资源、存储资源和网络资源) 进行匹配，找到最好最合理 的资源匹配方式和资源调度策略；而低层调度是一个为已经到达资源的任务计 算执行次序的问题。目前的研究主要集中在高层的任务调度上。 网格计算中的任务调度与传统的分布式环境下的任务调度有一些相同之 处，它们实际上都是通过多个步骤解决应用程序需求与可用资源之间的匹配问 题，同时保证服务质量。而任务与资源的最佳匹配是一个n p 完全问题，解决 这类问题多用启发式算法。 但是，网格环境下的任务调度面l 临着新的挑战，其调度目标也与过去有很 硕士学位论文 第一章绪论 大的不同。网格环境的异构性、动态性和自治性是设计任务调度策略时必须考 虑的问题。与此同时，从调度目标来讲，任务调度既要增加吞吐量，提高系统 利用率，同时又要满足用户提出的q o s 要求。 目前已有的调度算法中，比较典型的有静态任务调度、应用程序级的适应 性调度、基于资源预测的调度以及基于经济模型和理论的调度。对于相互间存 在通信的任务组的调度，存在的启发式算法有：遗传算法、模拟退火、演化方 法、随机化、搜索、分支定界等 1 0 q 3 。对于相互独立的任务的映射，动态的在 线方式有：最小完成时间启发式、最小执行时间启发式、交换算法、机会负载 平衡启发式等：批处理方式有：m i n m i n 启发式、m a x m i n 启发式、贪心启发 式、遗传算法、s u f f e r a g e 启发式等等 1 4 - 2 0 】。但是这些启发式算法都不是通用算 法，它们往往在某种资源情况下能取得好的效率，但是在另外一种资源情况下 可能不如另外某种算法；也有的算法调度的效果很好，但是算法复杂。因此， 对网格任务调度的研究还是有待继续。 在进行网格任务调度研究的过程中，必须认识到任务调度是网格计算的重 要环节，调度算法的效率对于整个系统的效率有着重大影响。因此，调度算法 的设计更应该精益求精。为了设计出高效的调度算法，需要对网格环境有深入 的理解，综合考虑各种因素，从而提出初步的调度算法。然后，还应该对所提 出的调度算法进行模拟和评测，分析其优缺点，并进一步对算法做出改进。因 此，对系统和算法的形式化描述、正确性检验、性能评价、测试等都是十分重 要和必要的。 1 2 网格任务调度建模的研究现状 常规的性能评测方法通常都是在真实的系统中进行测试，但是目前网格技 术的发展现状决定了这种测试只能在小规模的真实网格环境下进行。既便如此， 仍然有很多研究者无法获得这样的条件。网格模拟器的出现，给研究者带来了 新的希望。模拟器的作用是模拟一个网格环境，我们在这个模拟的环境中研究 不同的问题，比如可行性和性能问题。通过配置参数，可以更加真实的模拟出 现实环境中的各种应用场景，使得模拟结果更具真实性；通过分析在模拟器上 试验的结果，网格研究者可以不断的改进设计。 网格模拟器在对任务调度算法的可行性和性能的评测上的确能发挥一定的 作用，可以作为网格任务调度研究的辅助工具。然而，对于一个新设计出来的 调度算法，我们不但关心它的性能，同时还需要洞察更深层的一些特性。例如 一个算法可能在某些情况下性能很好，而在其他一些情况下则性能不佳。那么 就需要分析其背后的原因，并试图找出解决的办法。如果使用网格模拟器进行 硕士学位论文 第一章绪论 测试，则难于跟踪算法的执行过程，也难于发现问题的根源。另外，由于网格 模拟器不能用图形化的界面表示任务调度的执行过程，因此不便于对系统和算 法的理解。 p e t r i 网【2 ”可以弥补网格模拟器这些方面的不足。p e t r i 网是分析和规范并发 的动态离散系统的正式的、可视化的、可执行的建模技术标准。p e t r i 网是一种 图形化的建模工具，它能较好地描述离散事件的动态过程，并能精确描述事件 的顺序、并发和冲突关系。p e t r i 网是基于严格的数学理论的，它的很多静态和 动态属性都可以通过数学方法证明。p e t r i 网以图形方式描述系统，使系统形象 化，有利于理解；可分层建立p e t r i 网，适合于递阶结构的系统；它既可描述系 统内部数据流，又可描述系统外部数据流：采用变迁方式，可描述系统内部的 并发性、冲突现象。 p e t r i 网在自动控制、计算机应用、软件工程等领域得到了广泛的应用，其 理论和相应的计算机工具都臻成熟。然而，对于复杂系统而言，用传统p e t r i 网建立的模型将会是一个节点很多、规模非常大的模型，这使得对于大系统的 建模变得非常复杂，而且对模型的特性分析也非常困难。为了弥补传统p e t r i 网的缺陷，各种扩展的p e t r i 网相继出现，其中比较有影响的有时间p e t r i 网 ( t p n ) 、模糊p e t r i 网( f p n ) 、随机p e t r i 网( s p n ) 和有色p e t r i 网( c p n ) 等，其中常用于网格计算研究的有随机p e t r i 网和有色p e t r i 网。 对于p e t r i 网在网格任务调度领域的应用，国内外已经做了一些研究。这些 研究一般是使用p e t r i 网对调度过程或应用模型进行建模，然后借助p e t r i 网的 分析方法对模型的正确性、性能等特性进行分析。例如文献 2 2 币1 j 用随机p e t r i 网对容错网格作业调度进行了建模，并通过专业软件包s p n p 进行求解，从而 分析故障对网格中不同类别作业的影响。文献 2 3 中提出一种扩展的高级时间 p e t r i 网，并用这种p e t r i 网为网格计算中的任务调度构造了一个简单的模型， 然后通过可达图的分析方法对任务调度过程的时间特征进行分析。文献【2 4 对 o g s a 体系结构进行了扩展，提出了网格用户应用的价格时问p e m 网模型，用 于描述网格环境下用户应用的q o s 需求，并给出了模型正确性和可达性的分析 方法，为进一步研究网格资源管理和任务调度提供了基础。 然而，这些研究都是针对网格研究的某个方面的，而且所建立的模型没有 同时考虑网格级的调度和本地级的调度，而是单独考虑其中的某一级，因而缺 乏可扩展性。有色p e t r i 网拥有强大的描述能力以及各种优点，同时具有分层的 特性，因此采用有色p e t r i 网为网格任务调度建立分层的、可扩展的模型，可以 为调度算法的设计提供有力的帮助，对调度算法的研究具有重要意义。 硕士学位论文 第一章绪论 1 3 研究内容和研究意义 1 3 1 研究内容 网格计算涉及多种关键技术，仅网格任务调度方面就有任务管理、资源发 现、资源筛选、调度算法等等很多方面需要研究。因此本文主要针对网格任务 调度方面的研究中所存在的部分问题，从以下几个方面展开研究： ( 1 ) 分析网格任务调度系统的结构，应用有色p e t r i 网建立网格任务调度系 统的c p n 模型。 ( 2 ) 把握网格环境下任务和资源的特征，分析目前已有的一些启发式调度算 法，提出一种改进的调度算法。 ( 3 ) 为新设计的调度算法建立c p n 模型，利用有色p e t r i 网的分析功能，对 算法的性能进行分析。 1 3 2 研究意义 ( 1 ) 在设计调度算法时，必须对网格环境、任务和资源的特征等关键因素有 清楚的认识。然而，目前网格研究仍处于一个不太成熟的阶段，虽然出了不少 研究成果，但是往往难于对这些研究成果进行分析和评价。本文利用有色p e t f i 网为网格任务调度系统建立一个c p n 模型，该c p n 模型充分利用c p n 的分层 特性，将调度器的调度过程和任务在资源上的执行过程进行抽象，因而适用于 各种不同的调度算法和资源类型。通过建立网格任务调度系统的c p n 网模型， 可以增进对网格任务调度系统的理解，并且对网格任务调度进行仿真和状态空 间分析，以发现调度算法的优缺点，为算法的改进和性能评价提供支持。 ( 2 ) 目前存在多种启发式算法，如m i n m i n 、m a x m i n 、g a 、a + 和s u f i e r a g e 、 b e n e f i t 等。实验表明，g a 和a + 运行速度比较慢，不能适应大规模的网格计算 环境，m i n m i n h 和m a x m i n 的负载均衡性能不高，s u f f e r a g e 具有较好的综合 性能。但是，现有的s u f f e r a g e 算法有两个不足之处：首先，在计算任务完成时 间时，s u f f e r a g e 仅仅考虑了执行时间，忽略了任务执行开始前输入数据以及执 行完成后输出数据的存取和传输时间；另外，网格计算系统中一个关键的问题 是尽可能保证用户的q o s 要求【25 1 。s u f f e r a g e 启发式算法的调度目标是一味追 求最小的m a k e s p a n ，没有考虑任务q o s 要求，会造成过多的任务达不到q o s 要求而被抛弃。本文在s u f f e r a g e 基础上提出一种改进的启发式算法 i s u f f e r g a g e ( i m p r o v e ds u f f e r a g e ) ，一定程度上改善了s u f f e r a g e 算法的以上两个 不足之处。 硕士学位论文 第一章绪论 1 4 论文组织 本文的主要内容是设计一种改进的网格任务调度算法，并使用有色p e t r i 网为网格任务调度系统建立一个c p n 模型。此外还为新设计的调度算法建立 c p n 模型，代入网格任务调度系统的c p n 模型中，然后对新的调度算法进行 仿真和性能评测。 第一章是绪论，主要介绍了本论文的研究背景，当前的研究现状，论文的 研究内容和意义以及章节结构。 第二章对网格任务调度作了简介，然后谈到网格任务调度研究的四个方面： 静态任务调度、应用层调度、资源可用性预测和分散任务调度系统的经济方法。 第三章介绍了网格模拟器和p e t r i 网在网格任务调度研究中的应用，分析和 比较了几种常见网格模拟器和高级p e t r i 网的特点，最后确定了用于网格任务调 度建模的工具。 第四章使用有色p e t r i 网为网格任务调度系统建立了c p n 模型，并基于该 模型对两种经典的调度算法m i n m i n 和m a x m i n 进行了状态空间分析。 第五章分析了网格环境中任务调度机制和已有的启发式调度算法 s u f f e r a g e ，提出一种改进的任务调度算法i s u f f e r a g e 。 第六章为i s u f f e r a g e 算法建立了c p n 模型，并对其进行了仿真和分析。 第七章总结了全文，并对文章的后续研究进行了展望。 硕士学位论文 第二章网格任务调度 2 1 简介 第二章网格任务调度 由于网格的复杂性，网格资源的动态性，网格计算环境下任务的调度是n p 完全问题。因此目前针对任务调度的算法都是为了尽可能提高资源的利用率，缩 短系统的响应时间或缩短任务的执行时间而提出的。任务调度中的主要难点有： 网格中的资源是动态变化的，随着时间的变化，总是有旧的资源推出和新的资源 加入；由于资源之间的关联性，进入网格中的任务会和其他已经在网格中的任务 竞争资源，造成任务之间的相互影响，要同时找到满足所有任务要求的最优调度 方案，有时是不大可能的；网格中的资源种类繁多，各种任务对资源的要求也是 各种各样，很难用统一的尺度描述和度量其特征。 任务调度是任务系统( t s ，t a ) 到资源系统( r s ，r a ) 的一个映射m a p ： ( t s ，1 a ) 一 ( r s ，r a ) 。其中任务系统包含一组任务，t a 表示任务之间的 关联。资源系统r s 是一组资源，r a 表示资源间的互联结构。任务调度的目的 是找到好的映射函数使某些性能指标最优，这里有四个组件t s 、t a 、r s 和r a ， 这四个组件不同，映射算法就有很大的不同。 这类映射问题是n p 完全问题，能取得最优分配的算法只是在极严格的限制 条件下才能获得，这仅是很少的情况。一般的任务调度算法常以数学的方法和程 序模块相关图的方法寻求任务的最佳匹配或负载的高度平衡，大部分是采用启发 式方法来求得次优解 2 6 , 2 7 ，目前，研究主要集中在自适应的动态分配算法和基于 人工智能的启发式算法等，但有些算法需要特殊硬件支持，有些需要用户修改应 用程序以获得必要的信息。映射问题又可以分为静态解决方法和动态解决方法， 静态方法是在编译阶段和任务提交前完成分配问题，而动态方法是在任务提交后 进行分配和调度，它可以借助于系统的实时动态信息。静态方法有两个前提：一 是任务和任务执行环境等各种必要的信息在执行前是预知的或可估计的：二是任 务和任务执行环境在任务执行后的情况也是可以预知或可以预测的，这种方法的 特点效率高，是开销小，不需要收集存储当前资源的状态信息，常用在某些特定 的系统，但实际上先验知识难以确定或可能在确定时出现错误，另外静态方法只 能在任务执行前做出分配决定而不考虑系统当时状况，有相当的盲目性。动态方 法在运行时可以对分配方案进行调整，但是也增加了额外开销。因此以静态方法 为基础的静态和动态结合的方法在网格任务调度中是一种较好的方法。 硕士学位论文第二章网格任务调度 2 2 网格任务调度模式 在网格任务的调度中，网格任务调度模式的研究是基础。在此，从调度组织 模式、状态估计和调度策略三个方面对网格任务调度模式进行讨论。 2 2 1 调度组织模式 网格环境下的资源调度技术主要可以分为以下几类：基于“超级调度者”的 方法、基于市场的方法、基于发现的方法、以及由这几种方法组合的混合技术。 在基于“超级调度者”的方法中，网格环境下存在分层的多个调度器，它们 互相协作执行资源管理。层次较高的资源控制者调度较大的单元，而较低层次的 资源控制者调度较小的单元，逻辑上来说每层只有一个请求和任务队列。一个单 层的控制者模式和一个集中的控制模式其实是相同的。在一个完全分布的方法中 不存在专门的资源控制器，资源请求者和资源提供者直接确定资源的分配和调 度，一般不会存在多个不同的请求和任务队列。该方法难以处理站点自治以及存 在许多不同管理域和调度器的系统。更困难的问题是由不同调度器调度的资源的 协作配置( c o a l l o c a t i o n ) 。由于诸如分布式的交互仿真类的应用为了达到要求的 服务质量，要求多个资源的协作配置，协作配置式网格环境下的一个重要问题。 解决此类问题是层次调度未来的进一步研究方向之一。 对于基于市场的方法，资源管理使用源于人类经济的原则执行。使用较多的 技术是拍卖和多商品市场。在一个诸如网格的广域系统中，有可能必须充分使用 分布式的拍卖机制来提供容错和可扩展性。使用这种技术的主要研究在于价格管 理和资源的协作配置。 资源发现技术是在一个分布式的数据库中维持资源属性和状态信息。这种方 法之间的不同点在于它们更新、组织、或者维护分布式数据库的方法。广泛使用 的g l o b u s 工具集使用一个集中式的发现算法的变种来寻找对于一个请求来说最 合适的资源。该方面的挑战式设计容错和可扩展的高度分布式的发现技术。 混合技术使用一个双层机制。混合可以结合多重技术实现可扩展和容错的方 法。例如，网格可以在自治的管理域问使用一个分层的调度和在每一领域内使用 发现技术。采用哪些方案的组合是我们需要进一步研究的内容。 2 2 2 状态估计 用户提交的任务通常具有如执行期限之类的q o s 需求。因此管理系统需要 估计在具体资源上运行任务的运行时间。状态估计的方法有三种：基于理论的预 测、基于历史的预测和基于测试用例的预测方法。 ( 1 ) 基于理论的预测方法：基于对应用任务的程序模型和问题规模的分析， 硕士学位论文 第二章网格任务调度 对应用需求进行分析。 ( 2 ) 基于历史的预测方法：基于对应用任务以前运行的结果的分析进行预测。 ( 3 ) 基于测试用例的预测方法：在具有代表性的机器上运行一组用例，通过 对测试用例运行结果的分析进行预测。 2 2 3 调度策略 网格环境下的任务调度可以分为相互间存在通信的任务组的调度和相互独 立的任务组( m e t a t a s k ) 的调度两类。对于相互间存在通信的任务的调度，最常 用的方法是沿用传统的d a g 图调度，即将相互间存在数据依赖的任务组当作一 个有向无环图，根据这个有向无环图做出调度决策。但是对于大规模、多管理域 的网格系统，d a g 图调度方式执行可能由相当的困难，实际上经常采用预留和 合作配置的方法来保证任务的执行。 m e t a t a s k 调度根据调度的频度可分为批调度以及事件驱动的联机在线调度。 批调度方法将资源请求和系统时间分成组，间歇地处里它们。调度的间隔可以是 周期性的或者可能被一定的系统事件触发，关键在于任务调度是成批处理而不是 对单个请求或者事件，事件驱动的联机调度在r m s 收到资源请求或者发生系统 事件时执行调度。批调度潜在地能够更有效地利用网格资源，因为更多地请求能 够被综合考虑。 大多数的调度策略是面向系统的。面向系统的调度策略以最大化系统吞吐率 为调度目标：而面向应用的调度策略则尽力优化某些特定的参数如应用的完成时 间。 2 3 网格任务调度研究的重点 网格任务调度在本质上就比局部调度复杂。因为网格任务调度要面向跨管理 域的大范围的资源，而且在网格这样的动态分布式计算环境，资源可用性变化常 常出乎意料，所以网格环境中的调度很有难度。目前，对网格任务调度的研究主 要集中在四个方面：静态任务调度、应用层调度、资源可用性预测和分散任务调 度系统的经济方法。 2 3 1 静态任务调度 静态任务调度就是对于一组任务和资源，在任务运行前给出调度结果。在静 态调度中，资源情况和性能参数是假定已知的。基于任务是怎么分解的，当前对 静态任务调度的研究又可以划分为两类：任务量可分解的调度和大小固定相互不 依赖的任务调度。 硕士学位论文 第二章网格任务调度 任务量可分解调度是基于负载可分解理论( d l t ) 1 2 8 ) 的。任务量可分解调度 的目标是寻找任务分解的最佳方法使任务的总执行时间( m a k e s p a n ) 最小，其实 质是利用通信与计算在时间上的重叠，尽量缩短机器的空闲时间。实际上，任务 量可分解模式在很多应用领域都有应用，如图像处理、科学计算和数据挖掘等领 域。 对于一组可用的资源和一组不相关的任务，不相关的任务调度的目的是寻找 任务的最佳资源匹配，从而使这一组任务的总执行时间最短。寻找最优匹配的问 题实际上是一个组合最优问题，也是一个n p 一难问题。常用的方法是使用启发式 搜索程序寻找一个近似最优解。目前多数在这个领域的研究是理论研究，因为即 使是启发式搜索，由于其搜索空间太大也会代价昂贵。在网格中，由于存在大量 的任务和资源，所以需要一个实用而有效的启发式搜索算法。 在不相关的一组任务调度的领域，有几种启发式算法是常用的： ( 1 ) o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g ) ：随机负载平衡是最简单的策略，它 将任务直接分配到下一个可用的机器上去，而不考虑任务在那台机器上的预期执 行时间。 ( 2 ) m c t ( m i n i m u me x e c u t i o nt i m e ) ：和上一策略相反，它只考虑任务在机 器上的预期执行时间，每次选择个具有最短执行时间的机器分配给任务。 ( 3 ) m i n m i n ：m i n m i n 2 9 1 启发式方法是两步式调度方法。首先，为每一个任 务寻找最优( 具有最短完成时间) 的机器；然后，从所有任务中选择一个具有最 短完成时间的任务去执行。m i n m i n 的基本思想是把任务放到可用时间最早而且 执行速度最快的机器上去执行。 ( 4 ) m a x m i n ：m a x m i n 启发式方法也是两步式的。第一步和m i n - m i n 相同， 在第二步中则是从所有任务中选择一个具有最长完成时间的任务去执行。这种方 法在任务的完成时间之问相差悬殊时是有效的，采用这种启发式方法，完成时间 长的任务被先调度到最优可用机器上去和其它任务并行执行。这样可以获得更好 的负责平衡和更短的总执行时间。 ( 5 ) g a ：遗传算法是应用在大空间搜索的进化方法。一般的g a 搜索过程分 为三步：a ) 产生人口人口是一组染色体，每一条染色体描述了一种可能的解决 方案，也就是任务和机器之间的一个映射次序，在这一步，产生一定数量的染色 体；b ) 染色体评价每一条染色体被赋以一个适当的权值，权值就是这一条染色 体所描述的任务一机器任务所对应的总完成时间；c ) 遗传和变异在这一步中， 基于一定的挑选规则挑选染色体，挑选规则类似于进化规则。遗传是将挑选出来 的染色体互换某些序列；变异是针对新的任务映射的新情况替换某些染色体的序 列。遗传和变异以后，新代的人口产生了，然后重复b ) 和c ) 直到达到了停止 硕士学位论文 第二章网格任务调度 标准( s t o p p i n gc r i t e r i a ) 。 ( 6 ) s a ( s i m u l a t e da n n e a l i n g ) ：模拟退火算法是基于退火物理过程( 也就是 低能晶体状固体的热量获得过程) 的搜索方法。固体融化时会升高温度，如果温 度是慢慢升高的，融化了的固体其颗粒会在局部排列，处于一个“稳定”的状态， 而固体处于热量平衡状态，这是一个最佳状态。类似地，热量平衡是最优的任务 一机器映射，温度是映射的总完成时间，温度的变化的过程就是映射变化的过程。 如果下一个温度更高，那么就是一个更差的映射，下一个状态被接受的概率服从 指数分布。接受一个“坏”的状态可能局部不是最优但是从全局考虑却是较优的。 2 3 2 应用层调度 应用层调度研究的是不同的应用需求对调度的影响，以及如何采用基于实时 资源情况的调度机制，其思想是将资源可用性的动态信息反馈给应用任务，这样 应用任务就可以决定划分的子任务的大小。 应用层调度的作用表现在两个方面： ( 1 ) 如果资源的动态可用性信息是可知的，那么应用任务可以动态地分解并 产生一个调度序列来获得更好的总执行性能。 ( 2 ) 迭代和松散耦合的并行任务，如果先前任务执行情况信息可知，那么应 用可以对当前的任务调整调度策略。 2 3 3 基于预测的方法 网格应用最常使用的资源是计算、数据和网格资源。对于网格资源，我们可 以很容易地获得机器的静态资源信息，如c p u 的频率、内存的大小、网络的带 宽和文件系统的类型等。但是资源的实时信息，如c p u 负载、可用内存的大小 和可用的网络带宽等信息却难以准确地获得。因此在做调度决策时，能否准确地 预测资源的可用情况对网格应用的效率至关重要。在预测时，是基于先前资源可 用情况信息和任务执行情况的信息进行分析的，在这一过程中，可以应用不同的 静态预测技术。 基于是否建立性能模型，任务的预期执行时间的预测方法分为两类。如果没 有建立性能模型，可以依据经验对数据进行分析，首先寻找类似应用任务执行时 间的记录，然后计算先前这些类似任务的平均执行时间，把这个时间作为当前应 用任务的估计执行时间。如果为应用任务建立了性能模型，我们就能预测实时资 源情况。 在当前的网格任务调度研究中，大多数调度器从n m s ( n e t w o r kw e a t h e r s e r v i c e ) 获得资源预测参数。n m s 是在网格中配置的代理系统，专门周期性地 1 0 硕士学位论文 第二章网格任务调度 监测资源和任务执行情况。通常，n m s 每十秒取样次。 2 3 4 基于经济的调度 网格的大范围分布式系统的特性使得其调度策略和算法很复杂，但是无论如 何，调度本身地成本必须合理。当我们把网格看作一个分散的系统时，我们也可 以考虑在调度时也分散地进行。在分散调度中，市场经济理论是适用的，因为在 本质上市场也是一个竞争资源的分散的动态系统。在市场中，价格是操作中唯一 考虑的因素。如果生产者( 资源) 和消费者( 应用任务) 之间的价格策略已定， 在调度过程中使用价格可以大大降低通信代价。当前面向市场的程序模型是基于 平衡理论的，只要给出一些假设，平衡理论可以转化为最优化问题，而最优化问 题是调度中所需要解决的。平衡理论能保证全局均衡的优点使它成为寻找资源调 度最佳方案的可行途径。 市场的基本要素有生产者、消费者和商品，类似地，网格计算系统的基本组 成成分有资源所有者、资源使用者和各种计算资源。经济理论是建立在对市场行 为的研究之上的1 3 0 j 。 2 4 本章小结 本章首先对网格任务调度进行了简介。然后论述了网格任务调度模式的研 究，并分析了网格任务调度研究中的几个主要方面，包括静态任务调度、应用层 调度、基于预测的方法和基于经济的调度，另外还着重分析了静态任务调度策略 中针对不相关任务的几种启发式调度算法。为后面选择网格任务调度的建模方案 和建立网格任务调度模型打下了基础。 硕士学位论文第三章网格任务调度建模的技术方案 第三章网格任务调度建模的技术方案 3 1 需求分析 根据第二章对网格任务调度的分析，可以基本确定为网格任务调度系统建模 时，所建立的模型应该满足以下需求： ( 1 ) 具有通用性，能适合不同类型的资源。 网格环境具有异构性。网格环境下的资源并不是单一类型的，即使是同一种 类型的资源，其计算能力也存在差异；而且对于某种q o s 要求，有些资源可以 满足，有些资源不能满足。此外，不同资源的本地调度策略和资源预留策略也不 尽相同。例如，有些资源在本地采用先进先出的调度策略，有些资源在本地又采 用最短任务优先的策略。因此，如何反映网格资源的这种异构性，是为网格任务 调度系统建模时要着重考虑的问题。 ( 2 ) 具有可伸缩性，能反映网格环境的动态变化。 网格环境具有动态性。网格环境是动态变化的，不时有新的资源加入，也有 资源退出。而且，网格环境中资源本身的状态是不断变化的。在调度不同的任务 时，所面临的可用资源的类型和数量也是不同的。因此，如何反映网格资源的这 种动态性，是为网格系统建模时要特别考虑的问题。 ( 3 ) 具有层次结构，能反映网格环境的自相似性。 网格环境具有自相似性。和计算机网络类似，网格也是由很多自治的局部网 格通过互连形成的。整个网格任务调度系统可分为网格任务调度器和站点上的本 地调度器这两级。因此，采用分层抽象的方法为网格系统建模是十分有必要的。 “) 应该可以进行一定的分析和验证。 在设计出一种新的调度算法之后，需要对算法的有效性进行分析和验证，还 要对算法的性能进行评测。因此，所建立的模型最好是图形化的，以便于增进对 网格环境和调度算法的执行过程的理解。同时，所采用的建模技术应具有形式化 描述和分析的能力，以便对调度算法进行严谨的形式化分析和验证。最后，所建 立的模型应该是可执行的，以便对调度算法的执行过程进行仿真和性能分析。 3 2 选择建模技术 常规的性能评测方法通常都是在真实的系统中进行测试。在多样化和异构的 网格环境中，随着资源和相关策略的动态变化，观察、比较和分析性能要比普通 的分布式系统复杂得多，而且具有很大的局限性。这不仅是因为需要的资源可能 无法满足，还因为要在分布式异构环境下重复应用执行过程几乎是不可能做到 硕士学位论文第三章网格任务调度建模的技术方案 的。所以，由于网格系统本质上的不可重复性，导致了没有办法完全控制所有可 用的资源和任务。此外，目前的实验网格通常规模较小，并不能完全反映真实网 格系统中的某些行为特性。因此，很多研究常常以网格模拟器作为评价网格各方 面性能的重要工具。一个好的模拟系统允许研究者有更多的使用配置空间，能够 被用来对多种不同的系统模型和应用模型进行模拟，并且能得到准确有效的统计 分析结果。此外，由于p e t r i 网能很好地描述并行、并发、共享等特性，因此也 非常适合于网格研究。本节将分析网格模拟器和p e t r i 网这两种不同的建模技术 的优缺点，为本文的研究寻找一种合适的建模技术。 3 2 1 网格模拟器的适用性分析 目前已有多种用于网格研究的仿真工具( 也常常被称作网格模拟器) ，例如 b r i c k s 3 1 1 、m i c r o g r i d 32 1 、s i m g r i d 3 3 】、g r i d s i m l 3 4 1 、c h i c s i m 3 5 1 、g r i d n e t l 3 6 1 和 o p t o r s i m 【3 7 】，其中影响较大的有s i n i g r i d 、g r i d s i m 、m i c r o g r i d 等。下面就对这 三种常用的网格模拟器进行分析，看看它们是否适合对网格任务调度进行建模和 分析。 3 2 1 1s i m g r i d s i m g r i d 是用c 实现的，提供了一系列核心函数，用以建立异构分布环境下 分布应用的仿真环境。资源由名称、一组有关性能的参数和一些跟踪值来表示， 任务则由名称、代价和状态表示。s i m g r i d 使用基于t r a c e d r i v e n 的模拟，它按照 真实的网格资源中的访问t r a c e 记录来模拟网格资源，从而达到更真实的网格模 拟。s i m g r i d 该项目的主要目标是为在分布计算环境下进行分布并行应用调度研 究提供一个仿真环境，这里的分布计算环境可以是简单的工作站组成的网络，也 可以是复杂的计算网格。 s i m g r i d 的优点主要有两点：一是可以使用复杂的和实际情况相符的平台， 二是可以进行快速仿真。但是，在s i m g r i d 中，资源( 例如c p u 和网络连接) 被看作是不相关的，所以不存在资源互连的拓扑结构。此外，s i m g r i d 没有区分 计算和数据传输。两者都被看作任务，用户必须确保使计算任务被调度到处理器 上，而文件传输任务被调度到网络连接上。 3 2 1 2g r i d s i m g r i d s i m 是一个在w i n d o w s 和l i n u x 的平台上都可以运行的网格模拟器。这 个模拟器是用j a v a 编写的，所以具有跨平台特性。g r i d s i m 为模拟不同类型的异 构资源、用户、应用程序、资源中介和调度器提供了全面的功能。g r i d s i m 可以 进行网格任务调度算法的模拟，可以通过提供的j a v a 方法来编写模拟文件，从 而完成模拟的过程。 硕士学位论文 第三章网格任务调度建模的技术方案 g r i d s i m 的主要特性包括： ( 1 ) 可以对不同类型资源建模。 ( 2 ) 资源可以是空间共享或时间共享模式的。 ( 3 ) 资源的能力以s p e c ( 标准性能评估公司) 基准定义。 ( 4 ) 资源可以预留。 ( 5 ) 支持对静态调度器和动态调度器的仿真。 ( 6 ) 任务可以是不同类型的，可以是c p u 密集型或i o 密集型。 ( 7 ) 对资源上可以提交的任务数量没有限制。 ( 8 ) 可以记录所有操作或部分操作的统计信息，并可以使用g r i d s i m 的统计 分析方法加以分析。 3 2 1 3m i c r o