云計算中一種高效的工作流調度方法

胡紅宇 陳 政

1(永州職業技術學院計算機系 湖南 永州 425000) 2(湖南工學院計算機與信息科學學院 湖南 衡陽 421001)

0 引 言

許多科學領域，如生物信息學、物理、天文學等，均有著復雜的任務執行需求[1]，通?？山楣ぷ髁髂Ｊ?。這種工作流模式可表達為有向無循環圖DAG，圖中每個節點代表一個任務，任務間的有向邊代表兩個節點間的數據傳輸關系?？茖W工作流規模大，結構復雜，在處理時需要更強大的計算能力和存儲空間。云計算因為可以通過虛擬機技術提供無限制強大資源使其成為執行大規?？茖W工作流的有效平臺[2-3]。云計算中的工作流調度問題即將每個任務節點映射至虛擬機，實現任務執行，該問題本質上是一個NP完全問題。

已有很多類型的算法對任務調度問題進行了研究，包括啟發式算法、搜索算法、元啟發式算法。而任務調度管理中的任務通常分為獨立任務，即包任務(Bag of Tasks,BoT)和依賴任務(工作流)[4-6]。任務至資源間調度可劃分為兩個階段：調度階段和提供階段。傳統的GAIN算法[7]可歸類為純任務調度階段的算法，而DRIVE算法[8]更側重于資源提供階段。云調度系統則同時包含了調度與提供兩個階段。

工作流調度算法通常有兩個主要的分類：盡力服務調度算法與服務質量約束調度算法[9]。前者通常會忽略一些重要的參考因素，如代價因素，再以最小化執行跨度Makespan為目標進行任務調度。類似于啟發式算法，最小最小算法(MIN-MIN)、最大最小算法(MAX-MIN)及Suffrage[10]算法等均是以最小化makespan作為工作流調度目標的。MIN-MIN首先計算所有任務在所有資源上的最小完成時間，形成矩陣，然后在矩陣中選擇完成時間最小的任務優先進行在相應資源上進行調度執行。MAX-MIN類似于MIN-MIN，區別在于優先選擇的是完成時間最大的任務進行調度執行。此外，文獻[11]提出一種異構最快完成時間調度算法HEFT，通過賦予任務不同優先級，最小化任務調度時間。

為了解決云工作流調度問題，本文提出一種有效的調度算法：首先，將工作流中每個層次的任務劃分為包任務BoT從第一個包任務進行迭代調度，BoT中所有任務的估計計算時間值利用最小最大標準化方式進行標準化操作；然后，利用動態閾值將BoT中的所有任務劃分為兩類批任務B_large和B_small；最后，基于最小完成時間，將批任務中的每個任務調度至相應虛擬機上執行，在執行跨度最小化的同時，還可以確保較高的云資源利用率。

1 云計算中的工作流調度問題

1.1 工作流模型

工作流模型最佳的表達結構是圖論中的有向無環圖模型。該模型可以明確工作流結構中所有任務間的偏序關系，即前驅與后繼關系，以此約束任務間的執行次序，且工作流結構中的入口任務與出口任務在有向無環圖中也可明確表示?；谟邢驘o環圖，算法設計中對于任務的調度選擇也更加有利。一個工作流可表示為一個有向無循環圖DAG結構Dg=(T,E)，T={T1,T2,…,Tn}表示n個任務節點集合，E表示DAG中的有向邊集合。從Tp至Ts間的有向邊表示任務Ts無法開始執行，直到Tp完成為止，表示為Tp→Ts。此時，Tp是前驅節點，Ts是后繼節點。

在工作流結構中，若節點沒有任一前驅節點，則稱為入口任務；若節點沒有任一后繼節點，則稱為出口任務。若一個工作流擁有多個入口任務，可以對其添加一個偽入口任務，以權重為0(傳輸時間)的虛擬邊連接至所有入口任務節點上。同時，此偽入口任務的計算時間也為0。類似地，多出口任務時也可作同樣的處理。節點間的數據傳輸時間DT可通過矩陣表示為：

(1)

式中：元素DTi,j表示任務Ti至任務Tj間的數據傳輸時間，1≤i≤n,1≤j≤n。

1.2 云資源模型

一個云服務提供者CSP可提供具有不同能力的虛擬機VM實例集合用于執行工作流任務。令CS={CS1,CS2,…,CSM}表示可用云服務器集合，部署VM數量為m。需要注意的是，活躍的VM數量在每個云服務器間是變化的，進而導致每個云服務器的部署能力也是變化的。同時，假設若兩個VM部署于同一個云服務器上，兩者間的數據傳輸時間可忽略不計。對于該異構虛擬機構成的云資源模型，每一種可用的虛擬機類型均可以作為任務調度的所選目標，并基于虛擬機的處理能力和資源占用狀態進行任務調度目標的優化與映射求解。

