今天我們來談一談進程調度算法：

1. 先來先服務調度算法（FCFS）

先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。當在作業調度中采用該算法時，每次調度都是從后備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然后放入就緒隊列。在進程調度中采用FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞后才放棄處理機。

算法優點：易于理解且實現簡單，只需要一個隊列(FIFO)，且相當公平 算法缺點：比較有利于長進程，而不利于短進程，有利于CPU 繁忙的進程，而不利于I/O 繁忙的進程

2. 短作業（進程）優先調度算法（SJF）

短作業（進程）優先調度算法，它作用于作業調度和進程調度。短作業優先是從后備隊列當中選擇一個或者若干個運行時間最短的作業，調入內存當中運行。 短進程優先是從就緒進程隊列當中選出一個時間最短的進程，將處理機分配給它，立即執行并且一直執行到完成，當發生其他問題的時候，這個時候就重新調度。

算法優點：相比FCFS 算法，該算法可改善平均周轉時間和平均帶權周轉時間，縮短進程的等待時間，提高系統的吞吐量。 算法缺點：對長進程非常不利，可能長時間得不到執行，且未能依據進程的緊迫程度來劃分執行的優先級，以及難以準確估計進程的執行時間，從而影響調度性能。

3.優先權調度算法

優先級調度算法又被稱為優先權調度算法，這個算法既可以用于作業調度，也可以用于進程調度，這個算法中的優先級用于描述作業運行的緊迫程度。

在作業調度中，優先級調度算法每次從后備作業隊列中選擇優先級最髙的一個或幾個作業，將它們調入內存，分配必要的資源，創建進程并放入就緒隊列。在進程調度中，優先級調度算法每次從就緒隊列中選擇優先級最高的進程，將處理機分配給它，使之投入運行。

根據新的更高優先級進程能否搶占正在執行的進程，可將該調度算法分為： * 非剝奪式優先級調度算法。當某一個進程正在處理機上運行時，即使有某個更為重要或緊迫的進程進入就緒隊列，仍然讓正在運行的進程繼續運行，直到由于其自身的原因而主動讓出處理機時（任務完成或等待事件），才把處理機分配給更為重要或緊迫的進程。 * 剝奪式優先級調度算法。當一個進程正在處理機上運行時，若有某個更為重要或緊迫的進程進入就緒隊列，則立即暫停正在運行的進程，將處理機分配給更重要或緊迫的進程。

而根據進程創建后其優先級是否可以改變，可以將進程優先級分為以下兩種： * 靜態優先級。優先級是在創建進程時確定的，且在進程的整個運行期間保持不變。確定靜態優先級的主要依據有進程類型、進程對資源的要求、用戶要求。 * 動態優先級。在進程運行過程中，根據進程情況的變化動態調整優先級。動態調整優先級的主要依據為進程占有CPU時間的長短、就緒進程等待CPU時間的長短。

4.高響應比優先調度算法（HRRN）

高響應比優先調度算法主要用于作業調度，是堆FCFS和SJF的一種平衡。

FCFS是只考慮每個作業的等待時間不考慮執行時間長短，而SJF是只考慮執行時間未考慮等待時間的長短。

所以高響應比同時考慮每個作業的等待時間和估計運行時間，在每次進行作業調度時，先計算后備作業隊列當中的每個作業響應比，然后找出響應比最高的作業投入運行。

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

其中T為該作業估計需要的執行時間，W為作業在后備狀態隊列中的等待時間。每當要進行作業調度時，系統計算每個作業的響應比，選擇其中R最大者投入執行。 算法優點：由于長作業也有機會投入運行，在同一時間內處理的作業數顯然要少于SJF法，從而采用HRRN方式時其吞吐量將小于采用SJF 法時的吞吐量。 算法缺點：由于每次調度前要計算響應比，系統開銷也要相應增加。

5.時間片輪轉算法

主要用于分時系統。這種算法中，系統將所有的就緒進程按照到達時間先后次序排成一個隊列，按照先來先服務的原則運行，但是僅僅只能運行一個時間片，使用完一個時間片的時間以后，即使進程并未完成其運行，也必須釋放出處理機給下一個就緒的進程，而被剝奪的進程返回就緒隊列末尾重新排隊，等候再次運行。并且通過上下文切換執行當前的隊首進程，京城可以未使用完一個時間片，就讓出處理機。

在整個過程中，時間片的大小尤為重要，時間片過大，那么所有的進程都能在一個時間片內執行完畢，則時間片輪轉算法就會退化成為FCFS,如果太小，那么進程之間頻繁切換，那么處理機的開銷很大，真正用于運行用戶進程的時間將減小。因此時間片需要選擇恰當。

時間片大小的確定： 1. 系統對響應時間的要求 2. 就緒隊列中進程的數目 3. 系統的處理能力

算法優點：時間片輪轉調度算法的特點是簡單易行、平均響應時間短。 算法缺點：不利于處理緊急作業。在時間片輪轉算法中，時間片的大小對系統性能的影響很大，因此時間片的大小應選擇恰當。

6.多級反饋隊列

多級反饋隊列調度算法是一種CPU處理機調度算法，UNIX操作系統采取的便是這種調度算法。多級反饋隊列調度算法可以兼顧多方面的系統目標。

多級反饋隊列調度算法的實現思想如下： * 1.應設置多個就緒隊列，并為各個隊列賦予不同的優先級，第1級隊列的優先級最高，第2級隊列次之，其余隊列的優先級逐次降低。 * 2.賦予各個隊列中進程執行時間片的大小也各不相同，在優先級越高的隊列中，每個進程的運行時間片就越小。例如，第2級隊列的時間片要比第1級隊列的時間片長一倍， ……第i+1級隊列的時間片要比第i級隊列的時間片長一倍。 * 3.當一個新進程進入內存后，首先將它放入第1級隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第2級隊列的末尾，再同樣地按FCFS 原則等待調度執行；如果它在第2級隊列中運行一個時間片后仍未完成，再以同樣的方法放入第3級隊列……如此下去，當一個長進程從第1級隊列依次降到第 n 級隊列后，在第 n 級隊列中便釆用時間片輪轉的方式運行。 * 4.僅當第1級隊列為空時，調度程序才調度第2級隊列中的進程運行；僅當第1 ~ (i-1)級隊列均為空時，才會調度第i級隊列中的進程運行。如果處理機正在執行第i級隊列中的某進程時，又有新進程進入優先級較高的隊列（第 1 ~ (i-1)中的任何一個隊列），則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i級隊列的末尾，把處理機分配給新到的更高優先級的進程。

多級反饋隊列的優勢有： * 終端型作業用戶：短作業優先。 * 短批處理作業用戶：周轉時間較短。 * 長批處理作業用戶：經過前面幾個隊列得到部分執行，不會長期得不到處理。