融合喚醒閾值與半休眠模式的云虛擬機調度策略

李吉良，秦 兵，李文江，金順福，王志斌

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.通信網信息傳輸與分發技術國家重點實驗室，河北 石家莊 050081；3.燕山大學 信息科學與工程學院，河北 秦皇島 066004；4.燕山大學 電氣工程學院，河北 秦皇島 066004)

0 引言

在云平臺中，云服務提供商負責管理和分配云上的所有數據與資源，用戶則按需獲取資源。毫無疑問，這些資源對于用戶和云提供商來說，是非常重要的資產。平衡云用戶與云提供商兩者利益的關鍵在于合理分配云資源[1-2]。越來越多的研究專注于以降低云計算數據中心能耗和提高系統資源利用率為目標的云計算資源管理。

Saikrishna等[3]將Web服務器看成一個含有兩種控制輸入(虛擬機個數和工作量)的可變容量系統，針對系統控制輸入頻繁改變的問題，建立了一個多輸入多輸出的線性變參數(Linear Parameter-Varying，LPV)系統，設計了一種增益調度線性二次型調節控制器用于保證性能。Paya等[4]提出了一種應用于云負載均衡與云應用擴展的能量感知操作模型，通過最大化運行服務器的工作負載，將空閑和低負載的服務器轉換為休眠狀態，達到節能的目的。Singh等[5]提出了一個能量高效的自優化云計算系統，用于數據中心云資源的高效調度，將能量視為服務質量參數，通過降低能量消耗優化云資源的使用。

以上研究只是考慮了云計算的能量節省而忽略了響應性能的要求。本文綜合云平臺上的能量消耗和云用戶請求的響應性能，將喚醒閾值與半休眠模式相結合，提出一種新型的云虛擬機調度策略。將云平臺上的虛擬機與云用戶請求抽象為服務臺和顧客，構造一個帶有策略和多重異步工作休假的多服務臺排隊系統。結合虛擬機狀態和云用戶請求數量，構造二維連續時間馬爾科夫(Markov)鏈，采用矩陣幾何解方法，推導系統節能率與云請求平均逗留時間的表達式，評估云虛擬機調度策略的系統性能。按照云虛擬機調度策略的工作原理進行仿真實驗，得到相對應的性能指標的統計結果。比較數值分析結果和仿真實驗的統計結果，驗證所提策略的可行性及模型解析的正確性。綜合不同的性能指標建立成本函數，利用蟻群智能尋優算法，得到使系統成本最小的喚醒閾值與半休眠參數，進而給出云虛擬機調度策略的優化方案。

1 云虛擬機調度策略及系統模型

1.1 云虛擬機調度策略

在傳統的云平臺中，即便沒有任何云用戶請求，虛擬機仍要以正常速率運行，從而增加了能量消耗。

置空閑的虛擬機于休眠模式，可以有效降低系統的能耗水平，但云用戶請求的響應性能將受很大影響。半休眠機制是指虛擬機在休眠期間以較低的速率為云用戶請求提供服務，而不是完全停止服務。引入半休眠機制實質是使系統中的虛擬機以兩種不同服務速率交替運行，以解決節能水平與響應性能之間的矛盾。

為了減少速率轉換帶來的額外耗能，在半休眠模式中引入喚醒閾值N。只有當云緩沖區中的云用戶請求數量大于或等于喚醒閾值N時，虛擬機才可能從半休眠階段進入喚醒階段，以正常速率為云用戶請求提供服務。基于此，提出一種融合喚醒閾值與半休眠模式的云虛擬機調度策略。策略中喚醒閾值N與虛擬機的數量c一定滿足N≥c。

將云平臺中虛擬機狀態分為低速空閑、低速工作與正常工作，描述云虛擬機調度策略如下。

1) 當虛擬機以正常速率完成一個云用戶請求的服務時，如果云緩沖區中沒有其他云用戶請求排隊等待，虛擬機將進入半休眠階段，啟動半休眠定時器，開始一次新的半休眠周期，虛擬機由正常工作狀態轉換為低速空閑狀態；否則，虛擬機將繼續以正常速率為云緩沖區中排隊等待的第一個云用戶請求提供服務，即保持在正常工作狀態。

