劉雨瀟，　王　毅，　袁　磊，　吳　釗

(湖北文理學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院, 湖北 襄陽 441053)

0　引　言

大多數(shù)大規(guī)?？茖W(xué)應(yīng)用通常表現(xiàn)為復(fù)雜的科學(xué)工作流形式，包含了一個通過數(shù)據(jù)依賴性連接而成的有序任務(wù)集合[1]。工作流調(diào)度系統(tǒng)即是使用具體的調(diào)度策略實現(xiàn)可用云資源與工作流任務(wù)間的映射，并滿足用戶需求[2]。傳統(tǒng)的工作流調(diào)度環(huán)境多為靜態(tài)的，即資源可用性在保持不變的情況下進行工作流任務(wù)的調(diào)度。作為最新興的計算模式，云計算可以按即付即用和按需提供的方式提供各種互聯(lián)網(wǎng)資源[3]，因此，云資源的計算性能和可用狀態(tài)是動態(tài)變化的，該環(huán)境下的工作流調(diào)度將更為復(fù)雜。本文將設(shè)計一種動態(tài)自適應(yīng)的工作流調(diào)度算法，通過尋找動態(tài)的關(guān)鍵路徑，從而動態(tài)地以更低的調(diào)度開銷降低整個工作流的執(zhí)行跨度。

目前，云工作流調(diào)度問題已經(jīng)成為云計算領(lǐng)域中的研究熱點。相關(guān)研究中，文獻[4]中提出的HEFT是一種異構(gòu)最快完成時間工作流調(diào)度算法，旨在通過賦予任務(wù)不同的優(yōu)先級，最小化工作流的總調(diào)度時間。文獻[5]中提出基于遺傳算法GA的調(diào)度算法，將染色體表示為任務(wù)資源映射方案，同時表示任務(wù)執(zhí)行序列，算法根據(jù)最優(yōu)化目標(biāo)對個體進行進化，并基于約束目標(biāo)進化種群，但算法的進化代數(shù)過多，可能無法找到可行解。文獻[6]中提出一種基于動態(tài)規(guī)劃的云工作流調(diào)度算法，有效解決了資源價格變化環(huán)境中任務(wù)調(diào)度的開銷優(yōu)化問題。文獻[7]中提出Fussy-PSO算法嘗試使用粒子群優(yōu)化PSO算法實現(xiàn)工作流調(diào)度時執(zhí)行跨度與執(zhí)行代價的均衡。以上算法在進行任務(wù)映射時，其針對的對象多為靜態(tài)行為的資源，沒有考慮資源使用本身的動態(tài)性，可能導(dǎo)致任務(wù)調(diào)度的開銷過大。

基于關(guān)鍵路徑的啟發(fā)式算法是解決工作流依賴任務(wù)間調(diào)度問題的有效手段，其目標(biāo)是尋找任務(wù)DAG中所有執(zhí)行路徑中的最長路徑(關(guān)鍵路徑)，從而得到整個工作流的最小執(zhí)行跨度[8]。顯然，在單個任務(wù)被調(diào)度后，關(guān)鍵路徑會發(fā)生動態(tài)變化，而傳統(tǒng)的動態(tài)關(guān)鍵路徑調(diào)度算法僅僅實現(xiàn)了同質(zhì)環(huán)境中的任務(wù)與資源映射問題，即調(diào)度方案僅在任務(wù)DAG中計算一次。由于云計算環(huán)境是動態(tài)異構(gòu)環(huán)境，本文的目標(biāo)即是擴展傳統(tǒng)的動態(tài)關(guān)鍵路徑以適應(yīng)于云工作流的動態(tài)調(diào)度環(huán)境。

1　工作流調(diào)度問題

通常，工作流應(yīng)用以有向無循環(huán)圖(Directed Acyclic Graph,DAG)表示，圖的節(jié)點表示工作流任務(wù)，圖的邊表示任務(wù)間的依賴性，節(jié)點權(quán)重表示任務(wù)計算復(fù)雜性，邊的權(quán)重則表示任務(wù)間的通信數(shù)據(jù)量。因此，工作流調(diào)度問題通?？梢暈橐环NDAG調(diào)度問題，為NP完全問題。

