劉曉霞, 李 芳

(1. 四川水利職業(yè)技術(shù)學院 信息工程系， 四川 崇州 611231; 2. 重慶大學 計算機學院， 重慶 400044)

0 引 言

工作流被廣泛應用于大型復雜問題建模，云計算的工作過程調(diào)度問題是非常復雜的，故適合利用工作流來研究其過程調(diào)度問題[1]。不同于傳統(tǒng)的獨立任務調(diào)度問題，工作流任務的數(shù)據(jù)計算與通信代價更高更復雜，其本質(zhì)是實現(xiàn)關(guān)聯(lián)式任務與資源間的調(diào)度與分配，同時需滿足規(guī)定的服務質(zhì)量(Quality of Service, QoS)約束。求解工作流調(diào)度問題有兩個重要階段：選擇被調(diào)度任務和選擇提供的實例。兩個階段的決策對于調(diào)度方案的全局代價與是否可滿足全局期限約束均具有重要影響。一種方法是將全局期限在工作流間進行分割得到子期限以確保約束滿足問題，然后在實例提供時僅滿足子期限即可。這其中需要解決兩個關(guān)鍵問題：① 以何種方法將期限在工作流中進行分割？② 不同的分割策略對調(diào)度代價如何？

傳統(tǒng)工作流調(diào)度方法僅注重于優(yōu)化執(zhí)行效率，即降低任務執(zhí)行時間，但云資源的使用通常是有償付費的，資源能力越高，價格越高，此時，使用不同資源及不同調(diào)度方案得到的執(zhí)行代價和時間是不同的，必須更加注重資源利用代價的優(yōu)化。進而，云環(huán)境中的工作流調(diào)度需要同步考慮用時間和代價問題。

1 云計算工作流研究現(xiàn)狀

將工作流任務分配至資源劃分為兩個階段：調(diào)度與提供[2]。給定資源集，工作流任務調(diào)度階段目標是決定最優(yōu)的任務執(zhí)行序列和對應于用戶和工作流約束的任務部署[3-4]。資源提供階段目標是決定所要求的資源數(shù)量和類型，并為工作流執(zhí)行預留該資源[5-6]。

國內(nèi)外研究者們，對云計算工作流方面進行了相關(guān)研究。文獻[7-8]中給出了自底向上算法(Deadline Bottom Level, DBL)和自頂向下算法(Deadline Top Level, DTL)，兩種經(jīng)典的期限分配啟發(fā)式算法；DBL將任務以自底向上的方式進行分類，而DTL以自頂向下的方式進行。DBL中的任務被組織為不同的層次，每一層次中的任務不具有相關(guān)依賴性；DTL中任務被劃分為不同路徑作為同步任務或簡單任務，同步任務定義為擁有一個以上父任務或子任務的任務；在期限分布階段 ，全局期限被分割并以正比于每個層次的最小執(zhí)行時間的方式進行分割；在DBL中，首先需要計算最快的實例，然后將用戶定義的期限與估算值之差均勻分布方式在所有層次間。文獻[9]中將工作流任務劃分為兩種類型：關(guān)鍵和非關(guān)鍵任務；在關(guān)鍵路徑上的所有任務在給定期限下利用動態(tài)規(guī)劃進行調(diào)度非關(guān)鍵任務則在關(guān)鍵任務間進行回填法進行調(diào)度且該算法在調(diào)度過程中忽略了任務間的通信時間。文獻[10]中提出了正比例期限約束云工作流調(diào)度算法，算法將期限以正比于各層次中任務執(zhí)行時間的方式在層次間進行分割。文獻[11-12]中提出最遲完成時間算法將期限在各任務間進行分割，算法是在用戶定義期限條件完成下確保工作流時任務可完成其執(zhí)行的最早時間。文獻[12]中提出局部關(guān)鍵路徑算法根據(jù)任務在工作流中所處的局部關(guān)鍵路徑對任務進行分類，期限根據(jù)定義的路徑重分配，其缺點在于每個局部關(guān)鍵路徑執(zhí)行后，需要重新計算最遲完成時間。文獻[11]中提出一種期限約束下的動態(tài)代價最小化算法，該算法嘗試聯(lián)合管道任務集為單個任務，以消除任務間的數(shù)據(jù)傳輸時間；但該算法并未為任務尋找最佳執(zhí)行實際，不能實現(xiàn)最優(yōu)化。這些研究，促進了云計算工作流的發(fā)展和進步，但未解決云計算中服務時間有限情況下的工作流調(diào)度與優(yōu)化問題。

