混合云環(huán)境下的異構(gòu)任務(wù)調(diào)度方法

冒佳明 王鵬飛 趙然

摘要

混合云融合了私有云與公有云，同時(shí)兼具二者優(yōu)勢(shì)。然而，由于其中私有云的任務(wù)處理能力有限、任務(wù)的到達(dá)具有非周期性，動(dòng)態(tài)調(diào)度所有到達(dá)任務(wù)以獲得較高效益是具有挑戰(zhàn)性的問(wèn)題。針對(duì)此問(wèn)題，本文建立了基于延時(shí)服務(wù)與私有云成本的分布式異構(gòu)云環(huán)境模型，提出了一種私有云效益最大化算法，該算法的核心在于使用改進(jìn)的模擬退火粒子群算法，對(duì)每一次迭代進(jìn)行優(yōu)化從而實(shí)現(xiàn)較優(yōu)的調(diào)度效果。

【關(guān)鍵詞】混合云 效益最大化 任務(wù)調(diào)度 啟發(fā)式算法

1 簡(jiǎn)介

隨著云計(jì)算技術(shù)的日益成熟和持續(xù)推廣，更多用戶(hù)選擇將其應(yīng)用托管至云平臺(tái)中運(yùn)行。云可以被分為三類(lèi)：公有云、私有云與分布式異構(gòu)云（混合云）。私有云可保證應(yīng)用的安全與兼容性。公有云可保證豐富的計(jì)算資源與體驗(yàn)?；旌显迫诤纤接性坪凸性?，成為了近年來(lái)云計(jì)算的主要發(fā)展方向與模式，為更多企業(yè)級(jí)用戶(hù)采用。如圖1所示，混合云融合了二者的優(yōu)點(diǎn)，不僅確保了用戶(hù)的體驗(yàn)而且確保應(yīng)用的安全性。

基于混合云架構(gòu)的任務(wù)調(diào)度問(wèn)題是合理調(diào)度混合云系統(tǒng)資源的核心問(wèn)題之一。從云用戶(hù)的角度看，如何合理利用混合云資源，在保證任務(wù)完成的同時(shí)最大化系統(tǒng)效益，是開(kāi)展任務(wù)調(diào)度的核心問(wèn)題。然而，由于任務(wù)的到達(dá)具有非周期性的特點(diǎn)，且難以預(yù)測(cè)任務(wù)的資源需求形式與規(guī)模。因此，在保證任務(wù)響應(yīng)時(shí)延的前提下，如何動(dòng)態(tài)調(diào)度所有任務(wù)以獲得較高的總體效益是面向混合云架構(gòu)的任務(wù)調(diào)度的基本問(wèn)題。

從混合云執(zhí)行任務(wù)的角度看，完成一定的任務(wù)具有確定的效益。而在成本方面，私有云的資源價(jià)格相比公有云要低，且利用公有云資源需要更多的傳輸開(kāi)銷(xiāo)與時(shí)間開(kāi)銷(xiāo)，可能會(huì)導(dǎo)致任務(wù)無(wú)法及時(shí)完成。但是，私有云資源的有限定迫使公有云必須要納入到調(diào)度的資源池內(nèi)。針對(duì)混合云調(diào)度的特點(diǎn)，本文綜合考慮公有云虛擬機(jī)價(jià)格的多樣性、公有云與私有云之間的數(shù)據(jù)傳輸速率和私有云中波動(dòng)的價(jià)格成本，制定一項(xiàng)綜合模型用以描述分布式異構(gòu)云的環(huán)境;并提出私有云效益最大化算法來(lái)執(zhí)行任務(wù)調(diào)度。

2 私有云效益最大化問(wèn)題描述

混合云的體系架構(gòu)如圖2所示。該架構(gòu)分為兩部分，其中一部分是私有云模塊，另一部分是公有云模塊。任務(wù)通過(guò)網(wǎng)絡(luò)到達(dá)混合云中的私有云模塊，保存至先進(jìn)先出的任務(wù)隊(duì)列等待調(diào)度。任務(wù)調(diào)度器綜合分析私有云的剩余資源信息與私有云的未來(lái)電價(jià)信息對(duì)任務(wù)進(jìn)行調(diào)度。在私有云容納范圍之內(nèi)，將部分任務(wù)調(diào)度至其中，并把其余任務(wù)調(diào)度至公有云模塊中。

