（计算机软件与理论专业论文）网格环境下资源预约的可适应性分析以及优化.pdf

中山大学硕士学位论文碍格环境下资源预约的可适应性分析和优化 网格环境下资源预约的可适应性分析和优化 专业：计算机软件与理论 姓名：陈凯生 指导老师：李文军教授 摘要 随着网格应用的日益频繁和深入，而由于网格的动态性和异构性，使得网格 环境下各种应用的服务质量有很大差异，因而许多人提出把资源预约加入网格资 源管理中去。然而，目前对于把资源预约加入网格资源管理中去的有效性还缺乏 必要而且让入信服的证明。其次，当前能够进行预约的资源往往仅仅是带宽、 c p u 能力或者存储能力，很多作者或研究人员并没有把适合用数值型参数表征 的资源的算法应用到非数值型参数表征的资源预约上。而且这些预约的适应性不 高，造成资源预约的拒绝率很大。 本文首先对资源预约河题作一个详细的表述，这个表述包括了为了建立讨论 资源预约问题所建立的应用模型而涉及的各个内容的数学表示，分别建立了一个 有资源预约功能和一个没有资源预约功能的应用模型，然后通过详细的数学证明 过程以及利用网格模拟软件g r i d s i m ，证明了以下三点：当使用了资源预约功能， 同一任务执行多次时候，其时间的变化程度减低；当使用了资源预约功能，任务 的执行时间并不一定会增加，甚至在某些情况下，使用了资源预约功能能够使任 务的执行时间减少；当对过去的执行情况有了收集和详尽的统计后，我们能更精 准地预测未来的执行时间。 其次，本文改善了用户对数值型资源的预约工作：允许用户以一个范围来提 出用户的资源预约请求；允许用户提出一定的标准供给资源管理系统或者资源调 度系统，由其使用这些标准来匹配用户提出的资源预约请求与当前网格环境下的 可以供给用户使用或者预约的资源；允许资源管理系统或者资源调度系统对各个 预约子资源进行分别匹配。 最后，本文尝试了对一些较难预约的资源，譬如非数值型资源如操作系统等 中山大学硕士学位论文 网格环境下资源预约的可适应性分析和优化 资源的预约进行了一个探讨，基于的方法也是允许资源管理系统或者资源调度系 统对这些非数值型资源进行分别匹配。对旧有方法的改善以及新方法的提出，都 在我们的模拟实验中分别进行了验证。验证结果表明，本文提出的方法是的确能 够提高资源预约请求的接受率以及网格环境下各个资源的使用率。 关键字：资源预约，可适应性，网格环境 中山大学硕士学位论文 同格环境下资源预约的可适应性分析和优化 a d a p t a b i l i t ya n a l y s i sa n do p t i m i z a t i o nf o rr e s o u r c e r e s e r v a t i o ni ng r i de n v i r o n m e n t m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：k a i s h e n gc h e n s u p e r v i s o r ：p r o f e s s o rl iw e n j u l l l a b s t r a c t a st h eg r i da p p l i c a t i o n sa r eu s i n gf u r t h e ra n df u r t h e r , t o g e t h e rw i t ht h em o b i l i t y a n dh e t e r o g e n e o u sc h a r a c t e r i s t i c s ，i tm a k e st h eq o so ft h ev a r i o u sa p p l i c a t i o ni nt h e 鲥dv e r i f i e sg r e a t l y t h e nm a n yp e o p l es u g g e s tt h a tw ea d dt h er e s o u r c er e s e r v a t i o n f u n c t i o ni n t ot h eg r i dr e s o u r c em a n a g e m e n t h o w e v e r , t h ep r o v eo ft h ee f f i c i e n c yo f a d d i n gt h er e s o u r c er e s e r v a t i o nf u n c t i o ni n t ot h eg r i dr e s o u r c em a n a g e m e n ti sl a c k a l s om a n ya u t h o r sa n dr e s e a r c h e r sm a k er e s e r v a t i o nf o r t h er e s o u r c e st h a ta r ee a s y f o rr e s e r v a t i o n , s u c ha sc p un u m b e r sa n db a n d w i d t h m o r ee v e r , t h er e s e r v a t i o n l a c k st h ea d a p t a b i l i t yw h i c hr e s u l ti nt h eh i g hr 6 e c t i o nr a t ef o r t h er e s e r v a t i o n ht h i sp a p e r , i tf i r s to fa l lt h ed e s c r i b et h er e s e r v a t i o np r o b l e mi nd e t a i la n da f o r m a lw a y , b a s e do fw h i c hw es e tu pt w oa p p l i c a t i o nm o d e l sw i t ha n dw i t h o u t r e s o u r c er e s e r v a t i o nf u n c t i o n a n dt h e nw e p r o v et h ef o l l o w i n ga s s e r t i o n s ：v a r i a n c eo f e x e c u t i o ni sr e d u c e db yu s i n gr e s e r v a t i o n s ；e x p e c t e de x e c u t i o nt i m ei sn o tg u a r a n t e e d t oi n c r e a s ew h e nu s i n gr e s e r v a t i o n s ，a n d m i g h td e c r e a s ei ns o m es i t u a t i o n s ；b y c o l l e c t i n gp e r f o r m a n c ei n f o r m a t i o nf r o mp r e v i o u se x e c u t i o n sw ec a nb em o r ep r e c i s e i np r e d i c t i n gf u t u r ee x e c u t i o nt i m e s s e c o n d l y , r e s e r v a t i o nf o rn u m e r i c a lr e s o u r c ei si m p r o v e d i ta l l o w st h eu s e r st o m a k er e s e r v a t i o ni naf l e x i b l ew a ya n d op r o v i d es o m eb e n c h m a r k sf o r t h er e s o u r c e m a n a g e m e n ts y s t e mt om a t c ht h er e s o u r c et ob er e s e r v e da n dt h er e s o u r c ei nt h eg r i d m o r ee v e rw ea l l o wt h er e s o u r c em a n a g e m e n ts y s t e mt om a t c ht h er e s o u r c eb ym a t c h t h es u br e s o u r c eo ft h er e s e r v a t i o n a tl a s t , t h ep a p e rt r i e st om a k er e s e r v a t i o nf o rt h o s ea r ed i f f i c u l tt om a k e 中山大学硕士学位论文 网格环境下资源预约的可适应性分析和优化 r e s e r v a t i o n ，s u c ha s , s o m en o n - n n m e f i c a ir e s o u r c e t h em e t h o di sb a s e do nt h em a t c h b yt h er e s o u r c em a n a g e m e n ts y s t e m b o t ht h ei m p r o v e m e n ta n d t h en e wm e t h o da r c t e s t e db yt h es i m u l a t i o na n dp r o v et oh ee f f e c t i v ea n dm a k el o w e rr e j e c t i o nr a t e k e y w o r d s ：r e s o u r c er e s e r v a t i o n ，a d a p t a b i l i t y , g r i de n v i r o n m e n t i v 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 第1 章综述 1 1 目前网格环境下资源预约的现状 一、对资源预约有效性缺乏必要的证明 随着网格应用的日益频繁和深入，而由于网格的动态性和异构性，使得网格 环境下各种应用的服务质量有很大差异，因而许多人提出把资源预约加入网格资 源管理中去。然而，目前对于把资源预约加入网格资源管理中去的有效性还缺乏 必要而且让人信服的证明。 不少人认为加入资源预约到网格资源管理，由于带来额外的工作，势必会造 成整个应用或者服务的完成时间带来增加，但也有人认为，由于得到了足够的或 者最低限度的资源保证，能够使得应用或者服务更加顺畅和有序地执行，避免因 得不到资源而无必要的等待所造成的时间浪费，因而会使得整个应用或者服务的 完成时间带来减少：另一方面，也有不少人相信由于能够预约资源，至少得到了 最低限度的保证，因而对同一应用或者服务，在多次运行状况下，其时间变化幅 度应该比没有资源预约情况下更小。这些问题用文字描述起来比较简单，而道理 也似乎能够让人信服，但没有经过严格的数学形式证明，就不能轻易相信这些所 谓的“认为”和“相信”。目前，很多关于资源预约有效性的结论都是根据作者 的实验结果推导出来的，这很难避免作者的主观臆断和实验条件的限制所带来对 试验结果的偏差。 由于缺乏了对资源预约有效性必要的严格数学证明，缺乏了发现资源预约的 问题所在，从而也就不能对这些问题进行好好的研究和解决，使得目前对资源预 约的应用并不广泛，许多系统也只是仅仅包含了这样一个功能。 二、资源预约只停留在某些容易预约的资源 在目前提出能够实现资源预约的系统当中，能够进行预约的资源往往仅仅是 带宽、c p u 能力或者存储能力，这类资源有一个共同的特点，就是可以仅仅用 中山丈学硕士学位论文同格环境下资源预约的可适应性分析和优化 数值型参数就能够来表征它的能力。由于数值容易表示、得到、比较和处理，这 无论是对于提出资源预约还是进行预约处理等方面的工作都带来很大的便利性。 很多作者或研究人员选择能够用数值型参数表征的资源进行其有关资源预约的 研究，相信也是针对其为其研究和成果判别带来的便利性。 然而，在接下来第2 章关于资源的叙述中，我们发现在我们日常生活中，特 别是在网格环境下，需要用非数值型参数表征的资源也有很多种，而且其重要性 也不亚于用数值型参数表征的资源，典型的有如操作系统类型和网络拓扑结构。 相对数值型参数，非数值型参数更难表示、得到、比较和处理。很多作者或研究 人员在没有把适合用数值型参数表征的资源的算法应用到非数值型参数表征的 资源预约上，看看其应用得如何或者有否意想不到状况的情形下，就贸贸然根据 从用数值型参数表征的资源上得到的结果，得出资源预约对网格资源管理很有帮 助，或者其提出的资源预约算法对资源预约在网格中的应用有很大帮助，这是片 面的。这也可以看出，当前关于资源预约的工作缺乏充分的完备性，除了前文提 及的理论证明外，还需要在更多不同类型的资源上作更多研究和实验，才能充分 证明资源预约在网格资源管理中的作用。 三、资源预约不具备良好的适应性 关于适应性的定义可见文章1 1 l 【2 l f 3 】，主要关键点是当环境发生变化时候，我们 讨论是对象能够后很快或者很容易根据这种变化作出调整，就说它有很好的适应 性。显然，网格是一个经常变化的环境，而目前针对网格环境的很多资源预约工 作仅仅是初步的，仅仅验证了实现了资源预约，其资源预约功能并不是十分强大， 而且不具备良好的适应性。 这首先表现为，各种网格资源管理系统接受用户提出的资源预约请求时候， 很多时候要求各种资源预约参数都是固定的，而各种网格资源管理系统仅仅是凭 借当前网格环境下的资源状况作出简单的判断是否接纳还是拒绝该资源预约请 求，而并没有对网格环境的资源状况进行更深一步的分析或者对预约请求进行更 深一步的分析，从而看看有否以更灵活的方式来接受预约请求或者调整预约请 求，使得调整后的请求得到满足。另一方面，当用户提供资源预约时候，在系统 与用户之间缺乏一种协商的途径，无论是系统和用户之间对资源预约请求进行再 协商或者是用户以一种更加灵活的方式去提出资源预约都没有，这样造成用户资 源预约提出选择的余地太少，从而间接造成最后资源预约请求的接受率不高。 2 中山大学硕七学位论文 同格环境下资源预约的可适应性分析和优化 网格一个很重要的特征就是虚拟性，各种有用资源可以随时加入或者退出它 们所构成的虚拟组织，而目前各种网格资源管理系统对有更适合的资源加入时， 却不能重新调整原来接受的资源预约请求，使得可以利用更适合的资源，从而由 于对原来接受资源请求时预约好的资源继续使用造成不必要的浪费。而当预约好 的在预约后与执行前遇到意外情况时候，之前接受的资源预约往往就终止并发个 消息给用户，而不是与用户协商或者对用户透明地根据当前网格资源重新设置预 约。 1 2 论文研究动机 一、提高资源预约对网格不确定环境的适应性 随着网格服务的兴起，计算节点、数据节点等各类资源可以动态地组成各种 虚拟组织，并实现资源的动态加入和离开，这种虚拟性使我们能够很好地利用网 格中各种资源。但在我们获得了网格环境虚拟性的好处同时，这种虚拟性也带来 了网格环境的不确定性。这种不确定性往往表现在资源使用状况不确定如出现瞬 时峰值、资源退出整个虚拟组织的不确定性以及资源由于各种原因而出现失败的 不确定性。而这种不确定性使我们难以预计到我们真正使用资源时候究竟有无资 源可用或者说究竟有没有满足我们最低要求的各种资源可用，从而我们提倡虚拟 性说希望得到的如更大规模的资源共享或者服务与资源的松耦合关系就根本无 法达到。 针对网格这种不确定的应用环境，进行资源预约工作理想的状况就是：提出 资源预约请求时候根据提出时候的网格环境作出判断，当请求遭到拒绝时候能够 和用户协商是放弃预约请求还是在一定时间内继续等待有否更好的、满足要求的 资源加入；而当资源动态加入时候，我们能得知并且重新调整我们之前做好的预 约工作，使用新的更好的资源其为我们进行服务的执行；当资源离开发生失败状 况而不能继续运行的时候，我们也可以不拒绝之前预约好的预约请求，而是调整 其使得能把正在使用该资源的服务迁移到还在虚拟组织中的资源进行执行。 提高资源预约对网格不确定环境的适应性，目的是实现基于自适性资源预约 的可按插网格服务，把自适性资源预约机制加入到我们的可接插网格服务【1 2 1 中 去，通过资源预约机制来提高对网格这个不确定环境的适应性，使得我们在使用 3 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 资源之前确定有资源和有什么样的资源为我们服务，对我们服务所能达到的一个 性能层次有个很好的估计。另外也可以使得我们在使用资源过程中确定有资源为 可能的资源使用失败作一个后备。这样，我们既通过可接插网格服务给网格带来 了它所需要的虚拟性，同时也通过资源预约来限制它所带来的不确定性，整个网 格环境就更有利于作为我们提供服务和运行服务的基础设施。 二、证明资源预约对网格环境的作用并指明其着重研究方向 缺乏了对资源预约有效性必要的严格数学证明，缺乏了发现资源预约的问题 所在，从而也就不能对这些问题进行好好的研究和解决，使得目前对资源预约的 应用并不广泛。本文试图在力所能及的范围下，在理论上给出资源预约对网格环 境，或者其对在网格环境下的各种应用和服务的执行所带来的影响作出探讨，譬 如资源预约是否真的带来额外的耗费而超过了其所带来的作用，或者是否能够使 应用或者服务在多次执行下，其变化幅度更小。初步了解了这些问题，从而使我 们能够在理论上对资源预约对网格环境的作用有个更加中肯的认识，避免主观臆 断或者实验条件偏差带来对资源预约对网格环境作用的认识偏差。 同时也可通过证明发现与资源预约对网格环境作用产生重要影响的参数，譬 如在什么应用背景下适宜和需要进行资源预约，什么应用背景下进行资源预约却 并不是十分值得去做，从而在以后针对资源预约研究或者资源预约对网格环境作 用的研究能把精力和着重点放到更加值得研究和容易研究出成果的地方，可以为 我们以后进行资源预约的相关工作，提高资源预约对网格环境作用指明方向。 三、完善可接插网格服务，保证其所需必要的资源 可接插网格服务使得服务能够与计算资源动态绑定，也就是服务能够在其他 地方进行提供，解除了服务对底层计算资源的依赖性。然而，尽管服务能够与计 算资源动态绑定，但这种动态性相对于部署时候的静态绑定来说的，无论是静态 绑定还是动态绑定，它在执行时候同样需要特定的计算资源来进行服务的执行。 假如在运行时候并没有或者并没有适合的计算资源来执行我们所需要的服务，那 么就算我们的服务能够很方面的进行可接插，但无论接插到哪里都不能执行，失 去提供服务的最基本要素资源就失去了它最本质的需要。而恰恰可接插网格 服务并没有提供在运行时候的确有资源来进行服务执行的保证。 因此，我们提高网格环境下资源预约的可适应性，以便实现基于自适性资源 4 中山大学颈士学位论文网格环境下资源预约的可适应性分析和优化 预约的可接插网格服务，把自适性资源预约机制加入到我们的可接插网格服务中 去，目的就是让资源预约提供可接插网格服务所缺少的在运行时候的确有资源来 进行服务执行的保证，保证资源在某个时间范围内和在某个限度内提供给客户或 者服务使用，使得至少我们有资源可用，然后再来考虑是否利用可接插网格服务 的技术来在服务真正执行时候选择最好的资源来使用，以达到最后的服务性能效 果。 1 3 相关工作比较 一、g a r a ( g l o b u sa r c h i t e c t u r ef o rr e s e r v a t i o na n da l l o c a t i o n ) 应用程序需要资源发现和资源选择机制，根据标准的q o s 提出的可靠性、可 用性、价格、和性能，应用程序在候选资源中选择其一。应用程序同样需要提前 预约机制，规定一个提前的预约，使资源可以在需要的时候被分配。实现这些机制 和应用程序存在四个问题： 缺乏提前预约支持的系统配置； 应用程序不只是单一的资源的发现、预约和分配，而且需要对潜在的复杂 资源进行收集； 资源可以是广泛的异种类型：计算机c p u 、网络、硬盘、内存等； 资源一般都分布在不同的管理域中并且隶属于不同的控制策略和机制。 g l o b u s 提前预约和分配体系结构( g a r a ) 【4 l 是由a r g o n n el a bg l o b u s 项目提 出，以支持端到端的q o s 保障，是目前计算网格中最广为接受的q o s 框架，它的 目标是为发起预留的客户端或应用程序能从资源管理者处获得特定的0 0 s 提供 保障，并解决了上述这四个问题。 g a r a 有如下特点： 将预留资源与计算元素看作同样的实体，独立的进行创建、监测和管理； 支持异构资源类型； g a r a 分层次结构，使得资源集的发现、预留、分配和管理可以被包装 在c o - r e s e r v a t i o na g e n t s 和c o - a l l o c a t i o na g e n t s 中 5 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 图1 - 1g a r a 的体系结构 从开始预约时候看，g a r a 要求用户必须在提交资源请求时候，将各种参数以 固定的形式提交，这样往往会导致用户与资源管理者进行多次的协商以使得预约 能够被接受。从预约成功后到看，“队无法提供一种机制来使得用户在真正使 用资源时候，能够获得当前最好的资源来执行其需要的服务，不能够利用网格虚 拟性所带来的好处。 二、a s t a n d a r d s - b a s e dg r i dr e s o l l r b r o k e r i n gs e r v i c e 文章【5 1 提出此服务是为了解决各个网格中间件之问的互操作性问题而提出来 的。其在g l o b u st o o l k i t4 、n o r d u g r i d a r c 和l c g 2 这几个网格著名的中问件之 间实现了互操作，使用的方法是为这几个网格著名的中间件分别设计插件，然后 当基于这些中间件上的应用向运行于不同中间件上的资源提交任务时候，这些插 件就被用作屏蔽不同中间件之间的差别了。 有了这些插件，当然我们进行资源预约工作的范围就可以放宽很多，可以避 免网格异构性带给资源预约很多的不便。同时，在这个服务当中采取了一种资源 排序方法，其排序的标准是t o t a lt i m et od e l i v e r y ( 1 1 d ) ，也就是从任务提交到 输出文件到达用户的时间，包括输入时间、等待时间、任务执行时间和输出时间。 资源管理系统是选择t t d 最小的供给用户进行使用或者预约。 然而其工作并不具有通用性，一旦新的更加适用的网格中间件出现，它就要 6 中山大学硕士学位论文网格环境下资源预约的可适戊性分析和优化 重新对插件进行修改或者编写新的插件，以新的网格中间件出现带来的变化。另 外，由于每个任务的输出时问不能确定，这个服务虽然提出其作为排序标准的一 部分，但是在真正进行实现和评估时候并没有加入这个时间。 三、r e s e r v a t i o ns c h e d u l e rw i t hp r i o r i t i e sa n db e n e f i tf u n c t i o n s ( r s p b ) 文章 6 1 提出了一种新的资源预约方法，这个资源预约方法是基于优先级和利 益函数的- r 骼e a t i o ns c h e d u l e rw i t hp r i o r i t i e sa n db e n e f i tf u n c t i o n s ( r s p b ) 。 当资源调度器处理各个用户提交其资源预约请求时候，会考虑不同预约请求的优 先级。同时针对每一个预约请求也附带一个利益函数，通过其可以计算这个利益 函数，可以计算当资源调度系统能够满足用户请求时候，其可以获取的收益，同 时当用户愿意协商更低层次服务水平时候，它就可以通过这个函数来标明虽然利 益受到降低，但还是大于零的情况。 这种方法目前只可以预约c p u 资源，而且每次只能预约一个资源，无法进行 协同预约，以同时预约多个资源。另外其假设其进行资源预约或者实验的环境中， 所有机器都是在同构的平台上面的。当用户的资源预约请求到达时候，它并不是 第一时间处理这些请求，而是将在一定的时间范围内提交的所有资源预约请求收 集起来，然后集中处理。 四、可协商的资源预约服务 分布式计算需要一种提前预约机制，能够预约将要使用的资源从而保证任务 的顺利完成。在多数情况下，客户端的需求是瞬时变化的，服务端的资源使用状 况也是瞬时变化的。只是单纯的预约容易造成资源的过量供给或资源的供给不 足，这就要求客户端和服务端能够根据自身当前和今后的状况，对所要使用的资 源进行实时的动态协商，使得双方都做出适当调整达成一致。 为了能更好、更方便地使用互联网上的共享资源，文章1 7 1 设计并实现了一种 可协商的资源预约服务。此项服务主要以g l o b u s 项目的g a r a 协议为基础和参照， 对其做了一些修改和扩充，使得用户可以预约网络上的共享资源，并且在整个预 约过程中，可与资源的提供者进行协商，随时变更自己的预约请求。在可协商的 资源预约服务中资源预约协商状态转换可见图1 2 。 7 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 图1 2 可协商的资源预约服务资源预约协商状态图 可协商的资源预约服务能够提供一种机制使得在开始通过预约后，当用户需 要更好的资源或者对资源预约做出修改时，通过协商的形式来修改预约。协商无 疑能够更好的获取用户与资源管理器之间的最佳效果，但这种形式对用户的要求 高，而且并不能保证的确找到最好的。如果可以把这个协商的工作交给资源管理 器和选择器服务，而且能保证在运行时候的确找到最好的，这是我们最理想的效 果。 五、一种兼顾排队任务的资源预留机制 文章【8 j 提出了一种兼顾排队任务的资源预留机制，其目的是优化衡量支持资 源预约调度系统的性能的其中一个指标平均等待时间，即排队任务( 非预留 任务) 进入本地资源调度队列后，在提交到资源上运行前的平均等待时间。每个 资源上设置了两个等待队列：调度队列和预留队列。调度任务队列用来放置排队 任务，如果有资源空闲，它们按照一定的调度策略( f c f s 、l w f 、b a c k f i l l i n g 等) 把任务调度到空闲资源上运行。预留队列是用来放置已预留成功但没有开始运行 的任务，它们以预留请求时得到的实际开始时间的前后顺序排列，为了保证这些 预留任务的执行，只要时间达到实际开始时间，则剥夺正在资源上运行的排队任 务，而被剥夺的排队任务回到调度队列中等待下一次调度。 兼顾排队任务的资源预留请求过程可见图i - 3 。兼顾排队任务的策略思想是 在每个资源上设置阈值w m a x ，表示此资源上排队任务不能容忍的平均等待时间。 当资源上排队任务的平均等待时间超过w m a x 后，在调度系统决定是否接受新的 8 申山大学颈：上学位论文鼹格环境下资源预约的可适应性分析瓤优化 预留请求时，必须加强限制条件，使得推迟或者拒绝更多的预留请求，减少预留 任务占用的资源量，使得一部分排队任务尽快获得空闲资源以减少m w t 。 图1 - 3 兼顾排队任务的资源预留请求过程示意图 1 4 本文特色和贡献 一、提供并验证了资源预约有效性的初步证明 本文首先对资源预约问题作一个详细的表述，这个表述包括了为了建立讨论 资源预约问题所建立的应用模型而涉及的各个内容的数学表示，从而根据这些资 源预约问题的表述来展开对整个资源预约问胚的证明和探讨。 根据这个问题的表述，本文分别建立了一个有资源预约功能和一个没有资源 预约功能的应用模型，该应用模型主要是针对各个任务在一个有资源预约功能和 一个没有资源预约功能的资源上运行时间比较，然后通过详细的数学证明过程， 证明了以下三点：当使用了资源预约功能，同一任务执行多次时候，其时间的变 9 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 化程度减低；当使用了资源预约功能，任务的执行时间并不一定会增加，甚至在 某些情况下，使用了资源预约功能能够使任务的执行时间减少；当对过去的执行 情况有了收集和详尽的统计后，我们能更精准地预测未来的执行时间。除了在理 论上详细证明这三点之外，我们也在模拟实验中建立相应的模拟模型，而通过在 模拟模型上的实验，同样验证了这三点的正确性。 本文对资源预约问题的表述和根据这些表述所建立模型之后作出的三点证 明，可以作为资源预约有效性的初步证明。有了这个有效性的初步证明，从而使 得我们在以后针对资源预约研究或者资源预约对网格环境作用的研究时候，能把 精力和着重点放到更加值得研究和容易研究出成果的地方，为我们以后进行资源 预约的相关工作，提高资源预约对网格环境作用指明方向。 二、提出并验证了不同类型资源进行预约的方法 针对目前在网格这种不确定的应用环境下，资源预约工作的适应性并不高的 状况，本文首先改善了用户对数值型资源的预约工作：第一方面，允许用户不是 用固定的形式提出预约请求，而是可以采取一种更灵活的方式以一个范围来 提出用户的资源预约请求；第二方面，更进一步，允许用户提出一定的标准供给 资源管理系统或者资源调度系统，由其使用这些标准来匹配用户提出的资源预约 请求与当前网格环境下的可以供给用户使用或者预约的资源，使其能够在用户允 许的范围内接受用户提出的资源预约请求，把资源预约请求的拒绝率降低；第三 方面，不仅仅允许标准的存在，也允许资源管理系统或者资源调度系统对各个预 约子资源进行分别匹配，然后根据用户提供的反映对各个子资源偏好的权重和一 定的策略来对各个资源管理系统或者资源调度系统感兴趣的资源进行一个评级， 把根据这种算法算出来最优的供给用户进行使用或者预约 另一方面，针对目前资源预约工作预约的往往都是容易预约的资源，譬如很 多是数值型资源如c p u 和带宽等等，本文尝试了对一些较难预约的资源，譬如非 数值型资源如操作系统等资源的预约进行了一个探讨，基于的方法也是允许资源 管理系统或者资源调度系统对这些非数值型资源进行分别匹配，然后根据用户提 供的反映对各个非数值型资源偏好的权重和一定的策略来对各个资源管理系统 或者资源调度系统感兴趣的非数值型资源进行一个评级，这个评级可以结合对数 值型资源的评级来对各个资源进行一个综合的评价，而真正选择最优的资源供给 用户进行使用或者预约。 中山大学硕士学位论文 同格环境下资源预约的可适应性分折和优化 对旧有方法的改善以及新方法的提出，都在我们的模拟实验中分别进行了验 证。验证结果表明，本文提出的方法是的确能够提高资源预约请求的接受率以及 网格环境下各个资源的使用率。 三、为不同企业提供新的合作方式以及市场发展模式 把自适性资源预约机制加入到我们的可接插网格服务中，使得我们能够提供 基于资源预约的可接插服务，这样可以促使不同的企业往更专注于适合其自身发 展方面的工作：部分企业( 尤其是中小型企业) 可以专注于服务的开发，例如如 何使得服务更加高效，算法更加优化等，因为有资源预约的机制，所以其并不需 要对真正使用服务时候没有或者没有好的资源过分担心，即可通过服务本身的提 供实现盈利；另外一些企业如大型的服务器提供商则可以专注于寻找适合或者高 质量的计算资源或者数据资源，并加强对资源的管理使得资源能够保持为用户提 供高服务质量的状态，从而通过提供资源而获利。 把自适性资源预约机制加入到我们的可接插网格服务中去，目的就是可以令 到不同的企业可以从自身的优势和需要出发，动态加入各种虚拟组织：各服务拥 有者可以动态加入各种虚拟组织，以服务市场的形式提供不同的服务给客户，在 客户有需求时，就临时租赁资源；各资源拥有者也可以动态加入各种虚拟组织， 寻找需要其提供服务的或者等待资源管理器来使用它去为资源需要者提供服务， 对整个网格环境发挥其作用。这样，无论是服务本身还是计算、数据等资源提供 者等都得到全面发展，从而提供了一种新的企业合作方式。 1 l 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 第2 章论文理论和实现基础 2 1 关于网格和可接插网格服务 网格( g r i d ) 是把地理位置上分散的资源集成起来的一种基础设施。通过这 种基础设施，用户不需要了解这个基础设施上资源的具体细节就可以使用自己需 要的资源。分布式资源和通信网络是网格的物理基础，网格上的资源包括计算机、 集群、计算机池、仪器、设备、传感器、存储设施、数据、软件等实体，另外， 这些实体工作时需要的相关软件和数据也属于网格资源。 书【9 】中把网格描述为：“网格是构筑在互联网上的一组新兴技术，它将高速互 联网、计算机、大型数据库、传感器和远程设备等融为一体，为科技人员和普通 老百姓提供更多的资源、功能和服务。互联网主要为人们提供电子邮件、网页浏 览等通信功能，而网格则能提供更多更强的功能，它能让人们共享计算资源、存 储资源和其它资源。”网格资源除了包括能够通过网络使用的一般资源外，还包 括在网格设备旁边工作的人力资源。有人把网格看成是未来的互联网，国外媒体 常用“下一代互联网”、“国际互联网2 ”、“下一代万维网”等词语来描述网格相 关技术。 网格服务是i a nf o s t e r 等人针对w e b 服务存在的缺点，结合w e b 服务和网 格计算的优点，提出的新的计算体系，其主要特点是： 大规模资源共享【9 l ：可用统一的方式共享高性能计算机、高速磁盘阵列、 天文望远镜、传感器、遥感设备( r s ) 等各式各样的资源。 有状态的服务实例【1 0 l ；与无状态的传统w e b 服务相比更适合包装实时资 源。 非集中管理的动态虚拟组织【1 1 】：更好地支持为完成一项合作而动态组成 的合作关系。 在原有网格服务的基础上，重新定义服务接口，实现服务与资源松绑，以及 中山大学硕t 学位论文网格环境下资源预约的可适应性分析和优化 运行时的动态绑定。类比于普通的家电，只需要在插上电插座后就可以对外提供 服务的这种性质，以及硬件即插即用的思想，把具有这种性质的服务称为可按插 网格服务( p l u g , g a b l eg r i ds e r v i c e ) 0 2 1 。图2 - i 显示了可接插网格服务的总体设 计。 图2 - 1 可接插网格服务总体设计图 尽管服务能够与计算资源动态绑定，但这种动态性相对于部署时候的静态绑 定来说的，无论是静态绑定还是动态绑定，它在执行时候同样需要特定的计算资 源来进行服务的执行。假如在运行时候并没有或者并没有适合的计算资源来执行 我们所需要的服务，那么就算我们的服务能够很方面的进行可接插，但无论接插 到哪里都不能执行，失去提供服务的最基本要素资源就失去了它最本质的需 要。而恰恰可接插网格服务并没有提供在运行时候的确有资源来进行服务执行的 保证。 2 2 关于网格中的资源 资源可以理解为对用户存在利用价值的东西，如：计算机，高性能网络设备， 各种仪器，大容量存储设备，各种科学数据，各种软件分布式文件系统，数据库 缓冲池等。服务是对现实世界中业务活动的一种抽象与建模，用于提供访问某种 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 资源的能力。例如，读取文件和创建进程、向客户提供城市公车路线、或向电视 观众提供未来2 4 小时电视节目表等，这些业务均可抽象为一个服务。 网格环境中的资源包括处理器、存储系统、目录、分布式文件系统、分布式 计算机池、计算机集群、应用软件、数据、信息、知识以及天文望远镜、雷达和 家用电器等设备和仪器，并具有面向用户和透明性的特点。用户可以在不考虑资 源位置的情况下，方便地使用资源。此外，资源也具有动态演化的特性。 网格环境中，服务是一种重要的资源，可以被看作一种网格应用组件，用于 提供访问某种资源的能力，例如读取文件和创建进程等。服务通常以接口的形式 提供，在网格环境中通过协议进行请求，而资源共享则通过服务实现。通过选取 和结合使用适当的服务，开发人员能快速地构建大规模分布式应用。 2 3 关于资源预约 当可用资源非常丰富时，可以假定作业在提交之后就可以立即获得所需的资 源，因此不需要任何形式的资源预约。如果由于资源稀缺或者其他方面的原因导 致以上假定不能成立，就需要资源预约。 被大多数人使用的对于资源预约的定义是：资源预约是在与资源拥有者协调 后所获取的，在确定的时间段内，对资源能力的一个很有可能受到限制或约束的 能力代表【1 3 】。另外资源预约也指为了在随后时间内使用资源而进行要求的过程。 图2 - 2 显示了在【1 3 1 中的资源预约状态转换图。 静态预约( s t a t i cr e s e r v a t i o n ) 指在资源的初始化时就已经预约了资源，并且 预约的资源在资源的整个生命期都持续可用。如果预约的开始时问或者预约的期 限可以变化，则称为动态预约( d y n a m i cr e s e r v a t i o n ) 。动态预约的资源即可从预 约发起时刻开始，也可以在发起之后的某个协定的时刻开始。立即开始的动态预 约称为立即预约( i m m e d i a t er e s e r v a t i o n ) ，将延迟开始的动态预约称为提前预约 ( a d v a n c er e s e r v a t i o n ) 。 资源协商达成后，用户可以在协定的时间范围内使用协定的资源作业的实 际执行过程所需的时间往往与协定的使用时间有差别。如果作业提前完成，则剩 1 4 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 余的未使用的资源可以分配给其他作业。如果作业在协定的期限内不能完成，则 需要进行再次资源协商，以决定在预留期限完成之后如果处理未完成的作业部 分。一方面用户可以和当前预留的资源所有者进行协商，预留新的资源。另一方 面用户也可以和其他的资源所有者协商，以便将为完成的作业迁移到其他的预约 的资源。 图2 - 2 资源预约状态转换图 除用于网格资源调度领域之外，资源预留相关的研究和应用主要集中在计算 机网络和实时多媒体系统研究领域。为了支持i n t e r n e to o s ，研究人员提出了资 源预留协议r s v p ( r e s o u r c er e s e r v a t i o np r o t o c 0 1 ) 1 1 4 l 和采用r s v p 的综合业务 i n t s e r v ( i n t e g r a t e ds e r v i c e s ) m l 体系结构。r s v p 是一种可用于不同o o s 服务 的资源预留协议。它通过建立一条端到端的路由，使无连接的网络增加了面向连 接的特性，从而既利用了无连接的网络对多种业务的承载能力，又提供了接近面 向连接的网络的q o s 。综合业务模型是对现有疋网络模型的一个增强结构。它 在服务类型上可以支持尽力服务( b e s t - e f f o r ts e r v i c e ) 以外的保证型业务 ( g u a r a n t e e ds e r v i c e ) 【1 6 l 和负荷受控业务( c o n t r o l l e d - l o a ds e r v i c e ) 栩，在实现机 制上这种模型要求网络节点维持每个业务流的状态，并在分组发送之前通过资源 预留设置协议建立一条预留了资源的“虚拟”虚电路，然后通过流量控制机制实 现相应的q o s 。 2 4 关于网格模拟工具和g r i d s i m 为了研究网格资源管理与调度的不同策略与具体算法，需要通过实验验证其 中山大学硕士学位论文网格环境下资源预约的可适应性分析和优化 性能，同时通过调整参数确定其适用的范围，这是一个需要重复的过程，然而网 格所特有的动态性和自治性，使得建立这样的试验环境十分困难。即使对于能够 利用网格实验平台的用户而言，限于实验平台规模、应用的类型、性能监测等也 很难，利用实验平台对其资源管理与调度策略和算法做出全面的评测。因此，在 网格资源管理和调度的实际研究过程中，采用的方法是先建立网格模拟环境，然 后在网格模拟环境下，通过变化资源配置参数、应用的类型、评测其性能、确定 其适用条件，最后再在实验平台或实际的网格环境中验证算法的性能和模拟结 果。目前的网格模拟工具主要有b d c k s i 埘、m i c r o g r i d l l 引、s i m g r i d ：o 、s i r e j a v a l 2 1 】 和g r i d s i m l 2 2 等。 2 4 1b r i c k s b r i c k s 墙j 由日本东京理工大学开发，实现了在全球计算系统下不同映射算法 的性能评估，用于在虚拟网格环境中进行资源分配策略的研究。它的基础模拟环 境是在高性能计算机上提供科学计算函数包的以c s 模式运行的全球计算系 统。它能够模拟资源的发现和查询、资源行为的预测、任务的虚拟处理、网络拓 扑结构等，采用的是集中式的全局调度方法。b r i c k s 允许开发者用b r i c k s 脚本 语言来配置全球计算环境。b r i c k s 只能模拟客户端和服务器端的交互，由此具有 一定的局限性。 2 4 2m l e r o g r i d m i c r o g d d 1 9 】由加州大学圣迭戈分校开发，是为了研究网格资源管理而提供的 一个虚拟的网格基础设施，用来给g l o b u s 建模，属于仿真g l o b u s 上的应用。 它是建立在g l o b u s 平台上，其基础仿真环境是利用g l o b u s 工具包建立起来的 网格环境。它能够很好地仿真资源的行为、资源的发现、任务的处理、网络等。 m i c m g f i d 的仿真结果接近实际，但需要用g l o b u s 构造实际的网格任务，因此 适用于真实系统开发过程中对映射算法的仿真评测。 2 4 3s i r e g 订d s i m g r i d 加】也由加州大学圣迭戈