深入理解Linux內(nèi)核之主調(diào)度器（上）
1.開(kāi)場(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)程管理的核心部分，打開(kāi)調(diào)度器的黑匣子，來(lái)看看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)注的問(wè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)上的文章也五花八門(mén)，之前在內(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ī)，之前講解中我們知道他們都可以稱(chēng)為調(diào)度時(shí)機(jī)）。
先來(lái)說(shuō)一下什么是主調(diào)度器，其實(shí)和主調(diào)度器并列的還有一個(gè)叫做周期性調(diào)度器的東西（后面有機(jī)會(huì)會(huì)講解，主要用于時(shí)鐘中斷tick調(diào)來(lái)使奪取處理器的控制權(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ī)的注釋?zhuān)旅嫖覀兙鸵源藶橐罁?jù)來(lái)看下：
kernel/sched/core.c
/*
* __schedule() is the main scheduler function.
*
* The main means of driving the scheduler and thus entering this function are:
*
* 1. Explicit blocking: mutex, semaphore, waitqueue, etc.
*
* 2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
* paths. For example, see arch/x86/entry_64.S.
*
* To drive preemption between tasks, the scheduler sets the flag in timer
* interrupt handler scheduler_tick().
*
* 3. Wakeups don't really cause entry into schedule(). They add a
* task to the run-queue and that's it.
*
* Now, if the new task added to the run-queue preempts the current
* task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
* called on the nearest possible occasion:
*
* - If the kernel is preemptible (CONFIG_PREEMPTION=y):
*
* - in syscall or exception context, at the next outmost
* preempt_enable(). (this might be as soon as the wake_up()'s
* spin_unlock()!)
*
* - in IRQ context, return from interrupt-handler to
* preemptible context
*
* - If the kernel is not preemptible (CONFIG_PREEMPTION is not set)
* then at the next:
* - cond_resched() call
* - explicit schedule() call
* - return from syscall or exception to user-space
* - return from interrupt-handler to user-space
*
* WARNING: must be called with preemption disabled!
*/
static void __sched notrace __schedule(bool preempt)
我們對(duì)注釋做出解釋?zhuān)尨蠹疑羁汤斫庹{(diào)度時(shí)機(jī)（基本上是原樣翻譯，用顏色標(biāo)注）。
1.顯式阻塞場(chǎng)景：包括互斥體、信號(hào)量、等待隊(duì)列等。
這個(gè)場(chǎng)景主要是為了等待某些資源而主動(dòng)放棄處理器，來(lái)調(diào)用主調(diào)度器，如發(fā)現(xiàn)互斥體被其他內(nèi)核路徑所持有，則睡眠等待互斥體被釋放的時(shí)候來(lái)喚醒我。
解釋如下：這實(shí)際上是說(shuō)重新調(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)到來(lái)時(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à)，但其中的含義需要深刻去體會(huì)。
首先需要知道一點(diǎn)是：內(nèi)核搶占說(shuō)的是處于內(nèi)核態(tài)的任務(wù)被其他任務(wù)所搶占的情況（無(wú)論是不是可搶占式內(nèi)核，處于用戶(hù)態(tài)的任務(wù)都可以被搶占，處于內(nèi)核態(tài)的任務(wù)是否能被搶占由是否開(kāi)啟內(nèi)核搶占來(lái)決定），當(dāng)然內(nèi)核態(tài)的任務(wù)可以是內(nèi)核線(xiàn)程也可以是通過(guò)系統(tǒng)調(diào)用請(qǐng)求內(nèi)核服務(wù)的用戶(hù)任務(wù)。
情況1：這是重新開(kāi)啟內(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)用或異常返回到用戶(hù)空間 從中斷處理器返回到用戶(hù)空間
解釋如下：
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)景，像用戶(hù)任務(wù)調(diào)用sleep。
系統(tǒng)調(diào)用或異常返回到用戶(hù)空間使會(huì)判斷當(dāng)前進(jìn)程是否設(shè)置重新調(diào)度標(biāo)志（TIF_NEED_RESCHED），如果設(shè)置則調(diào)用主調(diào)度器，放棄處理器。
中斷處理器返回到用戶(hù)空間會(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)用或異常返回到用戶(hù)空間
從中斷處理器返回到用戶(hù)空間
可搶占式內(nèi)核（增加一些搶占點(diǎn)）
重新開(kāi)啟內(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)景
中斷返回用戶(hù)態(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.c false表示主動(dòng)調(diào)度
異常返回用戶(hù)態(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.c false表示主動(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.c false表示主動(dòng)調(diào)度
3.2 支持內(nèi)核搶占場(chǎng)景
中斷返回內(nèi)核態(tài)場(chǎng)景
arch/arm64/kernel/entry.S
el1_irq
#ifdef CONFIG_PREEMPTION
->arm64_preempt_schedule_irq
->preempt_schedule_irq();
->__schedule(true); //kernel/sched/core.c true表示搶占式調(diào)度
#endif
內(nèi)核搶占開(kā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)度
注：一般說(shuō)異常/中斷返回，返回是處理器異常狀態(tài)，可能是用戶(hù)態(tài)也可能是內(nèi)核態(tài)，但是會(huì)看到很多資料寫(xiě)的都是用戶(hù)空間/內(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)。
下面我們來(lái)看具體實(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))
goto restart;
/* Assumes fair_sched_class->next == idle_sched_class */
if (!p) {
put_prev_task(rq, prev);
p = pick_next_task_idle(rq);
}
return p;
}
for_each_class(class) {
p = class->pick_next_task(rq);
if (p)
return p;
}
這里做了優(yōu)化，當(dāng)當(dāng)前進(jìn)程的調(diào)度類(lèi)為公平調(diào)度類(lèi)或者空閑調(diào)度類(lèi)時(shí)，且cpu運(yùn)行隊(duì)列的進(jìn)程個(gè)數(shù)等于cfs運(yùn)行隊(duì)列進(jìn)程個(gè)數(shù)，說(shuō)明運(yùn)行隊(duì)列進(jìn)程都是普通進(jìn)程，則直接調(diào)用公平調(diào)度類(lèi)的pick_next_task_fair選擇下一個(gè)進(jìn)程（選擇紅黑樹(shù)最左邊的那個(gè)進(jìn)程），如果沒(méi)有找到說(shuō)明當(dāng)前進(jìn)程調(diào)度類(lèi)為空閑調(diào)度類(lèi)，直接調(diào)用pick_next_task_idle選擇idle進(jìn)程。
否則，遍歷調(diào)度類(lèi)，從高優(yōu)先級(jí)調(diào)度類(lèi)開(kāi)始調(diào)用其pick_next_task方法選擇下一個(gè)進(jìn)程。
下面以公平調(diào)度類(lèi)為例來(lái)看如何選擇下一個(gè)進(jìn)程的：調(diào)用過(guò)程如下(這里暫不考慮組調(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' back into the tree. */
__enqueue_entity(cfs_rq, prev);
cfs_rq->curr = NULL;
這里會(huì)調(diào)用__enqueue_entity將前一個(gè)進(jìn)程重新加入到cfs隊(duì)列的紅黑樹(shù)。然后將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ì)列紅黑樹(shù)最左邊進(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ì)列的紅黑樹(shù)中刪除，然后將cfs隊(duì)列的curr指向進(jìn)程的調(diào)度實(shí)體。
選擇下一個(gè)進(jìn)程總結(jié)如下：
運(yùn)行隊(duì)列中只有公平進(jìn)程則選擇公平調(diào)度類(lèi)的pick_next_task_fair選擇進(jìn)程。
當(dāng)前進(jìn)程為idle進(jìn)程，且沒(méi)有公平進(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)度類(lèi)的pick_next_task選擇進(jìn)程。
對(duì)于公平調(diào)度類(lèi)，選擇下一個(gè)進(jìn)程主要過(guò)程如下：1）調(diào)用put_prev_task方法將前一個(gè)進(jìn)程重新加入cfs隊(duì)列的紅黑樹(shù)。2）調(diào)用pick_next_entity 選擇紅黑樹(shù)最左邊的進(jìn)程作為下一個(gè)進(jìn)程。3）將下一個(gè)進(jìn)程從紅黑樹(shù)中刪除，cfs隊(duì)列的curr指向進(jìn)程的調(diào)度實(shí)體。
通用的調(diào)度類(lèi)選擇順序?yàn)椋?br>
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)到來(lái)時(shí)就會(huì)調(diào)用主調(diào)度器選擇rt進(jìn)程作為next進(jìn)程。
做了以上的工作之后，紅黑樹(shù)中選擇下一個(gè)進(jìn)程的時(shí)候就不會(huì)再選擇到當(dāng)前cpu上運(yùn)行的進(jìn)程了，而當(dāng)前進(jìn)程調(diào)度實(shí)體又被cfs隊(duì)列的curr來(lái)記錄著（運(yùn)行隊(duì)列的curr也會(huì)記錄當(dāng)前進(jìn)程）。
下面給出公平調(diào)度類(lèi)選擇下一個(gè)進(jìn)程圖解（其中A為前一個(gè)進(jìn)程，即是當(dāng)前進(jìn)程，即為前一個(gè)進(jìn)程，B為下一個(gè)進(jìn)程）：
