进程迁移技术可以将正在运行的进程在一组机器之间自由迁移，是分布式系统中实现动态负载均衡、增强容错、减少通信开销等的关键技术^[1].进程迁移分为静态迁移和动态迁移两种，其中进程动态迁移由于具有用户体验好、效率高、灵活度高等优点而被广泛使用.各种集群、网格以及云计算模型，如MOSIX，Sprite，欧洲数据网格(data grid)，微软System Center等，均采用适合自身体系的进程动态迁移算法来提高系统的工作效率和稳定性.

现有迁移算法虽各具优点，但也都存在着明显的缺陷.Eager-copy算法^[2]是最早提出的进程迁移算法，其成功实现了进程的动态迁移，但过长的冻结时间是该算法的致命伤.Zayas提出的Lazy-copy算法^[3]解决了进程冻结时间过长的问题，但后续运行时会发生大量缺页错误，严重影响进程恢复执行后的效率，并且该算法对源节点的依赖度非常高.目前使用最广泛的是预拷贝算法(Pre-copy)以及后拷贝算法(Post-copy).Pre-copy算法具有较短的冻结时间而且能够保证进程恢复运行后的执行效率，Clark等将其应用于XEN虚拟机迁移^[4]，陈阳等提出了基于内存混合复制方式的虚拟机实时迁移机制HybMEC(hybrid memory copy)，进一步提升了迁移的效率^[5].其缺点是在下达迁移指令后很长时间才能释放源节点计算资源，而且在迁移频繁读写内存的进程时，脏页面多次重复迁移，加重了网络传输的负担，同时还存在收敛性问题，大大延长了迁移总体时间.Post-copy算法具有较短的冻结时间，并且能够在较短的时间内在目标节点上恢复进程执行^[6].但在进程恢复执行时地址空间极度不完整，因此经常发生缺页错误(page faults)而导致进程被挂起，影响了恢复运行后的效率^[7].

针对现有各迁移算法的不足，本文提出了Pre-record算法.该算法利用源节点对进程进行一定时间的预处理并记录该过程中处于活跃状态的内存页面，以此对进程在恢复运行初期将要访问的内存页面进行预测.在接下来的迁移阶段，这些被记录的页面会被优先迁移，保证进程在目标节点上恢复运行后的最初阶段不会发生缺页错误，减少整个迁移过程中发生缺页错误的几率.该算法同时还保持了冻结时间较短、不增加网络负载的优点，同时保证了进程恢复运行后的流畅度.

进程迁移算法的优劣主要取决于3个方面:①尽量缩短进程从在源节点挂起到在目标节点恢复运行这段冻结时间；②降低迁移后对源节点的依赖程度(剩余依赖性^[8])；③进程恢复运行后保持执行效率.在设计算法时应综合这三方面进行考虑.

为了缩短进程的冻结时间，Pre-copy算法和Post-copy算法采取了截然不同的两种方式.考虑到分布式系统实施进程迁移的主要原因之一是需要降低节点负载，因此需要尽快将进程迁出，而Pre-copy算法中进程会在源节点运行直到迁移结束，相比之下，Post-copy算法仅迁移最小核心数据即恢复进程运行，源节点负载在最短时间内得到释放，更加符合系统需求.

在地址空间不完整的情况下恢复被迁移进程的运行，难免会发生大量的缺页错误，导致进程频频被挂起，严重影响进程恢复运行后的执行效率，目前主要的解决方法是对进程即将要访问的内存页面进行预测，然后优先发送预测页面.常用的预测方法是分析进程在目标节点恢复运行后的执行过程中在地址空间留下的足迹，大致推断出进程下一步将要访问的内容，其中比较有代表性的有Pre-Paging算法^[7]与AMPoM算法^[9]等.这类算法存在以下缺陷：①只能对进程将要访问的内存页进行概率性的预测，并不能保证预测结果的准确性；②进程恢复运行的初期是缺页错误发生的最高峰，这些预测算法需要进程执行一段时间以收集足够的推断依据，在高峰期里几乎无法发挥效用；③当预测算法发挥效用时，进程地址空间已经趋于完整，预测算法的效用大打折扣.

对进程迁移的过程进行分析可以看出，迁移后进程在目标节点的执行可以看作是其在源节点上执行的延续.如果源节点将进程地址空间数据同步至目标节点之后仍旧继续运行该进程，源节点与目标节点将处理同样的进程流程，访问同样的内存页面，见图 1a.如果源节点选择继续执行进程并同时在后台完成同步进程地址空间数据的工作，见图 1b，由于迁移过程的存在，进程在源节点与目标节点上的执行将会存在时间差，可以利用这个时间差，将进程在源节点上所访问的内存页优先迁移至目标节点，当进程在目标节点上恢复运行时，就已经获得了所需内存页，从而避免了进程恢复运行初期缺页错误的发生.

图 1(Figure 1)

