基于低能耗的動態虛擬機調度

王悅

（華北電力大學，北京102206）

隨著“大物云智移”技術的快速發展，加上高速率低時延的移動通信網絡為超高密度的信息接入提供了便捷，數據中心產生了海量的數據被存儲和操作的需求，數據中心是云計算基礎設備的核心部分，在規模以及數量方面都呈現出爆發式增長態勢，數據中心的能耗和效率問題亟待解決。根據報告顯示，數據中心服務器的利用率僅為總容量的35%，其余的效用都被浪費了[1]。因此通過對虛擬機的整合優化來減少這些未充分利用的資源起著至關重要的作用，通過對虛擬機的整合優化，將虛擬機放在有限的服務器上，以提高數據中心的利用率和總體吞吐量成為了降低數據中心能源消耗的一種思路。

1 相關工作

數據中心的使用情況具有不確定性，不同時段數據中心的物理機利用率不同，不同應用對物理機上的資源喜好不同，因此物理機的負載情況也是具有隨機性的。動態虛擬機遷移，就是在不停止對外提供服務的情況下，根據一定的策略，將虛擬機從一臺物理機遷移到另一臺虛擬機上。通過虛擬機的動態遷移來達到資源整合優化對改善數據中心能源消耗問題有著重要意義。目前對低能耗虛擬機調度已經有很多研究，文獻[2]中，作者數據中心所有虛擬機的遷移頻率和在物理機總體負載量設定隨運行情況變化的閾值，有效的解決了靜態閾值造成的一段是時間內虛擬機頻繁遷移的問題，但對物理機各資源的利用情況未加以考慮資源，如某單一資源需求量高，可能會出現物理機資源利用不均衡導致的資源浪費的問題[2]。Paulraj 等人提出了一種通過復雜的算法預測未來一段時間內的負載情況來決定觸發虛擬機遷移操作，雖然算法提高了預測的準確性，但是觸發遷移時機的合理性完全依賴預測值[3]。文獻[4]中提供了一種兩級狀態檢測的方法，很好的解決了物理機負載的易變性導致的資源利用不穩的問題，但是并未考慮物理機負載過低的情況[4]。

在考慮遷移虛擬機的觸發因素時，當物理機上某一或者某些資源被占用量過高以及物理機全部資源使用量過低都會出發虛擬機遷移操作。文獻[5]中，根據建立虛擬機能耗模型，在遷出虛擬后保證物理機不過負載的前提下，選擇虛擬機遷移代價最小的虛擬機進行遷出。雖然低了系統的能耗，但是算法復雜較高，也沒有在目標物理機的需選擇中體現節能[5]。L. Shi 等人提出的矢量箱包裝算法算法首先根據服務器的利用率和容量對服務器進行排序，然后嘗試將vm 從低容量服務器遷移到高容量服務器，以便在有限的機器上合并工作負載。但是，這可能會增加遷移的數量，從而對SLA 參數產生不良影響[6]。文獻[7]在VMD_TES 的基礎上，設計了4 種虛擬機選擇算法，通過對比實驗發現HLGP 充分兼顧SLA 違約和能耗兩方面[7]。

虛擬機放置策略不在像以前一樣只考慮單一要素，目前的研究都是基于多因素考慮，旨在得到一個性價比較高的調度策略。HALLAWI 等人將虛擬機放置問題做是一個多維裝箱問題，將CPU 和內存看做二維資源，物理機看做箱子，通過建立最小化資源浪費模型，在箱子盡量少的前提下，放下最多的虛擬機，并利用遺傳算法求解該模型[8]。Memaz 等人提出了同時兼顧完成時間和能耗的多目標混合遺傳算法，提高了系統效率并降低了能耗[9]。J. Chen 等人通過降低遷移虛擬機數量來實現節能，因為VM遷移過程涉及額外的CPU-MIPS 開銷和網絡帶寬，這會降低執行性能并導致違反SLA[10]。在上述的研究中都采用了智能啟發算法，能夠較好的多目標優化。但是基于負載平衡和低能耗的適應度函數易出現采樣空間有限損失最優個體的問題。而NSGA-II 算法能夠有效的解決這個問題。因此本文是在NSGA-II 算法上再次改進，旨在構建一個高效、節能、負載均衡的調度策略。

2 問題描述和模型介紹

虛擬機遷移主要是分為確定何時要進行虛擬機遷移、哪些虛擬機要從物理機中遷移出來以待遷移虛擬要遷移到哪臺物理機。

2.1 問題描述

云計算數據中心是一個由計算節點、存數設備、網絡設備構成的分布式網絡，是云計算基礎設備和資源的集合[11]。本文中假定數據中心擁有n 臺異構臺物理機PM= {PM1，PM2，PM1…PMm}，物理機i 上的資源集合由RSet（i）={Rcpu（i）、Rmem（i）、Rbro（i）…}表示，物理機i 上的虛擬機集合由VM={VM（i）1，VM（i）2，VM（i）3…VM（i）m}，包含CPU、內存、寬帶、硬盤等。由于數據中心的任務不具備規律性，導致數據中心可能存在部分物理機負載較重，部分物理負載過低以及物理機上某種資源利用率很高，其他資源不能得到充分利用。

2.2 負載均衡