令W(T,E)表示云工作流，T表示工作流任務(wù)集，T={T1,T2,…,Tx,…,Ty,Tn}，E表示任務(wù)間依賴關(guān)系集，E={,…,}，其中，Tx為Ty的父任務(wù)。R={R1,R2,…,Rx,…,Ry,Rm}表示云可用資源集，工作流的入口任務(wù)不存在父任務(wù)，出口任務(wù)不存在子任務(wù)。同時，只有任務(wù)的所有父任務(wù)完成后，該任務(wù)才能執(zhí)行。在調(diào)度發(fā)生的任意時間，其所有父任務(wù)已經(jīng)完成的任務(wù)稱為就緒任務(wù)(Ready task)。工作流調(diào)度問題即是尋找任務(wù)與云資源間的映射方案，使得工作流執(zhí)行跨度makespan或調(diào)度長度達到最小化。

2　CWS-DCP算法設(shè)計

在工作流任務(wù)DAG中，單個任務(wù)的開始時間的下限與上限可分別表示為絕對最早開始時間AEST和絕對最晚開始時間ALST。傳統(tǒng)的動態(tài)關(guān)鍵路徑算法中，由于關(guān)鍵任務(wù)的延遲會影響任務(wù)DAG的整體執(zhí)行時間，因此，處于關(guān)鍵路徑上的任務(wù)擁有相同的AEST和ALST。處于關(guān)鍵路徑上的第一個任務(wù)首先被調(diào)度，直至所有任務(wù)被調(diào)度完成為止。然而，以上的調(diào)度方法僅適用于調(diào)度資源不受限且不考慮計算和通信時間的環(huán)境，云計算提供的計算、存儲、帶寬資源擁有不同的能力和可用性，是異構(gòu)動態(tài)環(huán)境，因此，筆者作了如下幾點改進：

(1) 對于單個任務(wù)，其初始AEST和ALST由為該任務(wù)提供最小執(zhí)行時間的資源計算得到，總體目標(biāo)是降低每次通過的關(guān)鍵路徑的長度；

(2) 為了實現(xiàn)關(guān)鍵路徑上的任務(wù)映射，所有可用的云資源均被考慮進來，由于在異構(gòu)云環(huán)境中資源的可用性會發(fā)生變化，而通信與計算時間會受此影響；

(3) 當(dāng)任務(wù)映射至資源時，其執(zhí)行時間和與父任務(wù)間的數(shù)據(jù)傳輸時間進行實時更新，這會改變后續(xù)任務(wù)的AEST和ALST。

為了便于CWS-DCP算法的描述，表1給出了文中相關(guān)的符號及其含義說明。

表1　符號說明

2.1　AEST和ALST計算

CWS-DCP算法中，任務(wù)的開始時間直到被映射至資源上才被確定下來。此時，引入兩個屬性：任務(wù)的絕對執(zhí)行時間AET和絕對數(shù)據(jù)傳輸時間ADTT，AET表示任務(wù)的最小執(zhí)行時間，ADTT表示在當(dāng)前部署狀態(tài)下傳輸任務(wù)輸出數(shù)據(jù)的最小時間。初始狀態(tài)下，AET和ADTT的計算方法為：

(1)

(2)

式中:PC(Rk)表示資源Rk的處理能力，BW(Rk)表示資源Rk的傳輸能力(帶寬)。

當(dāng)任務(wù)t調(diào)度至資源時，AET(t)和ADTT(t)根據(jù)式(1)、式(2)進行更新。因此，資源R上任務(wù)t的AEST可表示為AEST(t,R)，以遞歸形式表示為：

AEST(t,R)=MAX1≤k≤p{AEST(tk,Rtk)+

AET(tk)+Ct,tk(Rt,Rtk)}

(3)

式中:t擁有p個父任務(wù)，tk表示第k個父任務(wù)，且：

(1) 如果t為入口任務(wù)，則AEST(t,R)=0；

(2) 如果Rt=Rtk，則Ct,tk(Rt,Rtk)=0；

(3) 如果t和tk未被調(diào)度，則Ct,tk(Rt,Rtk)=ADTT(tk)。

此時，如果兩個任務(wù)被調(diào)度至相同資源，則其通信時間等于0，如果子任務(wù)仍未被調(diào)度，則其通信時間等于父任務(wù)的ADTT。利用以上定義，AEST可以通過從入口任務(wù)開始以寬度優(yōu)先方式遍歷任務(wù)DAG的方式計算AEST。

計算所有任務(wù)的AEST后，可以計算動態(tài)關(guān)鍵路徑長度DCPL，即部分已映射工作流的調(diào)度長度(時間)，定義為：

DCPL=MAX1≤i≤n{AEST(ti,Rti)+AET(ti)}

