由于预拷贝迁移算法的迭代拷贝过程存在重复地拷贝同一个内存页的问题，从而导致拷贝内存页数量的增加和总迁移时间的延长。对脏页拷贝策略进行改进，将修改频繁的脏页在停机拷贝阶段传输，从而有效地缩短总迁移时间。然而该策略的改进又导致停机拷贝阶段的页面增多而引起停机时间延长，于是采用LZO压缩算法将停机阶段待拷贝的页面先压缩再传输，通过降低待传输的数据量来缩短停机时间。在进行虚拟机迁移实验时，与预拷贝迁移算法相比，结果表明该算法在未延长停机时间的同时，缩短了总迁移时间，尤其是在高脏页率环境下，该算法明显表现出更优的迁移性能。
90 016,52(23 Computer Engineering and Applications计算机工程与应用 主机上开启的时间,如图1中T所表示。由于宕机会 带宽大小不足时,迭代拷贝过程中每一轮拷贝的 导致虚拟机与1O等设备的连接中断,将引起服务质量脏页数量有限,应优先传送修改率低的脏页,而尽量多 下降或问断,因此,在虚拟机迁移的过程中,应尽可能地地将修改率高的脏页留到停机拷贝阶段,因而在设定n 缩短停机时间 和k的取值吋,应选择将内存页标示为修改频繁的概率 (2)总迁移时间,指虚拟机从源主机发起迁移请求大的方案,例如设定为n=4,k=2时,内存页在4轮拷贝 到在目的主机上恢复正常运行的时间,其长短主要受内中修改2次以上就认为修改频繁,则将其留到停机拷贝 存的送代拷贝过程影响,如图1中Tm所表示。由于阶段 在虚拟机迁移的整个过程中,虚拟机正常运行的同时需 当带宽大小充足时,虽然迭代拷叭过程每一轮拷贝 要颔外地进行数据的传输,势必引起虚拟机应用性能的足以传送完:一轮产牛的脏页,但出于降低传送数据量 下降,因此,应在考虑带宽的约束条件下合理地缩短总的目的,仍存在少量修改概率过高的脏页需要留到停机 迁移时间。 拷贝阶段,因而在设定n和k的取值时,选择的方案将 内存页标示为修改频繁的概率不宜太大,以免对停机拷 2内存预拷贝迁移算法的改进 贝造成压力,例如设定为n=4,k=3时,内存页在4轮拷 21改进脏页的拷贝策略 贝中至少修改3次才认为修改频繁,则将其留到停机拷 虚拟机内存的预拷贝迁移算法相比于静态迁移算贝阶段。 法极大稈度地缩短了停机时间,使整个迁移过程对外表 通过将修改频繁的内存贞在贞位图 to send last中 现出虚拟机未中断运行,但同时预拷贝迁移算法也引入标识,从而留到停机拷贝阶段再进行拷贝,可以有效地 了不可忽视的问题,即在预挎贝阶段迭代拷贝时,重复减少修改频繁的内存页被重复地拷贝,并降低每一轮拷 地拷贝同一个内冇脏页而增加传输的数据量,必然导致贝需要传输的数据量;同时在后续的拷贝中不用再考虑 总迁移时间的延长和迁移数据量的增加,进而加大系统该内存页是否会被再次修改,相当于降低了内存脏页 的开销。出现这个问题是因为脏页拷贝策略本身存在率,使内存脏页数H快速收敛到停机条件,因此,迭代拷 的缺陷,选择将某个內存页作为脏页进行拷贝传输的原贝过程所需的时间缩短,进而缩短虚拟机迁移的总迁移 则如下,如果某个内存贞在上一轮拷贝中被修改,而在时间。 本轮拷贝到当前为止还未被修改则将其拷贝到目标域,2.2压缩停机拷贝的脏页 由于后续的迭代拷贝中该内存页会被再次修改,该内存 对脏页的拷贝策略进行改进后,通过新增页位图 页就需要再次被拷贝。尤其是在密集型负载的环境下, to send last不仅可以降低内存页的重复拷贝,还可以加 出于内存页的修改频率普遍较高内存页需要被重复拷快收敛速度更早地进入停机拷贝阶段,但是在页位图 贝的机会就变得更大,内存脏页数量很难收敛到设定的 to send last中标识的内存将留到停机拷贝阶段再拷 值,往往需要很多轮的迭代拷贝,甚至要迭代拷贝达贝传送,需要传输的数据量与原来的内存预拷贝迁移算 釗上限轮数才被迫进入停机拷贝阶段,从而使内存预拷法相比必然有所增加,而网络带宽的大小却是有限的, 贝的效果大打折扣,造成内存预拷贝迁移整体性能的大于是将造成停机时间的延长,影响虚拟机的迁移性能。 幅下降。 因此,需要对停机拷贝阶段待拷贝的内存页进行压缩处 针对内存脏页在颜拷贝阶段中存在的述问题,对理,使停机时间缩短来保评虚拟机对外表现为不间断 脏页的拷贝策略进行以下改进:新增一种名叫 to send运行。 last的脏贞位图,用来标示在内存预拷贝阶段修改频繁 在内存迁移过程中,要求内存页数据完整地拷以到 的内存页,并将这种内存页留到停机拷贝阶段再拷贝到目的主机,于是在停机阶段对需要拷贝的页面进行处理 H的域。在内存预拷贝过程中,内存页是否需要在脏页时,必须选用一种无损压缩算法。其次,停机时间要求 位图 to send last中标示的具体判定如下,如果某内存尽可能得短,然而压缩算法本身存在开销,选择压缩算 页在n轮拷叭中出现k次以上被修改,就认为该内存页法时必须考虐开销。本文采用 Lempel-∠iv- Oberhumer 被频繁地修改,并将其在页位图 to send last中标识从(LZO)压缩算法,LZO算法为无损压缩,具有压缩与解 而留到停机拷贝阶段再进行拷贝。其中,n和k的取值速度快、开销小的优点,并且在压缩过程中压缩率修 大小决定着修改频繁的内存贞的判定精度,当n一定改方便,在内存压缩中具有广泛的应用。 时,k值越小意味着被标示为修改频繁的内存页的概率 为使内存的压缩操作对停机时间不造成太大影响, 越大;k值越大意味着被标示为修改频繁的内存页的概可以专门从内核中预先分配一块内存区作为内存压缩 率越小。该判定方法采用了概率预测的思想,可以避免管理的“工作区”。在预拷贝阶段迭代拷贝时,如果有内 因内存页暂时修改频繁而引起脏页归类错误的情况发存脏被判定为频繁修改的脏页,即被在位图to_send 生,有效地捕获修改频繁的脏页。 last中标识出来,则将该內存页压缩并保存到工作区 代西超,南建国,黄雷,等:改进的內存预拷贝动态迁移算法 2016,52(23) 中。同理,在迭代拷贝达到停机条件时,将页位图tfx法将不同内存大小的虚拟机由源主机迁移到目的主机, 屮标示的內存页压缩并保存到工作区中。于是,在停机当虛拟机迁移成功时,记录在预拷贝阶段进行迭代拷贝 拷贝阶段,需要拷叭的内存页都被压缩保存在工作区的轮数,得到的结果如表2所示。同理使虚拟机处于高 中,可以直接采用推送方式将其直接拷贝到目的主机:脏页率的环境下,进行相同的上述实验,得到的结果如 通过对内存页进行压缩相当于间接地增加了迁移表3所示。 过程中的网络带宽,同等数量的内存贞被压缩后可以更 表2低脏页率的环境下进行迭代拷贝轮数的比较 快地拷贝到目的域ε虽然通过压缩操作可以减少传输 虚拟机内存大小MB641282565121024 的数据量而缩短传输时间,但是压缩和解压操作本身都 预拷贝迁移算法 需要一定的开销,通常压缩算法在进行数据压缩时,压 本文算法 66 缩率越高,执行压缩的速度越慢,即需要压缩的时问越 表3高脏页率的环境下进行迭代拷贝轮数的比较 长。因此,应该为压缩算法合理地选择压缩率和压缩速 虚拟机内存大小MB64128256512 度来优化迁移性能,保证内存页在压缩后拷贝相比于未 预拷叭迁移算法3030303030 压缩拷贝的停机时间可以得到缩短。 本文算法 9101010 设本文提出的算法在停机拷贝阶段待迁移的内存 由表2可以得出,在低脏页率的环境下,两种算法 数据量为M,当前可用的网络带宽大小为B,L∠O压缩都表现良好,在送代拷贝轮数不人时就可以达到收敛进 算法的平均压缩速度为R,内存数据量的压缩率为入停机拷贝,改进的效果不是很明显;但由表3可以得 ρ,则在停机拷贝阶段,正常拷贝所需的停机时间如出,在高脏页率的环境下,预拷贝迂移算法需要达到预 式(1)所示,而对待迁移的内存页压缩后雨拷贝所需停设的最大迭代拷贝轮数30轮时才进入停机拷贝,而本 机时间t如式(2)所示 文算法迭代拷贝到第10轮前后时就可以收敛进入停机 B (1)拷贝,极大地降低了迭代拷贝的轮数。出现上述结果是 t'=t.+ t anrEp (1-p)M 因为在低脏页率的环境下,网络带宽大于脏页率,采用 (2) 两种算法进行虚拟机迁移时每一轮迭代拷贝产生的脏 要使虚拟机的迁移性能得到提高,则对内页压缩页都可以被及时拷贝,从而使脏页总数快速收敛;在高 后再拷贝听需的停机时问必须要小于正常拷贝的停机脏页率的环境下,网络带宽小于脏页率,采用预拷贝迁 时间,即t′<t,则得到压缩算法的压缩岑和压缩速度应 移算法时每一轮拷贝产生的脏页未能及时拷贝,导致脏 满足以下关系: 页总数无法收敛,从而每次迁移都迭代拷贝达到上限30 (3)轮时小进入停机拷贝,而本文算法将修改频繁的内存 因此将LZO算法应用于内存贞的压缩进行参数创停机拷贝阶段再拷贝,剔除了大量的重复脏贞,使 设置时,压缩速度与压缩率之积应大于在停机拷贝阶段脏页总数加快收敛,极大地降低了迭代拷贝的轮数,进 系统分配的可用网络带宽 而可以缩短虚拟机迁移过程的总迂移时间。 实验2在不同脏页率的环境下,采用本文算法和预 3实验与结果分析 拷贝迁移算法分别进行不同内存大小的虚拟机迁移,对 虚拟机的迁移性能进行比较。 3.1实验环境 图2和图3为采用两种算法进行虚拟机迁移的总迁 本文在局域閃环境下,选取2个计算节点分别作为移时间,图4和图5为采用两种算法进行虚拟机迁移的 源主机和目的主机进行实验,主机的配置相同且如下所停机时间,为了体现出本文算法对停机拷贝的脏页进行 示: cpu Intel corc i5四核3.4GHz、内存大小为4GB、 100r 硬盘为500GB,主机间采用100 Mbit/s网络带宽的以太 Pre-cop 网连接。主机的操作系统为 Ubuntu1404,虚批化平台 I mproved Pre-copy 为Xen44。实验中标示修改频繁的内存贞的参数为 n=5、k-2,迭代拷贝的上限次数为30,各项性能指标的 结果取多次实验的平均值。 32实验结果分析 实验1在不同脏页率的环境下,采用本文算法和预 拷贝迁移算法分别进行不同内存大小的虚拟机迁移,对 1282565121024 迭代拷贝的轮数进行比较 虚拟机内存大小MB 使虚拟机处于低脏页率的环境下,分别利用两种算 图2高脏页率环境下的总迁移时间 92 016,52(23 Computer Engineering and Applications计算机工程与应用 压缩后再传输的可行性,增加文献[l5中快速拷贝迁移能降低传输的数据量,迭代拷贝过程花费的时间仍会有 算法的停机时间作为对比,该算法仅对脏页的拷贝策一定的缩短,因而本文算法所需的总迁移时间暗小于预 略进行了改进。图屮将本文提出的算法记为 Improved拷贝迁移算法。由图4和图§可以看岀,如果采川快逑 Pre-eopy,预拷贝迁移算法记为prc-copy,文献∏5中提预拷叭迁移算法进行虚拟机迁移,即只对预拷贝迁移算 出的算法记为 Fast pre-copy 法的脏页拷贝策略进行改进,而未压缩停机拷贝阶段的 100 脏貞时,由于被频繁修改的内存页将留到停机拷贝阶 Pre-copy I Improved Pre-copy 段.需要传输的数据量与原来的预拷贝迁移算法相比必 然有所增加,而网络带宽的大小是有限的,明显引起了 三60 停机时间的延长。而本文算法在快速预拷贝算法的基 础上将停机拷贝的脏页进行压缩后再传输,使停机时间 H 缩短到与预拷叭迁移算法不相上下。综上所述,与预拷 贝迁移算法相比,采用本文算法进行虚拟机迁移在未延 长停机时间的情况下,可以缩短总迁移时间。 565121024 虚拟机内存大小MB 4总结 图3低脏贞率环境卜的总迁移时间 在虚拟机的迁移过程中,预拷贝迁移算法虽然可以 3.0 将停机时间缩短,对外表现出不屮断运行,但是在预拷 2.5 Fast Pre-copy 贝阶段迭代拷贝需要重复地挎叭同一个内存页,导致拷 贝内存页数量的增加和总迁移吋间的延长。针对该问 2.0 题,对内存脏页的拷贝策略进行改进而提出快速预拷贝 R 迁移算法,其主要思想是减少修改频繁的内存贞被重复 的拷贝,有效地缩短了总迁移时间,然而频繁修改的内 存页留到停机拷贝阶段再传输却又造成停机时间的延 长,影响着虚拟机的迁移性能。在此基础上,又提出对 641282565121024 停机拷贝的脏页进行压缩,即采用LZO压缩算法对停 虚拟机内存大小MH 机阶段需要拷贝的贞面先压缩再传输,从而将被延长的 图4高脏页率环境下的停机时间 停机吋间缩短到与预拷贝迁移算法不相上下。通过实 Prc-cop 验表明,与预拷贝迁移算法相比,采用本文算法进行虚 50 ast Pre-copy Improved Pre-cOl 拟机迁移在缩短总迁移时间的同时,并未延长停机时间。 参考文献 [1 Barham P, Dragovic B, Fraser K, et al.Xen and the art l00 of virtualization C] /Proceedings of the 19th ACM Sym on Operating sy Principles. Lake Ge United States: ACM SIGOPS, 2003 164-177 0 1282565121024 [2 Puthal D, Sahoo B P S, Mishra S, et al. Cloud comput- 虚拟机内存大小MB ing fcatures, issues, and challenges: a big picture[C]/ 图5低脏页率环境下的停机时间 2015 International Conference on Computational Intelli 由图2和图3可以看出,对于不同内存大小的虚拟 gence and Networks(CINE), 2015:116-123 机迁移,相比于预拷贝迁移算法,本文算法可以缩短总31 armbrust,FoxA, tallith,eta. vlew o Clou 迁移时间。其中,在高脏贞率环境下,由于预拷贝迁移 computing[J]. Communications of the ACM, 2010, 53(4) 算法的迭代拷贝很难收敛,而本文算法通过减少修改频 繁的内存页被重复地拷贝使迭代拷贝可以更快收敛,与 [4 Wood T, Shenoy P, Venkataramani A, ct al. Black-box and gray-box strategies for virtual machine migration[C]/ 前者相比,本文算法在迭代拷贝过程花费的时间必然减 Proceedings of the 4th USENIX Symposium on Networked 少,因而总迁移时间得到明显缩短;在低脏页率环境下, Systems Design and Implementation( NSDIW) Canbridge 由于修改频繁的内存的数量相对较低,两种算法的迭 MA. USA: USENIX ASSOciation, 2007: 229-242. 代拷贝均可以收敛,但是本文对脏页拷贝策略的改进还[s] Clark c, fraser K, Hand s,eta. Live migration of virtual 代西超,南建国,黄雷,等:改进的內存预拷贝动态迁移算法 2016,52(23) machines[c]//Proc of Nsdi 2005. Berkeley, CA, USA: [12 Svard P, Hudzia B, Tordsson J Evaluation of delta com- USENIX ASSOCiation, 2005: 273-286 pression techniques for efficient livc migration of largc [6 Nelson M, Lim B H, Hutchins G Fast transparent migra- virtual machines[c]Proc of the 7th ACM SIGPLAN/ tion for virtual machines [C]//Proccedings of the Annual SIGOPs International Conference on Virtual exccution Conference on USENix Annual Technical Conference Environments. New York: ACM Press. 2011:111-120 Berkeley, CA, USA: USENIX Association, 2005: 391-394 [13] Svard P, Tordsson J, Hudzia B, et al. High performance [7 Hines M R, Deshpande U, Gopalan K. Post-copy live migra ve migration through dynamic page transfer reorder- tion of virtual machines[J].ACM SIGOPS Operating Sy ing and compression[C]//Proceedings of 2011 3rd IEEE tems Review,2009,43(3):1426 International Conference on Cloud Computing Technology [8 Hines M R, Gopalan K. Post-copy bascd livc virtual and Science. Athens Greece. IEEE Press, 2011: 542-548 machine migration using adaptive pre-paging and dynamic [14 Hu Liang, Zhao Jia, Xu Gaochao, et al. IIMDC: live vir self-ballooningC]Proceedings of the 2009 ACM SIGPLAN/ tual machine migration based on hybrid memory copy SIGOPS International Conference on Virtual Execution Environments. New York. USA: ACM Press. 2009: 51-60 and delta compression[J]Applied Mathematics and Infor [9]陈阳,怀进鵬,胡春明基于内存混合复制方式的虚拟机在 mation Sciences. 2013.7(2L): 639-646 线迁移机制[J计算机学报,2011,34(12):2278-2291 [15] Ma Fei, Liu Feng, Liu Zhen. Live virtual machine migra 0]刘诗海,孙宇清,刘占月而向业务特征的自适应虚拟机 tion based on improved pre-copy approach[C]//Proceed 迁移带宽分配算法门计算机学报,2013,36(9):1816-1825 ings of 2010 IFFF International Conference on Soft Ill Jin Hai, Deng Li, Wu Song, et al. Live virtual machine ware Engineering and Service Sciences(ICSESS)Bei migration with adaptive memory compression[ C]/Proc jing, China: IEFF Press, 2010: 230-233 of IEEE International Conference on Cluster Comput--[16]马《,刘峰,李竹伊云计算环境卜虚拟机快速实吋迁移 ing [S1 IEEF Press, 2009: 1-10 方法[门北京邮电大学学报,201235(1):103-106 (上接74页) 472-480 [4]刘颖,张正堂,王亚蓓团队薪酬分配过程、任务互依性对 [21 Yang G, Shen W, Zhang D, ct al. Extended utility and 成员合作影响的实验研究[经济科学,201 DEA models without explicit input[J] Journal of the [15 Carson J B, Marrone J A Shared leadership in teams: Operational Research Society, 2014, 65: 12 12-1220 22] Tone K, Tsutsui M. Network DEA: a slacks-based mea- an investigation of antecedent conditions and perfor mance[J]. Academy of Management Journal, 2007, 50(5) sure approach[]. European Journal of Operational Research 2009,197(1):243-252 1217-1234 [23]Fare R, Grosskopf S Network DEA[]. Socio-cconomic [16 Rouyendegh B D, Erol SThe DEA-fuzzy ANP depart- ment ranking model applied in lran Amirkabir Univer Planning Sciences, 2000,34(1): 35-49 24]Cook w D, Zhu J, Bi G, et al. Network DEA: additive sity[J].Acta Polytechnica Hungarica, 2010, 7(4) cfficicncy dccomposition[J]. European Journal of Opera [17] Lee H, Lee C, Seol H, et al. On the R&d priority set tional rescarch,2010,207(2):1122-1129 ting in technology foresight: a DEA and ANP approach[J] 25 Banker R D, Charncs A, Cooper wwSomc models International Journal of Innovation Tcchnology Man for estimating technical and scalc incfficicncics in data agement,2011,5(2):1015-1019 envelopment analysis[J Management Scicncc, 1984, 30 [8]陈可嘉,于先康基于ANP权重确定的 AHP-DEA模型及 (9):1078-1092 其在逆向物流服务供应商选择中的应用[]数学的实践 26] Syrjancn M J. Non-discrctionary and discretionary fac 与认识,2012,42(21):1-8 tors and scalc in data envelopment analysis[J. European [19] Despotis d KMeasuring human development via data Journal of Operational Rescarch, 2004, 158(1): 20-33 cnvclopmcnt analysis: the casc of Asia and the Pacific[J] [27]Lober G, Staat M Integrating categorical variables in Omega,2005,33(5):385-390 data envelopment analysis models: a simple solution [20]Liu W B, Zhang D Q, Meng w, et al. a study of DEA tcchniquc[J]. Europcan Journal of Operational Rcscarch models without explicit inputs[J]. Omega, 2011, 39(5): 2010,202(3):810-818.