圖解經(jīng)典的進(jìn)程調(diào)度算法

文中的很多圖片來源我考研時看的網(wǎng)課，B 站上應(yīng)該還能找到，王道考研出品的操作系統(tǒng)系列，各位可以去看看，適用于考試，不太適用于春招秋招，因為知識點(diǎn)講的太細(xì)，邊邊角角都會講到，各位可以挑幾個章節(jié)去看。全文脈絡(luò)思維導(dǎo)圖如下：

1. 調(diào)度的概念

當(dāng) CPU 有一堆任務(wù)要處理時，由于其資源有限，這些事情就沒法同時處理。這就需要確定某種規(guī)則來決定處理這些任務(wù)的順序，這就是 “調(diào)度” 研究的問題。除了接下來將要說的進(jìn)程調(diào)度，還有作業(yè)調(diào)度、內(nèi)存調(diào)度等。

回顧一下進(jìn)程的三態(tài)模型：

• 「運(yùn)行態(tài)」（running）：進(jìn)程占有 CPU 正在運(yùn)行。
• 「就緒態(tài)」（ready）：進(jìn)程具備運(yùn)行條件，等待系統(tǒng)分配 CPU 以便運(yùn)行。
• 「阻塞態(tài)」 / 等待態(tài)（wait）：進(jìn)程不具備運(yùn)行條件，正在等待某個事件的完成。

所謂進(jìn)程調(diào)度，就是「從進(jìn)程的就緒隊列（阻塞）中按照一定的算法選擇一個進(jìn)程并將 CPU 分配給它運(yùn)行」，以實現(xiàn)進(jìn)程的并發(fā)執(zhí)行。這是操作系統(tǒng)中最基本（最低級）的一種調(diào)度，在一般的操作系統(tǒng)中都必須配置進(jìn)程調(diào)度。進(jìn)程調(diào)度的頻率很高，一般幾十毫秒一次。

2. 非搶占式進(jìn)程調(diào)度算法

所謂非搶占式的意思就是，當(dāng)進(jìn)程正在運(yùn)行時，它就會一直運(yùn)行，直到該進(jìn)程完成或發(fā)生某個事件發(fā)生而被阻塞時，才會把 CPU 讓給其他進(jìn)程。

對應(yīng)的，搶占式的意思就是，當(dāng)進(jìn)程正在運(yùn)行的時，可以被打斷，把 CPU 讓給其他進(jìn)程。

① 先到先服務(wù) FCFS

先來先服務(wù)調(diào)度算法（First Come First Serve，F(xiàn)CFS）：按照進(jìn)程到達(dá)的先后順序進(jìn)行調(diào)度，「先到的進(jìn)程就先被調(diào)度」，也就是說，等待時間越久的越優(yōu)先得到服務(wù)。

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

缺點(diǎn)：對短進(jìn)程不利。排在長進(jìn)程后面的短進(jìn)程需要等待很長時間，短進(jìn)程的響應(yīng)時間太長了，用戶交互體驗會變差。

② 最短作業(yè)優(yōu)先 SJF

最短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法（Shortest Job First，SJF）：「每次調(diào)度時選擇當(dāng)前已到達(dá)的、且運(yùn)行時間最短的進(jìn)程」。

最短作業(yè)優(yōu)先算法和先到先服務(wù)恰好相反，先到先服務(wù)對短進(jìn)程不利，而最短作業(yè)優(yōu)先算法對長程不利。因為如果一直有短進(jìn)程到來，那么長進(jìn)程永遠(yuǎn)得不到調(diào)度，長進(jìn)程有可能會餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。

③ 高響應(yīng)比優(yōu)先 HRRN

高響應(yīng)比優(yōu)先算法（Highest Response Ratio Next，HRRN）：只有當(dāng)前運(yùn)行的進(jìn)程主動放棄 CPU 時（正常/異常完成，或主動阻塞），才需要進(jìn)行調(diào)度，「調(diào)度時計算所有就緒進(jìn)程的響應(yīng)比，為響應(yīng)比最高的進(jìn)程分配 CPU」。響應(yīng)比 = (進(jìn)程的等待時間 + 進(jìn)程需要的運(yùn)行時間) / 進(jìn)程需要的運(yùn)行時間

3. 搶占式進(jìn)程調(diào)度算法

搶占就是指當(dāng)進(jìn)程正在運(yùn)行的時，可以被打斷，把 CPU 讓給其他進(jìn)程。搶占的原則一般有三種，分別是時間片原則、優(yōu)先權(quán)原則、短作業(yè)優(yōu)先原則。

① 最短剩余時間優(yōu)先 SRTN

最短剩余時間優(yōu)先（Shortest Remaining Time Next，SRTN）算法是「最短作業(yè)優(yōu)先的搶占式版本」。

「當(dāng)一個新的進(jìn)程到達(dá)時，把它所需要的整個運(yùn)行時間與當(dāng)前進(jìn)程的剩余運(yùn)行時間作比較。如果新的進(jìn)程需要的時間更少，則掛起當(dāng)前進(jìn)程，運(yùn)行新的進(jìn)程，否則新的進(jìn)程等待。」

