[[382804]]

本文轉載自微信公眾號「飛天小牛肉」，作者飛天小牛肉。轉載本文請聯系飛天小牛肉公眾號。

文中的很多圖片來源我考研時看的網課，B 站上應該還能找到，王道考研出品的操作系統系列，各位可以去看看，適用于考試，不太適用于春招秋招，因為知識點講的太細，邊邊角角都會講到，各位可以挑幾個章節去看。全文脈絡思維導圖如下：

1. 調度的概念

當 CPU 有一堆任務要處理時，由于其資源有限，這些事情就沒法同時處理。這就需要確定某種規則來決定處理這些任務的順序，這就是 “調度” 研究的問題。除了接下來將要說的進程調度，還有作業調度、內存調度等。

回顧一下進程的三態模型：

• 「運行態」(running)：進程占有 CPU 正在運行。
• 「就緒態」(ready)：進程具備運行條件，等待系統分配 CPU 以便運行。
• 「阻塞態」 / 等待態(wait)：進程不具備運行條件，正在等待某個事件的完成。

所謂進程調度，就是「從進程的就緒隊列(阻塞)中按照一定的算法選擇一個進程并將 CPU 分配給它運行」，以實現進程的并發執行。這是操作系統中最基本(最低級)的一種調度，在一般的操作系統中都必須配置進程調度。進程調度的頻率很高，一般幾十毫秒一次。

2. 非搶占式進程調度算法

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

對應的，搶占式的意思就是，當進程正在運行的時，可以被打斷，把 CPU 讓給其他進程。

① 先到先服務 FCFS

先來先服務調度算法(First Come First Serve，FCFS)：按照進程到達的先后順序進行調度，「先到的進程就先被調度」，也就是說，等待時間越久的越優先得到服務。

優點：公平、算法實現簡單

缺點：對短進程不利。排在長進程后面的短進程需要等待很長時間，短進程的響應時間太長了，用戶交互體驗會變差。

② 最短作業優先 SJF

最短作業/進程優先調度算法(Shortest Job First，SJF)：「每次調度時選擇當前已到達的、且運行時間最短的進程」。

最短作業優先算法和先到先服務恰好相反，先到先服務對短進程不利，而最短作業優先算法對長程不利。因為如果一直有短進程到來，那么長進程永遠得不到調度，長進程有可能會餓死，處于一直等待短作業執行完畢的狀態。

③ 高響應比優先 HRRN

高響應比優先算法(Highest Response Ratio Next，HRRN)：只有當前運行的進程主動放棄 CPU 時(正常/異常完成，或主動阻塞)，才需要進行調度，「調度時計算所有就緒進程的響應比，為響應比最高的進程分配 CPU」。響應比 = (進程的等待時間 + 進程需要的運行時間) / 進程需要的運行時間

3. 搶占式進程調度算法

搶占就是指當進程正在運行的時，可以被打斷，把 CPU 讓給其他進程。搶占的原則一般有三種，分別是時間片原則、優先權原則、短作業優先原則。

① 最短剩余時間優先 SRTN

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

「當一個新的進程到達時，把它所需要的整個運行時間與當前進程的剩余運行時間作比較。如果新的進程需要的時間更少，則掛起當前進程，運行新的進程，否則新的進程等待。」

② 輪轉調度算法 RR

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

輪轉調度算法對每個進程都一視同仁，就好比大家都排好隊，一個一個來，每個人都運行一會兒再接著重新排隊等待運行。

需要注意的是：時間片的長度是一個很關鍵的因素：

• 如果時間片設置得太短，就會導致頻繁的進程上下文切換，降低了 CPU 效率;
• 如果時間片設置得太長，那么隨著就緒隊列中進程數目的增加，輪轉一次消耗的總時間加長，即每隔進程的相應速度放慢。甚至時間片大到讓進程足以完成其所有任務，RR 調度算法便退化成 FCFS 算法。

4. 最高優先級調度算法 HPF

RR 調度算法對所有的進程都是相同的策略，如果用戶進程太多，可能會導致內核的服務進程響應跟不上。而在操作系統中，內核進程是比用戶進程重要的多的，畢竟它關乎整個系統的穩定性。

最高優先級調度算法(Highest Priority First，HPF)就是「從就緒隊列中選擇最高優先級的進程進行運行」。進程的優先級是怎么規定的呢?分為靜態優先級或動態優先級：

• 「靜態優先級」：創建進程時候，就預先規定優先級，并且整個運行過程中該進程的優先級都不會發生變化。一般來說，內核進程的優先級都是高于用戶進程的。
• 「動態優先級」：根據進程的動態變化調整優先級。比如隨著進程的運行時間增加，適當的降低其優先級;隨著就緒隊列中進程的等待時間增加，適當的升高其優先級。

另外，需要注意的是，最高優先級算法并非是固定的搶占式策略或非搶占式，「系統可預先規定使用哪種策略」：

• 非搶占式：當就緒隊列中出現優先級高的進程，則運行完當前進程后，再選擇該優先級高的進程。
• 搶占式：當就緒隊列中出現優先級高的進程，則立即強制剝奪當前運行進程的 CPU 資源，分配給優先級更高的進程運行。