楊 翎，姜春茂

（哈爾濱師范大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院，哈爾濱 150025）

0 引言

近年來，云計算［1-2］作為一種按需提供服務(wù)的計算模型，其能效問題日益得到關(guān)注。云能效問題涉及軟件、硬件、網(wǎng)絡(luò)等各種要素［3-4］，其中作為數(shù)據(jù)中心重要組成成分——主機(jī)的負(fù)載對于能耗的影響巨大。主機(jī)負(fù)載的程度與其所耗費的能源是不成正比的，這意味著，負(fù)載很輕時，如10%的負(fù)載，主機(jī)也要耗費60%～70%的正常標(biāo)定能耗；而負(fù)載超過特定閾值如70%時其能耗急劇增加［5］。因此，保持主機(jī)在一個合理的范圍內(nèi)，對于降低數(shù)據(jù)中心的能耗、平衡負(fù)載與均衡多維資源的利用率具有重要的意義。

虛擬機(jī)遷移技術(shù)［6-7］通過遷移過高負(fù)載主機(jī)的虛擬機(jī)合并到過輕負(fù)載的主機(jī)，進(jìn)而整合主機(jī)的多維資源，減少數(shù)據(jù)中心的資源浪費，提高資源利用率，避免主機(jī)負(fù)載過重導(dǎo)致的能耗急劇增加，從而降低了數(shù)據(jù)中心的能耗。

本文提出一種基于三支決策的虛擬機(jī)節(jié)能遷移調(diào)度策略（Virtual Machine Migration scheduling strategy based on Three-Way Decision，TWD-VMM），借鑒三支決策的思想，將主機(jī)分為高負(fù)載主機(jī)、中等負(fù)載主機(jī)和低負(fù)載主機(jī)，進(jìn)而作出虛擬機(jī)遷移調(diào)度的決策，即：1）高負(fù)載主機(jī)遷出虛擬機(jī)；2）低負(fù)載主機(jī)遷入虛擬機(jī)；3）將盡可能多的主機(jī)負(fù)載收斂至中等負(fù)載的區(qū)域，從而避免主機(jī)負(fù)載出現(xiàn)過高或過低的情況，達(dá)到主機(jī)負(fù)載均衡并降低數(shù)據(jù)中心的能耗開銷。

1 相關(guān)工作

近年來，利用虛擬機(jī)遷移技術(shù)來節(jié)省云能耗的調(diào)度算法相繼被研究。大體上包括如下幾類：

1）從遷移角度出發(fā)。Zhao等［8］研究基于啟發(fā)式的虛擬機(jī)節(jié)能調(diào)度算法，提出一種能量感知算法，將遺傳算法與禁忌搜索算法相結(jié)合，獲得一種最優(yōu)的虛擬機(jī)遷移方案，以達(dá)到節(jié)省云能耗、平衡資源負(fù)載的作用；Xu等［9］將虛擬機(jī)遷移歸結(jié)為一種多約束的優(yōu)化模型，提出了一種啟發(fā)式虛擬機(jī)整合算法，有效降低了遷移成本和能耗；穆瑞輝［10］提出了一種改進(jìn)的虛擬機(jī)在線遷移算法，依據(jù)各主機(jī)CPU、內(nèi)存和帶寬利用率確定虛擬機(jī)遷移時機(jī)，構(gòu)建了在線遷移算法模型。

2）通過預(yù)測和監(jiān)測主機(jī)負(fù)載來確定遷移時機(jī)，進(jìn)而選擇遷移虛擬機(jī)和目標(biāo)主機(jī)。吳小東等［11］提出了TVMS（Threshold-based energy-efficient VM Scheduling in cloud datacenters）算法，該算法為云數(shù)據(jù)中心基于閾值的虛擬機(jī)遷移節(jié)能調(diào)度算法，能夠動態(tài)預(yù)測虛擬機(jī)的計算性能，計算虛擬機(jī)需求的性能期望值與方差，同時根據(jù)靜態(tài)閾值判斷虛擬機(jī)遷移的時機(jī)，對過載主機(jī)采取虛擬機(jī)遷移，從而降低云能耗；阮順領(lǐng)等［12］針對遷移時機(jī)，提出面向數(shù)據(jù)中心能效優(yōu)化的虛擬機(jī)遷移調(diào)度EEVS（Virtual machine migration Scheduling method optimising Energy-Efficiency of data center）算法，EEVS算法將遷移時機(jī)細(xì)分為三種緊急度，并選擇遷移的虛擬機(jī)，確定目標(biāo)主機(jī)，完成虛擬機(jī)遷移前的準(zhǔn)備工作，對主機(jī)進(jìn)行動態(tài)遷移和整合，減少主機(jī)的運行數(shù)量，以此最小化云能耗；Tian等［13］提出了一種資源動態(tài)調(diào)度模型，考慮主機(jī)與虛擬機(jī)的多維資源，使用方差計算主機(jī)的綜合負(fù)載均衡值；黎紅友等［14］提出了一種負(fù)載感知的技術(shù)模型，該模型通過對主機(jī)負(fù)載均衡值排序與分區(qū)，將虛擬機(jī)遷移到資源最不均衡的主機(jī)；文獻(xiàn)［15］提出了基于虛擬機(jī)遷移的云計算中心節(jié)能調(diào)度REVMS（Virtual Machine migration Scheduling to Reduce Energy consumption in datacenter）算法，針對虛擬機(jī)分配與合并問題，提出一種優(yōu)化的虛擬機(jī)分配與整合調(diào)度算法，提高主機(jī)的資源利用率，并通過關(guān)閉空閑主機(jī)來節(jié)省云能耗。

