在操作系統(tǒng)中存在多種調(diào)度算法，其中有的調(diào)度算法適用于作業(yè)調(diào)度，有的調(diào)度算法適用于進程調(diào)度，有的調(diào)度算法兩者都適用。下面介紹幾種常用的調(diào)度算法。

[[258769]]

先來先服務(FCFS)調(diào)度算法

FCFS調(diào)度算法是一種最簡單的調(diào)度算法，該調(diào)度算法既可以用于作業(yè)調(diào)度也可以用于進程調(diào)度。在作業(yè)調(diào)度中，算法每次從后備作業(yè)隊列中選擇***進入該隊列的一個或幾個作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進程并放入就緒隊列。

在進程調(diào)度中，F(xiàn)CFS調(diào)度算法每次從就緒隊列中選擇***進入該隊列的進程，將處理機分配給它，使之投入運行，直到完成或因某種原因而阻塞時才釋放處理機。

下面通過一個實例來說明FCFS調(diào)度算法的性能。假設系統(tǒng)中有4個作業(yè)，它們的提交時間分別是8、8.4、8.8、9，運行時間依次是2、1、0.5、0.2，系統(tǒng)釆用FCFS調(diào)度算法，這組作業(yè)的平均等待時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間見表2-3。

平均等待時間 t = (0+1.6+2.2+2.5)/4=1.575

平均周轉(zhuǎn)時間 T = (2+2.6+2.7+2.7)/4=2.5

平均帶權(quán)周轉(zhuǎn)時間 W = (1+2.6+5.牡13.5)/4=5.625

FCFS調(diào)度算法屬于不可剝奪算法。從表面上看，它對所有作業(yè)都是公平的，但若一個長作業(yè)先到達系統(tǒng)，就會使后面許多短作業(yè)等待很長時間，因此它不能作為分時系統(tǒng)和實時系統(tǒng)的主要調(diào)度策略。但它常被結(jié)合在其他調(diào)度策略中使用。例如，在使用優(yōu)先級作為調(diào)度策略的系統(tǒng)中，往往對多個具有相同優(yōu)先級的進程按FCFS原則處理。

FCFS調(diào)度算法的特點是算法簡單，但效率低;對長作業(yè)比較有利，但對短作業(yè)不利(相對SJF和高響應比);有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。

短作業(yè)優(yōu)先(SJF)調(diào)度算法

短作業(yè)(進程)優(yōu)先調(diào)度算法是指對短作業(yè)(進程)優(yōu)先調(diào)度的算法。短作業(yè)優(yōu)先(SJF)調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選擇一個估計運行時間最短的進程，將處理機分配給它，使之立即執(zhí)行，直到完成或發(fā)生某事件而阻塞時，才釋放處理機。

例如，考慮表2-3中給出的一組作業(yè)，若系統(tǒng)釆用短作業(yè)優(yōu)先調(diào)度算法，其平均等待時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間見表2-4。

平均等待時間 t = (0+2.3+1.4+1)/4=1.175

平均周轉(zhuǎn)時間 T = (2+3.3+1.9+1.2)/4=2.1

平均帶權(quán)周轉(zhuǎn)時間 W = (1+3.3+3.8+6)/4=3.525

SJF調(diào)度算法也存在不容忽視的缺點：

• 該算法對長作業(yè)不利，由表2-3和表2-4可知，SJF調(diào)度算法中長作業(yè)的周轉(zhuǎn)時間會增加。更嚴重的是，如果有一長作業(yè)進入系統(tǒng)的后備隊列，由于調(diào)度程序總是優(yōu)先調(diào)度那些 (即使是后進來的)短作業(yè)，將導致長作業(yè)長期不被調(diào)度(“饑餓”現(xiàn)象，注意區(qū)分“死鎖”。后者是系統(tǒng)環(huán)形等待，前者是調(diào)度策略問題)。
• 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會被及時處理。
• 由于作業(yè)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

注意，SJF調(diào)度算法的平均等待時間、平均周轉(zhuǎn)時間最少。

優(yōu)先級調(diào)度算法

優(yōu)先級調(diào)度算法又稱優(yōu)先權(quán)調(diào)度算法，該算法既可以用于作業(yè)調(diào)度，也可以用于進程調(diào)度，該算法中的優(yōu)先級用于描述作業(yè)運行的緊迫程度。

在作業(yè)調(diào)度中，優(yōu)先級調(diào)度算法每次從后備作業(yè)隊列中選擇優(yōu)先級最髙的一個或幾個作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進程并放入就緒隊列。在進程調(diào)度中，優(yōu)先級調(diào)度算法每次從就緒隊列中選擇優(yōu)先級***的進程，將處理機分配給它，使之投入運行。

根據(jù)新的更高優(yōu)先級進程能否搶占正在執(zhí)行的進程，可將該調(diào)度算法分為：

• 非剝奪式優(yōu)先級調(diào)度算法。當某一個進程正在處理機上運行時，即使有某個更為重要或緊迫的進程進入就緒隊列，仍然讓正在運行的進程繼續(xù)運行，直到由于其自身的原因而主動讓出處理機時(任務完成或等待事件)，才把處理機分配給更為重要或緊迫的進程。
• 剝奪式優(yōu)先級調(diào)度算法。當一個進程正在處理機上運行時，若有某個更為重要或緊迫的進程進入就緒隊列，則立即暫停正在運行的進程，將處理機分配給更重要或緊迫的進程。

