范寶芝 王開(kāi)宇 白小軍 金順福

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

0 引言

隨著無(wú)線通訊技術(shù)的發(fā)展,網(wǎng)絡(luò)應(yīng)用程序的使用越來(lái)越多。移動(dòng)設(shè)備負(fù)載能力不足的問(wèn)題日趨明顯,云計(jì)算為移動(dòng)設(shè)備的任務(wù)卸載提供支持[1]。值得注意的是,不斷增長(zhǎng)的云應(yīng)用導(dǎo)致云數(shù)據(jù)中心消耗著巨大的能源,對(duì)環(huán)境也產(chǎn)生了惡劣的影響。研究發(fā)現(xiàn),按照每年40%～60%的增長(zhǎng)率估算,到2030 年云數(shù)據(jù)中心的能源消耗將達(dá)到8000 TWh[2]。綠色云計(jì)算是社會(huì)進(jìn)步的必然趨勢(shì),也是實(shí)現(xiàn)可持續(xù)發(fā)展的前提。緩解云數(shù)據(jù)中心的高耗能問(wèn)題是云計(jì)算研究的重點(diǎn)內(nèi)容之一。

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

考慮到云用戶(hù)對(duì)響應(yīng)性能的需求,文獻(xiàn)[5]提出了一種基于(N,T) 休眠機(jī)制的云計(jì)算中心節(jié)能策略。結(jié)合喚醒閾值N及長(zhǎng)度為T(mén)的休眠計(jì)時(shí)器,建立多重同步休假隨機(jī)模型。利用改進(jìn)飛蛾撲火優(yōu)化算法,給出了節(jié)能策略的聯(lián)合優(yōu)化方案,實(shí)驗(yàn)證實(shí)所提策略在保證用戶(hù)響應(yīng)性能的基礎(chǔ)上,有效降低了系統(tǒng)能耗。文獻(xiàn)[6]提出了一種基于動(dòng)態(tài)閾值的服務(wù)器喚醒策略。該策略綜合考慮用戶(hù)端的任務(wù)情況和服務(wù)器的能耗成本,動(dòng)態(tài)調(diào)整任務(wù)請(qǐng)求數(shù)的閾值,并根據(jù)時(shí)間優(yōu)先級(jí)喚醒服務(wù)器。與靜態(tài)閾值的服務(wù)器喚醒策略相比,該策略有效降低了云計(jì)算系統(tǒng)的能耗開(kāi)銷(xiāo)。以上研究專(zhuān)注于云系統(tǒng)本身,未考慮產(chǎn)生任務(wù)的移動(dòng)設(shè)備及移動(dòng)設(shè)備自身的處理能力。

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

1 任務(wù)調(diào)度策略及系統(tǒng)模型

1.1 任務(wù)調(diào)度策略

針對(duì)移動(dòng)設(shè)備存儲(chǔ)空間不足且處理能力有限等問(wèn)題,借助于遠(yuǎn)程云端的幫助,移動(dòng)設(shè)備任務(wù)負(fù)載能夠有效地得到均衡。在任務(wù)調(diào)度器的協(xié)調(diào)下,將移動(dòng)設(shè)備產(chǎn)生的任務(wù)分為兩部分,一部分任務(wù)分配到本地處理器接受服務(wù),另一部分任務(wù)則卸載到遠(yuǎn)程云端的虛擬機(jī)上接受服務(wù)。

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

圖1 移動(dòng)設(shè)備與遠(yuǎn)程云端構(gòu)成的體系結(jié)構(gòu)

傳統(tǒng)云服務(wù)中,云服務(wù)器一直處在活躍狀態(tài),增加了遠(yuǎn)程云端的能源消耗。休眠機(jī)制是一種有效減少能源消耗的人為手段。借助于虛擬化技術(shù),在同一臺(tái)物理機(jī)上的虛擬機(jī)中引入周期性同步休眠機(jī)制,不同物理機(jī)上的虛擬機(jī)引入周期性異步休眠機(jī)制。在每個(gè)物理機(jī)上設(shè)置一個(gè)休眠定時(shí)器。當(dāng)物理機(jī)上的全部任務(wù)結(jié)束服務(wù)時(shí),該定時(shí)器觸發(fā),部署在該物理機(jī)上的全部虛擬機(jī)同時(shí)進(jìn)入休眠狀態(tài)。不同物理機(jī)上的定時(shí)器的觸發(fā)相互獨(dú)立,也就是說(shuō),一個(gè)物理機(jī)上的虛擬機(jī)的休眠或喚醒,與另一個(gè)物理機(jī)上虛擬機(jī)無(wú)關(guān)。

