云計算平臺中非定期任務并行調度仿真

趙男男

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

1 引言

云計算是由分布式計算發展而來的新型計算模型與服務，運用模擬技術來完成擴展儲存和計算資源，目前已廣泛應用于醫藥醫療、工業制造、金融與能源等眾多領域。伴隨信息系統的復雜化，需要對云計算平臺結構進行調整，做到低成本、高性能[1]。客戶需求的不斷改變和物理節點性能的不同會導致云計算負載不平衡，直接影響到云計算平臺任務的處理效率、資源的利用率與資源消耗等問題[2]。相關專家學者針對云計算平臺集群負載、資源的利用率、集合性能、任務時間與耗損等進行多方面探究，應用各類調度優化算法實現任務調度[3]。

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

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

2 云計算平臺環境

圖1為云計算平臺環境系統模型圖，分析圖1可知，該系統模型中包含2點：分別為控制節點和計算節點。任務調度機器、數據調度器和信息中心3部分構成網絡控制節點。監控系統作為一個關鍵環節，其通過任務調度器、數據調度器和計算網絡節點來收集任務信息、儲存空間和處理器等消息，反映給任務與數據調度器，調整數據安放與任務調度，達到策略調整的目的[6]。任務與數據調度器依據收集到的信息，參考相應的的策略，將非定期任務和相關數據分配到計算節點上[7]。處理器和存儲空間共同組成計算節點，計算機節點主要負責對數據進行存儲，對非定期任務進行執行，并且將存儲空間和非定期任務執行的信息及時反饋到信息中心。

圖1 云計算系統模型

(1)

對于?i，j1，2…，|DN|，且i≠j，B中元素bi，j是節點dni和dnj之間的網絡帶寬值，其中bi，j=bj，i，?i，j=1，2，…，|DN|且i≠j都成立，即帶寬雙向相等，并忽略它的實時波動。

通過上述過程完成云計算平臺系統模型的建立，在云計算環境下應用平臺運行環境，結合模擬退火算法和粒子群算法實現非定期任務并行調度。

3 云計算平臺中非定期任務并行調度方法

3.1 非定期任務并行調度多約束條件建模

在構造多約束的云計算平臺非定期任務調度策略之前，對非定期任務調度多目標約束條件進行建模。

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

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

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

(2)

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

(3)

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

(4)

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

(5)

其中：cmin表示期望的非定期任務ti調度開銷，cij描述非定期任務ti在計算節點CNj上進行調度的調度開銷。

通過上述過程對非定期任務調度終止時間底線和調度開銷兩個目標約束條件的分析可知，為了盡可能降低調度開銷和最大程度上以最小終止底線完成非定期任務并行調度，需使上述兩項目標的隸屬度函數為最小[9]。基于此，采用上述兩項隸屬度函數將關于非定期任務并行調度的多目標約束優化問題變成單目標優化問題，如下式所示

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

(6)

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

3.2 非定期任務并行調度目標約束條件求解

3.1節給出的非定期任務并行調度目標求解問題實質為組合優化問題，為求取組合優化問題的最優解，采用模擬退火算法進行并行調度策略的選擇。模糊退火算法通常是從較高的溫度值開始，通過逐漸降低溫度并結合相關概率的突變特性在全局解空間中隨機搜索滿足目標函數最優解[10]。

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

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

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

3)形成新解S′。

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

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

5)如能滿足算法截止條件，則輸出當前階段的最優解，結束算法迭代過程[11]。

6)T漸漸縮小，T→0，轉為步驟2)。

經模擬退火算法推算出滿足云計算平臺用戶服務時間和服務可靠性需求的最佳任務調度方式[12]。

4 實驗結果及分析

為了有效驗證基于模擬退火算法的非定期任務并行調度方法的綜合有效性，在CloudSim模擬平臺上完成仿真平臺的構建。在上述仿真平臺下進行實驗，實驗運行20次后選取平均值，作為最終測試結果。實驗過程中選取基于可靠性約束的非定期任務并行調度方法、基于粒子群優化的非定期任務調度方法作為對比方法。

4.1 非定期任務量對數據傳輸的影響

圖2 任務集數量對數據傳輸的影響

圖2表示非定期任務集數量的增加對數據傳輸的影響。實驗過程中，設定數據集數量最多為600，最少為100。為了簡化描述，將本文提出的基于模擬退火算法的非定期任務并行調度方法、基于可靠性約束的非定期任務并行調度方法、基于粒子群優化的非定期任務調度方法分別表示為BUT、BD、BB。

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

圖3表示當非定期任務數量逐漸增加時，系統負載均衡變化情況。在實驗過程中，設定工作節點數最低為10個，最高為60個。

圖3 節點的數量

經過實驗對比：隨著節點數量的不斷增加，本文方法、基于可靠性約束的非定期任務并行調度方法、基于粒子群優化的非定期任務調度方法負載均衡偏差呈線性增長。同時，基于粒子群優化的非定期任務調度方法的偏差最大，基于可靠性約束的非定期任務并行調度方法的偏差值稍少于基于粒子群優化的非定期任務調度方法，本文方法對應的偏差值最少；當節點數量為50～60時，本文方法的負載均衡偏差值為基于可靠性約束的非定期任務并行調度方法的1/4，說明本文方法的負載均衡性更強。

5 結論

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

在未來的工作中，研究重點是，在不影響非定期任務傳輸時間的前提下，考慮算法的并行化實現，進一步提高算法的實際應用性能。