（计算机应用技术专业论文）进程迁移机制关键技术研究与实现.pdf

华中科技大学硕士学位论文 摘要 以工作站机群为代表的并行计算环境是当前并行分布式计算的研究热 、 点之一。各节点负载的平衡影响整个系统的性能，进程迁移是动态负载平 衡的有效手段，因而研究进程迁移具有十分重要的理论和实际意义。 目前大多数进程迁移机制采用检查点重起算法，进程冻结时间长、迁 移过程中消息会发生丢失。迁移机制中提取进程状态，通过提供用户空间 专用函数库或者修改内核实现，前者虽然简单但不能完整地获取进程状态： 后者实现复杂且无内核源代码不可行o y - ， 在对各种传统的u n i x l i n u x 进程迁移算法进行分析研究的基础上，对 进程迁移机制提出三个方面的改进。第一，在转移进程状态数据和恢复进程 执行方面，不做检查点直接转移数据至目标节点，避免了数据写盘等费时 操作。目标节点接收到状态和控制等必要信息后即可恢复进程的执行，剩 下的进程内存页面在执行的过程中继续传送，可显著缩短传统检查点重起 算法中的进程冻结时间。第二，在提取进程状态数据方面，采用内核模块 机制算法。与通过添加信号处理函数或修改内核的传统算法相比，实现相 对简单而且能比较完整地提取进程状态数据：同时不需要修改程序和内核 代码，版本维护容易。第三，在恢复进程网络连接等消息方面，采用缓存 进程消息，迁移完成后再恢复进程的网络连接。传统算法通常是断开网络 连接，不能正确迁移网络连接。 根据改进的迁移和提取进程状态算法，在l i f l u x 工作站机群环境下实现 一个进程迁移系统f p m s 。实验结果表明，采用上述改进可以缩短进程冻结 时间，正确恢复进程网络连接等消息。 关键词：进程迁移；内核模块：进程冻结时间；检查点 华中科技大学硕士学位论文 a b s t r a c t p a r a l l e lc o m p u t i n ge n v i r o n m e n te x e m p l i f i e db yc l u s t e ro fw o r k s t a t i o n si s o n eo ft h eh o ts p o t si ns t u d yo fd i s t r i b u t e ds y s t e m s t h el o a db a l a n c i n go f c l u s t e rn o d e sd e t e r m i n e st h ew h o l es y s t e mp e r f o r m a n c e p r o c e s sm i g r a t i o ni s v e r yi m p o r t a n ti nt h e o r ya n dp r a c t i c ea so n eo ft h ed y n a m i cl o a db a l a n c i n g m e a n s m o s to fc u r r e n tp r o c e s sm i g r a t i o nu t i l i t y i m p l e m e n t a t i o n sa r eb a s e do n c h e c k p o i n ta n dr e s t a r tm e t h o d t h e ys u f f e ri nl o n gf r o z e nt i m ea n dl o s eo f p r o c e s sm e s s a g e t h e yg e tp r o c e s ss t a t u s d a t ab yo f f e r i n g s p e c i a l f u n c t i o n l i b r a r yi nu s e rs p a c eo rm o d i f y i n gk e r n e ls o u r c ec o d e t h ef o r m e ri se a s i e rb u t c a n tg e tw h o l ep r o c e s ss t a t u sw h i l et h el a t t e ri sd i f f i c u l ta n di n f e a s i b l ew h e n s o u r c ec o d eu n a v a i l a b l e w ei m p r o v ep r o c e s sm i g r a t i o nu t i l i t yi nt h r e ea s p e c t sb a s e do ns t u d yo f t r a d i t i o n a lu n i x l i n u xp r o c e s sm i g r a t i o na l g o r i t h m f i r s t ，w er e d u c ew r i t i n g d i s k c o s t l yo p e r a t i o n sb yt r a n s f e r r i n gp r o c e s s s t a t u sd a t a d i r e c t l y t o d e s t i n a t i o nh o s ta ss o o na sa v a i l a b l e ，s h o r t e nf r o z e nt i m eb yr e s u m i n gp r o c e s s o n l ya f t e raf e wp r o c e s ss t a t u sp a g e si sa v a i l a b l ew h i l et h er e m a i n e dp a g e s b e i n gt r a n s f e r r e dt h e r e a f t e r s e c o n d ，w eu s ek e r n e lm o d u l et e c h n o l o g yt og e t p r o c e s ss t a t u s i ti se a s i e rt oi m p l e m e n ta n dm a i n t a i nc o m p a r e dt ot r a d i t i o n a l s p e c i a l l i b r a r y a n dk e r n e lm o d i f i c a t i o n a l g o r i t h m t h i r d ，w e b u f f e rt h e p r o c e s sm e s s a g e s u c ha sn e t w o r kl i n k sa n dr e s u m et h e mw i t h o u t l o s i n g m e s s a g ew h i l et h et r a d i t i o n a la l g o r i t h m so f t e ns t o pa n dd i s c a r dt h e m w ei m p l e m e n ta p r o c e s sm i g r a t i o nu t i l i t ys y s t e mn a m e df p m su n d e r l i n u xc l u s t e r a c c o r d i n gt o t h e i m p r o v e da l g o r i t h mm e n t i o n e da b o v e t h e r e s u l to f e x p e r i m e n t a t i o ns h o w s t h a ti tc a ns h o r t e nt h ef r o z e nt i m ea n dr e s u m e m e s s a g ec o r r e c t l y k e yw o r d s ：p r o c e s sm i g r a t i o n ；k e r n e lm o d u l e ；p r o c e s sf r o z e nt i m e ； c h e c k p o i n t i i 华中科技大学硕士学位论文 ：自= ；# = = = = = = = _ = = = = ；_ = 目= _ = _ = 自= # 自= = 1 1 课题背景 1 绪论 在科学研究领域和航空航天、地质勘探、天气预报等生产领域，人类 对计算能力的需求是永无止境的。目前集群以其高性能、可扩展性、高吞 吐量、易用性等特点逐渐成为高性能计算研究的热点，随着网络设备的快 速发展，工作站集群以其高性价比已经成为流行平台。 集群系统是一种并行分布式处理系统，由很多连接在一起的独立计算 机组成，像一个单独集成的计算资源一样协同工作【2 1 。集群系统的主要目 标是通过网络互联实现全系统范围内的资源共享，同时通过高效的资源管 理和任务调度技术实现资源的有效共享，从而提高资源利用率，获得高性 能。为了使由独立机器组成的集群系统工作起来，且形成对用户透明的单 一系统，必须为其提供调度、负载平衡和共享服务。集群计算系统的核心 问题是资源的共享及有效利用，只有平衡负载才能达到最大的资源使用 率。一般通过事先的任务放置静态地平衡各个节点的负载，计算过程中各 个节点的负载通常会动态发生改变，根据系统的负载情况，把计算任务从 负载较重的节点转移到另一负载较轻的节点继续运行，可以有效地实现负 载的动态平衡，计算任务可以并行执行而不影响其它用户从而更快地完 成。随着计算节点的增多，单个节点出错的可能性也会增大。当某节点出 现故障时，为了保存计算过程中的计算结果，可把故障节点上的任务转移 到其它节点上继续运行，这样可以提高系统的可靠性和可用性，在某些关 键性应用中，这一点尤为重要。另外。进程迁移还可以用于系统管理目的 迁移特定进程至特定节点，为达到使用特定资源目的迁移相关进程等其它 用途【3 1 。 概括起来，进程迁移主要有如下目的： 1 负载平衡共享：把重负载节点的任务转移到轻负载或空闲节点，可 以获得更好的总体吞吐量。 华中科技大学硕士学位论文 2 资源匹配：某些进程是有特定资源需求的，如需要一些适合于更快 或更精确计算特定问题的c p u 、需要频繁存取的数据源，也可能是一些特 定i 0 设备如扫描仪、取样器。把这些进程迁移到最能提供需求资源的处 理节点上，而不是频繁地把数据通过网络传输至某个节点，可以减少网络 通信开销。 3 减少进程间通信：在分布式计算中，某些紧耦合的进程之间通信频 繁，通过迁移使这些进程在同一台机器上运行，可以减少网络进程通信i s 】。 4 容错：进程迁移和动态配置可以提高系统的容错性能。某些情况下， 可以预先获知即将到来的故障，停止特定进程并迁移到别的节点可以恢复 进程执行，不受故障影响。 此外，在移动计算( m o b i l ec o p u t i n g ) 和广域计算( w i d ea r e a c o m p u t i n g ) 中也可应用进程迁移1 6 】。在移动计算中，可能需要把一个进程 迁入或迁出支持移动单元的基站，这样进程能够根据网络状况、移动的相 对处理能力和基站情况优化它的性能。同样。当一个移动单元迁移了，运 行在一个基站的与移动单元相关进程可以迁移到新的基站。在广域计算 中，进程可以迁移到它们使用的数据存放位置来提高性能，因为随着网络 带宽的提高，网络延迟并没有很显著地减少。由工作站、集群和并行机组 成的分布式网络可以称为广域多机系统( 霄i d e - a r e am u l t i c o m p u t e r ) ，也 可以称为在广域网内计算机中进行并行计算的广域计算结构 7 1 。广域网和 局域网中大部分工作站都没有完全利用，通过资源的共享可以利用广域网 来解决复杂的问题。组成网络的各种计算资源虽然通过网络设备物理上连 接起来了，但逻辑上仍然是孤立的，必须通过中间件层来完成广域计算资 源的有效共享。资源分配、任务迁移等技术直接影响系统性能。 进程迁移是指能够把一个正在运行进程的状态从一个节点转移到另一 个节点并且恢复进程的执行1 8 。早在2 0 世纪8 0 年代，人们就开始了进程 迁移的研究。目前已经有多种实现进程迁移的系统。按系统的体系结构可 分为同构进程迁移和异构进程迁移。同构的进程迁移指的是源和目标机器 的体系结构相同，这类系统有代表性的有：vc h a r l l o t e ，d e m o s m p s p r i t e ， 2 华中科技大学硕士学位论文 c o n d o t ，a c c e n t 。而异构的进程迁移则是不同体系结构的机器之间进行进 程迁移，异构的系统有：t u i ，e m e r a l d ，i d m f ，m s r 9 1 等。按照进程迁移系 统实现的方式可分为操作系统内核层次实现和用户层次实现。 尽管进程迁移已经在实验环境中成功实现了，但是还没有广泛地在商 用化产品中采用。其中一个原因是设计和实现转移进程执行状态、内存状 态和进程的通信状态机制时，如挑选错误的进程进行迁移，进程迁移所获 得的性能提高可能还不足以弥补进行迁移的开销，甚至会降低整个系统的 性能【l0 1 。同时，进程迁移会增大节点间网络通信。若要做到透明性迁移， 也会增加系统复杂性。另外，有的进程如机器的系统进程、文本编辑器等 非常依赖于用户终端和系统，是不能迁移的。有相关研究表明，只有c p u 强耦合( c p u b o u n d ) 的计算任务在需要指数分布的执行时间的情况下， 进程迁移才可以明显地提高动态负载平衡i ，然而进程迁移仍然是非常有 吸引力的一个研究方向。 根据迁移对象粒度的不同，进程迁移技术衍生了线程迁移、对象迁移、 任务迁移等其他相关技术。近几年来，轻量级线程的编程和使用在分布式 计算环境下越来越流行1 1 2 。在分布式计算环境下，运行时动态确定每个节 点上的工作负载，通过线程的迁移可以实现负载动态平衡。在综合考虑线 程通信开销和性能的基础上，是可以设计出更好粒度的线程迁移系统 f l ”。在采用面向对象技术设计的操作系统中，对象迁移通常作为操作系 统的核心机制提供，这些系统中持久性对象根据对象的使用和位置的统计 数据可以在机器间进行转移。在执行期间进行对象迁移可以等同于对象物 理位置的改变，但物理位置的改变只是迁移时需要考虑的改变属性之一， 其他改变的属性还包括对象生命周期、对象状态表示和错误处理语义等。 使用面向对象技术进行封装提供很好的用户接口，系统可以简化传输和转 换数据、执行状态等过程。对象迁移可以在异构环境下实现，需要转移描 述对象类型和特性的系统状态、由对象状态变量集描述的对象状态【1 5 】。在 微内该操作系统如m a c h 中，进程和任务是有区别的。o s f a d 服务器中一 个进程由m a c h 任务状态( 内存、权能、线程等) 和u n i x 相关状态( 打开 华中科技大学硕士学位论文 文件描述符、信号掩码等) 组成。d e j a ns 等在m a c h 上实现了一个进程 迁移和任务迁移的系统 】，该系统中进程迁移由m a c h 任务状态迁移完成， 支持透明进程迁移。 进程迁移的研究范围一般可以分为迁移策略和迁移机制两方面的研 究。目前已经实现的进程迁移系统在迁移机制上，大部分是遵循先停止源 节点上正在运行的待迁移进程、对进程全部状态做检查点并写入磁盘、把 检查点文件数据转移到目标节点、在目标节点恢复迁移进程执行等这些步 骤【1 7 】。譬如，c o n d o r 系统周期性做检查点并写入磁盘，在需要进程迁移 时再转移检查点文件。s n o w 系统中采用内存空间表示m s r 来保存内存内容， 然后迁移至异构节点恢复执行【1 8 】。这类算法属于全拷贝类型。在保存和转 移检查点文件直到恢复进程之前，目标节点上的新进程是不能执行的。 t h e i m e t 在v 系统中提出了预拷贝算法，在拷贝进程地址空间的同时进行 进程执行和消息接收，然后继续拷贝修改了的页面。但该算法增大了整个 工作量挎】。z a y a s 2 0 1 提出了请求页迁移算法，首先挂起进程只传送进程的 状态后就恢复进程的执行，地址空间的其它内容在新进程执行过程中出现 页面错误时再通过请求页面传输所需的页面内容。但该算法每页的传输代 价很大。 综合上述情况，我们考虑一种改进的不保存进程状态的进程迁移机制。 首先收集恢复进程必要的数据，把这些必要信息转移到目标机器后即开始 执行新的进程，并在执行的过程当中，陆续转移进程其他的信息。这样就 可以较快地实现进程迁移。 1 2 国内外研究现状 随着并行处理和分布式处理研究的日益广泛，两种新的计算领域移动 计算广域计算又促进了进程迁移的研究。进程迁移的研究可以分为两个范 围的研究，个是迁移的策略，另外一个是迁移的机制。迁移策略是研究 一个系统什么时候迁移哪个进程到什么地方去，而迁移机制是指如何实现 的问题。 华中科技大学硕士学位论文 大部分进程迁移策略是为了实现负载平衡目的，如h e l e n 等提出的自 适应负载调度策略【2 1 1 。在制定进程迁移策略时一个最根本的问题是如何评 估负载22 1 。有许多计算负载的方法，包括运行队列里任务的数目、平均负 载、c p u 利用率、i o 利用率、c p u 和内存的空闲时间等或者这些因素的 组合 2 3 l 。当迁移是着眼于性能原因时，通常有两类解决方法：负载共享和 负载平衡。负载共享解决本地问题，本地进程在可能的情况下迁移到另外 一台空闲机器上去，这种方法只提高本地性能。而负载平衡是试图在网络 内的各个节点之间平均的共享整个系统负载。这是全局的解决方案，着眼 于提高整个网络的性能。通常采用何种迁移策略是在系统初始化或者创建 新进程或者进程的整个生存期间等过程中决定的。负载共享有两种通用的 算法：投标算法和招募算法。这两种算法涉及到由谁发起进程迁移，通常 有发送节点发起( s e n d e r i n i t i a t e d ) 和接收节点发起( r e c e i v e r i n i t i a t e d ) 两 种【2 ”。投标算法中，一个重负载的处理器创建新进程时向其它节点发送请 求，其它节点回复包含它们处理新进程的能力的“标”，重负载的处理器 从返回的标中选择一个最好的然后发送新进程至该位置。投标算法简单只 在处理器过载时使用，不幸的是，由过载处理器完成该算法的大部分工作。 招募算法中，一个轻负载处理器发送消息给其它节点表明它还能处理更多 的任务，这样重负载的处理器可以给轻负载的处理器发送新进程。该算法 轻负载处理器傲了大部分工作。但在整个系统负载很轻的情况下可能产生 不必要的通信。两种算法都可能由于消息过时，其它节点给轻负载节点发 送过多的进程。 进程迁移机制是指如何进行迁移，比如怎样提取封装进程状态，如何 转移这些数据以及如何恢复进程的执行。目前国内外有很多进程迁移机制 的实现。进程迁移可以作为操作系统的一部分，或者用户空间、系统环境 的一部分或者应用程序的一部分。根据实现所在的级别，进程迁移可以 分为如下三类： 1 用户级迁移：不需要修改操作系统内核，实现较为简单，软件开发 和维护也相对容易，厘由于不能直接存取内核状态，所以不能迁移 华中科技大学硕士学位论文 所有的进程；内核空间和用户空间的边界使得调用内核提供服务开 销巨大。用户级实现效率远远低于内核级别实现。c o n d o r 在用户级 别使用检查点技术实现动态进程迁移 2 5 】。c o s m i c 2 6 】系统向用户提 供四个检查点库，用户透明检查点库l i b c k p ，文件检查点库l i b f c p ， 关键数据检查点库l i b f t ，强类型检查点库l i b s t ，用户级别根据这几 个库函数可以实现进程迁移。 2 应用级迁移：实现较为简单，可移植性好，但需要了解应用程序语 义，并可能需对应用程序进行修改和重编译，透明性较差。这类系 统提供应用级别进程迁移函数库，在编写应用程序时，在特定位置 调用库函数，进行编译后便可以完成进程迁移。t h e i m e r 等应用该 方法，重编译后实现异构环境下的进程迁移2 7 1 。 3 内核级迁移：通过修改内核可以使迁移更加容易更加有效，也可以 迁移更多种类的进程。基于内核的实现可以充分利用操作系统提供 的功能，全面获取进程和操作系统状态，因此实现效率较高，能够 为用户提供很好的透明性。但是需要对操作系统进行修改，实现较 为复杂。a m o e b a 是提供内核级别进程迁移机制支持的分布式操作系 统【2 8 1 。 上述进程迁移机制可以在节点有相同体系结构和相同操作系统的环境 下实现，这就是同构进程迁移。同构进程迁移并不需要各个节点有相同资 源和处理能力，这也正是进程迁移的原因。同构进程迁移可以很好地利用 空闲网络资源，但只在相同体系结构和相同操作系统可行。许多网络包含 运行不同操作系统的各种机器，在不同体系结构的机器上运行不同操作系 统，相对进程运行的机器来说可能有空闲资源可以提供给进程利用，需要 有异构进程迁移才可以使用这些计算能力。很显然，异构进程迁移更复杂， 因为它必须考虑跟机器和操作系统相关特性，比如同一个程序在不同体系 结构上的编译后程序计数器可能会不同，这就不能在程序任何地方停止 运行然后迁移，因为有些操作所需的指令数是不同的。在转移进程状态、 地址空间、打开文件和通信等等信息时，也必须考虑这些信息的组织安排。 6 华中科技大学硕士学位论文 异构进程迁移在移动环境中特别有用。异构进程迁移通常在代码和或数据 转换基础上实现的，迁移时把数据转换成一种中间格式，转移到目标机器 后再转换成当地体系结构的表示方式。如e m e r a l d 在迁移时数据转换成对 象内的全局数据格式和方法调用时的局部数据格式【2 ”。 1 3 国内外典型系统研究概况 1 3 1 m o s i x m o s i x 3 0 l 是h e b r e w 大学研制的一个支持进程迁移的软件包。它允许 多台运行类似u n i x 内核的( 如l i n u x ) 机器实现资源共享。m o s i x 采用 非集中式算法，每个节点既是本地创建进程的主节点又是其它节点迁移过 来的进程的服务器节点。这意味着可以在任意时刻向集群中增加节点或从 集群中删除节点，而不会对正在运行的进程产生不良的影响。m o s i x 主要 由可抢占的进程迁移机制和一组自适应资源共享算法实现。两者都是在内 核级别使用可装载模块实现，由于内核接口并未改变，所以在应用级别时 完全透明的。m o s i x 的进程迁移机制可以迁移可以在任何时候，迁移任何 进程到任何空闲可用节点上去。通常，迁移是根据某个资源共享算法提供 的信息进行的，但用户可以手动迁移他们自己的进程。进程迁移是m o s i x 资源管理的主要工具。 在实现进程迁移时，被迁移进程被分为两个上下文：可迁移的用户上 下文和依赖创建该进程的节点系统上下文，后者可能不能迁移。用户上下 文包括程序代码、堆栈、数据、内存映像和进程的寄存器等值，该部分封 装了进程在用户级运行的所有内容。系统上下文包括与进程关联的资源描 述、程序在内核运行时的内核堆栈，该部分封装了进程在内核运行的所以 内容。进程迁移时，先把用户上下文转移到目标节点，在目标节点恢复进 程执行，通过截获与系统上下文相关的系统调用，实现位置透明性。m o s i x 进程迁移花费的时间用于在新节点上建立新进程帧的时间是固定的，另一 部分跟传输的内存页面成线性关系。为了减少迁移开销，只传送页表和进 7 华中科技大学硕士学位论文 程“脏”页面。 m o s i x 使用系统调用截获的方法增大了执行系统调用的开销。对文件 和网络的存取操作引入了额外的开销。另外一个缺点是：某些内核函数不 适合上述进程上下文分割，如果进程使用了这些内核函数就不能迁移到其 它节点上去。 1 3 2c r a k c o l u m b i a 大学网络实验室在2 0 0 1 年发布的c r a k l 是采用l i n u x 内核 模块形式实现的透明进程迁移系统。它利用检查点，重起机制，无需修改、 重编译、重新链接应用程序或者操作系统，就可以透明地迁移网络应用程 序和计算环境。c r a k 进行进程迁移时采用如下步骤：首先在每台机器上 安装c r a k 内核模块，该模块在内核空间运行但并不需要修改内核。进程 之间通过虚拟网络地址转换进行通信：请求一个进程或一组进程做检查 点，该请求命令被送往本地内核模块；内核模块停止进程并对进程状态做 检查点写入文件，然后就杀死原来的进程。在进程迁移的目标节点上创建 个新进程，新进程的状态根据检查点文件来填充，网络地址由内核模块 翻译成新机器的地址：其它与原来进程通信的进程被通知并更新。 c r a k 系统是在同构节点上进行的进程迁移，对网络套接字也提供了 支持。它采用一次迁移全部检查点文件而不是按需( o nd e m a n d ) 方式传送 页面。它对程序代码和共享库等内容在传送时做了优化，避免了传送大块 内存页面。 1 3 3c h a r m c h a r m 3 2 l 是国内清华大学汪东升等研发的一种并行程序后向故障恢 复与进程迁移系统。它是基于接收，发送方消息记录。在消息传递库p v m 之上实现的，具有对用户程序透明、可移植性好、开销小和实现简单等特 点p “。迁移发起时，系统首先在目标机上为源机上的进程创建一个骨架进 程，接着，迁移进程设置检查点，并将检查点内容直接通过u n i x 中套接 字通道传给骨架进程。随后，迁移进程自动终止，骨架进程从通道中读出 检查点内容，即刻将自身状态恢复为检查点保存的状态，继续运行。 8 华中科技大学硕士学位论文 c h a r m 使用了“延迟发送”策略来支持异步迁移。为了处理消息丢失， c h a r m 系统采取了p v m 函数封装、任务号隐式匹配、消息驱赶等技术。 迁移期间发向迁移进程的应用消息，由于延迟到映射表更新后再实际发 送，因此将被正确地发往目的机上的恢复进程。 1 4 本课题的主要研究工作内容 如前所述，进程迁移的研究可以分为迁移策略研究和迁移机制方面的 研究。本课题着重进程迁移机制方面的研究，即如何快速地进行进程迁移。 进程迁移机制的实现有很多困难，最基本的问题包括如何确定进程的状 态，进程如何从当前的运行环境中分离出来，以及进程相关上下文如何传 输到目的处理机，并在新的运行环境中正常运行。进程迁移的主要工作就 在于提取进程状态，然后在目的节点根据进程状态再生该进程。进程的状 态一般可以分为：进程执行状态，进程控制，进程存储状态和进程地址空 间，进程的消息状态，文件状态。 首先需要解决的问题是确定进程的状态，以及实现这些状态的保存和 恢复。进程状态除了进程地址空间中的上下文，也就是进程的内部状态信 息，包括正文段、栈段、数据段、程序计数器和寄存器内容外，还包括与 远程进程的通信状态( 包括建立的连接，发送及接收队列，传输的消息等) 。 另个要解决的问题是，如何处理该进程未来的通信。进程在迁移之 后，还能够保持原有的通信连接，正常地接收和发送消息。 第三个问题要做到进程迁移对其他进程的透明性，迁移过程中不能影 响被迁移进程和其他进程的运行。 另外为了快速地迁移进程，如何传输进程的状态以及如何尽快地恢复 进程也很重要。提取进程状态之后，直接通过网络传送给目标节点，显然 比从内核空间拷贝至用户空间并写入硬盘再传输至目标节点恢复执行所 花时间要少。有研究表明”引，根据进程状态的一部分数据就可以恢复一个 进程的执行。 本课题研究的是一种快速的进程迁移机制。在l i n u x 集群环境下应用 9 华中科技大学硕士学位论文 快速进程迁移机制算法实现一个进程迁移系统。主要工作内容包括进程状 态的获取和转移、进程迁移过程中保持消息正确性、目标节点进程的快速 恢复。 1 进程状态的获取和转移。采用l i n u x 操作系统中内核模块技术，动 态地加载用于提取进程状态的模块。根据传入的p i d 模块可以很容 易地得到描述进程所有状态的t a s k s t r u c t 数据结构。模块可以方便 地调用内核提供各种函数来获取进程相关的虚拟内存、打开文件 表、进程间通信、网络连接等信息。 2 进程消息如信号、网络连接等的恢复。采用先缓存这些消息，待迁 移完成后，再处理缓存的信号重新建立新的网络连接。 3 尽快恢复进程的执行。先提取并传输恢复进程所需要的代码、堆栈 和堆的几个内存页面，然后在目标节点即开始恢复进程。在恢复进 程执行的过程当中，陆续传输其它的页面。这样可以缩短进程冻结 时间。 实验表明，采用上述改进方法可以减少进程迁移的冻结时间。f p m s 系 统是采用快速进程迁移算法实现的一个进程迁移系统。它使用内核模块机 制提取进程状态数据，根据一部分进程状态数据快速恢复进程执行，可以 正确恢复网络连接。 本文的章节安排如下： 第一章为绪论，介绍了课题的背景、国内外研究发展概况以及主要研 究内容。 第二章对传统的进程迁移算法及相关背景知识进行介绍。 第三章对快速进程迁移算法进行详述。并比较它与传统算法的区别。 第四章对f p m s 系统结构和功能组成进行介绍。对系统功能的具体实现 以及相关的数据结构和算法进行了详细描述。最后提出该系统需要进一步 完善和发展的地方。 华中科技大学硕士学位论文 2 传统进程迁移算法 本课题研究的进程迁移机制是在l i n u x 操作系统下完成的。因此，本 章首先介绍l i n u x 进程的相关概念。然后对传统进程迁移系统所采用的算 法进行详述，这样可以跟改进的快速进程迁移算法进行比较。 2 1 通用操作系统中进程概念 进程是一个正在执行的程序，包括程序计数器( p r o g r a m c o u n t e r ) ，寄 存器组和变量的当前值p5 1 。也就是说进程包括程序和它的执行状态。进程 是操作系统中资源竞争的最小单位。它是一个动态的实体，总是随着机器 代码指令和处理器的执行而处于变化之中。除了程序的指令和数据，进程 还包括程序计数器和其他c p u 寄存器，以及含有例程参数、返回地址和保 存的变量等i 临时变量的进程栈。程序是处理器正在执行的实际代码，程序 执行状态是该执行程序所需的所有信息。一个可执行程序可以存在于几个 不同的状态 3 6 1 ：就绪态、运行态和阻塞态，如图2 1 。 图2 1 进程的基本状态变迁 其他进程相关的一些概念有： 2 1 1 可执行文件的格式 用户对一个程序的源代码进行编译、链接而建立的可执行文件。在 l i n u x 中，可执行文件由系统调用e x e c v e 更换和装入并跳转执行。主要有 以下部分组成： ( 1 ) 首部( h e a d e r ) ：描述文件的属性，程序的格式及结构： 在l i n u x 中，可以是a o u t 、c o f f 、e l f 等。由文件首部的签名( m a g i cn u m b e r ) 华中科技大学硕士学位论文 可以识别出文件是哪种格式。( 2 ) 程序正文( t e x t ) ：即程序的指令序列；( 3 ) 数据f d a t a ) ：通常包括一个经初始化的数据段和一个尚未初始化的数据段 b s s ( b l o c ks t a t i cs t o r a g e ) 。初始化的数据段中，数据按其大小分配了空间， 并赋有初值；未初始化的数据段只有一个空间指示，表示核心应该为它分 配多大的空间，而该空间的分配仅在运行时进行。初始值为0 ；( 4 ) 其他 段：诸如符号表等信息。 2 1 2 进程的存储器模型 每个进程在自己的虚拟地址空间运行，l i n u x 区别用户进程和系统进 程。系统进程管理整个系统的资源，如分配内存、换进换出用户进程、在 第二级存储器之间换进换出内存页面。进程运行用户级的代码称为在用户 态( u s e r m o d e ) 下运行，进程执行系统级的指令称为在核心态( k e r n e l m o d e ) 下运行。程序在以下情况会进入核心态运行：执行系统调用，产生异常和 出错，中断处理等。进程在核心态运行核心代码，因此能够充分利用处理 器资源，可执行特权指令。虚拟存储系统允许核心访问进程的任何代码和 数据。进程在用户态只能通过系统调用向内核请求服务。 2 1 3 进程的上下文 进程上下文是进程当前的运行环境，包含描述进程的所有信息。主要 由如下部分组成：( i ) 用户地址空间。由正文段，数据段，栈和一些匿名 内存区等组成。( 2 ) 控制信息。包括核心栈、地址空间分布、页表，u i d 、 p i d ，g i d ，打开文件信息，信号处理信息，记帐信息，进程状态等。核心 管理进程而维护的信息。( 3 ) 环境变量。如程序运行时所需的参数，通常 保存在用户栈的底部。( 4 ) 硬件上下文。如寄存器内容等。 2 1 4 用户空间的进程映像 在现代虚存系统中，每个进程只在自己的虚地址空间中运行。从用户 程序角度看，进程地址空间是一段线性编址内存区域。u n i x l i n u x 核心代 码将可执行文件装入内存后，用户的虚地址空间应包含以下逻辑区段：正 文段，包含程序的机器指令序列，对应于可执行文件的正文段；数据段， 保存程序运行中数据；栈段，由系统创建，在运行过程中动态改变。每个 1 2 华中科技大学硕士学位论文 = # = = _ _ _ = # _ = 日e l = _ _ 1 日目；= = ；= = = = = 一 进程都有两个栈：用户栈和核心栈。前者用于用户态执行指令，后者用于 核心态执行指令。 2 1 5 信号处理机制 l i n u x 利用信号机制来通知进程发生了异步事件。每种信号都有一个缺 省的处理。用户可以通过相应的库函数和系统调用，来指定信号的非缺省 处理，激活一个指定的处理过程。进程从核心态返回用户态时，进程进入 或者离开一个适当的低优先级睡眠态时，核心检查它是否收到了信号并做 相应处理。 2 ，1 6 进程间通信( i p c ) 进程间通信机制允许任意进程交换数据和同步执行。在传统的单机 u n i x l i n u x 中，常用下列进程问通信方式：管道、命名管道、信号、信号 量、消息队列、共享内存等。随着互连网络的发展，人们又发展了许多可 以支持远程进程通信的通信方式。其中基于套接字( s o c k e t ) 的进程通信机制 被广泛使用。 2 2 l i n u x 进程相关的概念 l i n u x 是一个多进程操作系统。进程是独立的任务，一个进程崩溃并 不会引起系统中的另一个进程崩溃。每个单独的进程运行在自己的虚拟空 间，并且只能通过安全的内核管理机制和其他进程交互。进程使用系统的 c p u 来运行自己的指令并使用系统的物理内存来保存自己和自己的数据； 它将打开和使用文件子系统的文件并直接或间接地使用系统中的物理设 备。l i n u x 必须跟踪进程本身和它拥有的系统资源，保证它能公平地管理 该进程和系统中的其他进程l i n u x 中每个进程用一个t a s k s t r u c t 数据 结构来表示。该数据结构包括进程调度、进程标识和用户标识、信号量处 理、文件系统管理、内存管理、进程标志等等信息。进程标识符p i d 唯一 的标识一个进程。全局变量c u r r e n t 指针指向当前正在运行进程的进程控 制块。进程迁移涉及到的进程相关信息都可由t a s k s t r u c t 结构获得，包 括进程地址空间、寄存器组、打开文件管道套接字、i p c 结构、当前工 华中科技大学硕士学位论文 作目录、信号处理句柄、定时器、终端设置、用户标志符、进程标志符等 等。其中，地址空间内容和寄存器组的值是必须要迁移的，而其它的信息 根据实际应用可选。 2 2 1 进程内存状态 内存管理子系统是操作系统最重要的部分之一。映像被执行时，可执 行映像的内容和进程虚拟地址空间形成映射【3 。可执行文件并非被真正地 读到物理内存。随着运行程序部分不断被引用，映像从外部存储器读到内 存。进程虚拟地址空间如图2 2 。 圈2 2 进程虚拟地址空间布局 s t r u c t a m s t r u c t 数据结构描述进程的虚拟地址空间。彻一s t r u c t 包 含进程管理内存的很多重要数据，包括进程代码段、数据段、来初始化数 据段、调用参数区和进程环境区的起始地址和结束地址，栈的起始地址和 进程空间的大小。用户程序和代码一般占据虚拟地址空间的下方，这一部 分是内存映射部分，其内容来自映射文件。用户执行映象和堆栈之间的部 分是堆，在用户程序中动态申请的地址空间( 如m a l l o c ) 来源于堆。 咖一s t r t l c t 数据结构中的s t a r t b r k 和b r k 记录有关堆的信息。 为了管理进程虚空间，l i n l i x 定义了虚存段w l a ( v i t u a lm e m o r ya r e a ) ， 一个v m a 是进程的一段连续的虚存空间，在这段虚存里的所有单元拥有相 1 4 华中科技大学硕士学位论文 同的特征，如相同的访问权限等。v n ( a 由s t r u c tv i i i a r e a s t r u t t 数据结 构描述，域v m s t a r t 和v m e n d 是两个虚拟地址，它们描述了虚拟内存区 域在进程虚拟地址空间中的位置；域v m f i l e 记录了该区域映射的文件， v m o f f s e t 表示该区域在映射文件中的开始位置。如果这两个域非空，它 们和v i i i s t a r t 和v m e n d 一起，描述了文件v m f i l e 和虚拟内存之间的映 射关系。域v i i i n e x t 是个指针，指向下一个虚拟内存区域，所有虚拟内存 区域连接成一个链表，表头可由m m s t r u c t 结构的m m a p 成员得到。因此， 从i i i m a p 表头出发，可以获得所有虚拟内存区域的状态。根据虚拟内存区 提供的虚拟地址，可以得到实际物理内存的内容。t a s k s t r u c t 数据结构 和内存管理数据结构的关系如图2 3 1 3 8 i 。 帅s t r u c tv m a r e a s t r u c t进程虚拟内存 图2 3 进程的虚拟内存示意图 2 2 2 内存分页管理模式 标准l i n u x 的分页机制是三级页表结构，采用按需调页( d e m a n d 华中科技大学硕士学位论文 p a g i n g ) 算法，支持三层页式存储管理策略：页目录( p g d ) ，页中间目录 ( p m d ) ，页表( p t e ) 。每个页表项保存着物理内存页的开始址和属性。 t a s k s t r u c t 的数据成员m m 的p g d 成员是页目录的起始地址。l i n u x 提供 虚地址转换成物理地址的宏。每个进程都有一个页目录，存储进程使用内 存页面情况。创建新进程或执行系统调用e x e c 时都会首先分配几个内存页 面，如果执行时执行代码不在内存中，操作系统将产生缺页中断分配内存 页面并将代码读入内存中。进程终止时，操作系统释放进程占用的内存页 面。申请释放较小的内存块使用k m a l l o c 和k f r e e 调用，较大的存储空间 使用v m a l l o c 和v f r e e 调用。 在进行进程迁移时，可以利用操作系统分页机制，不需要传输进程所 有的页面才恢复进程的执行，先传输恢复进程所需要的代码段、堆栈段的 几个页面就可以恢复进程的执行了。 2 3 进程状态的保存和恢复 进程迁移可定义为在不同的处理器上移动一个正在执行进程的能力， 这些处理器通过网络互相连接而不是局部共享内存。源机器必须把整个进 程的状态封装起来，以便目标机器继续执行进程。迁移策略决定什么时候 系统发起迁移，迁移哪个进程，选择迁移的目标节点。迁移策略一般有源 节点主动发起迁移和目标节点主动请求迁移两种。源节点主动发起适合于 各个节点负载较轻的情况，而目标节点主动请求适合于各个节点负载较重 的情况 3 9j 。我们采用源节点主动发起迁移的策略。 实现进程迁移机制时，首先需要考虑的是在硬件和操作系统相同的节 点间迁移还是相异的节点之间迁移。不同硬件的环境下指令集和数据表示 都不同，不同操作系统的进程表示方式也不同。如果没有语言级的扩展支 持，在某个执行环境下的进程的状态信息，几乎不可能迁移到不同数据表 示方式的处理器。同样，编译好的代码若不采用仿真技术也不可能从一个 平台迁移到另一个不同平台。操作系统平台不同，也很难透明地迁移一个 进程，进程可能调用一个根本不存在的系统调用。异构平台的进程迁移1 4 0 l 1 6 华中科技大学硕士学位论文 国外有t o i 等系统。 我们研究的是同构平台下如何快速有效地迁移进程。目前国内外已经 实现的系统按实现方式可分为两种：一种是在用户级别实现，进程被链接 到一个用户级别迁移函数库，这个库提供进程状态维护函数和进程迁移函 数。这种方法通常只处理单一进程，限定进程执行时的操作范围。譬如， 进程不能有g u i 交互，不能打开网络链接或者存取文件。进程迁移通过在 某些特定位置做检查点操作保存进程状态，然后根据检查点文件恢复进程 实现。c o n d o r 系统只迁移计算密集型且没有g u i 交互或打开网络链接的 进程，并且假定通过网络文件系统可以远程访问文件。另外一种是在操作 系统内核级别实现，大多数支持进程迁移的分布式操作系统如c h o r u s 、 m o s i x 、a m o e b a 等等都属于这一类。进程状态或者任何进程相关的内核 状态都由操作系统提供的机制进行迁移，源节点可选择性地留下一个代理 来处理位置相关的操作。内核级别的实现方式虽然能迁移任何普通的进 程，但引入了非常显著的运行时开销，而且加大了操作系统的复杂性和可 维护性。要完全消除位置相关性也是不太可能的，除非底层操作系统网络 范围内共享标志符空间，同时采用网络文件系统。 不管用户级别实现，还是内核级别实现，一般来说进程迁移机制遵循 如下逻辑步骤： 1 挂起进程并收集