云計算環境中虛擬機內存自適應調節算法研究*

王德勝，張偉哲，郝 萌，魯剛釗，白恩慈

哈爾濱工業大學 計算機科學與技術學院，哈爾濱 150001

云計算環境中虛擬機內存自適應調節算法研究*

王德勝，張偉哲+，郝 萌，魯剛釗，白恩慈

哈爾濱工業大學 計算機科學與技術學院，哈爾濱 150001

WANG Desheng,ZHANG Weizhe,HAO Meng,et al.Research of adaptive virtual machine memory scheduling algorithm in cloud computing environment.Journal of Frontiers of Computer Science and Technology,2017, 11(1)：70-79.

Xen虛擬機；swap空間；內存調度算法

1 引言

隨著互聯網時代的發展，云計算已經發展成大范圍全局資源的池化、分配調度和管理監控，通過網絡提供給用戶動態易擴展且經常是虛擬化的資源，可以讓用戶體驗超強的運算能力[1]。虛擬化技術的應用是將計算機的實體資源分開使用，重新呈現，虛擬機就是虛擬化應用的代表作。其中，Xen虛擬機憑著獨特的虛擬化性能優勢得到社會的廣泛應用[2]，主要應用于服務器應用整合、軟件開發測試和集群運算等。

在學習工作過程中虛擬機的使用很多，用戶實際使用時會發現，有的虛擬機會運行大量程序而使內存負載較大[3]。如果負載量大于事先設定的內存量，此時虛擬機會去使用swap而造成系統工作效率降低，而有的虛擬機運行進程較少，進而內存比較空閑。從全局的角度來看，內存有浪費現象，所有虛擬機的內存并沒有得到很好的利用而使實際工作效率降低。在一臺物理主機上運行多臺虛擬機時，由于虛擬機在創建之初內存資源就已經是固定值了，當虛擬機由于運行進程太多而出現內存使用不足的情況時，可以設計合理的內存調度算法實現將其他虛擬機空閑內存分配到該虛擬機中，避免虛擬機使用swap空間。當所有虛擬機負載量高出總內存量，調節使各個虛擬機也能夠分配到相應的內存，提高整體虛擬機運行時使用效率。這樣不僅可以提高虛擬機的運行效率，還可以更加合理地利用整體物理資源。

顯然，虛擬機內存靜態分配不夠合理，要實現動態的內存分配系統，需要考慮兩個問題：一是正確使用內存調度的開發平臺，本文研究的是Xen虛擬機，這個平臺提供了氣球驅動機制，能夠穩定地完成內存調度任務；二是在多虛擬機運行時，各個虛擬機之間要有合理完善的內存調度策略。

本文從這兩個問題進行討論，重點關注內存調度算法的設計。目前已經有很多關于內存調度算法的研究，其中Zhang等人提出的虛擬機內存調度算法是本文研究和比對的對象[4]。該算法得出了一個當總內存能夠滿足總負載情況下的內存分配策略，但由于算法中沒有考慮到swap空間的使用情況而使得調節過程變長，降低調節效率。同時該算法還忽略了總內存不能滿足總負載的情況，這種情況下，調節結果會導致部分虛擬機內存調節越來越偏離合理值，且swap使用情況越來越大，也會導致部分虛擬機會因為分配內存太少而使得系統進程被殺死，出現死機情況。本文在Zhang的算法上，設計一個更加合理全面的內存調度算法，將swap使用情況作為算法計算的考慮因素之一，同時綜合考慮總內存滿足和不滿足總負載兩種情況。

本文探討在Xen虛擬機中多虛擬機運行時的內存調度算法。第2章介紹多虛擬機內存調度系統的相關設計與實現；第3章介紹內存調度算法；第4章分析系統實驗結果；最后，總結全文。

2 系統實現原理

下面主要介紹多虛擬機內存分配系統的相關技術和實現原理。

2.1 Xen虛擬機系統介紹

