进程迁移研究.docx

计算机工程与科学com pu t er en g in e er in g & sc ien c ecn 8121166/t pissn 10072130x2001 年第 23 卷第 5 期v o l123, n o. 5, 2001文章编号:10072130x (2001) 0520047204进 程 迁 移 研 究s tu dy o n p ro ce s s m ig ra t io n庞毅林, 蒋翠玲pa ng y i- l in , j ia ng cu i- l in g(武汉理工大学计算机科学与技术学院, 湖北 武汉430063) (schoo l of com puter sc ien ce an d techn o logy ,w uhan un iver s ity of sc ien ce an d techn o logy,w uhan 430063, ch ina )摘要: 进程迁移在分布式系统中的应用, 提高了系统的负载平衡, 实现了高效的容错性能。 本文介绍了进程的状态迁移算法以及检查点的设置和其它状态的迁移技术。a bstra c t: t h e app lica t io n o f p ro ce ss m ig ra t io n in d ist r ib u ted sy stem s h a s im p ro ved sy stem lo ad b a lan c in g an d rea lized eff ic ien t fau lt to le ran ce1 t h e p ap e r in t ro du ce s th e a lgo r ithm o f p ro ce ss sta te m i2 g ra t io n an d th e se t t in g o f ch eckpo in t s, a s w e ll a s th e m ig ra t io n tech no lo gy o f o th e r sta te s1关键词: 进程迁移; 容错; 检查点; 实时系统key word s: p ro ce ss m ig ra t io n;中图分类号: t p 31614fau lt to le ran ce; ch eckpo in t; rea l t im e sy stem文献标识码: a(3) 减少网络通信负载。 当某一进程与其它进程存在通信, 而与其通信的相对较多的进程不 在同一主机上, 那么就将该进程进行迁移, 从而减少整个网络通信的负载。 进程迁移是分布式系统中一个重要的技术环节, 如何有效地进行进程迁移将是本文探讨的主 要问题。1引言在分布式操作系统中, 进程迁移是一项重要的技术, 可以满足系统的实时性, 提高系统的负 载平衡, 实现容错性, 减少通信负载。 其作用概 括起来主要体现在以下几个方面:(1) 实现高效率容错。 在分布式系统中, 当 一个主机发生故障时, 则需将该主机正在运行的 进程给予迁移; 否则, 如果主机正在运行的是某 些关键进程, 则这样有可能导致整个系统任务的 错误运行, 后果将不堪设想。(2) 提高系统的负载平衡。在特定的时间内, 各主机负载具有不确定性, 会出现负载不平衡。这 时通过进程迁移才能使主机实时地计算任务、 实 时地动态调度, 使系统内部真正达到动态负载平 衡和动态负载分担。2进程的迁移状态信息进程迁移以后, 只有收集了足够的状态信息才能重新启动进程, 使进程得到如同迁移之前的 环境, 因而状态的获取就显得至关重要。 它主要包括以下几点:(1) 虚拟内存空间: 大量的状态都和进程的 内存空间有关, 如代码、 数据和堆栈。(2) 执行状态: 包括进行上下文切换时有关收稿日期: 2001203218; 修订日期: 2001206207基金项目: 十五国防预研基金资助项目 ( 413160201)作者简介: 庞毅林 ( 1975- ) , 男, 硕士生, 研究方向为实时分布式系统和数据库管理系统; 蒋翠玲, 硕士生。通讯地址: 430063 湖北省武汉市武汉理工大学计算机科学与技术学院 59# ; t e l: ( 027) 86533564; e 2m a il: y ilinp ang 1631ne ta ddre ss: schoo l o f com p u te r sc ience and t ech no lo gy, w uh an u n ive r sity o f sc ience and t ech no lo gy, w uh an, h ube i 430063, p 1r 1c h ina的核心存储和恢复信息, 如寄存器的值、sp 指针。(3) 打开文件: 包括打开文件的内部标识、文 件访问的位置及文件缓冲块。(4) 其它内核信息: 操作系统存储进程的其它信息, 如当前的工作目录、 p id 和 u id 等。(5) 进程消息: 如果操作系统是基于消息的,其状态包括收和发的缓冲信息。将某些信息拷贝两次, 总的传输时间反而增长。4实时分布式系统中进程状态迁移算法前面的算法是假设源主机在没有故障的情况下, 将源进程挂起, 从而得以完成进程的迁移。如 果源主机发生故障, 迁移不能得到迁移进程的状态信息, 将导致失败。为了提高系统的可靠性, 采 用基于检查点的迁移技术, 将进程的状态信息保 存到永久存储器中, 使其减小时间开销, 达到实 时性。 这样在源主机发生故障的情况下, 可依据 检查点在新的主机重构进程, 使其从检查点处继续运行。 那么何时设置检查点、 如何设置检查点 则成为关键。3常见进程状态迁移算法在目前进程迁移算法主要有贪婪拷贝算法、惰性拷贝算法、 预拷贝算法等。 这几种算法的不 同点主要体现在以下三个方面;(1)(2) (3)需从源主机传输多少状态到目标主机?何时挂起在源主机上运行的进程?何时启动在目标主机上的进程?411检查点的设置目前, 检 查 点 的 设 置 主 要 采 用 两 种 方 式:各个进程独立设置检查点。 这种机制会产生311贪婪拷贝算法(ea ger copy)(1)先挂起源主机进程, 然后传输进程的全部状态 (包括一些打开的文件、 执行状态等) 到目标 主机后, 再启动目标主机进程。这种算法简单, 易多米诺效应, 一个进程卷回时, 可能会使与之通信的进程也卷回。 这两个进程相互卷回的最坏情 况可能使它们卷回到最初始的状态, 将开销大量 的时间, 这是实时系统所不能容忍的。 (2) 全局 设置检查点。 该机制使检查点在各个进程之间保持同步。 当一个进程设置检查点时, 其它全部进 程即便与该进程没有通信也要设置检查点, 这样 不但会产生时间延迟, 还会浪费大量的存储空间。 另外在卷回时可能产生活锁。为满足系统的实时响应, 避免独立设置检查点的多米诺效应, 以及弥补全局设置检查点的时 间开销很大与活锁的不足, 因而提出了一种新的 检查点策略, 即对于设置检查点进程通信的进程, 同时对其设置检查点, 从而保持通信进程间的数 据一致性, 其它进程将不予考虑。 这样减少了全局检查点的设置个数, 避免了单个进程独立设置 检查点的缺陷。 进程间通信通常以消息队列、 共 享内存、 信号、 管道等方式进行。 例如对于消息 队列方式的通信来说, 可通过在消息队列中增加 一个标志位, 当一个进程修改消息队列时, 就将标志位置 1。这样就很容易找到与之通信的进程,并为之建立检查点, 从而实现数据的一致性。 在进程迁移中, 为使目标主机尽快启动, 过多设置检查点将会降低计算机性能, 而过少又可 能会丢失重要信息。 某些系统在系统调用时设置检查点, 而频繁设置检查点对于实时系统将是不于实现, 但有不足: (1)系统是不可接受的; (2)延时较长, 这对于实时有些冗余数据传输到目标主机后, 实际并没有用上, 造成网络负担。312惰性拷贝算法(l a zy copy)先传输进程在目标主机上重新执行所需要的最小相关信息。 比起贪婪拷贝算法, 它传输的是 必需的最少量的状态集合, 然后在主机上启动。这 些信息通常是进程的部分或全部核心数据和一小部分 (二、 三页) 地址空间。 当进程在目标主机 上的执行需要其余状态信息时, 再传输这些信息。 其优点是延迟小、 网络负担少, 缺点是会导致对 源主机的剩余依赖性, 因此不能提高系统的可靠 性。313预拷贝算法(pre- copy)与前面两种算法不同的是, 预拷贝算法在进程的部分或全部地址空间从源主机到目标主机的 传输完毕时, 源主机才挂起进程并且传输核心数 据。 也就是说, 当进程在源主机上执行时, 并行传输地址空间到目标主机上; 进程挂起后在传输 的核心数据 (包括打开的文件、 执行状态、 当前 目录等) 和一些先前已经传输而后被改变的地址 空间一起传输到目标主机上。 这样就会产生一个 问题: 这种算法虽然降低了进程挂起的时间, 避免因挂起时间长而导致的开销和错误, 但是却会(2) 在迁移过程中, 源主机收到消息后转发给目标主机。那么迁移进程对源主机存在剩余依赖性。 一旦源主机发生故障, 迁移的进程将会受到影响。在迁移过程后, 常用消息重定位法、 消息丢 失保护方法、 消息丢失恢复方法等。 针对以上两 种通信方法的特点, 可采用另一种进程通信迁移 方法。 该方法要求源主机上的进程在迁移之前通 知其它进程, 同时发送消息给源主机上的进程和目标主机上的进程。如果在目标节点恢复之前, 则 其它进程发送的消息在目标主机暂存; 进程恢复 后从目标主机缓存中取出消息。 该方法能克服在 迁移进行中的不响应, 实现了实时性; 同时也克 服了在迁移后对源主机的剩余依赖性。利的。 对于这个问题, 可通过以下两种策略来决定何时设置检查点:(1) 在被控系统的一个控制周期结束后进行 保存, 这样可减少检查点的个数。(2) 在系统写调用后保存 (读调用由于不改变数据, 其状态没有发生改变不设置检查点) , 这 样将减少系统调用对检查点设置的影响。同时, 在每个页表中增加一个修改标志位来检查最后一次设置检查点后被修改的页, 在新检 查点设置后, 如果某个页的修改标志位被设置, 只需对该页进行保存。 这样可以避免设置冗余的检 查点, 也保证了信息不丢失。412基于检查点的算法实时分布式系统中, 进程迁移在两种情况下 进行: ( 1) 源主机正常运行的情况下, 进程迁移主要是为了动态负载平衡, 减少网络通信负载; ( 2)源主机发生故障的情况下, 进程迁移主要是为了 提高系统的可靠性。 结合前面检查点设置策略的优缺点, 第一种情况下的状态迁移算法是:( 1) 在源主机运行的同时, 把最近检查点中最少量、必需的 信息从源主机传送到目标主机;( 2) 如果有新的检查点建立, 则转向 ( 1) , 否则执行下一步;( 3) 根据状态信息在目标主机上重构进程, 然后挂起源主机 上运行的进程, 传输被修改的 “脏”页到目标主机;( 4) 重新启动在目标主机上的新进程和源主机上的原进程;( 5) 通过一定的策略, 比较源主机进程和目标主机进程是否 一致。如果不一致, 源主机则转向 ( 1) , 否则传输其它信息, 退出源主机进程。该算法与前面所述的算法相比, 利用检查点 保存进程信息, 减少了源主机挂起的时间, 在进 程运行时, 并行从检查点传输状态信息; 在进程 挂起后, 传输 “脏”页。 由于 “脏”页的数据相 对较少, 能减少对事件的延迟, 能较好地实现系 统的实时性和容错性。如果在源节点有故障, 则直接从检查点提取 进程的状态信息, 在目标机上重构进程, 从检查 点处继续运行。打开文件的迁移6打开文件的迁移主要包括文件标识符、 文件缓冲区和文件访问位置。 通常采用两种方法:(1) 用文件的转发: 当迁移后的进程有内核 调用时, 转发到源主机上。 这样频繁的内核调用 和转发内核在网络上的开销, 将放慢远程进程的 执行, 同时装载源主机的文件状态, 这对于实时 系统是不可接受的。(2) 采用文件服务器: 这使该系统共享文件 系统。 首先从源主机打开文件信息, 通知目标主 机, 然后目标主机通知文件服务器打开的文件已 经被转移, 文件服务器获取最新的文件状态信息, 同时释放源主机的文件状态信息, 从而为目标主机服务。通过对上述两种方式的比较可以看出, 文件 转发存在剩余依赖性, 而文件服务器使文件访问 具有透明性。 因此, 在实时分布式系统中, 为了 提高容错性, 宜采用文件服务器的方式。7结束语5进程通信的迁移本文对进程迁移中的关键技术从检查点的设置、 状态迁移、 进程通信迁移、 打开文件迁移等 方面进行了讨论。 检查点的设置避免了多米诺效应及活锁。 利用检查点对进程状态保存, 提高了系统的可靠性, 同时减少了延迟。 对通信迁移和 文件的迁移也避免了对源目标主机的剩余依赖 性, 能较好地满足实时分布式系统的容错性和实时性。进程通信迁移主要包括迁移过程中的通信和迁移过程后的通信。 其 中 迁 移 过 程 中 的 通 信 有 以 下 两 种 方 法:(1) 在迁移过程前, 迁移的进程通知其它进程不 再发送任何消息给该进程, 即迁移进程不与其它任 何 进 程 通 信。 该 方 法 显 然 不 适 合 实 时 系 统。始状态到系统的故障状态共有 4 条转移链。 假定参考文献:部件故障率均为 21510- 6 /h ,由公式 (1) 就可1袁由光 1 实时系统中的可靠性技术 m .版社, 19951北京: 清华大学出求出任意时刻 t 系统发生故障的概率为:t = 10h 时, 系 统 处 于 故 障 状 态 的 概 率 为2d o ug lis f , o u ste rho u t j. t ran sp a ren t p ro ce ss m ig ra t io n:d e sign a lte rna t ive s and th e sp r ite im p lem en ta t io n j . so f tw a re2p rac t ice and e xp e r ience, 1991, 21 ( 8) : 757- 7851l i k , n augh to n j f , p lank j s1r ea l2t im e co ncu r ren t c h ec2kpo in t fo r p a ra lle l p ro g ram s j 1a cm s igpl a n n o t ice s,1990, 25 ( 3) : 79- 88.a r t sy y, f ink e l r. d e sign ing a p ro ce ss m ig ra t io n f ac ili2t ie s: t h e c h a r lo t te e xp e r ience j . ie e e com p u te r, 1989,22 ( 9) : 47- 56.- 911249 9710 ; t = 100h 时, 概率为 11249 6910- 7;= 10t = 1 000h 时, 概率为 11246 8810- 5; t3概 率 为 11218 83 10- 3;000h 时,t =100 000h 时, 概率为 91546 4110- 2。图 6 中从初始状态到系统的故障状态共有 44条转移链。由公式 (1)发生故障的概率为:就可求出任意时刻 t 系统5陆桑璐, 谢立. 进程的动态迁移技术 j .计算机研究与发t = 10h 时,21368 4810- 15;系 统 处 于 故 障 状 态 的 概 率 为t = 100h 时, 概率为 11657 93展, 1997, 34 ( 9) : 646-651.- 14- 1010; t = 1 000h 时, 概率为 11939 5210;(上接第 38 页)定量计算的方法虽然在理论上是可行的210 000h 时, 概 率 为 11821 36 10 ; t =- 6t =, 但随- 3100 000h 时, 概率为 91852 0310 。由计算结果可以看出, 在同一时刻, 带有公 用备件库的系统的可靠度比无公用备件库的系统至少提高一个数量级。着动态故障树规模的增大, 其相应的马尔科夫状态转移图中状态数目呈指数增长, 马尔科夫转移 矩阵的维数相应增加, 以至求解耗时过长, 失去了 计算的意义, 甚至根本无法计算。为 此, 下 面 我 们 给 出 一 种 简 便 的 计 算 方 法 状态转移链法。为了避免应用方程组, 可将状 态转移图分解成若干条状态转移链, 根据不同链的长度, 分别利用不同的计算公式, 然后综合各条 链的结果, 便可得到整个系统的可靠度 (或系统发生故障的概率)。我们不妨假设, 系统在瞬时 t 的故障只是通 过一条转移链到达故障状态, 而不可能同时通过两条或两条以上的链到达故障状态。 因此, 系统 发生的故障概率 (不可靠度) 即为所有转移链发生的概率之和。对于图 7 中链长为 n 的状态转移链 t n 的计 算公式由 (1) 给出。4结束语本文在故障树模型中引入带公用条件的备件逻辑门, 介绍了这种逻辑门转化为马尔可夫链的 方法, 扩展了传统故障树对容错系统可靠性分析的适用性。 文中例证表明, 在同一时刻, 带有公用备件库的系统可靠度比无公用备件库系统的至 少提高一个数量级。参考文献:1d ugan j b , b avu so s, bo ud m . d ynam ic f au lt t ree m o de lsfo r f au lt t o le ran t com p u te r sy stem s j . ie e e t ran s o nr e liab ility, 1992, 41 ( 3) : 363- 377.姚一平, 李沛琼, 等 1 可靠性及余度技术 m . 北京: 航空工 业出版社, 19911r en yan so ng, d ugan j b. d e sign