(4)

式中:n表示工作流的任務(wù)總數(shù)量。

計算DCPL后，ALST可以通過反向?qū)挾葍?yōu)先方式遍歷任務(wù)DAG的方式計算得到。因此，資源R上任務(wù)t的ALST可表示為ALST(t,R)，以遞歸形式表示為：

ALST(t,R)=MIN1≤k≤c{ALST(tk,Rtk)-

AET(t)-Ct,tk(Rt,Rtk)}

(5)

式中:t擁有c個子任務(wù)，tk表示第k個子任務(wù)，且：

(1) 如果t為出口任務(wù)，則ALST(t,R)=DCPL-AET(t)；

(2) 如果Rt=Rtk，則Ct,tk(Rt,Rtk)=0；

(3) 如果t和tk未被調(diào)度，Ct,tk(Rt,Rtk)=ADTT(tk)。

2.2　任務(wù)與資源選擇

任務(wù)調(diào)度過程中，任務(wù)DAG的關(guān)鍵路徑?jīng)Q定了部分調(diào)度工作流的調(diào)度長度，因此，必須賦予關(guān)鍵路徑上的任務(wù)優(yōu)先級。然而，隨著調(diào)度過程的進行，關(guān)鍵路徑是動態(tài)變化的，即：由于資源行為的動態(tài)變化可能導(dǎo)致在當(dāng)前步驟中關(guān)鍵路徑上的任務(wù)在下一步驟中可能不是關(guān)鍵路徑上的任務(wù)。因此，在云計算環(huán)境中，工作流的關(guān)鍵路徑是動態(tài)可變的。

動態(tài)關(guān)鍵路徑上的任務(wù)有著相同的開始時間上限和下限，即相同的AEST和ALSP。因此，如果任務(wù)的AEST和ALST是相同的，則動態(tài)關(guān)鍵路徑的任務(wù)也在關(guān)鍵路徑上，稱為關(guān)鍵任務(wù)。為了降低每一步中的DCPL，調(diào)度過程中選擇的任務(wù)需要處于關(guān)鍵路徑上，且不存在未被映射的父任務(wù)，即：選擇的為擁有最低AEST的關(guān)鍵路徑。

確定關(guān)鍵任務(wù)后，需要為任務(wù)選擇合適資源。此時選擇的資源是為任務(wù)提供最小執(zhí)行時間的資源。該過程可以通過遍歷所有可用資源，尋找在相同資源上關(guān)鍵子任務(wù)的最小開始時間的任務(wù)，該子任務(wù)即為關(guān)鍵任務(wù)所有子任務(wù)中擁有最小的AEST與ALST之差的任務(wù)。最后，關(guān)鍵任務(wù)被映射至能夠提供最早開始時間的資源上。

2.3　算法步驟

以下偽代碼給出了CWS-DCP算法的具體執(zhí)行過程。

1.Input:WorkflowW(T,E),TashDependencyList,

Resource SetR

2.Output: Mappling Strategy

3.for allt∈Tof workflowW

4.compute AET and ADTT fort

5.end for

6.for allt∈Tof workflowW

7.compute AEST for r running BFS

8.end for

9.compute DCPL

10.for allt∈Tof workflowW

11.compute ALST fortrunning BFS following reverse

task dependency

12.end for

13.while all tasks inTare not completed do

14.TaskList←Get unscheduled Ready tasks for workflowW

15.Schedule Tash(TaskList,R)

16.Update TaskDependencyList

17.end while

18.Schedule Task

19.Input: TaskList, Resource SetR

20.while TaskList is not empty do

21.Tct←Get critical task from all tasks of TaskList

22.Tctc←Get critical chile task from all child task ofTct

23.r←Get a resource from R that can provide earliest start time for bothTctandTctc

24.scheduleTctonr

25.update status ofr

26.for allt∈Tof workflowW

27.compute AEST fortrunning BFS

28.end for

29.cmpute DCPL

30.for allt∈Tof workflowW

31.compute ALST fortrunning BFS following reverse

task dependency

32.end for

33.end while