因此，本文針對現(xiàn)有在云計算工作流存在的不足，擬對云計算中即付即用服務中的期限約束下的工作流調(diào)度優(yōu)化問題進行研究，提出提出一種期限分割的工作流調(diào)度代價優(yōu)化算法(Workflow Scheduling Cost Optimization under Deadline Distribution,WSCO-DD)，并對算法進行仿真驗證。

2 系統(tǒng)模型

定義工作流為有向無循環(huán)圖(Directed Acyclic Graph, DAG)G=(T,E)，T={t0,t1,…,tn}為圖頂點集，即待調(diào)度的任務集合，E={ei,j|ti,tj∈T}為圖邊集，代表兩個任務間的數(shù)據(jù)傳遞性。有向邊ei,j∈E(ti,tj∈T)代表兩個任務間的執(zhí)行順序，即：僅當任務ti執(zhí)行完成并接收ti的所有數(shù)據(jù)后，任務tj才開始執(zhí)行。即：任務ti是tj的父任務，tj是ti的子任務。任務間的父子關(guān)系為多對多關(guān)系，即一個任務可擁有多個子任務，也可作為多個任務的父任務。并且，只有所有父任務完成，子任務ti才可以開始執(zhí)行。

在實例pj上執(zhí)行任務ti的代價為：

TaskCostpjti=wpjti/Nt×cj

(1)

執(zhí)行工作流的所有任務的總代價為：

(2)

云可以提供不同定價和類型的實例，實例在CPU、內(nèi)存、存儲和帶寬上具有不同的能力。工作流結(jié)構(gòu)中的任務根據(jù)其需求可執(zhí)行于不同類型的實例上，每種實例類型可認為是一個資源集合。本文的云資源以Amazon EC2為實例進行建模(由于Amazon EC2是當前最普遍的資源實例類型)，使用方式為按需提供。支付模型以最小賬單時間的即付即用方式建立，即賬單時間內(nèi)少于帳單時間的實例使用均以一個賬單時間支付費用。假設(shè)云供應商可提供無上限的異構(gòu)實例數(shù)量，表示為：P={p0,p1,…,pn}，h為實例類型的索引；且假設(shè)所有實例均位于同一區(qū)域內(nèi)，則實例間的平均帶寬也視為相同的。

3 期限分割的工作流調(diào)度代價優(yōu)化算法WSCO-DD

WSCO-DD算法分為4個階段：

(1) 工作流分層。根據(jù)工作流結(jié)構(gòu)中任務間的關(guān)聯(lián)次序，對任務進行層次劃分。

(2) 期限分割。將用戶定義的期限D(zhuǎn)eadline在每個層次間進行分割，每個層次得到其子期限，同一層次中的所有任務擁有相同的層次期限。

(3) 任務選擇。賦予任務優(yōu)先級，得到任務調(diào)度序列。

(4) 實例選擇。選擇任務執(zhí)行的最優(yōu)實例，在滿足可用期限的同時最小化執(zhí)行代價。

3.1 工作流分層

對工作流結(jié)構(gòu)中的任務進行層次劃分可以區(qū)分獨立任務與關(guān)聯(lián)任務，從而實現(xiàn)任務的最大并行化執(zhí)行，且假設(shè)處于同一層次中的任務與其它層次的任務間相互獨立。令任務ti的層次為該任務與工作流出口間的所有路徑邊的最大值，表示為NL(ti)。出口任務的層次始終為1，其他任務為：

NL(ti)=maxtj∈succ(ti){NL(tj)+1}

(3)

其中：succ(ti)表示任務ti的子任務集。那么，以l表示層次，相同層次的任務可組成一個集合，定義為TL，則：

TL(l)={ti|NL(ti)=l}

(4)

3.2 期限分割

