（计算机软件与理论专业论文）基于java+rmi的动态服务分配策略的研究.pdf

基于j a v ai 洲i 的动态服务分配策略的研究 摘要 j a v a 语言是一种优秀的程序开发语言，其优势在于其跨平台性，已经被广 泛应用于分布式网络应用的开发上，其中r m i 是开发网络分布式应用系统的简 单而主要的途径。现在r m i 技术被越来越多的应用系统所采用，随着客户端请 求的复杂化，单的服务器就很难满足当前用户的需求，因此基于此类应用系统 的集群服务就应运而生了。 集群系统的关键问题在于如何有效利用系统资源。进程迁移机制是集群系统 实现负载平衡算法的一种有效方式，负载平衡算法是实现系统资源有效利用的重 要手段。 本文首先讨论了r m i 技术，介绍了r m i 架构，核心体系。然后介绍了集群 中的资源共享与调度算法。在讨论动态服务平衡调度模型构建及实现中，本文利 用信息的弱一致性来描述集群系统中节点负载信息的部分性和不准确性。节点信 息的弱一致性是动态负载平衡算法进行有效调度时必须考虑的核心问题。本文利 用节点信息的弱一致性作为动态负载平衡调度的依据，提出了基于节点信息弱一 致性的k 子集随机算法。 基于节点信息弱一致性的k 子集随机算法，本文提出了一种具有双i n f o s 机 制的节点信息列表结构。节点i n f o s 通过一定的替换算法，将各个节点中的两个 n f o s 中的信息分别保存为当前集群系统中负载最高的k 个超载节点的信息和负 载最低的k 个欠载节点的信息。在这种情况下，进行动态服务的平衡调度时，不 论节点处于超载或欠载状态都能够准确地找到他所感兴趣的i n f o s 中的信息，来 作为负载平衡决定的依据。最后给出了基于r m i 的动态负载平衡算法。 关键词：刚l ：集群：弱一致陛；k 子集算法；动态负载平衡 r e s e a r c ho fd y n a m i cs e r v i c ea l l o c a t i o ns t r a t e g yb a s e do n j a v ar m i a b s t r a c t j a v ai sa l le x c e l l e n tp r o g r a md e v e l o p m e n tl a n g u a g e d u et ot h ea d v a n t a g eo f c r o s s p l a t f o r m ，i th a sb e e nw i d e l yu s e di nt h ed e v e l o p m e n to fd i s t r i b u t e dn e t w o r k a p p l i c a t i o n s r m it e c h n o l o g yi sas i m p l e ，a n dt h em a i nw a yt od e v e l o pn e t w o r k s d i s t r i b u t e da p p l i c a t i o ns y s t e m ，w h i c hi sa l s oi n c r e a s i n g l yu s e dn o w a l o n gw i t ht h e c o m p l e x i t yo fc l i e n tr e q u e s t s ，i ti sd i f f i c u l tf o ras i m p l es e r v e rt om e e tt h en e e d so ft h e c u r r e n tu s e r s s od u s t e rs e r v i c eb a s e do nt h i sk i n do fa p p l i c a t i o ns y s t e m sw a s p r o d u c e d t h ek e yp r o b l e mo fc l u s t e rs e r v i c ei sh o wt oe f f e c t i v e l yu s et h es y s t e mr e s o u r c e s p r o c e s sm i g r a t i o nm e c h a n i s mi sa ne f f e c t i v ew a yf o rc l u s t e rs y s t e m st oa c h i e v el o a d b a l a n c i n ga l g o r i t h ma n dl o a db a l a n c i n ga l g o r i t h mi sa ni m p o r t a n tt o o lo fa c h i e v i n g s y s t e mr e s o u r c e se f f i c i e n tu s e s t h er m it e c h n o l o g yi sd i s c u s s e da n dt h er m if r a m e w o r k ，p l u st h ec o l es y s t e mi s i n t r o d u c e d a n dt h e n ，r e s o u r c es h a r i n ga n ds c h e d u l i n ga l g o r i t h mo fd u s t e r ss y s t e m s a r ei n t r o d u c e d t od i s c u s st h ei m p l e m e n t a t i o no fd y n a m i cs e r v i c e sb a l a n c es c h e d u l i n g m o d e l ，w eu s e dt h ew e a kc o n s i s t e n c yo fi n f o r m a t i o nt od e s c r i b et h ep a r t i a l i t ya n d i n a c c u r a c yo ft h en o d el o a di n f o r m a t i o ni nd u s t e rs y s t e m s w e a kc o n s i s t e n c yo fn o d e i n f o r m a t i o ni st h ec o r ei s s u ew h e ne f f e c t i v es c h e d u l i n go fd y n a m i cl o a db a l a n c i n g a l g o r i t h mi sn e e d e d a c c o r d i n gt ot h i s ，ak - s u b s e t r a n d o ma l g o r i t h mt h ew e a k c o n s i s t e n c yo fn o d ei n f o r m a t i o ni sp r e s e n t e di nt h i st h e s i s b a s eo nt h ek - s u b s e tr a n d o ma l g o r i t h mw h i c hh a st h ep r o p e r t yo fn o d ei n f o r m a t i o n w e a kc o n s i s t e n c y ，an o d ei n f o r m a t i o nl i s ts t r u c t u r ew i t hd o u b l e i n f o sm e c h a n i s mi s p r e s e n t e d t h r o u g hac e r t a i nr e p l a c e m e n ta l g o r i t h m ，n o d ei n f o sr e s p e c t i v e l ys a v et h e i n f o r m a t i o no ft h et w oi n f o si ne a c hn o d et ob et h em a x i m u ms e to fo v e r l o a d i n gn o d e i nt h en u m b e ro fka n dt h em i n i m u ms e to fu n d e f l o d i n gn o d ei nt h en u m b e rki nt h e c u r r e n td u s t e rs y s t e m i nt h i sc a s e ，w h e np r o c e s s i n gt h eb a l a n c i n gs c h e d u l i n go f d y n a m i cs e r v i c e s ，w h e t h e rn o d e sa r ei nt h ee s t a t eo fo v e r l o a d i n go ru n d e r l o d i n g , n o d e sw i l lb ea b l et of i n de x a c t l yw h a th ei si n t e r e s t e di nt h ei n f o r m a t i o nl n f o st ob e t h es t a n d a r do fl o a db a l a n c i n g f i n a l l y ，d y n a m i cl o a db a l a n c i n ga l g o r i t h mb a s e do n r m ii sp r e s e n t e d k e y w o r d s ：r m i ，c l u s t e r , w e a kc o n s i s t e n c y , k - s u b s e tr a n d o ma l g o r i t h m ， d y n a m i cl o a db a l a n c i n g i n 独创声明 本入声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 逵! 堑遗查墓鱼益薹签型主题煎：奎拦互窒2 或其他教育机构的学位或证书使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：酽杰 签字日期： 呷占月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 耻参 芦1 7 导师签字： 1 黝 扣了 ， 基于j a v ar m i 的动态服务分配策略的研究 第一章引言 目前，一些大型应用、计算和i n t e m e t 公共服务的业务在并发执行的高峰时， 经常遇到的一个非常突出问题是负载超支，因此其提供服务的质量下降更甚至服 务崩溃、中断。当前的解决方法有两种：一个是超级计算机的使用；第二是使用 多台计算机组成一个局域网系统来分担负载，这样利用多台廉价的计算机组成一 个分布式的系统来达到解决问题的目的。 伴随着局域网络技术的高速发展、p c 整体性能的提高、分布式计算技术的 成熟，以及p c 成本的廉价、灵活和丰富的软件资源使之成为优选的高性能、高 可用计算平台，在这种情况下集群技术就应运而生了。集群由一组独立的计算机 经过网络互连而成，是一个松散耦合计算系统。集群中的每个节点是用以承担普 通主机负载和应用的个人计算机，他们都可单独配置并可独立进行操作。集群允 许递增伸缩性，可以通过增加节点来增加容量，是构造i n t e m e t 服务的一个优越 平台。集群使用相对较低的成本获得极高的性能，通过与高性能系统局域网紧密 结合，有助于服务构造，同时巨量数据吞吐率和可用性需求又能补集群的分布式 服务体系结构很好的解决。 1 1集群 集群【l l ( c l u s t e r ) 系统是一种并行或分布式处理系统，它包含多个由互连网络连 接来的独立计算节点，能够通过集群系统软硬件形成一个统一的计算资源。在 集群系统中，计算节点可以是单处理器系统，也可以是多处理器系统。这些计算 节点各自带有c p u 、存储器、i 0 设备以及独立的操作系统。集群系统的多个节 点通过通用网络或者其它高速网络进行互连，从而向用户和应用提供一个单系统 的映像。 集群系统一般采用通用的商用器件、操作系统、并行编程环境以及典型应用 软件等。因此，集群系统能够在较低投资的基础上，通过有效地管理和调度，充 分利用系统资源，达到较高的性能价格比。集群系统一般是多用户( m u l t i - u s e r ) 、 分时共享( t i m e - s h a r i n g ) 系统。 典型的集群系统包含下列组件： 基于j a v ar m i 的动态服务分配策略的研究 多个高性能计算机( p c ，w o r k s t a t i o n ，s m p ) ，一般称为计算节点 具有当前技术水平的操作系统( 层次结构或者微内核结构) 高性能互连网络 网络接口卡 快速通信协议与服务 集群系统中间件( m i d d l e w a r e ) ，包含： 单系统映像s s i ( s i n g l es y s t e mi m a g e ) 系统可用性基础结构( s y s t e ma v a i l a b i l i t yi n f r a s t r u c t u r e ) 资源管理与调度系统( r e s o u r c em a n a g e m e n ta n ds c h e d u l i n g ) 并行编程环境与工具( 如：m p i ，p v m ，调试工具等) 典型应用 串行应用 并行应用 分布式应用 集群系统有如下重要特征： 集群的每个节点都是一个完整的计算机，既可以是对称多处理机型 ( s m p ) ，可以是一台p c 。 节点通过廉价的商用网络连接，如以太网、f d d i 、f i b e r - c h a n n e l ，a t m 交换网等，有时也可使用专用网络。 节点之间是通过i o 总线连接的松耦合关系，这有别于大规模并行处理 机，m p p 通过内存总线连接的紧耦合关系。 节点拥有本地磁盘也使集群与m p p 不同，m p p 是共享磁盘的。 完整的操作系统驻留在每个集群节点上，而m p p 的节点仅运行微内核 系统。 集群系统具有许多其它并行系统无法比拟的优点：集群系统主要由廉价的商 用系统组成，因此在性价比上要比超级计算机和m p p 系统高；集群的每个节点 都是一个传统的计算机平台，用户能够在其熟悉且成熟的环境下开发并运行自己 的程序；集群系统能够很容易地通过添加节点的方式来达到计算性能的提高，可 扩展性较好；集群系统能够方便地通过冗余的廉价商用部件为用户提供高可用 2 基于j a v ar m i 的动态服务分配策略的研究 性。在拥有这些优点的同时，集群系统也面临着巨大的挑战，要解决的主要问题 包括：单一系统映像、高效通信、复制恢复管理、高可用性等。 1 2中间件 中间件是一种通用服务，他存在于系统平台和应用软件之间，这里的系统平 台主要包括：操作系统、网络和数据库。这些服务通常是根据标准的程序接口和 协议定制的，它的作用是解决分布异构的问题，屏蔽不同操作系统的异构，帮助 用户方便，高效地开发复杂的应用软件。针对不同的操作系统和硬件平台，它们 可以有符合接口和协议规范的多种实现。 当前计算机技能的迅猛发展，特别是硬件技术的不断提升，c p u 处理能力 变得更强劲，内存变得更廉价：同时软件规模的不断扩大，使得大型企业应用程 序需要在异构的网络平台上运行。这都对分布式的异构环境提出了新的要求。如 何处理不同操作系统、数据库、语言编译器间的交互和集成是一个非常困难但必 须解决的问题。 中间件作为存在于系统软件与应用之间，管理着计算资源和网络资源，是应 用软件和独立系统间通信的桥梁。网络互联的两个不同的操作系统，即使它们提 供的接口不同，但仍能通过中间件进行信息的通信和传递。中间件屏蔽了网络的 异构和操作系统平台之间的差异，能够使程序开发者把全部的精力都放在业务逻 辑上。 中间件可以应用于负载平衡，平衡调度方面，可以大幅度提高集群系统的性 能，使得集群系统高效运行。 中间件可分为六类： 终端仿真屏幕转换中间件 数据访问中间件 远程过程调用中间件 消息中间件 交易中间件 对象中间件 3 基于j a v ar m i 的动态服务分配策略的研究 中间件屏蔽操作系统和网络的异构性，必须能够提供相应的分布式条件下的 通讯服务，可以将通讯服务分为以下几类： 远程过程调用 面向消息 对象请求代理。 同时基于中间件开发的应用具有良好的可扩充性、易管理性、高可用性和可 移植性。 1 3r mi j a v a 语言是一种优秀的程序开发语言，其优势在于其跨平台性，已经被广泛 应用于分布式网络应用的开发上，其中r m i 就是开发网络分布式应用系统的简 单而主要的途径。用j a v ar m i 开发的应用系统可以部署在任何有j a v a 虚拟机的 平台上。现在r m i 技术被越来越多的应用系统所采用。 r m i 的主要优点如下【2 】： 面向对象： r m i 可将完整的对象作为参数和返回值进行传递，而不仅仅是预定 义的数据类型。也就是说，您可以将类似j a v a 哈希表这样的复杂类型作 为一个参数进行传递。 可移动属性： r m i 可将属性( 类实现程序) 从客户机移动到服务器，或者从服务器 移到客户机。 安全性： r m i 使用j a v a 内置的安全机制保证下载执行程序时用户系统的安 全。r m i 使用专门为保护系统免遭恶意小应用程序侵害而设计的安全 管理程序，可保护您的系统和网络免遭潜在的恶意下载程序的破坏。在 情况严重时，服务器可拒绝下载任何执行程序。 便于编写和使用： r m i 使得j a v a 远程服务程序和访问这些服务程序的j a v a 客户端程 4 基于j a v ar m i 的动态服务分配策略的研究 序的编写工作变得轻松、简单。远程接口实际上就是j a v a 接口。服务 程序大约用三行指令公布本身是服务程序，其它方面则与任何其它j a v a 对象类似。这种简单方法便于快速编写完整的分布式对象系统的服务程 序，并快速地制做软件的原型和早期版本，以便于进行测试和评估。因 为r m i 程序编写简单，所以维护也简单。 可连接现有原有的系统： r m i 可通过j a v a 的本机方法接口j n i 与现有系统进行进行交互。 利用r m i 和j n i ，您就能用j a v a 语言编写客户端程序，还能使用现有 的服务器端程序。在使用r m i j n i 与现有服务器连接时，您可以有选择 地用j a v a 重新编写服务程序的任何部分，并使新的程序充分发挥j a v a 的功能。类似地，r m i 可利用j d b c 、在不修改使用数据库的现有非j a v a 源代码的前提下与现有关系数据库进行交互。 编写一次，到处运行： r m i 是j a v a “编写一次，到处运行 方法的一部分。任何基于r m i 的系统均可1 0 0 地移植到任何j a v a 虚拟机上，r m i j d b c 系统也不例 外。假如使用r m i j n i 与现有系统进行交互工作，则采用j n i 编写的代 码可与任何j a v a 虚拟机进行编译、运行。 分布式垃圾收集： r m i 采用其分布式垃圾收集功能收集不再被网络中任何客户程序 所引用的远程服务对象。与j a v a 虚拟机内部的垃圾收集类似，分布式 垃圾收集功能答应用户根据自己的需要定义服务器对象，并且明确这些 对象在不再被客户机引用时会被删除。 并行计算： r m i 采用多线程处理方法，可使您的服务器利用这些j a v a 线程更 好地并行处理客户端的请求。所有r m i 系统均采用相同的公开协议， 所以，所有j a v a 系统均可直接相互对话，而不必事先对协议进行转换。 1 4 负载平衡研究现状与不足 负载平衡又可以分为两种：静态负载平衡、动态负载平衡。静态负载均衡研 5 基于j o v or m i 的动态服务分配策略的研究 究的内容比较简单，它是根据系统自身设定好的分配策略进行任务调度的，而没 有考虑到集群系统的动态性。本文主要研究的是异构的集群系统的动态负载平衡 问题。 1 4 1 动态负载平衡 在异构的集群系统中，系统中各节点的c p u ，内存等资源是不同的，因此 各节点的性能也是各异的，又由于进程( 任务) 请求都是随机产生的，这样就会 使集群系统的各个节点负载失衡即有的节点处于高负载状态而有的节点处于低 负载状态。 动态负载平衡算法是集群系统实时的根据当前各节点的负载信息进行的任 务调度，因此它能够准确有效地进行负载的平衡。对于异构的集群系统，由于节 点负载信息的动态变化，相比较而言动态负载平衡算法则更能适应这种调度动态 的特点。 1 4 2 动态负载平衡算法的研究现状与不足 传统的研究通常把节点收集的信息简单地认为是实时的、最新的，并没有考 虑到信息的弱一致性对于负载平衡算法的影响。如果不考虑如果不考虑信息弱一 致性对于负载平衡算法的影响，集群的性能将会下降，信息陈旧时间越长集群性 能的下降将越明显。只有充分考虑到信息弱一致性才能给出合理的负载平衡算 法。 大多数的传统研究都没有考虑到信息弱一致性对于负载平衡算法的负面效 果。在传统研究中，研究者通常简单地把节点目前己知的关于系统的信息作为实 时、最新的信息看待，并用这种信息进行调度。这种方法在实际的、信息陈旧时 间较长的环境中效果非常有限。 在负载平衡算法中目标节点的选择是位置策略中重要的组成部分，传统的研 究算法有： 随机选择算法 最短队列算法 k 子集算法 6 基于j a v or m i 的动态服务分配策略的研究 随机算法对目标节点的选择是随机的，盲目的完全不考虑系统各节点的负载 信息的差异。随机算法主要是为了完成任务在系统节点上的平均分配，它不是以 实现系统的负载平衡为目标的。这种负载平衡算法的性能虽然比较简单，但比起 不使用任何负载平衡算法，其性能上有很大的提升。 目前，在负载平衡算法的研究中，目标节点的选择大都采用最短队列算法。 这些研究简单地认为节点收集的信息是实时的、最新的，并没有考虑到信息的弱 一致性对于负载平衡算法的影响。因此他们大都采用最短队列算法来将目前已知 的系统所有节点中负载最低的节点做为目标节点进行进程的迁移。研究表明，节 点的信息陈旧时间越小，其信息的完整性就会越高，信息一致性就越强，因此最 短队列算法的性能越好。实际的集群系统都是信息弱一致性的，所以采用最短队 列算法不能取得理想的性能。 k 子集算法是目前解决集群系统信息弱一致性的比较有效的方法。系统在进 行负载平衡决策时，从系统当前所有节点中随机选择k 个节点( 作为系统所有 节点的一个子集) ，收集这k 个节点的负载信息然后从这k 个负载信息中选择出 负载最低的节点作为目标节点。 1 5 本章小结 本章简要介绍了集群，中间件，r m i 的相关信息，详细说明负载均衡的研 究现状与不足。 7 基于j a v ar m i 的动态服务分配策略的研究 第二章r m i 弟一早k m 2 1d a v ar r m i ( j 丞程方法调用) 是分布式应用程序的开发方法之一。用s o c k e t 开发分布 式应用程序，需要设计一个应用程序级的协议。而r m i 则是将客户和服务器间 的接口抽象为一个本地的过程调用。这样，不需要额外选用或设计新的应用程序 级协议。 2 1 - 1r m i 简介 在r m l 分布式应用程序中，远程对象的方法能够被运行于不同的主机上的 其他的j a v a 虚拟机的方法调用。r m i 非常类似与其他系统的r p c 机制，但是比 r p c 更易用。当所有参数被传送给远程的目标并且被解释，然后将结果返回给 调用者时，会给程序员一个感觉，以为是从本地类文件中调用一个本地方法。如 图2 - 1 ，说明了一个本地调用与远程调用的不同。远程方法调用就使我们调用远 程对象的远程方法就像调用本地方法一样容易。 机器a 机器b 图2 - 1r m i 远程方法调用 利用r m i 构建分布式应用时利用的j a v a 特征： 透明调用 分布式垃圾回收 流的方便访问 8 基于j o v or v i i 的动态服务分配策略的研究 2 1 2r m i 的目标 支持对存在于不同虚拟机上对象的远程调用，支持服务器对客户的回调。把 分布式对象模型自然地集成在j a v a 语言里，尽可能的从语义上保留j a v a 的面向 对象的特性。使分布式对象模型和本地j a v a 对象模型间的不同表面化，使编写 可靠的分布式应用程序尽可能的简单。 2 1 3 脒i 的分布式垃圾回收 当使用j a v a 开发单机版的应用程序时，不再被任何客户程序所应用的对象 将被自动删除。在开发分布式应用程序时，r m i 系统提供了一个分布式的垃圾 回收器，同样来自动删除不再被任何客户程序所应用的远程对象。r m i 使用引 用计数( r e f e r e n c e c o u n t i n g ) 垃圾回收算法，它使r m i 可以跟踪每一个虚拟机上的 所有活动应用。当一个引用进入虚拟机时，它的引用计数就增加。当一个活动引 用结束时，引用计数就减少。如果计数为o ，就说明没有活动引用，所以该对象 就被回收。需要注意的是，由于对象可以通过网络传递，所以r m i 系统还要保 持对虚拟机标识符的跟踪，以确保r m i 的垃圾回收器回收的是既没有被本地调 用，也没有被远程调用的对象。另外，只要有对远程对象的本地引用存在，它就 不能被回收，因为它将传递远程调用并返回客户。传递一个远程对象将增加标识 符到所传递对象的虚拟机的被引用集中。 2 1 4r m i 的架构 2 1 4 1 核心体系 r m i 的核心结构是是基于行为的定义和行为的实现是不同的概念的原则上 的。在r m i 中定义的行为代码和实现行为的代码是处于分开的状态的，是处于不 同的虚拟机中的。r m i 中行为是通过接口进行定义的，而行为的实现是通过对 接口的实现来完成的。在r m i 中的行为的定义即远程服务的定义，而行为的实 现则是远程服务的实现。如下图2 2 所示： 9 基于j o v or m i 的动态服务分配策略的研究 图2 2r m i 的接口与类 r m l 支持两种不同的类实现同一个接口： 服务器端的类实现接口定义的行为 作为远程服务的代理而运行于客户端 它们的关系如图2 3 所示： 图2 3r m i 的客户与服务关系 客户端程序通过远程方法调用，调用服务器端的方法，r m i 将这些请求发 送到服务器的实现程序中。然后将服务器端的处理结果以返回值的形式送回客户 端程序。 1 0 基于j a v ar m i 的动态服务分配策略的研究 2 1 4 2 分层结构 r m i 的分层结构包括三个层次即： 存根( s t u b ) 和框架( s k e l e t o n ) 层，主要功能是把客户端的调用重定向到远 程服务端； 远程引用层，主要功能是解析和管理从客户端发送到远程服务端的引 用。 传输层，主要功能是负责客户端和远程服务端之间的网络连接和数据传 输。 r m i 的三层结构如2 4 图所示： 图2 4r m i 三层结构 如图2 4 ，在存根和框架层中，使用了p r o x y 模式，即一个对象由处于 不同环境中的另一个对象代理，这个代理负责对象间方法调用的转发。在 r m i 系统中存根对象作为远程服务的代理；框架类负责r m i 连接与存根类 交互。 远程引用层主要功能是解析和管理从客户端发送到远程服务端的引用， 存根使用r e m o t e r e f 中的m v o k e o 方法来转发方法调用。r e m o t e r e f 对象能 够解释远程对象调用方法的语义。 传输层，主要功能是负责客户端和远程服务端之间的网络连接和数据传 输。 2 1 5 远程对象的访问 基于j a v ar m t 的动态服务分配策略的研究 在r m i 系统中，客户端第一次运行的时候，它会依据命名及目录服务等方 法来寻找服务器端所提供的服务。r m i 可使用j n d l ( 即标准的j a v a 命名系统接 口) 这种目录服务。同时r m i 系统自带的注册服务r m b e g i s t r y ，它运行在服务器 端，通过自行设定端口参数在特定的端口上提供服务。客户端程序可以利用r m i 系统自带l o o k u p 0 方法来访闻运行在服务器端服务，其中l o o k u p 0 方法的具体参 数是r m i ： 【： 】 。 2 2 本章小结 本章简要讨论了r m i 技术，介绍了r m i 架构，核心体系。 1 2 基于j a v ar m i 的动态服务分配策略的研究 第三章集群中的负载平衡与调度算法 3 1 资源共享与负载平衡 集群系统通过本地局域网络互连实现系统资源共享，同时通过一定的管理软 件进行任务调度和集群内部的资源管理，从而达到资源的高利用率以获得集群性 能的提升。因此，只有实现集群内部资源的有效利用才能把当前集群系统的关键 问题解决好。集群系统是一种松散藕合系统，由多个计算节点组成，集群各节点 之间的负载失衡是很常见的现象。要实现负载平衡得就必须先研究集群系统内节 点问的资源共享和调度算法。 集群系统一般都是多处理机，分时共享的【4 j ，这是与m p p ( m a s s i v e l yp a r a l l e l p r o c e s s i n g ) 最大的不同。集群系统内部节点资源的共享、分配和调度是集群系统 研究的关键问题。为使其便于管理，我们要求集群系统管理调度软件能够实时得 到各节点负载状态的动态变化和新节点的加入与旧节点的删除。基于集群系统这 种高伸缩性和灵活性，使得对高性能的集群系统管理调度软件的需求变得越来越 迫切了。 集群系统内部节点资源的有效共享、分配和调度变得愈发重要，因为只有节 点资源得到有效的平衡才能使得集群系统资源得到最有效的利用。因此说，集群 系统内部节点资源的负载平衡是实现节点资源有效分配、提高集群系统利用率的 必然要求。节点间的任务调度是实现集群系统中节点资源有效共享和负载平衡的 重要手段。任务调度可以分为两种：负载共享和负载平衡。任务调度问题比较复 杂，就目前的研究状况来看，即使在最简单的的情况下( 即当前的集群系统只有 两个节点) ，调度的最有效解决办法也是一个n p 完全问题( n p 即 n o n d e t e r m i n i s t i cp o l y n o m i a l 的问题，也就是多项式复杂程度的非确定性问题) 。 面在实际的条件下，我们只能在一定的可接受的前提下来研究有效的平衡调度算 法。 集群系统内部节点之间是通过平均分配当前所接收的任务来进行负载平衡 的，它是集群系统内部节点实现资源有效共享、分配和调度的重要手段，一直以 来都是集群系统技术研究的热点。集群系统是一种异构的系统，相对于同构系统 1 3 基于j a v ar m i 的动态服务分配策略的研究 的负载平衡来说，问题就变得复杂化了。同构系统相对简单，而异构系统中，各 计算节点的类型和具体结构相差很大，以及任务请求的动态到达，这些都使得集 群系统的负载平衡变得复杂多样。目前的研究表明，任务进程迁移机制是集群系 统内部节点资源实现负载平衡的重要手段，同时任务进程迁移机制可以被方便 地、有效地管理。 任务进程的调度在集群领域一直都是一个比较复杂的问题，因为它牵扯到具 体应用的特性和任务进程的特性。 首先，在任务调度的研究中，我们应该重点掌握任务进程的各方面信息参数。 这些参数为：当前进程的生命时间，进程的内存需用量，进程的i o 及进程间的 通信特性。上述的参数反应了当前任务进程的状态，是集群系统进行资源有效分 配的参考，它直接影响着调度算法的性能。h a r c h 0 1 b a i t e r l 3 1 对进程生命时间的研 究是很用借鉴意义的。就目前的研究现状来看，有关进程的内存需求、i o 特性 以及进程间的通信方面的结论还存着较大的分歧。目前对这些参数的研究大都采 用泊松分布等方式。集群系统的节点的资源主要分 5 1 1 6 1 为： c p u 资源 内存资源 i o 资源 网络通信资源 其中节点的c p u 资源和内存资源是我们研究的重点，它们在直接影响着调 度算法的性能和效果，而其它的资源受条件所限在本文尚不进行研究。节点的 c p u 资源和内存资源是进程赖以生存的根本同时他们之间是制约的，而节点之 间的资源在进程的分配上进行共享，从而达到节点资源的合理有效的利用，我们 的研究暂不考虑这些资源之间的的相互关系。 其次，具体应用对系统的性能有很大的影响，同样调度的算法也是与其相关 联的。对不同的应用系统就应该采用不同的调度算法和分配策略，这样才能适应 相应应用的需要。因此，我们要因地制宜，对不同的应用不同对待，同时还要充 分顾及任务进程的特点以及集群系统中各节点的特性来对任务进程给出相应的 调度算法，这样才能提高集群系统的整体性能和资源的有效利用。 1 4 基于j o v or v i i 的动态服务分配策略的研究 3 2 调度算法 3 2 1 调度算法分类 集群系统内部节点之间是通过平均地分配当前所接收的任务来进行任务的 调度，这是集群系统内部节点实现资源有效共享、分配和调度的重要手段。集群 系统内部节点根据其当前的负载信息来进行任务进程的迁移和调度，调度算法决 定了当前任务进程( 本文中我们不特别区分进程和任务的概念) 的执行要分配到 哪个节点。 就当前的研究状况看来，调度算法的分类已经很明朗，包括下面三种：接收 者启动算法、发送者启动算法、对称启动算法。 接收者启动算法是由集群系统中欠载的节点来首先发起的。当集群系统中一 个节点处于低负载的情况下就会激活本算法，这个节点就会通过一定的调度算法 将其它高负载的节点的某些任务进程迁移到本节点上来，以降低高负载节点的负 载系数，从而达到集群系统节点间的负载平衡。以往的研究说明，当系统处于中、 高负载的情况下，接收者启动算法比较适用。例：b r y a n ta n df i n l 【e r 【1 2 1 ，e a g e r 7 1 ， k x u e g e r l l 3 l 。 发送者启动算法是由集群系统中超载的节点来首先发起的。当集群系统中一 个节点处于高负载的情况下就会激活本算法，这个节点就会通过一定的调度算法 将自身某些任务进程迁移到其它低负载的节点来降低自身的负载系数，从而改善 集群系统节点间的负载平衡。以往的研究说明，当系统处于中、低负载的情况下， 发送者启动算法比较适用【7 】【8 】【9 】1 0 】f 1 1 】。 对称启动算法则结合了上述两种算法的优点，因此对称启动算法在集群系统 中具有更为广泛的使用环境。如：g o s c i n s k i t l 4 1 ，c h a p i n1 1 5 1 ，k r u e g e r t l 3 1 ， s h i v a r a t r i l l 6 1 。 3 2 2 调度算法的实现机制 从性能目标上看，集群系统的调度算法可以分为两种： 负载平衡算法，是在集群系统中以给定的标准进行集群系统各节点的负载平 衡，使得集群系统的资源得到有效的利用。 基于j a v ar m i 的动态服务分配策略的研究 负载共享算法，只是单纯地将集群系统中的等待执行的任务调度给当前空闲 的节点上，它只是为了确保没有节点处于空闲等待的状态。 从上面可以看负载平衡算法较之负载共享算法有更高的适用空间，它能有效 的分配集群系统节点资源，而本文研究的重点也是负载平衡算法。我们研究的负 载平衡的衡量标准是c p u 资源和内在资源，对i 0 资源和节点间的通信暂不深 入研究。 同时负载平衡又可以分为两种： 静态负载平衡算法：静态负载平衡算法是指任务在到达节点以前，先对这个 任务的期望信息进行预测，或者主动由集群系统根据一定的规则给出。它的缺点 在于没有动态地根据当前节点的信息进行分配，所以很可能会导致集群系统的崩 溃。 动态负载平衡算法：动态负载平衡算法是集群系统实时的根据当前各节点的 负载信息进行的任务调度，因此它能够准确有效地进行负载的平衡。因此我们 可以看出静态负载平衡算法必须要准确地得知任务的运行特点，所以只适合于能 够准确根据历史信息预知任务运行特点的固定的系统。但对于异构的集群系统， 由于节点负载信息的动态变化，静态负载平衡算法则显得力不从心，相比较而言 动态负载平衡算法则更能适应这种调度动态的特点。 集群系统的调度算法可以分为初始放置和进程迁移两种机制： 初始放置机制，它是当任务进程在集群系统节点中出现时，按照一定的 负载平衡算法将其迁移到目标节点的执行方法。可以看出由于是进程在 执行之前就产生了任务迁移，所以说他的实现相对简单。资料表明，以 前的集群系统大多采用这种机制来实现系统的负载平衡。 进程迁移机制，它是当任务进程在集群系统节点中运行时，根据当前各 节点的负载状况，将进程从高负载的节点迁移到低负载的节点。通常， 因为涉及到进程的迁移，所以它付出的代价是很大的。 1 6 基于j a v ar m i 的动态服务分配策略的研究 3 3 集群调度算法的设计标准和目标 3 3 1 算法设计的标准 能够适应集群系统中各节点状态的动态变化。 该算法应该能够高效的完成所需的任务，算法本身应当有很高的效率。 因为集群系统不是一个高内聚的系统，所以必须要能应对集群系统突发 的事件，如：节点的当机，掉线等情况，具有一定的容错能力。 3 3 1 算法设计的目标 任务进程在系统中的响应时间应当被减少 节点资源被有效的利用 3 4 负载平衡的策略问题 在集群系统的负载平衡算法中，系统的调度策略和机制是两个不同的概念， 它们之间是有区别的。首先，调度策略研究的问题是： 什么时候进行任务的迁移 从哪个节点选择哪个任务进行迁移 将要迁移的进程转移到哪个节点上 我们研究的机制主要是怎么样去实现策略的决定，这就涉及到怎么做的问 题。而这些问题大都是与底层相关的实现，和操作系统的联系很密切。因此，怎 么做就显得比较困难。因为策略处于相对较高的层次，所以策略的研究相比较机 制来说，比较切合实际。 负载平衡算法通常由六种策略组成，他们分别是：信息策略，转移策略，位 置策略，选择策略，接受策略，决定策略。 其中信息策略是指集群系统节点信息的管理方法，管理方法可以是集中 式也可以是分布式的。信息策略是负载平衡算法决策的基础，主要是决 定集群系统什么时候、怎么样去收集和散布各节点的负载信息。通常， 1 7 基于j a v ar m i 的动态服务分配策略的研究 首先，节点信息按照一定的周期进行收集或者按照一定的事件驱动的形 式来收集；其次，节点信息以广播的形式散布，或其它节点进行信息收 集时进行发送。在本文中，信息策略中的节点信息( 即负载系数) 被定 义为r m i 的远程对象通过其它节点的远程方法调用来获得节点信息。 转移策略即集群系统依据系统中各节点的负载信息进行任务进程的迁 移，通常是将高负载节点的进程迁移到低负载的节点上以获得系统的动 态平衡。以事件驱动的方式来进行任务进程的转移是常用的方式，即当 一个新的任务到达系统之后我们要将它分配给低负载的节点；当任务进 程结束时则降低该节点的负载系数，等待新任务的到来。 位置策略即集群系统依据系统中各节点的负载信息把要迁移的任务进 程分配到哪个节点上。位置策略是负载平衡算法的关键，在动态变化的 集群系统中，位置策略在很大程度上会受到负载信息获取有效性的影 响。 选择策略即在集群系统依据平衡算法选择哪个任务进程进行迁移。主要 涉及到以什么样的标准来选择需要迁移的任务进程，以及对迁移进程的 生命时间和将来行为特点的预测。 接受策略即集群系统中的节点有权决定是否拒绝从其它节点迁移过来 的进程，以此来防止有可能会出现的任务的泛滥与掠夺。 决定策略即集群系统按照一定的负载平衡算法来控制上述策略的先后 执行顺序。不同的策略执行顺序会对负载平衡算法的效率的产生不一样 的影响。 3 5 任务进程的生命时间模型 任务进程的调度在集群领域一直都是一个比较复杂的问题。因为它牵扯到具 体任务进程的特性。其特性主要有：进程的生命时间，进程的内存需用量，进程 的i o 及进程间的通信特性。在上述的对选择策略的阐述中可以看出进程生命时 间在很大程度上影响着选择的标准，同时对于负载平衡算法的决策有着紧密的联 系。 以往对于进程负载特性的研究都是基于两个假设的基础上进