[發明專利]一種基于調度粒度的任務優先級計算方法

在審

• 申請號: 201510523103.0
• 申請日: 2015-08-24
• 公開（公告）號: CN105069250A
• 公開（公告）日: 2015-11-18
• 發明（設計）人: 李靜梅;田喬;周智
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種基于調度粒度的任務優先級計算方法，能夠降低調度頻率，減少調度消耗時間。

背景技術

近些年來，多核處理器快速發展的同時，也給任務調度帶來了新的挑戰，如何利用高效的任務調度策略使多核處理器系統充分發揮其性能，已經是我們必須要解決的問題。動態任務調度可以根據運行時情況動態地將任務分配到各個內核上，由于需要實時地收集、存儲并分析狀態信息，動態調度的實施有一定的系統開銷，但這種開銷和付出通常是有回報的。

比較經典的調度算法有Min-Min、Max-Min、MCT(MinirnumCompletionTime)、MET(MinimumExecutionTime)等算法。Min-Min算法實現簡單，執行時間較快。算法的思想是比較所有待調度的任務，優先選取最早完成時間最小的一個任務進行調度。缺點是如果任務集中存在過多執行時間比較小的任務，那么時間比較大的任務將無法得到及時執行。Max-Min算法類似于Min-Min算法，不同的是Max-Min算法首先調度最早完成時間最大的任務。缺點是完成時間較小的任務等待時間過長，影響執行效率，也可能造成負載不均衡。

將任務分配到最合適的處理器內核上是任務調度的核心問題，而任務優先級計算是任務分配的關鍵，任務優先級表明任務被優先調度的程度，因此本發明方法在計算任務優先級時引入調度粒度，用來決定調度過程分配的任務數量，進而決定調度頻度。

發明內容

本發明的目的在于提供一種能夠降低調度頻率，減少調度消耗時間的基于調度粒度的任務優先級計算方法。

本發明的內容是這樣實現的：

(1)確定任務優先級

計算任務相對于一個確定內核的優先級T_ipk，取所有內核上的最大值作為任務優先級T_ip：

Tip=max0≤k≤m-1Tipk]]>

m為內核數量，T_ipk表示任務T_i相對于內核P_k的優先級；

(2)設定調度粒度

在計算任務T_i相對于一個處理器內核P的任務優先級時，設定調度粒度，其中處理器內核P的調度粒度定義為一次調度過程中為處理器內核P分配的任務數量，一次調度過程是指一個處理器內核請求調度；調度算法為其分配任務的過程中，調度的任務數量等于為每個處理器內核分配的任務數量之和，調度粒度為：

l_k＝l·sp_k0≤k≤m-1

其中l_p表示處理器內核P的調度粒度，l表示粒度因子，sp_p表示處理器內核P的處理速度；

(3)任務優先級計算細化

計算一個任務在所有處理器內核上的任務優先級T_ip及任務等待時間和任務間通信開銷因素：