一種多重約束下確保成功率的云工作流調(diào)度方法

張艮山 劉旭寧

(石家莊學(xué)院信息技術(shù)系 河北 石家莊 050035)

0 引 言

根據(jù)需求的不同，云計算可以動態(tài)地將資源提供至用戶任務(wù)，實例租用方式是即付即用的，這與傳統(tǒng)計算模式不同，其更為靈活的特征給云計算作為處理科學(xué)工作流任務(wù)以及實施工作流調(diào)度帶來了極大的便利。大規(guī)?？茖W(xué)工作流應(yīng)用的常規(guī)建模形式是圖論中的有向無環(huán)圖DAG，圖中頂點代表工作流中大量相互依賴或相互獨立的任務(wù)集。這些任務(wù)間或存在著直接關(guān)聯(lián)(執(zhí)行先后有嚴格次序)，或無直接關(guān)聯(lián)可并行執(zhí)行。為了滿足云工作流的服務(wù)質(zhì)量，工作流調(diào)度需要在既定約束條件下搜索有效調(diào)度方案，將工作流結(jié)構(gòu)中的各個任務(wù)映射和調(diào)度至云資源實例上，并優(yōu)化目標函數(shù)。

云計算按需提供和即付即用的資源使用方式使得目前的任務(wù)調(diào)度算法具有以下不足：1) 實例租用價格沒有利用更切合實際的商業(yè)云賬單模型；2) 實例利用時間相對固定；3) 在考慮多種約束條件的工作流調(diào)度問題時，所使用的啟發(fā)式算法或搜索算法時間復(fù)雜度較高，實施成本太大。針對1)，本文在設(shè)計工作流調(diào)度算法中應(yīng)用Amazon EC2的實例賬單價格模型，同時在已經(jīng)支付的賬單周期中，前一任務(wù)的空閑賬單時間仍可被其他調(diào)度任務(wù)所利用，以此節(jié)省任務(wù)執(zhí)行代價。針對2)，本文所考慮的場景中一旦實例空閑即可釋放，資源獲取更加靈活，資源利用也更加充分。針對3)，本文不僅同步考慮預(yù)算和期限的雙重約束，還同步優(yōu)化執(zhí)行效率和代價，設(shè)計了更加高效復(fù)雜度更低的調(diào)度算法。

1 相關(guān)工作

