Linux 內核 CFS 調度器：實現高效多任務處理
FS 調度器（Completely Fair Scheduler）是 Linux 操作系統中的一種進程調度器，用於管理和分配 CPU 時間給各個運行的進程。它採用紅黑樹數據結構來維護進程的就緒隊列，並使用虛擬時鐘來進行公平的時間片分配。CFS 調度器通過動態地計算每個進程的虛擬運行時間，以及維護一個近似最小優先級隊列，從而保證了公平性和高效性。
CFS 調度器在多核處理器環境下有效地利用了 CPU 資源，根據每個進程所需的權重來分配時間片，並提供良好的響應性能。它還支持實時任務，並可以自動調節調度策略以適應系統負載變化。
CFS 簡介
CFS，即 Completely Fair Scheduler，由資深內核開發者 IngoMolnar 開發，在 2.6.23 版本的內核中併入主線，並沿用至今。按照內核文檔介紹（參考 linux-4.18 Documentation/scheduler/sched-design-CFS.txt），CFS 的設計理念用一句話概括：在真實的硬件上實現理想的、精準、完全公平的多任務調度。
CFS 調度器的目標是保證每一個進程的完全公平調度。 CFS 調度器和以往的調度器不同之處在於沒有時間片的概念，而是分配 cpu 使用時間的比例。理想狀態下每個進程都能獲得相同的時間片，並且同時運行在 CPU 上，但實際上一個 CPU 同一時刻運行的進程只能有一個。 也就是說，當一個進程佔用 CPU 時，其他進程就必須等待。CFS 爲了實現公平，必須懲罰當前正在運行的進程，以使那些正在等待的進程下次被調度。CFS 調度引入虛擬時間代替實際時間，每次在就緒隊列中選擇虛擬時間最小的 task，實現公平。
任務調度器發展
什麼是調度器（scheduler）？調度器的作用是什麼？調度器是一個操作系統的核心部分，可以比作是 CPU 時間的管理員。調度器主要負責選擇某些就緒的任務來執行。不同的調度器根據不同的方法挑選出最適合運行的任務。那麼依據什麼挑選最適合運行的任務呢？這就是每一個調度器需要關注的問題。
不同的任務有不同的需求，因此我們需要對任務進行分類：一種是普通進程，另外一種是實時進程，對於實時進程，Linux 內核的主要考慮因素是優先級，調度器總是選擇優先級最高的那個進程執行。普通進程又分爲交互式進程（IO 密集型的，等待 IO）和批處理進程（CPU 密集型的，守護進程等），交互式進程需要和用戶進行交互，因此對調度延遲比較敏感，而批處理進程屬於那種在後臺默默幹活的，因此它更注重吞吐，對調度延遲要求不高。普通進程如何細分時間片則是調度器的核心思考點。過大的時間片會嚴重損傷系統的響應延遲，讓用戶明顯能夠感知到延遲，卡頓，從而影響用戶體驗。較小的時間片雖然有助於減少調度延遲，但是頻繁的切換對系統的吞吐會造成嚴重的影響。
任務？進程？進程是資源管理的單位，線程纔是調度的單位，但線程調度器這個說法很少見，所以我們可以說任務調度器。
Linux 內核中使用一個非常大的結構體來同時表達進程和線程，即 task_struct。但是調度類管理和調度的單位是調度實體，即 sched_entity，並不是 task_struct。我們這裏只看下 task_struct 中與調度相關的字段：
struct task_struct {
/*
進程執行時，它會根據具體情況改變狀態,Linux 中的進程主要有如下狀態
TASK_RUNNING 可運行
TASK_INTERRUPTIBLE 可中斷的等待狀態
TASK_UNINTERRUPTIBLE 不可中斷的等待狀態
TASK_ZOMBIE 僵死
TASK_STOPPED 暫停
*/
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
int prio; /*動態優先級，根據靜態優先級及其他條件計算而來*/
int static_prio; /*普通進程靜態優先級，取值範圍是100（優先級最高）～139（優先級最低），分別對應nice value的-20 ～ 19。*/
int normal_prio; /*調度器綜合考慮各種因素，例如調度策略，nice value、scheduling priority等，把這些factor全部考慮進來，歸一化成一個數軸上的number，以此來表示其優先級，這就是normalized priority。對於一個線程，其normalized priority的number越小，其優先級越大。*/
unsigned int rt_priority; /*實時進程優先級*/
unsigned int policy; /*調度策略*/
const struct sched_class *sched_class; /*調度類*/
struct sched_entity se; /*普通進程調度實體*/
struct sched_rt_entity rt; /*實時進程調度實體*/
struct sched_dl_entity dl;
};不同的任務有不同的需求，因此一個系統中會共存多個調度器，目前 Linux 支持的調度器有 RT scheduler、Deadline scheduler、CFS scheduler 及 Idle scheduler 等。
針對以上調度類，系統中有明確的優先級概念。每一個調度類利用 next 成員構建單項鍊表。優先級從高到低示意圖如下：
sched_class_highest----->stop_sched_class
.next---------->dl_sched_class
.next---------->rt_sched_class
.next--------->fair_sched_class
.next----------->idle_sched_class
.next = NULLLinux 的任務調度器是不斷演進的，先後出現過三種里程碑式的調度器：
-
O(n) 調度器 內核版本 2.4-2.6
-
O(1) 調度器 內核版本 2.6.0-2.6.22
-
CFS 調度器 內核版本 2.6.23 - 至今
O(n) 調度器
O(n) 調度器採用一個全局隊列 runqueue 作爲核心數據結構，存在的問題非常多：
-
對 runqueue 隊列的遍歷的複雜度是 O(n)；
-
多個 cpu 共享全局隊列，隨着 CPU 數目增多，加鎖開銷成爲性能瓶頸；
-
實時進程和普通進程混合且無序存放
-
CPU 空轉問題：當 runqueue 鏈表中的所有進程耗盡時間片，纔會啓動新一輪對系統中所有進程時間片重新計算的過程，只要有一個 CPU 上還在運行着進程，其他 CPU 都是 idle，造成 CPU 資源的浪費
-
task bouncing issue：一般而言，一個進程最好是一直保持在同一個 CPU 上運行。隨着 runqueue 中的進程一個個的耗盡其時間片，cpu 可選擇的餘地在不斷的壓縮，從而導致進程可能在一個和它親和性不大的處理器上執行。
O(1) 調度器
O（n）調度器中只有一個全局的 runqueue，嚴重影響了擴展性，因此 O（1）調度器中引入了 per-CPU runqueue 的概念。系統中所有的可運行狀態的進程首先經過負載均衡模塊掛入各個 CPU 的 runqueue，然後由各自的調度器驅動 CPU 上的調度行爲。
由於引入了 per-CPU runqueue，O（1）調度器刪除了全局 runqueue 的 spin lock，同時把 spin lock 放入到 per-CPU runqueue 數據結構中，通過把一個大鎖細分成小鎖，可以大大降低調度延遲，提升系統響應時間。這種方法在內核中經常使用，是一個比較通用的性能優化方法。
在 Linux 2.5 版本的開發過程中，Ingo Molnar 設計的 O（1）調度器替換掉了原始的、簡陋的 O（n）調度器，從而解決了擴展性很差，性能不佳的問題。然而 O（1）並非完美，在實際的使用過程中，還是有不少的桌面用戶在抱怨交互性比較差。
在 O（n）和 O（1）調度器中，時間片是固定分配的，靜態優先級高的進程獲取更大的 time slice。例如 nice value 等於 20 的進程獲取的 default timeslice 是 5ms，而 nice value 等於 0 的進程獲取的是 100ms。直觀上，這樣的策略沒有毛病（高優先級的獲取更多的執行時間），但是，這樣的設定潛臺詞就是：高優先級的進程會獲得更多的連續執行的機會，這是 CPU-bound 進程期望的，但是實際上，CPU-bound 進程往往在後臺執行，其優先級都是比較低的。
因此，假設我們調度策略就是根據進程靜態優先級確定一個固定大小的時間片，這時候我們在如何分配時間片上會遇到兩難的狀況：想要給用戶交互型進程設定高優先級，以便它能有更好的用戶體驗，但是分配一個大的時間片是毫無意義的，因爲這種進程多半是處於阻塞態，等待用戶的輸入。而後臺進程的優先級一般不高，但是根據其優先級分配一個較小的時間片往往會影響其性能，這種類型的進程最好是趁着 cache hot 的時候狂奔。
怎麼辦？或者傳統調度器固定分配時間片這個設計概念就是錯誤的。
在反反覆覆修復用戶卡頓 issue 的過程中，很多天才工程師試圖通過修改用戶交互指數算法來解決問題，試圖去猜測進程對交互性的需求，這其實非常困難，就像收集了一個人性格特點，業餘愛好，做事風格，邏輯思維水平，星座猜。。。也很難猜測一個人的心中所想。
在進程調度這件事情上爲何不能根據實實在在確定的東西來調度呢？一個進程的靜態優先級已經完說明了其調度需求了，這就足夠了，不需要猜測進程對交互性的需求，只要維持公平就 OK 了，而所謂的公平就是進程獲取和其靜態優先級匹配的 CPU 執行時間。在這樣的思想指導下，Con Kolivas 提出了 RSDL（Rotating Staircase Deadline）調度器。
RSDL 調度器
RSDL（Rotating Staircase Deadline)）調度器仍然沿用了 O（1）調度的數據結構和軟件結構，當然刪除了那些令人毛骨悚然的評估進程交互指數的代碼。限於篇幅，這一小節只簡單瞭解下 RSDL 算法，瞭解 Rotating、Staircase 和 Deadline 這三個基本概念。
首先看 Staircase 概念，它更詳細表述應該是 priority staircase，即在進程調度過程中，其優先級會象下樓梯那樣一點點的降低。在傳統的調度概念中，一個進程有一個和其靜態優先級相匹配的時間片，在 RSDL 中，同樣也存在這樣的時間片，但是時間片是散佈在很多優先級中。例如如果一個進程的優先級是 120，那麼整個時間片散佈在 120～139 的優先級中，在一個調度週期，進程開始是掛入 120 的優先級隊列，並在其上運行 6ms（這是一個可調參數，我們假設每個優先級的時間配額是 6ms），一旦在 120 級別的時間配額使用完畢之後，該進程會轉入 121 的隊列中（優先級降低一個 level），發生一次 Rotating，更準確的說是 Priority minor rotating。之後，該進程沿階而下，直到 139 的優先級，在這個優先級上如果耗盡了 6ms 的時間片，這時候，該進程所有的時間片就都耗盡了，就會被掛入到 expired 隊列中去等待下一個調度週期。這次 rotating 被稱爲 major rotating。當然，這時候該進程會掛入其靜態優先級對應的 expired 隊列，即一切又回到了調度的起點。
Deadline 是指在 RSDL 算法中，任何一個進程可以準確的預估其調度延遲。一個簡單的例子，假設 runqueue 中有兩個 task，靜態優先級分別是 130 的 A 進程和 139 的 B 進程。對於 A 進程，只有在進程沿着優先級樓梯從 130 走到 139 的時候，B 進程纔有機會執行，其調度延遲是 9 x 6ms ＝ 54ms。
多麼簡潔的算法，只需要維持公平，沒有對進程睡眠 / 運行時間的統計，沒有對用戶交互指數的計算，沒有那些奇奇怪怪的常數…… 調度，就是這麼簡單。
調度類
從 Linux 2.6.23 開始，Linux 引入 scheduling class 的概念，目的是將調度器模塊化。這樣提高了擴展性，添加一個新的調度器也變得簡單起來。一個系統中還可以共存多個調度器。在 Linux 中，將調度器公共的部分抽象，使用 struct sched_class 結構體描述一個具體的調度類。系統核心調度代碼會通過 struct sched_class 結構體的成員調用具體調度類的核心算法。先簡單的介紹下 struct sched_class 部分成員作用。
調度類 描述 調度策略
dl_sched_class deadline 調度器 SCHED_DEADLINE
rt_sched_class 實時調度器 SCHED_FIFO、SCHED_RR
fair_sched_class 完全公平調度器 SCHED_NORMAL、SCHED_BATCH
idle_sched_class idle task SCHED_IDLE
struct sched_class {
const struct sched_class *next;//指向下一個調度類，按照優先級
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);//向該調度類的runqueue(就緒隊列)中添加進程
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);//向該調度類的runqueue(就緒隊列)中刪除進程
void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);//當一個進程被喚醒或者創建的時候，需要檢查當前進程是否可以搶佔當前cpu上正在運行的進程，如果可以搶佔需要標記TIF_NEED_RESCHED flag。
//從runqueue中選擇一個最適合運行的task
struct task_struct * (*pick_next_task)(struct rq *rq,
struct task_struct *prev,
struct rq_flags *rf);普通進程的優先級及虛擬時間
CFS 調度器針對優先級又提出了 nice 值的概念，其實和權重是一一對應的關係。nice 值就是一個具體的數字，取值範圍是 [-20, 19]。數值越小代表優先級越大，同時也意味着權重值越大，nice 值和權重之間可以互相轉換。內核提供了一個表格轉換 nice 值和權重。
const int sched_prio_to_weight[40] = {
7527 /* -20 */ 88761, 71755, 56483, 46273, 36291,
7528 /* -15 */ 29154, 23254, 18705, 14949, 11916,
7529 /* -10 */ 9548, 7620, 6100, 4904, 3906,
7530 /* -5 */ 3121, 2501, 1991, 1586, 1277,
7531 /* 0 */ 1024, 820, 655, 526, 423,
7532 /* 5 */ 335, 272, 215, 172, 137,
7533 /* 10 */ 110, 87, 70, 56, 45,
7534 /* 15 */ 36, 29, 23, 18, 15,
7535};虛擬運行時間是通過進程的實際運行時間和進程的權重（weight）計算出來的。在 CFS 調度器中，將進程優先級這個概念弱化，而是強調進程的權重。一個進程的權重越大，則說明這個進程更需要運行，因此它的虛擬運行時間就越小，這樣被調度的機會就越大
虛擬運行時間的計算公式：
vriture_runtime = wall_time * 1024/weight
virtue_runtime — 虛擬運行時間
wall_time - 實際運行時間由公式可以看出 nice 爲 0 的 virtue_time 與 time 一致，且 weight 越大，相同的實際運行時間下，虛擬時間越小，越會被調度。下圖給實際運行時間，虛擬運行時間，nice 值之間的關係：
系統中使用 struct load_weight 結構體描述進程的權重信息。weight 代表進程的權重，inv_weight 等於 2^ 32/weight。
struct load_weight {
unsigned long weight;
u32 inv_weight;
};Linux 中有哪些調度類
Linux 中主要包含 dl_sched_class、rt_sched_class、fair_sched_class 及 idle_sched_class 等調度類。每一個進程都對應一種調度策略，每一種調度策略又對應一種調度類（每一個調度類可以對應多種調度策略）。例如實時調度器以優先級爲導向選擇優先級最高的進程運行。每一個進程在創建之後，總是要選擇一種調度策略。針對不同的調度策略，選擇的調度器也是不一樣的。不同的調度策略對應的調度類如下表：
針對以上調度類，系統中有明確的優先級概念。每一個調度類利用 next 成員構建單項鍊表。優先級從高到低示意圖如下：
sched_class_highest----->stop_sched_class
.next---------->dl_sched_class
.next---------->rt_sched_class
.next--------->fair_sched_class
.next----------->idle_sched_class
.next = NULLLinux 調度核心在選擇下一個合適的 task 運行的時候，會按照優先級的順序便利調度類的 pick_next_task 函數。因此，SCHED_FIFO 調度策略的實時進程永遠比 SCHED_NORMAL 調度策略的普通進程優先運行。代碼中 pick_next_task 函數也有體現。pick_next_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;
for_each_class(class) { /* 按照優先級順序便利所有的調度類，通過next指針便利單鏈表 */
p = class->pick_next_task(rq, prev, rf);
if (p)
return p;
}
}針對 CFS 調度器，管理的進程都屬於 SCHED_NORMAL 或者 SCHED_BATCH 策略。
普通進程的優先級
CFS 是 Completely Fair Scheduler 簡稱，即完全公平調度器。CFS 的設計理念是在真實硬件上實現理想的、精確的多任務 CPU。CFS 調度器和以往的調度器不同之處在於沒有時間片的概念，而是分配 cpu 使用時間的比例。例如：2 個相同優先級的進程在一個 cpu 上運行，那麼每個進程都將會分配 50% 的 cpu 運行時間。這就是要實現的公平。
以上舉例是基於同等優先級的情況下。但是現實卻並非如此，有些任務優先級就是比較高。那麼 CFS 調度器的優先級是如何實現的呢？首先，我們引入權重的概念，權重代表着進程的優先級。各個進程之間按照權重的比例分配 cpu 時間。例如：2 個進程 A 和 B。A 的權重是 1024，B 的權重是 2048。那麼 A 獲得 cpu 的時間比例是 1024/(1024+2048) = 33.3%。B 進程獲得的 cpu 時間比例是 2048/(1024+2048)=66.7%。我們可以看出，權重越大分配的時間比例越大，相當於優先級越高。在引入權重之後，分配給進程的時間計算公式如下：
分配給進程的時間 = 總的 cpu 時間 * 進程的權重 / 就緒隊列（runqueue）所有進程權重之和
CFS 調度器針對優先級又提出了 nice 值的概念，其實和權重是一一對應的關係。nice 值就是一個具體的數字，取值範圍是 [-20, 19]。數值越小代表優先級越大，同時也意味着權重值越大，nice 值和權重之間可以互相轉換。內核提供了一個表格轉換 nice 值和權重。
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,
};數組的值可以看作是公式：weight = 1024 / 1.25^nice 計算得到。公式中的 1.25 取值依據是：進程每降低一個 nice 值，將多獲得 10% cpu 的時間。公式中以 1024 權重爲基準值計算得來，1024 權重對應 nice 值爲 0，其權重被稱爲 NICE_0_LOAD。默認情況下，大部分進程的權重基本都是 NICE_0_LOAD。
調度延遲
什麼是調度延遲？調度延遲就是保證每一個可運行進程都至少運行一次的時間間隔。例如，每個進程都運行 10ms，系統中總共有 2 個進程，那麼調度延遲就是 20ms。如果有 5 個進程，那麼調度延遲就是 50ms。如果現在保證調度延遲不變，固定是 6ms，那麼系統中如果有 2 個進程，那麼每個進程運行 3ms。如果有 6 個進程，那麼每個進程運行 1ms。如果有 100 個進程，那麼每個進程分配到的時間就是 0.06ms。隨着進程的增加，每個進程分配的時間在減少，進程調度過於頻繁，上下文切換時間開銷就會變大。因此，CFS 調度器的調度延遲時間的設定並不是固定的。當系統處於就緒態的進程少於一個定值（默認值 8）的時候，調度延遲也是固定一個值不變（默認值 6ms）。當系統就緒態進程個數超過這個值時，我們保證每個進程至少運行一定的時間才讓出 cpu。這個 “至少一定的時間” 被稱爲最小粒度時間。在 CFS 默認設置中，最小粒度時間是 0.75ms。用變量 sysctl_sched_min_granularity 記錄。因此，調度週期是一個動態變化的值。調度週期計算函數是__sched_period()。
static u64 __sched_period(unsigned long nr_running)
{
if (unlikely(nr_running > sched_nr_latency))
return nr_running * sysctl_sched_min_granularity;
else
return sysctl_sched_latency;
}nr_running 是系統中就緒進程數量，當超過 sched_nr_latency 時，我們無法保證調度延遲，因此轉爲保證調度最小粒度。如果 nr_running 並沒有超過 sched_nr_latency，那麼調度週期就等於調度延遲 sysctl_sched_latency（6ms）。
虛擬時間（virtual time）
CFS 調度器的目標是保證每一個進程的完全公平調度。CFS 調度器就像是一個母親，她有很多個孩子（進程）。但是，手上只有一個玩具（cpu）需要公平的分配給孩子玩。假設有 2 個孩子，那麼一個玩具怎麼纔可以公平讓 2 個孩子玩呢？簡單點的思路就是第一個孩子玩 10 分鐘，然後第二個孩子玩 10 分鐘，以此循環下去。CFS 調度器也是這樣記錄每一個進程的執行時間，保證每個進程獲取 CPU 執行時間的公平。因此，哪個進程運行的時間最少，應該讓哪個進程運行。
NICE_0_LOAD
vriture_runtime = wall_time * ----------------
weight進程 A 的虛擬時間 3.3 * 1024 / 1024 = 3.3ms，我們可以看出 nice 值爲 0 的進程的虛擬時間和實際時間是相等的。進程 B 的虛擬時間是 2.7 * 1024 / 820 = 3.3ms。我們可以看出儘管 A 和 B 進程的權重值不一樣，但是計算得到的虛擬時間是一樣的。因此 CFS 主要保證每一個進程獲得執行的虛擬時間一致即可。在選擇下一個即將運行的進程的時候，只需要找到虛擬時間最小的進程即可。爲了避免浮點數運算，因此我們採用先放大再縮小的方法以保證計算精度。
內核又對公式做了如下轉換：
NICE_0_LOAD
vriture_runtime = wall_time * ----------------
weight
NICE_0_LOAD * 2^32
= (wall_time * -------------------------) >> 32
weight
2^32
= (wall_time * NICE_0_LOAD * inv_weight) >> 32 (inv_weight = ------------ )
weight權重的值已經計算保存到 sched_prio_to_weight 數組中，根據這個數組我們可以很容易計算 inv_weight 的值。內核中使用 sched_prio_to_wmult 數組保存 inv_weight 的值。計算公式是：sched_prio_to_wmult[i] = 232/sched_prio_to_weight[i]。
const u32 sched_prio_to_wmult[40] = {
/* -20 */ 48388, 59856, 76040, 92818, 118348,
/* -15 */ 147320, 184698, 229616, 287308, 360437,
/* -10 */ 449829, 563644, 704093, 875809, 1099582,
/* -5 */ 1376151, 1717300, 2157191, 2708050, 3363326,
/* 0 */ 4194304, 5237765, 6557202, 8165337, 10153587,
/* 5 */ 12820798, 15790321, 19976592, 24970740, 31350126,
/* 10 */ 39045157, 49367440, 61356676, 76695844, 95443717,
/* 15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};系統中使用 struct load_weight 結構體描述進程的權重信息。weight 代表進程的權重，inv_weight 等於 232/weight。
struct load_weight {
unsigned long weight;
u32 inv_weight;
};將實際時間轉換成虛擬時間的實現函數是 calc_delta_fair()。calc_delta_fair() 調用__calc_delta() 函數，__calc_delta() 主要功能是實現如下公式的計算。
__calc_delta() = (delta_exec * weight * lw->inv_weight) >> 32
weight 2^32
= delta_exec * ---------------- (lw->inv_weight = --------------- )
lw->weight lw->weight和上面計算虛擬時間計算公式對比發現。如果需要計算進程的虛擬時間，這裏的 weight 只需要傳遞參數 NICE_0_LOAD，lw 參數是進程對應的 struct load_weight 結構體。
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
u64 fact = scale_load_down(weight);
int shift = 32;
__update_inv_weight(lw);
if (unlikely(fact >> 32)) {
while (fact >> 32) {
fact >>= 1;
shift--;
}
}
fact = (u64)(u32)fact * lw->inv_weight;
while (fact >> 32) {
fact >>= 1;
shift--;
}
return mul_u64_u32_shr(delta_exec, fact, shift);
}按照上面說的理論，calc_delta_fair() 函數調用__calc_delta() 的時候傳遞的 weight 參數是 NICE_0_LOAD，lw 參數是進程對應的 struct load_weight 結構體。
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD)) /* 1 */
delta = __calc_delta(delta, NICE_0_LOAD, &se->load); /* 2 */
return delta;
}-
就不用計算。
-
調用__calc_delta() 函數。
Linux 通過 struct task_struct 結構體描述每一個進程。但是調度類管理和調度的單位是調度實體，並不是 task_struct。在支持組調度的時候，一個組也會抽象成一個調度實體，它並不是一個 task。所以，我們在 struct task_struct 結構體中可以找到以下不同調度類的調度實體。
struct task_struct {
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;
/* ... */
}se、rt、dl 分別對應 CFS 調度器、RT 調度器、Deadline 調度器的調度實體。
struct sched_entity 結構體描述調度實體，包括 struct load_weight 用來記錄權重信息。除此以外我們一直關心的時間信息，肯定也要一起記錄。struct sched_entity 結構體簡化後如下：
struct sched_entity {
struct load_weight load;
struct rb_node run_node;
unsigned int on_rq;
u64 sum_exec_runtime;
u64 vruntime;
};-
load：權重信息，在計算虛擬時間的時候會用到 inv_weight 成員。
-
run_node：CFS 調度器的每個就緒隊列維護了一顆紅黑樹，上面掛滿了就緒等待執行的 task，run_node 就是掛載點。
-
on_rq：調度實體 se 加入就緒隊列後，on_rq 置 1。從就緒隊列刪除後，on_rq 置 0。
-
sum_exec_runtime：調度實體已經運行實際時間總合。
-
vruntime：調度實體已經運行的虛擬時間總合。
調度實體
Linux 通過 struct task_struct 結構體描述每一個進程。但是調度類管理和調度的單位是調度實體，並不是 task_struct。在支持組調度的時候，一個組也會抽象成一個調度實體，它並不是一個 task。所以，我們在 struct task_struct 結構體中可以找到以下不同調度類的調度實體。
struct task_struct {
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;
/* ... */
}
struct sched_entity {
struct load_weight load;//權重信息
struct rb_node run_node;//就緒隊列紅黑樹上的掛載點
unsigned int on_rq;//調度實體se加入就緒隊列後，on_rq標誌置爲1，從就緒隊列刪除,on_rq置爲0
u64 sum_exec_runtime;//調度實體已經運行的實際時間總和
u64 vruntime;//調度實體已經運行的虛擬時間總和
};就緒隊列
系統中每個 CPU 都會有一個全局的就緒隊列（cpu runqueue），使用 struct rq 結構體描述，它是 per-cpu 類型，即每個 cpu 上都會有一個 struct rq 結構體。每一個調度類也有屬於自己管理的就緒隊列。例如，struct cfs_rq 是 CFS 調度類的就緒隊列，管理就緒態的 struct sched_entity 調度實體，後續通過 pick_next_task 接口從就緒隊列中選擇最適合運行的調度實體（虛擬時間最小的調度實體）。struct rt_rq 是實時調度器就緒隊列。struct dl_rq 是 Deadline 調度器就緒隊列。
struct rq {
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
};
struct rb_root_cached {
struct rb_root rb_root;//紅黑樹的根節點
struct rb_node *rb_leftmost;//紅黑樹的最左邊節點
};
struct cfs_rq {
struct load_weight load;//就緒隊列管理的所有調度實體權重之和
unsigned int nr_running;//調度實體的個數
u64 min_vruntime;//就緒隊列上的最小虛擬時間
struct rb_root_cached tasks_timeline;//就緒隊列紅黑樹的信息
};CFS 調度器實現
Linux 中所有的進程使用 task_struct 描述。task_struct 包含很多進程相關的信息（例如，優先級、進程狀態以及調度實體等）。但是，每一個調度類並不是直接管理 task_struct，而是引入調度實體的概念。CFS 調度器使用 sched_entity 跟蹤調度信息。
CFS 調度器使用 cfs_rq 跟蹤就緒隊列信息以及管理就緒態調度實體，並維護一棵按照虛擬時間排序的紅黑樹。tasks_timeline->rb_root 是紅黑樹的根，tasks_timeline->rb_leftmost 指向紅黑樹中最左邊的調度實體，即虛擬時間最小的調度實體（爲了更快的選擇最適合運行的調度實體，因此 rb_leftmost 相當於一個緩存）。
每個就緒態的調度實體 sched_entity 包含插入紅黑樹中使用的節點 rb_node，同時 vruntime 成員記錄已經運行的虛擬時間。我們將這幾個數據結構簡單梳理，如下圖所示：
源碼分析
流程分析
整個流程分析，圍繞着 CFS 調度類實體：fair_sched_class 中的關鍵函數來展開。
先來看看 fair_sched_class 都包含了哪些函數：
/* All the scheduling class methods: */
const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.yield_to_task = yield_to_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.migrate_task_rq = migrate_task_rq_fair,
.rq_online = rq_online_fair,
.rq_offline = rq_offline_fair,
.task_dead = task_dead_fair,
.set_cpus_allowed = set_cpus_allowed_common,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_fork = task_fork_fair,
.prio_changed = prio_changed_fair,
.switched_from = switched_from_fair,
.switched_to = switched_to_fair,
.get_rr_interval = get_rr_interval_fair,
.update_curr = update_curr_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.task_change_group = task_change_group_fair,
#endif
};(1)runtime 與 vruntime
CFS 調度器沒有時間片的概念了，而是根據實際的運行時間和虛擬運行時間來對任務進行排序，從而選擇調度。那麼，運行時間和虛擬運行時間是怎麼計算的呢？看一下流程調用：
Linux 內核默認的 sysctl_sched_latency 是 6ms，這個值用戶態可設。sched_period 用於保證可運行任務都能至少運行一次的時間間隔；(2) 當可運行任務大於 8 個的時候，sched_period 的計算則需要根據任務個數乘以最小調度顆粒值，這個值系統默認爲 0.75ms；(3) 每個任務的運行時間計算，是用 sched_period 值，去乘以該任務在整個 CFS 運行隊列中的權重佔比；(4) 虛擬運行的時間 = 實際運行時間 * NICE_0_LOAD / 該任務的權重；
從上面計算公式可以看出，權重高的進程運行時間 runtime 更大，但是 vruntime 由於分子分母互相消除，權重高的進程的虛擬運行時間的增速卻是一樣的。
還是來看一個實例吧，以 5 個 Task 爲例，其中每個 Task 的 nice 值不一樣（優先級不同），對應到的權重值在內核中提供了一個轉換數組：
/*權重只和進程的nice值有關*/
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,
};從 sched_prio_to_weight[] 可知，nice 值每減小 1，權重增加約 25%，一個調度週期中大約可以多獲得 25% 的 CPU 時間。
圖來了：
(2)CFS 調度 tick
CFS 調度器中的 tick 函數爲 task_tick_fair，系統中每個調度 tick 都會調用到，此外如果使用了 hrtimer，也會調用到這個函數。流程如下：
主要的工作包括：
-
(1) 更新運行時的各類統計信息，比如 vruntime， 運行時間、負載值、權重值等；
-
(2) 檢查是否需要搶佔，主要是比較運行時間是否耗盡，以及 vruntime 的差值是否大於運行時間等；
來一張圖，感受一下 update_curr 函數的相關信息更新吧：
/*註冊這些定時器中斷*/
arch_timer_register(void) //drivers\clocksource\arm_arch_timer.c
irqreturn_t timer_handler(const int access, struct clock_event_device *evt) //drivers\clocksource\arm_arch_timer.c
evt->event_handler(evt);
tick_device_uses_broadcast(struct clock_event_device *dev, int cpu) //kernel\time\tick-broadcast.c
tick_handle_periodic(struct clock_event_device *dev) //kernel\time\tick-common.c
tick_periodic(int cpu) //kernel\time\tick-common.c
/*在定時器中斷處理函數中調用，user_tick若是用戶時間爲1，若是系統時間爲0*/
update_process_times(int user_tick) //kernel\time\timer.c
/*這個函數是在定時器的代碼中被調用，調用週期爲HZ，關着中斷調用的*/
scheduler_tick(void) //kernel\sched\core.c
/*切換到高分辨率模式*/
hrtimer_switch_to_hres(void)
tick_setup_sched_timer(void) //kernel\time\tick-sched.c
tick_sched_timer(struct hrtimer *timer) //kernel\time\tick-sched.c
tick_sched_handle(struct tick_sched *ts, struct pt_regs *regs) //kernel\time\tick-sched.c
update_process_times(user_mode(regs));
tick_nohz_switch_to_nohz(void)
/*nohz低分辨率中斷處理函數*/
tick_nohz_handler(struct clock_event_device *dev)
tick_sched_handle(struct tick_sched *ts, struct pt_regs *regs) //kernel\time\tick-sched.c
update_process_times(user_mode(regs));(3) 任務出隊入隊
-
當任務進入可運行狀態時，需要將調度實體放入到紅黑樹中，完成入隊操作；
-
當任務退出可運行狀態時，需要將調度實體從紅黑樹中移除，完成出隊操作（移除後放在哪？）；
-
CFS 調度器，使用 enqueue_task_fair 函數將任務入隊到 CFS 隊列，使用 dequeue_task_fair 函數將任務從 CFS 隊列中出隊操作。
出隊與入隊的操作中，核心的邏輯可以分成兩部分：
-
1）更新運行時的數據，比如負載、權重、組調度的佔比等等；
-
2）將 sched_entity 插入紅黑樹，或者從紅黑樹移除；
(2) 由於 dequeue_task_fair 大體的邏輯類似，不再深入分析；
(3) 這個過程中，涉及到了 CPU 負載計算、task_group 組調度、CFS Bandwidth 帶寬控制等，這些都在前邊的文章中分析過，可以結合進行理解；
(4) 任務創建
在父進程通過 fork 創建子進程的時候，task_fork_fair 函數會被調用，這個函數的傳入參數是子進程的 task_struct。該函數的主要作用，就是確定子任務的 vruntime，因此也能確定子任務的調度實體在紅黑樹 RB 中的位置。
task_fork_fair 本身比較簡單，流程如下圖：
(5) 任務選擇
每當進程任務切換的時候，也就是 schedule 函數執行時，調度器都需要選擇下一個將要執行的任務。在 CFS 調度器中，是通過 pick_next_task_fair 函數完成的，流程如下：
-
(1) 當需要進程任務切換的時候，pick_next_task_fair 函數的傳入參數中包含了需要被切換出去的任務，也就是 pre_task；
-
(2) 當 pre_task 不是普通進程時，也就是調度類不是 CFS，那麼它就不使用 sched_entity 的調度實體來參與調度，因此會執行 simple 分支，通過 put_pre_task 函數來通知系統當前的任務需要被切換，而不是通過 put_prev_entity 函數來完成；
-
(3) 當 pre_task 是普通進程時，調用 pick_next_entity 來選擇下一個執行的任務，這個選擇過程實際是有兩種情況：當調度實體對應 task 時，do while() 遍歷一次，當調度實體對應 task_group 時，則需要遍歷任務組來選擇下一個執行的任務了。
-
(4) put_prev_entity，用於切換任務前的準備工作，更新運行時的統計數據，並不進行 dequeue 的操作，其中需要將 CFS 隊列的 curr 指針置位成 NULL；
-
(5) set_next_entity，用於設置下一個要運行的調度實體，設置 CFS 隊列的 curr 指針；
-
(6) 如果使能了 hrtimer，則將 hrtimer 的到期時間設置爲調度實體的剩餘運行時間；
-
(7) 調度類的優先級體現在 pick_next_task 函數中。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/9WNfVQIRAp5H_oD_xM7FgA