基于所提出的體系結(jié)構(gòu),遠(yuǎn)程云端上的虛擬機(jī)具有3 種狀態(tài):活躍狀態(tài)、空閑狀態(tài)和休眠狀態(tài)。虛擬機(jī)的狀態(tài)轉(zhuǎn)換過(guò)程如圖2 所示。

圖2 虛擬機(jī)的狀態(tài)轉(zhuǎn)移過(guò)程

(1) 活躍狀態(tài)。處于活躍狀態(tài)的虛擬機(jī)為某一個(gè)任務(wù)提供服務(wù)。虛擬機(jī)服務(wù)完成當(dāng)前任務(wù)后,按先來(lái)先服務(wù)規(guī)則為緩存區(qū)中等待的任務(wù)提供服務(wù)。若緩存區(qū)空,但其他虛擬機(jī)未全部空閑,則該虛擬機(jī)由活躍狀態(tài)切換到空閑狀態(tài)。若緩存區(qū)空且所有虛擬機(jī)空閑,則該虛擬機(jī)與其他虛擬機(jī)同步切換到休眠狀態(tài)。

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

(3) 休眠狀態(tài)。處于休眠狀態(tài)的虛擬機(jī)暫時(shí)不再為任務(wù)提供服務(wù)。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),新到達(dá)任務(wù)在系統(tǒng)緩存區(qū)中排隊(duì)等待。當(dāng)一個(gè)物理機(jī)的休眠定時(shí)器到期時(shí),若系統(tǒng)緩存區(qū)空,重新啟動(dòng)休眠定時(shí)器,其上的虛擬機(jī)同時(shí)開(kāi)始下一個(gè)休眠間隔,多個(gè)休眠間隔構(gòu)成一個(gè)休眠期;若系統(tǒng)緩存區(qū)不空,全部虛擬機(jī)則同時(shí)結(jié)束休眠,依次處理系統(tǒng)緩存區(qū)滯留的任務(wù)。分配到任務(wù)的虛擬機(jī)由休眠狀態(tài)切換到活躍狀態(tài),未被分配到任務(wù)的虛擬機(jī)由休眠狀態(tài)切換到空閑狀態(tài)。

1.2 系統(tǒng)模型

將移動(dòng)設(shè)備視為連續(xù)工作的M/M/1 排隊(duì),遠(yuǎn)程云端的每一個(gè)物理機(jī)視為虛擬機(jī)同步多重休假的M/M/ck排隊(duì),建立系統(tǒng)模型。

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

假設(shè)任務(wù)在本地執(zhí)行的概率為q(0 ≤q≤1),任務(wù)卸載到遠(yuǎn)程云端的概率為1-q。卸載到遠(yuǎn)程云端的任務(wù)將分配到某一個(gè)物理機(jī)上。假設(shè)某個(gè)任務(wù)分配到物理機(jī)Sk的概率為ξk,則ξ1+ξ2+…+ξn=1?；谝陨霞僭O(shè),本地任務(wù)的到達(dá)服從參數(shù)為λ0=λq的指數(shù)分布,物理機(jī)Sk上的任務(wù)到達(dá)服從參數(shù)λk=λ(1-q)ξk的指數(shù)分布。假設(shè)物理機(jī)具有無(wú)限容量的緩存。

本地移動(dòng)設(shè)備的系統(tǒng)服務(wù)強(qiáng)度ρ0定義為一個(gè)本地任務(wù)的服務(wù)時(shí)間內(nèi)分配到本地移動(dòng)設(shè)備的平均任務(wù)數(shù)。ρ0表示為

其中,μ0為本地移動(dòng)設(shè)備的服務(wù)率。

云端物理機(jī)Sk的系統(tǒng)服務(wù)強(qiáng)度ρk定義為一個(gè)云端任務(wù)的服務(wù)時(shí)間內(nèi)卸載到云端的平均任務(wù)數(shù)。ρk表示為

為了使系統(tǒng)穩(wěn)定,令本地移動(dòng)設(shè)備的系統(tǒng)服務(wù)強(qiáng)度ρ0和云端物理機(jī)Sk的系統(tǒng)服務(wù)強(qiáng)度ρk均小于1。

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

