（测试计量技术及仪器专业论文）分布式计算机系统动态负载平衡的研究.pdf

摘要恸态负载平衡是分布式系统中的个研究热点寸雄文利用在线跟踪技术，获得作业的行为特征( 资源需求和执行时间等) ，从而筛选出那些不值得转移的短作业；并且根据作业对各种资源的需求情况，为作业寻找一个更能满足其资源需求的执行节点；同时根据作业的不同行为特征，指出仅用c p u 队列长度作为负载指标的缺陷，验证了使用资源利用率为主要负载指标，资源队列长度为次要负载指标的合理性。另外，本文还讨论了不同的负载环境对于不同类型作业响应时间的影响，并以此为依据来估计作业转移的收益与开销，将一个基于收益与开销的新的选择策略应用到负载平衡算法中。此外，本文以执行时间最短为评价标准，为将要转移的作业寻找最佳执行主机。( 性能测试的结果表明，本文所提出的方法能够较好地缩短作业的平均响应时间和提高系统的资源利用率，实现了动态负载平衡的目的。上关键词：分布式系统i 动态负载平衡i 在线跟踪，一负载指标i 负载平衡算法a b s t r a c td y n a m i cl o a db a l a n c i n gi sah o tr e a e a r c hp o i n ti nd i s t r i b u t e ds y s t e m s b yu s i n go n - l i n et r a c i n gt e c h n i q u e ，t h i sp a p e rc a np r e d i c a t et h eb e h a v i o ro faj o b 。s u c ha si t sr e s o u r c er e q u i r e m e n t sa n di t sa p p r o x i m a t ee x e c u t i o nt i m e t h e r e f o r e w ec a nr e c o g n i z et h o s es h o r t - l i v e dj o b sw h i c ha r en o tw o r t ht r a n s f e r r i n g a n da c c o r d i n gaj o b sr e s o u r c er e q u i r e m e n t s w ec a na l s of i n dan o d et oe x e c u t ei tw h i c hs a t i s f i e si t sn e e db e s t i na d d i t i o n a l w ep o i n to u tt h a ti nd y n a m i ci o a db a l a n c i n gs y s t e m s u s i n gr e s o u r c eu t i l i z a t i o n sa sl o a di n d e xi sb e t t e rt h a nu s i n gc p uq u e u el e n g t h s i nt h i sp a p er lw eg i v ea na l g o r i t h mf o rp r e d i c a t i n gt h ee x e c u t i o nt i m eo fv a r i o u sj o b su n d e rv a r i o u sl o a de n v i r o n m e n t s b a s e do nt h i sp r e d i c a t i o n ，t h eo v e r h e a da n db e n e 讯o ft r a n s f e r r i n gaj o bc a nb ec a l c u l a t e d an e ws e l e c t i o np o l l c yb a s e do nt h eo v e r h e a da n db e n e f no ft r a n s f e r r i n gaj o bi sd e s i g n e da n di m p l e m e n t e d w ec o n s i d e rt h a tt h eb e s tn o d ef o raj o bi st h eo n eo nw h i c ht h ej o bw i l lr u nt h es h o r t e s tt i m e e x p e r i m e n tm e a s u r e m e n tr e s u l t ss h o wt h a ti ti sa b l et or e d u c em e a nr e s p o n s et i m ea n di m p r o v er e s o u r c eu t i l i z a t i o no fs y s t e m s k e yw o r d s ：d i s t r i b u t e ds y s t e m s ，d y n a m i cl o a db a l a n c i n g ，o n - l i n et r a c i n g ，l o a di n d e x ，l o a db a l a n c i n ga l g o r i t h m南京航空航天大学硕士学位论文第一章绪论由于传统的v o nn e u m a n n 体系结构日趋到达其处理能力的物理极限，计算机系统趋势朝向多机系统和松耦合的分布式系统方向发展。特别是由于高性能工作站和网络的价格越来越低，由网络连接几十甚至几百台工作站已越来越普遍。分布式系统中由于任务到达的随机性和各主机处理能力的差异，经常是某些主机上的负载很重，有若干任务等待服务，而某些主机上的负载很轻，几乎处于空闲状态。负载平衡就是要将重负载主机上的作业转移到轻负载主机上执行，使得整个计算机系统中所有主机的负载趋向平衡，目的是要缩短作业的平均响应时间和提高系统资源的利用率n “”。1 1引言2 0 世纪9 0 年代，计算机系统的发展表现为由单机向并行多处理机，由集中式向分布式，由单一信息媒体向多媒体方向发展的趋势。具体表现在如下两个方面：硬件由集中趋向物理上的分布，软件由分散趋向逻辑上的集中”“1 。( 1 ) 硬件方面：7 0 年代，人们通过运行分时系统来共享一台主机或小型机，人机比率较高，通常达到2 0 - - 1 0 0 人共享使用一台机器。8 0 年代，v l s i ( 超大规模集成电路) 技术和计算机技术相结合的产物微处理器迅速发展，高档3 2 位微处理器( i n t e l8 0 3 8 6 ，m o t o r o l a6 8 0 2 0 ) 相继出现，其硬件价格急剧下降，而性能已接近中小型计算机的水平。伴随着微型机的发展，局域网络也得到了广泛的应用，美国的以太网( e t h e r n e t ) 和欧洲的剑桥环网( c a m b r i d g er i n g ) 已成功地用于工厂、学校和政府机关。在许多大学和公司中，都通过网络技术进行单机互连，实现共享系统资源和相互通信，整个计算机系统是以通信网络为中心的。9 0 年代，硬件价格继续下跌，微型机、工作站数量增加，大量的微型机、工作站分布在中等大小地域内。为了充分利用这些资源，人们希望在利用网络环境来充分利用资源和通信的同时，又能像以往单机用户那样简单方便地操作，而不需要知道网上用户和当前网上资源等网络层次的实现细节。针对这一要求，以微型机、小型机为主，通过局域网络互联的分布式计算机系统就应运而生了。总之，多处理机系统和分布式计算机系统是计算机应用发展的必然趋势，微型机特别是高档的3 2 位微处理器为开发分布式计算机系统提供了物质基础，局域网技术为互连主机提供了物理环境和做好了技术准备，使计算机系统由集中式走向分布式。( 2 ) 软件方面：分布式操作系统中的每台机器都是高度自治的，每台工作站上都安装有网络软件，工作站之间由局域网互连在一起。用户所有的命令和程序均在本分布式计算机系统动态负载平衡的研究地工作站或远程登陆到其它工作站上运行。文件服务器为所有工作站提供可访闯的全面共享文件系统，而操作系统必须保证工作站和文件服务器之间的通信。分布式操作系统将多台计算机构成一个完整的系统，使其行为类似一个单机系统，即登陆到系统的用户不必了解系统有多少台机器，它们都位于哪里，它们的功能是什麽，文件在哪里，作业运行在哪台机器上等任何有关硬件物理分布的细节。从上面的叙述可以看到，分布式计算机系统( 或简称分布式系统) 就是由多台计算机组成的系统，更确切地说，它是满足以下条件的多计算机系统”“”：( 1 ) 系统中的计算机之间可以通过通信来交换信息。因此，运行于系统中的计算机上的程序之间可以使用系统提供的通信手段来交换数据。( 2 ) 系统中的各台计算机没有主次之分，既没有控制整个系统的主机，也没有受控于它机的从机。因此，主从控制计算机系统或分机控制计算机系统都不是分布式系统。( 3 ) 系统的资源为所有用户所共享。在某台计算机终端上的用户不仅可以使用位于该机上的资源，还可以使用位于它机上的资源。而且分布式系统提供的资源共享功能，可以使用户只需要考虑系统是否具有自己所需要的资源，而无需考虑资源在哪台些计算机上。( 4 ) 系统中的若干台计算机可以互相协作来完成一个共同的任务，或者说，一1 婆序或佳叁旦坠坌查王些鱼盐笺垫圭羞盆地重堑：二墼笪盐差盟塑竺垄至壁塑星整个条件的，所以分布式系统是一种特殊的计算机网络系统。近十几年来，各国已经展开了分布式计算机系统的研究工作。例如，1 9 7 6 年美国c a r n e g i e m e l l o n 大学用5 0 台l s l l l 型微型计算机组成了一个分布式系统。此后，加州大学b e r k e l e y 分校研制了x 树系统，w i s c o n s i n m a d i s o n 分校研制了a r a c h n e系统，纽约州立大学b u f f a l o 分校研制了m i c r o n e t 系统，加州大学l o sa n g e l e s 分校研制了l o c u s 系统等等。在英国，剑桥大学研制了c m d s 系统，国家物理实验室研制了d e m o s 系统；在日本，东芝公司研制了e p o s 系统；我国也正在进行这方面的积极探索。人们研究分布式系统是为了开辟一条发展计算机的新途径，经过几十年的研究实践，分布式系统在办公自动化、自动控制、企业管理、计算机教学系统和计算机辅助测试等方面已经有了越来越广泛和深入的应用，人们也已经看到，由若干台计算机所组成的分布式系统在许多方面都比单计算机的集中式系统优越，l l ：! m ，运行坚定，维护方便，扩充容易，真正地并行工作，效率较高等等。我们都知道，单计算机所组成的分时系统在用户用机频繁的“高峰”时间，往往不能及时处理所有用户的要求。而分布式系统可以并行地处理用户的各种要求，使得这些要求在用户满意的时间内处理完毕。但即使是在分布式计算机系统中，由于任务到达的随机性，以及各台工作站处理能力的差异，负载不平衡的现象会经常遇到。即当一些工作站处于重载时，而另一些工作站却处于轻载或空闲状态。这种负载的不平衡，显然造成了系统资源的浪费，2南京航空航天大学硕士学位论文将直接影响到分布式计算机系统的整体性能，包括系统的资源利用率、吞吐量、响应时间等。解决这个问题的办法就是对分布式系统进行负载平衡。前面李念强博士等人对分布式系统集成所需要的相关技术进行了研究，提出了分布式系统集成的通用框架，简单地组建了一个分布式系统的测试平台。但分布式系统是一个非常复杂的系统，它的设计和实现涉及到一系列的关键技术，并且，对于分布式系统而言，最大的问题不在功能方面，而是在性能方面。1 。分布式系统确实能够提供巨大的处理能力，但要实现和充分利用这一能力，需要优良的资源分配方案，对系统进行进一步的优化。负载分配是分布式系统的资源管理模块，它主要是合理透明地在处理器之间重新分配系统负载，以达到系统的综合性能最优。1 2负载平衡研究的意义现代分布式系统一般包含多台工作站，这些工作站的功能很强，例如s u n 4 工作站的处理能力一般为十几到几十个m i p s 。一个连接l o 台s u n 4 工作站的网络，其性能潜力可达几亿至几十亿次秒。很多调查研究表明，至少有i 3 到2 3 的时间是空闲的，而随着工作站处理能力的提高，空闲时间会不断增加，最近的统计资料表明，c p u 的平均利用率仅达9 。1 。利用这些空闲的处理能力并行求解大的计算问遂或并行执行多个作业，这不仅可以大大缩短问题的求解时间还可以节省大量的开销。同样的，某些作业由于资源的限制而在单机上不能执行，利用网络中的空闲资源可联合求解单机上不能解决的问题。某些用户需要运行大作业或同时执行多个作业，客观上需要多个工作站。以上几个方面都涉及到利用网络中的多个工作站进行作业内部或作业级的并行执行的问题，各工作站的负载是否平衡是关系到并行效果的一个极为关键的因素，所以探索负载平衡问题具有重大的现实意义。1 3负载平衡的分类一般来说，负载平衡方法可做如下分类“：静态负载平衡：静态负载平衡是根据系统的先验知识做出决策，而忽略系统当前的负载状况，经常用于任务比较确定的情况下。它的算法的目标是调度一个任务集合，使它们在各个目标处理机上有最小的执行时间，过程中要考虑计算开销与通信开销，在综合各种因素的基础上，进行合理的任务划分( 粒度决策) 和任务分配。动态负载平衡：动态负载平衡是根据系统当前的负载状态进行负载分配决策，主要用于任务不确定的情况。相对于静态负载平衡，它具有更大的灵活性和针对性，可根据当前的负载状态有目的地进行负载平衡，临时决定每个任务的执行过程，但收集、存储和分析系统的状态信息不可避免地会带来额外的开销( 开销的情况将会在后文描述) 。不过以往的研究表明，动态策略比静态策略更能改进系统的性能。因此本3分布式计算机系统动态负载平衡的研究文重点研究动态负载平衡，下文中出现的负载平衡指的都是动态负载平衡。混合负载平衡：混合负载平衡是介于静态负载平衡和动态负载平衡之间的一种平衡策略。对于已确定的任务采用静态策略，对于随机的、不可预见的任务采用动态策略。1 4动态负载平衡动态负载平衡算法必须是普适的、适应性的、稳定的、可扩展的、容错的和对应用程序是透明的。对它有如下分类“1 ：1 ) 全局的和局部的。局部负载平衡算法是在邻接的节点之间转移工作负载：全局负载平衡算法不仅在邻接的节点之间交换负载，还在全系统问计算负载，根据全局情况调整处理机的负载。2 ) 集中控制的和分散控制的。在集中控制算法中，中心控制器收集状态信息，作出负载平衡的决策；分散控制算法是把控制机制分散到全系统的各个节点。3 ) 不协作的和协作的。在不协作方法中，各个节点不知道系统中其它节点的状态，独立决定自己的位置和转移规则；协作算法中，各节点相互配合来决定负载平衡的决策。4 ) 适应性的和非适应性的。在适应性算法中，负载平衡策略是根据系统状态的变化而变化：在非适应性算法中，这些策略是不变的。本文所研究的负载平衡算法是全局的、分散控制的、协作的和适应性的。动态负载平衡的组成：转移策略，选择策略，定位策略，信息策略。每种策略都可以通过一定的方法实现。影响动态负载平衡性能的三个主要因素：远程执行时的文件访问效率，负载指标的选择，选择策略的有效性。动态负载平衡的目标：提供最短的作业平均响应时间，提高系统的资源利用率，系统中每台处理机的负载量与它的处理能力相当，避免各处理器花费它们所有的时间来传送任务。1 5本文的研究内容本文针对负载平衡各组成部分的实现机制，针对影响负载平衡性能的三个主要因素，提出了一种在线跟踪技术，应用此技术来获得作业的行为特征，设计并实现了一个基于在线跟踪的负载平衡系统。本文的主要内容有：1 利用s u n o s 的进程跟踪设备，提出使用在线跟踪技术，通过对作业的在线跟踪获得作业的行为特征( 包括作业的资源占用情况和作业执行时间的估计) 。2 根据作业的不同行为特征，指出仅用c p u 队列长度作为负载指标的缺陷，提4南京航空航天大学硕士学位论文出了使用资源利用率为主要负载指标，以资源队列长度为次要负载指标。3 讨论了不同的负载环境对不同类型作业响应时间的影响，并以此为依据来估计作业转移的收益与开销，将一个基于收益与开销的新的选择策略用在平衡算法中。4 系统负载状态的检测及根据某作业的行为特征为其寻找一个最合适的执行节点，在负载平衡算法的信息交换与定位策略中以最短执行时间作为最佳机的选择标准。5 负载平衡系统的性能测试。本课题在研究过程中得到了江苏省产学研联合开发项目的资助j 项目名称为现代测控系统集成技术及其应用研究，项目号：2 0 0 1 0 3 3 0 0 4 。分布式计算机系统动态负载平衡的研究第二章动态负载平衡2 1负载平衡的研究内容及研究方法一个负载平衡系统由两部分组成，即负载平衡的远程执行设备和负载平衡算法。负载平衡依赖于远程执行，即将本地上的作业迁移到远程轻负载的主机上执行，这依赖于远程执行设备的支持1 。负载平衡算法使用系统状态信息( 各节点上的负载) 进行负载分配决策，其组成包括以下四个部分：( 1 ) 转移策略：决定节点是否处于适合参加任务转移的合适状态。即决定某节点是个任务发送者还是远程任务的接收者。( 2 ) 选择策略：决定哪一个任务应该转移。选择一个任务进行转移的基本判据是转移此任务的开销比起它响应时间的减少( 收益) 是合算的( 3 ) 定位策略：决定把所选择的作业转移到哪个节点上去执行。( 4 ) 信息策略：负责收集系统的状态信息。2 1 1负载平衡的支持设备“”远程执行设备分为两类，一类是抢先的( p r e e m t i v e ) 远程执行设备，一类是非抢先的( n o n p r e e m t i v e ) 远程执行设备。抢先的远程执行设备支持作业的抢先转移，抢先式转移是进程迁移，即转移的进程已执行了一段时间，转移到新节点后继续执行，这种方法的开销很大，实现起来很困难。因为所涉及到的进程的状态很多并且很复杂，典型的情况包括虚存映象、进程控制块、未读的i o 缓存器和报文、文件指针、已设定的定时器等。目前国际上最流行的实现方法是使用c h e c k p o i n t i n g 设备支持进程迁移。其主要思想是当进程需要迁移时就生成一个关于该进程的c h e c kp o i n ti n g 文件，然后在其他空闲机上启动该c h e c k p o i n t i n g 文件继续执行。但由于种种原因，进程迁移的使用范围受到很大的限制。非抢先的远程执行设备支持作业的非抢先转移，它对尚未执行的作业进行转移，因而不需要转移此作业的状态，又叫作业放置。p h i l l i pk u e g e r 和m i r o nl i v n y 对两种远程执行设备做了比较，他们指出，只有在整个系统的负载较重并且作业的运行时间足够长的情况下，进程迁移才能获得比作业放置更好的效果。支持抢先的远程执行设备有美国加州大学伯克莱分校研制的s p r i t e 系统的远程执行设备，s t a n f o r d 大学研制的v 系统，贝尔实验室研制的n e s t 系统和w i s c o n s i n大学研制的c o n d o r 调度系统。支持非抢先的远程执行设备有c a r n e g i e m e l i o n 大学的a n d r e w 分布式系统中的b u t l e r 系统，x e r o xp a r c 研制的c e d a r 系统的进程服务6南京航空航天大学硕士学位论文员，加拿大v i c t o r i a 大学研制的r e m 远程执行系统和o h i o 州立大学研制的s t e a l t h分布调度程序。对远程执行设备最基本的要求是远程执行的透明性，进程运行的结果与该进程在网络中什麽地方执行无关，为了迁移此进程也不必用特定方式重新编写程序，也就是说，这些进程迁移后必须仍能像在原地那样访问文件和设备。2 i 2主机状态检测和信息交换策略n m m1 主机状态检测在网络环境中，各主机各自独立地计算自己的当前负载，整个系统为了获得各主机的负载，就必须通过网络通信。s t a n k o v i c 在1 9 8 4 年就提出表示负载的参数可以有多种，如c p u 队列长度、c p u 利用率、可用内存量、估计的作业响应时间。表示负载的值必须能指示出主机能为作业提供什麽样的服务，并且这个值能反映出网络状态的快速变化，使得系统中其他节点获得的并不是过时的信息。按照这个标准，在对主机状态的检测之前，应该确定对哪些资源进行检测。目前有两种检测主机状态的方法：一种是对资源本身( 主体) 的检测，即对资源使用情况的检测：另一种是对要求资源的客体( 作业或进程) 的行为特征的检测，通过对客体行为特征的检测估计资源的使用情况。对客体的检测能近似反映主体的状态，但不能准确反映，因为客体的差异是很大的，但由于这种方法能反映出资源将来的使用情况，对避免主机状态信息的过时很有用，如 w i n 9 2 ，g o s 9 3 就是采用了这种方法。而对主体的检测是通过测量资源最近一段时间的使用情况来估计资源将来的使用情况，虽然准确但容易产生负载信息的过时。大多数系统以某段时间内的资源使用情况( 资源队列长度和c p u 利用率) 表示负载的轻重。主机的状态应包含所有资源的使用情况，但由于系统中的资源有很多种，如果包含所有资源，会使得负载平衡系统很复杂，实现起来自然很困难，但至少应包含作业经常争用的主要资源的使用情况。但绝大部分负载平衡系统或算法的主机状态仅包含c p u 的使用情况，只有很少的研究者讨论了多种资源的使用情况，这也必然导致为作业寻找执行节点时，只能满足作业对c p u 资源的需求，而不能满足作业对其他资源的需求。c p u 和i o 通道是作业经常使用的资源，主机的状态应包含这两种主要资源的使用情况。2 信息交换策略在自适应性负载平衡策略中，为了对到达某节点的请求服务的进程决定如何布局，必须有个机构在网络中传播有关处理机负载状态的信息。因为网络结构是松散耦合的，所以此信息与真实的系统状态在精确程度上有所偏离( 过时) ，但在具有足够的精度的同时必须避免不稳定性。信息策略有以下三种：按需驱动，某节点当且仅当成为发送者或接受者时，才收集其它节点的状态信7分布式计算机系统动态负载平衡的研究息，如 e g a 8 6 和 k u r 8 7 等。 e g a 8 6 的信息策略是仅当某个处理机根据本地负载状态确信超载时才请求网络中其他处理机的负载信息。周期的，各节点定期交换负载信息。这个周期值必须精确地选择，必须有足够的精度以避免不稳定性，但是频繁的负载信息交换将产生附加的开销，如 b r y8 1 ，b o n 8 8 等。 b r y 8 1 的算法是每个处理机周期地向其每个邻居节点发送负载信息。状态改变时驱动，节点当其状态改变到某种程度时发布其状态信息。它与按需驱动策略不同的是它发布本节点的状态信息，而不是收集其它节点的状态信息，如 f e r 8 8 ，s t a b 4 ，n i 8 5 ，a 1 0 8 8 等。 n i 8 5 ，a i 0 8 8 将机器状态分为轻载，中等负载，重载，只有当机器由重负载状态变成轻负载状态时才进行信息交换。2 1 3定位策略n ”n m按照作业定位的范围可分为局部定位和全局定位，局部定位是在局部范围内为作业寻找合适的执行节点，而全局定位是在全局范围内为作业寻找合适的执行节点。局部定位策略有以下两种：成对方法，每个处理机力求与负载差极大的一个邻居处理机组成队，负载的转移是在成对的处理机之间发生的，如 b r y 8 1 和 n i 8 5 的定位算法。负载向量方法，h a c 和d o h n s o n h a c 8 6 等在每个机器上维持一个负载向量，它给出最近收到的网络中有限数目的机器的负载值。负载平衡的决策是根据一个机器的负载与此机器上保持的负载向量指出的其他机器的负载相对差作出的。b a r a k 等人的 b a r 8 5 a ，b a r 8 5 b 和n i 等人的 n i 8 5 也使用这种方法，所不同的是他们以估计的作业响应时间表示负载的轻重。全局定位策略有以下两种：广播方法，m a i t r e d 系统 b e r 8 5 和l i v n y 等的 l i v 8 2 的广播算法是仅当机器成为空闲时广播一个报文，通知它要接受迁移进程。g a m m o n 需要转移作业时，就通过广播交换负载信息并寻找最佳机 b a u 8 9 ，现存的负载共享系统v s t u 8 8 ，s p r i t e d o u 9 1 ，c o n d o r l i t 8 8 ，s t e a l t h k r u 9 1 和u t o p i a z h 0 9 3 不寻找最佳机，作业转移到第一个对发出的广播做出回答的轻载机上。全局系统负载方法，k r u g e r 和f i n k e l k r u 8 4 建议，每个机器应当力求计算出全系统的负载荠相对于此调整其自身的负载而不是交换本地负载值。这个方法的特点是能检测系统是否处于全面的重负载或轻负载，当一个机器的本地负载与平均值相差很大并且找不到与其负载处于互补状态的另一个机器时，就修改它所保持的全局平均值并向所有其它机器广播这一事实。例如，如果某机器超载并且找不到一个轻载的机器时，那麽就应增加全局平均值。要适当设置允许一个进程从某机器上迁移出去时所使用的该机器负载与全局平均值之间的差额量，太小会使机器花费很多时间进行进程迁移，太大会漏掉很多应该迁移的机会。c a s a v a n t 和k u h l c a s 8 6 使用分布式决策来8南京航空航天大学硕士学位论文评价全局系统负载并作出定位决定。2 1 4转移策略自适应负载平衡算法的转移策略主要处理这样的问题：决定在什麽条件下一个进程可以从一个机器迁移到另一个机器。决定何时可以迁移进程的一个非常简单并且有效的方法是使用静态门限( t h r e sh o l d ) e a 9 8 6 ，当超过它时，说明机器的负载太重，需要向网络中的其他节点卸掉一部分工作。l i n 和k e l l e t l i n 8 7 使用两个门限将机器负载大小分成轻载，中等负载和重载，认为仅当超过重载门限时才迁移进程。上面系统使用的转移策略是超载节点触发进程迁移，但某些研究学者如n i n i 8 2n i 8 5 却持相反的看法，认为轻负载机应主动地接受其它超载节点的进程，极端的情况是仅向空闲机迁移进程。某些转移策略决定进程迁移的主要标准是使用两机负载差值。s t a n k o v i c 的系统 s t a 8 4 ，k r u e g e r 和f i n k e l k r u 8 4 的“超平均”算法使用基于负载差的转移策略，若两机的负载差值超过某值则进行转移。另一个使用负载差的方法是根据远程机负载的当前估计值决定其是否转移，周期地检查本地进程在远程其它机上可能的响应时间，若有很大的改进( 考虑了迁移开销) ，则希望此进程迁移 b a r 8 5 。尽管有上面的选择策略，但都没有给出门限和负载差值大小的选择方法，所以都采用了固定值，一旦选定就长期不变，实际上不同的作业在不同的系统状态下应动态调整。d e r i c h e d e r 8 9 虽然没有使用动态调整的门限，但指出应在今后的工作使用。2 1 5选择策略选择策略指应选择哪个( 些) 进程进行迁移。一个简单且易实现的方法是只考虑迁移新到达的进程。v 系统 s t u 8 8 和n e s t e z z 8 6 使用的选择策略是只选择新到达的作业进行迁移，不管此作业是什麽类型。这种方法是盲目的，例如短作业转移后，作业响应时间的改进抵消不了转移的开销。要对作业响应时间的改进和转移的开销进行估计，必须获得作业的性质和不同系统环境对不同作业响应时间的影响。b a r a k 、s h i l o h b a r 8 5 和k r u g e r 等人的 k r u 8 4 在选择策略中考虑了作业响应时间的改进和转移的开销，但无法定量估计，所以并未用于实际的系统中。s v e n s o n s v e 9 0 根据作业过去的执行时间进行作业选择，即对一个命令事先测量其平均执行时间，把所有测量过的作业列个表，运行此作业时先查表，若大于某个门限则在本地执行，否则转移。这个被称为智能筛选的方法只考虑了作业执行时间的因素，末考虑作业的性质。此外，未执行过的作业无法处理。k o c h 【k o c 9 4 w a n g 等的 w a n 9 3 使用人工神经网，通过学习作业过去的执行特征9分布式计算机系统动态负载平衡的研究的知识来指导下次的作业选择。这个方案的优点是，决定作业是否转移时使用了比较精确的知识，适应各类作业和系统配置的变化。其缺点是：对某个作业的转移作出正确决定之前，必须已经执行过很多此，次处愈多愈正确；每个命令带有某个参数是一类，不同参数的相同命令不属于一类，所以限制很严。这种方法不适合用于实际系统的实现。s p i t e 系统 d o u 9 1 和c o n d o r l i t 8 8 由用户选择作业进行转移，不支持自动转移。s t e a l t h k r u 9 1 和u t o p i a z h 0 9 3 用查表的方法支持作业的自动选择，表中列出以前执行过的作业名及转移建议。2 1 6负载平衡算法的实现方法有很多种负载平衡算法，可将它们分成三大类“：发送者启动，接受者启动和对称启动，这种分类抓住了解决负载平衡问题方法的最基本的差异。发送者启动的方法迄今为止，这种方法研究最多的是 e b 9 8 6 ，b r y 8 1 ，l i n 8 7 ，s t a 8 4 ，k r u 8 4 ，b a r 8 5 ，负载分配活动由超载节点( 发送者) 启动，它力图把一个作业发送给轻载节点( 接受者) 。其性能在系统处于轻载、中等负载时较优。这是因为此种情况下轻载节点比较多，易于寻找。接受者启动的方法这种方法是欠载机或空闲机向网络中比较重的机器请求获得进程。相对于发送者启动策略来讲研究得较少 n i 8 5 ，l i v 8 2 ，e a 9 8 5 。e a g e r 等人的 e a 9 8 5 指出，这种方法在整个系统负载重的情况下工作很有效。对称启动的方法j o h n s o n 和h a r g e t h a r 8 8 使用兼有接受者启动和发送者启动的方案，根据当前的负载状态可以切换。发送者启动适用于系统负载较低的情况，而接收者启动适用于系统负载较高的情况，到底使用何种策略就根据系统的平均负载值进行切换。2 2影响负载平衡性能的几个主要因素从上面的分析不难看出，无论采用什麽样的负载平衡算法，以下几个因素是影响负载平衡性能的几个主要而带有普遍性的因素“。2 2 1远程执行时的文件访问效率作业远程执行时，它进入系统的节点是其基地节点。为了维持远程执行时的透明性，一个作业远程执行时，需要访问基地节点的文件系统，对于有大量文件操作的作1 0南京航空航天大学硕士学位论文业，性能将要大大的降低。目前有以下几种方法来提高远程执行的作业访问文件系统的性能：( 1 ) e z z a t 在n e s t a g r 8 7 系统中使用置换根的方法来确定哪些文件在执行节点访问，哪些文件需要回到远程基地节点访问，这种方法是通过减少对远程基地节点的文件访问操作来改进性能。他在s u n 3 上的实验表明，在完全空闲的本地机上编译源程序文件s o r t c 需执行1 2 2 1 秒，远程执行但所有文件回到基地节点访问需1 9 0 0 秒，“t m p ”下的文件在执行节点访问需1 6 3 1 秒，“b i n ”和“l i b ”下的文件在执行节点访问需1 5 7 5 秒，“t m p ”，“b i n ”和“1 i b ”下的文件在远程节点访问需1 2 9 3 秒。( 2 ) k o r n e r k o r 9 0 根据用户的行为实现对远程文件的智能缓存，以提高文件远程访问的效率。通过修改u n i x 内核跟踪程序的执行，从而知道此程序应访问哪些文件，当此程序下次远程执行时便对所要访问的文件进行远程智能缓存。( 3 ) t a i t 和d u c h a m p t a i 9 1 利用s u n o s 提供的c 2 安全设备来离线跟踪作业所要访问的文件，采用文件预取( p r e f e t c h ) 来提高文件远程访问效率。第( 1 ) 种方法需要用户指出哪些文件可以在执行节点访问，哪些文件需要回到远程基地节点访问，这对用户来说常常是不现实的；第( 2 ) 种方法需要修改操作系统，第( 3 ) 种方法的系统开销太大。另外，第( 2 ) 和第( 3 ) 种方法无法处理首次执行的程序。2 2 2负载指标的选择大多数分布式系统使用c p u 队列长度作为负载指标，但该指标没有区分进程的性质和大小。一个大进程对资源的占用量及其运行时间可能比几个小进程对资源占用量和运行时间的总和还要多，而且1 0 类作业和c p u 类作业对资源的使用情况也是大不相同的，一个长时间运行的i o 类作业占用很少的c p u 周期，而一个短的c p u 类作业在运行时可占用全部的c p u 。若表示系统负载情况的c p u 队列长度将系统进程也考虑进去，则更不准确，因为系统进程很少占用资源。例如，一个工作繁忙的工作站开机四小时，其s w a p 进程和i n t e d 进程才分别使用了7 秒和2 秒的时间。因而只使用进程队列长度作为负载指标是不合适的，而直接使用资源利用率，即c p u 利用率和i o利用率却很直观，准确。只有当资源利用率达1 0 0 9 6 时，c p u 队列长度对作业响应时间的影响才是主要的。所以对于不同类型的作业应该使用不同的负载指标。之所以大多数分布式系统使用c p u 队列长度作为负载指标是因为它容易获得，并且更主要的原因是无法预先获得作业行为特征的知识。如果知道作业的行为和特点，就可以选择更适合于此作业的负载指标。良好的负载指标关系到能否为作业找到最合适的执行节点，影响着定位策略的有效性。2 2 3选择策略的有效性l e l a n d 和o t t l e l 8 6 分析了v a x 7 8 0 和7 5 0 上正常运行的9 5 0 万个u n i x 进程，分布式计算机系统动态负载平衡的研究统计表明，9 8 的小进程占用了3 5 的c p u 时间，而o 1 的大进程却占用了5 0 的c p u时间。c a b r e r a c a b 8 6 指出绝大部分作业的寿命短于1 秒，对在若干台v a x l l 7 8 5上运行的1 2 2 万个进程的寿命分布进行了实验测量和分析，发现进程的平均寿命为0 4 秒，7 8 的进程寿命短于1 秒，9 7 的进程可在8 秒内结束。从进程占用资源的情况来看，进程可分为三类：c p u 类( 大量使用c p u 而很少访问磁盘) ，i o 类( 大量访问磁盘而很少使用c p u ) 以及普通类( 使用c p u 和磁盘均很少) 。大量使用c p u 同时且有大量i o 操作的作业极少。上述结果说明负载平衡只需迁移极少数长时间运行并且大量使用c p u 资源的作业。也就是说如果没有作业选择，绝大多数调度是无效的，短作业的响应时间有较大增加且浪费大量的调度开销。作业选择，特别是用于非抢先的作业选择是非常困难的问题，至今成果非常少，因为这要求在作业执行以前预测其性质( 如资源要求及执行时间) 。2 3本章小结一个负载平衡系统由两部分组成，即负载平衡的远程执行设备和负载平衡算法。负载平衡依赖于远程执行，即将本地上的作业迁移到远程轻负载的主机上执行，这依赖于远程执行设备的支持。远程执行设备分为两类，一类是抢先的( p r e e m t i v e ) 远程执行设备，一类是非抢先的( n o n p r e e m t i v e ) 远程执行设备。对远程执行设备最基本的要求是远程执行的透明性，进程运行的结果与该进程在网络中什麽地方执行无关，为了迁移此进程也不必用特定方式重新编写程序，也就是说，这些进程迁移后必须仍能像在原地那样访问文件和设备。负载平衡算法使用系统状态信息( 各节点上的负载) 进行负载分配决策，其组成包括：( 1 ) 转移策略：决定节点是否处于适合参加任务转移的合适状态。即决定某节点是个任务发送者还是远程任务的接收者。( 2 ) 选择策略：决定哪一个任务应该转移。选择一个任务进行转移的基本判据是转移此任务的开销比起它响应时间的减少( 收益) 是合算的。( 3 ) 定位策略：决定把所选择的作业转移到哪个节点上去执行。( 4 )信息策略：负责收集系统的状态信息。负载平衡算法的实现方法有三种：发送者启动，接受者启动和对称启动。无论采用什麽样的负载平衡算法，其负载平衡的性能都要受到以下几个因素的影响：远程执行时的文件访问效率、负载指标的选择和选择策略的有效性。所以我们的任务就是给出解决上面几个问题的方法，使负载平衡获得最佳的性能。南京航空航天大学硕士学位论文第三章利用在线跟踪获得作业性质在负载平衡系统中，对某个作业来说，同全局调度具有紧密关系的参数主要有以下几个：( 1 ) 作业使用了哪些文件：( 2 ) 作业对c p u 资源的要求：( 3 ) 作业对i o资源的要求，即作业输入输出的操作情况；( 4 ) 作业的大小，即作业执行时间的长短。按作业对资源的占用情况可将作业分为三类，即c p u 类，i o 类和c p u i o 混合类。n i s h i k a w a 和s t e e n k i s t e n i s 8 6 指出对于不同类型的作业，负载平衡系统应采用不同的方式处理。3 1获得作业性质的一般方法及在线跟踪的概念n 7 1作业执行时间和类型( 大量使用c p u 资源还是具有大量i o 操作，交互式还是非交互式) 等特征，在作业执行前一无所知，想做到成功调度是非常困难的，到目前为止，解决这个问题有两种智能方法：一种是事先运行这些作业以获得它们的特征，然后建立一个作业表，表中指出该作业的性质，作为作业下次执行时的调度依据。这种方法在调度时受到很大的限制：调度不但只限于表中的作业，而且作业名及其参数必须与表中完全一样才行。但是，具有相同作业名而具有不同参数的作业其特性差别可以很大。另一种方法是学习的方法，即通过对某一作业的多次执行而掌握该作业的比较准确的特性知识，也保存一个表用于指导对作业所进行的调度。跟踪( t r a c i n g ) 技术在国际上已普遍使用。 z h 0 8 8 使用跟踪方法产生用于负载指标研究的基准程序。 l e l 8 6 和 c a b 8 6 用跟踪方法研究作业的行为特征，并对负载平衡原则提出启示。 l e l 8 6 和 c a b 8 6 用跟踪方法进行负载平衡算法的性能模拟研究， k o r 9 0 和 t a i 9 1 使用跟踪方法研究远程文件缓存和预取以改进远程文件的访问性能。这些研究有两个共同点：鉴于用跟踪方法获取所需知识并据此作出一些规则，所以都称为智能的方法：但所有这些跟踪的使用都是离线的( o f f l i n e ) ，即都不是实时的，因而用于实际的系统时必然受到很大的限制，尽管大多具有较重要的理论价值。上面所说的第一种获得作业性质的方法实际上是一种离线跟踪的方法( o f f1 i n et r a c i n g ) ，即事先跟踪作业执行，从操作系统内核搜集关于此作业特性的有关数据，如使用c p u 的有关情况，文件访问模式和频度，执行时间等。我们使用在线跟踪( o nl i n et r a c i n g ) 的方法获得作业的性质，事先运行作业一段时间( 例如1 秒) ，在这段时间内根据作业的执行情况获得有关该作业的行为特征，估算执行时间和资源需求，从而决定该作业是否应该被转移，以及转移到哪个执行节点最合适等等；如作业被转移，则作业在远程执行节点重新开始执行，否则作业在本地继续往下执行。g o s w a m i g o s 9 3 也提出过在线获取作业性质的策略，但他们的方法是用于抢先的转移分布式计算机系统动态负载平衡的研究策略中，所以也具用抢先转移的局限性。他们以c p u 负载( c p u l o a d ) 描述作业的性质，c p u 负载定义为：c p u 负载= 作业已用的c p u 时间作业已执行的时间。3 2在线跟踪中获得作业性质的两种途径 k o r 9 0 和 t a i 9 1 都是通过系统内核获得作业的行为特征，只不过k o r n e r 是通过修改u n i x 内核来直接保存执行过的作业的行为特征，而t a i t 等是利用s u n o s 所提供的c 2 安全设备来跟踪访问系统内核而获得作业的行为特征。我们在在线跟踪中使用如下两种方法来获得作业的行为特征“。1 通过作业所使用的系统调用获得作业的性质一个作业的行为主要反映在它所使用的系统调用上，我们使用s u n o s 所提供的p t r a c e ( ) 来跟踪一个作业的所有系统调用，从而获得它的行为特征。其中最重要的是关于文件操作系统的调用，它们是：r e a d 0 ，w r i t e 0 ，o p e n 0 ，c l o s e 0 ，c r e a t 0 ，l s e e k 0 ，m m a p 0 ，r e a d y 0 ，w r i t e v 0，t r u n c a t e 0 ，f t r u n c a t e ( ) ，1 i n k 0 ，u n l i n k ( ) ，c h d i r ( ) ，s y m l i n k 0 ，d u p 2 0 ，r e n a m e 0，m k d i r 0 ，r m d i r 0 。通过对这些系统调用的分析可以获得以下信息：在跟踪的这段时间内，该作业访问了哪些文件，从磁盘上读写了多少数据。2 使用u n i x 内核数据分析作业的性质先使用系统调用“k v m _ o p e n 0 ：”打开系统的内核，然后通过系统调用“k v m _ g r tp r o c ( ) ”和“k v m _ g e t u0 ”可分别获得某指定进程的p r o c 结构和u s e r 结构，通过访问进程的p r o c 结构可获得对应作业所占用的总的内存资源( 包括代码段，数据段和堆栈段) 。同样，通过访问进程的u s e r 结构可获得对应作业在执行的这段时间内所占用的c p u 时间，这个时间包括四个方面：( 1 ) 主进程的用户时间；( 2 ) 主进程的系统时间；( 3 ) 它的所