而根據(jù)進程創(chuàng)建后其優(yōu)先級是否可以改變，可以將進程優(yōu)先級分為以下兩種：

• 靜態(tài)優(yōu)先級。優(yōu)先級是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。確定靜態(tài)優(yōu)先級的主要依據(jù)有進程類型、進程對資源的要求、用戶要求。
• 動態(tài)優(yōu)先級。在進程運行過程中，根據(jù)進程情況的變化動態(tài)調(diào)整優(yōu)先級。動態(tài)調(diào)整優(yōu)先級的主要依據(jù)為進程占有CPU時間的長短、就緒進程等待CPU時間的長短。

高響應比優(yōu)先調(diào)度算法

高響應比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度，該算法是對FCFS調(diào)度算法和SJF調(diào)度算法的一種綜合平衡，同時考慮每個作業(yè)的等待時間和估計的運行時間。在每次進行作業(yè)調(diào)度時，先計算后備作業(yè)隊列中每個作業(yè)的響應比，從中選出響應比***的作業(yè)投入運行。

響應比的變化規(guī)律可描述為：

根據(jù)公式可知：

• 當作業(yè)的等待時間相同時，則要求服務時間越短，其響應比越高，有利于短作業(yè)。
• 當要求服務時間相同時，作業(yè)的響應比由其等待時間決定，等待時間越長，其響應比越高，因而它實現(xiàn)的是先來先服務。
• 對于長作業(yè)，作業(yè)的響應比可以隨等待時間的增加而提高，當其等待時間足夠長時，其響應比便可升到很高，從而也可獲得處理機。克服了饑餓狀態(tài)，兼顧了長作業(yè)。

時間片輪轉(zhuǎn)調(diào)度算法

時間片輪轉(zhuǎn)調(diào)度算法主要適用于分時系統(tǒng)。在這種算法中，系統(tǒng)將所有就緒進程按到達時間的先后次序排成一個隊列，進程調(diào)度程序總是選擇就緒隊列中***個進程執(zhí)行，即先來先服務的原則，但僅能運行一個時間片，如100ms。在使用完一個時間片后，即使進程并未完成其運行，它也必須釋放出(被剝奪)處理機給下一個就緒的進程，而被剝奪的進程返回到就緒隊列的末尾重新排隊，等候再次運行。

在時間片輪轉(zhuǎn)調(diào)度算法中，時間片的大小對系統(tǒng)性能的影響很大。如果時間片足夠大，以至于所有進程都能在一個時間片內(nèi)執(zhí)行完畢，則時間片輪轉(zhuǎn)調(diào)度算法就退化為先來先服務調(diào)度算法。如果時間片很小，那么處理機將在進程間過于頻繁切換，使處理機的開銷增大，而真正用于運行用戶進程的時間將減少。因此時間片的大小應選擇適當。

時間片的長短通常由以下因素確定：系統(tǒng)的響應時間、就緒隊列中的進程數(shù)目和系統(tǒng)的處理能力。

多級反饋隊列調(diào)度算法(集合了前幾種算法的優(yōu)點)

多級反饋隊列調(diào)度算法是時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法的綜合和發(fā)展，如圖2-5 所示。通過動態(tài)調(diào)整進程優(yōu)先級和時間片大小，多級反饋隊列調(diào)度算法可以兼顧多方面的系統(tǒng)目標。例如，為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進程;為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程;同時，也不必事先估計進程的執(zhí)行時間。

圖2-5 多級反饋隊列調(diào)度算法

多級反饋隊列調(diào)度算法的實現(xiàn)思想如下：

1.應設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級，第1級隊列的優(yōu)先級***，第2級隊列次之，其余隊列的優(yōu)先級逐次降低。

2.賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先級越高的隊列中，每個進程的運行時間片就越小。例如，第2級隊列的時間片要比第1級隊列的時間片長一倍， ……第i+1級隊列的時間片要比第i級隊列的時間片長一倍。

3.當一個新進程進入內(nèi)存后，首先將它放入第1級隊列的末尾，按FCFS原則排隊等待調(diào)度。當輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準備撤離系統(tǒng);如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第2級隊列的末尾，再同樣地按FCFS 原則等待調(diào)度執(zhí)行;如果它在第2級隊列中運行一個時間片后仍未完成，再以同樣的方法放入第3級隊列……如此下去，當一個長進程從第1級隊列依次降到第 n 級隊列后，在第 n 級隊列中便釆用時間片輪轉(zhuǎn)的方式運行。

4.僅當?shù)?級隊列為空時，調(diào)度程序才調(diào)度第2級隊列中的進程運行;僅當?shù)? ~ (i-1)級隊列均為空時，才會調(diào)度第i級隊列中的進程運行。如果處理機正在執(zhí)行第i級隊列中的某進程時，又有新進程進入優(yōu)先級較高的隊列(第 1 ~ (i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在運行的進程放回到第i級隊列的末尾，把處理機分配給新到的更高優(yōu)先級的進程。

多級反饋隊列的優(yōu)勢有：

• 終端型作業(yè)用戶：短作業(yè)優(yōu)先。
• 短批處理作業(yè)用戶：周轉(zhuǎn)時間較短。
• 長批處理作業(yè)用戶：經(jīng)過前面幾個隊列得到部分執(zhí)行，不會長期得不到處理。