云計(jì)算平臺中非定期任務(wù)并行調(diào)度仿真

趙男男

(廣東海洋大學(xué)寸金學(xué)院，廣東 湛江 524094)

1 引言

云計(jì)算是由分布式計(jì)算發(fā)展而來的新型計(jì)算模型與服務(wù)，運(yùn)用模擬技術(shù)來完成擴(kuò)展儲(chǔ)存和計(jì)算資源，目前已廣泛應(yīng)用于醫(yī)藥醫(yī)療、工業(yè)制造、金融與能源等眾多領(lǐng)域。伴隨信息系統(tǒng)的復(fù)雜化，需要對云計(jì)算平臺結(jié)構(gòu)進(jìn)行調(diào)整，做到低成本、高性能[1]?？蛻粜枨蟮牟粩喔淖兒臀锢砉?jié)點(diǎn)性能的不同會(huì)導(dǎo)致云計(jì)算負(fù)載不平衡，直接影響到云計(jì)算平臺任務(wù)的處理效率、資源的利用率與資源消耗等問題[2]。相關(guān)專家學(xué)者針對云計(jì)算平臺集群負(fù)載、資源的利用率、集合性能、任務(wù)時(shí)間與耗損等進(jìn)行多方面探究，應(yīng)用各類調(diào)度優(yōu)化算法實(shí)現(xiàn)任務(wù)調(diào)度[3]。

文獻(xiàn)[4]提出基于可靠性約束的非定期任務(wù)并行調(diào)度方法。該方法將云計(jì)算平臺可靠性目標(biāo)換做單個(gè)非定期任務(wù)的可靠性目標(biāo)，給出非定期任務(wù)可靠性目標(biāo)計(jì)算過程；針對此過程設(shè)計(jì)一種并行調(diào)度方法。文獻(xiàn)[5]提出基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法。該方法首先建立云計(jì)算平臺中非定期任務(wù)調(diào)度能耗模型，針對該模型定義非定期任務(wù)調(diào)度多目標(biāo)優(yōu)化問題；采用粒子群算法對多目標(biāo)優(yōu)化問題進(jìn)行求解，獲取不同調(diào)度方案下的最優(yōu)解集合，在不同調(diào)度策略對應(yīng)的調(diào)度最優(yōu)解集合中尋找最優(yōu)解。

采用上述方法進(jìn)行非定期任務(wù)并行調(diào)度過程中，無法避免由非定期任務(wù)調(diào)度的不確定性所帶來的耗時(shí)長和高能耗等問題，對此，將模擬退火算法和粒子群算法相結(jié)合提出一種非定期任務(wù)調(diào)度方法。

2 云計(jì)算平臺環(huán)境

圖1為云計(jì)算平臺環(huán)境系統(tǒng)模型圖，分析圖1可知，該系統(tǒng)模型中包含2點(diǎn)：分別為控制節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)。任務(wù)調(diào)度機(jī)器、數(shù)據(jù)調(diào)度器和信息中心3部分構(gòu)成網(wǎng)絡(luò)控制節(jié)點(diǎn)。監(jiān)控系統(tǒng)作為一個(gè)關(guān)鍵環(huán)節(jié)，其通過任務(wù)調(diào)度器、數(shù)據(jù)調(diào)度器和計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)來收集任務(wù)信息、儲(chǔ)存空間和處理器等消息，反映給任務(wù)與數(shù)據(jù)調(diào)度器，調(diào)整數(shù)據(jù)安放與任務(wù)調(diào)度，達(dá)到策略調(diào)整的目的[6]。任務(wù)與數(shù)據(jù)調(diào)度器依據(jù)收集到的信息，參考相應(yīng)的的策略，將非定期任務(wù)和相關(guān)數(shù)據(jù)分配到計(jì)算節(jié)點(diǎn)上[7]。處理器和存儲(chǔ)空間共同組成計(jì)算節(jié)點(diǎn)，計(jì)算機(jī)節(jié)點(diǎn)主要負(fù)責(zé)對數(shù)據(jù)進(jìn)行存儲(chǔ)，對非定期任務(wù)進(jìn)行執(zhí)行，并且將存儲(chǔ)空間和非定期任務(wù)執(zhí)行的信息及時(shí)反饋到信息中心。

圖1 云計(jì)算系統(tǒng)模型

(1)