算法說明：首先，CWS-DCP算法計算所有任務(wù)的初始AET、ADTT、AEST和ALST，然后，選擇AEST與ALST之差最小的任務(wù)，并通過選擇擁有最小AEST的任務(wù)切斷與前驅(qū)任務(wù)的連接。根據(jù)之前的討論，處于動態(tài)關(guān)鍵路徑DCP上的該任務(wù)即為關(guān)鍵任務(wù)。關(guān)鍵任務(wù)的關(guān)鍵子任務(wù)也通過這種方式確定。然后，算法計算關(guān)鍵任務(wù)在所有可用資源上的開始時間(同時考慮了其所有父任務(wù)的完成時間)，選擇為任務(wù)tct和其關(guān)鍵子任務(wù)提供了最早開始時間的資源作為目標(biāo)資源。

選擇合適資源R之后，算法計算開始時間AEST(tct,R)和在該資源上任務(wù)tct的持續(xù)時間AET(tct)，并更新任務(wù)tct的實際開始時間和執(zhí)行時間。其他任務(wù)的AEST和ALST在每次調(diào)度的結(jié)束進行更新，以決定下一個關(guān)鍵任務(wù)。該過程進行至工作流中所有任務(wù)被調(diào)度時結(jié)束。

2.4　算例說明

為了進一步說明CWS-DCP算法的思想，圖1給出了以CWS-DCP算法進行工作流任務(wù)調(diào)度的算例過程。樣本工作流由五個任務(wù)組成，表示為{T0,T1,T2,T3,T4}，各任務(wù)擁有不同的執(zhí)行時間和數(shù)據(jù)傳輸需求。圖1(a)給出了每個任務(wù)的大小和輸出數(shù)據(jù)的大小，分別表示為百萬指令數(shù)(Million Instruction，MI)和GB，任務(wù)被調(diào)度至兩個云資源R1和R2，其處理能力表示為PC，傳輸能力表示為BW(帶寬)，如圖1所示。

算例說明：首先，圖1(a)計算每個任務(wù)的AET和ADTT，然后，使用以上得到的值，計算所有任務(wù)的AEST和ALST，如圖1(b)所示。由于T0、T2、T3和T4擁有相同的AEST和ALST，則這4個任務(wù)均在關(guān)鍵路徑上，且T0作為最高任務(wù)。由于選擇T0作為關(guān)鍵任務(wù)并被映射至R1，故R1帶給T0最小開始時間。該步驟完成后，可以計算此時工作流的調(diào)度長度DCPL為890。類似地，圖1(c)中，選擇T2作為關(guān)鍵任務(wù)并被映射至R1。由于T0和T2均被映射至R1，T0的數(shù)據(jù)傳輸時間此時為0，所有任務(wù)的AEST和ALST均發(fā)生改變，工作流的調(diào)度長DCPL變?yōu)?50，如圖1(d)。在下一步，T3被映射至R1，由于T2的數(shù)據(jù)傳輸時間為0，因此DCPL減少至770。

當(dāng)前，T4是唯一處于關(guān)鍵路徑上的任務(wù)，如圖1(e)。然而，T4的子任務(wù)之一T1仍然沒有被映射，因此，選擇T1作為關(guān)鍵任務(wù)。由于T2和T3已經(jīng)被映射至R1，R1上T1的開始時間為700，故在R2上其開始和結(jié)束時間分別為180和430，T1被映射至R2。最后，當(dāng)T4映射至R1時(圖1(g))，所有任務(wù)已被映射，工作流的調(diào)度長度DCPL無法進一步改進，得到最終DCPL為750。由CWS-DCP得到的最終調(diào)度方案如圖1(h)所示。

圖1算例說明

3　性能評估

為了評估CWS-DCP算法的性能，利用CloudSim[9]構(gòu)建云工作流調(diào)度環(huán)境，并建立了不同類型的工作流模型與同類型算法進行性能比較。

3.1　工作流模型

為了模擬產(chǎn)生不同格式不同權(quán)重的工作流模型，實驗中將以下參數(shù)作為工作流模型的輸入?yún)?shù)：

(1)N，表示工作流任務(wù)的總數(shù)量；

(2)α，表示形狀參數(shù)，即任務(wù)總量與寬度(即同一層次上節(jié)點的最大數(shù)量)的比例，因此，寬度W=int[N/α]。

(3) 工作流類型，提供3種不同類型的工作流：并行工作流、Fork-join工作流和隨機工作流。

① 并行工作流：并行工作流中，一組任務(wù)形成一個擁有單入口任務(wù)和出口任務(wù)的任務(wù)串，多個任務(wù)串形成一個工作流，因此，單個任務(wù)的執(zhí)行僅取決于某個任務(wù)，而任務(wù)串的串首任務(wù)取決于入口任務(wù)，出口任務(wù)取決于所有串尾任務(wù)。并行工作流的層次數(shù)為：

