散文網(wǎng) » 生活 »日常 » 詳解操作系統(tǒng)中的進(jìn)程調(diào)度策略有哪幾種！

詳解操作系統(tǒng)中的進(jìn)程調(diào)度策略有哪幾種！

2022-07-02 16:59 作者:補(bǔ)給站Linux內(nèi)核 0人讀過(guò) | 我要投稿

先來(lái)先服務(wù)調(diào)度算法：先來(lái)先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。
短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法：短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(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í)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。
高優(yōu)先權(quán)優(yōu)先調(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)度算法，還可用于實(shí)時(shí)系統(tǒng)中。當(dāng)把該算法用于作業(yè)調(diào)度時(shí)，系統(tǒng)將從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，這時(shí)，又可進(jìn)一步把該算法分成如下兩種。

? 3.1) 非搶占式優(yōu)先權(quán)算法：在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。

? ?3.2) 搶占式優(yōu)先權(quán)調(diào)度算法：在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(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)度算法時(shí)，是每當(dāng)系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程i 時(shí)，就將其優(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)度算法能更好地滿(mǎn)足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。

? ?3.3)容易出現(xiàn)優(yōu)先級(jí)倒置現(xiàn)象：優(yōu)先級(jí)反轉(zhuǎn)是指一個(gè)低優(yōu)先級(jí)的任務(wù)持有一個(gè)被高優(yōu)先級(jí)任務(wù)所需要的共享資源。高優(yōu)先任務(wù)由于因資源缺乏而處于受阻狀態(tài)，一直等到低優(yōu)先級(jí)任務(wù)釋放資源為止。而低優(yōu)先級(jí)獲得的CPU時(shí)間少，如果此時(shí)有優(yōu)先級(jí)處于兩者之間的任務(wù)，并且不需要那個(gè)共享資源，則該中優(yōu)先級(jí)的任務(wù)反而超過(guò)這兩個(gè)任務(wù)而獲得CPU時(shí)間。如果高優(yōu)先級(jí)等待資源時(shí)不是阻塞等待，而是忙循環(huán)，則可能永遠(yuǎn)無(wú)法獲得資源，因?yàn)榇藭r(shí)低優(yōu)先級(jí)進(jìn)程無(wú)法與高優(yōu)先級(jí)進(jìn)程爭(zhēng)奪CPU時(shí)間，從而無(wú)法執(zhí)行，進(jìn)而無(wú)法釋放資源，造成的后果就是高優(yōu)先級(jí)任務(wù)無(wú)法獲得資源而繼續(xù)推進(jìn)。

? ?3.4)優(yōu)先級(jí)反轉(zhuǎn)案例解釋?zhuān)翰煌瑑?yōu)先級(jí)線(xiàn)程對(duì)共享資源的訪(fǎng)問(wèn)的同步機(jī)制。優(yōu)先級(jí)為高和低的線(xiàn)程tall和線(xiàn)程low需要訪(fǎng)問(wèn)共享資源，優(yōu)先級(jí)為中等的線(xiàn)程mid不訪(fǎng)問(wèn)該共享資源。當(dāng)low正在訪(fǎng)問(wèn)共享資源時(shí)，tall等待該共享資源的互斥鎖，但是此時(shí)low被mid搶先了，導(dǎo)致mid運(yùn)行tall阻塞。即優(yōu)先級(jí)低的線(xiàn)程mid運(yùn)行，優(yōu)先級(jí)高的tall被阻塞。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)? ? ??

? ?3.5)優(yōu)先級(jí)倒置解決方案：

