調(diào)度程序是操作系統(tǒng)內(nèi)核的組成部分，它負(fù)責(zé)選擇下一個(gè)要運(yùn)行的進(jìn)程。所以調(diào)度策略就決定了這個(gè)操作系統(tǒng)的是非實(shí)時(shí)還是實(shí)時(shí)的操作系統(tǒng)。當(dāng)今操作系統(tǒng)的種類繁多，但進(jìn)程調(diào)度算法可以總結(jié)為一下幾種。

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

先來先服務(wù)的調(diào)度策略非常的簡(jiǎn)單。維護(hù)一個(gè)就緒隊(duì)列，每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。

短進(jìn)程優(yōu)先調(diào)度算法(SPF)

短進(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)度算法

為了照顧緊迫型的進(jìn)程，能讓這些進(jìn)程得到優(yōu)先的運(yùn)行，所以引入了優(yōu)先權(quán)優(yōu)先調(diào)度算法。這種調(diào)度算法可以用在實(shí)時(shí)操作系統(tǒng)上。當(dāng)進(jìn)程調(diào)度發(fā)生時(shí)，該算法把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程。

該算法有兩種類型：

非搶占式優(yōu)先權(quán)算法：在這種模式下，系統(tǒng)一旦把處理機(jī)分配給了就緒隊(duì)列中某個(gè)優(yōu)先級(jí)最高的進(jìn)程，這個(gè)進(jìn)程就會(huì)一直運(yùn)行下去，直到進(jìn)程結(jié)束;或者是主動(dòng)放棄處理機(jī)，系統(tǒng)才會(huì)將處理機(jī)分配給另一個(gè)優(yōu)先級(jí)最高的進(jìn)程。這種算法可用于某些對(duì)實(shí)時(shí)性要求不高的操作系統(tǒng)中。

搶占式優(yōu)先權(quán)調(diào)度算法：在這種模式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先級(jí)最高進(jìn)程，然后運(yùn)行。但是如果在運(yùn)行期間，就緒隊(duì)列中出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程，系統(tǒng)就會(huì)立即停止當(dāng)前運(yùn)行的進(jìn)程，重新將處理機(jī)分配給新加入的優(yōu)先級(jí)更高的進(jìn)程。所以在這種模式下，可以更好的滿足實(shí)時(shí)性的要求，故常用在實(shí)時(shí)性要求高的系統(tǒng)中。

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

怎么解決上述問題呢?

有三種方法：

設(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ā)生。

優(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)程回到原來的優(yōu)先級(jí)別。嵌入式系統(tǒng)VxWorks就是采用這種策略。

第三種方法就是臨界區(qū)禁止中斷，通過禁止中斷來保護(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ù)，此一問題也不會(huì)發(fā)生。

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

在CPU密集型系統(tǒng)中,短進(jìn)程優(yōu)先級(jí)算法是比較好的一種算法。但是長進(jìn)程的運(yùn)行時(shí)得不到確定保證的。該怎么解決這個(gè)問題呢?我們是不是可以引入一種動(dòng)態(tài)優(yōu)先級(jí)，用大白話說等待的時(shí)間越長，優(yōu)先級(jí)就會(huì)變得越高。所以，等待了一段時(shí)間之后，就會(huì)一定輪到運(yùn)行的。但是其中的這個(gè)動(dòng)態(tài)計(jì)算優(yōu)先級(jí)的算法是需要消耗CPU資源的。

時(shí)間片輪轉(zhuǎn)

在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(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)來停止該進(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)所有用戶的請(qǐng)求。

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

我們之前講的調(diào)度算法都有一定的局限性。如短進(jìn)程優(yōu)先調(diào)度算法，僅照顧了短進(jìn)程，而忽略了長進(jìn)程。而多級(jí)反饋隊(duì)列調(diào)度算法，是一種均衡的，能夠滿足各類進(jìn)程的需要。所以是目前比較好的進(jìn)程調(diào)度算法。

設(shè)置多個(gè)就緒隊(duì)列，并且每個(gè)隊(duì)列的優(yōu)先等級(jí)不一樣。第一隊(duì)列優(yōu)先級(jí)最高，第二隊(duì)列優(yōu)先級(jí)次之，以此類推。優(yōu)先級(jí)越高隊(duì)列，時(shí)間片就最短。

當(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è)長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n 隊(duì)列便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。

僅當(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)程。如下圖：

參考

https://blog.csdn.net/qq_35642036/article/details/82809812，源理君參考了這篇文章。

總結(jié)

本文講了幾種進(jìn)程調(diào)度算法，希望對(duì)進(jìn)程調(diào)度算法有興趣的朋友們，有所幫助。當(dāng)然還有本文沒有談到的調(diào)度算法，如：彩票調(diào)度，單比率調(diào)度等等。