王道操作系統(tǒng)第2章-進(jìn)程管理-調(diào)度

第2章-進(jìn)程管理-進(jìn)程調(diào)度

調(diào)度的概念、層次

當(dāng)有一堆任務(wù)要處理，但資源有限，這些事情沒法同時處理，這就需要確定某種規(guī)則來決定處理這些任務(wù)的順序，這就是“調(diào)度”研究的問題

調(diào)度的三個層次

高級調(diào)度（作業(yè)調(diào)度）

作業(yè)：一個具體的任務(wù)用戶向系統(tǒng)提交一個作業(yè)≈用戶讓操作系統(tǒng)啟動一個程序（來處理一個具體的任務(wù)）內(nèi)存空間有限，有時無法將用戶提交的作業(yè)全部放入內(nèi)存

高級調(diào)度：按一定的原則從外存的作業(yè)后備隊列中挑選一個作業(yè)調(diào)入內(nèi)存，并創(chuàng)建進(jìn)程。每個作業(yè)只調(diào)入一次，調(diào)出一次。作業(yè)調(diào)入時會建立PCB，調(diào)出時才撤銷PCB

低級調(diào)度（進(jìn)程調(diào)度/處理機(jī)調(diào)度）

低級調(diào)度：按照某種策略從就緒隊列中選取一個進(jìn)程，將處理機(jī)分配給它

進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，在一般的操作系統(tǒng)中都必須配置進(jìn)程調(diào)度

進(jìn)程調(diào)度的頻率很高，一般幾十毫秒一次

中級調(diào)度（內(nèi)存調(diào)度）

內(nèi)存不夠時，可將某些進(jìn)程的數(shù)據(jù)調(diào)出外存，等內(nèi)存空閑或者進(jìn)程需要運行時再重新調(diào)入內(nèi)存暫時調(diào)到外存等地的進(jìn)程狀態(tài)為掛起狀態(tài)，被掛起的進(jìn)程PCB會被組織成掛起隊列

中級調(diào)度：按照某種策略決定將哪個處于掛起狀態(tài)的進(jìn)程重新調(diào)入內(nèi)存一個進(jìn)程可能會被多次調(diào)出、調(diào)入內(nèi)存，因此中級調(diào)度發(fā)生的頻率要比高級調(diào)度更高

補(bǔ)充知識：進(jìn)程的掛起態(tài)和七狀態(tài)模型

暫時調(diào)到外存等待的進(jìn)程狀態(tài)為掛起狀態(tài)（suspend）

掛起態(tài)又可以進(jìn)一步細(xì)分為就緒掛起、阻塞掛起兩種狀態(tài)

五狀態(tài)模型\rightarrow七狀態(tài)模型

三層調(diào)度的聯(lián)系和對比

要做什么調(diào)度發(fā)生在..發(fā)生頻率對進(jìn)程狀態(tài)的影響高級調(diào)度(作業(yè)調(diào)度)按照某種規(guī)則,從后備隊列中選擇合適的作業(yè)將其調(diào)入內(nèi)存,并為其創(chuàng)建進(jìn)程外存\rightarrow內(nèi)存(面相作業(yè))最低無\rightarrow創(chuàng)建態(tài)\rightarrow就緒態(tài)中級調(diào)度(內(nèi)存調(diào)度)按照某種規(guī)則,從掛起隊列中選擇合適的進(jìn)程將其數(shù)據(jù)調(diào)回內(nèi)存外存\rightarrow內(nèi)存(面相進(jìn)程)中等掛起態(tài)\rightarrow就緒態(tài)(阻塞掛起\rightarrow阻塞態(tài))低級調(diào)度(進(jìn)程調(diào)度)按照某種規(guī)則,從就緒隊列中選擇一個進(jìn)程為其分配處理機(jī)內(nèi)存\rightarrowCPU最高就緒態(tài)\rightarrow運行態(tài)

進(jìn)程調(diào)度的時機(jī)、切換與過程、方式

進(jìn)程調(diào)度的時機(jī)

進(jìn)程調(diào)度（低級調(diào)度）：就是按照算法從就緒隊列中選擇一個進(jìn)程為其分配處理機(jī)

• 需要進(jìn)行進(jìn)程調(diào)度與切換的情況

• 分給進(jìn)程的時間片用完

• 有更緊急的事需要處理（如IO中斷）

• 有更高優(yōu)先級的進(jìn)程進(jìn)入就緒隊列

• 進(jìn)程正常終止

• 運行過程中發(fā)生異常而終止

