周瑤，盛國(guó)軍，張益民，張澤瀚

（大連東軟信息學(xué)院，大連116023）

0 引言

隨著云計(jì)算和網(wǎng)絡(luò)資源虛擬化技術(shù)的發(fā)展，越來(lái)越多的工作流任務(wù)在云環(huán)境中執(zhí)行，并且其調(diào)度方法已成為云計(jì)算領(lǐng)域的熱門主題[1]。文獻(xiàn)[2]提出了一種截止期約束任務(wù)的算法以最小化運(yùn)行成本，但該算法僅最小化了其中一個(gè)目標(biāo)。文獻(xiàn)[3]描述了云計(jì)算環(huán)境下任務(wù)調(diào)度中成本和截止期約束的重要性，并提出了相應(yīng)的算法。但是，所提出的模型和算法僅針對(duì)類似的資源。文獻(xiàn)[4]提出了BHEFT 算法，該算法充分考慮了用戶對(duì)成本預(yù)算和截止期的要求。但是，當(dāng)資源被分配時(shí)，全局資源搜索方法導(dǎo)致過(guò)多的時(shí)間成本。文獻(xiàn)[5]考慮了云環(huán)境下工作流的安全需求，提出了基于安全性和成本預(yù)算的云工作流調(diào)度方法，以最小化完成時(shí)間。在文獻(xiàn)[6]中，以風(fēng)險(xiǎn)概率和截止期因素為約束，提出了使云工作流的執(zhí)行成本最小化的粒子群優(yōu)化調(diào)度方法，但該方法主要針對(duì)單個(gè)工作流實(shí)例的執(zhí)行優(yōu)化，不適用于實(shí)例密集型工作流。Kianpisheh 等人[7]提出了一種調(diào)度算法，此算法在考慮用戶定義的最新限制和預(yù)算的同時(shí)最大化工作流執(zhí)行的可靠性。文獻(xiàn)[8]提出了DeadlineMDP 算法，將流程任務(wù)分為簡(jiǎn)單任務(wù)和同步任務(wù)，分解用戶指定的全局截止日期，然后根據(jù)不同的規(guī)則對(duì)工作流任務(wù)進(jìn)行調(diào)度。Topcuoglu 等人[9]提出了HEFT 算法，使工作流的完成時(shí)間最小化，算法根據(jù)任務(wù)數(shù)量和傳輸數(shù)據(jù)的大小對(duì)工作流中的任務(wù)進(jìn)行分級(jí)，優(yōu)先分配優(yōu)先級(jí)較高的任務(wù)，并選擇當(dāng)前具有最佳性能的空閑資源，以便能夠盡快完成任務(wù)。Abrishami 等人[10]提出了一種基于部分關(guān)鍵路徑的啟發(fā)式方法，該方法以截止期為工作流完成時(shí)間，利用反向迭代為每個(gè)活動(dòng)找到部分關(guān)鍵路徑，在部分關(guān)鍵路徑上為每個(gè)活動(dòng)設(shè)置子截止期，并在子期限的約束下為每項(xiàng)活動(dòng)選擇最便宜的服務(wù)。

本文在上述工作的基礎(chǔ)上，著重于減少整個(gè)執(zhí)行時(shí)間和云工作流任務(wù)的總成本，并提出了一種稱為ISACW（云工作流的改進(jìn)調(diào)度）的算法，該算法使用基于DAG 的云工作流模型。該算法采用關(guān)鍵路徑檢索和深度優(yōu)先搜索方法，根據(jù)DAG 模型考慮執(zhí)行時(shí)間的復(fù)雜度，動(dòng)態(tài)調(diào)整工作流任務(wù)的服務(wù)時(shí)間，降低云資源的使用成本。

1 ISACW算法

多云工作流引擎（CWE）通過(guò)鄰居互連形成分布式工作流實(shí)例過(guò)程調(diào)度網(wǎng)絡(luò)，并且每個(gè)CWE 具有稱為過(guò)程請(qǐng)求調(diào)度器的組件以接收和調(diào)度用戶工作流過(guò)程實(shí)例。CWE 從云服務(wù)注冊(cè)中心獲取該流程中每個(gè)工作流活動(dòng)的候選服務(wù)列表。

云工作流調(diào)度架構(gòu)如圖1 所示。

圖1 云工作流調(diào)度架構(gòu)

在圖2 中，V={v1,v2,...,vn}是DAG 圖中所有頂點(diǎn)的集合，E={e1,e2,...,em}是一組DAG 圖中的所有有向邊的集合。每個(gè)邊（vi→vj）表示工作流過(guò)程的任務(wù)之間的序數(shù)關(guān)系。沒(méi)有父頂點(diǎn)的頂點(diǎn)稱為初始任務(wù)頂點(diǎn)，用vst表示，在圖2 中顯示為v1，沒(méi)有后續(xù)任務(wù)頂點(diǎn)的頂點(diǎn)稱為結(jié)束任務(wù)定點(diǎn)，用ved表示，在圖2 中顯示為v8。

圖2 云工作流程的DAG