Fig. 1

图 1 内存页Pre-record算法原理示意图 Fig. 1 Schematic diagram of memory pages Pre-record algorithm (a)—源节点不释放进程； (b)—在保持进程执行的同时迁移进程核心地址空间.

根据上述原理，提出内存页预记录算法(Pre-record算法).算法工作流程如下：在做出将进程迁出的决定后，源节点开始将核心地址空间迁移至目标节点，与此同时保持进程正常执行，并记录进程执行时所访问的内存页地址信息，存入预设的被访问内存页记录表(DirtyPage_Map)中.DirtyPage_Map中存放被访问内存页面的原始信息，而不是被进程修改过的内容.当核心地址空间被迁移完毕后，源节点将进程挂起，首先迁移DirtyPage_Map中记录的内存页面，然后再迁移剩余内存页，并随时响应目标节点发送过来的缺页请求，直至地址空间完全迁移完毕.

Pre-record算法具体流程如图 2所示.

1) 源节点与目标节点达成迁移协议.将该时刻记为t₀，如图 2中所标示.

图 2(Figure 2)

Fig. 2

图 2 Pre-record算法工作流程示意图 Fig. 2 Pre-record algorithm working flow

2) 源节点将进程的核心地址空间迁移至目标节点，然后立即在目标节点上恢复进程的运行.迁移完毕的时间记为t₁.

3) 在t₀至t₁这段时间内，源节点保持进程的执行，并创建DirtyPage_Map表，依照被访问时间将在这段时间内所访问过的内存页面、堆栈等信息按序记录其中.

4) 在t₁时刻，进程核心地址空间迁移完毕，源节点挂起进程，目标节点创建一个空进程，将所接收到的内存页面写入该进程的相应位置中并开始恢复进程的执行，进程地址空间的其他内存页面暂时保持空白.

5) 由t₁时刻开始，源节点依照记录的顺序将DirtyPage_Map表中的页面依次推送至目标节点，直至t₂时刻所有预记录页面传输完毕.在对进程地址空间进行迁移的过程中，源节点会将进程地址空间以内存页为单位封装成一系列4 KB或8 KB大小的数据包，迁移时顺次发出，目标节点接收到这些数据包后依次写入地址空间相应位置中.

6)t₁时刻进程在目标节点上恢复运行后，首先将会重新执行源节点在t₀至t₁这段时间内的执行过的那部分过程，其所需要访问的内存页等信息正是DirtyPage_Map表中的记录.目标节点在进程执行的同时，在后台接收源节点发送过来的DirtyPage_Map表数据，存入本地相应位置中.

7) DirtyPage_Map表中所记录内存页在t₂时刻完全迁移完毕，源节点继续迁移进程剩余地址空间.若目标节点在执行进程过程中需要访问某一内存页面，却没有命中，系统产生一个缺页错误，挂起进程并同时向源节点发送缺页请求.源节点在推送地址空间页面的同时持续监听来自于目标节点的缺页请求，在监听到缺页请求后，会暂时中断当前发送动作，优先对该请求进行回应，将所请求页面发送至目标节点，然后继续原来的发送序列.目标节点接收到所缺页面后恢复进程的运行.

8) 在t₃时刻，进程地址空间完全迁移完毕，目标节点可以脱离源节点的辅助独立运行该进程，源节点删除该进程的所有信息，释放其所占用资源，整个迁移工作完成.

Pre-record算法具有较短的进程冻结时间.虽然在t₀至t₁这段时间里进程在源节点上处于执行状态，但这段时间内的执行结果并不会被迁移至目标节点，当目标节点在t₁时刻恢复进程的执行时，继承源节点上t₀时刻进程执行的结果继续执行，因此t₀至t₁这段时间可视为进程冻结时间.这段时间里系统完成迁移进程核心地址空间的工作，进程核心地址空间只占整体地址空间很小的一部分，在短时间内即可迁移完毕，进程也将在短时间内开始恢复执行.

Pre-record算法将显著降低缺页错误发生的几率，保证进程恢复执行后的执行效率，由于预记录内存页的存在，在进程恢复执行初期基本不会发生缺页错误，而且在这段时间里，源节点仍旧在后台不断迁移剩余地址空间.当进程将预记录的内存页访问完毕时，更多的地址空间页面已经被迁移至目标节点，使得进程地址空间得到了进一步的完善，进程继续执行时发生缺页错误的几率也会降低.

Pre-record算法的不足之处是对源节点的计算资源有些许浪费.在源节点迁移核心地址空间时，保持进程继续运行，而这段时间的运行结果最终并没有被迁移至目标节点，因此进程恢复运行后仍需要重新执行该段处理过程，如图 3所示.这段重复执行的过程不会很长，将对计算资源的浪费限制在可接受的范围内，与其对进程迁移效率的提升所起的贡献相比总体上来说还是利大于弊的.

图 3(Figure 3)

