面向虛擬化云數據中心的工作流聯合調度算法研究

董明剛，范 培，閉玉申，敬 超，3

1(桂林理工大學 信息科學與工程學院，廣西 桂林 541004)2(嵌入式技術與智能系統重點實驗室，廣西 桂林 541004)3(可信軟件重點實驗室，廣西 桂林 541004)

E-mail：jingchao@glut.edu.cn

1 引 言

虛擬化技術是云數據中心的核心技術之一，良好的資源及調度方法有利于云數據中心的虛擬資源管理從而提供快速、安全和可靠的服務.隨著云計算技術的不斷成熟和進步，基于該技術的數據中心也隨之發展，其中虛擬化技術是數據中心的關鍵技術之一，它能夠對現有的資源進行整合，提高服務器與存儲的利用率，讓用戶對新硬件設備的增長需求速度放緩，進而提高資源的利用率[1-3].由此可見，設計合理的方法對虛擬化資源進行管理有著重要的意義.

傳統的虛擬化資源管理主要是針對虛擬機部署的性能優化問題[4]，它主要包括將工作流分配到虛擬機，優化虛擬機部署后工作流的時延問題[5].還有的研究只是關注了數據中心的資源利用率和高能耗問題，如劉寧等人[6]提出了一種新穎的分層框架，通過強化學習進行虛擬機資源分配和有效的動態電源管理策略解決資源調度過程中高功耗的問題，但是這種方法忽略了數據中心費用優化問題.

針對這一問題，Tong等人[7]提出一種基于強化學習的云工作流調度算法，用Q-learning算法對任務進行預處理，獲得更加合理的任務序列，對任務進行分配時，使用線性加權法有效的將工作流分配給合適的虛擬機，完成了優化工作流的完成時間和用戶的費用，達到了同時優化多目標的問題.Cheng等人[8]提出一種降低資源成本的算法，主要通過深度強化學習算法，從不斷變化的環境中學習進而自動生成一個長期決策，使得在保持能源效益的同時運行時間極大的縮短，節省開銷.范利利等人[9]為了提高異構云計算系統的處理效率，減少費用開銷，在考慮了云環境的異構性、任務的截止時間、傳輸開銷的情況下，提出一種基于自學習策略和近鄰啟發機制的粒子群任務調度算法，能夠有效縮短工作流執行時間，減少開銷.

縱觀這些研究可以發現目前虛擬機部署問題，主要關注的是以優化費用為目的[10，11]，解決工作流到虛擬機的映射問題，而沒有考慮映射完成后虛擬機到物理機的調度問題，即工作流聯合調度問題.這是因為相比于傳統的虛擬機部署問題，聯合調度問題更加復雜，因為它涉及到了工作流，虛擬機以及物理機三者的資源協調問題.雖然Guo等人[12]做了聯合調度的研究，但是他們主要是利用影子算法指導實際的應用程序到虛擬機到物理機上的分配，提出了在云上的應用程序-虛擬機-物理機在線聯合調度算法，并沒有進一步考慮到資源調度過程中產生的費用開銷優化問題.

鑒于聯合調度過程中涉及的資源協調以及成本開銷優化等問題，因此，本文的主要工作是以費用最小化為目的，在保證工作流執行效率的前提下，提出了一種以蟻群系統和貪心算法為核心思想的聯合調度方法(A joint workflow scheduling algorithm based on improved Ant-colony system and greed algorithm，IAG).與以往的研究相比，該方法不僅考慮了在虛擬化云數據中心的工作流-虛擬機-物理機的聯合調度問題，而且還考慮了虛擬機多類型的問題，即同類型虛擬機在部署到同一臺物理機時可以免去部署開銷(如時間)[13].

本文的工作主要是：首先，通過建立工作流、虛擬機、物理機以及云數據中心的費用模型，對虛擬化云數據中心工作流聯合調度問題進行了形式化的描述；接著，針對提出的優化問題，提出了一種二階段的工作流聯合調度算法(IAG).該算法主要分為兩步：