多目標工作流調(diào)度可劃分為兩種情形：單工作流調(diào)度、多工作流調(diào)度。單工作流調(diào)度不適合云計算環(huán)境，與云計算的使用特征不符。單工作流調(diào)度目前主要體現(xiàn)在以下幾種類型：1) 在期限約束下優(yōu)化執(zhí)行代價。文獻[1]基于任務(wù)副本方法設(shè)計了期限約束下的工作流調(diào)度代價最優(yōu)化算法。文獻[2]設(shè)計了期限約束的動態(tài)代價啟發(fā)式調(diào)度算法，在公有云環(huán)境中進行了單個工作流的調(diào)度優(yōu)化。文獻[3-4]分別采用無啟發(fā)式和搜索式方法進行了工作流調(diào)度優(yōu)化。2) 在預(yù)算約束下優(yōu)化執(zhí)行時間。文獻[5-7]均設(shè)計了滿足預(yù)算約束的啟發(fā)式算法最小化執(zhí)行時間。文獻[8]設(shè)計的SABA算法是一種考慮安全與預(yù)算感知的工作流調(diào)度算法，在實現(xiàn)安全調(diào)度的同時提高了調(diào)度效率。以上兩種研究類型均屬于單約束單目標，此時調(diào)度方案的求解模型相對比較簡單，但其缺陷在于僅在單方面從效率或代價方面進行任務(wù)調(diào)度優(yōu)化，而云環(huán)境下的調(diào)度問題中這兩個因素是并存的，必須同步考慮。3) 同步實現(xiàn)執(zhí)行時間和執(zhí)行代價最優(yōu)。部分研究試圖在工作流調(diào)度中實現(xiàn)時間和代價的平衡。文獻[9]根據(jù)Critical-Path-First機制，通過工作流的擴展與壓縮來實現(xiàn)目標優(yōu)化。文獻[10]則利用帕累托的概念實現(xiàn)兩個指標優(yōu)化。同樣地，文獻[11]通過設(shè)計一種反映偏好的有效因子，實現(xiàn)了工作流執(zhí)行效率和代價優(yōu)化。但是以上工作多數(shù)為多約束下的單目標指標優(yōu)化或不做約束下同時優(yōu)化兩個指標。4) 預(yù)算與期限多約束。文獻[12]利用搜索機制對任務(wù)重分配，實現(xiàn)了一種雙約束調(diào)度算法。文獻[13]以自適應(yīng)混合啟發(fā)式算法對混合云環(huán)境中的工作流調(diào)度問題進行求解。文獻[14]提出了宏觀多工作流調(diào)度和微觀單工作流調(diào)度算法。文獻[15]提出多個工作流結(jié)構(gòu)下?lián)碛薪刂箷r間約束的吞吐量優(yōu)化調(diào)度算法，可以一定程度保證工作流的完成比例。文獻[16]則在資源分配過程中同樣采用了任務(wù)優(yōu)先級機制進行多工作流調(diào)度。以上研究方法的問題在于：(1) 考慮代價優(yōu)化時的資源定價多是固定定價，而非目前商業(yè)云所通用的云帳單模型，因此在進行目標優(yōu)化時得到的任務(wù)調(diào)度方案不一定能夠真正優(yōu)化調(diào)度代價；(2) 調(diào)度策略中所用的資源相對固定，無法反映云資源特有的彈性提供環(huán)境。

2 系統(tǒng)模型

工作流廣泛應(yīng)用于復(fù)雜分布式科學(xué)計算建模問題，有向無環(huán)圖DAG是工作流的最常用抽象工具。利用DAG抽象，一個工作流可定義為G=(T,E)，T={t0,t1,…,tn}為頂點任務(wù)集，E={ei,j|ti,tj∈T}為邊集，即任務(wù)依賴。邊ei,j∈E(ti,tj∈T)代表兩個任務(wù)ti和tj之間的有向邊的偏序約束，此時，任務(wù)ti為tj的父親，任務(wù)tj為ti的子代任務(wù)。

本文考慮的場景為IaaS云服務(wù)模型，IaaS通過提供包括不同CPU、內(nèi)存、存儲、網(wǎng)絡(luò)帶寬的實際類型來提供云服務(wù)，服務(wù)按照不同定價使用。本文在算法設(shè)計中考慮了Amazon EC2的云資源實例，以最小賬單時間租用，若實際使用時間小于賬單時間，仍按賬單時間付費。令實例集合為P={p0,p1,…,pn}。

pred(ti)={tj|(tj,ti)∈E}

(1)

任務(wù)ti的所有直接子任務(wù)可表示為：

succ(ti)={tj|(ti,tj)∈E}

(2)

如圖1所示的工作流結(jié)構(gòu)中，任務(wù)t8的父親任務(wù)為t5、t6和t7，任務(wù)t1的子任務(wù)為t2、t3和t4。若一個任務(wù)沒有父親任務(wù)則為工作流的入口任務(wù)，若一個任務(wù)沒有子任務(wù)則為工作流的出口任務(wù)。圖中，任務(wù)t1為工作流的入口任務(wù)，任務(wù)t9為工作流的出口任務(wù)。換言之：

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

pred(tentry)=?

(3)

succ(texit)=?

(4)

工作流的完成時間稱為調(diào)度長度或makespan，表示為Lms。由于出口texit是整個工作流執(zhí)行的最后一個任務(wù)，可以認為該任務(wù)的最終完成時間即為工作流的調(diào)度長度。因此，其可以表述如下：

Lms=FT(texit)

