前言

早期的Linux調度器采用了簡化的設計，顯然并不針對具有許多處理器甚至超線程的大規模架構。Linux 1.2調度器使用循環隊列對可運行任務進行管理，并采用循環調度策略。這個調度器對于添加和刪除進程非常高效（使用鎖來保護結構）。簡而言之，這個調度器并不復雜，但簡單且快速。

Linux 2.2版本引入了調度類的概念，允許為實時任務、非可搶占任務和非實時任務設置調度策略。2.2調度器還包括對對稱多處理（SMP）的支持。

2.4內核包含了一個相對簡單的調度器，它在O(N)時間內運行（因為它在每個調度事件中迭代所有任務）。2.4調度器將時間劃分為時期，在每個時期內，每個任務都可以執行其時間片的時間。如果一個任務沒有使用完其時間片，那么剩余時間片的一半將被添加到新的時間片中，以使其在下一個時期中執行時間更長。調度器只需要迭代任務，應用一個好度函數（度量）來確定下一個要執行的任務。盡管這種方法相對簡單，但它相對低效，缺乏可擴展性，并且對于實時系統來說并不強大。它也缺乏利用新的硬件架構（如多核處理器）的功能。

早期的2.6調度器被稱為O(1)調度器，旨在解決2.4調度器的許多問題。即調度器不需要迭代整個任務列表來確定下一個要調度的任務（因此得名O(1)，表示它更高效且可擴展性更好）。O(1)調度器通過在一個運行隊列中跟蹤可運行任務（實際上，對于每個優先級級別，有兩個運行隊列，一個用于活動任務，一個用于過期任務），這意味著為了確定下一個要執行的任務，調度器只需從特定的活動優先級運行隊列中出隊即可。O(1)調度器具有更好的可擴展性，并結合了交互性指標和許多啟發式方法，以確定任務是I/O綁定還是處理器綁定。但是O(1)調度器在內核中變得臃腫。用于計算啟發式方法的大量代碼基本上難以管理，并且對于純粹主義者來說，缺乏算法實質。

面對O(1)調度器及其他外部壓力，需要進行一些改變。這種改變來自于Con Kolivas的內核補丁，其中包括他之前在階梯調度器上的工作，引入了他的Rotating Staircase Deadline Scheduler (RSDL)。這項工作的結果是一個簡單設計的調度器，將公平性與有界延遲相結合。Kolivas的調度器給很多人留下了深刻印象（有人呼吁將其納入當前的2.6.21主線內核），因此可以明顯看到調度器的改變正在途中。接著，O(1)調度器的創建者Ingo Molnar基于Kolivas的工作思想開發了CFS。

CFS（Completely Fair Scheduler）是Linux操作系統中的一種新的進程調度器，與其競爭對手RSDL相比，CFS的選擇在某些圈子中引起了很大爭議。為了澄清發生了什么以及CFS相對于舊調度器的作用，需要一些歷史背景。

在Linux 2.5的開發過程中，來自Ingo Molnar的’O(1)'進程調度器（PS）被合并以取代從2.4繼承的調度器。O(1) PS的設計旨在解決2.4調度器存在的可擴展性問題 - 性能改進非常顯著，以至于O(1) PS成為商業Linux發行版中最常被反向移植到2.4的特性之一。然而，負責調度進程的算法并沒有發生太大改變，因為它們被認為是“足夠好”，或者至少沒有被視為關鍵問題。但是，這些算法在用戶所感知的“交互性”方面可能會產生巨大影響。例如，如果一個或多個進程開始執行無限循環，并且由于這些占用CPU的循環進程，調度器沒有為已經存在的負責實現用戶界面（如X.org、kicker、firefox、openoffice.org等）的非循環進程分配足夠的CPU時間，用戶會感覺這些程序對用戶的操作反應不夠流暢。更糟糕的是，在音樂播放器的情況下，你的音樂可能會出現跳躍。

