[發明專利]一種面向邊緣計算環境基于多副本的任務調度方法和系統

有效

• 申請號: 202010147501.8
• 申請日: 2020-03-05
• 公開（公告）號: CN111381950B
• 公開（公告）日: 2023-07-21
• 發明（設計）人: 錢柱中;王甜甜;陸桑璐
• 申請（專利權）人: 南京大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 南京泉為知識產權代理事務所(特殊普通合伙) 32408
• 代理人: 許丹丹

1.一種面向邊緣計算環境基于多副本的任務調度方法，其特征在于，包括以下步驟：

定期測量和收集每個邊緣集群內任務的執行狀態，建立本集群的任務時間延遲因子分布概率模型，所述模型描述了集群的資源性能；

基于最短剩余處理時間原則和公平共享原則預估各作業可執行任務需要的副本數，包括：根據最短剩余處理時間原則，將所有作業按照剩余任務數越少優先級越高進行排序；從排序結果中選擇前面指定比例ε的作業平等共享整個系統的計算節點；將作業分得的并且可用的計算節點平均分配給該作業當前的就緒任務，任務分得的節點數為其預估副本數，作為該任務可執行副本數的上界；

基于各作業當前進度和集群的資源性能，采用迭代分配方式將各集群的空閑節點，根據預估的副本數，分配給各個任務；

將分配到節點的任務調度到相應的集群來執行；

其中，所述迭代分配方式為任務的預估副本分配執行節點，迭代中每一輪每個任務最多分配一個節點，每一輪中按如下步驟執行：

(1)對作業進行排序，將當前執行階段剩余任務數更少的作業排在前面；

(2)對一個作業j內的任務進行排序，使用表示在本輪分配之前的輪次中，任務l已經被分配的節點位置情況，本輪依據各任務在前面輪次中獲得的執行時間期望值由高至低排序，表示在的副本部署方案下任務l的執行時間；

(3)依次為任務分配節點。

2.根據權利要求1所述的面向邊緣計算環境基于多副本的任務調度方法，其特征在于，所述集群的任務時間延遲因子分布概率模型表示為：

j表示作業編號，表示任務l在集群k的執行時間，s_k表示集群k中任務可能經歷的延遲因子，被設為一個隨機變量，表示該任務的固有時長，表示獲取數據的傳輸時延。

3.根據權利要求1所述的面向邊緣計算環境基于多副本的任務調度方法，其特征在于，所述步驟(3)包括：

(3-1)計算任務l的執行時間閾值，設任務l的執行時間閾值為其中為任務l的固有時長，u(t)表示當前系統的節點利用率；

(3-2)當任務l分配到的節點數未超過其預估副本數，且其執行時間期望仍然高于閾值，為該任務分配一節點，該節點是當前所有空閑節點中該任務執行時間最優的節點，表示當前擁有空閑節點的集群集合，則是分配給任務l這一個節點所在的集群，表示任務l在集群k的執行時間，更新

(3-3)當任務l用完其預估副本數，或者其執行時間期望已低于設定的閾值，則不再為該任務分配節點；

(3-4)當當前調度周期內不再有任務需要分配節點時，退出此次迭代。

4.一種面向邊緣計算環境基于多副本的任務調度系統，其特征在于，包括作業管理器、資源管理器、集中分配服務器，所述作業管理器用于追蹤作業執行進度，將就緒任務集提交給集中分配服務器；所述資源管理器用于收集集群中任務的執行信息，為每個集群建立延遲因子分布模型，捕獲各集群資源狀態；所述集中分配服務器在接收作業和資源狀態后，在線分配在當前調度周期各任務的可用副本以及副本運行節點的位置，并將分配結果返回給作業管理器，由作業管理器將任務在相應的節點上啟動運行；其中所述集中分配服務器采用迭代分配方式將各集群的空閑節點，根據預估的副本數，分配給各個任務，所述預估的副本數根據以下方式得到：根據最短剩余處理時間原則，將所有作業按照剩余任務數越少優先級越高進行排序；從排序結果中選擇前面指定比例ε的作業平等共享整個系統的計算節點；將作業分得的并且可用的計算節點平均分配給該作業當前的就緒任務，任務分得的節點數為其預估副本數，作為該任務可執行副本數的上界；

其中，所述迭代分配方式為任務的預估副本分配執行節點，迭代中每一輪每個任務最多分配一個節點，每一輪中按如下步驟執行：

(1)對作業進行排序，將當前執行階段剩余任務數更少的作業排在前面；

(2)對一個作業j內的任務進行排序，使用表示在本輪分配之前的輪次中，任務l已經被分配的節點位置情況，本輪依據各任務在前面輪次中獲得的執行時間期望值由高至低排序，表示在的副本部署方案下任務l的執行時間；

(3)依次為任務分配節點。

5.根據權利要求4所述的面向邊緣計算環境基于多副本的任務調度系統，其特征在于，所述步驟(3)包括：

(3-1)計算任務l的執行時間閾值，設任務l的執行時間閾值為其中為任務l的固有時長，u(t)表示當前系統的節點利用率；

(3-2)當任務l分配到的節點數未超過其預估副本數，且其執行時間期望仍然高于閾值，為該任務分配一節點，該節點是當前所有空閑節點中該任務執行時間最優的節點，表示當前擁有空閑節點的集群集合，則是分配給任務l這一個節點所在的集群，表示任務l在集群k的執行時間，更新

(3-3)當任務l用完其預估副本數，或者其執行時間期望已低于設定的閾值，則不再為該任務分配節點；

(3-4)當當前調度周期內不再有任務需要分配節點時，退出此次迭代。