② 輪轉(zhuǎn)調(diào)度算法 RR

輪轉(zhuǎn)調(diào)度算法（Round Robin，RR）也稱時間片調(diào)度算法：調(diào)度程序每次把 CPU 分配給就緒隊列首進(jìn)程使用規(guī)定的時間間隔，稱為時間片，通常為 10ms ~ 200ms，「就緒隊列中的每個進(jìn)程輪流地運(yùn)行一個時間片，當(dāng)時間片耗盡時就強(qiáng)迫當(dāng)前運(yùn)行進(jìn)程讓出 CPU 資源，轉(zhuǎn)而排到就緒隊列尾部，等待下一輪調(diào)度」。所以，一個進(jìn)程一般都需要多次輪轉(zhuǎn)才能完成。

輪轉(zhuǎn)調(diào)度算法對每個進(jìn)程都一視同仁，就好比大家都排好隊，一個一個來，每個人都運(yùn)行一會兒再接著重新排隊等待運(yùn)行。

需要注意的是：時間片的長度是一個很關(guān)鍵的因素：

• 如果時間片設(shè)置得太短，就會導(dǎo)致頻繁的進(jìn)程上下文切換，降低了 CPU 效率；
• 如果時間片設(shè)置得太長，那么隨著就緒隊列中進(jìn)程數(shù)目的增加，輪轉(zhuǎn)一次消耗的總時間加長，即每隔進(jìn)程的相應(yīng)速度放慢。甚至?xí)r間片大到讓進(jìn)程足以完成其所有任務(wù)，RR 調(diào)度算法便退化成 FCFS 算法。

4. 最高優(yōu)先級調(diào)度算法 HPF

RR 調(diào)度算法對所有的進(jìn)程都是相同的策略，如果用戶進(jìn)程太多，可能會導(dǎo)致內(nèi)核的服務(wù)進(jìn)程響應(yīng)跟不上。而在操作系統(tǒng)中，內(nèi)核進(jìn)程是比用戶進(jìn)程重要的多的，畢竟它關(guān)乎整個系統(tǒng)的穩(wěn)定性。

最高優(yōu)先級調(diào)度算法（Highest Priority First，HPF）就是「從就緒隊列中選擇最高優(yōu)先級的進(jìn)程進(jìn)行運(yùn)行」。進(jìn)程的優(yōu)先級是怎么規(guī)定的呢？分為靜態(tài)優(yōu)先級或動態(tài)優(yōu)先級：

• 「靜態(tài)優(yōu)先級」：創(chuàng)建進(jìn)程時候，就預(yù)先規(guī)定優(yōu)先級，并且整個運(yùn)行過程中該進(jìn)程的優(yōu)先級都不會發(fā)生變化。一般來說，內(nèi)核進(jìn)程的優(yōu)先級都是高于用戶進(jìn)程的。
• 「動態(tài)優(yōu)先級」：根據(jù)進(jìn)程的動態(tài)變化調(diào)整優(yōu)先級。比如隨著進(jìn)程的運(yùn)行時間增加，適當(dāng)?shù)慕档推鋬?yōu)先級；隨著就緒隊列中進(jìn)程的等待時間增加，適當(dāng)?shù)纳咂鋬?yōu)先級。

另外，需要注意的是，最高優(yōu)先級算法并非是固定的搶占式策略或非搶占式，「系統(tǒng)可預(yù)先規(guī)定使用哪種策略」：

• 非搶占式：當(dāng)就緒隊列中出現(xiàn)優(yōu)先級高的進(jìn)程，則運(yùn)行完當(dāng)前進(jìn)程后，再選擇該優(yōu)先級高的進(jìn)程。
• 搶占式：當(dāng)就緒隊列中出現(xiàn)優(yōu)先級高的進(jìn)程，則立即強(qiáng)制剝奪當(dāng)前運(yùn)行進(jìn)程的 CPU 資源，分配給優(yōu)先級更高的進(jìn)程運(yùn)行。

?? 點(diǎn)擊下方卡片關(guān)注公眾號「飛天小牛肉」（專注于分享計算機(jī)基礎(chǔ)、Java 基礎(chǔ)和面試指南的相關(guān)原創(chuàng)技術(shù)好文，幫助讀者快速掌握高頻重點(diǎn)知識，有的放矢），與小牛肉一起成長、共同進(jìn)步?

???并向大家強(qiáng)烈推薦我維護(hù)的?Gitee 倉庫?「CS-Wiki」（Gitee 推薦項目，目前已 1.0k+ star。致力打造完善的后端知識體系，在技術(shù)的路上少走彎路。相比公眾號，該倉庫擁有更健全的知識體系，歡迎給位小伙伴前來交流學(xué)習(xí)，倉庫地址 https://gitee.com/veal98/CS-Wiki。也可直接下方掃碼訪問