作業調度算法

在典型的設計中，一個任務有以下三種狀態：

正在運行（Running，正在CPU中執行）待命（Ready，等待執行）阻塞（Blocked，任務暫停，等待一個事件的發生，例如接收一組數據）

由於CPU在某個時間只能執行一個任務，大部分任務，在大部分時間，處於阻塞或待命狀態。可能會有大量項目在待命列表里等待執行，這取決於系統所需的任務數量以及調度器的類型。

通常情況下，對於簡單的時間觸髮式調度器來說，待命任務列表的數據結構的設計要儘可能縮短最壞情況下，程式在調度器關鍵部分的執行時間，以防止其他任務一直在待命列表中，無法及時執行。因此，在這種調度器中，應儘可能避免搶占式任務，甚至應該關閉調度器之外的所有中斷。當然，待命任務列表的數據結構也應根據這個系統需要的最大任務數量做進一步的最佳化。

先來先服務

先來先服務（FCFS, First Come First Serve）是最簡單的調度算法，按先後順序進行調度。

定義

按照作業提交或進程變為就緒狀態的先後次序，分派CPU；

當前作業或進程占用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。

在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。

適用場景

比較有利於長作業，而不利於短作業。

有利於CPU繁忙的作業，而不利於I/O繁忙的作業。

輪轉法

輪轉法(Round Robin)是讓每個進程在就緒佇列中的等待時間與享受服務的時間成正比例。

定義

將系統中所有的就緒進程按照FCFS原則，排成一個佇列。

每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。

在一個時間片結束時，發生時鐘中斷。

調度程式據此暫停當前進程的執行，將其送到就緒佇列的末尾，並通過上下文切換執行當前的隊首進程。

進程可以未使用完一個時間片，就出讓CPU（如阻塞）。

長度的確定

時間片長度變化的影響

過長－>退化為FCFS算法，進程在一個時間片內都執行完，回響時間長。

過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，回響時間長。

對回響時間的要求：T(回響時間)=N(進程數目)*q(時間片)

就緒進程的數目：數目越多，時間片越小

系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使回響時間，平均周轉時間和平均帶權周轉時間延長。

多級反饋佇列列算法

多級反饋佇列算法(Round Robin with Multiple Feedback)是輪轉算法和優先權算法的綜合和發展。

定義

設定多個就緒佇列，分別賦予不同的優先權，如逐級降低，佇列1的優先權最高。每個佇列執行時間片的長度也不同，規定優先權越低則時間片越長，如逐級加倍。

新進程進入記憶體後，先投入佇列1的末尾，按FCFS算法調度；若按佇列1一個時間片未能執行完，則降低投入到佇列2的末尾，同樣按FCFS算法調度；如此下去，降低到最後的佇列，則按“時間片輪轉”算法調度直到完成。

僅當較高優先權的佇列為空，才調度較低優先權的佇列中的進程執行。如果進程執行時有新進程進入較高優先權的佇列，則搶先執行新進程，並把被搶先的進程投入原佇列的末尾。

優點

為提高系統吞吐量和縮短平均周轉時間而照顧短進程。

為獲得較好的I/O設備利用率和縮短回響時間而照顧I/O型進程。

不必估計進程的執行時間，動態調節

幾點說明

I/O型進程：讓其進入最高優先權佇列，以及時回響I/O互動。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞佇列。

計算型進程：每次都執行完時間片，進入更低級佇列。最終採用最大時間片來執行，減少調度次數。

I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的佇列，以免每次都回到最高優先權佇列後再逐次下降。

為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先權；時間片用完時，降低優先權。

優先權法

優先權算法（Priority Scheduling）是多級佇列算法的改進，平衡各進程對回響時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。

靜態優先權

作業調度中的靜態優先權大多按以下原則確定：

由用戶自己根據作業的緊急程度輸入一個適當的優先權。

由系統或操作員根據作業類型指定優先權。

系統根據作業要求資源情況確定優先權。

進程的靜態優先權的確定原則：

按進程的類型給予不同的優先權。

將作業的情態優先權作為它所屬進程的優先權。

動態優先權

進程的動態優先權一般根據以下原則確定：

根據進程占用有CPU時間的長短來決定。

根據就緒進程等待CPU的時間長短來決定。

短作業優先法

短作業優先（SJF, Shortest Job First）又稱為“短進程優先”SPN(Shortest Process Next)；這是對FCFS算法的改進，其目標是減少平均周轉時間。

定義

對預計執行時間短的作業（進程）優先分派處理機。通常後來的短作業不搶先正在執行的作業。

SJF的特點

(1) 優點：

比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間；

提高系統的吞吐量；

(2) 缺點：

對長作業非常不利，可能長時間得不到執行；

未能依據作業的緊迫程度來劃分執行的優先權；

難以準確估計作業（進程）的執行時間，從而影響調度性能。

SJF的變型

“最短剩餘時間優先”SRT(Shortest Remaining Time)（允許比當前進程剩餘時間更短的進程來搶占）

“最高回響比優先”HRRN(Highest Response Ratio Next)（回響比R = (等待時間 + 要求執行時間) / 要求執行時間，是FCFS和SJF的折衷）

最高回響

最高回響比優先法(HRN，Highest Response_ratio Next)是對FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個作業的等待時間而未考慮執行時間的長短，而SJF方式只考慮執行時間而未考慮等待時間的長短。因此，這兩種調度算法在某些極端情況下會帶來某些不便。HRN調度策略同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出回響比最高的作業投入執行。

回響比R定義如下： R =(W+T)/T = 1+W/T

其中T為該作業估計需要的執行時間，W為作業在後備狀態佇列中的等待時間。每當要進行作業調度時，系統計算每個作業的回響比，選擇其中R最大者投入執行。這樣，即使是長作業，隨著它等待時間的增加，W / T也就隨著增加，也就有機會獲得調度執行。這種算法是介於FCFS和SJF之間的一種折中算法。由於長作業也有機會投入運行，在同一時間內處理的作業數顯然要少於SJF法，從而採用HRN方式時其吞吐量將小於採用SJF 法時的吞吐量。另外，由於每次調度前要計算回響比，系統開銷也要相應增加。