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

[[258769]]

先來(lái)先服務(wù)(FCFS)調(diào)度算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)公式可知：

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

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

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

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

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

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

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

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

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

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

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

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

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

多級(jí)反饋隊(duì)列的優(yōu)勢(shì)有：

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