Linux內(nèi)核態(tài)搶占機制分析
本文首先介紹非搶占式內(nèi)核(Non-Preemptive Kernel)和可搶占式內(nèi)核(Preemptive Kernel)的區(qū)別。接著分析Linux下有兩種搶占：用戶態(tài)搶占(User Preemption)、內(nèi)核態(tài)搶占(Kernel Preemption)。然后分析了在內(nèi)核態(tài)下：如何判斷能否搶占內(nèi)核(什么是可搶占的條件);何時觸發(fā)重新調度(何時設置可搶占條件);搶占發(fā)生的時機(何時檢查可搶占的條件);什么時候不能搶占內(nèi)核。***分析了2.6kernel中如何支持搶占內(nèi)核。
1. 非搶占式和可搶占式內(nèi)核的區(qū)別
為了簡化問題，我使用嵌入式實時系統(tǒng)uC/OS作為例子。首先要指出的是，uC/OS只有內(nèi)核態(tài)，沒有用戶態(tài)，這和Linux不一樣。
多任務系統(tǒng)中，內(nèi)核負責管理各個任務，或者說為每個任務分配CPU時間，并且負責任務之間的通訊。內(nèi)核提供的基本服務是任務切換。調度(Scheduler),英文還有一詞叫dispatcher，也是調度的意思。這是內(nèi)核的主要職責之一，就是要決定該輪到哪個任務運行了。多數(shù)實時內(nèi)核是基于優(yōu)先級調度法的。每個任務根據(jù)其重要程度的不同被賦予一定的優(yōu)先級?；趦?yōu)先級的調度法指，CPU總是讓處在就緒態(tài)的優(yōu)先級***的任務先運行。然而，究竟何時讓高優(yōu)先級任務掌握CPU的使用權，有兩種不同的情況，這要看用的是什么類型的內(nèi)核，是不可剝奪型的還是可剝奪型內(nèi)核。
非搶占式內(nèi)核
非搶占式內(nèi)核是由任務主動放棄CPU的使用權。非搶占式調度法也稱作合作型多任務，各個任務彼此合作共享一個CPU。異步事件還是由中斷服務來處理。中斷服務可以使一個高優(yōu)先級的任務由掛起狀態(tài)變?yōu)榫途w狀態(tài)。但中斷服務以后控制權還是回到原來被中斷了的那個任務，直到該任務主動放棄CPU的使用權時，那個高優(yōu)先級的任務才能獲得CPU的使用權。非搶占式內(nèi)核如下圖所示。
非搶占式內(nèi)核的優(yōu)點有：
- 中斷響應快(與搶占式內(nèi)核比較);
- 允許使用不可重入函數(shù);
- 幾乎不需要使用信號量保護共享數(shù)據(jù)。運行的任務占有CPU，不必擔心被別的任務搶占。這不是絕對的，在打印機的使用上，仍需要滿足互斥條件。
非搶占式內(nèi)核的缺點有：
- 任務響應時間慢。高優(yōu)先級的任務已經(jīng)進入就緒態(tài)，但還不能運行，要等到當前運行著的任務釋放CPU。
- 非搶占式內(nèi)核的任務級響應時間是不確定的，不知道什么時候***優(yōu)先級的任務才能拿到CPU的控制權，完全取決于應用程序什么時候釋放CPU。
搶占式內(nèi)核
使用搶占式內(nèi)核可以保證系統(tǒng)響應時間。***優(yōu)先級的任務一旦就緒，總能得到CPU的使用權。當一個運行著的任務使一個比它優(yōu)先級高的任務進入了就緒態(tài)，當前任務的CPU使用權就會被剝奪，或者說被掛起了，那個高優(yōu)先級的任務立刻得到了CPU的控制權。如果是中斷服務子程序使一個高優(yōu)先級的任務進入就緒態(tài)，中斷完成時，中斷了的任務被掛起，優(yōu)先級高的那個任務開始運行。搶占式內(nèi)核如下圖所示。
搶占式內(nèi)核的優(yōu)點有：
- 使用搶占式內(nèi)核，***優(yōu)先級的任務什么時候可以執(zhí)行，可以得到CPU的使用權是可知的。使用搶占式內(nèi)核使得任務級響應時間得以***化。
搶占式內(nèi)核的缺點有：
- 不能直接使用不可重入型函數(shù)。調用不可重入函數(shù)時，要滿足互斥條件，這點可以使用互斥型信號量來實現(xiàn)。如果調用不可重入型函數(shù)時，低優(yōu)先級的任務CPU的使用權被高優(yōu)先級任務剝奪，不可重入型函數(shù)中的數(shù)據(jù)有可能被破壞。
2. Linux下的用戶態(tài)搶占和內(nèi)核態(tài)搶占
Linux除了內(nèi)核態(tài)外還有用戶態(tài)。用戶程序的上下文屬于用戶態(tài)，系統(tǒng)調用和中斷處理例程上下文屬于內(nèi)核態(tài)。在2.6 kernel以前，Linux kernel只支持用戶態(tài)搶占。
2.1 用戶態(tài)搶占(User Preemption)
在kernel返回用戶態(tài)(user-space)時，并且need_resched標志為1時，scheduler被調用，這就是用戶態(tài)搶占。當kernel返回用戶態(tài)時，系統(tǒng)可以安全的執(zhí)行當前的任務，或者切換到另外一個任務。當中斷處理例程或者系統(tǒng)調用完成后，kernel返回用戶態(tài)時，need_resched標志的值會被檢查，假如它為1，調度器會選擇一個新的任務并執(zhí)行。
中斷和系統(tǒng)調用的返回路徑(return path)的實現(xiàn)在entry.S中(entry.S不僅包括kernel entry code，也包括kernel exit code)。
2.2 內(nèi)核態(tài)搶占(Kernel Preemption)
在2.6 kernel以前，kernel code(中斷和系統(tǒng)調用屬于kernel code)會一直運行，直到code被完成或者被阻塞(系統(tǒng)調用可以被阻塞)。在 2.6 kernel里，Linux kernel變成可搶占式。當從中斷處理例程返回到內(nèi)核態(tài)(kernel-space)時，kernel會檢查是否可以搶占和是否需要重新調度。kernel可以在任何時間點上搶占一個任務(因為中斷可以發(fā)生在任何時間點上)，只要在這個時間點上kernel的狀態(tài)是安全的、可重新調度的。
3. 內(nèi)核態(tài)搶占的設計
3.1 可搶占的條件
要滿足什么條件，kernel才可以搶占一個任務的內(nèi)核態(tài)呢?
- 沒持有鎖。鎖是用于保護臨界區(qū)的，不能被搶占。
- Kernel code可重入(reentrant)。因為kernel是SMP-safe的，所以滿足可重入性。
如何判斷當前上下文(中斷處理例程、系統(tǒng)調用、內(nèi)核線程等)是沒持有鎖的?Linux在每個每個任務的thread_info結構中增加了preempt_count變量作為preemption的計數(shù)器。這個變量初始為0，當加鎖時計數(shù)器增一，當解鎖時計數(shù)器減一。
3.2 內(nèi)核態(tài)需要搶占的觸發(fā)條件
內(nèi)核提供了一個need_resched標志(這個標志在任務結構thread_info中)來表明是否需要重新執(zhí)行調度。
3.3 何時觸發(fā)重新調度
set_tsk_need_resched()：設置指定進程中的need_resched標志
clear_tsk need_resched()：清除指定進程中的need_resched標志
need_resched()：檢查need_ resched標志的值;如果被設置就返回真，否則返回假
什么時候需要重新調度：
- 時鐘中斷處理例程檢查當前任務的時間片，當任務的時間片消耗完時，scheduler_tick()函數(shù)就會設置need_resched標志;
- 信號量、等到隊列、completion等機制喚醒時都是基于waitqueue的，而waitqueue的喚醒函數(shù)為default_wake_function，其調用try_to_wake_up將被喚醒的任務更改為就緒狀態(tài)并設置need_resched標志。
- 設置用戶進程的nice值時，可能會使高優(yōu)先級的任務進入就緒狀態(tài);
- 改變?nèi)蝿盏膬?yōu)先級時，可能會使高優(yōu)先級的任務進入就緒狀態(tài);
- 新建一個任務時，可能會使高優(yōu)先級的任務進入就緒狀態(tài);
- 對CPU(SMP)進行負載均衡時，當前任務可能需要放到另外一個CPU上運行;
3.4 搶占發(fā)生的時機(何時檢查可搶占條件)
- 當一個中斷處理例程退出，在返回到內(nèi)核態(tài)時(kernel-space)。這是隱式的調用schedule()函數(shù)，當前任務沒有主動放棄CPU使用權，而是被剝奪了CPU使用權。
- 當kernel code從不可搶占狀態(tài)變?yōu)榭蓳屨紶顟B(tài)時(preemptible again)。也就是preempt_count從正整數(shù)變?yōu)?時。這也是隱式的調用schedule()函數(shù)。
- 一個任務在內(nèi)核態(tài)中顯式的調用schedule()函數(shù)。任務主動放棄CPU使用權。
- 一個任務在內(nèi)核態(tài)中被阻塞，導致需要調用schedule()函數(shù)。任務主動放棄CPU使用權。
3.5 禁用/使能可搶占條件的操作
對preempt_count操作的函數(shù)有add_preempt_count()、sub_preempt_count()、inc_preempt_count()、dec_preempt_count()。
使能可搶占條件的操作是preempt_enable()，它調用dec_preempt_count()函數(shù)，然后再調用preempt_check_resched()函數(shù)去檢查是否需要重新調度。
禁用可搶占條件的操作是preempt_disable()，它調用inc_preempt_count()函數(shù)。
在內(nèi)核中有很多函數(shù)調用了preempt_enable()和preempt_disable()。比如spin_lock()函數(shù)調用了preempt_disable()函數(shù)，spin_unlock()函數(shù)調用了preempt_enable()函數(shù)。
3.6 什么時候不允許搶占
preempt_count()函數(shù)用于獲取preempt_count的值，preemptible()用于判斷內(nèi)核是否可搶占。
有幾種情況Linux內(nèi)核不應該被搶占，除此之外，Linux內(nèi)核在任意一點都可被搶占。這幾種情況是：
- 內(nèi)核正進行中斷處理。在Linux內(nèi)核中進程不能搶占中斷(中斷只能被其他中斷中止、搶占，進程不能中止、搶占中斷)，在中斷例程中不允許進行進程調度。進程調度函數(shù)schedule()會對此作出判斷，如果是在中斷中調用，會打印出錯信息。
- 內(nèi)核正在進行中斷上下文的Bottom Half(中斷的下半部)處理。硬件中斷返回前會執(zhí)行軟中斷，此時仍然處于中斷上下文中。
- 內(nèi)核的代碼段正持有spinlock自旋鎖、writelock/readlock讀寫鎖等鎖，處干這些鎖的保護狀態(tài)中。內(nèi)核中的這些鎖是為了在SMP系統(tǒng)中短時間內(nèi)保證不同CPU上運行的進程并發(fā)執(zhí)行的正確性。當持有這些鎖時，內(nèi)核不應該被搶占，否則由于搶占將導致其他CPU長期不能獲得鎖而死等。
- 內(nèi)核正在執(zhí)行調度程序Scheduler。搶占的原因就是為了進行新的調度，沒有理由將調度程序搶占掉再運行調度程序。
- 內(nèi)核正在對每個CPU“私有”的數(shù)據(jù)結構操作(Per-CPU date structures)。在SMP中，對于per-CPU數(shù)據(jù)結構未用spinlocks保護，因為這些數(shù)據(jù)結構隱含地被保護了(不同的CPU有不一樣的per-CPU數(shù)據(jù)，其他CPU上運行的進程不會用到另一個CPU的per-CPU數(shù)據(jù))。但是如果允許搶占，但一個進程被搶占后重新調度，有可能調度到其他的CPU上去，這時定義的Per-CPU變量就會有問題，這時應禁搶占。
4. Linux內(nèi)核態(tài)搶占的實現(xiàn)
4.1 數(shù)據(jù)結構
[cpp] view plain copy
- struct thread_info {
- struct task_struct *task; /* main task structure */
- struct exec_domain *exec_domain; /* execution domain */
- /**
- * 如果有TIF_NEED_RESCHED標志，則必須調用調度程序。
- */
- unsigned long flags; /* low level flags */
- /**
- * 線程標志:
- * TS_USEDFPU:表示進程在當前執(zhí)行過程中，是否使用過FPU、MMX和XMM寄存器。
- */
- unsigned long status; /* thread-synchronous flags */
- /**
- * 可運行進程所在運行隊列的CPU邏輯號。
- */
- __u32 cpu; /* current CPU */
- __s32 preempt_count; /* 0 => preemptable, <0 => BUG */
- mm_segment_t addr_limit; /* thread address space:
- 0-0xBFFFFFFF for user-thead
- 0-0xFFFFFFFF for kernel-thread
- */
- struct restart_block restart_block;
- unsigned long previous_esp; /* ESP of the previous stack in case
- of nested (IRQ) stacks
- */
- __u8 supervisor_stack[0];
- };
4.2 代碼流程
禁用/使能可搶占條件的函數(shù)
[cpp] view plain copy
- #ifdef CONFIG_DEBUG_PREEMPT
- extern void fastcall add_preempt_count(int val);
- extern void fastcall sub_preempt_count(int val);
- #else
- # define add_preempt_count(val) do { preempt_count() += (val); } while (0)
- # define sub_preempt_count(val) do { preempt_count() -= (val); } while (0)
- #endif
- #define inc_preempt_count() add_preempt_count(1)
- #define dec_preempt_count() sub_preempt_count(1)
- /**
- * 在thread_info描述符中選擇preempt_count字段
- */
- #define preempt_count() (current_thread_info()->preempt_count)
- #ifdef CONFIG_PREEMPT
- asmlinkage void preempt_schedule(void);
- /**
- * 使搶占計數(shù)加1
- */
- #define preempt_disable() \
- do { \
- inc_preempt_count(); \
- barrier(); \
- } while (0)
- /**
- * 使搶占計數(shù)減1
- */
- #define preempt_enable_no_resched() \
- do { \
- barrier(); \
- dec_preempt_count(); \
- } while (0)
- #define preempt_check_resched() \
- do { \
- if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) \
- preempt_schedule(); \
- } while (0)
- /**
- * 使搶占計數(shù)減1，并在thread_info描述符的TIF_NEED_RESCHED標志被置為1的情況下，調用preempt_schedule()
- */
- #define preempt_enable() \
- do { \
- preempt_enable_no_resched(); \
- preempt_check_resched(); \
- } while (0)
- #else
- #define preempt_disable() do { } while (0)
- #define preempt_enable_no_resched() do { } while (0)
- #define preempt_enable() do { } while (0)
- #define preempt_check_resched() do { } while (0)
- #endif
設置need_resched標志的函數(shù)
[cpp] view plain copy
- static inline void set_tsk_need_resched(struct task_struct *tsk)
- {
- set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
- }
- static inline void clear_tsk_need_resched(struct task_struct *tsk)
- {
- clear_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
- }
