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