對于?i，j1，2…，|DN|，且i≠j，B中元素bi，j是節(jié)點(diǎn)dni和dnj之間的網(wǎng)絡(luò)帶寬值，其中bi，j=bj，i，?i，j=1，2，…，|DN|且i≠j都成立，即帶寬雙向相等，并忽略它的實(shí)時(shí)波動(dòng)。

通過上述過程完成云計(jì)算平臺系統(tǒng)模型的建立，在云計(jì)算環(huán)境下應(yīng)用平臺運(yùn)行環(huán)境，結(jié)合模擬退火算法和粒子群算法實(shí)現(xiàn)非定期任務(wù)并行調(diào)度。

3 云計(jì)算平臺中非定期任務(wù)并行調(diào)度方法

3.1 非定期任務(wù)并行調(diào)度多約束條件建模

在構(gòu)造多約束的云計(jì)算平臺非定期任務(wù)調(diào)度策略之前，對非定期任務(wù)調(diào)度多目標(biāo)約束條件進(jìn)行建模。

假設(shè)，云計(jì)算平臺環(huán)境中包含N個(gè)計(jì)算節(jié)點(diǎn)，用集合CN={CN1，…，CN1}來表示。未調(diào)度的任務(wù)集為t={t1，…，tr}，其中L為任務(wù)數(shù)量。S(CNi，Rk)為計(jì)算節(jié)點(diǎn)CNi可提供的能用資源Rk的計(jì)算能力；R(ti，Rk)表示調(diào)度非定期任務(wù)ti時(shí)所損耗的計(jì)算能力；將大小為T×N的資源的分布矩陣M以運(yùn)行資源和其相應(yīng)的計(jì)算節(jié)點(diǎn)之間的任務(wù)映射的關(guān)系來描述。

假設(shè)，非定期任務(wù)ti被劃分到服務(wù)節(jié)點(diǎn)CNj上執(zhí)行調(diào)度，則矩陣M中的元素Mij=1，否則Mij=0；vij與cij分別表示任務(wù)ti被轉(zhuǎn)移到計(jì)算節(jié)點(diǎn)CNj實(shí)行調(diào)度的狀況下，平臺非定期任務(wù)的實(shí)際執(zhí)行時(shí)間和調(diào)度開銷超過截止時(shí)間底線與調(diào)度開銷目標(biāo)約束條件的概率；Min(Odeadline)與Min(Obudget)為指派非定期任務(wù)調(diào)度預(yù)算與任務(wù)調(diào)度的終止時(shí)間的狀況下，在云計(jì)算平臺中要實(shí)現(xiàn)的非定期任務(wù)調(diào)度目標(biāo)。

客戶期盼能在期望的時(shí)間線之前搞定所有的調(diào)度任務(wù)請求。因此，應(yīng)盡可能將調(diào)度任務(wù)實(shí)施運(yùn)行時(shí)間超越其結(jié)束時(shí)間底線約束條件的比例；同時(shí)在計(jì)算節(jié)點(diǎn)上指定資源Rk，全部任務(wù)在Rk上所消耗的計(jì)算能力累加和不能超過該資源能供給的總計(jì)算能力。上述過程所描述的任務(wù)調(diào)度截止時(shí)間底線的目標(biāo)約束條件，用式(2)來表示。

(2)

服務(wù)需求得到滿足后，云計(jì)算平臺用戶希望盡可能降低調(diào)度成本。同時(shí)，指定的非定期任務(wù)ti在其對應(yīng)計(jì)算節(jié)點(diǎn)全部可用資源上消耗的總調(diào)度成本不能高于其事先制定的調(diào)度預(yù)算。以上關(guān)于非定期任務(wù)并行調(diào)度預(yù)算的目標(biāo)約束條件，利用式(3)來表示

(3)

從客戶的角度分析，他們期望任務(wù)調(diào)度運(yùn)行時(shí)間能夠縮短。一方面，非定期任務(wù)調(diào)度的開銷與任務(wù)調(diào)度的截止時(shí)間有一定的關(guān)聯(lián)性，截止時(shí)間越長、用戶調(diào)度開銷越大。因此，在非定期任務(wù)并行調(diào)度預(yù)算固定的前提下，云計(jì)算平臺用戶期望非定期任務(wù)調(diào)度截止時(shí)間底線盡可能達(dá)到最小[8]。在非定期任務(wù)調(diào)度估算固定時(shí)，可以采用關(guān)于終止時(shí)間的隸屬度函數(shù)描述項(xiàng)式(4)來表達(dá)非定期任務(wù)的終止時(shí)間約束條件與調(diào)度目標(biāo)之間的隸屬關(guān)系。