1)解決了工作流到虛擬機的映射問題，以縮短工作流執行時間最小化為目的，提出了一種基于蟻群系統思想的算法；

2)利用貪心算法，考慮虛擬機的多類型問題，在保證工作流完成時間的前提下，以費用支出最小化為目的，將虛擬機調度到物理機.

最后，將提出的IAG算法與傳統調度FCFS算法、PSO算法以及IPSO算法[14]進行對比實驗分析.實驗結果表明：IAG聯合調度算法不僅可以保證工作流的執行效率，還降低了費用開銷，體現了它的可行性及有效性.

2 問題建模

2.1 云數據中心調度模型

該模型展示了云數據中心在處理用戶提交的工作流時所經歷的過程.首先用戶在線提交工作流到云數據中心，所有的工作流都會被緩存到工作流隊列中，通過調度器將工作流調度到數據中心生成的虛擬機中處理，并且隨后虛擬機會被以開銷最小化為目的部署到相應的物理服務器上，如圖1所示.

圖1 云數據中心處理工作流示意圖Fig.1 Schematic diagram of cloud data center processing workflow

2.2 工作流模型

對于每一種類型的工作流，都有截止時間Dk，將工作流的模型描述為一個有向無環圖G=(ν，ε)，工作流中的任務集用ν={υ0，υ1，…，υ|Q(k)|-1}表示，表示|Q(k)|工作流K中的總任務數量.其中K∈[0，H(t)-1]，H(t)表示工作流的總數量.ε表示任務之間的依賴關系，由于任務Tp和它的子任務Tq的依賴關系，定義為W(Tp，Tq).任務Tq只有在執行完任務Tp后才能進行.Tlength_i表示任務υi的數據量大小.工作流模型如圖2所示.

圖2 工作流模型Fig.2 Workflow model

2.3 云數據中心虛擬機模型

假設云數據中心里虛擬機的數量為N，用V={V1，V2，…，VN}表示.每個虛擬機資源需求為CPU、內存、帶寬，分別用Vcj，Vmj，Vbwj，j∈N表示.每個虛擬機在部署到物理機時會產生的開銷表示為PmC，若虛擬機由NT種類型組成，則兩個同類型的虛擬機部署到同一物理機時，在資源充足的情況下可以避免部署的開銷.虛擬機的處理能力如公式(1)所示：

VMcomp_j=mips×pes

(1)

任務的傳輸時間暫且不考慮在內，任務在虛擬機上的執行時間如公式(2)所示：

(2)

每個任務在虛擬機上的執行時間就是它的完成時間：

TRTimeij=etij

每個工作流的完成時間：

(3)

虛擬機上前r個工作流執行時間：

(4)

由于虛擬機并行執行的工作特性，工作流最終完成時間是最后一臺虛擬機執行完工作流的時間，如公式(5)所示：

WFFTime=max(vmcomptime_j)，j∈[1，n]

(5)

2.4 云數據中心物理機模型

假設云數據中心中物理機的數量為M表示為P={1，2，3…M}，每個物理機的資源需求為CPU、內存、帶寬，分別用Pci，Pmi，Pbwi，i∈P表示，其中物理機中的資源要滿足虛擬機中資源的需求.調度策略中的物理機資源需要滿足條件如下：其中X表示鄰接矩陣，若VMj放置在物理機Pi上，則Xij等于1，否則Xij等于0.

(6)

其中yi表示物理機數量.

(6a)

(6b)

(6c)

(6d)

2.5 云數據中心成本開銷模型

2.5.1 時間約束

時間約束分為兩部分:第1部分為工作流的執行時間，第2部分為物理機的部署資源時間.其中物理機部署資源的啟動、結束時間分別為Tstart、Toff.每個虛擬機部署資源的時間集合為：PT={T1，T2，T3…}.

其中工作流執行時間約束函數如公式(7)所示：

(7)

WFFTimemax、WFFTimemin分別表示任務在處理能力最差、最好的虛擬機上的執行時間.即Time_1=T_Time(I).物理機上部署資源時間如公式(8)所示：

Time_2=Tstart+T1+T2+…+Toff

