-
作業調度算法
鎖定
在典型的設計中，一個任務有以下三種狀態：
正在運行（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完成時，提高優先級；時間片用完時，降低優先級。
作業調度算法優先級法
優先級算法（Priority Scheduling）是多級隊列算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。
作業調度算法靜態優先級
作業調度中的靜態優先級大多按以下原則確定：
由用户自己根據作業的緊急程度輸入一個適當的優先級。
由系統或操作員根據作業類型指定優先級。
系統根據作業要求資源情況確定優先級。
進程的靜態優先級的確定原則：
按進程的類型給予不同的優先級。
將作業的情態優先級作為它所屬進程的優先級。
作業調度算法動態優先級
進程的動態優先級一般根據以下原則確定：
根據進程佔用有CPU時間的長短來決定。
根據就緒進程等待CPU的時間長短來決定。
作業調度算法短作業優先法
短作業優先（SJF, Shortest Job First）又稱為“短進程優先”SPN(Shortest Process Next)；這是對FCFS算法的改進，其目標是減少平均週轉時間。
作業調度算法定義
對預計執行時間短的作業（進程）優先分派處理機。通常後來的短作業不搶先正在執行的作業。
作業調度算法SJF的特點
(1) 優點：
提高系統的吞吐量；
(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
