[發明專利]一種基于局部路徑與截止期限分配的云工作流調度算法

在審

• 申請號: 201910523877.1
• 申請日: 2019-06-17
• 公開（公告）號: CN110287011A
• 公開（公告）日: 2019-09-27
• 發明（設計）人: 程實;李昊洋;趙赟;何金鳳;王則林
• 申請（專利權）人: 南通大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 朱小兵

本發明提供了一種基于局部路徑與截止期限分配的云工作流調度算法，屬于云計算技術領域。其技術方案為：一種基于局部路徑與截止期限分配的云工作流調度算法，包括兩個階段：期限分配與資源選擇兩個階段，期限分配階段中，全局任務DAG的截止期限在個體任務間進行分配，若每個任務可在其子期限內完成，則整個任務DAG可在截止期限內完成；資源選擇階段中，在滿足任務子期限的同時，為每個任務選擇最優資源完成任務調度。本發明的有益效果為：本發明的調度方法是將全局期限在所有工作流任務上進行分割，以得到任務的子期限，然后在實例提供時僅滿足子期限。

技術領域

本發明涉及云計算技術領域，尤其涉及一種基于局部路徑與截止期限分配的云工作流 調度算法。

背景技術

工作流結構廣泛應用于復雜計算問題建模，云計算特有的按需提供和付即用的定制資 源使用方式使其成為調度工作流的有效方法。與傳統批任務調度不同，工作流結構的任務 具有嚴格的邏輯執行次序，需要在滿足給定QoS約束的同時，實現了與資源間的映射。工 作流調度通常由選擇被調度任務和選擇提供實例兩個階段構成，兩階段決策對于是否能夠 滿足給定約束和全局調度代價均具有重要影響。傳統工作流調度方法僅注重執行效率/時 間，忽略了資源使用的費用，此時的調度問題在不同資源和不同調度方案下的執行時間和 代價均有所不同。因此，同步考慮用調度時間和代價更加符合云資源的使用環境。

為了解決期限約束時的工作流調度代價優化問題，本文設計的調度方法是將全局期限 在所有工作流任務上進行分割，以得到任務的子期限，然后在實例提供時僅滿足子期限即 可。

對于工作流調度過程的調度與提供兩個階段，給定資源集，調度階段的目標是決定任 務執行的最優序列和與用戶相應約束下的任務部署；提供階段的目標是為工作流內的任務 選擇資源類型和相應資源數量，并為任務執行預留資源。相關研究中，DBL和DTL算法是典 型的基于期限分配的啟發式調度算法。前者以down-top方式對任務進行劃分，后者則以 top-down方式對任務進行劃分。由于工作流可以有向無循環圖建模，故DBL將任務劃分為 不同層次，每個層次所包含的任務不具有依賴性；而DTL將任務劃分為不同路徑(作為同 步任務或簡單任務，同步任務定義為擁有一個以上父任務或子任務的任務)。為任務分配期 限時，全局期限以正比于每個層次的最小執行時間的方式在各層次間進行分割。然而，在 DBL算法，首先需要計算最快實例資源，然后再將期限與估算值之差以均勻分布方式在所有 層次間進行分配。DET算法將任務被分為兩種類型：關鍵和非關鍵任務。關鍵任務利用動態 規化進行調度，非關鍵任務則在關鍵任務間進行回填式調度，但該算法忽略了任務間的通 信時間。

另外，還有提出了云工作流調度算法PDC，算法將期限以正比于各層次中任務執行時間 的方式在層次間進行分割。最遲完成時間LFT算法，該算法也是將期限在各任務間進行分 割，并確保工作流在用戶定義期限條件完成下時任務可完成其執行的最早時間。與本文思 想相似，局部關鍵路徑算法MI)P，算法可以根據任務在工作流中所處的局部關鍵路徑對任務 進行分類，同時，期限根據定義的路徑時進行重分配。然而，算法在每個局部關鍵路徑PCP 執行后，需要重新計算最遲完成時間，開銷較大。基于動態代價最小的JIT算法，該算法 在期限約束下將聯合管道任務集建立為單個任務，以消除任務間的數據傳輸時間。然而， 該算法在任務執行實例的選擇上并非最優，有待改進。

如何解決上述技術問題為本發明面臨的課題。

發明內容

本發明的目的在于提供一種基于局部路徑與截止期限分配的云工作流調度算法。

本發明是通過如下措施實現的：一種基于局部路徑與截止期限分配的云工作流調度算 法，其中，所述云工作流調度算法是基于局部關鍵路徑和截止期限的云工作流調度算法包 括兩個階段：期限分配與資源選擇兩個階段，期限分配階段中，全局任務DAG的截止期限 在個體任務間進行分配，若每個任務可在其子期限內完成，則整個任務DAG可在截止期限 內完成；資源選擇階段中，在滿足任務子期限的同時，為每個任務選擇最優資源完成任務 調度。