令πk(i,j) 表示穩(wěn)態(tài)下物理機(jī)Sk的系統(tǒng)水平為i、系統(tǒng)階段為j的概率分布。πk(i,j) 表示為

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

2 系統(tǒng)模型的穩(wěn)態(tài)分析

假設(shè)遠(yuǎn)程云端部署了n個(gè)異構(gòu)物理機(jī),物理機(jī)Sk上部署了ck個(gè)虛擬機(jī)。物理機(jī)Sk可看作一個(gè)獨(dú)立的同步多重休假M(fèi)/M/ck排隊(duì)[8]。物理機(jī)Sk上虛擬機(jī)的狀態(tài)轉(zhuǎn)移機(jī)制如圖3 所示。

圖3 物理機(jī)Sk 上虛擬機(jī)的狀態(tài)轉(zhuǎn)移

由圖3 可以分析出一個(gè)物理機(jī)中多個(gè)虛擬機(jī)的狀態(tài)轉(zhuǎn)移過(guò)程。當(dāng)j=0 時(shí),物理機(jī)Sk上ck個(gè)虛擬機(jī)全部處于休眠狀態(tài)。當(dāng)j=1 時(shí),若系統(tǒng)內(nèi)有i

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

(1) 當(dāng)x=0 時(shí),虛擬機(jī)一定處于休眠狀態(tài),且緩存區(qū)為空。當(dāng)無(wú)任務(wù)到達(dá)時(shí),系統(tǒng)水平和系統(tǒng)階段均保持不變,Ak(0) 退化為一個(gè)數(shù)值,Ak(0)=-λk。若有一個(gè)任務(wù)到達(dá),系統(tǒng)水平由x=0 變?yōu)閤=1,系統(tǒng)階段不變,轉(zhuǎn)移率為λk,Ck(0) 為1 ×2 維矩陣,表示為

(2) 當(dāng)x=1 時(shí),虛擬機(jī)既可能處于休眠狀態(tài),也可能處于活躍狀態(tài)。

首先,討論系統(tǒng)水平下降的情形。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),任務(wù)不可能產(chǎn)生離去。當(dāng)虛擬機(jī)處于活躍狀態(tài)時(shí),若處理完成一個(gè)任務(wù),系統(tǒng)水平由x=1 變?yōu)閤=0,虛擬機(jī)由活躍狀態(tài)切換到休眠狀態(tài),系統(tǒng)階段由j=1 變?yōu)閖=0,轉(zhuǎn)移率為μk。Bk(1) 為2 ×1 維矩陣,表示為

其次,討論系統(tǒng)水平不變的情形。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),若無(wú)任務(wù)到達(dá)且休眠定時(shí)器未到期,轉(zhuǎn)移率為-(λk+θk);若休眠定時(shí)器到期,虛擬機(jī)由休眠狀態(tài)切換到活躍狀態(tài),系統(tǒng)階段由j=0 變?yōu)閖=1,轉(zhuǎn)移率為θk。當(dāng)虛擬機(jī)處于活躍狀態(tài)時(shí),若無(wú)任務(wù)到達(dá)且虛擬機(jī)未處理完成當(dāng)前任務(wù),轉(zhuǎn)移率為-(λk+μk),此時(shí),虛擬機(jī)無(wú)法進(jìn)入休眠狀態(tài)。Ak(1) 為2 ×2 維矩陣,表示為

最后,討論系統(tǒng)水平增加的情形。無(wú)論虛擬機(jī)處于休眠狀態(tài)還是活躍狀態(tài),若有一個(gè)任務(wù)到達(dá),系統(tǒng)水平由x=1 變?yōu)閤=2,系統(tǒng)階段不變,轉(zhuǎn)移率為λk。Ck(1) 為2 ×2 維矩陣,表示為

(3) 當(dāng)1

首先,討論系統(tǒng)水平下降的情形。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),任務(wù)不可能產(chǎn)生離去。當(dāng)虛擬機(jī)處于活躍狀態(tài)時(shí),若處理完成一個(gè)任務(wù),系統(tǒng)水平由x變?yōu)閤 -1,轉(zhuǎn)移率為xμk,此時(shí),物理機(jī)Sk還存在未處理完成的任務(wù),虛擬機(jī)無(wú)法進(jìn)入休眠狀態(tài)。Bk(x)為2 ×2 維矩陣,表示為

