面向異構物理機的云任務調度策略及性能優化①

范寶芝 王開宇 白小軍 金順福

(燕山大學信息科學與工程學院 秦皇島066004)

0 引言

隨著無線通訊技術的發展,網絡應用程序的使用越來越多。移動設備負載能力不足的問題日趨明顯,云計算為移動設備的任務卸載提供支持[1]。值得注意的是,不斷增長的云應用導致云數據中心消耗著巨大的能源,對環境也產生了惡劣的影響。研究發現,按照每年40%～60%的增長率估算,到2030 年云數據中心的能源消耗將達到8000 TWh[2]。綠色云計算是社會進步的必然趨勢,也是實現可持續發展的前提。緩解云數據中心的高耗能問題是云計算研究的重點內容之一。

文獻[3]提出了一種動態遷移虛擬機的調度方法,通過建立一個虛擬機放置/遷移的平臺,使用兩個調度程序分別調度預期的負載和未預期的負載,有效降低了云數據中心的功耗。文獻[4]提出了一種動態的空閑間隔預測方案,該方案可以估計未來中央處理器(central processing unit,CPU)空閑間隔長度,選擇考慮成本效益的休眠狀態以最小化運行功耗,并提高CPU 的利用率。以上文獻專注于降低云系統的能源消耗,卻忽略了云用戶對響應性能的需求。

考慮到云用戶對響應性能的需求,文獻[5]提出了一種基于(N,T) 休眠機制的云計算中心節能策略。結合喚醒閾值N及長度為T的休眠計時器,建立多重同步休假隨機模型。利用改進飛蛾撲火優化算法,給出了節能策略的聯合優化方案,實驗證實所提策略在保證用戶響應性能的基礎上,有效降低了系統能耗。文獻[6]提出了一種基于動態閾值的服務器喚醒策略。該策略綜合考慮用戶端的任務情況和服務器的能耗成本,動態調整任務請求數的閾值,并根據時間優先級喚醒服務器。與靜態閾值的服務器喚醒策略相比,該策略有效降低了云計算系統的能耗開銷。以上研究專注于云系統本身,未考慮產生任務的移動設備及移動設備自身的處理能力。

本文綜合考慮云用戶響應性能及云系統的能源消耗,基于部分用戶任務在移動設備本地處理器執行的實際情況,提出一種移動設備本地處理器持續工作和云端物理機內虛擬機同步休眠的任務調度策略。針對云端異構物理機的不同服務速率,在遠程云端建立多個帶有同步多重休假的M/M/ck排隊模型。利用擬生滅過程和矩陣幾何解給出系統模型的穩態分布,通過系統實驗揭示任務平均響應時間與系統平均運行功率的變化趨勢。構造系統成本函數,引入Logistic 映射混沌機制改進傳統鯨魚優化算法,給出最優任務分配策略,實現系統成本的最小化。

1 任務調度策略及系統模型

1.1 任務調度策略

針對移動設備存儲空間不足且處理能力有限等問題,借助于遠程云端的幫助,移動設備任務負載能夠有效地得到均衡。在任務調度器的協調下,將移動設備產生的任務分為兩部分,一部分任務分配到本地處理器接受服務,另一部分任務則卸載到遠程云端的虛擬機上接受服務。

遠程云端部署多個異構物理機,物理機的集合表示為S={S1,S2,…,Sn},| S|=n。通過虛擬化技術在物理機Sk(k=1,2,…,n) 上部署ck(ck≥1)個云虛擬機。假設部署在同一臺物理機上的虛擬機同構,不同物理機上的虛擬機異構[7]。給出由本地移動設備和遠程云端組成的體系結構,如圖1 所示。

圖1 移動設備與遠程云端構成的體系結構

傳統云服務中,云服務器一直處在活躍狀態,增加了遠程云端的能源消耗。休眠機制是一種有效減少能源消耗的人為手段。借助于虛擬化技術,在同一臺物理機上的虛擬機中引入周期性同步休眠機制,不同物理機上的虛擬機引入周期性異步休眠機制。在每個物理機上設置一個休眠定時器。當物理機上的全部任務結束服務時,該定時器觸發,部署在該物理機上的全部虛擬機同時進入休眠狀態。不同物理機上的定時器的觸發相互獨立,也就是說,一個物理機上的虛擬機的休眠或喚醒,與另一個物理機上虛擬機無關。