(5)

式中：FT(texit)為工作流最后一個任務(wù)texit的完成時間。

工作流結(jié)構(gòu)是目前科學(xué)計算領(lǐng)域中最常用的任務(wù)結(jié)構(gòu)形式，它定義了任務(wù)的觸發(fā)順序和觸發(fā)條件，直接關(guān)聯(lián)的任務(wù)間必須按照先后次序進行部署，無直接關(guān)聯(lián)的任務(wù)則可以并行執(zhí)行。而作為最常用的工作流結(jié)構(gòu)表示模型，本文采用的有向無環(huán)圖DAG結(jié)構(gòu)則較為明確的定義的了工作流的結(jié)構(gòu)特征，其開始任務(wù)和結(jié)束任務(wù)均可以在DAG中明確表示。在設(shè)計工作流任務(wù)調(diào)度算法過程中，有向無環(huán)圖DAG的存儲方式和編程表達也比較有利于進行實驗環(huán)境的搭建和性能測試。

令Ci,j表示任務(wù)ti和tj之間數(shù)據(jù)傳輸?shù)臅r間：

(6)

如果兩個任務(wù)ti和tj調(diào)度到相同的實例上(即pi=pj)，則任務(wù)間的數(shù)據(jù)傳輸發(fā)生在本地機器上，通信代價基本為0。否則，通信時間為數(shù)據(jù)傳輸量data與數(shù)據(jù)中心平均帶寬β間的比值。

ti的最早開始時間EST計算為：

(7)

式中：wtj表示任務(wù)tj在最快實例上的執(zhí)行時間。任務(wù)ti在實例pj上的執(zhí)行代價為：

(8)

式中：cj表示在單個時間周期里任務(wù)執(zhí)行時租用實例pj的代價；Nt表示租用實例的時間周期數(shù)量。工作流中所有任務(wù)的執(zhí)行總代價可表示為：

(9)

該代價模型應(yīng)用了Amazon EC2的實例賬單價格模型，同時在已經(jīng)支付的賬單周期中，前一任務(wù)的空閑賬單時間仍可被其他調(diào)度任務(wù)所利用(取式(8)中上限整數(shù)部分)，以此節(jié)省任務(wù)的總體執(zhí)行代價。

3 預(yù)算/期限感知調(diào)度算法

為了同時滿足預(yù)算和期限約束，并在調(diào)度長度和調(diào)度代價上取得同步優(yōu)化的效果，BDAS算法將劃分為五個階段實行。1) 工作流結(jié)構(gòu)分層：將工作流劃分為若干不具有相關(guān)性的包任務(wù)，稱之為層次level；2) 預(yù)算分配：利用某種策略將總體預(yù)算B分配至每個level中；3) 期限分配：將總體截止時間D分割并在不同level間進行分配，每個level得到層次期限；4) 任務(wù)選擇：根據(jù)就緒隊列中待執(zhí)行任務(wù)的優(yōu)先級，選擇調(diào)度任務(wù)；5) 實例選擇：以時間和代價的均衡性作為參考，選擇最優(yōu)實例。

3.1 工作流分層

由于工作流結(jié)構(gòu)中的任務(wù)或者具有直接相關(guān)性，或者不具備直接關(guān)聯(lián)。那么，工作流分層的目的就是通過分離或?qū)θ蝿?wù)進行劃分，使得在同一個層次中的任務(wù)不具有相關(guān)性，以此盡可能最大化任務(wù)執(zhí)行的可并行程度，以此節(jié)省任務(wù)調(diào)度的時間，而具有直接關(guān)聯(lián)的任務(wù)則必須依據(jù)先后關(guān)系執(zhí)行。這樣，每個層次即可考慮為一個包括若干不相關(guān)任務(wù)的包任務(wù)。本文利用一種期限底部分層的方法將任務(wù)劃分至不同的層次中。將任務(wù)ti的層次描述為從ti至texit間路徑邊的最大值。那么，任務(wù)texit的層次將總為1。而其他任務(wù)則有：

