一文解析Linux進程調(diào)度-CFS調(diào)度器（從這三點入手~）
說明：
Kernel版本：4.14 ARM64處理器，Contex-A53，雙核 使用工具：Source Insight 3.5， Visio
1. 概述
Completely Fair Scheduler，完全公平調(diào)度器，用于Linux系統(tǒng)中普通進程的調(diào)度。
CFS采用了紅黑樹算法來管理所有的調(diào)度實體sched_entity，算法效率為O(log(n))。CFS跟蹤調(diào)度實體sched_entity的虛擬運行時間vruntime，平等對待運行隊列中的調(diào)度實體sched_entity，將執(zhí)行時間少的調(diào)度實體sched_entity排列到紅黑樹的左邊。
調(diào)度實體sched_entity通過enqueue_entity()和dequeue_entity()來進行紅黑樹的出隊入隊。
老規(guī)矩，先上張圖片來直觀了解一下原理：
每個sched_latency周期內(nèi)，根據(jù)各個任務的權重值，可以計算出運行時間runtime；
運行時間runtime可以轉(zhuǎn)換成虛擬運行時間vruntime；
根據(jù)虛擬運行時間的大小，插入到CFS紅黑樹中，虛擬運行時間少的調(diào)度實體放置到左邊；
在下一次任務調(diào)度的時候，選擇虛擬運行時間少的調(diào)度實體來運行；
【文章福利】小編推薦自己的Linux內(nèi)核技術交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?
2. 數(shù)據(jù)結(jié)構(gòu)
2.1 調(diào)度類
Linux內(nèi)核抽象了一個調(diào)度類struct sched_class，這是一種典型的面向?qū)ο蟮脑O計思想，將共性的特征抽象出來封裝成類，在實例化各個調(diào)度器的時候，可以根據(jù)具體的調(diào)度算法來實現(xiàn)。這種方式做到了高內(nèi)聚低耦合，同時又很容易擴展新的調(diào)度器。
在調(diào)度核心代碼kernel/sched/core.c中，使用的方式是task->sched_class->xxx_func，其中task表示的是描述任務的結(jié)構(gòu)體struct task_struck，在該結(jié)構(gòu)體中包含了任務所使用的調(diào)度器，進而能找到對應的函數(shù)指針來完成調(diào)用執(zhí)行，有點類似于C++中的多態(tài)機制。
2.2 rq/cfs_rq/task_struct/task_group/sched_entity
struct rq：每個CPU都有一個對應的運行隊列；
struct cfs_rq：CFS運行隊列，該結(jié)構(gòu)中包含了struct rb_root_cached紅黑樹，用于鏈接調(diào)度實體struct sched_entity。rq運行隊列中對應了一個CFS運行隊列，此外，在task_group結(jié)構(gòu)中也會為每個CPU再維護一個CFS運行隊列；
struct task_struct：任務的描述符，包含了進程的所有信息，該結(jié)構(gòu)中的struct sched_entity，用于參與CFS的調(diào)度；
struct task_group：組調(diào)度（參考前文），Linux支持將任務分組來對CPU資源進行分配管理，該結(jié)構(gòu)中為系統(tǒng)中的每個CPU都分配了struct sched_entity調(diào)度實體和struct cfs_rq運行隊列，其中struct sched_entity用于參與CFS的調(diào)度；
struct sched_entity：調(diào)度實體，這個也是CFS調(diào)度管理的對象了；
來一張圖看看它們之間的組織關系：
struct sched_entity結(jié)構(gòu)體字段注釋如下：
struct cfs_rq結(jié)構(gòu)體的關鍵字段注釋如下：
3. 流程分析
整個流程分析，圍繞著CFS調(diào)度類實體：fair_sched_class中的關鍵函數(shù)來展開。
先來看看fair_sched_class都包含了哪些函數(shù)：
3.1 runtime與vruntime
CFS調(diào)度器沒有時間片的概念了，而是根據(jù)實際的運行時間和虛擬運行時間來對任務進行排序，從而選擇調(diào)度。
那么，運行時間和虛擬運行時間是怎么計算的呢？看一下流程調(diào)用：
Linux內(nèi)核默認的sysctl_sched_latency是6ms，這個值用戶態(tài)可設。sched_period用于保證可運行任務都能至少運行一次的時間間隔；
當可運行任務大于8個的時候，sched_period的計算則需要根據(jù)任務個數(shù)乘以最小調(diào)度顆粒值，這個值系統(tǒng)默認為0.75ms；
每個任務的運行時間計算，是用sched_period值，去乘以該任務在整個CFS運行隊列中的權重占比；
虛擬運行的時間 = 實際運行時間 * NICE_0_LOAD / 該任務的權重；
還是來看一個實例吧，以5個Task為例，其中每個Task的nice值不一樣（優(yōu)先級不同），對應到的權重值在內(nèi)核中提供了一個轉(zhuǎn)換數(shù)組：
圖來了：
3.2 CFS調(diào)度tick
CFS調(diào)度器中的tick函數(shù)為task_tick_fair，系統(tǒng)中每個調(diào)度tick都會調(diào)用到，此外如果使用了hrtimer，也會調(diào)用到這個函數(shù)。
流程如下：
主要的工作包括：
更新運行時的各類統(tǒng)計信息，比如vruntime， 運行時間、負載值、權重值等；
檢查是否需要搶占，主要是比較運行時間是否耗盡，以及vruntime的差值是否大于運行時間等；
來一張圖，感受一下update_curr函數(shù)的相關信息更新吧：
3.3 任務出隊入隊
當任務進入可運行狀態(tài)時，需要將調(diào)度實體放入到紅黑樹中，完成入隊操作；
當任務退出可運行狀態(tài)時，需要將調(diào)度實體從紅黑樹中移除，完成出隊操作；
CFS調(diào)度器，使用enqueue_task_fair函數(shù)將任務入隊到CFS隊列，使用dequeue_task_fair函數(shù)將任務從CFS隊列中出隊操作。
出隊與入隊的操作中，核心的邏輯可以分成兩部分：1）更新運行時的數(shù)據(jù)，比如負載、權重、組調(diào)度的占比等等；2）將sched_entity插入紅黑樹，或者從紅黑樹移除；
由于dequeue_task_fair大體的邏輯類似，不再深入分析；
這個過程中，涉及到了CPU負載計算、task_group組調(diào)度、CFS Bandwidth帶寬控制等，這些都在前邊的文章中分析過，可以結(jié)合進行理解；
3.4 任務創(chuàng)建
在父進程通過fork創(chuàng)建子進程的時候，task_fork_fair函數(shù)會被調(diào)用，這個函數(shù)的傳入?yún)?shù)是子進程的task_struct。該函數(shù)的主要作用，就是確定子任務的vruntime，因此也能確定子任務的調(diào)度實體在紅黑樹RB中的位置。
task_fork_fair本身比較簡單，流程如下圖：
3.4 任務選擇
每當進程任務切換的時候，也就是schedule函數(shù)執(zhí)行時，調(diào)度器都需要選擇下一個將要執(zhí)行的任務。
在CFS調(diào)度器中，是通過pick_next_task_fair函數(shù)完成的，流程如下：
當需要進程任務切換的時候，pick_next_task_fair函數(shù)的傳入?yún)?shù)中包含了需要被切換出去的任務，也就是pre_task；
當pre_task不是普通進程時，也就是調(diào)度類不是CFS，那么它就不使用sched_entity的調(diào)度實體來參與調(diào)度，因此會執(zhí)行simple分支，通過put_pre_task函數(shù)來通知系統(tǒng)當前的任務需要被切換，而不是通過put_prev_entity函數(shù)來完成；
當pre_task是普通進程時，調(diào)用pick_next_entity來選擇下一個執(zhí)行的任務，這個選擇過程實際是有兩種情況：當調(diào)度實體對應task時，do while()遍歷一次，當調(diào)度實體對應task_group是，則需要遍歷任務組來選擇下一個執(zhí)行的任務了。
put_prev_entity，用于切換任務前的準備工作，更新運行時的統(tǒng)計數(shù)據(jù)，并不進行dequeue的操作，其中需要將CFS隊列的curr指針置位成NULL；
set_next_entity，用于設置下一個要運行的調(diào)度實體，設置CFS隊列的curr指針；
如果使能了hrtimer，則將hrtimer的到期時間設置為調(diào)度實體的剩余運行時間；
