（计算机系统结构专业论文）基于新兴古典经济学的资源分配方法研究.pdf

，、 ，ttfi ；1j，i i ， y ： 1 j l k | ， at h e s i sf o rt h ed e g r e eo fm a s t e ri ns y s t e ma r c h i t e c t u r eo fc o m p u t e r r e s o u r c ea l l o c a t i o nb a s e do nn e wc l a s s i c 1 n - e c 0 n o m i c s b ys h e ng u o w e n s u p e r v i s o r ：p r o f e s s o rq i a oj i a n z h o n g n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 、 。、 。li、 ，麓器0矗，hf直鐾嚣书嚣 本人 的研究成 的研究成 作的同志 意。 学位论文作者签名：沁f 罚文 日期：汐6 必 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：阮f 列交 导师签名： 签字 日期：签字日期： ，i r ll j 1 1一 东北大学硕士学位论文 摘要 基于新兴古典经济学的资源分配方法研究 摘要 随着分布式系统的广泛发展和应用，资源分配问题也越来越突出。传统的资源分配 方法大多采用工程控制手段，通过进行全局的计算，将资源分配到最适合的地方。这种 分配方法在单系统中行之有效，因为单系统中资源的数量较少，而且可以做到同步。这 种方法在分布式系统中属于n p 完全问题，其计算规模随着系统规模的增大而剧增。事 实证明，简单地将这种方法引入到分布式系统中是行不通的，因此就衍生了一系列的资 源分配方法。其中智能优化算法和基于市场经济学的方法较为引入注目。然而，基于智 能优化方法的分配算法难以保证所得到的结果是最优解，而且前提条件是系统是稳定 的。基于市场经济学的资源分配方法将市场调配资源的方法引入到分布式系统环境中。 由于市场本身的分布性，这种方法显示出了其特有的优越性。然而，目前的研究显示， 这种方法执行的周期较长，不利于对时间要求较严格的资源分配。这种资源分配方法仍 处于研究阶段，其大多都使用新古典主义经济学的原理。 本文应用新兴古典经济学的原理来分析一个分布式系统环境下的资源分配问题。这 种分析方法重点关注如何提高整个系统的性能，使得客户得到的整体效用最大。其中有 效的资源分配方案将是达到这一目标的重要手段。其具体步骤是： ( 1 ) 根据分布式系统的网络拓扑结构和节点执行各种请求的能力，通过计算决定 处于哪种分配结构。由于各节点之间网络带宽的不同，决定了这各个节点之间交换效率 的不同，从而有着不同的交换系数。而各个节点对不同服务的执行能力不同，决定了任 意两种服务在两个节点之间存在不同的比较优势。这两个客观的条件决定了两节点之间 的关于这两种服务的分配结构。 ( 2 ) 在第一步的确定的分配结构下，通过对效用函数的求导，得出最优的分配点。 从而得出了请求在两节点之间的分配量。这一步使用的是新古典经济学中的边际分析， 这也是定价模型中使用的分析方法。 ( 3 ) 将请求按照计算值在两节点之间分配。依此类推，将所有的服务均衡地分配 到两节点之上。 通过这几步之后，每种请求都分配到最具有比较优势的服务节点上，每个服务器节 i i i 东北大学硕士学位论文 摘要 点都最大化提供其具有比较优势的服务，使得系统的整体性最优。其中，对各节点服务 网中请求的分配包含在专业化分工之内。这种思想将资源分配问题转化成专业化分工问 题，然后应用超边际分析，求出分配方案的最优解。 关键字：新兴古典经济，比较优势，分布式环境，资源分配 一 1 r 东北大学硕士学位论文 a b s t r a c t _ _ - l _ _ - _ - _ _ _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ l - - _ _ _ - - _ _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ i _ _ _ _ - _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ _ _ 一 r e s o u r c ea l l o c a t i o nb a s e do nn e wc l a s s i ce c o n o m i c s a b s t r a c t a st h ed e v e l o p m e n ta n dw i d e l yu s a g eo fd i s t r i b u t e ds y s t e m s ，i s s u e so fr e s o u r c e a l l o c a t i o na r eb e c o m i n gi n c r e a s i n g l yr e m a r k a b l e t r a d i t i o n a lr e s o u r c ea l l o c a t i n gm e t h o d sa r e l a r g e l yi m p l e m e n t e dt h r o u g hc o n t r o lt e c h n i q u ea p p l i e di n a r e a so fe n g i n e e r i n g ，w h i c hi s a l l o c a t i n gt h er e s o u r c ei n t oa p p r o p r i a t en o d e s t h i sm e t h o di se f f i c i e n ti nas o l es y s t e m ，f o r t h a tt h em o u n to fr e s o u r c e si nas o l es y s t e ma r es m a l le n o u g ht os y n c h r o n i z e sw i t he a c ho t h e r h o w e v e ri ti sp r o v e dt ob ean pp r o b l e mi nad i s t r i b u t e ds y s t e m ，w h i c hm e a n st h es i z eo f c o m p u t i n gw i l lb e c o m es i g n i f i c a n t l yl a r g ea st h es c a l e o fs y s t e mi n c r e a s e i nf a c t ，i ti s i n a c c e s s i b l ei fi t i ss i m p l yb r o u g h ti n t oad i s t r i b u t e ds y s t e m ，t h u sas e r i a lo fi m p r o v e d m e a s u r e sh a v eb e e nr e s e a r c h e da n di m p l e m e n t e di nr e a ls y s t e m s a m o n gt h e s ep o l i c i e s ， i n t e l l i g e n to p t i m i z a t i o na n dm a r k e t - b a s e dr e s o u r c ea l l o c a t i n gm e t h o d sa r ec o m p a r a t i v e l y o u t s t a n d i n g h o w e v e r , i ti sd i f f i c u l tf o ri n t e l l i g e n to p t i m i z a t i o n st oe n s u r et h es o l u t i o n sa r ea s o p t i m a la se x p e c t e d ，w h i c hi se v e ns oi ft h es y s t e m i su n s t a b l e t h em a r k e t - b a s e dm e t h o d sa r e p r o p o s e dt oi n t r o d u c em i c r o e c o n o m i c si n t od i s t r i b u t e ds y s t e m s ，w h i c hi sp r o v e d t ob eq u i t e s u c c e s s f u lf o rt h a tt h em a r k e ti so r i g i n a l l yad i s t r i b u t e do r g a n i z a t i o n u n f o r t u n a t e l y , i t s e x e c u t i n gp e r i o d s ，a c c o r d i n g t or e c e n tr e s e a r c h e s ，i st o ol o n gt of i ts o m et i m e r e s t r i c ts y s t e m s t h e s em e a s u r e sa r es t i l li nr e s e a r c h i n gs t a g e ，a n dl a r g e l yb a s e do nn e o c l a s s i ce c o n o m i c s t h i st h e s i s ，w i t hs u p p o r t i n go ft h e o r ya b o u tn e wc l a s s i c a le c o n o m i c s ，i sm a i n l ya r g u i n g t h ep r o b l e mo fr e s o u r c ea l l o c a t i o nu n d e rt h ee n v i r o n m e n to fd i s t r i b u t e ds y s t e m s t h i sm e t h o d i s l a r g e l yc o n c e r n i n g a b o u th o wt oi m p r o v et h ep e r f o r m a n c eo ft h ew h o l es y s t e m ， s i m u l t a n e o u s l ym a x i m i z i n gt h eu t i l i t yo fe a c hc l i e n t i nt h e s ep r o c e s s e s ，e f f e c t i v ep o l i c i e so f r e s o u r c ea l l o c a t i o na r ea b s o l u t e l yi m p o r t a n tt oa c h i e v et h i sg o a l t h es t e p sa r e ： ( 1 ) t h ec o m b i n a t i o no ft o p o l o g i c a ls t r u c t u r ea b o u tt h ed i s t r i b u t e ds y s t e ma n da b i l i t i e so f n o d e sh a n d l i n gr e q u e s t s ，a s s o c i a t i n gw i t hs o m ea d d i t i o n a lc o m p u t i n g ，d e t e r m i n ew h i c h a l l o c a t i n gs t r u c t u r ei ti sl a y i n go n t h ed i f f e r e n c e so f n e tb a n d w i d t hb e t w e e nn o d e si m p l yt h a t t h e r ea r e d i f f e r e n tt r a n s a c t i o ne f f i c i e n c i e sa m o n gt h o s en o d e s ，w h i c hm e a n sv a r i e t a l s v 夕p 卜j ，厂 东北大学硕士学位论文 a b s t r a c t t r a n s a c t i o nc o e f f i c i e n t se x i s t e d e a c ho f n o d e sh a sd i f f e r e n tc a p a c i t i e si np r o v i d i n gs e r v i c e s f o rc l i e n t s ，w h i c hp r e s e n tc o m p a r a t i v ea d v a n t a g ei si n h e r e n tf o rs e r v i c e sb e t w e e nt w on o d e s t h e s et w oe x t e m a lf a c t o r sd e c i d et h es t r u c t u r eo fa l l o c a t i o nb e t w e e nn o d e sa b o u tt w o s e r y l c e s ( 2 ) u n d e rt h ed e f i n i t es t r u c t u r ei nt h ep r e v i o u ss t e p ，o p t i m a lp o i n t sc a nb eo b t a i n e d t h r o u g hd e r i v a t i o n ，t h u st h ea m o u n to fr e s o u r c ea l l o c a t i o nb e t w e e nt h e s et w on o d e si sa w a r e t h i ss t e pi sa c c o m p l i s h e du n d e rh e l p so f m a r g i n a la n a l y s i si nn e o c l a s s i ce c o n o m i c s ( 3 ) a l l o c a t et h er e q u e s t si n t ot h e s et w on o d e sa c c o r d i n gt ot h es e c o n ds t e p a n da 1 1 0 c a t e 。 a l lt h er e q u e s t si n t ot h e s et w on o d e ss i m i l a r l y a f t e rt h e s es t e p s ，e a c hc l a s so fr e q u e s ti sn o wa l l o c a t i n gt ot h en o d e sw h i c hh a v e c o m p a r a t i v ea d v a n t a g ei nd e a l i n gw i t hi t ，a n de a c hn o d ei sm a x i m i z i n g l yp r o v i d i n gs e r v i c e si t h a v ec o m p a r a t i v ea d v a n t a g ei nh a n d l i n g f u r t h e r m o r e ，r e q u e s t sf r o me a c hs e r v i c en e ta r e c o n t a i n e di nt h es p e c i a l i z a t i o no fw o r k t o t a l l y , t h i si d e ai st r a n s l a t i n gt h ep r o b l e m so f r e s o u r c ea l l o c a t i o ni n t oi s s u e so fs p e c i a l i z a t i o no fw o r k ，a n dt h e n a p p l i e si n f r a m a r g i n a l a n a l y s i st og e tt h eo p t i m a ls o l u t i o n s k e y w o r d s ：n e wc l a s s i c a le c o n o m i c s ；c o m p a r a t i v ea d v a n t a g e ；d i s t r i b u t e ds y s t e m e n v i r o n m e n t ；r e s o u r c ea l l o c a t i o n v i - ， 。1 东北大学硕士学位论文目录 目录 ，一独创性声明i 摘要 a b s t r a c tv t 、夕 第1 章绪论1 1 1 研究背景1 1 2 分布式系统环境下资源分配研究现状与发展2 1 2 1 分布式系统中的资源分配问题研究现状2 1 2 2 分布式系统环境下资源分配的发展趋势3 1 3 本文采用的方法和解决的问题3 1 4 本文的组织结构4 第2 章分布式环境下的资源分配问题5 2 1 分布式系统5 2 1 1 分布式系统的定义5 2 1 2 分布式系统的特点6 2 1 3 分布式系统的体系结构6 2 2 资源分配8 2 2 1 传统单系统中的资源分配8 2 2 2 分布式系统环境下的资源分配8 2 2 3 基于微观经济学的资源分配方法9 2 3 分布式系统环境下的资源分配模型存在的问题1 1 2 4 本章小结1 1 ， 第3 章经济学中资源分配的一般理论1 3 3 1 消费者选择理论1 4 3 1 1 预算约束1 4 3 1 2 偏好和无差异曲线。1 4 3 1 3 最优化选择15 3 2 比较优势15 v i i 东北大学硕士学位论文目录 3 3 基于古典经济学原理的分配理论1 6 3 4 新古典经济学中资源分配问题1 7 3 5 新兴古典经济学1 7 3 6 竞争均衡1 8 3 7 本章小结1 8 第4 章具有比较优势和交换成本的分配模型1 9 ， 4 1 模型描述1 9 4 2 定理、假设及定义2 0 。 4 3 分布式系统环境下资源分配的一般均衡模型2 3 4 3 1 服务向量2 3 4 3 2 交换向量2 3 4 3 3 总服务向量2 4 4 3 4 竞争均衡2 4 4 4 系统模型2 5 4 4 1 服务器节点f 和，的效用函数2 5 4 4 2 服务器节点f 和，的服务向量2 7 4 4 3 服务节点的交换向量2 8 4 5 多种请求在任意两个节点之间的分配2 9 4 6 多个节点之间的请求分配问题。3 0 4 7 参数收集与系统改进3 0 4 8 本章小结3 1 第5 章模型分析与算法设计3 3 5 1 服务能力口和交换系数后的确定3 3 5 1 1 服务能力的确定3 3 5 1 2 交换系数的描述和计算3 3 1 5 1 3 构造每个节点的交换系数向量3 4 5 2 任意两节点之间的角点均衡分析3 5 5 2 1 自给自足结构3 6 5 2 2 执行具有比较优势的服务的半专业化结构。3 7 5 2 3 执行具有比较优势服务的专业化结构4 3 一v i i i h f _ ， 东北大学硕士学位论文 目录 5 2 4 命题证明一4 4 5 3 节点的决策分析4 5 5 3 1 自给自足结构的条件4 5 5 3 2 半专业化结构的条件一4 5 5 3 3 专业化结构的条件一4 6 5 3 4 计算分配结构的算法4 7 5 4 多种请求在任意两个节点之间的分配4 8 5 4 1 分配方法描述一4 8 5 4 2 分配算法4 9 5 5 多种服务在多节点之间的分配5 0 5 6 系统性能改善的方法5 0 5 7 本章小结一5 0 第6 章实例分析51 6 1 第一组节点的分配实例51 6 1 1 第1 组效用函数系数分配方案5 2 6 1 2 第2 组效用函数系数分配方案5 5 6 2 第二组节点的实例分析5 9 6 2 1 第1 组效用函数系数分配方案一5 9 6 2 2 第2 组效用函数系数分配方案6 2 6 3 结果分析6 3 6 4 本章小结6 4 第7 章结论6 5 7 1 结论6 5 7 2 特点6 5 7 3 存在的问题6 6 7 4 展望6 6 参考文献6 7 致谢7 3 ， 1 1 东北大学硕士学位论文 第1 章绪论 1 1 研究背景 第1 章绪论 本文以新兴古典经济学理论为依据，分析在分布式系统环境下资源最优化分配和组 合的可能性，其目的在于指导分布式系统中各个服务节点做尝试性试验，最终达到整个 系统资源的分配与组合最优化。 自第一台通用电子计算机诞生以来，计算机技术在6 0 多年的时间里有着飞速的发 展，其计算性能更是日新月异。然而，一个我们不得不接受的事实是，它的发展速度永 远跟不上人的期望。我们每天都在祈祷着计算机能够发扬奥林匹克中“更高“更快 “更强的精神，幻想着能把一切的烦恼都抛给它，然后等待着完美的结果。这是不可 能实现的，一个很重要的原因在于，计算机可操纵的资源与我们的要求相比永远是稀缺 的。自然，摆在计算机专家们面前一个很现实的问题就是，怎么能够利用这有限的资源 更好地为人类服务。 这个难题困扰着一代又一代的计算机专家们。虽然也产生了许许多多有效的解决方 法，这些方法在单独的处理器上都能够高效地运行，也取得了卓有成效的结果，如第一 个u n i x 系统所用的分时服用调度算法【l 】，以及其衍生出来的一系列系统，如4 2 b s d 、 4 3 b s d 、4 4 b s d ，虽然加入了应用于各种环境下的优化算法，如基于优先级的调度算 法【2 1 ，还有s o l a r i s1 0 使用的用于各种不同情况下的调度算法，包括实时算法【3 1 。然而当 把它放到分布式系统环境中时，又凸显不足。因为资源分配问题在计算机中称为n p 问 题，存在许多难点1 4 ，即很难以一种有效的分配算法，使整体效果达到最优。尽管如此， 依然有不少的计算机算法工作者在寻找一些启发式的算法【5 】【6 】【7 】【8 】，这些算法大多比较理 想化，省略了许多细节而很难应用于现实的系统，而且较为复杂。在处理一些预定义的 任务时，有许多基于有向无环图( d a g ) 的静态调度算法1 9 ，这又可以分为 u n c ( u n b o u n d e dn u m b e ro fc l u s t e r s ) 、b n p ( b o u n d e dn u m b e ro fp r o c e s s o r s ) 、a p n ( a r b i t r a r y p r o c e s s o rn e t w o r k ) 和t d b ( t a s k - d u p l i c a t i o nb a s e d ) 。 正因为这些算法在实现过程中过于复杂与低效，对于网络环境下的分布式系统，不 存在统一的管理策略。这种系统是动态存在的，即资源动态加入和退出，而且随着网络 规模的扩大，这种全局管理策略所需要掌握的信息相当大，以至于超出了计算机的计算 东北大学硕士学位论文第1 章绪论 能力。所以越来越多的计算机专家们把目光转向市场，希望以市场的组织形式来解决资 源的高效分配问题。市场经济方法是资源配置的有效方法之一，是解决多个自利个体间 资源调度问题的简单有效机制，并且得到该问题的最优解或近似最优解。目前使用经济 学原理解决资源分配问题还处于研究阶段，大多数基于市场定价和市场拍卖来分配资源 1 0 1 1 1 j 【12 1 。 1 2 分布式系统环境下资源分配研究现状与发展 1 2 - 1 分布式系统中的资源分配问题研究现状 分布式系统是一个硬件或软件组件分布在网络计算机上，仅仅通过消息传递进行通 信和动作协调的系统【1 3 】。 根据定义可知，一个分布式系统有许多重要的特点，包括并发性，缺乏全局时钟， 以及故障独立性等。正由于这些客观的特点，决定了分布式系统在许多特性上区别于传 统系统。 目前分布式系统环境下资源分配分两种情况：( 1 ) 通过工程控制的方法主动分配系 统资源；( 2 ) 通过竞争市场的方式使其中的资源利用最大化，从而实现资源的有效分配。 1 2 1 1 传统工程控制分配方法 传统的工程控制方法分配系统的资源，从本质上来说是传统的单系统资源分配的一 种演化，其核心就在于人为地将资源进行等级划分，然后通过某种分配算法将划分好的 资源分配到各个使用资源的任务上去。这种资源分配方法都是从资源提供方的角度，使 用优化理论集中地求解资源调度问题，决定各个资源使用者所能获得的资源数量。这种 方式往往是静态的，即资源的数量不发生改变，而且运算集中，不适应现代计算机的负 载均衡，高容错性等要求。 1 2 1 2 市场竞争分配方法 通过市场竞争进行资源分配，是近年来研究比较热的资源分配方法，其核心是在分 布式系统环境中引入市场的概念，通过市场竞争，将资源分配给对其评价最高的任务， 从而达到整个系统的效益最大化，实现资源的最优分配。这是分布式系统中资源分配的 一种新的思维方式。基于市场经济学理论的资源调度方法非常适合解决分布式资源管理 问题【1 4 1 。也可实现诸如基于q o s 、p a r e t o 最优、公平性等优化目标【1 5 】。 2 东北大学硕士学位论文第1 章绪论 1 2 - 2 分布式系统环境下资源分配的发展趋势 由于分布式系统环境下资源分配问题是n p 完全问题，传统的工程控制方法很难取 得突破。大家都把重心集中到一些较为先进的分配方法上，如智能优化方法及基于市场 经济的分配方法。 h智能优化方法如遗传算法、蚁群优化等，已经比较成熟，也日渐应用于现实系统中。 基于市场经济的分配方法则更多仍处于学术研究之中，这源于其竞争的复杂性，以及分 ， 配周期较长。然而，这些方法依旧会是各种研究机构的研究热点，因为未来的世界对分 布式系统的需求有增无减，而传统的分配方案已经成为研究瓶颈，很难取得重大突破， 这就决定了在分布式系统环境下其它的分配方法会取代传统的分配方法而成为主流。 1 3 本文采用的方法和解决的问题 由于分布式系统环境下资源分配固有的复杂性，目前的分析和实现方法都难以令人 满意。为了从源头上避免这种分析的复杂性，本文放弃了传统的分析框架，即使用新兴 古典经济模型来描述分布式系统环境下的资源分配问题。这种模型思想是根据不同的节 点在处理不同的请求时具有比较优势这一原理，将这些请求分配到最具有比较优势的节 点上执行。然而，由于网络传输的代价存在，节点必须在这种代价和比较优势的好处上 得到平衡，使节点总效用最大化。这种模型既使用了古典经济学中的分工和专业化理论， 也将新古典经济学的边际分析纳入其中，形成了新兴古典经济学中的超边际分析。 这种方法提供了一种以增加系统性能为目标的分析框架，将宏观经济学微观经济学 纳入到同一种分析体系中，解决了不同经济问题不同分析理论的复杂性。这种方法既不 同于目前广泛研究的瓦尔拉斯均衡的资源定价模型，也不同于基于纳什均衡的拍卖模 。 型。这两种广泛研究的模型，其重点和研究核心都在于资源分配问题的本身，而非提高 系统的性能。 ，本文所基于的经济理论来源于新兴古典经济学派，其研究核心放弃了分析如何分配 资源以达到资源的有效使用，而转而研究如何增长国民财富这个问题本身。因此本文所 研究的资源分配问题可称之为以提高系统性能为目标，以合理有效分配资源为重要手段 的资源分配方法。这种方法是一种高度自治的分配方法。每个节点根据本地信息做出分 配策略，而不涉及全局信息，因此避免了传统分配方法中信息膨胀的问题。这种方法根 据计算得出的分配策略，这与智能优化方法不同，它具有很强的可预测性。 一3 一 东北大学硕士学位论文第1 章绪论 1 4 本文的组织结构 本文分七章介绍基于新兴古典经济学原理，以市场为组织形式，以分布式系统为平 台的新型资源分配方法。 第一章绪论部分，介绍分布式系统及资源分配的一些背景，以及研究现状。 第二章介绍了分布式系统环境，以及目前在这种环境下的一些分配方法，重点介绍 了基于现代经济理论的分配方法。之后综合阐述了这些分配方法的优缺点。 第三章介绍了本文所基于的经济学原理，重点是新兴古典经济学原理，以及如何使 用超边际分析来对客户所发出的请求进行分配。 第四章具体描述了这种分配模型。 第五章重点解决这种分配模型的几个关键技术，如服务能力、交换系数、三种分配 结构等，以及多节点多服务的分配问题。 第六章是实例分析，将前面的分配模型实例化。 第七章对全文作了总结。 4 东北大学硕士学位论文第2 章分布式环境下资源分配问题 第2 章分布式环境下的资源分配问题 随着低成本计算机的出现，以及互联网的大规模普及，许多机构面临着管理大量的 分布式资源。这些资源可以分布在同一个局域网中，同一个城市中，也可能分布在世界 的任何一个角落。正因为其分布的广泛性，结构的多样性，以及开放性，使得管理和分 配这些资源给我们带来了很大的挑战，这种计算远远超出了目前计算机的计算能力。况 且，网络的状态随时发生变化，随时有服务节点加入或退出系统，这就加剧了分配的不 可预测性。因此资源分配的决策只能由单独的节点根据自己掌握的资源和网络信息进行 局部优化分配。 2 1 分布式系统 2 1 1 分布式系统的定义 分布式系统是由两台或两台以上的计算机组成的系统。根据e c k h o u s e 和e n s l o w 的 定义，分布式系统是满足以下四个条件的多计算机系统【1 6 1 ： ( 1 ) 系统由多台计算机组成。组成系统的各台计算机可以说大型、中型、小型或 微型，有各种不同的体系结构。而系统中每台计算机又可以是单处理系统，多处理系统， 或者是多计算机系统。 ( 2 ) 系统中的各台计算机通过某种网络互相连接的。从物理上看，这些计算机是 直接或间接相连的，且物理位置可远可近，网络拓扑结构可以多样。从逻辑上看，这些 计算机系统之间可以通过通信进行数据交换。 ( 3 ) 各台计算机是自治的、平等的，而且缺乏全局的系统信息。它们各自根据自 己所获得的信息进行工作。系统中没有中央控制系统之类的特殊机器。当各计算机之间 发生冲突时，通过协商解决。 ( 4 ) 系统在逻辑上是一个完整的整体。分布式系统的应用程序可以分解成几个独 立的部分，且分别运行于不同的计算机系统上，并通过通信互相协作。这些过程在系统 内部隐式执行，对用户透明。应用程序的用户感到系统是一个整体，好像工作在一台计 算机上。这个特点也是分布式系统与一般网络的最大区别。 5 - 东北大学硕士学位论文第2 章分布式环境下资源分配问题 2 1 2 分布式系统的特点 分布式系统是基于网络环境的一种系统，是在计算机网络发展到一定阶段的产物， 与传统的单系统或者对称多处理系统相比，有其鲜明的特点【”】： ( 1 ) 硬件本身相对独立。一个分布式系统由若干个通过某种网络互联的计算机组 成，这些计算机从硬件设备上可能干差万别，且地理位置分布没有约束。连接这些计算 机的网络也各不相同，从相差数千公里的广域网到只有几米之遥的局域网，都有可能存 在于同一个分布式系统中。 ( 2 ) 软件系统也各不相同。分布式系统的底层可能由许多种异构的操作系统控制 和调度本地资源，这些系统对资源的描述、表达、执行方式等，都不可兼容。这种现状 直接导致了整个系统管理上变得尤为复杂。由于各种网络使用的网络协议差异万千，使 得整个分布式系统在数据传输方面需要考虑的问题急剧膨胀，这种增长速度随着整个系 统的扩张而变得难以控制。因此，分布式系统在维持资源的一致性，在资源分配的合理 性方面，都显得不堪重负。再者，分布式系统满足的其它要求也在一定程度上制约着整 个系统高效地分配各种资源，如访问透明性、位置透明性、迁移透明性、重定位透明性 等。 2 1 3 分布式系统的体系结构 由于硬件结构的千差万别，现实世界中的分布式系统也多种多样。从网络拓扑结构 来说，大致可以分为四种【1 7 】：基于总线的共享存储器系统、基于总线的专用存储器系统、 基于交换的共享存储器系统和基于交换的专用存储器系统，如图2 1 所示。 2 1 3 1 多处理器系统 多处理器系统有一个共同的关键属性：系统中的所有c p u 都能直接访问共享存储 器。如图2 1 左边的两种。 对于基于总线的共享内存多处理器系统来说，任意时刻只能有一个处理器对存储器 进行访问。这种限制就决定了一个总线上的处理器数目不能太多，否则系统性能会因对 总线的争用而急剧下降。一种现实中使用的解决方案是在处理器和总线之间加装高速缓 存，以缓解总线的压力。而这又带来了新的问题，就是关于缓存一致性的问题。关于基 于总线的共享存储器的多处理器系统参考文献i l8 1 。 一6 t t 皇- ， 东北大学硕士学位论 基于总线的共享存储器系统基于总线的专用存储器系统 基于交换的共享存储器系统 基于交换的专用存储器系统 图2 1 分布式系统中处理器和存储器的不同组织形式 f i g2 1v a r i o u so r g a n i z a t i o n so fp r o c e s s o r sa n dm e m o r i e si nd i s t r i b u t e ds y s t e m 由于基于总线的共享存储多处理器系统存在固有的缺陷，其扩展性就受到了限制。 一种另外的技术是通过快速交换机把处理器和存储器连接起来。这种技术增强了系统的 可扩展性，而且使得多个处理器可以同时访问多个内存，只需要开启和关闭相应的交换 开关。对于不同的系统，其交换机组织结构各不相同。最常见的是通过纵横式交换机连 接和o m e g a 交换网络。 2 1 3 2 同构式多计算机系统 这种系统由许多结构相同的计算机通过单一的互联网络连接起来，通常也可以分为 基于总线的系统和基于交换的系统。 基于总线的同构式多计算机系统结构比较简单，只需将计算机和一条高速总线相 连。和基于总线的多处理器系统一样，这种系统的可扩展性也是有限的。 基于交换的多计算机系统，计算机之间通过消息进行信息交换。这种系统有多种形 式的网络拓扑结构。较为常用的有网状拓扑( m e s h ) 和超立方体拓扑( h y p e r c u b e ) 。 基于交换的多计算机系统应用较为广泛，且多种多样。规模最大的是大规模并行处 - 7 一 东北大学硕士学位论文第2 章分布式环境下资源分配问题 理器( m a s s i v e l yp a r a l l e lp r o c e s s o r s ，m p p ) 系统。规模较小的有一种较为流行的系统，成 为工作站集群( c l u s t e r so f w o r k s t a t i o n s c o w ) 。 2 1 3 3 异构式多计算机系统 这种系统是目前广泛使用的系统，多数分布式系统都建立在这一基础之上。在这种 系统中，各个计算机存在着较大的差异，连接这些计算机的网络也千差万别。但这种系 统是最容易扩展的，也是自适性最强的一种系统。 2 - 2 资源分配 2 2 1 传统单系统中的资源分配 这种系统中的资源分配问题较为简单，对这类问题的研究也较为成熟，其核心问题 是用某种方法人为地把资源分配到系统中，使得各种资源能得到最有效的利用。由于系 统掌握着整个系统的资源，对其有一个全局且确定的认识，因此，实施方法也较为简单。 日常使用的微型计算机系统就属于这种情况。操作系统掌握着全部的资源，且根据需要 对其资源进行分配。关于这种资源分配问题可参考早期的文献【1 9 1 2 0 1 。 2 2 2 分布式系统环境下的资源分配 2 2 2 _ 1 基于传统单系统的资源分配方法 这种资源分配算法大多数是一种知识确定型算法【2 1 1 。这种分配方法的共同特点是： 对系统的资源和结构有一个全局的确定的知识，