1.3 估計計算時間

工作流中的一個任務節點在不同的VM上的執行時間是不同的，所有任務在不同VM上的估計計算時間ECT可表示為一個矩陣：

(2)

1.4 工作流的執行跨度

工作流執行跨度MS，即工作流中所有任務的整體執行時間，根據有向無環圖所表示的工作流結構特征，即執行入口任務開始到出口任務完成的時間段。令MS(CSk)表示所有執行于云服務器CSk上虛擬機的任務的Makespan，1≤k≤M，MS(VMj)表示執行于虛擬機VMj上任務的Makespan，1≤j≤|CSk|(假設VMj部署于云服務器CSk)，則云服務器CSk(1≤k≤M)的個體Makespan可計算為：

MS(CSk)=max(MS(VMj)) 1≤j≤|CSk|

(3)

因此，對于給定工作流執行的所有云服務器的整體Makesapn可計算為：

MS=max(MS(CSk)) 1≤k≤M

(4)

工作流的執行跨度需要基于工作流本身的結構特征、云資源的異構處理能力以及各任務在資源上的估計計算時間的綜合考慮進行計算。在設計工作流調度算法過程中，也需要根據以上因素，設置優化目標，求解任務與虛擬機間的最佳映射關系，從而得到工作流的調度解。

1.5 平均云資源利用率

任一VM在其部署的云服務器上的時間占用率即為VM利用率，該利用率可表示為VM的Makespan與部署的云服務器CSk的整體Makespan間的比例，公式如下：

(5)

式中：U(VMj)為VMj的利用率。因此，云服務器的利用率可定義為同一云服務器上所部署的所有VM的平均利用率，即：

(6)

式中:U(CSk)表示云服務器CSk的利用率。類似地，所有云服務器的平均利用率為：

(7)

云計算中的工作流調度最優化問題，即將工作流的每個任務調度至部署于M個云服務器上的m個虛擬機上，同時實現執行跨度Makespan的最小化和平均云服務利用率的最大化。

1.6 相關參數描述

為了便于算法描述，定義工作流調度的相關參數與說明如表1所示。

表1 參數說明

1)估計計算時間ETi,j：表示的是任務Ti在VMj上的估計計算時間，由式(2)定義。

2)最早開始時間ESTi,j：表示任務Ti在VMj上執行的最早開始時間，可表示為：

(8)

式中：pi表示任務Ti的前驅節點；pred(i)表示前驅任務集合；ACTpi表示任務Tpi的實際完成時間；DTpi,j表示任務Tj與前驅任務Tpi間的數據傳輸時間。

對于所有的入口任務，ESTi,j=0，即ESTentry,j=0。同時，若任務Ti與其前驅任務Tpi調度至同一虛擬機或云服務器上，則其數據傳輸時間為0。

3)最早完成時間EFTi,j：任務Ti在VMj上的最早完成時間為最早開始時間與估計計算時間之和，即：

EFTi,j=ESTi,j+ETi,j

(9)

4)實際完成時間ACTi,j：表示任務Ti在VMj上的絕對完成時間。

5)標準化估算完成時間N_ECTi,j：

(10)

初始狀態下，在工作流層次1中，標準化ECTi,j通過式(10)計算。然后，N_ECTi,j會隨著N_Temp_ECTi,j進行更新，由于任一單個任務Ti被調度至任一可用VMj，則先前的ECTi,j需要更新為Temp_ECTi,j。

6)動態標準化閾值Thrsh(dTi)：任務Ti的Thrsh(dTi)表示任務Ti在m個VM上的最大計算時間與該任務與其所有前驅任務{Tp}的最大數據傳輸時間DTpi,i的比率。若任務不存在任一前驅任務，則數據傳輸時間為0。Thrsh(dTi)定義為：

1≤i≤n,1≤j≤m,1≤pi≤|Tp|

(11)

Thrsh(dTi)與Temp_ECTi,j是相互獨立的，僅在工作流Dg的每個層次中基于初始的ECTi,j進行計算。

7)平均通信/計算比率CCR：表示DAG中的平均數據傳輸時間(通信代價)與平均計算代價間的比率，為工作流調度問題的固有屬性?；贑CR值，DAG可被劃分為計算密集型或數據密集型工作流。

2 算法設計