物理機的負載不均衡主要體現以下兩個方面，對負失衡的原因分析，提出相應解決辦法，就能將負載均衡的思路運用到虛擬機放置策略中。

（1）物理機得資源利用率不均衡

物理機出現資源浪費的原因就是虛擬隨機分配到物理機上，就可能出現物理機上的虛擬機集合對某一資源利用率較高，而其他資源不能被充分的利用。本文根據物理機的是實際資源擁有量，為每一個資源設定負載閾值，超出這個閾值就需要對虛擬機進行遷移。

其中Rcpu（i）j，Rcpu（i）j，Rcpu（i）j分別表示物理機i 上的第j個虛擬機的CPU、內存、帶寬的使用量，Rcpu（i），Rcpu（i），Rcpu（i）分別表示物理機i 的CPU、內存、帶寬的使用量。

（2）物理機負載不均衡

數據中心接到任務后虛擬機被放置到能夠滿足要求的物理機上運行，并不會考慮對物理機的充分利用，就會存在數據中心有空閑和低負載的物理機在運行, 維持這些物理機運行也會產生資源浪費。因此根據物理機的總資源量，為物理機設定一個高負載閾值和低負載閾值，在這里我們設定總資源量的0.8倍為高閾值，總資源量的0.2 倍為低閾值。超過高閾值就會觸發接下來的對各項資源負載閾值的判斷決定被遷出的虛擬。對于低于負載閾值的物理機上的虛擬機需要全部被遷出。

其中mi表示物理機上有mi臺虛擬機，VMload （i）j 表示物理機i 上第j 個虛擬機的負載Pload（i）表示第i 個物理機的總負載量。

2.3 改進的NSGA-II 算法

多目標優化算法是為了解決有兩個或兩個以上的目標函數的優化問題。NSGA-II 算法是在的NSGA 的基礎上為了解決多目標優化問題改進而產生的，對解決多目標問題有很好的能力。算法流程如下：

（1）編碼：對染色體編碼時采取分組編碼的方式，編碼時每臺物理機都代表著染色體上的一個基因位，物理機上的虛擬機編號后就是該基因位的值。然后隨機產生初始種群P。

（2） 適 應 度 計 算 ： 根 據 適 應 度 函 數f=A*LoadRate+B*ResourceRate+C*VMMigrate 對種群進行適應性評估，其中VMMigrate 為虛擬機遷移數量，A、B、C 為權重系數且和為1。若滿足優化標準，輸出最最優解，結束循環，如不滿足，進行步驟（3）。

（3）交叉：在生成的初始種群中，采取隨機選擇策略隨機選擇兩個個體進行交叉，形成新的個體。在進行交叉時每個基因位的交叉概率相等。

（4）變異：在算法的變異階段，采取非均勻變異的方式進行變異步驟，對每個基因位以相同概率進行一次隨機擾動，產生新個體。

（5）非支配排序：對種群的解進行非支配排序，在種群P 和Q 中，進行三次非支配排序，得到三個不同等級的非支配解集。

（6）擁擠距離排序：對得到的非支配解集按照適應度大小進行擁擠距離排序，按適應度降序排列，取前N 個解作為初始種群P。

重復（2）（3）（4）直至結果收斂。

3 調度過程

虛擬機的調度過程是由虛擬機檢測器、虛擬管理器、虛擬機調度完成。根據每臺物理機所擁用的總資源設定物理機總體閾值PMUlow，PMUhigh，物理機中各項資源CPU、內存、寬帶的高負載閾值根據各自的利用率決定。

圖1 算法流程圖

通過對該物理機監測器實現對物理機的負載情況進行檢測，負載過高過低都會觸發遷移操作，當物理機總量超負載時，在對物理機資源進行二級檢測確定物理機的負載類型，根據HLGP 算法對超負載的資源進行排序將占用該資源量最大和最小的虛擬機遷出到待遷移虛擬機隊列，直至物理機處于正常負載，若物理機負載低于低閾值將物理機上的所以虛擬機遷到待遷移虛擬機隊列。虛擬機調度器根據虛擬機反饋的信息，通過改進NSGA-II 算法得到一個調度方案，既滿足負載均衡，又滿足能耗較低。最后對得到的調度方案由管理器來實施。（圖1）

4 仿真設計及結果

數據中心的運行情況較復雜，數據量很大，如果要完全復現數據中心的真是實運行環境比較困難且會耗費不必要的社會資源。CloudSim 能夠較真實的仿真云數據中新的運行情況，能夠有效的簡化云平臺的建設與測試，同時可實現跨平臺運行。因此在數據中心資源調度的研究中被廣泛運用。為了在對本文的虛擬機調度策略的有效性進行驗證，也采用了CloudSIM平臺。在實驗中數據中心的任務是采用的數據集為BitBrainstorm 公司提供的公開數據集，數據集包含本實驗所涉及的CPU、內存、帶寬三種類型的資源記錄，數據中心異構物理機數量為800 臺，虛擬機的數量根據任務變化。評價指數是根據論文[11]中的提出的評價指標對CloudSim 的能耗函數進行改進，通過與傳統的LBES 算法和PDT 算法進行對比實驗發現本文提出的算法能夠減少虛擬的遷移次數，提高物理機的資源利用率，降低能耗。