Linux作業系統任務排程的實現
相關影片推薦
挑戰360°無死角講解 程序管理，排程器的5種實現
linux核心，程序排程器的實現，完全公平排程器 CFS
協程排程器實現，底層原理，使用者態切換，多核模式，效能測試
LinuxC++後臺伺服器免費學習地址：C/C++Linux伺服器開發/後臺架構師-學習影片
前言
本文所有對於linux作業系統原始碼的引用均是基於linux 4。20版本，且文中列舉的原始碼主要是核心屬性或函式，內容有所省略。
基本概念
Linux排程單位
Linux的最小排程單位是執行緒，或者說基於task。
無論是程序還是執行緒到了Linux核心都是一個task，都有一個task_struct資料結構對其進行管理，Linux程序在建立時，其內部也會包含一個主執行緒。
Linux任務型別
Linux把任務主要分為兩類：
實時任務：有很高的優先順序需要儘快完成交付；
普通任務：沒有一定的實時性要求，儘快完成交付即可。
當系統中存在實時任務時，排程程式會優先選擇實時任務執行，普通任務將得不到執行的機會。同時不同型別的任務有不同的排程策略。
Linux支援的排程策略
task_struct內包含一個欄位標識task的排程策略：
unsigned int policy；
其可選值如下：
// kernel/sched/sched。h
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO： reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6
實時任務排程策略：
SCHED_FIFO，按照任務的先後順序執行，高優先順序的任務可以搶佔低優先順序的任務；
SCHED_RR，為每一個任務分配一定大小的時間片，時間片用完後會將任務準移到佇列的尾部，高優先順序的任務可以搶佔低優先順序的任務；
SCHED_DEADLINE，優先選擇當前時間距離任務截止時間近的任務。
普通任務排程策略：
SCHED_NORMAL，普通任務排程策略；
SCHED_BATCH，後臺任務；
SCHED_IDLE，空閒時才執行。
Linux排程優先順序
linux主要採用兩個優先順序範圍：
普通任務採用的nice值，我們可以透過nice庫函式為task設定nice值，nice值越小，排程執行的機會就越大，其取值範圍是 -20 ~ 19
實時任務採用的實時優先順序，其取值範圍是0 ~ 99
在task_struct中有下面幾個欄位標識著task的優先順序的值：
// 動態優先順序，prio 的值是排程器最終使用的優先順序數值，prio越小，表示優先順序越高，其取值範圍是0-139
// 它又被分為兩個區間，0~99表示實時任務優先順序，100~139表示普通任務優先順序（對於nice值-20~19）
int prio；
// 靜態優先順序不會隨時間改變，核心不會主動修改它，只能透過系統呼叫 nice 去修改 static_prio
// 有效範圍是 100 ~ 139，預設值為120，0~99 沒有意義
int static_prio；
// 歸一化優先順序，這是一些比較晦澀的概念，以後研究透了再解釋
int normal_prio；
// 實時優先順序，取值範圍是0~99，僅對實時任務有效
unsigned int rt_priority；
Linux排程類
排程類是負責真正執行排程策略的邏輯，在task_struct內部有一個排程類的結構體指標：
const struct sched_class *sched_class；
sched_class只是一個抽象的結構體，其內部定義了一些排程先關的方法，詳細內容如下：
struct sched_class {
// 排程類是一個連結串列，按照優先順序排列，next執行下一個排程類
const struct sched_class *next；
// 新增任務
void （*enqueue_task） （struct rq *rq， struct task_struct *p， int flags）；
// 移除任務
void （*dequeue_task） （struct rq *rq， struct task_struct *p， int flags）；
// 校驗是否當前任務應該被搶佔
void （*check_preempt_curr）（struct rq *rq， struct task_struct *p， int flags）；
// 或取下一個待執行的任務
struct task_struct * （*pick_next_task）（struct rq *rq，
struct task_struct *prev，
struct rq_flags *rf）；
void （*put_prev_task）（struct rq *rq， struct task_struct *p）；
void （*set_curr_task）（struct rq *rq）；
// 時鐘中斷處理
void （*task_tick）（struct rq *rq， struct task_struct *p， int queued）；
/*
* The switched_from（） call is allowed to drop rq->lock， therefore we
* cannot assume the switched_from/switched_to pair is serliazed by
* rq->lock。 They are however serialized by p->pi_lock。
*/
void （*switched_from）（struct rq *this_rq， struct task_struct *task）；
void （*switched_to） （struct rq *this_rq， struct task_struct *task）；
……
}；
排程類有下面幾種具體的實現：
// 會停止所有其他執行緒，不會被其他任務打斷，優先順序最高的任務會使用
extern const struct sched_class stop_sched_class；
// 對於上面deadline排程策略的執行
extern const struct sched_class dl_sched_class；
// 對應上面FIFO與RR排程策略的執行，具體哪一個策略，由policy欄位指定
extern const struct sched_class rt_sched_class；
// 對應NORMAL普通排程策略的執行，我們稱為公平排程類，其內部採用的是cfs排程演算法，後面會詳細說明
extern const struct sched_class fair_sched_class；
// 對應IDLE排程策略的執行
extern const struct sched_class idle_sched_class；
每一個排程類針對上面的介面函式都有各自的實現機制，同時排程類其實是連結串列的資料結構，按照優先順序依次為：
stop_sched_class → dl_sched_class → rt_sched_class → fair_sched_class → idle_sched_class
原始碼參考：
const struct sched_class stop_sched_class = {
。next = &dl_sched_class，
。。
}
const struct sched_class dl_sched_class = {
。next = &rt_sched_class，
。。。
}
const struct sched_class rt_sched_class = {
。next = &fair_sched_class
。。。
}
。。。
【文章福利】小編推薦自己的linuxC/C++語言交流群：
832218493
，整理了一些個人覺得比較好的學習書籍、影片資料共享在裡面，有需要的可以自行新增哦！~!
Linux排程實體
排程實體用於維護task排程相關的元資訊，其有以下幾種：
// 普通任務使用的排程實體
struct sched_entity se；
// 實時任務使用的排程實體
struct sched_rt_entity rt；
// deadline排程類的排程實體
struct sched_dl_entity dl；
因為我們接觸的大多都是普通任務，所以我們主要關注sched_entity的詳細資訊：
struct sched_entity {
// 當前任務的權重值，linux透過nice函式為任務設定優先順序，每一個nice值都對應一個權重值
struct load_weight load；
unsigned long runnable_weight；
struct rb_node run_node；
struct list_head group_node；
unsigned int on_rq；
u64 exec_start；
u64 sum_exec_runtime；
// 當前任務的虛擬執行時間，cfs排程演算法的概念，基於task的實際執行時間與優先順序權重計算出來的值
u64 vruntime；
u64 prev_sum_exec_runtime；
}
struct load_weight {
unsigned long weight；
u32 inv_weight；
}；
CFS排程演算法的思想與實現
CFS（Complete Fair Schedule）排程演算法的思想是為每一個task維護一個擬的執行時間vruntime，
排程程式優先選擇vruntime值最小的任務執行，之所以引入vruntime的概念，是為了支援優先順序排程。
vruntime其實是基於task的實際執行時間及優先順序權重計算出來的值，其計算公式如下：
vruntime += delta_exec * NICE_0_LOAD / weight
vruntime：虛擬執行時間
delta_exec： 實際的執行時間
NICE_0_LOAD：程序優先順序nice值為0對應的權重值
weight：task的nice值對應的權重值，前面我們說過nice值的取值範圍是-20~19，每一個nice值在linux記憶體程式中都有一個對應的權重值，詳細內容如下：const int sched_prio_to_weight［40］ = { /* -20 */ 88761， 71755， 56483， 46273， 36291， /* -15 */ 29154， 23254， 18705， 14949， 11916， /* -10 */ 9548， 7620， 6100， 4904， 3906， /* -5 */ 3121， 2501， 1991， 1586， 1277， /* 0 */ 1024， 820， 655， 526， 423， /* 5 */ 335， 272， 215， 172， 137， /* 10 */ 110， 87， 70， 56， 45， /* 15 */ 36， 29， 23， 18， 15， }； 複製程式碼
我們可以看出，nice值越小其權重值越大，則最終計算出來的vruntime就會偏小，於是得到排程執行的機會就越大，反之則越小。
為了優先獲取vruntime最小任務的時間複雜度，LinuxCFS演算法的實現上採用紅黑樹的資料結構，其具體實現是執行佇列中的cfs_rq。
Linux執行佇列
對於每一個CPU都會有一個rq的結構體，維護著所有待執行的任務，我們稱之為執行佇列（running queue，當然也有人稱之為就緒佇列，linux並沒有過於區分執行態與就緒態），每一個執行佇列rq內部又會有幾個子佇列，其中就包括：
struct rq {
// cfs執行佇列
struct cfs_rq cfs；
// 實時任務執行佇列
struct rt_rq rt；
// deadline任務執行佇列
struct dl_rq dl；
struct task_struct *curr；
}
其中針對普通任務使用的是cfs_rq執行佇列，cfs執行佇列的內部實現其實是一個紅黑樹，
// cfs任務佇列，qi
struct cfs_rq {
struct load_weight load；
unsigned long runnable_weight；
unsigned int nr_running；
unsigned int h_nr_running；
u64 exec_clock；
u64 min_vruntime；
struct rb_root_cached tasks_timeline；
/*
* ‘curr’ points to currently running entity on this cfs_rq。
* It is set to NULL otherwise （i。e when none are currently running）。
*/
// 指向cfs_rq上正在執行的執行實體
struct sched_entity *curr；
struct sched_entity *next；
struct sched_entity *last；
struct sched_entity *skip；
}；
/*
* Leftmost-cached rbtrees。
*
* We do not cache the rightmost node based on footprint
* size vs number of potential users that could benefit
* from O（1） rb_last（）。 Just not worth it， users that want
* this feature can always implement the logic explicitly。
* Furthermore， users that want to cache both pointers may
* find it a bit asymmetric， but that‘s ok。
*/
struct rb_root_cached {
struct rb_root rb_root；
struct rb_node *rb_leftmost；
}；
排程的執行
fair_sched_class排程類的實現
由於大多數任務都是普通任務，採用的都是公平排程類fair_sched_class，我們主要介紹一下其原始碼實現：
const struct sched_class fair_sched_class = {
。next = &idle_sched_class，
。check_preempt_curr = check_preempt_wakeup，
。pick_next_task = pick_next_task_fair，
。set_curr_task = set_curr_task_fair，
。task_tick = task_tick_fair，
}；
具體介面函式實現如下：
獲取下一個待執行任務pick_next_task實現——pick_next_task_fair
取出當前執行任務的task_struct
呼叫update_curr（）更新當前執行任務的總執行時間、vruntime等
獲取下一個待執行任務的排程實體
將任務排程實體放回cfs佇列
返回下一個待執行的任務
static struct task_struct *
pick_next_task_fair（struct rq *rq， struct task_struct *prev， struct rq_flags *rf）
{
struct cfs_rq *cfs_rq = &rq->cfs；
struct sched_entity *se；
struct task_struct *p；
int new_tasks；
again：
if （！cfs_rq->nr_running）
goto idle；
#ifdef CONFIG_FAIR_GROUP_SCHED
if （prev->sched_class ！= &fair_sched_class）
goto simple；
do {
struct sched_entity *curr = cfs_rq->curr；
if （curr） {
if （curr->on_rq）
// 更新當前任務，主要包括總時間、vruntime等
update_curr（cfs_rq）；
else
curr = NULL；
if （unlikely（check_cfs_rq_runtime（cfs_rq））） {
cfs_rq = &rq->cfs；
if （！cfs_rq->nr_running）
goto idle；
goto simple；
}
}
se = pick_next_entity（cfs_rq， curr）；
cfs_rq = group_cfs_rq（se）；
} while （cfs_rq）；
p = task_of（se）；
if （prev ！= p） {
struct sched_entity *pse = &prev->se；
while （！（cfs_rq = is_same_group（se， pse））） {
int se_depth = se->depth；
int pse_depth = pse->depth；
if （se_depth <= pse_depth） {
put_prev_entity（cfs_rq_of（pse）， pse）；
pse = parent_entity（pse）；
}
if （se_depth >= pse_depth） {
set_next_entity（cfs_rq_of（se）， se）；
se = parent_entity（se）；
}
}
// 修改完時間後，將任務重新放回cfs佇列
put_prev_entity（cfs_rq， pse）；
set_next_entity（cfs_rq， se）；
}
goto done；
simple：
#endif
// 將任務放回rq
put_prev_task（rq， prev）；
do {
se = pick_next_entity（cfs_rq， NULL）；
set_next_entity（cfs_rq， se）；
cfs_rq = group_cfs_rq（se）；
} while （cfs_rq）；
p = task_of（se）；
……
}
更新當前任務的執行時間統計update_curr函式
更新task執行總時間sum_exec_runtime
更新task的vruntime
static void update_curr（struct cfs_rq *cfs_rq）
{
struct sched_entity *curr = cfs_rq->curr；
u64 now = rq_clock_task（rq_of（cfs_rq））；
u64 delta_exec；
delta_exec = now - curr->exec_start；
curr->sum_exec_runtime += delta_exec；
// 裡面執行的就是vruntime的計算公式
curr->vruntime += calc_delta_fair（delta_exec， curr）；
update_min_vruntime（cfs_rq）；
。。。
。。。
}
時鐘中斷處理task_tick函式實現——task_tick_fair
時鐘中斷處理：
找到當前執行任務的排程實體se
執行entity_tick函式，entity_tick內部會呼叫update_curr更新當前執行task的總時間及vruntime，並判斷是否應該搶佔當前任務
static void task_tick_fair（struct rq *rq， struct task_struct *curr， int queued）
{
struct cfs_rq *cfs_rq；
struct sched_entity *se = &curr->se；
for_each_sched_entity（se） {
cfs_rq = cfs_rq_of（se）；
entity_tick（cfs_rq， se， queued）；
}
if （static_branch_unlikely（&sched_numa_balancing））
task_tick_numa（rq， curr）；
update_misfit_status（curr， rq）；
}
static void
entity_tick（struct cfs_rq *cfs_rq， struct sched_entity *curr， int queued）
{
// 更新當前執行任務的執行時間統計，包括vruntime，上面有詳細說明
update_curr（cfs_rq）；
if （cfs_rq->nr_running > 1）
// 判斷當前任務是否應該被搶佔
check_preempt_tick（cfs_rq， curr）；
}
判斷當前任務是否應該被搶佔——check_preempt_tick函式實現
計算task本週期理論上的執行時間ideal_runtime
計算task的實際執行時間delta_exec
校驗是否應該被搶佔
/* kernel/sched/fair。c */
static void
check_preempt_tick（struct cfs_rq *cfs_rq， struct sched_entity *curr）
{
unsigned long ideal_runtime， delta_exec；
struct sched_entity *se；
s64 delta；
// 計算當前任務應該要分到的時間， 理論執行時間
// 為了使vruntime相等，其計算出來的理論的執行時間應該是跟權重值成正比的
ideal_runtime = sched_slice（cfs_rq， curr）；
// 計算當前任務本週期內的實際執行時間
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime；
// 如果實際執行時間 > 理論執行時間，則應該搶佔
if （delta_exec > ideal_runtime） {
/* 告訴 rq 應該重新排程了 */
resched_curr（rq_of（cfs_rq））；
clear_buddies（cfs_rq， curr）；
return；
}
// 如果實際執行時間比最小排程時間還小，則不進行搶佔
if （delta_exec < sysctl_sched_min_granularity）
return；
// 和紅黑樹上最左節點的比較vruntime
se = __pick_first_entity（cfs_rq）；
delta = curr->vruntime - se->vruntime；
if （delta < 0）
return；
if （delta > ideal_runtime）
resched_curr（rq_of（cfs_rq））；
}
// 如果應該被搶佔，則resched_curr（rq_of（cfs_rq）），最終會呼叫set_tsk_need_resched，為task設定TIF_NEED_RESCHED標記
static inline void set_tsk_need_resched（struct task_struct *tsk）
{
set_tsk_thread_flag（tsk，TIF_NEED_RESCHED）；
}
如何實現實時任務優先普通任務執行
排程程式在執行核心排程邏輯的首要工作是獲取下一個應該被執行的任務，我們之前說過排程其實是一個按照優先順序的連結串列，排程程式會依次遍歷每一個排程類，分別呼叫每一個排程類的pick_next_task（）函式，實時任務排程類會優先呼叫，首先從rt_rq中獲取任務，如果沒有獲取到才會交給公平排程類fair_sched_class從cfs_rq中獲取任務，透過此機制實現了實時任務優先於普通任務執行。也正是因為此，當系統中存在實時任務的時候，普通任務將得不到執行的機會。其具體實現如下：
#ifdef CONFIG_SMP
#define sched_class_highest （&stop_sched_class）
#else
#define sched_class_highest （&dl_sched_class）
#endif
#define for_each_class（class） \
for （class = sched_class_highest； class； class = class->next）
/*
* Pick up the highest-prio task：
*/
static inline struct task_struct *
pick_next_task（struct rq *rq， struct task_struct *prev， struct rq_flags *rf）
{
const struct sched_class *class；
struct task_struct *p；
/*
* Optimization： we know that if all tasks are in the fair class we can
* call that function directly， but only if the @prev task wasn’t of a
* higher scheduling class， because otherwise those loose the
* opportunity to pull in more work from other CPUs。
*/
// 一個最佳化機制，因為通常大部分任務都是普通任務
// 如果當前rq中所有的任務都是普通任務，就可以直接從fair_sched_class排程類開始遍歷了
// 而不用像下面for_each_class（class）{} 從頭開始遍歷每一個排程類
if （likely（（prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class） &&
rq->nr_running == rq->cfs。h_nr_running）） {
p = fair_sched_class。pick_next_task（rq， prev， rf）；
if （unlikely（p == RETRY_TASK））
goto again；
/* Assumes fair_sched_class->next == idle_sched_class */
if （unlikely（！p））
p = idle_sched_class。pick_next_task（rq， prev， rf）；
return p；
}
// 遍歷每一個排程類，獲取下一個待執行的任務，例如fair_sched_class的具體參考上一小節原始碼實現
for_each_class（class） {
p = class->pick_next_task（rq， prev， rf）；
if （p） {
if （unlikely（p == RETRY_TASK））
goto again；
return p；
}
}
}
主動排程與搶佔式排程
通常我們把排程型別分為兩種：
主動排程：任務執行schedule庫函式（schedule系統呼叫），主動讓出CPU資源，例如當任務在等待IO資源時，此時任務處於不能推進的狀態，就可以呼叫schedule讓出CPU資源給別的task
搶佔式排程，主要有兩種：程序執行的時間太長了，時鐘中斷處理函式觸發搶佔當前正在執行的任務；當一個任務被喚醒的時候，如果被喚醒任務的優先順序高於當前執行任務的優先順序，則會觸發搶佔。
主動排程的執行過程
透過前面我們瞭解過觸發主動排程主要是使用者執行schedule（）函式，通常在進行IO的阻塞操作時，可以選擇執行schedule函式讓出CPU資源。
schedule（）函式的具體實現中有呼叫一個__schedule（）函式，核心排程邏輯就封裝在其中：
static void __sched notrace __schedule（bool preempt）
{
struct task_struct *prev， *next；
unsigned long *switch_count；
struct rq_flags rf；
struct rq *rq；
int cpu；
cpu = smp_processor_id（）；
// 獲取當前cpu上的執行佇列rq
rq = cpu_rq（cpu）；
// 去取當前執行佇列上正在執行的任務，記做prev，因為一旦切換後，當前任務就變成previous任務了
prev = rq->curr；
……
// 獲取下一個待執行的任務，內部邏輯就是遍歷每一個排程類，獲取任務，
// 具體實現原始碼請參考上面一小節：如何實現實時任務優先普通任務執行
next = pick_next_task（rq， prev， &rf）；
……
// 如果下一個待執行任務與prev不等，則需要程序上下文切換，next任務載入執行
if （likely（prev ！= next）） {
rq->nr_switches++；
rq->curr = next；
++*switch_count；
trace_sched_switch（preempt， prev， next）；
rq = context_switch（rq， prev， next， &rf）；
} else {
rq->clock_update_flags &= ~（RQCF_ACT_SKIP|RQCF_REQ_SKIP）；
rq_unlock_irq（rq， &rf）；
}
}
程式中關於上下文切換的具體實現，由於細節問題比較多，本文不再細緻研究，後續再進行完善。
搶佔式排程的執行過程
前面我們說過觸發搶佔式排程的時機主要有兩個：
時鐘中斷
程序喚醒
時鐘中斷觸發搶佔
時鐘中斷處理函式會呼叫scheduler_tick（）函式：
取出當前執行任務的task_struct
呼叫排程類的時鐘中斷函式task_tick的實現對於普通任務，會呼叫fair_sched_class的task_tick其內部會更新當前任務的執行時間、vruntime以及判斷當前任務是否應該被搶佔如果應該被搶佔，會給task打上一個TIF_NEED_RESCHED的標記，等到特定的時機執行真正的排程邏輯具體邏輯參考上述fair_sched_class的實現
/*
* This function gets called by the timer code， with HZ frequency。
* We call it with interrupts disabled。
*/
void scheduler_tick（void）
{
int cpu = smp_processor_id（）；
// 取出當前CPU的執行佇列
struct rq *rq = cpu_rq（cpu）；
// 取出當前執行佇列正在執行的任務的task_struct
struct task_struct *curr = rq->curr；
update_rq_clock（rq）；
// 呼叫當前任務的排程類的task_tick函式
curr->sched_class->task_tick（rq， curr， 0）；
。。。
。。。
}
喚醒任務觸發搶佔
在說主動排程的時候，我們說過在等待IO的時候，可以呼叫schedule函式主動放棄CPU，進入阻塞狀態。當IO完成的時候，就需要喚醒任務，如果被喚醒任務的優先順序高於當前執行任務的優先順序，就會觸發搶佔。
呼叫try_to_wake_up函式喚醒任務
最終會執行ttwu_do_wakeup喚醒邏輯try_to_wake_up會首先將喚醒任務新增到ttwu_queued佇列，最終呼叫ttwu_do_activate啟用任務ttwu_do_activate內部會呼叫ttwu_do_wakeup執行喚醒操作
ttwu_do_wakeup內部會呼叫check_preempt_curr函式判斷當前任務是否應該被搶佔
同樣如果應該搶佔會給task打上一個TIF_NEED_RESCHED的標記，等到特定的時機執行真正的排程邏輯
具體實現邏輯如下：
static int
try_to_wake_up（struct task_struct *p， unsigned int state， int wake_flags）
{
unsigned long flags；
cpu = task_cpu（p）；
// 將喚醒任務新增到佇列
ttwu_queue（p， cpu， wake_flags）；
return success；
}
static void ttwu_queue（struct task_struct *p， int cpu， int wake_flags）
{
struct rq *rq = cpu_rq（cpu）；
struct rq_flags rf；
rq_lock（rq， &rf）；
update_rq_clock（rq）；
// 啟用喚醒任務
ttwu_do_activate（rq， p， wake_flags， &rf）；
rq_unlock（rq， &rf）；
}
static void
ttwu_do_activate（struct rq *rq， struct task_struct *p， int wake_flags，
struct rq_flags *rf）
{
int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK；
lockdep_assert_held（&rq->lock）；
。。。
。。。
ttwu_activate（rq， p， en_flags）；
// 執行喚醒邏輯
ttwu_do_wakeup（rq， p， wake_flags， rf）；
}
static void ttwu_do_wakeup（struct rq *rq， struct task_struct *p， int wake_flags，
struct rq_flags *rf）
{
// 判斷是否應該搶佔
check_preempt_curr（rq， p， wake_flags）；
p->state = TASK_RUNNING；
trace_sched_wakeup（p）；
}
void check_preempt_curr（struct rq *rq， struct task_struct *p， int flags）
{
const struct sched_class *class；
if （p->sched_class == rq->curr->sched_class） {
// 呼叫當前執行的任務的排程類的實現判斷是否應該搶佔
rq->curr->sched_class->check_preempt_curr（rq， p， flags）；
} else {
for_each_class（class） {
if （class == rq->curr->sched_class）
break；
if （class == p->sched_class） {
resched_curr（rq）；
break；
}
}
}
}
真正執行搶佔邏輯的時機
真正搶佔的時機分為使用者態與核心態：
使用者態：
系統呼叫返回使用者態的時候static void exit_to_usermode_loop（struct pt_regs *regs， u32 cached_flags） { while （true） { // 判斷是否應該執行排程 if （cached_flags & _TIF_NEED_RESCHED） schedule（）； // 判斷是否有訊號待處理 if （cached_flags & _TIF_SIGPENDING） do_signal（regs）； } } 複製程式碼
中斷返回使用者態的時候有些中斷函式處理完成之後，也需要返回使用者態，最終都會呼叫到exit_to_usermode_loop函式
核心態：
開啟允許搶佔的時候，即呼叫preempt_enable（）的時候。核心執行的某些操作是不允許中斷的，因此在進行這些操作的時候，會臨時呼叫preempt_disable（）關閉搶佔，等到操作完成之後在開啟允許搶佔。
中斷返回核心態的時候
不管是主動排程還是搶佔式排程，最終都會執行__schedule（）核心排程邏輯。
總結
Linux任務排程之CFS排程演算法
CFS排程演算法其思想是為每一個task維護一個虛擬的執行時間vruntime，同時基於紅黑樹資料結構來儲存每一個task的排程資訊，紅黑樹按虛擬執行時間排序，排程程式優先選擇vruntime最小的task來執行，即紅黑樹最左的結點。
之所以稱之為虛擬執行時間是因為它是基於實際的執行時間及權重比計算出來的，具體公式為：
虛擬執行時間 = 實際執行時間 * NICE_0_LOAD（nice為0值時對應的權重值） / weight
每一個任務在使用者程式層面的優先順序nice值取值範圍是 -20 ~ 19， 每一個nice值在核心程式設計裡面都對應著一個權重值，nice值越低，則權重值越高，則計算出來的vruntime就會偏小，則獲取排程執行的機會就越大，反之就越小。
