操作系統的進程調度算法（CPU虛擬化）
關于操作系統是如何虛擬化 CPU 的我們上一篇文章已經聊過了，今天再深入一下，聊一聊進程調度那些事。
我們已經知道，對 CPU 虛擬化的目的就是能夠同時運行多個進程(這不是唯一目的)，而實質就是對進程的切換，也就是快速的切換執行多個進程，這樣對于用戶而言，所有的進程都是同時進行的，但是我們應該如何對多個進程來公平合理并安全高效的運行呢?所以，我們就出現了很多的進程調度算法。這里我們由淺入深，來講一下目前比較廣泛的算法。
第一個就是最簡單的先進先出(FIFO)，也可以叫做先到先服務。這個算法的最大優點就是簡單。沒錯，就是我們理解的那個進程先來了，CPU 就先處理哪個，等當前的處理結束，在處理下一個。
我們假設有三個進程，每一個進程處理需要10s，這時，無論哪個進程先來，最后一個進程的完成時間都是30s，也就是說這種情況下最大完成時間是所有進程需要時間之和。但是如果同樣有三個進程，其中兩個進程需要10s，另外一個進程需要100s，這種情況，最大完成時間就是120s，由于三個進程的各自完成時間不同，所以根據他們到達的順序不同最終的影響也有很大差異。假設三個進程 A(10s)、B(10s)、C(100s)，如果按照 A、B、C 的順序到達，那么執行的過和我們預想的是一樣的，開始十秒鐘，A 執行結束，二十秒后，B 執行結束，一百二十秒后，C執行結束。但是如果是按照相反的順序到達的呢?C、B、A，這樣開始一百秒后，C 執行結束，一百一十秒后，B 執行結束，一百二十秒后，A 執行結束。很顯然，這種情況下，B 和 A 都要等待時間最長的 C 結束才可以執行，所以這個算法的效率根據到達的順序有很大關系。顯然，這并不是我們想要的。在這里我們計算一下進程的平均周轉時間，當三個進程都需要10s的時候平均周轉時間：
(10+20+30)/3=20，因為 A 在第10s完成，B 在第20s完成，C 在第30s完成。大家想一下當進程 A、B、C 時間分別為 10s、10s、100s呢?此時進程的順序是 C、B、A，那么平均周轉時間就是：(100+110+120)/3=110。這是我們不能接受的。這個問題通常被稱為護航效應(convoy effect)。這種情況在我們生活中也是非常常見的，例如我們去一個地方辦一件事，大多數人只需要一分鐘就可以辦完，但是前面有一個人需要三十分鐘才可以辦完，那么后面的人都要一起等待這三十分鐘。
針對上面的問題，我們有新的解決方案：最短任務優先(SJF)與最短完成時間優先(STCF)。
最短任務優先顧名思義，就是需要占用 CPU 時間短的進程先執行，也就是在上面的例子中(A需要10s、B需要20s、C需要100s)，先讓A和B先到達，執行結束后在執行C。但是這種算法中，我們依然不能保證C一定最后到達，如果C依然是最先到達，情況依然糟糕，情況下圖：
SJF
為了解決這個問題，我們放款條件，就是我們不需要保證所有的進程必須一次都執行完。現在我們在假設最壞的情況，C先到達，之后才是A和B。當C總執行時間需要100s時，剛開始執行到了10s的時候，B到達，此時我們不需要保證C執行全部完成，發現B的時間只需要10s就可以結束，此時就暫停C同時開始執行B，當B執行結束后，A又到達，此時我們同樣不執行C而是執行A，當A結束后，我們再回到C，這樣性能又上升了一個臺階。如下圖：
STCF
上面的算法中主要考量的是平均周轉時間，但是現實中如果用這樣的算法依然是不可靠的，試想我們打開一個軟件，某一個功能需要等待100s后才反應，那我們豈不是要瘋掉?此時新的度量指標出現了：響應時間(響應時間=首次運行-到達時間)。
我們再介紹新的算法，輪轉(Round-Robin，RR)。顧名思義，就是輪訓執行進程。在一個時間片內運行一個工作，然后切換到運行隊列中的下一個任務。重復執行，直到所有結束。這里我們有一點需要注意，就是時間片需要是時鐘中斷周期的倍數，時鐘中斷部分這里不再細講，上一篇文章我們已經聊過了。假如時鐘中斷周期是10ms，那么時間片可以是10ms、20ms、30ms或者10ms的任何倍數。三個進程A、B、C，所需時間都是5，如果使用RR這種算法，執行過程就是如下圖：
RR
但是這種算法還要付出另外的代價，就是上下文切換的成本。所以說需要找一個合理的時間片。但是最主要的問題是，這種算法與之前的最短任務優先與最短完成時間優先是有些相反的，也就是說，這種算法導致了周轉時間變得更長。如圖例子，A程序在13完成，B在14，C在15，這是非常可怕的。
現在我們有了兩種算法，各自的度量標準不同，一個是周轉時間，另一個是響應時間，但是魚與熊掌不可兼得的道理大家都知道，那么我們具體應該怎么做呢?下一篇文章我們繼續聊更加完善的兩個算法多級反饋隊列與比例份額。這兩個算法內容較多，所以再單獨拿出來。
今天說的是比較基礎的東西，可以說的進程調度思想的一個起步，有了這個基礎我們就可以更加深入的理解后面的多級反饋隊列算法與比例份額。再啰嗦幾句，最近為什么要寫操作系統相關的內容呢?因為我覺得這對生產是有很大幫助的，尤其在生產環境中找問題，性能提升等，所以建議大家可以了解一些。這也是我一直所提倡的，語言只是工具，框架也是工具，但是百變不離其宗，只有掌握了最核心，最基礎的才能所向披靡。