基于所提出的體系結構,遠程云端上的虛擬機具有3 種狀態:活躍狀態、空閑狀態和休眠狀態。虛擬機的狀態轉換過程如圖2 所示。

圖2 虛擬機的狀態轉移過程

(1) 活躍狀態。處于活躍狀態的虛擬機為某一個任務提供服務。虛擬機服務完成當前任務后,按先來先服務規則為緩存區中等待的任務提供服務。若緩存區空,但其他虛擬機未全部空閑,則該虛擬機由活躍狀態切換到空閑狀態。若緩存區空且所有虛擬機空閑,則該虛擬機與其他虛擬機同步切換到休眠狀態。

(2) 空閑狀態。處于空閑狀態的虛擬機,可以隨時為分配到的任務提供服務,也可以與其他虛擬機同步進入休眠狀態。若分配到任務,空閑虛擬機可以立即切換到活躍狀態。若所有虛擬機全部執行完成所分配的任務且緩存區空,該虛擬機與其他虛擬機同步切換到休眠狀態。

(3) 休眠狀態。處于休眠狀態的虛擬機暫時不再為任務提供服務。當虛擬機處于休眠狀態時,新到達任務在系統緩存區中排隊等待。當一個物理機的休眠定時器到期時,若系統緩存區空,重新啟動休眠定時器,其上的虛擬機同時開始下一個休眠間隔,多個休眠間隔構成一個休眠期;若系統緩存區不空,全部虛擬機則同時結束休眠,依次處理系統緩存區滯留的任務。分配到任務的虛擬機由休眠狀態切換到活躍狀態,未被分配到任務的虛擬機由休眠狀態切換到空閑狀態。

1.2 系統模型

將移動設備視為連續工作的M/M/1 排隊,遠程云端的每一個物理機視為虛擬機同步多重休假的M/M/ck排隊,建立系統模型。

令任務的產生服從參數為λ(0<λ <+∞) 的指數分布。假設一個物理機上的虛擬機服務能力相同,令物理機Sk(k=1,2,…,n) 上的虛擬機服務一個任務的時間服從參數為μk(0<μk <+∞) 的指數分布,令物理機休眠定時器長度服從參數為θk(0<θk <+∞) 的指數分布。

假設任務在本地執行的概率為q(0 ≤q≤1),任務卸載到遠程云端的概率為1-q。卸載到遠程云端的任務將分配到某一個物理機上。假設某個任務分配到物理機Sk的概率為ξk,則ξ1+ξ2+…+ξn=1。基于以上假設,本地任務的到達服從參數為λ0=λq的指數分布,物理機Sk上的任務到達服從參數λk=λ(1-q)ξk的指數分布。假設物理機具有無限容量的緩存。

本地移動設備的系統服務強度ρ0定義為一個本地任務的服務時間內分配到本地移動設備的平均任務數。ρ0表示為

其中,μ0為本地移動設備的服務率。

云端物理機Sk的系統服務強度ρk定義為一個云端任務的服務時間內卸載到云端的平均任務數。ρk表示為

為了使系統穩定,令本地移動設備的系統服務強度ρ0和云端物理機Sk的系統服務強度ρk均小于1。

令隨機變量Xk(t)=i(i=0,1,…) 表示時刻t物理機Sk內的任務數。令隨機變量Yk(t)=j(j=0,1) 表示時刻t物理機Sk上虛擬機所處的狀態。當j=0 時,表示虛擬機處在休眠狀態;當j=1 時,表示虛擬機處在活躍狀態。{(Xk(t),Yk(t)),t≥0} 構成一個二維時間連續馬爾科夫鏈,其狀態空間表示為

令πk(i,j) 表示穩態下物理機Sk的系統水平為i、系統階段為j的概率分布。πk(i,j) 表示為

