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