|
作者:SAE團(tuán)隊 朱榮澤
【摘要】本文首先介紹非搶占式內(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ā)重新調(diào)度(何時設(shè)置可搶占條件)；搶占發(fā)生的時機(jī)(何時檢查可搶占的條件)；什么時候不能搶占內(nèi)核。最后分析了2.6kernel中如何支持搶占內(nèi)核。
【關(guān)鍵字】內(nèi)核態(tài)搶占 用戶態(tài)搶占 中斷 實時性 自旋鎖 linux
kernel schedule preemption reentrant
1.非搶占式和可搶占式內(nèi)核的區(qū)別
為了簡化問題，我使用嵌入式實時系統(tǒng)uC/OS作為例子。首先要指出的是，uC/OS只有內(nèi)核態(tài)，沒有用戶態(tài)，這和Linux不一樣。
多任務(wù)系統(tǒng)中，內(nèi)核負(fù)責(zé)管理各個任務(wù)，或者說為每個任務(wù)分配CPU時間，并且負(fù)責(zé)任務(wù)之間的通訊。內(nèi)核提供的基本服務(wù)是任務(wù)切換。調(diào)度（Scheduler）,英文還有一詞叫dispatcher，也是調(diào)度的意思。這是內(nèi)核的主要職責(zé)之一，就是要決定該輪到哪個任務(wù)運(yùn)行了。多數(shù)實時內(nèi)核是基于優(yōu)先級調(diào)度法的。每個任務(wù)根據(jù)其重要程度的不同被賦予一定的優(yōu)先級?；趦?yōu)先級的調(diào)度法指，CPU總是讓處在就緒態(tài)的優(yōu)先級最高的任務(wù)先運(yùn)行。然而，究竟何時讓高優(yōu)先級任務(wù)掌握CPU的使用權(quán)，有兩種不同的情況，這要看用的是什么類型的內(nèi)核，是不可剝奪型的還是可剝奪型內(nèi)核。
非搶占式內(nèi)核
非搶占式內(nèi)核是由任務(wù)主動放棄CPU的使用權(quán)。非搶占式調(diào)度法也稱作合作型多任務(wù)，各個任務(wù)彼此合作共享一個CPU。異步事件還是由中斷服務(wù)來處理。中斷服務(wù)可以使一個高優(yōu)先級的任務(wù)由掛起狀態(tài)變?yōu)榫途w狀態(tài)。但中斷服務(wù)以后控制權(quán)還是回到原來被中斷了的那個任務(wù)，直到該任務(wù)主動放棄CPU的使用權(quán)時，那個高優(yōu)先級的任務(wù)才能獲得CPU的使用權(quán)。非搶占式內(nèi)核如下圖所示。
非搶占式內(nèi)核的優(yōu)點(diǎn)有：
·中斷響應(yīng)快(與搶占式內(nèi)核比較)；
·允許使用不可重入函數(shù)；
·幾乎不需要使用信號量保護(hù)共享數(shù)據(jù)。運(yùn)行的任務(wù)占有CPU，不必?fù)?dān)心被別的任務(wù)搶占。這不是絕對的，在打印機(jī)的使用上，仍需要滿足互斥條件。
非搶占式內(nèi)核的缺點(diǎn)有：
·任務(wù)響應(yīng)時間慢。高優(yōu)先級的任務(wù)已經(jīng)進(jìn)入就緒態(tài)，但還不能運(yùn)行，要等到當(dāng)前運(yùn)行著的任務(wù)釋放CPU。
·非搶占式內(nèi)核的任務(wù)級響應(yīng)時間是不確定的，不知道什么時候最高優(yōu)先級的任務(wù)才能拿到CPU的控制權(quán)，完全取決于應(yīng)用程序什么時候釋放CPU。
搶占式內(nèi)核
使用搶占式內(nèi)核可以保證系統(tǒng)響應(yīng)時間。最高優(yōu)先級的任務(wù)一旦就緒，總能得到CPU的使用權(quán)。當(dāng)一個運(yùn)行著的任務(wù)使一個比它優(yōu)先級高的任務(wù)進(jìn)入了就緒態(tài)，當(dāng)前任務(wù)的CPU使用權(quán)就會被剝奪，或者說被掛起了，那個高優(yōu)先級的任務(wù)立刻得到了CPU的控制權(quán)。如果是中斷服務(wù)子程序使一個高優(yōu)先級的任務(wù)進(jìn)入就緒態(tài)，中斷完成時，中斷了的任務(wù)被掛起，優(yōu)先級高的那個任務(wù)開始運(yùn)行。搶占式內(nèi)核如下圖所示。
搶占式內(nèi)核的優(yōu)點(diǎn)有：
·使用搶占式內(nèi)核，最高優(yōu)先級的任務(wù)什么時候可以執(zhí)行，可以得到CPU的使用權(quán)是可知的。使用搶占式內(nèi)核使得任務(wù)級響應(yīng)時間得以最優(yōu)化。
搶占式內(nèi)核的缺點(diǎn)有：
·不能直接使用不可重入型函數(shù)。調(diào)用不可重入函數(shù)時，要滿足互斥條件，這點(diǎn)可以使用互斥型信號量來實現(xiàn)。如果調(diào)用不可重入型函數(shù)時，低優(yōu)先級的任務(wù)CPU的使用權(quán)被高優(yōu)先級任務(wù)剝奪，不可重入型函數(shù)中的數(shù)據(jù)有可能被破壞。
2.Linux下的用戶態(tài)搶占和內(nèi)核態(tài)搶占
Linux除了內(nèi)核態(tài)外還有用戶態(tài)。用戶程序的上下文屬于用戶態(tài)，系統(tǒng)調(diào)用和中斷處理例程上下文屬于內(nèi)核態(tài)。在2.6
kernel以前，Linux kernel只支持用戶態(tài)搶占。
2.1 用戶態(tài)搶占(User
Preemption)
在kernel返回用戶態(tài)(user-space)時，并且need_resched標(biāo)志為1時，scheduler被調(diào)用，這就是用戶態(tài)搶占。當(dāng)kernel返回用戶態(tài)時，系統(tǒng)可以安全的執(zhí)行當(dāng)前的任務(wù)，或者切換到另外一個任務(wù)。當(dāng)中斷處理例程或者系統(tǒng)調(diào)用完成后，kernel返回用戶態(tài)時，need_resched標(biāo)志的值會被檢查，假如它為1，調(diào)度器會選擇一個新的任務(wù)并執(zhí)行。中斷和系統(tǒng)調(diào)用的返回路徑(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)調(diào)用屬于kernel code)會一直運(yùn)行，直到code被完成或者被阻塞(系統(tǒng)調(diào)用可以被阻塞)。在 2.6
kernel里，Linux
kernel變成可搶占式。當(dāng)從中斷處理例程返回到內(nèi)核態(tài)(kernel-space)時，kernel會檢查是否可以搶占和是否需要重新調(diào)度。kernel可以在任何時間點(diǎn)上搶占一個任務(wù)(因為中斷可以發(fā)生在任何時間點(diǎn)上)，只要在這個時間點(diǎn)上kernel的狀態(tài)是安全的、可重新調(diào)度的。
3.內(nèi)核態(tài)搶占的設(shè)計
3.1 可搶占的條件
要滿足什么條件，kernel才可以搶占一個任務(wù)的內(nèi)核態(tài)呢？
·沒持有鎖。鎖是用于保護(hù)臨界區(qū)的，不能被搶占。
·Kernel
code可重入(reentrant)。因為kernel是SMP-safe的，所以滿足可重入性。
如何判斷當(dāng)前上下文(中斷處理例程、系統(tǒng)調(diào)用、內(nèi)核線程等)是沒持有鎖的？Linux在每個每個任務(wù)的thread_info結(jié)構(gòu)中增加了preempt_count變量作為preemption的計數(shù)器。這個變量初始為0，當(dāng)加鎖時計數(shù)器增一，當(dāng)解鎖時計數(shù)器減一。
3.2 內(nèi)核態(tài)需要搶占的觸發(fā)條件
內(nèi)核提供了一個need_resched標(biāo)志(這個標(biāo)志在任務(wù)結(jié)構(gòu)thread_info中)來表明是否需要重新執(zhí)行調(diào)度。
3.3 何時觸發(fā)重新調(diào)度
set_tsk_need_resched()：設(shè)置指定進(jìn)程中的need_resched標(biāo)志
clear_tsk
need_resched()：清除指定進(jìn)程中的need_resched標(biāo)志
need_resched()：檢查need_
resched標(biāo)志的值;如果被設(shè)置就返回真，否則返回假
什么時候需要重新調(diào)度：
·時鐘中斷處理例程檢查當(dāng)前任務(wù)的時間片，當(dāng)任務(wù)的時間片消耗完時，scheduler_tick()函數(shù)就會設(shè)置need_resched標(biāo)志；
·信號量、等到隊列、completion等機(jī)制喚醒時都是基于waitqueue的，而waitqueue的喚醒函數(shù)為default_wake_function，其調(diào)用try_to_wake_up將被喚醒的任務(wù)更改為就緒狀態(tài)并設(shè)置need_resched標(biāo)志。
·設(shè)置用戶進(jìn)程的nice值時，可能會使高優(yōu)先級的任務(wù)進(jìn)入就緒狀態(tài)；
·改變?nèi)蝿?wù)的優(yōu)先級時，可能會使高優(yōu)先級的任務(wù)進(jìn)入就緒狀態(tài)；
·新建一個任務(wù)時，可能會使高優(yōu)先級的任務(wù)進(jìn)入就緒狀態(tài)；
·對CPU(SMP)進(jìn)行負(fù)載均衡時，當(dāng)前任務(wù)可能需要放到另外一個CPU上運(yùn)行；
3.4 搶占發(fā)生的時機(jī)(何時檢查可搶占條件)
·當(dāng)一個中斷處理例程退出，在返回到內(nèi)核態(tài)時(kernel-space)。這是隱式的調(diào)用schedule()函數(shù)，當(dāng)前任務(wù)沒有主動放棄CPU使用權(quán)，而是被剝奪了CPU使用權(quán)。
·當(dāng)kernel
code從不可搶占狀態(tài)變?yōu)榭蓳屨紶顟B(tài)時(preemptible
again)。也就是preempt_count從正整數(shù)變?yōu)?時。這也是隱式的調(diào)用schedule()函數(shù)。
·一個任務(wù)在內(nèi)核態(tài)中顯式的調(diào)用schedule()函數(shù)。任務(wù)主動放棄CPU使用權(quán)。
·一個任務(wù)在內(nèi)核態(tài)中被阻塞，導(dǎo)致需要調(diào)用schedule()函數(shù)。任務(wù)主動放棄CPU使用權(quán)。
3.5 禁用/使能可搶占條件的操作
對preempt_count操作的函數(shù)有add_preempt_count()、sub_preempt_count()、inc_preempt_count()、dec_preempt_count()。
使能可搶占條件的操作是preempt_enable()，它調(diào)用dec_preempt_count()函數(shù)，然后再調(diào)用preempt_check_resched()函數(shù)去檢查是否需要重新調(diào)度。
禁用可搶占條件的操作是preempt_disable()，它調(diào)用inc_preempt_count()函數(shù)。
在內(nèi)核中有很多函數(shù)調(diào)用了preempt_enable()和preempt_disable()。比如spin_lock()函數(shù)調(diào)用了preempt_disable()函數(shù)，spin_unlock()函數(shù)調(diào)用了preempt_enable()函數(shù)。
3.6 什么時候不允許搶占
preempt_count()函數(shù)用于獲取preempt_count的值，preemptible()用于判斷內(nèi)核是否可搶占。
有幾種情況Linux內(nèi)核不應(yīng)該被搶占，除此之外，Linux內(nèi)核在任意一點(diǎn)都可被搶占。這幾種情況是：
·內(nèi)核正進(jìn)行中斷處理。在Linux內(nèi)核中進(jìn)程不能搶占中斷(中斷只能被其他中斷中止、搶占，進(jìn)程不能中止、搶占中斷)，在中斷例程中不允許進(jìn)行進(jìn)程調(diào)度。進(jìn)程調(diào)度函數(shù)schedule()會對此作出判斷，如果是在中斷中調(diào)用，會打印出錯信息。
·內(nèi)核正在進(jìn)行中斷上下文的Bottom
Half(中斷的下半部)處理。硬件中斷返回前會執(zhí)行軟中斷，此時仍然處于中斷上下文中。
·內(nèi)核的代碼段正持有spinlock自旋鎖、writelock/readlock讀寫鎖等鎖，處干這些鎖的保護(hù)狀態(tài)中。內(nèi)核中的這些鎖是為了在SMP系統(tǒng)中短時間內(nèi)保證不同CPU上運(yùn)行的進(jìn)程并發(fā)執(zhí)行的正確性。當(dāng)持有這些鎖時，內(nèi)核不應(yīng)該被搶占，否則由于搶占將導(dǎo)致其他CPU長期不能獲得鎖而死等。
·內(nèi)核正在執(zhí)行調(diào)度程序Scheduler。搶占的原因就是為了進(jìn)行新的調(diào)度，沒有理由將調(diào)度程序搶占掉再運(yùn)行調(diào)度程序。
·內(nèi)核正在對每個CPU“私有”的數(shù)據(jù)結(jié)構(gòu)操作(Per-CPU date
structures)。在SMP中，對于per-CPU數(shù)據(jù)結(jié)構(gòu)未用spinlocks保護(hù)，因為這些數(shù)據(jù)結(jié)構(gòu)隱含地被保護(hù)了(不同的CPU有不一樣的per-CPU數(shù)據(jù)，其他CPU上運(yùn)行的進(jìn)程不會用到另一個CPU的per-CPU數(shù)據(jù))。但是如果允許搶占，但一個進(jìn)程被搶占后重新調(diào)度，有可能調(diào)度到其他的CPU上去，這時定義的Per-CPU變量就會有問題，這時應(yīng)禁搶占。
4.Linux內(nèi)核態(tài)搶占的實現(xiàn)
4.1 數(shù)據(jù)結(jié)構(gòu)
在thread_info.h中
1.
struct thread_info {
2.
struct task_struct *task;
3.
struct exec_domain *exec_domain;
4.
__u32 flags;
5.
__u32 status;
6.
__u32 cpu;
7.
int preempt_count;
9.
mm_segment_t addr_limit;
10.
struct restart_block restart_block;
11.
void __user *sysenter_return;
12.
#ifdef CONFIG_X86_32
13.
unsigned long previous_esp;
16.
__u8 supervisor_stack[0];
17. #endif
18. };
4.2 代碼流程
禁用/使能可搶占條件的函數(shù)
1.
#if defined(CONFIG_DEBUG_PREEMPT) || defined(CONFIG_PREEMPT_TRACER)
2.
3.
extern void add_preempt_count(int val);
4.
5.
extern void sub_preempt_count(int val);
6.
7. #else
8.
9.
# define add_preempt_count(val) do { preempt_count() += (val); } while (0)
10.
11.
# define sub_preempt_count(val) do { preempt_count() -= (val); } while (0)
12.
13. #endif
14.
15.
#define inc_preempt_count() add_preempt_count(1)
16.
17.
#define dec_preempt_count() sub_preempt_count(1)
18.
19.
#define preempt_count() (current_thread_info()->preempt_count)
20.
21.
#define preempt_disable() \
22.
23.
do { \
24.
25.
inc_preempt_count(); \
26.
27.
barrier(); \
28.
29.
} while (0)
30.
31.
#define preempt_enable_no_resched() \
32.
33.
do { \
34.
35.
barrier(); \
36.
37.
dec_preempt_count(); \
38.
39.
} while (0)
40.
41.
#define preempt_check_resched() \
42.
43.
do { \
44.
45.
<pre name="code" class="cpp"> if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) \
46.
47.
<pre name="code" class="cpp"><pre name="code" class="cpp"> preempt_schedule(); \
48.
49.
} while (0)
50.
51.
#define preempt_enable() \
52.
53.
do { \
54.
55.
preempt_enable_no_resched(); \
56.
57.
barrier(); \
58.
59.
preempt_check_resched(); \
60.
61.
} while (0)
檢查可搶占條件
1.
# define preemptible() (preempt_count() == 0 && !irqs_disabled())
2.
自旋鎖的加鎖與解鎖
1.
void __lockfunc _spin_lock(spinlock_t *lock)
2. {
3.
preempt_disable();
4.
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
5.
LOCK_CONTENDED(lock, _raw_spin_trylock, _raw_spin_lock);
6. }
7.
8.
void __lockfunc _spin_unlock(spinlock_t *lock)
9. {
10.
spin_release(&lock->dep_map, 1, _RET_IP_);
11.
_raw_spin_unlock(lock);
12.
preempt_enable();
13. }
設(shè)置need_resched標(biāo)志的函數(shù)
1.
static inline void set_tsk_need_resched(struct task_struct *tsk)
2. {
3.
set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
4. }
5.
6.
static inline void clear_tsk_need_resched(struct task_struct *tsk)
7. {
8.
clear_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
9. }
10.
11.
static inline int test_tsk_need_resched(struct task_struct *tsk)
12. {
13.
return unlikely(test_tsk_thread_flag(tsk,TIF_NEED_RESCHED));
14. }
時鐘中斷時調(diào)用的task_tick()函數(shù)，當(dāng)時間片消耗完之后，設(shè)置need_resched標(biāo)志
1.
static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
2. {
3.
update_curr_rt(rq);
4.
5.
watchdog(rq, p);
6.
7.
11.
if (p->policy != SCHED_RR)
12.
return;
13.
14.
if (--p->rt.time_slice)
15.
return;
16.
17.
p->rt.time_slice = DEF_TIMESLICE;
18.
19.
23.
if (p->rt.run_list.prev != p->rt.run_list.next) {
24.
requeue_task_rt(rq, p, 0);
25.
set_tsk_need_resched(p);
26.
}
27. }
設(shè)置任務(wù)的need_resched標(biāo)志，并觸發(fā)任務(wù)所在CPU的調(diào)度器。
1.
static void resched_task(struct task_struct *p)
2. {
3.
int cpu;
4.
5.
assert_spin_locked(&task_rq(p)->lock);
6.
7.
if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
8.
return;
9.
10.
set_tsk_thread_flag(p, TIF_NEED_RESCHED);
11.
12.
cpu = task_cpu(p);
13.
if (cpu == smp_processor_id())
14.
return;
15.
16.
17.
smp_mb();
18.
if (!tsk_is_polling(p))
19.
smp_send_reschedule(cpu);
20. }
5.參考資料
http://blog.csdn.net/sailor_8318/archive/2008/09/03/2870184.aspx
《uC/OS-II源碼公開的嵌入式實時多任務(wù)操作系統(tǒng)內(nèi)核》
Linux 2.6.29內(nèi)核源碼
|
