帶你玩轉(zhuǎn)Linux內(nèi)核調(diào)度器源碼分析!
引言
調(diào)度器作為操作系統(tǒng)的核心部件,具有非常重要的意義,其隨著linux內(nèi)核的更新也不斷進(jìn)行著更新。本系列文章通過(guò)linux-3.18.3源碼進(jìn)行調(diào)度器的學(xué)習(xí)和分析,一步一步將linux現(xiàn)有的調(diào)度器原原本本的展現(xiàn)出來(lái)。此篇文章作為開(kāi)篇,主要介紹調(diào)度器的原理及重要數(shù)據(jù)結(jié)構(gòu)。
調(diào)度器介紹
隨著時(shí)代的發(fā)展,linux也從其初始版本穩(wěn)步發(fā)展到今天,從2.4的非搶占內(nèi)核發(fā)展到今天的可搶占內(nèi)核,調(diào)度器無(wú)論從代碼結(jié)構(gòu)還是設(shè)計(jì)思想上也都發(fā)生了翻天覆地的變化,其普通進(jìn)程的調(diào)度算法也從O(1)到現(xiàn)在的CFS,一個(gè)好的調(diào)度算法應(yīng)當(dāng)考慮以下幾個(gè)方面:
公平:保證每個(gè)進(jìn)程得到合理的CPU時(shí)間。
高效:使CPU保持忙碌狀態(tài),即總是有進(jìn)程在CPU上運(yùn)行。
響應(yīng)時(shí)間:使交互用戶的響應(yīng)時(shí)間盡可能短。
周轉(zhuǎn)時(shí)間:使批處理用戶等待輸出的時(shí)間盡可能短。
吞吐量:使單位時(shí)間內(nèi)處理的進(jìn)程數(shù)量盡可能多。
負(fù)載均衡:在多核多處理器系統(tǒng)中提供更高的性能
而整個(gè)調(diào)度系統(tǒng)至少包含兩種調(diào)度算法,是分別針對(duì)實(shí)時(shí)進(jìn)程和普通進(jìn)程,所以在整個(gè)linux內(nèi)核中,實(shí)時(shí)進(jìn)程和普通進(jìn)程是并存的,但它們使用的調(diào)度算法并不相同,普通進(jìn)程使用的是CFS調(diào)度算法(紅黑樹(shù)調(diào)度)。之后會(huì)介紹調(diào)度器是怎么調(diào)度這兩種進(jìn)程。
進(jìn)程
在linux中,進(jìn)程主要分為兩種,一種為實(shí)時(shí)進(jìn)程,一種為普通進(jìn)程
實(shí)時(shí)進(jìn)程:對(duì)系統(tǒng)的響應(yīng)時(shí)間要求很高,它們需要短的響應(yīng)時(shí)間,并且這個(gè)時(shí)間的變化非常小,典型的實(shí)時(shí)進(jìn)程有音樂(lè)播放器,視頻播放器等。
普通進(jìn)程:包括交互進(jìn)程和非交互進(jìn)程,交互進(jìn)程如文本編輯器,它會(huì)不斷的休眠,又不斷地通過(guò)鼠標(biāo)鍵盤(pán)進(jìn)行喚醒,而非交互進(jìn)程就如后臺(tái)維護(hù)進(jìn)程,他們對(duì)IO,響應(yīng)時(shí)間沒(méi)有很高的要求,比如編譯器。
它們?cè)趌inux內(nèi)核運(yùn)行時(shí)是共存的,實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)為0~99,實(shí)時(shí)進(jìn)程優(yōu)先級(jí)不會(huì)在運(yùn)行期間改變(靜態(tài)優(yōu)先級(jí)),而普通進(jìn)程的優(yōu)先級(jí)為100~139,普通進(jìn)程的優(yōu)先級(jí)會(huì)在內(nèi)核運(yùn)行期間進(jìn)行相應(yīng)的改變(動(dòng)態(tài)優(yōu)先級(jí))。
調(diào)度策略
在linux系統(tǒng)中,調(diào)度策略分為
SCHED_NORMAL:普通進(jìn)程使用的調(diào)度策略,現(xiàn)在此調(diào)度策略使用的是CFS調(diào)度器。
SCHED_FIFO:實(shí)時(shí)進(jìn)程使用的調(diào)度策略,此調(diào)度策略的進(jìn)程一旦使用CPU則一直運(yùn)行,直到有比其更高優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程進(jìn)入隊(duì)列,或者其自動(dòng)放棄CPU,適用于時(shí)間性要求比較高,但每次運(yùn)行時(shí)間比較短的進(jìn)程。
SCHED_RR:實(shí)時(shí)進(jìn)程使用的時(shí)間片輪轉(zhuǎn)法策略,實(shí)時(shí)進(jìn)程的時(shí)間片用完后,調(diào)度器將其放到隊(duì)列末尾,這樣每個(gè)實(shí)時(shí)進(jìn)程都可以執(zhí)行一段時(shí)間。適用于每次運(yùn)行時(shí)間比較長(zhǎng)的實(shí)時(shí)進(jìn)程。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面,有需要的可以自行添加哦?。。。ê曨l教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??


