深入理解Linux內核之主調度器（上）
本文轉載自微信公眾號「Linux內核遠航者」，作者Linux內核遠航者。轉載本文請聯(lián)系Linux內核遠航者公眾號。
1.開場白
環(huán)境：
- 處理器架構：arm64
- 內核源碼：linux-5.11
- ubuntu版本：20.04.1
- 代碼閱讀工具：vim+ctags+cscope
本文步進到Linux內核進程管理的核心部分，打開調度器的黑匣子，來看看Linux內核如何調度進程的。實際上，進程調度器主要做兩件事：選擇下一個進程，然后進行上下文切換。而何時調用主調度器調度進程那是調度時機所關注的問題，而調度時機在之前的內核搶占文章已經做了詳細講解，在此不在贅述，而本文關注的調度時機是真正調用主調度器的時機。
本文分析的內核源代碼主要集中在：
- kernel/sched/core.c
- kernel/sched/fair.c
2.調用時機
關于調度時機，網(wǎng)上的文章也五花八門，之前在內核搶占文章已經做了詳細講解，而在本文我們從源碼注釋中給出依據(jù)(再次強調一下：本文的調度時機關注的是何時調用主調度器，不是設置重新調度標志的時機，之前講解中我們知道他們都可以稱為調度時機)。
先來說一下什么是主調度器，其實和主調度器并列的還有一個叫做周期性調度器的東西(后面有機會會講解，主要用于時鐘中斷tick調來使奪取處理器的控制權)，他們都是內核中的一個函數(shù)，在合適的時機被調用。
主調度器函數(shù)如下：
- kernel/sched/core.c
- __schedule（）
內核的很多路徑會包裝這個函數(shù)，主要分為主動調度和搶占式調度場景。
內核源碼中主調度器函數(shù)也給出了調度時機的注釋，下面我們就以此為依據(jù)來看下：
- 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)
我們對注釋做出解釋，讓大家深刻理解調度時機(基本上是原樣翻譯，用顏色標注)。
1.顯式阻塞場景：包括互斥體、信號量、等待隊列等。
這個場景主要是為了等待某些資源而主動放棄處理器，來調用主調度器，如發(fā)現(xiàn)互斥體被其他內核路徑所持有，則睡眠等待互斥體被釋放的時候來喚醒我。
2.在中斷和用戶空間返回路徑上檢查TIF_NEED_RESCHED標志。例如，arch/x86/entry_64.S。為了在任務之間驅動搶占，調度程序在計時器中斷處理程序scheduler_tick()中設置標志。
解釋如下：這實際上是說重新調度標志(TIF_NEED_RESCHED)的設置和檢查的情形。
1)重新調度標志設置情形：如scheduler_tick周期性調度器按照特定條件設置、喚醒的路徑上按照特定條件設置等。當前這樣的場景并不會直接調用主調度器，而會在最近的調度點到來時調用主調度器。
2)重新調度標志檢查情形：是真正的調用主調度器，下面的場景都會涉及到，在此不在贅述。
3.喚醒并不會真正導致schedule()的進入。他們添加一個任務到運行隊列，僅此而已。
現(xiàn)在，如果添加到運行隊列中的新任務搶占了當前任務，那么喚醒設置TIF_NEED_RESCHED, schedule()在最近的可能情況下被調用:
1)如果內核是可搶占的(CONFIG_PREEMPTION=y)
-在系統(tǒng)調用或異常上下文中，最外層的preempt_enable()。(這可能和wake_up()的spin_unlock()一樣快!)
-在IRQ上下文中，從中斷處理程序返回到搶占上下文
注釋中很簡潔的幾句話，但其中的含義需要深刻去體會。
首先需要知道一點是：內核搶占說的是處于內核態(tài)的任務被其他任務所搶占的情況(無論是不是可搶占式內核，處于用戶態(tài)的任務都可以被搶占，處于內核態(tài)的任務是否能被搶占由是否開啟內核搶占來決定)，當然內核態(tài)的任務可以是內核線程也可以是通過系統(tǒng)調用請求內核服務的用戶任務。
情況1：這是重新開啟內核搶占的情況，即是搶占計數(shù)器為0時，檢查重新調度標志(TIF_NEED_RESCHED)，如果設置則調用主調度器，放棄處理器(這是搶占式調度)。
情況2：中斷返回內核態(tài)的時候，檢查重新調度標志(TIF_NEED_RESCHED)，如果設置且搶占計數(shù)器為0時則調用主調度器，放棄處理器(這是搶占式調度)。
注：關于內核搶占可以參考之前發(fā)布的文章。
2)如果內核是不可搶占的(CONFIG_PREEMPTION=y)
- cond_resched()調用
- 顯式的schedule()調用
- 從系統(tǒng)調用或異常返回到用戶空間
- 從中斷處理器返回到用戶空間
解釋如下：
cond_resched()是為了在不可搶占內核的一些耗時的內核處理路徑中增加主動搶占點(搶占計數(shù)器是否為0且當前任務被設置了重新調度標志)，則調用主調度器進行搶占式調度，所進行低延時處理。
顯式的schedule()調用，這是主動放棄處理器的場景，如一些睡眠場景，像用戶任務調用sleep。
系統(tǒng)調用或異常返回到用戶空間使會判斷當前進程是否設置重新調度標志(TIF_NEED_RESCHED)，如果設置則調用主調度器，放棄處理器。
中斷處理器返回到用戶空間會判斷當前進程是否設置重新調度標志(TIF_NEED_RESCHED)，如果設置則調用主調度器，放棄處理器。
其實還有一種場景也會調用到主調度器讓出處理器，那就是進程退出時，這里不在贅述。
下面給出總結：
1.主動調度：
- 睡眠場景，如sleep。
- 顯式阻塞場景，如互斥體，信號量，等待隊列，完成量等。
- 任務退出時，調用do_exit去釋放進程資源，最后會調用一次主調度器
2.搶占調度：
不可搶占式內核
- cond_resched()調用
- 顯式的schedule()調用
- 從系統(tǒng)調用或異常返回到用戶空間
- 從中斷處理器返回到用戶空間
可搶占式內核(增加一些搶占點)
- 重新開啟內核搶占
- 中斷返回內核態(tài)的時候
3.主調度器調用時機源碼窺探
下面給出主要的一些主調度器調用時機源碼分析，作為學習參考。
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.c false表示主動調度
異常返回用戶態(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.c false表示主動調度
顯式阻塞場景(舉例互斥體)：
- 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表示主動調度
3.2 支持內核搶占場景
中斷返回內核態(tài)場景
- arch/arm64/kernel/entry.S
- el1_irq
- #ifdef CONFIG_PREEMPTION
- ->arm64_preempt_schedule_irq
- ->preempt_schedule_irq();
- ->__schedule(true); //kernel/sched/core.c true表示搶占式調度
- #endif
內核搶占開啟場景
- preempt_enable
- ->if (unlikely(preempt_count_dec_and_test())) \ //搶占計數(shù)器減一 為0
- __preempt_schedule(); \
- ->preempt_schedule //kernel/sched/core.c
- -> __schedule(true) //調用主調度器進行搶占式調度
注：一般說異常/中斷返回，返回是處理器異常狀態(tài)，可能是用戶態(tài)也可能是內核態(tài)，但是會看到很多資料寫的都是用戶空間/內核空間并不準確，但是我們認為表達一個意思，做的心中有數(shù)即可。
3.3.選擇下一個進程
本節(jié)主要講解主調度器是如何選擇下一個進程的，這和調度策略強相關。
下面我們來看具體實現(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)化，當當前進程的調度類為公平調度類或者空閑調度類時，且cpu運行隊列的進程個數(shù)等于cfs運行隊列進程個數(shù)，說明運行隊列進程都是普通進程，則直接調用公平調度類的pick_next_task_fair選擇下一個進程(選擇紅黑樹最左邊的那個進程)，如果沒有找到說明當前進程調度類為空閑調度類，直接調用pick_next_task_idle選擇idle進程。
否則，遍歷調度類，從高優(yōu)先級調度類開始調用其pick_next_task方法選擇下一個進程。
下面以公平調度類為例來看如何選擇下一個進程的：調用過程如下(這里暫不考慮組調度情況)：
- 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;
這里會調用__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;
這里調用__dequeue_entity將下一個選擇的進程從cfs隊列的紅黑樹中刪除，然后將cfs隊列的curr指向進程的調度實體。
選擇下一個進程總結如下：
- 運行隊列中只有公平進程則選擇公平調度類的pick_next_task_fair選擇進程。
- 當前進程為idle進程，且沒有公平進程存在情況下，調用pick_next_task_idle選擇idle進程。
- 運行隊列存在除了公平進程的其他進程，則從高優(yōu)先級到低優(yōu)先級調用具體調度類的pick_next_task選擇進程。
- 對于公平調度類，選擇下一個進程主要過程如下：1)調用put_prev_task方法將前一個進程重新加入cfs隊列的紅黑樹。2)調用pick_next_entity 選擇紅黑樹最左邊的進程作為下一個進程。3)將下一個進程從紅黑樹中刪除，cfs隊列的curr指向進程的調度實體。
通用的調度類選擇順序為：
stop_sched_class -> dl_sched_class ->rt_sched_class -> fair_sched_class ->idle_sched_class
比如：當前運行隊列都是cfs的普通進程，某一時刻發(fā)生中斷喚醒了一個rt進程，那么在最近的調度點到來時就會調用主調度器選擇rt進程作為next進程。
做了以上的工作之后，紅黑樹中選擇下一個進程的時候就不會再選擇到當前cpu上運行的進程了，而當前進程調度實體又被cfs隊列的curr來記錄著(運行隊列的curr也會記錄當前進程)。
下面給出公平調度類選擇下一個進程圖解(其中A為前一個進程，即是當前進程，即為前一個進程，B為下一個進程)：
