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

譚清寬

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

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

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

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

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

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

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

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

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

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

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