Fig. 3

图 3 进程部分执行过程在目标节点上需重复执行 Fig. 3 The same phase of the migrated process is executed twice by source node and destination node

对进程迁移算法工作效率的评价是一个比较复杂的问题，应该将多方面的因素综合起来进行对比分析.本文根据文献[10]将分别从冻结时间、停止时间、网络负载以及剩余依赖性等几个方面对Pre-record算法性能进行评估，结果如表 1所示.

表 1

Table 1

表 1(Table 1)

表 1 进程迁移算法比较 Table 1 The comparison of process migration algorithms 算法名称 冻结时间 停止时间 网络负载 剩余依赖性 Eager-copy 高 非常低 中 否 Lazy-copy 低 高 低 是 Pre-copy 中 非常低 高 否 Post-copy 低 中 中 否 Pre-record 低 低 中 否

表 1 进程迁移算法比较 Table 1 The comparison of process migration algorithms

从比较结果可以看出，Pre-record算法在完成核心地址空间数据的迁移之后便恢复进程的执行，其冻结时间非常短暂.并且由于预记录页面的存在大大降低了进程恢复执行后发生缺页错误的几率，进程恢复运行后比Post-copy算法的停止时间更少.在网络负载方面，Pre-record与Post-copy及Eager-copy算法同样需要完成整个地址空间的迁移工作，网络负载相似.Pre-record算法具有剩余依赖性较低的优点.由此可见Pre-record算法的综合性能更加优秀.

通过仿真程序对进程迁移的过程进行实验，评估Pre-record算法对迁移效率的影响.仿真程序创建一个以预定频率随机读写内存的进程，将其在不同的主机之间进行迁移并对各项数据进行记录，以Post-copy算法作为主要参照对象.

分别对Post-copy算法及Pre-record算法进行仿真，并对仿真过程中发生缺页错误的时间与所缺页的地址进行记录，进程地址空间总大小为32 Mb，实验结果如图 4所示.

图 4(Figure 4)

Fig. 4

图 4 Post-copy和Pre-record算法中缺页错误分布情况 Fig. 4 The distribution of page faults of Post-copy and Pre-record algorithms

从图 4中可以看出，进程在目标节点上恢复运行的初期，缺页错误的发生数量最多，这是由于进程地址空间极度不完整造成的.随着时间的推移，进程地址空间不断被补充完整，缺页错误发生几率也逐渐降低，当地址空间完全迁移完毕后不再发生缺页错误.在采用Pre-record算法进行迁移的实验中，进程恢复运行初期由于预记录页面的存在，在发送预记录内存页面阶段不会发生缺页错误.当进程对所有预记录页面访问完毕后，进程地址空间已经更加完整，发生缺页错误的几率进一步降低，整个迁移过程中缺页错误的总数显著减少，整个迁移过程也会在更短的时间内完成.

设置实验进程每50 ms对地址空间进行一次随机读取，网络延时在10~70 ms的区间内变化，观察在不同的网络条件下Pre-record算法的效率，并与Post-copy算法进行比较.实验进程地址空间32 Mb，在Pre-record算法中预记录地址空间大小为3 Mb，实验结果如图 5所示.

图 5(Figure 5)

Fig. 5

图 5 在不同网络延迟状态下缺页错误次数 Fig. 5 The page faults under different network delays

从实验结果中可以看出，在不同的网络延迟条件下Pre-record算法均可以明显减少缺页错误的发生率，具有比Post-copy算法更高的迁移效率.并且对于同一个程序来说，网络传输速度越快，Pre-record算法迁移效率越高;在相同的网络传输速度下，对内存读取不频繁的程序会比读取频繁的程序获得更好的迁移效率.

通过调整预记录页面占总进程地址空间的比例，实验观察预记录内存页面的大小对Pre-record算法效率的影响.实验中设置进程地址空间为32 Mb，传输数据时间为10 ms，进程访问内存间隔为30 ms，预记录页面占总进程地址空间的比例分别为0，5%，10%，15%，20%，25%，30%，实验结果如图 6所示.从实验结果可以看出，随着预记录内存页面数量的增多，发生缺页错误的次数越少，进程执行所需的时间越短.由此可以看出预记录页面的存在可以明显提高迁移效率.

图 6(Figure 6)

Fig. 6

图 6 不同预记录页面比例缺页错误的次数 Fig. 6 The number of page faults under different percentage of pre-recorded memory pages

本文以降低进程迁移过程中缺页错误的数量为目标提出Pre-record算法，考虑到进程在两个节点间的执行具有延续性，源节点利用迁移进程核心地址空间的这段时间，对进程进行短时间的预处理，记录活跃内存页地址并优先传输.实验结果表明，该算法可以有效降低缺页错误的发生率，进而提高迁移整体效率.该算法也可应用于虚拟机在线迁移，并为异构系统间的进程迁移提供更优的解决方案.