224
調(diào)度的發(fā)展歷史
| 字段 | 版本 |
|---|---|
| O(n) 調(diào)度器 | linux0.11 - 2.4 |
| O(1) 調(diào)度器 | linux2.6 |
| CFS調(diào)度器 | linux2.6至今 |
O(n) 調(diào)度器是在內(nèi)核2.4以及更早期版本采用的算法，其調(diào)度算法非常簡單和直接，就緒隊列是個全局列表，從就緒隊列中查找下一個最佳任務，由于每次在尋找下一個任務時需要遍歷系統(tǒng)中所有的任務（全局列表），因此被稱為 O(n) 調(diào)度器（時間復雜度）。
內(nèi)核2.6采用了O(1) 調(diào)度器，讓每個CPU維護一個自己的就緒隊列，從而減少了鎖的競爭。就緒隊列由兩個優(yōu)先級數(shù)組組成，分別是active優(yōu)先級數(shù)組和expired優(yōu)先級數(shù)組。每個優(yōu)先級數(shù)組包含140個優(yōu)先級隊列，也就是每個優(yōu)先級對應一個隊列，其中前100個對應實時進程，后40個對應普通進程。如下圖所示：
這樣設(shè)計的好處，調(diào)度器選擇下一個被調(diào)度任務就變得高效和簡單多了，只需要在active優(yōu)先級數(shù)組中選擇優(yōu)先級高，并且隊列中有可運行的任務即可。這里使用位圖來定義該隊列中是否有可運行的任務，如果有，則位圖中相應的位就會被置1。這樣選擇下一個被調(diào)用任務的時間就變成了查詢位圖的操作。
- 但上面的算法有個問題，一個高優(yōu)先級多線程的應用會比低優(yōu)先級單線程的應用獲得更多的資源，這就會導致一個調(diào)度周期內(nèi)，低優(yōu)先級的應用可能一直無法響應，直到高優(yōu)先級應用結(jié)束。CFS調(diào)度器就是站在一視同仁的角度解決了這個問題，保證在一個調(diào)度周期內(nèi)每個任務都有執(zhí)行的機會，執(zhí)行時間的長短，取決于任務的權(quán)重。下面詳細看下CFS調(diào)度器是如何動態(tài)調(diào)整任務的運行時間，達到公平調(diào)度的。
實際運行時間
CFS是Completely Fair Scheduler簡稱，即完全公平調(diào)度器。CFS調(diào)度器和以往的調(diào)度器不同之處在于沒有時間片的概念，而是公平分配cpu使用的時間。例如：2個相同優(yōu)先級的進程在一個cpu上運行，那么每個進程都將會分配50%的cpu運行時間。這就是要實現(xiàn)的公平。
但現(xiàn)實中，必然是有的進程優(yōu)先級高，有的進程優(yōu)先級低。CFS調(diào)度器引入權(quán)重的概念，用權(quán)重代表進程的優(yōu)先級，各個進程按照權(quán)重的比例分配cpu的時間。比如：2個進程A和B。A的權(quán)重是1024，B的權(quán)重是2048。那么A獲得cpu的時間比例是1024/(1024+2048) = 33.3%。B進程獲得的cpu時間比例是2048/(1024+2048)=66.7%。
在引入權(quán)重之后，分配給進程的時間計算公式如下：
實際運行時間 = 調(diào)度周期 * 進程權(quán)重 / 所有進程權(quán)重之和
CFS調(diào)度器用nice值表示優(yōu)先級，取值范圍是[-20, 19]，nice和權(quán)重是一一對應的關(guān)系。數(shù)值越小代表優(yōu)先級越大，同時也意味著權(quán)重值越大，nice值和權(quán)重之間的轉(zhuǎn)換關(guān)系：
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
數(shù)組值計算公式是：weight = 1024 / 1.25nice。
公式中的1.25取值依據(jù)是：進程每降低一個nice值，將多獲得10% cpu的時間。公式中以1024權(quán)重為基準值計算得來，1024權(quán)重對應nice值為0，其權(quán)重被稱為NICE_0_LOAD。默認情況下，大部分進程的權(quán)重基本都是NICE_0_LOAD。
虛擬運行時間
根據(jù)上面的理解，這里看個例子。假如一個CPU的調(diào)度周期是6ms，進程A和B的權(quán)重分別是1024和820（nice值分別是0和1），那么進程A獲得的運行時間是6x1024/(1024+820)=3.3ms，進程B獲得的執(zhí)行時間是6x820/(1024+820)=2.7ms。進程A的cpu使用比例是3.3/6x100%=55%，進程B的cpu使用比例是2.7/6x100%=45%。（符合上面說的“進程每降低一個nice值，將多獲得10% CPU的時間”）
很明顯，2個進程的實際執(zhí)行時間是不相等的，但是CFS想保證每個進程運行時間相等。因此CFS引入了虛擬時間的概念，也就是說上面的2.7ms和3.3ms經(jīng)過一個公式的轉(zhuǎn)換可以得到一樣的值，這個轉(zhuǎn)換后的值稱作虛擬時間。這樣的話，CFS只需要保證每個進程運行的虛擬時間是相等的即可。虛擬時間vriture_runtime和實際時間（wall time）轉(zhuǎn)換公式如下：
虛擬運行時間 = 實際運行時間 * NICE_0_LOAD / 進程權(quán)重 = (調(diào)度周期 * 進程權(quán)重 / 所有進程權(quán)重之和) * NICE_0_LOAD / 進程權(quán)重 = 調(diào)度周期 * 1024 / 所有進程總權(quán)重
從公式可以看出，在一個調(diào)度周期里，所有進程的虛擬運行時間是相同的。所以在進程調(diào)度時，只需要找到虛擬運行時間最小的進程調(diào)度運行即可。
為了能夠快速找到虛擬運行時間最小的進程，Linux 內(nèi)核使用紅黑樹來保存可運行的進程。CFS跟蹤調(diào)度實體sched_entity的虛擬運行時間vruntime，將sched_entity通過enqueue_entity()和dequeue_entity()來進行紅黑樹的出隊入隊，vruntime少的調(diào)度實體sched_entity排列到紅黑樹的左邊。
如上圖所示，紅黑樹的左節(jié)點比父節(jié)點小，而右節(jié)點比父節(jié)點大。所以查找最小節(jié)點時，只需要獲取紅黑樹的最左節(jié)點即可。
相關(guān)步驟如下：
- 每個sched_latency周期內(nèi)，根據(jù)各個任務的權(quán)重值，可以計算出運行時間runtime；運行時間runtime可以轉(zhuǎn)換成虛擬運行時間vruntime；根據(jù)虛擬運行時間的大小，插入到CFS紅黑樹中，虛擬運行時間少的調(diào)度實體放置到左邊；在下一次任務調(diào)度的時候，選擇虛擬運行時間少的調(diào)度實體來運行（pick_next_task從就緒隊列中選擇最適合運行的調(diào)度實體，即虛擬時間最小的調(diào)度實體）；
CFS 數(shù)據(jù)結(jié)構(gòu)
- task_struct: 任務描述符，包含很多進程相關(guān)的信息，例如，優(yōu)先級、進程狀態(tài)以及調(diào)度實體等。
struct task_struct {
...
struct sched_entity se;
...
}
- cfs_rq：跟蹤就緒隊列信息以及管理就緒態(tài)調(diào)度實體，并維護一棵按照虛擬時間排序的紅黑樹。tasks_timeline->rb_root是紅黑樹的根，tasks_timeline->rb_leftmost指向紅黑樹中最左邊的調(diào)度實體，即虛擬時間最小的調(diào)度實體。
struct cfs_rq {
...
struct rb_root_cached tasks_timeline
...
};
- sched_entity：可被內(nèi)核調(diào)度的實體。每個就緒態(tài)的調(diào)度實體sched_entity包含插入紅黑樹中使用的節(jié)點rb_node，同時vruntime成員記錄已經(jīng)運行的虛擬時間。
struct sched_entity {
...
struct rb_node run_node;
...
u64 vruntime;
...
};
這些數(shù)據(jù)結(jié)構(gòu)的關(guān)系如下圖所示：
CFS 算法實現(xiàn)
- 時鐘中斷 scheduler_tick 更新虛擬運行時間，檢查是否需要搶占。
- 更新運行時的各類統(tǒng)計信息，比如vruntime， 運行時間、負載值、權(quán)重值等。檢查是否需要搶占，主要是比較運行時間是否耗盡，以及vruntime的差值是否大于運行時間等。
- 任務出隊入隊
當任務進入可運行狀態(tài)時，用 enqueue_task_fair 將調(diào)度實體放入到紅黑樹中，完成入隊操作；當任務退出可運行狀態(tài)時，用 dequeue_task_fair 將調(diào)度實體從紅黑樹中移除，完成出隊操作；隊操作。
調(diào)用 __enqueue_entity 函數(shù)后，就可以把進程調(diào)度實體插入到運行隊列的紅黑樹中。同時會把紅黑樹最左端的節(jié)點緩存到運行隊列的 rb_leftmost 字段中，用于快速獲取下一個可運行的進程。
- 從 cfs_rq 中獲取下一個可運行的任務
每當進程任務切換的時候，也就是schedule函數(shù)執(zhí)行時，調(diào)度器都需要選擇下一個將要執(zhí)行的任務。在CFS調(diào)度器中，是通過 pick_next_task_fair 函數(shù)完成的，其本質(zhì)是從就緒隊列中選擇最適合運行的調(diào)度實體（虛擬時間最小的調(diào)度實體）。