其次,討論系統(tǒng)水平不變的情形。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),若無(wú)任務(wù)到達(dá)且休眠定時(shí)器未到期,轉(zhuǎn)移率為-(λk+θk);若休眠定時(shí)器到期,虛擬機(jī)由休眠狀態(tài)切換到活躍狀態(tài),系統(tǒng)階段由j=0 變?yōu)閖=1,轉(zhuǎn)移率為θk。當(dāng)虛擬機(jī)處于活躍狀態(tài)時(shí),若無(wú)任務(wù)到達(dá)且虛擬機(jī)未處理完成當(dāng)前任務(wù),轉(zhuǎn)移率為-(λk+xμk),此時(shí),虛擬機(jī)無(wú)法進(jìn)入休眠狀態(tài)。Ak(x) 為2 ×2 維矩陣,表示為

最后,討論系統(tǒng)水平增加的情形。無(wú)論虛擬機(jī)處于休眠狀態(tài)還是活躍狀態(tài),若有一個(gè)任務(wù)到達(dá),系統(tǒng)水平由x變?yōu)閤 +1,系統(tǒng)階段不變,轉(zhuǎn)移率為λk。Ck(x) 為2 ×2 維矩陣,表示為

(4) 當(dāng)x >ck時(shí),虛擬機(jī)仍然可能處于休眠狀態(tài)或者活躍狀態(tài)。

首先,討論系統(tǒng)水平下降的情形。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),任務(wù)不可能產(chǎn)生離去。當(dāng)虛擬機(jī)處于活躍狀態(tài)時(shí),有ck個(gè)任務(wù)同時(shí)接受服務(wù),若處理完成一個(gè)任務(wù),系統(tǒng)水平由x變?yōu)閤 -1,轉(zhuǎn)移率為ckμk,此時(shí),虛擬機(jī)同樣無(wú)法進(jìn)入休眠狀態(tài)。Bk(x)為2 ×2 維矩陣,表示為

其次,討論系統(tǒng)水平不變的情形。當(dāng)虛擬機(jī)處于休眠狀態(tài)時(shí),若無(wú)任務(wù)到達(dá)且休眠定時(shí)器未到期,轉(zhuǎn)移率為-(λk+θk);若休眠定時(shí)器到期,虛擬機(jī)由休眠狀態(tài)切換到活躍狀態(tài),系統(tǒng)階段由j=0 變?yōu)閖=1,轉(zhuǎn)移率為θk。當(dāng)虛擬機(jī)處于活躍狀態(tài)時(shí),若無(wú)任務(wù)到達(dá)且虛擬機(jī)未處理完成當(dāng)前任務(wù),轉(zhuǎn)移率為-(λk+ckμk),此時(shí),虛擬機(jī)無(wú)法進(jìn)入休眠狀態(tài)。Ak(x) 為2 ×2 維矩陣,表示為

最后,討論系統(tǒng)水平增加的情形。無(wú)論虛擬機(jī)處于休眠狀態(tài)還是活躍狀態(tài),若有一個(gè)任務(wù)到達(dá),系統(tǒng)水平由x變?yōu)閤 +1,系統(tǒng)階段不變,轉(zhuǎn)移率為λk。Ck(x) 為2 ×2 維矩陣,表示為

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

從一步轉(zhuǎn)移率矩陣Qk的結(jié)構(gòu)可知,狀態(tài)的轉(zhuǎn)移只發(fā)生在相鄰的系統(tǒng)水平之間。因此,二維連續(xù)時(shí)間馬爾可夫鏈{(Xk(t),Yk(t)),t≥0} 可以看成一種擬生滅過(guò)程。該過(guò)程正常返的充分必要條件是矩陣方程

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

由Qk子陣結(jié)構(gòu),可設(shè)率陣,將Ak、Bk、Ck與Rk代入式(17),可得率陣Rk如下。

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

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

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

系統(tǒng)的穩(wěn)態(tài)分布表示為

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

3 系統(tǒng)性能指標(biāo)

任務(wù)響應(yīng)時(shí)間定義為從任務(wù)的產(chǎn)生時(shí)刻開(kāi)始,到任務(wù)結(jié)束服務(wù)離開(kāi)系統(tǒng)為止所經(jīng)歷的時(shí)間段。

