基于半休眠模式的云計(jì)算任務(wù)卸載策略及性能研究①

宋 家 余 靖 金順福

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

0 引言

隨著智能手機(jī)的大量普及和移動(dòng)通信網(wǎng)絡(luò)的迅猛發(fā)展,各類網(wǎng)絡(luò)應(yīng)用程序,如交互式游戲、虛擬現(xiàn)實(shí)、自然語(yǔ)言處理等層出不窮。這些應(yīng)用程序通常是計(jì)算密集型和高耗能的,不適合在計(jì)算能力和電池供應(yīng)有限的移動(dòng)設(shè)備上工作。為了滿足復(fù)雜應(yīng)用程序的資源需求,移動(dòng)云計(jì)算的概念應(yīng)運(yùn)而生。如何設(shè)計(jì)同時(shí)保證云用戶的服務(wù)質(zhì)量和云服務(wù)供應(yīng)商運(yùn)營(yíng)利潤(rùn)的云計(jì)算卸載策略成為熱門研究問題[1-2]。

過去的幾年中,云數(shù)據(jù)中心的能源消耗持續(xù)增長(zhǎng),云數(shù)據(jù)中心消耗的大量能量對(duì)環(huán)境造成了不利影響。文獻(xiàn)[3]提出了以節(jié)省能量消耗為目標(biāo)的云資源調(diào)度優(yōu)化管理程序,利用虛擬機(jī)監(jiān)控程序分配資源,實(shí)現(xiàn)云計(jì)算資源分配的最小能耗和最高效率。文獻(xiàn)[4]為了解決云用戶的服務(wù)質(zhì)量和能耗等問題提出了一種云計(jì)算環(huán)境下動(dòng)態(tài)資源分配模型,使用間距多目標(biāo)蟻群算法將云系統(tǒng)狀態(tài)的動(dòng)態(tài)變化與任務(wù)調(diào)度相結(jié)合,通過調(diào)整未使用的虛擬機(jī),節(jié)省云系統(tǒng)的能源消耗。上述文獻(xiàn)均采用資源優(yōu)化配置的方式節(jié)省云系統(tǒng)能源消耗。

考慮到大部分云資源的使用率都較低,部分研究通過應(yīng)用休眠機(jī)制以實(shí)現(xiàn)降低能源消耗的目的。文獻(xiàn)[5]為提高云系統(tǒng)節(jié)能水平,同時(shí)滿足云用戶響應(yīng)性能,引入休眠延遲機(jī)制與休眠喚醒閾值,提出了一種云資源調(diào)度策略。建立帶有休假延遲與啟動(dòng)過程的同步N-策略多重休假排隊(duì)模型,評(píng)估了所提策略的系統(tǒng)性能。文獻(xiàn)[6]以實(shí)現(xiàn)綠色云計(jì)算為目的,將基于喚醒閾值的休眠模式引入到集群虛擬機(jī)中,提出了一種云任務(wù)分配策略。建立異步N-策略多重休假排隊(duì)模型,給出了任務(wù)平均延遲和系統(tǒng)節(jié)能率的表達(dá)式。在以上的休眠機(jī)制中,處于休眠狀態(tài)的虛擬機(jī)完全不工作,雖然有效降低了云系統(tǒng)能源消耗,但是云用戶的服務(wù)質(zhì)量得不到保證。

本文兼顧云用戶的服務(wù)質(zhì)量與云系統(tǒng)的能源消耗水平,在云端引入周期性同步半休眠模式,提出一種新型的云計(jì)算任務(wù)卸載策略?？紤]不同負(fù)載情況下的云端虛擬機(jī)服務(wù)速率,構(gòu)建連續(xù)時(shí)間工作休假的排隊(duì)模型,研究云用戶的隨機(jī)行為。結(jié)合系統(tǒng)中任務(wù)請(qǐng)求的數(shù)量、本地處理器狀態(tài)以及云端虛擬機(jī)狀態(tài),建立二維連續(xù)時(shí)間的Markov 鏈,進(jìn)行云用戶平均響應(yīng)時(shí)間與云系統(tǒng)能源消耗的理論分析。考慮不同休眠參數(shù)和不同系統(tǒng)負(fù)載,基于Matlab 進(jìn)行系統(tǒng)實(shí)驗(yàn),給出系統(tǒng)性能指標(biāo)的統(tǒng)計(jì)結(jié)果。構(gòu)造系統(tǒng)成本函數(shù),利用Logistic 映射混沌方法初始化種群位置,改進(jìn)海鷗優(yōu)化算法。以最小化系統(tǒng)成本函數(shù)為目標(biāo),優(yōu)化任務(wù)請(qǐng)求本地分配概率,為云計(jì)算任務(wù)卸載策略的實(shí)施提供理論依據(jù)。

1 云計(jì)算任務(wù)卸載策略及系統(tǒng)模型

1.1 云計(jì)算任務(wù)卸載策略

針對(duì)移動(dòng)設(shè)備存儲(chǔ)空間不足且處理能力有限等問題,將部分任務(wù)請(qǐng)求遷移到云端[7]。云服務(wù)通過分布式軟件依托于云計(jì)算環(huán)境。在云數(shù)據(jù)服務(wù)中心上通常部署一個(gè)或多個(gè)物理機(jī),而一個(gè)物理機(jī)上又可以部署多個(gè)虛擬機(jī)。當(dāng)一個(gè)物理機(jī)上沒有需要被執(zhí)行的任務(wù)時(shí),如果其上部署的虛擬機(jī)保持空閑狀態(tài),會(huì)因此產(chǎn)生大量的能耗,讓空閑的虛擬機(jī)進(jìn)入休眠狀態(tài)是降低云計(jì)算能耗的有效方法之一。然而,休眠模式也可能會(huì)降低響應(yīng)性能。因此在云端引入半休眠模式,提出一種新的云計(jì)算任務(wù)卸載策略。

