作業系統導論 第九章 排程：比例份額

文章目錄

• 第九章 排程：比例份額
• • 9.1 基本概念：彩票數代表份額
  • 9.2 彩票機制
  • 9.3 實作
  • 9.4 步長排程
  • 9.5 小結

第九章 排程：比例份額

在本章，我們将看到一個不同類型的排程程式–比例份額（proportional-share）排程程式，有時也被稱為公平份額（fair-share）排程程式。

比例份額算法基于一個簡單的想法：排程程式的最終目标，是確定每個工作獲得一定比例的CPU時間，而不是優化周轉時間和響應時間。

每一個程序相當于買彩票的人，越是應該頻繁運作的程序，買到的彩票越多。

每隔一段時間都會舉辦一次抽獎，抽到的彩票是哪個程序，就運作哪個程序。

9.1 基本概念：彩票數代表份額

彩票數（ ticket）代表了程序占有某個資源的份額。

一個程序擁有的彩票數占總彩票書的百分比，就是它占有資源的份額。

假設有100張彩票，我們希望A占用CPU 75%的時間，而B占用CPU 25%的時間。

則我們應該配置設定給 A 75張彩票，配置設定給 B 25張彩票。

排程程式不斷定時地抽取彩票，有100張彩票，就從0-99中抽取一個數字。

如果抽到0-24，就決定運作A；如果抽到25-99，就決定運作B。

雖然，這種随機性可能導緻短時間的排程不均。

但是，随着兩個工作運作時間的增加，它們的CPU時間所占比例會越來越接近于期望的25%和75%，從長時間看起來是很公平的。

9.2 彩票機制

彩票排程還提高了一些機制，以不同且有效的方式來排程彩票。

• 彩票貨币（ticket currency）

這種方式運作擁有一組彩票的使用者以他們喜歡的某種貨币将彩票分給自己的不同工作。

之後作業系統再自動将這種貨币兌換為正确的全局彩票。

類似于匯率，将使用者的自有貨币比作國家貨币，如人民币、日元，将全局彩票比作全世界的通用貨币–美元。

使用者将自己擁有的彩票按照匯率折算成自有貨币，配置設定給自己的不同工作。

當使用者的工作需要運作時，會将配置設定到的自有貨币再根據匯率折算成全局彩票進行抽獎，來決定由誰來運作。

• 彩票轉讓（ticket transfer）

通過轉讓，一個程序可以臨時将自己的彩票交給另一個程序。

這種機制在C/S互動的場景中尤其有用，在這種場景中，用戶端程序向服務端發送消息，請求其按自己的需求執行工作。

為了加速服務端的執行，用戶端可以将自己的彩票轉讓給服務端，進而盡可能加速服務端執行自己請求的速度。

服務端執行結束後會将這部分彩票歸還給用戶端。

• 彩票通脹（ticket inflation）

利用通脹，一個程序可以臨時提升或降低自己擁有的彩票數量。

當然在競争環境下，程序之間互相不信任，這種機制就會沒有意義。

因為一個貪婪的程序可能給自己非常多的彩票，進而接管機器。

但是，通脹可以用于程序之間互相信任的環境。

在這種情況下，急需更多CPU時間的程序就可以自己增加持有彩票，進而将自己的需求告知作業系統，也不用耗費時間與其他程序通信。

9.3 實作

彩票排程中最不可思議的，或許就是實作簡單。

隻需要

• 一個用來選擇中獎彩票的随機數生成器
• 一個記錄系統中所有程序的資料結構
• 所有彩票的總數

假設有A、B、C三個程序，每個程序有一定數量的彩票，彩票總數為400，如下圖所示

在做出排程決策之前，首先從彩票總數400中選擇一個随機數，假設選擇了300。

然後周遊連結清單，用一個簡單的計數器找到中獎者。

從零開始，将每個程序的票數按序相加，當超過或等于中獎彩票時，目前程序就是中獎者。

1. 程序A擁有100張彩票，0+100=100<300，繼續尋找；
2. 程序B擁有50張彩票，100+50=150<300，繼續尋找；
3. 程序C擁有250張彩票，150+250=400<300，程序C是中獎者。

要讓這個過程更有效率，建議将清單項按照彩票數遞減排序。

這樣的順序不會影響算法的正确性，卻可以用最小的的疊代次數找到中獎者，尤其當大多數彩票被少數程序掌握時。

9.4 步長排程

你可能會想到，雖然随機方式可以使得排程程式的實作簡單，但偶爾并不能産生正确的比例，尤其在工作運作時間很短的情況下。

那麼，為什麼要利用随機性呢？

基于這個原因，Waldspurger提出了步長排程（stride scheduling），一個确定性的公平配置設定算法。

系統中的每個工作都有自己的步長，這個值與票數成反比。

之前的例子中，A、B、C三個程序的票數分别為100、50、250，我們用一個大數除以每個工作的票數，就可以得到每個工作的步長。

比如用10000作為大數，則A、B、C的步長分别為100，200，40。

每個程序都有一個計數器，當程序運作時，它對應的計數器會增加相應的步長，記錄它的總體進展。

步長排程的基本思路是：每次需要進行排程時，選擇目前擁有最小行程值的程序，并且在運作之後将該程序的行程值增加一個步長。

程序A、B、C一段時間内的排程行為如下：

行程值（A）（步長=100）	行程值（B）（步長=200）	行程值（C）（步長=40）	誰運作
A
100	B
100	200	C
100	200	40	C
100	200	80	C
100	200	120	A
200	200	120	C
200	200	160	C
200	200	200	······

可以看出，C運作了5次，A運作了2次，B運作了1次，正好是票數的比例——250、100、50。

彩票排程算法隻能在一段時間後，在機率上實作比例。

而步長排程算法可以在每個排程周期後做到。

既然這樣，為什麼還要彩票排程算法呢？

因為彩票排程有步長排程沒有的優勢，它不需要全局狀态。

如果一個新的程序在步長排程執行過程中加入系統，應該怎麼設定它的行程值？

設定為0的話，它就獨占CPU了。

而彩票排程不需要對每個程序記錄全局狀态，進加入的程序隻要将它的票數更新進全局總票數即可。

9.5 小結

本章我們介紹了比例份額排程的概念，并簡單讨論了兩種實作：彩票排程和步長排程。

雖然兩者都很有趣，但由于一些原因，并沒有作為CPU排程程式被廣泛使用。

一個原因是它們并不能很好地适合I/O，另一個原因是其中最難的票數配置設定問題沒有确定的解決方案。

通用排程程式（比如MLFQ以及其他類似的Linux排程程式）做得更好，是以得到了廣泛的應用。