3.2.1初始值估算

對于每個層次的初始估算期限計算為：

InitialTsd(l)=maxti∈TLS(l){ECT(ti)}

(5)

式中:ECT(ti)為ti在所有資源上的最早完成時間，定義為：

(6)

式中:EST(ti)定義為式(9);pred(ti)為任務ti的父任務集;wti為任務ti的最小執(zhí)行時間;l為父任務ti所處的分層。若任務tentry不存在前驅(qū)，則有ECT(tentry)=0。

式(5)表明，一個分層的所有任務的最大ECT可視為該層的全局完成時間估算，該時間可作為所處分層中所有任務并行執(zhí)行時要求的絕對最小完成時間。

3.2.2期限分割方法

期限分割的目標是工作流總體期限在不同層次間進行子劃分，使得各層次在其分配的子期限內(nèi)完成，并確保工作流執(zhí)行滿足全局期限。本文設(shè)計以下幾種基準期限分割算法：

(1) 隨機法Random，簡稱R。以隨機方式將期限在工作流各層次上進行分割。

(2) 平均法Uniform，簡稱U。將期限平均分割至每個層次，各層次期限分割相等。

(3) 高度法Height，簡稱H。層次得到的期限分割和層次與工作流入口的距離成正比。則距離越近，期限分割越小。

(4) 寬度法Width，簡稱W。層次得到的期限分割與該層次包含的任務數(shù)量成正比。任務越多，期限分割越大。

(5) 區(qū)域法Area，簡稱A。聯(lián)立H與W法進行期限分割。

(6) 長度正比例分割算法Length，簡稱L。每個層次根據(jù)與其長度正比的方式以非均勻方式得到期限分割，任務越長的層次得到的期限分割也越長。

通過一個實例說明不同期限分割方法的實現(xiàn)原理。圖1所示為一種工作流結(jié)構(gòu)示例，該工作流的任務總數(shù)為10，圖中給出了工作流的分層結(jié)構(gòu)及各層次中的任務。可以看出，該工作流結(jié)構(gòu)最大層次Nmax=5。假設(shè)此時期限為150。

圖1 工作流示例

R算法該算法對期限進行隨機分割，不作說明。

U算法工作流層次數(shù)為5，則每個層次的期限分割為150/5=30。

H算法定義工作流層次的高度權(quán)值：

則期限因子DF=deadline/Lweight=150/15=10。對于層次3(包含4個任務)而言，期限分割為3×DF=3×10=30。其他層次同理。

W算法層次的期限分割取決于包含的任務數(shù)量，則期限因子DF=deadline/n=150/10=15。則對于層次3(包含4個任務)而言，期限分割為4×DF=4×15=60。其他層次同理。

A算法聯(lián)立H和W算法，此時權(quán)值為：

期限因子DF=deadline/Lweight=150/55=2.73。

然后，期限根據(jù)TL中的數(shù)值之和進行分割。如：層次3 的期限分割為(4+5+6+7)×DF=22×2.73=60。其他層次同理。

L算法計算所有層次的期限估算值后，需要以正比于πdeadline的方式，將用戶定義的執(zhí)行期限在所有任務上進行非均勻重分配，πdeadline定義為：

(7)

其中，InitialTsd(1)表示包含出口任務texit的分層值， sd(sub-deadline,sd)表示子期限。

然后，每個層次期限長度為正比于該層次期限的函數(shù)：

Tsd(l)=InitialTsd(l)+

(πdeadline×|InitialTsd(l)|)

(8)

顯然，分層中的任務越長，該分層得到子期限也越長。表1給出各個算法的期限分割的詳細情況。對應于每一個層次，第1行為每一層次得到的期限分割值，第2行為分配子期限至每一層次后的期限剩余值，該值基于先前層次中的分割值進行累積計算。顯然，第一個層次的子期限值應為總體期限值。例如，層次4的H策略中，期限分割為40，而待分配的子期限為90。表1中未給出L策略得到的期限分割，原因在于該方法需計算每個任務的執(zhí)行時間，需結(jié)合具體參數(shù)進行。

表1 預算分割情況