• 進(jìn)程主動請求阻塞（如等待IO）

1. 當(dāng)前運行的進(jìn)程主動放棄處理機(jī)

2. 當(dāng)前運行的進(jìn)程被動放棄處理機(jī)

• 不能進(jìn)行進(jìn)程調(diào)度與切換的情況

1. 在處理中斷的過程中。中斷處理過程復(fù)雜，與硬件密切相關(guān)，很難做到在中斷處理過程中進(jìn)行進(jìn)程切換

2. 進(jìn)程在操作系統(tǒng)內(nèi)核程序臨界區(qū)中。

3. 在原子操作過程中（原語）。原子操作不可中斷，要一氣呵成（如之前講過的修改PCB進(jìn)程狀態(tài)標(biāo)志，并把PCB放到相應(yīng)隊列）

進(jìn)程在操作系統(tǒng)內(nèi)核臨界區(qū)中不能進(jìn)行調(diào)度與切換(√)

(2012真題)進(jìn)程處于臨界區(qū)時不能進(jìn)行處理機(jī)調(diào)度(×)

臨界資源:一個時間段只允許一個進(jìn)程使用的資源，各進(jìn)程需要互斥地訪問臨界資源臨界區(qū):訪問臨界資源的那段代碼

內(nèi)核程序臨界區(qū)一般是用來訪問某種內(nèi)核數(shù)據(jù)結(jié)構(gòu)的，比如進(jìn)程的就緒隊列（由各就緒進(jìn)程的PCB組成）

當(dāng)有一個進(jìn)程處于內(nèi)核程序臨界區(qū)，并且要訪問就緒隊列時，在訪問之前會把就緒隊列上鎖，如果還沒有退出臨界區(qū)（還沒解鎖）就進(jìn)行進(jìn)程調(diào)度，但是進(jìn)程調(diào)度相關(guān)的程序也需要訪問就緒隊列，但此時就緒隊列被鎖住了，因此又無法順利進(jìn)行進(jìn)程調(diào)度。

內(nèi)核程序臨界區(qū)訪問的臨界資源如果不盡快釋放的話，極有可能影響到操作系統(tǒng)內(nèi)核的其他管理工作。因此在訪問內(nèi)核程序臨界區(qū)期間不能進(jìn)行調(diào)度與切換。

另一種情況，當(dāng)進(jìn)程訪問的是普通的臨界資源如打印機(jī)時，在打印機(jī)打印完成之前，進(jìn)程一直處于臨界區(qū)內(nèi)，臨界資源不會解鎖。但打印機(jī)又是慢速設(shè)備，此時如果一直不允許進(jìn)程調(diào)度的話就會導(dǎo)致CPU一直空閑。

普通臨界區(qū)訪問的臨界資源不會直接影響操作系統(tǒng)內(nèi)核的管理工作。因此在訪問普通臨界區(qū)時可以進(jìn)行調(diào)度與切換。

進(jìn)程調(diào)度的方式

1. 非剝奪調(diào)度方式：又稱非搶占方式。即只允許進(jìn)程主動放棄處理機(jī)，在運行過程中即便有更緊迫的任務(wù)到達(dá)，當(dāng)前進(jìn)程依然會繼續(xù)使用處理機(jī)，直到該進(jìn)程終止或主動要求進(jìn)入阻塞態(tài)。特點：實現(xiàn)簡單，系統(tǒng)開銷小，但是無法及時處理緊急任務(wù)，適合于早期的批處理系統(tǒng)

2. 剝奪調(diào)度方式：又稱搶占方式。當(dāng)一個進(jìn)程正在處理機(jī)上執(zhí)行時，如果有一個更重要或更緊迫的進(jìn)程需要使用處理機(jī)，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給更重要緊迫的那個進(jìn)程特點：可以優(yōu)先處理更緊急的進(jìn)程，也可以實現(xiàn)讓各進(jìn)程按時間片輪流執(zhí)行的功能（通過時鐘中斷）。適合于分時操作系統(tǒng)、實時操作系統(tǒng)

進(jìn)程的切換與過程

“狹義的進(jìn)程調(diào)度”與“進(jìn)程切換”的區(qū)別：狹義的進(jìn)程調(diào)度指的是從就緒隊列中選中一個要運行的進(jìn)程（這個進(jìn)程可以是剛剛被暫停執(zhí)行的進(jìn)程，也可能是另一個進(jìn)程，后一種情況就需要進(jìn)程切換）進(jìn)程切換是指一個進(jìn)程讓出處理機(jī)，由另一個進(jìn)程占用處理機(jī)的過程

