[發明專利]一種基于多處理器的任務調度方法

有效

• 申請號: 201611110809.5
• 申請日: 2016-12-02
• 公開（公告）號: CN106598716B
• 公開（公告）日: 2019-05-28
• 發明（設計）人: 王睿巋;劉濤;王思陽
• 申請（專利權）人: 陜西尚品信息科技有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于多處理器的任務調度方法，其特征在于，包括以下步驟：

步驟一：獲取系統參數，對每個模式下的任務進行區分并且排序；

步驟二：獲得最優的任務調度方法；

步驟三：檢驗調度方法的合理性，并對系統的每個模式進行任務調度；

其中，在計算機應用程序中存在多個模式，記為P_r(r＝1，…，n)，其中n表示模式的種類數，為有限正整數，MD任務為計算機應用程序中特定模式下才完成的任務，模式P_r對應一個MD任務集合R_r，計算機應用程序功能由模式之間的相互切換共同完成，當模式切換P_r→P_r+1未發生時，任務集合R_r中的任務按照順序周期性執行；當模式切換P_r→P_r+1發生時，任務集合R_r中的任務j必須在一個時間點之前完成，此時間點為截止時間，記為D_j；為了使得計算機應用程序正常運行，需要使計算機應用程序中多個模式進行相互切換；基于多處理器平臺的任務進行合理調度，使得每個模式的模式切換時延最小，在模式切換P_r→P_r+1發生時，必須保證在模式P_r下的任務在對應截止時間之前全部完成，并且不因模式切換而中斷，模式切換時延必須是有限長；MI任務為計算機應用程序中，不受模式切換影響，在任何模式下都會執行的任務，對于MI任務，不需要進行人為調度，只需要按照系統默認順序執行；

步驟一中獲取系統參數，對每個模式下的任務進行區分并且排序；系統獲取計算機應用程序系統所基于的多處理器的數目m，獲取計算機應用程序中不同的工作模式的種類數n，獲取每種模式下的任務集合R_r；按照任務截止時間早，任務先執行的規則對MD任務進行排序；

步驟二中獲得最優的任務調度方法，模式切換時延越小越好，模式切換P_r→P_r+1，具體步驟如下：(2-1)對MD任務的調度進行處理器匹配限制，每個MD任務都要分配給一個處理器并且每個處理器的利用率小于等于1，有其中y_ij為一個布爾型變量，取值為0或1，如果任務j被分配到處理器i，則y_ij取值為1；如果任務j沒有被分配到處理器i，則y_ij取值為0，M表示系統所有MD任務的集合；(2-2)對MD任務進行系統任務利用率限制，對于一個具體的計算機應用程序系統，完成這個應用程序的所有任務的利用率小于等于1，有其中U_j表示任務j的時間利用率，表示任務的執行時間與任務的執行周期之比，有C_j為任務j的執行時間，T_j為任務j的執行周期，I_i為分配到處理器i的MI任務的集合，m為系統中處理器的數量；(2-3)對模式切換時延的下界進行限制，模式切換P_r→P_r+1發生時，模式P_r對應的任務集合R_r中的任務j必須在截止時間D_j之前完成，對于集合M中的任一元素j，即任務，設其執行周期為T_j，用表示第i個處理器中的任務執行周期的最大值，則對于第i個處理器，可得M_i表示分配到處理器i的MD任務，在模式切換P_r→P_r+1發生的同時，如果模式P_r對應的任務集合R_r中的有新的任務j加入，并且MI任務也同時執行，把這種情況作為模式切換時延的另一個下界，用表示，對于第i個處理器，有：其中C_j表示任務j的執行時間，T_j表示任務j的執行周期，求解得到最小模式切換時延L_r和布爾型變量y_ij；(2-4)預處理模式切換P_r→P_r+1具體的調度方法，根據布爾型變量y_ij，若y_ij的取值為1，則把任務j被調度給處理器i；若變量y_ij取值為0，則表示任務j沒有被調度給處理器i。