O(1)進程調度器PS和之前的調度器一樣，試圖改善這些情況，并且大多數時候表現良好。然而，許多用戶報告了一些特殊情況和非特殊情況，新的調度器并沒有按預期工作。其中一個用戶是Con Kolivas，盡管他在內核編程領域沒有經驗，但他試圖微調調度算法，而不是替換它們。他的工作取得了成功，他的補丁被納入了主內核，其他人（Mike Galbraith、Davide Libenzi、Nick Piggin）也幫助調整了調度器。但并非所有特殊情況都消失了，當嘗試修復其中一個問題時，可能會出現新問題。Con發現，“交互性估計器”——PS用來嘗試判斷哪些進程更具“交互性”，因此需要更多關注，以便用戶感知其桌面更具“交互性”的一段代碼，引發了比解決問題更多的問題。與其原始目的相反，交互性估計器無法解決PS中存在的所有“交互性”問題，而且嘗試修復一個問題可能會導致另一個問題的出現。這是一個典型的算法使用統計數據和啟發式方法來預測未來并在其上失敗的案例。Con設計了一個名為RSDL的新的調度器，它取消了交互性估計代碼。相反，他的調度器基于“公平性”的概念：進程被平等對待，并被分配相同的時間片（有關此調度器的更多細節，請參閱LWN文章：https://lwn.net/Articles/224865/）。這個調度器在這些特殊情況下改善了用戶所感知的“交互性”。

這個PS原本打算合并，但Ingo Molnar（O(1)的創建者）創建了另一個名為CFS（完全公平調度器）的新的PS，其中一個基本設計元素是Con的PS證明了“公平調度”的優越性。CFS得到了一些黑客的好評，這幫助Ingo使CFS成為主線內核的一個很好的進程調度器替代方案。'公平性’是RSDL和CFS之間唯一共享的概念，這也是它們的相似之處終止的地方，甚至’公平性’的定義也非常不同：RSDL使用了’嚴格’的公平性定義。但是CFS將任務的睡眠時間包括在公平性指標中：這意味著在CFS中，睡眠任務（通常運行用戶感覺為’交互式’的代碼，如X.org、mp3播放器等）獲得比運行任務更多的CPU時間（與RSDL的’嚴格公平性’不同，RSDL對它們采用嚴格的公平性處理），但這一切都受到公平性引擎的控制。這種設計兼顧了公平性和交互性，但沒有使用交互性估計器。

CFS相對于舊的主線調度器和RSDL還有其他一些不同之處：它使用一個按時間順序排列的紅黑樹（time-ordered rbtree）來構建未來任務執行的’時間軸’，以嘗試避免常規調度器和RSDL調度器可能出現的’數組切換’問題。CFS還使用納秒級粒度的計時，并且不依賴于任何滴答數或其他HZ細節；實際上，它沒有傳統的’timeslices’概念：切片決策是動態的，而不是靜態的，并且切片沒有持久性（即切片不是以傳統意義上的方式’給予’任務并被任務’消耗’），因為CFS能夠通過納秒級計時準確追蹤任務的完整執行歷史。

最終，CFS被選擇作為當前’O(1)'進程調度器的替代品，而不是RSDL。必須指出的是，無論是RSDL還是CFS，它們都是比主線內核中的調度器更好的調度器，而正是Con首創了使用’公平性’的概念而不是’交互性估計’的想法，但這并不意味著CFS不應該作為主線內核進程調度器的最終替代品被合并；這也不意味著RSDL不是一個很好的替代品。

可以看到CFS調度器是用來解決交互性進程響應快慢的問題，更適用于桌面操作系統；對于服務器來說，更注重吞吐性，CFS調度器和O1調度器沒啥差別。

在一個混雜著大量計算型進程和IO交互進程的系統中，CFS調度器對待IO交互進程要比O(1)調度器更加友善和公平。

O(1)調度器直接將優先級線性映射到了時間片（進程的優先級和進程可運行的時間片進行了強映射），以表示差異化。
CFS調度器則直接將進程優先級映射到了CPU時間份額，以表示差異化。

優先級和時間片本來就是兩個概念，二者中間還得有個變量溝通才可以。優先級高只是說明該進程能運行的久一些，但是到底久多少，并不是僅僅優先級就能決定的，還要綜合考慮，換句話距離來說，如果只有一個進程，那么即便它優先級再低，它也可以永久運行，如果系統中有很多的進程，即便再高優先級的進程也要讓出一些時間給其它進程。

CFS考慮到系統中總體的進程情況，將優先級轉換為權重，將時間片轉換為份額。最終的坐標系應該是 權重占比/時間片 坐標系而不是 權重(或者優先級)/時間片 。

CFS的時間片是動態的，是系統負載均衡以及其優先級的函數，這便可以把進程調度動態適應到系統最佳，以節省切換開銷。

一、概要

CFS（Completely Fair Scheduler）是由Ingo Molnar實現并在Linux 2.6.23中合并的新的“桌面”進程調度器。它是對以前的普通調度器（vanilla scheduler）的SCHED_OTHER互動性代碼的替代。

CFS的設計中，80%可以用一句話總結：CFS基本上在真實硬件上模擬了一個“理想的、精確的多任務CPU”。

