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

一、先來(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)度中，FCFS 調(diào)度算法每次從就緒隊(duì)列中選擇最先進(jìn)入該隊(duì)列的進(jìn)程，將處理機(jī)分配給它，使之投入運(yùn)行，直到完成或因某種原因而阻塞時(shí)才釋放處理機(jī)。

下面通過一個(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í)間見表2-3。
?

表2-3 FCFS調(diào)度算法的性能作業(yè)號(hào)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間等待時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

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

平均等待時(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.4 + 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)先（SPF）調(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í)間見表 2-4 。

表2-4 SJF調(diào)度算法的性能作業(yè)號(hào)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間等待時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

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

平均等待時(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)度策略問題）。
• 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會(huì)被及時(shí)處理。
• 由于作業(yè)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(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)度算法又稱優(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)程類型、進(jìn)程對(duì)資源的要求、用戶要求。
• 動(dòng)態(tài)優(yōu)先級(jí)。在進(jìn)程運(yùn)行過程中，根據(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)程間過于頻繁切換，使處理機(jī)的開銷增大，而真正用于運(yùn)行用戶進(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 所示。通過動(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)思想如下：

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

賦予各個(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)一倍。

當(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)行。

僅當(dāng)?shù)?1 級(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è)用戶：短作業(yè)優(yōu)先。
  • 短批處理作業(yè)用戶：周轉(zhuǎn)時(shí)間較短。
  • 長(zhǎng)批處理作業(yè)用戶：經(jīng)過前面幾個(gè)隊(duì)列得到部分執(zhí)行，不會(huì)長(zhǎng)期得不到處理。

轉(zhuǎn)載：https://www.cnblogs.com/kxdblog/p/4798401.html

?

（SAW：Game Over！）

總結(jié)

以上是生活随笔為你收集整理的OS / 几个常用的操作系统进程调度算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。