令πk(0)=πk(0,0) 表示為穩態下系統水平為0 的概率向量,令πk(i)=(πk(i,0),πk(i,1))表示為穩態下系統水平為i的概率向量。二維連續時間馬爾可夫鏈{(Xk(t),Yk(t)),t≥0} 的穩態概率分布Πk表示為

2 系統模型的穩態分析

假設遠程云端部署了n個異構物理機,物理機Sk上部署了ck個虛擬機。物理機Sk可看作一個獨立的同步多重休假M/M/ck排隊[8]。物理機Sk上虛擬機的狀態轉移機制如圖3 所示。

圖3 物理機Sk 上虛擬機的狀態轉移

由圖3 可以分析出一個物理機中多個虛擬機的狀態轉移過程。當j=0 時,物理機Sk上ck個虛擬機全部處于休眠狀態。當j=1 時,若系統內有i

令Qk表示二維連續時間馬爾可夫鏈{(Xk(t),Yk(t)),t≥0} 的一步轉移率矩陣,Qk(x,y) 表示經過一步轉移后,系統水平從x(x=0,1,…) 到y(y=0,1,…) 的轉移率子陣。為了表述方便,將Qk(x,x -1)、Qk(x,x) 與Qk(x,x +1) 分別記為Bk(x)、Ak(x) 與Ck(x)。

(1) 當x=0 時,虛擬機一定處于休眠狀態,且緩存區為空。當無任務到達時,系統水平和系統階段均保持不變,Ak(0) 退化為一個數值,Ak(0)=-λk。若有一個任務到達,系統水平由x=0 變為x=1,系統階段不變,轉移率為λk,Ck(0) 為1 ×2 維矩陣,表示為

(2) 當x=1 時,虛擬機既可能處于休眠狀態,也可能處于活躍狀態。

首先,討論系統水平下降的情形。當虛擬機處于休眠狀態時,任務不可能產生離去。當虛擬機處于活躍狀態時,若處理完成一個任務,系統水平由x=1 變為x=0,虛擬機由活躍狀態切換到休眠狀態,系統階段由j=1 變為j=0,轉移率為μk。Bk(1) 為2 ×1 維矩陣,表示為

其次,討論系統水平不變的情形。當虛擬機處于休眠狀態時,若無任務到達且休眠定時器未到期,轉移率為-(λk+θk);若休眠定時器到期,虛擬機由休眠狀態切換到活躍狀態,系統階段由j=0 變為j=1,轉移率為θk。當虛擬機處于活躍狀態時,若無任務到達且虛擬機未處理完成當前任務,轉移率為-(λk+μk),此時,虛擬機無法進入休眠狀態。Ak(1) 為2 ×2 維矩陣,表示為

最后,討論系統水平增加的情形。無論虛擬機處于休眠狀態還是活躍狀態,若有一個任務到達,系統水平由x=1 變為x=2,系統階段不變,轉移率為λk。Ck(1) 為2 ×2 維矩陣,表示為

(3) 當1

首先,討論系統水平下降的情形。當虛擬機處于休眠狀態時,任務不可能產生離去。當虛擬機處于活躍狀態時,若處理完成一個任務,系統水平由x變為x -1,轉移率為xμk,此時,物理機Sk還存在未處理完成的任務,虛擬機無法進入休眠狀態。Bk(x)為2 ×2 維矩陣,表示為

其次,討論系統水平不變的情形。當虛擬機處于休眠狀態時,若無任務到達且休眠定時器未到期,轉移率為-(λk+θk);若休眠定時器到期,虛擬機由休眠狀態切換到活躍狀態,系統階段由j=0 變為j=1,轉移率為θk。當虛擬機處于活躍狀態時,若無任務到達且虛擬機未處理完成當前任務,轉移率為-(λk+xμk),此時,虛擬機無法進入休眠狀態。Ak(x) 為2 ×2 維矩陣,表示為

最后,討論系統水平增加的情形。無論虛擬機處于休眠狀態還是活躍狀態,若有一個任務到達,系統水平由x變為x +1,系統階段不變,轉移率為λk。Ck(x) 為2 ×2 維矩陣,表示為

(4) 當x >ck時,虛擬機仍然可能處于休眠狀態或者活躍狀態。