(8)

物理機部署資源時，利用貪心算法先對需求資源大的虛擬機進行資源部署，當后續到達虛擬機與前一個虛擬機類型相同且所需資源小于前一個虛擬機時，則不需要重新為其部署資源，節省了部署虛擬機的開銷，同時能夠盡可能將資源類型相同的虛擬機優先部署到同一臺物理機上.其中物理機啟動時間如公式(9)所示：

Tstart(i)=lnPmi

(9)

將Toff設置為啟動時間的一半.聯合調度的總時間如公式(10)所示：

f(t)=Time_1+Time_2

(10)

2.5.2 成本開銷問題

不同類型的虛擬機所需的單位費用與它的CPU、內存、帶寬資源相關，記為Vcostj.當所有工作流執行完成后，虛擬機所需費用如公式(11)所示：

(11)

物理機的單位費用同樣與其CPU、內存、帶寬資源相關，記為Pcosti，物理機的所需的費用開銷如公式(12)所示：

(12)

其中Tstart>0，Toff>0，聯合調度的總費用表示為：

F(c)=TC+PmC

(13)

2.6 問題定義

本文主要工作是以費用最小化為目的，在保證工作流執行效率的前提下，將虛擬機在物理機上進行資源部署，從而達到了對資源的整體聯合調度.優化目標如公式(14)所示：

minsizeF(c)=TC+PmC

(14)

s.t.f(t)≤T

(14a)

3 算法設計

3.1 算法基本思想

一方面，針對工作流-虛擬機的映射問題，在基于蟻群系統的基本思想上，對工作流執行時間和開銷成本建立相關函數，縮短了工作流調度時的任務完成時間.另一方面，針對虛擬機-物理機的部署問題，利用貪心算法將多類型的虛擬機部署到物理機上，若同類型的虛擬機部署到同一個物理機上時可以免去部署開銷.通過對這兩層的資源調度進行優化，即節省了時間，又縮減了整體的費用開銷.

3.2 算法設計細節

3.2.1 初始化相關參數

對蟻群系統中的啟發函數、信息素、和信息素轉移規則進行初始化.

(15)

τ0表示任務到虛擬機路徑上信息素的初始化值.其中VMavg_comp表示虛擬機的平均計算能力，如公式(16)所示：

(16)

(17)

ηij是啟發函數，表示任務υi在虛擬機VMj上的執行期望強度.其中，LFj是虛擬機負載函數[15]，如公式(18)所示：

LFj=1-((Ej-Eavg)/∑j∈VMEj)

(18)

etij表示任務υi在虛擬機VMj上的執行時間.Ej是虛擬機j的執行時間，Eavg是所有虛擬機的執行時間的平均時間.若先不考慮信息素調整因子，任務的執行時間越長，則ηij越大.

3.2.2 虛擬機節點選擇

螞蟻在選擇下一個虛擬機節點時，采用了蟻群系統的隨機轉移概率規則[16]；

(19)

(20)

其中q為[0，1]之間的隨機數，q0為固定參數，α為信息素的啟發因子，β為期望啟發因子，allowedk是螞蟻可以為任務選擇的虛擬機集合.τij(t)表示t時刻時，任務υi與虛擬機VMj的映射路徑上的信息素的值.

3.2.3 動態信息素更新

當螞蟻為所有任務進行分配后，對其映射路徑上的局部信息素進行更新：

a)局部信息素更新規則

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(21)

公式(21)中ρ表示信息素揮發因子，(1-ρ)表示信息素的殘留度，ρ的值范圍是(0，1]，若ρ越大，則表示信息素揮發的越快，殘留度越小.Δτij(t)是在t時刻時，任務υi與虛擬機VMj的映射路徑上的信息素增量.

(22)

其中D為螞蟻完成一輪尋解后的時間與成本函數值，表達式為D=ι1Time_1+ι2TC，ι1、ι2分別為時間函數和成本函數的權重因子，取值范圍是[0，1].Uk(t)表示第k只螞蟻在第t次的迭代尋解.

b)全局信息素更新規則

