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

[[318073]]

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

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

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

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

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

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

SJF

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

STCF

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

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

RR

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

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

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