[發明專利]一種基于時間片段的任務調度方法

有效

• 申請號: 201611113867.3
• 申請日: 2016-12-07
• 公開（公告）號: CN106598717B
• 公開（公告）日: 2019-06-11
• 發明（設計）人: 何俊樺;王艷;朱潔
• 申請（專利權）人: 陜西尚品信息科技有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于時間片段的任務調度方法，其特征在于，包括以下步驟：

步驟一：每當系統監測到有新任務到達或者有任務執行結束時，系統中的任務參數進行初始化；

步驟二：對任務拆分，并確定任務執行時間片段；

步驟三：確定任務的執行順序，并輸出任務調度表；

步驟四：系統實時更新任務調度表，按照時間片段的先后順序，依次控制各處理器執行任務；

其中，步驟一中每當系統監測到有新任務到達或者有任務執行結束時，系統中的任務參數進行初始化；系統中的任務總數為N，以1,2,...,N對系統中的任務進行編號，編號組成的集合表示為I，I＝{1,2,...,N}，則系統中所有任務的集合可以表示為T，T＝{T_i|i∈I}；b_i表示任務的到達時間，x_i表示任務的估計最少執行時間，d_i表示任務的執行時限，則集合T中任一任務T_i用T_i＝(b_i,x_i,d_i)表示；若任務T_i在b_i時刻到達，則它必須在接下來的d_i時間內完成，即截止時刻為b_i+d_i；

x_i為處理器在最壞情況下以最大頻率執行該任務時所需的時間，故而任務的實際最少執行時間y_i要比x_i小，設γ_i為實際執行時間估計系數，則有y_i＝γ_ix_i，0＜γ_i≤1，γ_i越小，系統中任務參數的不確定性越大；

步驟二中對任務拆分，并確定任務執行的時間片段；對任務集T中的所有任務，從第一個任務開始到第N個任務依次作如下映射：第1個任務T₁的到達時刻b₁映射到時刻τ₀，截止時刻b₁+d₁映射到時刻τ₁，滿足τ₁-τ₀＝d₁；第2個任務T₂的到達時刻b₂映射到時刻τ₁，截止時刻b₂+d₂映射到時刻τ₂，滿足τ₂-τ₁＝d₂；…；第N個任務T_N的到達時刻b_N映射到時刻τ_N-1，截止時刻b_N+d_N映射到時刻τ_N，滿足τ_N-τ_N-1＝d_N；t₁,t₂滿足t₁＝τ₀＜τ₁＜...＜τ_N＝t₂，于是時間間隔[t₁,t₂]就被τ₀,τ₁,...,τ_N分割成許多小段的時間片段；用μ來標識{τ₀,τ₁,...,τ_N}中的元素，μ∈U，U＝{0，1，…，N-1}，[t₁,t₂]內的一個時間片段可用[τ_μ,τ_μ+1]來表示，確保至少需要1個處理器就可以在[t₁,t₂]時間內完成任務集T里所有的任務；

系統中包含m個完全相同的處理器，每個處理器的運行頻率f₁,f₂,...,f_max(f₁＜f₂＜...＜f_max)，用運行頻率等級集合Q＝{1,2,...,l}來表示，其中1對應最小的運行頻率f₁，l對應最大的運行頻率f_max；所述處理器的電壓/頻率分別通過動態電壓頻率調節DVFS技術獨立地進行調整，多個處理器可以同時分別以不同的運行頻率等級執行不同的任務；

所述任務集T中的單個任務可以拆分成多個子任務來分步執行，再確定子任務將在哪個執行時間片段，以及執行時長和運行頻率等級；

用q表示處理器的一個運行頻率等級，q∈Q，把稱為負載分布系數，表示處理器將在時間間隔[τ_μ,τ_μ+1]上某一時長為的時間區間內以運行頻率等級q執行任務T_i，

有如下約束條件：

(1)一個任務一次只能被指派到一個處理器上被執行，于是有