目前眾多針對虛擬機(jī)遷移的研究，基本都是將主機(jī)的負(fù)載劃分為高負(fù)載和低負(fù)載，采取的遷移策略如表1所示。

通過從高負(fù)載主機(jī)遷出虛擬機(jī)到低負(fù)載主機(jī)上來避免主機(jī)負(fù)載過高，進(jìn)而保持?jǐn)?shù)據(jù)中心的主機(jī)負(fù)載在一個合理的范圍內(nèi)，從而降低數(shù)據(jù)中心的能耗。在選擇低負(fù)載目標(biāo)主機(jī)時，通常需要遍歷所有的低負(fù)載主機(jī)。如果低負(fù)載主機(jī)數(shù)量很多，則虛擬機(jī)選擇范圍較廣，影響算法效率。因此，本文試圖給出基于三支決策的調(diào)度模型，通過將負(fù)載劃分為高負(fù)載區(qū)域、中等負(fù)載區(qū)域、低負(fù)載區(qū)域三個區(qū)域，然后針對性地設(shè)計不同的策略加以調(diào)度，使所有主機(jī)的負(fù)載都收斂在中等負(fù)載的區(qū)域內(nèi)，從而優(yōu)化數(shù)據(jù)中心的總能耗。三支決策［16-22］的基本思想契合了本文需要解決的問題。三支決策是一種有效的復(fù)雜問題處理策略，自從提出以來，廣泛地被應(yīng)用于垃圾郵件過濾［23］、面部識別［24］、政府決策［25］、推薦系統(tǒng)［26］等。

表1 主機(jī)遷移策略Tab.1 Host migration strategy

隨著云計算理論研究工作的深入，不難發(fā)現(xiàn)云計算系統(tǒng)中存在大量三支粒度現(xiàn)象，當(dāng)前開展了諸多基于三支決策的云計算研究，三支決策的相關(guān)算法和模型得以被廣泛研究和使用［27-30］。姜春茂等［31］依據(jù)任務(wù)的延遲時間特性建立三支隊列模型，提出了面向?qū)崟r云任務(wù)的細(xì)粒度合并調(diào)度算法；徐曉霞等［32］提出了一種面向延遲容忍型任務(wù)的移動云計算節(jié)能卸載策略，將卸載分為立即卸載、延遲卸載和不卸載三種決策；吳俊偉等［33］提出了代價敏感的三支聚類評分算法，在任務(wù)平均響應(yīng)時間與資源利用率等方面有顯著效果。

三支決策的核心思想是通過粒度劃分的方式將整體分為互不相交或者弱相交的三個部分或三個子集，并對各個部分或子集采取不同的策略。三支決策理論以三分而治作為基本的理論模型，包括分、治、效三部分。本文借鑒三支決策的基本思想，提出基于三支決策的虛擬機(jī)遷移調(diào)度模型，把主機(jī)按照負(fù)載劃分為高、中、低是“分”；針對三種不同類型的主機(jī)分別采取不同的遷移決策是“治”；最終達(dá)到負(fù)載均衡和節(jié)省能耗是“效”。

2 基于三支決策的虛擬機(jī)遷移調(diào)度模型

本章通過一個實例分析基于三支決策模型的動機(jī)以及本文提出的模型，即基于三支決策的虛擬機(jī)遷移調(diào)度策略（Virtual Machine Migration scheduling strategy based on Three-Way Decision，TWD-VMM）。

2.1 模型提出的動機(jī)

在虛擬機(jī)遷移技術(shù)中，往往是二分主機(jī)負(fù)載，即：當(dāng)主機(jī)負(fù)載大于某閾值時判定為高負(fù)載，主機(jī)負(fù)載小于等于某閾值時判定為低負(fù)載，這是典型的二支決策。在此基礎(chǔ)上，本文將二支情況拓展到三支情況，主機(jī)分為高中低三種類型，即三分主機(jī)負(fù)載。為研究二分主機(jī)與三分主機(jī)在虛擬機(jī)遷移方面的異同，假設(shè)數(shù)據(jù)中心有10 臺不同負(fù)載的主機(jī)，對比二分主機(jī)與三分主機(jī)在虛擬機(jī)遷移的不同決策，如圖1所示。

圖1（a）、（b）有相同的數(shù)據(jù)中心。圖1（a）為二分主機(jī)的遷移決策，將主機(jī)分為高負(fù)載和低負(fù)載。第1 臺主機(jī)負(fù)載為98%，明顯為高負(fù)載，其余9 臺主機(jī)為低負(fù)載。當(dāng)高負(fù)載主機(jī)的虛擬機(jī)遷出時，目標(biāo)主機(jī)的搜索范圍是9 臺低負(fù)載主機(jī)。圖1（b）為三分主機(jī)的遷移決策，分別將主機(jī)分為高負(fù)載、中等負(fù)載和低負(fù)載。第1臺主機(jī)為高負(fù)載，第4、5、6臺主機(jī)負(fù)載為2%，明顯為低負(fù)載，其余6 臺主機(jī)為中等負(fù)載。當(dāng)虛擬機(jī)遷出時，目標(biāo)主機(jī)的搜索范圍是3 臺低負(fù)載主機(jī)，相較于前者極大地縮小了目標(biāo)主機(jī)的搜索范圍。隨著數(shù)據(jù)中心主機(jī)負(fù)載情況越復(fù)雜，三分主機(jī)的虛擬機(jī)遷移策略在縮小目標(biāo)主機(jī)搜索范圍的效果上就會越明顯。假設(shè)虛擬機(jī)遷出后使第1 臺主機(jī)負(fù)載降低10%，目標(biāo)主機(jī)負(fù)載增加10%，分別對基于二分主機(jī)和三分主機(jī)的虛擬機(jī)遷移，統(tǒng)計遷移后10 臺主機(jī)的負(fù)載情況，并計算遷移后主機(jī)負(fù)載方差，設(shè)第i臺主機(jī)負(fù)載表示為Loi，主機(jī)負(fù)載方差如式（1）所示，遷移后負(fù)載結(jié)果如表2所示。