2) 處于低速空閑狀態的虛擬機可以立即為新到達的云用戶請求提供服務，虛擬機由低速空閑狀態轉換為低速工作狀態。當虛擬機處于低速空閑狀態時，如果半休眠定時器到期，虛擬機將重新啟動半休眠定時器，開始一次新的半休眠周期，即保持在低速空閑狀態。

3) 當虛擬機以低速率完成一個云用戶請求的服務時，如果云緩沖區中沒有其他云用戶請求排隊等待，虛擬機由低速工作狀態轉換為低速空閑狀態；否則，虛擬機將繼續以低速率為云緩沖區中排隊等待的第一個云用戶請求提供服務，即保持在低速工作狀態。

4) 處于低速工作狀態的虛擬機在半休眠定時器到期時，統計云緩沖區中排隊等待的云用戶請求數量。如果云緩沖區中排隊等待的云用戶請求數量大于或等于喚醒閾值時，虛擬機將進入喚醒階段，以正常速率為未完成的云用戶請求持續提供服務，虛擬機由低速工作狀態轉換為正常工作狀態；否則，虛擬機將重新啟動半休眠定時器，開始一次新的半休眠周期，繼續以低速率為未完成的云用戶請求提供服務，即保持在低速工作狀態。

1.2 系統模型

考慮云平臺上的一臺物理機。假設在這臺物理機上部署多個虛擬機，稱之為虛擬機集群。將半休眠模式抽象成工作休假，每個半休眠周期為一次工作休假；將虛擬機和云用戶請求分別抽象成服務臺和顧客。根據所提出的云虛擬機調度策略的工作原理，建立一個帶有N策略和多重異步工作休假的連續時間排隊模型。

假設云用戶請求的到達時間間隔服從參數為λ的指數分布。假設處于正常工作狀態的虛擬機服務一個云用戶請求的時間服從參數為μh(μh>0)的指數分布，處于低速工作狀態的虛擬機服務一個云用戶請求的時間服從參數為μl(μl>0)的指數分布，且μh>μl。假設一次半休眠過程的時間長度服從參數為的θ(θ>0)指數分布，稱θ為半休眠參數。當一次半休眠結束時，如果云緩沖區中的云用戶請求數量大于或等于喚醒閾值N，虛擬機立即停止半休眠，服務率由μl提高至μh，此時云用戶請求將以正常速率繼續接受服務；否則，虛擬機重新開始一次獨立同分布的半休眠過程。基于以上假設，得出系統的穩態條件為λ

令L(t)表示t時刻云用戶請求的數量，J(t)表示t時刻處于正常工作狀態的虛擬機數量。{L(t)=k,J(t)=j,t≥0}表示系統的狀態，其狀態空間為

Ω={(k,j)|k∈{0,1,2,…},

j∈{0,1,2,…,c}}。

2 模型解析

{L(t)=k,J(t)=j,t≥0}構成一個二維連續時間Markov鏈[6]。假設{L(t)=k,J(t)=j,t≥0}正常返，令πkj表示二維連續時間Markov鏈的穩態分布。πkj定義為

πkj=limP{L(t)=k,J(t)=j},(k,j)∈Ω。

令πk(k≥0)表示在穩定狀態下系統水平的概率分布，則

πk=(πk0,πk1,πk2,…,πkc),k≥0

Π=(π0,π1,π2,…)。

2.1 狀態轉移過程

在Markov鏈的狀態轉移過程中，第n次結果只受第n-1次的結果的影響。故根據一步轉移原則，系統狀態變化分析如下：

1) 系統中云用戶請求數量由k(k>0)變為k-1，說明有一個云用戶請求離開系統。

當0

當1

當0

當k>c且j≤c時，系統中有(c-j)個虛擬機低速率工作，有j個虛擬機正常速率工作。云用戶請求無論是由低速率工作的虛擬機完成，還是由正常速率工作的虛擬機完成，系統狀態都由(k,j)轉移到(k-1,j)，轉移率為(c-j)μl+μh。

2) 系統中的云用戶請求數量保持在k(k≥0)，說明既沒有云用戶請求離開也沒有云用戶請求到達。

當0

當1