當所有螞蟻完成一輪迭代尋解后，得到本次迭代尋解的最佳方案，然后將局部最佳的信息素設置為全局信息素.

(23)

其中Dbest為螞蟻到目前迭代尋解中的最優解.

3.2.4 算法及時間復雜度分析

在算法1中，首先初始化所需的各項參數(行1-3)，為任務匹配最佳的虛擬機并更新局部信息素(行4-10)，更新全局信息素，并獲得最佳匹配方案(行11-17).

在算法2中，首先將所需資源最大的虛擬機優先部署到物理機上(行1-3)，將后續到達的虛擬機與前一個虛擬機進行類型與資源比較，并為其部署資源(行4-12).

算法1.

輸入：工作流中的任務總數TASK_NUM，虛擬機數量，物理機數量，螞蟻數量ANT_NUM，迭代次數I_NUM，揮發因子，啟發因子α，啟發因子β，偽隨機狀態轉移參數q0.

輸出：工作流與虛擬機匹配方案

1.Begin

2. 初始化虛擬機計算能力，虛擬機計算費用，期望執行時間，全局

3. 信息素，螞蟻列表，全局匹配方案.

4. ForD=1 toI_NUM

5. ForN=1 toANT_NUM

6. ForT=1 toTASK_NUM

7. 螞蟻根據偽隨機狀態轉移公式，選擇最合適的虛擬機.

8.

9. End

10. 更新局部信息素.

11. End

12. 計算并選擇最佳的螞蟻.

13. 用最佳螞蟻的局部信息素，來更新全局信息素.

14. 選擇最佳螞蟻的匹配方案，來更新全局匹配方案.

15. 初始化螞蟻列表.

16. End

17.End

輸出結果：工作流與虛擬機匹配方案

算法2.

輸入：虛擬機數量VM_NUM，虛擬機類型Type，虛擬機內存RAM，物理機現存資源數據

輸出：虛擬機與物理機部署方案

1.Begin

2. Fori=1 toVM_NUM

3. 找出現有資源最大的物理機.

4. 獲取物理機上最新部署的虛擬機VM_i的類型Type_i，所

5. 需內存大小RAM_i.

6. IfType_i+1不等于Type_i或RAM_i+1大于RAM_i

7. 在該物理機上重新為VM_i+1部署資源.

8. Else

9. 將VM_i+1直接放置到該物理機上.

10. End

11. End

12.End

輸出結果：虛擬機與物理機部署方案

假設工作流中的任務數量為T，虛擬機數量為S，且任務的數量T大于虛擬機資源的數量S(T>S)，迭代次數為R，螞蟻數量為N.本文提出的IAG算法的時間復雜度主要分為兩部分：1)利用改進的蟻群系統算法解決工作流到虛擬機上的映射問題，即算法1的時間復雜度為O(R·T·N).2)將貪心算法應用到虛擬機到物理機的部署問題上，即算法2的時間復雜度為O(S).

4 實驗模擬

4.1 實驗設置以及算法參數設置

本文在Cloudsim-3.0.3云計算仿真平臺進行仿真實驗，驗證提出算法的有效性.

表1 實驗參數配置Table 1 Experimental parameter configuration

測試中的參數配置如表1所示.本文采用CyberShake、Montage、LIGO、SIPHT等數據集上任務數量為100，200的2組任務進行實驗，迭代100次后得出最佳結果，并與FCFS算法、PSO算法、IPSO算法對比，為確保實驗結果的有效性，每種算法進行獨立實驗10次，取其平均值，對比結果如圖3所示.

圖3 不同任務大小下的實驗結果Fig.3 Experimental results under different task sizes

算法1中涉及到一些參數設置，具體如下：α=0.5，β=0.5，ρ=0.2，q0=0.2螞蟻數量ANT_NUM=20，最大迭代次數為I_NUM=100.

4.2 實驗結果分析