(10)

所有任務(wù)根據(jù)其分層可劃分至任務(wù)分層集合TLS中，則：

TLS(l)={ti|L(ti)=l}

(11)

式中：l表示層次，l∈{1,2,…,L(tentry)}。

3.2 預(yù)算分配

預(yù)算分配的思想是將全局預(yù)算B在不同層次中進行分配，在考慮分配至一個層次的可用子預(yù)算subB(l)的情況下將任務(wù)調(diào)度至實例上，其優(yōu)勢是可以將除去已經(jīng)使用后的全部預(yù)算按層次全部預(yù)留至下層任務(wù)。先將預(yù)算B全部分配給tentry，tentry調(diào)度完成后將剩余預(yù)算分配至下一層任務(wù)。將分配至一個層次上的子預(yù)算稱為層次預(yù)算，預(yù)算分配策略是將預(yù)算分配至最早的層次上，然后將未使用的剩余預(yù)算繼續(xù)分配至下一層次上，表示如下：

(12)

式中：TaskCostti由式(8)定義。將剩余預(yù)算定義為調(diào)度層次l中的所有任務(wù)后的剩余費用值。

3.3 期限分配

期限分配階段的目標是將初始定義的整體截止時間在劃分后的工作流不同層次上進行分配，即將整體的截止時間約束分割成不同層次間的子截止時間的約束。換言之，若在所分配的子期限內(nèi)層次中的所有任務(wù)可以保證完成，則整體截止時間同樣可以得到滿足。策略需要考慮每個層次的執(zhí)行時間以及層次中任務(wù)的數(shù)量，從而得到更低的代價。一旦任務(wù)被劃分入各自層次后，每個層次中的任務(wù)即可按比例從整體期限D(zhuǎn)中分配相應(yīng)子期限。令subD(l)表示層次期限，即分配至每個層次l的子期限。為了滿足整體期限，需要確保每個層次中的每個任務(wù)在其分配的子期限內(nèi)完成。每個層次l的初始估計期限計算為：

(13)

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

(14)

式中：pred(ti)為ti的父任務(wù)集;wti為ti的最小執(zhí)行時間;l為父任務(wù)ti的層次。tentry沒有父親任務(wù)，故其ECT=0。

計算層次期限值后，需要根據(jù)截止時間的比例和每個層次中任務(wù)的數(shù)量將期限在所有任務(wù)間進行非均勻分配。引入一個比例單元∝deadline定義為：

(15)

式中：|subD(l)|表示層次l的期限長度；|TSL(l)|表示每個層次中的任務(wù)數(shù)量。

定義期限因子DF為：

(16)

式中：subD(1)表示包括出口任務(wù)的層次。式(16)的分子部分表示剩余的期限，即總體截止時間與出口任務(wù)所在層次子期限之差值。

將每個層次的期限的長度更新為期限因子DF的函數(shù)：

subD(l)=DF×|subD(l)|×|TSL(l)|+subD(l)

(17)

可見，擁有越長任務(wù)執(zhí)行時間和越多任務(wù)數(shù)量的層次，將獲得更多的截止時間分配。

3.4 任務(wù)選擇

由于處于相同層次中的任務(wù)間不具有相關(guān)性，所有這部分任務(wù)可以并行同步執(zhí)行。算法執(zhí)行過程中，待執(zhí)行的就緒任務(wù)將被置入就緒隊列中，而從就緒隊列中選擇執(zhí)行任務(wù)的依據(jù)是最早開始時間EST?；谌蝿?wù)的最早開始時間對任務(wù)進行調(diào)度次序選擇，可以確保盡可能短的工作流任務(wù)完成時間，從而提高任務(wù)調(diào)度效率。BDAS算法中，任務(wù)將按層次執(zhí)行，這表明只有在前一層次中的所有任務(wù)得到調(diào)度后，其下層次中的任務(wù)才可以開始執(zhí)行。

