帶大家看看Linux內(nèi)核如何調(diào)度進(jìn)程的

1.開場(chǎng)白

環(huán)境：

處理器架構(gòu)：arm64

內(nèi)核源碼：linux-5.11

ubuntu版本：20.04.1

代碼閱讀工具：vim+ctags+cscope

本文步進(jìn)到Linux內(nèi)核進(jìn)程管理的核心部分，打開調(diào)度器的黑匣子，來看看Linux內(nèi)核如何調(diào)度進(jìn)程的。實(shí)際上，進(jìn)程調(diào)度器主要做兩件事：選擇下一個(gè)進(jìn)程，然后進(jìn)行上下文切換。

而何時(shí)調(diào)用主調(diào)度器調(diào)度進(jìn)程那是調(diào)度時(shí)機(jī)所關(guān)注的問題，而調(diào)度時(shí)機(jī)在之前的內(nèi)核搶占文章已經(jīng)做了詳細(xì)講解，在此不在贅述，而本文關(guān)注的調(diào)度時(shí)機(jī)是真正調(diào)用主調(diào)度器的時(shí)機(jī)。

本文分析的內(nèi)核源代碼主要集中在：

kernel/sched/core.c

kernel/sched/fair.c

2.調(diào)用時(shí)機(jī)

關(guān)于調(diào)度時(shí)機(jī)，網(wǎng)上的文章也五花八門，之前在內(nèi)核搶占文章已經(jīng)做了詳細(xì)講解，而在本文我們從源碼注釋中給出依據(jù)（再次強(qiáng)調(diào)一下：本文的調(diào)度時(shí)機(jī)關(guān)注的是何時(shí)調(diào)用主調(diào)度器，不是設(shè)置重新調(diào)度標(biāo)志的時(shí)機(jī)，之前講解中我們知道他們都可以稱為調(diào)度時(shí)機(jī)）。

先來說一下什么是主調(diào)度器，其實(shí)和主調(diào)度器并列的還有一個(gè)叫做周期性調(diào)度器的東西（后面有機(jī)會(huì)會(huì)講解，主要用于時(shí)鐘中斷tick調(diào)來使奪取處理器的控制權(quán)），他們都是內(nèi)核中的一個(gè)函數(shù)，在合適的時(shí)機(jī)被調(diào)用。

主調(diào)度器函數(shù)如下：

kernel/sched/core.c __schedule（）

內(nèi)核的很多路徑會(huì)包裝這個(gè)函數(shù)，主要分為主動(dòng)調(diào)度和搶占式調(diào)度場(chǎng)景。

內(nèi)核源碼中主調(diào)度器函數(shù)也給出了調(diào)度時(shí)機(jī)的注釋，下面我們就以此為依據(jù)來看下：

kernel/sched/core.c /* *__schedule()isthemainschedulerfunction. * *Themainmeansofdrivingtheschedulerandthusenteringthisfunctionare: * *1.Explicitblocking:mutex,semaphore,waitqueue,etc. * *2.TIF_NEED_RESCHEDflagischeckedoninterruptanduserspacereturn *paths.Forexample,seearch/x86/entry_64.S. * *Todrivepreemptionbetweentasks,theschedulersetstheflagintimer *interrupthandlerscheduler_tick(). * *3.Wakeupsdon'treallycauseentryintoschedule().Theyadda *tasktotherun-queueandthat'sit. * *Now,ifthenewtaskaddedtotherun-queuepreemptsthecurrent *task,thenthewakeupsetsTIF_NEED_RESCHEDandschedule()gets *calledonthenearestpossibleoccasion: * *-Ifthekernelispreemptible(CONFIG_PREEMPTION=y): * *-insyscallorexceptioncontext,atthenextoutmost *preempt_enable().(thismightbeassoonasthewake_up()'s *spin_unlock()!) * *-inIRQcontext,returnfrominterrupt-handlerto *preemptiblecontext * *-Ifthekernelisnotpreemptible(CONFIG_PREEMPTIONisnotset) *thenatthenext: *-cond_resched()call *-explicitschedule()call *-returnfromsyscallorexceptiontouser-space *-returnfrominterrupt-handlertouser-space * *WARNING:mustbecalledwithpreemptiondisabled! */ staticvoid__schednotrace__schedule(boolpreempt)

我們對(duì)注釋做出解釋，讓大家深刻理解調(diào)度時(shí)機(jī)（基本上是原樣翻譯，用顏色標(biāo)注）。

1.顯式阻塞場(chǎng)景：包括互斥體、信號(hào)量、等待隊(duì)列等。

這個(gè)場(chǎng)景主要是為了等待某些資源而主動(dòng)放棄處理器，來調(diào)用主調(diào)度器，如發(fā)現(xiàn)互斥體被其他內(nèi)核路徑所持有，則睡眠等待互斥體被釋放的時(shí)候來喚醒我。