其中：N為主機(jī)數(shù)量；load_avg表示為主機(jī)負(fù)載平均值；load_var表示為主機(jī)負(fù)載方差。

如表2 所示，二分主機(jī)的虛擬機(jī)遷移有3 種方式，分別是虛擬機(jī)遷移到負(fù)載為60%、70%和2%的主機(jī)；三分主機(jī)的虛擬機(jī)遷移只有1 種結(jié)果，即虛擬機(jī)遷移到負(fù)載為2%的主機(jī)。分別計算10 臺主機(jī)的負(fù)載方差，方差越小主機(jī)負(fù)載越均衡。從表2看出虛擬機(jī)遷移到負(fù)載為2%的主機(jī)時負(fù)載方差最小，主機(jī)負(fù)載最均衡。二分主機(jī)的虛擬機(jī)遷移決策有3 種結(jié)果，可能最終的目標(biāo)主機(jī)不是最優(yōu)選擇；而三分主機(jī)在遷移虛擬機(jī)的決策上直接選擇低負(fù)載的主機(jī)。本文根據(jù)負(fù)載將主機(jī)三分有以下優(yōu)勢：

1）減少虛擬機(jī)遷移時對目標(biāo)主機(jī)的搜索范圍，精確虛擬機(jī)選擇目標(biāo)，提高虛擬機(jī)遷移效率。

2）主機(jī)負(fù)載均衡。從表1 看出，將高負(fù)載主機(jī)的虛擬機(jī)遷移到低負(fù)載主機(jī)，更有利于主機(jī)的負(fù)載均衡。

3）本文通過虛擬機(jī)遷移，將所有主機(jī)的負(fù)載收斂到中等區(qū)域內(nèi)，避免主機(jī)負(fù)載過高導(dǎo)致的能耗急劇增加，避免主機(jī)負(fù)載過低導(dǎo)致的資源浪費，達(dá)到節(jié)省能耗的目的。

圖1 二分主機(jī)與三分主機(jī)的虛擬機(jī)遷移決策示意圖Fig.1 Virtual machine migration decisions for two-way hosts and three-way hosts

表2 主機(jī)遷移后負(fù)載情況Tab.2 Load after host migration

2.2 基于三支決策的虛擬機(jī)遷移模型

虛擬機(jī)遷移通常有三個方面：遷移時機(jī)的確定、遷移虛擬機(jī)的選擇，以及目標(biāo)主機(jī)的確定。本文提出的三支決策虛擬機(jī)遷移策略，是將主機(jī)依據(jù)負(fù)載情況劃分為高、中、低三種類型，如果存在高負(fù)載主機(jī)，則立刻從高負(fù)載主機(jī)列表中選擇虛擬機(jī)遷出，從低負(fù)載主機(jī)列表中選擇主機(jī)遷入，如圖2所示。

圖2 遷移總框架Fig.2 Overall framework of migration

從圖2 中可以看出，本文調(diào)度策略中需要研究的兩個方面：1）主機(jī)三分閾值的確定；2）主機(jī)高、中、低的三支治略。從圖2 可知，高負(fù)載主機(jī)和低負(fù)載主機(jī)最終通過虛擬機(jī)的遷移，都收斂成為中等負(fù)載，使所有主機(jī)負(fù)載均衡，從而降低數(shù)據(jù)中心能耗。

3 三支閾值的確定方法

本章主要介紹如何確定三支閾值，即確定一對閾值[α，β]，將主機(jī)劃分為三個集合，分別為高負(fù)載主機(jī)、中等負(fù)載主機(jī)和低負(fù)載主機(jī)集合。

首先初始化閾值α=0.1，β=0.9，設(shè)置閾值浮動值d=0.1。其中閾值的浮動變化有4 種方式：α=α+d、α=α-d、β=β+d和β=β-d，如圖3所示；其次執(zhí)行數(shù)據(jù)中心所有任務(wù)，初始閾值作為根節(jié)點并計算總能耗E，和4 個子節(jié)點的總能耗E′，數(shù)據(jù)中心能耗計算如式（2）；最后比較根節(jié)點與子節(jié)點的能耗，如果存在E′＜E，選擇E′的閾值作為下一次迭代的根節(jié)點，更新閾值[α，β]和總能耗E=E′，重復(fù)上述步驟，迭代1 000次，逐漸收斂閾值范圍。

圖3 閾值樹狀圖Fig.3 Threshold tree

計算閾值的中心任務(wù)：找到最佳閾值，將主機(jī)分為高負(fù)載、中等負(fù)載和低負(fù)載主機(jī)。通過不斷改變閾值，搜索所有閾值可能取到的值，形成閾值樹狀圖。如圖3 所示，層次遍歷計算不同閾值下的數(shù)據(jù)中心能耗，搜索到總能耗最低的閾值，作為該數(shù)據(jù)中心負(fù)載的閾值。式（2）中使用的是文獻(xiàn)［5］的能耗模型：

其中：E表示數(shù)據(jù)中心在時間[t0，t1]內(nèi)的總能耗；e(μ(t))表示為主機(jī)利用率在t時的能耗［5］。

如圖3所示，在層次遍歷過程中，需要遵循以下4點：

