虛擬化(3)：os調度策略

來自專欄計算機操作系統基礎

這一章主要是介紹幾個簡單的調度器策略。內容比較簡單，就簡單匯總下。

首先我們對現有的計算機環境有如下幾個假設：

1.每個job都運行相同的時間。

2.所有的job都同時準備好運行

3.一旦一個job啟動，那麼他就會一直運行到結束。

4.所有的job都不會有I/O

5.每個job運行的時間都是可知的。

我們先引入一個效率的測量值：turnaround time

Tturnaround = Tcompletion ? Tarrival

一個測量反應時間的：

Tresponse = Tfirstrun ? Tarrival

也就是任務第一次開始運行的時間點減去任務到達的時間點。

首先第一個策略是先入先出（First In, First Out (FIFO)），就是誰先到誰先運行。

這個是一個例子，有三個任務A，B，C，我們計算對應的turnaround time為10+20+30/3=30但是如果運行時間長的任務先到，那麼turnaround time就會很高，比如這個例子，

因為任務A執行時間太長，導致turnaround time為100+110+120/3=110。因此引入了下一個策略：短任務先執行（Shortest Job First (SJF)）。這樣會減少turnaround time。但是如果我們放開所有任務同時到達的假設，如果是長任務先來那麼就還是有問題，因此引入下一個策略：運行時間短的先執行（Shortest Time-to-Completion First (STCF)）。但是如果運行時間不確定那還是有問題，進一步引入了新的策略：循環執行（Round Robin）。這種策略不是讓一個任務從開始執行一直到結束，而是將任務劃分為固定時間的一個一個時間片，然後順序執行，

這樣對應的response time會比較好，但是turnaround time會很糟糕，可以從上面的2個對比中看出來。另外RR的這種方式還會帶來任務間切換的消耗變多。而且如果進程中有I/O的時候，會導致很大的時間浪費，因此就引出了下個章節的內容：多級反饋隊列（multi-level feedback queue）；

1.MLFQ的的規則

我們會有一些隊列，不同的隊列對應不同的優先順序.對於隊列中的進程，調度的規則如下：

（1）如果Priority(A) > Priority(B)，那麼A運行。

（2）如果Priority(A) = Priority(B)，那麼A，B按照Round-Robin方式運行。

（3）當一個任務創立的是時候，它在最高的優先順序中

（4a）如果一個任務執行的時候消耗了整個時間片，那麼降低優先順序

（4b）如果一個任務主動放棄cpu的執行時間，那麼保持優先順序不變

上面的規則所構成的調度規則，會有如下的問題：

（1）如果有很多的job是交互性的，那麼會導致那些需要大量cpu時間的job無法運行

（2）不公平性。如果有些job寫的時候故意在時間片的最後一點時間放棄cpu，那麼他就可以一直保持一個高優先順序的狀態。

（3）上面的規則只規定了job的優先順序下降，但是如果一個job 從耗費cpu變為了交互性，它的優先順序也是沒辦法提高的。

所以對上面的規則又新增了一些規則：

（5）經過一個時間S後，將所有的任務都調整到許可權最高的隊列。

（6）對規則4a和4b進行修改，一個job使用完該等級上的時間後，就會降低它的優先順序。

上面的這些規則中包含了很多的設置內容，比如隊列的個數，時間片的時間，調整所有低優先順序job的時間，每個隊列對應的時間為多少等等，這些都是具體在實現MLFQ的時候需要考慮的，一個好的建議是這些數值能夠可配置化，避免寫死。

上面介紹的調度策略在多核的時代還能不能適用呢？

首先什麼是多核，就是因為單核的速度無法提升，所以只能以增加核心的方式來提升cpu 的速度。而且需要注意的是每個核心都有對應的緩存，所以這個會導致緩存不一致的情況。另外還需要考慮的就是並發的問題，這個可以通過加鎖機制來完成。另外對於多核來說，會帶來一個新的問題，那就是緩存關聯性（Cache Affinity）。也就是說，如果一個進程如果能夠一直運行在一個核上，那麼就可以利用高速緩存來提高運行的效率，反之運行速度就會低下。

對於多核的OS調度機制，可以有兩種方案，一種是單個調度隊列（SQMS:single queue multiprocessor scheduling），一種是每個核一個調度隊列（multi-queue multiprocessor scheduling (or MQMS)）。

SQMS的優勢在於能夠簡單，能夠直接應用之前的調度代碼。弊端也顯而易見，首先是效率的問題，因為一個隊列表示需要大量的鎖操作來實現對數據的正確訪問。其次緩存關聯性問題也很突出，不過也有一些解決方案，比如固定一些進程只在某個核上跑，另外的則在多個核之前輪轉的運行。

MQMS對於每個核都有一個調度的隊列，這保證了擴展性，並發不是公用鎖，所以效率也得到提升。但是會牽扯出負載均衡的問題。首先是怎麼決定新生成的進程應該屬於哪個隊列，其次是如果核之間的任務數量失衡，怎麼補救。第一個問題我們用啟發式的方法決定，第二個可以使用進程在隊列間的移動。再來個問題，每個核如何發現其他核的情況呢，那麼肯定就需要去訪問對應核的內核數據結構，這個頻率不應該太高，也不應該太低，具體的就需要在實現的時候考慮了。所以實際的策略實現中，都需要大量的trade-off，因為在實際的場景中，沒有一個最優的答案，有的只是不斷探索然後將方案做到儘可能好。

最後對於linux來說，對多核是有多個調度器策略的。O(1)， CFS ， BFS，這個就不做介紹了。