由圖3可以看出，在不同大小的任務下，IAG算法與IPSO算法、PSO算法、FCFS算法相比較，在聯合調度的資源開銷方面均有明顯的優勢.由圖3(a)、圖3(b)可以看出，當任務數量為100和200時，在數據集CyberShake、Montage、LIGO、SIPHT上，IAG算法在費用這一指標上明顯優于其他算法.其中當任務數量為100時，在LIGO這一數據集上，IAG算法的開銷為3116，而IPSO算法、PSO算法、FCFS算法的開銷分別是3125、3126、3125.當任務數量為200時，IAG算法表現更為顯著，IAG算法的開銷為5405，而IPSO算法、PSO算法、FCFS算法的開銷分別是5442，5443，5443.這是由于提出的IAG算法將蟻群系統進行改進，對工作流執行時間和開銷成本建立相關函數，同時采用蟻群算法加快對虛擬機的搜尋，將工作流中的任務匹配給更適合的虛擬機，從而提高任務的完成時間，另一方面，在將虛擬機部署到物理機上時，該算法針對同類型的虛擬機的部署可以免去部署開銷，節省部署時間.而IPSO算法、PSO算法相較于FCFS算法能夠在執行時間和費用開銷方面有明顯提升，但是，由于虛擬機在物理機上進行部署時，以上算法是針對同類型的虛擬機沒有免去部署時間，增加了部署時間與開銷，從而在實驗中顯示出劣勢.

圖4 不同數據集下的實驗結果Fig.4 Experimental results under different data sets

圖4為不同數據集下的任務在由6臺物理機，20臺類型數為8的虛擬機構成的小型數據中心的測試結果.同樣分別采用了CyberShake、Montage、LIGO、SIPHT數據集，任務量分別為100，200進行測試.將由圖4可以看出，在圖4(a)、圖4(b)、圖4(c)中，當任務數量為100、200時，在CyberShake、SIPHT、Montage數據集上，IAG算法的費用開銷在750左右浮動，而IPSO算法、PSO算法、FCFS算法在3個數據集上的費用在880左右浮動.同時在LIGO數據集上，IAG算法也明顯優于其他算法.因此，在構造的小型數據中心中，IAG算法在不同任務大小的數據集上表現優于IPSO算法、PSO算法、FCFS算法.

表2 任務為100的完成時間(s)Table 2 Completion time of task 100

各個算法在執行任務為100、200的時間如表2、表3所示，任務數量為100時，IAG算法在CyberShake、Montage、SIPHT上面時間上均優于其他算法，其中在CyberShake上，對比FCFS算法、PSO算法、IPSO算法分別提高了1.45%、1.38%、2.03%；在Montage上，分別提高了2.14%、2.01%、2.16%；在LIGO上，分別提高了1.14%、1.18%、1.58%；在SIPHT上，分別提高了2.26%、2.26%、2.28%.表3可以看出，

表3 任務為200的完成時間(s)Table 3 Completion time of task 200

當任務數量為200時，IAG算法較其他算法在任務完成時間上也有明顯提高.隨著任務數量的不斷增加，IAG算法的優勢更加明顯，這是因為任務數量的不斷增加，相對應的虛擬機、物理機數量也在不斷增多，而對于工作流到虛擬機上的映射問題，利用改進的蟻群系統能夠為工作流中的任務更加快速需找到合適的虛擬機，節省了時間；同時隨著虛擬機數量的增多，虛擬機到物理機上進行部署時，同類型的虛擬機的部署也會節省更多的時間和費用開銷.

5 結束語

本文提出一種基于蟻群系統和貪心思想的二階段工作流聯合調度算法(IAG)，該算法首先基于現有的蟻群系統算法，以最小化工作流完成時間為目的，設計了啟發式函數和信息激素更新規則，將工作流映射到虛擬機.然后，再以最小化費用開銷為目的，保證工作流完成的前提下，提出了一種基于貪心思想的虛擬機到物理機的部署方法，該方法主要的特點在于考慮了虛擬機多類型的特點，從而避免了虛擬機部署開銷大的問題.最后，通過Cloudsim仿真平臺，以及與 FCFS算法、PSO算法、IPSO算法分別比較，驗證了提出IAG算法的有效性和優越性.