基本介紹
- 中文名：任務調度優先權
- 外文名：task scheduling priority
- 學科：計算機科學
- 定義：任務被調度運行時的優先權
- 有關術語：優先權、任務調度算法
- 領域：作業系統
任務調度,優先權的類型,任務調度算法,總結,
任務調度
任務調度是作業系統的重要組成部分，而對於實時作業系統，任務調度直接影響其實時性能。任務調度方式常規可分為：可打斷調度（實時系統基本功能）：關鍵防止優先權倒置；不可打斷調度：先來先服務，不可中斷。任務調度優先權即作業系統賦予任務的優先數，用於決定任務調度的先後順序。任務調度優先權不僅與任務調度方式有關，還有與優先權的類型和調度算法有關。
優先權的類型
每個進程都有相應的優先權，優先權決定它何時運行和接收多少 CPU 時間。Windows的優先權共 32 級，是從 0 到 31 的數值，稱為基本優先權別（Base Priority Level）。系統按照不同的優先權調度進程的運行，0-15 級是普通優先權，進程的優先權可以動態變化，高優先權進程優先運行，只有高優先權進程不運行時，才調度低優先權進程運行，優先權相同的進程按照時間片輪流運行。16-31 級是實時優先權，實時優先權與普通優先權的最大區別在於相同優先權進程的運行不按照時間片輪轉，而是先運行的進程就先控制 CPU，如果它不主動放棄控制，同級或低優先權的進程就無法運行。Linux系統的優先權從0-140，0-99表示實時進程，100-140表示非實時進程，與Windows相反，Linux優先權值越小，意味著級別越高，任務優先被核心調度。
靜態優先權
靜態優先權是在創建進程時確定的，且在進程的整個運行期間保持不變。一般地，優先權是利用某一範圍內的一個整數來表示的，例如，0～7 或 0～255 中的某一整數，又把該整數稱為優先數，只是具體用法各異：有的系統用“0”表示最高優先權，當數值愈大時，其優先權愈低；而有的系統恰恰相反。確定進程優先權的依據有如下三個方面：
(1)進程類型。通常，系統進程(如接收進程、對換進程、磁碟 I/O 進程)的優先權高於一般用戶進程的優先權。
(2)進程對資源的需求。如進程的估計執行時間及記憶體需要量的多少，對這些要求少的進程應賦予較高的優先權。
(3) 用戶要求。這是由用戶進程的緊迫程度及用戶所付費用的多少來確定優先權的。靜態優先權法簡單易行，系統開銷小，但不夠精確，很可能出現優先權低的作業(進程)長期沒有被調度的情況。因此，僅在要求不高的系統中才使用靜態優先權。
動態優先權
動態優先權是指在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒佇列中的進程，隨其等待時間的增長，其優先權以速率 a 提高。若所有的進程都具有相同的優先權初值，則顯然是最先進入就緒佇列的進程將因其動態優先權變得最高而優先獲得處理機，此即FCFS 算法。若所有的就緒進程具有各不相同的優先權初值，那么，對於優先權初值低的進程，在等待了足夠的時間後，其優先權便可能升為最高，從而可以獲得處理機。當採用搶占式優先權調度算法時，如果再規定當前進程的優先權以速率 b 下降，則可防止一個長作業長期地壟斷處理機。
任務調度算法
任務調度算法可分為：
事件驅動調度算法：根據事件的先後以及任務的優先權安排任務的執行。如先來先服務調度算法。
時鐘驅動調度算法：一般用於周期任務。如基於時間片的輪轉調度算法，多級反饋佇列調度算法。
事件驅動調度：依賴外部硬體設備，通過產生中斷方式為任務調度提供信號。分兩種，集成事件驅動調度：中斷的優先權與任務的優先權相對應，中斷只有在其優先權高於正在執行的任務時才會被處理器回響。 非集成事件驅動調度：任務通過外部中斷啟動，中斷優先權與相關任務優先權沒有關係。
一種基於調度粒度的任務優先權計算方法
背景
近些年來，多核處理器快速發展的同時，也給任務調度帶來了新的挑戰，如何利用 高效的任務調度策略使多核處理器系統充分發揮其性能，已經是我們必須要解決的問題。 動態任務調度可以根據運行時情況動態地將任務分配到各個核心上，由於需要實時地收 集、存儲並分析狀態信息，動態調度的實施有一定的系統開銷，但這種開銷和付出通常是有 回報的。
比較經典的調度算法有Min-Min、Max-Min、MCT(Minimum Completion Time)、 MET(Minimum Execution Time)等算法。Min-Min算法實現簡單，執行時間較快。算法的思想是比較所有待調度的任務，優先選取最早完成時間最小的一個任務進行調度。缺點是如果任務集中存在過多執行時間比較小的任務，那么時間比較大的任務將無法得到及時執行。Max-Min算法類似於Min-Min算法，不同的是Max-Min算法首先調度最早完成時間最大的任務。缺點是完成時間較小的任務等待時間過長，影響執行效率，也可能造成負載不均衡。
步驟
將任務分配到最合適的處理器核心上是任務調度的核心問題，而任務優先權計算是任務分配的關鍵，任務優先權表明任務被優先調度的程度，因此本發明方法在計算任務 優先權時引入調度粒度，用來決定調度過程分配的任務數量，進而決定調度頻度。
(1)確定任務優先權
計算任務相對於一個確定核心的優先權Tipk，取所有核心上的最大值作為任務優 先級Tip:
m為核心數量，Tipk表示任務Ti相對於核心Pk的優先權；
(2)設定調度粒度
在計算任務1\相對於一個處理器核心P的任務優先權時，設定調度粒度，其中處 理器核心P的調度粒度定義為一次調度過程中為處理器核心P分配的任務數量，一次調度 過程是指一個處理器核心請求調度；調度算法為其分配任務的過程中，調度的任務數量等 於為每個處理器核心分配的任務數量之和，調度粒度為：
Ik=l*spkm-1
其中Ip表示處理器核心P的調度粒度，1表示粒度因子，spp表示處理器核心P的 處理速度；
(3)任務優先權計算細化
計算一個任務在所有處理器核心上的任務優先權Tip及任務等待時間和任務間通 信開銷因素：
其中PW1代表任務Ti的等待時間，PC1P代表平均通信開銷，Ip代表核心P的調度粒 度，Cip表示任務Ti的通信開銷；t表示當前時間，Tlt表示任務就緒時間。
總結
本發明方法首先計算一個 任務在所有處理器核心上的任務優先權，然後取其在所有處理器核心上任務優先權的最大 值作為該任務的優先權，在任務調度時優先調度任務優先權大的任務。在計算任務相對於 一個確定處理器核心的任務優先權時，綜合考慮任務等待時間、任務間通信開銷和調度粒度因素，其中任務等待時間因素可避免存在就緒任務長時間不被調度的現象；同時計算任務間的平均通信開銷，可以將通信開銷大的任務分配到相應的處理器核心上，以節省更多 的任務間通信開銷；同樣調度粒度通過粒度因子和處理器核心的處理速度來調節大小，對 於一個實際的處理器系統，處理器核心速度是確定的已知量，其中粒度大小要根據系統模 型而定，它起到將處理器核心的計算速度轉換為處理器核心的調度任務數量的作用，結合 三種因素計算任務優先權可充分發揮任務調度優勢，提高處理器效率，從而降低調度頻率， 減少調度消耗時間。