2.在中斷和用戶空間返回路徑上檢查TIF_NEED_RESCHED標(biāo)志。例如，arch/x86/entry_64.S。為了在任務(wù)之間驅(qū)動(dòng)搶占，調(diào)度程序在計(jì)時(shí)器中斷處理程序scheduler_tick()中設(shè)置標(biāo)志。

解釋如下：這實(shí)際上是說重新調(diào)度標(biāo)志（TIF_NEED_RESCHED）的設(shè)置和檢查的情形。

1）重新調(diào)度標(biāo)志設(shè)置情形：如scheduler_tick周期性調(diào)度器按照特定條件設(shè)置、喚醒的路徑上按照特定條件設(shè)置等。當(dāng)前這樣的場(chǎng)景并不會(huì)直接調(diào)用主調(diào)度器，而會(huì)在最近的調(diào)度點(diǎn)到來時(shí)調(diào)用主調(diào)度器。

2）重新調(diào)度標(biāo)志檢查情形：是真正的調(diào)用主調(diào)度器，下面的場(chǎng)景都會(huì)涉及到，在此不在贅述。

3.喚醒并不會(huì)真正導(dǎo)致schedule()的進(jìn)入。他們添加一個(gè)任務(wù)到運(yùn)行隊(duì)列，僅此而已。

現(xiàn)在，如果添加到運(yùn)行隊(duì)列中的新任務(wù)搶占了當(dāng)前任務(wù)，那么喚醒設(shè)置TIF_NEED_RESCHED, schedule()在最近的可能情況下被調(diào)用:

1）如果內(nèi)核是可搶占的(CONFIG_PREEMPTION=y)

-在系統(tǒng)調(diào)用或異常上下文中，最外層的preempt_enable()。(這可能和wake_up()的spin_unlock()一樣快!)

-在IRQ上下文中，從中斷處理程序返回到搶占上下文

注釋中很簡(jiǎn)潔的幾句話，但其中的含義需要深刻去體會(huì)。

首先需要知道一點(diǎn)是：內(nèi)核搶占說的是處于內(nèi)核態(tài)的任務(wù)被其他任務(wù)所搶占的情況（無論是不是可搶占式內(nèi)核，處于用戶態(tài)的任務(wù)都可以被搶占，處于內(nèi)核態(tài)的任務(wù)是否能被搶占由是否開啟內(nèi)核搶占來決定），當(dāng)然內(nèi)核態(tài)的任務(wù)可以是內(nèi)核線程也可以是通過系統(tǒng)調(diào)用請(qǐng)求內(nèi)核服務(wù)的用戶任務(wù)。

情況1：這是重新開啟內(nèi)核搶占的情況，即是搶占計(jì)數(shù)器為0時(shí)，檢查重新調(diào)度標(biāo)志（TIF_NEED_RESCHED），如果設(shè)置則調(diào)用主調(diào)度器，放棄處理器（這是搶占式調(diào)度）。

情況2：中斷返回內(nèi)核態(tài)的時(shí)候，檢查重新調(diào)度標(biāo)志（TIF_NEED_RESCHED），如果設(shè)置且搶占計(jì)數(shù)器為0時(shí)則調(diào)用主調(diào)度器，放棄處理器（這是搶占式調(diào)度）。

注：關(guān)于內(nèi)核搶占可以參考之前發(fā)布的文章。

2）如果內(nèi)核是不可搶占的(CONFIG_PREEMPTION=y)

cond_resched()調(diào)用

顯式的schedule()調(diào)用

從系統(tǒng)調(diào)用或異常返回到用戶空間

從中斷處理器返回到用戶空間

解釋如下：

cond_resched()是為了在不可搶占內(nèi)核的一些耗時(shí)的內(nèi)核處理路徑中增加主動(dòng)搶占點(diǎn)（搶占計(jì)數(shù)器是否為0且當(dāng)前任務(wù)被設(shè)置了重新調(diào)度標(biāo)志），則調(diào)用主調(diào)度器進(jìn)行搶占式調(diào)度，所進(jìn)行低延時(shí)處理。

顯式的schedule()調(diào)用，這是主動(dòng)放棄處理器的場(chǎng)景，如一些睡眠場(chǎng)景，像用戶任務(wù)調(diào)用sleep。

系統(tǒng)調(diào)用或異常返回到用戶空間使會(huì)判斷當(dāng)前進(jìn)程是否設(shè)置重新調(diào)度標(biāo)志（TIF_NEED_RESCHED），如果設(shè)置則調(diào)用主調(diào)度器，放棄處理器。

