在操作系統中存在多種調度算法，其中有的調度算法適用于作業調度，有的調度算法適用于進程調度，有的調度算法兩者都適用。下面介紹幾種常用的調度算法。 ###先來先服務(FCFS)調度算法 FCFS調度算法是一種最簡單的調度算法，該調度算法既可以用于作業調度也可以用于進程調度。在作業調度中，算法每次從后備作業隊列中選擇最先進入該隊列的一個或幾個作業，將它們調入內存，分配必要的資源，創建進程并放入就緒隊列。 在進程調度中，FCFS調度算法每次從就緒隊列中選擇最先進入該隊列的進程，將處理機分配給它，使之投入運行，直到完成或因某種原因而阻塞時才釋放處理機。 下面通過一個實例來說明FCFS調度算法的性能。假設系統中有4個作業，它們的提交時間分別是8、8.4、8.8、9，運行時間依次是2、1、0.5、0.2，系統釆用FCFS調度算法，這組作業的平均等待時間、平均周轉時間和平均帶權周轉時間見表2-3。 表2-3 FCFS調度算法的性能 作業號 提交時間 運行時間 開始時間 等待時間 完成時間 周轉時間 帶權周轉時間 1 8 2 8 0 10 2 1 2 8.4 1 10 1.6 11 2.6 2.6 3 8.8 0.5 11 2.2 11.5 2.7 5.4 4 9 0.2 11.5 2.5 11.7 2.7 13.5 平均等待時間 t = (0+1.6+2.2+2.5)/4=1.575 平均周轉時間 T = (2+2.6+2.7+2.7)/4=2.5 平均帶權周轉時間 W = (1+2.6+5.牡13.5)/4=5.625 FCFS調度算法屬于不可剝奪算法。從表面上看，它對所有作業都是公平的，但若一個長作業先到達系統，就會使后面許多短作業等待很長時間，因此它不能作為分時系統和實時系統的主要調度策略。但它常被結合在其他調度策略中使用。例如，在使用優先級作為調度策略的系統中，往往對多個具有相同優先級的進程按FCFS原則處理。 FCFS調度算法的特點是算法簡單，但效率低；對長作業比較有利，但對短作業不利（相對SJF和高響應比）；有利于CPU繁忙型作業，而不利于I/O繁忙型作業。 ###短作業優先(SJF)調度算法 短作業（進程）優先調度算法是指對短作業（進程）優先調度的算法。短作業優先(SJF)調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法，則是從就緒隊列中選擇一個估計運行時間最短的進程，將處理機分配給它，使之立即執行，直到完成或發生某事件而阻塞時，才釋放處理機。 例如，考慮表2-3中給出的一組作業，若系統釆用短作業優先調度算法，其平均等待時間、平均周轉時間和平均帶權周轉時間見表2-4。 表2-4 SJF調度算法的性能 作業號 提交時間 運行時間 開始時間 等待時間 完成時間 周轉時間 帶權周轉時間 1 8 2 8 0 10 2 1 2 8,4 1 10.7 2.3 11.7 3.3 3.3 3 8.8 0.5 10.2 1.4 10.7 1.9 3.8 4 9 0.2 10 1 10.2 1.2 6 平均等待時間 t = (0+2.3+1.4+1)/4=1.175 平均周轉時間 T = (2+3.3+1.9+1.2)/4=2.1 平均帶權周轉時間 W = (1+3.3+3.8+6)/4=3.525 SJF調度算法也存在不容忽視的缺點： 該算法對長作業不利，由表2-3和表2-4可知，SJF調度算法中長作業的周轉時間會增加。更嚴重的是，如果有一長作業進入系統的后備隊列，由于調度程序總是優先調度那些 (即使是后進來的）短作業，將導致長作業長期不被調度（“饑餓”現象，注意區分“死鎖”。后者是系統環形等待，前者是調度策略問題）。 該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業會被及時處理。 由于作業的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。 注意，SJF調度算法的平均等待時間、平均周轉時間最少。 ###優先級調度算法 優先級調度算法又稱優先權調度算法，該算法既可以用于作業調度，也可以用于進程調度，該算法中的優先級用于描述作業運行的緊迫程度。 在作業調度中，優先級調度算法每次從后備作業隊列中選擇優先級最髙的一個或幾個作業，將它們調入內存，分配必要的資源，創建進程并放入就緒隊列。在進程調度中，優先級調度算法每次從就緒隊列中選擇優先級最高的進程，將處理機分配給它，使之投入運行。 根據新的更高優先級進程能否搶占正在執行的進程，可將該調度算法分為： 非剝奪式優先級調度算法。當某一個進程正在處理機上運行時，即使有某個更為重要或緊迫的進程進入就緒隊列，仍然讓正在運行的進程繼續運行，直到由于其自身的原因而主動讓出處理機時（任務完成或等待事件），才把處理機分配給更為重要或緊迫的進程。 剝奪式優先級調度算法。當一個進程正在處理機上運行時，若有某個更為重要或緊迫的進程進入就緒隊列，則立即暫停正在運行的進程，將處理機分配給更重要或緊迫的進程。 而根據進程創建后其優先級是否可以改變，可以將進程優先級分為以下兩種： 靜態優先級。優先級是在創建進程時確定的，且在進程的整個運行期間保持不變。確定靜態優先級的主要依據有進程類型、進程對資源的要求、用戶要求。 動態優先級。在進程運行過程中，根據進程情況的變化動態調整優先級。動態調整優先級的主要依據為進程占有CPU時間的長短、就緒進程等待CPU時間的長短。 ###高響應比優先調度算法 高響應比優先調度算法主要用于作業調度，該算法是對FCFS調度算法和SJF調度算法的一種綜合平衡，同時考慮每個作業的等待時間和估計的運行時間。在每次進行作業調度時，先計算后備作業隊列中每個作業的響應比，從中選出響應比最高的作業投入運行。 響應比的變化規律可描述為：  根據公式可知： 當作業的等待時間相同時，則要求服務時間越短，其響應比越高，有利于短作業。 當要求服務時間相同時，作業的響應比由其等待時間決定，等待時間越長，其響應比越高，因而它實現的是先來先服務。 對于長作業，作業的響應比可以隨等待時間的增加而提高，當其等待時間足夠長時，其響應比便可升到很高，從而也可獲得處理機。克服了饑餓狀態，兼顧了長作業。 ###時間片輪轉調度算法 時間片輪轉調度算法主要適用于分時系統。在這種算法中，系統將所有就緒進程按到達時間的先后次序排成一個隊列，進程調度程序總是選擇就緒隊列中第一個進程執行，即先來先服務的原則，但僅能運行一個時間片，如100ms。在使用完一個時間片后，即使進程并未完成其運行，它也必須釋放出（被剝奪）處理機給下一個就緒的進程，而被剝奪的進程返回到就緒隊列的末尾重新排隊，等候再次運行。 在時間片輪轉調度算法中，時間片的大小對系統性能的影響很大。如果時間片足夠大，以至于所有進程都能在一個時間片內執行完畢，則時間片輪轉調度算法就退化為先來先服務調度算法。如果時間片很小，那么處理機將在進程間過于頻繁切換，使處理機的開銷增大，而真正用于運行用戶進程的時間將減少。因此時間片的大小應選擇適當。 時間片的長短通常由以下因素確定：系統的響應時間、就緒隊列中的進程數目和系統的處理能力。 ###多級反饋隊列調度算法（集合了前幾種算法的優點） 多級反饋隊列調度算法是時間片輪轉調度算法和優先級調度算法的綜合和發展，如圖2-5 所示。通過動態調整進程優先級和時間片大小，多級反饋隊列調度算法可以兼顧多方面的系統目標。例如，為提高系統吞吐量和縮短平均周轉時間而照顧短進程；為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程；同時，也不必事先估計進程的執行時間。  圖2-5 多級反饋隊列調度算法 多級反饋隊列調度算法的實現思想如下： 應設置多個就緒隊列，并為各個隊列賦予不同的優先級，第1級隊列的優先級最高，第2級隊列次之，其余隊列的優先級逐次降低。 賦予各個隊列中進程執行時間片的大小也各不相同，在優先級越高的隊列中，每個進程的運行時間片就越小。例如，第2級隊列的時間片要比第1級隊列的時間片長一倍， ……第i+1級隊列的時間片要比第i級隊列的時間片長一倍。 當一個新進程進入內存后，首先將它放入第1級隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第2級隊列的末尾，再同樣地按FCFS 原則等待調度執行；如果它在第2級隊列中運行一個時間片后仍未完成，再以同樣的方法放入第3級隊列……如此下去，當一個長進程從第1級隊列依次降到第 n 級隊列后，在第 n 級隊列中便釆用時間片輪轉的方式運行。 僅當第1級隊列為空時，調度程序才調度第2級隊列中的進程運行；僅當第1 ~ (i-1)級隊列均為空時，才會調度第i級隊列中的進程運行。如果處理機正在執行第i級隊列中的某進程時，又有新進程進入優先級較高的隊列（第 1 ~ (i-1)中的任何一個隊列），則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i級隊列的末尾，把處理機分配給新到的更高優先級的進程。 多級反饋隊列的優勢有： * 終端型作業用戶：短作業優先。 * 短批處理作業用戶：周轉時間較短。 * 長批處理作業用戶：經過前面幾個隊列得到部分執行，不會長期得不到處理。