廣義的進(jìn)程調(diào)度包含了選擇一個進(jìn)程和進(jìn)程切換兩個步驟

• 進(jìn)程切換的過程主要完成了：

1. 對原來運行各種數(shù)據(jù)的保存

2. 對新的進(jìn)程各種數(shù)據(jù)的恢復(fù)（如：程序計數(shù)器、程序狀態(tài)字、各種數(shù)據(jù)寄存器等處理機(jī)現(xiàn)場信息，這些信息一般保存在進(jìn)程控制塊）

進(jìn)程切換是有代價的，因此如果過于頻繁地進(jìn)行進(jìn)程調(diào)度、切換，必然會使整個系統(tǒng)的效率降低，使系統(tǒng)大部分時間都花在進(jìn)程切換上，而真正用于執(zhí)行進(jìn)程的時間減少

調(diào)度器和閑逛進(jìn)程

調(diào)度器/調(diào)度程序(scheduler)

②、③由程序調(diào)度引起，調(diào)度程序決定：

1. 讓誰運行？——調(diào)度算法

2. 運行多長時間？——時間片大小

調(diào)度時機(jī)——什么事件會觸發(fā)“調(diào)度程序”？

• 創(chuàng)建新進(jìn)程

• 進(jìn)程退出

• 運行進(jìn)程阻塞

• IO中斷發(fā)生（可能喚醒某些阻塞進(jìn)程）

非搶占式調(diào)度策略：只有運行進(jìn)程阻塞或退出才觸發(fā)調(diào)度程序工作搶占式調(diào)度策略：每個時鐘中斷或k個時鐘中斷會觸發(fā)調(diào)度程序工作

不支持內(nèi)核級線程的操作系統(tǒng)，調(diào)度程序的處理對象是進(jìn)程支持內(nèi)核級程序的操作系統(tǒng)，調(diào)度程序的處理對象是內(nèi)核線程

閑逛進(jìn)程

調(diào)度程序永遠(yuǎn)的備胎，沒有其他就緒進(jìn)程時，運行閑逛進(jìn)程

• 閑逛進(jìn)程的特性：

• 優(yōu)先級最低

• 可以是0地址指令，占一個完整的指令周期（指令周期末尾例行檢查中斷）

• 耗能低

調(diào)度算法的評價指標(biāo)

1. CPU利用率:指CPU"忙碌"的時間占總時間的比例

2. 系統(tǒng)吞吐量:單位時間完成的作業(yè)的數(shù)量系統(tǒng)吞吐量=\frac{總共完成了多少道作業(yè)}{總共花了多少時間}某計算機(jī)系統(tǒng)處理完10道作業(yè)共花費100s,則系統(tǒng)吞吐量為0.1道/s

3. 周轉(zhuǎn)時間：指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔包括四個部分：作業(yè)在外存后備隊列上等待作業(yè)調(diào)度（高級調(diào)度）的時間、進(jìn)程在就緒隊列上等待進(jìn)程調(diào)度（低級調(diào)度）的事件、進(jìn)程在CPU上執(zhí)行的時間、進(jìn)程等待IO操作完成的事件。后三項（就緒態(tài)、運行態(tài)、阻塞態(tài)）在一個作業(yè)的整個處理過程中，可能發(fā)生多次作業(yè)周轉(zhuǎn)時間=作業(yè)完成時間-作業(yè)提交時間平均周轉(zhuǎn)時間=\frac{各作業(yè)周轉(zhuǎn)時間之和}{作業(yè)數(shù)}帶權(quán)周轉(zhuǎn)時間=\frac{作業(yè)周轉(zhuǎn)時間}{作業(yè)實際運行的時間}=\frac{作業(yè)完成時間-作業(yè)提交時間}{作業(yè)實際運行的時間}

   平均帶權(quán)周轉(zhuǎn)時間=\frac{各作業(yè)帶權(quán)周轉(zhuǎn)時間之和}{作業(yè)數(shù)}帶權(quán)周轉(zhuǎn)時間必然\ge1對于周轉(zhuǎn)時間相同的兩個作業(yè)，實際運行時間長的作業(yè)在相同時間內(nèi)被服務(wù)的時間更多，帶權(quán)周轉(zhuǎn)時間更小，用戶滿意度更高對于實際運行時間相同的兩個作業(yè)，周轉(zhuǎn)時間短的帶權(quán)周轉(zhuǎn)時間更小，用戶滿意度更高帶權(quán)周轉(zhuǎn)時間與周轉(zhuǎn)時間都是越小越好

