關(guān)于操作系統(tǒng)是如何虛擬化 CPU 的我們上一篇文章已經(jīng)聊過了，今天再深入一下，聊一聊進(jìn)程調(diào)度那些事。

[[318073]]

我們已經(jīng)知道，對(duì) CPU 虛擬化的目的就是能夠同時(shí)運(yùn)行多個(gè)進(jìn)程(這不是唯一目的)，而實(shí)質(zhì)就是對(duì)進(jìn)程的切換，也就是快速的切換執(zhí)行多個(gè)進(jìn)程，這樣對(duì)于用戶而言，所有的進(jìn)程都是同時(shí)進(jìn)行的，但是我們應(yīng)該如何對(duì)多個(gè)進(jìn)程來公平合理并安全高效的運(yùn)行呢?所以，我們就出現(xiàn)了很多的進(jìn)程調(diào)度算法。這里我們由淺入深，來講一下目前比較廣泛的算法。

第一個(gè)就是最簡(jiǎn)單的先進(jìn)先出(FIFO)，也可以叫做先到先服務(wù)。這個(gè)算法的最大優(yōu)點(diǎn)就是簡(jiǎn)單。沒錯(cuò)，就是我們理解的那個(gè)進(jìn)程先來了，CPU 就先處理哪個(gè)，等當(dāng)前的處理結(jié)束，在處理下一個(gè)。

我們假設(shè)有三個(gè)進(jìn)程，每一個(gè)進(jìn)程處理需要10s，這時(shí)，無論哪個(gè)進(jìn)程先來，最后一個(gè)進(jìn)程的完成時(shí)間都是30s，也就是說這種情況下最大完成時(shí)間是所有進(jìn)程需要時(shí)間之和。但是如果同樣有三個(gè)進(jìn)程，其中兩個(gè)進(jìn)程需要10s，另外一個(gè)進(jìn)程需要100s，這種情況，最大完成時(shí)間就是120s，由于三個(gè)進(jìn)程的各自完成時(shí)間不同，所以根據(jù)他們到達(dá)的順序不同最終的影響也有很大差異。假設(shè)三個(gè)進(jìn)程 A(10s)、B(10s)、C(100s)，如果按照 A、B、C 的順序到達(dá)，那么執(zhí)行的過和我們預(yù)想的是一樣的，開始十秒鐘，A 執(zhí)行結(jié)束，二十秒后，B 執(zhí)行結(jié)束，一百二十秒后，C執(zhí)行結(jié)束。但是如果是按照相反的順序到達(dá)的呢?C、B、A，這樣開始一百秒后，C 執(zhí)行結(jié)束，一百一十秒后，B 執(zhí)行結(jié)束，一百二十秒后，A 執(zhí)行結(jié)束。很顯然，這種情況下，B 和 A 都要等待時(shí)間最長(zhǎng)的 C 結(jié)束才可以執(zhí)行，所以這個(gè)算法的效率根據(jù)到達(dá)的順序有很大關(guān)系。顯然，這并不是我們想要的。在這里我們計(jì)算一下進(jìn)程的平均周轉(zhuǎn)時(shí)間，當(dāng)三個(gè)進(jìn)程都需要10s的時(shí)候平均周轉(zhuǎn)時(shí)間：

(10+20+30)/3=20，因?yàn)? A 在第10s完成，B 在第20s完成，C 在第30s完成。大家想一下當(dāng)進(jìn)程 A、B、C 時(shí)間分別為 10s、10s、100s呢?此時(shí)進(jìn)程的順序是 C、B、A，那么平均周轉(zhuǎn)時(shí)間就是：(100+110+120)/3=110。這是我們不能接受的。這個(gè)問題通常被稱為護(hù)航效應(yīng)(convoy effect)。這種情況在我們生活中也是非常常見的，例如我們?nèi)ヒ粋€(gè)地方辦一件事，大多數(shù)人只需要一分鐘就可以辦完，但是前面有一個(gè)人需要三十分鐘才可以辦完，那么后面的人都要一起等待這三十分鐘。

針對(duì)上面的問題，我們有新的解決方案：最短任務(wù)優(yōu)先(SJF)與最短完成時(shí)間優(yōu)先(STCF)。