分配到本地執(zhí)行的任務(wù)平均響應(yīng)時(shí)間W0包括任務(wù)在本地緩存區(qū)的平均等待時(shí)間與在本地處理器的平均服務(wù)時(shí)間。根據(jù)排隊(duì)模型M/M/1 的解析結(jié)果,給出本地任務(wù)平均響應(yīng)時(shí)間W0的表達(dá)式為

卸載到遠(yuǎn)程云端的任務(wù)平均響應(yīng)時(shí)間包括任務(wù)在緩存區(qū)的平均等待時(shí)間與在虛擬機(jī)上的平均服務(wù)時(shí)間。由第2 節(jié)給出的系統(tǒng)模型的穩(wěn)態(tài)分析結(jié)果計(jì)算出平均等待隊(duì)長(zhǎng)的表達(dá)式,進(jìn)一步利用Little 公式[9]得出物理機(jī)Sk上任務(wù)平均響應(yīng)時(shí)間Wk的表達(dá)式為

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

移動(dòng)設(shè)備處于活躍狀態(tài)時(shí),其處理器高速運(yùn)轉(zhuǎn),令其運(yùn)行功率表示為。移動(dòng)設(shè)備處于空閑狀態(tài)時(shí),其處理器低速運(yùn)轉(zhuǎn),令其運(yùn)行功率表示為。顯然,。移動(dòng)設(shè)備平均運(yùn)行功率P0為

其中,ρ0表示為移動(dòng)設(shè)備處于活躍狀態(tài)的概率。

綜合式(27)給出的移動(dòng)設(shè)備平均運(yùn)行功率P0和式(28)給出的物理機(jī)Sk平均運(yùn)行功率Pk,得出系統(tǒng)平均運(yùn)行功率P的表達(dá)式為

4 系統(tǒng)實(shí)驗(yàn)

為量化任務(wù)到達(dá)率λ、休眠參數(shù)θk、任務(wù)分配到移動(dòng)設(shè)備本地的概率q及任務(wù)卸載到遠(yuǎn)程云端物理機(jī)Sk上的概率ξk對(duì)云系統(tǒng)任務(wù)調(diào)度策略的影響,進(jìn)行系統(tǒng)實(shí)驗(yàn),刻畫(huà)以分鐘(min)為單位的任務(wù)平均響應(yīng)時(shí)間與以毫瓦(mW)為單位的系統(tǒng)平均運(yùn)行功率的變化趨勢(shì)。系統(tǒng)實(shí)驗(yàn)所用計(jì)算機(jī)的處理器為Intel(R) Core(TM) i7-4790,運(yùn)行頻率為3.60 GHz,內(nèi)存為8 GB。系統(tǒng)實(shí)驗(yàn)與系統(tǒng)優(yōu)化在Matlab R2016a的環(huán)境下實(shí)現(xiàn)。

在保證系統(tǒng)穩(wěn)定,即本地服務(wù)強(qiáng)度ρ0<1 與遠(yuǎn)程云端物理機(jī)的服務(wù)強(qiáng)度Max(ρ1,ρ2,…,ρn)<1的約束下,設(shè)置如表1 所示的系統(tǒng)實(shí)驗(yàn)參數(shù)。

表1 系統(tǒng)實(shí)驗(yàn)參數(shù)設(shè)置

使用表1 設(shè)定的參數(shù),固定卸載到遠(yuǎn)程云端物理機(jī)S1、S2、S3的概率(ξ1=0.2225、ξ2=0.3432、ξ3=0.4343),考慮不同的休眠參數(shù)θk(k=1,2,3)進(jìn)行系統(tǒng)實(shí)驗(yàn),圖4 刻畫(huà)了任務(wù)到達(dá)率λ與任務(wù)分配到移動(dòng)設(shè)備本地的概率q對(duì)任務(wù)平均響應(yīng)時(shí)間W的影響。

橫向觀察圖4,隨著任務(wù)分配到移動(dòng)設(shè)備本地的概率q的增大,任務(wù)平均響應(yīng)時(shí)間W先呈現(xiàn)下降趨勢(shì),在到達(dá)最低點(diǎn)之后開(kāi)始上升。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率較小時(shí),任務(wù)在遠(yuǎn)程云端物理機(jī)的響應(yīng)時(shí)間占平均響應(yīng)時(shí)間的主導(dǎo)地位。隨著任務(wù)分配到移動(dòng)設(shè)備本地的概率的增大,任務(wù)在遠(yuǎn)程云端物理機(jī)緩存區(qū)的平均等待時(shí)間隨之減少,任務(wù)平均響應(yīng)時(shí)間降低。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率較大時(shí),任務(wù)在移動(dòng)設(shè)備的響應(yīng)時(shí)間占平均響應(yīng)時(shí)間的主導(dǎo)地位。隨著任務(wù)分配到移動(dòng)設(shè)備本地的概率的增大,任務(wù)在移動(dòng)設(shè)備本地的平均等待時(shí)間隨之增大,任務(wù)平均響應(yīng)時(shí)間上升。