Xen Project包括Xen Hypervisor[5-9]。Xen Hyper-visor（即Xen的virtual machine monitor，VMM）位于操作系統和硬件環境之間，負責為上層運行的操縱系統內核提供虛擬化的硬件資源，為上層創建的虛擬機，也叫作域，提供相互隔離的物理資源環境。Hypervisor中并不包含任何與硬件對話的驅動，也沒有與root或管理員對話的接口，因此通過賦予Domain0特權調用這些驅動來管理操作Hypervisor，這樣就可以通過Domain0來調用Xen創建虛擬機（DomainU）的命令，從而創建其他虛擬機。另外Domain0中會載入xend進程，有管理DomainU的權限，提供DomainU的控制臺訪問權限，在創建虛擬機的過程中會直接與Domain0控制臺對話并進行配置。

2.2 氣球驅動機制

氣球驅動機制這一概念最早是Carl在VMware ESX Server中提出并使用[10]，后來沿用到Xen中，氣球驅動機制提供了調節虛擬機內存的功能[11]。

在整個氣球驅動過程中有充氣（inflate）和放氣（deflate）兩個過程。圖1所示為氣球驅動原理。

Fig.1 Mechanism of Xen balloon driver圖1 氣球驅動機制原理

圖1中給虛擬機VM1和VM2確定了初始內存，在運行過程中由于系統自調節或者Domain0控制Hypervisor進行內存調節，要將VM1的內存頁面分配給VM2，首先Hypervisor向VM1發出獲取內存頁面的請求，通過后，運行在VM1中的氣球驅動程序會進行充氣操作，獲取內存頁面，將頁面交付給Hypersivor；然后Hypervisor向VM2發出釋放內存頁的請求，通過之后，進行放氣操作，將內存頁面分給VM2，這樣VM2就可以使用分配到的內存頁面。Hypersivor獲取頁面時就已經做了處理，可以放心地釋放給需要的虛擬機來使用。

2.3 XenStore

XenStore是在Domain之間的一種分等級的共享命名空間[12]。系統設計過程中將利用這一技術，對XenStore進行文件讀寫操作，在此過程中需要用到系統提供的接口函數，這樣就可以在虛擬機使用過程中存儲各個虛擬機的信息。在本文研究中會重點利用XenStore，其中/local/domain目錄下就存儲著每個domain的本地信息，也可以向該目錄下讀寫數據，這樣可以獲取各個虛擬機在運行過程中的內存使用情況。

2.4 Libxenctrl

Libxenctrl是系統提供的C語言函數接口，該函數接口提供了很多功能，可以直接調用氣球驅動完成虛擬機內存分配。列舉幾個有關的接口函數：xc_ interface_open()和xc_interface_close()分別是開啟和關閉一個叫作xc_handle的句柄；xc_domain_set_maxmem()是設置虛擬機最大內存；xc_domain_set_pod_ target()是設置虛擬機目標內存。

2.5 proc文件系統

/proc[13]是非常特殊的虛擬化文件系統，它并不包含真正的文件，而是存儲記錄系統運行時的信息，比如系統內存信息、設備掛載信息、硬件配置等。因此，/proc可以被視為內核服務的控制和信息中心。其中/proc/meminfo文件是負責記錄物理內存和swap空間使用信息的，像內存的空閑空間MemFree、總內存MemTotal、交換空間SwapFree和SwapTotal，以及被內核使用的buffer和cache等[14]。

2.6 Swap性能

Linux系統中的swap空間類似于Windows的虛擬機內存，當系統內存不足時，swap空間的功能是將磁盤虛擬成內存來使用，將內存中暫時不用的數據或命令移交到swap空間中，但是會有大量的I/O消耗，使系統性能有所降低。盡管swap空間可以作為虛擬的內存來使用，但是速度卻遠不及物理內存。本文論述目的之一就是讓虛擬機分得足夠的內存，從而避免使用swap空間造成不必要的消耗。

2.7 多虛擬機內存分配管理系統

系統架構如圖2所示，系統分為服務器端、虛擬機端和網頁端。主要的功能實現是在服務器端和虛擬機端，網頁顯示端只是將虛擬機的內存信息顯示出來。

Fig.2 Automatic memory control system圖2 內存分配管理系統

虛擬機端，主要負責從/proc/meminfo中收集內存和swap數據來說明虛擬機的內存狀態，其中空閑內存=MemFree+Buffers+Cached。獲取數據之后就可以將數據寫入到Xenstore下的對應目錄中，這樣服務器端就可以從中獲取數據。