最短任務(wù)優(yōu)先顧名思義，就是需要占用 CPU 時(shí)間短的進(jìn)程先執(zhí)行，也就是在上面的例子中(A需要10s、B需要20s、C需要100s)，先讓A和B先到達(dá)，執(zhí)行結(jié)束后在執(zhí)行C。但是這種算法中，我們依然不能保證C一定最后到達(dá)，如果C依然是最先到達(dá)，情況依然糟糕，情況下圖：

SJF

為了解決這個(gè)問題，我們放款條件，就是我們不需要保證所有的進(jìn)程必須一次都執(zhí)行完?，F(xiàn)在我們?cè)诩僭O(shè)最壞的情況，C先到達(dá)，之后才是A和B。當(dāng)C總執(zhí)行時(shí)間需要100s時(shí)，剛開始執(zhí)行到了10s的時(shí)候，B到達(dá)，此時(shí)我們不需要保證C執(zhí)行全部完成，發(fā)現(xiàn)B的時(shí)間只需要10s就可以結(jié)束，此時(shí)就暫停C同時(shí)開始執(zhí)行B，當(dāng)B執(zhí)行結(jié)束后，A又到達(dá)，此時(shí)我們同樣不執(zhí)行C而是執(zhí)行A，當(dāng)A結(jié)束后，我們?cè)倩氐紺，這樣性能又上升了一個(gè)臺(tái)階。如下圖：

STCF

上面的算法中主要考量的是平均周轉(zhuǎn)時(shí)間，但是現(xiàn)實(shí)中如果用這樣的算法依然是不可靠的，試想我們打開一個(gè)軟件，某一個(gè)功能需要等待100s后才反應(yīng)，那我們豈不是要瘋掉?此時(shí)新的度量指標(biāo)出現(xiàn)了：響應(yīng)時(shí)間(響應(yīng)時(shí)間=首次運(yùn)行-到達(dá)時(shí)間)。

我們?cè)俳榻B新的算法，輪轉(zhuǎn)(Round-Robin，RR)。顧名思義，就是輪訓(xùn)執(zhí)行進(jìn)程。在一個(gè)時(shí)間片內(nèi)運(yùn)行一個(gè)工作，然后切換到運(yùn)行隊(duì)列中的下一個(gè)任務(wù)。重復(fù)執(zhí)行，直到所有結(jié)束。這里我們有一點(diǎn)需要注意，就是時(shí)間片需要是時(shí)鐘中斷周期的倍數(shù)，時(shí)鐘中斷部分這里不再細(xì)講，上一篇文章我們已經(jīng)聊過了。假如時(shí)鐘中斷周期是10ms，那么時(shí)間片可以是10ms、20ms、30ms或者10ms的任何倍數(shù)。三個(gè)進(jìn)程A、B、C，所需時(shí)間都是5，如果使用RR這種算法，執(zhí)行過程就是如下圖：

RR

但是這種算法還要付出另外的代價(jià)，就是上下文切換的成本。所以說需要找一個(gè)合理的時(shí)間片。但是最主要的問題是，這種算法與之前的最短任務(wù)優(yōu)先與最短完成時(shí)間優(yōu)先是有些相反的，也就是說，這種算法導(dǎo)致了周轉(zhuǎn)時(shí)間變得更長(zhǎng)。如圖例子，A程序在13完成，B在14，C在15，這是非常可怕的。

現(xiàn)在我們有了兩種算法，各自的度量標(biāo)準(zhǔn)不同，一個(gè)是周轉(zhuǎn)時(shí)間，另一個(gè)是響應(yīng)時(shí)間，但是魚與熊掌不可兼得的道理大家都知道，那么我們具體應(yīng)該怎么做呢?下一篇文章我們繼續(xù)聊更加完善的兩個(gè)算法多級(jí)反饋隊(duì)列與比例份額。​這兩個(gè)算法內(nèi)容較多，所以再單獨(dú)拿出來。

今天說的是比較基礎(chǔ)的東西，可以說的進(jìn)程調(diào)度思想的一個(gè)起步，有了這個(gè)基礎(chǔ)我們就可以更加深入的理解后面的多級(jí)反饋隊(duì)列算法與比例份額。再啰嗦幾句，最近為什么要寫操作系統(tǒng)相關(guān)的內(nèi)容呢?因?yàn)槲矣X得這對(duì)生產(chǎn)是有很大幫助的，尤其在生產(chǎn)環(huán)境中找問題，性能提升等，所以建議大家可以了解一些。這也是我一直所提倡的，語言只是工具，框架也是工具，但是百變不離其宗，只有掌握了最核心，最基礎(chǔ)的才能所向披靡。