實例密集型云工作流的改進調度算法

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

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

0 引言

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

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

1 ISACW算法

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

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

圖1 云工作流調度架構

在圖2 中，V={v1,v2,...,vn}是DAG 圖中所有頂點的集合，E={e1,e2,...,em}是一組DAG 圖中的所有有向邊的集合。每個邊（vi→vj）表示工作流過程的任務之間的序數關系。沒有父頂點的頂點稱為初始任務頂點，用vst表示，在圖2 中顯示為v1，沒有后續任務頂點的頂點稱為結束任務定點，用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的最新執行時間tsti和最早完成時間tedi；

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

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

2 討論與結果

實驗環境描述如下：Windows 8.1 操作系統，Eclipse 3.5，JDK 1.7 和CloudSim 3.0.3。

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

實驗步驟描述如下：

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

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

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

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

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

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

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

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

表1 任務計算量（MI）

表2 服務執行率和執行任務的成本

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

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

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

圖4 平均執行成本

圖5 平均執行時間

3 結語

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