[發明專利]減少CPU占用的多處理器上實時任務集資源預留方法

有效

• 申請號: 201310199824.1
• 申請日: 2013-05-24
• 公開（公告）號: CN103257900A
• 公開（公告）日: 2013-08-21
• 發明（設計）人: 吳以凡;趙備;高志剛;戴國駿
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 杜軍

1.?減少CPU占用的多處理器上實時任務集資源預留方法，包括實時任務集優化劃分、任務截止期與激活時間設置以及任務子集的資源預留參數優化，其特征在于：

所述的實時任務集優化劃分是在動態關鍵路徑劃分的基礎上，以資源優化使用為目標，使得滿足任務集可調度性的同時最小化CPU占用，其步驟如下：

Step?101:?初始化劃分結果P為空集；

Step?102:?使用動態關鍵路徑劃分方法對任務集V進行劃分，該劃分結果以P’={F_k}表示，其中執行流F_k表示任務集V的一個子集；

Step?103:?若劃分結果的關鍵路徑長度L大于任務集截止期D，則任務集不可調度；

Step?104:?取P’中任務執行時間之和最小的執行流F*，將F*從P’中移除；

Step?105:?取F*中未被訪問過的最早開始時間EST_i最小的任務T_i，將其從F*中移除；

Step?106:?取P’中尚未尋找過的任務執行時間之和最大的執行流F_k，尋找能置放T_i的最早的空閑時間段；

Step?107:?若未找到空閑時間段，且P’中仍有未尋找過的執行流，則返回Step?106；若未找到空閑時間段，且P’中所有執行流均被尋找過，則將T_i放回F*中的原位置；若找到空閑時間段，則將T_i放到該位置；

Step?108:?若F*中仍有T_i未被訪問過，則返回Step?105；

Step?109:?若F*不為空集，則將其加入劃分結果P；

Step?110:?若P’不為空集，則返回Step?104；

Step?111:?按劃分結果P將任務集進行劃分；

所述的任務截止期與激活時間設置是與數據傳輸時延相關聯的任務截止期與激活時間設置；其中，所述的各任務T_i的截止期d_i設置步驟如下：

Step?201：計算關鍵路徑長度與截止期之比U=L/D，其中L為關鍵路徑長度，D為任務集截止期；

Step?202：對所有結束任務，設置其截止期為D；

Step?203：選擇一個所有后繼任務的截止期已經被設置的任務T_i，設置d_i為其所有后繼任務T_j中最小的d_j-(C_j+?r_i,jDelay_i,j)/U值，其中Delay_i,j為數據傳輸時延，r_i,j為二元變量，當T_i和T_j被劃分在同一執行流中，其值為0，反之為1；

Step?204：若存在未被設置的任務，返回Step?202，否則設置結束；

所述的各任務T_i激活時間a_i設置步驟如下：

Step?301：對所有起始任務，設置其激活時間為0；

Step?302：選擇一個所有前驅任務的激活時間已經被設置的任務T_i，計與a_i同屬一個執行流的所有a_i的前驅任務T_j中最大a_j值為a’_i，計與a_i不屬于同一個執行流的所有a_i的前驅任務T_j中最大d_j+r_j,iDelay_j,i值為d’_i，設置a_i=max{a’_i,?d’_i}；

Step?303：若存在未被設置的任務，返回Step?302，否則設置結束。