1.開場白

環(huán)境：

處理器架構：arm64

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

ubuntu版本：20.04.1

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

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

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

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

kernel/sched/core.c

kernel/sched/fair.c

2.調(diào)用時機

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

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

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

kernel/sched/core.c __schedule（）

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

內(nèi)核源碼中主調(diào)度器函數(shù)也給出了調(diào)度時機的注釋，下面我們就以此為依據(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)

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

1.顯式阻塞場景：包括互斥體、信號量、等待隊列等。

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

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

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

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

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

3.喚醒并不會真正導致schedule()的進入。他們添加一個任務到運行隊列，僅此而已。

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

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

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

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

注釋中很簡潔的幾句話，但其中的含義需要深刻去體會。

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

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

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

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

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

cond_resched()調(diào)用

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

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

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

解釋如下：

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

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

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

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

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

下面給出總結：

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

睡眠場景，如sleep。

顯式阻塞場景，如互斥體，信號量，等待隊列，完成量等。

任務退出時，調(diào)用do_exit去釋放進程資源，最后會調(diào)用一次主調(diào)度器

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

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

cond_resched()調(diào)用

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

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

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

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

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

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

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

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

3.1 常規(guī)場景

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

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表示主動調(diào)度

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

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

任務退出場景：

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

顯式阻塞場景（舉例互斥體）：

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

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

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

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)核搶占開啟場景

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

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

3.選擇下一個進程

本節(jié)主要講解主調(diào)度器是如何選擇下一個進程的，這和調(diào)度策略強相關。

下面我們來看具體實現(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)化，當當前進程的調(diào)度類為公平調(diào)度類或者空閑調(diào)度類時，且cpu運行隊列的進程個數(shù)等于cfs運行隊列進程個數(shù)，說明運行隊列進程都是普通進程，則直接調(diào)用公平調(diào)度類的pick_next_task_fair選擇下一個進程（選擇紅黑樹最左邊的那個進程），如果沒有找到說明當前進程調(diào)度類為空閑調(diào)度類，直接調(diào)用pick_next_task_idle選擇idle進程。

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

下面以公平調(diào)度類為例來看如何選擇下一個進程的：調(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;

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

再看pick_next_entity：

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

將選擇cfs隊列紅黑樹最左邊進程。

最后看set_next_entity：

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

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

選擇下一個進程總結如下：

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

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

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

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

通用的調(diào)度類選擇順序為：

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

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

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

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

編輯：jq