胡紅宇 陳 政

1(永州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系 湖南 永州 425000) 2(湖南工學(xué)院計(jì)算機(jī)與信息科學(xué)學(xué)院 湖南 衡陽 421001)

0 引 言

許多科學(xué)領(lǐng)域，如生物信息學(xué)、物理、天文學(xué)等，均有著復(fù)雜的任務(wù)執(zhí)行需求[1]，通?？山楣ぷ髁髂Ｊ健＿@種工作流模式可表達(dá)為有向無循環(huán)圖DAG，圖中每個(gè)節(jié)點(diǎn)代表一個(gè)任務(wù)，任務(wù)間的有向邊代表兩個(gè)節(jié)點(diǎn)間的數(shù)據(jù)傳輸關(guān)系?？茖W(xué)工作流規(guī)模大，結(jié)構(gòu)復(fù)雜，在處理時(shí)需要更強(qiáng)大的計(jì)算能力和存儲空間。云計(jì)算因?yàn)榭梢酝ㄟ^虛擬機(jī)技術(shù)提供無限制強(qiáng)大資源使其成為執(zhí)行大規(guī)?？茖W(xué)工作流的有效平臺[2-3]。云計(jì)算中的工作流調(diào)度問題即將每個(gè)任務(wù)節(jié)點(diǎn)映射至虛擬機(jī)，實(shí)現(xiàn)任務(wù)執(zhí)行，該問題本質(zhì)上是一個(gè)NP完全問題。

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

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

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

1 云計(jì)算中的工作流調(diào)度問題

1.1 工作流模型

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

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

(1)

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

1.2 云資源模型

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

1.3 估計(jì)計(jì)算時(shí)間

工作流中的一個(gè)任務(wù)節(jié)點(diǎn)在不同的VM上的執(zhí)行時(shí)間是不同的，所有任務(wù)在不同VM上的估計(jì)計(jì)算時(shí)間ECT可表示為一個(gè)矩陣：

(2)

1.4 工作流的執(zhí)行跨度

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

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

(3)

因此，對于給定工作流執(zhí)行的所有云服務(wù)器的整體Makesapn可計(jì)算為：

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

(4)

工作流的執(zhí)行跨度需要基于工作流本身的結(jié)構(gòu)特征、云資源的異構(gòu)處理能力以及各任務(wù)在資源上的估計(jì)計(jì)算時(shí)間的綜合考慮進(jìn)行計(jì)算。在設(shè)計(jì)工作流調(diào)度算法過程中，也需要根據(jù)以上因素，設(shè)置優(yōu)化目標(biāo)，求解任務(wù)與虛擬機(jī)間的最佳映射關(guān)系，從而得到工作流的調(diào)度解。

1.5 平均云資源利用率

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

(5)

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

(6)

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

(7)

云計(jì)算中的工作流調(diào)度最優(yōu)化問題，即將工作流的每個(gè)任務(wù)調(diào)度至部署于M個(gè)云服務(wù)器上的m個(gè)虛擬機(jī)上，同時(shí)實(shí)現(xiàn)執(zhí)行跨度Makespan的最小化和平均云服務(wù)利用率的最大化。

1.6 相關(guān)參數(shù)描述

為了便于算法描述，定義工作流調(diào)度的相關(guān)參數(shù)與說明如表1所示。

表1 參數(shù)說明

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

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

(8)

式中：pi表示任務(wù)Ti的前驅(qū)節(jié)點(diǎn)；pred(i)表示前驅(qū)任務(wù)集合；ACTpi表示任務(wù)Tpi的實(shí)際完成時(shí)間；DTpi,j表示任務(wù)Tj與前驅(qū)任務(wù)Tpi間的數(shù)據(jù)傳輸時(shí)間。

對于所有的入口任務(wù)，ESTi,j=0，即ESTentry,j=0。同時(shí)，若任務(wù)Ti與其前驅(qū)任務(wù)Tpi調(diào)度至同一虛擬機(jī)或云服務(wù)器上，則其數(shù)據(jù)傳輸時(shí)間為0。

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

EFTi,j=ESTi,j+ETi,j

(9)

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

5)標(biāo)準(zhǔn)化估算完成時(shí)間N_ECTi,j：

(10)

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

6)動態(tài)標(biāo)準(zhǔn)化閾值Thrsh(dTi)：任務(wù)Ti的Thrsh(dTi)表示任務(wù)Ti在m個(gè)VM上的最大計(jì)算時(shí)間與該任務(wù)與其所有前驅(qū)任務(wù){(diào)Tp}的最大數(shù)據(jù)傳輸時(shí)間DTpi,i的比率。若任務(wù)不存在任一前驅(qū)任務(wù)，則數(shù)據(jù)傳輸時(shí)間為0。Thrsh(dTi)定義為：

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

(11)

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

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

2 算法設(shè)計(jì)

2.1 算法原理

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

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

算法1NMMWS算法

輸入：包括n個(gè)任務(wù)節(jié)點(diǎn)的工作流Dg(T,E)。

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

1. 讀取估計(jì)計(jì)算時(shí)間矩陣ECT和數(shù)據(jù)傳輸時(shí)間矩陣DT

2. while任務(wù)池中有未調(diào)度的任務(wù)

3. for each levelliofDg

//在工作流Dg的每個(gè)層次上迭代

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

//調(diào)用算法2生成就緒任務(wù)列表

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