層次數(shù)=int[(N-2)/W]

(6)

② Fork-join工作流：Fork-join工作流中，任務(wù)先分支再連接，因此，只擁有一個入口任務(wù)和出口任務(wù)，在每個層次上的任務(wù)數(shù)量取決于任務(wù)總數(shù)和層次寬度W。Fork-join工作流的層次數(shù)為：

層次數(shù)=int[N/(W+1)]

(7)

③ 隨機工作流：隨機工作流中，單個任務(wù)與其它任務(wù)的依賴性與父任務(wù)數(shù)量即是工作流DAG中節(jié)點的入度，均是隨機產(chǎn)生的。此時，任務(wù)依賴性和入度定義為：

max indegree(Ti)=int[W/2]

(8)

min indegree(Ti)=1

(9)

Parent(Ti)={Tx|Tx∈[T0,…,Ti-1]},

ifTiis not a root task

(10)

xis a random number and

0≤x≤int[W/2]

(11)

Parent(Ti)={φ},ifTiis a root task

(12)

圖2給出以上3種工作流模型的示意圖，其中N=10，α=5。仿真中，利用百萬指令數(shù)MI表示任務(wù)長度，兆字節(jié)數(shù)MB表示任務(wù)輸出數(shù)據(jù)量大小。

圖23種工作流結(jié)構(gòu)

3.2　資源模型

工作流任務(wù)的執(zhí)行環(huán)境模擬為異構(gòu)資源環(huán)境，即設(shè)置不同處理能力的異構(gòu)云資源供任務(wù)調(diào)度。參考文獻[10]，設(shè)置8種不同地域不同能力的云資源，具體參數(shù)如表2所示，其中，資源的處理能力以MI/s和Mb/s度量。

表2　資源配置

3.3　比較算法

(1) Myopic算法[11]：將未映射的任意就緒任務(wù)調(diào)度至能最早完成時任務(wù)的資源上，直到所有任務(wù)被調(diào)度。

(2) MIN-MIN算法[12]：基于任務(wù)在資源上的期望完成時間ECT最小為任務(wù)分配優(yōu)先級，將任務(wù)分組并迭代調(diào)度，每次迭代中，尋找最小ECTs中使得總時間達到最小的調(diào)度方案。

(3) MAX-MIN算法[13]：與MIN-MIN類似，區(qū)別在于算法為擁有最長執(zhí)行時間ECT的任務(wù)分配優(yōu)先級。

(4) HEFT算法[4]：異構(gòu)最早完成時間算法，給予擁有更高等級的工作流任務(wù)更高優(yōu)先級，該等級使用每個任務(wù)的平均執(zhí)行時間和兩個連續(xù)任務(wù)在資源上的平均通信時間計算得到。

(5) GRASP算法[14]：貪婪隨機自適應(yīng)搜索算法，利用貪婪思想，搜索整個解空間(工作流任務(wù)與所有可用資源)，將最優(yōu)解保留至最終解中，搜索過程直到達到最大迭代次數(shù)為止。

(6) GA算法[5]：算法利用遺傳進化的思想，通過對解空間的快速搜索和對個體的適應(yīng)度評價，不同于GRASP的隨機搜索方式，可以在更短時間內(nèi)得到較優(yōu)解。

按算法分類，Myopic、MIN-MIN、MAX-MIN和HEFT均屬于啟發(fā)式算法，而GRASP和GA則屬于元啟發(fā)式算法，以上算法均是分布式計算環(huán)境中常用的工作流調(diào)度算法。

3.4　實驗參數(shù)

(1) 工作流類型。并行工作流、Fork-join工作流和隨機工作流。通過配置3種不同類型的工作流拓撲結(jié)構(gòu)，可以觀察和評估算法在搜索關(guān)鍵路徑時與任務(wù)結(jié)構(gòu)的關(guān)系。

(2)N={50,100,200,300}。通過在工作流中配置不同數(shù)量的任務(wù)，可以觀察算法性能與工作流任務(wù)間的關(guān)系。

(3)α={10}。該參數(shù)值隨機選取，由于工作流的結(jié)構(gòu)寬度W=int[N/α]，因此該值主要影響拓撲結(jié)構(gòu)中同一層次上的任務(wù)最大數(shù)量。