1）閾值用于判斷主機(jī)為高負(fù)載還是低負(fù)載，閾值會影響該主機(jī)是否遷移的決策，而不同的遷移決策會影響數(shù)據(jù)中心總能耗大小，因此通過層次遍歷的方式，遍歷閾值可能出現(xiàn)的值，通過比較每種閾值時的能耗，獲得閾值在何值時，數(shù)據(jù)中心的能耗最低，且α值不能大于β。

2）每次迭代都會完整執(zhí)行數(shù)據(jù)中心的所有任務(wù)，在執(zhí)行任務(wù)過程中，主機(jī)負(fù)載是動態(tài)變化的。

3）每次比較根節(jié)點與子節(jié)點的能耗E與E′，選擇總能耗最小的閾值作為下一次迭代的根節(jié)點；如果不存在E′＜E，選擇E′=E的閾值作為下一次迭代的根節(jié)點，暫時不更新[α，β]與E，直到出現(xiàn)E′＜E時再更新。

4）數(shù)據(jù)中心負(fù)載與能耗之間的關(guān)系：數(shù)據(jù)中心一定實際存在高負(fù)載與低負(fù)載的閾值，在該閾值下數(shù)據(jù)中心能耗最低。設(shè)實際閾值為[α′，β′]，如果計算出的[α，β]與實際閾值[α′，β′]不一致，可能出現(xiàn)如圖4的4種情況：

1）若β比實際閾值高，說明存在高負(fù)載主機(jī)被誤判成中等負(fù)載主機(jī)，如圖4（a）所示，介于[β′，β]范圍的主機(jī)為菱形，菱形主機(jī)本身是高負(fù)載，但是由于β閾值的不正確，被錯誤判斷成中等負(fù)載，因此沒有及時遷出虛擬機(jī)，導(dǎo)致數(shù)據(jù)中心存在高負(fù)載主機(jī)，增加數(shù)據(jù)中心總能耗。

2）若β比實際閾值低，說明存在中等負(fù)載主機(jī)被誤判成高負(fù)載主機(jī)，如圖4（b）所示，介于[β′，β]范圍的主機(jī)為菱形，菱形主機(jī)本身是中等負(fù)載，卻被錯誤判斷成高負(fù)載，并通過虛擬機(jī)遷出使該主機(jī)負(fù)載降低，數(shù)據(jù)中心主機(jī)資源沒有充分利用，很可能導(dǎo)致主機(jī)數(shù)量的增加。

3）若α比實際閾值高，說明存在中等負(fù)載主機(jī)被誤判成低負(fù)載，如圖4（c）所示，介于[α′，α]范圍的主機(jī)為菱形，菱形主機(jī)本身是中等負(fù)載，但是由于α閾值的不正確，接受了虛擬機(jī)的遷入導(dǎo)致負(fù)載增加，可能成為高負(fù)載主機(jī)，增加數(shù)據(jù)中心總能耗。

4）若α比實際閾值低，說明存在低負(fù)載主機(jī)被誤判成中等負(fù)載主機(jī)，如圖4（d）所示，介于[α′，α]范圍的主機(jī)為菱形，菱形主機(jī)本身是低負(fù)載，但是沒有接受虛擬機(jī)遷入，仍然是低負(fù)載主機(jī)，導(dǎo)致數(shù)據(jù)中心資源浪費，總能耗增加。

圖4 [α，β]與[α′，β′]不一致的4種情況Fig.4 Four cases of[α，β]differing to[α′，β′]

4 不同負(fù)載主機(jī)的三支遷移策略

本章分別對高、中、低負(fù)載的主機(jī)采取不同“治”。對于高負(fù)載主機(jī)，選擇虛擬機(jī)遷出的決策；對于低負(fù)載主機(jī)，采取接受虛擬機(jī)遷入的決策；對于中等負(fù)載主機(jī)，優(yōu)先采取不遷移，但所有主機(jī)最終都會收斂到中等負(fù)載區(qū)間。因此本章分別闡述三種不同負(fù)載的主機(jī)的不同遷移治略。

在虛擬機(jī)遷移過程中，考慮到主機(jī)屬性的多維性，本文考慮用3 維向量來刻畫主機(jī)性能，其中包括主機(jī)的CPU、內(nèi)存能力和網(wǎng)絡(luò)帶寬能力。定義第i臺主機(jī)的多維資源描述為hi=分別表示為第i臺主機(jī)的CPU、內(nèi)存和網(wǎng)絡(luò)帶寬傳輸能力。定義虛擬機(jī)資源的描述為vr={vrc，vrr，vrb}，同理vrc，vrr，vrb分別表示為虛擬機(jī)請求的CPU、內(nèi)存資源和網(wǎng)絡(luò)帶寬傳輸資源，并且虛擬機(jī)在分配主機(jī)時，目標(biāo)主機(jī)的空閑CPU、內(nèi)存和網(wǎng)絡(luò)帶寬都必須滿足虛擬機(jī)的資源請求，遷出虛擬機(jī)的原主機(jī)和目標(biāo)主機(jī)都需要滿足網(wǎng)絡(luò)傳輸?shù)恼埱筚Y源。

4.1 高負(fù)載主機(jī)遷移策略

高負(fù)載主機(jī)的遷移策略是將虛擬機(jī)遷出，涉及選擇虛擬機(jī)的問題，考慮兩方面因素，分別是主機(jī)預(yù)遷出后多維資源均衡度和主機(jī)負(fù)載下降幅度。

4.1.1 主機(jī)預(yù)遷移后多維資源均衡度

定義1主機(jī)預(yù)遷移后多維資源均衡度。表示第i臺主機(jī)上遷出第j臺虛擬機(jī)后，該主機(jī)的多維資源均衡度為BUij，公式如下：

4.1.2 主機(jī)負(fù)載下降幅度

