Linux内核作為一個通用的操作系統（OS），需要兼顧各種各樣類型的進程，包括實時進程、交互式進程、批處理進程等。而調度器（Scheduler）作為OS的核心組件——CPU時間的管理器，主要負責選擇某些就緒的進程來執行。不同的調度器根據不同的方法挑選出最适合運行的進程。目前，在Linux内核中支持的調度器有CFS調度器、Realtime調度器、Deadline調度器和Idle調度器 。本篇将簡單介紹CFS調度器的設計原理。

CFS （完全公平調度器）實現的主要思想是維護為任務提供處理器時間方面的平衡（公平性），這意味着應給進程分配相當數量的處理器。分給某個任務的時間失去平衡時（意味着一個或多個任務相對于其他任務而言未被給予相當數量的時間），應給失去平衡的任務分配時間，讓其執行。

CFS通過虛拟運行時間（vruntime）來實現平衡，維護提供給某個任務的時間量。進程的虛拟時間是指實際運行時間相對于權重為0的進程的比例值。在CFS調度器中有一個計算虛拟時間的核心函數calc_delta_fair(),它的計算公式為：

vruntime = 實際運行時間*1024 / 進程權重

因此，進程按照各自不同的速率在物理時鐘節拍内前進，優先級高則權重大，其虛拟時鐘比真實時鐘跑得慢，但獲得比較多的運行時間；反之，優先級低則權重小，其虛拟時鐘比真實時鐘跑得快，反而獲得比較少的運行時間。CFS調度器總是選擇虛拟時鐘跑得慢的進程來運行，從而讓每個調度實體（sche_entity）的虛拟運行時間互相追趕，進而實現進程調度上的平衡。

CFS調度器沒有将進程維護在運行隊列中，而是維護了一個以虛拟運行時間為順序的紅黑樹。 紅黑樹的主要特點有：

1. 自平衡，樹上沒有一條路徑會比其他路徑長出倆倍。
2. O(log n) 時間複雜度，能夠在樹上進行快速高效地插入或删除進程。

如圖所示，進程存儲在以vruntime排序的紅黑樹中，對處理器需求最多的任務 （vruntime最低）存儲在樹的左側，處理器需求最少的進程（vruntime最高）存儲在樹的右側。為了保證公平性，調度器每次選取紅黑樹最左端的進程進行調度。

CFS的内部原理大緻為如圖所示：

Linux内的所有任務都由稱為 task_struct 的任務結構表示，它位于調度的最頂端。該結構（在./linux/include/linux/sched.h）完整地描述了任務并包括了任務的當前狀态、其堆棧、進程标識、優先級（靜态和動态）等等。

更多linux内核視頻教程文檔資料免費領取後台私信【内核】自行獲取.

Linux内核源碼/内存調優/文件系統/進程管理/設備驅動/網絡協議棧-學習視頻教程-騰訊課堂

struct task_struct{ 　　... 　　volatile long state; 　　void *stack; 　　unsigned int flags; 　　int prio; 　　int static_prio; 　　int normal_prio; 　　struct sche_entity se; 　　... };

但是，由于不是所有任務都是可運行的，所以在task_struct中不會發現任何與CFS相關的字段。因此，需要通過一個名為 sched_entity 的新結構來跟蹤調度信息。

struct sched_entity{ 　　... 　　struct load_weight load; 　　struct rb_node run_node; 　　struct list_head group_node; 　　u64 vruntime; 　　... }; sched_entity包含負載權重、各種統計數據以及vruntime（任務運行的虛拟時間量，并作為紅黑樹的索引）。同時，sched_entity還包含紅黑樹的節點rb_node。 struct rb_node{ 　　unsigned long __rb_parent_color; 　　struct rb_node *rb_right; 　　struct rb_node *rb_left; }; 紅黑樹的每個節點都由 rb_node 表示，它隻包含子引用和父對象的顔色。紅黑樹的葉子不包含信息，但是内部節點代表一個或多個可運行的任務。紅黑樹的根通過rb_root_cached結構中的rb_root引用，而該結構同時包含了紅黑樹的最左節點rb_leftmost的指針。 struct rb_root_cached{ 　　struct rb_root rb_root; 　　struct rb_node *rb_leftmost; };

在運行過程中，__schedule()（在./kernel/sched/core.c中）是CFS調度器的核心函數，其作用是讓調度器選擇和切換到一個合适的進程運行。在時鐘周期開始時，調度器調用__schedule()函數來開始調度的運行。然後，__schedule()函數調用pick_next_task()讓進程調度器從就緒隊列中選擇一個最合适的進程next，即紅黑樹最左邊的節點。接着，通過context_switch()切換到新的地址空間，從而保證next進程運行。在時鐘周期結束時，調度器調用entity_tick()函數來更新進程負載、進程狀态以及vruntime（當前vruntime 該時鐘周期内運行的時間）。最後，将該進程的虛拟時間與就緒隊列紅黑樹中最左邊的調度實體的虛拟時間做比較，如果小于坐左邊的時間，則不用觸發調度，繼續調度當前調度實體。否則，則表明最左邊的調度實體更需要調度。因此，調度器将當前調度實體放回紅黑樹，并選擇紅黑樹中最左邊的調度實體作為next在下一個時鐘周期進行調度。通過以上的結構和調度方式，Linux内核保證了操作系統中進程調度的公平性。

- - 内核技術中文網 - 構建全國最權威的内核技術交流分享論壇

轉載地址：講解Linux内核CFS調度器！ - 圈點 - 内核技術中文網 - 構建全國最權威的内核技術交流分享論壇

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!