首先,討論系統水平下降的情形。當虛擬機處于休眠狀態時,任務不可能產生離去。當虛擬機處于活躍狀態時,有ck個任務同時接受服務,若處理完成一個任務,系統水平由x變為x -1,轉移率為ckμk,此時,虛擬機同樣無法進入休眠狀態。Bk(x)為2 ×2 維矩陣,表示為

其次,討論系統水平不變的情形。當虛擬機處于休眠狀態時,若無任務到達且休眠定時器未到期,轉移率為-(λk+θk);若休眠定時器到期,虛擬機由休眠狀態切換到活躍狀態,系統階段由j=0 變為j=1,轉移率為θk。當虛擬機處于活躍狀態時,若無任務到達且虛擬機未處理完成當前任務,轉移率為-(λk+ckμk),此時,虛擬機無法進入休眠狀態。Ak(x) 為2 ×2 維矩陣,表示為

最后,討論系統水平增加的情形。無論虛擬機處于休眠狀態還是活躍狀態,若有一個任務到達,系統水平由x變為x +1,系統階段不變,轉移率為λk。Ck(x) 為2 ×2 維矩陣,表示為

由上述分析可得,轉移率子陣Ak(x) 與Bk(x)均從系統水平ck開始重復,Ck(x) 從1 開始重復。將重復的Ak(x) 與Bk(x) 分別用Ak與Bk來表示,將重復的Ck(x) 用Ck來表示,則馬爾可夫鏈{(Xk(t),Yk(t)),t≥0} 的一步轉移率矩陣Qk可以表示為如下分塊形式。

從一步轉移率矩陣Qk的結構可知,狀態的轉移只發生在相鄰的系統水平之間。因此,二維連續時間馬爾可夫鏈{(Xk(t),Yk(t)),t≥0} 可以看成一種擬生滅過程。該過程正常返的充分必要條件是矩陣方程

的最小非負解Rk(也稱為率陣)的譜半徑Sp(Rk)<1。

由Qk子陣結構,可設率陣,將Ak、Bk、Ck與Rk代入式(17),可得率陣Rk如下。

根據率陣Rk的解析結果,可以看出率陣Rk的譜半徑,所以二維馬爾可夫鏈{(Xk(t),Yk(t)),t≥0} 正常返。利用所求得的率陣Rk,構造方陣B[Rk]如下。

由平衡方程及歸一化條件可得如下方程組:

其中,Ι為單位矩陣,e為全1 列向量。

系統的穩態分布表示為

其中,πk(0,0) 由歸一化條件給出如下。

3 系統性能指標

任務響應時間定義為從任務的產生時刻開始,到任務結束服務離開系統為止所經歷的時間段。

分配到本地執行的任務平均響應時間W0包括任務在本地緩存區的平均等待時間與在本地處理器的平均服務時間。根據排隊模型M/M/1 的解析結果,給出本地任務平均響應時間W0的表達式為

卸載到遠程云端的任務平均響應時間包括任務在緩存區的平均等待時間與在虛擬機上的平均服務時間。由第2 節給出的系統模型的穩態分析結果計算出平均等待隊長的表達式,進一步利用Little 公式[9]得出物理機Sk上任務平均響應時間Wk的表達式為

任務在本地執行的概率為q(0 ≤q≤1),卸載到遠程云端的概率為1-q,卸載到遠程云端的任務分配給物理機Sk的概率為ξk。綜合式(24)給出的本地任務平均響應時間W0和式(25)給出的物理機Sk任務平均響應時間Wk,得出任務平均響應時間W為

移動設備處于活躍狀態時,其處理器高速運轉,令其運行功率表示為。移動設備處于空閑狀態時,其處理器低速運轉,令其運行功率表示為。顯然,。移動設備平均運行功率P0為

其中,ρ0表示為移動設備處于活躍狀態的概率。

綜合式(27)給出的移動設備平均運行功率P0和式(28)給出的物理機Sk平均運行功率Pk,得出系統平均運行功率P的表達式為

4 系統實驗