2.1 算法原理

本文設計的工作流調度算法(簡稱NMMWS)的主要思想如下：首先，將工作流中每個層次的任務劃分為包任務BoT，從第一個包任務進行迭代調度，BoT中所有任務的ECT值利用最小最大標準化方式進行標準化操作。然后，利用動態閾值將BoT中的所有任務劃分為兩類批任務B_large和B_small。最后，基于最小完成時間，將批任務中的每個任務調度至相應虛擬機上執行。這種動態的閾值計算機制可以對任務進行有效的批集合劃分，使得不同的批任務可以基于最小完成時間標準選擇最佳的目標虛擬機進行調度，進而實現任務執行時間和資源利用率的同步優化。

算法在工作流Dg的每個層次li上分兩個階段進行。第一個階段中，算法對每個層次上的每個任務Ti的ECTi,j進行標準化操作，然后利用式(11)計算每個任務的閾值。對{N_ECTi,j}中的最大標準化值和閾值Thrsh(dTi)進行比較，以便將每個層次中的任務劃分為大批任務B_large和小批任務B_small。以上的計算過程從工作流的入口任務至出口任務自頂向下的方式進行計算。第二個階段中，算法通過從ECTi,j中選擇最小的執行時間將任務調度至相應虛擬機上。任務分配后，將ECTi,j更新為Temp_ECTi,j。該過程迭代執行至所有任務完成調度，同時要計算任務的EST和EFT。算法過程如算法1至算法4所示。

算法1NMMWS算法

輸入：包括n個任務節點的工作流Dg(T,E)。

輸出：Dg(T,E)在部署于M個云服務器上的m個VM上的映射。

1. 讀取估計計算時間矩陣ECT和數據傳輸時間矩陣DT

2. while任務池中有未調度的任務

3. for each levelliofDg

//在工作流Dg的每個層次上迭代

4. call Generate-Ready-Tasks-List(n,ECTi,j)

//調用算法2生成就緒任務列表

5. call Comp_EFT(ECTi,j,ofQRli,DTi,j)

//調用算法3計算任務的估算完成時間

6. call Norm_Partition(ECTi,j,N_ECTi,j,Thrsh(dTi))

//調用算法4分割任務，生成任務的B_large和B_small集合

7. if B_large is not empty then

8. find min(EFTi,j)

//尋找EFT中的最小值

9.taskVMmap(Ti)=VMj

//按EFT最小值作出相應調度

10.ACTi,j=EFTi,j

//更新任務實際完成時間

11.ESTi,j=1

//設置最早開始時間

12. removeTifrom B_large

//從B_large移除任務

13. else

//在B_small集中搜索

14. find min(EFTi,j)

//尋找EFT中的最小值

15.taskVMmap(Ti)=VMj

//按EFT最小值作出相應調度

16.ACTi,j=EFTi,j

//更新任務實際完成時間

17.ESTi,j=1

//設置最早開始時間

18. end if

19. end for

20.end while

算法2Generate-Ready-Tasks-List(n,ECTi,j)

1. while there is unscheduled task in workflowDgdo

2. B_large of tasks is empty

//B_large為空

3. for each taskTido

//在每個任務上迭代

4. ifECTi,jthen

//若存在估計計算時間值

5. addTitoQRli

//將任務添加至就緒隊列

6. end if

7. end for

8. end while

算法3COMP_EFT(ECTi,jofQRli,DTi,j)

1. for each taskTiin ready task listQRlido

2. ifTihas no parent taskTpthen

//若任務不存在前驅任務

3.ECTi,j=Availj+ETi,j

//計算任務估計計算時間

4. else

5. for eachVMjandTpin parent task ofTido

6. iftaskVMmap(Tp)is not equalVMjthen

7. ifECTi,j

8.ECTi,j=max{Availj,max{ACTpi+DTpi,i}}

//更新任務的估計計算時間

9. end if

10. else

11. ifECTi,j

//估計計算時間小于虛擬機可用時間與前驅任務的

//實際完成時間較大值

12.ECTi,j=max(Avail,ACTpi)

//更新估計計算時間

13. end if

14. end if

15. end for

16. end if

17.end for

算法4Norm_Partition(ECTi,j,N_ECTi,j,Thrsh(dTi))

1. for each taskTiin ready task listQRliandVMjdo

2. find min(ECTi,j)

//尋找ECT中的最小值

3. find max(ECTi,j)

//尋找ECT中的最大值

4. find the normalizedECTi,jasN_ECTi,j

5. find theThrsh(dTi)

//尋找閾值

