|
1.概述 CFS（completely fair schedule）是最終被內(nèi)核采納的調(diào)度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進(jìn)程的睡眠時(shí)間，也不再企圖區(qū)分交互式進(jìn)程。它將所有的進(jìn)程都統(tǒng)一對(duì)待，這就是公平的含義。CFS的算法和實(shí)現(xiàn)都相當(dāng)簡(jiǎn)單，眾多的測(cè)試表明其性能也非常優(yōu)越。 CFS 背后的主要想法是維護(hù)為任務(wù)提供處理器時(shí)間方面的平衡（公平性）。這意味著應(yīng)給進(jìn)程分配相當(dāng)數(shù)量的處理器。分給某個(gè)任務(wù)的時(shí)間失去平衡時(shí)（意味著一個(gè)或多個(gè)任務(wù)相對(duì)于其他任務(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)度的對(duì)象，可以理解為進(jìn)程。 虛擬運(yùn)行時(shí)間(vruntime)：即每個(gè)調(diào)度實(shí)體的運(yùn)行時(shí)間。任務(wù)的虛擬運(yùn)行時(shí)間越小， 意味著任務(wù)被允許訪問服務(wù)器的時(shí)間越短 — 其對(duì)處理器的需求越高。 公平調(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í)間越短 — 其對(duì)處理器的需求越高。 例如，如果具有 4 個(gè)可運(yùn)行的任務(wù)，那么 fair_clock 將按照實(shí)際時(shí)間速度的四分之一增加。每個(gè)任務(wù)將設(shè)法跟上這個(gè)速度。這是由分時(shí)多任務(wù)處理的量子化特性決定的。也就是說，在任何一個(gè)時(shí)間段內(nèi)只有一個(gè)任務(wù)可以運(yùn)行；因此， 其他進(jìn)程在時(shí)間上的拖欠將增大（wait_runtime）。因此，一旦某個(gè)任務(wù)進(jìn)入調(diào)度，它將努力趕上它所欠下的時(shí)間（并且要比所欠時(shí)間多一點(diǎn)，因?yàn)樵谧汾s時(shí)間期間，fair_clock 不會(huì)停止計(jì)時(shí)）。 加權(quán)任務(wù)引入了優(yōu)先級(jí)。假設(shè)我們有兩個(gè)任務(wù)：其中一個(gè)任務(wù)占用 CPU 的時(shí)間量是另一個(gè)任務(wù)的兩倍，比例為 2:1。執(zhí)行數(shù)學(xué)轉(zhuǎn)換后，對(duì)于權(quán)重為 0.5 的任務(wù)，時(shí)間流逝的速度是以前的兩倍。 (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ù)情況下都可以很快的完成，特別是對(duì)于組織得相當(dāng)好的數(shù)據(jù)。 4.CFS工作原理 CFS 調(diào)度程序使用安撫（appeasement）策略確保公平性。當(dāng)某個(gè)任務(wù)進(jìn)入運(yùn)行隊(duì)列后，將記錄當(dāng)前時(shí)間，當(dāng)某個(gè)進(jìn)程等待 CPU 時(shí)，將對(duì)這個(gè)進(jìn)程的 wait_runtime 值加一個(gè)數(shù)，這個(gè)數(shù)取決于運(yùn)行隊(duì)列當(dāng)前的進(jìn)程數(shù)。當(dāng)執(zhí)行這些計(jì)算時(shí)，也將考慮不同任務(wù)的優(yōu)先級(jí)值。 將這個(gè)任務(wù)調(diào)度到 CPU 后，它的 wait_runtime 值開始遞減，當(dāng)這個(gè)值遞減到其他任務(wù)成為紅黑樹的最左側(cè)任務(wù)時(shí)，當(dāng)前任務(wù)將被搶占。通過這種方式，CFS 努力實(shí)現(xiàn)一種理想 狀態(tài)，即 wait_runtime 值為 0！ CFS 維護(hù)任務(wù)運(yùn)行時(shí)（相對(duì)于運(yùn)行隊(duì)列級(jí)時(shí)鐘，稱為 fair_clock(cfs_rq->fair_clock)），它在某個(gè)實(shí)際時(shí)間的片段內(nèi)運(yùn)行，因此，對(duì)于單個(gè)任務(wù)可以按照理想的速度運(yùn)行。 最后，根據(jù) fair_clock 對(duì)樹進(jìn)行排隊(duì)。 5.CFS的實(shí)現(xiàn) 5.1 2.6.23 VS 2.6.25 在2.6.23內(nèi)核中，剛剛實(shí)現(xiàn)的CFS調(diào)度器顯得很淳樸，每次的時(shí)鐘滴答中都會(huì)將當(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)了一種更為簡(jiǎ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)的簡(jiǎ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)度。 5.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ù)存儲(chǔ)在以時(shí)間為順序的紅黑樹中（由 sched_entity 對(duì)象表示），對(duì)處理器需求最多的任務(wù) （最低虛擬運(yùn)行時(shí)）存儲(chǔ)在樹的左側(cè)，處理器需求最少的任務(wù)（最高虛擬運(yùn)行時(shí)）存儲(chǔ)在樹的右側(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ù)都會(huì)追趕其他任務(wù)以維持整個(gè)可運(yùn)行任務(wù)集合的執(zhí)行平衡。 5.3調(diào)度類 調(diào)度類類似于一個(gè)模塊鏈，協(xié)助內(nèi)核調(diào)度程序工作。每個(gè)調(diào)度程序模塊需要實(shí)現(xiàn) struct sched_class 建議的一組函數(shù)。 代碼如下
4.4 CFS內(nèi)部原理 CFS 去掉了 struct prio_array，并引入調(diào)度實(shí)體（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é)點(diǎn)代表一個(gè)或多個(gè)可運(yùn)行的任務(wù)。紅黑樹的每個(gè)節(jié)點(diǎn)都由 rb_node 表示，它只包含子引用和父對(duì)象的顏色。 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ù)非常簡(jiǎn)單。 在 ./kernel/sched.c 中的 schedule() 函數(shù)中，它會(huì)先搶占當(dāng)前運(yùn)行任務(wù)（除非它通過 yield() 代碼先搶占自己）。注意 CFS 沒有真正的時(shí)間切片概念用于搶占，因?yàn)閾屨紩r(shí)間是可變的。 當(dāng)前運(yùn)行任務(wù)（現(xiàn)在被搶占的任務(wù)）通過對(duì) put_prev_task 調(diào)用（通過調(diào)度類）返回到紅黑樹。 當(dāng) schedule 函數(shù)開始確定下一個(gè)要調(diào)度的任務(wù)時(shí)，它會(huì)調(diào)用 pick_next_task 函數(shù)。此函數(shù)也是通用的（在 ./kernel/sched.c 中），但它會(huì)通過調(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è)簡(jiǎn)單的 task_of() 調(diào)用確定返回的 task_struct 引用。通用調(diào)度器最后為此任務(wù)提供處理器。 4.4 CFS的優(yōu)先級(jí) CFS 不直接使用優(yōu)先級(jí)而是將其用作允許任務(wù)執(zhí)行的時(shí)間的衰減系數(shù)。 低優(yōu)先級(jí)任務(wù)具有更高的衰減系數(shù)，而高優(yōu)先級(jí)任務(wù)具有較低的衰減系數(shù)。 這意味著與高優(yōu)先級(jí)任務(wù)相比，低優(yōu)先級(jí)任務(wù)允許任務(wù)執(zhí)行的時(shí)間消耗得更快。 這是一個(gè)絕妙的解決方案，可以避免維護(hù)按優(yōu)先級(jí)調(diào)度的運(yùn)行隊(duì)列。 2.CFS是如何實(shí)現(xiàn)公正調(diào)度的 2.2每個(gè)進(jìn)程的weight值的確定 CFS的公平依據(jù)就是每個(gè)調(diào)度實(shí)體的權(quán)重(weight)，這個(gè)權(quán)重是有優(yōu)先級(jí)來決定的，即優(yōu)先級(jí)越高權(quán)重越高，linux內(nèi)核采用了從nice 到 prio 到 weight的一個(gè)轉(zhuǎn)換關(guān)系來實(shí)現(xiàn)了每個(gè)調(diào)度實(shí)體權(quán)重的確定。 進(jìn)程被創(chuàng)建的時(shí)候他的優(yōu)先級(jí)是繼承自父進(jìn)程的，如果想改變有優(yōu)先級(jí)，linux內(nèi)核提供了幾個(gè)系統(tǒng)調(diào)用來改變進(jìn)程的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)先級(jí)就在100 - 139之間。 說明：用戶進(jìn)程的優(yōu)先級(jí)為101-140，前100個(gè)是分給實(shí)現(xiàn)實(shí)時(shí)進(jìn)程的。 prio和weight之間的轉(zhuǎn)換關(guān)系，這是個(gè)經(jīng)驗(yàn)公式，如下圖所示。  通過以上分析我們就可以通過修改nice來修改weight了。(未講解清楚) CFS 組調(diào)度 考慮一個(gè)兩用戶示例，用戶 A 和用戶 B 在一臺(tái)機(jī)器上運(yùn)行作業(yè)。用戶 A 只有兩個(gè)作業(yè)正在運(yùn)行，而用戶 B 正在運(yùn)行 48 個(gè)作業(yè)。組調(diào)度使 CFS 能夠?qū)τ脩?A 和用戶 B 進(jìn)行公平調(diào)度，而不是對(duì)系統(tǒng)中運(yùn)行的 50 個(gè)作業(yè)進(jìn)行公平調(diào)度。每個(gè)用戶各擁有 50% 的 CPU 使用。用戶 B 使用自己 50% 的 CPU 分配運(yùn)行他的 48 個(gè)作業(yè)，而不會(huì)占用屬于用戶 A 的另外 50% 的 CPU 分配。 待續(xù) 參考文獻(xiàn) 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）進(jìn)行多任務(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 |
|
|
