譚清寬

對CPU虛擬化的目的之一就是能夠同時(shí)運(yùn)行多個進(jìn)程，實(shí)質(zhì)就是對進(jìn)程的切換，也就是快速的切換執(zhí)行多個進(jìn)程，這樣對于用戶而言，所有的進(jìn)程都是同時(shí)進(jìn)行的，但是應(yīng)該如何讓多個進(jìn)程公平合理并安全高效的運(yùn)行呢？所以，就出現(xiàn)了很多進(jìn)程調(diào)度算法。

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

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

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

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

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

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

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

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

但是這種算法還要付出另外的代價(jià)，就是上下文切換的成本。所以說需要找一個合理的時(shí)間片。但是最主要的問題是，這種算法與之前的最短任務(wù)優(yōu)先與最短完成時(shí)間優(yōu)先是有些相反的，也就是說，這種算法導(dǎo)致了周轉(zhuǎn)時(shí)間變得更長。

其實(shí)2種算法，各自的度量標(biāo)準(zhǔn)不同，一個是周轉(zhuǎn)時(shí)間，另一個是響應(yīng)時(shí)間，畢竟魚與熊掌不可兼得的道理大家都知道。