由于虛擬機(jī)遷移會導(dǎo)致數(shù)據(jù)中心能耗變化，為控制主機(jī)負(fù)載下降的幅度，定義能耗抖動值x；同時在選擇虛擬機(jī)進(jìn)行遷移時需要遵循以下兩點規(guī)則：

1）遷移一次即可，不要多次遷移，因為多次遷移可能會造成原主機(jī)執(zhí)行任務(wù)數(shù)量突然減少，使原主機(jī)負(fù)載下降過多；

2）遷移后的原主機(jī)依然可以保持在中等負(fù)載中較高的主機(jī)負(fù)載。

定義2為保證選擇虛擬機(jī)遷移時遵循以上兩點規(guī)則，定義能耗抖動值x，該值意義在于控制遷出的虛擬機(jī)占主機(jī)CPU比率。

表3 為數(shù)據(jù)中心的主機(jī)CPU 性能（Host_MIPS）與虛擬機(jī)CPU 請求（Vm_MIPS），其中CPU_Utilization為虛擬機(jī)占主機(jī)的CPU比率，計算公式如式（4）所示：

表3 虛擬機(jī)占主機(jī)CPU的比率Tab.3 Ratios of CPU performance of host and virtual machine

從表3 可以看出，數(shù)據(jù)中心有6 種虛擬機(jī)類型、1 種主機(jī)類型，不同類型的虛擬機(jī)對應(yīng)的CPU_Utilization值不相同，分別為8%、14%、22%、25%、27%、40%。假設(shè)目前有3 種主機(jī)負(fù)載，分別為98%、96%、94%，明顯為高負(fù)載主機(jī)，需要遷出虛擬機(jī)。如表4 所示，對3 種高負(fù)載主機(jī)，分別遷移6 種虛擬機(jī)后的負(fù)載情況。

表4 不同虛擬機(jī)遷移后負(fù)載情況Tab.4 Load after different virtual machine migrations

從表4 看出：在選擇遷出的虛擬機(jī)時，如果把負(fù)載為8%、14%的虛擬機(jī)遷出，該主機(jī)仍然可能是高負(fù)載，違背了遷移一次即可的原則；如果把25%、27%的虛擬機(jī)遷出，該主機(jī)可能會成為中等負(fù)載主機(jī)，并且負(fù)載為69%、67%，可能是中等區(qū)域中較高的負(fù)載；如果把40%的虛擬機(jī)遷出，遷出后主機(jī)負(fù)載為56%左右，可能導(dǎo)致原主機(jī)負(fù)載下降過多，違背原主機(jī)遷移后仍保持中等負(fù)載中較高負(fù)載的原則。

隨著數(shù)據(jù)中心越加復(fù)雜，主機(jī)負(fù)載多樣化，以及主機(jī)上虛擬機(jī)類型多樣性等各種因素，遷移虛擬機(jī)對原主機(jī)負(fù)載的影響會越來越大。x取值的作用就是控制遷出虛擬機(jī)對主機(jī)負(fù)載的影響程度，選擇CPU_Utilization趨近于x值的虛擬機(jī)，就是讓遷出后的主機(jī)負(fù)載下降幅度控制在x左右，因此x取值并不是越大越好，也不是越小越好，x取值存在以下兩種情況。

1）x取值大：說明主機(jī)遷出虛擬機(jī)后，該主機(jī)負(fù)載會大幅度下降，可能違反遷移虛擬機(jī)的第2 條規(guī)則，即不能保證遷出后的主機(jī)仍然是中等負(fù)載中較高的負(fù)載，導(dǎo)致主機(jī)資源浪費，可能會增加數(shù)據(jù)中心主機(jī)數(shù)量，總能耗增加。

2）x取值?。赫f明主機(jī)遷出虛擬機(jī)后，該主機(jī)負(fù)載下降幅度小，可能會違反遷移虛擬機(jī)的第1 條規(guī)則，即遷移后主機(jī)仍然是高負(fù)載主機(jī)，數(shù)據(jù)中心能耗增加。

在選擇遷出的虛擬機(jī)時，不僅關(guān)注主機(jī)多維資源均衡度，還關(guān)注虛擬機(jī)遷出后對主機(jī)負(fù)載的影響，因此遷移虛擬機(jī)選擇的目標(biāo)函數(shù)計算如式（5）所示：

其中：BUij值越小，說明該主機(jī)遷移虛擬機(jī)后的多維資源越均衡；|CPU_Utilization-x|表示虛擬機(jī)所占主機(jī)的CPU 利用率與x的偏移程度大小，該值越小，說明該虛擬機(jī)所占主機(jī)的CPU利用率越接近x。綜合考慮兩者的因素，將乘積作為目標(biāo)函數(shù)，選擇虛擬機(jī)的原則是目標(biāo)函數(shù)最小值的虛擬機(jī)作為遷移的虛擬機(jī)。其中需要說明的是：由于BUij是根據(jù)方差計算的，不同虛擬機(jī)的BUij值不同，但是不會出現(xiàn)特別大或者特別小的數(shù)值，且|CPU_Utilization-x|的最大范圍在0 到1 之間，不會存在特別大或者特別小的數(shù)值，所以不存在兩個變量乘積的結(jié)果會因為其中一個變量太大或者太小，造成目標(biāo)函數(shù)的數(shù)據(jù)偏移現(xiàn)象。

4.2 中等負(fù)載主機(jī)遷移策略

中等負(fù)載主機(jī)一般不進(jìn)行遷移，但是考慮到如果低負(fù)載主機(jī)中沒有合適的主機(jī)遷移，該情況下，可以考慮選擇中等負(fù)載主機(jī)。雖然低負(fù)載和中等負(fù)載主機(jī)都是目標(biāo)主機(jī)的選擇范圍，但是選擇優(yōu)先級不同。目標(biāo)主機(jī)選擇總流程如圖5所示。