4. 等待時間：指進(jìn)程/作業(yè)處于等待處理機(jī)狀態(tài)時間之和，等待時間越長，用戶滿意度越低對于進(jìn)程來說，等待時間就是指進(jìn)程建立后等待被服務(wù)的時間之和，在等待IO完成的期間其實進(jìn)程也是在被服務(wù)的，所以不計入等待時間對于作業(yè)來說，不僅要考慮建立進(jìn)程后的等待時間，還要加上作業(yè)在外存后備隊列中等待的時間一個作業(yè)總共被CPU服務(wù)多久，被IO設(shè)備服務(wù)多久一般是確定不變的，因此調(diào)度算法其實只會影響作業(yè)/進(jìn)程的等待時間。當(dāng)然與前面指標(biāo)類似，也有“平均等待時間”來評價整體性能。

5. 響應(yīng)時間：指用戶提交請求到首次響應(yīng)所用的時間

調(diào)度算法

饑餓：某進(jìn)程或作業(yè)長期得不到服務(wù)

先來先服務(wù)（FCFS，F(xiàn)irst Come First Serve）

• 算法思想：主要從”公平“的角度考慮

• 算法規(guī)則：按照作業(yè)/進(jìn)程到達(dá)的先后順序進(jìn)行服務(wù)

• 用于作業(yè)/進(jìn)程調(diào)度：用于作業(yè)調(diào)度時，考慮的是哪個作業(yè)先到達(dá)后備隊列；用于進(jìn)程調(diào)度時，考慮的是哪個進(jìn)程先到達(dá)就緒隊列

• 非搶占式的算法

• 優(yōu)缺點：

• 優(yōu)點：公平、算法實現(xiàn)簡單

• 缺點：排在長作業(yè)（進(jìn)程）后面的短作業(yè)需要等待很長時間，帶權(quán)周轉(zhuǎn)時間很大，對短作業(yè)來說用戶體驗不好。即FCFS算法對長作業(yè)有利，對短作業(yè)不利

短作業(yè)優(yōu)先（SJF，Shortest Job First）

• 算法思想：追求最少的平均等待時間，最少的平均周轉(zhuǎn)時間，最少的平均帶權(quán)周轉(zhuǎn)時間

• 算法規(guī)則：最短的作業(yè)/進(jìn)程優(yōu)先得到服務(wù)（所謂“最短”，是指要求服務(wù)時間最短）

• 用于作業(yè)/進(jìn)程調(diào)度：既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。用于進(jìn)程調(diào)度時稱為“短進(jìn)程優(yōu)先（SPF，Shortest Process First）算法”

• 是非搶占式的算法，但是也有搶占式的版本——最短剩余時間優(yōu)先算法（SRTN，Shortest Remaining Time Next）

非搶占式的短作業(yè)優(yōu)先算法

搶占式的短作業(yè)優(yōu)先算法（最短剩余時間優(yōu)先算法SRTN）

• 注意幾個小細(xì)節(jié)：

1. 如果題目未明確說明，所提到的“短作業(yè)/進(jìn)程優(yōu)先算法”默認(rèn)是非搶占式的

2. 嚴(yán)格來說“SJF調(diào)度算法的平均等待時間、平均周轉(zhuǎn)時間最少”這種說法是錯誤的，不嚴(yán)謹(jǐn)?shù)?。最短剩余時間優(yōu)先算法得到的平均等待時間、平均周轉(zhuǎn)時間還要更少。應(yīng)該加上條件“在所有進(jìn)程同時可運行時”或“所有進(jìn)程幾乎同時到達(dá)時”的前提條件才準(zhǔn)確。或者說“搶占式的短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法（即最短剩余時間有限SRNT算法）的平均等待時間、平均周轉(zhuǎn)時間最少）

3. 如果選擇題中遇到“SJF算法的平均等待時間、平均周轉(zhuǎn)時間最少”的選項，那最好判斷其他選項是否有很明顯的錯誤，如果沒有更合適的選項，也應(yīng)該選擇該項

• 短作業(yè)優(yōu)先算法的優(yōu)缺點

• 優(yōu)點：“最短的”平均等待時間、平均周轉(zhuǎn)時間

• 缺點：不公平。對短作業(yè)有利，對長作業(yè)不利。可能產(chǎn)生饑餓現(xiàn)象。另外，作業(yè)/進(jìn)程的運行時間是由用戶提供的，并不一定真實，不一定能做到真正的短作業(yè)有限