(2)每個處理器在[τ_μ,τ_μ+1]內所能處理的最大負載為1，即在[τ_μ,τ_μ+1]內該處理器上一直都有任務在執行，而系統包含m個處理器，故系統在[τ_μ,τ_μ+1]內所能處理的最大負載即為m，于是有

處理器的標準化運行速率s與運行頻率f之間的關系為s＝f/f_max,f∈[f₁,f_max],s∈[0,1]，此時相應的功率由P(s^q)給出，于是在時間間隔[t₁,t₂]內系統的總能耗

所述步驟二中方法等價為一個目的變量和約束條件數量可控的有限維線性規劃問題，即求出所有任務在各時間片段內的負載分布系數使得系統在整個時間間隔[t₁,t₂]內的總能耗E(t₁,t₂)達到最小；

從而得到負載分布系數集合表示某一處理器將在時間間隔[τ_μ,τ_μ+1]中某一時長為的時間區間內以運行頻率等級q執行任務T_i；

步驟三中確定任務的執行順序，并輸出任務調度表；用1,2,...,m對所有處理器進行編號，編號組成的集合表示為K，K＝{1,2,...,m}；i∈I，表示任務編號；k∈K，表示處理器編號；q∈Q，表示運行頻率等級；在時間間隔[t₁,t₂]內的某一時間片段中，用起始系數表示處理器k在時刻開始以模式q運行任務T_i，用截止系數表示在時刻結束該任務的本次執行，具體按如下步驟執行：

(3-1)給所有任務在所有時間片段內的起始系數和截止系數均置0，向系統申請一個處理器用于執行任務，稱該處理器處于活躍態，其它暫未被申請過的處理器稱為空閑態，此時處于活躍態的處理器最大編號為k＝1；

(3-2)按照任務編號i遞增的順序，從第1個任務開始，依次為任務集T中的各任務確定起始系數和截止系數；對第1個任務，其截止系數賦值為從第2個任務開始一直到第N個任務，將前一任務的截止系數作為本任務的起始系數；

(3-3)此時處于活躍態的處理器最大編號為k，若前一個任務的截止系數加上本任務的負載分布系數之和不大于處理器最大編號k，則對所有的運行頻率等級q，本任務在處理器k上以運行頻率等級q執行時的截止系數設置為本任務的起始系數加上負載分布系數的和，本任務分配完畢，則返回步驟3-2，開始下個任務分配；

若前一個任務的截止系數加上本任務的負載分布系數之和大于處理器最大編號k，則將本任務在處理器k上以運行頻率等級q執行時的截止系數設置為1，說明已分配的處理器已經達到滿負載，故再向系統申請一個處理器；申請規則為：第1次申請的處理器其編號為1，第2次申請的處理器編號為2，……，第m次申請的處理器編號為m；若申請的次數超過任務執行模塊中處理器的最大數量，則說明系統出錯，本次任務調度結束，此時處于活躍態的處理器最大編號為k＝k+1；將本任務的負載分布系數減去本任務在處理器k-1上以運行頻率等級q執行時的截止系數與起始系數的差，作為本任務在處理器k上以運行頻率等級q執行時的截止系數；返回步驟3-2，開始下個任務分配；

(3-4)所有任務分配完畢后，輸出包含所有任務的起始系數和截止系數的一個集合該集合為任務調度表。

2.根據權利要求1所述基于時間片段的任務調度方法，其特征在于，步驟四中系統實時更新任務調度表，按照時間片段如[τ₀,τ₁]，[τ₁,τ₂]，……，[τ_N-1,τ_N]的先后順序，依次控制各處理器執行任務；在時間片段[τ_μ,τ_μ+1]內，根據和的值，任務執行模塊控制處理器k于時刻以運行頻率等級q開始執行任務T_i，并于時刻結束該本次任務的執行；

每個任務T_i結束時，任務執行模塊將該任務的結束信息及時反饋到開始的輸入端，當系統中所有任務執行完畢時，本次任務調度結束。