產(chǎn)生于移動(dòng)設(shè)備的任務(wù)請(qǐng)求首先匯聚于接入點(diǎn),然后在本地負(fù)載均衡器的調(diào)度下就近分配到本地處理器接受服務(wù),或卸載至云端接受服務(wù)。卸載到云端的任務(wù)請(qǐng)求由云端負(fù)載均衡器分配給某一個(gè)物理機(jī)。云計(jì)算任務(wù)卸載策略的系統(tǒng)架構(gòu)如圖1 所示。

圖1 云計(jì)算任務(wù)卸載策略系統(tǒng)架構(gòu)

當(dāng)一個(gè)物理機(jī)上的任務(wù)請(qǐng)求全部完成時(shí),若緩存區(qū)中也無(wú)等待的任務(wù)請(qǐng)求,則該物理機(jī)上部署的全部虛擬機(jī)同時(shí)由常規(guī)狀態(tài)進(jìn)入半休眠狀態(tài)。在常規(guī)狀態(tài)下的虛擬機(jī)有高速工作狀態(tài)和高速空閑狀態(tài)兩種狀態(tài)。在半休眠狀態(tài)下,虛擬機(jī)不是完全停止工作,而是以低速率運(yùn)轉(zhuǎn),此時(shí)包含有低速工作狀態(tài)和低速空閑狀態(tài)。在所提出的云計(jì)算任務(wù)卸載策略中,虛擬機(jī)共有4 種狀態(tài):高速工作狀態(tài)、高速空閑狀態(tài)、低速工作狀態(tài)和低速空閑狀態(tài)。虛擬機(jī)的狀態(tài)轉(zhuǎn)換過程如圖2 所示。

圖2 虛擬機(jī)的狀態(tài)轉(zhuǎn)換圖

(1) 高速工作狀態(tài)。物理機(jī)及物理機(jī)上部署的全部虛擬機(jī)正常工作,此狀態(tài)下物理機(jī)中至少有一個(gè)虛擬機(jī)正在服務(wù)任務(wù)請(qǐng)求。高速工作狀態(tài)下到達(dá)緩存區(qū)的任務(wù)請(qǐng)求依次在虛擬機(jī)接受服務(wù)。當(dāng)服務(wù)完成最后一個(gè)任務(wù)請(qǐng)求時(shí),物理機(jī)啟動(dòng)休眠定時(shí)器,開始一段半休眠期,物理機(jī)上的所有虛擬機(jī)同時(shí)進(jìn)入低速空閑狀態(tài)。若處于高速工作狀態(tài)的虛擬機(jī)服務(wù)完成當(dāng)前的任務(wù)請(qǐng)求,未分配到新的任務(wù)請(qǐng)求,且同一物理機(jī)內(nèi)有其他虛擬機(jī)還處于高速工作狀態(tài),則該虛擬機(jī)轉(zhuǎn)換到高速空閑狀態(tài)。

(2) 高速空閑狀態(tài)。處于高速空閑狀態(tài)的虛擬機(jī)若分配到新的任務(wù)請(qǐng)求,則立即轉(zhuǎn)換到高速工作狀態(tài)提供服務(wù)。若物理機(jī)服務(wù)完成最后一個(gè)任務(wù)請(qǐng)求,則啟動(dòng)休眠定時(shí)器,其上的所有虛擬機(jī)同時(shí)進(jìn)入低速空閑狀態(tài)。

(3) 低速空閑狀態(tài)。處于低速空閑狀態(tài)的虛擬機(jī)可以隨時(shí)為新到達(dá)的任務(wù)請(qǐng)求提供服務(wù),不受半休眠定時(shí)器的控制。如果在休眠定時(shí)器所規(guī)定的范圍內(nèi)沒有任務(wù)請(qǐng)求到達(dá),物理機(jī)將重新啟動(dòng)休眠定時(shí)器,開始一次新的半休眠期,其上的虛擬機(jī)均保持在低速空閑狀態(tài)。當(dāng)一個(gè)虛擬機(jī)處于低速空閑狀態(tài)時(shí),若休眠定時(shí)器到期,且同一物理機(jī)內(nèi)有其他虛擬機(jī)未服務(wù)完成任務(wù)請(qǐng)求,則物理機(jī)結(jié)束半休眠,該虛擬機(jī)轉(zhuǎn)換到高速空閑狀態(tài);若分配到新的任務(wù)請(qǐng)求,該虛擬機(jī)立即由低速空閑狀態(tài)轉(zhuǎn)換到低速工作狀態(tài)。

(4) 低速工作狀態(tài)。當(dāng)一個(gè)虛擬機(jī)以較低的速率完成當(dāng)前的任務(wù)請(qǐng)求時(shí),如果緩存區(qū)沒有其他等待的任務(wù)請(qǐng)求,該虛擬機(jī)將由低速工作狀態(tài)轉(zhuǎn)換到低速空閑狀態(tài);否則,該虛擬機(jī)保持在低速工作狀態(tài),以較低的服務(wù)速率為緩存區(qū)中等待的任務(wù)請(qǐng)求提供服務(wù)。當(dāng)休眠定時(shí)器到期時(shí),如果有其他虛擬機(jī)還在服務(wù)當(dāng)前的任務(wù)請(qǐng)求,該物理機(jī)上的全部虛擬機(jī)同時(shí)進(jìn)入高速工作狀態(tài)[8]。

1.2 系統(tǒng)模型