服務器端，是整個系統的核心，里面包含著內存數據計算機構以及內存執行機構。前者是從Xen-Store下的對應目錄中獲取所有的虛擬機內存數據，根據設計的內存調節算法，根據虛擬機這一時刻的內存情況，計算出虛擬機下一時刻的目標內存。而后者就是為了調節所有虛擬機的內存，爭取下一時刻到達算法計算出的目標內。

3 多虛擬機內存分配管理系統內存調度算法描述

現在已經有很多關于內存調度算法的研究[15-20]，本文提出的多虛擬機內存調度算法思想來自Zhang等人提出的調度算法[4]，但是經過推敲發現該算法的不足之處，進而做出修改得出更加合理完善的算法。表1為算法中的變量定義。

Table 1 Summary of key notations表1 變量定義

Zhang的算法如下：

式中變量A的原始意義是系統負載量的大小，然而沒有考慮到swap信息是不合理的，因為內存不足使用swap的部分也是系統負載的一部分，也應當計算在A內。另外這個算法的思想不夠全面，只能應用于系統總負載小于系統總內存的情況。

為了簡化設計過程，沿用了式（1）中的一些變量，但是虛擬機的負載量重新定義為內存使用量與swap使用量之和。在虛擬機實際運行中，根據不同的內存使用情況可以分為兩種情況：總內存量能夠滿足總負載量和總內存量不能滿足總負載量。

3.1 總內存滿足總負載

公式前半部分是固定的數據，也就是將所有內存按運行虛擬機數量進行均等分配；后半部分是關于每臺虛擬機總負載量與平均負載量的差值的線性函數；參數τ是這個函數的關鍵。公式右邊的所有數據，比如Ti，以采集到數據的時間為標準，以調節周期為時間單位，Ti是0時刻的數據。而公式左邊的Nti是1時刻的數據，也就是說，左邊的運算結果是虛擬機下一時刻的目標內存。

3.1.1 虛擬機可行域范圍和τ的關系

在總內存滿足總負載量的情況下，系統調節的目標是使得虛擬機分配得到的目標內存能夠滿足負載量，因此只需要滿足：

當總內存量能夠滿足總負載量時，針對式（1），令Ai=Ti，其中Ti=Si+Ai，也就是將swap使用量算入虛擬機真正的進程負載量，如式（2）：

也就是：

不等式中有τ和Ti未知量，是由Ti組成的變量。為了方便討論，假設n=2，這樣只需要滿足：

τ在不等式中決定T1和T2的使用范圍，通過圖3可以觀察到在不同τ下的虛擬機內存的可行解。

Fig.3 Relationship betweenτand memory圖3 τ值和內存可行域的關系

橫縱坐標分別為T1和T2。線段下方代表在該τ值下，兩臺虛擬機的內存只要保證這樣的狀態就不會使用swap空間。如果內存狀態達到線段上方，此時虛擬機會使用swap空間而造成內存浪費現象。

τ＜0的情況沒有意義，會讓最大目標內存小于0；τ＞1的情況也是沒有意義的，這會過度放大負載量與平均負載量的差值。當總負載量過高，而某臺虛擬機負載量很低，會導致分配目標內存小于0，或者某臺虛擬機負載量很高，會導致分配目標內存大于總負載，這些情形都是不合理的。因此參數τ∈[0,1]。

3.1.2 空閑內存的討論

系統調節的目標是讓虛擬機可用內存達到不使用swap空間，對于調節后的空閑內存進行如下討論。

這里假設運行n臺虛擬機，任意比較兩個虛擬機調節之后的空閑內存大小。假設編號為a和b的兩臺虛擬機，借助空閑內存公式比較Fa和Fb，則有：

化簡，可得：

由于τ∈[0,1]，結果也正如上面討論的那樣，Fi∝-Ti。從空閑內存相減的結果中可以看到，如果虛擬機a正是負載量最大的虛擬機m，則結果如下：

因此從結果中可以看出，負載量最大的虛擬機在經過調節后，分得的空閑內存最小。

3.1.3 動態τ的使用