“理想的多任務CPU”是一個（不存在的) CPU，它具有100%的物理能力，并且可以以精確相等的速度并行運行每個任務，每個任務運行在1/nr_running的速度上。例如，如果有2個任務正在運行，那么它會以每個任務50%的物理能力運行，也就是實際上是并行運行。

在真實硬件上，我們一次只能運行一個任務，因此我們必須引入“虛擬運行時間”的概念。任務的虛擬運行時間指定了它在上述理想多任務CPU上下一個時間片開始執行的時間。實際上，任務的虛擬運行時間是其實際運行時間與正在運行的任務總數的歸一化結果。

CFS（完全公平調度器）的主要思想是在為任務提供處理器時間時保持平衡（公平性）。這意味著進程應該被給予公平的處理器時間。當任務的時間不平衡（意味著一個或多個任務與其他任務相比沒有得到公平的時間）時，那些不平衡的任務應該被給予執行的時間。

為了確定平衡，CFS維護了所謂的虛擬運行時間，即為給定任務提供的時間量。任務的虛擬運行時間越小（意味著任務被允許訪問處理器的時間越少），它對處理器的需求就越高。CFS還包括了“睡眠公平性”的概念，以確保當前不可運行的任務（例如，等待I/O的任務）在它們最終需要處理器時能夠獲得相當的份額。

但與以前的Linux調度器在運行隊列中維護任務不同，CFS維護一個按時間排序的紅黑樹（如下圖所示）。紅黑樹是一種具有一些有趣和有用屬性的樹。首先，它是自平衡的，這意味著樹中的任意路徑長度都不會超過其他路徑長度的兩倍。其次，對樹的操作在O(log n)的時間內完成（其中n是樹中節點的數量）。這意味著您可以快速高效地插入或刪除一個任務。

在按時間排序的紅黑樹中存儲任務（表示為sched_entity對象），具有最迫切需要處理器的任務（虛擬運行時間最低）存儲在樹的左側，而對處理器需求最小的任務（虛擬運行時間最高）存儲在樹的右側。為了保持公平性，調度器選擇紅黑樹的最左邊的節點作為下一個要調度的任務，以保持公平性。任務通過將其執行時間添加到虛擬運行時間來記錄其在CPU上的時間，如果可運行，則重新插入到樹中。通過這種方式，樹的左側的任務被給予執行時間，并且樹的內容從右側向左側遷移，以保持公平性。因此，每個可運行的任務都會追逐其他任務，以在可運行任務集合中保持執行的平衡。

二、實現

2.1 簡介

CFS有一些有趣的方面。首先，它完全取消了運行隊列數組的使用。相反，CFS使用單個紅黑樹來跟蹤所有處于可運行狀態的進程。在樹的最左節點出現的進程是在任何給定時間最有資格運行的進程。因此，理解這個調度器的關鍵是了解它如何計算用于將進程插入樹中的鍵值。

這個計算相當簡單。當一個任務進入運行隊列時，記錄下當前時間。當進程等待CPU時，調度器跟蹤它本應獲得的處理器時間量；這個權益簡單地是等待時間除以運行進程數（根據不同優先級值進行修正）。在實際情況下，鍵值是進程應獲得的CPU時間量，而較高優先級的進程會稍微獲得提升。因此，進程的短期優先級將根據它是否獲得了公平的處理器份額而變化。

只是略微簡化地說，上述討論涵蓋了CFS調度器的全部內容。它沒有跟蹤睡眠時間，也沒有嘗試識別交互式進程等等。從某種意義上說，CFS調度器甚至取消了時間片的概念；一切都取決于給定進程是否獲得了根據試圖運行的進程數而應得的CPU份額。CFS調度器提供了一個可調整的參數："granularity"值，用于描述調度器為了保持公平性而切換進程的速度。較低的granularity值會導致更頻繁的切換；這個設置會降低交互響應的延遲，但可能會稍微降低吞吐量。服務器系統可能會在較高的granularity值下運行得更好。

2.2 算法實現

在CFS中，虛擬運行時間通過每個任務的p->se.vruntime（納秒單位）值來表示和跟蹤。通過這種方式，可以準確地記錄和測量任務應該獲得的“預期CPU時間”。

一個小細節是，在“理想”的硬件上，任何時候所有任務的p->se.vruntime值都相同，也就是說，任務會同時執行，沒有任務會從“理想”的CPU時間份額中“失衡”。

CFS的任務選擇邏輯基于p->se.vruntime值，因此非常簡單：它總是嘗試運行具有最小p->se.vruntime值的任務（即到目前為止執行最少的任務）。CFS始終盡可能地將CPU時間在可運行的任務之間分配得接近“理想的多任務硬件”。

