深入理解Linux內核之內核搶占
本文轉載自微信公眾號「Linux內核遠航者」，作者Linux內核遠航者。轉載本文請聯系Linux內核遠航者公眾號。
1.開場白
環境：
處理器架構：arm64
內核源碼：linux-5.11
ubuntu版本：20.04.1
代碼閱讀工具：vim+ctags+cscope
我們或許經常聽說過內核搶占，可是我們是否真正理解它呢?內核搶占和搶占式內核究竟有什么關系呢?搶占計數器究竟干什么用?... 本文我們就來好好討論下，關于內核搶占的一些技術細節，力求讓大家理解內核搶占。
注：本文主要關注CFS調度類。
2.內核搶占和搶占式內核
我們經常使用uname -a命令能看到“PREEMPT”的字樣，沒錯，我們使用的是搶占式內核。
- # uname -a
- Linux (none) 5.11.0-g08a3831f3ae1 #1 SMP PREEMPT Fri Apr 30 17:41:53 CST 2021 aarch64 GNU/Linux
那什么是搶占式內核呢? 實際上，支持內核搶占的內核叫做搶占式內核，不支持內核搶占的內核叫做不可搶占式內核。那么問題又來了，什么是內核搶占呢?我們都知道，拿周期性的tick來說：對于用戶任務，當每個時鐘中斷到來后都會檢查它的實際運行時間是否超過理想運行時間，或者運行隊列中有沒有優先級更高的進程，一般如果滿足其中一個條件就會設置重新調度標志，然后在中斷返回用戶態的前夕發生調度，這是所謂的用戶任務搶占。
但是如果處于一個內核態的任務正在運行，這個時候發生中斷喚醒了一個高優先級的任務，那么這個被喚醒的任務能否被調度執行呢?這個時候就會分兩種情況分析，如果是搶占式內核那么高優先級任務就有可能搶占當前任務而調度執行(之所有是有可能是因為兩者虛擬運行時間差值要大于搶占粒度才允許搶占)，如果是不可搶占式內核那么不允許搶占，除非當前進程執行完或者主動發生調度高優先級進程該有機會被調度。
也就是說，支持內核搶占的內核不僅允許在用戶態的任務可以被搶占，處在內核態的任務也允許被搶占(請注意這里說的是內核態，因為用戶空間任務可以通過系統調用等進入內核態)，這樣對于交互性或者低延遲的應用場景很友好，如手持設備和桌面應用，響應會很快。而對于服務器來說，它就對吞吐量要求較高，希望獲得更多的cpu時間，而交互性或者低延遲都是次要的，所以被設計成不可搶占式內核。
下圖給出非搶占式內核調度情況：
下圖給出搶占式內核調度情況：
對比兩個圖可以發現：采用搶占式內核調度的情況下，在中斷中喚醒一個高優先級任務能夠得到很好的響應。
關于搶占式內核還是不可搶占式內核的選擇在源碼的kernel/Kconfig.preempt有所描述：
- config PREEMPT_NONE
- bool "No Forced Preemption (Server)"
- help
- ¦ This is the traditional Linux preemption model, geared towards
- ¦ throughput. It will still provide good latencies most of the
- ¦ time, but there are no guarantees and occasional longer delays
- ¦ are possible.
- ¦ Select this option if you are building a kernel for a server or
- ¦ scientific/computation system, or if you want to maximize the
- ¦ raw processing power of the kernel, irrespective of scheduling
- ¦ latencies.
- config PREEMPT
- bool "Preemptible Kernel (Low-Latency Desktop)"
- depends on !ARCH_NO_PREEMPT
- select PREEMPTION
- select UNINLINE_SPIN_UNLOCK if !ARCH_INLINE_SPIN_UNLOCK
- select PREEMPT_DYNAMIC if HAVE_PREEMPT_DYNAMIC
- help
- ¦ This option reduces the latency of the kernel by making
- ¦ all kernel code (that is not executing in a critical section)
- ¦ preemptible. This allows reaction to interactive events by
- ¦ permitting a low priority process to be preempted involuntarily
- ¦ even if it is in kernel mode executing a system call and would
- ¦ otherwise not be about to reach a natural preemption point.
- ¦ This allows applications to run more 'smoothly' even when the
- ¦ system is under load, at the cost of slightly lower throughput
- ¦ and a slight runtime overhead to kernel code.
- ¦ Select this if you are building a kernel for a desktop or
- ¦ embedded system with latency requirements in the milliseconds
- ¦ range.
上面列舉了兩個編譯選項一個是支持內核搶占一個是不支持內核搶占，其實還有PREEMPT_VOLUNTARY和PREEMPT_RT，前者會顯式增加一些搶占點，后者用于支持實時性 。
3.重新調度標志和搶占計數器
內核有些路徑是不允許調度的，如原子上下文，那么這個時候如果喚醒一個高優先級的任務或者tick的時候檢查可重新調度條件滿足，那么高優先級的任務將不能馬上得到執行，但是我又要標識一下需要重新調度，那么就需要設置重新調度標志，當返回到可調度上下文的時候(如開搶占)，這個時候就會檢查是否設置了這個標志來決定是否調用調度器來選擇下一個任務來運行。
標識重新調度是設置：
- //當前任務的task_struct的thread_info的flag
- stsk->thread_info->flags設置TIF_NEED_RESCHED標志
- #define TIF_NEED_RESCHED 1 /* rescheduling necessary */
內核的某些路徑上設置了這個標志之后，將在最近的調度點發生調度(可能是最近開啟搶占的時候，也可能是最近中斷異常返回的時候)。
當前任務被設置了重新調度標志，只是表明不久的將來會發生調度，并不是馬上發生調度，對于用戶任務來說就是中斷異常返回用戶態的前夕發生調度，而對于處于內核態的任務來說，想要在內核態搶占當前進程，僅僅置位重新調度標志還不行，還需要判斷當前進程的搶占計數器是否為0。
所有對于處于內核態的任務來說，搶占計數器對于重新調度至關重要，只要搶占計數器不為0，無論被喚醒的任務在緊急都不能獲得調度器，我們來看看這個搶占計數器：
- tsk->thread_info->preempt.count
我們來看下對于arm64架構，搶占計數器的定義：
- 24 struct thread_info {
- 25 unsigned long flags; /* low level flags */
- 29 union {
- 30 u64 preempt_count; /* 0 => preemptible, <0 => bug */
- 31 struct {
- 32 #ifdef CONFIG_CPU_BIG_ENDIAN
- 33 u32 need_resched;
- 34 u32 count;
- 35 #else
- 36 u32 count;
- 37 u32 need_resched;
- 38 #endif
- 39 } preempt;
- 40 };
- 45 };
可以發現它是一個共用體，內核某些路徑使用preempt_count，有的是preempt，為何會使用這么奇怪的定義呢?因為一個成員可以表示兩種狀態：重新調度標志和搶占計數器的數值
當需要重新調度的時候會置位flags的TIF_NEED_RESCHED標志，與此同時會將preempt.need_resched清零。當檢查thread_info 的preempt_count==0成立時，說明搶占計數器的數值為0且flags的TIF_NEED_RESCHED標志被置位，這個時候可以進程重新調度(如中斷返回內核態前夕的檢查)。
下面看下如何設置重新調度標志：
- resched_curr //kernel/sched/core.c
- 613 if (cpu == smp_processor_id()) {
- 614 set_tsk_need_resched(curr);
- 615 set_preempt_need_resched();
- 616 return;
- 617 }
- 29 static inline void set_preempt_need_resched(void) //arch/arm64/include/asm/preempt.h
- 30 {
- 31 current_thread_info()->preempt.need_resched = 0;
- 32 }
當內核的某個路徑設置重新調度標志(如時鐘中斷tick時)，會調用到resched_curr 來設置重新調度標志：可以看到除了設置任務的flags的TIF_NEED_RESCHED標志外，還設置了preempt.need_resched為0。
如何清除重新調度標志：
- kernel/sched/core.c
- __schedule //主動調度或搶占式調度 都會調用到這
- 5046 clear_tsk_need_resched(prev);
- 5047 clear_preempt_need_resched();
- //arch/arm64/include/asm/preempt.h
- 34 static inline void clear_preempt_need_resched(void)
- 35 {
- 36 current_thread_info()->preempt.need_resched = 1;
- 37 }
可以看到在主調度器中，除了調用clear_tsk_need_resched來清除任務的flags的TIF_NEED_RESCHED標志外，會調用clear_preempt_need_resched來設置preempt.need_resched為1, 來清除重新調度。
下面為搶占計數器的各個域的表示：
0-7 表示搶占計數 ，8-15表示軟中斷計數， 16-19表示硬中斷計數，20-23表示不可屏蔽中斷計數。當進入不同的上下文時會設置響應的位域，表示在某個上下文中，當某個位域被設置，搶占計數器不為0，任務在內核態就不容許被搶占。
所以，搶占計數器有兩個作用：一個是標識內核路徑在某個原子上下文，一個是用來判斷是否允許任務在內核態被搶占。
- include/linux/preempt.h
- 85 /*
- 86 * Macros to retrieve the current execution context:
- 87 *
- 88 * in_nmi() - We're in NMI context
- 89 * in_hardirq() - We're in hard IRQ context
- 90 * in_serving_softirq() - We're in softirq context
- 91 * in_task() - We're in task context
- 92 */
- 93 #define in_nmi() (nmi_count()) //判斷是否在 不可屏蔽中斷上下文
- 94 #define in_hardirq() (hardirq_count()) //判斷是否在硬中斷上下文
- 95 #define in_serving_softirq() (softirq_count() & SOFTIRQ_OFFSET) //判斷是否在軟中斷上下文
- 96 #define in_task() (!(in_nmi() | in_hardirq() | in_serving_softirq())) //判斷是否在進程上下文
- 97
- 98 /*
- 99 * The following macros are deprecated and should not be used in new code:
- 100 * in_irq() - Obsolete version of in_hardirq()
- 101 * in_softirq() - We have BH disabled, or are processing softirqs
- 102 * in_interrupt() - We're in NMI,IRQ,SoftIRQ context or have BH disabled
- 103 */
- 104 #define in_irq() (hardirq_count()) //判斷是否在硬中斷上下文
- 105 #define in_softirq() (softirq_count()) //判斷是否在軟中斷上下文（關閉軟中斷或者在執行軟中斷）
- 106 #define in_interrupt() (irq_count()) //判斷是否在中斷上下文（包括硬中斷 軟中斷和不可屏蔽中斷）
- //判斷是否在原子上下文（搶占計數器不為0）
- 144 #define in_atomic() (preempt_count() != 0)
4.內核搶占的調度時機
這里調度時機我將它細分為兩種情況，一種是不進行調度的cheek點，一種是真正的搶占點(即是調用主調度器進行調度)：
cheek點->
tick的時候 : 滿足條件(任務使用完理想運行時間，運行時間大于最小搶占粒度且運行隊列有優先級更高的任務) 時，設置TIF_NEED_RESCHED標志,最近的搶占點發生調度 。
喚醒搶占 : 滿足條件(喚醒的任務與當前任務的虛擬運行時間差值大于最小喚醒搶占粒度 ，喚醒的任務虛擬運行時間更小) 時， 設置TIF_NEED_RESCHED標志，最近的搶占點發生調度。
搶占點->
中斷返回內核態 : 滿足條件(重新調度標志置位且搶占計數器為0) 時， 搶占式調度 。
打開搶占的時候 : (如開搶占，開中斷下半部，釋放自旋鎖) 滿足條件(重新調度標志置位且搶占計數器為0)時， 搶占式調度。
開啟軟中斷的時候 ： 滿足條件(重新調度標志置位且搶占計數器為0)時， 搶占式調度。
中斷返回內核態是常規的搶占點，一般情況下即使沒有其他中斷產生，周期性的tick中斷也會發生， 滿足條件(重新調度標志置位且搶占計數器為0)時，當前任務就會被搶占。而在一些會發生多任務竟態的臨界區中，我們需要關閉內核搶占，有的直接調用preempt_disable, 有的是間接調用preempt_disable(如申請自旋鎖的臨界區), 有的則是關閉軟中斷等，這些都會導致搶占計數器不為0，但是在這些臨界區中如果中斷喚醒了高優先級的任務，中斷返回內核態的前夕是不能進行調度的，所以在這些臨界區結束的時候會檢查調度條件是否滿足，如果滿足進行搶占式調度，從而使得被喚醒的任務被及時的響應。一般，一些cheek點設置了當前任務的重新調度標志之后，如果搶占計數器為0，會在最近的搶占點發生調度(就是上面所說的三種情況)。還有需要注意的是：關搶占的臨界區中，只是禁止了當前任務所在cpu的內核搶占，其他cpu依然可以進行內核搶占，如果這段臨界區有可能被其他cpu訪問到，可以直接使用自旋鎖來保護。
4.1 cheek點
1) 時鐘中斷tick時：
- kernel/sched/core.c
- scheduler_tick
- ->curr->sched_class->task_tick(rq, curr, 0)
- ->task_tick_fair
- ->entity_tick
- ->check_preempt_tick
- ->4374 if (delta_exec > ideal_runtime) { //1.當前任務的實際運行時間大于理想運行時間
- 4375 resched_curr(rq_of(cfs_rq)); //設置重新調度標志
- 4389 if (delta_exec < sysctl_sched_min_granularity) //當前任務的實際運行時間 小于 最小調度粒度嗎？
- 4390 return;
- 4398 if (delta > ideal_runtime) //2.紅黑樹最左邊的任務的虛擬運行時間和當前任務的虛擬運行時間的差值小于 理想運行時間
- 4399 resched_curr(rq_of(cfs_rq)); //設置重新調度標志
每個時鐘tick到來時，會調用scheduler_tick來檢查是否需要重新調度，以下兩個條件有一個發生都會設置重新調度標志：
1.當前任務的實際運行時間大于理想運行時間(保證任務在一個調度周期內運行時間不會超過理想運行時間，防止“流氓”任務一直霸占cpu，通過周期性的時鐘中斷奪回處理器的使用權)。
2.當前任務的實際運行時間大于最小調度粒度，且紅黑樹最左邊的任務的虛擬運行時間和當前任務的虛擬運行時間的差值小于理想運行時間(紅黑樹中的高優先級的任務可以搶占當前任務)。
2)喚醒搶占：
在fork和正常的喚醒路徑上：
fork路徑:
- kernel/fork.c
- kernel_clone
- ->wake_up_new_task(p)
- ->check_preempt_curr(rq, p, WF_FORK)
- ->rq->curr->sched_class->check_preempt_curr(rq, p, flags)
- ->check_preempt_wakeup //kernel/sched/fair.c
- -> 6994 if (wakeup_preempt_entity(se, pse) == 1) { //喚醒的任務的虛擬運行時間和當前任務的虛擬運行時間差值小于最新喚醒搶占粒度轉換的虛擬運行時間
- 6995 /*
- 6996 ¦* Bias pick_next to pick the sched entity that is
- 6997 ¦* triggering this preemption.
- 6998 ¦*/
- 6999 if (!next_buddy_marked)
- 7000 set_next_buddy(pse);
- 7001 goto preempt;
- 7002 }
- 7003
- 7004 return;
- 7005
- 7006 preempt:
- 7007 resched_curr(rq); //設置重新調度標志
正常喚醒路徑：
- kernel/sched/core.c
- wake_up_process
- ->try_to_wake_up
- ->ttwu_queue
- ->ttwu_do_activate
- ->ttwu_do_wakeup
- ->check_preempt_curr(rq, p, wake_flags)
無論是創建新任務或者是喚醒任務的時候，都有可能新喚醒的任務搶占當前任務，判斷條件如下：喚醒的任務的虛擬運行時間和當前任務的虛擬運行時間差值小于最小喚醒搶占粒度轉換的虛擬運行時間(喚醒的任務的虛擬運行時間更小)。
4.2 搶占點
上面介紹的都是cheek點，只是設置重新調度標志，并沒有讓搶占的任務運行，真正的搶占點是調用主調度器的時候。
1)中斷返回內核態
當開啟內核搶占的時候，在中斷返回內核態的前夕，會檢查當前任務是否設置了重新調度標志且搶占計數器為0，如果都滿足，進行搶占式調度。
- arch/arm64/kernel/entry.S
- el1_irq
- -> 671 #ifdef CONFIG_PREEMPTION
- 672 ldr x24, [tsk, #TSK_TI_PREEMPT] // get preempt count
- 673 alternative_if ARM64_HAS_IRQ_PRIO_MASKING
- 674 /*
- 675 ¦* DA_F were cleared at start of handling. If anything is set in DAIF,
- 676 ¦* we come back from an NMI, so skip preemption
- 677 ¦*/
- 678 mrs x0, daif
- 679 orr x24, x24, x0
- 680 alternative_else_nop_endif
- 681 cbnz x24, 1f // preempt count != 0 || NMI return path
- 682 bl arm64_preempt_schedule_irq // irq en/disable is done inside
- 683 1:
- 684 #endif
當發生中斷時，會執行el1_irq來處理中斷，
672行 來讀取當前任務的thread_info.preempt_count 681行 判斷thread_info.preempt_count是否為0，如果為0 則調用682 行的arm64_preempt_schedule_irq 進行搶占式調度(上一節已經分析過)。
下面看下搶占式調度：
- arm64_preempt_schedule_irq
- ->preempt_schedule_irq
- ->__schedule(true) //調用主調度器進行搶占式調度
2)打開搶占的時候
開啟搶占：
- preempt_enable
- ->if (unlikely(preempt_count_dec_and_test())) \ //搶占計數器減一 為0
- __preempt_schedule(); \
- ->preempt_schedule //kernel/sched/core.c
- -> __schedule(true) //調用主調度器進行搶占式調度
釋放自旋鎖：
- spin_unlock
- ->raw_spin_unlock
- ->__raw_spin_unlock
- ->preempt_enable //如上
3) 開啟軟中斷
- local_bh_enable
- ->__local_bh_enable_ip
- ->preempt_check_resched
- ->if (should_resched(0)) \
- __preempt_schedule();
- ->preempt_schedule
- -> __schedule(true) //調用主調度器進行搶占式調度
其實，無論是主動進行調度還是搶占式調度都會調用__schedule，而__schedule是屬于關搶占上下文，在調度期間不允許被搶占。
5.不可搶占內核的低延遲處理
下面我們來看下在沒有開啟內核搶占的內核中如何處理低延遲：
我們會看到在一些比較耗時的處理中如文件系統和內存回收的一些路徑會調用cond_resched，它是干什么用呢：
下面是使用這個宏的例子：在內存回收路徑中，會從不活躍的lru鏈表尾部取出一些頁面回收隔離到page_list中，最終會調用到shrink_page_list：
- mm/vmscan.c
- shrink_page_list
- ->
- 1084 while (!list_empty(page_list)) {
- ...
- 1091 cond_resched();
- ... //回收處理
- }
可以看到對于page_list中的每一個被隔離的候選回收頁，在處理之前都會調用到cond_resched來主動判斷是否需要重新調度。
下面我們來看下cond_resched這個宏實現：
- include/linux/sched.h
- 1868 /*
- 1869 * cond_resched() and cond_resched_lock(): latency reduction via
- 1870 * explicit rescheduling in places that are safe. The return
- 1871 * value indicates whether a reschedule was done in fact.
- 1872 * cond_resched_lock() will drop the spinlock before scheduling,
- 1873 */
- 1874 #ifndef CONFIG_PREEMPTION
- 1875 extern int _cond_resched(void);
- 1876 #else
- 1877 static inline int _cond_resched(void) { return 0; }
- 1878 #endif
- 1879
- 1880 #define cond_resched() ({ \
- 1881 ___might_sleep(__FILE__, __LINE__, 0); \
- 1882 _cond_resched(); \
- 1883 })
我們可以很清楚的看到，搶占式內核中(CONFIG_PREEMPTION=y)cond_resched宏的_cond_resched為空，并沒有主動判斷重新調度的功能，只有非搶占式內核才會調用_cond_resched來執行主動檢查可搶占性。
下面我們來看下_cond_resched：
- 6671 #ifndef CONFIG_PREEMPTION
- 6672 int __sched _cond_resched(void)
- 6673 {
- 6674 if (should_resched(0)) { //判斷搶占計數器是否為0
- 6675 preempt_schedule_common(); //進行搶占式調度
- 6676 return 1;
- 6677 }
- 6678 rcu_all_qs();
- 6679 return 0;
- 6680 }
- 6681 EXPORT_SYMBOL(_cond_resched);
- 6682 #endif
會主動檢查搶占計數器是否為0(實際上搶占計數器是否為0且當前任務被設置了重新調度標志)，則進行搶占式調度。
實際上，對于非搶占式內核來說，在內核的很多地方，特別是文件系統操作和內存管理相關的一些耗時路徑中，都已經被內核開發者識別出來，并使用cond_resched來減小延遲(感興趣的小伙伴可以通過grep和wc -l命令來查看一下)。
6.自愿內核搶占
內核搶占模型有一種叫做自愿內核搶占模型(CONFIG_PREEMPT_VOLUNTARY=y)，可以使得內核開發者在進行耗時操作的時候，主動檢查是否需要發生搶占式調度，這個和上一節差不多。
- config PREEMPT_VOLUNTARY
- bool "Voluntary Kernel Preemption (Desktop)"
- depends on !ARCH_NO_PREEMPT
- help
- ¦ This option reduces the latency of the kernel by adding more
- ¦ "explicit preemption points" to the kernel code. These new
- ¦ preemption points have been selected to reduce the maximum
- ¦ latency of rescheduling, providing faster application reactions,
- ¦ at the cost of slightly lower throughput.
- ¦ This allows reaction to interactive events by allowing a
- ¦ low priority process to voluntarily preempt itself even if it
- ¦ is in kernel mode executing a system call. This allows
- ¦ applications to run more 'smoothly' even when the system is
- ¦ under load.
- ¦ Select this if you are building a kernel for a desktop system.
使用might_resched：
- 83 #ifdef CONFIG_PREEMPT_VOLUNTARY
- 84 extern int _cond_resched(void);
- 85 # define might_resched() _cond_resched()
- 86 #else
- 87 # define might_resched() do { } while (0)
- 88 #endif
發現只有CONFIG_PREEMPT_VOLUNTARY=y時，might_resched才有效，否則為空。
可以驚奇的發現，當搜索might_resched在內核中使用的使用的時候，并沒有看見有任何地方在使用，猜想是因為大多數耗時的內核路徑，都已經使用cond_resched來進行檢查是否具備調度時機。
7.總結
本文講解了內核搶占的方方面面，非搶占式內核主要用于服務器等對吞吐量要求較高的場景，而搶占式內核主要用于嵌入式設備和桌面等對響應要求較高的場景。內核搶占的調度時機主要從check點和搶占點兩個角度去分析：check點是在合適的時機(如時鐘中斷tick時或者任務喚醒的時候)判斷是否需要重新調度任務，如果需要設置重新調度標志(need_resched)，并沒有馬上進行調度，然后在最近的搶占點發生調度;而搶占點是真正調用主調度器發生調度的時機，一般會在中斷返回內核態或者重新開啟內核搶占等情況下發生。最后，我們又分析了非搶占式內核如何進行低延遲處理已經自愿搶占式內核如何實現自愿式搶占。