//調(diào)用算法3計(jì)算任務(wù)的估算完成時(shí)間

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

//調(diào)用算法4分割任務(wù)，生成任務(wù)的B_large和B_small集合

7. if B_large is not empty then

8. find min(EFTi,j)

//尋找EFT中的最小值

9.taskVMmap(Ti)=VMj

//按EFT最小值作出相應(yīng)調(diào)度

10.ACTi,j=EFTi,j

//更新任務(wù)實(shí)際完成時(shí)間

11.ESTi,j=1

//設(shè)置最早開始時(shí)間

12. removeTifrom B_large

//從B_large移除任務(wù)

13. else

//在B_small集中搜索

14. find min(EFTi,j)

//尋找EFT中的最小值

15.taskVMmap(Ti)=VMj

//按EFT最小值作出相應(yīng)調(diào)度

16.ACTi,j=EFTi,j

//更新任務(wù)實(shí)際完成時(shí)間

17.ESTi,j=1

//設(shè)置最早開始時(shí)間

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

//在每個(gè)任務(wù)上迭代

4. ifECTi,jthen

//若存在估計(jì)計(jì)算時(shí)間值

5. addTitoQRli

//將任務(wù)添加至就緒隊(duì)列

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

//若任務(wù)不存在前驅(qū)任務(wù)

3.ECTi,j=Availj+ETi,j

//計(jì)算任務(wù)估計(jì)計(jì)算時(shí)間

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}}

//更新任務(wù)的估計(jì)計(jì)算時(shí)間

9. end if

10. else

11. ifECTi,j

//估計(jì)計(jì)算時(shí)間小于虛擬機(jī)可用時(shí)間與前驅(qū)任務(wù)的

//實(shí)際完成時(shí)間較大值

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

//更新估計(jì)計(jì)算時(shí)間

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

//判定閾值與標(biāo)準(zhǔn)值的關(guān)系

7. add taskTito batch B_large

//若任務(wù)的標(biāo)準(zhǔn)ECT值大于等于閾值，則被添加至B_large

8. else

9. taskTigo to batch B_small

//否則添加至B_small

10. end if

11.end for

2.2 時(shí)間復(fù)雜度分析

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

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

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

證明：現(xiàn)有n個(gè)任務(wù)節(jié)點(diǎn)被調(diào)度至m個(gè)虛擬機(jī)上，算法步驟1至步驟8的while循環(huán)最差情況下會執(zhí)行n次，步驟3至步驟7的內(nèi)層循環(huán)會迭代n次，因此算法的時(shí)間復(fù)雜度為O(n2)。

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

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

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

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

3 算例說明

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

圖1 Montage工作流

表2 估計(jì)計(jì)算時(shí)間

圖1中工作流的層次1的就緒隊(duì)列QRl1擁有三個(gè)任務(wù)節(jié)點(diǎn)T1、T2和T3，這三個(gè)任務(wù)均有可能調(diào)度至可用的4個(gè)VM上。因此，對于層次1，T1、T2和T3的Temp_ECT為：

根據(jù)式(10)，標(biāo)準(zhǔn)化Temp_ECT計(jì)算為：

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

對應(yīng)的標(biāo)準(zhǔn)化Temp_ECT為：

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

對應(yīng)的標(biāo)準(zhǔn)化Temp_ECT為：

此時(shí)，Thrsh(dTi)

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

然后，標(biāo)準(zhǔn)化Temp_ECT被依次計(jì)算，并根據(jù)Thrsh(dTi)，任務(wù)被置入B_small或B_large中。最終得到的調(diào)度結(jié)果如表3所示。

表3 工作流各任務(wù)的調(diào)度結(jié)果

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

(a)本文算法

圖3 工作流的執(zhí)行Makespan

圖4 算法平均資源利用率

4 仿真實(shí)驗(yàn)

4.1 環(huán)境搭建

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

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

4.2 仿真結(jié)果

圖6為在不同類型的工作流不同CCR取值環(huán)境下得到的算法的執(zhí)行Makespan結(jié)果?？梢钥闯觯疚乃惴ㄌ峁┝俗钚〉膱?zhí)行跨度，執(zhí)行效率更高。即使改變工作流任務(wù)中的通信密集型和計(jì)算密集型任務(wù)的配比，依然不會對結(jié)果產(chǎn)生反轉(zhuǎn)式的影響，僅僅會在不同算法間增加或降低執(zhí)行跨度，但對其他算法同樣會產(chǎn)生影響，驗(yàn)證了本文算法的適應(yīng)性和魯棒性。圖7為各算法的平均資源利用率結(jié)果，可以看出，本文算法也體現(xiàn)出了優(yōu)勢。主要原因在于，本文算法不僅根據(jù)任務(wù)在工作流結(jié)構(gòu)的位置以及對資源執(zhí)行的需求進(jìn)行了分類，而且可以更加精確地選擇最優(yōu)的虛擬機(jī)執(zhí)行任務(wù)；不僅可以提高執(zhí)行效率，還可以保證云服務(wù)器資源得到更大化的利用。本文算法均得到最高的平均資源利用率，說明本文算法面臨不同的任務(wù)類型和任務(wù)組成結(jié)構(gòu)時(shí)也具有很好的適應(yīng)性。

(a)CyberShake工作流

圖7 平均資源利用率

5 結(jié) 語

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