[發明專利]一種云工作流調度方法及系統

有效

• 申請號: 202110404960.4
• 申請日: 2021-04-15
• 公開（公告）號: CN113064710B
• 公開（公告）日: 2022-09-09
• 發明（設計）人: 夏元清;楊立文;葉玲娟;詹玉峰;戴荔;孫中奇;翟弟華;張金會;劉坤;郭澤華;閆莉萍;鄒偉東;崔冰
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京高沃律師事務所 11569
• 代理人: 韓雪梅

1.一種云工作流調度方法，其特征在于，包括：

獲取用戶提交的工作流；所述工作流包括n個任務，且所述任務與所述任務之間具有數據依賴關系或控制依賴關系；

計算所述工作流中每個任務的優先級；所述優先級為具有寬度變化趨勢的概率秩；

根據所述任務的優先級，計算每個所述任務的子截止時刻；

根據每個所述任務的子截止時刻，調用預存的服務實例集合、工作流調度模型以及前瞻性服務實例選擇策略，確定每個任務對應的服務實例；所述工作流調度模型的目標函數為在截止時間約束條件下確定工作流最小執行花費的函數；所述前瞻性服務實例選擇策略為根據隨后任務選擇的服務實例調整當前任務的服務實例的策略；所述隨后任務為所述當前任務執行后再執行的任務；

在執行根據每個所述任務的子截止時刻，調用預存的服務實例集合、工作流調度模型以及前瞻性服務實例選擇策略，確定每個任務對應的服務實例之前，還包括：

根據每個所述任務對應的優先級，對工作流中的任務進行非升序排序，并統計排序后的工作流的第一級連續入口任務、非第一級連續入口任務以及第一級連續入口任務的個數K；

所述根據每個所述任務的子截止時刻，調用預存的服務實例集合、工作流調度模型以及前瞻性服務實例選擇策略，確定每個任務對應的服務實例，具體包括：

確定每個所述任務的預測步長；其中，所述第一級連續入口任務的預測步長為a*K，所述非第一級連續入口任務的預測步長s為b，a與b均為正整數；

根據每個所述任務的預測步長，確定每個所述任務關聯的隨后任務的個數；

初始化最好的服務實例為在預存的服務實例集合中使所述當前任務完成時間最早的服務實例，閾值花費為無窮大；

判斷指定服務實例是否滿足當前任務的子截止時刻，若是則將所述當前任務關聯的s個隨后任務分別指派給能夠滿足每個所述隨后任務的子截止時刻同時使每個所述隨后任務的花費增加值最小的服務實例；若否則更換所述指定服務實例，并返回判斷指定服務實例是否滿足當前任務的子截止時刻步驟；

根據所述工作流調度模型，計算所述當前任務以及所述當前任務關聯的s個隨后任務對應的當前花費增加值；所述當前花費增加值為所述當前任務以及所述當前任務關聯的s個隨后任務被假設指派服務實例后增加的花費；

判斷所述當前花費增加值是否小于閾值花費，若是則將最好的服務實例更新為所述指定服務實例，并將所述閾值花費更新為當前花費增加值；

判斷是否遍歷完預存的服務實例集合中的每個服務實例，若否則更換所述服務實例，并返回判斷指定服務實例是否滿足當前任務的子截止時刻步驟；

將所述當前任務指派給最好的服務實例；

重復上述操作，直到每個任務都有指派的服務實例為止。

2.根據權利要求1所述的一種云工作流調度方法，其特征在于，所述計算所述工作流中每個任務的優先級，具體包括：

根據以下公式計算所述工作流中每個任務的優先級；

所述公式為：

其中，表示出口任務t_exit的概率秩，t_exit表示出口任務，表示任務t_i的參考執行時間，CU^*表示所有服務實例的最高處理能力；表示任務t_i的概率秩，是任務t_i的所有子任務，表示任務t_c的概率秩，表示任務t_i和任務t_c之間的傳輸時間，是屬于區間(0，1)的參數；表示從出口任務t_exit到任務t_i最長路徑上的任務數，稱為任務t_i的級別，表示屬于級別的任務的個數，稱為級別的寬度；是級別和級別的寬度比，稱為寬度變化趨勢，γ_c是任務t_c的布爾變量。

3.根據權利要求2所述的一種云工作流調度方法，其特征在于，所述根據所述任務的優先級，計算每個所述任務的子截止時刻，具體包括：

根據公式計算每個所述任務的子截止時刻；

其中，表示任務t_i的子截止時刻，D表示用戶定義的截止時間約束條件，t_entry表示入口任務。

4.一種云工作流調度系統，其特征在于，包括：

工作流獲取模塊，用于獲取用戶提交的工作流；所述工作流包括n個任務，且所述任務與所述任務之間具有數據依賴關系或控制依賴關系；

優先級計算模塊，用于計算所述工作流中每個任務的優先級；所述優先級為具有寬度變化趨勢的概率秩；

子截止時刻計算模塊，用于根據所述任務的優先級，計算每個所述任務的子截止時刻；

服務實例確定模塊，用于根據每個所述任務的子截止時刻，調用預存的服務實例集合、工作流調度模型以及前瞻性服務實例選擇策略，確定每個任務對應的服務實例；所述工作流調度模型的目標函數為在截止時間約束條件下確定工作流最小執行花費的函數；所述前瞻性服務實例選擇策略為根據隨后任務選擇的服務實例調整當前任務的服務實例的策略；所述隨后任務為所述當前任務執行后再執行的任務；

在執行根據每個所述任務的子截止時刻，調用預存的服務實例集合、工作流調度模型以及前瞻性服務實例選擇策略，確定每個任務對應的服務實例之前，還包括：

根據每個所述任務對應的優先級，對工作流中的任務進行非升序排序，并統計排序后的工作流的第一級連續入口任務、非第一級連續入口任務以及第一級連續入口任務的個數K；

所述根據每個所述任務的子截止時刻，調用預存的服務實例集合、工作流調度模型以及前瞻性服務實例選擇策略，確定每個任務對應的服務實例，具體包括：

確定每個所述任務的預測步長；其中，所述第一級連續入口任務的預測步長為a*K，所述非第一級連續入口任務的預測步長s為b，a與b均為正整數；

根據每個所述任務的預測步長，確定每個所述任務關聯的隨后任務的個數；

初始化最好的服務實例為在預存的服務實例集合中使所述當前任務完成時間最早的服務實例，閾值花費為無窮大；

判斷指定服務實例是否滿足當前任務的子截止時刻，若是則將所述當前任務關聯的s個隨后任務分別指派給能夠滿足每個所述隨后任務的子截止時刻同時使每個所述隨后任務的花費增加值最小的服務實例；若否則更換所述指定服務實例，并返回判斷指定服務實例是否滿足當前任務的子截止時刻步驟；

根據所述工作流調度模型，計算所述當前任務以及所述當前任務關聯的s個隨后任務對應的當前花費增加值；所述當前花費增加值為所述當前任務以及所述當前任務關聯的s個隨后任務被假設指派服務實例后增加的花費；

判斷所述當前花費增加值是否小于閾值花費，若是則將最好的服務實例更新為所述指定服務實例，并將所述閾值花費更新為當前花費增加值；

判斷是否遍歷完預存的服務實例集合中的每個服務實例，若否則更換所述服務實例，并返回判斷指定服務實例是否滿足當前任務的子截止時刻步驟；

將所述當前任務指派給最好的服務實例；

重復上述操作，直到每個任務都有指派的服務實例為止。