（计算机软件与理论专业论文）集群系统中迁移机制的研究与实现.pdf

重庆邮电大学硕士论文摘要 摘要 随着i n t e r n e t 相关技术的发展，互联网上进行传送、交换的数据量呈指数增 长，对网络服务器的提出了更高的要求。而集群系统具有的高可靠性、高性能 性正好能够较好地满足网络应用所提出来的这种需求。这是因为集群能够充分 利用空闲计算资源，通过相对低廉的软、硬件资源获得较高的性能。因此近些 年来集群技术成为计算机领域研究的热点之一。 进程迁移是实现集群系统的基础，它是指将一个正在执行的作业进程从构成 系统的诸多结点( 微型机) 中的一个结点迁移到另一个结点，并保证迁移后的进 程是从迁移前提供服务的中断处继续往下执行从而提供连续的服务。为了顺利地 完成进程迁移，使用l i n u x 检查点机制，结合l i n u x 的信号机制和网络通信的方法， 实现被迁移的进程在空闲结点上从断点恢复执行。在我们所从事的研究中，主流、 开源的a p a c h ew 曲服务器和m y s q l 数据库服务器作为w 曲服务集群系统开发的 基础。在实现中使用贪婪拷贝策略对a p a c h e j l t 务器子进程进行整体迁移。本文还 分析 a p a c h e 的s e 作原理和进程虚拟地址空间的分布的特点并简要分析了进程 上下文、进程执行期间的动态链接等一些问题。为了使集群系统提供高性能w e b 服务的功能，通过对l i n u x 系统下进程结构和进程资源如打开文件、网络连接等 的分析，也分析t m y s q l 的c s l a 务模型，对访i p m y s q l 服务器的a p a c h e 子进程 进行了迁移，并正确恢复执行。论文最后对集群系统进行了功能测试和系统测试， 并对测试的结果做了简单的分析。 关键词：集群系统，进程迁移，检查点 重庆邮电大学硕士论文 摘要 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t ，t r a n s a c t i o na n de x c h a n g eo fd a t ai n f o r m a t i o n h a si n c r e a s e de x p o n e n t i a l l y ，s ot h es e r v e rw i t hh i g hr e l i a b i l i t ya n dp e r f o r m a n c ei s r e q u i r e dt os u p p l yb e t t e rs e r v i c e t h u sc l u s t e rw i t hh i g hr e l i a b i l i t ya n dp e r f o r m a n c e a p p e a r e dt os a t i s f yt h er e q u i r e m e n to f n e t w o r ka p p l i c a t i o n c l u s t e rc a nm a k ef u l lu s e o fi d l ep r o c e s sr e s o u r c e sa n dg e th i g hp e r f o r m a n c eb yl o wc o s to fs o f t w a r ea n d h a r d w a r e s oc l u s t e rh a sb e e nt h er e s e a r c hf o c u so f c o m p u t e rf i e l di nr e c e n ty e a r s p r o c e s sm i g r a t i o ni st h ef o u n d a t i o no fc l u s t e r t h em e c h a n i s mo fp r o c e s s m i g r a t i o ni st h a ts w i t c h i n gat a s ko fc u r r e n t l yp r o c e s s e df r o mo n en o d et oa n o t h e r , a n de n s u r i n gt h a tt h em i g r a t e dt a s kr e s u n l e sf r o mb r e a k p o i n t ，t h e nt o p r o v i d e c o n t i n u o u ss e r v i c e i no r d e rt os u c c e s s f u l l yc o m p l e t ep r o c e s sm i g r a t i o n ，s e r v e rw i l l u s et h em e c h a n i s mo fl i n u xc h e c k p o i n t ，s i g n a la n dt h es y s t e mc a l lt os t o r ep r o c e s s s t a t u si nb u s yn o d e ，a n dr e s u m et h ee x e c u t i o nf r o mb r e a k p o i n ti n i d i en o d e i no u r r e s e a r c h ，w eb e g i nw i t ha p a c h es e r v e ra n dm y s q ls e r v e r , t or e s e a r c ha n dc o n s t r u c t an e ws e r v e rs y s t e m ，a n ds u c c e s s f u l l yc o m b i n ew e bs e r v i c ew i t hc l u s t e rt e c h n o l o g y t oa c h i e v eh i g he f f f i c i e n c yn e t w o r ks e r v i c e i nt h ee x e c u t i o n ，w eu s et h el o w - c o s to f t i m ea n dh i g he f f i c i e n c ya r i t h m e t i cn a m e dt o t a lc o p yt ot o t a l l ym i g r a t et h ea p a c h e s e r v e rp r o c e s s t h i sp a p e rf i r s t l ya n a l y z e st h ep r i n c i p l eo fa p a c h es e r v e r ，t h ef e a t u r e o fp r o c e s sv i r t u a l m e m o r y a r e a , t h ec o n t e x to fp r o c e s s ，d y n a m i cl i n k so fp r o c e s s e x e c u t i o n ，a n ds oo n t h i sp a p e ra l s od i s c u s s e st h ep r o c e s sm o d e lb a s e do nl i n u x ， p r o c e s so p e n e df i l ea n ds o c k e ta n da n a l y z e sm y s q lc l i e n t s e r v e ra r c h i t e c t u r e b y m i g r a t i n gt h ea p a c h eh t t p dp r o c e s sw h i c hc o n n e c t e dm y s q ls e r v e r , t h ec l u s t e r p r o v i d e sc o n t i n u o u sa n dc o r r e c t l ys e r v i c e t h el a s tp a r to f p a p e ri st h ef u n c t i o n a lt e s t a n dp e r f o r m a n c em e a s u r e k e yw o r d s ：c l u s t e r , p r o c e s sm i g r a t i o n ，c h e c k p o i n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得重庆邮电太堂或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：；厶p 口签字日期： m 6 年6 月，日 学位论文版权使用授权书 本学位论文作者完全了解重迭壑虫太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人授权 重麽整电太堂 可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：豸以即 导师签名： 签字日期： 伊年6 巧日 签字日期：炒6 年月f 日 重庆邮电大学硕士论文第一章绪论 1 1 论文的选题背景 第一章绪论 随着计算机、通信网和w e b 相关技术的发展，无论在i n t e m e t 还是在i n t r a n e t 中，使用网络来获取信息、收发邮件或进行大规模计算的情况越来越多。大量用 户通过各种方式接入互联网络。根据中国互联网络信息中- i j , ( c n n i ) 的调查报告显 示，在过去得7 年中中国互联网络的上网用户人数、上网计算机数、w w w 站点 数均迅速增长。具体情况如表1 1 ： 表1 1 ：中国互联网络发展增长表 汰 1 9 9 8 72 0 0 0 72 0 0 2 12 0 0 5 1 上网用户人数( 万) 1 1 7 51 6 9 03 3 7 04 1 6 0 上网计算机数( 万) 5 4 2 6 5 0 1 2 5 49 4 0 0 w w w 站点数( 个)约3 7 0 0约2 7 2 8 9约2 7 7 1 0 0约6 6 8 9 0 0 面对这种爆发式增长的需求，各类信息中心或数据处理中心对服务器提出了 更高的要求，需要它们既能合理接受各种客户端的请求，又要能够在很短的时间 内做出应答响应，及时处理用户的请求，减少等待时间，提升服务质量。 当w e b 服务器处理负载过重时，在传统的数据信息处理中，就是对服务器 进行软、硬件升级，如更换容量更大、处理速度更快的服务器等。这样做至少有 两方面的缺陷：一是硬件升级及平台的迁移将造成设备中断一定时间，停止对外 的服务，对于某些要求2 4 小时不间断服务的w e b 站点而言将造成巨大的损失； 二是数据环境的迁移将可能面临设备是否具有高可靠性与稳定性的风险。 在这种情况下，服务器集群系统出现了。所谓服务器集群系统是指由多台同 构或异构的服务器组成的服务器组，对外提供透明的服务，从而协同地完成特定 的任务。 集群计算机技术一直是计算机领域研究的一个热点问题。目前，在科学计算 领域。集群系统不但能够充分利用现有的计算资源，而且能够通过较低的软、硬 件代价实现较高性能的计算机系统。随着微处理器技术和高性能网络技术的飞速 发展，集群计算逐渐成为一种有成本效益的并行分布式计算资源。人们已经开 始把注意力投向普通p c 机或者工作站所组成的集群系统来代替昂贵的超级计算 重庆邮电大学硕士论文第一章绪论 机。著名的互联网搜索引擎g o o g l e 公司采用的就是低廉的l i n u x 集群技术，至 2 0 0 3 年4 月，g o o g l e 集群已集成1 5 0 0 0 台p c 机，成为当时世界上最大的p c 机 集群系统【2 】。 1 2 论文的研究工作 研究工作围绕a p a c h e 服务器集群迁移机制的实现技术来展开。主要涉及到 四个部分： 1 分析l i n u x 部分源代码。了解l i n u x 系统进程运行相关的实现细节，包 括进程的上下文环境、虚拟地址空间的映像、e l f 文件格式和加载过程。 2 通过分析a p a c h e 、m y s q l 部分源代码，与a p a c h e 服务器的体系结构相 结合，设计出a p a c h e 服务器进程迁移方案。 3 构建a p a c h e 服务器集群原型系统。 4 搭建l i n u x 环境下的a p a c h e 服务器进程迁移测试环境。设计测试方案， 并分析测试结果。 1 3 研究现状 早在上世纪8 0 年代，进程迁移就作为分布式操作系统的一种系统功能来进 行开发。d e m o s m p 、v 口l 、l o c u s 【4 l 、和s p r i t e 5 1 系统都在一定程度上实现了进 程迁移。这些系统提供k e r n e l 级的支持，通过内核原语访问进程状态，设立检查 点和透明迁移应用进程。目前，采用这种方式成功的实现了进程迁移的系统主要 包括b e o w u l f t ”、s p r i t e 、a c c e n t 、m o s i x 等。在s p r i t e 系统1 丁，强调了透明性和 效率，提供了内核之问的远程过程调用( r p c ) ，允许系统中的任何节点的内核调 用其它节点机上所提供的服务，提供透明的信息传递；a c c e n t 系统采用了一种新 的分段方式虚拟存储方式，该段中数据的访问不能直接访问存储器或者硬 盘，而必须通过i p c 系统来实现，每一个虚拟存储段都有一个后备的i p c 接口与 之相连，每当一个进程访问到某一虚拟的页面时，高层将发一个“虚拟读请求” 消息给该后备接口。存储管理服务进程则通过i p c 信息传送，在其它节点机上找 到对应的段内容。在这种管理方式下，进程迁移时不必将进程的映像信息传到目 的地，而只是传送一个虚拟段给目的机，进程映像的内容则到访问该段时才访问， 以提高系统的响应时间。m o s i x 系统则是基于l i n u x 内核，采用单一系统映像 模式s s i ( s i n g l es y s t e mi m a g e ) “，支持所有的u n i x 接口和机制，其最显著的特 性就是透明性，分布性和配置的灵活性， 让应用程序感觉到自己运行在一个单 处理器系统上。 重庆邮电大学硕士论文第一章绪论 还有另外一类集群系统，它们依赖于原有低层操作系统，并在其上附加相关 软件来达到集群协同工作的效果，而不从低层重新开发自己专用的操作系统，以 维持原有操作系统的通用性和一致性。例如c o n d o r ”、c o c h e c k 9 】等系统采用让 应用程序重新链接相关的检查点库，无需修改源代码的方法。而c l i p 等系统则 采用更为直接的方法，需要将检查点库函数嵌入到相关的源代码中。下面介绍几 种经典的集群系统： c o n d o r c o n d o r 是由美国威斯康星大学开发的集群作业管理系统f l0 1 。该集群系统能充 分利用工作站的空闲时间，它监测网络中所有工作站的状态一旦某台计算机被 认为空闲，便把它纳入到资源池中。在资源池中的工作站被用来执行作业。当工 作站的主人开始使用该工作站时，c o n d o r 便将运行在该工作站上的作业迁移到 其它节点上继续运行，从而避免了对工作站主人的影响。所有这些特征并不需要 修改底层的u n i x 操作系统核心，只需在用户级进行，而且不需修改用户程序， 只需与c o n d o r 提供的库函数重新链接。c o n d o r 的主要特征是：充分利用工作站 的空闲时间：用户只需与库函数重新链接便可利用c o n d o r 提供的检查点和进程 迁移功能；对于远程执行的进程，本地的执行环境被保留；工作站主人对该工作 站拥有最高优先级和完全的控制权：作业保证彻底完成，不会因为系统的故障或 工作站的退出而终止：本地磁盘空间不会被c o n d o r 作业所占用；对网络资源、 数据传送和检查点操作的有效监控：对网络资源、c p u 的协同调度。 l v s l v s 也是目前运用最广泛的一种c l u s t e r 方案。l v s 也是一个中国人创建和开 发的开放源码项目j 。l v s 始于1 9 9 8 年。l v s 方式的c l u s t e r 从结构上可分为两 部分：前端的负载均衡器( 称之为d i r e c t o r ) 和后端的真实服务器( 称之为r e a l s e r v e r ) 。c l u s t e r 前端的d i r e c t o r 将来自外界的请求调度到c l u s t e r 后端不同的r e a l s e r v e r 去执行。r e a ls e l n e r 负责真正的提供各种应用服务，比如：w e b 、f t p 、m a i l 等服务。r e a ls e r v e r 的数量可以根据实际需求进行增加、减少。l i n u x 虚拟服务器 ( l i n u xv i r t u a ls e r v e r , l v s ) 建筑于实际的服务器集群之上，用户看不到提供服 务的多台实际服务器，而只能看见一台作为负载平衡器的服务器。实际的服务器 通过高速局域网或地理上分散的广域网连接。实际服务器的前端是一台负载平衡 器，他将用户的请求调度到实际服务器上完成，这样看起来好像所有服务都是通 过虚拟服务器来完成的。l i n u x 虚拟服务器能够提供良好的可升级性、可靠性和 可用性。用户可以透明地增加或减少一个节点，可以对实际服务器进行监测，如 果发现有节点失败就重新配置系统。 重庆邮电大学硕士论文第一章绪论 m o s i x m o s i x 是由以色n i 约h e b r e w 大学开发【l “。m o s i x 为l i n u x 核心增添了集群 计算的功能。它支持的操作系统平台有b s d o s 和l i n u x ，它允许任意多个基于 x 8 6 p e n t i u m 的服务器和工作站协同工作 1 3 , 1 4 】。在m o s i x 集群环境中，用户无需 对应用程序进行修改，或将应用程序与库连接起来，或将应用程序分配到不同的 节点上运行。m o s i x 会自动将这些工作透明地交给别的节点来执行。m o s i x 的 核心是适应性的资源管理算法，它对各节点的负载进行监测并做出相应的回应， 从而提高所有进程的整体性能。它使用抢先的进程迁移方法来在各节点中分配和 再分配进程，从而充分利用所有的资源。适应性的资源管理算法具体上又包括适 应性的负载平衡算法、内存引导算法和文件i o 的优化算法。这些算法都对集群 中的资源使用情况的变化做出响应。如：节点上的不平衡的负载分布或由于内存 不足而导致的过多的磁盘换入换出。在这种情况下，m o s i x 将进程从一个节点 迁移到另外一个节点上，从而来均衡负载或将进程迁移到有足够的内存空间的节 点上。由于m o s i x 是在l i n u x 的核心中实现的，因此它的操作对应用程序而言是 完全透明的。可以用它来定义不同的集群类型，这些集群中的机器可以相同也可 以不同。与l v s 等集群系统不同的是，m o s i x 集群中的每个节点既是主节点又是 服务节点，不存在主控节点。对于那些在本地节点创建的进程而言，该节点就是 一个主节点：对于那些从远方节点迁移过来的进程而言，该节点就是服务节点。 这意味着可以在任意时刻向集群中增加节点或从集群中删除节点，而不会对正在 运行的进程产生不良的影响。m o s i x 的另外一个特性就是它的监测算法能够监 测每个节点的速度、负载、可用内存、i p c 以及i or a t e 。系统使用这些信息来 决定将进程发送到哪个具体的节点上。当在某个节点上创建了一个进程以后，该 进程就在这个节点上执行。当该节点的负载超过了一定的阀值以后，就将该进程 透明地迁移到别的节点上继续执行。m o s i x 文件系统采用直接文件系统访问的 方法，它可以允许迁移到别的节点的进程在本地进行i o 操作。这样就减少了需 要进行“o 操作的进程与创建该进程的节点之间的通讯，从而允许这些进程更加 自由地在集群中的节点中进行迁移。 国内的许多公司也进行了集群技术的研究与开发。联想公司在1 9 9 9 年9 月推 出了用于分布式高性能计算的n s l 0 0 0 高性能集群服务器。该系统是由4 个节点的 系统，主要基于联想万全4 5 0 0 r 服务器，以总体成本相对较低的组合，替代传统 的小型机或者中型机的工作，价格仅为同等性能的小型机的1 2 1 4 。 从国内的研究情况来看，应用较为广泛的集群系统多是商业产品，无法获得 其技术实现，而且解决方案主要以专有结构和硬件冗余为主。因此研究自主的集 群技术，探索集群解决方案具有实际的意义。 重庆邮电大学硕士论文第一章绪论 1 4 论文的结构 本论文由6 章组成。 第一章绪论。给出论文主要工作、研究背景，介绍国内外一些典型集群系 统。 第二章集群及相关理论。主要介绍集群的理论知识，各种关键支撑技术， 进程状态的收集，e l f 文件的格式及加载过程，进程状态迁移策略。 第三章a p a c h e 服务器集群实现。详细介绍w e b 服务器工作原理，a p a c h e 体系结构分析，a p a c h e 服务器的工作流程。详细描述系统的物理拓扑图和软件 部署。 第四章进程迁移的实现。详细描述a p a c h e 子进程访问m y s q l 服务器和打 开文件时的迁移过程，结合检查点文件格式介绍了恢复过程。 第五章系统测试。给出了测试系统模型。分别进行功能测试和性能测试， 分析得到的测试结果。 第六章结束语。介绍该项目的进一步计划、需要完善的地方。 重庆邮电大学硕士论文 第二章集群及相关问题 第二章集群及相关问题 本章主要讨论集群理论以及相关问题。论述了j a v a 语言的线程迁移机制。 分析和比较了线程迁移和进程迁移。针对w e b 服务器集群的特点和功能，重点 讨论了进程迁移机制。本章后半部分介绍了e l f 文件格式以及链接过程。 2 1 集群系统 简单的说，集群( c l u s t e r ) 就是实现网络高性能计算的一种有效方式。一组 计算机，它们作为一个整体向用户提供一组网络资源【1 5 】。这些单个的计算机系 统就是集群的节点( n o d e ) 。一个理想的集群是，用户从来不会意识到集群系统 底层的节点。在用户看来，集群是一个系统，而非多个计算机系统。集群的多 结点性、分布性等特征及控制信息传输延迟等均被屏蔽在下层。集群系统的管 理员可以随意增加和删改集群系统的节点。 2 1 1 为什么需要集群 集群并不是一个全新的概念。早在七十年代计算机厂商和研究机构就开始 了对集群系统的研究和开发。由于主要用于科学工程计算，所以这些系统并不 为大家所熟知。直到l i n u x 集群的出现，集群的概念才得以广为传播。 对集群的研究起源于集群系统的良好的性能可扩展性( s c a l a b i l i t y ) 。提高c p u 主频和总线带宽是最初提供计算机性能的主要手段。但是这一手段对系统性能 的提供是有限的。接着通过增加c p u 个数和内存容量来提高性能，于是出现了 向量机，对称多处理机( s m p ) 等。但是当c p u 的个数超过某一阈值，像s m p 这些多处理机系统的可扩展性就变的极差。主要瓶颈在于c p u 访问内存的带宽 并不能随着c p u 个数的增加而有效增长。与s m p 相反，集群系统的性能随着 c p u 个数的增加几乎是线性变化的。 集群系统的优点并不仅在于此。下面列举集群系统的主要优点： 高性能成本比。p c 机和标准网络设备大规模生产，价格低。集群系统 的松耦合结构比紧偶合的多处理系统具有更高的性价比。 资源共享。集群系统能有效地支持不同地方的用户对信息和资源( 硬件 和软件) 的共享。 灵活性和可扩展性。集群系统可以增量扩展，并能方便地修改或扩展系 6 重庆邮电大学硕士论文第二章集群及相关问题 统以适应变化的环境而无需中断其运行。 高可靠性和容错性。依靠存储单元和处理单元的多重性，硬件、软件都 有冗余，集群系统具有在系统出现故障的情况下继续运行的潜力。检查 点技术被广泛用于系统故障恢复。 作者认为可扩展性在实际应用中更能体现集群的特点，可以随着对性能要 求的提高而随时增加或减少集群的节点数。 2 1 2 集群的分类 从功能角度看，最常见的三种群集类型包括高性能科学群集、负载均衡群 集和高可用性群集卅。 1 科学群集 又称超级计算集群。按照计算关联程度的不同，可分为两种：一种是任务片 方式。这种方式要把计算任务分成任务片，再把任务片分配给各节点，在：各节 点上分别计算后再把结果汇总，生成最终计算结果。另一种是并行计算方式。 这种方式的节点之间在计算过程中大量地交换数据，可以进行具有强偶合关系 的计算。使用超级计算集群软件，利用若干台p c 机就可以完成通常只有超级 计算机才能完成的计算任务。l i n u x 超级计算机实际是一个计算集群集，其处 理能力与真的超级计算机相等。 2 负载均衡群集 负载均衡群集为企业需求提供了更实用的系统。该系统使负载可以在：计算 集群集中尽可能平均地分摊处理。该负载可能是需要均衡的应用程序处理负载 或网络流量负载。这样的系统非常适合于运行同一组应用程序的大量用户。每 个节点都可以处理一部分负载，并且可以在节点之间动态分配负载，以实现平 衡。对于网络流量也是如此。通常，网络服务器应用程序接受了太多入网流量， 以致无法迅速处理，这就需要将流量发送给在其它节点上运行的网络服务器应 用。还可以根据每个节点上不同的可用资源或网络的特殊环境来进行优化。 3 高可用性群集 高可用性群集的出现是为了使群集的整体服务尽可能可用，以便考虑：计算 硬件和软件的易错性。如果高可用性群集中的主节点发生了故障，那么这：段时 间内将由次节点代替它。次节点通常是主节点的镜像，所以当它代替主节点时， 它可以完全接管其身份，并且因此使系统环境对于用户是一致的。有许多的应 用都必须一天二十四小时不停的运转，如关键性的w e b 服务器、工业控带习器、 医学监测仪、军事设备以及金融股票处理机等。对于这些应用而言，暂时的停 机都会导致数据的丢失和灾难性的后果。高可用性集群的设计思想就是要最大 重庆邮电大学硕士论文 第二章集群及相关问题 限度地减少服务中断时间。 2 2 线程迁移 线程是程序执行的基本单位。线程迁移多用于j a v a 语言。j a v a 作为一种面 向对象的语言，提供了许多开发移动应用程序的工具：比如对象序列化可以捕 获对象的状态，允许对象数据的迁移；而动态类加载机制可以方便的通过网络 传输j a v a 程序代码，允许代码迁移。这些机制使j a v a 对象迁移到新的节点上执 行，但是每次都是从同一位置( 程序的起点位置) 开始执行，而j a v a 线程迁移 克服了这个弱点，它是从断点位置恢复执行。 在j v m ( j a v a 虚拟机) 内部，j a v a 线程的状态如图2 1 。包括： 程序状态：正在执行线程的当前调用方法所使用的类的集合； 数据状态：包含正在执行线程的当前方法的局部变量和中间运算结果； j a v a 栈：每当启动一个新的线程时，j a v a 虚拟机都会为它分配一个j a v a 栈。 j a v a 以桢为单位保存线程的运行状态，线程调用一个j a v a 方法时，在栈中压入 一个新桢，方法返回时弹出该桢然后释放掉。栈桢由三部分组成：局部变量区， 包含中间结果的操作数栈和一些寄存器，比如程序计数器p c ( p c 指向程序被 中断时的那条指令) 。 方法区 j a v a 战 堆 操作数栈 口局部变量i至量!l 图2 i j a v a 线程状态 目前j a v a 线程迁移主要是语言级实现和扩展m 实现两种方式。j a v a 程序 的方法调用栈和p c 是在j v m 中的。只要访问j v m ，就可以捕捉到j a v a 程序 的方法调用栈的状态和p c 。而程序包含的所有对象的状态可从对象流中得到， 这些工作都可以在语言层实现。从语言层上的实现最大的特征是便携性，不需 要修改j v m ，能方便的运行在支持j v m 的任何操作系统平台上，并且实现起来 重庆邮电大学硕士论文第二章集群及相关问题 相对简单。但是性能不高。扩展j v m 的实现，从很大程度上减少了迁移带来的 开销，既减少了程序执行的性能开销，也减少了捕获和恢复机制的代价，但是 修改j v m ，实现复杂。 j a v a 线程迁移过程中状态捕获和恢复的开销来源于两个方面：迁移机制本 身和程序执行导致的。解释器的类型识别导致了第二种来源的开销，为了避免 这种额外的开销，在程序状态捕获时刻而不是在程序执行时进行类型判断。 线程状态捕获时，对于j a v a 栈上的每一桢，分析与桢对应的方法的每条指 令( 从方法开始到p c ) ，判断操作数的类型并压入( 或弹出) 类型桢中。但是 有个问题是：如果代码中存在条件语句( i f 或s w i t c h ) ，从方法开始到方法退 出可能存在几种路径，特别是不同的路径为栈上相同的项分配不同的类型，所 以分析指令之前先确定路径，对每条路径分析如下伪代码所示： s w i t c h ( 指令) c a s e 压栈：把操作数的类型压入类型栈；b r e a k ； c a s e 弹栈：把操作数的类型弹出类型栈；b r e a k ； c a s e 局部变量：局部变量相应的类型压入( 或弹出) 类型栈；b r e a k ； d e f a u l t ：继续处理 另外一个问题是：捕获机制与j i t ( j u s t i n t i m e ) 编译技术的兼容性。若当前 线程执行的方法是j i t 编译时，它的执行是基于本地栈而不是j a v a 栈，也就是 当前线程的j a v a 栈没有真正映射线程的执行状态。面对这个问题，我们使用了 s u nm i c r o s y s t e m s h o t s p o t 虚拟机提供的动态不优化技术( d y n a m i c d e o p t i m i z a t i o n ) 所谓动态不优化，是指将j i t 编译的方法的本地栈转换为j a v a 栈。在状态捕获时，在j i t 编译栈调用动态反优化，重新找回j a v a 解释器生成 的j a v a 桢，然后用上面介绍的方法建立相应的类型栈。 这种迁移方法可以高效的实现包容器负载均衡，包容器的线程在执行时， 从负载对象中读取负载的大小，如果高于某个阀值，则调用迁移方法，迁移方 法将该点的状态保存到状态对象，然后用对象序列化机制将状态对象传送到负 载轻的节点，在该节点上，创建一个新的线程，使用接收到的状态对象初始化 新线程并恢复到迁移前的状态，然后控制转移的中断前的最后一条在指令位置 继续执行。但所有的迁移都必须由程序员指定，即写在代码中，如果线程使用 了资源( 文件、套接字) ，每迁移一次开销很大，尤其在并行系统中表现的更 加明显，所以程序员指定迁移时应该在合适的位置，比如线程进入超强计算时。 对提供w e b 服务为主的集群来说，采用j a v a 线程迁移是不合适的，所以我们 主要的实现办法选用了进程迁移。 重庆邮电大学硕士论文 第二章集群及相关问题 2 3 进程迁移 2 3 1 进程的概念 进程是操作系统中的一个概念。进程是一个动态使用系统资源、处于活动 状态的程序。l i n u x 是一个多任务操作系统，系统调度器使用合适的调度算法 来调度进程。从内核的观点看，进程是担当分配系统资源的实体 1 7 , 1 8 , 1 9 1 。一个 程序可启动多个进程，他的每个运行副本都有自己的进程。进程的存在分为进 程的产生、执行和结束三个步骤。在一个进程的生命周期中它会使用许多系统 资源。它会用系统的c p u 执行它的指令，用系统的物理内存来存储它和它的 数据。它会打开和使用文件系统中的文件，会直接或者间接使用系统的物理设 备。 每个进程都具有自己的属性。为了让内核管理进程，每一个进程都是由一 个进程描述符表示，进程和进程描述符之间有非常严格的一一对应关系。进程 描述符用一个t a s k _ s t r u c t 数据结构来存储，它包含了进程的详细信息，主要有 进程标志符( p i d ) 、进程所占的内存区域、相关文件的文件描述符( f d ) 、安 全信息、进程环境、信号处理、进程状态等几个方面。这些信息是完整保存进 程状态并正确复原的关键。 c p u 既可以运行在用户态下，也可以运行在内核态下。例如：i n t e l8 0 x 8 6 微处理器有四种不同的执行状态。但l i n u x 内核仅仅使用其中的内核态和用户 态。当一个程序在用户态下执行时，它不能直接访问内核数据结构或者内核的 程序。当程序在内核态执行的时候，访问的限制不再有效。在l i n u x 中，进程 描述符存放在动态内存中，系统把每个进程的两个不同数据结构存放在一个单 独的8 k b 内存区。 2 3 2 进程的状态 进程是程序的一个执行环境，由正文段、用户数据段、系统数据段【1 5 挪1 构成， 随着执行的过程状态不断的变化。 正文段：存放被执行的机器指令。这个段是只读的，允许系统中正在运行 的两个或者多个进程之间能够共享这一段代码。例如，有几个用户都在使用文 本编辑器，在内存中仅需要改程序指令的一个副本，他们全都共享这一副本。 用户数据段：存放进程在执行的过程中直接进行操作的所有数据，包括进 程使用的全部变量在内。这里包含的信息是实时的，可以被改变。虽然进程之 1 0 重庆邮电大学硕士论文第二章集群及相关问题 间可以共享正文段，但是每个进程需要有它自己的专用用户数据段。例如同时 编辑文本的用户，虽然运行着同样的程序编辑器，但是每个用户都有不同的数 据：正在编辑的文本。 系统数据段：该段存放程序运行的环境。程序是由一组指令和数据组成的 静态事物，它们是进程最初使用的正文段和用户数据段。作为动态事物，进程 是正文段、用户数据段和系统数据段的信息的交叉综合体，其中系统数据段是 进程实体最重要的部分，因为这一部分存放有进程的控制信息。系统中有许多 进程，操作系统要管理他们、调度它们运行，就是通过这些控制信息。 进程执行环境就是进程上下文环境，是进程执行时所需的静态与动态条件 的组合。具体说，进程上下文由其用户地址空间的内容，硬件寄存器的内容以 及与该进程有关的内核数据结构组成。进程的上下文是由它的用户级上下文、 寄存器上下文以及系统上下文组成。 用户级上下文：用户级上下文由进程的用户程序段部分编译而成的用户正 文段、用户数据、用户栈等组成。 寄存器上下文由程序寄存器p c 、处理机状态字寄存器p s 、栈指针和通用寄 存器的值组成。 系统上下文包括：进程描述符、与进程相联系的终端设备描述符、文件描 述符、内存描述符、内核而系统上下文包括：进程描述符、与进程相联系的终 端设备描述符、文件描述符、内存描述符、内核栈等内核数据信息。其中进程 描述符是最基本的一个，它包含了有关进程的描述信息、控制信息和资源信息， 是进程动态特征的集中反映。具体包括操作系统用来控制进程的所有控制信息， 比如进程优先级、进程标识、父进程标识等；包括进程缓冲的消息和连接控制 信息等消息状态；包括文件描述符和文件缓冲块等进程所使用文件的状态信息； 以及描述进程使用内存情况和进程映射关系的内存描述符和页表等相关内容。 栈等内核数据信息。其中进程描述符是最基本的一个，它包含了有关进程 的描述信息、控制信息和资源信息，是进程动态特征的集中反映。具体包括操 作系统用来控制进程的所有控制信息，比如进程优先级、进程标识、父进程标 识等：包括进程缓冲的消息和连接控制信息等消息状态；包括文件描述符和文 件缓冲块等进程所使用文件的状态信息；以及描述进程使用内存情况和进程映 射关系的内存描述符和页表等相关内容。 一个进程的状态信息主要包括内容如表2 1 ： 重庆邮电大学硕士论文第二章集群及相关问题 表2 1 进程主要状态信息 进程虚拟内存 包括此进程的所有内存地址空间：代码、数 据、堆栈等 打开文件的状态 包括文件的标识f d ，文件访问偏移 o f f s e t 和文件打开方式等等 进程消息包括进程缓存的发送和接收的消息 进程执行的状态包括寄存器值、进程p c 和s p 指针等 其他内核状态 包括进程的p i d 号、信号和端口、c p u 状态等 信息 这些状态有一些可以从进程的上下文中直接获取，有一些去只能通过o s 内 核的数据结构中提取，比较困难。 2 3 3 进程迁移概念 进程迁移是指将一个正在运行的进程，从一个结点( 源结点) 传送至u 另外 一个结点( 目的结点) ，并能继续运行的过程。进程迁移的基本流程如图2 2 图2 2 进程迁移的基本流程 从图中可以看到，进程迁移一般包括在源结点上提取被迁移进程的状态信 息，状态信息向目标结点的传送。目标结点产生一个新的进程接收并导入被迁 移进程的状态信息。恢复被迁移进程与其它进程间的通信。 进程迁移是支持负载平衡和高容错性的一种非常有效的手段。对一系列的 负载平衡策略的研究表明进程迁移是实现负载平衡的基础，进程迁移在很二多方 面具有适用性： 动态负载平衡：将进程迁移到负载轻或空闲的节点上，充分利用可用资源， 通过减少节点间负载的差异来全面提高性能。 容错性和高可用性：某节点出现故障时，通过将进程迁移到其它节点继续 重庆邮电大学硕士论文第二章集群及相关问题 恢复运行，这将极大的提高系统的可靠性和可用性。在某些关键性应用中，这 一点尤为重要。 进程迁移的实现复杂性及对o s 的依赖性阻碍了进程迁移的广泛使用，尤其 是对透明的进程迁移实现。根据应用的级别，进程迁移可以作为o s 的一部分、 用户空间、系统环境的一部分或者成为应用程序的一部分。 用户级迁移：用户级实现较为简单，软件开发和维护也较为容易，因此， 现有的很多系统都是采用用户级实现，如c o n d o r 和u t o p i a 。但由于在用户级无 法获得k e r n e l 的所有状态，因此，对于某类进程，无法进行迁移。另外，由于 k e r n e l 空间和u s e r 空间之间存在着壁垒，打破这个边界获得k e m e l 提供的服务 需要巨大的开销。因此，用户级实现效率远远低于内核级实现。 应用级迁移：应用级迁移实现较为简单，可移植性好，但是需要了解应用 程序语义并可能需对应用程序进行修改或重编译，透明性较差，这方面的系统 有f r e e d m a n 、s k o r d o s 等。 内核级迁移：基于内核的实现可以充分利用o s 提供的功能，全面的获取进 程和o s 状态，因此实现效率较高，能够为用户提供很好的透明性。但是由于 需要对o s 进行修改，实现较为复杂。这方面的典型系统有m o s i x 和s p r i t e 系统。 进程迁移的一般步骤为1 2 i j ：主机调度 确定目标进程 状态收集一 状态保存 一 转移状态 状态恢复一 选择进程一 恢复断点。状态的收集是比较关键的一步， 只有正确的、完整的收集到目标进程的状态信息，才能保证迁移到新的主机后 能够顺利地、正确的恢复到中断点后一条指令继续执行。 目前的集群系统多利用l i n u x 操作系统中的检查点机制来获取进程的足够 信息。检查点( c h e c k p o i n t ) 是容错计算机系统进行故障恢复的重要手段 2 2 , 2 3 1 。 l i n u x 的检查点机制在产生检查点文件的时候，只是对表2 1 中第l 、4 、5 项中 的内容做了保存，而上表中2 、3 项情况就没有考虑。这自然就限制了恢复进程 的种类，比如打开文件的、有s o c k e t 连接的进程就不可能直接使用l i n u x 的检 查点文件保存的信息来正确恢复。如何处理这类进程迁移的问题将成为本论文 第四章主要讨论的对象。考虑到同构环境( 各节点硬件和操作系统相同) 实现 进程的状态提取相对容易，所以采用同构节点组成集群原型系统。 2 3 4 经典进程迁移策略 在进程迁移中，如何处理进程状态也是一个较为重要的地方。对于这个问 题，目前已经有许多成熟的策略。其中主要有贪婪拷贝策略、惰性拷贝策略、 预拷贝策略、f i l es e r v e r 2 4 1 等。这几种策略的不同点主要体现在以下三个方面： 重庆邮电大学硕士论文第二章集群及相关问题 1 从源主机上传输多少状态到目标主机；2 何时挂起在源主机上运行的进程：3 何时启动在目标主机上的进程。 ( 1 ) 贪婪拷贝策略( e a g e rc o p y ) ：贪婪拷贝策略是最早出现，也是应用最广泛 的策略。该策略先挂起源主机进程，然后传输进程的全部状态( 包括一些打开的 文件、执行状态等) 到目标主机后，再在目标主机启动进程。这种策略较简单， 方便实现，对源节点的迁移驻留依赖较少。但有两个不足：1 状态传输时间、 进程冻结时间都相对较长，致使系统认为是进程间通信失败的可能。这对于实 时系统是不可接受的：2 有些冗余的数据传输到目标主机后，实际并没有用上， 造成网络负担。c o n d o r 、l s f 就是采用这种方法实现。 ( 2 ) 惰性拷贝策略( 1 a z yc o p y ) ：又名d e m a n d p a g e 策略。该策略先传输进程在 目标主机上重新执行所需要的最小相关的信息。比起贪婪拷贝策略，它传输的 是必需的最少量的状态集合，然后在目标主机上启动。这些信息通常是进程的 部分或全部的核心数据和- - + 部分用户地址空间内容。当进程在