[發明專利]一種基于任務復制的多復本容錯并行任務調度方法

有效

• 申請號: 201210225099.6
• 申請日: 2012-06-29
• 公開（公告）號: CN102799475A
• 公開（公告）日: 2012-11-28
• 發明（設計）人: 汪蕓;馬俊
• 申請（專利權）人: 東南大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/50
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 夏雪

1.一種基于任務復制的多復本容錯并行任務調度方法，包括如下步驟：

(1)確定任務優先級；采用以關鍵路徑構建優先級隊列的方法來確定任務的屬性優先級；

(2)預調度：首先根據關鍵路徑構造任務優先級隊列，假定處理器數量無限，每輪調度加入f+1個空處理器，首先利用多復本任務復制函數MST_AR()計算任務t_i在當前所有處理器上的最早開始時間優化值EST(t_i,p_j)，p_j為處理器編號，通過計算選擇空處理器和不選擇空處理器兩種情況下的最早開始時間的差值來獲得最早開始時間優化值OPT(t_i)，然后選擇EST(t_i,p_j)值最小的f+1個處理器預放置t_i的f+1個復本，以<t_i,OPT(t_i)>的格式記錄最早開始時間優化值；

(3)重調度：首先按照最早開始時間優化值排序，然后統計任務t_i在最早開始時間優化值集合中出現的次數z(t_i)，然后每輪調度加入z(t_i)個空處理器，調用MST_AR()函數計算任務t_i在當前所有處理器上的最早開始時間EST(t_i,p_j)，選擇開始時間最早的f+1個處理器來放置任務t_i的所有復本，從而完成任務調度。

2.根據權利要求1所述一種基于任務復制的多復本容錯并行任務調度方法，其特征在于：

在多復本任務復制函數MST_AR()中，利用MST_AR()函數計算任務t_i的在處理器p_j上的最早開始時間EST(t_i,p_j)時：

①任務t_i在處理器p_j上的最早開始時間取決于其所有前驅任務的數據到達時間與該處理器的可用時間，前驅任務的數據達到時間等于前(f+1)個復本的數據到達時間，但不需要等待該前驅所有復本的數據；

②若本地有前驅任務t_p的一個復本，則不需要等待t_p的其他復本；

預調度階段計算最早開始時間優化值中，每輪加入f+1個處理器，記錄處理器空閑狀態empty(t_i)，根據MST_AR()函數計算任務t_i在當前所有處理器上的最早開始時間EST(t_i,p_j)，將最早開始時間按照處理器的空閑狀態分為兩組并升序排列，兩組的差值就是任務t_i選擇空處理器獲得的最早開始時間優化值集合；

重調度階段，系統中處理器數量n有限，首先降序排序所有任務的最早開始時間優化值，選擇優化值最好的n個記錄，記為集合F，并統計任務t_i在最早開始時間優化值集合F中出現的次數z(t_i)，最后在每輪調度中，對于當前任務t_i加入z(t_i)個空處理器。