1.概述 CFS（completely fair schedule）是最終被內(nèi)核采納的調(diào)度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進(jìn)程的睡眠時(shí)間，也不再企圖區(qū)分交互式進(jìn)程。它將所有的進(jìn)程都統(tǒng)一對待，這就是公平的含義。CFS的算法和實(shí)現(xiàn)都相當(dāng)簡單，眾多的測試表明其性能也非常優(yōu)越。 CFS 背后的主要想法是維護(hù)為任務(wù)提供處理器時(shí)間方面的平衡（公平性）
。這意味著應(yīng)給進(jìn)程分配相當(dāng)數(shù)量的處理器。分給某個(gè)任務(wù)的時(shí)間失去平衡時(shí)（意味著一個(gè)或多個(gè)任務(wù)相對于其他任務(wù)而言未被給予相當(dāng)數(shù)量的時(shí)間），應(yīng)給失去平衡的任務(wù)分配時(shí)間，讓其執(zhí)行。 CFS拋棄了時(shí)間片，拋棄了復(fù)雜的算法，從一個(gè)新的起點(diǎn)開始了調(diào)度器的新時(shí)代，最開始的2.6.23版本，CFS提供一個(gè)虛擬的時(shí)鐘
，所有進(jìn)程復(fù)用這個(gè)虛擬時(shí)鐘的時(shí)間，CFS將時(shí)鐘的概念從底層體系相關(guān)的硬件中抽象出來，進(jìn)程調(diào)度模塊直接和這個(gè)虛擬的時(shí)鐘接口 而不必再為硬件時(shí)鐘操作而操心
，如此一來，整個(gè)進(jìn)程調(diào)度模塊就完整了，從時(shí)鐘到調(diào)度算法，到不同進(jìn)程的不同策略，全部都由虛擬系統(tǒng)提供，也正是在這個(gè)新的內(nèi)核，引入了調(diào)度類。因此新的調(diào)度器就是不同特性的進(jìn)程在統(tǒng)一的虛擬時(shí)鐘下按照不同的策略被調(diào)度。 按照作者Ingo Molnar的說法："CFS百分之八十的工作可以用一句話概括：CFS在真實(shí)的硬件上模擬了完全理想的多任務(wù)處理器
"。在“完全理想的多任務(wù)處理器 “下，每個(gè)進(jìn)程都能同時(shí)獲得CPU的執(zhí)行時(shí)間
。當(dāng)系統(tǒng)中有兩個(gè)進(jìn)程時(shí)，CPU的計(jì)算時(shí)間被分成兩份，每個(gè)進(jìn)程獲得50%。然而在實(shí)際的硬件上，當(dāng)一個(gè)進(jìn)程占用CPU時(shí)，其它進(jìn)程就必須等待。這就產(chǎn)生了不公平。2.相關(guān)概念調(diào)度實(shí)體(sched entiy)
：就是調(diào)度的對象，可以理解為進(jìn)程。虛擬運(yùn)行時(shí)間(vruntime)
：即每個(gè)調(diào)度實(shí)體的運(yùn)行時(shí)間。任務(wù)的虛擬運(yùn)行時(shí)間越小， 意味著任務(wù)被允許訪問服務(wù)器的時(shí)間越短 — 其對處理器的需求越高。公平調(diào)度隊(duì)列(cfs_rq)
：采取公平調(diào)度的調(diào)度實(shí)體的運(yùn)行隊(duì)列。3.CFS的核心思想 全公平調(diào)度器（CFS）的設(shè)計(jì)思想是：在一個(gè)真實(shí)的硬件上模型化一個(gè)理想的、精確的多任務(wù)CPU。該理想CPU模型運(yùn)行在100%的負(fù)荷、在精確 平等速度下并行運(yùn)行每個(gè)任務(wù)，每個(gè)任務(wù)運(yùn)行在1/n速度下，即理想CPU有n個(gè)任務(wù)運(yùn)行，每個(gè)任務(wù)的速度為CPU整個(gè)負(fù)荷的1/n。 由于真實(shí)硬件上，每次只能運(yùn)行一個(gè)任務(wù)，這就得引入"虛擬運(yùn)行時(shí)間"（virtual runtime）的概念，虛擬運(yùn)行時(shí)間為一個(gè)任務(wù)在理想CPU模型上執(zhí)行的下一個(gè)時(shí)間片(timeslice)。實(shí)際上，一個(gè)任務(wù)的虛擬運(yùn)行時(shí)間為考慮到運(yùn)行任務(wù)總數(shù)的實(shí)際運(yùn)行時(shí)間。 CFS 背后的主要想法是維護(hù)為任務(wù)提供處理器時(shí)間方面的平衡（公平性）。
CFS為了體現(xiàn)的公平表現(xiàn)在2個(gè)方面(1)進(jìn)程的運(yùn)行時(shí)間相等 CFS 在叫做虛擬運(yùn)行時(shí) 的地方維持提供給某個(gè)任務(wù)的時(shí)間量。任務(wù)的虛擬運(yùn)行時(shí)越小， 意味著任務(wù)被允許訪問服務(wù)器的時(shí)間越短 — 其對處理器的需求越高。 假設(shè)runqueue中有n個(gè)進(jìn)程，當(dāng)前進(jìn)程運(yùn)行了 10ms。在“完全理想的多任務(wù)處理器”中，10ms應(yīng)該平分給n個(gè)進(jìn)程(不考慮各個(gè)進(jìn)程的nice值)，因此當(dāng)前進(jìn)程應(yīng)得的時(shí)間是(10/n)ms，但 是它卻運(yùn)行了10ms。所以CFS將懲罰當(dāng)前進(jìn)程，使其它進(jìn)程能夠在下次調(diào)度時(shí)盡可能取代當(dāng)前進(jìn)程。最終實(shí)現(xiàn)所有進(jìn)程的公平調(diào)度。(2)睡眠的進(jìn)程進(jìn)行補(bǔ)償 CFS 還包含睡眠公平概念以便確保那些目前沒有運(yùn)行的任務(wù)（例如，等待 I/O）在其最終需要時(shí)獲得相當(dāng)份額的處理器。 CFS調(diào)度器的運(yùn)行時(shí)間是O(logN)，而以前的調(diào)度器的運(yùn)行時(shí)間是O(1)，這是不是就是說CFS的效率比O(1)的更差呢？ 答案并不是那樣，我們知道 CFS調(diào)度器下的運(yùn)行隊(duì)列是基于紅黑樹組織的，找出下一個(gè)進(jìn)程就是截下左下角的節(jié)點(diǎn)，固定時(shí)間完成，所謂的O(logN)指的是插入時(shí)間，可是紅黑樹的統(tǒng) 計(jì)性能是不錯(cuò)的，沒有多大概率真的用得了那么多時(shí)間，因?yàn)榧t節(jié)點(diǎn)和黑節(jié)點(diǎn)的特殊排列方式既保證了樹的一定程度的平衡，又不至于花太多的時(shí)間來維持這種平 衡，插入操作大多數(shù)情況下都可以很快的完成，特別是對于組織得相當(dāng)好的數(shù)據(jù)。4.CFS的實(shí)現(xiàn)4.1 2.6.23 VS 2.6.25 在2.6.23內(nèi)核中，剛剛實(shí)現(xiàn)的CFS調(diào)度器顯得很淳樸，每次的時(shí)鐘滴答中都會將當(dāng)前進(jìn)程先出隊(duì)，推進(jìn)其虛擬時(shí)鐘和系統(tǒng)虛擬時(shí)鐘后再入隊(duì)，然后判斷紅黑 樹的左下角的進(jìn)程是否還是當(dāng)前進(jìn)程而抉擇是否要調(diào)度，這種調(diào)度器的key的計(jì)算是用當(dāng)前的虛擬時(shí)鐘減去待計(jì)算進(jìn)程的等待時(shí)間，如果該計(jì)算進(jìn)程在運(yùn)行，那么其等待時(shí)間就是負(fù)值，這樣，等待越長的進(jìn)程key越小，從而越容易被選中投入運(yùn)行； 在2.6.25內(nèi)核以后實(shí)現(xiàn)了一種更為簡單的方式，就是設(shè)置一個(gè)運(yùn)行隊(duì)列的虛擬時(shí)鐘，它單調(diào)增長并且跟蹤該隊(duì)列的最小虛擬時(shí)鐘的進(jìn)程，key值由進(jìn)程的vruntime和隊(duì)列的虛擬時(shí)鐘的差值計(jì)算，這種方式就是真正的追趕， 比2.6.23實(shí)現(xiàn)的簡單，但是很巧妙，不必在每次時(shí)鐘滴答中都將當(dāng)前進(jìn)程出隊(duì)，入隊(duì)，而是根據(jù)當(dāng)前進(jìn)程實(shí)際運(yùn)行的時(shí)間和理想應(yīng)該運(yùn)行的時(shí)間判斷是否應(yīng)該調(diào)度。4.2紅黑樹 與之前的 Linux 調(diào)度器不同，它沒有將任務(wù)維護(hù)在運(yùn)行隊(duì)列中，CFS 維護(hù)了一個(gè)以時(shí)間為順序的紅黑樹（參見下圖）。 紅黑樹 是一個(gè)樹，具有很多有趣、有用的屬性。首先，它是自平衡的，這意味著樹上沒有路徑比任何其他路徑長兩倍以上。 第二，樹上的運(yùn)行按 O(log n) 時(shí)間發(fā)生（其中 n 是樹中節(jié)點(diǎn)的數(shù)量）。這意味著您可以快速高效地插入或刪除任務(wù)。 
任務(wù)存儲在以時(shí)間為順序的紅黑樹中（由 sched_entity 對象表示），對處理器需求最多的任務(wù) （最低虛擬運(yùn)行時(shí)）存儲在樹的左側(cè)，處理器需求最少的任務(wù)（最高虛擬運(yùn)行時(shí)）存儲在樹的右側(cè)。 為了公平，調(diào)度器先選取紅黑樹最左端的節(jié)點(diǎn)調(diào)度為下一個(gè)以便保持公平性。任務(wù)通過將其運(yùn)行時(shí)間添加到虛擬運(yùn)行時(shí)， 說明其占用 CPU 的時(shí)間，然后如果可運(yùn)行，再插回到樹中。這樣，樹左側(cè)的任務(wù)就被給予時(shí)間運(yùn)行了，樹的內(nèi)容從右側(cè)遷移到左側(cè)以保持公平。 因此，每個(gè)可運(yùn)行的任務(wù)都會追趕其他任務(wù)以維持整個(gè)可運(yùn)行任務(wù)集合的執(zhí)行平衡。 4.3 CFS內(nèi)部原理 Linux 內(nèi)的所有任務(wù)都由稱為 task_struct 的任務(wù)結(jié)構(gòu)表示。該結(jié)構(gòu)完整地描述了任務(wù)并包括了任務(wù)的當(dāng)前狀態(tài)、其堆棧、進(jìn)程標(biāo)識、優(yōu)先級（靜態(tài)和動(dòng)態(tài)）等等。您可以在 ./linux/include/linux/sched.h 中找到這些內(nèi)容以及相關(guān)結(jié)構(gòu)。 但是因?yàn)椴皇撬腥蝿?wù)都是可運(yùn)行的，您在 task_struct 中不會發(fā)現(xiàn)任何與 CFS 相關(guān)的字段。 相反，會創(chuàng)建一個(gè)名為 sched_entity 的新結(jié)構(gòu)來跟蹤調(diào)度信息（參見下圖）。
樹的根通過 rb_root 元素通過 cfs_rq 結(jié)構(gòu)（在 ./kernel/sched.c 中）引用。紅黑樹的葉子不包含信息，但是內(nèi)部節(jié)點(diǎn)代表一個(gè)或多個(gè)可運(yùn)行的任務(wù)。紅黑樹的每個(gè)節(jié)點(diǎn)都由 rb_node 表示，它只包含子引用和父對象的顏色。 rb_node 包含在 sched_entity 結(jié)構(gòu)中，該結(jié)構(gòu)包含 rb_node 引用、負(fù)載權(quán)重以及各種統(tǒng)計(jì)數(shù)據(jù)。最重要的是， sched_entity 包含 vruntime（64 位字段），它表示任務(wù)運(yùn)行的時(shí)間量，并作為紅黑樹的索引。 最后，task_struct 位于頂端，它完整地描述任務(wù)并包含 sched_entity 結(jié)構(gòu)。 CFS 調(diào)度函數(shù)非常簡單。 在 ./kernel/sched.c 中的 schedule() 函數(shù)中，它會先搶占當(dāng)前運(yùn)行任務(wù)（除非它通過 yield() 代碼先搶占自己）。注意 CFS 沒有真正的時(shí)間切片概念用于搶占，因?yàn)閾屨紩r(shí)間是可變的。 當(dāng)前運(yùn)行任務(wù)（現(xiàn)在被搶占的任務(wù)）通過對 put_prev_task 調(diào)用（通過調(diào)度類）返回到紅黑樹。 當(dāng) schedule 函數(shù)開始確定下一個(gè)要調(diào)度的任務(wù)時(shí)，它會調(diào)用 pick_next_task 函數(shù)。此函數(shù)也是通用的（在 ./kernel/sched.c 中），但它會通過調(diào)度器類調(diào)用 CFS 調(diào)度器。 CFS 中的 pick_next_task 函數(shù)可以在 ./kernel/sched_fair.c（稱為 pick_next_task_fair()）中找到。 此函數(shù)只是從紅黑樹中獲取最左端的任務(wù)并返回相關(guān) sched_entity。通過此引用，一個(gè)簡單的 task_of() 調(diào)用確定返回的 task_struct 引用。通用調(diào)度器最后為此任務(wù)提供處理器。4.4 CFS的優(yōu)先級 CFS 不直接使用優(yōu)先級而是將其用作允許任務(wù)執(zhí)行的時(shí)間的衰減系數(shù)。 低優(yōu)先級任務(wù)具有更高的衰減系數(shù)，而高優(yōu)先級任務(wù)具有較低的衰減系數(shù)。 這意味著與高優(yōu)先級任務(wù)相比，低優(yōu)先級任務(wù)允許任務(wù)執(zhí)行的時(shí)間消耗得更快。 這是一個(gè)絕妙的解決方案，可以避免維護(hù)按優(yōu)先級調(diào)度的運(yùn)行隊(duì)列。