（计算机软件与理论专业论文）基于linux的分布式系统中的进程迁移技术的设计与实现.pdf

论文摘要 f 分布式系统是充分利用现有计算机资源的一个很好的解决方案。而要 让分布式系统获得良好的负载平衡、高通信性能、高可用性等特性，进程 迁移功能是不可或缺的。 分布式操作系统涉及到多个方面的工作，如：进程管理和调度、进程 间通信、存储管理、并发控制、文件系统、事务处理、时钟同步、安全机 制等。本论文的研究范围是针对分布式进程管理和调度的目标之一：“负 载分布”。 负载分布( l o a dd i s t r i b u t i o n ) 的目标是有效地利用分布式系统中 的资源。这一目标可以表述为“负载平衡”( l o a db a l a n c i n g ) 它是 指在整个系统中尽量平均分配工作量，或者表述为“负载分担”( l o a d s h a r i n g ) 它是指仅仅尽力帮助那些已经超负荷工作的资源。前者的 要求比后者更严格。在本文中，我们讨论“负载平衡”。 负载平衡的实现方法就是“进程迁移”( p r o c e s sm i g r a t i o n ) 即 将进程及其所有的相关状态信息重新放置到另一个处理器上。事实上，通 过将进程从负载较重的系统移动到负载较轻的系统，负载就会得到平衡， 从而改善整体性能。 为了实现负载平衡，我们需要做三个方面的工作：收集和监控分布式 系统中各处理器的负载信息；掌握各进程信息，以决定何时需要迁移哪个 进程到什么位置：进行进程迁移。l 撇中讨论了在l i n u x 操作系统的基础上为分布式系统提供进程迁移功 能所需要的“负载信息管理”、“分布式调度”、“进程迁移机制”三个模块 的设计和实现。 其中，通过对现有的相关工作的分析和比较，提出了对动态进程迁移 算法的改进方案。通过对l i n u x 核心的修改，和g l o b a lo p e r a t i o n 模块 的增添，为用户提供了一个“透明”的具有进程迁移功能的分布式操作系 统接口。设计了一套迁移协议，使客户机与服务器能提供一致的进程观点 和透明的远程执行，并处理了网络失败和节点失败两类错误。 最终完成预定设计目标，使用并行编译任务验证其有效性并给出性能 比较数据。 关键词：分布杈进程迁移j 迁移协议? 动态进程迁移；算数 d i s t r i b u t e ds y s t e mh a sb e c o m eo n eo ft h eb e s tm e t h o d st ou t i l i z ee x i s t i n g i d l ec o m p u t i n gr e s o u r c e st oh a n d l ed i f f i c u l tt a s k s b u ti no r d e rt om a k ef u l l u s eo ft h er e s o u r c e si nd i s t r i b u t e ds y s t e m s ，晰n lg o o dl o a d - b a l a n c i n g ，h i g h c o m m u n i c a t i o n p e r f o r m a n c e a n d h i 出a v a i l a b i l i t y , p r o c e s sm i g r a t i o n i s r e q u i r e d d i s t r i b u t e d o p e r a t i n gs y s t e m si n v o l v em a n ya s p e c t si nc o m p u t e rs c i e n c e ， e g ：p r o c e s sm a n a g e m e n ta n ds c h e d u l i n g ，i n t e r - p r o c e s sc o m m u n i c a t i o n ， s t o r a g em a n a g e m e n t ，p a r a l l e lc o n t r o l ，f i l es y s t e m s ，t r a n s a c t i o n ，c l o c k s y n c h r o n i z a t i o n ，s e c u r i t ym e c h a n i s m ，e r e t h er e s e a r c ht o p i co f t h i st h e s i si s “l o a dd i s t r i b u t i o n ”ad e s t i n a t i o no fd i s t r i b u t e dp r o c e s sm a n a g e m e n ta n d s c h e d u l i n g t h eg o a lo f “l o a dd i s t r i b u t i o n i sh i 【g he f f i c i e n tu s a g eo fr e s o u r c e si n d i s t r i b u t e ds y s t e m s t h i sg o a lc a nb ed e s c r i b e da s “l o a db a l a n c i n g ”w h i c h m e a n st r y i n gb e s tt o a v e r a g et h ew o r k l o a dt o t h ew h o l es y s t e m ；o r “l o a d s h a r i n g ，w h i c hm e a n so n i yt r y i n gt oh e l pt h o s eo v e d o a d e dr e s o u r c e s t h e f o r m e ri sm u c hm o r ed i 伍c u l tt oa t t a i nt h a nt h el a t t e r w ed i s c u s s “l o a d b a l a n c i n g ”i no u rt h e s i s t h e i m p l e m e n t a t i o n m e t h o do f l o a d b a l a n c i n gi s “p r o c e s sm i g r a t i o n ，t h a t i s ，r e p l a c i n g a p r o c e s sa n da l l i t sr e l a t i v es t a t u si n f o r m a t i o no na n o t h e r p r o c e s s o r i nf a c t , i n t h ew a y o f m o v i n gp r o c e s s e sf r o m o v e r l o a d e ds y g e mt oa l o w e r - l o a d e ds y s t e m ，w o r k l o a dc a nb eb a l a n c e d ，a n dt h ew h o l er n f o r m a n c e o f t h ed i s t r i b u t e ds y s t e mi sa p p r o v e d i no r d e rt oi m p l e m e n tl o a db a l a n c i n g ，w en e e dd ow o r ko ft h r e ea s p e c t s ： g a t h e r i n ga n dm o n i t o r i n gl o a di n f o r m a t i o no fe a c hp r o c e s s o ri nd i s t r i b u t e d s y s t e m si no r d e r t od e c i d ew h e t h e ro rn o tm o v es o m el o a do ns o m e p r o c e s s o r ； m o n i t e r i n gt h ei n f o r m a t i o no fp r o c e s s e si no r d e rt oc h o o s es u i t a b l ec a n d i d a t e p r o c e s st om i g r a t ea n d w h e r et o ，a t 文血如l et i m e ；m i g r a t i n g p r o c e s s i l l t h i sp a p e rd i s c u s s e st h ed e s i g na n di m p l e m e n t a t i o no ft h r e em o d u l e sf o r t h ep r o c e s sm i g r a t i o ni nd i s t r i b u t e ds y s t e m sb a s e do r ll i n u x ，w h i c ha r e l o a d i n f o r m a t i o nm a n a g e m e n t ，“d i s t r i b u t e ds c h e d u l i n g a n d “p r o c e s sm i g r a t i o n m e c h a n i s m ” w e g i v ean e wa l g o r i t h mf o rd y n a m i cp r o c e s sm i g r a t i o na f t e rc o m p a r i n g t h ee x i s t i n ga l g o r i t h m s ；o f f e rt h es y s t e mu s e r sat r a n s p a r e n td i s t r i b u e t e d o s i n t e r f a c eb ym o d i l y i n gl i n u xk e r n e la n da d d i n gag l o b a lo p e r a t i o nm o d u l e ； d e s i g nam i g r a t ep r o t o c o ls ot h a tt h ec l i e n ta n ds e r v e rc a ng i v et h ec o n s i s t e n t v i e wo f p r o c e s sa n dt r a n s p a r e n tr e m o t ee x e c u t i o n ，a n dh a n d l el i n kf a i l u r ea n d n o d ef a i l u r e t h es u c c e s so ft h ei m p l e m e n t a t i o ni sp r o v e db yat e s t u s i n g p a r a l l e lc o m p i l a t i o nt a s k a n dt h es y s t e m s p e r f o r m a n c e i s c o m p a r e d 、丽t h a n o t h e rt w os i m i l a rs y s t e m s k e y w o r d s ： d i s t r i b u t e d ，p r o c e s sm i g r a t i o n ，m i g r a t ep r o t o c o l ，d y n a m i c p r o c e s s m i g r a t i o n ，a l g o r i t h m i v 附件三 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：盔渣 日期：红谚年f 1 月j - t e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：勿兹年月歹日 第一章概述 第一章概述 本章第一节中我们首先介绍分布式系统的概念。接着在第二节中，我 们讨论了分布式系统中进程迁移的概念和作用，以及进程迁移涉及的问 题。在第三节中我们给出了本论文的结构。 1 1 分布式系统的概念 在人类生产生活中一直存在着固有的分布式应用，例如，在我们的社 会中，人群在地理上是分布的，并且分布式地共享信息【l 】。而在过去的 半个世纪里，计算机技术的惊人进步，使计算机硬件的性能价格比提高了 1 0 1 1 倍，并且伴随以商速计算机网络的出现，这些技术的应用，使得将大 量c p u 组成的计算系统通过高速网络连接在一起不仅成为可能，而且变 得十分容易。相对于以前包括单个c p u 、存储器、外设和一些终端在内 的集中式系统( 又称单处理机系统) 而言，它们被称为分布式系统 ( d i s t r i b u t e ds y s t e m ) 。 关于分布式系统，有很多不同的定义，我们使用 1 】的描述：“一个分 布式系统是一个对用户看起来像普通系统，然而运行在一系列自治处理单 元上的系统，每个处理单元有各自的物理存储器空间并且信息传输延迟不 能忽略不计。在这些处理单元间有紧密的合作。系统必须支持任意数量的 进程和处理单元的动态扩展。” 尽管所有的分布式系统都包含多个处理单元，但仍有一些不同的硬件 组织方法，特别体现在这些处理单元的互连方式及通信方式上。然而，系 统呈现给用户的印象，以及用户如何看待系统“看起来像普通系统” 大都取决于系统的操作系统软件，而非硬件。 1 。2 什么是进程迁移 进程迁移即是为了将一个进程在两台机器之间进行移动的动作。 在分布式系统中，需要进程迁移的原因有很多，主要包括以下几点 2 】： 夺负载平衡：通过将进程从负载较重的系统移动到负载较轻的系统，从 而使负载得到平衡，改善整体性能。 3 】的实验表明取得显著的性能提 电子科技大学硕士学位论文 高是有可能的。 夺通信性能：交互密集的多个进程可以移动到同一节点上，以减少因为 它们之间的交互而带来的通信开销。同样，当一个进程在某些文件或 某组文件上执行数据分析，且文件的大小比进程要大很多时，将进程 移动到数据端也许是更有利的，而非相反。 夺可用性：需要长时间运行的进程，在得到错误的预先通知时，或者在 预定的停机时间之前，为了能够存活下来，可能需要移动到别的机器 中。 夺特殊功能的使用：进程的移动可以充分利用特定节点上独特的软硬件 功能。 尽管进程迁移能够使以上几点成为可能，迁移尚未被广泛应用。原因 之一是：向我们原有的、设计来单独运行的成为了工业标准的系统增加透 明的迁移，是很困难的，而直接从头设计具有迁移能力的新系统也是不现 实的。另外一个原因是：操作系统开发商并没有从商业上支持进程迁移。 然而，进程迁移仍然具有很大的研究价值。某些研究者得出的“进程 迁移不实用”的结论已经被证明太悲观了。 随着分布式系统，尤其是分布式操作系统的更加广泛地应用，人们对 高性能计算的研究重点已经从超级计算机转移到了工作站网络( n e t w o r k s o f w o r k s t a t i o n s ，简称n o w ) 和大规模分布式系统【4 】。我们可以预期进 程迁移技术将扮演一个更加重要的角色，并获得广泛的认可。 操作系统的研究者已经考虑支持进程迁移，如s o l a r i sm c ，但是到目 前为止，在商业系统中对进程迁移技术的使用还是很少见的。在w w w 上的移动a g e n t 的开发当中，对那些需要长时间运行的任务采用了断点恢 复系统，而这一技术原本是为进程迁移开发的。 1 3 进程迁移涉及的问题 在设计进程迁移功能时我们需要解决如下问题： _ 何时由谁( 哪台主机作为源主机) 选择谁( 哪个进程) 向谁( 哪 台主机作为目的主机) 迁移? 一如何迁移，使得进程能够在新主机上正确运行? ( 如果进程意识 第一章概述 不到这个迁移，我们称该迁移为“透明的”。) 当然，进程迁移问题的设计与实现一定要为其具体的目的服务。本文 中我们针对的是负载平衡目标。为了解决这两个问题，进程迁移应该包括 如下几个部分：负载信息管理、分布式调度、进程迁移机制。 1 4 本文结构 我们将在接下来的第二章中，描述本文讨论的问题范围，包括术语、 目标，以及什么是“负载信息管理”、“分布式调度”、“进程迁移机制”。 第三章将介绍和比较现有的各种研究成果，并着重分析其效率。第四章中 我们给出了本系统的“负载信息管理”和“分布式调度”部分的设计与实 现。然后在第五章中讨论我们的“进程迁移机制”部分的实现。第六章则 列出了现有的几种动态进程迁移机制算法，并指出其改进余地，提出我们 的改进算法。第七章是系统测试结果及总结。 电子科技大学硕士学位论文 第二章进程迁移问题的背景和理论 本章中我们通过对进程迁移的术语、体系结构、适用对象的介绍，给 出对进程迁移问题的背景介绍。然后在第四、五、六节中分别介绍负载信 息管理、分布式调度和进程迁移机制的理论知识。最后一节将指出进程迁 移的一些特性。 2 1 术语 进程这是操作系统中的一个关键概念 5 。它包括：数据、堆栈、 寄存器内容，以及与下层o s 直接相关的特定状态信息( 如：进程相关参 数，内存和文件管理) 。 进程迁移就是在源节点和目的节点之间移动一个进程。有些系统 又把这个“节点”称为“主机”，实则是个进程逻辑上运行的地方。我 们可以把进程迁移描述成下面这个图2 1 。被传送的进程状态包括进程的 地址空间、执行状态( 即寄存器内容) 、通信状态( 如打开的文件和消息 通道) 以及其他一些与o s 相关的信息。在迁移过程中，一个迁移中的进 程存在两个实体，一个是在源节点上的旧进程( s o u r c ei n s t a n c e ) ，一个 是目标节点上的新进程( d e s t i n a t i o ni n s t a n c e ) 。在迁移完成后，新进程 成为“m i g r a t e dp r o c e s s ”。以源节点的观点来看，则被迁移走的进程也 可以叫做“r e m o t ep r o c e s s ”，而从目的节点的观点来看，被迁移来的进 程又叫“f o r e i g np r o c e s s ”。 图2 1 进程迁移示意图 第二章进程迁移问题的背景和理论 进程迁移可以分为静态迁移和动态迁移两种。前者是指被迁移的程序 在源节点上还没有开始运行就被迁移，而后者是指进程在源机上运行的过 程中被迁移到目的节点。我们从中可以看出，进程迁移可以发生在任意时 刻。 进程迁移只是移动性的一种。一般而言，移动性( m o b i l i t y ) 可以划 分为硬件移动性和软件移动性，如图2 2 。硬件移动性处理移动计算，如 移动计算机和移动i p 。移动计算中的某些技术与软件移动性是相似的， 如安全、定位、命名、转发等。软件移动性又可以分为被动数据的移动性 与主动数据的移动性。被动数据移动指的是传统的在计算机之间传送数 据：自从计算机开始互相连接以来我们就一直在采用被动数据移动。而主 动数据移动可进一步划分为：移动代码( m o b i l ec o d e ) ，进程迁移 ( p r o c e s sm i g r a t i o n ) 和移动代理( m o b i l ea g e n t s ) 。移动代码，如j a v a a p p l e t 只在节点之间传送代码；进程迁移本文的讨论对象，处理代 码与数据的传送。最后，移动代理在大规模系统中( 如整个i n t e r n e t ) 传送代码、数据和权限( a u t h o r i t y ) 。 m “ 撕“s o f t w a r e p 2 2 体系结构 进程迁移的研究是随着多处理器间的分布式处理的出现而开始的。最 早在早期的多处理器系统中被提出 6 ，7 。但是现在的多处理器系统，特 别是对称多处理器系统，往往使用传统的调度方法，并没有采用进程迁移。 扩 d 第二章进程迁移问题的背景和理论 ；_ ；j ；= 目j i ；i i _ l _ ；= _ i i _ ；| _ i _ _ l ；一i _ - l _ _ _ ，；= = j _ 口_ _ e ； 进程迁移可以分为静态迁移和动态迁移两种。前者是指被迁移的程序 在源节点上还没有开始运行就被迁移，而后者是指进程在源机上运行的过 程中被迁移到目的节点。我们从中可以看出，进程迁移可以发生在任意时 刻。 进程迁移只是移动性的一种。一般而言，移动性( m o b i l i t y ) 可以划 分为硬件移动性和软件移动性，如图2 2 。硬件移动性处理移动计算，如 移动计算机和移动i p 。移动计算中的某些技术与软件移动性是相似的， 如安全、定位、命名、转发等。软件移动性又可以分为被动数据的移动性 与主动数据的移动性。被动数据移动指的是传统的在计算机之间传送数 据：自从计算机开始互相连接以来我们就一直在采用被动数据移动。而主 动数据移动可进一步划分为：移动代码( m o b i l ec o d e ) ，进程迁移 ( p r o c e s sm i g r a t i o n ) 和移动代理( m o b i l ea g e n t s ) 。移动代码，如j a v a a p p l e t 只在节点之间传送代码；进程迁移本文的讨论对象，处理代 码与数据的传送。最后，移动代理在大规模系统中( 如整个i n t e r n e t ) 传送代码、数据和权限( a u t h o r i t y ) 。 m “ 帅“s o f t w a r e d a t a m o b i l ec o d e ( t r a n s f e rc 。d e 。n l y ) ( t r a n s f e r d e + d a t 4 ) ( 订a i l s f e 。 c o d , * l - d a t a + a u t h o r i t y ) 图2 2m o b i l i t y 的分类及进程迁移在其中的位置 2 2 体系结构 进程迁移的研究是随着多处理器间的分布式处理的出现而开始的。最 早在早期的多处理器系统中被提出 6 ，7 。但是现在的多处理器系统，特 别是对称多处理器系统，往往使用传统的调度方法，并没有采用进程迁移。 电子科技大学硕士学位论文 用于负载平衡的进程迁移技术采用三种基本的系统模型： 自治系统： 此模型将分布式系统看成由多个独立计算机系统通过通信连接组成 的集合。每个自治系统都属于一个用户。只有当“主人”不使用该系统时， 系统才对外服务；一旦“主人”重新使用系统，则系统不再替其他机器工 作。进程通常情况下在本机上执行，有一个特殊的命令要求进程在远程机 器上运行。 c o n d o r 8 ，9 就是一个具有负载平衡能力的自治系统的原型。其缺省 的设置是当一台机器的c p u 负载低于0 3 个任务，并且连续1 5 分钟以上 没有键盘和鼠标动作时，该机被认为是空闲的。但是即使是在这样保守而 严格的条件下，研究报告仍然说有7 0 的机器会空闲。c o n d o r 为在远程执 行的进程维护个任务队列，使用u p d o w n 算法来公平地分配c p u 资源。 整体系统： 此模型将分布式系统看成一个整体。它接近于单处理器系统中的分时 共享模型，只是将其扩展到了多个c p u 上。模型将c p u 、存储、i o 设备 等看成一个资源集合，以尽量处理最多的任务。该模型中的硬件可以和自 治系统相同，也是一组工作站，但是其策略不同。此模型中并没有一个“主 人”的概念。 a m o e b a 5 ，1 0 提出了该模型的原型。a m o e b a 将机器作为一个处理器 池进行管理。由r u n s e r v e r 监督每个处理器的负载。当要执行一个新程序 时，r u n s e r v e r 就选择一个处理器来执行之。 大规模并行处理器系统： 在m a s s i v e l yp a r a l l e lp r o c e s s o r ( m p p ) 模型下，应用程序控制了很 多原本由操作系统控制的东西，特别是，应用程序自己控制了负载平衡， 这与分布式系统中一般的操作系统层次方式是不同的。 而现在，计算机局域网成为了进程迁移最常使用的结构，秉承了“自 治系统”的原理。m u t k a 和l i v n y 在 1 1 中指出，在任意时刻，局域网内 的许多自治工作站经常都是空闲的。 第二章进程迁移问题的背景和理论 2 3 适用对象 即，哪些类型的应用可以从进程迁移中获益： 可并行应用可以在某个节点开始，然后因为负载平衡等原因被迁 移到其他节点运行。有些进程是本质上就可并行化的，如m a k e 工具。例 如，s p r i t e 系统提供了一个能够在多个节点上进行分布式编译的m a k e 工 具p m a k e 。又s k o r d o s 表明象科学计算等应用也是可以在多各节点上并行 执行的。 运行时间长的应用有些应用需要运行多日，甚至数周，一旦被节 点故障停机或者预定的停机管理所中断将损失惨重。进程迁移可以使这些 应用在被中断之前透明地搬迁到其他节点上运行。这类工作的例子如 1 2 。 多用户工作例如，对于一个公共机房而言，随着用户的到来和离 开，每个节点的负载可能会发生很大的变化，动态进程迁移可以自动地在 所有节点上传播进程。 专用于迁移的应用这类应用在编码实现时就已经利用了进程迁 移的优越性。如果不同节点之间的负载变得不平衡，进程迁移可以自动地 将相关进程重新分布。这类应用是在1 9 9 5 年由s k o r d o s 和c a r d e l l i 中提 出的。 网络应用这类应用是当前进程迁移最有应用前景的一类。尽管 “移动性”( m o b i l i t y ) 与单纯的“进程迁移”并不完全相同，却使用了 很多相同的技术：定位策略、检查点、透明性等。 2 4 负载信息管理 本文中讨论的进程迁移，是用于负载平衡目的的。因此，我们应当完 成这样一个任务：通过收集负载信息，选择恰当的进程进行迁移，以及选 择恰当的目的节点。这个任务就称为“负载信息管理”，它收集的负载信 息将被送往“分布式调度”模块( 见2 5 节) 。 负载信息管理应该考虑如下几个问题： _ 如何表示负载信息 - 收集负载信息 电子科技大学硕士学位论文 _ 发布负载信息 下面我们依次回答这三个问题。 1 、如何表示负载信息 节点的负载往往是由下面一些参数中的一个或多个来确定的。这些可 以描述节点负载的参数称为“l o a di n d e x ”。它们是：c p u 的利用率、c p u 运行队列中的任务数、当前前台进程数、后台进程数、内存空间利用率、 网络速度、磁盘利用率和中断频率等。根据 1 3 的研究，c p u 运行队列长 度是最可靠的负载标志。 2 、收集负载信息 对负载信息的收集可以是周期性的，也可以是由事件驱动的。典型地 周期性收集信息是以每一秒或更长的间隔收集负载信息，而典型的驱动事 件如进程的创建、结束或迁移。一般而言，为了避免信息变化过快，信息 的发布频率低于收集的频率。当然，收集和发布的频度也依赖于这样的操 作所花费的代价，代价越低越频繁。 3 、发布负载信息 我们使用广播方式向组内其他节点发送自己的负载信息。 对负载信息管理的研究和观察有两个重要结论。 一是：很小景的信息就可以造成明显的性能提高( 这一点由e a g e r 等 人最早在 1 4 中指出) ； 二是：进程的当前的l i f e t i m e ( 生存时间) 可以用于负载平衡的目的。 我们在判断进程是否值得被迁移之前要判断进程应该有多“老”。对于那 些生存期很短的进程而言，迁移的弊端超过t n 益。l e l a n d 和0 t t 是最 先在平衡策略中提出这一点的研究者 3 。 2 5 分布式调度 “分布式调度”模块根据从“负载信息管理”模块送来的信息，做出 迁移决定。其主要任务是：决定“何时”将“哪个”进程迁向“哪里”。 首先由! 邀活：策略来回答这个“何时”的闯题。激活策略可以是周 期性的，也可以是事件驱动的。在激活后，模块检查负载，如果高于低 第二章进程迁移问题的背景和理论 于某个阀值，则要根据“选择”策略采取相应的动作。 “选搔二策略回答的是“哪个”的问题迁移哪个进程。模块检查 进程，然后根据特定的标准选择其中一些供迁移。 “定位”策略回答“哪里”的问题，它根据系统可用性信息选择一个 远程节点。 以下是分布式调度策略的分类： 发送者主动策略：由负载过重的节点发起，希望将自己的负载转移给 别的节点。本策略对中低负载的系统( 即高负载过重节点数目较少的系 统) 有利。 接收者主动策略：由负载过轻的节点发起，主动要求承担负载过重的 节点的任务。本策略对高负载系统有利。 对称策略( 或称混合策略) ：是前两种策略的组合。 随机策略：在分布式系统中，随机地选择目的节点。这种看似简单的 策略其实也能带来明显的性能改善 1 4 1 5 。 下面是“分布式调度”模块的设计所应考虑的问题： 1 、适应性。在调度问题上我们应该考虑适应性。在当前的主机和网络负 载的基础上，负载参数的相对重要性可能发生变化。策略应当能适应这样 的变化。进程迁移本质上是适应性的，因为迁移可以在任何时候发生，因 此可以适应突发的负载变化。 2 、稳定性。稳定性定义为能够检测到“根据用户的目标而言，进一步的 动作( 如负载调度等) 不会改善系统状态”的能力。在分布式系统中，一 定程度的不稳定性是不可避免的，因为并不可能立即传送所有的状态变 化。然而，过大程度的不稳定是可以避免的。有时候一例如，在特别高 的负载情况下最好的动作就是“什么都不做”，比如根本不做负载平 衡的工作。如果进程在节点间频繁来回地迁移( 这就是特别商负载下所可 能遇到的情况) ，则负载迁移将损害系统的稳定性。 3 、近似调度。这是必须的，因为理想的解决方案是很难得到的。我们只 能使用近似方案，只要求能够做出较为正确的迁移判断。 4 、结合分布式调度和集中调度。可以在一组节点内部支持分布式调度， 而在各组之间采用集中调度。 电子科技大学硕士学位论文 然而，归根结底，“分布式调度”模块对进程调度最大的影响就在于： 前者做出的判断是否使得迁移是有成效的。 无论如何，h a r c h o l b a l t e r 和d o w n e y 在 1 6 中给出的研究结果是鼓 舞人心的，他们的研究表明，即使是在迁移代价很高的情况下，使用进程 迁移也比使用远程执行在平均延迟问题上改善了3 5 5 0 。( 远程执行：是 一种被经常使用的不同于进程迁移的方法，它简单地在远程节点上唤醒某 些代码，通常比进程迁移要快，因为无须传送进程状态，但是它只允许在 进程创建时进行而不象进程迁移一样能在任何时候进行。) 2 6 进程迁移机制 “进程迁移机制”是进程迁移中的核心部分，在“分布式调度”模块 接收了来自“负载信息管理”模块的信息并做出了何时将哪个进程迁往哪 里的决定之后，具体的工作就由“进程迁移机制”模块来完成了。我们将 在本节中给出整个迁移机制的一般流程，和迁移所涉及的信息。 2 6 1 流程描述 在本节中，我们将描述进程迁移的一般流程： 1 源节点向目的节点发出“进程迁移请求”消息。如果目的节点拒绝， 则本次迁移尝试失败，源节点将考虑向其他节点迁移进程；否则，目 的节点批准此请求。继续下面的步骤。 2 一个进程在源节点上被挂起。其执行被挂起，该进程被宣布进入“迁 移中”状态，然后暂时地将其与其他进程的通信冻结。 3 进程状态的传送。包括：进程控制信息、处理器状态、地址空间( 代 码段、数据段、堆栈) 、打开的文件等。如果是在异构系统中，这一步 骤还应包括数据表示的翻译过程。 4 创建目标节点上的进程实体。获得传送过来的状态信息，直到得到了 足够的状态信息后才激活该进程。此后，作为一个普通的进程运行。 5 恢复执行新进程。进程迁移完成后，由新节点恢复其执行。 2 6 2 迁移信息 为了实现两台主机之间的进程迁移，两者之间需要定义一个进程迁移 第二章进程迁移问题的背景和理论 协议。该协议规定了要迁移的信息的顺序。在协议设计时，要注意由于目 的节点可能拒绝迁移请求，所以在目的节点上的迁移后的进程被恢复执行 之前，源节点上的进程信息都不可丢弃。以下是要迁移的信息： l 、进程控制信息：包括了0 s 管理该进程的所有信息，如：优先级、p i d 、 p p i d 。最重要的一点是，一旦控胄0 信息被原节点冻结后，该进程就应 被挂起。 2 、执行状态：处理器状态，包括通用寄存器内容、浮点寄存器内容、堆 栈指针、程序计数器( p c ) 以及状态寄存器内容。执行状态与机器是 密切相关的。 3 、地址空间：包括属于该进程的所有虚存空间，这是进程状态信息中最 大的部分。即使对于小进程而言，要传送整个地址空间都是极其耗时 的。 4 、消息：进程的消息状态包括被缓存的消息和关于通信连接的控制信息。 在进程迁移期间的通信连接的管理和进程迁移完成后通信连接的重建 是迁移消息状态的主要问题。 5 、文件：进程的文件状态包括进程的文件描述符和缓存的文件块。所有 被打开的文件在迁移时会被关闭，但迁移后应该在目的节点上打开， 这里就涉及到临时文件在关闭时会被删除的问题；如果把整个缓存文 件发送到目的节点或者文件服务器，效率是很低的，所以应该考虑仅 仅刷新脏块( f l u s h ) 。 2 7 进程迁移的特性 在本节中，我们将讨论进程迁移问题中的一些关键问题，如复杂性、 性能、透明性、容错、可扩展性。这些特性对进程迂移的效果和应用有重 大的影响。另外，要说明的是，虽然异构性也是进程迁移的一个重要特性， 但是本文没有讨论这一点。 1 、复杂性和操作系统支持 进程迁移要广泛应用，其最大的障碍在于实现的复杂性和对操作系统 的依赖。特别是要完全透明地迁移，实现更加困难。迁移可以根据它应用 的级别来分类。它可以是操作系统内核的部分，可以在用户空间，可以 电子科技大学硕士学位论文 是系统环境的的一部分，或者作为应用程序的一部分。如图2 3 所示。在 不同级别实现的迁移有不同的性能、复杂性、透明性和可重用性。 应用程序特有迁移 ( a p p l i c a t i o n - s p e c i f i c m i g r a t i o n ) 用户应用程序 ( e n du s e ra p p l i c a t i o n s l 用户级进程迁移 ( u s e r - l e v e lp r o c e s s m i g r a t i o n ) 用户空间 ( u s e rs p a c e ) 传统的进程迁移 ( t r a d i t i o n a lp r o c e s s m i g r a t i o n ) 核心空间 ( k e r n e la p p l i c a t i o n s ) 图2 3 迁移的不同实现级别 用户级迁移通常实现较简单，却以性能和透明性的降低为代价 1 7 。 作为应用程序的一部分实现的进程迁移重用性很差 1 2 ，1 8 ，要求对应用 程序十分熟悉并且为每个应用程序分别实现迁移功能。而低层的迁移实现 虽然较难实现，但是在性能、透明性和重用性上要更好些。 2 、性能 迁移的性能取决于由迁移所引入的初始化和运行的代价。前者是由状 态传送引起的( t r a n s f e re a g e r l y ) 。因为状态并不一定需要在迁移时完 成，而可以在后来需要的时候传送( t r a n s f e rl a z i l y 或者 c o p y o n d e m a n d ) ，故产生了运行时的代价。这两者都依赖于应用程序的 特点，和e a g e r l y l a z i l y 地传送的状态信息的比例。( 本文将在第六章具 体分析不同的迁移算法，并着重分析其性能。) 3 、透明性 透明性要求无论是被迁移的任务( 进程) 还是系统中的其他任务( 进 程) 除了其性能会受到影响之外，都不能意识到发生了迁移。与被迁移的 第二章进程迁移问题的背景和理论 进程进行的通信在迁移过程中应当被推迟，但是消息不应该丢失。在迁移 完成后，进程应当继续通过先前被挂起的己打开的i o 通道通信，例如， 向原先的控制台输出，和从同样的文件读入数据。 1 2 ，1 9 。 4 、容错 容错是进程迁移的优点当中经常被提到的一个方面。然而，容错也要 依靠具体的实现来达到。在进程迁移的实现中，“失败”扮演着重要的角 色。失败可能发生在源节点上，或目的节点上，或者通信介质上。不同的 迁移实现对不同类型的失败有不同的敏感程度。容错能力可以用多种方法 提高。例如，通过将进程状态保留在源节点上，直到目标节点收到全部信 息且进程已恢复运行后通知了源节点再删除，可以应付在迁移过程当中的 失败。 5 、可扩展性 这是与进程迁移的下层环境的扩展性相关的。它可以用如下标准衡 量：系统中的节点数目、一个进程生存期中可以迁往的节点数目、进程的 类型和复杂程度打开的通道或文件的个数以及虚存空间大小。 迁移算法应避免对要传送的信息的数目的线性依赖。例如，e a g e r ( a 1 1 ) 算法的代价与进程地址空间的大小是成线性增长关系的，于是对于 地址空间而言，其扩展性较差。 2 8 本章小结 本章择要介绍了进程迁移问题的背景、理论知识和特点，并分别介绍 了其三个组成部分：负载信息管理、分布式调度和进程迁移机制。在下一 章中，我们将介绍并比较前人在这方面的工作。 电子科技大学硕士学位论文 第三章相关工作介绍及比较 在本章中，我们将列出一些现有的著名的分布式系统所采用的进程迁 移技术，并进行比较。 3 1 用户级进程迁移 l 、r s h u n ix 的r s h 命令支持在远程机器上执行一部分s h e l l 命令，包括在 远程机器上执行一个应用程序。但是r s h 只支持静态进程迁移。其主要缺 陷在于r s h 不保存进程环境如：当前工作目录等。 2 、z h o ua n df e r r a r i z h o u 和f e r r a r i 为运行在d e cv a x 机器上的u n i x4 3b s d 实现静态 进程迁移。他们修改了cs h e l l 以远程执行特定类型的用户命令。由一个 负载信息管理器( l i m ) 一直监视系统负载，执行任务分派。由一个负载 平衡管理器( l b m ) 在每台机器上运行以支持远程执行。 3 、p r o c e s ss e r v e r 进程服务器运行在c e d a r 系统上 2 0 ，支持那些只使用字符串、流和 文件来进行通信的进程的静态迁移。 4 、b u s l e r c a r n e g i e m e l l o n 大学的b u t l e r 系统 2 1 是运行在a n d r e w 工作站上 的一组程序。该系统管理空闲工作站并自动地为一个任务请求选择一个恰 当的工作站来运行。b u t l e r 只支持静态迁移，它将环境信息传到目的主 机。遵从“自治系统”( 见第2 2 节) 。每当某个主机的“主人”回到主机 上工作时，b u t l e r 会发出一个2 分钟的警告，然后杀掉剩余的外来进程。 这意味着在这两分钟之内，外来的进程将被再度迁移。 5 、r e m o t ee x e c u t i o nm o n i t o r 远程执行监督( r e m ) 2 2 是在b e r k e l e yu n i x 上开发的，它允许应 用程序管理远程进程即应用程序可以创建和删除远程进程。r e m 在多 第三章相关工作介绍及比较 台机器上保持多个复本的进程，从而支持多种级别的容错。r e m 还增加了 个支持位置独立性的消息协议。 c o n d o r 在u n i x 工作站网络上支持进程迁移 1 7 9 ，它能将进程分 配到空闲的工作站上。c o n d o r 是“自治系统”的典范，其判断工作站空 闲的标准是非常严格的：u n i x 主机负载低于0 3 ，键盘和鼠标连续1 5 分 钟以上没有活动。当主机的“主人”回来时，外来的进程被迁移走。c o n d o r 使用u p d o w n 算法公平地调度机器。c o n d o r 将进程的断点状态保存在一 个文件中，然后把文件传送给目的主机，再从文件中恢复断点状态。 7 、m a n d e l b e r ga n ds u n d e r a m u a n d e l b e r g 和s u n d e r a m 在u n i x 上实现了一个未命名的进程迁移系 统。它们所迁移的进程不能做以下任何操作：通过管道或套接字通信、访 问非n f s 的文件、s p a w n 进程。在新主机上，一个程序伪装成终端界面与 旧主机上的一个程序交换数据，而旧程序的这个程序再与真实的终端界面 交换数