圖5 目標(biāo)主機(jī)確定流程Fig.5 Target host determination process

選擇目標(biāo)主機(jī)的優(yōu)先級如下：

1）低負(fù)載主機(jī)。

優(yōu)先級最高的是低負(fù)載主機(jī)，其中可能存在以下3 種情況：①低負(fù)載主機(jī)列表為空；②低負(fù)載主機(jī)列表中存在空負(fù)載主機(jī)，將這類主機(jī)添加至空負(fù)載主機(jī)列表，并且不進(jìn)行遷移；③存在低負(fù)載主機(jī)列表，且不包括空負(fù)載主機(jī)，則遍歷該列表，分別計算虛擬機(jī)預(yù)放置該主機(jī)后多維資源均衡度BHk，選擇最小均衡度值的主機(jī)遷移，計算如式（6）所示。

2）中等負(fù)載主機(jī)。

如果低負(fù)載主機(jī)列表中沒有合適放置的主機(jī)，原因有以下兩種情況：①低負(fù)載主機(jī)列表為空；②低負(fù)載主機(jī)列表中都是空負(fù)載主機(jī)，不進(jìn)行遷移。優(yōu)先級為第二的是中等負(fù)載主機(jī)，需要滿足兩點條件：①中等負(fù)載主機(jī)的剩余資源能夠滿足虛擬機(jī)鏡像請求的資源大小；②虛擬機(jī)放置主機(jī)后仍然可以滿足該主機(jī)是中等負(fù)載。如果存在滿足以上兩點條件的主機(jī)列表，分別計算式（6）的多維資源均衡度BHk，選擇均衡度值最小的主機(jī)進(jìn)行遷移。如果以上兩點條件有一條不滿足，就不進(jìn)行遷移。

3）空負(fù)載主機(jī)列表。

如果以上兩類主機(jī)都沒有進(jìn)行遷移，再遍歷空負(fù)載主機(jī)，即需要重新開一臺新主機(jī)。遍歷空負(fù)載主機(jī)列表，選擇第一個滿足資源請求的主機(jī)進(jìn)行遷移，遷入后更新主機(jī)類型。

4.3 低負(fù)載主機(jī)遷移治略策略

低負(fù)載主機(jī)的遷移治略是接受從高負(fù)載主機(jī)遷出的虛擬機(jī)，并通過遷入虛擬機(jī)使主機(jī)負(fù)載增加到中等的區(qū)間內(nèi)，該過程涉及遷移虛擬機(jī)的目標(biāo)主機(jī)選擇問題，本節(jié)考慮兩方面因素：①主機(jī)預(yù)放置后多維資源均衡度；②低負(fù)載主機(jī)資源利用率是否為0，若利用率為0 表示該主機(jī)沒有執(zhí)行任務(wù)，處于休眠狀態(tài)的主機(jī)，定義為空負(fù)載主機(jī)。

4.3.1 主機(jī)預(yù)放置后多維資源均衡度

定義3主機(jī)預(yù)放置后多維資源均衡度，指遷移虛擬機(jī)預(yù)放置在第k臺主機(jī)后，該主機(jī)的多維資源均衡度BHk，計算如式（6）所示：

4.3.2 空負(fù)載主機(jī)

由于低負(fù)載主機(jī)存在兩種狀態(tài)，負(fù)載小于閾值α的主機(jī)和負(fù)載等于0的主機(jī)，因此將負(fù)載等于0的主機(jī)添加至空負(fù)載主機(jī)列表，在不需要重新開一臺主機(jī)的情況下，空負(fù)載主機(jī)不接受虛擬機(jī)的遷入。

4.4 TWD-VMM遷移算法

經(jīng)過上述研究與討論，針對高、中、低三種不同情況的負(fù)載主機(jī)，分別設(shè)計了不同的主機(jī)遷移策略，在本節(jié)將提出一種基于三支決策的虛擬機(jī)調(diào)度算法。

4.4.1 TWD-VMM流程

4.4.2 時間復(fù)雜度分析

TWD-VMM 算法時間復(fù)雜度集中在虛擬機(jī)與主機(jī)的遍歷上，設(shè)置數(shù)據(jù)中心有N臺主機(jī)，每臺主機(jī)上的虛擬機(jī)數(shù)量為m，在最差情況下，虛擬機(jī)在選擇目標(biāo)主機(jī)時需要遍歷所有主機(jī)列表，迭代次數(shù)為O(n×m)，即時間復(fù)雜度為O(N2)。

5 實驗與結(jié)果分析

本文使用Cloudsim 模擬器［34］工具，通過模擬云數(shù)據(jù)中心環(huán)境，主要對比虛擬機(jī)遷移算法TVMS、EEVS、REVMS，分別比較所有主機(jī)負(fù)載平均值、主機(jī)多維資源利用均衡度、數(shù)據(jù)中心總能耗方面的異同。實驗?zāi)M數(shù)據(jù)中心環(huán)境的主機(jī)與虛擬機(jī)參數(shù)如表3 所示，分別在4 種數(shù)據(jù)中心環(huán)境進(jìn)行測試，結(jié)果如表5所示。

表5 四種數(shù)據(jù)中心環(huán)境Tab.5 Four data center environments

實驗采用模擬器CloudSim 進(jìn)行，它因為較好地對于云計算進(jìn)行了建模而得到廣泛的應(yīng)用。實驗所使用的計算機(jī)操作系統(tǒng)為64 位Windows10，內(nèi)存16 GB。在此操作系統(tǒng)上使用Java在IDEA開發(fā)平臺上進(jìn)行實驗。

