操作系統的CPU虛擬化

譚清寬

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

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

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

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

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

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

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

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

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

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

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