OS / 几个常用的操作系统进程调度算法
在操作系統(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。
?
| 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 。
| 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)思想如下:
多級(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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: OS / linux / 互斥锁实现原理
- 下一篇: OS / 进程和线程的区别和联系