本文還利用基準期限分割方法的不同組合，進一步得到不同的分割方法。例如：聯(lián)合E、W和L 3種方法，產(chǎn)生新的期限分割方法EWL，其中，E表示每個層次的初始估算期限，由式(5)表示。該策略中，首先，為所有層次計算期限估算值，然后，剩余期限基于W和L方法的聯(lián)合進行分配。通過組合不同方法，可產(chǎn)生14種期限分割方法，如圖2所示。

圖2 不同策略組合

3.3 任務選擇

WSCO-DD算法中，待執(zhí)行的就緒任務放入就緒任務列表中。當所有父任務執(zhí)行完成并接收所有數(shù)據(jù)后，任務可視為就緒任務。因此，在同一工作流層次中，其任務間無依賴性。為了選擇合適的任務執(zhí)行，就緒任務列表中的所有任務以最早開始時間EST賦予任務優(yōu)先級。EST為任務可開始執(zhí)行的最早可能時間，取決于其父任務的完成時間。任務ti的最早開始時間EST計算為在擁有最短執(zhí)行時間的實例上得到的執(zhí)行時間：

(9)

式中：wtj為任務tj在最快實例上的執(zhí)行時間;Ci,j為任務ti與tj間的傳輸數(shù)據(jù)的通信時間;pred(ti)為任務ti的父任務集合。對于每個任務，計算其在所有實例上的EST，最先開始執(zhí)行的任務即被選擇為執(zhí)行侯選任務。

3.4 實例選擇

該階段的目標是選擇最優(yōu)的任務執(zhí)行實例，選擇標準是在滿足任務的子期限的同時，最小化工作流執(zhí)行總代價。引入涉及實例比率ICR的目標函數(shù)：

(10)

云服務提供商，如Amazon EC2，均以1 h時間周期向用戶收取費用。云實例提供后，用戶需要支付整個帳單周期費用，即使其任務在帳單時間結(jié)束前完成。那么，如果其他任務能執(zhí)行于還剩余帳單時間的同一實例上，則其調(diào)度代價即為0。因此，當分配實例時，算法優(yōu)先選擇仍剩余帳單時間的實例。算法的第一步即選擇執(zhí)行當前任務無代價的實例，同時需要確保任務的最早完成時間不超過該層次的分割期限。然后選擇擁有最小ECT的實例，即最快實例。

如果不存在以上條件的實例，算法基于最高ICR值的原則開啟一個新的實例。對于嚴格期限約束而言，可能更低價的實例無法滿足任務層次的子期限約束。因此，式(10)的分子為負值，導致ICR也為負值。如果出現(xiàn)該情況，則需要為當前任務選擇價格更高的實例。可以看出，ICR可以調(diào)整任務在所有實例上的執(zhí)行代價和時間。為了最小化執(zhí)行代價，文獻[20]中試圖將任務調(diào)度至價格最低的實例上，同時滿足其分配的子期限。然而，該方法中，如果資源過慢，會導致任務的子任務的EST出現(xiàn)延遲，進而導致任務的執(zhí)行時間變長。為了避免此情況，本文設(shè)置ICR=20以均衡執(zhí)行時間和代價。

4 仿真實驗

4.1 實驗配置

基于WorkFloSim[13]仿真平臺對算法進行仿真實驗，平臺中配置為一個云數(shù)據(jù)中心，由6種不同的實例類型組成，具體配置見表2。實例帶寬固定設(shè)置為20 MB/s，EC2的處理能力以1 m/s浮點操作數(shù)MFLOPS度量。同時，在定價模型方面，本文使用基于Amazon EC2彈性計算云的資源模型，其實例類型按需提供，其定價使用即付即用的1 h帳單機制，所有小于1 h的資源使用，均按1 h支付。

表1 資源實例類型

利用兩種科學工作流作為現(xiàn)實負載評估算法性能。相似的合成工作流結(jié)構(gòu)作為測試數(shù)據(jù)源，其結(jié)構(gòu)如圖3所示。將期限約束在嚴格與寬松間進行動態(tài)設(shè)置，令FS表示最快調(diào)度，作為基準調(diào)度方案。該基準值為忽略執(zhí)行代價時得到的執(zhí)行時間，表示為：