將移動(dòng)設(shè)備的CPU 視為本地服務(wù)臺(tái),建立單一服務(wù)臺(tái)連續(xù)工作排隊(duì)。云端每個(gè)虛擬機(jī)視為遠(yuǎn)程服務(wù)臺(tái),建立多服務(wù)臺(tái)同步多重工作休假排隊(duì)。結(jié)合單一服務(wù)臺(tái)連續(xù)工作排隊(duì)與同步多重工作休假排隊(duì),建立系統(tǒng)模型。

假設(shè)移動(dòng)設(shè)備任務(wù)請(qǐng)求的生成間隔是參數(shù)為λ(0＜λ ＜+∞) 的指數(shù)分布。經(jīng)過本地負(fù)載均衡器調(diào)度后以概率p分配到本地,以概率卸載至云端。

顯然,本地服務(wù)臺(tái)任務(wù)請(qǐng)求的到達(dá)服從參數(shù)為λ0=pλ(0＜λ0＜λ) 的Poisson 過程。假設(shè)本地服務(wù)臺(tái)對(duì)一個(gè)任務(wù)請(qǐng)求的服務(wù)時(shí)間服從參數(shù)為μ0(0＜μ0＜+∞) 的指數(shù)分布。假設(shè)本地只有一個(gè)服務(wù)臺(tái),等待緩存區(qū)容量無(wú)窮大,假設(shè)任務(wù)請(qǐng)求的到達(dá)過程與服務(wù)過程是彼此獨(dú)立的。因此,本地服務(wù)臺(tái)執(zhí)行任務(wù)請(qǐng)求的過程可看做M/M/1 排隊(duì)。

在云端負(fù)載均衡器的調(diào)度下,分配到云端的任務(wù)請(qǐng)求以qi(0＜i≤n)(n為云端部署的物理機(jī)個(gè)數(shù))的概率分配到第i個(gè)物理機(jī)接受服務(wù)。對(duì)于第i個(gè)物理機(jī),任務(wù)請(qǐng)求的到達(dá)服從參數(shù)為的Poisson 過程。假設(shè)第i個(gè)物理機(jī)中部署了ci個(gè)相互獨(dú)立并行工作的虛擬機(jī),當(dāng)任務(wù)請(qǐng)求到達(dá)一個(gè)物理機(jī)時(shí),若有高速空閑狀態(tài)的虛擬機(jī),則立即接受服務(wù),否則排隊(duì)等待。一旦物理機(jī)服務(wù)完成最后一個(gè)任務(wù)請(qǐng)求,ci個(gè)虛擬機(jī)同時(shí)開始隨機(jī)長(zhǎng)度Vi的工作休假,其中Vi服從參數(shù)為θi(0＜θi ＜+∞) 的指數(shù)分布。在非工作休假期內(nèi),任務(wù)請(qǐng)求的服務(wù)時(shí)間服從參數(shù)為μbi(0＜μbi ＜+∞) 的指數(shù)分布,工作休假期服務(wù)時(shí)間服從參數(shù)為μvi(0＜μvi ＜μbi) 的指數(shù)分布。假設(shè)所有物理機(jī)具有無(wú)限緩存,假設(shè)任務(wù)請(qǐng)求的到達(dá)間隔、服務(wù)時(shí)間和工作休假期的長(zhǎng)度相互獨(dú)立。因此,第i個(gè)物理機(jī)執(zhí)行任務(wù)請(qǐng)求的過程可看做同步多重工作休假M(fèi)/M/ci排隊(duì)[9-10]。

令隨機(jī)變量Li(t)=l(l=0,1,…) 表示時(shí)刻t第i個(gè)物理機(jī)中任務(wù)請(qǐng)求的數(shù)量,稱為系統(tǒng)水平。令隨機(jī)變量Ji(t)=j(j=0,1) 表示時(shí)刻t物理機(jī)所處的狀態(tài):j=0 表示物理機(jī)處于工作休假狀態(tài),j=1 表示物理機(jī)處于正規(guī)忙狀態(tài)。{(Li(t),Ji(t)),t≥0} 構(gòu)成一個(gè)二維連續(xù)時(shí)間Markov 鏈,其狀態(tài)空間Ωi為

令πi(l,j) 表示穩(wěn)態(tài)下系統(tǒng)水平為l且物理機(jī)狀態(tài)為j的概率分布。πi(l,j) 定義為

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

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

2.1 穩(wěn)態(tài)條件

根據(jù)云計(jì)算任務(wù)卸載策略建立的系統(tǒng)模型由1 個(gè)M/M/1 排隊(duì)和n(n為云端部署的物理機(jī)個(gè)數(shù))個(gè)同步多重工作休假M(fèi)/M/ci排隊(duì)構(gòu)成,其中ci為云端部署的第i(0＜i≤n) 個(gè)物理機(jī)上虛擬機(jī)的個(gè)數(shù)。為確保整個(gè)系統(tǒng)模型達(dá)到穩(wěn)態(tài),需要系統(tǒng)模型中的每一個(gè)排隊(duì)均達(dá)到穩(wěn)態(tài)。

本地處理器所對(duì)應(yīng)的M/M/1 排隊(duì)的穩(wěn)態(tài)條件為

其中,ρ0表示為本地處理器的流通強(qiáng)度。

云端服務(wù)器上部署的第i(0＜i≤n) 個(gè)物理機(jī)所對(duì)應(yīng)的同步多重工作休假M(fèi)/M/ci排隊(duì)的穩(wěn)態(tài)條件為

其中,ρi表示云端服務(wù)器上部署的第i個(gè)物理機(jī)的流通強(qiáng)度。

結(jié)合式(1)與式(2),給出系統(tǒng)模型處于穩(wěn)定狀態(tài)的充分必要條件為

