前面我們了解了linux進程調度器的設計思路和注意框架
周期調度器scheduler_tick通過linux定時器周期性的被激活, 進行程序調度
進程主動放棄CPU或者發生阻塞時, 則會調用主調度器schedule進行程序調度
在分析的過程中, 我們提到了內核搶占和用戶搶占的概念, 但是並沒有詳細講, 因此我們在這裡詳細分析一下子
CPU搶占分兩種情況, 用戶搶占, 內核搶占
其中內核搶占是在Linux2.5.4版本發布時加入, 同SMP(Symmetrical Multi-Processing, 對稱多處理器), 作為內核的可選配置。
1 前景回顧
1.1 Linux的調度器組成
2個調度器
可以用兩種方法來激活調度
一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要
因此當前linux的調度程序由兩個調度器組成：主調度器，周期性調度器(兩者又統稱為通用調度器(generic scheduler)或核心調度器(core scheduler))
並且每個調度器包括兩個內容：調度框架(其實質就是兩個函數框架)及調度器類
6種調度策略
linux內核目前實現了6中調度策略(即調度算法), 用於對不同類型的進程進行調度, 或者支持某些特殊的功能
SCHED_NORMAL和SCHED_BATCH調度普通的非實時進程
SCHED_FIFO和SCHED_RR和SCHED_DEADLINE則采用不同的調度策略調度實時進程
SCHED_IDLE則在系統空閒時調用idle進程.
5個調度器類
而依據其調度策略的不同實現了5個調度器類, 一個調度器類可以用一種種或者多種調度策略調度某一類進程, 也可以用於特殊情況或者調度特殊功能的進程.
其所屬進程的優先級順序為
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
3個調度實體
調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度.
這種一般性要求調度器不直接操作進程, 而是處理可調度實體, 因此需要一個通用的數據結構描述這個調度實體,即seched_entity結構, 其實際上就代表了一個調度對象，可以為一個進程，也可以為一個進程組.
linux中針對當前可調度的實時和非實時進程, 定義了類型為seched_entity的3個調度實體
sched_dl_entity 采用EDF算法調度的實時調度實體
sched_rt_entity 采用Roound-Robin或者FIFO算法調度的實時調度實體
sched_entity 采用CFS算法調度的普通非實時進程的調度實體
1.2 主調度器與內核/用戶搶占
1.2.1 調度過程中關閉內核搶占
我們在上一篇linux內核主調度器schedule中在分析主調度器的時候, 我們會發現內核在進行調度之前都會通過preempt_disable關閉內核搶占, 而在完成調度工作後, 又會重新開啟內核搶占
參見主調度器函數schedule
do {
preempt_disable(); /* 關閉內核搶占 */
__schedule(false); /* 完成調度 */
sched_preempt_enable_no_resched(); /* 開啟內核搶占 */
} while (need_resched()); /* 如果該進程被其他進程設置了TIF_NEED_RESCHED標志，則函數重新執行進行調度 */
這個很容易理解, 我們在內核完成調度器過程中, 這時候如果發生了內核搶占, 我們的調度會被中斷, 而調度卻還沒有完成, 這樣會丟失我們調度的信息.
1.2.2 調度完成檢查need_resched看是否需要重新調度
而同樣我們可以看到, 在調度完成後, 內核會去判斷need_resched條件, 如果這個時候為真, 內核會重新進程一次調度.
這個的原因, 我們在前一篇博客中, 也已經說的很明白了,
內核在thread_info的flag中設置了一個標識來標志進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED, 內核在即將返回用戶空間時會檢查標識TIF_NEED_RESCHED標志進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占
2 非搶占式和可搶占式內核
為了簡化問題，我使用嵌入式實時系統uC/OS作為例子
首先要指出的是，uC/OS只有內核態，沒有用戶態，這和Linux不一樣
多任務系統中, 內核負責管理各個任務, 或者說為每個任務分配CPU時間, 並且負責任務之間的通訊.
內核提供的基本服務是任務切換. 調度(Scheduler),英文還有一詞叫dispatcher, 也是調度的意思.
這是內核的主要職責之一, 就是要決定該輪到哪個任務運行了. 多數實時內核是基於優先級調度法的, 每個任務根據其重要程度的不同被賦予一定的優先級. 基於優先級的調度法指，CPU總是讓處在就緒態的優先級最高的任務先運行. 然而, 究竟何時讓高優先級任務掌握CPU的使用權, 有兩種不同的情況, 這要看用的是什麼類型的內核, 是不可剝奪型的還是可剝奪型內核
2.1 非搶占式內核
非搶占式內核是由任務主動放棄CPU的使用權
非搶占式調度法也稱作合作型多任務, 各個任務彼此合作共享一個CPU. 異步事件還是由中斷服務來處理. 中斷服務可以使一個高優先級的任務由掛起狀態變為就緒狀態.
但中斷服務以後控制權還是回到原來被中斷了的那個任務, 直到該任務主動放棄CPU的使用權時，那個高優先級的任務才能獲得CPU的使用權。非搶占式內核如下圖所示.
非搶占式內核的優點有
中斷響應快(與搶占式內核比較);
允許使用不可重入函數;
幾乎不需要使用信號量保護共享數據, 運行的任務占有CPU，不必擔心被別的任務搶占。這不是絕對的，在打印機的使用上，仍需要滿足互斥條件。
非搶占式內核的缺點有
任務響應時間慢。高優先級的任務已經進入就緒態，但還不能運行，要等到當前運行著的任務釋放CPU
非搶占式內核的任務級響應時間是不確定的，不知道什麼時候最高優先級的任務才能拿到CPU的控制權，完全取決於應用程序什麼時候釋放CPU
2.2 搶占式內核
使用搶占式內核可以保證系統響應時間. 最高優先級的任務一旦就緒, 總能得到CPU的使用權。當一個運行著的任務使一個比它優先級高的任務進入了就緒態, 當前任務的CPU使用權就會被剝奪，或者說被掛起了，那個高優先級的任務立刻得到了CPU的控制權。如果是中斷服務子程序使一個高優先級的任務進入就緒態，中斷完成時，中斷了的任務被掛起，優先級高的那個任務開始運行。
搶占式內核如下圖所示
搶占式內核的優點有
使用搶占式內核，最高優先級的任務什麼時候可以執行，可以得到CPU的使用權是可知的。使用搶占式內核使得任務級響應時間得以最優化。
搶占式內核的缺點有：
不能直接使用不可重入型函數。調用不可重入函數時，要滿足互斥條件，這點可以使用互斥型信號量來實現。如果調用不可重入型函數時，低優先級的任務CPU的使用權被高優先級任務剝奪，不可重入型函數中的數據有可能被破壞。
3 linux用戶搶占
3.1 linux用戶搶占
當內核即將返回用戶空間時, 內核會檢查need_resched是否設置, 如果設置, 則調用schedule()，此時，發生用戶搶占.
3.2 need_resched標識
內核如何檢查一個進程是否需要被調度呢?
內核在即將返回用戶空間時檢查進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占, 因此內核在thread_info的flag中設置了一個標識來標志進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED
並提供了一些設置可檢測的函數
函數描述定義
set_tsk_need_resched設置指定進程中的need_resched標志include/linux/sched.h, L2920
clear_tsk_need_resched清除指定進程中的need_resched標志include/linux/sched.h, L2926
test_tsk_need_resched檢查指定進程need_resched標志include/linux/sched.h, L2931
而我們內核中調度時常用的need_resched()函數檢查進程是否需要被重新調度其實就是通過test_tsk_need_resched實現的, 其定義如下所示
// http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L3093
static __always_inline bool need_resched(void)
{
return unlikely(tif_need_resched());
}
// http://lxr.free-electrons.com/source/include/linux/thread_info.h?v=4.6#L106
#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)
3.3 用戶搶占的發生時機(什麼時候需要重新調度need_resched)
一般來說，用戶搶占發生幾下情況：
從系統調用返回用戶空間;
從中斷(異常)處理程序返回用戶空間
從這裡我們可以看到, 用戶搶占是發生在用戶空間的搶占現象.
更詳細的觸發條件如下所示, 其實不外乎就是前面所說的兩種情況: 從系統調用或者中斷返回用戶空間
時鐘中斷處理例程檢查當前任務的時間片，當任務的時間片消耗完時，scheduler_tick()函數就會設置need_resched標志;
信號量、等到隊列、completion等機制喚醒時都是基於waitqueue的，而waitqueue的喚醒函數為default_wake_function，其調用try_to_wake_up將被喚醒的任務更改為就緒狀態並設置need_resched標志。
設置用戶進程的nice值時，可能會使高優先級的任務進入就緒狀態;
改變任務的優先級時，可能會使高優先級的任務進入就緒狀態;
新建一個任務時，可能會使高優先級的任務進入就緒狀態;
對CPU(SMP)進行負載均衡時，當前任務可能需要放到另外一個CPU上運行
4 linux內核搶占
4.1 內核搶占的概念
對比用戶搶占, 顧名思義, 內核搶占就是指一個在內核態運行的進程, 可能在執行內核函數期間被另一個進程取代.
4.2 為什麼linux需要內核搶占
linux系統中, 進程在系統調用後返回用戶態之前, 或者是內核中某些特定的點上, 都會調用調度器. 這確保除了一些明確指定的情況之外, 內核是無法中斷的, 這不同於用戶進程.
如果內核處於相對耗時的操作中, 比如文件系統或者內存管理相關的任務, 這種行為可能會帶來問題. 這種情況下, 內核代替特定的進程執行相當長的時間, 而其他進程無法執行, 無法調度, 這就造成了系統的延遲增加, 用戶體驗到”緩慢”的響應. 比如如果多媒體應用長時間無法得到CPU, 則可能發生視頻和音頻漏失現象.
在編譯內核時如果啟用了對內核搶占的支持, 則可以解決這些問題. 如果高優先級進程有事情需要完成, 那麼在啟用了內核搶占的情況下, 不僅用戶空間應用程序可以被中斷, 內核也可以被中斷,
linux內核搶占是在Linux2.5.4版本發布時加入的, 盡管使內核可搶占需要的改動特別少, 但是該機制不像搶占用戶空間進程那樣容易實現. 如果內核無法一次性完成某些操作(例如, 對數據結構的操作), 那麼可能出現靜態條件而使得系統不一致.
內核搶占和用戶層進程被其他進程搶占是兩個不同的概念, 內核搶占主要是從實時系統中引入的, 在非實時系統中的確也能提高系統的響應速度, 但也不是在所有情況下都是最優的，因為搶占也需要調度和同步開銷，在某些情況下甚至要關閉內核搶占, 比如前面我們將主調度器的時候, linux內核在完成調度的過程中是關閉了內核搶占的.
內核不能再任意點被中斷, 幸運的是, 大多數不能中斷的點已經被SMP實現標識出來了. 並且在實現內核搶占時可以重用這些信息. 如果內核可以被搶占, 那麼單處理器系統也會像是一個SMP系統
4.3 內核搶占的發生時機
要滿足什麼條件，kernel才可以搶占一個任務的內核態呢?
沒持有鎖。鎖是用於保護臨界區的，不能被搶占。
Kernel code可重入(reentrant)。因為kernel是SMP-safe的，所以滿足可重入性。
內核搶占發生的時機，一般發生在：
當從中斷處理程序正在執行，且返回內核空間之前。當一個中斷處理例程退出，在返回到內核態時(kernel-space)。這是隱式的調用schedule()函數，當前任務沒有主動放棄CPU使用權，而是被剝奪了CPU使用權。
當內核代碼再一次具有可搶占性的時候，如解鎖(spin_unlock_bh)及使能軟中斷(local_bh_enable)等, 此時當kernel code從不可搶占狀態變為可搶占狀態時(preemptible again)。也就是preempt_count從正整數變為0時。這也是隱式的調用schedule()函數
如果內核中的任務顯式的調用schedule(), 任務主動放棄CPU使用權
如果內核中的任務阻塞(這同樣也會導致調用schedule()), 導致需要調用schedule()函數。任務主動放棄CPU使用權
內核搶占，並不是在任何一個地方都可以發生，以下情況不能發生
內核正進行中斷處理。在Linux內核中進程不能搶占中斷(中斷只能被其他中斷中止、搶占，進程不能中止、搶占中斷)，在中斷例程中不允許進行進程調度。進程調度函數schedule()會對此作出判斷，如果是在中斷中調用，會打印出錯信息。
內核正在進行中斷上下文的Bottom Half(中斷下半部，即軟中斷)處理。硬件中斷返回前會執行軟中斷，此時仍然處於中斷上下文中。如果此時正在執行其它軟中斷，則不再執行該軟中斷。
內核的代碼段正持有spinlock自旋鎖、writelock/readlock讀寫鎖等鎖，處干這些鎖的保護狀態中。內核中的這些鎖是為了在SMP系統中短時間內保證不同CPU上運行的進程並發執行的正確性。當持有這些鎖時，內核不應該被搶占。
內核正在執行調度程序Scheduler。搶占的原因就是為了進行新的調度，沒有理由將調度程序搶占掉再運行調度程序。
內核正在對每個CPU“私有”的數據結構操作(Per-CPU date structures)。在SMP中，對於per-CPU數據結構未用spinlocks保護，因為這些數據結構隱含地被保護了(不同的CPU有不一樣的per-CPU數據，其他CPU上運行的進程不會用到另一個CPU的per-CPU數據)。但是如果允許搶占，但一個進程被搶占後重新調度，有可能調度到其他的CPU上去，這時定義的Per-CPU變量就會有問題，這時應禁搶占。
5 內核搶占的實現
5.1 內核如何跟蹤它能否被搶占?
前面我們提到了, 系統中每個進程都有一個特定於體系結構的struct thread_info結構, 用戶層程序被調度的時候會檢查struct thread_info中的need_resched標識TLF_NEED_RESCHED標識來檢查自己是否需要被重新調度.
自然內核搶占·也可以應用同樣的方法被實現, linux內核在thread_info結構中添加了一個自旋鎖標識preempt_count, 稱為搶占計數器(preemption counter).
struct thread_info
{
/* ...... */
int preempt_count; /* 0 => preemptable, <0 => BUG */
/* ...... */
}
preempt_count值描述
0禁止內核搶占, 其值標記了使用preempt_count的臨界區的數目
0開啟內核搶占
<0鎖為負值, 內核出現錯誤
內核自然也提供了一些函數或者宏, 用來開啟, 關閉以及檢測搶占計數器preempt_coun的值, 這些通用的函數定義在include/asm-generic/preempt.h, 而某些架構也定義了自己的接口， 比如x86架構/arch/x86/include/asm/preempt.h
函數描述定義
preempt_count獲取當前current進程搶占計數器的值include/asm-generic/preempt.h, line 8
preempt_count_ptr返回指向當前current進程的搶占計數器的指針include/asm-generic/preempt.h, line 13
preempt_count_set重設當前current進程的搶占計數器include/asm-generic/preempt.h, line 18
init_task_preempt_count初始化task的搶占計數器為FORK_PREEMPT_COUNTinclude/asm-generic/preempt.h, line 26
init_idle_preempt_count初始化task的搶占計數器為PREEMPT_ENABLEDinclude/asm-generic/preempt.h, line 30
preempt_count_add將增加current的搶占計數器增加valinclude/linux/preempt.h, line 132
preempt_count_sub將增加current的搶占計數器減少valinclude/linux/preempt.h, line 133
preempt_count_dec_and_test將current的搶占計數器減少1, 然後看是否可以進程內核搶占, 即檢查搶占計數器是否為0(允許搶占), 同時檢查tif_need_resched標識是否為真include/linux/preempt.h, line 134, 61
preempt_count_inccurrent的搶占計數器增加1include/linux/preempt.h, line 140
preempt_count_deccurrent的搶占計數器減少1include/linux/preempt.h, line 141
還有其他函數可用於開啟和關閉內核搶占
函數描述定義
preempt_disable通過preempt_count_inc來停用內核搶占, 並且通過路障barrier同步來避免編譯器的優化include/linux/preempt.h, line 145
preempt_enablepreempt_count_dec_and_test啟用內核搶占, 然後通過__preempt_schedule檢測是夠有必要進行調度include/linux/preempt.h, line 162
preempt_enable_no_resched開啟搶占, 但是不進行重調度include/linuxc/preempt.h, line 151
preempt_check_resched調用__preempt_schedule檢測是夠有必要進行調度include/linux/preempt.h, line 176
should_resched檢查current的搶占計數器是否為參數preempt_offset的值, 同時檢查 tif_need_resched是否為真include/linux/preempt.h, line 74
preemptible檢查是否可以內核搶占, 檢查搶占計數器是否為0, 以及是否停用了中斷/include/linux/preempt.h, line159
5.2 內核如何知道是否需要搶占?
首先必須設置了TLF_NEED_RESCHED標識來通知內核有進程在等待得到CPU時間, 然後會在判斷搶占計數器preempt_count是否為0, 這個工作往往通過preempt_check_resched或者其相關來實現
5.2.1 重新啟用內核搶占時使用preempt_schedule檢查搶占
在內核停用搶占後重新啟用時, 檢測是否有進程打算搶占當前執行的內核代碼, 是一個比較好的時機, 如果是這樣, 應該盡快完成, 則無需等待下一次對調度器的例行調用.
搶占機制中主要的函數是preempt_schedule, 設置了TIF_NEED_RESCHED標志並不能保證可以搶占內核, 內核可能處於臨界區, 不能被干擾
// http://lxr.free-electrons.com/source/kernel/sched/core.c?v=4.6#L3307
/*
* this is the entry point to schedule() from in-kernel preemption
* off of preempt_enable. Kernel preemptions off return from interrupt
* occur there and call schedule directly.
*/
asmlinkage __visible void __sched notrace preempt_schedule(void)
{
/*
* If there is a non-zero preempt_count or interrupts are disabled,
* we do not want to preempt the current task. Just return..
*/
/* !preemptible() => preempt_count() != 0 || irqs_disabled()
* 如果搶占計數器大於0, 那麼搶占被停用, 該函數立即返回
* 如果
*/
if (likely(!preemptible()))
return;
preempt_schedule_common();
}
NOKPROBE_SYMBOL(preempt_schedule);
EXPORT_SYMBOL(preempt_schedule);
// http://lxr.free-electrons.com/source/include/linux/preempt.h?v=4.6
#define preemptible() (preempt_count() == 0 && !irqs_disabled())
!preemptible => preempt_count() != 0 || irqs_disabled()表明
如果搶占計數器大於0, 那麼搶占仍然是被停用的, 因此內核不能被打斷, 該函數立即結束.
如果在某些重要的點上內核停用了硬件中斷, 以保證一次性完成相關的處理, 那麼搶占也是不可能的.irqs_disabled會檢測是否停用了中斷. 如果已經停用, 則內核不能被搶占
接著如果可以被搶占, 則執行如下步驟
static void __sched notrace preempt_schedule_common(void)
{
do {
/*
preempt_disable_notrace定義在
http://lxr.free-electrons.com/source/include/linux/preempt.h?v=4.6#L198 等待於__preempt_count_inc();
*/
preempt_disable_notrace();
/* 完成一次調度 */
__schedule(true);
/*
preempt_enable_no_resched_notrace
http://lxr.free-electrons.com/source/include/linux/preempt.h?v=4.6#L204
等價於__preempt_count_dec
*/
preempt_enable_no_resched_notrace();
/*
* Check again in case we missed a preemption opportunity
* between schedule and now.
* 再次檢查, 以免在__scheudle和當前點之間錯過了搶占的時機
*/
} while (need_resched());
}
我們可以看到, 內核在增加了搶占計數器的計數後, 用__schedule進行了一次調度, 參數傳入preempt = true, 表明調度不是以普通的方式引發的, 而是由於內核搶占. 在內核重調度之後, 代碼流程回到當前進程, 那麼就井搶占計數器減少1.
5.2.2 中斷之後返回內核態時通過preempt_schedule_irq觸發
上面preempt_schedule只是觸發內核搶占的一種方法, 另一種激活搶占的方式是在處理了一個硬件中斷請求之後. 如果處理器在處理中斷請求後返回內核態(返回用戶態則沒有影響), 特定體系結構的匯編例程會檢查搶占計數器是否為0, 即是否允許搶占, 以及是否設置了重調度標識, 類似於preempt_schedule的處理. 如果兩個條件都滿足則通過preempt_schedule_irq調用調度器, 此時表明搶占請求發自中斷上下文
該函數與preempt_schedule的本質區別在於: preempt_schedule_irq調用時停用了中斷, 防止終端造成的遞歸調用, 其定義在kernel/sched/core.c, line3360
/*
* this is the entry point to schedule() from kernel preemption
* off of irq context.
* Note, that this is called and return with irqs disabled. This will
* protect us against recursive calling from irq.
*/
asmlinkage __visible void __sched preempt_schedule_irq(void)
{
enum ctx_state prev_state;
/* Catch callers which need to be fixed */
BUG_ON(preempt_count() || !irqs_disabled());
prev_state = exception_enter();
do {
preempt_disable();
local_irq_enable();
__schedule(true);
local_irq_disable();
sched_preempt_enable_no_resched();
} while (need_resched());
exception_exit(prev_state);
}
5.2.3 PREEMPT_ACTIVE標識位和PREEMPT_DISABLE_OFFSET
之前的內核版本中, 搶占計數器中於一個標識位PREEMPT_ACTIVE, 這個位設置後即標識了可以進行內核搶占, 使得preempt_count有一個很大的值, 這樣就不受普通的搶占計數器加1操作的影響了
PREEMPT_ACTIVE的引入, 參見PREEMPT_ACTIVE: add default defines
// http://lxr.free-electrons.com/source/include/linux/preempt.h?v=4.3#L58
#define PREEMPT_ACTIVE_BITS 1
#define PREEMPT_ACTIVE_SHIFT (NMI_SHIFT + NMI_BITS)
#define PREEMPT_ACTIVE (__IRQ_MASK(PREEMPT_ACTIVE_BITS) << PREEMPT_ACTIVE_SHIFT)
然後也為其提供了一些置位的函數，其實就是將preempt_count加上/減去一個很大的數, 參見preempt: Disable preemption from preempt_schedule*() callers
但是在linux-4.4版本之後移除了這個標志, 取而代之的是在linux-4.2時引入的PREEMPT_DISABLE_OFFSET
6 總結
一般來說，CPU在任何時刻都處於以下三種情況之一：
運行於用戶空間，執行用戶進程
運行於內核空間，處於進程上下文
運行於內核空間，處於中斷上下文
6.1 用戶搶占
一般來說, 當進程從系統調用或者從中斷(異常)處理程序返回用戶空間時會觸發主調度器進行用戶搶占
從系統調用返回用戶空間
從中斷(異常)處理程序返回用戶空間
為了對一個進程需要被調度進行標記, 內核在thread_info的flag中設置了一個標識來標志進程是否需要重新調度, 即重新調度need_resched標識TIF_NEED_RESCHED, 內核在即將返回用戶空間時會檢查標識TIF_NEED_RESCHED標志進程是否需要重新調度，如果設置了，就會發生調度, 這被稱為用戶搶占
6.2 內核搶占
如果內核處於相對耗時的操作中, 比如文件系統或者內存管理相關的任務, 這種行為可能會帶來問題. 這種情況下, 內核代替特定的進程執行相當長的時間, 而其他進程無法執行, 無法調度, 這就造成了系統的延遲增加, 用戶體驗到”緩慢”的響應. 因此linux內核引入了內核搶占.
linux內核通過在thread_info結構中添加了一個自旋鎖標識preempt_count, 稱為搶占計數器(preemption counter)來作為內核搶占的標記,
內核搶占的觸發大致也是兩類, 內核搶占關閉後重新開啟時, 中斷返回內核態時
內核重新開啟內核搶占時使用preempt_schedule檢查內核搶占
中斷之後返回內核態時通過preempt_schedule_irq觸發內核搶占
而內核搶占時, 通過調用__schedule(true)傳入的preempt=true來通知內核, 這是一個內核搶占