(4)

另一方面，客戶們期望任務(wù)調(diào)度開銷越少越好。采用與相關(guān)任務(wù)的調(diào)度開銷隸屬度函數(shù)即式(5)來描述任務(wù)調(diào)度估算約束條件與調(diào)度目標(biāo)的隸屬關(guān)系。

(5)

其中：cmin表示期望的非定期任務(wù)ti調(diào)度開銷，cij描述非定期任務(wù)ti在計(jì)算節(jié)點(diǎn)CNj上進(jìn)行調(diào)度的調(diào)度開銷。

通過上述過程對非定期任務(wù)調(diào)度終止時(shí)間底線和調(diào)度開銷兩個(gè)目標(biāo)約束條件的分析可知，為了盡可能降低調(diào)度開銷和最大程度上以最小終止底線完成非定期任務(wù)并行調(diào)度，需使上述兩項(xiàng)目標(biāo)的隸屬度函數(shù)為最小[9]?；诖耍捎蒙鲜鰞身?xiàng)隸屬度函數(shù)將關(guān)于非定期任務(wù)并行調(diào)度的多目標(biāo)約束優(yōu)化問題變成單目標(biāo)優(yōu)化問題，如下式所示

Min(0)=ω1Min(Odeadline)+ω2Min(Obudget)=

(6)

其中：權(quán)重系數(shù)ω1+ω2=1，ωi≥0。在建立非定期任務(wù)調(diào)度求解目標(biāo)函數(shù)過程中，由于不同云計(jì)算平臺用戶對于任務(wù)終止時(shí)間底線和調(diào)度開銷的需求度不同，可根據(jù)參數(shù)ω1和ω2的調(diào)整來滿足不同云計(jì)算平臺用戶對非定期任務(wù)調(diào)度目標(biāo)約束需求。

3.2 非定期任務(wù)并行調(diào)度目標(biāo)約束條件求解

3.1節(jié)給出的非定期任務(wù)并行調(diào)度目標(biāo)求解問題實(shí)質(zhì)為組合優(yōu)化問題，為求取組合優(yōu)化問題的最優(yōu)解，采用模擬退火算法進(jìn)行并行調(diào)度策略的選擇。模糊退火算法通常是從較高的溫度值開始，通過逐漸降低溫度并結(jié)合相關(guān)概率的突變特性在全局解空間中隨機(jī)搜索滿足目標(biāo)函數(shù)最優(yōu)解[10]。

模擬退火算法可劃分為三部分，包括目標(biāo)函數(shù)、目標(biāo)函數(shù)初始解和目標(biāo)函數(shù)解空間。模擬退火算法求解過程如下：

1)最初化：設(shè)定最初溫度為T(足夠大)，最初解狀態(tài)為S，設(shè)定T值的迭代次數(shù)為L。

2)對k=1，…，L運(yùn)行過程3)～6)。

3)形成新解S′。

估計(jì)增長量Δt′=C(S′)-C(S)，C(S)中的C(S)為評估函數(shù)。

4)如果滿足Δt′<0，則接收S′作為最新的當(dāng)前階段的最優(yōu)解，否則以概率exp(-Δt′/T)接收S′作為最新的當(dāng)前階段的最優(yōu)解。

5)如能滿足算法截止條件，則輸出當(dāng)前階段的最優(yōu)解，結(jié)束算法迭代過程[11]。

6)T漸漸縮小，T→0，轉(zhuǎn)為步驟2)。

經(jīng)模擬退火算法推算出滿足云計(jì)算平臺用戶服務(wù)時(shí)間和服務(wù)可靠性需求的最佳任務(wù)調(diào)度方式[12]。

4 實(shí)驗(yàn)結(jié)果及分析

為了有效驗(yàn)證基于模擬退火算法的非定期任務(wù)并行調(diào)度方法的綜合有效性，在CloudSim模擬平臺上完成仿真平臺的構(gòu)建。在上述仿真平臺下進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)運(yùn)行20次后選取平均值，作為最終測試結(jié)果。實(shí)驗(yàn)過程中選取基于可靠性約束的非定期任務(wù)并行調(diào)度方法、基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法作為對比方法。

4.1 非定期任務(wù)量對數(shù)據(jù)傳輸?shù)挠绊?/h3>

