（计算机软件与理论专业论文）基于预测的集群作业资源管理研究.pdf

华中科技大学硕士学位论文 摘要 预测技术被广泛地应用于生活的各个领域，如气象领域，经济领域，商业领域， 地理领域等。它的使用与发展使得人们可以对未来一段时间内事物的发展趋势有一个 较明确的掌握和理解，从而可以指导大家在下一阶段的生活和工作安排。具有极大的 现实意义。 在计算机领域中，对计算机运行预测的研究也越来越广泛。现有的资源预测技术 中，各种不同的资源预测算法各有优缺点，适应于不同的资源运行情况。出于资源运 行情况的多样性，设计出一种能够对所有的情况准确预测的算法是不现实的。一种将 所有预测算法糅合在一起的自适应算法提供了这样一种思路：整合现有大多数资源预 测算法，采用一定的选择策略，针对不同的应用环境使用不同的预测算法进行预测。 该算法目的是通过将各种算法整合使得它们的优势充分发挥出来，避免用单一的一种 算法对所有运行情况进行预测。 集群资源管理系统作为集群系统的一个重要组成部分，其目的是将系统分散的资 源整合起来，为用户提供一个单一的系统映像。它直接关系到集群性能的发挥和使用 率的提高。 现有的作业和资源管理系统普遍采用传统的c s ( 服务器客户端) 模式，在资源 的信息获取方面只考虑资源的当前情况，从而导致在对作业调度和资源管理的策略定 制时也就围绕着资源的当前情况进行。调度的作业是在“未来”运行的，负载平衡考 虑的是“未来”的平衡，利用当前的信息来衡量未来的情况，这样做的不足是显而易 见的。为此，将上述资源预测技术应用于作业资源管理系统，设计基于b s ( 浏览器 服务器) 模式的带有预测信息的资源管理系统是必需的。预测系统经过长时间的性能 测试，与现有的主流的几个单一的预测算法进行了对比，给出了定性和定量的分析。 在此平台的基础上，基于预测信息的作业调度和资源管理策略的分析和研究为系统资 源的有效利用和性能的提高提供了新的思路。 关键词：预测，资源预测，自适应预测算法，作业和资源管理 华中科技大学硕士学位论文 a b s t r a c t t h ep r e d i c t i o nt e c h n o l o g yi s w i d e l yu s e di ne v e r yf i e l di no u rf i f e ，s u c ha st h ei n w e a t h e rf i e l d , t h eb u s i n e s sf i e l d ，a n dt h eg e o g r a p h yf i e l d t h eu s ea n dd e v e l o p m e n to f p r e d i c t i o nt e c h n o l o g ym a k ei tp o s s i b l ef o rp e o p l et om a s t e rt h et r e n do ft h et h i n g si nt h e f u t u r et i m e a n ds op e o p l ec a n a r r a n g et h e i rl i f ea n dw o r kt h r o u g ht h ef o r e c a s ti n f o r m a t i o n i nt h ec o m p u t e rs c i e n c ef i e l d ，t h ep r e d i c t i o nt e c h n o l o g yi sa l s ow i d e l yu s e da n dm o r e a n dm o r er e s e a r c hi sm a d eo ni t t h ec u r r e n tv a r i e so fr c s o b r c ep r e d i c tt e c h n o l o g i e sh a v e t h e i ro w nm e r i ta n dd e m e r i tw h i c ha r cf i tf o rd i f f e r e n tt y p eo f c o n d i t i o n s t h e o r e t i c a l l y ，i ti s i m p o s s i b l e t o d e s i g n s u c ha na r i t h m e t i ct h a tc a na c c u r a t e l y p r e d i c t a l lt h e r u n n i n g c i r c u m s t a n c e an e wa r i t h m e t i co fr e s o u r c e p r e d i c t i n gt e c h n o l o g y w h i c hw ec a l l s e l f - a d a p t i n g r e s o u r c ep r e d i c t i n ga r i t h m e t i ct a k e sa l lt h ep o p u l a ra r i t h r a e t i ct o g e t h e rs h o w s t h i n k i n gl i k et h a t ：w em a yc o n g r e g a t ea l lt h ec u r r e n ta r i t h m e t i ct o g e t h e r ，a d o i p ts o m e k i n do f s e l e c t i o np o l i c y ，a n du s et h ed i f f e r e n ta r i t h m e t i ct op r e d i c tt h er e s o u r c eu t i l i z a t i o nu n d e r d i f f e r e n tc i r c u m s t a n c e s t h i sa r i t h m e t i ci sa i m e dt op u tl o to fa r i t h m e t i ct o g e t h e rs ot h a ti t m a y h a v ea l lt h ec t l r r e n ta r i t h m e t i c sa d v a n t a g e s oi ta v o i d su s i n go n ek i n do fa r i t h m e t i ct o p r e d i c t a l lo f t h e r u n n i n gc i r c u m s t a n c e s t h e j o ba n d r e s o u r c em a n a g e m e n ts y s t e mi st h em o s ti m p o r t a n tp a r ti nt h ec l u s t e r i t a i m st oi n t e g r a t ea l lt h ed i s p e r s i v er e s o u r c e si na l lt h en o d e sa n dp r o v i d eas i n g i es y s t e m i m a g e t ot h eu s e r s i ti sh i g h l yr e l a t e dt ot h ep e r f o r m a n c eo f t h ec l u s t e r t h ec u r r e n tj o ba n dr e s o u r c em a n a g e m e n ts y s t e m sn o r m a l l ya d o p tt h et r a d i t i o n a lc s ( c l i e n t s e r v e r ) m o d e l ，a n dp a yt h e i ra t t e n t i o nt ot h ec u r r e n tr e s o u r c ei 岱o r m a t i o n w h e n m a k i n gt h e i rs c h e d u l i n ga n dl o a db a l a n c i n gp o l i c i e s i nd o i n gt h i s ，i ti so b v i o u s l yf a u l t e d b e c a u s et h ej o b ss c h e d u l e db yt h es y s t e ma r er u n n i n gi nt h e “f u t u r e ”a n dt h es y s t e m sl o a d b a l a n c ei st h e “f u t u r e s s y s t e m l o a db a l a n c e t h en e wk i n do f j o b r e s o u r c e m a n a g e m e n t s y s t e m sm u s t b ed e s i g n e dt ob em o r ec o n v e n i e n ta n ds i m p l ef o rt h eu s e r st ou s e ，a n ds u p p l y m o r es y s t e mi n f o r m a t i o nf o rt h ea d m i n i s t r a t o rt om a n a g e i no r d e rt od ot h i s ，t h es y s t e m 1 l 华中科技大学硕士学位论文 m a ya d o p tb sr b r o w s e r s e r v e r ) m o d e la n d u s et h ep r e d i c t i o nt e c h n o l o g yw et a l k e da b o u t a b o v e a r e ral o n gt i m eo fp r e d i c t i n gp e r f o r m a n c et e s t i n g ，t h e p e r f o r m a n c e o ft h e s e l f - a d a p t i n gp r e d i c t i n g a r i t h m e t i ci s a n a l y z e d a n dc o m p a r e dw i t l lt h e w i d e l y u s e d a r i t h m e t i cn o w a d a y s i ns u c has y s t e m ，f i 删h e r m o r e ，t h er e s o l l r c ep r e d i c t i o ni r f f o r m a t i o nc a n b eu s e dt om a k et h ep o l i c yo f j o bs c h e d u l i n ga n dr e s o u r c em a n a g e m e n t k e yw o r d s ：p r e d i c t i o n , r e s o u r g ep r e d i c t i o n ，s e l f - a d a p t i n g 姗b r g ep r e d i c t i n ga r i t h m e t i c ， j o ba n dr e s o u r c em a n a g e m e n t i i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 学位论文作者签名 去点卑 只期：2 a 3 a - 年年月g 同 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 奄阅和借阅：本人授权华中科技大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密留。 龇姒午躲勃i 刑? 同期：如冉年4 月g 日 同期：肿( 绢占甬 。 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 随着社会和科学技术的发展，应用的不断深入，人们对计算机运行速度和处理能力 的要求越来越高，越来越多的应用领域需要高性能计算机，如科学与工程计算、决策 支持和事务处理等商业计算、大型信息服务和网络服务、数字图书馆、生物信息处理 和视频媒体系统。 传统的终端主机的网络模式，终端功能简单，无需维护工作，在主机一端进行专 门的管理与维护，具有资源共享、便于管理的特点。但是其主机造价昂贵，终端没有 处理能力，限制了网络的规模化发展。之后的客户机服务器模式推进了计算产业的标 准化和开发化的发展，为系统提供了相当大的灵活性，但是随着分布系统规模的规模 扩大，给系统的维护和管理带来了巨大的开销。 在现有的集群系统中，处理器不再分布在各处，而是集中在一起进行统一管理和 维护。它保持了分布式客户机n 务器模式的开发性、可扩展性的优点，同时又具备了 终端主机模式的资源共享和集中易于管理的优点，成为了当今高性能计算机体系结构 和并行处理的发展方向。集群系统以其卓越的性能价格比和良好的可扩展性等因素成 为当今高性能计算机系统的主流体系结构。 随着越来越多的应用被移植到集群系统中，对集群系统的任务管理提出了更高的 要求和挑战。为满足科学计算和信息处理的需要，需要研究怎样将集群中分散的资源 整合起来，有效的管理各种资源并将之提供给用户使用；怎样满足用户的不同需求， 提供给用户易用，方便的单一系统映像。 本课题以国家高技术研究发展计划( 8 6 3 计划) ”软件重大专项”第一期课题 “集群服务器功能软件”研究为依托，对集群部分相关技术展开研究。其目的是为了 研制与服务器操作系统配套的具有自主知识产权的集群功能软件，支持高性能集群服 华中科技大学硕士学位论文 务器的构造。 课题研究的主要任务是根据集群处理作业的特征，充分利用集群的软硬件资源， 有效的管理集群，合理的调度作业，提高系统的利用率和吞吐率，重点研究集群环境 下的作业与资源管理技术，包括对系统的负载平衡技术、作业调度策略以及单系统映 像研究等方面。 1 2 国内外概况 i 2 1 集群作业资源管理 作业与资源管理提供用户和底层系统之间的一个中间平台，由它来对集群资源 进行统一管理，统一调度，屏蔽底层资源，在作业和资源之间寻找最佳匹配策略，管 理和调度作业的并行执行，从而提高系统的资源的利用效率。 一个典型的作业资源管理软件应有如下三个基本组成部分：用户服务器模块，资 源管理模块，作业调度模块。各部分的功能如下： 用户服务器：提供对作业的提交、删除和查询的单一入口点，并可以对提交的作 业信息状态进行查询，对系统相关信息进行了解。 资源管理模块：定义、分配、监控整个系统资源，定制执行资源分配和调度策略， 优化资源利用，收集完整的作业记账信息。 作业调度器：过与用户服务器的交互，获得作业信息，进行作业排队，通过与资 源管理器的交互，获得系统资源状态信息，通过一定的调度策略及作业信息、系统资 源状态信息，确定作业在何时何地运行。 此外，考虑到系统的可用性以及性能，一个完整的作业与资源管理系统还要包括： c h e c kp o i n t i n g 模块：存储和收回检查点信息。 负载平衡模块：支持动态负载平衡。 安全模块：该模块提供对用户使用系统的身份鉴别，确认和执行访问权限，对系 统模块之间的通信连接进行加密。 错误检测模块：对任何软件、硬件的错误进行检测以便进行及时的解决。 华中科技大学硕士学位论文 作业与资源管理技术提供了允许由管理部门进行结构化的资源利用规划与控制， 以抽象，透明、易于理解和易于使用的方式将计算中心的资源提供给用户，提供了一 个与生产商无关的用户界面。它首先被应用于高性能计算环境，主要用户中的大多数 是在研究中心。 国外比较成熟的几个集群系统全局资源管理软件包括s g e ( s u ng r i de n g i n e ) 、 l s f ( l o a ds h a r i n gf a c i l i t y ) 、p b s ( p o r t a b l eb a t c hs y s t e m ) 、g r d ( g l o b a lr e s o u r c e d i r e c t o r ) 、c o n d o r 和l o a d l e v e l e r ；国内比较成熟的几个集群系统全局资源管理软件 包括j o s s 和r m s ：j o s s ( 曙光集群作业管理系统) 是在d q s 基础上开发的曙光系列超 级服务器作业管理系统；p a l s ( 曙光集群资源管理系统) 。它们在目标、结构、功能和 实现上各有差异。1 ，从不同侧面反映了集群作业管理系统所应具备的特性。p b se ”、 c o n d o r “1 、l s f “3 、s g e 、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 p b s ( p o r t a b i eb a t o hs y s t e m ) p b s 最初由n a s a 的a m e s 研究中心开发，为了提供一个能满足异构计算网络需要 的软件包，特别是满足高性能计算的需要。它力求提供对批处理的初始化和调度执行 的控制，允许作业在不同主机问的路由。p b s 的独立的调度模块允许系统管理员定义 资源和每个作业可使用的数量。调度模块存有各个可用的排队作业、运行作业和系统 资源使用状况信息。使用它提供的t c l 、b a c l 、e 三种过程语言，它的调度策略可以很 容易被修改，以适应不同的计算需要和目标，即系统管理员可以方便地实现自己的调 度策略。 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 l s f ( l o a ds h a r i n gf a o fi t y ) 负载共享软件l s f 是由加拿大平台计算公司研制与开发的，由t o r o n t o 大学开发 的u t o p i a 系统发展而来。从强大的功能和广泛使用的角度看，l s f 可谓是一个成熟的 集群作业管理系统。在使用范围上，l s f 不仅用于科学计算，也用于企业的事务处理。 用户包括摩托罗拉、美国宇航局( n a s a ) 、休斯敦飞机公司、通用电气公司、斯坦福大 学等著名企业与科研团体。功能上，除了一般的作业管理特性外，它还在负载平衡、 系统容错、检查点操作、进程迁移等方面作了很好的努力，并力图使之实用化。 l s f 的主要特点是：支持多种操作系统，包括n t 和w i n 2 0 0 0 ：支持检查点操作( 核 心级、用户级及应用程序级) 和进程迁移；具有高可用性，消除单一故障点；提供了 抢占式调度和关键资源保障，保证紧急作业的调度；可通过逻辑表达式创建作业依赖 图，提供对依赖性作业的支持；提供了多种调度策略，包括r e s e r v a t i o n 和b a c k f i l l ； 动态的负载平衡与负载监测，负载指标包括节点状态、运行队列长度、c p u 利用率、 分页速率、登录用户数、空闲时间、可用交换空间、可用存贮器、t m p 目录下的可用 空间；提供了完整的负载共享库；具有强大的资源管理功能。 3 l o a d l e v e l e r l o a d l e v e l e r 是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 no 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 兼容。 4 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 华中科技大学硕士学位论文 以自愿加入或退出。c o n d o r 监测网络中所有工作站的状态，一旦某台计算机被认为空 闲，便把它纳入到资源池( p o o l ) 中。1 。在资源池中的工作站被用来执行作业。当工 作站的主人开始使用该工作站时，c o n d o r 便将运行在该工作站上的作业迁移至q 其它节 点上继续运行，从而避免了对工作站主人的影响。所有这些特征并不需要修改底层的 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 作业所 占用；对网络资源、数据传送和检查点操作的有效监控：对网络资源、c p u 的协同调 度。 5 曙光集群作业管理系统j o s s j o s s 。1 是中科院在d q s 基础上开发的曙光系列超级服务器集群作业管理系统。它 成功地运行在曙光天潮系列超级服务器上。它具有d q s 所具有的特点，同时又根据曙 光超级服务器的体系结构和软件平台加以改造，具有一些新的特点。图1 1 是j o s s 的系统结构图。 图1 1j o s s 系统的拓扑结构 抽筋结点 华中科技大学硕士学位论文 j o s s 由两个守护进程组成。“：m a s t e r d 和e x e c d ，它们负责为系统的运作提供最 根本的支持，是整个系统的核心。运行m a s t e r d 的节点称为主节点，运行e x e c d 的节 点称为计算或执行节点。系统中只有一个主节点，但可同时由多个执行节点。以上是 逻辑上的概念。在物理上，m a s t e r d 和e x e c d 可存在于同一个节点上。从图1 1 中可 以看出，m a s t e r d 用来接受用户的各种请求，并调度作业，管理系统资源。它维护着 整个系统的关键配置信息和两种队列：作业队列和节点队列。作业队列存放用户已提 交的各个作业的信息，节点队列存放各个执行节点的资源信息。l a s t e r d 还负责作业 的调度和执行节点的选取，根据一定的作业调度策略选取作业和节点，将执行作业的 命令发送给e x e c d 。e x e c d 用来接收m a s t e r d 执行作业的命令，将作业投入运行。同时 监控作业的运行状态和资源使用情况，向m a s t e r d 报告，还定期报告节点的负载信息。 1 2 2 资源预测 预测技术被广泛地应用于生活的各个领域，如气象领域，经济领域，商业领域， 地理领域等。它的使用与发展使得人们可以对未来一段时间内事物的发展趋势有一个 较明确的掌握和理解，从而可以指导大家在下一阶段的生活和工作安排，具有极大的 现实意义。 在对现有作业资源管理软件的分析与研究中“2 ”1 ，可以发现目前的作业资源管理 软件在对集群内节点的资源信息收集与处理以及在对作业调度和资源管理定制策略 时，只是考虑到作业提交当时的资源情况，对整个系统的了解也是停留在对整个系统 历史和当前的资源使用情况，而对整个系统未来一段时间内的资源利用情况以及将会 发生的状况没有一定的分析和估计，从而可能导致对系统出现意外的未知。 对系统整个进行资源使用的预测是有必要的，通过对系统各个节点在过去一段时 间内的资源利用情况分析，利用科学的数值分析与统计，得出系统各个节点在未来一 段时间内的大致使用情况，对于整个系统的资源管理监控以及对于作业的调度策略改 进都是具有极大的意义。 预测分为面向应用程序的预测( a p p l i c a t i o n o r i e n t e d ) 和面向资源的预测 ( r e s o u r c e o r i e n t e d ) 两种。前者使用先前运行过的类似的应用程序性能来直接对本 华中科技大学硕士学位论文 应用程序进行预测；后者则是用过去一段时间内资源的可用性信息来预测未来一段时 间内的资源可用性，预测信息和任务的资源需求信息被用来估计作业的性能。面向应 用程序的预测( a p p l i c a t i o n o r i e n t e d ) 其基本思想是对各种应用程序类型进行分类， 把程序按照各种分类做成相应的模板，每当要对一个程序进行性能预测时，就会对其 进行相关的匹配，按照相应模板的历史运行性能对其进行模拟。由于应用程序的多样 性以及复杂性，对程序本身进行预测的预测技术在设计和实现上难度很大。而面向资 源的预测( r e s o u r c e o r i e n t e d ) 则只是对机子本身资源利用率的统计分析和预测，便 于统一，有很好的度量标准，因此应用和研究很广泛。现有的不同资源预测软件分别 对以上预测形式都有体现。 对资源预测的研究国外很早就开始进行了，但在国内目前还没有专门的机构进行 研究。国外知名的资源预测软件主要有r p s 和n w s 两种，它们的设计思想和算法都各 有特色，下面对这两个软件逐一进行介绍。 1 r p s ( r e s o u r c ep r e d i c t j o ni nd ls t r i b u t e ds y s t e m s ) r p s “1 是由美国西北大学计算机科学系p r e s c i e n c el a b 的p e t e ra d i n d a 组织 开发的。英文全称是p r e s c i e n c el a bd e p a r t m e n to fc o m p u t e rs c i e n c en o r t h w e s t e r n u n i v e r s i t y 。它是一个可扩展的，设计，搭建，评价系统的工具软件，能够预测分布 式系统内资源的动态表现。其核心代码由c 十+ 语言写成，可移植性好。在r p s 中包括 了下列的组件“川： ( 1 )测量系统负载，网络带宽，1i n u x p r o c 文件系统数据和w i n d o w s 性能计数 的探测器和数据库； ( 2 )一个保存和分析预测时间序列数据的预测工具和数据库。它支持包括 m e a n ，l a s t ，b e s t m e a n ，b e s t m e a n ，n e w t o n ，a r ，m a ，a r m a ，a r i m a i 等预测算法模块。 任何模块可以用一个管理模板进行包装嵌入： ( 3 )一个对时间序列数据的基于w a v e l e t b a s e d 分析和重建的工具和数据库， 1 a r ，m a ，a r m a ，a r i m a ：分别表示自回归模型滑动回归模型，自回归滑动平均模型，求和自回归滑动平 均模型这些都是数学上用于预报的控制和非控制的模型。 华中科技大学硕士学位论文 利用该工具可以进行不同类别的配置； ( 4 )一个使得搭建预测组件很容易的通讯模板； ( 5 ) 可实时连接和配置的一套预测组件，可形成在线预测和微波分析系统。 除此之外，r p s 提供了图形化的显示工具，提供了基于j a v a 的显示实测值和预测 值的工具。提供了完整的文档和一个w e b 接口。在该软件中采用了a r ，a r a m 等等算法。 2 n w s ( n e t w o r kw e a t h e rs e r vic e ) n w s 。“”3 是指是由u c s b 发起，联合n s f ，n p a c i 合作研发的，( 注；n s f ：n a t i o n a l s c i e n c ef o u n d a t i o n ，n p a c i ：n a t i o n a lp a r t n e r s h i pf o ra d v a n c e dc o m d u t a t i o n a l i n f r a s t r u c t u r e 和加利福尼亚大学u n i v e r s i t yo fc a l i f o r n i as a n t ab a r b a r a ) 。 n w s 采用分布式结构。“1 ，其结构如图1 2 所示。n w s 系统包括了四个主要的组件： ( 1 )命名服务器n a m es e r v e r 以目录模式保存了主机注册，对象数据和进程等 信息； ( 2 )存储服务器m e m o r ys e r v e r 也叫( p e r s i s t e n ts t a t e ) 保存了从其他组件 收集的测量数据； 能。 图1 2n w s 结构图 ( 3 )信息收集器s e n s o rh o s t 收集从特定主机上已经定义的资源； ( 4 ) 预测主机f o r e c a s t e rh o s t 分析收集来的数据并预测特定时间段内的性 华中科技大学硕士学位论文 n w s 可以对c p u 资源，内存资源，网络带宽资源等进行预测。“4 ，而对网络资源 的预测是其特色，在预测方法的选择上采用了均值和中值算法等”“2 ”。 由于网络资源作为计算的重要资源越来越受到重视，其性能直接影响到在作业处 理过程中的传输速度，响应时间等等，因此对它的预测研究也同样具有积极的意义。 在应用方面n w s 取得了很好的成效，被a p p l e s ”系统所引用，并且被用于g l o b u s 和 g g f ，g i s 体系中2 。 1 3 课题主要研究工作 现有的资源预测算法各有特色，有其各自适用的不同的运行环境。而在现实的系 统中，资源的使用情况是千差万别的，用一种预测函数来对所有的资源利用情况来进 行预测有其极大的局限性。 传统的集群资源管理软件采用客户机n 务器模式，用户需要下载其客户端软件与 服务器通信，进行交互；在系统资源的管理上，其管理信息一般局限于对集群现有资 源信息及负载的了解上，而对整个系统未来一段时间内的负载信息却没有相应的了解； 在调度方面，多是基于对现有资源的了解基础上进行的。而对于集群这样一个庞大的 资源系统而言，对某一个提交的应用程序，其满足条件的资源配置会有很多，应用程 序在其上的运行也是有差异的，现有系统却忽略其区别。 针对上述问题，本课题首先对系统资源的预测进行研究，通过系统的分析现有的 各主流预测算法，研究设计新的资源预测算法，并将其实现为独立的系统；其次在分 析现有的作业资源管理软件基础上，针对其不足提出新的作业资源管理系统模型，改 进原有系统的平台模式，使得用户使用简单化，系统维护方便合理：引入资源预测技 术，全面了解系统的资源利用的信息状况：尝试基于预测的调度的研究，选择最适合 作业运行的节点。 具体而言，本课题主要拟进行以下工作： 2 o g f ：g l o b l dg r i df o r u m 全球网格论坛 o i s ：g r i di n f o r m m i o ns y s t e m 网格信息系统 华中科技大学硕士学位论文 1 分析现有的资源预测算法，并对各种算法的有缺点进行分析评价； 2 设计新的整合预测算法一一自适应预测算法，该算法要能够通过整合现有的各 种主流预测算法，扬长避短； 3 将自适应预测算法实现，应能够取得比单一预测算法更高的预测精确度； 4 针对现有的作业与资源管理系统的不足，提出并实现新的作业资源管理系统， 系统能够提供用户很好的交互平台； 5 将资源预测技术引入作业资源管理系统，使得系统信息更为全面； 6 在此作业资源管理系统的基础上进行基于预测信息的作业调度与资源管理策 略研究。 1 4 论文的内容以及组织 本课题详细的介绍了一种新型的资源管理技术一一资源预测技术，分析了目前 主流的各种资源预测算法的优缺点，并在此基础上做出改进；并将其运用于一个高级 的作业与资源管理系统，优化整个系统的设计，使得系统具有更全面的功能和更多的 调度方案选择；最后给出了预测数据分析并对课题的发展方向做出了建议。在此系统 上实现一个更为积极的调度策略以优化资源的利用和减少作业的响应时间环境。 本文共分六章。 第一章介绍了课题的来源，目的意义以及国内外研究现状； 第二章介绍了新的资源分析监测技术一资源预测技术，并对当前的资源预测算 法进行了详述，并分析评价了各种算法的优缺点； 第三章在总结第二章的基础上提出了自适应的资源预测算法，描写了算法的理论 分析和具体实现； 第四章针对现有的作业与资源管理系统的不足，提出了新的作业资源管理系统体 系结构，并在其中引入了资源预测技术以及预测技术的应用； 第五章对资源预测进行了性能评价并给出预测曲线图以及性能参数分析； 第六章对本课题进行了展望和总结。 i o 华中科技大学硕士学位论文 2 资源预测 在进行本章的描述之前，先介绍一些相关的术语。 时间序列，指按照时间顺序取得的一系列观察值，现实中很多数据是以时间序列 的形式出现的，如月产量，周劳动强度等等。时间序列的一个典型特征就是相邻观察 值的依赖性，而预测就是对这种依赖性的分析。 预测，就是在分析和统计了过去一段时间内对象随时间的变化情况后，估算其下 一时间段内的走势。其主要是依据数理统计原理乜毗进行一种科学的推理和判断。预测 技术被广泛的应用于各个科学领域。 资源预测，就是以计算机资源为对象，将资源随着时间的顺序所得的观察值定义 为时间序列，通过分析该时间序列，采用数理统计的方法对下一时间段内的可能资源 情况进行估计和评测。在这里本文中所讲的计算机资源是指内存，c p u ，硬盘以及网络 这些对于作业处理有重要影响的计算资源，它们在很大程度上决定了用户所提交作业 在集群系统内的处理速度啪1 。 2 1 理论模型 用数学方式定义预测，就是利用一个时间序列在t 时刻的有效观察值预报未来某 个t + n 时刻的该序列的观察值。下面用一个数学模型( 2 1 ) 来说明这一过程： p r e d i c t i o n ，( f ) = m e t h o d ，( v a l u e ( f ) ，h i s t o r y ，( f ) ) ( 2 1 ) 其中 v a l u e ( t ) 一t 时刻测到的数值； p r e d i c t i o n ，( t )一由预测函数f 为t + 1 时刻预测到的数值； h i s t o r y i ( r ) 一使用函数f 预测到的t 时刻的值，或者t 时刻测量到的 数值： m e t h o d ， 一一预测函数f 。 华中科技大学硕士学位论文 预测函数的定义域就是时间序列，它是由一个由数值和时间组成的序列对，例如 ( 8 0 ，1 0 ) 、( 8 2 ，2 0 ) 、( 8 5 ，3 0 ) 分别表示在t = 0 t = 1 0 时间段，其性能统计值为8 0 ， t = 1 0 t = 2 0 的时间段统计值为8 2 ，t = 2 0 t = 3 0 时间段内性能值为8 5 ，以此类推。预测 函数的值域与定义域一样，也是由数值和时间组成的序列对，但表达的意义不一样， 如( 8 3 ，4 0 ) 表示该函数预测，在下一时间段t = 4 0 t = 5 0 内，该性能值为8 3 。 预测的精确性描述用数学表达如式( 2 2 ) ： p 盯，o ) = v a l u e ( t ) 一p r e d i c t i o n ，( f 一1 )( 2 2 ) 它表示在t 时刻所测得的实际数值和先前由函数f 预测到的数值之间的差值，这 实际上是一个评价标准，它的值越小说明预测越精确。 以上的数学模型说明了预测的一般模式，可以看到问题的关键是函数f 的选取， 它关系到预测的准确性和成功与否。以下就是几种常见的预测函数类型。 2 2 平均值算法 由统计学的知识，大家自然而然的想到的第一个预测函数就是算术平均运算函数， 而实际上这类预测函数也已经出现，就是使用平均值作为预测值的预测算法 ( m e a n b a s e dm e t h o d ) 。下面就是最简单的均值算法。 1 均值算法( r u n n i n ga v e r a g em e t h o d ) 该函数使用过去一段时间内的平均值作为下一个测量值的预测值，其数学定义如 公式( 2 3 ) 所示： r u n 一彳粥( f ) = 击 ( f ) ( 2 3 ) v a l u e 。r 1 一 具体是指，在t 时刻所测得的值和t 以前所有的测量值的平均值作为t + 1 时刻韵 预测值。 用r u n _ a v g 函数作预测，它考虑用整个测量的历史记录来做预测，这样给每个测 量值的权值就会随着时间增大而逐渐降低。其不足是显而易见的，在历史数据越来越 多的情况下，尤其是在资源利用情况起伏比较大的情况下，很多较久的历史信息就不 华中科技大学硕士学位论文 能真实的反应目前的资源状况。而在这是，只有最近的一些测量值才能很好的预测下 一个时间段内的资源运行情况e 出于这种考虑，出现了由均值算法改进而得的滑动窗 口算法。 2 滑动窗口均值算法( s i d i n gw i n d o wa v e r a g em e t h o d ) 针对上述算法的不足，s w _ a v g 算法采用选择历史记录中最近的记录作为预测的有 效采集值，也就是由一个固定时间段长度或者滑动窗口内的测量值来计算平均值，其 数学定义如公式( 2 4 ) 所示： 册一爿陬，栌志p m 酮 ( 2 - 4 ) 这里k o 或者k = o ，是一个整数，表示滑动窗口或者固定段内的测量值的个数。 由h a r c h o l b a i t e r 和d o w n e y 的研究表明这个函数对c p u 资源的预测效果很好，能 够比较真实的反映资源的利用情况。 但是从上面的函数可以看出，为每个资源的预测选择一个合适的k 值是比较困难 的，进一步可以想到这个k 值也一定会随着时间t 变化的。最好的方法是能够使得k 值自动的随着t 的变化而变化以适应需要。 理想的情况是，定义一个关于k 的随着时间t 变化的函数，使得它能够在e r r ( t ) 最小的情况下作为函数f 的参数。但实际上这个函数是不存在的。而通过每次的预测 进行适当的调整则是可行的方法。 滑动窗口算法得的极端形式就是k = o ，这也是常见的一种算法。 3 l a s t 算法 该算法直接用上次的实测值作为下一时间段内的预测值，数学定义如( 2 5 ) 所示： 上4 s r ( f ) = v a l u e ( ，) ( 2 5 ) 适用于预测时段比较小性能较为稳定的情况，在该情况下，预测机制简单，应用 几乎不占用系统资源。但是其问题也是显而易见的，本身是服务程序，却对应用要求 太为苛刻。 华中科技大学硕士学位论文 2 3 中值算法 中值也可以用来作为一个有效的预测值。当测量值序列中包括一些任意的突发事 件时，就会产生一些不规则的数值。这些不规则数据会对由平均值算法对下一时刻的 性能值进行的预测产生不良影响。中值算法( m e d i a n b a s e dm e t h o d ) 可以有效地避免 这以问题。 中值算法同上面介绍的平均值算法差不多，分类及优缺点也有共同之处，只作简 单介绍。 中值算法根据选择时间段的不同分为中值算法( r u n n i n g m e d i a n a v e r a g em e t h o d ) 和滑动窗口中值算法( s l i d i n gm e d i a nw i n d o wm e t h o d ) 。前者将历史上所有的实测值 作为其取值空间其缺点同上也是显而易见的；后者则在此基础上有所改进，把在一 个滑动窗口或者固定长度队列中的中值作为下一个时刻的预测值。公式( 2 6 ) 给出了 中值算法的数学表达式： s o r t k被选的最近被测到的k 个测量值序列； s o r tx