背景
Read the fucking source code!--By 魯迅A picture is worth a thousand words.--By 高爾基
說明：
- Kernel版本：4.14
- ARM64處理器，Contex-A53，雙核
- 使用工具：Source Insight 3.5， Visio
1. 概述
Completely Fair Scheduler，完全公平調度器，用于Linux系統中普通行程的調度，CFS采用了紅黑樹演算法來管理所有的調度物體sched_entity，演算法效率為O(log(n))，CFS跟蹤調度物體sched_entity的虛擬運行時間vruntime，平等對待運行佇列中的調度物體sched_entity，將執行時間少的調度物體sched_entity排列到紅黑樹的左邊，- 調度物體
sched_entity通過enqueue_entity()和dequeue_entity()來進行紅黑樹的出隊入隊，
老規矩，先上張圖片來直觀了解一下原理：
- 每個
sched_latency周期內，根據各個任務的權重值，可以計算出運行時間runtime； - 運行時間
runtime可以轉換成虛擬運行時間vruntime； - 根據虛擬運行時間的大小，插入到CFS紅黑樹中，虛擬運行時間少的調度物體放置到左邊；
- 在下一次任務調度的時候，選擇虛擬運行時間少的調度物體來運行；
在開始本文之前，建議先閱讀下（一）Linux行程調度器-基礎，
開始探索之旅！
2. 資料結構
2.1 調度類
Linux內核抽象了一個調度類struct sched_class，這是一種典型的面向物件的設計思想，將共性的特征抽象出來封裝成類，在實體化各個調度器的時候，可以根據具體的調度演算法來實作，這種方式做到了高內聚低耦合，同時又很容易擴展新的調度器，
- 在調度核心代碼
kernel/sched/core.c中，使用的方式是task->sched_class->xxx_func，其中task表示的是描述任務的結構體struct task_struck，在該結構體中包含了任務所使用的調度器，進而能找到對應的函式指標來完成呼叫執行，有點類似于C++中的多型機制，
2.2 rq/cfs_rq/task_struct/task_group/sched_entity
struct rq：每個CPU都有一個對應的運行佇列；struct cfs_rq：CFS運行佇列，該結構中包含了struct rb_root_cached紅黑樹，用于鏈接調度物體struct sched_entity，rq運行佇列中對應了一個CFS運行佇列，此外，在task_group結構中也會為每個CPU再維護一個CFS運行佇列；struct task_struct：任務的描述符，包含了行程的所有資訊，該結構中的struct sched_entity，用于參與CFS的調度；struct task_group：組調度（參考前文），Linux支持將任務分組來對CPU資源進行分配管理，該結構中為系統中的每個CPU都分配了struct sched_entity調度物體和struct cfs_rq運行佇列，其中struct sched_entity用于參與CFS的調度；struct sched_entity：調度物體，這個也是CFS調度管理的物件了；
來一張圖看看它們之間的組織關系：
struct sched_entity結構體欄位注釋如下：
struct sched_entity {
/* For load-balancing: */
struct load_weight load; //調度物體的負載權重值
struct rb_node run_node; //用于連接到CFS運行佇列的紅黑樹中的節點
struct list_head group_node; //用于連接到CFS運行佇列的cfs_tasks鏈表中的節點
unsigned int on_rq; //用于表示是否在運行佇列中
u64 exec_start; //當前調度物體的開始執行時間
u64 sum_exec_runtime; //調度物體執行的總時間
u64 vruntime; //虛擬運行時間，這個時間用于在CFS運行佇列中排隊
u64 prev_sum_exec_runtime; //上一個調度物體運行的總時間
u64 nr_migrations; //負載均衡
struct sched_statistics statistics; //統計資訊
#ifdef CONFIG_FAIR_GROUP_SCHED
int depth; //任務組的深度，其中根任務組的深度為0，逐級往下增加
struct sched_entity *parent; //指向調度物體的父物件
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq; //指向調度物體歸屬的CFS佇列，也就是需要入列的CFS佇列
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q; //指向歸屬于當前調度物體的CFS佇列，用于包含子任務或子的任務組
#endif
#ifdef CONFIG_SMP
/*
* Per entity load average tracking.
*
* Put into separate cache line so it does not
* collide with read-mostly values above.
*/
struct sched_avg avg ____cacheline_aligned_in_smp; //用于調度物體的負載計算（`PELT`）
#endif
};
- struct cfs_rq結構體的關鍵欄位注釋如下：
/* CFS-related fields in a runqueue */
struct cfs_rq {
struct load_weight load; //CFS運行佇列的負載權重值
unsigned int nr_running, h_nr_running; //nr_running：運行的調度物體數（參與時間片計算）
u64 exec_clock; //運行時間
u64 min_vruntime; //最少的虛擬運行時間，調度物體入隊出隊時需要進行增減處理
#ifndef CONFIG_64BIT
u64 min_vruntime_copy;
#endif
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).
*/
struct sched_entity *curr, *next, *last, *skip; //分別指向當前運行的調度物體、下一個調度的調度物體、CFS運行佇列中排最后的調度物體、跳過運行的調度物體
#ifdef CONFIG_SCHED_DEBUG
unsigned int nr_spread_over;
#endif
#ifdef CONFIG_SMP
/*
* CFS load tracking
*/
struct sched_avg avg; //計算負載相關
u64 runnable_load_sum;
unsigned long runnable_load_avg; //基于PELT的可運行平均負載
#ifdef CONFIG_FAIR_GROUP_SCHED
unsigned long tg_load_avg_contrib; //任務組的負載貢獻
unsigned long propagate_avg;
#endif
atomic_long_t removed_load_avg, removed_util_avg;
#ifndef CONFIG_64BIT
u64 load_last_update_time_copy;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/*
* h_load = weight * f(tg)
*
* Where f(tg) is the recursive weight fraction assigned to
* this group.
*/
unsigned long h_load;
u64 last_h_load_update;
struct sched_entity *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */
#ifdef CONFIG_FAIR_GROUP_SCHED
struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */ //指向CFS運行佇列所屬的CPU RQ運行佇列
/*
* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
* a hierarchy). Non-leaf lrqs hold other higher schedulable entities
* (like users, containers etc.)
*
* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
* list is used during load balance.
*/
int on_list;
struct list_head leaf_cfs_rq_list;
struct task_group *tg; /* group that "owns" this runqueue */ //CFS運行佇列所屬的任務組
#ifdef CONFIG_CFS_BANDWIDTH
int runtime_enabled; //CFS運行佇列中使用CFS帶寬控制
u64 runtime_expires; //到期的運行時間
s64 runtime_remaining; //剩余的運行時間
u64 throttled_clock, throttled_clock_task; //限流時間相關
u64 throttled_clock_task_time;
int throttled, throttle_count; //throttled：限流，throttle_count：CFS運行佇列限流次數
struct list_head throttled_list; //運行佇列限流鏈表節點，用于添加到cfs_bandwidth結構中的cfttle_cfs_rq鏈表中
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};
3. 流程分析
整個流程分析，圍繞著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
};
3.1 runtime與vruntime
CFS調度器沒有時間片的概念了，而是根據實際的運行時間和虛擬運行時間來對任務進行排序，從而選擇調度，
那么，運行時間和虛擬運行時間是怎么計算的呢？看一下流程呼叫：
- Linux內核默認的
sysctl_sched_latency是6ms，這個值用戶態可設，sched_period用于保證可運行任務都能至少運行一次的時間間隔； - 當可運行任務大于8個的時候，
sched_period的計算則需要根據任務個數乘以最小調度顆粒值，這個值系統默認為0.75ms； - 每個任務的運行時間計算，是用
sched_period值，去乘以該任務在整個CFS運行佇列中的權重占比； - 虛擬運行的時間 = 實際運行時間 * NICE_0_LOAD / 該任務的權重；
還是來看一個實體吧，以5個Task為例，其中每個Task的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,
};
圖來了：
3.2 CFS調度tick
CFS調度器中的tick函式為task_tick_fair，系統中每個調度tick都會呼叫到，此外如果使用了hrtimer，也會呼叫到這個函式，
流程如下：
主要的作業包括：
- 更新運行時的各類統計資訊，比如
vruntime， 運行時間、負載值、權重值等； - 檢查是否需要搶占，主要是比較運行時間是否耗盡，以及
vruntime的差值是否大于運行時間等；
來一張圖，感受一下update_curr函式的相關資訊更新吧：
3.3 任務出隊入隊
- 當任務進入可運行狀態時，需要將調度物體放入到紅黑樹中，完成入隊操作；
- 當任務退出可運行狀態時，需要將調度物體從紅黑樹中移除，完成出隊操作；
- CFS調度器，使用
enqueue_task_fair函式將任務入隊到CFS佇列，使用dequeue_task_fair函式將任務從CFS佇列中出隊操作，
- 出隊與入隊的操作中，核心的邏輯可以分成兩部分：1）更新運行時的資料，比如負載、權重、組調度的占比等等；2）將sched_entity插入紅黑樹，或者從紅黑樹移除；
- 由于
dequeue_task_fair大體的邏輯類似，不再深入分析； - 這個程序中，涉及到了
CPU負載計算、task_group組調度、CFS Bandwidth帶寬控制等，這些都在前邊的文章中分析過，可以結合進行理解；
3.3 任務創建
在父行程通過fork創建子行程的時候，task_fork_fair函式會被呼叫，這個函式的傳入引數是子行程的task_struct，該函式的主要作用，就是確定子任務的vruntime，因此也能確定子任務的調度物體在紅黑樹RB中的位置，
task_fork_fair本身比較簡單，流程如下圖：
3.4 任務選擇
每當行程任務切換的時候，也就是schedule函式執行時，調度器都需要選擇下一個將要執行的任務，
在CFS調度器中，是通過pick_next_task_fair函式完成的，流程如下：
- 當需要行程任務切換的時候，
pick_next_task_fair函式的傳入引數中包含了需要被切換出去的任務，也就是pre_task； - 當
pre_task不是普通行程時，也就是調度類不是CFS，那么它就不使用sched_entity的調度物體來參與調度，因此會執行simple分支，通過put_pre_task函式來通知系統當前的任務需要被切換，而不是通過put_prev_entity函式來完成； - 當
pre_task是普通行程時，呼叫pick_next_entity來選擇下一個執行的任務，這個選擇程序實際是有兩種情況：當調度物體對應task時，do while()遍歷一次，當調度物體對應task_group是，則需要遍歷任務組來選擇下一個執行的任務了， put_prev_entity，用于切換任務前的準備作業，更新運行時的統計資料，并不進行dequeue的操作，其中需要將CFS佇列的curr指標置位成NULL；- set_next_entity，用于設定下一個要運行的調度物體，設定CFS佇列的
curr指標； - 如果使能了
hrtimer，則將hrtimer的到期時間設定為調度物體的剩余運行時間；
暫且分析到這吧，CFS調度器涵蓋的內容還是挺多的，fair.c一個檔案就有將近一萬行代碼，相關內容的分析也分散在前邊的文章中了，感興趣的可以去看看，
打完收工，洗洗睡了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/126982.html
標籤：Linux
上一篇：作業系統-行程同步與信號量