當0

當k>c且j≤c時，系統中有(c-j)個虛擬機低速率工作，有j個虛擬機正常速率工作。系統狀態保持不變的轉移率為-(λ+(c-j)μl+jμh)。

當k≥c+N且j≤c時，系統中的虛擬機有(c-j)個低速率工作，有j個正常速率工作。如果某個低速率工作的虛擬機半休眠定時器到期，該虛擬機進入喚醒階段，系統狀態由(k,j)轉移到(k,j+1)，轉移率為(c-j)θ；否則，系統狀態保持不變，轉移率為-(λ+(c-j)μl+jμh+(c-j)θ)。

3) 系統中的云用戶請求數量由k(k≥0)變為k+1，說明有一個云用戶請求到達系統。

當新的云用戶請求的到達系統時，系統狀態由(k,j)轉移到(k+1,j)，轉移率為λ。

2.2 平穩分布

令Q表示二維連續時間Markov鏈的一步轉移率矩陣。根據狀態轉移過程，在任意時刻，系統中的云用戶請求數量只能減少一個、固定不變或增加一個，即轉移只能發生在相鄰狀態。

1) 系統中的云用戶請求數量減少一個。

當1≤k≤c時，子塊Bk是一個(k+1)×k的非負矩陣，Bk表示為

k-1,0k-1,1k-1,2…k-1,k-1

(1)

當k>c時，子塊Bk是一個c+1階方陣，Bk表示為

k-1,0k-1,1 …k-1,c-1k-1，c

(2)

2) 系統中的云用戶請求數量固定不變。

當k=0時，子塊A0退化為一個數值，表示為

A0=-λ。

(3)

當1≤k≤c時，子塊Ak是一個k+1階含負對角線元素的方陣，Ak表示為

k,0k,1…k，k-1k，k

其中，αx=-(λ+(x-1)μh+(k-x+1)μl),1≤x≤k+1。

當c

k,0k,1…k，c-1k，c

(5)

其中，βy=-(λ+(y-1)μh+(c-y+1)μl),1≤y≤c+1。

當k≥c+N時，子塊Ak是一個c+1階方陣，Ak表示為

k,0k,1k，2…k，c

(6)

其中，φz=-(λ+(c-z+1)μl+(z-1)μh+(c-z+1)θ),1≤z≤c+1。

3) 系統中的云用戶請求數量增加一個。

當k=0時，子塊C0退化為一個數值，表示為

C0=λ。

(7)

當1≤k≤c時，子塊Ck是一個(k+1)×(k+2)階矩陣，Ck表示為

k-1,0k-1,1…k-1,k-1k-1,kk-1,k+1

(8)

當k≥c時，子塊Ck是一個c+1階方陣，Ck表示為

Ck=λI,

(9)

其中，I是c+1階單位矩陣。

由上述子塊的表示形式可知，當k≥c+N時，子塊Bk，Ak，Ck中的元素不再變化。將重復的子塊Bk，Ak，Ck(k≥c+N)分別記作B，A,C。子塊B，A,C分別表示為

(10)

(11)

其中，ξp=-(λ+(c-p+1)μl+(p-1)μh+(c-p+1)θ),1≤p≤c+1。

C=λI,

(12)

其中，I是c+1階單位矩陣。

綜合以上分析，給出二維連續時間Markov鏈的一步轉移率矩陣令Q為

由矩陣Q的結構可知，二維連續時間Markov鏈{L(t),J(t),t≥0}是一個擬生滅過程(QBD)[7-8]。QBD正常返的充分必要條件是矩陣二次方程R2B+RA+C=0的最小非負解R的譜半徑SP(R)<1。由式(10)～(12)可知，B,A，C都是上三角形式的矩陣，可知率陣R必然也是上三角形式的。設

(13)

將R，B，A，C代入矩陣二次方程得到矩陣R。

由矩陣幾何解方法[9-10]可得ΠB[R]=0，其中

(14)

二維連續時間Markov鏈的平穩分布滿足

(15)

其中，e1是(C+N)×(c+1)列全1向量，e2是c+1列全1向量，I是c+1階單位矩陣。

通過式(15)可以給出系統穩態分布πk(k≥0)的數值解。

