（计算机应用技术专业论文）基于linux的分布式系统中的进程迁移及实现.pdf

摘要 摘要 进程迁移系统能提高分布式系统的负载平衡性和可靠性，但在这一研究领域， 国外处于领先地位。由于进程迁移几乎都是在各商用操作系统中实现的，其源代 码不公开，所以很难得到广泛使用。并且现有的进程迁移系统还不尽如人意 迁移算法主要采用了效率较低的t o t a l c o p y 算法、网络通信量过重等。另一方面， 对于最大的开放源代码的操作系统l i n u x 来说，在其内核中也还没有正式发布具有 进程迁移功能的模块。因此，研究分布式系统中的进程迁移，以及在l i n u x 上的实 现，将为我国的信息化进程提供坚实的保证，具有很强的社会意义和市场价值。 本论文分为两大部分：分布式系统中的进程迁移理论研究；进程迁移理论在 l i n u x 上的实现。在整个理论分析的部分，主要是围绕着两个问题进行展开论述： ( 1 ) 如何迁移，使得进程能够在新主机上正确运行，即进程迁移算法；( 2 ) 迁移机 制，即由哪台主机( 源主机) 选择哪个进程向哪台主机迁移( 目的主机) 。本文基于进 程迁移的三个条件提出的进程迁移算法，最大程度地将进程状态迁移和进程的运 行并行起来，从而提高了迁移速度，网络通信量也较小，而且也没有对源节点的 残余依赖性。在对进程迁移机制的理论分析中，采取了利于提高系统性能的迁移 机制，并与现有的经典迁移系统进行了比较。在l i n u x 上实现迁移系统时，与通 常的项目设计样，首先规划出了整个迁移系统的模块划分：m i g r a t e o u t 模块、 m i g r a t e l n 模块、s e l e c t e r 模块和l o a d m a n a g e r 模块，并给出了各模块的实现流程图。 实际上，实现部分也分为对迁移算法的实现和对迁移机制的实现。迁移算法的实 现，也就是对m i g r a t e o u t 模块和m i g r a t e i n 模块的实现；迁移机制的实现，也就是 对s e l e c t e r 模块和l o a d m a n a g e r 模块的实现，实现部分会涉及到对l i n u x 内核的编 程。 论文的最后是测试与结果分析部分。通过对进程迁移系统和同类产品的功能 和性能测试比较，得出本进程迁移系统的适用范围，并证明本进程迁移算法和整 个迁移系统都具有较高的性能。 关键词：分布式系统，进程迁移，迁移算法，l i n u x 内核 a b s t r a c t a b s t r a c t p r o c e s sm i g r a t i o nh a sb e e na d v o c a t e da sam e a n so fi m p r o v i n gt h el o a db a l a n c i n g a n dr e l i a b i l i t yo fd i s t r i b u t e ds y s t e m s h o w e v e r , t h ef o r e i g ns o f t w a r ea r et h eo nt h e d o m i n a t i n gp o s i t i o ni nt h ep r o c e s sm i g r a t i o nf i e l d b e c a u s et h a tt h ep r o c e s sm i g r a t i o n h a sa l m o s tb e e nr e a l i z e di nt h ec o m m e r c i a lo p e r a t i n gs y s t e m s ，i e w ec a n tg e tt h e s o u r c ec o d ef r e e l y , t h ep r o c e s sm i g r a t i o nw o n tb eu s e dw i d e l y f u r t h e r m o r e ，t h e e x i s t i n gm i g r a t i o ns y s t e m sa r ew a i t i n gt ob ei m p r o v e df o rt h eo u to fd a t em i g r a t i o n a l g o r i t h m s ，t h eh e a v yc o m m u n i c a t i o no v e r h e a da n ds oo n o nt h eo t h e rh a n d ，t h e b i g g e s ts o u r c eo p e n i n go p e r a t i n gs y s t e ml i n u xh a s n tr e l e a s e dt h ee d i t i o ni n c l u d i n g p r o c e s sm i g r a t i o ns u b s y s t e m i t i sn o to n l yt h e o r e t i c a l l ys i g n i f i c a n tb u ts o c i a l l y m e a n i n g f u lt or e s e a r c ha n dd e v e l o p et h ep r o c e s sm i g r a t i o no fo u ro w nc o u n t r y t h i sp a p e ri n c l u d e st w oc o m p o n e n t s ：t h et h e o r e t i c a lr e s e a r c ha n dt h er e a l i z a t i o ni n l i n u x t h ef i r s tc o m p o n e n ti sp r e s e n t e da r o u n dt w oq u e s t i o n s t oa n s w e rt h eq u e s t i o n “h o wt om i g r a t e ”，ap r o c e s sm i g r a t i o na l g o r i t h mi sp r o p o s e db a s i n go nt h r e em i g r a t i o n c o n d i t i o n s t h es e c o n dq u e s t i o ni s “w h i c hp r o c e s si st h es o u r c ch o s t ，w h i c hp r o c e s si s t h ed e s t i n a t i o nh o s t ，w h i c hp r o c e s ss h o u l db ec h o s e nt om i g r a t ea n dw h e n ? ”t oa n s w e r t h eq u e s t i o n ，ai m p r o v e dm e a n so fm i g r a t i o nm e c h a n i s mi sp r e s e n t e d t h em i g r a t i o n a l g o r i t h mp r o p o s e db yt h i sp a p e ra l l o wt h a tt h ee x e c u t i o no fp r o c e s sm i g r a t i n ga n d p r o c e s sg o i n gi sc o n c u r r i n gt ot h em o s td e g r e e t h em i g r a t i o n a l g o r i t h ms p e e d su pt h e m i g r a t i o n ，r e d u c e st h ec o m m u n i c a t i o no v e r h e a da n da v o i d sr e s i d u a ld e p e n d e n c i e s t o t h er e s e a r c ho ft h em i g r a t i o nm e c h a n i s m ，ia d o p t e dt h em e r i to fo t h e r sa n ds e l e c t e dt h e m o s te f f i c i e n tw a y s t ot h es e c o n dc o m p o n e n t ，w h e nir e a l i z e dt h em i g r a t i o ns y s t e m ， t h es y s t e mi sd e v i d e df o u rm o d u l e s ：m i g r a t e o u tm o d u l e ，m i g r a t e i nm o d u l e ，s e l e c t e r m o d u l ea n dl o a d m a n a g e rm o d u l e t h ef l o wc h a r t sw e r ea l s od i s p l a y e d i nf a c t ，t h e r e a l i z a t i o ni n c l u d e st w op a r t s ，t h er e a l i z a t i o no ft h ep r o c e s sm i g r a t i o na l g o r i t h ma n dt h e r e a l i z a t i o no ft h ep r o c e s sm i g r a t i o nm e c h a n i s m t h ef i r s tp a r ti sa l s ot h er e a l i z a t i o no f m i g r a t e o u tm o d u l ea n dm i g r a t e l nm o d u l e ，t h es e c o n dp a r ti sa l s ot h er e a l i z a t i o no f s e l e c t e rm o d u l ea n dl o a d m a n a g e rm o d u l e t h ec o m p o n e n to fr e a l i z a t i o ni si n v o l v e di n t h el i n u xk e r n e lp r o g r a m i i 垒! ! ! ! ! 里 a tt h ee n d t h e p r o c e s sm i g r a t i o ns y s t e m i st e s t e db o t hi n f u n c t i o na n d p e r f o r m a n c e t h et e s tr e s u l t sa r ea n a l y s e da n dt h e yp r o v et h eh i g hp e r f o r m a n c eo ft h e p r o c e s sm i g r a t i o na l g o r i t h ma n dt h ew h o l em i g r a t i o ns y s t e m k e yw o r d s ：d i s t r i b u t e ds y s t e m s ，p r o c e s sm i g r a t i o n ，m i g r a t i o na l g o r i t h m ，l i n u x k e l l l e l i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：季躲日期：d 6 年6 月舌日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：晕墼导师签名：三丝 日期：年月，日 纱昭占莎 第一章引言 1 1 课题背景和意义 第一章引言 分布式系统的特点之是允许信息在系统中移动，但有的系统只允许数据f 文 件、数据库记录等) 在系统中迁移，有的系统只允许还未开始执行的进程进行迁移 f 静态迁移) ，有的系统允许处于运行状态的进程进行迁移( 动态迁移) ，本文将对最 后这种情况进行深入的讨论，下文中所提到的进程迁移都是指动态进程迁移。 分布式系统中的进程迁移，其作用概括起来主要体现在以下几个方面： 第一是实现高效率容错。在分布式系统中，当一个主机发生故障时，则需将该 主机正在运行的进程给予迁移；否则，如果主机正在运行的是某些关键进程，则 这样有可能导致整个系统任务的错误运行，后果将不堪设想。 第二是提高系统的负载平衡。在特定的时间内，各主机负载具有不确定性， 会出现负载不平衡。这时通过进程迁移才能使主机实时地计算任务、实时地动态 调度，使系统内部真正达到动态负载平衡和动态负载分担。 第三是减少网络通信负载。当某一进程与其它进程存在通信，而与其通信的 相对较多的进程不在同一主机上，那么就将该进程进行迁移，从而减少整个网络 通信的负载。 第四是特殊资源的使用。进程的迁移可以充分利用特定节点上独特的软硬件 资源。 当然，进程迁移问题的设计与实现一定要为其具体的目的服务。本文针对的 是负载平衡目标。 尽管进程迁移能够使以上几点成为可能，但迁移尚未被广泛应用。原因之一 是：一方面向已有系统增加透明迁移非常困难，另一方面，直接从头设计具有迁移 能力的新系统也是一项工作量很大的工程。此外，操作系统开发商并没有从商业 上支持进程迁移。 然而，进程迁移仍然具有很大的研究价值。某些研究者得出的“进程迁移不 实用”的结论已经被证明过于悲观。 随着分布式系统，尤其是分布式操作系统的更加广泛地应用，人们对高性能 计算的研究重点己经从超级计算机转移到了工作站网络( n e t w o r k so fw o r k s t a t i o n s ，简称n o w ) 和大规模分布式系绀“。可以预期进程迁移技术将扮演一个 1 电子科技大学硕士学位论文 更加重要的角色，并获得广泛的认可。 另方面，l i n u x 系统作为世界上最为著名的自由软件，得到了业界广泛的认 可。伴随着人们对l i n u x 的日益关注，它的应用范围也是一日千里。然而，令人感 到遗憾的是，截止到l i n u x2 6 版本，还未支持进程迁移技术。所以，本文利用其 源代码的开放性来研究分布式系统中的进程迁移是极其有意义的。 1 2 进程迁移的含义和所涉及的问题 分布式系统中的进程迁移是指， 动的内容包括进程的控制执行状态、 统有关的信息。 把进程从源节点移动到目的节点去执行。移 地址空间、通信状态以及其他一些与操作系 在设计进程迁移功能时我们需要解决如下问题： 第，如何迁移，使得进程能够在新主机上正确运行? 第二，何时( 迁移时机) 由谁( 哪台主机作为源主机) 选择谁( 哪个进程) 向谁( 哪台 主机作为目的主机1 迁移? 1 3 章节内容安排 后续章节内容安排如下： 第二章是进程迁移算法分析。文中基于三个迁移条件的组合提出了一种“连 续拷贝”迁移算法“c o n t i n u o u s c o p y ”，并将此算法与目前的几种算法进行了性能 比较，解决进程迁移所涉及的第一个问题。 第三章是进程迁移的机制。我们给出了本系统对“迁移时机”、“源主机”、“待 迁移进程”和“目的主机”的选择机制，解决进程迁移所涉及的第二个问题。 第四章是进程迁移模块在l i n u x 上的实现。主要介绍前面章节中的进程迁移理 论在l i n u x 操作系统上的设计与实现。 第五章是测试与结果分析。分别对前述工作进行功能和性能方面的测试，并 对结果进行分析。 第六章总结和展望。总结全文并指出有待解决的问题。 正文后是致谢、参考文献和作者在学期间的研究成果。 2 第二章进程迁移算法分析 第二章进程迁移算法分析 本章是进程迁移算法的理论分析，将回答进程迁移的一个问题。第一节说明 究竟有哪些内容需要迁移；第二节首先阐述现有的进程迁移算法，然后根据进程 迁移的三个条件提出一种新的迁移算法，最后从理论上把此新算法与以往的算法 进行比较；第三节是本章的总结。 2 1 迁移的具体进程信息 在研究迁移算法之前，先说明需要对哪些具体的进程信息进行迁移。 1 进程控制和运行信息：包括进程标识符信息( p i d ，p p i d ) ( 这里我们要考虑 在迁移之后的新主机上仍然能够保持p i d 的唯一性) ；处理器状态信息( 处理器的通 用寄存器、指令计数器、程序状态字p s w 以及用户栈指针) ；进程调度信息( 进程 当前状态、优先级、调度所需的其他信息、进程的阻塞原因) ；进程控制信息( 程序 和数据的地址、进程同步和通信机制、资源清单、链接指针) 。 2 地址空间：包括属于该进程的所有虚存空间。这是进程的所有状态信息中 最大的部分，包括代码页、栈页和堆页。我们后面会看到不同算法最主要的差别 就在于对这部分信息的处理不同：一次发送还是多次发送、与进程的执行是顺序 进行还是并行进行。 3 消息：进程缓存的消息和关于通信连接的控制信息。需要考虑如何让在迁 移过程中到来的消息能够立刻或稍后被迁移后恢复运行的进程所接收和处理。 4 文件：进程的文件描述符和缓存的文件块。这里需要一个分布式文件系统 的支持，以便让源节点和目的节点上的进程都能看到统一的文件名字空间。 2 2 迁移算法分析 目前流行的几种迁移算法有t o t a l c o p y 、l a z y c o p y 、p r e c o p y 和h u s h i n g 。 前三种算法只有源节点和目的节点参与了迁移过程，而f l u s h i n g 除了源节点和目 的节点外，还有文件服务器作为第三方节点，参与迁移过程。在只有源节点和目 的节点参与的算法中，可以用三个条件来区分迁移算法，这三个条件是：从源节 3 电子科技大学硕士学位论文 点传输至目的节点的进程状态量s t a t e ；挂起源节点上被迁移进程的时间t i m e l ； 在目的节点上继续执行迁移进程的时间t i m e 2 。这三个条件是进程迁移算法需要 考虑的最基本的问题，也是区分进程迁移算法的有效条件。 而对于以上条件的值都有两个，s t a t e 的值为：“全部”或“部分”；t i m e l 的值为：“决定进程迁移时”或“进程状态传输完成时”；t i m e 2 的值为：“传输完 全部进程状态时”或“传输完最少所需状态时”。根据这三个条件值的不同组合， 可以形成不同的算法，如表1 - 1 所示： 表1 - 1 进程迁移条件 s 丑 旺耵m e l1 1 m e 2 l 全部决定进程迁移时传输完全部进程状态时 2部分决定进程迁移时 传输完最少必需状态对 3全部 进程状态传输完成时传输完全部进程状态时 4全部决定进程迁移时传输完最少必需状态时 三个条件值的组合可有八种算法，但除了表1 中的4 种算法外，其余4 种算 法都是不合理的。t o t a l c o p y 算法对应于表1 中的第1 种组合，l a z y c o p y 算法对 应于第2 种组合，p r e c o p y 算法对应于第3 种组合。而本文提出的算法对应于第4 种组合，命名为“连续拷贝”c o n t i n u o u s c o p y 算法。 2 2 1 已有经典算法描述 t o t a l c o p y 算法，当决定进程迁移时，在源节点上挂起要迁移的进程，然后将 进程的全部状态信息传送到目的节点上，再由目的节点恢复执行迁移后的进程。 t o t a l c o p y 算法是所有算法中实现最简单的，有可能是最常用的，对源节点也没有 残余依赖。但它的进程迁移时延依赖于进程状态量的大小，对于实时进程和有大 量l o 的进程，此算法进程迁移时延是不允许的。 l a z y c o p y 算法，当决定进程迁移时，在源节点上挂起要迁移的进程，然后将 进程的部分状态信息( 进程执行时的最少必需状态) 传送到目的节点上，再由目的节 点恢复执行迁移后的进程，在进程需要时，再传送其余的进程状态。从决定迁移 到在目的节点上执行所需时间，l a z y c o p y 算法是最短的，网络传输量也有可能是 最少的。但此算法最大的缺陷是它对源节点有残余依赖性，并存在一定的进程迁 移时延。 p r e c o p y 算法，首先传输全部的进程状态到目的节点，此时在源节点上并行地 执行此进程，当传输完全部进程状态时，在源节点上挂起此进程，再次传输所有 4 第二章进程迁移算法分析 的因进程与传输并行执行而产生的“脏页”，在所有的传输完成时，再由目的节点 恢复执行迁移后的进程。因为有可能某个页面在被传输至目的节点的过程中，在 源节点上进程执行，会被再次访问修改，所以在p r e c o p y 算法中，某些页面会被 传送两次。这样就增加了系统的通信传输量，有可能进程迁移时延会比t o t a l c o p y 算法的还长，但此算法对源节点没有残余依赖性。 f l u s h i n g 算法，引入了第三台机器文件服务器，首先传送除进程地址空间 之外的进程状态信息至目的节点，然后将进程地址空间所涉及的内存页传送至文 件服务器，之后恢复进程的执行，目的节点发生缺页时向文件服务器申请相关页。 f l u s h i n g 算法对源节点没有残余依赖性，存在一定的进程迁移时延。虽然此算法没 有残余依赖性，进程迁移时延也较短，但它的瓶颈在于如果文件服务器一旦失效， 那么正在迁移的进程都会受到影响，而且迁移进程的某些页会在系统中被传送两 次( 先传送至文件服务器，再由文件服务器传送至目的节点) ，增加了系统通信量。 算法t o t a l c o p y 、l a z y c o p y 、p i e c o p y 和f l u s h i n g 是目前经典的几种算法， 已经被应用于不同的场合。但它们还有一些缺陷：进程迁移时延太长，存在对于 别的节点的残余依赖性，偶尔还会发生网络拥塞等。下面说明c o n t i n u o u s 。c o p y 算 法。 2 2 2 c o n t i n u o u s c o p y 算法 c o n t i n u o u s c o p y 算法与上述的几种算法有相似之处，因为在表1 的3 个迁移 条件中，c o n t i n u o u s c o p y 算法的迁移条件并非与别的算法完全不同。与l a z y c o p y 算法的相似之处是，一旦决定要进行进程迁移时，便立即在源主机上挂起待迁移 进程，而且都只需传送进程执行时的最少必需状态，进程便可以开始在目的节点 继续执行。与p r e c o p y 算法相比，相同点在于，进程状态传输和进程执行是并行 的。不同之处在于，进程执行的位置不同，在p r e c o p y 算法中，进程是在源节点 上执行的，在c o n t i n u o u s 。c o p y 算法中，进程是在目的节点上执行的。“连续拷贝” c o n t i n u o u s c o p y 算法具体描述如下： 1 决定进程迁移； 2 在源节点上挂起要迁移的进程； 3 进程的部分状态信息( 进程执行时的最少必需状态1 传送到目的节点上； 4 根据第( 3 ) 步传送来的状态信息，在目的节点上重新创建进程； 5 在目的节点上恢复执行迁移后的进程； 5 电子科技大学硕士学位论文 6 继续传送剩余状态信息至目的节点，该传送过程与目的节点上的进程执行 并行； 7 在剩余状态信息的传送过程中，当目的节点请求尚未传送的页面时，优先 传送该页面。 c o n t i n u o u s c o p y 算法相对于以往的算法( 只与没有第三方机器参与的基本算法 进行比较1 来说，是有许多优越性的。可以从以下几个方面进行比较： 1 从“决定进程迁移”到“在目的节点上恢复执行”这之间的时延d e l a y l ； 2 进程迁移的总时延d e l a y 2 ； 3 残余依赖性r e s i d u a l d e p e n d e n c i e s ； 4 网络通信量n e t w o r k t r a f f i c 。 在对d e l a y l 的比较中，c o n t i n u o u s c o p y 算法的d e l a y l 与l a z y c o p y 算法的都 较小，其他算法的d e l a y l 较大。因为c o n t i n u o u s c o p y 算法与l a z y c o p y 算法都只 需要传输完最少必需状态，便可以在目的节点上恢复执行迁移后的进程。 d e l a y 2 指的是，“进程迁移后的完成时间”与“如果不进行进程迁移的完成时 间”相减得出的时间差。c o n t i n u o u s c o p y 算法的d e l a y 2 稍大于p r e c o p y 算法的 d e l a y 2 ，因为在p r e c o p y 算法的进程执行过程中不会发生“缺页”。但是，当产生 的“脏页”较多，也就是当需要二次传送的页面较多时，p r e c o p y 算法的d e l a y 2 便会急剧增大。而c o n t i n u o u s c o p y 算法的d e l a y 2 主要来自于，进程在目的节点上 执行后，当请求的页面还未按顺序传送至目的节点时，发生的缺页传送将会产生 时延。虽然在l a z y c o p y 算法中，不必传送所有的信息至目的节点，但在迁移后的 进程执行过程中发生的每次缺页传送，都会产生时延。而在c o n t i n u o u s c o p y 算法 中，一些页面在进程发生“缺页”之前，便会被传送至目的节点。所以 c o n t i n u o u s c o p y 算法的d e l a y 2 比t o t a l c o p y 算法和l a z y c o p y 算法的d e l a y 2 都小。 虽然l a z y c o p y 算法具有较小的d e l a y l 和d e l a y 2 ，但它在残余依赖性 r e s i d u a l d e p e n d e n c i e s 方面，却有着不容忽视的缺陷，而t o t a l c o p y 算法、p r e c o p y 算法和c o n t i n u o u s c o p y 算法都没有对源节点的残余依赖性。 c o n t i n u o u s c o p y 算法的网络通信量n e t w o r k t r a f f i c 与l a z y c o p y 算法的相比， 显然要大。它比t o t a l c o p y 算法的n e t w o r k - t r a f f i c 也要大。因为在t o t a l c o p y 算法 中，会一次性传送所有的进程状态至目的节点，而在c o n t i n u o u s c o p y 算法中，不 但要传送所有的进程状态至目的节点，当进程发生“缺页”时，还要向源节点发 送“请求页面”信息。但c o n t i n u o u s c o p y 算法的n e t w o r k t r a f f i c 比p r e - c o p y 算法 的要小，因为p r e c o p y 算法毫无疑问地会有“二次页面传送”的附加通信量。 6 第二章进程迁移算法分析 综合以上的比较，可以看出c o n t i n u o u s c o p y 算法的改进之处，它在每项比较 的指标中，都有着较好的表现。 2 3 本章小结 在本章中我们分析了现有的四种经典迁移算法，并基于三个迁移条件的组合 提出了一种“连续拷贝”迁移算法：“c o n t i n u o u s c o p y ”。在c o n t i n u o u s c o p y 算法 与以往的四种经典算法的比较中，都有着较好的表现。 本章解决了进程迁移所涉及的第一个问题：如何迁移，使得进程能够在新主 机上正确运行? 下一章将解决进程迁移所涉及的第二个问题。 7 电子科技大学硕士学位论文 第三章进程迁移机制分析 本章是对进程迁移机制的理论分析，第一节将阐述迁移机制的基础，即对负 载信息的管理方式；第二节阐述如何选择进程迁移的时机，如何选择源主机、选 择待迁移进程以及选择目标主机；第三节将对已有的进程迁移系统进行介绍和比 较；第四节是对本章的总结。 3 1 负载信息的管理 在回答“何时( 迁移时机) 由谁( 哪台主机作为源主机) 选择谁( 哪个进程) 向谁( 哪 台主机作为目的主机1 迁移? ”这个问题时，必须参考各台主机的负载信息来作出 回答。因此，我们首先应当完成这样一个任务：负载信息的管理。 负载信息管理应该考虑如下几个问题： 1 如何表示负载信息 2 如何收集负载信息； 3 如何发布负载信息。 3 1 1 如何表示负载信息 节点的负载往往是由下面一些参数中的一个或多个来确定的。这些可以描述 节点负载的参数称为“l 0 a di n d e x ”。它们是c p u 的利用率、c p u 运行队列中的任 务数、当前前台进程数、后台进程数、内存空间利用率、网络速度、磁盘利用率 和中断频率等。根据【4 】的研究，c p u 运行队列长度是最可靠的负载标志。 我们采用了c p u 运行队列的长度( 称为r u n q u e u e ) 来表示负载信息。另外，考 虑到不同c p u 物理速度的明显差异即在有相同长度的r u n q u e u e 时不同物理速 度的c p u 执行也有明显的快慢之分，因此结合了c p u 的物理速度啊尔为s p e e d l e v e l ) 作为另一个l o a di n i d e x 。用r u n q u e u e 与s p e e d l e v e l 的加权乘积作为l o a di n d i c e s ，来 表示负载信息。每台主机上都保持了一个链表，其中元素是分布式系统中各主机 的负载信息。 本机上的负载信息链表中各台主机的负载信息不是某个时刻的负载信息， 而是一段时间以内的负载信息，所以每台主机的负载信息值不会在短时间内出现 过大的变化。 8 第三章进程迁移机制分析 3 1 2 如何发布和收集负载信息 对负载信息的收集可以是周期性的，也可以是由事件驱动的。典型的周期性 收集信息是以每一秒或更长的间隔收集负载信息，而典型的驱动事件如进程的创 建、结束或迁移。当然，收集和发布的频率也依赖于这样的操作所花费的代价， 代价越低越频繁。 周期性地收集负载信息，本机的负载信息是以一秒( 此时间间隔可调) 为时间间 隔计算得到的，其它主机的负载信息是通过其它主机发来的广播消息进行收集的。 每次计算完本机的负载信息后，先判断是否需要发布，再通过广播把本机的负载 信息强制性的发布出去。 3 2 迁移机制分析 3 2 1 迁移时机的选择 可以是周期性的，也可以是事件驱动的进行本机负载情况的检查f 我们采用的 是有新任务加入时便进行检查) ，如果本机的负载高于某个阀值，再检查整个系统 的负载情况。检查自己的链表h o s t l o a d l i s t ，其中保存了所有主机的负载信息，根据 【2 9 的研究，只要系统中很繁忙主机不超过7 0 ，就可以准备进行进程迁移。如果 在系统中多数主机都很繁忙的情况下进行进程迁移，是非常得不偿失的。 3 2 2 源主机的选择 在源主机中的选择中，有以下几种策略： 1 发送者主动策略：由负载过重的节点发起，希望将自己的负载转移给别的 节点。本策略对中低负载的系统( 即高负载过重节点数目较少的系统) 有利。 2 接收者主动策略：由负载过轻的节点发起，主动要求承担负载过重的节点 的任务。本策略对高负载系统有利。 3 对称策略f 或称混合策略) ：是前两种策略的组合。 4 随机策略：在分布式系统中，随机地选择目的节点。这种看似简单的策略 其实也能带来明显的性能改善。 我们采用的是发送者主动策略，即当一台主机检查了自己的负载情况后，如 果发现自己的负载过重，此台主机便自动被当作进程迁移的源主机。 9 电子科技大学硕士学位论文 3 2 3 待迁移进程的选择 由于要支持进程的动态迁移，因此在就绪态、运行态、睡眠态的进程都是考 虑对象。 首先，我们倾向选择新创建尚未运行过的将要长时间运行的进程，因为它们 的迁移是静态迁移，代价最小。 其次，如果需要迁移动态进程，又倾向于迁移已运行时间短而剩余的执行时 问还很长的进程，因为对它们做动态迁移所需要移动的信息量较小。进程当前的 l i f e t i m e ( 生存时间) 可以用于负载平衡的目的。我们在判断进程是否值得被迁移之前 要判断进程应该有多“老”。对于那些生存期很短的进程而言，迁移的弊端超过了 利益。l e l a n d 和o t t 是最先在平衡策略中提出这一点的研究者i ”。 最后，访问设备和文件越少的进程，也就是说与系统的交互性越弱的进程越 便于迁移。本机l i n u x 运行必需的系统进程和本系统本身的服务进程当然是不能迁 移的，所以我们要设法区分本系统中允许的用户进程和原有的系统进程。 前面提到，每台主机保持有一个h o s t l o a d l i s t 链表，其中保存了整个系统中所 有主机的负载信息( 自上一次更新以来) ，于是每台主机在需要做进程迁移时，都能 结合各台主机的负载情况和进程迁移的代价来独立选择恰当的目标主机。 3 3 已有的进程迁移系统 实现了进程迁移的系统较多，由于我们的进程迁移是在内核级实现的动态进 程迁移，所以也只对相关的进程迁移系统进行介绍和比较。 1 l o c u s l o c u s 是个基于u n i x 的分布式操作系统，它在分布式的、多处理器的环境 中支持单处理器u n i x 的语义。l o c u s 为其分布式文件系统【8 】提供一个全网络的、 与位置无关的名字结构。l o c u s 使用修改后的f o r k 命令支持静态迁移，使用m i g r a t e 命令支持动态迁移【9 】o 它使用t o t a l c o p y 算法支持动态迁移。【1 0 】 2 d e m o s m p d e m o s m p 使用t o t a l c o p y 算法支持动态迁移。它是一个基于消息的分布式操 作系统。d e m o s m p 服务器维护资源状态。它在有缓存的单向通道称为“l i n k ” 上传递消息。d e m o s m p 在进程迁移过程中和迁移完成后通过l i n k 将消息转发 到新主机去；而当更新l i n k 时，转发机器会将新的目的主机的地址通知所有的消 1 0 第三章进程迁移机制分析 息发送机器。 3 m o s m o s 是一种在应用层上与u n i xv 7 兼容的分布式操作系统。m o s 试图为计算 机网络提供一个形如一个单独系统的外观，它支持动态进程迁移。对于一个1 0 0 k b 的进程，m o s 的报告说它可以在5 4 m s 内完成传送，但研究者没有给出整个迁移 时间的结果。m o s 运行由p d p 1 1 机器组成的1 0 m b p s 局域网中。 4 n e s t n e s t l 3 0 嚓统运行在由a t & t 3 b n e t ( 它是与1 0 m b p s 的以太网兼容的) 连接的一 组a t & t3 8 2 计算机上。它管理机器资源池。用r e x e c 命令提交工作交付远程执行； 当用户没有指定主机时，由n e s t 自动选择一台主机运行。支持静态进程迁移。n e s t 能保持迁移后的进程所面临的文件系统、父子进程关系、进程组、进程信号等环 境都和原来的一致。 5 p r o c e s ss u s p e n d r e s u m e c a g l e 3 2 1 在a t & tu n i x 系统v 操作系统上实现了将一个进程挂起保存为一个 文件，然后再从文件中恢复执行的功能。即使操作系统在进程挂起期间重新启动， 这个恢复执行的工作仍然可以完成。 6 a l o n s oa n dk y r i m i s a l o n s o 和k y r i m i s 修改了s u nu n i xv 3 3 以支持动态进程迁移【1 ”，但不支持如 下进程的迁移：通过管道或套接字与其他进程通信的进程、依赖于环境信息f 如p r o ) 的进程。他们的动态迁移采用了t o t a l c o p y 算法的变种。在迁移时，源节点上的断 点被保存为三个文件，第一个文件包含了代码段和数据段的卸出映像，第二个文 件包含了主机名、当前工作目录、文件信息等，第三个文件包含了堆栈、寄存器 和进程控制信息。这三个文件送往目的节点供恢复进程用。该系统运行在由1 0 m b p s 以太网连接的s u n 2 工作站局域网上。 7 m a c h m a c h 是一个基于消息的操作系统【1 2 1 。m i l o j i c i c 等人在m a c h 上实现了两个任 务迁移系统【1 3 】【1 4 1 。一个是简单迁移服务器( s m s ) ，另一个是最优迁移服务器( o m s ) 。 其进程迁移运行在以太网连接的3 3 m h zi n t e l8 0 4 8 6 处理器上，性能结果显示，迁 移典型大小的任务，s m s 花费5 0 0 m s 而o m s 花费2 5 0 m s 。 8 m o s m o s i x 是一个与a t & tu nixv 5 2 兼容的分布式操作系统。m o s i x 让应用 程序感觉到自己运行在一个单处理器系统上。它支持动态进程迁移【1 5 】。内存传送 电子科技大学硕士学位论文 时间是每k b 用时1 9 m s 。报告没有给出整个迁移时间。 9 m e s s m e s s 分布式操作系统将所有内存作为一个全局虚存对待。提供对所有资源( 包 括处理器) 的统一的和透明的访问。多个处理器和网络的存在对应用程序是不可见 的。进程迁移是作为统一的分布式虚存( d v m ) 的副产品产生的。 1 0 c h a r l o t t c h a r l o t t 是一个基于消息的、分布式的操作系统。使用t o t a l 。c o p y 的变种【1 6 1 【1 7 】 支持动态进程迁移。运行在令牌环网连接的v a x 1 1 7 5 0 机器上，约7 5 0 m s 内迁移 一个有6 个l i n k 的l o o k b 的进程。 1 1 a m o e b a a m o e b a 是一个基于对象的分布式操作系统，并且遵循c s 体系结构。在1 9 9 0 年发布的实现中它支持静态进程迁移，到1 9 9 4 年发布了对动态进程迁移的实现， 使用t o t a l c o p y 算法。在迁移过程中冻结迁移中的进程，以“进程正在迁移”的理 由拒绝发往该进程的消息。源迁移服务器发送一个包含了控制信息的消息并等待 该消息被接受。目的迁移服务器通过一系列r p c 请求获得迁移进程的内存页。最 终源迁移服务器提交一个e x e c u t i o nt o k e n ( 执行令牌) 让迁移进程恢复执行。由消息 恢复最终更新该进程的地址并且正确投递受到进程迁移影响的消息。 1 2 m d x 模块分布式计算系统( m d x ) 将迁移功能扩展到几乎所有系统对象( 包括进程) 上去【”】。m d x 使用透明名字定位，采用t o t a l ，c o p y 算法的变种支持动态进程迁移。 运行在1 0 m b p s 以太网连接的3 3 m h zi n t e l8 0 4 8 6p c a t 计算机上。在大约3 6 0 m s 内迁移一个1 0 0 k b 的进程。 1 3 v v 是一个基于消息的分布式操作系统1 1 9 】。运行在无盘工作站和服务器上。因 为在该环境中进程己经可以访问全网的文件，故进程迁移不引起对文件系统的影 响。v 进程只使用i p c 原语( 消息) 访问进程地址空间以外的环境。在迁移完成后， 更新通信连接服务器以重新建立与进程的通信连接。v 一开始是采用的t o t a l c o p y 算法支持动态进程迁移，然而t h e i m e r 在【2 0 】 2 1 】中提出了p r e c o p y 算法以克服消息 冻结问题。在进程迁移的研究发展过程中，v 可以被称为一个里程碑，因为它表 明：进程的地址空间无须在一个操作中完全传送。v 运行在1 0 m b p s 以太网连接的 s u n l 0 m h z6 8 0 1 0 局域网上，在约6 8 0 m s 的时间内完成对一个1 0 0 k b 进程的迁移。 1 4 s p r i t e 1 2 第三章进程迁移机制分析 s p r i t e 是一个有分布式文件系统的网络操作系统【2 2 】。其进程迁移【2 3 】【2 4 】【捌【2 6 】【2 7 在进程迁移系统中引入了s p r i t e 文件服务器，这也是一个里程碑式的进步。迁移时， 使用f l u s h i n g