基于Linux的进程迁移机制设计

基于Linux的进程迁移机制设计来源：引言进程迁移在集群和分布式系统中发挥着相当重要的作用。通过将进程从负载较重的系统移动到负载较轻的系统,负载就会得到平衡,从而改善整体性能。进程迁移的算法直接影响着进程迁移时间,目前流行的几种迁移算法有Total2Copy、Demand2Page和FileServer,从表1中我们可以看到,在以这些算法为基础的系统中,进程迁移时间都比较长,这影响着系统的性能,因此有必要对迁移算法做出改进以提高迁移速度。本文在分析和比较了目前已有的几种迁移算法后,提出了改进的进程迁移算法,并在这个算法的基础上设计了基于Linux操作系统的进程迁移机制,实验结果证明这一迁移算法有效提高了进程迁移速度。表1部分进程迁移系统比较表操作系统迁移算法网络迁移100kB进程耗时/msSpriteFileServerEthernet10M330MachOMSDemandPageEthernet10M250MDXTotal-CopyEthernet10M3602进程迁移的基本概念进程———这是操作系统中的一个关键概念。它包括:数据、堆栈、寄存器内容,以及与下层OS直接相关的特定状态信息。进程迁移———就是在源节点和目的节点之间移动一个进程。被传送的进程状态包括进程的地址空间、执行状态、通信状态以及其他一些与OS相关的信息。进程迁移时间———进程从在源节点上被挂起直到在目的节点上恢复执行之间的时间段,也叫迁移延迟时间。3进程迁移算法3.1已有算法的分析Total-Copy算法首先在源节点上挂起要迁移的进程,然后将进程的全部状态信息传送到目的节点,再由目的节点恢复迁移后的进程。Demand-Page算法一开始只传送进程的执行状态、通信状态,进程的地址空间保留在源节点上,然后恢复进程的运行,目的节点仅在需要访问某些页时才请求之。FileServer算法引入了第三台机器———文件服务器,它和Demand-Page算法类似,一开始也是传送除进程地址空间之外的进程状态信息给目的节点,然后将进程地址空间所涉及的内存页传送到文件服务器,之后恢复进程的运行,目的节点发生缺页时向文件服务器申请相关页。通过比较Total-Copy和Demand-Page可以发现它们处于两个正好相反的极端,前者是非常积极主动地一次发送完所有需要的内存页后再执行,后者是非常消极地让源节点等待目的节点上的进程来请求每一个内存页。事实上,我们完全可以把二者的思想进行折中,即:在迁移过程中,让源节点只积极地发送一部分地址空间,这样可以防止迁移完成后的进程立刻遇到缺页中断。然后我们还可以借鉴FileServer算法的思路———把其余的地址空间发送到文件服务器上,从而立刻减轻源节点的负荷。进程迁移到目的节点后并不会一直运行,当它的时间片用完或是它在等待某些IO操作完成时会将处理器让出,我们完全可以利用这些时间进行剩余地址空间页面的传送,而不必等到发生缺页时再传。3.2迁移算法描述算法流程描述如图1所示。首先挂起要迁移的进程。源节点将进程的控制和运行状态信息整理为一条消息并发送给目的节点。目的节点决定是否接受迁移,并向源节点发送同意或反对消息,如果同意,源节点开始发送“当前”代码页、堆页、栈页。我们由局部性原理可知,目的节点一旦接收到当前代码页,就可以立即恢复进程的执行———而且不会立刻发生缺页中断。源节点发送完当前页后,继续工作(这时源节点的后续迁移工作和目的节点上的进程运行也就并行起来了):最后将进程地址空间的其他页面发送到文件服务器(FileServer)上。目的节点在恢复完进程的执行后,继续在后台从文件服务器上接收进程其它地址空间的页面。进程恢复执行一定时间后,会需要访问其他的内存页,如果发现需要访问的内存页不在,就向文件服务器上请求。图1改进后的进程迁移算法数据交换流程该算法只积极发送当前页,而大量的页面都在以后发送给FileServer,尽可能减少了进程迁移延迟期间所传递的信息量,有效地减少了迁移延迟。后台继续接收进程其它地址空间的页面,这在某种程度将程序的运行和地址空间的传送并行起来,可以减少进程迁移后缺页的发生次数,从而加快进程运行的速度。4进程迁移机制的设计我们来分析一下一个进程迁移机制应该有哪些功能模块。一次进程迁移操作的必须步骤是将被迁移进程的状态从源节点传送到目的节点,因此需要发送和接收进程状态的功能模块;进程迁移的命令可以由人发出,也可以由“分布式调度”模块(它的主要任务就是决定何时将哪个进程迁向哪里)发出,这需要进程迁移机制提供一个调用接口。这几个功能模块的设计框图如图2所示,MigrateClient负责发送进程状态,MigrateServer负责接收进程状态,Mig2Operation提供调用接口。图2进程迁移机制结构MigrateServer是多线程(这里的线程指的是内核线程)服务器,由一个主线程等待在预先定义好的端口上,收到迁移请求后就交给线程池中一个线程处理,主线程又返回继续接收新请求。主线程在系统启动时就开始运行,它预创建一些处理线程,然后就开始在预先指定的端口上等待迁移请求,当请求到来时主线程把请求挂入请求队列,唤醒那些正在等待请求到达的处理线程,此后主线程又回去继续等待请求到达。处理线程检查队列上是否有请求存在,如果没有,处理线程睡眠,当被唤醒时再度检查。如果发现队列上有请求存在,就从队列上摘下该请求并处理之。处理线程也是一个内核级线程,主要完成以下操作:(1)用alloc-task-struct()函数获取8KB的uniontask-union内存区域;(2)预先分配需要接收的三个当前页;(3)将自己挂起;(4)被主线程唤醒后处理迁移请求,它接收被迁移进程的状态信息并用此初始化(1)中分配的相应结构单元,然后接收被迁移进程的三个当前页;(5)在初始化相应的进程结构后将其放到运行队列中,之后调用schedule(),以使被迁移进程有机会马上运行;(6)当该线程重新被调度后,从FileServer上继续接收被迁移进程的其它地址空间,接收完毕后,重复步骤(1)。在Migrate-Server的设计中,通过在迁移请求到来之前采取相关资源预分配和线程池策略来减少进程迁移过程中这些步骤带来的延时。Migrate-Client的主要任务是负责发送迁移进程的状态信息,在一个进程返回用户态之前,内核将检查该进程是否需要迁移,如果需要迁移的话,内核将此进程挂起,然后唤醒Migrate-Client。Migrate-Client与Migrate-Server建立网络连接并传送进程的状态信息。Migrate-Client采用单线程的方式,因为进程迁出一般发生在系统负载过重的情况下,如果此时再开多个线程进行迁移,势必会进一步增加系统的负载。5实验结果实验环境是:3台Linux工作站,每台配置为Cerelon667MHz处理器和128MB内存。工作站之间由10Mbps以太网连接。一台作为源节点,一台作为目的节点,一台作为FileServer。由于无法重复表1中的实验环境,为了进行比较,我们将Demand-Page算法作为一个选项实现在系统中,没有加入Total-Copy和FileServer算法的原因是因为这两种算法在恢复进程执行前将传送进程的全部进程状态信息,这在时间上将肯定长于传送部分进程状态信息的Demand-Page算法和改进算法。最后,我们编写了运行时大小约为100KB的测试程序进行迁移测试,测试结果如图3所示。图3实验数据结果从实验结果可以看出,改进算法的迁移时间绝大多数在130ms左右。Demand-Page算法的迁移时间大都在110ms左右,改进算法略慢于Demand-Page算法的主要原因是改进算法要比Demand-Page算法一开始多传送三个页面。表面上看,改进的算法的迁移时间不但没缩短,反而变长了,在分析之后会发现其实不然,Demand-Page算法事先没有传送进程的当前页,因此进程恢复执行后会立刻发现缺页,于是马上又被挂起然后向源节点请求页面,这时进程并没有真正开始执行。在改进算法中,由于当前页已在进程恢复运行前被传送,进程恢复运行后将不会立刻缺页,从而开始执行。通过分析可以看出,改进算法进程真正开始执行的时间是早于Demand-Page的。除此优势之外,改进算法会在目的节点后台接收进程其余页面,势必会减少迁移后进程的缺页请求,这也将加快进程的执行,这一优点也是其它算法所不具有的。6结束语改进的进程迁移算法汲取了几种现有迁移算法的优点,并最大程度的使进程状态的传送与进程的运行并行起来,从而提高了迁移速度。在此算法基础上我们还设计了一种新的进程迁移机制,在设计中,通过采用线程池与预分配资源的策略,减少了进程迁移中不必要的时间损耗。