對于某個任務(wù)是否為就緒任務(wù)的判斷依據(jù)為是否其所有父親任務(wù)已完成并已接收所有數(shù)據(jù)，若滿足該條件，該任務(wù)即可進入就緒隊列。同一層中的任務(wù)由于任務(wù)間均沒有依賴性，故可以同步并行執(zhí)行。而選擇任務(wù)的依據(jù)是根據(jù)就緒隊列中的任務(wù)的優(yōu)先級來決定，此時優(yōu)先級的定義依據(jù)為最早開始時間EST。ti的最早開始時間EST計算為：

因此，調(diào)度算法需要首先計算每個任務(wù)在實例上的EST，而最先開始執(zhí)行的任務(wù)也擁有最高的選擇優(yōu)先級，該任務(wù)也將被選為執(zhí)行的候選任務(wù)(該任務(wù)擁有最高的優(yōu)先級)。

3.5 實例選擇

處于以下狀況時需要進行實例選擇：1) 每個任務(wù)已被分配至一個層次中；2) 每個層次的預(yù)算和期限已被分配；3) 每個就緒任務(wù)的優(yōu)先級已被分配。實例選擇過程中，需要均衡任務(wù)的執(zhí)行時間和執(zhí)行代價。本文算法在進行實例選擇時將兼顧考慮到任務(wù)的執(zhí)行時間和執(zhí)行代價，通過設(shè)計的均衡函數(shù)選擇最佳的任務(wù)執(zhí)行實例，確保在截止時間和預(yù)算兩個不同的約束狀況下都能夠完成對任務(wù)的有效調(diào)度。

對于當(dāng)前任務(wù)ti，其在實例pj上的最早執(zhí)行時間表示為ECT(ti|pj)，該時間是任務(wù)在實例上完成的最早時間，由式(14)定義?；诖耍梢杂嬎惝?dāng)前任務(wù)的估計層次期限與任務(wù)在實例pj上的最早完成時間的差異：

(18)

式中：subDlti表示分配給包括任務(wù)ti所在層次的子期限；ECTmin表示在所有實例中得到的任務(wù)最小執(zhí)行時間。

(19)

式中：subBlti表示分配給包括任務(wù)ti所在層次的子預(yù)算；TaskCostmin表示ti在所有實例上執(zhí)行的最小代價(最優(yōu)代價)。

為了尋找最優(yōu)實例，算法利用Cost/Time均衡因子CTTF實現(xiàn)執(zhí)行代價與執(zhí)行時間的均衡。CTTF值可以調(diào)整當(dāng)前任務(wù)在所有實例上的Time值和Cost值。為了代價最小化，目前已有的算法會將任務(wù)調(diào)度至最便宜可用的實例上(最慢實例)，從而滿足其分配的子期限。然而，在這種策略下，任務(wù)執(zhí)行將花費更多時間，進而導(dǎo)致其子任務(wù)的EST出現(xiàn)延時。為了避免這種情況，在滿足期限的同時較貴的實例是更好的選擇，但又可能導(dǎo)致超過預(yù)算。因此，CTTF的作用即是在時間和代價間取得均衡。

利用式(18)和式(19)計算任務(wù)的Time和Cost值時，會出現(xiàn)以下四種不同的情況：

1)Cost>0，Time>0。此情況為最優(yōu)情形，其表明可以得到充足的預(yù)算進行工作流調(diào)度，同時，截止時間也相對寬松。當(dāng)分配預(yù)算和期限時，每個層次可以得到相對大的份額。因此，任務(wù)所在層次的子預(yù)算和子期限均較為充足，故Cost和Time值均為正值。

2)Cost≤0，Time>0。層次l分配的預(yù)算已被支付(subBlti=0)，因此，無法啟動新的實例，由于此時已無預(yù)算。另外一個可能的情形是當(dāng)前任務(wù)ti在實例pj上的代價高于剩余子預(yù)算(式(19)的分子)。若滿足以上兩種情況之一，則式(19)的值小于或等于0。

