（基础心理学专业论文）异构环境中的pe资源控制策略研究.pdf

异构王1 - 境中的p e 资源拧制策略研究 异构环境中的p e 资源控制策略研究 学科专业： 指导教师： 基础心理学 邱玉辉教授 研究方向：人工智能与认知 研究生：( b 2 0 0 4 0 8 8 ) 内容摘要 异构环境下的并发处理已经成为分布式系统研究领域的一个重要课题，而所 处理任务的资源分配控制则是提高分布式系统并发能力的一个关键途径。在一个 网络环境中，c p u 、存储能力、带宽、缓存，甚至是文件、信息等都统称为网络 环境中的资源。因此，针对所控制资源的不同，资源控制策略也各不相同，如果 将c p u ，存储等与节点性能密切相关的资源看作是p e 的处理能力，那么分布式 计算环境中的资源控制策略就分为面向p e 处理能力的资源控制、面向带宽的资 源控制以及面向服务的资源控制。本文以面向p e 处理能力的资源控制为研究重 点。深入探讨几种不同类型的资源控制策略。由于资源控制可分为任务划分、任 务调度和资源分配三个主要的阶段，因此文中主要要解决的问题是如何通过这三 个阶段的控制使得任务最终可以被有效完成。虽然优化资源控制中的任务调度策 略可以增加资源控制的有效性，但传统的集中式计算技术使得计算任务调度策略 随着网络规模的扩大和任务量的增加而成为瓶颈。因此单纯改进任务调度策略已 经无法完全适应资源控制需求，从其他方面改进资源控制策略的性能是在所难免 的。 本文在研究过程中除了对传统集中式资源控制策略进行了改进，还提出了分 散式的可处理d a g 的资源控制策略。另外，我们基于分布式认知理论的原理，提 出了一个可动态进行资源控制的模型，这个模型可以在任务性质发生变化时( 例 如q o s 要求) 动态调整资源控制的相关参数，以提高资源控制策略的灵活性和有 效性。最后在几个改进策略之间用5 个指标对其进行了综合分析。 本文的研究工作和创新点主要包括以下几个方面： 两南人学博l 。学位论文 一、构建了异构网络及p e 资源的数学模型及其实例一b w r a p 由于已有的资源控制策略研究中缺乏一个一个完整的数学模型中对资源、任 务之问的关系以及对p e 资源差异和网络性能差异进行抽象。因此本文提出了一 个通用的数学模型，对资源控制策略所适用的异构网络环境、异构p e 资源、任 务与环境之间的关系、任务与资源控制策略之间的关系进行了抽象。 提出了一个实例离散任务资源分配策略( b w r a p ) 模型构建。b w r a p ( b a l a n c e dw o r k l o a dr e s o u r c ea l l o c a t i o np o l i c y ) 是一个应用于这个通用数学模型 中的集中式资源分配策略，做为一个实例，b w r a p 说明这个通用的数学模型在 进行资源分配策略构建上，特别是集中式资源分配策略的构建上是有用并且有效 的。 二、构建了一个m a s t e r s l a v e 结构下可保证q o s 限制的资源控制策略m m p b w r a p 是一个通用数学模型的实例，它通过任务流的任务均衡解决了离散 任务流的资源分配问题，但它在构建网络环境的数学模型时忽略了网络通信的建 模，由于离散任务流的任务分配主要应用在实时系统中，而不具有q o s 限制的任 务流处理几乎是不存在的。因此在离散任务资源控制策略中进行网络状态的建 模，并保证其q o s 限制是必须的。另外，其高复杂度的求解算法也无法适用于大 型网络环境。 本文提出了一个基于主从结构的离散任务流资源控制策略m m p ( m i n m a x p o l i c y ) ，通过构建代价函数为最小化系统整体响应时间来实现任务均衡。而对代 价函数添加q o s 限制条件则实现了资源分配对实时系统时限的保证。 三、构建了一个可进行任务复制有效性检查的d a g 任务资源控制策略一e d c p 以上两个策略都只能针对事件驱动任务流，对于具有相互关联的d a g 任务 流来说，是无法适用的。已有的d a g 资源控制策略中，以基于复制的策略为主。 但这些策略都忽略了复制本身的开销以及复制有效性等问题。本文提出了一种改 进的基于复制的集中式资源控制策略e d c p 。它具有如下优点： ( 1 ) 在复制过程中引入了复制有效性检查，提高复制效率； i l 异构环境中的p e 资源控制策略删究 ( 2 ) 在复制过程中使用2 次目标函数g ，通过对g 的设置可以实现双目标资 源控制。 四、构建了一个可处理d a g 的分散式资源控制策略一c d r a p 由于以上提到的集中式资源控制策略都无法适用于大型网络环境( 如p 2 p 网络) ，因此分散式的资源控制策略成为资源控制策略的重要分支。分散式资源 控制策略可以绕过集中式计算的瓶颈。但是已有的分散式资源控制策略都无法处 理d a g 任务流图。因为d a g 图中任务间的牵制关系很难使任务本身根据局部 消息来获得全局稳定。希望能够在满足d a g 任务间牵制关系的前提下发挥分散 式资源控制策略的优势，即资源和任务本身的高度自治化。基于以上考虑我们提 出了一种基于聚类的分散式资源控制策略一c d r a p 。c d r a p 使用消息机制来传 递任务间约束关系，但是资源分配的处理则不采用传统的集中式计算，而是使用 分散式计算原理( 移动a g e n t 的自我判断机制) 。使用处理器中间件( b r o k e r ) + 订 阅发布( s u b s c r i b e i s s u e ) 消息传递机制作为支撑结构。c d r a p 可分布式处理任务 间具有相互关联的任务流，并且使得普通机群高效处理大量任务成为可能。 五、基于分布式认知理论的动态资源控制策略模型和4 种资源控制策略的综 合性能分析 上述4 种资源控制策略，分别适用于任务驱动和数据驱动的任务流，并且适 用环境逐步向大型网络扩展。但是上述的这些策略中都是用户要求固定的资源控 制。若用户对任务执行需求发生变化，那么上述的这些资源控制策略都会出现相 应的瓶颈。例如可处理d a g 任务图的分散式资源控制策略c d r a p ，从实验数 据可以看出当策略所应用的网络状况不好时，c d r a p 的性能会大受影响。因此 一个改进c d r a p 的有效手段是使得c d r a p 中移动a g e n t 的迁移策略随网络质 量的变化而变化。本文受分布式认知概念启发，提出了一种基于分布式认知理论 的动态资源控制模型，在该模型中，网络环境的特征会随着任务性质的变化而发 生凸显变化，因此该模型对于提高资源控制策略的灵活性和有效性上具有很大帮 助。 最后针对上面提出的4 种资源控制策略，对其进行了5 个指标的综合分析。 两南人学博卜学位论文 关键词：p e 资源控制任务调度资源分配移动a g e n t 异构环境中的p e 资源挡制策略研究 r e s e a r c ho np er e s o u r c ec o n t r o lp o l i c yi nh e t e r o g e n e o u s r e s e a r c hd i r e c t i o n ：a r t i f i c i a li n t e l l i g e n c e a u t h o r ：y a n g , j u a n ( b 2 0 0 f f 0 8 8 ) o n ev i t a lm e t h o do fe n h a n c i n gt h ep e r f o r m a n c eo fad i s t r i b u t e ds y s t e m i st oi m p r o v ei t sc o n c u r r e n c yc a p a b i l i t yw i t hr e s o u r c ec o n t r o la sac o r e t h er e s o u r c ec a l lb er e f e r e dt o a n yh a r d w a r e sa n ds o f l w a r e so n l y d e p e n d i n g o nw e a t h e rt h e ya r en e c e s s a r yf o rt h eo t h e r s t h i sp a p e rl i m i t s t h er e s o u r c ed e f i n i t i o na st h ep r o c e s s i n ge n t i t yf o rt h ed e e p l yd i c u s s i n g c e n t r a lr e s o u r c ec o n t r o lm a k e st h ef o u c u so nj o bs c h e d u l i n gw h i c hi s t h em a j o rb r a n c hi nr e s o u r c ec o n t r 0 1 t h i sp a p e rs t u d i e do nh o wt o i m p r o v e t h ec e n t r a lr e s o u r c ec o n t r o lp o l i c e s c e n t r a lr e s o u r c ec o n t r o lp o l i c e sh a v eg o taw o n d e r f u lr e s u l tf o rt h e l o c a la r e an e t w o r k s h o w e v e r , w i t ht h ed e v e l o p m e n to ft h en e t w o r k s t h e r u n n i n ge n v i r o n m e n to ft h ed i s t r i b u t e ds y s t e m sh a se x p a n d e df r o ml o c a l a r e an e t w o r kt oo p e n ，l a r g es c a l e dn e t w o r k s ，s u c ha sp 2 pn e t w o r k c e n t r a l r e s o u r c ec o n t r o lp o l i c i e sh a v et of a c eah u g eg a pb e t w e e ni n c r e a s i n gj o b n u m b e r sa n dt h ec o m p u t i n gb o t t l e n e c k d e c e n t r a l i z e dr e s o u r c ec o n t r o l v 两南人学博 ：学位论文 p o l i c yi n a v o i d a b l ye m e r g e d t os o l v et h i sp r o b l e m t h i sp a p e ra l s os t u d i e d t h ed e c e n t r a l i z e dr e s o u r c ec o n t r o lp o l i c i e s t h er e s e a r c hw o r ka n dc r e a t i o n so ft h i sp a p e ra r ei n c l u d i n ga sf o l l o w s ： 1 c o n s t r u c t e dam a t h e m a t i c a lm o d e lf o rh e t e r o g e n e o u sn e t w o r k sa n d p er e s o u r c e sw i t ha l li n s t a n c eb w r a p t h e r ei sa na b s e n to fa ni n t e g r a t e dm a t h e m a t i c a lm o d e lf o rt h er e s o u r c e c o n t r o lp o l i c i e sw h i c hc a l le f f e c t i v e l yd e s c r i b et h er e l a t i o n s h i pb e t w e e n j o b s ，r e s o u r c e s ，a n d e n v i r o n m e n t t h i s p a p e rg a v e at h r e e s t e p c o n s t r u c t i n gm e t h o dt ou n i f o r mi t a sa ni n s t a n c e ，ac e n t r a l i z e dr e s o u r c e c o n t r o lp o l i c yb w r a pi sb e e ng i v e n 2 c o n s t r u c e dac e n t r a l i z e dr e s o u r c ec o n t r o lp o l i c y m m pw h i c hc a n g a n r a n t e et h eq o s l i m i t su n d e rm a s t e r s l a v ea r c h i t e c t u r e m m ps o l v e dt h ed i s c r e t et a s k s r e s o u r c ea l l o c a t i o nu n d e rm a s t e r s l a v e a r c h i t e c t u r e b e c a u s ew ec o n s t r u c ti t sc o s tf u n c t i o na sl i n e a rp r o g r a m m i n g p r o b l e m , t h es o l v i n ga l g o r i t h mi sn o tn e c e s s a r ya so t h e rc e n t r a lr e s o u r c e c o n t r o lp o l i c i e s 。 3 c o n s t r u c t e dac e n t r a l i z e dr e s o u r c ec o n t r o lp o l i c y - e d c pw h i c hc a n e f f e c t i v e l yc h e c k i n gt h ed u p l i c a t i o np r o c e s si nd a g r e s o u r c ea l l o c a t i o n e d c pc a ni m p r o v et h ep e r f o r m a n c eo fc e n t r a l i z e dr e s o u r c ec o n t r o l p o l i c i e sb a s e do nd u p l i c a t i o nt e c h n o l o g i e sb yc h e c k i n gt h en e c e s s i t yo f i t s d u p l i c a t i o n 4 c o n s t r u c t e dad e c e n t r a l i z e dr e s o u r c ec o n t r o lp o l i c y - c d r a pw h i c h a l s oc a nt r e a td a gt a s k s 异 勾环境中的p e 资源控制策略研究 c d r a p u s i n gm e s s a g e b r o k e r + s u b s c r i b e i s s u e p l a t f o r m t o d e s c e n t r a l i z e da l l o c a t i n gt a s k s r e s o u r c e sa n dc a l la c h i e v eaf a i r l yb a l a n c e r e s u l t 5 c o n s t r u c t dad y n a m i cr e s o u r c ec o n t r o lm o d e lb a s e do nd i s t r i b u t e d c o g n i t i o nt h e o r ya n da n a l y z e d4p o l i c i e sd e s c r i b e da b o v e t h ed y n a m i cr e s o u r c ec o n t r o lm o d e lb a s e do nd i s t r i b u t e dc o g n i t i o n t h e o r yc a r lp o po u td i f f e r e n tc h a r a c t e r so f as a m ee n v i r o n m e n tw h i c hc a n e f f e c tt h ee x e c u t i n go f ag i v e nr e s o u r c ec o n t r o lp o l i c y k e y w o r d ：p er e s o u r c ec o n t r o l ，j o bs c h e d u l i n g ，r e s o u r c e a l l o c a t e ， m o b i l ea g e n t v i i 独创性声明 学位论文题目：崖翅班缝生的曼登速控制篡堕班宜 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所矢，除丫义t t 特别加以标注和致谢的地 力+ 外，论文r f i 不包含他人已经发表或撰j j 过的研究成果，也不包含 为获得两南人学或其他教育机构的学位或证书而使州过的材料。与我 | 司j ：作的同志对本研究所做的任何贡献均已在论义中作了明确的 说明j ：表示谢意。 学位论文作者：撇签字日期：砷 7 年4 - 月，2 ，日 学位论文版权使用授权书 本学位论文作者完个j 7 解i j 撕南人学有关保留、使j h ：l 学位论文的规 定，有权保留， 向幽家有关部f 或机构送交沦义的复印件和磁盘，允 许论文被查阅和借阅。本人授权两南人学研究牛院叮以将学位论义的 全部或部分内容编入有关数据库进行检索，町以采厢影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：曲不保密， 口保密期限至年月止) 。 学位论文作者签名：糊 签字日期：如呵年年月2 - 2 - 日 学位论文作者毕业后去向： 导师签名： 签字日期： 工作单位：酉直盍鲎 电话：l ! 1 8 s 3 1 8 8 s ! 12 通讯地址： 亟虚盍芏i 士簋扭董焦! 塾牡堂堂睦 邮编：4 0 0 7 l 5 异构环境中的p e 资源控制策略研究 图 图 图 图 图目录 1 1 主妇问题中的资源控制4 1 - 2 分布式互连阿络分类7 2 - 1 c s 模式与移动a g e n t 模式的比较2 0 2 - 2 移动a g e n t 基本体系结构2 1 图3 - 1g ( j p f ) 2 8 图3 - 2b w l l a p 计算时间2 9 图4 1f o r k 结构图3 2 图4 - 2 实例f o r k 图3 6 图5 1 样例d a g 图3 8 图5 - 2t d s 中的复制过程4 4 图5 3t d s e d c p 性能对比4 6 图5 _ 4t a n h i d c p 性能对比4 6 图6 - 1 样例d a g 4 9 图6 - 2 任务5 的优先表5 7 图6 3 任务6 的优先表。5 7 图6 - 4 任务7 的优先表5 7 图6 5c d r a p 具有m u l t t a s k f ( 升) 与不具有m u l t t a s k _ f ( t ) 的性能比较一5 9 图6 - 6c d i l a p 的性能图6 0 图6 7 由c c r 所引起的c d r a p 性能变化图6 l 图7 1q o s 较低的任务分布图6 5 图7 2q o s 较高的任务分布图6 5 图7 - 3 某节点特征凸显率变化图6 6 两南人学博i ：学位论文 表目录 表3 - 1 两个n * n 矩阵执行时间2 8 表4 1 相笑参数定义3 3 表5 1e d c p 的相关参数表4 0 表5 - 2t a n h 上应用e d c a 的结果4 5 表5 - 3e d c p 数据采集表示例4 6 表6 - 1 时间耗费表4 9 表6 - 2c d r a p 的相关参数表5 0 表6 - 3c d r a p 的数据采集5 9 表7 - 14 种策略比较6 8 2 异构环境中的p e 资源抟! 制策略研究 第1 章前言 未来对计算速度、系统可靠性和成本实效性的要求必须促使发展另外的计算机模 型来取代传统的冯诺依曼型结构的计算机。随着计算机网络的出现，分布式计算 ( d i s t i b u t e d c o m p u t i n g ) 使得这个梦想成为町能。当用户需要完成任何任务时，分布式计 算提供对尽可能多的计算机能力和数据的透明访问，同时实现高性能与高可靠性的目标。 在过去的二十年里，人们对分布式计算系统的必趣迅猛发展。异构环境下的并发处理已 经成为分布式系统研究领域的一个重要课题，因为各种各样的应用系统( 如天气模拟计 算、实时系统中的数据流控制，图像处理，等) 都潜在地要求在这样的背景下进行代价函 数的构建。因此问题最终衍变成了如何提高系统进行自治并发处理的能力。系统自治并 发性除了可以通过硬件性能改进提高外，最主要的改进还是通过对所处理任务流的合理 资源控制来实现。分布式系统中的资源控制作为分布式系统控制算法中的一个重要分支， 主要解决任务均衡和资源分配问题。 1 1 理论意义 资源控制( r e s o l l l ec o n t r 0 1 ) 问题几乎随处可见，它最初从经典的任务调度问题( j o b s c h e d u l i n g ) 起源，随后延伸到我们日常生活中的每个角落。从车站调度到操作系统多任 务控制，处处都渗透着最优资源控制的思想。我们从一个家庭主妇合理利用资源做家务 开始理解资源控制所涉及的各个环节以及要解决的问题。首先我们把所有家用电器和能 源都看作是资源。而资源的最终使用者是主妇今天要完成的任务一“家务“。那么资 源控制的最终目的足使得主妇在最短的时间内完成这个名为“家务”的任务。整个资源 过程涉及到主妇如何有效将家务划分成不同子任务，以及如何根据资源限制将这些子任 务分配给不同的资源。最后在最短的时间内完成任务。 首先将这个名为“家务”的任务划分为洗衣、洗菜、拖地、抹灰尘等子任务，如图 1 - 1 。这个时候我们会发现这些子任务间有的相互有联系，有的没有联系，当使用资源不 3 西南人学博i 学位论文 属于同一类时，它们足相互间无关联的离散任务；相反，若它们使州的资源是同一类型， 那么它们之间由于受到资源有限性限制，所以它们的执行相互制约。 图1 - 1 主妇问题中的资源控制 然后根据任务间的关系进行任务调度，发现不同任务需要不同资源，而资源有时候 也需要利用其他资源进行协作，那么这个时候它的角色也是一个资源利用者，因此我们 在广义上将使用资源者看做是任务，而提供资源者看做是资源。因此在很多情况下，主 妇、洗衣机都被看作是需要资源的任务。相互问无关的任务调度比较容易，因为它们可 以并发执行，例如煮饭和洗衣服，而相互间有关联的任务则需要协商解决资源争用问题， 例如洗菜和洗抹布，它们都需要资源主妇和水。 从图1 1 中可以发现当把任务进行了调度以后，还需要将给这些任务分配适当的资 源，以保证任务的顺利执行。这个时候足具体的分配过程，它遵从调度结果。从上面的 分析町以看出，资源控制分为任务划分、任务调度和资源分配三个主要的阶段。而主要 要解决的问题则是如何通过这三个阶段的控制使得任务最终可以被完成。 最后将资源控制放入分布式计算中说明其必要性。分布式计算环境足构建的资源控 制策略的背景。由于推动分布式计算产生的主要冈素包括【l 】： ( 1 ) 同有的分布式应用。分布式系统以一种很自然的方式开始存在，例如主妇问题中各 资源足分布式存放而使用共享的。 ( 2 ) 性能成本。分布式系统减少了处理瓶颈。 4 异构王f 、境中的p e ；赉源控制策略研究 ( 3 ) 资源共享。 ( 4 ) 实用性和容错性。 ( 5 ) 可扩展性。系统容易扩大规模。 因此从l e l a n n 2 系统的分析町看出，分布式系统的的可扩展性、逐渐增加的实_ j 性和 更好的资源共享被认为足最重要的目标。而资源控制则是促进分布式系统有效提高自治 并发处理的能力的一个重要途径。 1 2 资源控制三阶段 1 2 1 任务划分 任务划分的一个荤要参考指标是所划分任务的粒度，粒度的定义为任务分解中影响 通信开销的所有单元的平均尺度。任务划分的粒度如果太大，则会降低并行度，因为潜 在的予任务间可能没有资源使用冲突，可以并发执行。而相反，如果粒度太小，则会增 大进程切换和相互间通信的开销。因此任务划分的主要f 1 标是在尽可能保证系统并行性 的前提下尽町能消除处理器间通信引起的开销。 任务划分的结果是将任务及任务间相互约束关系抽象成d a g ( 有向无环图) 的形式 提交给分布式系统进行任务调度和资源分配。每一个d a g 中的节点对应于任务，而节 点间的有向边则代表任务间的关系。与任务调度和任务分配相比，任务划分是一个相对 独立的阶段，属于另一个研究方向。因此这里不再详述。 1 2 2 任务调度与任务分配 在集中式资源控制策略中，任务调度足整个资源控制的核心部分。任务分配则只是 一个静态的环节，其时间耗费可以控制在一个预期的范围内。而对于分散式资源控制策 略来说任务调度与任务分配则是紧耦合的两个部分。其协作工作的有效性是资源控制策 略性能的决定因素。因此在讨论集中式资源控制策略时，主要针对的是它的任务调度策 略，而在讨论分散式资源控制策略时，主要针对的足任务调度和任务分配整体。 两南人学博i 学仙沦文 1 分布式计算环境 分布式训算环境足整个资源控制的应用背景，对其进行正确描述足至关苇要的。因 此我们考虑对分布式环境进行定义。首先我们从 3 】对“并行的”、“并发的”以及“分布 式的”这几个在内容上相互覆盖的关联术语的定义来对分布式系统有一个简单的描述： “并行的”指一个单一控制线程对数据集的锁步操作。 “并发的”指某些动作可以以任意次序执行。 “分布式的”指计算的成本或性能取决于数据和控制的通信。 因此某些研究人员【4 】认为如果系统的构件局限在一个地方，那么它就是集中式的， 如果构件不在同一个地方，且它们之间投有合作时，那么它被称为网络的，而如果构件 间存在紧密的合作，那么它才被称为分布式的。这个关于分布式的定义在今天p 2 p 网络 的高度发达的d 口提下已经无法适应，因为没有一个网络中的构件是纯粹的没有任何协作 的。而相反，大部分网络在很多时候都是只有有限的协作，因此这个关于分布式的定义 忽略了这种协作松耦合的情况。 而另外一些研究人员则认为计算机网络和并行计算是分布式系统的一部分【5 7 】。定 义一个分布式系统是一个对用户看起来像普通系统，然而运行在一系列自治处理单元 ( p e ) 上的系统，每个p e 有各自的物理存储空间，并且信息传输延迟不能忽略不计。 在这些p e 间有紧密合作。系统必须支持任意数量的进程和p e 的动态扩展。 我们沿用计算机网络和并行计算是分布式系统一部分的概念，认为现在网络结构中， 无论其拓扑结构如何，只要它存在一定的协作，那么它就足个分布式系统。s c h r o e d e r 8 】 定义分布式系统的特征如下： ( 1 )多处理单元( p e ) ( 2 )互连硬件 ( 3 ) 处理单元的故障无关 ( 4 ) 共享状态 2 分布式计算环境 分布式计算环境町分为同构网络和异构网络。同构分布式环境足传统资源控制研究 6 异构环境中的p e 资源控制策略研究 的酊提。但足随着网络多元化的发展，越来越多的分布式环境是由不同网络所构成。【9 】 提出了如图1 - 2 所示的网络环境划分。如我们前面所提到，我们认为网络是分缸式系统的 部分，因此不同种类网络间的资源控制是在异构分布式环境中进行的。对于资源控制 策略来说资源环境异构性这个特征至关苇要。 图1 - 2 分布式互连网络分类 图l - 2 从拓扑结构角度对网络环境进行了划分，其中规则代表规则拓扑结构网络， 它又分为静态拓扑和动态拓扑结构。静态拓扑网络由点到点直接连接组成。进程执行过 程中不改变。动态网络由交换信道实现，能动态配置满足通信要求。典型的规则网络有 立方体网络、超立方体网络、依里埃克网络等。而不规则网络则指网络中没有一个固定 的拓扑结构来描述网络构造，如p 2 p 网络，这种网络通常使用小世界模型【l o 】来描述它。 当然分布式环境的异构性除了包括网络拓扑结构的异构性外还包括分布式环境中p e 处理能力的异构性。如果考虑的资源控制策略是建于网络拓扑结构上层应用的，那么分 布式环境的异构性就主要由p e 处理差异来体现。为了构建一个抽象的分布式计算环境， 我们将每个独立的p e 看做是分布式计算环境中的节点，这意味着通信设备将被看做是 透明的。 3 异构分布式环境中的p e 资源控制策略 在一个网络环境中，c p u 、存储能力、带宽、缓存，甚至是文件、信息等都统称为网 络环境中的资源。因此，针对所控制资源的不同，资源控制策略也各不相同，如果将c p u ， 存储等与节点性能密切相关的资源看作足p e 的处理能力，那么分布式计算环境中的资 7 两南人学博l 学位论文 源控制策略就分为面向p e 的资源控伟r j 1 4 、面向带宽的资源控制【1 1 - 1 2 】以及面向服务的 资源控制【1 3 】等各种资源控制策略。本文以面向p e 处理能力的资源控制为研究熏点。深 入探讨几种不同类型的资源控制策略。 如l j 所述，资源控制总是有一个i ：t 标，例如在主妇问题中，资源控制的i ：t 标就为任 务完成时间最短，我们称构建的这个目标为资源控制策略的代价函数( c o s tf u n c t i o n ) 。 常见的资源控制的代价函数包括以下几类： l 、最小化整体响应时间【1 5 一1 8 】。若定义m a k e s p a n 为任务( 任务划分前规模) 的整体完 成时间，则资源控制代价函数为m i n ( m a k e s p a n ) 。若所处理任务间无关联，且无q o s 限制，那么这个代价函数等价于任务均衡( 1 0 a db a l a n c e ) 。 2 、在保证任务流q o s 限制( 如实时系统中数据流从输入到输出必须要小于的时延限制 【1 9 】) 的基础上最大化系统容错性 2 0 2 h 。若定义r o b u s t n e s s 为任务完成的可靠性保 证，那么资源控制代价函数为m i n ( r o b u s t n e s s ) ，且有q o s 限制条件。 3 、最大化系统吞吐量【2 2 】。若定义t h r o u g h p u t 为系统单位时间内能够处理的任务数量， 那么资源控制代价函数为m a x ( t h r o u g h p u t ) 。最大化系统吞吐量代价函数必须在系 统处理能力受除p e 以外其他资源限制( 例如带宽) 的情况下才能构建。 4 、将q o s 限制条件添加在其他代价函数中。可以通过限制条件的添加实现多目标的资源 控制。例如在满足任务均衡的前提下最大化系统吞吐罱 2 3 1 。 另一个影响资源控制策略选择的重要因素是任务类型。分布式环境中任务流类型【1 9 】 可分为： l 、事件驱动( e v e n td r i v i n g ) 任务流。事件驱动型的任务流其特点主要体现在任务流的 任务间没有数据依赖性 1 5 1 1 7 ，是离散的。针对这种类型的资源控制策略主要指实 时系统中的任务流控制，由于任务间相对独立，冈此可通过限制满足条件构建其代价 函数，并在解空间上应用各种启发式搜索策略来实现任务流的均衡负载 2 4 1 。 2 、数据驱动( d a t ad r i v i n g ) 任务流。数据驱动任务流则指任务流的任务间存在数据依赖 关系，任务流可用d a g 图准确描述1 2 5 1 1 8 1 1 2 6 ，且数据驱动任务流的资源分配不仅 仅局限于实时系统，其优化问题覆盖整个分布式系统。冈此针对d a g 图的资源分配 8 异掏环境中的p e 资源拧制攮略州f 究 成为资源控制问题的研究重点。 1 3 研究现状 1 3 1 事件驱动任务的资源控制 事件驱动任务的资源控制町分为实时( r e a l t i m e ) 任务调度和非实时( n o n - r e a l t i m e ) 任务调度，在没有q o s 限制的分布式环境中，事件驱动任务的资源控制就足任务均衡问 题。在q o s 限制条件严格的实时系统中，一旦q o s 被破坏，后果将是灾难性的。因此构 建实时任务调度代价函数的q o s 限制条件是必要的，或者通过多代价函数的构建来实现 q o s 保证。 1 、p a l i s 在【2 7 】中提出了一种基于预留的实时系统，提供了q o s 保证。在p a l i s 的调度框 架中任务是预先准备好的。 2 、分布式计算中一个很蕈要的计算模型是主从模型，s a h n i 在1 2 8 设计了一个有效的 适用于主从模型的资源控制策略，使得主从系统的任务完成时间最短。但它没有其 他q o s 限制约束条件。 3 、c y r i l 在 2 3 1 中提出了一个可保证系统的q o s 限制的基于主从网络模型的资源控制策 略，通过考虑边竞争问题保证了系统的q o s 限制，并构建最大化系统吞吐量代价函 数。 4 、c a s a n o v a 将主从模型5 1 a , n 格计算 2 9 3 2 ，提出一种任务町任意划分的资源控制策 略u m r ，p e 节点采用主从结构，主节点将任务划分成任意大小的事件驱动子任务， 并将其分配给从节点执行。这个策略受网络主从拓扑结构限制，无法适应于网格中 存在大量的p e 节点和异构网络连接的特征。 5 、 2 4 1 提出了基于聚类的扩散收敛策略，通过收敛因子进行邻接节点间的任务传递控制，当 收敛因子收敛时则说明系统整体己取得最大效益。 。 6 、j i m i n gl i u 在 3 3 1 提出了a l b p ，一种基于a g e n t 的任务均衡策略。它是扩散收敛 策略的改进。主要思想是将每个任务包装成一个移动a g e n t ，且具有一定的学习机制， 9 两南人学博i ：学位论文 使其町以根据从节点通信层获得的节点信息自动调整自己的移动策略，阵l 为移动 a g e n t 在网络中移动时只有髓陆和离开两种行为，因此每个a g e n t 可以动态设置自己 的臀陆策略和离j r 策略，分别用参数工和，表示，工和，分别表示了当时移动a g e n t 可能登陆或足离丌节点的概率。当以 0 ，t = 0 时表示该a g e n t 肯定会臀陆节点， 且在节点的执行队列中排队，等待执行，当工= 0 ， 0 时表示a g e n t 肯定会离开 节点。其中j 表示节点上已经有的a g e n t ( 等待执行的任务) 个数。 n ：= - l ，h ，+ 丘一。，l ，l ，+ + 。开表示大小为s 的a g e n t 组的个数随时间的变化率。当m ： 收敛到一个极小值时，表示该系统任务已经均衡分布。 1 3 2 数据驱动任务的资源控制 数据驱动任务体现在任务间某种原因而产生关联，具有相互牵制的特征。数据驱动的任务 流可以用d a g 准确描述。由于d a g 的任务调度是n p 完全问题 3 4 - 3 6 ，因此d a g 的资源 控制是采用启发式算法产生近似最优解。 1 、优先表和聚类调度是调度d a g 的经典方法。在优先表调度策略中 3 7 5 3 ，任务根据其 被预先赋予的优先级权重而顺序调度。【5 4 - 5 8 4 8 5 9 4 2 4 3 1 都是基于聚类任务调度的 原理是将通信密切的节点放在同一个聚类种，最终日的是要使得任务间通信耗费最小。 2 、【6 0 u 可以进行d a g 图的实时任务调度，即可以将任务的实时q o s 要求作为限制条件加入 代价函数。 3 、【6 1 ，w u 提出了一个运行时并行增加的d a g 调度方法 4 、 5 9 ，c o s n a r d 提出了一种参数化d a g 调度策略，开始生成符号线性任务聚类，然后将任 务聚类分配给处理节点 5 、 【4 6 d p s 是同构网络中调度d a g 非常有效的资源控制策略 6 、 【5 1 c p o p ，d a g 的芙键路径上的任务被分配给最快的处理器，其余的任务则根据h e f t 算法分别赋予优先级，并进行处理器匹配。它没有使用复制策略，性能比h e f t 差 7 、 【4 5 最好级别b i l ，给每个任务赋予优先级，一个给定处理器上的给定任务的b i l 值是 1 0 异构环境中的p e 资源控制策略研究 从给定任务剑出口任务的最长路径。给定任务在给定处理器上的执行时间用来计算最长 路径。平均执行时问用来保留任务而任务问平均通信时间则h j 来计算最长路径。b i l 策 略通过反复的至底向上执行公式 b i l ( v i ，p j ) = w ，+ m a x 时。s w c m ， m i n b i l ( v t ，p ) ，m i n t 。( b i l ( v l ，p i ) + c i ，) ) 来 为任务q 获得最佳处理器h _ 是处理器n 与p j 之间的通信耗费 8 、 【5 1 异构晟早完成时间h e f t ，将任务撤据其上限在调度队列中进行排序。它通过首先计 算所有任务对于所有处理器来说的船丁( v f ，p f ) 。具有最高上限的任务匕被分配给具有 角d f f , e f t ( v j ，p t ) 的处理器以虽然它也考虑在处理器的空闲时间槽中插入任务，但 通过使用复制技术依然能获得更好的性能 9 、【1 8 】 4 8 】任务复制调度t d s ，t d s 为所有任务h 都定义了：( 1 ) 一个喜欢的前驱处理器 劝r p d ( u ) ，这个节点是吩前驱节点集中的最后一个向u 传送数据的节点。( 2 ) 最 喜欢的处理器f p r o e ( v , ) ，这是使得任务u e f t ( v j ) 值最d 、的处理器。t d s 首先进行 任务聚类划分，然后根据每个任务的b l e v e l 值创建任务表，具有最小b l e v e l 值的任务被 赋予其最优处理器 1 0 、 4 2 4 3 动态任务复制调度s t d s ，是t d s 的改进版，它通过类似【4 5 】中至低向上计算出 l e v e l 值来替代t d s 中的b l e v e l 值，任务队列也通过l e v e l 值创建。但它在计算l e v e l 值时 也没有考虑通信耗费 1 1 、【2 5 】中的h n p d ，在异构存储系统中进行d a g 资源控制。 1 2 、【1 4 1 所提出的异构分布式系统中的资源控制策略t a n h 是基于t d s 的改进，它具有更好 的性能。 1 3 、 5 2 - 5 3 ，是基于优先级任务调度的，根据任务优先级将处理器分配给任务，没有考虑处 理器间通信 1 4 、【5