2.2 狀態(tài)轉(zhuǎn)移

根據(jù)云端中每個(gè)物理機(jī)上任務(wù)請(qǐng)求的數(shù)量l與物理機(jī)所處狀態(tài)j之間的關(guān)系,給出Markov 鏈{(Li(t),Ji(t)),t≥0} 的狀態(tài)轉(zhuǎn)移過程,如圖3所示。

圖3 Markov 過程的狀態(tài)轉(zhuǎn)移

由圖3 可知,狀態(tài)轉(zhuǎn)移只發(fā)生在相鄰的系統(tǒng)水平之間,表明二維Markov 鏈{(Li(t),Ji(t)),t≥0}是擬生滅過程。

2.3 穩(wěn)態(tài)分布

令Qi表示Markov 鏈{(Li(t),Ji(t)),t≥0}的一步轉(zhuǎn)移率矩陣。根據(jù)系統(tǒng)水平劃分Qi為若干個(gè)子陣。令Qi(x,y) 表示系統(tǒng)水平由x(x=0,1,…) 到y(tǒng)(y=0,1,…) 的轉(zhuǎn)移率子陣。為表述方便,將Qi(x,x -1)、Qi(x,x) 和Qi(x,x +1) 分別記為Bi(x)、Ai(x) 和Ci(x)。

(1) 當(dāng)?shù)趇個(gè)物理機(jī)中任務(wù)請(qǐng)求的數(shù)量由x變?yōu)閤 -1 時(shí),轉(zhuǎn)移率子陣為Bi(x)。

當(dāng)x=1 時(shí),若以低速率服務(wù)完成任務(wù)請(qǐng)求,虛擬機(jī)將由低速工作狀態(tài)變?yōu)榈退倏臻e狀態(tài),即由狀態(tài)(1,0)轉(zhuǎn)換到狀態(tài)(0,0),轉(zhuǎn)移率為μvi;若以高速率服務(wù)完成任務(wù)請(qǐng)求,虛擬機(jī)將由高速工作狀態(tài)變?yōu)榈退倏臻e狀態(tài),即由狀態(tài)(1,1)轉(zhuǎn)換到狀態(tài)(0,0),轉(zhuǎn)移率為μbi。Bi(1) 為2 ×1 維矩陣,可表示為

當(dāng)2 ≤x≤ci時(shí),若以低速率服務(wù)完成任務(wù)請(qǐng)求,虛擬機(jī)將由低速工作狀態(tài)變?yōu)榈退倏臻e狀態(tài),即由狀態(tài)(x,0) 轉(zhuǎn)換到狀態(tài)(x -1,0),轉(zhuǎn)移率為xμvi;若以高速率服務(wù)完成任務(wù)請(qǐng)求,虛擬機(jī)將由高速工作狀態(tài)變?yōu)楦咚倏臻e狀態(tài),即由狀態(tài)(x,1) 轉(zhuǎn)換到狀態(tài)(x -1,1),轉(zhuǎn)移率為xμbi。Bi(x) 為2 ×2維矩陣,可表示為

當(dāng)x ＞ci時(shí),若以低速率服務(wù)完成任務(wù)請(qǐng)求,虛擬機(jī)將繼續(xù)保持低速工作狀態(tài),即由狀態(tài)(x,0) 轉(zhuǎn)換到狀態(tài)(x -1,0),轉(zhuǎn)移率為ciμvi;若以高速率服務(wù)完成任務(wù)請(qǐng)求,虛擬機(jī)將繼續(xù)保持高速工作狀態(tài),即由狀態(tài)(x,1) 轉(zhuǎn)換到狀態(tài)(x -1,1),轉(zhuǎn)移率為ciμbi。Bi(x) 為2 ×2 維矩陣,可表示為

(2) 當(dāng)?shù)趇個(gè)物理機(jī)中任務(wù)請(qǐng)求的數(shù)量x保持不變時(shí),轉(zhuǎn)移率子陣為Ai(x)。

當(dāng)x=0 時(shí),第i個(gè)物理機(jī)處于半休眠狀態(tài),其上所有虛擬機(jī)低速空轉(zhuǎn)。若無(wú)任務(wù)請(qǐng)求到達(dá),狀態(tài)(0,0)保持不變,轉(zhuǎn)移率為-λi。Ai(0) 退化為一個(gè)數(shù),可表示為

當(dāng)1 ≤x≤ci時(shí),若j=0,第i個(gè)物理機(jī)處于半休眠狀態(tài),其上部署的虛擬機(jī)部分低速運(yùn)轉(zhuǎn)部分低速空轉(zhuǎn)。若無(wú)任務(wù)請(qǐng)求到達(dá)也無(wú)任務(wù)請(qǐng)求離開且休眠定時(shí)器未到期,狀態(tài)(x,0) 保持不變,轉(zhuǎn)移率為-(λi+xμvi+θi);若休眠定時(shí)器到期,物理機(jī)由狀態(tài)(x,0) 轉(zhuǎn)換到狀態(tài)(x,1),轉(zhuǎn)移率為θi。若j=1,第i個(gè)物理機(jī)處于常規(guī)狀態(tài),其上部署的虛擬機(jī)部分高速運(yùn)轉(zhuǎn)部分高速空轉(zhuǎn)。若無(wú)任務(wù)請(qǐng)求到達(dá)也無(wú)任務(wù)請(qǐng)求離開,狀態(tài)(x,1) 保持不變,轉(zhuǎn)移率為-(λi+xμbi)。Ai(x) 為2 ×2 維矩陣,可表示為