為了使實驗結(jié)果更加具有普遍性，設(shè)置每個工作流任務(wù)的大小均勻分布于區(qū)間[100000MI,500000MI]，任務(wù)的輸出數(shù)據(jù)量大小均勻分布于區(qū)間[1×106,5×106]。同時，對于GRASP算法，調(diào)度迭代次數(shù)為600次。對于GA算法，參數(shù)參考原始配置，如表3所示。

3.5　實驗結(jié)果分析

表3　GA參數(shù)

為了評估算法在工作流執(zhí)行跨度上的性能，筆者設(shè)計了兩種不同的實驗場景，第1種場景考慮為靜態(tài)場景，即：云資源的可用性和負荷保持為靜態(tài)不變，根據(jù)不同的調(diào)度算法映射任務(wù)至資源并執(zhí)行調(diào)度；第2種場景考慮為現(xiàn)實場景，即：云資源的可用性和負荷為動態(tài)改變的，此時，仿真期間每個資源的瞬時負荷(占用PE數(shù)量)服從高斯分布。

(1) 靜態(tài)場景中的執(zhí)行跨度makespan。圖3給出了算法在3種工作流結(jié)構(gòu)中任務(wù)數(shù)分別為50、100、200和300時的工作流執(zhí)行跨度。對于隨機工作流(圖3(c))，CWS-DCP的調(diào)度makespan比HEFT低13%左右，而HEFT則優(yōu)于Myopic、MIN-MIN和MAX-MIN，主要是由于隨機工作流中任意任務(wù)與出口任務(wù)間擁有多條路徑，而CWS-DCP通過為任務(wù)動態(tài)分配優(yōu)先權(quán)可以形成更優(yōu)的解。由于GRASP和GA搜索了最優(yōu)解的全部空間，比較CWS-DCP節(jié)省了20%～30%的makespan。

對于Fork-join工作流(圖3(b))，啟發(fā)式算法與元啟發(fā)式算法性能差別較大。任務(wù)選擇過程中，啟發(fā)式算法沒有考慮映射子任務(wù)的影響，因此，所有啟發(fā)式算法與CWS-DCP擁有類似的結(jié)果。然而，在Fork-join工作流中，連接交叉點任務(wù)取決于上層所有分支非依賴任務(wù)的輸出。如果連接點任務(wù)分配至與其他資源帶寬較低的資源，數(shù)據(jù)傳輸時間的增加會影響工作流執(zhí)行跨度。而元啟發(fā)式算法GRASP和GA不僅考慮了父分支任務(wù)對映射的影響，而且考慮了子分支任務(wù)的影響，因此，比較CWS-DCP，性能提升了40%～50%。

對于并行工作流(圖3(a))，其執(zhí)行跨度隨著工作流大小的變化表現(xiàn)出相對較慢的指數(shù)級增長，原因在于，不同于Fork-join工作流，在調(diào)度每一步中，并行工作流中未被映射的就緒任務(wù)的數(shù)量恒等于W，且只要其父任務(wù)完成，該任務(wù)即轉(zhuǎn)變成就緒任務(wù)。因此，當(dāng)可用資源量少于未被映射任務(wù)量時，任務(wù)等待被調(diào)度的時間將導(dǎo)致執(zhí)行跨度的增加。同時，并行工作流中，CWS-DCP和GA的結(jié)果優(yōu)于其他算法，makespan至少低于其他算法20%左右。此時，GRASP的執(zhí)行跨度高于CWS-DCP，主要是由于任務(wù)映射候選解的數(shù)量會隨著工作流大小的增長呈指數(shù)級增加。

(a) 并行工作流

(b) Fork-join工作流

(c) 隨機工作流

(2) 動態(tài)場景中的執(zhí)行跨度makespan。由于動態(tài)環(huán)境中資源可用性是動態(tài)變化的，在確定周期中資源可用性信息需要連續(xù)不斷更新，且任務(wù)需要根據(jù)資源可用性重新映射。此時，需要比較CWS-DCP與其他啟發(fā)式調(diào)度算法和元啟發(fā)式調(diào)度算法在靜態(tài)場景下的結(jié)果。

