調(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)的位就會(huì)被置1。這樣選擇下一個(gè)被調(diào)用任務(wù)的時(shí)間就變成了查詢位圖的操作。
- 但上面的算法有個(gè)問題,一個(gè)高優(yōu)先級多線程的應(yīng)用會(huì)比低優(yōu)先級單線程的應(yīng)用獲得更多的資源,這就會(huì)導(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ī)會(huì),執(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)程都將會(huì)分配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í)會(huì)把紅黑樹最左端的節(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í)體)。