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

在審

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

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

2.一種如權利要求1所述的基于局部路徑與截止期限分配的云工作流調度算法，其特征在于，所述云工作流調度算法主要包括WS-PCPDC算法、AssignParent算法、Costdecrease PathAssigning Algorithm算法、Fair PathAssigning Algorithm算法和Planning算法；

所述云工作流調度算法具體為：對于每個未調度任務t_i，令EST(t_i)表示任務t_i的最早開始時間，該時間是未考慮實際執行該任務的資源時得到的時間；由于云環境是異構環境，任務執行時間在不同資源間是變化的；數據傳輸時間取決于所選資源及資源間的傳輸帶寬，任務t_i的最小執行時間MET(t_i)和最小傳輸時間可分別定義為：

基于以上定義，最早開始時間可定義為：

其中，pred(t_i)表示t_i的父節點任務；

對于每個未調度任務t_i，令LFT(t_i)為整個任務DAG在截止時間D內保證完成時任務t_i能夠完成執行的最遲時間，則：

對于每個調度任務t_i，令SS(t_i)為執行t_i的所選資源，AST(t_i)為任務t_i在資源上的實際開始時間。

3.根據權利要求2所述的基于局部路徑與截止期限分配的云工作流調度算法，其特征在于，所述云工作流調度算法還包括WS-PCPDC算法的偽代碼，添加兩個傀儡節點至任務DAG中，計算所需參數值后，節點tentry和texit分配子期限，并將這兩個任務標記為已分配assigned節點，已分配節點表明該任務節點已經分配子期限，未分配子期限的節點稱為未分配unassigned節點；texit的子期限設置為截止期限D，出口任務在截止期限D內完成，對出口任務調用AssignParent算法，該算法的目標是為輸入節點的所有未分配父節點分配子期限，從出口任務texit開始分配可證為DAG中的所有任務分配子期限，AssignParent算法負責在所有任務間分配全局截止期限，調用Planning算法，用于在滿足子期限的情況下為每個任務選擇執行資源；

所述AssignParent算法偽代碼為：輸入一個已分配節點，并分配子期限至其所有父節點上，AssignParent算法要尋找終止于輸入的未分配節點的局部關鍵路徑。