圖4 任務(wù)平均響應(yīng)時(shí)間的變化趨勢(shì)

縱向觀察圖4,隨著任務(wù)到達(dá)率λ的增大,任務(wù)平均響應(yīng)時(shí)間W的變化趨勢(shì)與任務(wù)分配到移動(dòng)設(shè)備本地的概率q有關(guān)。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率較小時(shí),更多的任務(wù)卸載到遠(yuǎn)程云端物理機(jī)接受服務(wù)。任務(wù)到達(dá)率越大,虛擬機(jī)進(jìn)入休眠狀態(tài)的概率越小,任務(wù)平均響應(yīng)時(shí)間隨之減少。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率較大時(shí),分配到移動(dòng)設(shè)備本地的任務(wù)越多,任務(wù)在移動(dòng)設(shè)備本地的等待時(shí)間變長(zhǎng),任務(wù)平均響應(yīng)時(shí)間隨之增大。

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

圖5 刻畫(huà)了任務(wù)到達(dá)率λ與任務(wù)分配到移動(dòng)設(shè)備本地的概率q對(duì)系統(tǒng)平均運(yùn)行功率P的影響。

橫向觀察圖5,隨著任務(wù)分配到移動(dòng)設(shè)備本地的概率q的增大,系統(tǒng)平均運(yùn)行功率P先呈現(xiàn)下降趨勢(shì),在到達(dá)最低點(diǎn)之后開(kāi)始逐漸上升。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率較小時(shí),更多的任務(wù)卸載到遠(yuǎn)程云端物理機(jī)接受服務(wù),遠(yuǎn)程云端物理機(jī)的運(yùn)行功率占系統(tǒng)平均運(yùn)行功率P的主導(dǎo)地位。隨著任務(wù)分配到移動(dòng)設(shè)備本地的概率增大,卸載到遠(yuǎn)程云端物理機(jī)的任務(wù)量減少,物理機(jī)上的虛擬機(jī)處于活躍狀態(tài)的可能性減小,物理機(jī)的運(yùn)行功率下降,系統(tǒng)平均運(yùn)行功率下降。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率較大時(shí),更多的任務(wù)分配到移動(dòng)設(shè)備本地接受服務(wù),移動(dòng)設(shè)備本地的運(yùn)行功率占系統(tǒng)平均運(yùn)行功率P的主導(dǎo)地位。隨著任務(wù)分配到移動(dòng)設(shè)備本地的概率增大,分配到移動(dòng)設(shè)備本地的任務(wù)增多,移動(dòng)設(shè)備功耗增大,系統(tǒng)平均運(yùn)行功率上升。

縱向觀察圖5,隨著任務(wù)到達(dá)率λ的增大,系統(tǒng)平均運(yùn)行功率P隨之增大。任務(wù)到達(dá)率越大,意味著任務(wù)量越多,移動(dòng)設(shè)備與物理機(jī)的功耗增大,系統(tǒng)平均運(yùn)行功率上升。

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

圖5 系統(tǒng)平均運(yùn)行功率的變化趨勢(shì)

比較圖4 與圖5 可以看出,最低的平均響應(yīng)時(shí)間所對(duì)應(yīng)的任務(wù)分配到移動(dòng)設(shè)備本地的概率無(wú)法實(shí)現(xiàn)最低的能耗水平。實(shí)際應(yīng)用中,需根據(jù)實(shí)際應(yīng)用的業(yè)務(wù)特點(diǎn)設(shè)置任務(wù)分配到移動(dòng)設(shè)備本地的概率。

5 系統(tǒng)優(yōu)化

系統(tǒng)實(shí)驗(yàn)所揭示的任務(wù)平均響應(yīng)時(shí)間和系統(tǒng)平均運(yùn)行功率的變化規(guī)律表明,任務(wù)到達(dá)率、休眠參數(shù)與任務(wù)分配到移動(dòng)設(shè)備本地的概率是影響系統(tǒng)性能的重要因素。在不同的任務(wù)到達(dá)率下,合理設(shè)置任務(wù)分配到移動(dòng)設(shè)備本地的概率能夠?qū)崿F(xiàn)響應(yīng)性能與能耗水平的合理均衡。

