|
1.概述 CFS（completely fair schedule）是最終被內(nèi)核采納的調(diào)度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區(qū)分交互式進程。它將所有的進程都統(tǒng)一對待，這就是公平的含義。CFS的算法和實現(xiàn)都相當(dāng)簡單，眾多的測試表明其性能也非常優(yōu)越。 CFS 背后的主要想法是維護為任務(wù)提供處理器時間方面的平衡（公平性）。這意味著應(yīng)給進程分配相當(dāng)數(shù)量的處理器。分給某個任務(wù)的時間失去平衡時（意味著一個或多個任務(wù)相對于其他任務(wù)而言未被給予相當(dāng)數(shù)量的時間），應(yīng)給失去平衡的任務(wù)分配時間，讓其執(zhí)行。 CFS拋棄了時間片，拋棄了復(fù)雜的算法，從一個新的起點開始了調(diào)度器的新時代，最開始的2.6.23版本，CFS提供一個虛擬的時鐘，所有進程復(fù)用這個虛擬時鐘的時間，CFS將時鐘的概念從底層體系相關(guān)的硬件中抽象出來，進程調(diào)度模塊直接和這個虛擬的時鐘接口 而不必再為硬件時鐘操作而操心，如此一來，整個進程調(diào)度模塊就完整了，從時鐘到調(diào)度算法，到不同進程的不同策略，全部都由虛擬系統(tǒng)提供，也正是在這個新的內(nèi)核，引入了調(diào)度類。因此新的調(diào)度器就是不同特性的進程在統(tǒng)一的虛擬時鐘下按照不同的策略被調(diào)度。 按照作者Ingo Molnar的說法："CFS百分之八十的工作可以用一句話概括：CFS在真實的硬件上模擬了完全理想的多任務(wù)處理器"。在“完全理想的多任務(wù)處理器 “下，每個進程都能同時獲得CPU的執(zhí)行時間。當(dāng)系統(tǒng)中有兩個進程時，CPU的計算時間被分成兩份，每個進程獲得50%。然而在實際的硬件上，當(dāng)一個進程占用CPU時，其它進程就必須等待。這就產(chǎn)生了不公平。 2.相關(guān)概念 調(diào)度實體(sched entiy)：就是調(diào)度的對象，可以理解為進程。 虛擬運行時間(vruntime)：即每個調(diào)度實體的運行時間。任務(wù)的虛擬運行時間越小， 意味著任務(wù)被允許訪問服務(wù)器的時間越短 — 其對處理器的需求越高。 公平調(diào)度隊列(cfs_rq)：采取公平調(diào)度的調(diào)度實體的運行隊列。 3.CFS的核心思想 全公平調(diào)度器（CFS）的設(shè)計思想是：在一個真實的硬件上模型化一個理想的、精確的多任務(wù)CPU。該理想CPU模型運行在100%的負(fù)荷、在精確 平等速度下并行運行每個任務(wù)，每個任務(wù)運行在1/n速度下，即理想CPU有n個任務(wù)運行，每個任務(wù)的速度為CPU整個負(fù)荷的1/n。 由于真實硬件上，每次只能運行一個任務(wù)，這就得引入"虛擬運行時間"（virtual runtime）的概念，虛擬運行時間為一個任務(wù)在理想CPU模型上執(zhí)行的下一個時間片(timeslice)。實際上，一個任務(wù)的虛擬運行時間為考慮到運行任務(wù)總數(shù)的實際運行時間。 CFS 背后的主要想法是維護為任務(wù)提供處理器時間方面的平衡（公平性）。CFS為了體現(xiàn)的公平表現(xiàn)在2個方面 (1)進程的運行時間相等 CFS 在叫做虛擬運行時 的地方維持提供給某個任務(wù)的時間量。任務(wù)的虛擬運行時越小， 意味著任務(wù)被允許訪問服務(wù)器的時間越短 — 其對處理器的需求越高。 例如，如果具有 4 個可運行的任務(wù)，那么 fair_clock 將按照實際時間速度的四分之一增加。每個任務(wù)將設(shè)法跟上這個速度。這是由分時多任務(wù)處理的量子化特性決定的。也就是說，在任何一個時間段內(nèi)只有一個任務(wù)可以運行；因此， 其他進程在時間上的拖欠將增大（wait_runtime）。因此，一旦某個任務(wù)進入調(diào)度，它將努力趕上它所欠下的時間（并且要比所欠時間多一點，因為在追趕時間期間，fair_clock 不會停止計時）。 加權(quán)任務(wù)引入了優(yōu)先級。假設(shè)我們有兩個任務(wù)：其中一個任務(wù)占用 CPU 的時間量是另一個任務(wù)的兩倍，比例為 2:1。執(zhí)行數(shù)學(xué)轉(zhuǎn)換后，對于權(quán)重為 0.5 的任務(wù)，時間流逝的速度是以前的兩倍。 (2)睡眠的進程進行補償 CFS 還包含睡眠公平概念以便確保那些目前沒有運行的任務(wù)（例如，等待 I/O）在其最終需要時獲得相當(dāng)份額的處理器。 CFS調(diào)度器的運行時間是O(logN)，而以前的調(diào)度器的運行時間是O(1)，這是不是就是說CFS的效率比O(1)的更差呢？ 答案并不是那樣，我們知道 CFS調(diào)度器下的運行隊列是基于紅黑樹組織的，找出下一個進程就是截下左下角的節(jié)點，固定時間完成，所謂的O(logN)指的是插入時間，可是紅黑樹的統(tǒng) 計性能是不錯的，沒有多大概率真的用得了那么多時間，因為紅節(jié)點和黑節(jié)點的特殊排列方式既保證了樹的一定程度的平衡，又不至于花太多的時間來維持這種平 衡，插入操作大多數(shù)情況下都可以很快的完成，特別是對于組織得相當(dāng)好的數(shù)據(jù)。 4.CFS工作原理 CFS 調(diào)度程序使用安撫（appeasement）策略確保公平性。當(dāng)某個任務(wù)進入運行隊列后，將記錄當(dāng)前時間，當(dāng)某個進程等待 CPU 時，將對這個進程的 wait_runtime 值加一個數(shù)，這個數(shù)取決于運行隊列當(dāng)前的進程數(shù)。當(dāng)執(zhí)行這些計算時，也將考慮不同任務(wù)的優(yōu)先級值。 將這個任務(wù)調(diào)度到 CPU 后，它的 wait_runtime 值開始遞減，當(dāng)這個值遞減到其他任務(wù)成為紅黑樹的最左側(cè)任務(wù)時，當(dāng)前任務(wù)將被搶占。通過這種方式，CFS 努力實現(xiàn)一種理想 狀態(tài)，即 wait_runtime 值為 0！ CFS 維護任務(wù)運行時（相對于運行隊列級時鐘，稱為 fair_clock(cfs_rq->fair_clock)），它在某個實際時間的片段內(nèi)運行，因此，對于單個任務(wù)可以按照理想的速度運行。 最后，根據(jù) fair_clock 對樹進行排隊。 5.CFS的實現(xiàn) 5.1 2.6.23 VS 2.6.25 在2.6.23內(nèi)核中，剛剛實現(xiàn)的CFS調(diào)度器顯得很淳樸，每次的時鐘滴答中都會將當(dāng)前進程先出隊，推進其虛擬時鐘和系統(tǒng)虛擬時鐘后再入隊，然后判斷紅黑 樹的左下角的進程是否還是當(dāng)前進程而抉擇是否要調(diào)度，這種調(diào)度器的key的計算是用當(dāng)前的虛擬時鐘減去待計算進程的等待時間，如果該計算進程在運行，那么其等待時間就是負(fù)值，這樣，等待越長的進程key越小，從而越容易被選中投入運行； 在2.6.25內(nèi)核以后實現(xiàn)了一種更為簡單的方式，就是設(shè)置一個運行隊列的虛擬時鐘，它單調(diào)增長并且跟蹤該隊列的最小虛擬時鐘的進程，key值由進程的vruntime和隊列的虛擬時鐘的差值計算，這種方式就是真正的追趕， 比2.6.23實現(xiàn)的簡單，但是很巧妙，不必在每次時鐘滴答中都將當(dāng)前進程出隊，入隊，而是根據(jù)當(dāng)前進程實際運行的時間和理想應(yīng)該運行的時間判斷是否應(yīng)該調(diào)度。 5.2紅黑樹 與之前的 Linux 調(diào)度器不同，它沒有將任務(wù)維護在運行隊列中，CFS 維護了一個以時間為順序的紅黑樹（參見下圖）。 紅黑樹 是一個樹，具有很多有趣、有用的屬性。首先，它是自平衡的，這意味著樹上沒有路徑比任何其他路徑長兩倍以上。 第二，樹上的運行按 O(log n) 時間發(fā)生（其中 n 是樹中節(jié)點的數(shù)量）。這意味著您可以快速高效地插入或刪除任務(wù)。  任務(wù)存儲在以時間為順序的紅黑樹中（由 sched_entity 對象表示），對處理器需求最多的任務(wù) （最低虛擬運行時）存儲在樹的左側(cè)，處理器需求最少的任務(wù)（最高虛擬運行時）存儲在樹的右側(cè)。 為了公平，調(diào)度器先選取紅黑樹最左端的節(jié)點調(diào)度為下一個以便保持公平性。任務(wù)通過將其運行時間添加到虛擬運行時， 說明其占用 CPU 的時間，然后如果可運行，再插回到樹中。這樣，樹左側(cè)的任務(wù)就被給予時間運行了，樹的內(nèi)容從右側(cè)遷移到左側(cè)以保持公平。 因此，每個可運行的任務(wù)都會追趕其他任務(wù)以維持整個可運行任務(wù)集合的執(zhí)行平衡。 5.3調(diào)度類 調(diào)度類類似于一個模塊鏈，協(xié)助內(nèi)核調(diào)度程序工作。每個調(diào)度程序模塊需要實現(xiàn) struct sched_class 建議的一組函數(shù)。 代碼如下
4.4 CFS內(nèi)部原理 CFS 去掉了 struct prio_array，并引入調(diào)度實體（scheduling entity）和調(diào)度類 （scheduling classes），分別由 struct sched_entity 和 struct sched_class 定義。因此，task_struct 包含關(guān)于 sched_entity 和 sched_class 這兩種結(jié)構(gòu)的信息。詳見 ./linux/include/linux/sched.h  樹的根通過 rb_root 元素通過 cfs_rq 結(jié)構(gòu)（在 ./kernel/sched.c 中）引用。紅黑樹的葉子不包含信息，但是內(nèi)部節(jié)點代表一個或多個可運行的任務(wù)。紅黑樹的每個節(jié)點都由 rb_node 表示，它只包含子引用和父對象的顏色。 rb_node 包含在 sched_entity 結(jié)構(gòu)中，該結(jié)構(gòu)包含 rb_node 引用、負(fù)載權(quán)重以及各種統(tǒng)計數(shù)據(jù)。最重要的是， sched_entity 包含 vruntime（64 位字段），它表示任務(wù)運行的時間量，并作為紅黑樹的索引。 最后，task_struct 位于頂端，它完整地描述任務(wù)并包含 sched_entity 結(jié)構(gòu)。 CFS 調(diào)度函數(shù)非常簡單。 在 ./kernel/sched.c 中的 schedule() 函數(shù)中，它會先搶占當(dāng)前運行任務(wù)（除非它通過 yield() 代碼先搶占自己）。注意 CFS 沒有真正的時間切片概念用于搶占，因為搶占時間是可變的。 當(dāng)前運行任務(wù)（現(xiàn)在被搶占的任務(wù)）通過對 put_prev_task 調(diào)用（通過調(diào)度類）返回到紅黑樹。 當(dāng) schedule 函數(shù)開始確定下一個要調(diào)度的任務(wù)時，它會調(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。通過此引用，一個簡單的 task_of() 調(diào)用確定返回的 task_struct 引用。通用調(diào)度器最后為此任務(wù)提供處理器。 4.4 CFS的優(yōu)先級 CFS 不直接使用優(yōu)先級而是將其用作允許任務(wù)執(zhí)行的時間的衰減系數(shù)。 低優(yōu)先級任務(wù)具有更高的衰減系數(shù)，而高優(yōu)先級任務(wù)具有較低的衰減系數(shù)。 這意味著與高優(yōu)先級任務(wù)相比，低優(yōu)先級任務(wù)允許任務(wù)執(zhí)行的時間消耗得更快。 這是一個絕妙的解決方案，可以避免維護按優(yōu)先級調(diào)度的運行隊列。 2.CFS是如何實現(xiàn)公正調(diào)度的 2.2每個進程的weight值的確定 CFS的公平依據(jù)就是每個調(diào)度實體的權(quán)重(weight)，這個權(quán)重是有優(yōu)先級來決定的，即優(yōu)先級越高權(quán)重越高，linux內(nèi)核采用了從nice 到 prio 到 weight的一個轉(zhuǎn)換關(guān)系來實現(xiàn)了每個調(diào)度實體權(quán)重的確定。 進程被創(chuàng)建的時候他的優(yōu)先級是繼承自父進程的，如果想改變有優(yōu)先級，linux內(nèi)核提供了幾個系統(tǒng)調(diào)用來改變進程的nice值，從而改變權(quán)重，不如sys_nice()系統(tǒng)調(diào)用，下面來看一下他們之間的轉(zhuǎn)換關(guān)系： #define NICE_TO_PRIO(MAX_RT_PRIO + (nice) + 20) #define PRIO_TO_NICE((prio) - MAX_RT_PRIO - 20) 其中，MAX_RT_PRIO=100,nice的值在-20到19之前，那么優(yōu)先級就在100 - 139之間。 說明：用戶進程的優(yōu)先級為101-140，前100個是分給實現(xiàn)實時進程的。 prio和weight之間的轉(zhuǎn)換關(guān)系，這是個經(jīng)驗公式，如下圖所示。  通過以上分析我們就可以通過修改nice來修改weight了。(未講解清楚) CFS 組調(diào)度 考慮一個兩用戶示例，用戶 A 和用戶 B 在一臺機器上運行作業(yè)。用戶 A 只有兩個作業(yè)正在運行，而用戶 B 正在運行 48 個作業(yè)。組調(diào)度使 CFS 能夠?qū)τ脩?A 和用戶 B 進行公平調(diào)度，而不是對系統(tǒng)中運行的 50 個作業(yè)進行公平調(diào)度。每個用戶各擁有 50% 的 CPU 使用。用戶 B 使用自己 50% 的 CPU 分配運行他的 48 個作業(yè)，而不會占用屬于用戶 A 的另外 50% 的 CPU 分配。 待續(xù) 參考文獻 1.http://www./article/6/2010/linux_37764.html 2.linux2.6.29 CFS調(diào)度詳細(xì)分析. http://linux./techdoc/system/2009/05/03/1109877.shtml 3.使用完全公平調(diào)度程序（CFS）進行多任務(wù)處理. http://www.ibm.com/developerworks/cn/linux/l-cfs/index.html 3.Linux 2.6 Completely Fair Scheduler 內(nèi)幕. http://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html?ca=drs-cn-0125 |
|
|
