深入理解Linux內(nèi)核之主調(diào)度器（上）
本文轉(zhuǎn)載自微信公眾號(hào)「Linux內(nèi)核遠(yuǎn)航者」，作者Linux內(nèi)核遠(yuǎn)航者。轉(zhuǎn)載本文請(qǐng)聯(lián)系Linux內(nèi)核遠(yuǎn)航者公眾號(hà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ī)，之前講解中我們知道他們都可以稱為調(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ī)的注釋，下面我們就以此為依據(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ì)注釋做出解釋，讓大家深刻理解調(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)喚醒我。
2.在中斷和用戶空間返回路徑上檢查T(mén)IF_NEED_RESCHED標(biāo)志。例如，arch/x86/entry_64.S。為了在任務(wù)之間驅(qū)動(dòng)搶占，調(diào)度程序在計(jì)時(shí)器中斷處理程序scheduler_tick()中設(shè)置標(biāo)志。
解釋如下：這實(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ì)。
首先需要知道一點(diǎn)是：內(nèi)核搶占說(shuō)的是處于內(nèi)核態(tài)的任務(wù)被其他任務(wù)所搶占的情況(無(wú)論是不是可搶占式內(nèi)核，處于用戶態(tài)的任務(wù)都可以被搶占，處于內(nèi)核態(tài)的任務(wù)是否能被搶占由是否開(kāi)啟內(nèi)核搶占來(lái)決定)，當(dāng)然內(nèi)核態(tài)的任務(wù)可以是內(nèi)核線程也可以是通過(guò)系統(tǒng)調(diào)用請(qǐng)求內(nèi)核服務(wù)的用戶任務(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)用或異常返回到用戶空間
- 從中斷處理器返回到用戶空間
解釋如下：
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))
- 重新開(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)景
中斷返回用戶態(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)度
異常返回用戶態(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)，可能是用戶態(tài)也可能是內(nèi)核態(tài)，但是會(huì)看到很多資料寫(xiě)的都是用戶空間/內(nèi)核空間并不準(zhǔn)確，但是我們認(rèn)為表達(dá)一個(gè)意思，做的心中有數(shù)即可。
3.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)度類為公平調(diào)度類或者空閑調(diào)度類時(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)度類的pick_next_task_fair選擇下一個(gè)進(jìn)程(選擇紅黑樹(shù)最左邊的那個(gè)進(jìn)程)，如果沒(méi)有找到說(shuō)明當(dāng)前進(jìn)程調(diào)度類為空閑調(diào)度類，直接調(diào)用pick_next_task_idle選擇idle進(jìn)程。
否則，遍歷調(diào)度類，從高優(yōu)先級(jí)調(diào)度類開(kāi)始調(diào)用其pick_next_task方法選擇下一個(gè)進(jìn)程。
下面以公平調(diào)度類為例來(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)度類的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)度類的pick_next_task選擇進(jìn)程。
- 對(duì)于公平調(diào)度類，選擇下一個(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)度類選擇順序?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)到來(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)度類選擇下一個(gè)進(jìn)程圖解(其中A為前一個(gè)進(jìn)程，即是當(dāng)前進(jìn)程，即為前一個(gè)進(jìn)程，B為下一個(gè)進(jìn)程)：
