（计算机系统结构专业论文）支持socket迁移的抢占式进程迁移系统.pdf

华中科技大学硕士学位论文 摘要 随着计算机系统中商用部件性能的不断提高和价格的不断下降，使得具有良好可 扩展性和高性价比的集群系统在高性能计算中的地位越来越重要。应用于高性能计算 的集群系统中存在大量的计算资源，因而有效管理和利用这些资源是一个非常重要的 问题。集群动态负载平衡系统正是解决这个问题的重要工具。它通过在集群各个结点 间动态的平衡系统负载来达到更有效的资源利用率，从而提高集群系统的整体性能。 由于集群并行程序设计和运行环境中网络通信的地位越来越重要，而现有的绝大 多数集群负载平衡系统对存在网络通信的应用程序缺乏有效支持。为此本文提出了一 种支持s o c k e t 迁移的抢占式进程迁移系统，结合负载平衡算法可以有效解决以上问题。 在本文的进程迁移系统中，使用了一种改进的t o t a lc o p y 进程迁移算法来避免传 送进程虚拟地址空间中的动态连接库和代码段部分，这样可以大大减少进程迁移过程 代价和减小被迁移进程的冻结时间。通过对现有的s o c k e t 迁移实现途径和相关系统的 分析，发现现有的s o c k e t 迁移系统在迁移监听状态s o c k e t 时只是简单地将监听套接字 从一个结点迁移到另一个结点。当有客户端向原结点的原监听端口发起连接时，这个 连接请求将会失败而导致整个程序运行失败。本文通过介绍采用p 4 通信库的并行程 序f 铷建立通信连接的过程描述了以上现象，充分说明如果不解决这个问题，会导致现 有的s o c k e t 迁移系统没有太大的实际应用价值。通过使用本文提出s y n - c h a n g e 方法可 以简单有效地解决这个问题。另外，本文通过使用t c p 的超时重传原理，对现有的 s o c k e t 系统在迁移连接状态s o c k e t 的迁移算法进行了改进。 本文在l i n u x 操作系统中以可动态加载内核模块形式实现了抢占式进程迁移系统 p p m m ( p r c e m p 吐v e p r o c e s sm i g r a t i o n m o d u l e ) 。由于不需要对操作系统内核做任何 修改，因此大大提高了进程迁移系统的易用性和可维护性。系统功能测试表明本文的 进程迁移系统可以完全支持s o c k e t 迁移。同时通过性能的对比测试，也表明了进程迁 移算法的改进带来了较大的性能提升。 关键词：进程迁移， 套接字迁移，集群，动态负载平衡，内核模块 一一 i 华中科技大学硕士学位论文 a b s t r a c t w i t ht h ei m p r o v e m e n to f p e r f o r m a n c ea n dt h ed e c r e a s eo f t h ep r i c eo f t h ec o m m o d i t y p a r to f t h ec o m p u t e r s y s t e m s ，t h ec l u s t e rs y s t e m sw h i c h h a v eb e t t e rs c a l a b i l i t ya n dh i g h e r p e r f o r m a n c ep r i c e r a t i ob e c o m em o i la n dm o i li m p o r t a n ti nt h e h i g hp e r f o r m a n c e c o m p u t i n ga r e a t h e r ea r ep l e n t i f u lc o m p u t l u g r e s o u r c e si nh i g hp e r f o r m a n c ec o m p u t i n g c l u s t e r s ，t h e r e f o r em a n a g i n ga n du t i l i 商a g s u c hi l s o l l r c e s e f f i c i e n t l yi s ab i gp r o b l e m ， d y n a m i c l o a db a l a n c i n gs y s t e mt h a td i s t r i b u t i n gs y s t e ml o a da m o n gt h ec l u s t e rt og e tb e t t e r r e s o u r c eu t i l i z a t i o na n dt oi m p r o v et h eo v e r a l lp e r f o r m a n c ei sa ni m p o r t a n tt o o lt os o l v e t h e s e p r o b l e m s n o w d a y s ，t h en e t w o r kc o m m u n i c a t i o ni sb e c o m i n gv e r yi m p o r t a n ti nt h ep a r a l l e l p r o g r a m m i n ge n v i r o n m e n t so f c l u s t e rc o m p u t i n g ，b u tm o s to ft h ee x i s t i n gd y n a m i cl o a d b a l a n c i n gs y s t e m a r e i n s u f f i c i e n t l ys u p p o r t i n g t h e p r o g r a m s t h a th a c en e t w o r k c o m m u n i c a t i o n t h i sp a p e rp r o p o s e sap r e e m p t i v ep r o c e s sm i g r a t i o ns y s t e mw i mt h e s u p p o r t i n go f s o c k e tm i g r a t i o n c o m b i n e dw i t ht h el o a db a l a n c i n ga l g o r i t h mi tc a l ls o l v e t h ea b o v e p r o b l e me f f i c i e n t l y a no p t i m i z e dt o t a l c o p yp r o c e s sm i g r a t i o na l g o r i t h m i s a d o p t e db yt h ep r o c e s s m i g r a t i o ns y s t e mp r o p o s e di nt h i sp a p e rt h a tc a na v o i dt r a n s f e r r i n gt h ed y n a m i cl i n k e d l i b r a r ya n dc o d es e g m e n tp a r t so f t h ev i r t u a la d d r e s ss p a c eo ft h em i g r a t i n gp r o c e s s 1 1 l i s o p t i m i z a t i o n c i l i a g r e a t l yd e c r e a s et h em i g r a t i o nc o s ta n dt h ef r e e z et i m eo f t h em i g r a t i n g p r o c e s s t h r o u g ht h ea n a l y s i so f t h ei m p l e m e n t a t i o na p p r o a c h e sa n dr e l e v a n ts y s t e m s ，w e f i n dt h a tt h ee x i s t i n gs o c k e tm i g r a t i o ns y s t e m ss i m p t ym i g r a t i n gt h el i s t e n i n gs t a t es o c k e t f r o mo n en o d et oa n o t h e r t h ec o n n e c t i o nw i l lf a i l e di f t h e r ei sa n yc l i e n tc o n n e c t i n gt ot h e o r i g i n a ln o d e w i t ht h e o r i g i n a ll i s t e n i n gp o r t t h i sw i l lc a u s e t h ew h o l e p r o g r a m f a i l u r e w e p r e s e n tt h es c e n eb yd e s c r i b i n gt h ec o m m u n i c a t i o ne s t a b l i s h i n gs t e p so fm p ip r o g r a m s u s i n gp 4l i b r a r y w ec o m e t ot h ec o n c l u s i o nt h a ti f d o n ts o l v et i f f sp r o b l e mt h e r ew i l lb en o p r a c t i c a l v a l u eo ft h e e x i s t i n g s o c k e t m i g r a t i n g s y s t e m s 1 1 1 ea p p r o a c h n a m e d s y n c h a n g ei sp r o p o s e di nt h i s p a p e rt o s o l v et h ep r o b l e m 1 1 1 ee x i s t i n gm i g r a t i o n a l g o r i t h m o ft h ee s t a b l i s h e ds o c k e ti sa l s ob e e n o p t i m i z e db yu s i n g t h et c p t i m e o u t r e t r a n s m i tm e c h a n i s mt h a tc a l li m p r o v et h es o c k e tm i g r a t i o np e r f o r m a n c ea n d d e c r e a s et h eo v e r a l lf r e e z et i m e t h e p r e e m p t i v ep r o c e s sm i g r a t i o ns y s t e mp r o p o s e d i nt h i s 肼i p e rw h i c hn a m e dp p m m ( p r e e m p t i v ep r o c e s sm i g r a t i o nm o d u l e ) h a s b e e n i m p l e m e n t e d a sal i n u xl o a d a b ek e r n e l 华中科技大学硕士学位论文 m o d u l e b e c a u s eo fn e e d0 0m o d i f i c a t i o no ft h eo p e r a t i n gs y s t e mk e r n e l ，t h es y s t e mc a l l i m p r o v et h eu s a b i l i t ya n dm a i n t a i n a b i l i t yo f t h ep r o c e s sm i g r a t i o ns y s t e m s t h ef u n c t i o n a l t e s t e so f t h e p r o c e s sm i g r a t i o ns y s t e mi n d i c a t et h a ti tc a l ls u p p o r ts o c k e tm i g r a t i o n p e r f e c t l y t h r o u g ht h ep e r f o r m a n c em e a s u r e m e n tw ef i n dt h a tt h e o p t i m i z e dp r o c e s sm i g r a t i o n m g o f i t h r n c a r lg r e a t l yi m p r o v et h e p e r f o r m a n c e k e y w o r d s ：p r o c e s sm i g r a t i o n , s o c k e t m i g r a t i o n , c l u s t e r ，d y n a m i cl o a db a l a n c i n g ， k e m e lm o d u l e 一 i i i 独创性声明 本人声明所呈交韵学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名 日期：细僻厂月f 乙日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密叫。 ( 请在以上方框内打“4 ”) 学位论文作者签名：栅 日期：伽吖年y 月( 恫 指导教师签名 日期：俨l f 年 华中科技大学硕士学位论文 1 绪论 本章主要讨论进程迁移与集群负载平衡系统的关系，并指出支持s o c k e t 迁移在集 群动态负载平衡系统中的重要意义。最后分祈国内外己有的迸程迁移系统的实现特 点。 1 1 研究背景 1 1 1 集群及其动态负载平衡系统 随着计算机中商用部件性能的不断提高和价格的不断下降，使得集群系统在高性 能计算中的地位越来越重要。应用于高性能计算的集群系统中有大量的计算资源，如 何有效管理和利用这些资源是一个非常重要的问题。集群负载平衡系统正是解决这个 问题的一个重要工具。它通过将负载( 一般指计算任务或进程) 从高负载节点转移到 负载较低的节点上，来平衡集群各节点负载，达到更有效的资源利用率，从而提高集 群系统的整体性能。已有的研究表明，在集群系统中采用负载平衡系统可以显著地提 高集群系统的性能 ”。这使得集群负载平衡系统一直都是集群计算中的研究热点。 现有的集群负载平衡系统可以分为动态和静态负载平衡系统。二者的区别在于负 载平衡决策的根据。在静态负载平衡系统中，负载平衡并不考虑集群各个节点当前的 负载情况，而根据固定的分配方法在集群中分派任务。与前者相反，后者在考虑了集 群各节点当前的负载情况后，才做出负载平衡的决定。 静态负载平衡算法实现简单，但显然其负载效果较差。因此，为了得到更好的性 能，绝大多数负载平衡系统都采用了动态负载平衡算法。 1 1 2 进程迁移与集群动态负藏平衡系统 在动态负载平衡系统中，在做出负载平衡决定后，需要将负载从高负载的节点转 移到低负载的节点上。进程迁移和进程的远程执行是用于完成这个的工作的两种技 术。 进程迁移是指将一个正在运行的进程从一个节点迁移到另外个节点上运行的 过程。这个迁移的过程可以发生在进程运行的任何时刻。与进程迁移相比，进程的远 程执行只能迁移新产生的进程。进程的远程执行不涉及进程运行过程中产生的各种运 华中科技大学硕士学位论文 行状态的迁移，因而实现极为简单，且其迁移速度大大高于进程迁移。但是进程的远 程执行只能在进程产生的那个时刻才能发生迁移，将会大大减少负载平衡系统用于转 移负载的时机。并且，由于进程被远程执行到远端节点后，只能在这个节点上运行直 到退出。另外，进程远程执行迁移进程的粒度一般为任务，当任务中包含有多个进程 时，其迁移的粒度较低。这些原因将都会导致，进程的远程执行不能及时对集群中可 能出现的负载不平衡的情况做出及时的响应。导致进程的远程执行并不适合于应用到 通用的集群动态负载平衡系统中。已有的研究表明，在集群动态负载平衡系统中采用 进程迁移相对采用进程的远程执行可以得到更好的性能【2 ，3 1 。因此已实现的负载平衡 系统多采用进程迁移作为负载转移的手段。 1 1 3 s o c k e t 迁移的应用需求 集群动态负载平衡系统所能迁移的进程类型对集群动态负载平衡的性能有直接 影响。 从集群动态负载乎衡算法的角度来看，如果可供挑选用于迁移的负载越多，其进 行负载平衡的时机也越多，显然能够取得更好的负载平衡效果。相反，如果一个集群 负载平衡系统能用于负载转移的负载类型和数量十分有限，将会使负载平衡的时机大 大减少。这样，即使负载平衡算法知道需要进行负载转移来平衡负载，却找不到适合 的负载进行迁移而无法进行负载平衡。显然，这样会严重影响集群动态负载平衡系统 的性能。如果一个集群动态负载平衡系统对大部分的进程都不能进行迁移，对可被迁 移的进程限制太多，则导致集群动态负载平衡系统失去意义。 高性能集群计算中的任务或者应用可以分为两类。第一类为传统的串行任务。这 类任务间的关系相对独立。任务间不需要进行大量的数据交互即可以完成各自的任 务。这类任务是以往的集群动态负载平衡系统所针对的应用。高性能计算中更为普遍 且更为重要的另一类任务为并行任务。这类任务之间关系密切，往往需要通过频繁的 数据交换或同步来完成一个共同的计算任务。这类任务通常为基于消息传递的并行程 序设计和运行环境，比如p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 1 4 1 m p i ( m a s s a g e p a s s i n g i n t e r f a c e ) 晡】等。这些并行程序设计环境在一定的通信协议之上构建消息传递接v i ，提 供给并行任务使用。通用的t c p i p 协议在其中使用比较普遍。比如使用非常广泛的 m p i c h p 4 【6 j 通信库正是基于通用的t c p i p 协议。 2 华中科技大学硕士学位论文 从集群动态负载平衡系统的角度来看，这些并行计算任务间存在大量的基于 t c p i p 协议的s o c k e t 通信。因此，能够迁移这类任务即实现s o c k e t 的迁移对集群动 态负载平衡系统是非常有必要的。 1 2 国内外研究现状 1 2 1 进程迁移的背景 进程是操作系统中的一个关键概念，它是可执行程序的一次运行的表现1 7 ) 。一个 进程有一个唯一的标识( p i d ) ，一个寄存器组、一个地址空间和，或一些其它的资源，比 如打开的文件等等。在现代的操作系统中，每个进程在自己独立的地址空间中运行。 进程一般通过系统调用与操作系统进行交互。它也可以通过由操作系统提供的进程间 通信机制与其它进程进行交互。 进程迁移是指将一个正在运行的进程，从一个结点( 源结点) 传送到另外一个结 点( 目的结点) ，并能继续运行的过程。对进程迁移的整体概括可以由图1 1 来表示。 通信结点 图1 1 进程迁移的基本流程 从图中可以看到，进程迁移一般过程包括在源结点上提取被迁移进程的状态信 息，状态信息向目标结点的传送。目标结点产生一个新的进程接收并导入被迁移进程 的状态信息。恢复被迁移进程与其它进程间的通信。 进程迁移过程中需要被传送的进程状态信息般包括以下的内容t ( 1 ) 进程的控制状态：这部分包括所有被操作系统用来管理进程的信息。这些 信息包括进程优先级、进程状态、进程标识( p i d ) 、父进程标识( p p i d ) 等。 ( 2 ) 进程的执行状态：这部分主要包括进程的处理机状态，即进程的执行现场 信息。这些信息包括；通用寄存器、浮点寄存器、堆栈指针、程序计数器、c p u 状态 3 华中科技大学硕士学位论文 寄存器等的内容。 ( 3 ) 进程的地址空间：进程整个虚拟地址空间的内容，这是进程状态信息中最 大的一部分。 ( 4 ) 文件状态：这部分包括文件描述符、文件路径名、文件缓存块等。 ( 5 ) 进程的通信状态：这部分内容比较特殊，除了与以上类似的部分比如进程 缓存的消息和通信连接的控锘8 信息这些内容外。还包括在进程迁移过程中如何管理通 信连接，以及在进程迁移完毕后如何恢复与其它进程的连接等这些内容。这部分内容 比前面的部分实现更复杂。 1 2 2 进程迁移的实现途径比较与分析 不同的应用环境对进程迁移的实现复杂度、性能以及功能等有不同的要求，因而 也产生了不同的进程迁移的实现途径。这些实现途径实际上是一些在设计与实现进程 迁移系统时根据应用环境所做出的不同取舍。这些取舍主要包括：进程迁移的实现层 次( 内核空间或用户空间) 、进程地址空间的传送算法( 完全拷贝算法或远程按需调页 算法) 以及进程迁移的使用方法( 抢占式进程迁移或非抢占式进程迁移) 。下面对这些 实现途径分别进行讨论。关于进程迁移的实现途径的详细分析和介绍可以见文献【8 一。 ( 1 ) 内核空间实现与用户空间实现 进程迁移可以作为操作系统内核的一部分实现也可以在用户空间实现。不同的实 现层次导致了进程迁移的不同性能、实现复杂度、透明性和可重用性。 用户空间的进程迁移实现简单，可移植性较好。但由于在用户空间存取操作系统 内核状态信息受到极大的限制，导致用户空间进程迁移系统所能迁移的进程类型十分 有限。另外，由于在迁移时必须通过系统调用来越过内核，应用空间这个界限，也导致 在用户空间的进程迁移系统迁移代价大，迁移速度慢。用户空间进程迁移系统在性能 和透明性这两方面的缺陷，使得它们不能应用在通用目的的负载平衡系统中。用户空 间的进程迁移系统一般应用在运行时间较长的计算任务中。 内核空间的进程迁移实现复杂，对操作系统内核改动较大，但其迸程迁移的性能， 以及对用户程序的透明性较高。这些优点使得内核空间的进程迁移系统更适合于通用 目的的负载平衡系统。 ( 2 ) 抢占式进程迁移与非抢占式进程迁移 进程迁移从是否由被迁移进程主动请求迁移，又可以分为抢占式进程迁移和非抢 4 华中科技大学硕士学位论文 占式进程迁移。抢占式进程迁移是指一个进程可以被另外一个进程( 可以是动态负载 平衡系统) 迁移。非抢占式进程迁移中，一个进程不能使得另外一个进程被迁移，即 在非抢占式进程迁移中，只能由进程迁移自己。因此从进程迁移的透踢性方面来看， 抢占式进程迁移对于应用程序是透明的。 ( 3 ) 进程迁移的完全拷贝算法与远程按需调页算法 进程迁移过程中所需要传送的被迁移进程的状态信息主要包括：进程的控制状 态信息：进程的执行状态信息；进程的虚拟地址空间：进程的文件状态；进 程的通信状态信息。 分析这些状态信息可以看出，一个进程的状态信息可以区分为固定大小部分和可 变大小部分。前者主要包括进程的控制状态信息、执行状态信息、文件状态信息、通 信状态信息等等。这部分状态的特点是信息量较小，不同进程这部分信息量的大小变 化较小。状态信息的可变大小部分为被迁移进程的虚拟地址空间的内容，这部分信息 所占比例最大，并且不同的进程其信息量大小变化很大，其大小对不同的进程来说也 无法预测。 进程迁移中需要传送的状态信息量由进程虚拟地址空间的大小决定，导致了进程 迁移的性能主要取决于进程虚拟地址空间的传送时间。如果在进程迁移过程中将进程 的虚拟地址空间的全部内容都传送到目标结点上，将会使得进程迁移的代价十分巨 大。为此，很多进程迁移系统采用了一些懒惰( 按需) 传送的策略来减小在进程迁移 时所传送的进程虚拟地址空间的内容，这样可以大大缩短进程迁移的进程冻结时间。 实现这种懒惰( 按需) 传送策略需要有远程按需调页系统的支持。因此。在对进程虚 拟地址空间的传送方法上，可以将进程迁移系统区分为完全拷贝算法( t o t a lc o p y ) 和远 程按需调页算法( r e m o t ed e m a n dp a g i n g ) 这两类。这两种算法的迁移时序可由图1 2 和 图1 3 来描述。 从图1 2 可以看出，在完全拷贝进程迁移算法中，只有当进程的虚拟地址空间的 内容全部被传送到目标结点上后，被迁移进程才能投入运行。完全拷贝进程迁移算法 的优点在于实现简单，且被迁移进程在迁移后的运行不依赖于原结点，没有残余依赖 性。但这种进程迁移算法存在较大迁移初始代价，使得被迁移进程的冻结时间过长。 由于在进程迁移过程中，被迁移进程不能发送通信消息，过长的冻结时河可能会让其 它进程认为通信连接发生超时故障而撤销与被迁移进程间的通信连接，导致进程迁移 失败。出于以上的缺点，完全拷贝进程迁移算法只被早期的进程迁移系统采用。 s 华中科技大学硕士学位论文 对于远程按需调页进程迁移算法( 如图1 - 3 ) ，在进程迁移时只需要传送部分状态 信息到目标结点，被迁移进程即可以投入运行。这些状态信息主要包括进程的控制状 态信息、执行状态信息、打开文件信息和通信状态信息。而地址空间的内容可以等到 被迁移进程投入运行后需要访问这些地址空间时，通过远程调页机制传送到目标结 点。 远程按需调页迁移算法大大减小了进程迁移的启动代价，使得被迁移进程的冻结 时间大大减小，非常有利于存在通信连接的进程的迁移。但这种进程迁移算法却增加 了进程迁移的运行时代价，即被迁移进程在投入运年亍后，需要访问的页面必须从原结 点上传送到目标结点上。另外，这种进程迁移算法也增加了一定的残余依赖性，即被 迁移进程在进程迁移完毕后的运行仍然需要原结点的支持。尽管如此，由于远程按需 调页算法具有相对较小的进程冻结时间和启动代价，因此被现在的大多数进程迁移系 统所采用。 o l dh o s tn e wh o s t a p p r o v e d p , c q u e s t m i 粤- a t i 7 、 j p r o c e s sc o n t r o le n d “e c u t i o f ls 吨 1 c o m m u n i c a t i o nl i n k s ： f i l ei n f o r m a t i o n c o d e p a g e s l k p a g e s、 h e a p p a g c s 。 融。p ”“5 。删 o l dh o s tn o wh o s t a p p r o v e dr e q u e s t m i g r a t i o n p r o c e i sc o n u o l 飘de x e c u t i o ns t a t e 1 c o m m u n i c a t i o nl i n k s ： f i l ei n f o r m a t i o n ： r e s t t m cp r o c e s sc o m m a n d 二 r c q u “c o d ep n g j c o d e p a g e s 。 r c q s t e kp a g e s s t a c k p a g e s l r r e q u e s t - k 叩p 啊 、 h e a pp a g 图1 ，2 完全拷贝进程迁移算法图1 3 远程按需调页进程迁移算法 1 2 3 营内外相关系统分析 从8 0 年代开始，已有很多进程迁移系统的研究与实现。这些进程迁移系统被应用 于各种不同的目的。其中最重要的应用环境为集群动态负载平衡系统和容错系统。 早期的进程迁移系统多为各种实验室原型系统，并构建在各种不同的实验性质的 专用操作系统之上。它们中的很多现在都已经停止研究与开发，并且一直都没有得到 6 华中科技大学硕士学位论文 广泛的应用。这些系统有l o c u s 1 讲、r h o d o s 【1 ”、c l o u d s 12 1 ，a m o e b a t 妇1 、v 【1 4 1 ， s p r i t e ”】、c h o i c e 1 6 1 等等。下面简单介绍其中有代表性的系统。 s p r i t e 由加州大学伯克利分校于1 9 8 4 年开始开发。s p r i t e 是一个专用的操作系 统，它提供了一个u n i x - l i k e 编程环境，并实现了一个完全透明的进程迁移系统。s p r i t e 中每个进程从逻辑上看直在称为h o m e 结点的结点上运行，但实际上这个进程可能在 不同的物理结点上运行。s p r i t e 操作系统内核区分结点依赖( 1 0 c a f i o n - d e p e f l d e n t ) 和结点 独靠_ ( 1 0 c a t i o n i n d e p e n d e n t ) 的系统调用。内核将位于远程结点上的被迁移进程的结点依赖 的系统调用，返回到这个进程的h o m e 结点上执行，来达到对被迁移进程完全透明的目 的。s p r i t e 对操作系统内核进行了大量的修改，采用远程按需调页进程迁移算法，它不 支持s o c k e t 迁移。这个项目于1 9 9 4 年终止，并一直没有被广泛应用。 c h o i c e 是一个基于面向对象概念的专用操作系统，由u n i v e r s i t yo fi l l i n o i s a t u r b a n a - c h a m p a i g n 于1 9 9 4 年开发。t h o m a sr o u s h 于1 9 9 5 年在这个操作系统之上实 现了一个较新颖的进程迁移算法f 1 8 ，1 9 1 。这个进程迁移算法对远程按需调页进程算法进 行了一系列的改进，将进程迁移的延迟时间减少到1 4 m s ，这个延迟时间是当时所有 进程迁移系统中最快的。但该进程迁移系统一直没有后续工作，也没有得到广泛应用。 还有一些早期的在用户空间实现的进程迁移系统。这些系统都以c h e c k p o i n t r e s t a r t 技术的形式出现，类似于以上介绍的t o t a jc o p y 进程迁移算法。这些系统主要有 m p v m 2 0 1 、d y n a m i c p v m f 2 ”、c o n d o r i n l 、l i b c k p t l 2 3 1 等等。下面挑选其中有代表性的 系统进行介绍。 m p v m ( m i g r a t a b t ep v m ) 是对并行虚拟桃p v m 的扩展。m p v m 在p v m 环境下 提供了透明的进程迁移机制，它通过将进程的状态信息从一个结点传送到另外一个结 点，来允许将并行程序中的菜个部分暂停，并且在其它结点上重新开始运行。它通过 修改p v m 的运行库和p v m 的守护进程来对一些系统调用进行包装，从而达到对并行 程序迁移的透明性。所有的实现均在用户空间完成。v l p v m 的缺点在于用户进程必须 与m p v m 所提供的库函数进行重新链接，因而对用户程序的透明性较差。m p v m 只 针对p v m 这种并行环境设计，而不是一个通用目的的进程迁移系统。 c o n d o r 是一个为u n i x 环境设计的分布式批处理作业管理系统。它在工作站集群 环境下来调度作业a 它将进程的状态信息c h e c k p o i n t 到个文件，从而可以在另外的 结点上重新启动。用户进程必须与c o n d o r 提供的进程迁移库进行重新连接。c o n d o r 7 华中科技大学硕士学位论文 在用户空间实现，它有如下一些缺陷。首先，c o n d o r 不支持存在任何进程间通信的进 程迁移。即被迁移进程不能调用f o r k 0 或者e x e c v e 0 系统调用，或者通过信号、s o c k e t 、 管道、文件等进程间通信方式与其它进程进行通信。用户进程需要使用c o n d o r 的进 程迁移机制时必须要与c o n d o r 提供的库函数进行重新链接，这样没有源代码的用户 程序将不能使用c o n d o r 的进程迁移机制。 近年来，随着l i n u x 操作系统的出现和快速普及以及在高性能集群计算中的广泛 采用，现在的集群动态负载平衡系统都纷纷基于l i n u x 操作系统构建，其中的一些已 经得到了广泛的应用。本节也挑选其中有代表性的系统进行简单的介绍。 m o s i x p a l 是为数不多的一直坚持在通用的操作系统上构建的通用集群动态负载 平衡系统。它已经得到了广泛的应用，并取得了良好的效果。m o s i x 由以色列耶路 撒冷大学从1 9 8 1 年开始开发，先后为各种u n i x 版本开发了6 个版本，并于1 9 9 7 年 发布了第7 版基于l i n u x 的版本。m o s i x 的设计目标是使整个集群系统从作业 的角度来看像一个大型的s m p 单机系统。作业可以根据系统的负载情况在任何时候 被迁移到集群系统中的任何节点，被迁移作业并不会意识到这个过程，这一切都依赖 于m o s i x 中的全透明抢占式进程迁移系统。m o s i x 通过修改操作系统内核实现了远 程按需调页进程迁移算法，为达到较高的透明性也采用了类似与s p r i t e 中的h o m e 结点概念，并区分结点依赖性和结点独立性系统调用。m o s i x 通过一种效率低下的 方式间接地支持s o c k e t 迁移( 第2 章将对m o s 的s o c k e t 迁移进行讨论) 。 e p c k p t e 2 5 1 是巴西r i od ej a n e i r o 州立大学开发的集群操作系统n o m a d 2 6 项目 中的一部分。它是一个在内核实现的全透明c h e c k f i o i n f f r c s t a r t 系统。它通过修改l i n u x 操作系统，在内核中安装了一个默认的信号处理函数，使得迁移个进程只需要简单 地向被迁移的进程发送一个信号即可以_ 完成。e p c k p t 的主要缺点是，为了达到较高 的进程迁移透明性，在迁移一个进程前必须调用它提供的系统调用来收集被迁移进程 的所打开的文件等信息。这就是说，在决定迁移一个进程前就必须知道迁移哪个进程， 显然这不利于在其之上构建集群动态负载平衡系统。另外，这种实现方式会带来较大 的额外开销。e p c 叮不支持s o c k e t 迁移。采用e p c k p t 的集群动态负载平衡系统还 有美国w o r c e s t e rp o l y t e c h n i c 学院于1 9 9 9 年开发p a n t s t 2 ”。 b p r o c 跚( b e o w u l f d i s t r i b u t e dp r o c e s ss p a c e ) g j 美国l o sa l a m o s 国家实验室的高性 能计算实验室的e r i kh e n d r i k s 从2 0 0 1 年开始开发，直到现在仍然是一个在研项目。 8 华中科技大学硕士学位论文 b p r o c 是一个用于管理集群并行程序的库，它通过修改l i n u x 内核在其中加入一些 h o o k 点来实现进程迁移。b p r o c 所实现的进程迁移是一种非抢占式进程迁移，即b p r o c 中的进程迁移只能由进程自己来完成，需要迁移的进程必须和b p r o c 提供的库函数重 新链接接。这种实现方法使得无法在b p r o c 之上构建集群动态负载平衡系统。b p r o c 采用t o t a lc o p y 进程迁移算法实现。b p r o c 不支持对打开文件的迁移，进程被迁移时所 有已打开的文件都要被关闭，因此不支持s o c k e t 迁移。 虽然w i n d o w s 操作系统在集群计算中应用较少，但也有一些在w i n d o w s 操作系 统下迸行进程迁移的尝试。由于w i n d o w s 这种商用操作系统没有公开源代码，其内部 的实现机制也并不公开，因此在这种操作系统中实现进程迁移的难度较大。w i n d o w s 操作系统下实现的进程迁移系统较少，主要有v o s 2 9 j ( v i r t u a l i z i i n go p e r a t i o ns y s t e m ) n t - s w i f t 3 0 j 。本节仅仅介绍v o s 。 v o s 是美国a r i z o i a 州立大学于2 0 0 1 年开始开发的c c 日1 ( c o m p u t i n gc o m m t m i t y ) y 页h 中的部分。c c 的主要目标是使一些相互合作的集群结点像介单一的系统工作。所有通 用目的的应用程序可以不做任何修改就可以在这个系统e 运行。v o s 在w m d o w s n t 操作系 统下实现了透明的进程迁移，这是实现c c 设计目标的主要工具。v o s 通过使用a p i 拦截 技术，在被迁移进程的执行映象中注入个d l l ，这个d l l 会产生一个在被迁移进程地址 空间中运行的线程，而这个线程会记录被迁移进程的所有运行信息。通过这些记录的信息， 被迁移进程可以在新的结点上得到恢复运行。v o s 的特点在于它支持对拥有g u i 进程的迁 移。v o s 实际上是在用户空间完成进程迁移。由于v o s 在迂移进程前就必须知道被迁移的 进程，以便从其运行开始时就记录其运行信息，否则将无法对其进行恢复。这样的实现存 在较大的迁移代价。在实际擐 试中，v o s 迁移一个进程的时间达到了数秒钟。并且由于v o s 是一种非抢占式进程迁移系统，因此并不适合在其上构建集群动态负载平衡系统。 1 3 本文内容的组织 本文以后的章节组织如下：第二章对s o c k e t 迁移的基本概念，以及现有s o c k e t 迁 移系统存在的问题进行讨论。第三章给出了本文的抢占式进程迁移系统的设计目标和 基本机制。第四、第五章分别讨论抢占式进程迁移模块中基本的进程迁移部分的设计 与实现。第六章讲述s o c k e t 迁移部分的设计与实现。第七章对抢占式进程迁移模块进 行了功能和性能两方面的测试。第八章总结全文并对未来的工作进行展望。 9 华中科技大学硕士学位论文 2s o c k e t 迁移的背景 在第一章中分析了s o c k e t 迁移在高性能集群计算中的应用需求，本章主要介绍 s o c k e t 迁移的背景。主要包括连接状态s o c k e t 迁移的实现途径以及以往的s o c k e t 迁移 系统在迁移监听状态s o c k e t 时所遇到的问题。 2 1 s o c k e t 迁移的一般定义 s o c k e t 迁移的定义口2 ，3 3 1 是将一个连接状态的s o c k e t 的一端从一个结点传送到另外 一个结点，在传送过程中不能有任何数据包的丢失。s o c k e t 迁移可以包含两个方面的 内容，第一是在进程迁移过程中，支持将包含连接状态的s o c k e t 的进程，从一个结点 迁移到另外一个结点，进程迁移过程中这个s o c k e t 连接上的数据不能有任何的丢失。 s o c k e t 迁移也可以包含另外一个方面的内容，即s o c k e t h a n d o f f , 与前者不同的是，这 种s o c k e t 迁移只是将连接状态的s o c k e t 的某一端从一个进程迁移到另外一个进程。即 s o c k e t 被从一个进程h a n d o f f 到另外一个进程，而进程本身不迁移。同样，这个连接 状态的s o c k e t 在迁移过程中也不能有任何数据包的丢失。为了不至于将这两者混淆， 只将连同进程一起迁移的s o c k e t 迁移( 如上所述的第一种情况) 称为s o c k e t 迁移。而 将后者称之为s o c k e th a n d o f f os o c k e th a n d o f f 技术多应用于基于内容的网络服务器调 度系统中【3 4 ，3 5 1 。 2 2 s o c k e t 迁移的实现途径和相关系统分析 已有的s o c k e t 迁移的实现途径有两种，第一种为基于代理转发的s o c k e t 迁移，另 一种为基于端到端支持的s o c k e t 迁移。下面对这两种方法和采用这些方法的相关系统 进行简单介绍。 2 。2 1 基于代理转发的s o c k e t 迁移 基于代理转发的s o c k e t 迁移不需要关心底层协议的实现细节，因而实现相对比较 简单、直接。m o s i x 采用一种称为文件操作函数返回的方法实现了基于代理转发的 s o c k e t 迁移。m o s i x 中的s o c k e t 迁移实现如图2 1 描述。 1 0 华中科技大学硕士学位论文 如图2 1 所示，位于结点1 上的进程a 和位于结点2 上的进程b 之间存在s o c k e t 连接。当进程b 从结点2 迁移到结点3 时，m o s i x 的进程迁移系统会在结点2 上放 置一个代理进程。这个代