從開始任務(wù)vst到結(jié)束任務(wù)ved的所有路徑的時(shí)間約束等于整個(gè)工作流時(shí)間限制，這個(gè)原則可以確保每個(gè)任務(wù)的結(jié)束時(shí)間在指定的時(shí)間內(nèi)，以便使整個(gè)工作流實(shí)例在指定時(shí)間完成。為每個(gè)任務(wù)分配的時(shí)間不能少于任務(wù)的最短時(shí)間，以保證在適當(dāng)?shù)臅r(shí)間限制內(nèi)完成所有任務(wù)。預(yù)期的總結(jié)束時(shí)間按比例分配給每個(gè)任務(wù)。假設(shè)用戶期望的結(jié)束時(shí)間tue 是整個(gè)工作流實(shí)例的最后結(jié)束時(shí)間，用戶指定的總成本是Cu，可用服務(wù)資源的集合是CS={cs1,cs2,...,csn}，完成任務(wù)的時(shí)間是trd。

步驟1：輸入一組工作流實(shí)例WFIS={wfi1,wfi2,...,wfin}和用戶預(yù)期的結(jié)束時(shí)間tue。

步驟2：對(duì)輸入實(shí)例的任務(wù)進(jìn)行分類：

（1）將vi添加到DAG 并標(biāo)記vst和ved；

（2）使用DFS 方法搜索從vst到ved的關(guān)鍵路徑，并標(biāo)記路徑中的所有任務(wù)；

（3）標(biāo)記任務(wù)vi的最新執(zhí)行時(shí)間tsti和最早完成時(shí)間tedi；

步驟5：為每個(gè)就緒任務(wù)vi選擇最佳可用服務(wù)資源。

步驟6：在就緒隊(duì)列中執(zhí)行任務(wù)，調(diào)整每個(gè)任務(wù)的最新結(jié)束時(shí)間，以確保它有更大的可能性來(lái)獲得更低成本的服務(wù)資源。

2 討論與結(jié)果

實(shí)驗(yàn)環(huán)境描述如下：Windows 8.1 操作系統(tǒng)，Eclipse 3.5，JDK 1.7 和CloudSim 3.0.3。

有5 種不同類型的服務(wù)資源，每種服務(wù)類型有4個(gè)服務(wù)節(jié)點(diǎn)；生成總共1,500 個(gè)工作流程實(shí)例作為CWE 的輸入數(shù)據(jù)。每個(gè)工作流實(shí)例都遵循圖3 中所示的模板來(lái)模擬實(shí)例密集型任務(wù)。

實(shí)驗(yàn)步驟描述如下：

步驟1：初始化CloudSim 庫(kù)并在數(shù)據(jù)庫(kù)中創(chuàng)建流程模板。

步驟2：創(chuàng)建數(shù)據(jù)中心作為云資源的提供者，實(shí)驗(yàn)需要至少一個(gè)數(shù)據(jù)中心來(lái)運(yùn)行CloudSim 模擬。

步驟3：從數(shù)據(jù)庫(kù)中選擇DAG 作為模板。

步驟4：創(chuàng)建數(shù)據(jù)中心代理，創(chuàng)建虛擬機(jī)并將每個(gè)虛擬機(jī)添加到vmlist，然后將vmlist 提交給數(shù)據(jù)中心代理。

步驟5：創(chuàng)建1500 個(gè)工作流實(shí)例，每個(gè)實(shí)例對(duì)應(yīng)一個(gè)用戶ID，并將建立的任務(wù)添加到任務(wù)列表中。

步驟6：使用該算法執(zhí)行每個(gè)實(shí)例任務(wù)，并標(biāo)記一個(gè)任務(wù)的執(zhí)行時(shí)間和成本。

步驟7：提交任務(wù)并結(jié)束模擬。

圖3 實(shí)驗(yàn)中云工作流實(shí)例的模板

表1 任務(wù)計(jì)算量（MI）

表2 服務(wù)執(zhí)行率和執(zhí)行任務(wù)的成本

該實(shí)驗(yàn)將工作流實(shí)例的平均執(zhí)行時(shí)間和平均執(zhí)行成本作為評(píng)估標(biāo)準(zhǔn)。將所提出的ISACW 算法與常用的工作流調(diào)度算法Max-Min 和DeadlineMDP 調(diào)度算法進(jìn)行比較。

從圖4 可以看出，三種算法的平均執(zhí)行成本隨著用戶預(yù)期結(jié)束時(shí)間的增加而減小，ISACW 算法成本低于其他兩種算法，特別是當(dāng)用戶預(yù)期結(jié)束時(shí)間時(shí)差距明顯逐漸增加。實(shí)驗(yàn)通過(guò)DAG 圖調(diào)整時(shí)間和成本來(lái)確認(rèn)ISACW 算法的有效性。

如圖5 所示，三種算法的執(zhí)行時(shí)間增加了上一個(gè)預(yù)期的結(jié)束時(shí)間，但I(xiàn)SACW 算法的增加幅度小于其他兩種算法，ISACW 更有可能在用戶特定的時(shí)間內(nèi)以較小的成本完成所有任務(wù)。

圖4 平均執(zhí)行成本

圖5 平均執(zhí)行時(shí)間

3 結(jié)語(yǔ)

本文提出了一種名為ISACW 的云工作流調(diào)度算法。首先，分析了云工作流的執(zhí)行過(guò)程，指出了限制云工作流執(zhí)行性能的問(wèn)題。該算法考慮了任務(wù)執(zhí)行時(shí)間的復(fù)雜性，改進(jìn)了任務(wù)執(zhí)行時(shí)間和成本的計(jì)算方法。與MaxMin 算法和DeadlineMDP 算法相比，結(jié)果表明ISACW 算法在用戶預(yù)期的最晚時(shí)間完成任務(wù)，同時(shí)降低任務(wù)的使用成本，有效提高云工作流執(zhí)行的效率。