894
CFS 調度器
首先簡單介紹一下基本的設計思路，CFS思路很簡單，就是根據各個進程的權重分配運行時間(權重怎麼來的後麵再說)。進程的運行時間計算公式為:
分配給進程的運行時間 = 調度周期 * 進程權重 / 所有進程權重之和 (公式1)
調度周期很好理解，就是將所有處於TASK_RUNNING態進程都調度一遍的時間，差不多相當於O(1)調度算法中運行隊列和過期隊列切換一次的時間（我對O(1)調度算法看得不是很熟，如有錯誤還望各位大蝦指出）。舉個例子，比如隻有兩個進程A, B，權重分別為1和2，調度周期設為30ms，那麼分配給A的CPU時間為:30ms * (1/(1+2)) = 10ms,而B的CPU時間為:30ms * (2/(1+2)) = 20ms。那麼在這30ms中A將運行10ms，B將運行20ms。
公平怎麼體現呢？它們的運行時間並不一樣阿？
其實公平是體現在另外一個量上麵，叫做virtual runtime(vruntime)，它記錄著進程已經運行的時間，但是並不是直接記錄，而是要根據進程的權重將運行時間放大或者縮小一個比例。
我們來看下從實際運行時間到vruntime的換算公式：
vruntime = 實際運行時間 * 1024 / 進程權重 。 (公式2)
為了不把大家搞暈，這裏我直接寫1024，實際上它等於nice為0的進程的權重，代碼中是NICE_0_LOAD。也就是說，所有進程都以nice為0的進程的權重1024作為基準，計算自己的vruntime增加速度。還以上麵AB兩個進程為例，B的權重是A的2倍，那麼B的vruntime增加速度隻有A的一半。現在我們把公式2中的實際運行時間用公式1來替換，可以得到這麼一個結果：
vruntime = (調度周期 * 進程權重 / 所有進程總權重) * 1024 / 進程權重 = 調度周期 * 1024 / 所有進程總權重
看出什麼眉目沒有？沒錯，雖然進程的權重不同，但是它們的 vruntime增長速度應該是一樣的 ，與權重無關。（實際運行時間和權重有關，vruntime也和權重有關，抵消）
好，既然所有進程的vruntime增長速度宏觀上看應該是同時推進的，那麼就可以用這個vruntime來選擇運行的進程，誰的vruntime值較小就說明它以前占用cpu的時間較短，受到了“不公平”對待，因此下一個運行進程就是它。這樣既能公平選擇進程，又能保證高優先級進程獲得較多的運行時間。這就是CFS的主要思想了。
再補充一下權重的來源，權重跟進程nice值之間有一一對應的關係，可以通過全局數組prio_to_weight來轉換，nice值越大，權重越低。
下麵來分析代碼。網上已經有很多cfs的文章，因此我打算換一個方式來寫，選擇幾個點來進行情景分析，包括進程創建時，進程被喚醒，主動調度(schedule)，時鍾中斷。
介紹代碼之前先介紹一下CFS相關的結構。第一個是調度實體sched_entity，它代表一個調度單位，在組調度關閉的時候可以把他等同為進程。每一個task_struct中都有一個sched_entity，進程的vruntime和權重都保存在這個結構中。那麼所有的sched_entity怎麼組織在一起呢？紅黑樹。所有的sched_entity以vruntime為key(實際上是以vruntime-min_vruntime為單位，難道是防止溢出？反正結果是一樣的)插入到紅黑樹中，同時緩存樹的最左側節點，也就是vruntime最小的節點，這樣可以迅速選中vruntime最小的進程。注意隻有等待CPU的就緒態進程在這棵樹上，睡眠進程和正在運行的進程都不在樹上。我從ibm developer works上偷過來一張圖來展示一下它們的關係：
最後更新：2017-04-03 12:56:08