實驗的內(nèi)容主要包括：計算主機(jī)負(fù)載閾值，并與其他閾值進(jìn)行比較；確定x的取值，并比較有無x下的能耗；將TWDVMM 算法與其他三種虛擬機(jī)遷移算法進(jìn)行能耗、主機(jī)負(fù)載平均值和主機(jī)多維資源均衡度方面的比較。

5.1 閾值確定與比較

計算主機(jī)負(fù)載閾值，分別在4 種數(shù)據(jù)中心環(huán)境下進(jìn)行實驗。根據(jù)第4章所述計算負(fù)載閾值的模型，在4種數(shù)據(jù)中心環(huán)境下分別計算閾值，所得負(fù)載閾值結(jié)果都為［0.3，0.7］，為驗證該閾值下數(shù)據(jù)中心的能耗最低，分別與閾值［0.3，0.8］、［0.2，0.9］、［0.2，0.8］進(jìn)行實驗比較，計算在4 種數(shù)據(jù)中心環(huán)境下的總能耗，能耗比較結(jié)果如表6所示。

表6 不同閾值下的數(shù)據(jù)中心能耗 單位：kWTab.6 Data center energy consumption under different thresholds unit：kW

不同閾值下數(shù)據(jù)中心能耗不同，隨著任務(wù)數(shù)量的增加，數(shù)據(jù)中心總能耗也在增加。從表6 可知，當(dāng)數(shù)據(jù)中心負(fù)載閾值為［0，2，0.8］時，能耗相對最高，原因是上閾值太高，下閾值太低，導(dǎo)致大多數(shù)主機(jī)判斷不準(zhǔn)確，不能作出正確的遷移決策，遷移后的主機(jī)仍然存在高負(fù)載和低負(fù)載的情況，造成數(shù)據(jù)中心資源浪費，能耗增加，因此合理的主機(jī)閾值確實可以降低總能耗。當(dāng)數(shù)據(jù)中心負(fù)載閾值為［0.3，0.7］時，分別在4 種數(shù)據(jù)中心環(huán)境下，都可以保持最低的能耗，說明［0.3，0.7］作為負(fù)載閾值最優(yōu)。在之后的實驗中，可以不用重新計算數(shù)據(jù)中心負(fù)載閾值，使用［0.3，0.7］即可。

5.2 能耗抖動x值確定

根據(jù)5.1節(jié)所述，x用于控制遷出虛擬機(jī)對主機(jī)負(fù)載的影響程度，合理的x取值可以遵循虛擬機(jī)遷移的兩條規(guī)則。為研究x的取值，本節(jié)分別取x=0.1，0.2，0.3 時，計算4 種數(shù)據(jù)中心環(huán)境下總能耗如圖6所示。

圖6 x取值比較Fig.6 x value comparison

從圖6 可以看出，隨著x取值的不同，數(shù)據(jù)中心能耗也在發(fā)生變化，通過比較得出，當(dāng)x取值為0.2時總能耗最低，說明當(dāng)限制遷移虛擬機(jī)后，控制原主機(jī)負(fù)載降低20%左右時，能保證較低的數(shù)據(jù)中心總能耗，因此統(tǒng)一設(shè)置x取值為0.2。

為證明x取值具有實際意義，分別在4 種數(shù)據(jù)中心環(huán)境下，對比有x約束和無x約束兩種情況的數(shù)據(jù)中心總能耗，如表7所示，可以看出，在有x約束的情況下，數(shù)據(jù)中心總能耗比沒有x約束的總能耗低，說明x的約束條件是有存在意義的，能夠有效選取虛擬機(jī)，并控制虛擬機(jī)遷出后對主機(jī)負(fù)載的影響。

表7 有無x約束的數(shù)據(jù)中心總能耗 單位：kWTab.7 Total energy consumption of data center with or without x constraint unit：kW

5.3 能耗比較

將TWD-VMM 算法與TVMS、EEVS、REVMS 三種算法分別在虛擬機(jī)遷移時機(jī)和遷移調(diào)度上進(jìn)行研究，比較它們與本文算法的數(shù)據(jù)中心總能耗，結(jié)果如表8所示。

表8 四種算法在四種數(shù)據(jù)中心環(huán)境下總能耗 單位：kWTab.8 Comparison of total energy consumption of four algorithms under 4four data center environments unit：kW

從表8 可以看出，REVMS 算法的數(shù)據(jù)中心能耗最高，該算法尋找負(fù)載最小的主機(jī)，并將其主機(jī)上所有的虛擬機(jī)遷出，并對其下電操作，但是對高載主機(jī)選擇恰當(dāng)?shù)奶摂M機(jī)遷移沒有較好的決策，因此導(dǎo)致能耗較高。TVMS算法在4種數(shù)據(jù)中心下能耗較高，由于該算法在調(diào)度過程中，通過結(jié)合靜態(tài)閾值和主機(jī)動態(tài)預(yù)測進(jìn)行虛擬機(jī)遷移，計算主機(jī)所需的CPU 期望值和標(biāo)準(zhǔn)差，進(jìn)而估算主機(jī)的CPU 需求量可能達(dá)到的值，來決定遷移的時機(jī)，但是估算的準(zhǔn)確性很大程度上影響虛擬機(jī)遷移的判斷，說明合理的遷移判斷能夠有效地節(jié)省數(shù)據(jù)中心總能耗。從實驗比較發(fā)現(xiàn)，本文TWD-VMM 算法無論在哪種數(shù)據(jù)中心環(huán)境下執(zhí)行任務(wù)，都可以保持最低的數(shù)據(jù)中心總能耗，說明本文的TWD-VMM算法最優(yōu)。