中斷處理器返回到用戶空間會(huì)判斷當(dāng)前進(jìn)程是否設(shè)置重新調(diào)度標(biāo)志（TIF_NEED_RESCHED），如果設(shè)置則調(diào)用主調(diào)度器，放棄處理器。

其實(shí)還有一種場(chǎng)景也會(huì)調(diào)用到主調(diào)度器讓出處理器，那就是進(jìn)程退出時(shí)，這里不在贅述。

下面給出總結(jié)：

1.主動(dòng)調(diào)度：

睡眠場(chǎng)景，如sleep。

顯式阻塞場(chǎng)景，如互斥體，信號(hào)量，等待隊(duì)列，完成量等。

任務(wù)退出時(shí)，調(diào)用do_exit去釋放進(jìn)程資源，最后會(huì)調(diào)用一次主調(diào)度器

2.搶占調(diào)度：

不可搶占式內(nèi)核

cond_resched()調(diào)用

顯式的schedule()調(diào)用

從系統(tǒng)調(diào)用或異常返回到用戶空間

從中斷處理器返回到用戶空間

可搶占式內(nèi)核（增加一些搶占點(diǎn)）

重新開啟內(nèi)核搶占

中斷返回內(nèi)核態(tài)的時(shí)候

3.主調(diào)度器調(diào)用時(shí)機(jī)源碼窺探

下面給出主要的一些主調(diào)度器調(diào)用時(shí)機(jī)源碼分析，作為學(xué)習(xí)參考。

3.1 常規(guī)場(chǎng)景

中斷返回用戶態(tài)場(chǎng)景：