當(dāng)x ＞ci時(shí),若j=0,第i個(gè)物理機(jī)處于半休眠狀態(tài),其上部署的虛擬機(jī)部分低速運(yùn)轉(zhuǎn)部分低速空轉(zhuǎn)。若無(wú)任務(wù)請(qǐng)求到達(dá)也無(wú)任務(wù)請(qǐng)求離開且休眠定時(shí)器未到期,狀態(tài)(x,0)保持不變,轉(zhuǎn)移率為-(λi+ciμvi+θi);若休眠定時(shí)器到期,物理機(jī)由狀態(tài)(x,0) 轉(zhuǎn)換到狀態(tài)(x,1),轉(zhuǎn)移率為θi。若j=1,第i個(gè)物理機(jī)處于常規(guī)狀態(tài),其上部署的虛擬機(jī)部分高速運(yùn)轉(zhuǎn)部分高速空轉(zhuǎn)。若無(wú)任務(wù)請(qǐng)求到達(dá)也無(wú)任務(wù)請(qǐng)求離開,狀態(tài)(x,1)保持不變,轉(zhuǎn)移率為-(λi+ciμbi)。Ai(x) 為2 ×2 維矩陣,可表示為

(3) 當(dāng)?shù)趇個(gè)物理機(jī)中任務(wù)請(qǐng)求的數(shù)量由x變?yōu)閤 +1 時(shí),轉(zhuǎn)移率子陣為Ci(x)。

當(dāng)x=0 時(shí),第i個(gè)物理機(jī)處于半休眠狀態(tài),其上所有虛擬機(jī)低速空轉(zhuǎn)。若有任務(wù)請(qǐng)求達(dá)到,其中一個(gè)虛擬機(jī)將變?yōu)榈退俟ぷ鳡顟B(tài),即由狀態(tài)(0,0)轉(zhuǎn)換到狀態(tài)(1,0),轉(zhuǎn)移率為λi。Ci(0) 為1 ×2 維矩陣,可表示為

當(dāng)x≥1 時(shí),若j=0,第i個(gè)物理機(jī)處于半休眠狀態(tài),其上部署的虛擬機(jī)既有低速空轉(zhuǎn)又有低速運(yùn)轉(zhuǎn)。若有任務(wù)請(qǐng)求到達(dá),物理機(jī)由狀態(tài)(x,0) 轉(zhuǎn)換到狀態(tài)(x +1,0),轉(zhuǎn)移率為λi。若j=1,第i個(gè)物理機(jī)處于常規(guī)狀態(tài),其上部署的虛擬機(jī)部分高速運(yùn)轉(zhuǎn)部分高速空轉(zhuǎn)。若有任務(wù)請(qǐng)求到達(dá),物理機(jī)由狀態(tài)(x,1) 轉(zhuǎn)換到狀態(tài)(x +1,1),轉(zhuǎn)移率為λi。Ci(x) 為2 ×2 維矩陣,可表示為

結(jié)合以上給出的一步轉(zhuǎn)移率子陣,發(fā)現(xiàn)Bi(x)(0＜i≤n) 和Ai(x)(0＜i≤n) 從系統(tǒng)水平ci起開始重復(fù),轉(zhuǎn)移率子陣Ci(x)(0＜i≤n) 從系統(tǒng)水平1 起開始重復(fù)。將重復(fù)的Bi(x)、Ai(x) 和Ci(x) 分 別 用Bi、Ai和Ci表 示,則Markov 鏈{(Li(t),Ji(t)),t≥0} 的一步轉(zhuǎn)移率矩陣Qi可表示為分塊三對(duì)角形式

擬生滅過程{(Li(t),Ji(t)),t≥0} 正常返的充分必要條件是矩陣二次方程式

有最小非負(fù)解Ri,且譜半徑Sp(Ri)＜1。最小非負(fù)解Ri被稱為率陣,可以推出其精確解。

由于轉(zhuǎn)移率子陣Bi、Ai和Ci均為上三角矩陣,因此,率陣Ri也為上三角矩陣,表示為

將Ri、Bi、Ai和Ci代入矩陣二次方程式(4)中,可得方程組

利用所得出的率陣Ri,構(gòu)建一個(gè)方陣B[Ri]為

由矩陣幾何解中的平衡方程和歸一化條件可知,擬生滅過程{(Li(t),Ji(t)),t≥0} 的平穩(wěn)分布滿足方程組

其中,e1是(2ci -1)×1 的全1 列向量,e2是2 ×1的全1 列向量,I是2 ×2 的單位陣。

利用高斯-塞德爾法求解方程式(7),可以給出πi(k)(0 ≤k≤ci) 的數(shù)值解。

基于矩陣幾何解方法,由πi(ci) 進(jìn)一步給出πi(k)(k≥ci +1) 如下:

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

關(guān)注云用戶響應(yīng)時(shí)間和云系統(tǒng)能耗水平,評(píng)估基于半休眠模式的云計(jì)算任務(wù)卸載策略的性能指標(biāo)。

任務(wù)請(qǐng)求在本地處理器接受服務(wù)的平均響應(yīng)時(shí)間TMD包括任務(wù)請(qǐng)求在本地緩存中的等待時(shí)間與在本地處理器上執(zhí)行的時(shí)間。根據(jù)M/M/1 排隊(duì)模型,可以得到TMD的表達(dá)式為

任務(wù)請(qǐng)求卸載到云端服務(wù)器接受服務(wù)的平均響應(yīng)時(shí)間TC包括任務(wù)請(qǐng)求在云端緩存中的等待時(shí)間與在云端服務(wù)器上執(zhí)行的時(shí)間。卸載到云端后第i個(gè)物理機(jī)上任務(wù)請(qǐng)求的平均響應(yīng)時(shí)間Ti的表達(dá)式為

