[[382804]]

本文轉(zhuǎn)載自微信公眾號(hào)「飛天小牛肉」，作者飛天小牛肉。轉(zhuǎn)載本文請(qǐng)聯(lián)系飛天小牛肉公眾號(hào)。

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

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

當(dāng) CPU 有一堆任務(wù)要處理時(shí)，由于其資源有限，這些事情就沒(méi)法同時(shí)處理。這就需要確定某種規(guī)則來(lái)決定處理這些任務(wù)的順序，這就是 “調(diào)度” 研究的問(wèn)題。除了接下來(lái)將要說(shuō)的進(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)行條件，正在等待某個(gè)事件的完成。

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

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

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

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

① 先到先服務(wù) FCFS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

需要注意的是：時(shí)間片的長(zhǎng)度是一個(gè)很關(guān)鍵的因素：

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

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

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

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

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

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

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