對(duì)任務(wù)平均響應(yīng)時(shí)間W與系統(tǒng)平均運(yùn)行功率P進(jìn)行歸一化處理,構(gòu)造無(wú)量綱系統(tǒng)成本函數(shù)如下。

其中,f1表示任務(wù)平均響應(yīng)時(shí)間對(duì)系統(tǒng)成本函數(shù)的影響因子,f2表示系統(tǒng)平均功率對(duì)系統(tǒng)成本函數(shù)的影響因子[10]。當(dāng)任務(wù)分配到移動(dòng)設(shè)備本地的概率q的取值在[0,0.9]時(shí),任務(wù)平均響應(yīng)時(shí)間W的最大值和最小值表示為Wmax和Wmin,系統(tǒng)平均運(yùn)行功率P的最大值和最小值表示為Pmax和Pmin。

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

步驟1初始化算法執(zhí)行的最大迭代次數(shù)Maxiter=10 000,鯨魚(yú)種群規(guī)模N=1000;設(shè)置任務(wù)分配到移動(dòng)設(shè)備本地的概率q的上限qup=1 及下限qlow=0,當(dāng)前迭代次數(shù)iter=1。

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

步驟3設(shè)第1 條鯨魚(yú)位置為當(dāng)前最優(yōu)位置q*,利用式(30)計(jì)算系統(tǒng)成本函數(shù)F(q*)。

步驟4利用式(30)計(jì)算全部鯨魚(yú)所對(duì)應(yīng)的系統(tǒng)成本函數(shù)F(qi(iter)),i=1,2,…,N,找出當(dāng)前最優(yōu)鯨魚(yú)位置q*。

步驟5根據(jù)鯨魚(yú)捕食行為更新鯨魚(yú)位置。

步驟6判斷迭代過(guò)程是否完成。

步驟7輸出最優(yōu)鯨魚(yú)位置為最優(yōu)分配到移動(dòng)設(shè)備本地的概率q*,給出最小系統(tǒng)成本函F(q*)。

設(shè)置系統(tǒng)成本函數(shù)的影響因子f1=2.0、f2=1.6,利用改進(jìn)的鯨魚(yú)優(yōu)化算法給出不同任務(wù)到達(dá)率下任務(wù)分配到移動(dòng)設(shè)備本地的最優(yōu)概率,優(yōu)化結(jié)果如表2 所示。

表2 任務(wù)分配到移動(dòng)設(shè)備本地的概率的優(yōu)化結(jié)果

從表2 的數(shù)值結(jié)果可以看出,任務(wù)分配到移動(dòng)設(shè)備本地的最優(yōu)概率隨著任務(wù)到達(dá)率的增大逐漸減小。移動(dòng)設(shè)備的本地處理能力有限,隨著任務(wù)到達(dá)率的增大,移動(dòng)設(shè)備本地的任務(wù)量負(fù)載加重,因此,任務(wù)分配到本地執(zhí)行的最優(yōu)概率呈下降趨勢(shì)。

6 結(jié)論

綜合考慮云用戶(hù)的響應(yīng)性能與云系統(tǒng)的能耗水平,在遠(yuǎn)程云端引入周期性休眠機(jī)制,提出了一種云計(jì)算任務(wù)調(diào)度策略。基于遠(yuǎn)程云端,考慮異構(gòu)物理機(jī),建立同步多重休假M(fèi)/M/ck排隊(duì)模型,給出了系統(tǒng)模型的穩(wěn)態(tài)分布。基于Matlab 進(jìn)行了系統(tǒng)實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,任務(wù)平均響應(yīng)時(shí)間與系統(tǒng)平均運(yùn)行功率之間存在折衷關(guān)系。設(shè)定任務(wù)平均響應(yīng)時(shí)間和系統(tǒng)平均運(yùn)行功率的影響因子,構(gòu)建了系統(tǒng)成本函數(shù)。利用混沌方程初始化種群位置,改進(jìn)鯨魚(yú)優(yōu)化算法,給出了任務(wù)分配到移動(dòng)設(shè)備本地的概率的優(yōu)化結(jié)果,實(shí)現(xiàn)了系統(tǒng)成本函數(shù)的最小化。