其中,Tsi表示任務(wù)請(qǐng)求在第i個(gè)物理機(jī)上的平均服務(wù)時(shí)間,e為2 ×1 的全1 列向量。

根據(jù)卸載到第i個(gè)物理機(jī)上的任務(wù)請(qǐng)求到達(dá)云端時(shí)的狀態(tài),分以下4 種情況討論Tsi。(1) 若第i個(gè)物理機(jī)處于常規(guī)狀態(tài),當(dāng)前任務(wù)請(qǐng)求接受高速率服務(wù),平均服務(wù)時(shí)間為;(2) 若第i個(gè)物理機(jī)處于半休眠狀態(tài),休眠定時(shí)器到期之前緩存中排隊(duì)等待的所有任務(wù)請(qǐng)求及當(dāng)前任務(wù)請(qǐng)求均完成服務(wù),當(dāng)前任務(wù)請(qǐng)求接受低速率服務(wù),平均服務(wù)時(shí)間為;(3) 若第i個(gè)物理機(jī)處于半休眠狀態(tài),休眠定時(shí)器到期之前緩存中排隊(duì)等待的所有任務(wù)請(qǐng)求均完成服務(wù),但當(dāng)前任務(wù)請(qǐng)求未服務(wù)完成,當(dāng)前任務(wù)請(qǐng)求經(jīng)歷一段低速率服務(wù)和一段高速率服務(wù),平均服務(wù)時(shí)間為;(4) 若第i個(gè)物理機(jī)處于半休眠狀態(tài),休眠定時(shí)器到期時(shí),緩存中有排隊(duì)等待的任務(wù)請(qǐng)求未服務(wù)完成,當(dāng)前任務(wù)請(qǐng)求接受高速率服務(wù),平均服務(wù)時(shí)間為。因此,任務(wù)請(qǐng)求在第i個(gè)物理機(jī)上的平均服務(wù)時(shí)間Tsi表示為

令任務(wù)請(qǐng)求分配到第i個(gè)物理機(jī)上的概率為qi(0＜qi ＜1),則卸載到云端接受服務(wù)的任務(wù)請(qǐng)求的平均響應(yīng)時(shí)間TC的表達(dá)式為

云用戶的平均響應(yīng)時(shí)間T定義為任務(wù)請(qǐng)求從進(jìn)入系統(tǒng)開始直到離開系統(tǒng)所經(jīng)歷的時(shí)間長(zhǎng)度的平均值。結(jié)合式(8)和式(9),給出平均響應(yīng)時(shí)間T的表達(dá)式為

其中,p(0＜p ＜1) 為任務(wù)請(qǐng)求在本地處理器接受服務(wù)的概率,為任務(wù)請(qǐng)求卸載到云端服務(wù)器接受服務(wù)的概率。

本地處理器處于工作狀態(tài)時(shí)的平均運(yùn)行功率表示為Pbusy,處于空閑狀態(tài)時(shí)的平均運(yùn)行功率表示為Pidle。任務(wù)請(qǐng)求在本地處理器接受服務(wù)的平均功率消耗EMD為

云端上部署的第i個(gè)物理機(jī)處于半休眠狀態(tài)時(shí),該物理機(jī)維持其上一個(gè)虛擬機(jī)空轉(zhuǎn)的平均運(yùn)行功率表示為;維持其上一個(gè)虛擬機(jī)運(yùn)轉(zhuǎn)的平均運(yùn)行功率表示為。云端上部署的第i個(gè)物理機(jī)處于常規(guī)狀態(tài)時(shí),該物理機(jī)維持其上一個(gè)虛擬機(jī)空轉(zhuǎn)的平均運(yùn)行功率表示為;維持其上一個(gè)虛擬機(jī)運(yùn)轉(zhuǎn)的平均運(yùn)行功率表示為。任務(wù)請(qǐng)求在云端服務(wù)器接受服務(wù)的平均功率消耗為

結(jié)合式(11)和式(12),給出系統(tǒng)平均功率E的表達(dá)式為

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

為了進(jìn)一步進(jìn)行系統(tǒng)實(shí)驗(yàn)研究任務(wù)請(qǐng)求初始分配概率與休眠參數(shù)對(duì)云計(jì)算任務(wù)卸載策略的影響,進(jìn)行性能指標(biāo)變化趨勢(shì)的系統(tǒng)實(shí)驗(yàn)。系統(tǒng)實(shí)驗(yàn)的計(jì)算機(jī)硬件環(huán)境為Intel(R) Core(TM),i7-4790 CPU@3.60 GHz,8.00 GB RAM。軟件環(huán)境為Matlab R2016a。

在保證系統(tǒng)模型穩(wěn)定的條件下的參數(shù)設(shè)置如表1所示。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

根據(jù)表1 設(shè)定的實(shí)驗(yàn)參數(shù),針對(duì)不同的休眠參數(shù)θ和不同的任務(wù)請(qǐng)求到達(dá)率λ,給出云用戶平均響應(yīng)時(shí)間T隨任務(wù)請(qǐng)求本地分配概率p的變化趨勢(shì)如圖4 所示。

圖4 云用戶平均響應(yīng)時(shí)間的變化趨勢(shì)

對(duì)比圖4 (a)和4 (b)可知,當(dāng)任務(wù)請(qǐng)求本地分配概率p和任務(wù)請(qǐng)求到達(dá)率λ一定時(shí),隨著休眠參數(shù)θ的增大,云用戶平均響應(yīng)時(shí)間T減小。休眠參數(shù)θ較大時(shí),云端物理機(jī)處于半休眠狀態(tài)的時(shí)間長(zhǎng)度縮短。這種情況下,云端服務(wù)器可以更及時(shí)地返回常規(guī)狀態(tài)以高速服務(wù)率為任務(wù)請(qǐng)求提供服務(wù)。因此,云用戶平均響應(yīng)時(shí)間T減小。