為量化任務到達率λ、休眠參數θk、任務分配到移動設備本地的概率q及任務卸載到遠程云端物理機Sk上的概率ξk對云系統任務調度策略的影響,進行系統實驗,刻畫以分鐘(min)為單位的任務平均響應時間與以毫瓦(mW)為單位的系統平均運行功率的變化趨勢。系統實驗所用計算機的處理器為Intel(R) Core(TM) i7-4790,運行頻率為3.60 GHz,內存為8 GB。系統實驗與系統優化在Matlab R2016a的環境下實現。

在保證系統穩定,即本地服務強度ρ0<1 與遠程云端物理機的服務強度Max(ρ1,ρ2,…,ρn)<1的約束下,設置如表1 所示的系統實驗參數。

表1 系統實驗參數設置

使用表1 設定的參數,固定卸載到遠程云端物理機S1、S2、S3的概率(ξ1=0.2225、ξ2=0.3432、ξ3=0.4343),考慮不同的休眠參數θk(k=1,2,3)進行系統實驗,圖4 刻畫了任務到達率λ與任務分配到移動設備本地的概率q對任務平均響應時間W的影響。

橫向觀察圖4,隨著任務分配到移動設備本地的概率q的增大,任務平均響應時間W先呈現下降趨勢,在到達最低點之后開始上升。當任務分配到移動設備本地的概率較小時,任務在遠程云端物理機的響應時間占平均響應時間的主導地位。隨著任務分配到移動設備本地的概率的增大,任務在遠程云端物理機緩存區的平均等待時間隨之減少,任務平均響應時間降低。當任務分配到移動設備本地的概率較大時,任務在移動設備的響應時間占平均響應時間的主導地位。隨著任務分配到移動設備本地的概率的增大,任務在移動設備本地的平均等待時間隨之增大,任務平均響應時間上升。

圖4 任務平均響應時間的變化趨勢

縱向觀察圖4,隨著任務到達率λ的增大,任務平均響應時間W的變化趨勢與任務分配到移動設備本地的概率q有關。當任務分配到移動設備本地的概率較小時,更多的任務卸載到遠程云端物理機接受服務。任務到達率越大,虛擬機進入休眠狀態的概率越小,任務平均響應時間隨之減少。當任務分配到移動設備本地的概率較大時,分配到移動設備本地的任務越多,任務在移動設備本地的等待時間變長,任務平均響應時間隨之增大。

對比觀察圖4(a)和圖4(b),隨著休眠參數θk(k=1,2,3) 的增大,任務平均響應時間W呈現下降趨勢。任務分配到本地設備的概率較小時,更多的任務卸載到遠程云端物理機。當休眠參數較小時,任務在緩存區中等待虛擬機結束休眠的時間較長,導致任務平均響應時間加大。這種情況下,本文所提策略中的休眠機制對任務平均響應時間的影響較大。而當休眠參數較大時,任務在緩存區中等待虛擬機結束休眠的時間相對縮短,任務平均響應時間隨之減少。這種情況下,本文所提策略中的休眠機制對任務平均響應時間的影響較小。

圖5 刻畫了任務到達率λ與任務分配到移動設備本地的概率q對系統平均運行功率P的影響。

橫向觀察圖5,隨著任務分配到移動設備本地的概率q的增大,系統平均運行功率P先呈現下降趨勢,在到達最低點之后開始逐漸上升。當任務分配到移動設備本地的概率較小時,更多的任務卸載到遠程云端物理機接受服務,遠程云端物理機的運行功率占系統平均運行功率P的主導地位。隨著任務分配到移動設備本地的概率增大,卸載到遠程云端物理機的任務量減少,物理機上的虛擬機處于活躍狀態的可能性減小,物理機的運行功率下降,系統平均運行功率下降。當任務分配到移動設備本地的概率較大時,更多的任務分配到移動設備本地接受服務,移動設備本地的運行功率占系統平均運行功率P的主導地位。隨著任務分配到移動設備本地的概率增大,分配到移動設備本地的任務增多,移動設備功耗增大,系統平均運行功率上升。

縱向觀察圖5,隨著任務到達率λ的增大,系統平均運行功率P隨之增大。任務到達率越大,意味著任務量越多,移動設備與物理機的功耗增大,系統平均運行功率上升。