圖4顯示了動態(tài)場景下的結(jié)果，其資源可用性的更新周期為50 s。此時，資源可用處理元素PE數(shù)量和資源上可以開始執(zhí)行的任務(wù)數(shù)量會隨著資源負荷動態(tài)變化。對于GRASP和GA算法而言，如果資源負荷較重且不可用，被映射至該資源的任務(wù)需要等待執(zhí)行，該等待時間會相應(yīng)影響其他依賴任務(wù)的開始時間，并增加工作流執(zhí)行跨度makespan，GRASP和GA的較差性能也可以反映出這一結(jié)果。而且，啟發(fā)式算法的結(jié)果高于元啟發(fā)式算法30%左右。在所有啟發(fā)式算法中，CWS-DCP可以比其他算法節(jié)省6%左右makespan，主要是由于在CWS-DCP中，在負載較重的資源上等待執(zhí)行的關(guān)鍵路徑上的任務(wù)會被重新調(diào)度至擁有可用PE的資源上，這會降低關(guān)鍵路徑長度，即工作流執(zhí)行跨度makespan會降低。

同時可以看出，對于相同類型的工作流，動態(tài)場景中的啟發(fā)式算法性能優(yōu)于靜態(tài)場景的性能，主要原因是動態(tài)場景中的資源負荷和資源可用性是周期性更新的，這表明啟發(fā)式算法可以更加適應(yīng)于資源的可用性變化，產(chǎn)生調(diào)度方案的更優(yōu)解。

(a) 并行工作流

(b) Fork-join工作流

(c) 隨機工作流

(3) 算法調(diào)度時間比較。圖5給出了不同類型工作流下算法的調(diào)度時間的比較結(jié)果。調(diào)度時間即為調(diào)度開銷，即調(diào)度算法產(chǎn)生調(diào)度解的運行時間。為了表述的方便，單個任務(wù)的平均調(diào)度時間(單位：ms)得到的單個調(diào)度方案如表4所示，可以看出，為產(chǎn)生一個調(diào)度方案，Myopic、MIN-MIN、MAX-MIN和HEFT需要接近1 ms產(chǎn)生調(diào)度解，而CWS-DCP需要16～17 ms，且不會隨著工作流類型發(fā)生變化，主要是由于該算法的任務(wù)選擇與工作流結(jié)構(gòu)是無關(guān)的。

表4　單個任務(wù)的平均調(diào)度時間　ms

(a) 并行工作流

(b) Fork-join工作流

(c) 隨機工作流

GRASP的調(diào)度時間不僅會隨著工作流任務(wù)的增加呈指數(shù)級增長，而且與工作流結(jié)構(gòu)也密切相關(guān)。在每次迭代中，GRASP為每個未被映射的就緒任務(wù)建立約束候選資源列表RCL，然后隨著為任務(wù)選擇資源映射。當(dāng)任務(wù)增加時，RCL會呈指數(shù)級增長，從而導(dǎo)致調(diào)度時間的增加，而RCL本身的大小又依賴于工作流結(jié)構(gòu)的不同。例如：如果工作流由于300個任務(wù)組成，并行和Fork-join工作流結(jié)構(gòu)在每個層次包括30個任務(wù)，隨機工作流結(jié)構(gòu)層次與每個層次上的任務(wù)數(shù)量均是隨機的。因此，在每一步驟中，并行工作流擁有30個就緒任務(wù)，F(xiàn)ork-join工作流擁有最多30個就緒任務(wù)，隨機工作流每個層次上的平均就緒任務(wù)數(shù)量低于30。因此，隨機工作流的調(diào)度時間是最低的，并行工作流的調(diào)度時間是最高的。

同時，GA的調(diào)度時間不會因為工作流類型的變化而變化，由于GA始終執(zhí)行相同數(shù)量的遺傳操作，與工作流類型無關(guān)。但是，解空間聽每個個體的大小等于工作流任務(wù)的數(shù)量，因此，調(diào)度時間會隨著工作流大小的增加而增加。

綜上，結(jié)合圖3，很明顯在啟發(fā)式算法中，靜態(tài)場景中CWS-DCP的性能可以提升20%，尤其對于隨機工作流和并行工作流，且與工作流類型無關(guān)。在隨機工作流和Fork-join工作流，GRASP和GA的性能優(yōu)于CWS-DCP，但是其調(diào)度時間也更高。對于任務(wù)數(shù)為300的并行工作流，CWS-DCP需要6 s將任務(wù)映射至資源，而GRASP和GA分別需要580 s和2 076 s。

在動態(tài)場景中，啟發(fā)式算法可以自適應(yīng)于資源的動態(tài)特征并避免性能降低。但是，元啟發(fā)式算法在靜態(tài)場景中且由于確定間隔內(nèi)映射資源的不可用而表現(xiàn)更差。同時，動態(tài)場景中，無論工作流類型和大小的不同，CWS-DCP的性能均優(yōu)于其他算法。

4　結(jié)　語