3 系統性能指標

基于系統模型的穩態解，分析融合喚醒閾值與半休眠模式的云虛擬機調度策略的性能指標。

1) 定義云用戶請求平均逗留時間W為一個云用戶請求從進入系統開始到離開系統時刻所經歷的平均時間長度(包括在云緩沖區中的等待時間與在虛擬機上接受服務的時間)。云用戶請求平均逗留時間是衡量系統中云用戶請求服務質量的重要指標。由Little公式[11]可知，云用戶請求平均逗留時間W表達式為

(16)

2) 定義系統節能率φ為單位時間內因設置喚醒閾值與半休眠模式而節省的能量消耗。系統節能率是衡量云平臺上節能策略有效性的重要指標。在所提出的云虛擬機調度策略中，在半休眠階段，假設處于工作狀態的虛擬機單位時間消耗能量為ωlb，處于空閑狀態的虛擬機單位時間消耗能量為ωli；在喚醒階段，假設處于工作狀態和空閑狀態的虛擬機單位時間消耗能量分別為ωhb和ωhi；將單位時間內虛擬機由半休眠階段轉入喚醒階段時所消耗的能量記為ωt。系統節能率φ表達式如下：

φ=(ωhi-ωliμl)·Nidle+(ωhb-ωlbμl)
Nbusy-ωtNtransterθ，

(17)

4 數值與仿真實驗

為了驗證融合喚醒閾值與半休眠模式的云虛擬機調度策略的有效性，并進一步分析系統參數對系統性能的影響，進行數值與仿真實驗，定量刻畫云用戶請求平均逗留時間與系統節能率的變化趨勢。系統實驗的運行環境：MATLAB R2011a，Eclipse，Intel Core i7-4790 CPU @ 3.60 GHz，8.00GB RAM。數值分析實驗在MATLAB環境下運行，仿真實驗在Eclipse環境下使用Java語言運行。

在保證系統平穩的前提下，參數的具體取值不會影響系統性能指標的變化趨勢。本文的實驗參數設置如下：系統中虛擬機數量c=10臺，云用戶請求到達率λ=5.0 s-1，正常工作服務率μh=2.0 s-1，處于喚醒階段空閑虛擬機的能量消耗ωhi=0.55 mW，處于喚醒階段工作虛擬機的能量消耗ωhb=0.62 mW，處于半休眠階段空閑虛擬機的能量消耗ωli=0.5 mW，處于半休眠階段工作虛擬機的能量消耗ωlb=0.6 mW，由半休眠階段切換到喚醒階段虛擬機的能量消耗ωt=2.5 mJ。

針對不同的喚醒閾值N與不同的虛擬機低速服務率μl，云用戶請求平均逗留時間W隨半休眠參數θ的變化趨勢如圖1所示。

圖1 云用戶請求平均逗留時間的變化趨勢
Fig.1 Cloud users request an average trend of stay time

對比圖1(a)與(b)可知，當虛擬機低速服務率μl與半休眠參數θ一定時，隨著喚醒閾值N的增大，云用戶請求平均逗留時間W增加。當喚醒閾值較大時，虛擬機處于半休眠階段的時間延長，更多的云用戶請求被低速工作的虛擬機處理，虛擬機處理云用戶請求的時間延長，因此云用戶請求平均逗留時間增加。

分別觀察圖1中的(a)與(b)可知，當喚醒閾值N與半休眠參數θ一定時，隨著低速服務率μl的增大，云用戶請求平均逗留時間W減少。當低速服務率較大時，低速工作的虛擬機處理云用戶請求的時間縮短，因此云用戶請求平均逗留時間減少。

由圖1中的(a)與(b)可知，當喚醒閾值N與低速服務率μl一定時，隨著半休眠參數θ的增大，云用戶請求平均逗留時間W減少。在等待的云用戶請求數量達到喚醒閾值的情況下，當半休眠參數較大時，低速工作的虛擬機將更早地切換到正常工作狀態。正常工作的虛擬機將以更快的速度處理云用戶請求，因此云用戶請求平均逗留時間減少。

針對不同的喚醒閾值N與不同的虛擬機低速服務率μl，系統節能率φ隨半休眠參數θ的變化趨勢如圖2所示。