3)Cost>0，Time≤0。此時為較緊密的期限情形(實例計算能力較低，無法滿足任務(wù)層次分割的子期限)，導(dǎo)致式(18)中的ECT值大于或等于任務(wù)層次的子期限。若滿足此情況，式(18)的值變?yōu)樨撝祷?。

4)Cost≤0，Time≤0。此時為較緊密的期限和預(yù)算，即當(dāng)前的子預(yù)算和子期限分別小于TaskCost和ECT。對于任務(wù)ti，式(19)和式(18)均小于或等于0。均衡函數(shù)定義為：

(20)

具有最大CTTF值的實例將被選擇為執(zhí)行任務(wù)ti的實例。

4 實 驗

4.1 實驗配置

利用科學(xué)工作流調(diào)度仿真平臺WorkFloSim[13]進行仿真，所構(gòu)成的數(shù)據(jù)中心包括六種實例類型，實例類型的相關(guān)參數(shù)如表1所示。將不同實例類型間任務(wù)進行數(shù)據(jù)傳輸?shù)膸捲O(shè)為20 MB/s，實例的處理能力以MFLOPS計算度量，即資源每秒鐘可進行的百萬浮點操作數(shù)。此外，在實例租用價格方面，本文參考Amazon EC2的云資源實例定價機制，其定價利用以小時為單位的賬單機制。

表1 實例類型以及能力參數(shù)

選擇四種具有代表性且性能較被認可的云環(huán)境中的工作流調(diào)度算法與本文的BDAS算法進行性能比較，包括Hybrid算法[11]、MTCT算法[18]、CWFT算法[19]、SABA算法[8]。為了測試算法在處理不同類型的工作流結(jié)構(gòu)上的優(yōu)勢以體現(xiàn)算法的適應(yīng)性，選擇不同科學(xué)領(lǐng)域中的工作流結(jié)構(gòu)進行測試[20]，包括CyberShake工作流、EPIGENOMIC工作流、LIGO工作流、Montage工作流。其中：CyberShake和LIGO兩種工作流的特點是存儲需求較大，前者是地震科學(xué)中仿真工作流應(yīng)用類型，后者為物理學(xué)中引力波的工作流應(yīng)用類型；Epigenomic工作流屬于計算密集型，是生物信息學(xué)中的工作流應(yīng)用類型；Montage工作流屬于輸入/輸出密集型，是天文學(xué)中的工作流應(yīng)用類型。此外，CyberShake工作流也是數(shù)據(jù)密集型。為了表現(xiàn)不同規(guī)模的工作流，仿真過程中分別配置200、400和800個工作流任務(wù)進行測試。

為了測試算法對工作流執(zhí)行預(yù)算和期限的滿足程度，以一種靈活方式生成工作流的整體預(yù)算和期限值。具體方式如下：

D=minD+αD×(maxD-minD)

(21)

B=minB+αB×(maxB-minB)

(22)

式中：minD為所有任務(wù)均調(diào)度至處理能力最差(代價相應(yīng)最小)的實例上執(zhí)行算法得到的調(diào)度長度；maxB為此時算法得到的對應(yīng)調(diào)度代價；maxD為所有任務(wù)均調(diào)度至處理能力最強(代價相應(yīng)最大)的實例上執(zhí)行算法得到的調(diào)度長度；minB為此時算法得到的對應(yīng)調(diào)度代價；αD和αB分別表示處于0至1之間的期限因子和預(yù)算因子。通過式(21)和式(22)中設(shè)置期限和預(yù)算約束，可以確保算法尋求調(diào)度解時滿足此時給出的約束條件。實驗中分別設(shè)置αD、αB的取值為{0.1,0.3,0.5}進行測試，以此觀察算法在不同的期限和預(yù)算緊密程度下算法的適應(yīng)性。而在理論上，兩個因子取值增加，成功調(diào)度工作流概率應(yīng)用是有所提高的。