• 會導(dǎo)致饑餓，如果源源不斷地有短作業(yè)/進(jìn)程到來，可能使長作業(yè)/進(jìn)程長時間得不到服務(wù)，產(chǎn)生“饑餓”現(xiàn)象。如果一直得不到服務(wù)，則稱為“餓死”

高響應(yīng)比優(yōu)先算法（HRRN）

FCFS對每次調(diào)度時選擇一個等待時間最長的作業(yè)（進(jìn)程）服務(wù)，但是沒有考慮到作業(yè)的運行時間，對短作業(yè)不友好；SJF選擇一個執(zhí)行時間最短的作業(yè)為其服務(wù)，但是又完全不考慮各個作業(yè)的等待時間，因此導(dǎo)致了對長作業(yè)不友好的問題，甚至可能造成饑餓。因此推出了高響應(yīng)比優(yōu)先算法。

• 算法思想：要綜合考慮作業(yè)/進(jìn)程的等待時間和要求服務(wù)的時間

• 算法規(guī)則：在每次調(diào)度時先計算各個作業(yè)/進(jìn)程的響應(yīng)比，選擇響應(yīng)比最高的作業(yè)/進(jìn)程為其服務(wù)。響應(yīng)比=\frac{等待時間+要求服務(wù)時間}{要求服務(wù)時間}

• 用于作業(yè)/進(jìn)程調(diào)度：既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度

• 非搶占式的算法。因此只有當(dāng)前運行的作業(yè)/進(jìn)程主動放棄處理機(jī)時，才需要調(diào)度，才需要計算響應(yīng)比

• 優(yōu)點：綜合考慮了等待時間和運行時間（要求服務(wù)時間）等待時間相同時，要求服務(wù)時間短的優(yōu)先（SJF的優(yōu)點）要求服務(wù)時間相同時，等待時間長的優(yōu)先（FCFS的優(yōu)點）對于長作業(yè)來說，隨著等待時間越來越久，其響應(yīng)比也會越來越大，從而避免了長作業(yè)饑餓的問題

先來先服務(wù)、短作業(yè)優(yōu)先、高響應(yīng)比優(yōu)先算法都只適用于早期的批處理系統(tǒng)。適用于交互式系統(tǒng)的調(diào)度算法見下文

時間片輪轉(zhuǎn)調(diào)度算法

• 算法思想：公平地、輪流地為各個進(jìn)程服務(wù)，讓每個進(jìn)程在一定時間間隔內(nèi)都可以得到響應(yīng)

• 算法規(guī)則：按照各個進(jìn)程到達(dá)就緒隊列的順序，輪流讓各個進(jìn)程執(zhí)行一個時間片（如100ms）。若進(jìn)程未在一個時間片內(nèi)執(zhí)行完，則剝奪處理機(jī)，將進(jìn)程重新放到就緒隊列隊尾重新排隊

• 用于作業(yè)/進(jìn)程調(diào)度：用于進(jìn)程調(diào)度（只有作業(yè)放入內(nèi)存建立了相應(yīng)的進(jìn)程后，才能被分配處理機(jī)時間片

• 若進(jìn)程未能在時間片內(nèi)運行完，將被強(qiáng)行剝奪處理機(jī)使用權(quán)，因此時間片輪轉(zhuǎn)調(diào)度算法屬于搶占式的算法。由時鐘裝置發(fā)出時鐘中斷通知CPU時間片已到

• 如果時間片太大，使得每個進(jìn)程都可以在一個時間片內(nèi)完成，則時間片輪轉(zhuǎn)調(diào)度算法退化為先來先服務(wù)調(diào)度算法，并且會增大程序響應(yīng)時間。因此時間片不能太大

• 如果時間片太小，進(jìn)程調(diào)度、切換是有時間代價的（保護(hù)、恢復(fù)運行環(huán)境），進(jìn)程切換過于頻繁，系統(tǒng)會花大量時間來處理進(jìn)程切換，從而導(dǎo)致實際用于進(jìn)程執(zhí)行的時間比例減少。

• 時間片輪轉(zhuǎn)調(diào)度算法的優(yōu)缺點：

1. 優(yōu)點：公平、響應(yīng)快，適用于分時響應(yīng)系統(tǒng)

2. 缺點：由于高頻率的進(jìn)程切換，因此有一定的開銷；不區(qū)分任務(wù)的緊急程度

• 不會導(dǎo)致饑餓

優(yōu)先級調(diào)度算法

