（计算机软件与理论专业论文）可协商的资源预约服务.pdf

摘要 随着人们求解问题领域的不断拓展，所遇到的问题越来越复杂，而且规模 越来越大，局部的计算资源是无法满足这样的需求的，因此必须使用互联网内 广大的分布资源，将它们集中起来协同解决问题。于是，网格计算技术就这样 应运而生了。为了确保在求解问题的过程中，获得足够的资源，就需要提供一 种能够在互联网内预约共享资源的机制。为了避免预约资源的供给过量或供给 不足，需要资源的提供方和资源的使用方能对“预约资源”请求进行协商。因 此，本文以网格计算平台为基础，设计了一种“可协商的资源预约”服务，并 解决了一些相关问题。 在第一章中首先介绍了现有的各种调度系统，并对它们的预约调度性能做 了比较。然后，介绍了网格计算项目一g l o b u s 中，专门用于预约服务的协议一 g a r a 。最后，提出了一些尚待解决的问题，并总结了本文的工作。 在预约资源时，需要知道资源的未来状况，需要对资源的性能做出预测， 本文采用了时间序列分析的方法来解决这个问题。用户在预约网络资源，运行 自己的程序时，需要指明资源的占用量。本文提出了一种在程序运行前，就能 预测程序占用资源状况的方法。这两个预测问题将在第二章中讨论。 在第三章中设计了“可协商的资源预约”服务的总体结构。并设计了一种 专门用于资源协商的语言( 消息) ，提供了对这种语言进行解析、分析的方 法。这种语言是十分简单而实用的，并可由系统自动生成。 第四章讲述了如何以g l o b u s 项目为基础，实现第三章所设计的“可协商的 资源预约”服务。在本章的最后，提出了一种较为通用的“预约资源分配”算 法，此算法主要对预约资源的使用数量进行跟踪和分配；并且讲述了如何合理 的分配“预约请求”的资源占用量与“立即请求”的资源占用量。 第五章对本文的工作做了总结，并指出了不足和今后所要完成的工作。 关键宇： 网格计算；资源；预约：协商 a b s t r a c t f o rt h ec o n v e n i e n c eo fs o l v i n gm o r ec o m p l e xa n dl a r g e rs c a l ep r o b l e m s ，t h e t e c h n o l o g yo fg r i dc o m p u t i n g i sc r e a t e d ，w h i c hc a nc o l l e c tt h ed i s t r i b u t e dr e s o u r c e si n t h ei n t e m e tt oc o - w o r ko nt h es a l t i ct a s k r e s o u r c er e s e r v a t i o ns h o u l db e p r o v i d e d t o p r o m i s e t h a ta na p p l i c a t i o nc a l lr e c e i v eac e r t a i nl e v e lo fs e r v i c ef r o mar e s o u r c e f o r e x a m p l e ，ar e s e r v a t i o nm a yp r o m i s eac e r t a i nb a n d w i d t ho n an e t w o r ko rac e r t a i n p e r c e n t a g e o fac p u t oo b t a i nm o r ee f f i c i e n tr e s o u r c e u s a g e t h a ni n p u r e l y r e s e r v a t i o n - b a s e da p p r o a c h e s t h ea p p l i c a t i o ns h o u l db ea l l o w e dt on e g o t i a t e 、析t 1 1t h e r e s o u r c eo w n e r so nt h er e s e r v a t i o n t h i sp a p e rc o m b i n e st h e s et w of a c t o r sa n d e x p l o r e sak i n do f s e r v i c es u p p o r t i n g b o t hr e s e r v a t i o na n d n e g o t i a t i o no f r e s o u r c e s i nc h a p t e ro n e ，w ei n t r o d u c es e v e r a ls c h e d u l i n gs y s t e m sa n dc o m p a r et h e mu p o n t h e p r o p e r t i e so f r e s e r v a t i o n ，a n dw e a l s og i v ea no v e r v i e wo f t h eg a r aa r c h i t e c t u r e g a r ai su s e df o rr e s o u r c er e s e r v a t i o ni ng 1 0 b u sp r o c o t ak i n do f g r i d i nc h a p t e rt w o ，w e p r e s e n t an e wm e t h o db a s e do nt i m es e r i e sa n a l y s i st op r e d i c t r e s o u r c e p e r f o r m a n c e ，t h e nd e v e l o p as t a t i s t i c a l a p p r o a c h f o r p r e d i c t i n g t h e r e q u i r e m e n t s o fap r o g r a mb e f o r et h eb e g i n n i n go fi t sl i f e t h e s et w ok i n d so f p r e d i c t i o n c a nm a k et h eu s eo f t h i ss e r v i c ee a s ya n de f f i c i e n t i nc h a p t e rt h r e ew eo u t l i n et h es e r v i c ea r c h i t e c t u r eo f r e s e r v a t i o na n d n e g o t i a t i o n a n dd e s i g nt h er e s o u r c en e g o t i a t i o nl a n g u a g e ，w h i c hc a nb ep a r s e dq u i c k l ya n d g e n e r a t e da u t o m a t i c a l l y i n c h a p t e rf o u rw ee x p l a i nh o w t o i m p l e m e n tt h es e r v i c eb a s e do nt h eg r i d c o m p u t i n gt e c h n o l o g y w eg i v ea na l g o r i t h m a b o u tr e s e r v e dr e s o u r c ea l l o c a t i o na tt h e e n do f t h i sc h a p t e r i nc h a p t e rf i v ew es u m m a r i z et h ep a p e ra n dd i s c u s sf h t u f ew o r k k e yw o r d s ：g r i d ，r e s o u r c e ，r e s e r v a t i o n ，n e g o t i a t i o n 第一章绪论 第一章绪论 本文的主旨是在互联网内，提供一种预约网络中共享资源的机制，并且在 整个预约的过程中，资源的提供方和资源的使用方可根据自身当前和今后的状 况对资源的使用要求进行协商，使得用户的工作与共享资源的状况相适应，使 得资源得到更合理的利用，也使得用户的工作得到可靠的保证。有关预约和协 商的工作，一直是分布式计算领域的重要课题。目前，已有一些调度系统【1 】【1 7 】 具备预约和协商的功能。但它们都是为专门的计算系统( 例如，机群系统、并 行系统) 而设计的，并不是针对互联网内普通的共享资源的。近年来，网格计 算技术蓬勃发展，此项技术主要是为了实现互联网内的资源共享，使得共享资 源之间能够协同工作，屏蔽异构系统之间的差异，力求将网络虚拟成一台计算 机。在g l o b u s 网格计算项耳中，有一项g a r a 【2 1 协议专门用于互联网内的资源预 约，它构建了一个专门用于预约服务的体系，但具体资源的预约分配还需要专 门的预约分配程序来完成。 本章的第一节首先介绍了有关预约的两个重要概念。第二节主要介绍预约 的相关属性。第三节以第二节列举的属性作为衡量指标，对现有调度程序的预 约性能做出比较。第四节主要介绍g a r a 。第五节主要介绍本文在预约和协商这 两方面所做的工作。 1 1 两个基本概念 夺用户( 客户) 一个用户可以只是一个简单的预约请求。这个请求可由某人( 通过某种图形界 面、命令行) 发出，也可由某种代理软件发出。 夺提前预约 提前预约就是通过用户和资源拥有者之间的协商，双方达成一致后，用户可以 得到在一定时间间隔内，有限的、受到严格限制的对于某些资源使用的许可。 这些资源可以是一定数量的处理器、内存空间、硬盘空间、软件许可证或网络 带宽等。 1 2 预约的属性 本节所讲述的属性主要用于对现有调度系统的预约性能进行评价。 第一章绪论 1 - 2 1 基本属性 调度程序是否支持提前预约 对于支持提前预约的调度程序，可认为它可以取消已经达成的预约请求，或者 可以终止一个已经运行的预约请求。 预约能否被“普通”用户所建立 对于大多数调度程序来说，预约只能由系统管理员建立。这对广大的普通用户 来讲是一个很大的限制。 预约能否有自己的队列 这点与预约调度密切相关。将用户的预约请求排成一个队列是一个非常普通的 方法。如果预约服务有自己的队列，那么只要预约请求达成后，就可将预约请 求插入到队列中。 预约是否可以采用交互的工作方式 用户的预约请求是以批处理的方式执行，还是允许用户通过交互的方式( 命令 行或图形用户界面) 来控制预约请求的执行。 例如，对于e a s y c o s y 系统来讲，用户在提交资源使用的预约请求后，它需 要决定它的请求是以一种不被干扰的批处理方式运行呢，还是以交互的方式运 行。对于批处理方式，用户通常要提交一份运行脚本，对于交互方式它要登录 到经过授权的节点上进行交互。 预约的使用控制 当预约请求达成后，是否允许其它用户( 例如，同组用户) 使用预约资源。 预约的访问控制 预约请求能否被用户修改、取消或终止。 1 - 2 2 提前预约属性 已达成的预约请求能否变更 一个预约请求达成后，它执行的起始时间、结束时间、处理器数量等内容是否 可以改变。 2 第一章绪论 已执行的预约请求能否变更 当一个预约请求被执行了，它所预约的资源能否变更。例如：一个计算请求发 觉它将运算超时，此时，它能否增加处理时间或增加计算资源的数量。 1 2 - 3 两阶段提交属性 两阶段提交 是否允许预约请求在确定之前，进行协商。例如下面的对话能否发生。 用户：“我能在下午一点钟使用3 2 个处理器吗? ” 系统：“不行，现在只有2 0 个空闲。” 用户：“那么，我能在下午一点钟使用1 6 个处理器吗? ” 系统：“可以，但是如果你想使用，必须在以后的6 0 分钟内确认。” 用户：“行，我确认使用它们。” 显然这会增加问题的复杂性。如果系统仅对第一个问题回答“不”，那么协商 将会一直持续下去。系统必须明确告知用户：某一时间段内可用资源的数量。 这里需要一个超级调度程序代表多个资源与用户协商，并能协同多个资源的完 成用户请求。 预约过程中是否支持协商 调度程序是否允许用户( 人、或代理) 按照上述的方式进行协商。就目前所 知，还没有调度程序能够完成上述方式的协商。 预约达成后能否协商 预约请求达成后，能否按照上述方式进行协商。 预约执行后能否协商 预约请求被执行后，能否按照上述方式进行协商。 第一章绪论 1 3 各种调度系统的预约性能 1 3 1 现有调度系统的介绍 l s f l s f 是由p l a t f o r m 公司开发的负载均衡系统，并未提供开放的源代码。从 强大的功能和广泛使用的角度看，l s f 可谓是一个成熟的机群作业管理系统。 在使用范围上，l s f 不仅用于科学计算，也用于企业的事务处理。功能上，除 了一般的作业管理特性外，它还在负载平衡、系统容错、检查点操作，进程迁 移等方面做了很好的努力，并力图使之实用化。 l s f 的主要特点是：支持多种操作系统，包括n t 和w i n 2 0 0 0 ；支持检查点 操作( 核心级、用户级及应用程序级) 和进程迁移；具有高可用性，消除单一 故障点；提供了抢占式调度和关键资源保障，保证紧急作业的调度；可通过逻 辑表达式创建作业依赖图，提供对依赖性作业的支持；提供了多种调度策略， 包括预约和b a c k f i l l ；动态的负载平衡与负载检测，负载指标包括节点状态、 运行队列长度、c p u 利用率、分页速率、登录用户数、空闲时间、可用交换空 间、可用存储器、t m p 目录下的可用空间；提供了完整的负载共享库；具有强 大的资源管理功能。 p b s p b s 最初由n a s a 的a m o s 研究中心开发，为了提供一个能够满足异构计 算网络需要的软件包，特别是满足高性能计算的需要。它力求提供对批处理的 初始化和调度执行的控制，允许作业在不同主机间的路由。p b s 的独立的调度 模块允许系统管理员定义资源和每个作业可使用的数最。调度模块存有各个可 用的排队作业、运行作业和系统资源使用状况信息。使用它提供的t c l 、 b a c l 、c 三种过程语言，它的调度策略可以很容易的被修改，以适应不同的计 算需要和目标，即系统管理员可以方便的实现自己的调度策略。 p b s 的主要特点有：代码开放，免费获取：支持批处理、交互式作业和串 行、多种并行作业，如肝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 0 0 3 。2 d 标准；支持作业依赖；自动的负载均衡；完整的安全 4 第一章绪论 认证i 提供了完整的a p i ；方便新的调度器的开发；提供用户影像功能，使p b s 能用于用户不一致的系统中。 l 0 a d l e v e i e r l o a d l e v e l e r 由i b m 公司开发的机群作业管理系统，并不具备提前预约机 制。它成功地运行在i b m s p 2 机群系统上。它允许用户在同构或异构的机群系 统中提交交互式批处理作业。除了i b m a i x 操作系统外，它还支持m u n i 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 的主要特点是：支持并行串行，交互式批处理作业；对工作 站主人的影响小：可定义作业类，优化调度；具有较好的系统可用性：系统中 心控制；完整的文档；分布的用户服务器；提供完整的a p i ；与n q s 兼容。 m a m m a u i 是开放源代码的，并已被现有的批处理系统( p b s 、l o a d l e v e r l e r 、 l s fs u ng r d e n g i n e ) 所采用。m a u l 是高性能计算领域公认的可以灵活配置 的、高效率的批处理系统。它目前已经广泛应用于s p 、0 2 k 和l i n u x 机群系 统。它具备多种调度能力，如：b a c k f i l l 、公平共享( f a i rs h a r e ) 、动态优先级 和资源的预约分配。它已被世界上大多数的高性能计算中心所采用。 m a u i 的主要特点是：基于优先级的单一作业队列：提供预约服务，即用户 可指明在未来的某段时间内使用多少个节点；b a c k f i l l 功能，即在不影响高优先 级作业的前提下，有效的运行低优先级作业；可扩展的策略配置功能：整合模 拟功能；负载分析工具；单节点可支持多个任务；可扩展的历史负载跟踪库； 新算法和策略的即插即用机制。 s u ng r i d e n g i n e s u i l t m 】o n eg r i de n g i n e ( s g e ) 是一个分布式的资源管理系统和任务排队系 统，由s u n 公司发布，并可以免费下载。s g e 并没有直接提供提前预约机制， 它结合了m a u i ，m a u l 作为s g e 的外部调度程序。s g e 控制任务队列并管理资 源，m a u l 处理有关提前预约的部分，并将具体的任务传递给s g e 。 第一章绪论 e a s y 和c o s y e a s y 源自于为s p 2 设计的a r g o n n ee a s y 调度程序，它由算法和科学计 算协会( s c a i ) 研制。它支持批处理和交互式作业。并且已应用于并行机和u m x 机群。它具备较强的b a c k f i l l 功能。 c o s y 源自于s c a ie a s y ，它由n e c 公司的c & c 实验室研制。与e a s y 具有相同的特性，但它以c + + 和c o r b a 为基础。并且c o s y 可与与其类似的调 度程序协同分配资源。它既支持批处理作业也支持交互式作业。已应用于不同 类型的p c 机群。程序可以免费下载，但源代码没有公开。 c a t a l i n a c a t a l 血a 由加利福尼亚大学研制，已被p b s 和l o a d l e v e l e r 所采用，它主要 用于教学、科研等非盈利目的。它与m a r e 非常类似，它由p y t h o n 写成。缺少 m a r e 的公平共享( f a i rs h a r e ) 和负载分析等功能。它具有小型的资源池，更为 灵活的作业预调度机制，并设计了用于预约调度的编程接口( a p i ) 。 c a t a l i n a 的主要特点是：它能够提供更为复杂的预约服务，它能生成预约请 求，支持对预约请求的修改，支持协商操作；它预留了若干节点，用于对紧急 请求做出快速响应；它具有更为灵活的机制来选择可以预约执行的作业；它允 许系统管理员编写程序来选择用于预约服务的节点。 c o n d o r c o n d o r 是一个分布式的资源管理系统，它由w i s c o m i i l 大学研制。它主要 为计算密集型应用而设计。它并不支持提前预约。充分利用工作站的空闲时间 是c o n d o r 的最主要特征。c o m o r 管理的机群由网络中的工作站组成。工作站 的主人可以自动的加入或退出。c o n d o r 监测网络中所有工作站的状态，一旦某 台机器被认为空闲，就把它纳入资源池中。在资源池中的工作站用来执行作 业。当工作站的主人开始使用工作站时，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 提供的检查点和进程迁移功能；对于远程执行的进程， 本地的执行环境被保留；工作站主人对该工作站拥有最高优先级和完全的控制 6 第一章绪论 权；作业保证彻底完成，不会因为系统的故障或工作站的退出而终止；本地磁 盘不会被c o n d o r 作业所占用 对网络资源、数据传送和检查点操作的有效控 制；对网络资源、c p u 的协同调度。 1 3 2 预约性能比较 根据第二节的预约属性，来评价现有调度系统的预约性能，如表1 3 1 所 示。只有提供预约服务的调度程序才出现在表中。此表是针对普通用户的，而 不是针对系统管理员的。y 表示“具备此项功能”；n 表示“不具备此项功 能”；空白表明不能确定。 从表1 3 1 可知，已有很多调度程序都具有预约功能，但具备协商功能的调 度程序还是很少的，并且这些调度程序只适用于某些专门的计算系统，例如： 机群或并行机，不具备在整个互联网上预约共享资源的功能。 l s fp b sm a u ic a t a l i n ae a s yc o s y 是否支持提 yyyyyy 前预约 能否被“普 yyyyyy 通”用户建 业 是否有自己 yyynyy 的队列 是否可以采 yyyyyy 用交互的方 式 预约的使用 yyyn 控制 预约的访问 yyn 控制 达成的预约 nnyn 请求能否变 史 执行的预约 nnyn 请求能否变 更 7 第一章绪论 是否支持协 nnynyy 商 预约达成后 nnynyy 能否协商 预约执行后 nnyn 能否协商 1 4g a r a 表1 3 1 提前预约性能比较图 g a r a 为应用程序提供了方便的端到端的具有一定质量保证的使用网络中 共享资源的功能。它提供了多种资源的预约服务，包括：计算机、网络、硬盘 等。在g a r a 中，一个预约就是指保证应用程序将会得到某个资源一定质量的 服务。例如一个预约可以确保应用程序获得一定数量的网络带宽或一定比例的 处理器。 g a r a 是一种分层的结构，有三层a p i ，最下面为一层服务机制，如图 1 4 1 所示。 lh i 班州a p i s ia d d sm d t o - e d r 瞄百v 且t j o n 瑚e d 瑚i j 譬膳船 ln 帅耐喁b y 皿& h 砩m 嘞k 他w 砒i 嘲- + | g 】队砸 a 曲a b i l i l y m m a k e r m l 如, a u t h 蹦i c a t m ( 圆d ir 自r v 出 ， 1 il o c i j r 螂啦智i t 协n a p ! im 吐珊强r v 鲥。璐埘m 击眦= e l e i 舶帅e 写 i 删n 面嗨k 蛔缸 0 l h f l o u i c em | m g 口 ( b n 虹d sa d r n 蜮咂a n d e n 南北疆。日v 刊j a n 墨f b f 阳晡o l l l a r 槽9 鼠r 乱 图1 4 1g r a 的分层结构 注意g a r a 指两件事情：它既可指上面的结构图，又可指g a r aa p i ，a p i 用 于生成一个单一的预约请求。g a r aa p t 是与r e s o u r c em a n a g e r 通讯的远过程 调用。一个r e s o u r c em a n a g e r 控制具体资源的预约，它完成访问控制，控制资 源完成预约服务。有些资源已经具备预约功能，但是大部分资源都不具备预约 8 第一章绪论 功能，所以r e s o u r c em a n a g e r 需要跟踪预约请求。g a r a 的主要工作是研制有 用的r e s o u r c em a n a g e r 。下面要逐一讨论各层的功能。 1 4 1r e s o u r c em a n a g e r 目前，g a r a 提供了三种不同的r e s o u r c e m a n a g e r ： 各种类型网络资源的r e s o u r c em a n a g e r 使用动态软时钟调度( d s r t ) 的中央处理器r e s o i l r e e m a n a g e r 允许外部访问d p s ss e r v e r 的d p s sr e s o u r c em a n a g e r 资源管理者主要完成四方面工作： 许可控制：决定是否接受预约请求。 资源配置：配置底层的资源( 例如：网络中的路由器) ，确保预约请求获 得一定质量的服务。 管理：当一个预约请求被执行时，r e s o u r c e m a n a g e r 要观测底层资源的状 况。并向用户反馈执行状况，传送预约不足或预约过量的警告。 汇报：r e s o u r c em a n a g e r 要向元计算目录服务( m d s ) 汇报资源的当前状态， 例如：还剩余多少资源可供预约。还要汇报已达成的预约请求的列表。 1 4 2g a r aa p i g a r aa p i 提供了简单而又统一的界面用于提前预约各种资源。它所提供 的功能包括：产生、修改、绑定、取消和管理预约请求。虽然a p i 是统一的， 但是不同的资源有不同的参数。例如：预约网络资源需要指明带宽、预约处理 器需要指明使用处理器的比例。 当预约请求被接受后，它将配有一个唯一的标志，这个标志是一个字符 串，它可存于硬盘，也可打印出来。这个预约请求可以被其它的用户所使用， 而不被产生这个请求的用户所使用。其它的用户可经授权，获得某个预约请求 的标志，在未来的某一时刻，通过这个标志使用已经准备好的预约资源。 在预约请求被接受时，很多信息是无法预知的。例如：预约处理器时需要 知道进程的i d 号，预约网络资源时需要知道端口号。这些信息无法提前预知， 所以g a r aa p i 提出了绑定( b i n d ) 操作，在程序运行时，将预约资源的具体信息 与要在其上运行的程序联系起来。 预约请求是可以修改的。如果预约请求不能修改，主要因为资源不足。当 修改失败时，原有的预约请求仍被保存。预约请求的状态是可以被监控的，有 两种监控机制：调用和反馈。程序可以调用监控函数来随时检查预约请求的状 9 第一章绪论 态。在某些情况下，反馈方式是一种更加有效的机制。当预约请求的状态( 开 始、结束等) 改变时，可按照用户预先设定的地址，向用户自动传送状态改变 的消息。 1 4 3h i g h l e v e la p l 考 因为g 肌已经为预约不同类型的资源提供了统一的a p i ，可以直接使用 g a r aa p i 构造功能更为专一的a _ p i ，这些h i g hl e v e la p i s 使得应用程序的编写 更加容易。目前，已有专门预约端到端网络资源的a p i ( e n dt o e n dn e t w o r k r e s e r v a t i o na p i ) 。现在正在研制可帮助用户完成多种资源同时预约的】l i g hl e v e l a p i ，称其为c o r e s e r v a t i o na g e n t ，它主要完成下面三项工作： 1 现那些资源能够满足用户的请求。用户可说明所需资源的工作方式( 例如， 用户需要使用s o l a r i s2 7 系统) j 也可说明需要使用的时间( 例如，机器是 否在周三下午两点至五点可用? ) 2 定预约请求。如果所要求的资源不再是可用的，需要驳回用户请求。 3 理预约请求并通知用户所预约的资源何时可用。如果预约资源变为不可用 ( 例如：资源故障或资源被抢占) c o - r e s e r v a t i o na g e n t 将返回第l 、2 步。 在g a r a 中还没有实现c o - r e s e r v a t i o na g e n t ，它正在研发当中。g a r a 提 供了在整个互联网范围内，预约共享资源的机制，但是并不具备协商功能。 1 5 本文的工作 由前面的分析可知：目前的大多数调度程序虽都具备预约功能，但它们都 只为机群系统或并行系统而设计，并不能在整个互联网内使用。g a r a 搭建了 在整个互联网上预约共享资源的平台，但是对预约请求还不能进行灵活的协 商。为了能够更好的实现整个互联网内，共享资源的预约，并能够对预约请求 进行灵活的协商，本文做了如下工作： 为了进行预约调度和预约分配资源，就需要对资源的未来状况进行预测。 本文提出了一种预测资源性能的方法。由于有关资源性能的各项指标( 例如： 处理器的利用率、内存的利用率等) 在时间上都是连续的，所以本文采用了时 间序列分析的方法进行预测。本文所提出的预测算法具备很好的通用性，任何 一项资源性能指标都可以用此方法进行预测，它能根据以往的资源性能值动态 的建立预报函数，从而不必为每项性能指标都研制一种预测算法。 互联网上存在许多共享资源，用户程序在使用这些资源时，需要明确自身 的资源占用量，这样才能找到合适的资源，才不会出现资源供给不足或资源供 第一章绪论 给过量的问题。本文提出了一种在程序运行前，就能够自动预测程序占用资源 状况的方法。这样，用户只需指明要运行的程序即可，而不必说明程序占用资 源的状况，使得用户对共享资源的使用更具透明性。并且这个算法对各种资源 占用状况的预测( 无论预测程序占用处理器的时间，还是预测占用内存的多 少) 都是普遍适用的。上述两个问题将在第二章中详加讨论。 在第三章中设计了能够在互联网内完成“可协商的资源预约”服务的总体 结构。此项服务不仅能预约互联网内的共享资源，关键在于它具备较强的协商 功能。这使得用户和资源之间能够相互协调，既保证了用户工作的顺利完成， 又有助于资源的有效使用。为了能使资源的使用方和资源的提供方，对资源预 约请求进行协商，本文设计了一种资源协商语言( 消息) ，给出了对这种语言 进行解析、分析的方法。此语言能像“1 2 3 两阶段提交”所要求的那样，用户 和资源之间均可根据自身状况，互提建议，共同确定预约请求。此语言能够被 快速的解析，快速的进行语义分析，并且可由系统自动生成，这些都是实时的 在线协商所必须具备的特性。 第四章的工作为：( 1 ) 讲述了如何以o l o b u s 项目为基础，实现第三章所 设计的“可协商的资源预约”服务。( 2 ) 设计了专门用于协商工作的智能代 理。协商代理的实现是不固定的，是根据需要灵活多交的。( 3 ) 提出了一种具 有通用性的“预约资源分配”算法。此算法对内存、处理器、网络带宽等资源 的预约都是适用的。算法主要对预约资源的使用数量进行跟踪和分配。算法还 可以根据预约请求的总体状况进行调整，使其发挥更好的性能。( 4 ) 给出了合 理的分配“预约请求”的资源占用量与“立即请求”的资源占用量的方法，此 方法既保证了资源得到充分的利用，又保证了预约请求的顺利完成。 第五章对本文的工作做了总结，并指出了不足和今后的工作。 第二章预测问题 第二章预测问题 与以往的单机系统、并行系统或机群系统相比较，在互联网内预约共享资源， 需要预知更多的系统性能信息，和程序( 服务) 占用资源状况的信息。比较如 下： 1 对于单机系统来讲，只有一个唯一确定的资源集合。例如：一个处理器、若 干内存、一块硬盘等等。无论用户程序对资源的要求如何，都必须在这个确 定的集合上运行。同时，不管系统性能如何，都要运行整个系统内部提交的 所有程序。此类系统不具备选择性。图示如下： 图2 1 单机系统中程序与资源的关系 2 对于并行机或机群来讲，系统资源较为充裕和丰富，此类系统常有几十、甚 至数百个结点，每个结点都有自己的处理器、内存、外存等。用户程序可以 在其上的一个或多个结点上运行。即此时出现了一定范围的可选性。由于资 源毕竟是有限的，备选方案也是有限的。这就体现在一些处理器的分配策略 上。例如：以负载均衡作为分配准则，只将待运行的程序分配给负载最轻的 结点就可以了，并不需要知道程序将要占用多少资源。此类系统的特征是采 用某些确定性的策略将程序分配到若干可选资源集合中的一个。此类系统具 备有限的可选性。简单图示如下： 图2 2 分布式系统中程序与资源的关系 3 若允许程序使用互联网内的共享资源，则可选性将有本质的变化。对某一道 第二章预测问题 待运行的程序而言，在互联内将有不计其数的各选资源集合供其使用。程序 可以从中选择与自身资源占用状况最为匹配的资源集合。对某一特定的资源 集合而言，它并不需要运行全部的程序，它可以只接受与其性能最相匹配的 程序。因此在程序运行前就需要预知自身占用资源的状况。也就是说，在程 序运行前就要评估出它的资源使用状况。可选性如下图所示： 任意盎幡 ；! 图2 3 广域网范围内程序与资源的关系 随着可选性的增强，就需要在程序运行前预知它的资源占用状况。若用户 需要提前预约互联网内的共享资源，就需预知共享资源的未来状况。这样资源 的拥有者才能为用户程序预留出适量的资源，用户程序也可根据资源的未来状 况，预约到能够满足自身要求的资源。下面两节将分别讨论：共享资源的性能 预测和程序占用资源状况的预测。 2 1 共享资源的性能预测 资源是多种多样的，每种资源又有很多性能指标。经常遇到的指标有：处 理器的利用率、内存的利用率、网络的传输速度等等。目前有许多用于预测的 程序或算法，大部分都是针对其中的某一项指标的，例如：仅对处理器的利用 率或仅对网络的传输速度进行预测。 大部分的资源性能指标在时域上都是连续的。无论是处理器的利用率、还 是内存的利用率、或者网络的传输速度等等，它们都可以看成是时间上的连续 函数。基于这种特性，本文引入了时间序列分析网的方法来解决此类预测问 题。时间序列分析的方法被广泛的用于国民生产、生活的各个领域。计算机科 学和通讯科学的许多问题也是通过它来解决的，例如：对系统负载【1 8 】【2 l 】的预 测、对( 无论是有线的，还是无线的) 网络传输性能的预测【2 0 】，都应用过时间 序列分析的方法，并收到了很好的效果。它是一种普遍适用而又可靠的方法。 很多资源性能指标都可以看成是时间序列，均可采用本文所提出的时间序 列分析的算法，这个算法可根据序列自身的特性动态的生成预报函数。所以无 第一二章预测问题 论是处理器的利用率，还是内存的利用率，只要在时域上时连续的，都可以使 用这个方法进行预测。 2 1 ，1 算法介绍 没当前时刻为t ，z ，为t 时刻的观测值( 这里指t 时刻，观测到的某种资源的性 能指标，既可是处理器的利用率，也可指网络带宽等等) 。互一，( - = 1 , 2 ，) 为 以往各时刻的观测值。 定义【3 l ：v z = z 一z t - j - 1 ( ，= 0 , 1 ，2 ) v 2 z _ = v 互一，一v z ，十l ( _ ，= 0 , 1 ，2 ) 乞= z n ( 为常数) 1n 一1 一k q 2 专善( z 一一一z ) ( z 一女一三) = o ，1 ，2 ，世础常数) 1 - 1 一k 其中。专善( 钆。) 2 丸= ( 七= 1 , 2 足) l _ _ 1 r 2 ： 一l一2 其中：破。= r 如：1 1 i _ 1 1 九，= l _ i 也 川 “ f 1 屯 i 1 ，1 i 也 1 i 唯一ir k 一2r k 一3 r k 一2 以一1 r k 3 r k 2 唯一4 r k 一3 ， ： 只l ( k = 1 , 2 屹。： ， k 1 如 l ，n 第二章预测问题 下面定义六类预测估计模型a r ( p ，d ) 嘲 a r ( 1 ，o ) ： a r ( 1 ，1 ) ： a r ( 1 ，2 ) a r ( 2 ，0 ) a r ( 2 ，1 ) 宣( 1 ) = 蛹 2 ，( f ) = 庐乏( i 1 ) 够 1 ) z 。( 1 ) = ( 1 + 妒z 。一9 甄一l z ，( 2 ) = ( i + ) z 。( 1 ) 一蜴 宣u ) = ( 1 + ) 2 ，( ，一1 ) 一垂宕，( ，一2 ) ( z 2 ) 宣( 1 ) = ( 2 + ) z ，一( 1 + 2 ) z | 一i + 庐z 。一2 乏( 2 ) = ( 2 + ) 毒( 1 ) 一( 1 + 2 庐) z ，+ 弘。 乏( 3 ) = ( 2 + 妒) 宣( 2 ) 一( 1 + 2 ) 毒( 1 ) + 必 2 ，( ? ) = ( 2 + 咖乏( ? 一1 ) 一( 1 + 2 庐) 之，( ，一2 ) + 咖毒( 1 - 3 ) u 3 ) z 。( 1 ) = l z ，+ 也互一i z t ( 2 ) = 氟互( 1 ) + 丸互 毒( ，) = 氟乏( ，一1 ) + 晚毒( ? 一2 ) ( f 2 ) 宣( 1 ) = ( 1 + a ) z 。一( 疵一九) z 。一，一屯z ，一： 乏( 2 ) = ( 1 + 哦) 之( 1 ) 一( 破一戎) z ，- 2 z 。 2 ，( 3 ) = 0 + 0 2 ，( 2 ) 一( 破一戎) 2 ：( 1 ) 一2 z ， 第二章预测问题 a r ( 2 ，2 ) ： 2 ，u ) = ( 1 + 办) 宣( f 一1 ) 一( 晚一如) 2 。u 一2 ) 一九乏( ，一3 ) ( ， 3 ) z ，( 1 ) = ( 2 + 庐1 ) z t 一( 1 + 2 磊一丸) 互一。一( 2 办一氟) z t 一：一九z ， z ，( 2 ) = ( 2 + 而) z ，( 1 ) 一( 1 + 2 氟一兜) z | ( 2 也一a ) z f i 一戎z 。 z f ( 3 ) = ( 2 + 疵) 乙( 2 ) 一( 1 + 2 唬一疵) 互( 1 ) 一( 2 办一办) z f 一戎z f 一 z ，( 4 ) = ( 2 + 磊) z ，( 3 ) 一( 1 + 2 破一欢) z t ( 2 ) 一( 2 欢一苁) 互( 1 ) 一屯互 z ，( f ) = ( 2 + 磊) 互u - 1 ) 一( 1 + 2 旃一戎) z 。u 一2 ) 一( 2 戎一办) z l ( z 一3 ) 一九互( ，一4 ) ( ， 4 ) 在上述模型中，f 代表预报的提前期。例如：乏( ，) 说明当前时刻为t ，对 什f 时刻的预报值( 这里指，某项资源性能在t + z 时刻的预报值 。破、屯和 都是模型中的待定参数。下面的算法讲述了如何来确定估计模型a r o ，d ) 、以 及模型中的参数值，从而得到明确的预报函数的过程。 算法如下： 第一步： 计算关于序列z 。的全部九i 若关于序列z ，的九序列能很快衰减为0 ，则令d ；o ； 否则，计算关于序列v z f 的全部珐； 若关于序列v z f 的丸序列能很快衰减为0 ，则令d = l ； 否则，计算y m y t v 2 z 。的全部丸； 并令d = 2 ； 第二步： 对于关于v 4 z t 的九序列。 若只有珐。明显大于0 ，并且其他九都明显接近于0 ，n 令p 2 1 ； 1 6 第二章预测问题 否则，令p = 2 ； 第三步： 若p = = l ，贝0 令庐= ，i ； 硎，令办= 等，丸= 寄； 第四步： 按( p ，d ) 的值，查找到相应的预测函数模型； 并将参数庐( 破，办) 代入到函数模型中，从而得到明确的预测函 数； 第五步： 在得到什l 时刻的观测值z f + 。后，重复前四步， 可得到下一时刻的预测函数； 算法结束。 2 1 2 算法的解释说明 1 本算法采用了时间序列分析中的自回归模型进行预测。选用此类模型的主要 原因为：在时间序列分析中存在三大类模型：可根据系统以往的输入值进行 预测一滑动平均模型；可根据系统以往的输出值进行预测一自回归模型：还 可以将二者混合起来进行预测一自回归滑动平均混合模型。三种模型的表达 式虽不相同，但本质是相同的，它们之间是相互等价的。若将某个资源集合 看成是一个系统，资源的性能指标作为输出，用户的程序和数据就是这个系 统的输入。而输入的程序和数据是不好量化和度量的，所以本文采用自回归 模型进行预测是比较合适的。 2 痧。和丘是两个十分重要的统计量，它们从不同的角度度量了整个时间序列 观测值的相互关系和相互影响。即它们表征了任意两个相隔k 个时间间隔的 观测值之间的相关度。九和实际上客观的描述了整个时间序列的固有本 质特征。 3 模型参数d 指明了时间序列的平稳程度。若时间序列互对于任意时刻t 的 概率分布p ( z ，) 都是相同的，我们称序列互是平稳的。若互是平稳的，则关 1 7 第二章预铡问题 于z 。的九和气会迅速衰减为零，本文用d = 0 指明。若z ，不是平稳的，则 对互作一阶差分得到序列v 互。若序列是平稳的。本文用d = l 指明。 若序列v z 还不是平稳的，本文用d = 2 指明。 4 模型参数p 指明了每类模型中需要多少个以往的观测值。当d = 0 时，p = 1 表明只需要一个，p = 2 表明只需要两个。p 的意义在6 类模型的定义中有 明显的体现。p 的选取也由序列的固有特征所决定，即由九所决定。 5 每类模型中的待定参数矿( 氟，以) 也是由时间序列的固有特征所决定的，即它 们由 和如所决定。 6 预测函数实际上是由丸和_ 所确定的，但需要多少个丸和气来确定预测函 数呢? 往往取k = 1 0 ，即有1 0 个值就足以确定模型了。而所需时间序列的 观测值z 的个数为n = 4 k ，即需要4 0 个时间序列的观测值，才能确定预 报函数。本文认为4 0 个观测值是比较多的，而资源的性能参数一般都是时 域上的连续函数，4 0 个观测值是比较容易获得的。这也是本文采用