進(jìn)程調(diào)度算法也稱 CPU 調(diào)度算法，畢竟進(jìn)程是由 CPU 調(diào)度的。
當(dāng) CPU 空閑時，操作系統(tǒng)就選擇內(nèi)存中標(biāo)的某個 [就緒狀態(tài)] 的進(jìn)程，將其分配給 CPU。
什么時候會發(fā)生CPU調(diào)度呢？通常有以下情況：
- 當(dāng)進(jìn)程從運行狀態(tài)轉(zhuǎn)換到等待狀態(tài)
- 當(dāng)進(jìn)程從運行狀態(tài)轉(zhuǎn)換到就緒狀態(tài)
- 當(dāng)進(jìn)程從等待狀態(tài)轉(zhuǎn)換到就緒狀態(tài)
- 當(dāng)進(jìn)程從運行狀態(tài)轉(zhuǎn)換到終止?fàn)顟B(tài)
其中發(fā)生在 1 和 4 兩種情況下的調(diào)度稱為 [非搶占式調(diào)度] ， 2 和 3 兩種情況下發(fā)生的調(diào)度稱為 [搶占式調(diào)度]。
非搶占式的意思是，當(dāng)進(jìn)程正在運行時，它就會一直運行，直到該進(jìn)程完成或發(fā)生某個事件而被阻塞時，才會把 CPU 讓給其他進(jìn)程。
搶占式調(diào)度，顧名思義就是進(jìn)程正在運行的時候，可以被打斷，使其把 CPU 讓給其他進(jìn)程。那搶占的原則一般有三種，分別是時間片原則，優(yōu)先權(quán)原則，短作業(yè)優(yōu)先原則。
調(diào)度算法影響的是等待時間（進(jìn)程在就緒隊列中等待調(diào)度的時間總和），而不能影響進(jìn)程真在使用的 CPU 時間和 I/O 時間。
常見的調(diào)度算法：
- 先來先服務(wù)算法
- 最短作業(yè)優(yōu)先調(diào)度
- 高響應(yīng)比優(yōu)先調(diào)度
- 時間片輪轉(zhuǎn)調(diào)度
- 最高優(yōu)先級調(diào)度
- 多級反饋隊列調(diào)度
先來先服務(wù)調(diào)度算法
最簡單的一個調(diào)度算法，就是非搶占式的先來先服務(wù)（FCFS）算法。
?先來先服務(wù)：每次從就緒隊列選擇最先進(jìn)入隊列的進(jìn)程，然后一直運行，直到進(jìn)程退出或被阻塞，才會繼續(xù)從隊列中選擇第一個進(jìn)程接著運行。
這似乎很公平，但是當(dāng)一個長作業(yè)先運行了，那么后面的短作業(yè)等待的時間就會很長，不利于短作業(yè)。
FCFS對長作業(yè)有利，適用于CPU繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。
最短作業(yè)優(yōu)先調(diào)度算法
最短作業(yè)優(yōu)先（SJF）調(diào)度算法同樣也是顧名思義，它會優(yōu)先選擇運行時間最短的進(jìn)程來運行，這有助于提高系統(tǒng)的吞吐量。
這顯然對長作業(yè)不利，很容易造成一種極端現(xiàn)象。
比如，一個長作業(yè)在就緒隊列等待運行，而這個就緒隊列有非常多的短作業(yè)，那么就會使得長作業(yè)不斷地往后推，周轉(zhuǎn)時間變長，致使長作業(yè)長期不會被運行。
高響應(yīng)比優(yōu)先調(diào)度算法
前面的 [先來先服務(wù)調(diào)度算法] 和 [最短作業(yè)優(yōu)先調(diào)度算法] 都沒有很好的權(quán)衡短作業(yè)和長作業(yè)。
那么。高響應(yīng)比優(yōu)先（HRRN）調(diào)度算法主要是權(quán)衡了短作業(yè)和長作業(yè)。
每次進(jìn)行進(jìn)程調(diào)度時，先計算 [響應(yīng)比優(yōu)先級]，然后把 [響應(yīng)比優(yōu)先級] 最高的進(jìn)程投入運行，[響應(yīng)比優(yōu)先級] 的計算公式：
從上面的公式可以發(fā)現(xiàn)：
- 如果兩個進(jìn)程的 [等待時間] 相同時， [要求服務(wù)時間] 越短，[響應(yīng)比] 就越高，這樣短作業(yè)的進(jìn)程容易被選中運行
- 如果兩個進(jìn)程 [要求服務(wù)時間] 相同時，[等待時間] 越長，[響應(yīng)比] 就越高，這就兼顧到了長作業(yè)進(jìn)程，因為進(jìn)程的響應(yīng)比可以隨時間等待的增加而提高，當(dāng)其等待時間足夠長時，其響應(yīng)比便可以升到很高，從而獲得運行的機會
時間片輪轉(zhuǎn)調(diào)度算法
最古老、最簡單、最公平且使用最廣泛的算法就是時間片輪轉(zhuǎn)（RR）調(diào)度算法。
每個進(jìn)程被分配一個時間段，稱為時間片，即允許該進(jìn)程在該時間段中運行。
- 如果時間片用完，進(jìn)程還在運行，那么將會把此進(jìn)程從CPU釋放出來，并把 CPU分配另外一個進(jìn)程
- 如果該進(jìn)程在時間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換
另外。時間片的長度就是一個很關(guān)鍵的點：
- 如果時間片設(shè)的太短會導(dǎo)致過多的進(jìn)程上下文切換，降低了 CPU 效率
- 如果設(shè)的太長又可能引起對短作業(yè)進(jìn)程的響應(yīng)時間變長，通常將時間片設(shè)置為 20ms-50ms 是一個比較合理的折中值。
最高優(yōu)先級調(diào)度算法
前面的 [時間片輪轉(zhuǎn)算法] 做了一個假設(shè)，即讓所有的進(jìn)程同等重要，也不偏袒誰，大家的運行時間都一樣。
但是對于多用戶計算機系統(tǒng)就有不同的看法了，它們希望調(diào)度是有優(yōu)先級的，即希望調(diào)度程序能從就緒隊列中選擇最高優(yōu)先級的進(jìn)程進(jìn)行運行，這稱為最高優(yōu)先級（HPF）調(diào)度算法。
進(jìn)程的優(yōu)先級可以分為，靜態(tài)優(yōu)先級或動態(tài)優(yōu)先級：
- 靜態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時候，就已經(jīng)確定優(yōu)先級了，然后整個運行時間優(yōu)先級都不會變化；
- 動態(tài)優(yōu)先級：根據(jù)進(jìn)程的動態(tài)變化調(diào)整優(yōu)先級，比如如果進(jìn)程運行時間增加，則降低其優(yōu)先級，如果進(jìn)程等待時間（就緒隊列的等待時間）增加，則升高其優(yōu)先級，也就是隨著時間的推移增加等待進(jìn)程的優(yōu)先級。
該算法也有兩種處理優(yōu)先級高的方法，非搶占式和搶占式：
- 非搶占式：當(dāng)就緒隊列中出現(xiàn)優(yōu)先級高的進(jìn)程，運行完當(dāng)前進(jìn)程，再選擇優(yōu)先級高的進(jìn)程。
- 搶占式：當(dāng)就緒隊列中出現(xiàn)優(yōu)先級高的進(jìn)程，當(dāng)前進(jìn)程掛起，調(diào)度優(yōu)先級高的進(jìn)程運行。
但是依然有缺點，可能會導(dǎo)致低優(yōu)先級的進(jìn)程永遠(yuǎn)不會運行。
多級反饋隊列調(diào)度算法
多級反饋隊列（MFQ）調(diào)度算法是 [時間片輪轉(zhuǎn)算法] 和 [最高優(yōu)先級算法] 的綜合和發(fā)展。
顧名思義：
- [多級] 表示有多個隊列，每個隊列優(yōu)先級從高到低，同時優(yōu)先級越高時間片越短
- [反饋] 表示如果有新的進(jìn)程加入優(yōu)先級高的隊列時，立刻停止當(dāng)前正在運行的進(jìn)程，轉(zhuǎn)而去運行優(yōu)先級高的隊列
?工作方式：文章來源：http://www.zghlxwxcb.cn/news/detail-665606.html
- 設(shè)置多個隊列，賦予每個隊列不同的優(yōu)先級，每個隊列優(yōu)先級從高到低，同時優(yōu)先級越高時間片越短。
- 新的進(jìn)程會被放入到第一級隊列的末尾，按先來先服務(wù)的原則排隊等待被調(diào)度，如果在第一級隊列規(guī)定的時間片沒運行完成，則將其裝入到第二級隊列的末尾，以此類推，直至完成
- 當(dāng)較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進(jìn)程運行。如果進(jìn)程運行時，有新的進(jìn)程進(jìn)入較高優(yōu)先級的隊列，則停止當(dāng)前運行的進(jìn)程并將其移入到原隊列末尾，接著讓較高優(yōu)先級的進(jìn)程運行
可以發(fā)現(xiàn)，對于短作業(yè)可能可以在第一級隊列很快被處理完。對于長作業(yè)，如果在第一級隊列處理不完，可以移入下次隊列等待被執(zhí)行，雖然等待的時間變長了，但是運行時間也會變長，所以該算法很好的兼顧了長短作業(yè)，同時有較好的響應(yīng)時間。文章來源地址http://www.zghlxwxcb.cn/news/detail-665606.html
到了這里，關(guān)于（學(xué)習(xí)筆記-調(diào)度算法）進(jìn)程調(diào)度算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