對比觀察圖5(a)和圖5(b),隨著休眠參數θk(k=1,2,3) 的增大,系統平均運行功率P呈現上升趨勢。隨著休眠參數的增大,虛擬機進入休眠狀態的可能性降低,而虛擬機處于活躍狀態或空閑狀態的可能性增大,系統平均運行功率上升。

圖5 系統平均運行功率的變化趨勢

比較圖4 與圖5 可以看出,最低的平均響應時間所對應的任務分配到移動設備本地的概率無法實現最低的能耗水平。實際應用中,需根據實際應用的業務特點設置任務分配到移動設備本地的概率。

5 系統優化

系統實驗所揭示的任務平均響應時間和系統平均運行功率的變化規律表明,任務到達率、休眠參數與任務分配到移動設備本地的概率是影響系統性能的重要因素。在不同的任務到達率下,合理設置任務分配到移動設備本地的概率能夠實現響應性能與能耗水平的合理均衡。

對任務平均響應時間W與系統平均運行功率P進行歸一化處理,構造無量綱系統成本函數如下。

其中,f1表示任務平均響應時間對系統成本函數的影響因子,f2表示系統平均功率對系統成本函數的影響因子[10]。當任務分配到移動設備本地的概率q的取值在[0,0.9]時,任務平均響應時間W的最大值和最小值表示為Wmax和Wmin,系統平均運行功率P的最大值和最小值表示為Pmax和Pmin。

為了實現系統成本函數的最小化,利用智能尋優算法找出最優任務分配到移動設備本地的概率。相比于一般的優化算法,鯨魚優化算法的收斂速度較快,能夠在較短的時間內尋找到目標函數的最優解。算法中的每一頭鯨魚所處的位置代表目標函數的一個可行解,采用隨機和最佳搜索代理模擬鯨魚的捕獵行為,并使用螺旋模型模擬座頭鯨的汽泡網攻擊機制[11]。本文中,增加了混沌初始化用來提高鯨魚優化算法的全局搜索能力。算法的主要步驟如下所示。

步驟1初始化算法執行的最大迭代次數Maxiter=10 000,鯨魚種群規模N=1000;設置任務分配到移動設備本地的概率q的上限qup=1 及下限qlow=0,當前迭代次數iter=1。

步驟2利用混沌方程初始化鯨魚種群的位置。

步驟3設第1 條鯨魚位置為當前最優位置q*,利用式(30)計算系統成本函數F(q*)。

步驟4利用式(30)計算全部鯨魚所對應的系統成本函數F(qi(iter)),i=1,2,…,N,找出當前最優鯨魚位置q*。

步驟5根據鯨魚捕食行為更新鯨魚位置。

步驟6判斷迭代過程是否完成。

步驟7輸出最優鯨魚位置為最優分配到移動設備本地的概率q*,給出最小系統成本函F(q*)。

設置系統成本函數的影響因子f1=2.0、f2=1.6,利用改進的鯨魚優化算法給出不同任務到達率下任務分配到移動設備本地的最優概率,優化結果如表2 所示。

表2 任務分配到移動設備本地的概率的優化結果

從表2 的數值結果可以看出,任務分配到移動設備本地的最優概率隨著任務到達率的增大逐漸減小。移動設備的本地處理能力有限,隨著任務到達率的增大,移動設備本地的任務量負載加重,因此,任務分配到本地執行的最優概率呈下降趨勢。

6 結論

綜合考慮云用戶的響應性能與云系統的能耗水平,在遠程云端引入周期性休眠機制,提出了一種云計算任務調度策略。基于遠程云端,考慮異構物理機,建立同步多重休假M/M/ck排隊模型,給出了系統模型的穩態分布。基于Matlab 進行了系統實驗,實驗結果表明,任務平均響應時間與系統平均運行功率之間存在折衷關系。設定任務平均響應時間和系統平均運行功率的影響因子,構建了系統成本函數。利用混沌方程初始化種群位置,改進鯨魚優化算法,給出了任務分配到移動設備本地的概率的優化結果,實現了系統成本函數的最小化。