4.2 性能指標

為了測試算法的性能，以下指標被選取進行性能比較，包括：調(diào)度成功率、時間比率和代價比率。

調(diào)度成功率SR：該指標表示滿足預(yù)算和期限兩個約束條件時成功執(zhí)行的實驗次數(shù)與總仿真次數(shù)(nTot)的比值：

(23)

時間比率TR：該指標表示整體期限D(zhuǎn)與工作流調(diào)度的實際時間的比值：

(24)

代價比率CR：該指標表示整體預(yù)算B與工作流調(diào)度的實際代價間的比值：

(25)

顯然，TR和CR的取值若小于1，則說明算法得到的工作流調(diào)度沒有滿足期限和預(yù)算的約束條件。

4.3 實驗分析

圖2-圖5展示了五種算法得到的調(diào)度結(jié)果中的平均調(diào)度成功率SR。可以明顯地看出，本文算法相較其他四種對比算法在所有四種類型的工作流結(jié)構(gòu)中均得到了更高的調(diào)度成功率。換言之，BDAS算法得到的同時滿足預(yù)算和期限的調(diào)度結(jié)果次數(shù)是最多的。由于四種工作流的任務(wù)類型和結(jié)構(gòu)特征也有所差異，所有算法得到的平均調(diào)度成功率也不同。BDAS算法通過分層后的任務(wù)以及預(yù)算和期限的子分割機制，可以有效解決雙約束時的工作流調(diào)度問題，同時同步降低工作流的執(zhí)行時間和執(zhí)行代價。此外，還可以看到，若增加預(yù)算因子αB，工作流的各層次將擁有更多的可用預(yù)算，從而使得BDAS算法的平均調(diào)度成功率SR會進一步得到增加。對于αD=0.1所表達的較為緊密的截止時間，在四種工作流的多數(shù)實驗情形中，僅本文算法實現(xiàn)成功調(diào)度的可能性最大。

圖2 CyberShake工作流

圖3 Epigenomic工作流

圖4 LIGO工作流

圖5 Montage工作流

圖6是改變預(yù)算因子得到的時間比率TR指標情況，圖7是改變期限因子得到的代價比率CR指標情況。如指標的定義可知，如果TR大于1，則表明算法得到的工作流調(diào)度解的執(zhí)行時間Makespan是小于整體期限約束的，反之亦然。同樣對于代價比率也有同樣的結(jié)果。圖6表明，本文算法得到的工作流調(diào)度方案的執(zhí)行時間對于不同程度的預(yù)算因子，總可以滿足期限約束。然而，根據(jù)圖7的CR指標，若降低αD，本文算法的代價將超過預(yù)算。圖2-圖5給出的SR指標的含義是在算法同時滿足期限約束和預(yù)算約束時成功調(diào)度的工作流的比例大小。圖7所示的CWFT算法雖然在降低執(zhí)行代價方面表現(xiàn)不錯，但在圖6所示的TR指標結(jié)構(gòu)中卻無法滿足期限約束，其SR指標性能是所有算法中表現(xiàn)最差的。多數(shù)情況下，SABA算法均無法得到成功調(diào)度，即無法同時滿足兩個條件的約束，原因在于SABA算法進行任務(wù)調(diào)度并未控制執(zhí)行代價，雖然該算法在總體執(zhí)行時間優(yōu)化上性能是最好的，但其代價性能是最差的。

圖6 時間比率指標

圖7 代價比率指標

5 結(jié) 語

為了求解在期限和預(yù)算雙重約束條件上的云工作流調(diào)度解，本文提出了一種新的調(diào)度算法。算法將工作流調(diào)度過程劃分為五個子階段，通過科學(xué)工作流結(jié)構(gòu)的仿真實驗，證明了算法在調(diào)度成功率和執(zhí)行時間與執(zhí)行代價的同步優(yōu)化上較同類型算法的性能更優(yōu)。