固定任務(wù)請(qǐng)求到達(dá)率λ和休眠參數(shù)θ,分別觀察圖4(a)和圖4(b)可知,隨著任務(wù)請(qǐng)求本地分配概率p的增加,云用戶平均響應(yīng)時(shí)間T呈現(xiàn)出先下降后上升的趨勢(shì)。在曲線最低點(diǎn)左側(cè),任務(wù)請(qǐng)求本地分配概率p較小,任務(wù)請(qǐng)求到達(dá)系統(tǒng)后大概率地卸載到云端服務(wù)器接受服務(wù),任務(wù)請(qǐng)求在云端的響應(yīng)時(shí)間成為云用戶平均響應(yīng)時(shí)間T的主導(dǎo)因素。隨著任務(wù)請(qǐng)求本地分配概率p的增加,分配到本地的任務(wù)請(qǐng)求逐漸增多,堆積在云端的任務(wù)請(qǐng)求減少,云用戶平均響應(yīng)時(shí)間T隨之減小。在曲線最低點(diǎn)右側(cè),任務(wù)請(qǐng)求本地分配概率p較大,任務(wù)請(qǐng)求到達(dá)系統(tǒng)后大概率地選擇在本地處理器接受服務(wù),任務(wù)請(qǐng)求在本地處理器接受服務(wù)的響應(yīng)時(shí)間成為云用戶平均響應(yīng)時(shí)間T的主導(dǎo)因素。隨著任務(wù)請(qǐng)求本地分配概率p的增加,分配到本地的任務(wù)請(qǐng)求越來(lái)越多,大量的任務(wù)請(qǐng)求將會(huì)堆積在本地處理器的緩存區(qū),云用戶平均響應(yīng)時(shí)間T隨之增大。

固定休眠參數(shù)θ和任務(wù)請(qǐng)求本地分配概率p,分別觀察圖4(a)和圖4(b)可知,隨著任務(wù)請(qǐng)求到達(dá)率λ的增加,云用戶平均響應(yīng)時(shí)間T增加。無(wú)論是在本地還是云端,隨著任務(wù)請(qǐng)求到達(dá)率λ的值增大,系統(tǒng)內(nèi)到達(dá)的任務(wù)請(qǐng)求數(shù)量也就越多,顯然云用戶平均響應(yīng)時(shí)間T將會(huì)增大。

針對(duì)不同的休眠參數(shù)θ和不同的任務(wù)請(qǐng)求到達(dá)率λ,給出云系統(tǒng)平均功率E隨任務(wù)請(qǐng)求本地分配概率p的變化趨勢(shì)如圖5 所示。

對(duì)比圖5(a)和5(b)可知,當(dāng)任務(wù)請(qǐng)求到達(dá)率λ一定而任務(wù)請(qǐng)求本地分配概率p較小時(shí),隨著休眠參數(shù)θ的增大,云系統(tǒng)平均功率E略有增大。休眠參數(shù)θ較大時(shí),云端物理機(jī)處于半休眠狀態(tài)的時(shí)間長(zhǎng)度縮短,物理機(jī)可以更及時(shí)地轉(zhuǎn)換到常規(guī)狀態(tài)。處于常規(guī)狀態(tài)的物理機(jī)所消耗的功率大于處于半休眠狀態(tài)的物理機(jī)所消耗的功率。因此,云系統(tǒng)平均功率E增加。當(dāng)任務(wù)請(qǐng)求到達(dá)率λ一定而任務(wù)請(qǐng)求本地分配概率p較大時(shí),卸載到云端的任務(wù)請(qǐng)求數(shù)量較少,云端物理機(jī)有更多的機(jī)會(huì)持續(xù)處于半休眠狀態(tài)。云系統(tǒng)平均功率E與休眠參數(shù)θ的關(guān)系減弱。

固定休眠參數(shù)θ和任務(wù)請(qǐng)求到達(dá)率λ,分別觀察圖5(a)和圖5(b)可知,隨著任務(wù)請(qǐng)求本地分配概率p的增加,云系統(tǒng)平均功率E呈現(xiàn)出先下降后上升的趨勢(shì)。在曲線最低點(diǎn)左側(cè),任務(wù)請(qǐng)求本地分配概率p較小,任務(wù)請(qǐng)求到達(dá)系統(tǒng)后大概率地卸載到云端服務(wù)器接受服務(wù)。隨著任務(wù)請(qǐng)求本地分配概率p的增加,卸載到云端的任務(wù)請(qǐng)求減少,云端物理機(jī)有更多的機(jī)會(huì)進(jìn)入半休眠狀態(tài),云系統(tǒng)平均功率E隨之減小。在曲線最低點(diǎn)右側(cè),任務(wù)請(qǐng)求本地分配概率p較大,任務(wù)請(qǐng)求到達(dá)系統(tǒng)后大概率地選擇在本地處理器接受服務(wù)。隨著任務(wù)請(qǐng)求本地分配概率p的增加,本地處理器提供服務(wù)需要的功耗增加,云系統(tǒng)平均功率E隨之變大。

圖5 云系統(tǒng)平均功率的變化趨勢(shì)

固定休眠參數(shù)θ和任務(wù)請(qǐng)求本地分配概率p,分別觀察圖5(a)和圖5(b)還可知,隨著任務(wù)請(qǐng)求到達(dá)率λ的增加,云系統(tǒng)平均功率E增加。無(wú)論是在本地還是云端,隨著任務(wù)請(qǐng)求到達(dá)率λ的增大,系統(tǒng)內(nèi)到達(dá)的任務(wù)請(qǐng)求數(shù)量增多,執(zhí)行任務(wù)請(qǐng)求需要的功耗更多,因此云系統(tǒng)平均功率E將會(huì)增大。