首先在可行域討論中，只有τ=1時可以滿足虛擬機在總內存范圍內進行內存調節；其次當τ=1時，從調節結果上來看，是將所有的空閑內存平均分配到每個虛擬機中，這是一種盲目分配的行為，當系統能夠正常工作時要盡可能減少調節內存的動作。

綜合考慮這些，在調節過程中使用動態τ進行內存調節。

理論上系統調節的要求要使得每臺虛擬機調節之后的空閑內存量大于0，這樣調節的結果能夠使虛擬機不使用swap空間。但在實際系統中，并不是當可用內存減少到0時才去使用swap空間，當可用內存少于某個值時，系統就會去使用swap。這里不對具體空閑內存降到什么程度才去使用swap做深究。假設虛擬機調用swap空間前的最小空閑內存為f，只需要保證一個值f′≥f，保證所有虛擬機調節目標內存中空閑內存不少于f′，要求滿足Fi＞f′。以此為條件，討論參數τ。

系統調節之后虛擬機的空閑內存Fi=Nti-Ti，為了滿足以上條件，則有：

分析公式結構易得當最大的負載Tm滿足即可：

化簡后，取臨界條件，如式（4）：

從上述內容得知，內存調節范圍隨著τ值增大而增大，負載量最大的虛擬機在最終分配的目標內存最大，并且空閑內存最小。在調節過程中，當內存申請最大的虛擬機仍然有不少于f′的空閑內存，按公式計算會有τ＜0，此時強制使τ=0，即是將總內存均等分配到各個虛擬機，比較合理。等到最大負載量達到使空閑內存不大于f′時，τ值就可以根據公式計算得到，并進行調節。調節之后，負載量最大的虛擬機會調整到空閑內存為f′，而其他虛擬機可以分配到更多的空閑內存。當負載量最大的虛擬機經過調節后空閑內存不能達到f′，此時會使得τ=1，將可用內存進行均等分配。因此f′在調節過程中決定著內存調節的一些特殊情況的切換時刻。

3.2 總內存不滿足總負載

對于總負載量高于總內存的情況，需要知道無論怎么分配系統都會去調用swap空間，因為系統無法超越實際資源的局限。

算法設計需要保證兩點：一是保證每個虛擬機分配到最小內存，也就是在算法上設定分配目標內存最小值，以供系統進程運行；二是保證最小內存以外的內存都被使用，不能有空閑內存。

利用上面的算法處理總內存不能滿足系統負載時，會出現負載量低的虛擬機顯示系統進程被殺死而進入死機狀態，因此要保證一個最小內存x運行系統程序。這個最小值跟上面的人工預留內存f相似，此處不需要它的具體數字，只需要保證在實際使用中確定一個參數x′＞x。在實驗操作中x′取150 MB。

算法的思路是，在獲取虛擬機內存和swap空間使用信息之后，進過上述算法計算，如果出現分配目標內存不能達到x′的虛擬機，從所有虛擬機的總內存Ni中扣除x′內存信息，并且是當作已用內存來扣除。假設扣除之后的虛擬機內存為，即：

這使得Ti減少了x′，同時也改變了總內存N。假設所有虛擬機扣除之后的總內存為N′，則有：

然后將改變之后的數據帶入式（2）中進行計算，得式（5）：

這種情況下，虛擬機對內存可行域要求是全域可行的，因此要求τ=1。其實此時τ=1，導致的分配結果是所有虛擬機會使用相同大小的swap空間，從而使得負載量較小的虛擬機獲得理論目標內存為負。為了解決這一問題，將目標內存為負的虛擬機內存置0，然后讓所有為負的內存作為債務，利用τ=1的分配思想，讓其他分配目標為正的虛擬機來還。還的思想是不斷地平均分配債務給這些虛擬機，過程中會遇到“還不起”的虛擬機，則直接將其結果置為0，繼續將債務平均分到剩余各個虛擬機中，直至還完。這樣處理結束之后，會保證所有虛擬機的分配內存。最后Nti≥0分配內存再加上之前扣除的x′，即：

就可以保證所有虛擬機的目標內存：

