劉曉霞, 李 芳

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

0 引 言

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

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

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

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

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

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

2 系統(tǒng)模型

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

在實(shí)例pj上執(zhí)行任務(wù)ti的代價(jià)為：

TaskCostpjti=wpjti/Nt×cj

(1)

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

(2)

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

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

WSCO-DD算法分為4個(gè)階段：

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

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

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

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

3.1 工作流分層

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

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

(3)

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

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

(4)

3.2 期限分割

3.2.1初始值估算

對(duì)于每個(gè)層次的初始估算期限計(jì)算為：

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

(5)

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

(6)

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

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

3.2.2期限分割方法

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

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

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

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

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

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

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

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

圖1 工作流示例

R算法該算法對(duì)期限進(jìn)行隨機(jī)分割，不作說(shuō)明。

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

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

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

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

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

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

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

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

(7)

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

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

Tsd(l)=InitialTsd(l)+

(πdeadline×|InitialTsd(l)|)

(8)

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

表1 預(yù)算分割情況

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

圖2 不同策略組合

3.3 任務(wù)選擇

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

(9)

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

3.4 實(shí)例選擇

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

(10)

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

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

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

4.1 實(shí)驗(yàn)配置

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

表1 資源實(shí)例類型

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

(11)

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

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

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

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

4.2 實(shí)驗(yàn)分析

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

Costw=∑kCosto(k)/SR

(12)

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

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

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

(a) 基因工作流

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

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

(a) 基因工作流

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

5 結(jié) 語(yǔ)

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

(a) 基因工作流

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