操作系統(tǒng)四種調(diào)度算法
操作系統(tǒng)四種調(diào)度算法
操作系統(tǒng)對進(jìn)程的調(diào)度一般上有四種常見的算法。下面由學(xué)習(xí)啦小編為大家整理了操作系統(tǒng)的四種調(diào)度算法的相關(guān)知識,希望對大家有幫助!
操作系統(tǒng)四重調(diào)度算法之一、先來先服務(wù)調(diào)度算法
先來先服務(wù)(FCFS)調(diào)度算法是一種最簡單的調(diào)度算法,該算法既可用于作業(yè)調(diào)度,也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時,每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進(jìn)入該隊列的作業(yè),將它們調(diào)入內(nèi)存,為它們分配資源、創(chuàng)建進(jìn)程,然后放入就緒隊列。在進(jìn)程調(diào)度中采用FCFS算法時,則每次調(diào)度是從就緒隊列中選擇一個最先進(jìn)入該隊列的進(jìn)程,為之分配處理機(jī),使之投入運行。該進(jìn)程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。
操作系統(tǒng)四重調(diào)度算法之二、短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法
短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F,是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè),將它們調(diào)入內(nèi)存運行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進(jìn)程,將處理機(jī)分配給它,使它立即執(zhí)行并一直執(zhí)行到完成,或發(fā)生某事件而被阻塞放棄處理機(jī)時再重新調(diào)度。
操作系統(tǒng)四重調(diào)度算法之三、高優(yōu)先權(quán)優(yōu)先調(diào)度算法
1.優(yōu)先權(quán)調(diào)度算法的類型
為了照顧緊迫型作業(yè),使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理,引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中,作為作業(yè)調(diào)度算法,也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度算法,還可用于實時系統(tǒng)中。當(dāng)把該算法用于作業(yè)調(diào)度時,系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時,該算法是把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程,這時,又可進(jìn)一步把該算法分成如下兩種。
1) 非搶占式優(yōu)先權(quán)算法
在這種方式下,系統(tǒng)一旦把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后,該進(jìn)程便一直執(zhí)行下去,直至完成;或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時,系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中;也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中。
2) 搶占式優(yōu)先權(quán)調(diào)度算法
在這種方式下,系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程,使之執(zhí)行。但在其執(zhí)行期間,只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程,進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行,重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此,在采用這種調(diào)度算法時,是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i 時,就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j 的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj,原進(jìn)程Pj便繼續(xù)執(zhí)行;但如果是Pi>Pj,則立即停止Pj的執(zhí)行,做進(jìn)程切換,使i 進(jìn)程投入執(zhí)行。顯然,這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求,故而常用于要求比較嚴(yán)格的實時系統(tǒng)中,以及對性能要求較高的批處理和分時系統(tǒng)中。
操作系統(tǒng)四重調(diào)度算法之四、基于時間片的輪轉(zhuǎn)調(diào)度算法
1.時間片輪轉(zhuǎn)法
1) 基本原理
在早期的時間片輪轉(zhuǎn)法中,系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊列,每次調(diào)度時,把CPU 分配給隊首進(jìn)程,并令其執(zhí)行一個時間片。時間片的大小從幾ms 到幾百ms。當(dāng)執(zhí)行的時間片用完時,由一個計時器發(fā)出時鐘中斷請求,調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行,并將它送往就緒隊列的末尾;然后,再把處理機(jī)分配給就緒隊列中新的隊首進(jìn)程,同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進(jìn)程在一給定的時間內(nèi)均能獲得一時間片的處理機(jī)執(zhí)行時間。換言之,系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。
2.多級反饋隊列調(diào)度算法
前面介紹的各種用作進(jìn)程調(diào)度的算法都有一定的局限性。如短進(jìn)程優(yōu)先的調(diào)度算法,僅照顧了短進(jìn)程而忽略了長進(jìn)程,而且如果并未指明進(jìn)程的長度,則短進(jìn)程優(yōu)先和基于進(jìn)程長度的搶占式調(diào)度算法都將無法使用。而多級反饋隊列調(diào)度算法則不必事先知道各種進(jìn)程所需的執(zhí)行時間,而且還可以滿足各種類型進(jìn)程的需要,因而它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。在采用多級反饋隊列調(diào)度算法的系統(tǒng)中,調(diào)度算法的實施過程如下所述。
(1) 應(yīng)設(shè)置多個就緒隊列,并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高,第二個隊列次之,其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不相同,在優(yōu)先權(quán)愈高的隊列中,為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如,第二個隊列的時間片要比第一個隊列的時間片長一倍,……,第i+1個隊列的時間片要比第i個隊列的時間片長一倍。
(2) 當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后,首先將它放入第一隊列的末尾,按FCFS原則排隊等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時,如它能在該時間片內(nèi)完成,便可準(zhǔn)備撤離系統(tǒng);如果它在一個時間片結(jié)束時尚未完成,調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊列的末尾,再同樣地按FCFS原則等待調(diào)度執(zhí)行;如果它在第二隊列中運行一個時間片后仍未完成,再依次將它放入第三隊列,……,如此下去,當(dāng)一個長作業(yè)(進(jìn)程)從第一隊列依次降到第n隊列后,在第n 隊列便采取按時間片輪轉(zhuǎn)的方式運行。
(3) 僅當(dāng)?shù)谝魂犃锌臻e時,調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運行;僅當(dāng)?shù)?~(i-1)隊列均空時,才會調(diào)度第i隊列中的進(jìn)程運行。如果處理機(jī)正在第i隊列中為某進(jìn)程服務(wù)時,又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列(第1~(i-1)中的任何一個隊列),則此時新進(jìn)程將搶占正在運行進(jìn)程的處理機(jī),即由調(diào)度程序把正在運行的進(jìn)程放回到第i隊列的末尾,把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。