arch/arm64/kernel/entry.S el0_irq ->ret_to_user ->work_pending ->do_notify_resume ->if(thread_flags&_TIF_NEED_RESCHED){//arch/arm64/kernel/signal.c schedule(); ->__schedule(false);//kernel/sched/core.cfalse表示主動(dòng)調(diào)度

異常返回用戶態(tài)場(chǎng)景：

arch/arm64/kernel/entry.S el0_sync ->ret_to_user ...

任務(wù)退出場(chǎng)景：

kernel/exit.c do_exit ->do_task_dead ->__schedule(false);//kernel/sched/core.cfalse表示主動(dòng)調(diào)度

顯式阻塞場(chǎng)景（舉例互斥體）：

kernel/locking/mutex.c mutex_lock ->__mutex_lock_slowpath ->__mutex_lock ->__mutex_lock_common ->schedule_preempt_disabled ->schedule(); ->__schedule(false);//kernel/sched/core.cfalse表示主動(dòng)調(diào)度

3.2 支持內(nèi)核搶占場(chǎng)景

中斷返回內(nèi)核態(tài)場(chǎng)景

arch/arm64/kernel/entry.S el1_irq #ifdefCONFIG_PREEMPTION ->arm64_preempt_schedule_irq ->preempt_schedule_irq(); ->__schedule(true);//kernel/sched/core.ctrue表示搶占式調(diào)度 #endif

內(nèi)核搶占開啟場(chǎng)景

preempt_enable ->if(unlikely(preempt_count_dec_and_test()))//搶占計(jì)數(shù)器減一為0 __preempt_schedule(); ->preempt_schedule//kernel/sched/core.c ->__schedule(true)//調(diào)用主調(diào)度器進(jìn)行搶占式調(diào)度

注：一般說異常/中斷返回，返回是處理器異常狀態(tài)，可能是用戶態(tài)也可能是內(nèi)核態(tài)，但是會(huì)看到很多資料寫的都是用戶空間/內(nèi)核空間并不準(zhǔn)確，但是我們認(rèn)為表達(dá)一個(gè)意思，做的心中有數(shù)即可。

3.選擇下一個(gè)進(jìn)程

本節(jié)主要講解主調(diào)度器是如何選擇下一個(gè)進(jìn)程的，這和調(diào)度策略強(qiáng)相關(guān)。

下面我們來看具體實(shí)現(xiàn)：

kernel/sched/core.c __schedule ->next=pick_next_task(rq,prev,&rf); ->if(likely(prev->sched_class<=?&fair_sched_class?&&?????????????? ????????|??rq->nr_running==rq->cfs.h_nr_running)){ p=pick_next_task_fair(rq,prev,rf); if(unlikely(p==RETRY_TASK)) gotorestart; /*Assumesfair_sched_class->next==idle_sched_class*/ if(!p){ put_prev_task(rq,prev); p=pick_next_task_idle(rq); } returnp; } for_each_class(class){ p=class->pick_next_task(rq); if(p) returnp; }

這里做了優(yōu)化，當(dāng)當(dāng)前進(jìn)程的調(diào)度類為公平調(diào)度類或者空閑調(diào)度類時(shí)，且cpu運(yùn)行隊(duì)列的進(jìn)程個(gè)數(shù)等于cfs運(yùn)行隊(duì)列進(jìn)程個(gè)數(shù)，說明運(yùn)行隊(duì)列進(jìn)程都是普通進(jìn)程，則直接調(diào)用公平調(diào)度類的pick_next_task_fair選擇下一個(gè)進(jìn)程（選擇紅黑樹最左邊的那個(gè)進(jìn)程），如果沒有找到說明當(dāng)前進(jìn)程調(diào)度類為空閑調(diào)度類，直接調(diào)用pick_next_task_idle選擇idle進(jìn)程。

否則，遍歷調(diào)度類，從高優(yōu)先級(jí)調(diào)度類開始調(diào)用其pick_next_task方法選擇下一個(gè)進(jìn)程。

下面以公平調(diào)度類為例來看如何選擇下一個(gè)進(jìn)程的：調(diào)用過程如下(這里暫不考慮組調(diào)度情況)：

pick_next_task ->pick_next_task_fair//kernel/sched/fair.c ->if(prev) put_prev_task(rq,prev); se=pick_next_entity(cfs_rq,NULL); set_next_entity(cfs_rq,se);

先看put_prev_task：

put_prev_task ->prev->sched_class->put_prev_task(rq,prev); ->put_prev_task_fair ->put_prev_entity(cfs_rq,se); ->/*Put'current'backintothetree.*/ __enqueue_entity(cfs_rq,prev); cfs_rq->curr=NULL;

這里會(huì)調(diào)用__enqueue_entity將前一個(gè)進(jìn)程重新加入到cfs隊(duì)列的紅黑樹。然后將cfs_rq->curr 設(shè)置為空。

再看pick_next_entity：

pick_next_entity ->left=__pick_first_entity(cfs_rq); ->left=rb_first_cached(&cfs_rq->tasks_timeline);

將選擇cfs隊(duì)列紅黑樹最左邊進(jìn)程。

最后看set_next_entity：

set_next_entity ->__dequeue_entity(cfs_rq,se); ->cfs_rq->curr=se;

這里調(diào)用__dequeue_entity將下一個(gè)選擇的進(jìn)程從cfs隊(duì)列的紅黑樹中刪除，然后將cfs隊(duì)列的curr指向進(jìn)程的調(diào)度實(shí)體。

選擇下一個(gè)進(jìn)程總結(jié)如下：

運(yùn)行隊(duì)列中只有公平進(jìn)程則選擇公平調(diào)度類的pick_next_task_fair選擇進(jìn)程。

當(dāng)前進(jìn)程為idle進(jìn)程，且沒有公平進(jìn)程存在情況下，調(diào)用pick_next_task_idle選擇idle進(jìn)程。

運(yùn)行隊(duì)列存在除了公平進(jìn)程的其他進(jìn)程，則從高優(yōu)先級(jí)到低優(yōu)先級(jí)調(diào)用具體調(diào)度類的pick_next_task選擇進(jìn)程。

對(duì)于公平調(diào)度類，選擇下一個(gè)進(jìn)程主要過程如下：1）調(diào)用put_prev_task方法將前一個(gè)進(jìn)程重新加入cfs隊(duì)列的紅黑樹。2）調(diào)用pick_next_entity 選擇紅黑樹最左邊的進(jìn)程作為下一個(gè)進(jìn)程。3）將下一個(gè)進(jìn)程從紅黑樹中刪除，cfs隊(duì)列的curr指向進(jìn)程的調(diào)度實(shí)體。

通用的調(diào)度類選擇順序?yàn)椋?/p>

stop_sched_class ->dl_sched_class->rt_sched_class->fair_sched_class ->idle_sched_class

比如：當(dāng)前運(yùn)行隊(duì)列都是cfs的普通進(jìn)程，某一時(shí)刻發(fā)生中斷喚醒了一個(gè)rt進(jìn)程，那么在最近的調(diào)度點(diǎn)到來時(shí)就會(huì)調(diào)用主調(diào)度器選擇rt進(jìn)程作為next進(jìn)程。

做了以上的工作之后，紅黑樹中選擇下一個(gè)進(jìn)程的時(shí)候就不會(huì)再選擇到當(dāng)前cpu上運(yùn)行的進(jìn)程了，而當(dāng)前進(jìn)程調(diào)度實(shí)體又被cfs隊(duì)列的curr來記錄著（運(yùn)行隊(duì)列的curr也會(huì)記錄當(dāng)前進(jìn)程）。

下面給出公平調(diào)度類選擇下一個(gè)進(jìn)程圖解（其中A為前一個(gè)進(jìn)程，即是當(dāng)前進(jìn)程，即為前一個(gè)進(jìn)程，B為下一個(gè)進(jìn)程）

編輯：jq