作業系統管理了系統的有限資源，當有多個進程（或多個進程發出的請求）要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（請求）來占用資源。這就是調度。目的是控制資源使用者的數量,選取資源使用者許可占用資源或占用資源。
基本介紹
- 中文名：調度算法
- 所屬領域：作業系統
調度算法,評價因素,吞吐量,CPU利用率,周轉時間,確定進程調度原則,調度算法分類,先來先服務(FCFS),輪轉法(Round Robin),多級反饋佇列算法,linux進程調度算法,
調度算法
在作業系統中調度是指一種資源分配，因而調度算法是指：根據系統的資源分配策略所規定的資源分配算法。對於不同的的系統和系統目標，通常採用不同的調度算法，例如，在批處理系統中，為了照顧為數眾多的段作業，應採用短作業優先的調度算法；又如在分時系統中，為了保證系統具有合理的回響時間，應當採用輪轉法進行調度。目前存在的多種調度算法中，有的算法適用於作業調度，有的算法適用於進程調度；但也有些調度算法既可以用於作業調度，也可以用於進程調度。
通常將作業或進程歸入各種就緒或阻塞佇列。
調度算法要求：高資源利用率、高吞吐量、用戶滿意等原則。
進程調度所採用的算法是與整個系統的設計目標相一致的：
1.批處理系統：增加系統吞吐量和提高系統資源的利用率;
2.分時系統：保證每個分時用戶能容忍的回響時間。
3.實時系統：保證對隨機發生的外部事件做出實時回響。
評價因素
吞吐量
單位時間內CPU完成作業的數量。
CPU利用率
從0%～100%。
周轉時間
評價批處理系統的性能指標。
Ti = 作業完成時刻 － 作業提交時刻
確定進程調度原則
在系統角度來說，公平性：每個進程（不論優先權）都有機會被運行；較大的吞吐量。
用戶角度：及時性：回響速度要快；較短的周轉時間：不應當讓用戶等待時間過長。
調度算法分類
先來先服務(FCFS)
先來先服務（FCFS, First Come First Serve）是最簡單的調度算法，按先後順序進行調度。
1. FCFS算法
按照作業提交或進程變為就緒狀態的先後次序，分派CPU； 當前作業或進程占用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。 在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。最簡單的算法。
2. FCFS的特點
比較有利於長作業，而不利於短作業。 有利於CPU繁忙的作業，而不利於I/O繁忙的作業。
輪轉法(Round Robin)
輪轉法(Round Robin)是讓每個進程在就緒佇列中的等待時間與享受服務的時間成正比例。
1. 輪轉法
將系統中所有的就緒進程按照FCFS原則，排成一個佇列。
每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。
在一個時間片結束時，發生時鐘中斷。
2. 時間片長度的確定
對回響時間的要求：T(回響時間)=N(進程數目)*q(時間片)
就緒進程的數目：數目越多，時間片越小
系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使回響時間，平均周轉時間和平均帶權周轉時間延長。
多級反饋佇列算法
多級反饋佇列算法時間片輪轉算法和優先權算法的綜合和發展。優點：2 為提高系統吞吐量和縮短平均周轉時間而照顧短進程。2 為獲得較好的I/O設備利用率和縮短回響時間而照顧I/O型進程。2 不必估計進程的執行時間，動態調節。
1. 多級反饋佇列算法2 設定多個就緒佇列，分別賦予不同的優先權，如逐級降低，佇列1的優先權最高。每個佇列執行時間片的長度也不同，規定優先權越低則時間片越長，如逐級加倍。2 新進程進入記憶體後，先投入佇列1的末尾，按FCFS算法調度；若按佇列1一個時間片未能執行完，則降低投入到佇列2的末尾，同樣按FCFS算法調度；如此下去，降低到最後的佇列，則按“時間片輪轉”算法調度直到完成。2 僅當較高優先權的佇列為空，才調度較低優先權的佇列中的進程執行。如果進程執行時有新進程進入較高優先權的佇列，則搶先執行新進程，並把被搶先的進程投入原佇列的末尾。
2. 幾點說明
I/O型進程：讓其進入最高優先權佇列，以及時回響I/O互動。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞佇列。
計算型進程：每次都執行完時間片，進入更低級佇列。最終採用最大時間片來執行，減少調度次數。 I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的佇列，以免每次都回到最高優先權佇列後再逐次下降。2為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先權；時間片用完時，降低優先權。
3.shortest job next
系統計算程式調用的時間，時間最短的先執行。
linux進程調度算法
linux核心的三種調度方法：
1. SCHED_OTHER 分時調度策略，
2. SCHED_FIFO實時調度策略，先到先服務
3. SCHED_RR實時調度策略，時間片輪轉
實時進程將得到優先調用，實時進程根據實時優先權決定調度權值，分時進程則通過nice和counter值決
定權值，nice越小，counter越大，被調度的機率越大，也就是曾經使用了cpu最少的進程將會得到優先調
度。
SHCED_RR和SCHED_FIFO的不同：
當採用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒佇列尾。放在佇列
尾保證了所有具有相同優先權的RR任務的調度公平。
SCHED_FIFO一旦占用cpu則一直運行。一直運行直到有更高優先權任務到達或自己放棄。
如果有相同優先權的實時進程（根據優先權計算的調度權值是一樣的）已經準備好，FIFO時必須等待該
進程主動放棄後才可以運行這個優先權相同的任務。而RR可以讓每個任務都執行一段時間。
SHCED_RR和SCHED_FIFO的相同點：
SHCED_RR和SHCED_FIFO都只用於實時任務。
創建時優先權大於0(1-99)。
按照可搶占優先權調度算法進行。
就緒態的實時任務立即搶占非實時任務。
所有任務都採用linux分時調度策略時。
1. 創建任務指定採用分時調度策略，並指定優先權nice值(-20~19)。
2. 將根據每個任務的nice值確定在cpu上的執行時間(counter)。
3. 如果沒有等待資源，則將該任務加入到就緒佇列中。
4. 調度程式遍歷就緒佇列中的任務，通過對每個任務動態優先權的計算(counter+20-nice)結果，選擇
計算結果最大的一個去運行，當這 個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在
就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。
5. 此時調度程式重複上面計算過程，轉到第4步。
6. 當調度程式發現所有就緒任務計算所得的權值都為不大於0時，重複第2步。
所有任務都採用FIFO時:
1. 創建進程時指定採用FIFO，並設定實時優先權rt_priority(1-99)。
2. 如果沒有等待資源，則將該任務加入到就緒佇列中。
3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用
cpu，該FIFO任務將一直占有cpu直到有優先權更高的任務就緒(即使優先權相同也不行)或者主動放棄(等
待資源)。
4. 調度程式發現有優先權更高的任務到達(高優先權任務可能被中斷或定時器任務喚醒，再或被當前運行
的任務喚醒，等等)，則調度程式立即在當前任務 堆疊中保存當前cpu暫存器的所有數據，重新從高優先權
任務的堆疊中載入暫存器數據到cpu，此時高優先權的任務開始運行。重複第3步。
5. 如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒佇列中刪除，加入等待佇列，此時
重複第3步。
所有任務都採用RR調度策略時
1. 創建任務時指定調度參數為RR，並設定任務的實時優先權和nice值(nice值將會轉換為該任務的時間片
的長度)。
2. 如果沒有等待資源，則將該任務加入到就緒佇列中。
3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用
cpu。
4. 如果就緒佇列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時將該任務放入就緒隊
列的末尾。重複步驟3。
5. 當前任務由於等待資源而主動退出cpu，則其加入等待佇列中。重複步驟3。
系統中既有分時調度，又有時間片輪轉調度和先進先出調度
1. RR調度和FIFO調度的進程屬於實時進程，以分時調度的進程是非實時進程。
2. 當實時進程準備就緒後，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。
3. RR進程和FIFO進程都採用實時優先權做為調度的權值標準，RR是FIFO的一個延伸。FIFO時，如果兩
個進程的優先權一樣，則這兩個優先 級一樣的進程具體執行哪一個是由其在佇列中的未知決定的，這樣導
致一些不公正性(優先權是一樣的，為什麼要讓你一直運行?),如果將兩個優先權一樣的任務 的調度策略都
設為RR,則保證了這兩個任務可以循環執行，保證了公平。