CFS的大部分設計都是基于這個非常簡單的概念。

CFS的設計非常激進：它不使用舊的運行隊列數據結構，而是使用一個按時間排序的紅黑樹來構建未來任務執行的“時間線”，因此沒有“數組切換”現象（這會影響到以前的普通調度器和RSDL/SD）。

CFS還維護了rq->cfs.min_vruntime值，它是一個單調遞增的值，跟蹤運行隊列中所有任務中最小的vruntime。系統完成的總工作量通過min_vruntime來跟蹤；該值被用于盡可能將新激活的實體放在樹的左側。

運行隊列中正在運行的任務總數通過rq->cfs.load值來統計，該值是排隊在運行隊列上的任務權重的總和。

CFS維護了一個按時間排序的紅黑樹，其中所有可運行的任務按照p->se.vruntime鍵進行排序。CFS從這棵樹中選擇“最左邊”的任務并堅持執行。隨著系統的前進，執行的任務被逐漸放置到樹的右側，以便給每個任務一個機會成為“最左邊的任務”，從而在確定的時間內獲得CPU時間。

總結起來，CFS的工作方式如下：它運行一個任務一小段時間，當任務調度（或發生調度器時鐘中斷）時，任務的CPU使用情況被“記賬”：剛剛使用物理CPU的時間被添加到p->se.vruntime中。一旦p->se.vruntime變得足夠高，以至于另一個任務成為它維護的按時間排序的紅黑樹的“最左邊的任務”（加上一小段與最左邊任務的“粒度”距離，以避免過度調度任務和緩存垃圾），則選擇新的最左邊任務并搶占當前任務。

2.3 內核源碼

在Linux中，所有任務都由一個名為task_struct的任務結構表示。該結構（以及與之相關的其他結構）完整描述了任務，包括任務的當前狀態、堆棧、進程標志、優先級（靜態和動態）等等。但是，由于并非所有任務都是可運行的，因此在task_struct中找不到與CFS相關的字段。相反，創建了一個名為sched_entity的新結構來跟蹤調度信息。

// linux-4.10.1/include/linux/sched.hstruct sched_entity {struct load_weight	load;		/* for load-balancing */struct rb_node		run_node;struct list_head	group_node;unsigned int		on_rq;......u64			vruntime;	
}struct task_struct {......struct sched_entity se;	......
}

sched_entity結構用于存儲任務的調度信息，包括任務的虛擬運行時間、調度實體的優先級以及其他與CFS調度器相關的字段。通過sched_entity結構，CFS可以跟蹤每個任務的運行時間和調度狀態，并根據任務的需求進行公平調度。

各種結構之間的關系如上圖所示。樹的根節點通過cfs_rq結構中的rb_root元素進行引用。紅黑樹中的葉子節點不包含任何信息，但內部節點表示一個或多個可運行的任務。紅黑樹中的每個節點都由一個rb_node表示，其中只包含子節點的引用和父節點的顏色信息。rb_node包含在sched_entity結構中，該結構包括rb_node引用、負載權重和各種統計數據。最重要的是，sched_entity包含一個64位的vruntime字段，用于表示任務運行的時間量，并作為紅黑樹的索引。最后，task_struct位于頂部，完整描述了任務，并包含sched_entity結構。

三、特點

CFS的設計非常激進：它不使用運行隊列，而是使用一個按時間排序的rbtree來構建未來任務執行的“時間軸”，因此沒有“數組切換”現象（這是原始調度器和RSDL/SD所受影響的）。

CFS使用納秒級的精確度進行計算，不依賴于任何jiffies或其他HZ細節。因此，CFS調度器沒有像以前的調度器那樣關于“時間片”的概念，并且沒有任何啟發式規則。中心可調參數為"/proc/sys/kernel/sched_granularity_ns"，可以用來根據不同的工作負載從"桌面"（低延遲）到"服務器"（良好批處理）進行調整。默認設置適用于桌面工作負載，并且還處理SCHED_BATCH工作負載。

CFS保證的是每時每刻的公平，cfs依據的是進程的執行時間，利用的是補償原理，cfs讓進程先超前運 行，然后補償別的進程，這樣很合理。另外cfs不用任何啟發算法，只是一個虛擬時鐘就夠了，因為當進程睡眠的時候，其虛擬時鐘就不走了，這樣當然落后于別 的進程的虛擬時鐘，理應得到補償。

可以用來調整調度器以適應“桌面”（即低延遲）到“服務器”（即良好批處理）負載。它的默認設置適用于桌面工作負載。CFS調度器模塊也處理SCHED_BATCH。