首先,我們需要清楚,什么樣的進(jìn)程會(huì)進(jìn)入調(diào)度器進(jìn)行選擇,就是處于TASK_RUNNING狀態(tài)的進(jìn)程,而其他狀態(tài)下的進(jìn)程都不會(huì)進(jìn)入調(diào)度器進(jìn)行調(diào)度。系統(tǒng)發(fā)生調(diào)度的時(shí)機(jī)如下
調(diào)用cond_resched()時(shí)
顯式調(diào)用schedule()時(shí)
從系統(tǒng)調(diào)用或者異常中斷返回用戶空間時(shí)
從中斷上下文返回用戶空間時(shí)
當(dāng)開(kāi)啟內(nèi)核搶占(默認(rèn)開(kāi)啟)時(shí),會(huì)多出幾個(gè)調(diào)度時(shí)機(jī),如下
在系統(tǒng)調(diào)用或者異常中斷上下文中調(diào)用preempt_enable()時(shí)(多次調(diào)用preempt_enable()時(shí),系統(tǒng)只會(huì)在最后一次調(diào)用時(shí)會(huì)調(diào)度)
在中斷上下文中,從中斷處理函數(shù)返回到可搶占的上下文時(shí)(這里是中斷下半部,中斷上半部實(shí)際上會(huì)關(guān)中斷,而新的中斷只會(huì)被登記,由于上半部處理很快,上半部處理完成后才會(huì)執(zhí)行新的中斷信號(hào),這樣就形成了中斷可重入, 但是即使是中斷下半部, 也是不能夠被調(diào)度的)
而在系統(tǒng)啟動(dòng)調(diào)度器初始化時(shí)會(huì)初始化一個(gè)調(diào)度定時(shí)器,調(diào)度定時(shí)器每隔一定時(shí)間執(zhí)行一個(gè)中斷,在中斷會(huì)對(duì)當(dāng)前運(yùn)行進(jìn)程運(yùn)行時(shí)間進(jìn)行更新,如果進(jìn)程需要被調(diào)度,在調(diào)度定時(shí)器中斷中會(huì)設(shè)置一個(gè)調(diào)度標(biāo)志位,之后從定時(shí)器中斷返回,因?yàn)樯厦嬉呀?jīng)提到從中斷上下文返回時(shí)是可能有調(diào)度時(shí)機(jī)的,如果定時(shí)器中斷返回時(shí)正好是返回到用戶態(tài)空間, 而且調(diào)度標(biāo)志位又置位了, 這時(shí)候就會(huì)做進(jìn)程切換. 在內(nèi)核源碼的匯編代碼中所有中斷返回處理都必須去判斷調(diào)度標(biāo)志位是否設(shè)置,如設(shè)置則執(zhí)行schedule()進(jìn)行調(diào)度。而我們知道實(shí)時(shí)進(jìn)程和普通進(jìn)程是共存的,調(diào)度器是怎么協(xié)調(diào)它們之間的調(diào)度的呢,其實(shí)很簡(jiǎn)單,每次調(diào)度時(shí),會(huì)先在實(shí)時(shí)進(jìn)程運(yùn)行隊(duì)列中查看是否有可運(yùn)行的實(shí)時(shí)進(jìn)程,如果沒(méi)有,再去普通進(jìn)程運(yùn)行隊(duì)列找下一個(gè)可運(yùn)行的普通進(jìn)程,如果也沒(méi)有,則調(diào)度器會(huì)使用idle進(jìn)程進(jìn)行運(yùn)行。之后的章節(jié)會(huì)放上代碼進(jìn)行詳細(xì)說(shuō)明。
系統(tǒng)并不是每時(shí)每刻都允許調(diào)度的發(fā)生,當(dāng)處于中斷期間的時(shí)候(無(wú)論是上半部還是下半部),調(diào)度是被系統(tǒng)禁止的,之后中斷過(guò)后才重新允許調(diào)度。而對(duì)于異常,系統(tǒng)并不會(huì)禁止調(diào)度,也就是在異常上下文中,系統(tǒng)是有可能發(fā)生調(diào)度的。
數(shù)據(jù)結(jié)構(gòu)
在這一節(jié)中,我們都是以普通進(jìn)程作為講解對(duì)象,因?yàn)槠胀ㄟM(jìn)程使用的調(diào)度算法為CFS調(diào)度算法,它是以紅黑樹(shù)為基礎(chǔ)的調(diào)度算法,其相比與實(shí)時(shí)進(jìn)程的調(diào)度算法復(fù)雜很多,而實(shí)時(shí)進(jìn)程在組織結(jié)構(gòu)上與普通進(jìn)程沒(méi)有太大差別,算法也較為簡(jiǎn)單。
組成形式圖1:

從圖1 中可以看出來(lái),每個(gè)CPU對(duì)應(yīng)包含一個(gè)運(yùn)行隊(duì)列結(jié)構(gòu)(struct rq),而每個(gè)運(yùn)行隊(duì)列又包含有其自己的實(shí)時(shí)進(jìn)程運(yùn)行隊(duì)列(struct rt_rq)、普通進(jìn)程運(yùn)行隊(duì)列(struct cfs_rq)、和一個(gè)我自己也不太知道有什么用的dl隊(duì)列(struct dl_rq),也就是說(shuō)每個(gè)CPU都有他們自己的實(shí)時(shí)進(jìn)程運(yùn)行隊(duì)列及普通進(jìn)程運(yùn)行隊(duì)列,為了方便,我們?cè)趫D中只描述普通進(jìn)程的組織結(jié)構(gòu)(最復(fù)雜的也是普通進(jìn)程的組織結(jié)構(gòu)),紅色se則為當(dāng)前CPU上正在執(zhí)行的程序,藍(lán)色為下個(gè)將要執(zhí)行的程序,其實(shí)圖中并不規(guī)范,實(shí)際上當(dāng)進(jìn)程運(yùn)行時(shí),會(huì)從紅黑樹(shù)中剝離出來(lái),然后設(shè)定下一個(gè)調(diào)度進(jìn)程,當(dāng)進(jìn)程運(yùn)行時(shí)間結(jié)束時(shí),再重新放入紅黑樹(shù)中。而為什么CPU0上有兩個(gè)藍(lán)色將被調(diào)度進(jìn)程,將在組調(diào)度中解釋。而為什么紅黑樹(shù)中又有一個(gè)子紅黑樹(shù),我們將在調(diào)度實(shí)體中解釋。
組調(diào)度(struct task_group)
我們知道,linux是一個(gè)多用戶系統(tǒng),如果有兩個(gè)進(jìn)程分別屬于兩個(gè)用戶,而進(jìn)程的優(yōu)先級(jí)不同,會(huì)導(dǎo)致兩個(gè)用戶所占用的CPU時(shí)間不同,這樣顯然是不公平的(如果優(yōu)先級(jí)差距很大,低優(yōu)先級(jí)進(jìn)程所屬用戶使用CPU的時(shí)間就很小),所以內(nèi)核引入組調(diào)度。如果基于用戶分組,即使進(jìn)程優(yōu)先級(jí)不同,這兩個(gè)用戶使用的CPU時(shí)間都為50%。這就是為什么圖1 中CPU0有兩個(gè)藍(lán)色將被調(diào)度的程序,如果task_group1中的運(yùn)行時(shí)間還沒(méi)有使用完,而當(dāng)前進(jìn)程運(yùn)行時(shí)間使用完后,會(huì)調(diào)度task_group1中的下一個(gè)被調(diào)度進(jìn)程;相反,如果task_group1的運(yùn)行時(shí)間使用結(jié)束,則調(diào)用上一層的下一個(gè)被調(diào)度進(jìn)程。需要注意的是,一個(gè)組調(diào)度中可能會(huì)有一部分是實(shí)時(shí)進(jìn)程,一部分是普通進(jìn)程,這也導(dǎo)致這種組要能夠滿足即能在實(shí)時(shí)調(diào)度中進(jìn)行調(diào)度,又可以在CFS調(diào)度中進(jìn)行調(diào)度。 linux可以以以下兩種方式進(jìn)行進(jìn)程的分組:
用戶ID:按照進(jìn)程的USER ID進(jìn)行分組,在對(duì)應(yīng)的/sys/kernel/uid/目錄下會(huì)生成一個(gè)cpu.share的文件,可以通過(guò)配置該文件來(lái)配置用戶所占CPU時(shí)間比例。
cgourp(control group):生成組用于限制其所有進(jìn)程,比如我生成一個(gè)組(生成后此組為空,里面沒(méi)有進(jìn)程),設(shè)置其CPU使用率為10%,并把一個(gè)進(jìn)程丟進(jìn)這個(gè)組中,那么這個(gè)進(jìn)程最多只能使用CPU的10%,如果我們將多個(gè)進(jìn)程丟進(jìn)這個(gè)組,這個(gè)組的所有進(jìn)程平分這個(gè)10%。
注意的是,這里的進(jìn)程組概念和fork調(diào)用所產(chǎn)生的父子進(jìn)程組概念不一樣,文章所使用的進(jìn)程組概念全為組調(diào)度中進(jìn)程組的概念。為了管理組調(diào)度,內(nèi)核引進(jìn)了struct task_group結(jié)構(gòu),如下:
在struct task_group結(jié)構(gòu)中,最重要的成員為 struct sched_entity ** se 和 struct cfs_rq ** cfs_rq。在圖1 中,root_task_group與task_group1都只有一個(gè),它們?cè)诔跏蓟瘯r(shí)會(huì)根據(jù)CPU個(gè)數(shù)為se和cfs_rq分配空間,即在task_group1和root_task_group中會(huì)為每個(gè)CPU分配一個(gè)se和cfs_rq,同理用于實(shí)時(shí)進(jìn)程的 struct sched_rt_entity ** rt_se 和 struct rt_rq ** rt_rq也是一樣。為什么這樣呢,原因就是在多核多CPU的情況下,同一進(jìn)程組的進(jìn)程有可能在不同CPU上同時(shí)運(yùn)行,所以每個(gè)進(jìn)程組都必須對(duì)每個(gè)CPU分配它的調(diào)度實(shí)體(struct sched_entity 和 struct sched_rt_entity)和運(yùn)行隊(duì)列(struct cfs_rq 和 struct rt_rq)。
調(diào)度實(shí)體(struct sched_entity)
在組調(diào)度中,也涉及到調(diào)度實(shí)體這個(gè)概念,它的結(jié)構(gòu)為struct sched_entity(簡(jiǎn)稱se),就是圖1 紅黑樹(shù)中的se。其實(shí)際上就代表了一個(gè)調(diào)度對(duì)象,可以為一個(gè)進(jìn)程,也可以為一個(gè)進(jìn)程組。對(duì)于根的紅黑樹(shù)而言,一個(gè)進(jìn)程組就相當(dāng)于一個(gè)調(diào)度實(shí)體,一個(gè)進(jìn)程也相當(dāng)于一個(gè)調(diào)度實(shí)體。我們可以先看看其結(jié)構(gòu),如下:
實(shí)際上,紅黑樹(shù)是根據(jù) struct rb_node 建立起關(guān)系的,不過(guò) struct rb_node 與 struct sched_entity 是一一對(duì)應(yīng)關(guān)系,也可以簡(jiǎn)單看為一個(gè)紅黑樹(shù)結(jié)點(diǎn)就是一個(gè)調(diào)度實(shí)體。可以看出,在 struct sched_entity 結(jié)構(gòu)中,包含了一個(gè)進(jìn)程(或進(jìn)程組)調(diào)度的全部數(shù)據(jù),其被包含在 struct task_struct 結(jié)構(gòu)中的se中,如下:
在 struct sched_entity 結(jié)構(gòu)中,值得我們注意的成員是:
load:權(quán)重,通過(guò)優(yōu)先級(jí)轉(zhuǎn)換而成,是vruntime計(jì)算的關(guān)鍵。
on_rq:表明是否處于CFS紅黑樹(shù)運(yùn)行隊(duì)列中,需要明確一個(gè)觀點(diǎn)就是,CFS運(yùn)行隊(duì)列里面包含有一個(gè)紅黑樹(shù),但這個(gè)紅黑樹(shù)并不是CFS運(yùn)行隊(duì)列的全部,因?yàn)榧t黑樹(shù)僅僅是用于選擇出下一個(gè)調(diào)度程序的算法。很簡(jiǎn)單的一個(gè)例子,普通程序運(yùn)行時(shí),其并不在紅黑樹(shù)中,但是還是處于CFS運(yùn)行隊(duì)列中,其on_rq為真。只有準(zhǔn)備退出、即將睡眠等待和轉(zhuǎn)為實(shí)時(shí)進(jìn)程的進(jìn)程其CFS運(yùn)行隊(duì)列的on_rq為假。
vruntime:虛擬運(yùn)行時(shí)間,調(diào)度的關(guān)鍵,其計(jì)算公式:一次調(diào)度間隔的虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(shí)間 * (NICE_0_LOAD / 權(quán)重)。可以看出跟實(shí)際運(yùn)行時(shí)間和權(quán)重有關(guān),紅黑樹(shù)就是以此作為排序的標(biāo)準(zhǔn),優(yōu)先級(jí)越高的進(jìn)程在運(yùn)行時(shí)其vruntime增長(zhǎng)的越慢,其可運(yùn)行時(shí)間相對(duì)就長(zhǎng),而且也越有可能處于紅黑樹(shù)的最左結(jié)點(diǎn),調(diào)度器每次都選擇最左邊的結(jié)點(diǎn)為下一個(gè)調(diào)度進(jìn)程。注意其值為單調(diào)遞增,在每個(gè)調(diào)度器的時(shí)鐘中斷時(shí)當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間都會(huì)累加。單純的說(shuō)就是進(jìn)程們都在比誰(shuí)的vruntime最小,最小的將被調(diào)度。
cfs_rq:此調(diào)度實(shí)體所處于的CFS運(yùn)行隊(duì)列。
my_q:如果此調(diào)度實(shí)體代表的是一個(gè)進(jìn)程組,那么此調(diào)度實(shí)體就包含有一個(gè)自己的CFS運(yùn)行隊(duì)列,其CFS運(yùn)行隊(duì)列中存放的是此進(jìn)程組中的進(jìn)程,這些進(jìn)程就不會(huì)在其他CFS運(yùn)行隊(duì)列的紅黑樹(shù)中被包含(包括頂層紅黑樹(shù)也不會(huì)包含他們,他們只屬于這個(gè)進(jìn)程組的紅黑樹(shù))。
對(duì)于怎么理解一個(gè)進(jìn)程組有它自己的CFS運(yùn)行隊(duì)列,其實(shí)很好理解,比如在根CFS運(yùn)行隊(duì)列的紅黑樹(shù)上有一個(gè)進(jìn)程A一個(gè)進(jìn)程組B,各占50%的CPU,對(duì)于根的紅黑樹(shù)而言,他們就是兩個(gè)調(diào)度實(shí)體。調(diào)度器調(diào)度的不是進(jìn)程A就是進(jìn)程組B,而如果調(diào)度到進(jìn)程組B,進(jìn)程組B自己選擇一個(gè)程序交給CPU運(yùn)行就可以了,而進(jìn)程組B怎么選擇一個(gè)程序給CPU,就是通過(guò)自己的CFS運(yùn)行隊(duì)列的紅黑樹(shù)選擇,如果進(jìn)程組B還有個(gè)子進(jìn)程組C,原理都一樣,就是一個(gè)層次結(jié)構(gòu)。 而在 struct task_struct 結(jié)構(gòu)中,我們注意到有個(gè)調(diào)度類,里面包含的是調(diào)度處理函數(shù),它具體如下:
這個(gè)調(diào)度類具體有什么用呢,實(shí)際上在內(nèi)核中不同的調(diào)度算法它們的操作都不相同,為了方便修改、替換調(diào)度算法,使用了調(diào)度類,每個(gè)調(diào)度算法只需要實(shí)現(xiàn)自己的調(diào)度類就可以了,CFS算法有它的調(diào)度類,SCHED_FIFO也有它自己的調(diào)度類,當(dāng)一個(gè)進(jìn)程創(chuàng)建時(shí),用什么調(diào)度算法就將其 task_struct->sched_class 指向其相應(yīng)的調(diào)度類,調(diào)度器每次調(diào)度處理時(shí),就通過(guò)當(dāng)前進(jìn)程的調(diào)度類函數(shù)進(jìn)程操作,大大提高了可移植性和易修改性。
CFS運(yùn)行隊(duì)列(struct cfs_rq)
我們現(xiàn)在知道,在系統(tǒng)中至少有一個(gè)CFS運(yùn)行隊(duì)列,其就是根CFS運(yùn)行隊(duì)列,而其他的進(jìn)程組和進(jìn)程都包含在此運(yùn)行隊(duì)列中,不同的是進(jìn)程組又有它自己的CFS運(yùn)行隊(duì)列,其運(yùn)行隊(duì)列中包含的是此進(jìn)程組中的所有進(jìn)程。當(dāng)調(diào)度器從根CFS運(yùn)行隊(duì)列中選擇了一個(gè)進(jìn)程組進(jìn)行調(diào)度時(shí),進(jìn)程組會(huì)從自己的CFS運(yùn)行隊(duì)列中選擇一個(gè)調(diào)度實(shí)體進(jìn)行調(diào)度(這個(gè)調(diào)度實(shí)體可能為進(jìn)程,也可能又是一個(gè)子進(jìn)程組),就這樣一直深入,直到最后選出一個(gè)進(jìn)程進(jìn)行運(yùn)行為止。
對(duì)于 struct cfs_rq 結(jié)構(gòu)沒(méi)有什么好說(shuō)明的,只要確定其代表著一個(gè)CFS運(yùn)行隊(duì)列,并且包含有一個(gè)紅黑樹(shù)進(jìn)行選擇調(diào)度進(jìn)程即可。
load:其保存的是進(jìn)程組中所有進(jìn)程的權(quán)值總和,需要注意子進(jìn)程計(jì)算vruntime時(shí)需要用到進(jìn)程組的load。CPU運(yùn)行隊(duì)列(struct rq)
每個(gè)CPU都有自己的 struct rq 結(jié)構(gòu),其用于描述在此CPU上所運(yùn)行的所有進(jìn)程,其包括一個(gè)實(shí)時(shí)進(jìn)程隊(duì)列和一個(gè)根CFS運(yùn)行隊(duì)列,在調(diào)度時(shí),調(diào)度器首先會(huì)先去實(shí)時(shí)進(jìn)程隊(duì)列找是否有實(shí)時(shí)進(jìn)程需要運(yùn)行,如果沒(méi)有才會(huì)去CFS運(yùn)行隊(duì)列找是否有進(jìn)行需要運(yùn)行,這就是為什么常說(shuō)的實(shí)時(shí)進(jìn)程優(yōu)先級(jí)比普通進(jìn)程高,不僅僅體現(xiàn)在prio優(yōu)先級(jí)上,還體現(xiàn)在調(diào)度器的設(shè)計(jì)上,至于dl運(yùn)行隊(duì)列,我暫時(shí)還不知道有什么用處,其優(yōu)先級(jí)比實(shí)時(shí)進(jìn)程還高,但是創(chuàng)建進(jìn)程時(shí)如果創(chuàng)建的是dl進(jìn)程創(chuàng)建會(huì)錯(cuò)誤(具體見(jiàn)sys_fork)。