5.4 主機(jī)負(fù)載平均值比較

主機(jī)負(fù)載平均值是所有主機(jī)的CPU 利用率的平均值，代表主機(jī)的負(fù)載程度，主機(jī)負(fù)載動態(tài)規(guī)律如下：1）高負(fù)載主機(jī)通過虛擬機(jī)遷出使得該主機(jī)負(fù)載降低，負(fù)載達(dá)到平穩(wěn)且繼續(xù)執(zhí)行任務(wù)；2）主機(jī)上任務(wù)執(zhí)行結(jié)束的過程中，該主機(jī)的負(fù)載動態(tài)呈現(xiàn)下降的趨勢；3）當(dāng)主機(jī)上所有任務(wù)結(jié)束完成，該主機(jī)的負(fù)載為0。收集主機(jī)所有時刻的負(fù)載情況，計算主機(jī)負(fù)載平均值如圖7所示。

圖7 主機(jī)負(fù)載平均值比較Fig.7 Average host load comparison

如果負(fù)載平均值太低，意味著主機(jī)的CPU 資源沒有充分利用；如果負(fù)載平均值太高，說明任務(wù)在運行過程中，存在并可能長期存在高負(fù)載的狀態(tài)，云環(huán)境服務(wù)水平較低。從圖7得出，REVMS 算法負(fù)載平均值在0.9 左右，相較于其他算法負(fù)載偏高，存在大量主機(jī)都在高負(fù)載狀態(tài)。EEVS 算法和TWD-VMM 算法的負(fù)載平均值在0.75 左右，為觀察TWDVMM 算法在執(zhí)行過程中負(fù)載的動態(tài)情況，隨機(jī)選取20 臺主機(jī)，獲取1 s 到10 s 內(nèi)主機(jī)歷史數(shù)據(jù)的負(fù)載情況，如圖8～9所示。

圖8 前10臺主機(jī)負(fù)載圖Fig.8 Load diagram of first 10 hosts

圖9 后10臺主機(jī)負(fù)載圖Fig.9 Load diagram of last 10 hosts

如圖8～9 所示，當(dāng)主機(jī)在1 s 時正在執(zhí)行任務(wù)，該時刻的主機(jī)CPU 利用率有以下3種情況：1）主機(jī)為高負(fù)載；2）主機(jī)為中等負(fù)載；3）主機(jī)為低負(fù)載。從圖8～9中可以看出：2 s之后主機(jī)的負(fù)載開始發(fā)生變化，高負(fù)載主機(jī)通過遷出虛擬機(jī)使負(fù)載降低，低負(fù)載主機(jī)通過遷入虛擬機(jī)使負(fù)載增加。并且在3 s時所有低負(fù)載和高負(fù)載主機(jī)通過虛擬機(jī)遷移都收斂到中等負(fù)載的區(qū)間。同時11 s后，主機(jī)還會接收新的任務(wù)，導(dǎo)致主機(jī)負(fù)載增加，因此主機(jī)的負(fù)載平均值在0.75 左右，意味著單位時間檢測主機(jī)負(fù)載時，存在中等負(fù)載的主機(jī)，也存在由于執(zhí)行新任務(wù)而負(fù)載增加的主機(jī)，但從圖8～9 可以看出TWD-VMM 符合虛擬機(jī)遷移的兩條規(guī)則，即遷移一次即可，和遷移后仍然保持較高的中等負(fù)載。

5.5 主機(jī)多維資源均衡度比較

主機(jī)多維資源均衡度計算如式（7）所示：

其中：ahi表示該主機(jī)的三維資源平均值；vhi表示三維資源方差；VH為計算數(shù)據(jù)中心的所有主機(jī)方差平均值，數(shù)值越小說明主機(jī)的多維資源越均衡表示第i臺主機(jī)已使用的CPU資源同理。如圖10 可以看出，TWD-VMM 算法的主機(jī)多維資源均衡較低，雖然與其余算法比較優(yōu)勢不明顯，但是TWD-VMM 算法具有較高的CPU 利用率，主機(jī)多維資源均衡度低，說明主機(jī)不但能夠利用充分CPU 資源，而且內(nèi)存、帶寬資源也能夠充分利用，有利于數(shù)據(jù)中心資源的多種資源的充分利用。

圖10 主機(jī)多維資源均衡度比較Fig.10 Comparison of multidimensional resource balance of host

6 結(jié)語

通過引入三支決策的方法，本文提出的虛擬機(jī)遷移調(diào)度算法TWD-VMM 將主機(jī)分為高負(fù)載主機(jī)、中等負(fù)載主機(jī)和低負(fù)載主機(jī)，然后分別對高、中、低負(fù)載主機(jī)在遷移時采取不同的策略，通過高負(fù)載主機(jī)的遷出與低負(fù)載主機(jī)的遷入，將所有主機(jī)負(fù)載最終收斂到中等負(fù)載的區(qū)間內(nèi)，實現(xiàn)負(fù)載均衡，節(jié)省數(shù)據(jù)中心能耗。本文對于如何確定不同負(fù)載類型的主機(jī)，即三支閾值確定方法，作出了詳細(xì)的闡述。實驗結(jié)果表明，TWD-VMM 算法無論在哪種數(shù)據(jù)中心環(huán)境下，相較于其他三種對比算法，在資源利用充分、總能耗降低等方面有明顯效果。

在未來工作中，可以將三支決策的理論更多地運用在優(yōu)化云能耗問題上，包括對主機(jī)性能的更細(xì)粒度劃分，和更細(xì)粒度的調(diào)度算法優(yōu)化等方面進(jìn)一步研究，并在虛擬機(jī)遷移技術(shù)上追求其他更多指標(biāo)等。