在上述算法實現過程中，x′是最小目標內存衡量標準。在總內存不能滿足總負載時，如果某臺虛擬機不開啟任何負載進程，內存調節系統為其分配不少于x′的內存，可能系統實際使用的內存比分配得到的目標內存要小而導致有空閑空間。不過在實驗中發現，取x′為150 MB時，盡管有這種情況發生，造成的空閑空間也是非常少的，可以忽略不計。因此算法保證了系統在內存分配過程中內存都被使用，沒有空閑內存，同時也保證了每個虛擬機的最小目標內存。

4 實驗結果與分析

4.1 實驗方案

實驗主要測試多虛擬機內存調節算法相比較之前算法在功能和性能上的提升，創建10臺虛擬機供實驗測試。實驗前給每臺虛擬機設定相同初始內存和最大內存，在初始化虛擬機內存時將每臺虛擬機都設置成統一值，方便實驗數據對總內存的管理和計算。同時也要為每個虛擬機設置最大內存，這個可以根據實驗預期的結果進行設定。在啟動服務器端內存調節程序時，會輸入總內存N和人工預留內存f′兩個參數。

利用這些虛擬機，在功能方面設計了有效性測試實驗，主要是模擬虛擬機實際使用過程中遇到的內存使用情況，設計的實驗如下。

4.1.1 mono實驗

mono測試就是根據輸入參數[low,high]，系統負載量從low開始進行申請，之后每隔相同時間等量遞增負載量，直到負載量為high，之后負載量從high開始釋放，每隔相同時間等量釋放，直到負載量為low結束，其中low＜high。

4.1.2 靜態負載實驗

靜態負載測試是通過人工操作在不同的虛擬機上申請負載，從而模擬虛擬機使用過程中遇到的各種內存使用情況，整理內存調節過程中各個虛擬機內存的變化。該實驗是與之前算法實驗結果進行比對，觀察新算法在功能上的提升，設計了幾組比對情景。

另外，還設計性能檢測實驗測試系統運行時的性能，主要利用DaCapo測試集來比較兩個算法的優劣性。

4.1.3 DaCapo實驗

DaCapo測試集專門用于測試編程語言[21]、內存管理和系統結構，由一些開源的真實應用程序組成，運行時進行一些非正常的負載手段。DaCapo測試集開發至今，已經有了一些版本，本實驗用的DaCapo測試集版本是9.12-bach。這個jar包中包含的測試程序，根據測試類型可分為內存測試型、磁盤測試型和CPU測試型。其中內存型測試程序有h2、tradebeans、tradesoap；磁盤型測試程序有eclipse、luindex；CPU型測試程序有avrora、fop、jython、lusearch、pmd、sunflow、tomcat和xalan。實驗中將運行所有測試程序，所得測試結果是各個測試程序運行指定次數需要的時間，運行多次的目的是將同一項測試程序的結果取平均數，測得的結果更可靠，以時間消耗反應系統對應性能狀態。

4.2 功能有效性測試

功能測試時首先設計mono測試來驗證內存調度算法的功能有效性，然后用靜態負載實驗與之前算法實驗進行比對。

4.2.1 mono測試

這個實驗僅僅是為了驗證本文算法的功能有效性。實驗配置如表2所示。在Domain0上運行調節程序，在虛擬機上運行內存采集程序，在VM1中運行mono測試程序，并觀察實驗結果。本實驗中令low= 50 MB，high=500 MB。

Table 2 Experiment configuration表2 實驗配置

實驗結果如圖4所示，從VM1的內存變化曲線中可以看到，一開始mono增加內存負載時，VM1內存并沒有變化，而是當空閑內存達到預留值時，才開始進行改變，此時從VM2中分得空閑內存，而VM2的內存也因此改變。從兩臺虛擬機的實驗結果可以得出結論，模擬接近真實環境的動態負載量，內存調節系統對于內存的調節結果和預期一致，能夠合理地為虛擬機動態分配內存。

Fig.4 Automatic memory curve of two VMs圖4 虛擬機內存變化曲線

4.2.2 靜態負載測試

這個實驗是為了比對在不同內存使用情況下，新舊兩種調節程序的調節情況。

情景1調節程序啟動后，在一臺虛擬機VM1中運行800 MB負載，實驗配置如表3所示，圖5是觀察的VM1的數據。

Table 3 Experiment configuration表3 實驗配置

