操作系統(tǒng)的CPU虛擬化

譚清寬

對(duì)CPU虛擬化的目的之一就是能夠同時(shí)運(yùn)行多個(gè)進(jìn)程，實(shí)質(zhì)就是對(duì)進(jìn)程的切換，也就是快速的切換執(zhí)行多個(gè)進(jìn)程，這樣對(duì)于用戶(hù)而言，所有的進(jìn)程都是同時(shí)進(jìn)行的，但是應(yīng)該如何讓多個(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)單。沒(méi)錯(cuò)，就是我們理解的哪個(gè)進(jìn)程先來(lái)了，CPU就先處理哪個(gè)，等當(dāng)前的處理結(jié)束，再處理下一個(gè)。

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

在這里我們計(jì)算一下進(jìn)程的平均周轉(zhuǎn)時(shí)間，當(dāng)3個(gè)進(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。這是我們不能接受的。這個(gè)問(wèn)題通常被稱(chēng)為護(hù)航效應(yīng)（convoy effect）。這種情況在我們生活中也是非常常見(jiàn)的，例如我們?nèi)ヒ粋€(gè)地方辦一件事，大多數(shù)人只需要1min就可以辦完，但是前面有一個(gè)人需要30min分鐘才可以辦完，那么后面的人都要一起等待這30min。

針對(duì)上面的問(wèn)題，我們有新的解決方案：最短任務(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á)，情況依然糟糕。

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

上面的算法中主要考量的是平均周轉(zhuǎn)時(shí)間，但是現(xiàn)實(shí)中如果用這樣的算法依然是不可靠的，試想我們打開(kāi)一個(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í)鐘中斷周期是10ms，那么時(shí)間片可以是10ms，20ms，30ms，10ms的任何倍數(shù)。3個(gè)進(jìn)程A，B，C，所需時(shí)間都是5，如果使用RR這種算法，執(zhí)行過(guò)程就是如下圖：

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

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