6. if max(N_ECTi,j)≥Thrsh(dTi)then

//判定閾值與標準值的關系

7. add taskTito batch B_large

//若任務的標準ECT值大于等于閾值，則被添加至B_large

8. else

9. taskTigo to batch B_small

//否則添加至B_small

10. end if

11.end for

2.2 時間復雜度分析

1)NMMWS算法(算法1)的時間復雜度為O(n3ml)。

證明：令n為DAG中e條連接邊時的任務總量，l為工作流DAG的層次，M個云服務器上部署的虛擬機數量為m。步驟2和步驟3時間復雜度分別為O(n+e)和O(l)。步驟4在最差情況下需要執行O(n2)次，以生成n個任務的就緒任務隊列。步驟5需要執行O(nm)，以計算DAG中每個層次li中的每個任務的估計計算時間。步驟6執行O(n+e)次，步驟3至步驟19迭代n2m次，步驟2至步驟20的while循環迭代執行n次。因此，算法的總體時間復雜度為O(n3ml)。

2)Generate-Ready-Tasks-List(n,ECTi,j)算法(算法2)的時間復雜度為O(n2)。

證明：現有n個任務節點被調度至m個虛擬機上，算法步驟1至步驟8的while循環最差情況下會執行n次，步驟3至步驟7的內層循環會迭代n次，因此算法的時間復雜度為O(n2)。

3)COMP_EFT(ECTi,j,DTi,j)算法(算法3)的時間復雜度為O(nm)。

證明：對于個n個DAG的分隔任務，步驟1至步驟17的for循環會迭代n次，步驟5至步驟15的內層循環會迭代m次，m為部署于M個云服務器上的可用虛擬機數量，因此算法時間復雜度為O(nm)。

4)Norm_Partition(ECTi,j,N_ECTi,j,Thrsh(dTi))算法(算法4)的時間復雜度為O(n2m)。

證明：令n為DAG中總的任務數量，m為部署在M個云服務器上的所有活躍虛擬機數量。算法步驟1至步驟11的for循環會迭代nm次，步驟2至步驟13執行nm次，步驟4和步驟5均執行n次。因此，算法的時間復雜度為O(n2m)。

3 算例說明

通過圖1的Montage科學工作流示例說明算法的詳細執行思路。Montage工作流多應用于天文學領域，基于輸入圖像產生天氣的定制輸出模式，對CPU處理能力要求較低，完全串行任務較少。該示例中的工作流包括15個任務T={T1,T2,…,T15}，7個層次，24條有向邊，由并行任務和管道任務混合組成。圖中有向邊上的權值即為任務間的數據傳輸時間，即矩陣DT。表2為每個任務在部署于2個云服務器上的4臺虛擬機上的估計計算時間。

圖1 Montage工作流

表2 估計計算時間

圖1中工作流的層次1的就緒隊列QRl1擁有三個任務節點T1、T2和T3，這三個任務均有可能調度至可用的4個VM上。因此，對于層次1，T1、T2和T3的Temp_ECT為：

根據式(10)，標準化Temp_ECT計算為：

任務T1、T2和T3不存在前驅任務，因此不存在來自于前驅的數據傳輸。若DTpi,i=0，則式(11)中的閾值Thrsh(dTi)也為0。因此，此時將閾值可固定設置為0.99?，F在比較Thrsh(dTi)與N_Temp_ECT的最大元素間的關系。N_Temp_ECT矩陣中，在層次1中任務T1的最大元素N_Temp_ECTi,j=1.0，而Thrsh(dTi)固定為0.99，故Thrsh(dTi)

對應的標準化Temp_ECT為：

在更新的N_Temp_ECT矩陣中，任務T3的最大N_Temp_ECTi,j也為1，與固定Thrsh(dTi)為0.99比較，Thrsh(dTi)

對應的標準化Temp_ECT為：

此時，Thrsh(dTi)

在DAG的層次2中，擁有5個任務T4、T5、T6、T7和T8在就緒隊列QRli中。由于層次1中的任務T1、T2和T3已經調度至VM3、VM1和VM4上，因此，VM1、VM2、VM3和VM4的可用時間Availj分別為14、0、13和12。而T4為T1和T2的前驅任務，帶有數據傳輸時間DTi,j為13和15。根據算法4中步驟5至步驟11，任務T4、T5、T6、T7和T8在4個虛擬機VM1、VM2、VM3和VM4上的Temp_ECT可更新為：

然后，標準化Temp_ECT被依次計算，并根據Thrsh(dTi)，任務被置入B_small或B_large中。最終得到的調度結果如表3所示。