圖2 任務(wù)集數(shù)量對數(shù)據(jù)傳輸?shù)挠绊?/p>

圖2表示非定期任務(wù)集數(shù)量的增加對數(shù)據(jù)傳輸?shù)挠绊?。?shí)驗(yàn)過程中，設(shè)定數(shù)據(jù)集數(shù)量最多為600，最少為100。為了簡化描述，將本文提出的基于模擬退火算法的非定期任務(wù)并行調(diào)度方法、基于可靠性約束的非定期任務(wù)并行調(diào)度方法、基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法分別表示為BUT、BD、BB。

分析圖2可知：隨著非定期任務(wù)集數(shù)量的增加，基于模擬退火算法的非定期任務(wù)并行調(diào)度方法、基于可靠性約束的非定期任務(wù)并行調(diào)度方法、基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法傳輸次數(shù)、傳輸數(shù)量和傳輸時(shí)間呈線性趨勢增長。這三種方法的傳輸次數(shù)與傳輸量相差不多，基于可靠性約束的非定期任務(wù)并行調(diào)度方法、基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法之間相差較?。粓D2(a)中基于可靠性約束的非定期任務(wù)并行調(diào)度方法傳輸次數(shù)為最少，圖2(b)中基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法的傳輸量最小，基于模擬退火算法的非定期任務(wù)并行調(diào)度方法的傳輸數(shù)量與次數(shù)與其它兩種方法相比，傳輸次數(shù)及傳輸量均是最多的。圖2(c)中，本文方法的傳輸時(shí)間為最少，基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法的傳輸時(shí)間較多，基于可靠性約束的非定期任務(wù)并行調(diào)度方法稍少于基于可靠性約束的非定期任務(wù)并行調(diào)度方法，本文方法的時(shí)間延長率比其它兩種方法都小，在非定期任務(wù)集數(shù)量是600時(shí)，本文方法的傳輸時(shí)間比基于可靠性約束的非定期任務(wù)并行調(diào)度方法少約1/3，并且從變化趨勢上來看，這種差距隨著非定期任務(wù)數(shù)據(jù)集的增加而逐漸增大，說明本文方法能夠有效降低非定期任務(wù)的傳輸時(shí)間，提高非定期任務(wù)的傳輸效率。

圖3表示當(dāng)非定期任務(wù)數(shù)量逐漸增加時(shí)，系統(tǒng)負(fù)載均衡變化情況。在實(shí)驗(yàn)過程中，設(shè)定工作節(jié)點(diǎn)數(shù)最低為10個(gè)，最高為60個(gè)。

圖3 節(jié)點(diǎn)的數(shù)量

經(jīng)過實(shí)驗(yàn)對比：隨著節(jié)點(diǎn)數(shù)量的不斷增加，本文方法、基于可靠性約束的非定期任務(wù)并行調(diào)度方法、基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法負(fù)載均衡偏差呈線性增長。同時(shí)，基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法的偏差最大，基于可靠性約束的非定期任務(wù)并行調(diào)度方法的偏差值稍少于基于粒子群優(yōu)化的非定期任務(wù)調(diào)度方法，本文方法對應(yīng)的偏差值最少；當(dāng)節(jié)點(diǎn)數(shù)量為50～60時(shí)，本文方法的負(fù)載均衡偏差值為基于可靠性約束的非定期任務(wù)并行調(diào)度方法的1/4，說明本文方法的負(fù)載均衡性更強(qiáng)。

5 結(jié)論

本文指出了由于云計(jì)算平臺的動(dòng)態(tài)不確定性和非定期任務(wù)調(diào)度本身的復(fù)雜性，使得非定期任務(wù)調(diào)度過程存在耗時(shí)長和高能耗等問題。分析影響非定期任務(wù)傳輸時(shí)間的影響因素，提出基于模擬退火算法的非定期任務(wù)并行調(diào)度方法。根據(jù)仿真結(jié)果可知，與傳統(tǒng)方法對比，在排除任務(wù)集與節(jié)點(diǎn)較少的情況下，本文方法能夠有效降低非定期任務(wù)的傳輸時(shí)間，對系統(tǒng)負(fù)載進(jìn)行有效均衡，從而提高了云計(jì)算平臺的工作效率。

在未來的工作中，研究重點(diǎn)是，在不影響非定期任務(wù)傳輸時(shí)間的前提下，考慮算法的并行化實(shí)現(xiàn)，進(jìn)一步提高算法的實(shí)際應(yīng)用性能。