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

（大連東軟信息學院，大連116023）

0 引言

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

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

1 ISACW算法

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

云工作流調度架構如圖1 所示。

圖1 云工作流調度架構

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

圖2 云工作流程的DAG

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

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

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

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

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

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

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

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

2 討論與結果

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

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

實驗步驟描述如下：

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

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

步驟3：從數據庫中選擇DAG 作為模板。

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

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

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

步驟7：提交任務并結束模擬。

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

表1 任務計算量（MI）

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

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

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

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

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

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

3 結語

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