? ? ? (3.5.1）設(shè)置優(yōu)先級(jí)上限，給臨界區(qū)一個(gè)高優(yōu)先級(jí)，進(jìn)入臨界區(qū)的進(jìn)程都將獲得這個(gè)高優(yōu)先級(jí)，如果其他試圖進(jìn)入臨界區(qū)的進(jìn)程的優(yōu)先級(jí)都低于這個(gè)高優(yōu)先級(jí)，那么優(yōu)先級(jí)反轉(zhuǎn)就不會(huì)發(fā)生。

? ? （3.5.2）優(yōu)先級(jí)繼承，當(dāng)一個(gè)高優(yōu)先級(jí)進(jìn)程等待一個(gè)低優(yōu)先級(jí)進(jìn)程持有的資源時(shí)，低優(yōu)先級(jí)進(jìn)程將暫時(shí)獲得高優(yōu)先級(jí)進(jìn)程的優(yōu)先級(jí)別，在釋放共享資源后，低優(yōu)先級(jí)進(jìn)程回到原來(lái)的優(yōu)先級(jí)別。嵌入式系統(tǒng)VxWorks就是采用這種策略。

這里還有一個(gè)八卦，1997年的美國(guó)的火星探測(cè)器（使用的就是vxworks)就遇到一個(gè)優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題引起的故障。簡(jiǎn)單說(shuō)下，火星探測(cè)器有一個(gè)信息總線(xiàn)，有一個(gè)高優(yōu)先級(jí)的總線(xiàn)任務(wù)負(fù)責(zé)總線(xiàn)數(shù)據(jù)的存取，訪(fǎng)問(wèn)總線(xiàn)都需要通過(guò)一個(gè)互斥鎖（共享資源出現(xiàn)了）；還有一個(gè)低優(yōu)先級(jí)的，運(yùn)行不是很頻繁的氣象搜集任務(wù)，它需要對(duì)總線(xiàn)寫(xiě)數(shù)據(jù)，也就同樣需要訪(fǎng)問(wèn)互斥鎖；最后還有一個(gè)中優(yōu)先級(jí)的通信任務(wù)，它的運(yùn)行時(shí)間比較長(zhǎng)。平常這個(gè)系統(tǒng)運(yùn)行毫無(wú)問(wèn)題，但是有一天，在氣象任務(wù)獲得互斥鎖往總線(xiàn)寫(xiě)數(shù)據(jù)的時(shí)候，一個(gè)中斷發(fā)生導(dǎo)致通信任務(wù)被調(diào)度就緒，通信任務(wù)搶占了低優(yōu)先級(jí)的氣象任務(wù)，而無(wú)巧不成書(shū)的是，此時(shí)高優(yōu)先級(jí)的總線(xiàn)任務(wù)正在等待氣象任務(wù)寫(xiě)完數(shù)據(jù)歸還互斥鎖，但是由于通信任務(wù)搶占了CPU并且運(yùn)行時(shí)間比較長(zhǎng)，導(dǎo)致氣象任務(wù)得不到CPU時(shí)間也無(wú)法釋放互斥鎖，本來(lái)是高優(yōu)先級(jí)的總線(xiàn)任務(wù)也無(wú)法執(zhí)行，總線(xiàn)任務(wù)無(wú)法及時(shí)執(zhí)行的后果被探路者認(rèn)為是一個(gè)嚴(yán)重錯(cuò)誤，最后就是整個(gè)系統(tǒng)被重啟。Vxworks允許優(yōu)先級(jí)繼承，然而遺憾的工程師們將這個(gè)選項(xiàng)關(guān)閉了。

? ? （3.5.3）第三種方法就是臨界區(qū)禁止中斷，通過(guò)禁止中斷來(lái)保護(hù)臨界區(qū)，采用此種策略的系統(tǒng)只有兩種優(yōu)先級(jí)：可搶占優(yōu)先級(jí)和中斷禁止優(yōu)先級(jí)。前者為一般進(jìn)程運(yùn)行時(shí)的優(yōu)先級(jí)，后者為運(yùn)行于臨界區(qū)的優(yōu)先級(jí)?；鹦翘铰氛哒怯捎谠谂R界區(qū)中運(yùn)行的氣象任務(wù)被中斷發(fā)生的通信任務(wù)所搶占才導(dǎo)致故障，如果有臨界區(qū)的禁止中斷保護(hù)，此一問(wèn)題也不會(huì)發(fā)生。

4、高響應(yīng)比優(yōu)先調(diào)度算法：在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長(zhǎng)作業(yè)的運(yùn)行得不到保證。如果我們能為每個(gè)作業(yè)引入前面所述的動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a 提高，則長(zhǎng)作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為：

在利用該算法時(shí)，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計(jì)算，這會(huì)增加系統(tǒng)開(kāi)銷(xiāo)。

5、時(shí)間片輪轉(zhuǎn)法：在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU 分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的大小從幾ms 到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來(lái)停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一給定的時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。換言之，系統(tǒng)能在給定的時(shí)間內(nèi)響應(yīng)所有用戶(hù)的請(qǐng)求。

6、多級(jí)反饋隊(duì)列調(diào)度算法：前面介紹的各種用作進(jìn)程調(diào)度的算法都有一定的局限性。如短進(jìn)程優(yōu)先的調(diào)度算法，僅照顧了短進(jìn)程而忽略了長(zhǎng)進(jìn)程，而且如果并未指明進(jìn)程的長(zhǎng)度，則短進(jìn)程優(yōu)先和基于進(jìn)程長(zhǎng)度的搶占式調(diào)度算法都將無(wú)法使用。而多級(jí)反饋隊(duì)列調(diào)度算法則不必事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，而且還可以滿(mǎn)足各種類(lèi)型進(jìn)程的需要，因而它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。在采用多級(jí)反饋隊(duì)列調(diào)度算法的系統(tǒng)中，調(diào)度算法的實(shí)施過(guò)程如下所述。

(1) 應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍。

(2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(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)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n 隊(duì)列便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。

(3) 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?～(i-1)隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1～(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。