(11)

定義工作流期限為最快調(diào)度的函數(shù)，表示為：期限=α×FS，這樣使得期限值在相對的嚴格-適中-寬松中變化，其中α為期限因子，α∈[0,20]，α可以按某步長進行遞增，其值越小，期限約束越嚴格，其值越大，期限約束越寬松。

同時，Amazon EC2的云實例以1 h作為帳單服務時間，仿真中應用該價格模型。設(shè)置工作流的任務總數(shù)為1 000。仿真結(jié)果以10次實驗的平均值作為標準。

(a) 基因工作流結(jié)構(gòu)(b) 網(wǎng)絡空間工作流結(jié)構(gòu)

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

4.2 實驗分析

實驗1觀察不同期限分割方法的性能，性能指標為滿足期限時的失效代價。令k為成功滿足調(diào)度期限的仿真集合，分配于算法的權(quán)重代價計算為：

Costw=∑kCosto(k)/SR

(12)

式中:Costo(k)為滿足期限時得到的代價;SR為調(diào)度成功率。

如圖4所示，可得到不同策略具有不同的變化趨勢。如：W策略在網(wǎng)絡空間工作流中性能最差，而在基因工作流中則擁有最低的代價； EL策略在網(wǎng)絡空間工作流和基因工作流中的趨勢相似。這主要是源于工作流在結(jié)構(gòu)、規(guī)模、計算和通信需要等方面的特征均有所不同。綜合來看，EWL策略在不同的工作流結(jié)構(gòu)中均具有較好的性能，源于該策略同步考慮了層次中任務的數(shù)量和層次的長度。因此，下文實驗中算法WSCO-DD的期限分割方法將應用EWL策略。同時，部分策略間的代價差異雖然較小，但可以看出期限分割方法仍對工作流的執(zhí)行代價會產(chǎn)生實質(zhì)影響[15]。

實驗2觀察算法執(zhí)行代價和調(diào)度成功率。選擇基礎(chǔ)設(shè)施即服務云關(guān)鍵路徑算法(Infrastructure as a Service, IaaS) Cloud Partial Critical Paths, IC-PCP)、聯(lián)合誘導傳輸算法(Joint Induce Transmission, JIT)和比例截止日期約束算法(Proportion Deadline Constraint,

(a) 基因工作流

(b) 網(wǎng)絡空間工作流

PDC)3種算法作為比較算法，結(jié)果如圖5～6所示?？梢钥闯?，在所有工作流中，JIT的代價是最高的，而WSCO-DD算法幾乎在所有工作流中擁有最低代價和最高的調(diào)度成功率。只有少數(shù)情況下，如極嚴格期限約束時的CyberShake和Epigenomics工作流，WSCO-DD算法才出現(xiàn)無法調(diào)度部分工作流的情形。IC-PCP算法在嚴格期限下?lián)碛凶畈畹恼{(diào)度成功率，期限的寬松會增加所有算法的調(diào)度成功率，這是由于任務的執(zhí)行擁有了更長的時間限制。在Epigenomics中即使較寬松的期限，IC-PCP仍擁有最高的失效率，滿足期限的調(diào)度僅占25%。JIT在多數(shù)期限條件下性能均較好，調(diào)度成功率接近100%。然而，JIT的執(zhí)行代價過高，未均衡考慮代價與調(diào)度成功率間的平衡，這主要是由于該算法并未優(yōu)化實例目標選擇。

(a) 基因工作流

(b) 網(wǎng)絡空間工作流

5 結(jié) 語

為了解決動態(tài)商業(yè)云環(huán)境中的工作流調(diào)度優(yōu)化，提出一種工作流調(diào)度代價優(yōu)化算法。算法側(cè)重于解決期限在工作流結(jié)構(gòu)上的分割問題，并在此基礎(chǔ)上，通過多階段調(diào)度方案求解，實現(xiàn)了期限約束下的工作流最優(yōu)調(diào)度。實驗結(jié)果證明WSCO-DD算法執(zhí)行代價和調(diào)度成功率均具有較好表現(xiàn)。

(a) 基因工作流

(b) 網(wǎng)絡空間工作流