（计算机软件与理论专业论文）网格计算中改进minmin算法的研究.pdf

摘要 网格计算是近年来国际上兴起的一种重要网络技术，它可以帮助人们更好地共享 i n t e m e t 上的一切资源，其重要组成部分之一是作业调度。网格具有动态性、分布性、 异构性、多样性等特点，因此其中的作业调度具有一定的复杂性。本文以此为出发点， 对网格计算中的作业调度进行了研究。 作业调度的关键在于调度算法的选取，作为启发式算法中的经典算法，m i n m i n 经 常作为标准对其他算法的性能进行评估，因此本文选取m i n - m i n 算法对网格系统中的 作业调度进行研究。本文主要做了以下三个方面的工作： 1 对m i n m i l l 算法进行了详细的分析和研究，该算法总是优先执行最早完成时间 最小的作业，具有算法思路简单、总执行时间少的优点。但是，由于该算法总是优先调 度短作业，势必造成长作业等待时间过长甚至“饿死 的情况发生。 2 针对这方面的不足，本文提出了d p r i m i n - m i n 算法。该算法引入了作业动态优 先级的概念，它在用户指定的初始优先级的基础之上，加入了动态改变因子，该因子随 着等待时间的增加而增大。d p r i m i n m i i l 将动态优先级与m i n - m i n 相结合，在每个调 度周期开始时，首先计算出所有作业的最早完成时间和动态优先级，然后对两者进行归 一化处理并加权求和，最后根据加权和的大小对作业进行调度。 3 本文采用网格模拟器g r i d s i m 对m i n m i n 和d p r i m i n m i n 进行了模拟，结果表 明d p r i m i n m i n 在长作业平均等待时间方面有了明显的提高，在m a k e s p a n 和负载平衡 方面也有了一定的提高，证明了d p r i m i n - m i n 在长作业调度方面的优越性以及对网格 环境的适应性。 关键词：网格，作业调度，m i n m i n 算法，g r i d s i m a b s t r a c t g r i dc o m p u t i n gi sa l li m p o r t a n tn e t w o r kt e c h n o l o g yi nw o r l di nr e c e n ty e a r s ；i tw i l lh e l p p e o p l es h a r er e s o u r c e si ni n t e m e tb e t t e r ；t a s ks c h e d u l i n gi so n ei m p o r t a n tp a r to fi t g r i di s d y n a m i c ，d i s t r i b u t e d ，h e t e r o g e n e o u sa n dd i v e r s e ，w h i c hm a k e st h et a s ks c h e d u l i n gi ng r i d c o m p u t i n gi sm o r ec o m p l e x t h i sp a p e rs t u d i e st h et a s ks c h e d u l i n gi ng r i dc o m p u t i n gi n t h i s r e s p e c t t h ek e yo ft a s ks c h e d u l i n gi ss c h e d u l i n ga l g o r i t h m ；a sac l a s s i c a lh e u r i s t i ca l g o r i t h m ， m i n m i l li su s e da st h es t a n d a r do fp e r f o r m a n c ee v a l u a t i o nf o rt h eo t h e ra l g o r i t h m s t h e r e f o r et h i sp a p e rs e l e c t sm i n m i na l g o r i t h mt os t u d yt h et a s ks c h e d u l i n gi ng r i d c o m p u t i n g t h ec o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： 1 t h i sp a p e rh a sad e t a i l e da n a l y s i sa n dr e s e a r c ho fm i n - m i na l g o r i t h m ，w h i c hi sf n s t l y e x e c u t i n gt h et a s kw i t hm i n i m u mc o m p l e t i o nt i m e ；i t ss i m p l ea n dh a sl e s se x e c u t i o nt i m e b u tt h i ss t r a t e g yw i l lc a u s et h el o n g e rt a s k sw a i t i n gt o ol o n go re v e n “s t a r v et o d e a t h ， b e c a u s ei ta l w a y ss c h e d u l e ds h o r t e rt a s ke a r l i e r 2 i nt h i sr e s p e c t ，t h i sp a p e rp r o p o s e sd p r i - m i n - m i na l g o r i t h m ，w h i c hi n t r o d u c e s t h e c o n c e p to ft a s kd y n a m i cp r i o r i t y , i t si n i t i a lv a l u ei sa s s i g n e db yu s e ra n di si n c r e a s e da st h e w a i t i n gt i m ei n c r e a s e d p r i m i n m i nc o m b i n e st h ed y n a m i cp r i o r i t ya n dm i n - m i l la l g o r i t h m i nt h e b e g i n n i n go fe v e r ys c h e d u l i n gc y c l ei nd p r i m i n m i n ，a l lt h et a s k s m i n i m u m c o m p l e t i o nt i m ea n dp r i o r i t ya r ec a l c u l a t e d ，a n dt h e nn o r m a l i z e da n dw e i g h t e ds u m m a t i o n ；a t l a s t ，t h e ya r es c h e d u l e da c c o r d i n gt ot h ew e i g h t e ds u m 3 i nt h i sp a p e r , m i n m i na n dd p r i m i i l m i na l g o r i t h ma l es i m u l a t e di nt h eg r i d s i m u l a t o r , g r i d s i m i ts h o w st h a td p r i m i n m i na l g o r i t h mh a sas i g n i f i c a n t l yi m p r o v e di n l o n gt a s ks c h e d u l i n g ，a n dac e r t a i ni m p r o v e di nt h ep e r f o r m a n c eo fm a k e s p a na n dl o a d b a l a n c e ；i tp r o v e st h a td p r i m i n m i na l g o r i t h m ss u p e r i o r i t yi nl o n gt a s ks c h e d u l i n ga n d a d a p t a b i l i t yt og r i d k e yw o r d s ：g r i d ，t a s ks c h e d u l i n g ，m i n m i na l g o r i t h m ，g r i d s i m 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： 垒塾 指导教师签名。瘥鑫壹 钞i 。年易月加日缈年口，月吻锢 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：勺尿礁 仂，口年多月加日 西北大学硕士学位论文 1 1 选题背景和意义 第一章绪论 1 1 1 网格计算的产生和发展 随着计算机和互联网的迅猛发展，基于网络的各种新型技术和产业的兴起，人们对 计算机的需求也朝着多样性、高性能的方向发展。对于一些大型企业和研究机构，特别 是一些需要大量数据计算的研究，不仅仅需要一台超高性能的计算机，还需要由多种机 器组成、多个系统合作、多个科学仪器设备相连的网络虚拟超级计算机【l 】，这样网格计 算【2 】( g r i dc o m p u t i n g ) 技术就应运而生了。 网格的概念最早来源于电网【3 】( e l e c t r i c a lp o w e rg r i d ) ，人们试图实现：计算应用在 使用网格资源时，可以方便的如同各种电器使用电力资源一样，从一个统一的资源池中 获取所需资源。当前我们在使用电力资源时，不必考虑电能从何而来，它是以哪种方式 产生的，水力发电还是核反应发电等，我们使用的是统一的电能。同样，在使用计算资 源时，人们也期望能够方便的“购买这种计算力，而无需考虑它来自哪里，它的产生 方式等问题。网格计算便是实现这种方式的一种途径。在网格计算中，用户无需知道这 个计算网格的位置、组成结构、计算方式等，用户只需将自己的计算任务提交给网格， 然后等待网格输出计算结果即可。 网格计算的推动力来源于高性能计算。而这种高性能计算主要应用于学术界和产业 界。如学术界的高能物理、分子生物、海洋科学、气象分析等领域；产业界的生物技术、 制药行业等。这些领域都需要高性能的计算，因此推动了网格计算的快速发展。网格计 算不同于一般的高性能计算，它具有一些独有的性质： 首先，网格计算打破了传统计算对于地理位置的限制。网格计算没有要求计算资源 必须局限于某个地理位置范围内，因为它可以通过高速的网络将各个计算节点互联起 来，使得所有的计算能力高效地结合起来，如同一个超级计算机。没有了地理位置的限 制，用户就可以把精力集中到提交的任务本身上，而不必担心执行任务的节点位于什么 地方。网格系统对于用户而言是透明的，用户关心的是自己所提交任务能够按照要求顺 利完成，对于如何完成并不是很关心。 其次，网格计算突破了以往的计算能力。由于网格由大量的计算节点互联而成，因 此具有以往难以达到的计算能力，突破了这方面的限制，使得用户可以充分完成自己的 第一章绪论 计算任务。对于大任务，用户也不必自己将其分成多个小任务并提交多次来完成。在网 格计算中，用户只需将自己的任务提交给系统，其余工作都由网格系统来完成。网格最 大的优势就在于它可以把大量的闲置资源结合起来，同时将各个资源的计算能力组合到 一起，形成对外具有超强能力的资源。小范围资源的结合可称之为集群( c l u s t e r ) ，当 大量的集群结合到一起时，便形成了网格。 最后，网格计算打破了传统计算在资源共享和协作方面的限制。网格资源的共享允 许对其他资源的直接访问，而不必像以前那样对资源的共享停留在数据资源传输的层次 上。而且共享资源的各方在协作时可以以多种方式更广泛的交流各种信息，充分利用网 格提供的各种功能。可以看出，网格在资源共享和协作方面有了很大的突破，系统中物 理上分布各异的节点可以方便地共享逻辑上统一的资源，并且相互间可以进行无缝地协 作。 1 1 2 网格计算中作业调度的重要性 网格计算的两大核心部分是资源管理和作业调度。网格的构建是将地理上分布各异 的可用资源通过网络技术互联起来，这些资源不仅数量多、性能差异大，而且体系结构 具有异构性，如何合理地管理和利用这些可用资源是资源管理的主要任务。资源管理是 网格计算中的一个重要方面，但网格计算的主要目标是完成用户提交的各种计算任务， 要完成这些任务，首先需要对各个任务进行分析和资源解析，有必要的情况下还需要将 一个大任务分解成多个子任务进行完成。在对任务进行分析和分解后，就需要为每个 ( 子) 任务寻找合适的资源来完成它，如何合理地将这些任务分配到可用资源上，便是 作业调度的目标，其调度模型如图1 所示。 由此可见，作业调度是用户任务得以顺利完成的关键，一个好的调度策略不仅可以 高效地完成各种任务，取得较高的用户满意度，而且可以为网格系统节省很大一部分的 开销。调度策略是用户和系统共同关注的问题，它的优劣主要取决于调度算法的选取， 调度算法的分析和比较是作业调度研究的关键。由上一节的分析知，网格计算的产生和 发展具有必然性和重要性，它相对于一般的高性能计算，又具有一定的特性。因此，本 文以此为出发点，对网格计算中的作业调度算法进行研究。 2 两北大学硕士学位论文 1 2 国内外研究现状 图1 作业调度模型 1 2 1 网格系统的研究现状 网格计算源于美国和欧洲的研究计划，作为一种新兴的计算机网络技术，它正在向 世界其他国家和地区迅速传播。全球网格论坛( g l o b a lg r i df o r u m ，g g f ) ，以及各地区 和国家的网格论坛也正在迅速的发展，学术交流活动也在积极地展开，其中全球网格论 坛已经成为网格标准制定与发布的主要机构。美国是目前网格研究走在世界前列的国 家，其比较有影响的软件和工具有g l o b u s 4 1 和l e g i o n f 5 1 。欧洲的网格研究起步也很早， 其中的欧洲数据网格【6 】( e u r o p e a nd a t ag r i d ) 是欧洲联盟支持的一个网格项目，它主要 的研究涉及中间件、基础设施、应用和管理四个方面。目前我国的网格研究主要包括 8 6 3 资助的中国国家网格( c h i n an a t i o n a lg r i d ) 计划，教育部资助的中国网格( c h i n a g r i d ) 计划、国家基金委资助的国家科学网计划( n a t i o n a ls c i e n c eg r i d p r o j e c t ) 以及中 国科学院计算所研究的织女星计划。下面对目前应用比较广泛的几种网格系统进行研究 和分析。 g l o b u s l 7 】是目前最成功的网格工具软件之一，它由美国加g o l l l l e 国家实验室、芝加 哥大学、爱丁堡大学和瑞典的皇家研究院等单位合作研究，其中的g t 3 是第一个基于 o g s a ( o p e ng r i ds e r v i c e a r c h i t e c t u r e ) 体系结构的网格平台。g l o b u st o o l k i t 工具包源 于g l o b u s 项目，它是个开放源码的网格基础平台，具有较为统一的国际标准，有利 于整合现有资源，也便于维护和升级换代。新近发布的g l o b u s 4 2 0 ，包含了g t 4 使用 的w e b 服务规范的更新，并且增加了服务的新特性。g l o b u s 对资源管理、数据管理、 安全、信息服务等网格计算的关键理论进行研究并提供了基本的机制和接口。目 第一章绪论 前，一些重要的公司，包括m 和微软都公开宣布支持g l o b u st o o l k i t 。g l o b u s 工具 包机制已经被应用于全球数百个站点和几十个主要的网格计算项目：n a s a 网格 ( n a s ai p g ) 、欧洲数据网格和美国国家技术网格( n a t i o n a lt e c h n o l o g yg r i d ，n t g ) 等。 l e g i o n 是弗吉尼亚大学的一个基于对象的元系统软件项目，它的目标是为用户提供 单一的、一致的虚拟机器模型。该项目开始于1 9 9 3 年，其主要研究内容包括面向对象 的并行计算、分布式系统和安全等，其研究的关键在于系统的可扩展性、易编程性、容 错性、节点自治性等。l e g i o n 的设计是用来支持大型的并行计算系统，以及为用户管理 复杂的物理系统。其第一个公开发布的版本是在高速计算盛行的1 9 9 7 年，地点在加州 圣荷西市。l e g i o n 的作业调度子系统主要侧重于应用级别的调度，强调节点和用户的自 治性。 l s f 8 】( l o a ds h a r i n gf a c i l i t y ) 是由加拿大的p l a t f o r m 公司开发和研制的产品，它 是目前世界上比较成功的一个网格产品。l s f 不仅可以高效完成用户所提交的任务，而 且可以满足用户在s l a ( s e r v e rl e v e l a g r e e m e n t ) 级别上的要求。l s f 提供了多种调度 策略供用户选择，如抢占式调度、b a c k f i l l 调度、资源预留、f 蕊h a r e ( 公平共享) 等 调度方式。另外，如同l s f 的字面意思负载均衡器，它在进行网格作业调度的同 时，还会保证各个节点的负载平衡。l s f 属于集中式作业调度，它有个负责整个系统 的中央调度器，会定期收集各个计算节点的负载信息，如c p u 使用率、分页速率、可 用交换空间和可用存储器的大小、当前在线用户数量、系统空闲时间等，中央调度器会 对这些负载信息进行分析，在作业调度时将其考虑在内，以避免单个节点负载过重的情 况发生。同时，它还具有强大的资源管理能力，能够有效的对系统资源进行管理和分配。 c o n d o 一9 】是由美国威斯康辛大学研究开发的一个关于计算密集型的资源管理系统， 该系统由资源管理和作业管理两部分组成。资源管理部分主要是监视资源的可用情况， 进行资源的调度和分配等。作业管理主要负责管理用户作业，用户可以通过它提交新的 作业、了解作业队列、查询作业的情况等。在资源管理部分，c o n d o r 不同于其他分布 式系统中的集中控制模型，它的资源所有者拥有对该资源的最高使用权，可以根据自己 的实际情况，制定资源使用策略，而其他用户提交给系统的作业不会影响到资源所有者 对其资源的使用。c o n d o r 系统具有很多的优点，如支持检查点和进程迁移、支持多种 平台、支持远程系统调用、c o n d o r 池可以动态扩充、c o n d o r 池之间可以互连等。 4 两北大学硕士学位论文 1 2 2 网格作业调度算法的研究现状 作业调度是网格计算的核心部分，而作业调度算法是作业调度的灵魂所在。因此， 对调度算法的研究具有十分重要的意义。现存的作业调度算法多种多样，本节将对应用 比较广泛的几种算法进行分析、研究和比较。 ( 1 ) o l b ( o p p o r t u n i t yl o a db a l a n c i n g ) 算法，即随机负载平衡算法，它随机将作业 分配到系统可用资源上，而不考虑在该资源上的执行时间、完成时间等。该算法具有思 路简单、调度效率高、一定程度上保证了负载平衡等优点，但是由于其没有考虑执行时 间长短等因素，因此比较耗费计算资源【1 m 1 2 1 。 ( 2 ) m e t ( m i n i m u me x e c u t i o nt i m e ) 和m c t ( m i n i m u mc o m p l i c a t i o nt i m e ) 算法， 即最小执行时间和最早完成时间算法。m e t 是以任意顺序分配作业到具有最小执行时 间的节点上，而不考虑在该节点上何时能够执行完成；m c t 是以任意顺序分配作业到 具有最早完成时间的节点上，而不考虑该节点上的计算资源是否对此作业具有最小执行 时间。m e t 和m c t 算法思路简单，各自仅考虑了最小执行时间和最早完成时间的一个 方面，因此必然存在一定的弊端，前者节省了一定的计算资源，但完成任务的时间跨度 会比较大；后者的时间跨度比较小，适合于要求快速响应的任务，但可能会比较浪费计 算资源。 ( 3 ) m i n m i n 和m a x m i i l 算法，m i n m i n 算法是当前研究网格调度的基础算法之一， 经常作为标准对其他算法进行性能评估。其基本步骤是将所有作业组成一个任务集合， 每次计算集合中所有作业在每个计算资源上的最早完成时间，然后选择最早完成时间最 小的任务进行调度，同时在集合中删除该任务，重新计算集合中剩余任务的最小完成时 间，进行新一轮的调度，直到所有任务都调度完毕。m a x m i n 算法与m i n m i n 算法类 似，只是每次选择最小完成时间最大的任务进行调度，即优先调度长作业【1 0 。2 1 。 ( 4 ) u d a ( u s e rd i r e c t l ya s s i g n i n g ) 算法，即用户直接指派算法。该算法直接由用 户指定某个作业到某个节点上去执行，用户并不知道该节点上资源使用情况，也不清楚 指定的作业在该资源上的执行时间如何。作业的开始运行时间取决于指定节点上的负载 情况，如果负载比较轻可以得到快速响应，如果负载比较重，则需要等待很长时间。该 算法思路简单，但作业何时开始执行、执行的效率如何都是未知的【1 0 1 1 】。 ( 5 ) a 书( a s t a t ) 算法是在静态路网中求解最短路径最有效的方法。它可以用公式表 示为：删俐+ 五例，其d p f ( n ) 是节点刀从初始点到目标点的估价函数，g 例是在状 态空间中从初始节点到靠节点的实际代价，j l l 俐是从以到目标节点最佳路径的估计代价。 5 第一章绪论 保证找到最短路径( 最优解) 的条件，关键在于估价函数j j l 似的选取：如果估价值而例 小于以到目标节点的实际距离，则搜索的点数多，搜索范围大，效率低，但能得到最 优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到 最优解。估价值与实际值越接近，说明选取的估价函数就越好。a 木算法在很多任务分 配的问题中都有应用，它是一种静态启发式的搜索方法，根节点是空节点，每个中间节 点都代表部分解。 ( 6 ) g a ( g e n e t i ca l g o r i t h m ) 算法，即遗传算法。遗传算法是模拟达尔文生物进化 论的自然选择以及遗传学机理的生物进化过程的一种计算模型，它是一种通过模拟自然 进化过程搜索最优解的方法，最初由美国m i c h i g a n 大学j h o l l a n d 教授于1 9 7 5 年提出 来的。g a 算法经常应用于作业调度问题，它假定问题的解可以用一串参数的组合来表 示( 参数串称为染色体) ，并借鉴生物学中“适者生存 的概念，在解决问题开始时随 即生成一个染色体，然后加上一定数量的任意解，从而生成多个染色体，最后通过轮转 法选择合适的染色体作为父本进行保留，两个父本可以进行交叉配对，从而产生下一代 染色体。这样经过多次的重复，就会产生越来越接近最优解的染色体 1 3 - 15 1 。 1 3 本文的主要研究内容和结构安排 本文在研究网格体系结构、作业调度算法以及网格模拟器的基础之上，详细分析了 m i n m i n 算法的性能及其不足，并对其进行了改进，提出了d p r i m i n m i i l 算法。最后 通过网格模拟器g r i d s i m 对m i n m i n 和d p r i m i n m i n 算法进行了模拟和比较。论文的 主要工作如下： 1 了解网格的相关概念，深入学习网格的体系结构及其作业调度算法，对目前比 较流行的几种网格调度系统进行了分析研究，同时详细分析了各种作业调度算法的特点 及其优缺点。对集中式调度、分布式调度和分层式调度三种网格作业调度模式进行了研 究和比较。 2 详细分析研究了m i n m i n 作业调度算法的步骤、特点、优点及其缺点，重点分 析了该算法在长作业调度方面的不足，提出了改进算法d p r i m i n m i n 。在改进过程 中引入了作业优先级的概念，并将其与作业的最早完成时间相结合，综合对其进行考虑， 最后给出作业的调度顺序。 3 分析和比较了应用比较广泛的几种网格模拟器，选择出比较适合模拟本文算法 的g r i d s i m 。最后，使用网格模拟器对m i n - m i n 和d p r i m i n m i n 算法进行了仿真和性 6 西北大学硕士学位论文 能分析，证明了d p r i m i n m i n 算法的优越性及其对网格环境的适应性。 全文共分为六章，各章节的主要内容如下： 第一章，绪论。主要介绍选题背景和意义、国内外研究现状，以及本文主要研究内 容和章节安排。 第二章，网格及其作业调度的研究。在网格体系结构学习的基础上，研究和分析了 网格计算中作业调度的特点、模式、性能评价标准等，最后对主流的网格模拟器进行了 学习和比较。 第三章，d p r i m i n m i n 算法研究。在网格系统中作业调度的相关概念、m i n m i n 调度的基本概念了解的基础上，对m i l l m i n 算法进行了深入学习，发现其中的不足， 提出了改进算法- d p r i m i n - m i n 算法，并对其进行详细分析和研究。最后，通过一 个实例对两种算法的调度过程进行说明和比较。 第四章，d p r i m i n m i i l 算法设计与实现。本章主要对网格系统中作业调度模块的 主要阶段进行分析和研究，采用面向对象的方法对其实现，介绍主要类的设计与交互。 在此基础之上，对m i n m i n 和d p r i m i n - m i n 算法进行设计和实现，给出算法的主要流 程图和核心代码。 第五章，d p r i m i n m i n 算法模拟和性能分析。在网格模拟器g r i d s i m 学习的基础上， 对m i n - m i n 和d p r i m i n m i l l 算法进行模拟，并对模拟结果进行分析和比较。 第六章，总结和展望。对本文研究工作进行总结，对未来工作进行展。 7 西北大学硕士学位论文 第二章网格及其作业调度的研究 网格，是继传统因特网、w e b 之后的第三次互联网浪潮，它试图实现互联网上所有 资源的全面连通，从而消除信息孤岛。其中包括计算资源、存储资源、通信资源、软件 资源、信息资源、知识资源等。网格最大的特点不在于物理规模的庞大，而在于通过网 络技术将多个节点互联起来所具有的超强计算能力，以及通过共享地理上分布在多个自 治系统中的资源来协同完成某个任务的能力。网格的超强计算能力是通过多个系统的协 作实现的，而一个任务是由网格中一个或多个节点来完成的，如何将任务分配到各个节 点上，则需要作业调度。因此本章在分析网格系统结构的基础之上，研究了网格系统中 作业调度的特点以及调度模式，进而研究了网格模拟器，以便对调度算法进行模拟和比 较。 2 1 网格体系结构 网格体系结构是关于如何构建网格的技术，它的主要功能是划分系统的基本组件， 描述各组件的基本功能、组件之间的相互作用，以及各组件集成的方式方法等。到目前 为止，主要的网格体系结构有两种：一种是由f o s t e r 等人在早些时候提出来的五层沙漏 结构【1 6 1 ；另一种是在w e b 技术的发展与影响下，f o s t e r 等人结合w e bs e r v i c e s 的思想，提 出的开放网格服务结构o g s a ( o p e i lg r i ds e r v i c ea r c h i t e c t u r e ) 1 7 】。本节将对这两种体系结 构进行详细的分析和研究。 1 五层沙漏结构 该结构是早些年由f o s t e r 等人提出的一种比较简单的结构，应用十分广泛，它主要 侧重于定性的描述而不是协议的定义，因此没有严格的规范。该结构共分为五层，即构 造层、连接层、资源层、汇聚层和应用层，如图2 所示，每层组件具有相同的特征，上 层组件可以在任何一个下层组件之上构建，从而形成一个层次结构。 第一层是构造层( f a b r i c ) ，它的功能是向上提供网格中可供使用的资源，即物理或 逻辑上的实体，如计算资源、存储资源、仪器设备、网络资源、软件等，它通过管理这 些物理资源，向上层提供资源使用接口及管理控制界面，网格通过支持设备共享的协议 来访问本地设备。 9 第二章网格及其作业调度的研究 一阙 应用层 脲佃澎控 汇聚层 资源与服务的安全访问i l 资源层 与连接层 蹴熟麓弋 构造层 图2 网格的五层沙漏结构 第二层是连接层( c o n n e c t i v i t y ) ，它主要为下层的物理资源提供安全的数据通信能 力，是资源间进行互操作的前提，为孤立的单个资源间建立了联系，构造层的各种资源 间的数据通信都是在这一层的控制下完成的。 第三层是资源层( r e s o u r c e ) ，它主要是对单个资源进行控制，与系统可用资源进行 安全握手、对资源做初始化、统计资源使用数据、监控资源运行状况等。 第四层是汇聚层( c o l l e c t i v e ) ，它的作用是将资源层提供的受控资源汇聚在一起，并 协调解决多个资源之间的问题，供虚拟组织的应用程序共享、调用，主要提供目录代理、 诊断监控、资源分配、负载控制等功能。 第五层是应用层( a p p l i c a t i o n ) ，这层是网格上用户的应用程序，它关心的是有什么 样的资源可以提供给网格用户，以解决网格用户的不同问题。 这种结构的典型特征就是它的沙漏形状，这主要是由网格环境中对不同层服务要求 量的不同而形成的。最上面的应用层，由于其分布在不同的客户端，所以一般不会发生 争用；而汇聚层只有在协调多个资源时才使用，争用的可能性比较小；最下面的构造层 分布在各个物理资源上，基本不会争用。但是核心的资源层和连接层是所有任务分配和 资源使用都要调用的部分，同时要实现上层各种协议向核心协议的映射，以及核心协议 向下层各种协议的映射，这势必造成此结构的瓶颈，从而显示为沙漏形状。 2 开放网格服务结构o g s a l n 西北大学硕士学位论文 该结构是w e bs e r v i c e s 和g r i d 技术相结合的产物，它已成为网格基础框架的 标准，利用w e bs e r v i c e s 的标准接口定义机制、多协议绑定、本地与远端的透明 性，同时利用网络服务的服务语义、可靠性和安全模型、生命周期管理、发现和 其他服务，以及多主机或运行环境来建构自己的框架。o g s a 是在五层沙漏结构 的基础之上，结合w e b 服务而提出来的，以服务为中心，试图实现对服务的共享， 而五层沙漏结构实现的是对资源的共享。o g s a 主要包括资源层、w e b 服务层、 基于o g s a 架构的服务层、网格应用层四部分。 第一层是资源层，资源的概念是o g s a 以及网格计算的中心部分，它包括物理资源 和逻辑资源，物理资源在逻辑资源之上。 第二层是w e b 服务层，所有网格资源( 包括逻辑的和物理的) 在这一层都被定义为 服务，它为所有的资源定义标准的接口、行为与交互，并进一步扩展了w e b 服务的定义， 提供了动态的、有状态的、可管理的w e b 服务的能力。 第三层是基于o g s a 架构的服务层，它定义了基于网格的服务，这些网格服务包括 管理服务、通信服务、策略服务、安全服务等，随着这些新服务的出现，o g s a 变成更 加有用的面向服务的架构。 第四层是网格应用层，当基于网格架构的服务不断被开发出来时，使用其提供的各 种服务的新网格应用程序也将出现，从而构成了o g s a 的这一层。 2 2 网格系统中作业调度的研究 作业调度本身是一个比较复杂的过程，加之网格系统具有的一些独特性质( 1 8 j ，导致 网格系统中的作业调度更加复杂。对于一个作业调度系统，从应用的角度来说，用户关 注的是它给应用所带来的等待时间、执行时间等指标；而从系统的角度来说，管理员关 注的则是它导致的系统吞吐率、负载平衡等指标。这两方面的指标有时候并不能达到完 全一致，这就给作业调度带来了多种可能性，下面将对网格系统中的作业调度进行相关 研究。 2 2 1 网格作业调度的特点 网格调度技术比传统高性能计算中的调度技术更复杂，这主要是因为网格具有一些 独有的特征。例如，网格资源的动态变化性、资源类型的异构性和多样性1 9 】、调度器的 分布性和局部管理性等。在网格调度中，还需要考虑移植性、扩展性、效率、可重复 第二章网格及其作业调度的研究 性以及网格调度和本地调度的结合等一系列问题。总的来说，网格计算中的作业调度主 要有以下几方面的特征： ( 1 ) 作业调度面向的是异构平台。组成网格的节点可以是各种类型的主机、工作站 或者p c 机，它们是异构的，可以运行在w i n d o w s 、l i n u x 等操作系统上，同样可以是 上述机型组成的集群系统、存储系统、数据库或者其他设备。所以网格系统中的作业调 度面向的是异构平台，必须在该异构平台上进行作业的调度。 ( 2 ) 网格节点具有自治性。网格系统中的作业调度是针对整个网格而言的，但该调 度不会影响也不能影响各节点内部的调度策略，节点内部的调度具有自治性。 ( 3 ) 作业调度具有自适应性。网格资源不仅是异构的，而且是动态变化的，任何资 源在任何时间都可能出现故障，也可能随时加入网格系统，或者重新开始工作，总之， 网格资源可能随时变动，网格中的作业调度必须具有自适应性才能满足这种变化。 ( 4 ) 作业调度具有可扩展性。网格在刚开始建立时，规模一般都比较小，但是随着 超级计算机系统的不断加入，网格系统就会逐步扩大。因此在网格资源规模不断扩大， 应用不断增加的情况下，网格作业调度必须具有可扩展性，才能保证系统的总体性能不 会下降。 总之，网格环境下的作业调度由于网格独有的特征而具有一定的复杂性，为了便于 研究，下节将详细讨论网格系统中应用比较广泛的几种调度模式。 2 2 2 常见的网格系统调度模式 在目前的网格系统中，应用比较广泛的调度模式有三种：集中式作业调度、分布式 作业调度和分层式作业调度。 ( 1 ) 集中式作业调度。在集中式调度中，有一个专门的中央调度器，它负责整个网 格环境下的作业调度。在这种模式下，用户首先将作业提交给中央调度器，然后由调度 器将作业分配到适当的节点上。这种调度模型一般适用于所有网格资源具有相类似的特 性和使用规则的场合。集中式作业调度的优点是它能给出更好的调度策略，因为中央调 度器掌握了所有可用资源的信息，能够在整体上进行把握。但是，当调度器所管理的网 格环境不断扩大时，就会出现调度瓶颈，因为这种情况下很容易出现单点失效，解决此 问题的有效方法是提供备用调度器。 ( 2 ) 分布式作业调度。在分布式作业调度系统中，存在多个调度器，每个调度器负 责一个管理域的作业信息，不存在管理所有作业的中央调度器。这种模式克服了集中式 1 2 西北大学硕士学位论文 调度的扩展性问题，并且具有更好的容错性和可靠性。但是由于没有管理整个环境的中 央调度器，分布式调度通常会产生不够理想的调度策略。 ( 3 ) 分层式作业调度。分层式作业调度是集中式作业调度和分布式作业调度的结 合，这种调度模式包含一个中央调度器和多个本地调度器。中央调度器相当于一个元调 度器，它负责接收用户提交的作业，并将作业分配到下一层的本地调度器上。与集中式 相比较，分层式也有一定的通信瓶颈，但是它的主要优点在于中央调度器和本地调度器 可以采用不同的调度策略。 以上三种模式各有优缺点。集中式调度比较适用于小型的网格系统，因为在这种系 统下中央调度器的负担不会太重，容易生成好的调度策略。分布式调度具有好的容错性 和扩展性，但各调度器之间若没有好的吞吐量时，很难产生好的调度策略。分层式调度 结合了两者的优点，但是却没有地域自治性。 2 2 3 算法性能的评价标准 网格调度的目标是多元的，用户和系统的要求也是不尽相同的，但是网格调度的总 体目标是为用户提供最有效的调度结果。评价一个调度结果的标准也是多样的，常用的 有以下四个：负载平衡【2 l 】( l o a db a l a n c i n g ) ，时间跨度( m a k e s p a n ) ，服务质量【2 2 】( o o s ， q u a l i t yo f s e r v i c e ) ，经济原则【2 3 1 ( e c o n o m i cp r i n c i p a l s ) 。 ( 1 ) 负载平衡主要是站在系统的角度进行考虑，它是分布式计算中一个很重要的指 标。所谓负载平衡就是尽量的将作业分配到更多的计算节点之上，各个节点负载相差尽 量小，以避免有的节点负载过重，而有的节点过轻，甚至零负载( 极端情况) 。负载平 衡常作为一个标准来检测调度算法的性能。 ( 2 ) 时间跨度是指一个用户所有作业的执行时间，即系统从运行用户第一个作业开 始到执行完最后一个作业所经历的时间，一般是用户和系统共同追求的目标。时间跨度 越小，执行作业所用时间就越短，调度策略就越好。 ( 3 ) 服务质量是指用户对使用资源在某些方面特殊的要求，如c p u 性能、内存大小、 网络带宽等。这是更高级的用户需求，一般会在提交作业时给出。系统在对这些有 q o s 要求的作业进行调度时，首先筛选出符合条件的资源，然后对其进行调度。当然， q o s 也经常作为标准对调度结果进行评估，类似于用户满意度。 ( 4 ) 经济原则是指作业在执行过程中的资源消费问题。网格系统中的资源是多种多 样的，而且分布在不同的地理位置，因此使用不同的资源所花费的代价是不同的。在网 第二章网格及其作业调度的研究 格系统中，对同一组作业可以产生不同的调度策略，虽然都能顺利完成，并且也可以满 足用户的q o s 需求，但是其花费可能相差很大。因此经济原则也经常作为一个重要指 标来衡量调度策略的优劣。 2 3 网格模拟器的研究与选择 对网格环境下的作业调度进行研究，必然需要搭建网格环境。但网格是动态变化的， 而且其分布也比较广泛，构建真实的网格环境很复杂而且不具有现实意义。因此需要网 格模拟器对其进行模拟，这是进行网格系统研究的主要途径之一。 2 3 1 主流网格模拟器的研究 目前，有很多网格模拟工具【2 4 1 ，应用比较广泛的有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 等。 b r i c k s l 2 5 1 由日本东京技术学院主导开发，由广域计算环境和调度单元两部分构成， 它使用的是j a v a 语言编写的一个离散事件包，所有的资源和网络模拟的都是简单的先 来先服务f c f s ( f i r s tc o m ef i r s ts e r v e r ) 策略，所有的作业都是由数据的传输和指令的 执行来表示的。b r i c k s 模拟的并不是真正的网格环境，它主要用于在虚拟网格环境中进 行资源分配策略的研究。目前，该模拟器还没有提供下载，也没有公开的源码。 m i c r o g r i d 2 6 1 由美国加州大学圣地亚哥分校并行系统体系结构小组( c s a g ) 领导开 发，它是基于l i n u x ，使用c 语言开发的。m i c r o g r i d 试图通过利用现有的物理资源( 比 如一个c l u s t e r ) 来模拟一个虚拟的网格环境，并以此来运行真实的网格应用，从而达到 更真实的评估网格系统的目的。它建立在g l o b u s 平台上，可以执行使用g l o b u s 工具包 构成的应用程序。m i c r o g r i d 创建的是一个虚拟的网格，而不是创建网格的模拟，它能 够产生精确的结果，但也存在不足之处。由于大量资源运行在模拟资源之上，所以对比 较大的应用程序而言，环境的模拟和调度算法的执行都比较耗时。因此，m i c r o g r i d 使 用g l o b u s 构造的应用程序要付出很大的开发代价，它经常作为补充性的工具来检验真 实应用程序的模拟结果。 s i m g r i d l 2 7 】是由美国加州大学圣地亚哥分校网格研究和创新实验室( g r i dr e s e a r c h a n di n n o v a t i o nl a b o r a t o r y ) 主导开发，它的目标是为在网格环境下进行分布式应用调度 研究提供一个合适的模型和抽象，同时生成准确的模拟