云資源的動態(tài)行為特征導(dǎo)致云工作流調(diào)度不同于傳統(tǒng)靜態(tài)分布式計算環(huán)境中的調(diào)度問題。針對該問題，提出了一種動態(tài)自適應(yīng)工作流調(diào)度算法CWS-DCP，算法通過不斷迭代計算工作流任務(wù)DAG中的關(guān)鍵路徑，為關(guān)鍵路徑上的任務(wù)分配優(yōu)先級的方式有效實現(xiàn)了工作流任務(wù)與云資源間的映射調(diào)度。實驗結(jié)果表明，在資源可用性動態(tài)改變的情況下，CWS-DCP算法在多數(shù)工作流結(jié)構(gòu)中均能得到更好的調(diào)度方案，且與工作流規(guī)模無關(guān)。進一步的研究將關(guān)注多QoS參數(shù)下的工作流調(diào)度問題，如：考慮任務(wù)與服務(wù)之間映射時的資源可靠性問題或服務(wù)資源執(zhí)行任務(wù)時的能效問題，設(shè)計多目標(biāo)最優(yōu)化算法實現(xiàn)多QoS指標(biāo)的同步優(yōu)化，并以Pareto最優(yōu)評估多目標(biāo)優(yōu)化性能。

參考文獻(References)：

[1]Liu L, Zhang M, Lin Y, et.al. A survey on workflow management and scheduling in cloud computing[C]//In Cluster, Cloud and Grid Computing, 14th IEEE/ACM International Symposium on. IEEE, 2014:837-846.

[2]Vockler JS, Juve G, Deelman E, et.al. Experiences using cloud computing for a scientific workflow application[C]//In Proceedings of the 2nd international workshop on Scientific cloud computing. ACM, 2011: 15-24.

[3]Cusumano M, Cloud computing and SaaS as new computing platform[J], Communication of the ACM, 2011,53(4):27-29.

[4]Topcuoglu H, Hariri S, Wu MY. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions Parallel Distributed Systems,2012,13(3):260-274.

[5]Huang J. The workflow task scheduling algorithm based on the GA model in the cloud computing environment[J]. Journal of Software. 2014,9(4):873-880.

[6]鄭敏，曹健，姚艷.面向價格動態(tài)變化的云工作流調(diào)度算法[J].計算機集成制造系統(tǒng)，2013，19(8):1849-1858.

[7]Garg R, Singh A K. Multi-objective workflow grid scheduling using ε-fuzzy dominance sort based discrete particle swarm optimization[J]. Journal of Supercomputing, 2014,68(2):709-732.

[8]Wu Z, Liu X, Ni Z,et.al. A market-oriented hierarchical scheduling strategy in cloud workflow systems[J].Journal of supercomputing,2013, 63(1):256-293.

[9]Rodrigo C, Rajiv R, Anton B,etal. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50.

[10]Venugopal S, Buyya R. A Set Coverage-based Mapping Heuristic for Scheduling Distributed Data-Intensive Applications on Global Grids[C]//IEEE/ACM International Conference on Grid Computing. IEEE, 2006:238-245.

[11]Wieczorek M, Prodan R, Fahringer T. Scheduling of scientific workflows in the ASKALON grid enviornment[J]. ACM SIGMOD Record, 2005,34(3):56-62.

[12]Maheswaran M, Ali S, Siegel H J,etal. Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems[C]//Heterogeneous Computing Workshop. IEEE Xplore, 1999:30-44.

[13]Mandal A, Auton M. Scheduling strategies for mapping application workflows onto the grid[C]//In Proceedings of the 14thIEEE International Symposium on High Performance Distributed Computing. IEEE,2005:125-134.

[14]Blythe J, Jain S, Deelman E,et.al. Task scheduling strategies for workflow-based applications in grids[C]//In Proceedings of the 5th IEEE International Symposium on Cluster Computing and the Grid. IEEE, 2005:759-767.

[15]楊玉麗, 彭新光, 黃名選,等. 基于離散粒子群優(yōu)化的云工作流調(diào)度[J]. 計算機應(yīng)用研究, 2014, 31(12):3677-3681.

[16]Calheiros R, Buyya R. Meeting deadlines of scientific workflows in public clouds with tasks replication[J]. IEEE Transactions on Parallel and Distributed Systems, 2014,25(7):1787-1796.

·名人名言·

知識是一座寶庫，而實踐則是開啟寶庫的鑰匙。

——托馬斯·富勒