表3 工作流各任務的調度結果

Montage工作流DAG調度的甘特圖如圖2所示，其中還包括了算法MIN-MIN、MAX-MIN和HEFT得到的結果?？梢钥闯?，本文算法在工作流執行跨度和平均云資源利用率方面均優于另外3種算法。各算法的工作流執行Makespan和平均資源利用率分別如圖3和圖4所示。MIN-MIN算法的主要調度思想是以最快的時間進行任務分配與處理，以時間為單一權重設計的任務調度算法，將任務分配至處理時間最小的資源上，保證任務完成的時間最短。這種算法雖然保證了處理時間最短，但會導致處理能力強的資源一直處于工作狀態，而處理能力相對一般的資源則資源率不足。MAX-MIN算法與MIN-MIN算法非常類似，同樣是計算每一個任務在任一可用資源上的最早完成時間，不同的是MAX-MIN算法優先調度大任務，任務到資源間的映射是選擇最早完成時間最大的任務映射到所對應的資源上。HEFT算法是一種基于異構最快完成時間的工作流調度算法。首先通過升秩值或降秩值的計算賦予任務不同的優先級，按照優先級遞減的次序形成任務的調度隊列，然后以最小任務調度時間為標準依次將任務調度至資源上，是一種最為經典的單一優化目標工作流調度算法。由此可見，已有的方法更加注重的是調度效率的優化，更加適用于傳統的計算環境。而本文算法在優化調度效率與提高資源利用率、均衡不同處理能力的虛擬機資源上均可體現出較好的優勢，更加適用于云計算中的工作流調度環境。

(a)本文算法

圖3 工作流的執行Makespan

圖4 算法平均資源利用率

4 仿真實驗

4.1 環境搭建

為了評估算法性能，設計仿真實驗對算法進行測試。利用CloudSim作為仿真工具[12]，現有CloudSim工具包僅允許調度獨立任務，不適用于多個相互關聯的依賴任務組成的工作流調度問題。因此，本文對CloudSim的內核架構進行擴展。使用5種不同科學領域中的合成工作流結構作為數據源，包括：天文學中的Montage工作流、生物學中的Genomics工作流、地震學中的CyberShake工作流、引力物理學中的LIGO工作流和生物信息學中的SIPHT工作流。圖5給出5種科學工作流的結構模型。5種工作流結構在其結構特征和任務并行程度等方面均體現出不同特征，在此環境下的測試有利于觀察算法在不同結構組成的工作流中性能的適應性和穩定性。在不違背不同工作流的核心結構的前提下，設置工作流中的任務的通信/計算率分別為{0.05,0.5,1,2,4}進行測試，任務規模為1 000，云服務器數量為4，部署的虛擬機數量為30。

(a)Montage (b)Genomics (c)CyberShake

4.2 仿真結果

圖6為在不同類型的工作流不同CCR取值環境下得到的算法的執行Makespan結果?？梢钥闯?，本文算法提供了最小的執行跨度，執行效率更高。即使改變工作流任務中的通信密集型和計算密集型任務的配比，依然不會對結果產生反轉式的影響，僅僅會在不同算法間增加或降低執行跨度，但對其他算法同樣會產生影響，驗證了本文算法的適應性和魯棒性。圖7為各算法的平均資源利用率結果，可以看出，本文算法也體現出了優勢。主要原因在于，本文算法不僅根據任務在工作流結構的位置以及對資源執行的需求進行了分類，而且可以更加精確地選擇最優的虛擬機執行任務；不僅可以提高執行效率，還可以保證云服務器資源得到更大化的利用。本文算法均得到最高的平均資源利用率，說明本文算法面臨不同的任務類型和任務組成結構時也具有很好的適應性。

(a)CyberShake工作流

圖7 平均資源利用率

5 結 語

為了解決云計算科學工作流調度優化問題，本文提出基于執行跨度和資源利用率為優化目標的工作流調度算法。算法在工作流結構的層次基礎上，將任務節點與云服務器的虛擬機間的映射關系求解劃分為兩個階段。第一階段算法對每個層次上的每個任務的估計計算時間以最小最大標準化方式進行操作，并計算任務閾值，將得到的最大標準化值和閾值進行比較，以便將每個層次中的任務劃分為大批任務和小批任務；第二個階段算法通過從估計計算時間矩陣中選擇最小執行時間將任務調度至相應虛擬機上，并更新相應執行時間矩陣。實驗結果表明，算法不僅可以最小化執行跨度，還可確保更高的云資源利用率。