圖2 系統節能率的變化趨勢
Fig.2 Trend of system energy saving rate

對比圖2中的(a)與(b)可知，當虛擬機低速服務率μl與半休眠參數θ一定時，隨著喚醒閾值N的增大，系統節能率φ增加。當喚醒閾值較大時，虛擬機處于半休眠階段的時間延長，虛擬機在半休眠階段所消耗的能量較小，故系統節能率增加。

分別觀察圖2中的(a)與(b)可知，當喚醒閾值N與半休眠參數θ一定時，隨著低速服務率μl的增大，系統節能率φ降低。當低速服務率提高時，虛擬機所消耗的能量隨之增加，故系統節能率降低。

由圖2中的(a)與(b)可知，當喚醒閾值N與低速服務率μl一定時，隨著半休眠參數θ的增大，系統節能率φ降低。當半休眠參數較大時，低速工作的虛擬機將更早地切換到正常工作狀態，正常工作的虛擬機所消耗的能量較大，故系統節能率降低。

以上的實驗結果表明，云平臺上的喚醒閾值N，低速服務率μl，半休眠參數θ對系統性能有著不容忽視的影響。喚醒閾值的加大使得云用戶請求平均逗留時間與系統節能率均增加；低速服務率的提高使得云用戶請求平均逗留時間與系統節能率均減小；半休眠參數的增大使得云用戶請求平均逗留時間與系統節能率均減小。綜上可知，不同參數對系統性能有著折中影響。為了能夠更合理地滿足云用戶響應要求與最大限度地提高云平臺能量效率，需要對喚醒閾值與半休眠參數進行聯合優化。

5 系統優化

為了平衡云用戶請求平均逗留時間與系統節能率之間的折中關系，構造系統成本函數F為

F=fWW2-fφφ，

(18)

其中，fW為云用戶請求二次逗留時間影響因子，fφ為系統節能率影響因子。云用戶請求平均逗留時間W由式(16)給出，系統節能率φ由式(17)給出。

沿用第4章給出的系統參數，并以fW=3.0，fφ=0.8為例，針對不同的低速服務率μl，進行系統實驗，揭示喚醒閾值N與半休眠參數θ對系統成本函數F的影響。實驗結果如圖3所示。

圖3 系統成本函數的變化趨勢
Fig.3 Trend of system cost function

觀察圖3可知，對于一定的低速服務率μl來說，適當地選取喚醒閾值N與半休眠參數θ，可以最小化成本函數F。針對每一個可選喚醒閾值，利用蟻群智能尋優算法找出最優半休眠參數θ以及最小成本。結合所選定的喚醒閾值及與喚醒閾值相關的最優半休眠參數，構造可選二元組(N,θ)。在全部的可選二元組中，進一步選取最小成本函數F*所對應的二元組，即喚醒閾值與半休眠參數最優組合(N*,θ*)。尋優結果如表1所示。

表1 喚醒閾值與半休眠參數的聯合優化結果
Tab.1 Joint optimization result of wake-up threshold and semi-dormant parameter

低速服務率μl/s-1喚醒閾值與半休眠參數最優組合(N*,θ*)最小成本函數F*0.85(3,0.986 1)3.333 10.90(4,1.082 7)3.078 50.95(4,0.584 8)2.890 51.00(5,0.573 7)2.761 4

6 結論

融合喚醒閾值與半休眠模式提出了一種最小化云平臺成本的云虛擬機調度策略。喚醒閾值的引入可以提高云平臺的節能效率；半休眠模式的引入可以滿足云用戶請求的響應要求。綜合云平臺上云用戶請求數量與以正常速率服務的虛擬機數量，建立二維連續時間Markov鏈，利用矩陣幾何解方法，給出了系統性能指標的表達式。分別采用MATLAB與Eclipse進行數值分析與系統仿真實驗，實驗結果表明，適當地選取喚醒閾值與半休眠參數，可以使所提出的云虛擬機調度策略在保證云用戶請求響應性能的同時提高云平臺節能效率。折中云用戶請求平均逗留時間與系統節能率，構造成本函數，進行策略參數的聯合優化，實現了系統成本的最小化。