綜合圖4 和圖5 的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn),任務(wù)請(qǐng)求本地分配概率是影響系統(tǒng)性能的重要因素。兼顧云用戶和云系統(tǒng)的不同要求,在不同的任務(wù)請(qǐng)求到達(dá)率和相同的休眠參數(shù)情況下,優(yōu)化任務(wù)請(qǐng)求本地分配概率。

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

為了權(quán)衡云用戶平均響應(yīng)時(shí)間與云系統(tǒng)平均功率之間的折衷關(guān)系,構(gòu)造系統(tǒng)成本函數(shù)F為

其中,β1表示云用戶平均響應(yīng)時(shí)間T對(duì)系統(tǒng)成本的影響因子,β2表示云系統(tǒng)平均功率E對(duì)系統(tǒng)成本的影響因子。在實(shí)際應(yīng)用中,對(duì)于高響應(yīng)需求的云系統(tǒng),可將參數(shù)β1的值設(shè)置得大些;而對(duì)于高節(jié)能需求的云系統(tǒng),則可將參數(shù)β2的值設(shè)置得大些。

與其他智能優(yōu)化算法相比,海鷗智能優(yōu)化算法容易實(shí)現(xiàn),且不需要調(diào)整過多的參數(shù)[13]。為了加快算法搜索速度,利用Logistic 映射混沌方法進(jìn)行海鷗位置初始化,改進(jìn)海鷗優(yōu)化算法,優(yōu)化任務(wù)請(qǐng)求本地分配概率。算法中海鷗的位置表示任務(wù)請(qǐng)求本地分配概率p,海鷗的適應(yīng)值表示系統(tǒng)成本函數(shù)F的值。算法的主要步驟如下。

步驟1初始化海鷗數(shù)量N,最大迭代次數(shù)Maxiterations,控制海鷗在給定搜索空間中運(yùn)動(dòng)行為A的頻率fc,螺旋攻擊形狀的相關(guān)常數(shù)u、v,海鷗飛行位置的上邊界Maxp與下邊界Minp。初始化當(dāng)前迭代次數(shù)t=0。

步驟2利用Logistic 映射方法產(chǎn)生混沌變量初始化海鷗的位置。

步驟3初始化當(dāng)前最佳海鷗位置p*和適應(yīng)值F*。

步驟4根據(jù)海鷗遷徙行為和攻擊行為更新海鷗位置。

步驟5使用系統(tǒng)成本函數(shù)F計(jì)算海鷗的適應(yīng)值F(pm),m=1,2,…,N。

步驟6找出當(dāng)前最佳海鷗位置p*和適應(yīng)值F*。

步驟7更新迭代次數(shù)。

步驟8輸出最佳海鷗位置為最優(yōu)任務(wù)請(qǐng)求本地分配概率p*;輸出最佳適應(yīng)值為最小系統(tǒng)成本F*。

沿用第4 節(jié)系統(tǒng)實(shí)驗(yàn)的參數(shù),設(shè)定β1=2,β2=0.2,N=30,Maxiterations=1000,fc=2,u=1,v=1,Maxp=0.99999,Minp=0.00001。利用改進(jìn)的海鷗優(yōu)化算法,給出任務(wù)請(qǐng)求本地分配概率的優(yōu)化結(jié)果如表2 所示。

由表2 的優(yōu)化結(jié)果可知,對(duì)于相同的休眠參數(shù)θ,當(dāng)任務(wù)請(qǐng)求到達(dá)率λ增大時(shí),受本地處理器處理能力的限制,會(huì)有更多的任務(wù)請(qǐng)求卸載到云端服務(wù)器,因此,最優(yōu)任務(wù)請(qǐng)求本地分配概率p*變小。對(duì)于相同的任務(wù)請(qǐng)求到達(dá)率λ,休眠參數(shù)θ越大,云端服務(wù)器處于半休眠狀態(tài)的時(shí)間越短,云端服務(wù)器產(chǎn)生的功率消耗越高。為了實(shí)現(xiàn)系統(tǒng)成本的最小化,更多的任務(wù)請(qǐng)求將在本地處理器接受服務(wù),因此,最優(yōu)任務(wù)請(qǐng)求本地分配概率p*越大越好。

表2 任務(wù)請(qǐng)求本地分配概率的優(yōu)化結(jié)果

6 結(jié)論

綜合考慮云用戶低響應(yīng)時(shí)間與云系統(tǒng)低功率消耗的要求,根據(jù)系統(tǒng)負(fù)載調(diào)整云端服務(wù)器的工作速率,基于半休眠模式,提出了一種云計(jì)算任務(wù)卸載策略。通過建立本地單一服務(wù)臺(tái)連續(xù)工作排隊(duì)和云端多服務(wù)臺(tái)同步多重工作休假排隊(duì),給出了穩(wěn)態(tài)下云用戶平均響應(yīng)時(shí)間和云系統(tǒng)平均功率的表達(dá)式,并通過實(shí)驗(yàn)揭示出不同性能指標(biāo)之間的折衷關(guān)系。從經(jīng)濟(jì)學(xué)角度出發(fā),構(gòu)建了系統(tǒng)成本函數(shù),改進(jìn)傳統(tǒng)的海鷗優(yōu)化算法,給出了任務(wù)請(qǐng)求本地分配概率的優(yōu)化方案。

本文所引入的周期性同步半休眠模式具有良好的節(jié)能效果。在未來(lái)的研究中,將考慮具有多級(jí)適應(yīng)性的半休眠模式,以進(jìn)一步提高用戶的響應(yīng)性能。