[發明專利]云環境下基于階段劃分的數據密集型工作流調度方法

有效

• 申請號: 202010033432.8
• 申請日: 2020-01-13
• 公開（公告）號: CN111274009B
• 公開（公告）日: 2022-08-30
• 發明（設計）人: 陳俊宇;劉茜萍
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;H04L67/10
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 彭雄

1.一種云環境下基于階段劃分的數據密集型工作流調度方法，其特征在于，包括以下步驟：

步驟1，對工作流結構進行抽象：獲取工作流信息，根據工作流信息建立DAG圖，通過DAG圖來表示工作流，W＝T,D，W為需要調度的工作流，包含n個任務，T＝{t_i|i＝1…n}，T表示工作流W任務集合，t_i表示工作流W的第i個任務，D＝{d_ij|i,j＝1…n}，D表示工作流W中傳輸數據量的集合，d_ij表示t_i需要向t_j傳輸的數據量，傳輸時間大小為d_ij/bw，bw為t_i和t_j之間的傳輸帶寬；

步驟2，任務候選服務商定義：

云環境下有若干個在不同地域的服務商，每個服務商租用了一臺服務器，以利用其硬件資源來執行各種計算任務；工作流中的每個計算任務描述并不包含具體的處理細節，由多個候選服務商通過執行不同的算法來完成，相同的一個任務交由不同的服務商執行將會對應不同的執行時間；

每個任務有多個候選服務商；云工作流調度的過程就是決定每個任務應該交由哪個服務商完成也即調度至哪個服務器執行；

當d_ij0時，兩個任務之間需要直接的數據傳輸，而如果兩個任務選擇了相同的服務商，則數據傳輸時間為0，否則傳輸數據時間不可忽略；若某服務商只能處理單個任務，則該任務的輸入、輸出數據都必須在該服務商和其他服務商之間進行傳輸；

服務商集合S中有m個服務商s_p參與工作流的調度，p＝1…m，各候選服務商與待調度任務之間的關聯如下：ST＝{ST_p＝{t_i,et_pi|et_pi表示服務商s_p執行t_i的執行時間，t_i∈T，i∈{1…n}}，p＝1…m}，其中，ST表示ST_p的集合，ST_p表示服務商s_p能執行所有t_i的執行時間集合，n表示有n個任務，t_i,et_pi表示任務t_i和服務商s_p執行t_i的執行時間的對應關系；

步驟3，將工作流W劃分成多個階段進行調度，盡量使當前階段所有任務的完成時間最早；分階段調度則能相繼計算出每個階段的較優調度結果，進而得出最終的調度結果相對較優，由于是分階段進行調度，這樣的調度策略更適用于各個任務之間的傳輸時間相比較為平均的工作流；根據ST_p的具體情況，為任務確認候選服務商并為其選擇最佳服務商，直至所有任務分配完畢，調度結果為r_i即t_i的分配結果，滿足存在t_i,et_pi屬于ST_p這一條件，其中：s_p表示t_i最終選擇的服務商，rft_i表示t_i的實際完成時間，R表示所有任務的分配情況集合；

步驟4，工作流中各個任務的執行條件是其前驅任務都被執行完畢且數據傳輸至當前任務，工作流由數據依賴導出各任務之間潛在的時序前驅，故對工作流的分配階段劃分主要基于數據依賴開展，TS_u＝{t_u|t_u是第u階段的任務}，u＝1,2…l，TS_u表示第u階段的任務集合，|TS_u|表示第u階段的任務個數；

步驟5，任務調度：

步驟51，候選完成時間計算

針對某待分配的任務t_j，其候選服務商及對應執行時間集合表示為CS_j＝{s_p,ft_pj|s_p∈S，t_j∈T}，s_p表示服務商，S表示服務商集合，在若干個已分配的t_i指向待分配的t_j的情況下，對CS_j中每個服務商s_p計算t_j在該服務器下執行的完成時間ft_pj；

步驟52，計算得出當前階段每個任務被其候選服務商執行的完成時間，需要通過矩陣A_u(n*m)將數據進行排列以完成分配，A_u(n*m)＝[s_p，ft_pi]n*m，A_u(n*m)為第u階段所有待分配任務在不同候選服務商處執行后的完成時間所構成的矩陣；其中每行對應某任務在不同候選服務商上執行時的完成時間，且這些值按從小到大順序依次排列，ft_pi表示s_p執行t_i的完成時間；

步驟53，基于A_u(_n*m)確定參與分配的候選服務商FS_i和最小x列

首先需要通過A_u(n*m)確定第i列新增候選服務商集合FS_i，FS_i＝{s_p|s_p∈S}，|FS_i|表示該集合的大小，接下來需要找到滿足條件中最小的x，以保證參與分配的服務商個數超過該階段的任務數從而實現物理并行；

步驟54，基于FS_i和x開展當前階段的分配

基于步驟53得到的給出的參與分配的候選服務商FS_i和最小x列給所有任務分配到不同的服務商；觀察A_u(n*m)中第x列中和FS_x對應的所有服務商，并按ft_pi從小到大排序，排序結果為{s_p，ft_pi…}，其中s_p∈FS_x，選擇排序結果中最小的ft_pi，確認被當前服務商執行的任務是t_i，當前階段其余任務的候選服務商舍棄該s_p，觀察當前情況是否滿足篩選條件：剩余任務的候選服務商個數sum大于等于未分配任務個數，根據滿足篩選條件判斷剩余候選服務商是否存在可行解；

滿足條件即存在當前可行解，則更新矩陣，將矩陣中的t_i一行舍棄，并將t_i選擇的s_p從其他任務中舍棄，從步驟53開始繼續計算新矩陣的FS_i和x，然后執行步驟53中的篩選條件判斷，如果排序結果中的所有服務商篩選完畢還是無可行解，選定排序結果中完成時間最小的s_p，確認選擇該s_p的當前任務；當前階段其余任務舍棄該s_p，更新矩陣。