（计算机应用技术专业论文）pc集群作业调度算法研究.pdf

摘要根据t o p 5 0 0 数据显示，集群系统已经成为高性能计算机的主流，而集群作业管理则是保证集群高效运行的关键，也是集群应用的基础。同时，作业调度算法又是集群作业管理系统的核心，是作业调度的重中之重。一个好的调度算法不但可以减少作业的等待时间，缩短作业响应时间，还能够充分利用系统的资源，提高系统利用率。在众多的集群系统中，o p e n p b s 是为数不多的开源产品之一，它对集群系统提供了良好的支持。而在作业调度算法中，b a c k f i l l i n g 算法越来越被认同是集群作业系统中有效的调度算法。本文对作业管理系统和作业调度算法进行了深入的分析和研究，阐述了集群管理系统o p e n p b s 系统默认调度算法f i f o ，以及b a c k f i l l i n g 算法的优缺点。针对o p e n p b s系统默认调度算法f i f o 调度策略单一、造成大作业长期等待、系统资源利用率低以及b a c k f i l l i n g 算法因无法找到合适作业回填而造成资源浪费的问题，提出了l a r b ( l a r g ea r e a - r e s e r v a t i o nb a c k f i l l i n g ) 算法，并将其引入o p e n p b s 系统。l a r b 算法以作业所需c p u 数及预估运行时间所构成的二维面积作为优先调度条件，引入二级优先级和预约算法来消除大作业的饥饿现象。通过减少回填作业所需的c p u 数，并相应增加预估运行时间，使作业能够成功回填，从而提高c p u 利用率。为了检验l a r b 算法的有效性，在具有1 0 个节点的集群系统下进行了测试实验。实验证明该算法是合理且有效的。该算法引入o p e n p b s 系统后，与f i f o 及b a c k f i l l i n g相比，大大缩短了作业平均响应时间，同时提高系统c p u 的利用率，很好的解决了资源利用率低的问题。关键词：集群，作业调度，o p e n p b s 系统，l a r b 算法，回填算法，面积最大优先，预约算法r e s e a r c ho nj o bs c h e d u l i n ga l g o r i t h mb a s e do i lp cc l u s t e r( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y )d i r e c t e db ya s s o c i a t ep r o f a b s t r a e ta c c o r d i n gt ot h ed a t ao ft o p 5 0 0 ，c l u s t e rs y s t e mh a sb e e nt h em a i n s t r e a mo fh i g h - p e r f o r m a n c ec o m p u t i n gs y s t e m a n dt h ej o bm a n a g e m e n ts y s t e mi st h ek e yo fc l u s t e r j o bs c h e d u l i n ga l g o r i t h mi st h ec o r eo f j o bm a n a g e m e n ts y s t e ma n dt h em o s ti m p o r t a n tp a r to ft h ew h o l es y s t e m ag o o dj o bs c h e d u l i n ga l g o r i t h mn o to n l yr e d u c e st h ew m f i n gt i m eo faj o b ，b u ta l s om a k e sf u l lu s eo fr e s o u r c e si ns y s t e m ，a n di m p r o v e sc p uu t i l i z a t i o n o p e n p b si so n eo ft h em o s tp o p u l a rj o bm a n a g e m e n ts y s t e m s ，w h i c hh a sag o o ds u p p o r tf o rh i g h - p e r f o r m a n c ec o m p u t i n g b a c k f i l l i n ga l g o r i t h ma sa l le f f e c t i v es c h e d u l i n ga l g o r i t h mh a sb e e nm o r ea n dm o r er e c o g n i z e d t h i sp a p e rm a i n l yf o c u s e so nj o bm a n a g e m e n ts y s t e ma n dt h es c h e d u l i n ga l g o r i t h m ，e l a b o r a t e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so fo p e n p b ss y s t e ma n db a c k f i l l i n ga l g o r i t h m t h ef i f os c h e d u l i n ga l g o r i t h mo fo p e n p b sm a yc a u s es o m ei d l er e s o u r c e si nt h es y s t e m ，a n dw h e nt h ei d l ec p u sc a n tm e e tt h er e q u i r e m e n t so f t h es m a l l e rb a c k f i l l e dj o b s ，t h e r ea r es t i l li d l ec p u s ，a n dt h ec p uu t i l i z a t i o nc a n tb eb e t t e re n h a n c e d i no r d e rt or e s o l v et h o s ep r o b l e m s ，l a r b ( l a r g ea r e a r e s e r v a t i o nb a c k f i l l i n g ) i sp r o p o s e di n t h i sp a p e r i ti sp r o v e dr e a s o n a b l ea n de f f e c t i v el a r ba l g o r i t h mi sb a s e do nl a r g e s ta r e af n s t t h ef i r s ts c h e d u l e dl a r g ea r e aj o b si m p r o v et h ej o bf a i r n e s s i n t r o d u c i n gt w ol e v e lp r i o r i t ya n dr e s e r v a t i o na l g o r i t h mc a ne l i m i n a t et h eh u n g e ro fb i g g e rj o b s ，r e d u c et h er u n n i n gt i m eo f j o b sa n de n h a n c et h ec p uu t i l i z a t i o n i nt h ep a p e r , ac l u s t e rw i t h10n o d e sw a sb u i l t t h et e s t e dr e s u l ti st h a tr e s e r v a t i o n b a c k f i l l i n ga l g o r i t h mc a nb e t t e ri m p r o v et h ej o bf a i r n e s s ，c p uu t i l i z a t i o na n dt h ea v e r a g er e s p o n s et i m et h a nt h et r a d i t i o n a lb a c k f i l l i n ga l g o r i t h m k e yw o r d s ：c l u s t e r , b a c k f i l l i n ga l g o r i t h m ，p b s ，j o bs c h e d u l i n g ，l a r g e s ta r e af i r s t ，r e s e r v a t i o na l g o r i t h m关于学位论文的独创性声明本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外，本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对研究所做的任何贡献均己在论文中作出了明确的说明。若有不实之处，本人愿意承担相关法律责任。学位论文作者签名：盘垒昼日期：矽、7 1 年牟月厂日j学位论文使用授权书本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手段保存学位论文。保密学位论文在解密后的使用授权同上。学位论文作者签名：垂垒堡指导教师签名：日期：刨绛争月日醐一垆垆月7 日中国石油大学( 华东) 硕士学位论文第一章绪论随着计算机技术和通讯技术的发展，采用高速局域网连接的微机群进行并行计算，从而取代一部分大型并行机，这种新的计算系统已成为人们研究的热点。集群作为其中的一项技术也受到了国内外人士的关注。在本章中，对集群技术及集群计算中作业调度的分析，引出了课题的意义及研究内容。最后，介绍论文的组织结构。1 1 集群技术的发展在2 0 世纪8 0 年代，人们认为计算机性能的提高主要是由于生产出了更快更有效的处理器。这种观点受到了并行处理概念的挑战。并行计算的根本意义在于将两台或者更多台的机器连接起来，共同解决一些计算问题。从2 0 世纪9 0 年代以来，昂贵而特制的并行超级计算机向工作站网络( n o w ) 转换的趋势越来越强，高性能工作站和网络逐渐的商品化成为促使这种转换的驱动因素。技术的发展使计算机网络成为并行处理的理想工具，从而导致了低价商品化超级计算机的出现【1 1 。对于利用并行处理来为大规模和具有高度挑战性的应用提供高性能计算能力的技术，人们已经进行了广泛的研究。直到最近，从事这个领域研究的人们仍然可以从中获益。并行计算的发展趋势正从传统的专用超级计算机平台转变到廉价而通用、松耦合、由单一或者多个处理器的p c 机或者工作站构成的集群系统。这种趋势有很多的优势，包括可以按照给定的任务建造平台，以适应较大型的应用程序和工作负荷等。使用集群建立原型、调试、运行并行应用程序越来越成为替代专用、特别是昂贵的并行计算平台的发展趋势。由于p c 集群和高端大型机相比，具有极其优越的性能价格比和高的可扩展性，近年来，使用低端工作站和p c 进行集群计算的技术逐渐成为研究的热点。1 2 集群作业管理系统集群管理系统的出现就是要解决用户如何高效的、透明的使用集群的问题。对用户来说，他没有必要去了解整个集群系统内部的结构是怎么样的，甚至于不必知道他即将使用的集群系统位于何地。所以作为集群系统软件的重要组成部分，集群作业管理系统要可以根据用户的需求，统一管理和调度集群的软硬件资源，提供作业的提交、调度、执行以及控制等机制，平衡网络负载，保证用户作业公平合理地共享集群资源，第一章绪论提高系统利用率和吞吐率。目前的几十种集群作业管理系统，在目标、结构、功能和实现上各有差异，从不同侧面反映了集群作业管理系统所应具备的特性。p b s ，c o n d o r , l s f ，l o a d l e v e l e r 是当今颇具代表性和影响力的几种集群作业管理系统。其中p b s ，c o n d o r 是研究产品，l s f ，l o a d l e v e l e r 是商业软件。1 3 集群计算中的作业调度从本质上讲，集群计算这项分布式技术核心的服务对象是一个个应用程序【2 】，或者说是作业，所以作业的调度自然就成为集群的一个核心部分。集群表现的好坏，也即作业执行的速度与效果如何，除了会受到前面提到的处理器、网络、程序本身的结构等方面的影响，还取决于对作业的调度与控制。如何将各个作业派遣到集群中合适的资源上执行，如何使各并行作业的各个处于不同节点的分进程协调地工作，如何使各个作业的执行不会互相干扰，当被分配给工作的资源出现故障或被收回时又该如何处理，等等，这一切都影响着作业运行的性能，而这是用户极为关心的问题。除了单纯的速度要求，人们还可能提出要高效利用集群资源、平衡集群中各处的负载、实现具有不同重要性的用户作业可以按比例获得对资源的使用权，等等诸如此类的要求。可见，作业的调度与管理是集群的重要组成部分，涉及到作业从提交到完成返回结果之间的各个阶段，关系到集群中的方方面面，可谓自成系统【3 】是集群技术研发的重点之一。如果把集群管理软件视作控制集群这个由分散的节点组成的分布式系统的操作系统，那么作业管理系统所实现的就是这个操作系统关于作业调度与执行方面的功能。1 4 课题的意义及研究内容集群及类集群系统已经存在了很多年，成为目前高性能计算机的主流，而集群作业管理则是保证集群高效使用的关键。作为集群系统软件的重要组成部分，集群作业管理可以根据用户的需求，统一管理和调度集群的软硬件资源，保证用户作业公平合理地共享集群资源，提高系统利用率和吞吐率。在集群作业管理技术上，作业调度对于集群的性能有着很重要的影响。影响作业管理系统调度工作的因素主要有：系统结点的负载，作业对资源的需求、日历规则以及调度算法。一个好的作业调度策略对于系统资源利用率、作业平均运行时间、公平2中国石油大学( 华东) 硕士学位论文性等方面有着至关重要的影响。因此，寻找一个好的作业调度算法对于作业管理系统是种迫切需求。目前存在几十种集群管理系统，其中p b s 系统最初由n a s a 的a m e s 研究中心开发，为了提供一个能满足异构计算网络需要的软件包，特别是满足高性能计算的需要。b a c k f i l l i n g 算法即所谓回填算法，是一种充分利用作业管理系统在作业调度时产生的时间空隙，提高系统资源利用率的调度算法。由于o p e n p b s 系统的开源性使得我们可以根据不同的目标来制定自己的调度策略。因为o p e n p b s 调度算法存在不足，而b a c k f i l l i n g 优点可以弥补其不足，所以将两者相结合为本论文提供了很大的研究空间。课题研究内容主要有两点：( 1 ) 调度算法研究调度算法会直接影响系统的性能，因此要选择合理的算法。调度算法有许多，主要包括：f c f s 、f i r s t f i t 、b e s t f i t 、g r e e d y 、r e s e r v a t i o n 、b a c k f i l l i n g 等。其中b a c k f i l l i n g t l l l 2 算法通过对大作业进行资源预留，并让小作业填充资源预留产生的空隙，较好的解决系统高利用率和作业公平性之间的矛盾，然而通过对b a c k f i l l i n g 算法的分析后可以看到，利用b a c k f i l l i n g 算法进行作业调度的时候，该算法每次在调用时只考虑一个作业，因此并不一定能够找到一个最合适的作业来对空隙进行填充，还是有可能对系统资源造成较大的浪费。因此如何改进b a c k f i l l i n g 算法是本课题的研究重点。( 2 ) p b s 作业管理系统与b a c k f i l l i n g 算法结合的研究在p b s 3 】的调度模块中，提供了由c ，t c l ，b a s l 三种语言各自书写的三个任务调度器，系统管理员可以自由选择其中一种作为整个系统的调度器。其中，由c 语言书写的调度器所实现的功能更多，也更容易得以扩充，因而被p b s 组织所推荐使用【3 】。但是由于p b s 系统作业调度算法的单一性，不灵活，导致了系统资源利用率的下降。研究分析p b s 的系统的作业调度策略，以及如何将b a c k f i l l i n g 算法引入该系统是本课题的第二个研究内容。1 5 论文的组织第一章引言，介绍集群技术的发展、集群作业管理系统、集群计算中的作业调度，以及课题的意义及研究内容。第二章集群和作业管理系统，对集群计算技术进行概述，包括集群概念以及集群作业管理系统，特别是p b s 系统，分析该系统并指出不足。3第一章绪论第三章集群作业调度算法，介绍典型集群作业调度算法，并分析它们的优缺点，最后对b a c k f i l l i n g 进行了详细的剖析。第四章调度算法设计及实现，详细分析说明了改进后的b a c k f i l l i n g 算法的设计与实现。第五章实验测试及结果，搭建实验环境，对新的算法性能进行了测试，最后给出了综合评价。最后一部分是总结与展望，总结全文，归纳创新点，并给出以后的研究方向。4中国石油大学( 华东) 硕士学位论文2 1 集群计算概述2 1 1 集群系统结构第二章集群和作业管理系统集群是一种并行或者分布式处理系统，由很多连接在一起的独立计算机组成，使其像一个单独集成的计算资源一样协同工作【3 】。运行一个操作系统、具有一个或几个i p 地址的一台计算机称为一个节点( n o d e ) ，它可以是一个单处理器或多处理器的系统( p c 、工作站、s m p ) ，拥有独立的内存、i o 设备和操作系统。一个集群通常指连接在一起的两个或者多个计算机节点。节点可以是连接在一起的，也可以是物理上分散而通过l a n 连接到一起的。一个连接在一起的计算机集群对于用户和应用程序而言就像一个单一的系统。这样的系统可以提供一种价格合理、并能获得所需性能和优势的解决方法。这在以往只能通过共享内存的系统来达到。典型的集群系统的结构如图2 1 所示：ii串行应用 _l并行编程环境图2 - 1 集群计算机的体系结构1 4 1f i g2 - 1c l u s t e ra r c h i t e c t u r e l 4 i2 1 2 集群的特点在相对较低的费用下，集群系统还具有以下特剧4 】：( 1 ) 集群都是将普通p c 、工作站或服务器通过某种方式连接起来构成的多机系统。连接方式可以采取通过网络适配器和网络集线器，或通过将各个机器的r s 2 3 2串口直接连接起来，还可以通过内存通道卡和内存通道集线器的方式连接各台机器。第二章集群和作业管理系统( 2 ) 集群系统都具有良好的可用性。即它们都能够在集群的某部分资源出故障的情况下继续向用户提供持续的服务。几乎所有的典型集群都拥有灾难恢复功能。( 3 ) 集群系统有良好的可扩展性。只需很少的配置工作就可以方便地向集群中加入或删除工作节点。( 4 ) 典型的集群系统提供了良好的可管理性。管理人员通过简单的操作就可以对集群中的工作节点或控制节点进行配置工作。( 5 ) 集群系统一般都提供了负载平衡功能。负载平衡包括静态负载平衡和动态负载平衡，为了最大程度地利用集群中的一切资源，集群需要具有动态负载平衡功能，它能够通过监视集群中的实际节点的负载情况进行调度的改变。( 6 ) 大部分集群系统都有一个主控机，它能够对集群中的机器的运行状态进行监视，而且能够根据各机器的负载轻重进行任务的调度。2 1 3 集群的分类基于不同的因素，集群可有以下几种分类方式【8 9 1 1 1 0 】【l l 】：( 1 ) 应用目的计算科学或具有很高要求的应用高性能( h p ) 集群。高可用性( h a ) 集群。高性能集群通过将多台机器连接起来同时处理复杂的计算问题。模拟星球附近的磁场、预测龙卷风的出现、定位石油资源的储藏地等情况都需要对大量的数据进行处理。传统的处理方法是使用超级计算机来完成计算工作，但是超级计算机的价格比较昂贵，而且可用性和可扩展性不够强，因此集群成为了高性能计算领域瞩目的焦点。高可用性集群的主要功能就是提供不问断的服务。有许多应用程序都必须一天二十四小时地不停运转，如所有的w e b 服务器、工业控制器、a t m 、远程通讯转接器、医学与军事监测仪以及股票处理机等。对这些应用程序而言，暂时的停机都会导致数据的丢失和灾难性的后果。( 2 ) 节点归属归属于个人或只作为集群的节点专用集群。非专用集群。这两者的区别在于集群节点的归属。在专用集群中，特定个体并不拥有一个工作站，资源是共享的，所以并行计算可以在整个集群上执行。而非专用集群是指个人拥6中国石油大学( 华东) 硕士学位论文有工作站，应用程序是靠窃取空闲c p u 周期来执行的。导致这种应用的原因是工作站的大部分c p u 周期是空闲的，即使在高峰时间也是如此。这种在非专用的动态变化的工作站集群上运行的并行计算叫做自适应并行计算。在非专用集群中，工作站所有者和需要使用工作站来运行他们的程序的远程用户之间存在着一种张力。前者希望他们的工作站能快速做出反应，后者只在乎使用所有空闲的c p u 周期来完成他们的计算。强调分享处理能力资源使节点归属的概念模糊了，并引进了如进程迁移和负载平衡策略这样复杂的概念。这些策略允许集群在达到适当的反应能力的同时提供串行和并行计算所需的共享资源。( 3 ) 节点硬件p c 、工作站或s m p 。p c 集群( c o p )工作站集群( c o w )s mp 集群( c l u m p )( 4 ) 节点操作系统i ，i n u ) 【，n t ，s o l a r i a ，a i x 等。l i n u x 集群( 例如，b e o w u l f )s o l a r i s 集群( 例如，b e r k e l e yn o w )n t 集群( 例如，h p v m )a i x 集群( 例如，i b ms p 2 )d i g i t a lv m s 集群h p u x 集群微软w o l f p a c k 集群2 2 集群上的作业管理2 2 i 集群作业管理系统概述集群作业管理系统作为使用户作业得以在系统资源上高效运行的媒介，或者说是工具，其担负着满足用户对作业执行的各种性能需求的重任，是整个集群管理软件的核心部分。把作业交付到一个对于用户来说近乎未知的分布式环境系统中，将会产生大量单机上作业执行不会遇到的难题，而且很多原来在单机中的问题一旦换成了多机的环境就会变得复杂。比如，可用的资源在哪里，这对于简单的单机环境来说不成问题，而在集群中就需要作业管理系统来从复杂且动态变化的集群环境中找到适合某个作业的7第二章集群和作业管理系统资源，还要使集群中各个作业不会因为互相干扰而减低系统性能，又要保持系统各处的负载平衡以获得更大的系统吞吐率，等等。这一切都促使作业管理系统的出现。一个作业管理系统主要由以下四部分构成f 1 2 】【1 3 】【1 4 j ：用户服务器：该服务器接纳用户提交的作业，获得每个作业的资源需求，响应用户的命令操作，如删除作业，查询作业或某些资源的状态信息。节点代理：作为集群管理软件的一部分，代表集群驻扎在一个节点上，设法通过与节点操作系统协作而发挥作用。负责接纳、执行、管理( 包括挂起、唤醒) 派到本节点上的作业，使之获得服务，并向资源管理器、作业调度器报告作业执行情况和节点状态。资源管理器：该管理器要对各种资源进行配置并对它们定位，监视各资源的状态。按照作业调度器的指示，把资源分配给某作业。把作业传送到目的节点并生成执行迸程后，还要设法使作业的各进程获得合理的调度，作业执行出了问题还要处理。最后要收集资源使用的记帐信息。作业调度器：该调度器根据作业类型、资源需求、资源可用性以及调度策略来执行作业调度与排队。一般作业调度器都把从用户服务器发来的作业组织成作业队列，每次处理一个作业的资源分配。一方面要决定优先调度哪些作业，即确定如何对各作业在作业队列中排列；另一方面，对本次欲处理的作业，按照作业附带的资源需求，并遵循其他方面的调度策略，负责把合乎要求的资源分配给某作业1 1 5 】。作业管理系统基本的实现结构是客户一服务器模型，即作业管理系统的各功能部件都是作为后台进程( 也称守护进程) 而出现。用户通过客户端程序与作业管理系统的服务器进行交互，提交作业并等待结果的返回【i 酬。一般来说，作业管理应该集中进行，即整个系统只有一个中央作业管理服务器( 不算冗余的应急系统) 。这样有利于对集群进行统一地管理，能够从全局的高度优化作业的调度。但是也有集群系统拥有多个作业管理部件，每个作业管理服务器只为处于某一位置范围内的部分用户的作业提供服务，甚至可以在每个用户可以用来登录集群的节点上都有一个作业管理服务器。这样做有助于避免因为集群规模扩大导致中央服务器不堪负重、性能降低。无疑，这就意味着作业管理系统的信息是不全面的，只能在有限的范围内进行一般优化的调度决策，否则为了获取全面的系统信息会给集群网络带来过大的负载，同样影响性能。作业在到达执行节点后，往往要建立类似于相应的工作目录等事关运行的环境，8中国石油大学( 华东) 硕十学位论文并创建管理此作业的服务进程和执行作业本身的各进程【1 7 1 。此外在每个作业执行之前和之后分别要运行管理者的一个开场程序和收尾程序，它们主要负责安全性检查、记帐和清除关于此作业的所有进程。最后一点很重要，因为如果不能很“干净”地清理用户的进程，会在系统中留下一些“孤儿 进程，导致许多集群资源的浪费，最终使系统变得不可用。2 2 2 评价集群作业管理系统的指标一个好的集群作业管理系统应该要尽量提高系统资源的利用率、吞吐率、减小作业平均等待时间和平均响应时间【1 8 】【1 9 】【2 0 1 1 2 1 1 。系统资源利用率：从系统的角度来看，集群系统的资源利用率是最重要的问题。系统资源利用率越高，说明系统吞吐能力( t h r o u g h p u t ) 越大，资源共享的效果也越好。高吞吐能力计算( h i g h - t h r o u g h p u tc o m p u t i n g ) 的目标就是充分有效的利用集群系统中的所有资源，达到更高的总体性能。系统吞吐率：其定义为系统在单位时间内所处理的作业数。如果每次只执行一个作业，那么吞吐率就是时间的倒数。在许多情况下，系统的吞吐率可以用下面两个方法加以提高：( 1 ) 设法流水线化。在几个流水线级上连续的作业重复它们的执行。此时的吞吐率便是在最长的流水级上执行时间的倒数。( 2 ) 设法为每个结点分配一个分离的或可以并行的作业，这样n 个作业就可在n 个结点上同时处理。平均响应时间：就是作业完成结束的时间减去作业递交到系统的时间，求出所有作业响应时间的平均值即作为平均响应时间。对于用户来说，作业的平均响应时间是最重要的。平均等待时间：就是作业开始运行的时间与递交到系统的时间差，即作业在队列中等待运行的时问。求出所有作业等待时间的平均值作为平均等待时间。平均减速：减速定义为作业的w a i tt i m e 时间与它使用的c p u 时间( c p ut i m e ) 的比值，、jw a i tt i m e 为作业运行时间、队列等待时间和迁移时间等的总和。作业的减速主要来自于c p u 队列的等待时间、内存页故障的调页时间、进程通信时间以及进程迁移的开销等因素。平均减速为所有作业减速的平均值。9第二章集群和作业管理系统2 2 3 典型的作业管理系统作业管理系统涉及多个概念和术语，下面就这些概念和术语作简单的说明。作业f 2 2 1 ( j o b ) ：作业是个会话组( 一个会话组是一进程，会话组的成员进程不能脱离会话组而存在) ，在操作系统上作业是一个s h e l l 语言程序，由系统的命令解释器加载执行。在作业管理系统中，作业是系统管理的基本单位，它与普通s h e l l 语言程序的不同之处在于增加了作业属性定义。交互式( i n t e r a c t i o n ) ：用户登录到操作系统，在一定的用户环境( 如环境变量、当前目录等) 中运行作业，作业在执行过程中，可能需要用户提供控制台输入，用户也可以及时查看控制台的输出，这种运行作业的方式称交互式。批处理( b a t c hp r o c e s s i n g ) ：由操作系统上的一个子系统而不是由用户使用交互式的会话过程运行作业的方式，称为批处理，这种子系统称为批处理服务器。批处理系统( b a t c hs y s t e m ) ：多台安装有批处理服务器的主机，通过网络连接共同完成网络中的批处理作业，并被作为一个整体进行配置、管理，就形成批处理系统。作业管理系统就是一个复杂的批处理系统，它除了能以批处理的方式运行作业外，还能对作业调度、作业对资源的竞争、系统的负载等进行全面控制。队y l j ( q u e u e ) ：批处理系统中设置的一种基本的作业分类机制，它将不同属性的作业分成不同的集合，作业的属性与所参加队列的属性要求不能矛盾。队列属性有名称、优先级、资源限制、目标机器和作业个数限制等。并行作业( p a r a l l e lj o b ) ：一个程序投入运行后，拥有多个并发运行的进程分别驻留在不同的处理器上，并且进程相互通讯完成数据交换，这样的程序称为并行程序。并行程序在作业管理系统中形成的作业称为并行作业。目前的几十种集群作业管理系统反映了集群作业管理系统所应具备的特性。n q s 、p b s 、c o n d o r 、l s f 、l o a d l e v e l e r 是当今颇具代表性和影响力的几种集群作业管理系统。其中p b s 、c o n d o r 是研究产品，l s f 、l o a d l e v e l e r 是商业软件。下面，我们对这几种作业管理系统进行简单介绍和讨论。( 1 ) n q s 2 3 】 2 4 】 2 5 1n q s 由n a s a 的a m e s 研究中心研发，其最初的目的在于对其c r a y 2 和c r a yy m p并行处理机资源进行有效的管理。它本质上是一个批调度系统。从1 9 8 6 年n q s 开发完成至今，n q s 在高性能计算领域已经得到了广泛的应用，并成为了批处理作业管理软件的事实上的标准。根据n q s 的使用经验，工业界制定了p o s i x1 0 0 3 2 d 批处理1 0中国石油大学( 华东) 硕士学位论文标准。在c r a y 系统中，n q s 试图优化两种资源的利用率：内存和c p u 计算时间。已经提交的作业必须声明其内存和c p u 的限制。作业根据这些限制分类，每个不同的类别使用单独的队列进行管理。作业调度器从不同的队列中选择作业以形成合适的运行作业集合。例如，表2 1 给出了n a s 的一个管理1 2 8 节点集群的n q s 的队列配置f 2 5 2 6 ：表2 - 1n a s1 2 8 节点集群的n q s 队列配置t a b l e 2 1t h ec o n f i g eo fn q sq u e u eo fc l u s t e rw i t h1 2 8n o d e sb a s e do nn a s管理的节点数时间限制1 63 26 41 2 82 0 分钟q 1 6 sq 3 2 sq 6 4 sq 1 2 8 s1 小时q 1 6 mq 3 2 mq 6 4 mq 1 2 8 m3 小时q 1 6 iq 3 2 1q 6 4 1q 1 2 8 1其中由4 个可用的分区大小和3 个时间限制形成了共1 2 个队列。批作业调度器将使用这些限制来对不同要求的作业进行调度。为了支持不同的作业负载，管理员可以选择激活其中的某些队列来实现。例如，系统刚开始运行时可以只使用q 1 6 s 、q 1 6 m 、q 3 2 s 、q 3 2 m ，这样可以有效的将执行的作业限制为1 小时内，需要最大节点数不超过3 2 个。其他更大的作业被放入其他队列中，到夜间激活这些队列开始执行这些大作业。由于n q s 的有效调度取决于特定的作业分类，从而给用户带来了更多的负担，即用户必须了解n q s 提供的队列的详细信息。另外，当需要考虑其他附加资源的情况时，如大容量存储介质的使用、内存的需求等，就需要管理员提供更为复杂的队列配置，这些对用户的使用和系统的管理都带来了负担。近年以来，n q s 的局限性变得越来越明显，其主要局限性在于缺少系统管理员优化系统和提供特殊服务控制的机制，所以管理员能做的只是使用各种优先级和资源限制来配置不同的队列。这推动了人们开发功能更为强大的资源管理系统，使其能提供更为有效的调度策略。( 2 ) l s f 2 7 】l s f 是由加拿大平台公司( p l a t f o r mc o m p u t i n gc o r p o r a t i o n ) 开发的分布式作业管理系统和调度系统商用软件包【5 1 。它的主要部分包括：第二章集群和作业管理系统l s fs t a n d a r de d i t i o n ：s t a n d a r de d i t i o n 是所有l s f 产品的基础。它支持分布式u n i x 和w i n d o w sn t 计算环境，为用户提供负载共享和复杂的批处理作业调度功能。l s fa n a l y z e r - 提供整个计算机群计算资源的全面负载分析，并生成记账报告，系统管理员可以根据报告状态做出正确的决定以清除瓶颈现象，提高整个系统的性能。l s fm u l t i c l u s t e r ：支持广域网中多个计算机群之间的资源共享，它把l s fs u i t e的优势扩展到整个企业，同时又保证资源的所有权和计算机群的自治权。l s fj o b s c h e d u l e r ：提供基于服务器组的，由日历或者事件驱动的作业调度功能，其高可靠性及可扩展性保证了日常数据处理任务的顺利完成。l s fm a k e ：是一个以g n um a k e 为基础的分布式并行m a k e 软件，它能把作业同时提交到多个主机上，从而大大减少了作业运行时间。l s fp a r a l l e l ：允许将一个大型计算任务分发到多个c p u 和主机。l s fp a r a l l e l 确保并行作业执行时所有相关c p u 及主机都能达到负载平衡，从而保证了优化的性能和网络的吞吐量。和n q s 相比，l s f 主要有一下特点【2 8 】：1 ) 更复杂的批处理调度：l s f 标准版套件包括两个产品i ，s fb a s e 和l s fb a t c h 。l s fb a s e 提供分布式异构计算环境的单一映像系统，并支持动态负载共享。l s fb a t c h 根据作业、主机和队列状态，按照作业的需求和系统的负载情况对作业进行调度。2 ) 更为灵活的队列和共享控制：l s f 提供了对作业的优先级、作业调度负载、作业运行时间、作业运行数和作业使用资源限制的配置。3 ) 批处理作业的可靠断点检测和进程迁移：如果一个作业失败或停止，l s fb a t c h 能够保证作业从断点上恢复并在网络中的其他机器上继续进行。l s f 提供内核、库函数及应用程序等三种断点检测手段以支持作业的断点检测及迁移。4 ) 提供批处理a p i 以支持应用开发：l s f 标准套件提供l s b l i b c 应用程序接口( a p i ) ，内容包括作业、队列、主机的操作，系统管理及作业事件处理。另外一个l s f a p i l s l i b 可与l s b l i b 配合使用。( 3 ) c o n d o r t 2 9 】c o n d o r ( c o m p u t i n gi nd i s t r i b u t i n gn e t w o r k e de n v i r o n m e n t s ) 是由威斯康星大学开发的集群作业管理系统，充分利用工作站的空闲时间是c o n d o r 的最显著特征。1 2中国石油大学( 华东) 硕士学位论文c o n d o r 管理的集群由网络中的工作站组成，工作站主人可以自愿加入或退出。c o n d o r 监测网络中所有工作站的状态，一旦某台计算机被认为空闲，便把它纳入到资源池( p o o l ) 中，在资源池中的工作站被用来执行作业。当工作站的主人开始使用该工作站时，c o n d o r 便将运行在该工作站上的作业迁移到其它结点上继续运行，从而避免了对工作站主人的影响。所有这些特征并不需要修改底层的u n i x 操作系统核心，只需在用户级进行，而且不需修改用户程序，只需与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 ) l o a d l e v e l e rl o a d l e v e l e r 1 7 1 是i b m 开发的集群管理系统。它成功地运行在i b ms p 2 集群系统上。l o a d l e v e l e r 允许用户在同构或者异构的集群系统中提交交互式批处理作业。除了i b ma i x 操作系统外，它还支持h p u x 、s g ii r i x 、s u n o s 和s o l a r i s等主流u n i x 平台。在教育、研究机构、企业等各行各业，l o a d l e v e l e r 以其灵活高效的特点得以广泛应用，例如大规模的仿真、资源的优化利用、天气预报、底层模拟、经济分析等。l o a d l e v e l e r 的主要特点是；支持并行串行、交互式批处理作业；对工作站主人的影响小；可定义作业类，优化调度；具有较好的系统可用性；系统中心控制：完整的文档；分布的用户服务器；提供完整的a p i ；与n q s 兼容。( 5 ) p b sp b s 最初由n a s a 的a m e s 研究中心开发，为了提供一个能满足异构计算网络需要的软件包，特别是满足高性能计算的需要。它力求提供对批处理的初始化和调度执行的控制，允许作业在不同主机间的路由。p b s 的独立的调度模块允许系统管理员定义资源和每个作业可使用的数量。调度模块存有各个可用的排队作业、运行作业和系统资源使用状况的信息。p b s 提供了t c l ，b a c l ，c 三种过程语言，它的调度策略可以很容易被修改，以适应不同的计算需要和目标，即系统管理员可以方便地实现自己的调度策略。p b s 的主要特点有：代码开放，免费获取；支持批处理、交互式作业和串行、多第二章集群和作业管理系统种并行作业，如m p i ，p v m ，h p f ，m p l ；提供t c l ，b a c l ，c 三种过程语言，容易实现新的调度策略；提供文件传送功能，f i l es t a g e i n 和s t a g e o u t ；满足p o s i x l 0 0 3 2 d标准；完整的安全认证；提供了完整的a p i ，方便新的调度器的开发：提供用户影像功能，使p b s 能用于用户不一致的系统中，在下一节中将会对它进行详细的论述分析。2 3p b s 系统2 3 。lp b s 作业管理系统概述近年来得到广泛使用的集群系统具有低成本、高性能的特性，提供了强大的批处理和并行计算能力。作为集群系统的重要组成部分，集群作业管理系统可以统一管理和调度各种软硬件资源，保证用户公平合理地使用集群系统，从而提高整个系统的利用率。通用批作业处理系统p b s 是目前已有的集群作业管理系统中颇具代表性和影响力的一种， 醌n a s a 在n q s 的基础上开发的【3 0 1 ，以完善和增强n q s 的作业管理功能。它提供了一个能满足异构计算网络需要的软件包，特别是能满足高性能计算的需要。当前，p b s 常用的版本有o p e n p b s 和p b s p r o ，其中o p e n p b s 是完全开源，p b s p r o 是商业版本。p b s 与之前的n q s 相比有以下特点：1 ) 基于t c y t k 的跨平台的图形用户界面；2 ) 对批作业和交互式作业的管理支持；3 ) 提供了用m p i p v m 实现的并行作业的支持；4 ) 提供了灵活的作业调度策略的接口；5 ) 批处理作业的可靠断点检测功能；6 ) 对具有依赖性的作业集进行处理的支持：7 ) 提供了各种a p l 支持应用的开发；8 ) p b s 提供了符合p o s i x1 0 0 3 2 d 标准的命令行管理工具，n q s 的用户仍能使用习惯的命令对其作业进行管理。由于p b s 提供了全面的作业管理功能，以及它对各种l i n u x 和u n i x 的免费支持，p b s 已经在高性能环境中得到了广泛的应用。下面将对其进行详细的说明。2 3 2p b s 作业管理的体系结构从整体上来看，p b s 主要有三大模块【3 1 1 1 3 2 1 构成，它们分别是p b s _ - s e r 、，e r 、p b s _ s c h e d 、p b s，其中，是整个管理系统的核心部分，负责接收各种外部请求、实现m o mp b ss e r v e r对资源的监测、分配和管理；p b sm o m 主要是进行资源的探测，并反馈给p b ss e r v e r ，同1 4中国石油大学