Fig.5 Automatic memory curve of VM1圖5 VM1數據變化曲線

情景2調節程序啟動后，依次在10臺虛擬機中運行1 GB負載程序實驗配置如表4所示。在實驗中以前的算法不能做出分配而導致實驗失敗，而圖6是觀察本文內存調度算法中每臺虛擬機的內存數據變化曲線。

Table 4 Experiment configuration表4 實驗配置

綜合這兩個實驗，可以得出兩個結論：（1）情景1的實驗結果顯示，負載程序啟動后，在內存方面，新算法能夠更快地調整到目標內存；在swap使用方面，新算法能夠更短時間且更少地使用swap空間，這都說明了新算法提升了多虛擬機內存調節系統的調節效率。（2）情景2的實驗更有說服力，舊算法不能對情景2進行處理，因為此時負載量已經超出總內存；而新算法仍然能夠進行合理的內存分配。雖然看到最終每臺虛擬機有幾乎相近的swap使用量，那是因為總負載超出總內存的部分必須要swap空間來補給，并且這個swap使用量的結果也是非常合理的，說明新算法更加全面，不管總內存能否滿足負載，系統都能合理穩定地為虛擬機分配內存。

Fig.6 Automatic memory curve of 10 VMs圖6 10臺虛擬機數據變化曲線

4.2.3 DaCapo測試

這個實驗是為了檢測新的調節算法是否能減少DaCapo的測試時間。

實驗使用了5臺虛擬機，每臺初始內存為1 GB，實驗配制如表5所示。為了檢驗內存調節系統對于物理主機性能提升的幫助，將對是否開啟內存調節系統兩種情況進行比較。至于負載量的選擇，由于低負載狀態并沒有涉及太多內存調節過程，進行實驗的話沒有意義，實驗中會選擇讓虛擬機處于高負載狀態進行測試，因為該狀態會有頻繁調節過程。再分別測試在兩種內存調度算法下的系統性能。

Table 5 Experiment configuration表5 實驗配置

實驗過程中，讓虛擬機處于高負載的狀態，分別測試虛擬機在兩種內存調度算法下的內存調節情況。啟動虛擬機后，運行服務器端和虛擬機端程序，在VM1虛擬機中運行1 GB負載程序，從調節程序中觀察到虛擬機內存趨于穩定時，關閉調節程序，再開啟調節程序，同時在該虛擬機中運行DaCapo測試集，測試所有程序，運行次數為10，并記錄實驗結果。

實驗結果對比情況如圖7所示，顯示了DaCapo中的13個測試程序分別在新舊兩種調節算法下的測試結果。從實驗結果可以看到eclipse測試項的運行時間得到了明顯的減少，這是disk類型的測試程序。還有tradesoap的運行時間也有微弱的減少，tradesoap是內存性的測試程序。整體看來，實驗結果顯示在虛擬機運行性能上得到了某些方面的提升。

Fig.7 Automatic memory of VM1圖7 VM1數據變化

5 結束語

本文論述了多虛擬機內存分配系統的內存調度算法，相比較之前的算法，新的內存調度算法在功能上提高了內存調度策略的效率，并且完善了總內存不能滿足總負載的情況；新的內存調度算法使得在多虛擬機運行環境下的虛擬機整體性能得到提升，在云計算高速發展的時代，這一研究很有應用前景和價值。

[1]Armbrust M,Fox A,Griffith R,et al.Above the clouds:a Berkeley view of cloud computing,UCB/EECS 28[R].University of California,Department of Electrical Engineering and Computer Sciences,Berkeley,2009.

[2]Gupta D,Cherkasova L,Gardner R,et al.Enforcing performance isolation across virtual machines in Xen[C]//LNCS 4290:Proceedings of the ACM/IFIP/USENIX 7th International Middleware Conference,Melbourne,Australia,Nov 27-Dec 1,2006.Berlin,Heidelberg:Springer,2006:342-362.

[3]Govil K,Teodosiu D,Huang Yongqiang,et al.Cellular disco: resource management using virtual clusters on shared-memory multiprocessors[J].ACM Transactions on Computer Systems,2000,18(3):229-262.