CFS調度器對于nice級別和SCHED_BATCH的處理比以前的普通調度器更強大：這兩種類型的工作負載被更積極地隔離。

負載平衡代碼在對稱多處理（SMP）系統中進行了重新設計和清理。代碼不再依賴于運行隊列遍歷的假設，而是使用來自調度模塊的迭代器。這個改變簡化了負載平衡代碼。

引入了調度類（Scheduling Classes）：這是一個可擴展的調度程序模塊層次結構。這些模塊封裝了調度策略的細節，并由調度器核心處理，而核心代碼對它們的假設不過多。

該模塊以比原始調度器更簡單的方式實現了SCHED_FIFO和SCHED_RR的語義。它使用100個運行隊列來處理所有100個實時（RT）優先級級別，而不是原始調度器的140個運行隊列。它也不需要一個過期數組。

四、調度策略

CFS（完全公平調度器）實現了三種調度策略：
（1）SCHED_NORMAL（傳統上稱為SCHED_OTHER）：這是用于常規任務的調度策略。它用于普通任務的默認調度策略。

（2）SCHED_BATCH：相比于常規任務，該策略不會頻繁地進行搶占，從而允許任務運行更長時間并更好地利用緩存，但代價是降低了交互性。這非常適合批處理作業。

（3）SCHED_IDLE：該策略比nice 19的任務優先級還要低，但它不是一個真正的空閑定時器調度器，以避免陷入優先級反轉問題，這可能導致系統死鎖。

五、調度類

CFS發布還帶來了一個意外的特性，幾乎讓所有關注內核開發領域的人感到驚訝：一個模塊化調度器框架。Ingo將其描述為"一個可擴展的調度器模塊層次結構"，但是，如果是這樣的話，它是一個沒有分支的層次結構。它是一個按優先級順序排列的模塊簡單鏈表；第一個能夠提供可運行任務的調度器模塊將決定下一個運行的進程。

新的CFS調度器的設計引入了“調度類（Scheduling Classes）”，這是一種可擴展的調度器模塊層次結構。這些模塊封裝了調度策略的細節，并由調度器核心處理，核心代碼不會對它們做過多的假設。

調度類通過sched_class結構來實現，該結構包含了在發生事件時必須調用的函數鉤子。

// kernel/sched/sched.hstruct sched_class {const struct sched_class *next;void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);void (*yield_task) (struct rq *rq);bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);/** It is the responsibility of the pick_next_task() method that will* return the next task to call put_prev_task() on the @prev task or* something equivalent.** May return RETRY_TASK when it finds a higher prio class has runnable* tasks.*/struct task_struct * (*pick_next_task) (struct rq *rq,struct task_struct *prev,struct pin_cookie cookie);void (*put_prev_task) (struct rq *rq, struct task_struct *p);......
}

● Stop○ No policy
● Deadline○ SCHED_DEADLINE
● Real Time○ SCHED_FIFO○ SCHED_RR
● Fair○ SCHED_NORMAL○ SCHED_BATCH○ SCHED_IDLE
● Idle○ No policy

以下是這些函數鉤子的（部分）列表：

enqueue_task(…)

當任務進入可運行狀態時調用。它將調度實體（任務）放入紅黑樹中，并增加nr_running變量。

dequeue_task(…)

當任務不再可運行時，調用此函數將相應的調度實體從紅黑樹中移除。它減少nr_running變量。

yield_task(…)

除非啟用了compat_yield sysctl，否則此函數基本上只是一個dequeue，然后是一個enqueue操作；在這種情況下，它將調度實體放置在紅黑樹的最右端。

wakeup_preempt(…)

此函數檢查進入可運行狀態的任務是否應該搶占當前正在運行的任務。

pick_next_task(…)

此函數選擇下一個合適的可運行任務。

set_next_task(…)

當任務更改其調度類、更改其任務組或被調度時，調用此函數。

task_tick(…)

此函數主要從時間滴答函數中調用；它可能導致進程切換。它驅動運行搶占。

參考資料

Linux 4.10.0
https://www.kernel.org/doc/html/latest/scheduler/sched-design-CFS.html
https://kernelnewbies.org/Linux_2_6_23#The_CFS_process_scheduler
https://lwn.net/Articles/230574/
https://developer.ibm.com/tutorials/l-completely-fair-scheduler/

https://blog.csdn.net/dog250/article/details/95729830
https://blog.csdn.net/dog250/article/details/96500186
https://zhuanlan.zhihu.com/p/659215677