作業調度

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

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

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

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

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

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

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

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

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

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

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

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

時間片長度變化的影響

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

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

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

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

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

^[1]  多級反饋隊列算法(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）是多級隊列算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。

^[1]  作業調度中的靜態優先級大多按以下原則確定：

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

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

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

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

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

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

^[1]  進程的動態優先級一般根據以下原則確定：

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

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

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

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

(1) 優點：

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

提高系統的吞吐量；

(2) 缺點：

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

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

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

“最短剩餘時間優先”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 法時的吞吐量。另外，由於每次調度前要計算響應比，系統開銷也要相應增加。