[4]Zhang Weizhe,Xie Hucheng,Hsu R.Automatic memory control of multiple virtual machines on a consolidated server[J]. IEEE Transactions on Cloud Computing,2015.

[5]Magenheimer D.Memory overcommit without the commitment[J].Extended Abstract at the Xen Summit Boston, 2008:1-3.

[6]Abels T,Dhawan P,Chandrasekaran B.An overview of Xen virtualization[J].Dell Power Solutions,2005,8:109-111.

[7]Barham C P,Dragovic B,Fraser K,et al.Xen and the art of virtualization[C]//Proceedings of the 19th ACM Symposium on Operating Systems Principles,Bolton Landing, USA,Oct 19-22,2003.New York:ACM,2003:164-177.

[8]Smith J,Nair R.Virtual machines:versatile platforms for systems and processes[M].San Francisco,USA:Morgan Kaufmann Publishers Inc,2005.

[9]Rosenblum M.VMware's virtual platform:a virtual machine monitor for commodity PCs[C]//Proceedings of the 11th Hotchips Conference,1999.

[10]Waldspurger C A.Memory resource management in VM-ware ESX server[J].ACM SIGOPS Operating Systems Review,2002,36(SI):181-194.

[11]Schopp J H,Fraser K,Silbermann M J.Resizing memory with balloons and hotplug[J].Proceedings of the Linux Symposium,2006,2:313-319.

[12]XEN.XenStore reference[EB/OL].(2013)[2015-10-31].http: //wiki.xen.org/wiki/XenStoreReference.

[13]Wilding M,Behman D.Self service Linux[M].Upper Saddle River,USA:Prentice Hall,2006.

[14]Jones S T,Arpaci-Dusseau A C,Arpaci-Dusseau R H.Geiger:monitoring the buffer cache in a virtual machine environment[J].ACM SIGOPS Operating Systems Review, 2006,40(5):14-24.

[15]Ma Bo.Dynamic memory management for virtual machines via memory hotplug[D].Wuhan:Huazhong University of Science and Technology,2012.

[16]Zhao Weiming,Wang Zhenlin,Luo Yingwei.Dynamic memory balancing for virtual machines[J].ACM SIGOPS Operating Systems Review,2009,43(3):37-47.

[17]Li Dawei,Zhao Fengyu.Memory scheduling strategy for virtual machine in private cloud platform[J].Journal of ComputerApplications,2014,34(9):2523-2526.

[18]Wang Zhigang,Wang Xiaolin,Jin Xinxin,et al.Mbalancer: predictive dynamic memory balancing for virtual machines [J].Journal of Software,2014,25(10):2206-2219.

[19]Wei Yong.Research and implementation of Xen virtual machine memory live migration techniques[D].Shenyang: Northeastern University,2012.

[20]Hu Yao,Xiao Ruliang,Jiang Jun,et al.Virtual machine memory of real-time monitoring and adjusting on-demand based on Xen virtual machine[J].Journal of Computer Applications,2013,33(1):254-257.

[21]The DaCapo benchmark suite[EB/OL].[2015-10-31].http:// www.dacapobench.org/.

附中文參考文獻：

[15]馬博.基于內存熱插拔的虛擬機動態內存管理系統[D].武漢:華中科技大學,2012.

[17]李大為,趙逢禹.私有云平臺的虛擬機內存調度策略[J].計算機應用,2014,34(9):2523-2526.

[18]王志鋼,汪小林,靳辛欣,等.Mbalancer:虛擬機內存資源動態預測與調配[J].軟件學報,2014,25(10):2206-2219.

[19]魏勇.Xen虛擬機內存實時遷移技術研究與實現[D].沈陽:東北大學,2012.

[20]胡耀,肖如良,姜軍,等.基于Xen虛擬機的內存資源實時監控與按需調整[J].計算機應用,2013,33(1):254-257.

WANG Desheng was born in 1992.He is an M.S.candidate at Harbin Institute of Technology,and the student member of CCF.His research interests include virtualization techniques for cloud computing and machine learning,etc.

王德勝（1992—），男，安徽全椒人，哈爾濱工業大學計算機學院碩士研究生，CCF學生會員，主要研究領域為云計算環境中虛擬化技術，機器學習等。