• 算法思想：隨著實時操作系統(tǒng)的出現(xiàn)，越來越多的應(yīng)用場景需要根據(jù)任務(wù)的緊急程度來決定處理順序

• 算法規(guī)則：每個作業(yè)/進(jìn)程都有各自的優(yōu)先級，調(diào)度時選擇優(yōu)先級最高的作業(yè)/進(jìn)程

• 用于作業(yè)/進(jìn)程調(diào)度：既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度，甚至可以用于之后學(xué)習(xí)的IO調(diào)度中

• 搶占式、非搶占式都有。非搶占式只需在進(jìn)程主動放棄處理機(jī)時進(jìn)行調(diào)度即可，而搶占式還需在就緒隊列變化時，檢查是否會發(fā)生搶占

非搶占式優(yōu)先級調(diào)度算法

搶占式優(yōu)先級調(diào)度算法

• 補(bǔ)充：

• 就緒隊列未必只有一個，可以按照不同優(yōu)先級來組織。另外，也可以把優(yōu)先級高的進(jìn)程排在更靠近隊頭的位置

• 根據(jù)優(yōu)先級是否可以動態(tài)改變，可以將優(yōu)先級分為靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級兩種靜態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時確定，之后一直不變動態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時有一個初始值，之后會根據(jù)情況動態(tài)地調(diào)整優(yōu)先級。比如，如果某進(jìn)程在就緒隊列中等待了很長時間，則可以適當(dāng)提升其優(yōu)先級；如果某進(jìn)程占用處理機(jī)運行了很長時間，則可適當(dāng)降低其優(yōu)先級

• 通常系統(tǒng)進(jìn)程優(yōu)先級高于用戶進(jìn)程；前臺進(jìn)程優(yōu)先級高于后臺進(jìn)程；操作系統(tǒng)更偏好IO型進(jìn)程（或IO繁忙型進(jìn)程）與IO型進(jìn)程相對的是計算型進(jìn)程（或稱CPU繁忙型進(jìn)程），IO設(shè)備和CPU可以并行工作，如果讓IO繁忙型進(jìn)程優(yōu)先運行的話，則越有可能讓IO設(shè)備盡早投入工作，則資源利用率、系統(tǒng)吞吐量都會得到提升

• 優(yōu)先級調(diào)度算法的優(yōu)缺點：

1. 優(yōu)點：用優(yōu)先級區(qū)分緊急程度、重要程度，適用于實時操作系統(tǒng)。可靈活地調(diào)整對各種作業(yè)/進(jìn)程的偏好程度

2. 缺點：若源源不斷地有高優(yōu)先級進(jìn)程到來，則可能導(dǎo)致饑餓

多級反饋隊列調(diào)度算法

• 算法思想：對其他調(diào)度算法的折中權(quán)衡

• 算法規(guī)則：

1. 設(shè)置多級就緒隊列，各級隊列優(yōu)先級從高到低，時間片從小到大

2. 新進(jìn)程到達(dá)時先進(jìn)入第1級隊列，按FCFS原則排隊等待被分配時間片，若用完時間片進(jìn)程還未結(jié)束，則進(jìn)程進(jìn)入下一級隊列隊尾。如果此時已經(jīng)是在最下級的隊列，則重新放回該隊列隊尾

3. 只有第k級隊列為空時，才會為k+1級隊頭的進(jìn)程分配時間片

• 用于進(jìn)程調(diào)度

• 搶占式的算法。在k級隊列的進(jìn)程運行過程中，若更上級的隊列（1~k-1級）中進(jìn)入了一個新進(jìn)程，則由于新進(jìn)程處于優(yōu)先級更高的隊列中，因此新進(jìn)程會搶占處理機(jī)，原來運行的進(jìn)程放回k級隊列隊尾

• 優(yōu)點：對各類型進(jìn)程相對公平（FCFS的優(yōu)點）；每個新到達(dá)的進(jìn)程都可以很快就得到響應(yīng)（RR的優(yōu)點）；短進(jìn)程只用較少的時間就可以完成（SPF的優(yōu)先）；不必實現(xiàn)估計進(jìn)程的運行時間（避免用戶作假）；可靈活地調(diào)整各類進(jìn)程的偏好程度，比如CPU密集型進(jìn)程、IO密集型進(jìn)程（拓展：可以將因IO而阻塞的進(jìn)程重新放回原隊列，這樣IO型進(jìn)程就可以保持較高優(yōu)先級）

• 有可能導(dǎo)致饑餓

多級隊列調(diào)度算法