實例密集型云工作流的改進調(diào)度算法

周瑤，盛國軍，張益民，張澤瀚

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

0 引言

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

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

1 ISACW算法

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

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

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

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

圖2 云工作流程的DAG

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

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

步驟2：對輸入實例的任務(wù)進行分類：

（1）將vi添加到DAG 并標記vst和ved；

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

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

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

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

2 討論與結(jié)果

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

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

實驗步驟描述如下：

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

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

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

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

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

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

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

圖3 實驗中云工作流實例的模板

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

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

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

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

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

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

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

3 結(jié)語

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