ZHANG Weizhe was born in 1976.He received the Ph.D.degree from Harbin Institute of Technology in 2006. Now he is a professor and Ph.D.supervisor at Harbin Institute of Technology.His research interests include virtualization techniques,parallel and distributed system,etc.

張偉哲（1976—），男，黑龍江哈爾濱人，2006年于哈爾濱工業大學獲得博士學位，現為哈爾濱工業大學教授、博士生導師，主要研究領域為虛擬化技術，并行與分布式系統等。

HAO Meng was born in 1991.He is a Ph.D.candidate at Harbin Institute of Technology,and the student member of CCF.His research interest is performance prediction of parallel applications.

郝萌（1991—），男，山東濟寧人，哈爾濱工業大學計算機學院博士研究生，CCF學生會員，主要研究領域為并行程序性能預測技術。

LU Gangzhao was born in 1990.He received the M.S.degree from Harbin Institute of Technology in 2014.Now he is a Ph.D.candidate at Harbin Institute of Technology,and the student member of CCF.His research interests include performance analysis of scientific programs,analytical performance model and statistical performance model,etc.

魯剛釗（1990—），男，河北唐山人，2014年于哈爾濱工業大學獲得碩士學位，現為哈爾濱工業大學博士研究生，CCF學生會員，主要研究領域為科學計算程序的性能分析，分析性能模型和統計性能模型等。

BAI Enci was born in 1988.He received the M.S.degree in computational mathematics from Harbin Institute of Technology in 2013.His research interests include real time system and cloud computing,etc.

白恩慈（1988—），男，河北邯鄲人，2013年于哈爾濱工業大學獲得碩士學位，主要研究領域為實時系統，云計算等。

Research of Adaptive Virtual Machine Memory Scheduling Algorithm in Cloud Computing Environment*

WANG Desheng,ZHANG Weizhe+,HAO Meng,LU Gangzhao,BAI Enci
School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China
+Corresponding author:E-mail:wzzhang@hit.edu.cn

Resource of Xen virtual machines has been fixed when booted.However,some virtual machines have to use swap space because of the lack of memory while there is idle memory in other virtual machines,which reduces the usage efficiency of memory.There has been the design of memory scheduling algorithm among virtual machines in the previous research,but the scheduling algorithm is inefficient without the consideration of swap.On the foundation of the previous research,this paper puts forward a more reasonable scheduling algorithm that combines swap and the usage of memory to adjust the allocation of memory in virtual machines.The algorithm is also designed on the theory of the idle memory tax proposed by Carl.Firstly,the range of the adjustment will be settled based on the usage of memory and swap.Then the object memory will be calculated in the range.Compared with the previous algorithm,the improved algorithm has been proved to be more effective in experiments.

Xen virtual machine;swap space;memory scheduling algorithm

A

：TP391

10.3778/j.issn.1673-9418.1512055

*The National Natural Science Foundation of China under Grant Nos.61202457,61472108(國家自然科學基金);the National Basic Research Program of China under Grant No.2013CB329606(國家重點基礎研究發展計劃(973計劃));the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20132302110037(高等學校博士學科點專項科研基金(博導類)).

Received 2015-11,Accepted 2016-01.

CNKI網絡優先出版:2016-01-07,http://www.cnki.net/kcms/detail/11.5602.TP.20160107.1540.002.html

摘 要：Xen虛擬機自身的資源在創建之初已經固定，往往會因某些虛擬機內存不足而使用swap，使得虛擬機工作性能降低，而有的虛擬機內存比較空閑，使得整體虛擬機內存使用效率不高。之前已經有研究對虛擬機使用過程中的內存調度算法進行設計，但是經過推敲發現，之前內存調度算法由于沒有考慮swap空間使用情況而導致整體內存調度不夠高效。在前人算法研究基礎上，提出了一個更加完善合理的內存調度算法，結合swap和內存使用情況一起調節虛擬機內存。算法仍然延續了Carl提出的空閑內存稅概念加以設計，首先根據虛擬機內存和swap使用情況確定該次調節周期的調節范圍，之后根據各個虛擬機的內存和swap空間使用情況計算虛擬機目標內存。對前后兩種算法分別設計實驗進行測試，驗證了新算法的高效性。