假設(shè)CP={CP₁，CP₂，…，CP_n}為混合云計(jì)算中心集合，CP₁為私有云計(jì)算中心，CP₂，…，CP_n為公有云計(jì)算中，n為云計(jì)算中心的數(shù)量。用CP_kv表示CP_k中第v類(lèi)虛擬機(jī)的單位時(shí)隙價(jià)格;CPU_v，MEM_v和POW_v分別代表了第v類(lèi)虛擬機(jī)的CPU數(shù)量，內(nèi)存大小與功耗;CPU_total，CPU_t^rest，MEM_total和MEM_t^rest分別表示私有云的總CPU資源，私有云在t時(shí)隙剩余的CPU資源，私有云的總內(nèi)存資源和私有云在t時(shí)隙剩余的內(nèi)存資源;B和B_k則分別代表了私有云的服務(wù)延時(shí)范圍與公有云k的服務(wù)延時(shí)范圍;P_t代表了私有云在t時(shí)隙中的電價(jià)。假設(shè)T為一個(gè)云計(jì)算任務(wù)，則該任務(wù)到達(dá)云計(jì)算中心的時(shí)隙、目標(biāo)虛擬機(jī)、需要運(yùn)行時(shí)間和存儲(chǔ)空間大小分別用T_A，T_V，T_R和T_S表示。

對(duì)于一次任務(wù)調(diào)度，用Income表示的收入，Cost表示花費(fèi)，Benefit表示效益。由問(wèn)題定義可得，任務(wù)調(diào)度的收入Income由所有到達(dá)任務(wù)的目標(biāo)虛擬機(jī)、任務(wù)的運(yùn)行長(zhǎng)度決定。同時(shí)收入Income可定義為在時(shí)隙t任務(wù)被調(diào)度至私有云與公有云中用戶(hù)所需要支付的費(fèi)用之和，如下表示：

對(duì)于混合云中的成本Cost可表示為任務(wù)在私有云運(yùn)行消耗電費(fèi)與向公有云支付的費(fèi)用之和，表示如下：

其中，中POW，表示該類(lèi)虛擬機(jī)耗電量，P_t+j表示t+j時(shí)隙的電價(jià)·因此，該問(wèn)題表示如下：

3 效益最大化優(yōu)化算法

本問(wèn)題的目標(biāo)問(wèn)題為最大化Benefit，當(dāng)中決策參數(shù)為d_t，d_tⁱ，Y_t^jk，dk_t，dk_tⁱ都為整數(shù)型變量，同時(shí)該參數(shù)受到多條件約束。可將該問(wèn)題規(guī)約至整數(shù)規(guī)劃問(wèn)題（integer linearprogramming，ILP）。啟發(fā)式算法常用于解決整數(shù)規(guī)劃問(wèn)題，是由于該類(lèi)算法一般不依賴(lài)于一些特定的數(shù)學(xué)結(jié)構(gòu)并且有較好的魯棒性和易于實(shí)現(xiàn)，基于此優(yōu)點(diǎn)，可選擇啟發(fā)式算法來(lái)解決本問(wèn)題。大量的實(shí)驗(yàn)表明，粒子群算法比其它啟發(fā)式算法的計(jì)算時(shí)間快，但是其針對(duì)大規(guī)模優(yōu)化問(wèn)題的最終解往往偏差較大。本節(jié)提出了私有云效益最大化算法，該算法當(dāng)中使用改進(jìn)的模擬退火粒子群算法來(lái)進(jìn)行迭代優(yōu)化。其具體算法如算法I所示。

對(duì)于ISAPSO算法，在粒子初始化時(shí)，算法依據(jù)到達(dá)任務(wù)的總需求資源和私有云剩余資源的比值K進(jìn)行初始化。在對(duì)粒子的速度進(jìn)行更新時(shí)，使用模擬退火的規(guī)律與后期局部搜索的方式對(duì)粒子的速度進(jìn)行更新。在對(duì)粒子的位置進(jìn)行更新時(shí)，使用離散粒子群的位置更新方式對(duì)粒子進(jìn)行更新。即對(duì)粒子的位置進(jìn)行整數(shù)化。

4 結(jié)論

本文研究了混合云環(huán)境下的異構(gòu)任務(wù)調(diào)度研究，以最大化系統(tǒng)收益為基礎(chǔ)，在考慮異構(gòu)云特征及任務(wù)響應(yīng)時(shí)間約束的基礎(chǔ)上，提出了一種基于粒子群優(yōu)化的效益最大化算法，改算法在保證完成任務(wù)響應(yīng)的基礎(chǔ)上，可以實(shí)現(xiàn)較優(yōu)的系統(tǒng)效益。

參考文獻(xiàn)

[1]李智勇，陳少森，楊波，李仁發(fā).異構(gòu)云環(huán)境多目標(biāo)Memetic優(yōu)化任務(wù)調(diào)度方法[J].計(jì)算機(jī)學(xué)報(bào)，2016，39（02）：377-390.

[2]Q.Zhang，M.Zhani，R.Boutaba，and J.Hellerstein，“Dynamic heterogeneity-aware resource provisioning in thecloud，”IEEE Trans.Cloud Comput.，Vol.2，no.1，pp.14-28，Jan.2014.

[3]L.F.Bittencourt and E.R.M.Madeira，“HCOC：A cost optimizationalgorithm for workflow scheduling inhybrid clouds，”Journal of InternetServices and Applications，Springer，Vol.2，issue 3，pp.207-227，December 2011.