本文主要圍繞 Linux 內核調度器 Preemption 的相關實現進行討論。其中涉及的一般操作系統和 x86 處理器和硬件概念，可能也適用於其它操作系統。
Linux 調度器的實現實際上主要做了兩部分事情，
任務上下文切換
在 Preemption Overview 裡，我們對任務上下文切換做了簡單介紹。可以看到，任務上下文切換有兩個層次的實現：公共層和處理器架構相關層。任務運行狀態的切換的實現最終與處理器架構密切關聯。因此 Linux 做了很好的抽象。在不同的處理器架構上，處理器架構相關的代碼和公共層的代碼相互配合共同實現了任務上下文切換的功能。這也使得任務上下文切換代碼可以很容易的移植到不同的處理器架構上。
任務調度策略
同樣的，為了滿足不同類型應用場景的調度需求，Linux 調度器也做了模塊化處理。調度策略的代碼也可被定義兩層 Scheduler Core (調度核心) 和 Scheduling Class (調度類)。調度核心的代碼實現了調度器任務調度的基本操作，所有具體的調度策略都被封裝在具體調度類的實現中。這樣，Linux 內核的調度策略就支持了模塊化的擴展能力。Linux v3.19 支持以下調度類和調度策略，
Real Time (實時)調度類 - 支持 SCHED_FIFO 和 SCHED_RR 調度策略。 CFS (完全公平)調度類 - 支持 SCHED_OTHER(SCHED_NORMAL)，SCHED_BATCH 和 SCHED_IDLE 調度策略。(注：SCHED_IDLE 是一種調度策略，與 CPU IDLE 進程無關)。 Deadline (最後期限)調度類 - 支持 SCHED_DEADLINE 調度策略。Linux 調度策略設置的系統調用 SCHED_SETATTR(2) 的手冊有對內核支持的各種調度策略的詳細說明。內核的調度類和 sched_setattr 支持的調度策略命名上不一致但是存在對應關系，而且調度策略的命名更一般化。這樣做的一個好處是，同一種調度策略未來可能有不同的內核調度算法來實現。新的調度算法必然引入新的調度類。內核引入新調度類的時候，使用這個系統調用的應用不需要去為之修改。調度策略本身也是 POSIX 結構規范的一部分。上述調度策略中，SCHED_DEADLINE 是 Linux 獨有的，POSIX 規范中並無此調度策略。SCHED(7) 對 Linux 調度 API 和歷史發展提供了概覽，值得參考。
調度器核心代碼位於 kernel/sched/core.c 文件。主要包含了以下實現，
調度器的初始化，調度域初始化。核心調度函數 __schedule 及上下文切換的通用層代碼。時鐘周期處理的通用層代碼，包含 Tick Preemption 的代碼。喚醒函數，Per-CPU Run Queue 操作的代碼，包含 Wakeup Preemption 通用層的代碼。基於高精度定時器中斷實現的高精度調度，處理器間調度中斷。處理器 IDLE 線程，調度負載均衡，遷移任務的代碼。與調度器有關的系統調用的實現代碼。調度器核心代碼的主要作用就是調度器的模塊化實現，降低了跨處理器平台移植和實現新調度算法模塊的重復代碼和模塊間的耦合度，提高了內核可移植性和可擴展性。
在 Linux 內核引入一種新調度算法，基本上就是實現一個新的 Scheduling Class (調度類)。調度類需要實現的所有借口定義在 struct sched_class 裡。下面對其中最重要的一些調度類接口做簡單的介紹，
enqueue_task
將待運行的任務插入到 Per-CPU Run Queue。典型的場景就是內核裡的喚醒函數，將被喚醒的任務插入 Run Queue 然後設置任務運行態為 TASK_RUNNING。
對 CFS 調度器來說，則是將任務插入紅黑樹，給 nr_running 增加計數。
dequeue_task
將非運行態任務移除出 Per-CPU Run Queue。典型的場景就是任務調度引起阻塞的內核函數，把任務運行態設置成 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE，然後調用 schedule 函數，最終觸發本操作。
對 CFS 調度器來說，則是將不在處於運行態的任務從紅黑樹中移除，給 nr_running 減少計數。
yield_task
處於運行態的任務申請主動讓出 CPU。典型的場景就是處於運行態的應用調用 sched_yield(2) 系統調用，直接讓出 CPU。此時系統調用 sched_yield 系統調用先調用 yield_task 申請讓出 CPU，然後調用 schedule 去做上下文切換。
對 CFS 調度器來說，如果 nr_running 是 1，則直接返回，最終 schedule 函數也不產生上下文切換。否則，任務被標記為 skip 狀態。調度器在紅黑樹上選擇待運行任務時肯定會跳過該任務。之後，因為 schedule 函數被調用，pick_next_task 最終會被調用。其代碼會從紅黑樹中最左側選擇一個任務，然後把要放棄運行的任務放回紅黑樹，然後調用上下文切換函數做任務上下文切換。
check_preempt_curr
用於在待運行任務插入 Run Queue 後，檢查是否應該 Preempt 正在 CPU 運行的當前任務。Wakeup Preemption 的實現邏輯主要在這裡。
對 CFS 調度器而言，主要是在是否能滿足調度時延和是否能保證足夠任務運行時間之間來取捨。CFS 調度器也提供了預定義的 Threshold 允許做 Wakeup Preemption 的調優。本文有專門章節對 Wakeup Preemption 做詳細分析。
pick_next_task
選擇下一個最適合調度的任務，將其從 Run Queue 移除。並且如果前一個任務還保持在運行態，即沒有從 Run Queue 移除，則將當前的任務重新放回到 Run Queue。內核 schedule 函數利用它來完成調度時任務的選擇。
對 CFS 調度器而言，大多數情況下，下一個調度任務是從紅黑樹的最左側節點選擇並移除。如果前一個任務是其它調度類，則調用該調度類的 put_prev_task 方法將前一個任務做正確的安置處理。但如果前一個任務如果也屬於 CFS 調度類的話，為了效率，跳過調度類標准方法 put_prev_task，但核心邏輯仍舊是 put_prev_task_fair 的主要部分。關於 put_prev_task 的具體功能，請參考隨後的說明。
put_prev_task
將前一個正在 CPU 上運行的任務做拿下 CPU 的處理。如果任務還在運行態則將任務放回 Run Queue，否則，根據調度類要求做簡單處理。此函數通常是 pick_next_task 的密切關聯操作，是 schedule 實現的關鍵部分。
如果前一個任務屬於 CFS 調度類，則使用 CFS 調度類的具體實現 put_prev_task_fair。此時，如果任務還是 TASK_RUNNING 狀態，則被重新插入到紅黑樹的最右側。如果這個任務不是 TASK_RUNNING 狀態，則已經從紅黑樹移除過了，只需要修改 CFS 當前任務指針 cfs_rq->curr 即可。
select_task_rq
為給定的任務選擇一個 Run Queue，返回 Run Queue 所屬的 CPU 號。典型的使用場景是喚醒，fork/exec 進程時，給進程選擇一個 Run Queue，這也給調度器一個 CPU 負載均衡的機會。
對 CFS 調度器而言，主要是根據傳入的參數要求找到符合親和性要求的最空閒的 CPU 所屬的 Run Queue。
set_curr_task
當任務改變自己的調度類或者任務組時，該函數被調用。用戶進程可以使用 sched_setscheduler系統調用，通過設置自己新的調度策略來修改自己的調度類。
對 CFS 調度器而言，當任務把自己調度類從其它類型修改成 CFS 調度類，此時需要把該任務設置成正當前 CPU 正在運行的任務。例如把任務從紅黑樹上移除，設置 CFS 當前任務指針 cfs_rq->curr 和調度統計數據等。
task_tick
這個函數通常在系統周期性 (Per-tick) 的時鐘中斷上下文調用，調度類可以把 Per-tick 處理的事務交給該方法執行。例如，調度器的統計數據更新，Tick Preemption 的實現邏輯主要在這裡。Tick Preemption 主要判斷是否當前運行任務需要 Preemption 來被強制剝奪運行。
對 CFS 調度器而言，Tick Preemption 主要是在是否能滿足調度時延和是否能保證足夠任務運行時間之間來取捨。CFS 調度器也提供了預定義的 Threshold 允許做 Tick Preemption 的調優。需要進一步了解 Tick Preemption，請參考 2.1 章節。
Linux 內核的 CFS 調度算法就是通過實現該調度類結構來實現其主要邏輯的，CFS 的代碼主要集中在 kernel/sched/fair.c 源文件。下面的 sched_class 結構初始化代碼包含了本節介紹的所有方法在 CFS 調度器實現中的入口函數名稱，
const struct sched_class fair_sched_class = {
[...snipped...]
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
[...snipped...]
.check_preempt_curr = check_preempt_wakeup,
[...snipped...]
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
[...snipped...]
.select_task_rq = select_task_rq_fair,
[...snipped...]
.set_curr_task = set_curr_task_fair,
[...snipped...]
.task_tick = task_tick_fair,
[...snipped...]
};
Linux 內核為支持 Kernel Preemption 而引入了 preempt_count 計數器。如果 preempt_count 為 0，就允許 Kernel Preemption，否則就不允許。內核函數 preempt_disable 和 preempt_enable 用來內核代碼的臨界區動態關閉和打開 Kernel Preemption。其主要原理就是要通過對這個計數器的加和減來實現關閉和打開。
一般而言，打開 Kernel Preemption 特性的內核，在盡可能的情況下，允許在內核態通過 Tick Preemption 和 Wakeup Preemption 去觸發和執行 Kernel Preemption。但在以下情形，Kernel Preemption 會有關閉和打開操作，
內核顯式調用 preempt_disable 關閉搶占期間，進入中斷上下文時，preempt_count 計數器被加操作置為非零。退出中斷時打開 Kernel Preemption。獲取各種內核鎖以後，preempt_disable 被間接調用。退出內核鎖會有 preempt_enable 操作。關於preempt_disable 和 preempt_enable 的用法，請參考 Proper Locking Under a Preemptible Kernel。
早期 Linux 內核，preempt_count 是每個任務所屬的 struct thread_info 裡的一個成員，是 Per-thread 的。
而在 Linux 新內核，為了優化 Kernel Preemption 帶來的頻繁檢查 preempt_count 的開銷，Linus 和調度器的維護者決定對其做更多的優化。因此，Per-CPU preempt_count 的優化被集成到 3.13 版內核。所以，新內核的的 preempt_count 定義如下，
DECLARE_PER_CPU(int, __preempt_count);
源代碼裡有對這個計數器不同位意義的詳細說明，
/*
* We put the hardirq and softirq counter into the preemption
* counter. The bitmask has the following meaning:
*
* - bits 0-7 are the preemption count (max preemption depth: 256)
* - bits 8-15 are the softirq count (max # of softirqs: 256)
*
* The hardirq count could in theory be the same as the number of
* interrupts in the system, but we run all interrupt handlers with
* interrupts disabled, so we cannot have nesting interrupts.
* Though there are a few palaeontologic drivers which reenable
* interrupts in the handler, so we need more than one bit here.
*
* PREEMPT_MASK: 0x000000ff
* SOFTIRQ_MASK: 0x0000ff00
* HARDIRQ_MASK: 0x000f0000
* NMI_MASK: 0x00100000
* PREEMPT_ACTIVE: 0x00200000
*/
這裡要特別注意的是，如上面的注釋中所說，preempt_count 的設計時允許嵌套的。例如，
內核的鎖原語都有 preempt_disable 和 preempt_enable，而鎖是可以嵌套的。內核在拿鎖的同時，被中斷打斷，鎖和中斷進入的代碼路徑裡也會有 preempt_count 操作。在有嵌套調用的情況下，調用 preempt_enable 時 preempt_count 也不會立刻減成零。
sched: likely profiling 這個布丁的最後一個 unlikely 到 likely 的優化很好的說明了一點：
在內核裡，`preempt_enable` 在 `preempt_disable` 和中斷關閉情形下的調用比例更高。
另外要特別注意 PREEMPT_ACTIVE 位的用法，
在內核打開 Kernel Preemption 的時候，PREEMPT_ACTIVE 用來指示 __schedule 函數正確處理 Kernel Preemption 語義，防止被打斷的即將睡眠的任務被從 Run Queue 誤刪。在內核關閉 Kernel Preemption 時，雖然只有 User Preemption，cond_resched 還是利用這個標志來判斷內核調度器是否初始化完成。以上兩點在後續的 User Preemption 和 Kernel Preemption 的相關章節會展開介紹。
Preemption Overview 裡對時鐘中斷和 Tick Preemption 都有簡單的介紹。本節主要關注 Tick Preemption 在 Linux v3.19 裡的實現。
Tick Preemption 的主要邏輯都實現在調度類的 task_tick 方法裡，調度核心代碼裡並不做處理。
如前所述，Tick Preemption 主要在時鐘中斷上下文處理。從時鐘中斷處理函數到 CFS 調度類的 task_tick 方法，中間要經歷四個層次的處理。
以 x86 為例，時鐘中斷處理是 Per-CPU 的 Local APIC 定時器中斷，中斷處理函數 apic_timer_interrupt 被初始化到中斷門 IDT 的 LOCAL_TIMER_VECTOR 上。當 CPU LAPIC 時鐘中斷發生時，apic_timer_interrupt 中斷處理函數會一路調用到處理器無關的通用時鐘中斷處理函數 tick_handle_periodic，
apic_timer_interrupt->smp_apic_timer_interrupt->local_apic_timer_interrupt->tick_handle_periodic
進一步的細節請參考 arch/x86/kernel/entry_64.S 裡的 apic_timer_interrupt 匯編代碼。
特別注意 apicinterrupt 宏展開後 apic_timer_interrupt 是如何調用 smp_apic_timer_interrupt 的匯編技巧。
函數 tick_handle_periodic 在時鐘中斷的處理器平台無關層，經過一路調用，最終會進入到調度核心代碼層的 scheduler_tick 函數，
tick_handle_periodic->tick_periodic->update_process_times->scheduler_tick
內核時鐘中斷處理函數要做很多其它復雜的工作，例如，jiffies 和進程時間的維護，Per-CPU 的定時器的調用，RCU 的處理。進一步的細節請參考 kernel/time/tick-common.c 裡的 tick_handle_periodic 的實現。
函數 scheduler_tick 屬於調度核心層代碼，通過調用當前任務調度類的 task_tick 方法，進入到具體調度類的入口函數。對 CFS 調度類而言，就是 task_tick_fair，
void scheduler_tick(void)
{
[...snipped...]
curr->sched_class->task_tick(rq, curr, 0); /* CFS 調度類時，指向 task_tick_fair */
[...snipped...]
}
除了 Tick Preemption 處理，scheduler_tick 函數還做了調度時鐘維護和處理器的負載均衡等工作。進一步的細節請參考 kernel/sched/core.c 裡的 scheduler_tick 的實現。
如前所述，Linux 支持多種調度類，而且可以通過系統調用設置進程的調度類。不同調度類對 Tick Preemption 的支持可以是不同的，只需要實現 task_tick 的方法即可。本小節只關注 CFS 調度類的實現。
CFS 調度器的 task_tick_fair 會最終調用到 check_preempt_tick 來檢查是否需要 Tick Preemption，進而調用 resched_curr 申請 Preemption，
task_tick_fair->entity_tick->check_preempt_tick->resched_curr
進入到 check_preempt_tick 之前，entity_tick 需要檢查本 CPU 所屬處於運行狀態的任務數是否大於 1，只有一個運行的任務則根本沒有必要觸發 Preemption。在 check_preempt_tick 內部，主要做以下幾件事情，
調用 sched_slice 根據 Run Queue 任務數和調度延遲，任務權重計算任務理想運行時間: ideal_runtime 計算當前 CPU 上運行任務的運行時間 delta_exec進一步的細節請參考 kernel/sched/fair.c 裡的 check_preempt_tick 的實現。
如 Preemption Overview 所述，Wakeup Preemption 與 Linux 內核喚醒機制密切相關。從喚醒發生到 Wakeup Preemption，涉及到個重要的層次。
Linux 內核裡，很多同步原語都會觸發進程喚醒，典型的場景如下，
鎖退出時，喚醒其它等待鎖的任務。
例如，semaphore，mutex，futex 等機制退出時會調用 wake_up_process 或 wake_up_state 等待該鎖的任務列表裡的第一個等待任務。
等待隊列 (wait queue) 或者 completion 機制裡，喚醒其它等待在指定等待隊列 (wait queue) 或者 completion 上的一個或者多個其它任務。
Linux 定義了 wake_up 即其各種變體 主動喚醒等待隊列上的任務。
而以上各種機制觸發的喚醒任務操作最終都會進入一個共同的入口點 try_to_wake_up。
作為調度核心層代碼，try_to_wake_up 定義在 kernel/sched/core.c 原文件裡。
首先 try_to_wake_up 會使用 select_task_rq 方法為要被喚醒的任務選擇一個 Run Queue，返回目標 Run Queue 所屬的 CPU 號。然後，ttwu_queue 的代碼會判斷這個選擇的 CPU 與執行 try_to_wake_up 任務的當前運行的 CPU 是否 共享緩存 (即 LLC，最後一級 cache，x86 就是 L3 Cache)。在 Preemption Overview 的相關章節裡，針對共享緩存的兩個不同情況都做了詳細的介紹。因此，這裡只給出相關的代碼調用路徑，作為參考，
共享緩存
這類喚醒是同步的，在調用喚醒任務當前的上下文完成。從 try_to_wake_up 到調用到觸發 Wakeup Preemption 檢查的代碼路徑如下，
try_to_wake_up->ttwu_queue->ttwu_do_activate->ttwu_activate->activate_task->enqueue_task->...
|
+->ttwu_do_wakeup->check_preempt_curr->...
喚醒任務被調用具體調度類的 enqueue_task 方法插入到目標 CPU Run Queue 之後，再調用 check_preempt_curr 來檢查是否觸發 Wakeup Preemption。
不共享緩存
這類喚醒是異步的，調用喚醒任務當前的上文只是將待喚醒的任務加入到目標 CPU Run Queue 的專用喚醒隊列裡 (wake_list)，然後給目標 CPU 觸發調度處理器間中斷 (IPI) 後，立即返回，
try_to_wake_up->ttwu_queue->ttwu_queue_remote->smp_send_reschedule->...
其中 smp_send_reschedule 函數是處理器相關的調度 IPI 觸發函數，在不同處理器架構實現時不同的，下個小節會簡單介紹。
調度 IPI 觸發後，目標 CPU 會接收到該中斷，然後通過處理器相關的中斷處理函數調入到調度核心層的中斷處理函數 scheduler_ipi。在這個 scheduler_ipi 處理上下文中，任務通過 sched_ttwu_pending 調用 ttwu_activate 被插入目標 CPU Run Queue，然後最終的 Wakeup Preemption 檢查和觸發代碼會被調用，
scheduler_ipi->sched_ttwu_pending->ttwu_do_activate->ttwu_do_wakeup->check_preempt_curr->...
總之，不共享緩存的情況下，Linux 內核通過實現異步的喚醒操作，將任務實際喚醒操作的下半部分移到被喚醒任務所在 Run Queue 的 CPU 上的 IPI 中斷處理上下文中執行。這樣做的好處主要是減少同步喚醒操作的 Run Queue 鎖競爭和緩存方面的開銷。詳情請參考 sched: Move the second half of ttwu() to the remote cpu。
此外，在 try_to_wake_up 函數一進入時，還有一個特殊情況的檢查：當被喚醒任務還在 Run Queue 上沒有被刪除時 (如睡眠途中)，則代碼走如下快速處理路徑，
try_to_wake_up->ttwu_remote->ttwu_do_wakeup->check_preempt_curr->...
注意此時不需要有 Run queue 的選擇和插入操作，因此不需要調用 ttwu_do_activate，而是直接調用 ttwu_do_wakeup。
函數 check_preempt_curr 是核心調度器的代碼，主要的處理邏輯有三點，
檢查目標 Run Queue 所屬 CPU 上正在運行的任務和喚醒的任務是否同屬一個調度類
如果是相同調度類，則調用具體調度類的 check_preempt_curr 方法來處理真正的 Wakeup Preemption。如果不是相同的調度類，如果被喚醒任務的調度類優先級比當前 CPU 運行任務高，則直接調用 resched_curr 觸發 Wakeup Preemption 申請。否則，則直接退出，沒有搶占資格函數退出前檢查是否進入 check_preempt_curr 之前是否發生過隊列插入操作，並且是否 Wakeup Preemption 申請成功。
如果兩個條件都滿足，就把 skip_clock_update 置 1，這樣接下來的 __schedule 調用裡，update_rq_clock 會被調用，但在這個函數裡會跳過整個函數的處理，這算是個小小的優化。因為在插入隊列操作時，同樣的 update_rq_clock 已經被調用過了。
下面是 check_preempt_curr 的代碼，關鍵行有代碼注釋，
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); /* 具體調度類方法，CFS 的是 check_preempt_wakeup */
} else {
for_each_class(class) { /* 調度類的優先級就是鏈表的順序: DL > RT > CFS > IDLE */
if (class == rq->curr->sched_class) /* 當前 CPU 運行任務先匹配，意味著新喚醒的調度類優先級低 */
break;
if (class == p->sched_class) { /* 新喚醒的任務先匹配到，說明當前 CPU 上的優先級低 */
resched_curr(rq); /* 觸發 Wakeup Preemption */
break;
}
}
}
/*
* A queue event has occurred, and we're going to schedule. In
* this case, we can save a useless back to back clock update.
*/
if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr)) /* 滿足條件即可以跳過一次 update_rq_clock */
rq->skip_clock_update = 1;
}
上一小節裡，介紹了被喚醒任務的目標運行 CPU 和執行 try_to_wake_up 的任務所在 CPU 不共享緩存時，需要利用調度 IPI 執行異步喚醒流程。整個過程中，主要分為以下兩個階段，
前半部：觸發異步喚醒的調度 IPI
從 try_to_wake_up 一直調用到處理器相關實現 smp_send_reschedule，
try_to_wake_up->ttwu_queue->ttwu_queue_remote->smp_send_reschedule->...
以 Intel x86 平台為例，smp_send_reschedule 最終調用 smp_ops 結構的 smp_send_reschedule 方法。而 smp_send_reschedule 方法則早已被初始化成 native_smp_send_reschedule。
在 native_smp_send_reschedule 函數裡，調用 apic 的 send_IPI_mask 方法給指定 CPU 的中斷向量 RESCHEDULE_VECTOR 觸發中斷，
apic->send_IPI_mask(cpumask_of(cpu), RESCHEDULE_VECTOR);
在大於 8 個 CPU 的 x86 平台上，apic 結構的 send_IPI_mask 成員被初始化成 physflat_send_IPI_mask，
physflat_send_IPI_mask->default_send_IPI_mask_sequence_phys->__default_send_IPI_dest_field->__default_send_IPI_dest_field
而在 __default_send_IPI_dest_field 函數裡，代碼通過對 APIC_ICR 寄存器編程來觸發 IPI。
後半部：處理調度 IPI 中斷
IPI 觸發後，目標 CPU 的 Local APIC 收到中斷，陷入中斷門，而
IDT 表的 RESCHEDULE_VECTOR 向量的中斷處理入口被初始化成了 reschedule_interrupt，因此，從 reschedule_interrupt 一直會調用到 scheduler_ipi，
reschedule_interrupt->smp_reschedule_interrupt->__smp_reschedule_interrupt->scheduler_ipi->...
其中，reschedule_interrupt 調用 smp_reschedule_interrupt 的匯編技巧 與之前介紹的時鐘中斷類似。
上小節中，已經介紹了 scheduler_ipi 的代碼是通過調用 sched_ttwu_pending 來實現異步喚醒的下半部操作，並觸發 Wakeup Preemption 的。
至此，通過本節和上節的描述，我們可以清楚的知道處理器相關的調度 IPI 處理代碼是如何與調度器核心代碼緊密合作，實現異步喚醒並觸發 Wakeup Preemption 的。此外，調度 IPI 更重要的一個功能就是觸發真正的 User Preemption 和 Kernel Preemption，這部分在 Preemption Overview 已有相關說明，此處不再贅述。
本節以 CFS 調度類為例，介紹 check_preempt_curr 在 CFS 調度類裡的實現。
如前所述，在調度核心層的 check_preempt_curr 函數如果發現被喚醒的任務和正在被喚醒任務目標 CPU 上運行的任務共同屬於一個調度類，則立即調用具體調度類的 check_preempt_curr 方法。具體觸發 Wakeup Preemption 的代碼路徑如下，
check_preempt_curr->check_preempt_wakeup->resched_curr
如上所示，CFS 調度類裡，該方法的具體實現為 check_preempt_wakeup。這個函數主要做以下工作，
如果被喚醒的任務已經被目標 CPU 調度運行，立即返回。如果喚醒的任務處於被 throttled 節流狀態 (CFS 帶寬控制)，就不做搶占。因為 throttled 的任務已經睡眠。如果 NEXT_BUDDY 特性被打開，則調用 set_next_buddy 標記任務。該任務會在下次調度調用 pick_next_entity 被優先選擇。如果 TIF_NEED_RESCHED 已經被置位，則已經申請 Preemption 成功，退出。如果當前正在運行的 CFS 調度類任務的調度策略是 SCHED_IDLE，而當前被喚醒任務不是這個調度策略，則肯定當前任務有更高優先級，可以觸發 Preemption。如果被喚醒的 CFS 調度類任務的調度策略是 SCHED_BATCH 或 SCHED_IDLE，或者 Wakeup Preemption 特性沒有打開，則退出。調用 wakeup_preempt_entity 函數，判斷當前運行任務和被喚醒任務的 vruntime 的差值是否足夠大。不論是 Tick Preemption 還是 Wakeup Preemption，一旦滿足搶占條件，都會調用 resched_curr 來請求搶占。這個函數的主要功能如下，
一進入函數，檢查是否當前要搶占的 CPU 當前運行的任務已經有人標記了 TIF_NEED_RESCHED 標志，如果有，就無需重復請求搶占。檢查目標搶占的 CPU 是否是當前執行 resched_curr 的 CPU，如果是，則請求搶占當前運行任務，然後直接返回。下面是相關的代碼，
/*
* resched_curr - mark rq's current task 'to be rescheduled now'.
*
* On UP this means the setting of the need_resched flag, on SMP it
* might also involve a cross-CPU call to trigger the scheduler on
* the target CPU.
*/
void resched_curr(struct rq *rq)
{
struct task_struct *curr = rq->curr;
int cpu;
lockdep_assert_held(&rq->lock);
if (test_tsk_need_resched(curr)) /* 是否已經有人申請搶占 */
return;
cpu = cpu_of(rq);
if (cpu == smp_processor_id()) { /* 目標 CPU 與當前運行 CPU 相同 */
set_tsk_need_resched(curr); /* 標記 `TIF_NEED_RESCHED` */
set_preempt_need_resched(); /* 標記 `PREEMPT_NEED_RESCHED` */
return;
}
if (set_nr_and_not_polling(curr)) /* 是否是 IDLE 線程正在做輪詢 */
smp_send_reschedule(cpu); /* 在給定 CPU 上觸發 IPI，引起 scheduler_ipi 被執行, 間接觸發 Preemption. */
else
trace_sched_wake_idle_without_ipi(cpu);
}
如前所述，User Preemption 主要發生在以下兩類場景，
系統調用，中斷，異常時返回用戶空間時。
此處的代碼都是和處理器架構相關的，本文都以 x86 64 位 CPU 為例。
在系統調用返回用戶空間的代碼裡檢查 TIF_NEED_RESCHED 標志，決定是否調用 schedule。不論是外設中斷還是 CPU 的 APIC 中斷，都會在任務為 TASK_RUNNING 狀態時，直接或間接地調用 schedule
Linux 內核的 Kernel Preemption 沒有打開的話，除了系統調用，中斷，異常返回用戶空間時發生 Preemption，使用 cond_resched 是推薦的方式來防止內核濫用 CPU。由於這些代碼可以在只有 User Preemption 打開的時候工作，因此本文將此類代碼歸類為 User Preemption。
3.13 之前的內核版本，cond_resched 在內核代碼主動調用它時，先檢查 TIF_NEED_RESCHED 標志和 preempt_count 的 PREEMPT_ACTIVE 標志，然後再決定是否調用 schedule。這裡檢查 PREEMPT_ACTIVE 標志，只是為了阻止內核使用 cond_resched 的代碼在調度器初始化完成前執行調度。
而 3.13 引入的 per_CPU 的 preempt_count patch，則將 TIF_NEED_RESCHED 標志設置到 preempt_count 裡保存，以便一條指令就可以完成原來的兩個條件判斷。因此，TIF_NEED_RESCHED 標志檢查的代碼變成了只檢查 preempt_count。需要注意的是，雖然 preempt_count 已經包含 TIF_NEED_RESCHED 標志，但原有的 task_struct::state 的TIF_NEED_RESCHED 標志仍舊在 User Preemption 代碼裡發揮作用。
這裡不再分析 yield 的實現。但需要注意的是，內核中的循環代碼應該盡量使用 cond_resched 來讓出 CPU，而不是使用 yield。詳見 yield 的注釋。
POSIX 規范裡規定了 sched_yield(2) 調用，一些實時調度類的應用可以使用 sched_yield 讓出 CPU。內核 API yield 使用了 sched_yield 的實現。與 cond_resched 最大的不同是，yield 會使用具體調度類的 yield_task 方法。不同調度類對 yield_task 可以有很大不同。例如，SCHED_DEADLINE 調度策略裡，yield_task 方法會讓任務睡眠，這時的 sched_yield 已經不再屬於 Preemption 的范疇。
User Preemption 的代碼同樣是顯示地調用 schedule 函數，但與主動上下文切換中很大的不同是，調用 schedule 函數時，當前上下文任務的狀態還是 TASK_RUNNING。只要調用 schedule 時當前任務是 TASK_RUNNING，這時 schedule 的代碼就把這次上下文切換算作強制上下文切換，並且這次上下文切換不會涉及到把被 Preempt 任務從 Run Queue 移除操作。
下面是 schedule 代碼在 Linux 3.19 的實現，
static void __sched __schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
[...snipped...]
raw_spin_lock_irq(&rq->lock);
switch_count = &prev->nivcsw; /* 默認 switch_count 是強制上下文切換的 */
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { /* User Preemption 是 TASK_RUNNING 且無 PREEMPT_ACTIVE 置位，所以下面代碼不會執行 */
if (unlikely(signal_pending_state(prev->state, prev))) {
prev->state = TASK_RUNNING; /* 可中斷睡眠有 Pending 信號，只做上下文切換，無需從運行隊列移除 */
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP); /* 不是 TASK_RUNNING 且無 PREEMPT_ACTIVE 置位，需要從運行隊列移除 */
prev->on_rq = 0;
[...snipped...]
switch_count = &prev->nvcsw; /* 不是 TASK_RUNNING 且無 PREEMPT_ACTIVE 置位，
swtich_count 則指向主動上下文切換計數器 */
}
[...snipped...]
next = pick_next_task(rq, prev);
[...snipped...]
if (likely(prev != next)) { /* Run Queue 上真有待調度的任務才做上下文切換 */
rq->nr_switches++;
rq->curr = next;
++*switch_count; /* 此時確實發生了調度，要給 nivcsw 或者 nvcsw 計數器累加 */
rq = context_switch(rq, prev, next); /* unlocks the rq 真正上下文切換發生 */
cpu = cpu_of(rq);
} else
raw_spin_unlock_irq(&rq->lock);
從代碼可以看出，User Preemption 觸發的上下文切換，都被算作了強制上下文切換。
內核搶占需要打開特定的 Kconfig (CONFIG_PREEMPT=y)。本文只介紹引起 Kernel Preemption 的關鍵代碼。如前所述，Kernel Preemption 主要發生在以下兩類場景，
中斷和異常時返回內核空間時。
如前面章節介紹，系統調用返回不會發生 Kernel Preemption，但中斷和異常則會。
中斷和異常返回內核空間的代碼是共享同一段實現，調用 preempt_schedule_irq 來檢查 TIF_NEED_RESCHED 標志，決定是否調用 schedule。
禁止搶占上下文結束時。
內核代碼調用 preempt_enable，preempt_check_resched 和 preempt_schedule 退出禁止搶占的臨界區。下面主要針對這部分實現做詳細介紹。
如 Preemption Overview 所述，User Preemption 總是限定在任務處於 TASK_RUNNING 的幾個有限的固定時機發生。而 Kernel Preemption 發生時，任務的運行態是不可預料的，任務運行態可能處於任何運行狀態，如 TASK_UNINTERRUPTIBLE 狀態。
一個典型的例子就是，任務睡眠時要先將任務設置成睡眠態，然後再調用 schedule 來做真正的睡眠。
set_current_state(TASK_UNINTERRUPTIBLE);
/* 中斷在 schedule 之前發生，觸發 Kernel Preemption */
schedule();
設置睡眠態和 schedule 調用之間並不是原子的操作，大多時候也沒有禁止搶占和關中斷。這時 Kernel Preemption 如果正好發生在兩者之間，那麼就會造成我們所說的情況。上面的例子裡，中斷恰好在任務被設置成 TASK_UNINTERRUPTIBLE 之後發生。中斷退出後，preempt_schedule_irq 就會觸發 Kernel Preemption。
下面的例子裡，Kernel Preemption 可以發生在最後一個 spin_unlock 退出時，這時當前任務狀態是 TASK_UNINTERRUPTIBLE，
prepare_to_wait(wq, &wait.wait, TASK_UNINTERRUPTIBLE);
spin_unlock(&inode->i_lock);
spin_unlock(&inode_hash_lock); /* preempt_enable 在 spin_unlock 內部被調用 */
schedule();
不論是中斷退出代碼調用 preempt_schedule_irq， 還是 preempt_enable 調用 preempt_schedule，都會最在滿足條件時觸發 Kernel Preemption。下面以 preempt_enable 調用 preempt_schedule 為例，剖析內核代碼實現。
在內核中需要禁止搶占的臨界區代碼，直接使用 preempt_disable 和 preempt_enable 即可達到目的。關於為何以及如何禁止搶占，請參考 Proper Locking Under a Preemptible Kernel 這篇文檔。
如 Preemption Overview 所述，preempt_disable 和 preempt_enable 函數也被嵌入到很多內核函數的實現裡，例如各種鎖的進入和退出函數。
以 preempt_enable 的代碼為例，如果 preempt_count 為 0，則調用 __preempt_schedule，
而該函數會最終調用 preempt_schedule 來嘗試內核搶占。
#define preempt_enable() \
do { \
barrier(); \
if (unlikely(preempt_count_dec_and_test())) \
__preempt_schedule(); \ /* 最終會調用 preempt_schedule */
} while (0)
在 preempt_schedule 函數內部，在調用 schedule 之前，做如下檢查，
檢查 preempt_count 是否非零和 IRQ 是否處於 disabled 狀態，如果是則不允許搶占。
做這個檢查是為防止搶占的嵌套調用。例如，preempt_enable 可以在關中斷時被調用。總之，內核並不保證調用 preempt_enable 之前，總是可以被搶占的。這是因為，preempt_enable 嵌入在很多內核函數裡，可以被嵌套間接調用。此外，搶占正在進行時也能讓這種嵌套的搶占調用不會再次觸發搶占。
設置 preempt_count 的 PREEMPT_ACTIVE，避免搶占發生途中，再有內核搶占。
被搶占的進程再次返回調度點時，檢查 TIF_NEED_RESCHED 標志，如果有新的內核 Preemption 申請，則再次觸發 Kernel Preemption。
這一步驟是循環條件，直到當前 CPU 的 Run Queue 裡再也沒有申請 Preemption 的任務。
Linux v3.19 preempt_schedule 的代碼如下，
/*
* 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..
*/
if (likely(!preemptible())) /* preempt_enable 可能在被關搶占和關中斷後被嵌套調用 */
return;
do {
__preempt_count_add(PREEMPT_ACTIVE); /* 調用 schedule 前，PREEMPT_ACTIVE 被設置 */
__schedule();
__preempt_count_sub(PREEMPT_ACTIVE); /* 結束一次搶占，PREEMPT_ACTIVE 被清除 */
/*
* Check again in case we missed a preemption opportunity
* between schedule and now.
*/
barrier();
} while (need_resched()); /* 恢復執行時，檢查 TIF_NEED_RESCHED 標志是否設置 */
}
需要注意，schedule 調用前，PREEMPT_ACTIVE 標志已經被設置好了。
如前所述，進入函數調用前，PREEMPT_ACTIVE 標志已經被設置。根據當前的任務的運行狀態，我們分別做出如下分析，
當前任務是 TASK_RUNNING。
任務不會被從其所屬 CPU 的 Run Queue 上移除。這時只發生上下文切換，當前任務被下一個任務取代後在 CPU 上運行。
當前任務是其它非運行態。
繼續本節開始的例子，當前任務設置好 TASK_UNINTERRUPTIBLE 狀態，即將調用 schedule 之前被 spin_unlock 裡的 preempt_enable 調用 preempt_schedule。
由於是 Kernel Preemption 上下文，PREEMPT_ACTIVE 被設置，任務不會被從 CPU 所屬 Run Queue 移除而睡眠，這時只發生上下文切換，當前任務被下一個任務取代在 CPU 上運行。當 Run Queue 中已經處於 TASK_UNINTERRUPTIBLE 狀態的任務被調度到 CPU 上時，PREEMPT_ACTIVE 標志早被清除，因此，該任務會被 deactivate_task 從 Run Queue 上刪除，進入到睡眠狀態。
這樣的處理保證了 Kernel Preemption 的正確性，以及後續被 Preempt 任務再度被調度時的正確性，
Preemption 的本質是一種打斷引起的上下文切換，不應該處理任務的睡眠操作。
當前被 Preempt 的任務從 Run Queue 移除去睡眠的工作，本來就應該由任務自己代碼調用的 schedule 來完成。假如沒有 PREEMPT_ACTIVE 標志的檢查，那麼當前被 Preempt 任務就在 preempt_schedule 調用 schedule 時提前被從 Run Queue 移除而睡眠。這樣一來，該任務原來代碼的語義發生了變化，從任務角度看，Preemption 只是一種任務打斷，被 Preempt 任務的睡眠不應該由 preempt_schedule 的代碼來做。
Run Queue 隊列移除操作給 Kernel Preemption 的代碼路徑被增加了不必要的時延。
不但如此，這個被 Preempt 任務再次被喚醒後，該任務還未執行的 schedule 調用還會被執行一次。
下面是 schedule 的代碼，針對 Kernel Preemption 做了詳細注釋，
static void __sched __schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
[...snipped...]
raw_spin_lock_irq(&rq->lock);
switch_count = &prev->nivcsw; /* Kernel Preemption 使用強制上下文切換計數器 */
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { /* 非 TASK_RUNNING 和非 Kernel Preemption 任務才從運行隊列移除 */
if (unlikely(signal_pending_state(prev->state, prev))) {
prev->state = TASK_RUNNING; /* 可中斷睡眠有 Pending 信號，只做上下文切換，無需從運行隊列移除 */
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP); /* 非 TASK_RUNNING，非 Kernel Preemption，需要從運行隊列移除 */
prev->on_rq = 0;
[...snipped...]
switch_count = &prev->nvcsw; /* 非 TASK_RUNNING 和非 Kernel Preemption 任務使用這個計數器 */
}
}
