Linux程序排程-------O(1)排程和CFS排程器

  1. 概述

    對于分時作業系統而言，表面上看起來是多個程序同時在執行，而在系統内部則進行着從一個程序到另一個程序的切換動作。這樣的程序并發執行涉及到程序切換（process switch）和程序排程（process scheduling）兩大問題。其中程序排程是作業系統的核心功能，它是一個非常複雜的過程，需要多個系統協同工作完成。Linux作為一個通用作業系統，其排程器的設計一直是一個頗有頗有挑戰性的課題。一方面它涉及應用Linux的使用模型。盡管Linux最初開發為桌面作業系統環境，但現在在伺服器、微型嵌入式裝置、主機和超級計算機中都能發現它，無疑這些領域的排程負載有很大差異。另一方面，它要考慮平台方面的技術進步，包括架構（多處理、對稱多線程、非一緻記憶體通路 [NUMA] 和虛拟化）。另外，這裡還要考慮互動性（使用者響應能力）和整體公平性之間的平衡。通常Linux排程器将程序分為三類：

    （1）互動式程序：此類程序有大量的人機互動，是以程序不斷地處于睡眠狀态，等待使用者輸入。典型的應用比如編輯器vi。此類程序對系統響應時間要求比較高，否則使用者會感覺系統反應遲緩。

    （2）批處理程序：此類程序不需要人機互動，在背景運作，需要占用大量的系統資源。但是能夠忍受響應延遲。比如編譯器。

    （3）實時程序：實時對排程延遲的要求最高，這些程序往往執行非常重要的操作，要求立即響應并執行。比如視訊播放軟體或飛機飛行控制系統，很明顯這類程式不能容忍長時間的排程延遲，輕則影響電影放映效果，重則機毀人亡。

    根據程序的不同分類Linux采用不同的排程政策。對于實時程序，采用FIFO或者Round Robin的排程政策。對于普通程序，則需要區分互動式和批處理式的不同。傳統Linux排程器提高互動式應用的優先級，使得它們能更快地被排程。而CFS和RSDL等新的排程器的核心思想是“完全公平”。這個設計理念不僅大大簡化了排程器的代碼複雜度，還對各種排程需求的提供了更完美的支援。注意Linux通過将程序和線程排程視為一個，同時包含二者。程序可以看做是單個線程，但是程序可以包含共享一定資源（代碼和/或資料）的多個線程。是以程序排程也包含了線程排程的功能。

     2. Linux排程器的簡史

     （1）Linux 2.4之前的核心排程器

    早期的Linux程序排程器使用了最低的設計，它顯然不關注具有很多處理器的大型架構，更不用說是超線程了。1.2 Linux排程器使用了環形隊列用于可運作的任務管理，使用循環排程政策。 此排程器添加和删除程序效率很高（具有保護結構的鎖）。簡而言之，該排程器并不複雜但是簡單快捷。Linux版本2.2引入了排程類的概念，允許針對實時任務、非搶占式任務、非實時任務的排程政策。2.2 排程器還包括對稱多處理 (SMP) 支援。

     （2）Linux 2.4的排程器

    Linux2.4.18中使用的排程器采用基于優先級的設計，這個排程器和Linus在1992年釋出的排程器沒有大的差別。該排程器的 pick next 算法非常簡單：對 runqueue 中所有程序的優先級進行依次進行比較，選擇最高優先級的程序作為下一個被排程的程序。(Runqueue 是 Linux 核心中儲存所有就緒程序的隊列) 。術語 pick next 用來指從所有候選程序中挑選下一個要被排程的程序的過程。

    每個程序被建立時都被賦予一個時間片。時鐘中斷遞減目前運作程序的時間片，當程序的時間片被用完時，它必須等待重新賦予時間片才能有機會運作。Linux2.4 排程器保證隻有當所有 RUNNING 程序的時間片都被用完之後，才對所有程序重新配置設定時間片。這段時間被稱為一個epoch。這種設計保證了每個程序都有機會得到執行。每個epoch中，每個程序允許執行到其時間切片用完。如果某個程序沒有使用其所有的時間切片，那麼剩餘時間切片的一半将被添加到新時間切片使其在下個epoch中可以執行更長時間。排程器隻是疊代程序，應用goodness函數（名額）決定下面執行哪個程序。當然，各種程序對排程的需求并不相同，Linux 2.4排程器主要依靠改變程序的優先級，來滿足不同程序的排程需求。事實上，所有後來的排程器都主要依賴修改程序優先級來滿足不同的排程需求。

    實時程序：實時程序的優先級是靜态設定的，而且始終大于普通程序的優先級。是以隻有當 runqueue 中沒有實時程序的情況下，普通程序才能夠獲得排程。實時程序采用兩種排程政策，SCHED_FIFO 和 SCHED_RR。FIFO 采用先進先出的政策，對于所有相同優先級的程序，最先進入 runqueue 的程序總能優先獲得排程；Round Robin采用更加公平的輪轉政策，使得相同優先級的實時程序能夠輪流獲得排程。

    普通程序：對于普通程序，排程器傾向于提高互動式程序的優先級，因為它們需要快速的使用者響應。普通程序的優先級主要由程序描述符中的 Counter 字段決定 (還要加上 nice 設定的靜态優先級) 。程序被建立時子程序的 counter 值為父程序 counter 值的一半，這樣保證了任何程序不能依靠不斷地 fork() 子程序進而獲得更多的執行機會。

    Linux2.4排程器是如何提高互動式程序的優先級的呢？如前所述，當所有 RUNNING 程序的時間片被用完之後，排程器将重新計算所有程序的 counter 值，所有程序不僅包括 RUNNING 程序，也包括處于睡眠狀态的程序。處于睡眠狀态的程序的 counter 本來就沒有用完，在重新計算時，他們的 counter 值會加上這些原來未用完的部分，進而提高了它們的優先級。互動式程序經常因等待使用者輸入而處于睡眠狀态，當它們重新被喚醒并進入 runqueue 時，就會優先于其它程序而獲得 CPU。從使用者角度來看，互動式程序的響應速度就提高了。

    該排程器的主要缺點：

    可擴充性不好：排程器選擇程序時需要周遊整個 runqueue 從中選出最佳人選，是以該算法的執行時間與程序數成正比。另外每次重新計算 counter 所花費的時間也會随着系統中程序數的增加而線性增長，當程序數很大時，更新 counter 操作的代價會非常高，導緻系統整體的性能下降。

    高負載系統上的排程性能比較低：2.4的排程器預配置設定給每個程序的時間片比較大，是以在高負載的伺服器上，該排程器的效率比較低，因為平均每個程序的等待時間于該時間片的大小成正比。

    互動式程序的優化并不完善：Linux2.4識别互動式程序的原理基于以下假設，即互動式程序比批處理程序更頻繁地處于SUSPENDED狀态。然而現實情況往往并非如此，有些批處理程序雖然沒有使用者互動，但是也會頻繁地進行IO操作，比如一個資料庫引擎在處理查詢時會經常地進行磁盤IO，雖然它們并不需要快速地使用者響應，還是被提高了優先級。當系統中這類程序的負載較重時，會影響真正的互動式程序的響應時間。

    對實時程序的支援不夠：Linux2.4核心是非搶占的，當程序處于核心态時不會發生搶占，這對于真正的實時應用是不能接受的。

    為了解決這些問題，Ingo Molnar開發了新的O(1)排程器，在CFS和RSDL之前，這個排程器不僅被Linux2.6采用，還被backport到Linux2.4中，很多商業的發行版本都采用了這個排程器。

     （3）Linux 2.6的O(1)排程器

    從名字就可以看出O(1)排程器主要解決了以前版本中的擴充性問題。O(1)排程算法所花費的時間為常數，與目前系統中的程序個數無關。此外Linux 2.6核心支援核心态搶占，是以更好地支援了實時程序。相對于前任，O(1)排程器還更好地區分了互動式程序和批處理式程序。Linux 2.6核心也支援三種排程政策。其中SCHED_FIFO和SCHED_RR用于實時程序，而SCHED_NORMAL用于普通程序。O(1)排程器在兩個方面修改了Linux 2.4排程器，一是程序優先級的計算方法；二是pick next算法。O(1)排程器跟蹤運作隊列中可運作的任務（實際上，每個優先級水準有兩個運作隊列，一個用于活動任務，一個用于過期任務）， 這意味着要确定接下來執行的任務，排程器隻需按優先級将下一個任務從特定活動的運作隊列中取出即可。

    1）普通程序的優先級計算

    不同類型的程序應該有不同的優先級。每個程序與生俱來（即從父程序那裡繼承而來）都有一個優先級，我們将其稱為靜态優先級。普通程序的靜态優先級範圍從100到139，100為最高優先級，139 為最低優先級，0－99保留給實時程序。當程序用完了時間片後，系統就會為該程序配置設定新的時間片（即基本時間片），靜态優先級本質上決定了時間片配置設定的大小。靜态優先級和基本時間片的關系如下：

    靜态優先級<120，基本時間片=max((140-靜态優先級)*20, MIN_TIMESLICE)

    靜态優先級>=120，基本時間片=max((140-靜态優先級)*5, MIN_TIMESLICE)

    其中MIN_TIMESLICE為系統規定的最小時間片。從該計算公式可以看出，靜态優先級越高（值越低），程序得到的時間片越長。其結果是，優先級高的程序會獲得更長的時間片，而優先級低的程序得到的時間片則較短。程序除了擁有靜态優先級外，還有動态優先級，其取值範圍是100到139。當排程程式選擇新程序運作時就會使用程序的動态優先級，動态優先級和靜态優先級的關系可參考下面的公式：

    動态優先級=max(100 , min(靜态優先級 – bonus + 5) , 139)

    從上面看出，動态優先級的生成是以靜态優先級為基礎，再加上相應的懲罰或獎勵(bonus)。這個bonus并不是随機的産生，而是根據程序過去的平均睡眠時間做相應的懲罰或獎勵。所謂平均睡眠時間（sleep_avg，位于task_struct結構中）就是程序在睡眠狀态所消耗的總時間數，這裡的平均并不是直接對時間求平均數。平均睡眠時間随着程序的睡眠而增長，随着程序的運作而減少。是以，平均睡眠時間記錄了程序睡眠和執行的時間，它是用來判斷程序互動性強弱的關鍵資料。如果一個程序的平均睡眠時間很大，那麼它很可能是一個互動性很強的程序。反之，如果一個程序的平均睡眠時間很小，那麼它很可能一直在執行。另外，平均睡眠時間也記錄着程序目前的互動狀态，有很快的反應速度。比如一個程序在某一小段時間互動性很強，那麼sleep_avg就有可能暴漲（當然它不能超過 MAX_SLEEP_AVG），但如果之後都一直處于執行狀态，那麼sleep_avg就又可能一直遞減。了解了平均睡眠時間，那麼bonus的含義也就顯而易見了。互動性強的程序會得到排程程式的獎勵（bonus為正），而那些一直霸占CPU的程序會得到相應的懲罰（bonus為負）。其實bonus相當于平均睡眠時間的縮影，此時隻是将sleep_avg調整成bonus數值範圍内的大小。可見平均睡眠時間可以用來衡量程序是否是一個互動式程序。如果滿足下面的公式，程序就被認為是一個互動式程序：

    動态優先級≤3*靜态優先級/4 + 28

    平均睡眠時間是程序處于等待睡眠狀态下的時間，該值在程序進入睡眠狀态時增加，而進入RUNNING狀态後則減少。該值的更新時機分布在很多核心函數内：時鐘中斷scheduler_tick()；程序建立；程序從TASK_INTERRUPTIBLE狀态喚醒；負載平衡等。

    2）實時程序的優先級計算

    實時程序的優先級由sys_sched_setschedule()設定。該值不會動态修改，而且總是比普通程序的優先級高。在程序描述符中用rt_priority域表示。

    3）pick next算法

    普通程序的排程選擇算法基于程序的優先級，擁有最高優先級的程序被排程器選中。2.4中，時間片counter同時也表示了一個程序的優先級。2.6中時間片用任務描述符中的time_slice域表示，而優先級用prio（普通程序）或者rt_priority（實時程序）表示。排程器為每一個CPU維護了兩個程序隊列數組：指向活動運作隊列的active數組和指向過期運作隊列的expire數組。數組中的元素着儲存某一優先級的程序隊列指針。系統一共有140個不同的優先級，是以這兩個數組大小都是140。它們是按照先進先出的順序進行服務的。被排程執行的任務都會被添加到各自運作隊列優先級清單的末尾。每個任務都有一個時間片，這取決于系統允許執行這個任務多長時間。運作隊列的前100個優先級清單保留給實時任務使用，後40個用于使用者任務，參見下圖：

圖1 排程器的運作隊列結構

    當需要選擇目前最高優先級的程序時，2.6排程器不用周遊整個runqueue，而是直接從active數組中選擇目前最高優先級隊列中的第一個程序。假設目前所有程序中最高優先級為50（換句話說，系統中沒有任何程序的優先級小于50）。則排程器直接讀取 active[49]，得到優先級為50的程序隊列指針。該隊列頭上的第一個程序就是被選中的程序。這種算法的複雜度為O(1)，進而解決了2.4排程器的擴充性問題。為了實作O(1)算法active數組維護了一個由5個32位的字（140個優先級）組成的bitmap，當某個優先級别上有程序被插入清單時，相應的比特位就被置位。 sched_find_first_bit()函數查詢該bitmap，傳回目前被置位的最高優先級的數組下标。在上例中sched_find_first_bit函數将傳回49。在IA處理器上可以通過bsfl等指令實作。可見查找一個任務來執行所需要的時間并不依賴于活動任務的個數，而是依賴于優先級的數量。這使得 2.6 版本的排程器成為一個複雜度為 O(1) 的過程，因為排程時間既是固定的，而且也不會受到活動任務個數的影響。

    為了提高互動式程序的響應時間，O(1)排程器不僅動态地提高該類程序的優先級，還采用以下方法：每次時鐘tick中斷時，程序的時間片(time_slice)被減一。當time_slice為0時，表示目前程序的時間片用完，排程器判斷目前程序的類型，如果是互動式程序或者實時程序，則重置其時間片并重新插入active數組。如果不是互動式程序則從active數組中移到expired數組，并根據上述公式重新計算時間片。這樣實時程序和互動式程序就總能優先獲得CPU。然而這些程序不能始終留在active數組中，否則進入expire數組的程序就會産生饑餓現象。當程序已經占用CPU時間超過一個固定值後，即使它是實時程序或者互動式程序也會被移到expire數組中。當active數組中的所有程序都被移到expire數組中後，排程器交換active數組和expire數組。是以新的active數組又恢複了初始情況，而expire數組為空，進而開始新的一輪排程。

    Linux 2.6排程器改進了前任排程器的可擴充性問題，schedule()函數的時間複雜度為O(1)。這取決于兩個改進：

    1）Pick next算法借助于active數組，無需周遊runqueue；

    2）取消了定期更新所有程序counter的操作，動态優先級的修改分布在程序切換，時鐘tick中斷以及其它一些核心函數中進行。

    O(1)排程器區分互動式程序和批處理程序的算法與以前雖大有改進，但仍然在很多情況下會失效。有一些著名的程式總能讓該排程器性能下降，導緻互動式程序反應緩慢。例如fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c等。而且O(1)排程器對NUMA支援也不完善。為了解決這些問題，大量難以維護和閱讀的複雜代碼被加入Linux2.6.0的排程器子產品，雖然很多性能問題是以得到了解決，可是另外一個嚴重問題始終困擾着許多核心開發者，那就是代碼的複雜度問題。很多複雜的代碼難以管理并且對于純粹主義者而言未能展現算法的本質。

    為了解決 O(1) 排程器面臨的問題以及應對其他外部壓力， 需要改變某些東西。這種改變來自Con Kolivas的核心更新檔staircase scheduler（樓梯排程算法），以及改進的RSDL（Rotating Staircase Deadline Scheduler）。它為排程器設計提供了一個新的思路。Ingo Molnar在RSDL之後開發了CFS，并最終被2.6.23核心采用。接下來我們開始介紹這些新一代排程器。

    3. Linux 2.6的新一代排程器CFS

    （1）樓梯排程算法staircase scheduler

    樓梯算法(SD)在思路上和O(1)算法有很大不同，它抛棄了動态優先級的概念。而采用了一種完全公平的思路。前任算法的主要複雜性來自動态優先級的計算，排程器根據平均睡眠時間和一些很難了解的經驗公式來修正程序的優先級以及區分互動式程序。這樣的代碼很難閱讀和維護。樓梯算法思路簡單，但是實驗證明它對應互動式程序的響應比其前任更好，而且極大地簡化了代碼。

    和O(1)算法一樣，樓梯算法也同樣為每一個優先級維護一個程序清單，并将這些清單組織在active數組中。當選取下一個被排程程序時，SD算法也同樣從active數組中直接讀取。與O(1)算法不同在于，當程序用完了自己的時間片後，并不是被移到expire數組中。而是被加入active數組的低一優先級清單中，即将其降低一個級别。不過請注意這裡隻是将該任務插入低一級優先級任務清單中，任務本身的優先級并沒有改變。當時間片再次用完，任務被再次放入更低一級優先級任務隊列中。就象一部樓梯，任務每次用完了自己的時間片之後就下一級樓梯。任務下到最低一級樓梯時，如果時間片再次用完，它會回到初始優先級的下一級任務隊列中。比如某程序的優先級為1，當它到達最後一級台階140後，再次用完時間片時将回到優先級為2的任務隊列中，即第二級台階。不過此時配置設定給該任務的time_slice将變成原來的2倍。比如原來該任務的時間片time_slice為10ms，則現在變成了20ms。基本的原則是，當任務下到樓梯底部時，再次用完時間片就回到上次下樓梯的起點的下一級台階。并給予該任務相同于其最初配置設定的時間片。總結如下：設任務本身優先級為P，當它從第N級台階開始下樓梯并到達底部後，将回到第N+1級台階。并且賦予該任務N+1倍的時間片。

    以上描述的是普通程序的排程算法，實時程序還是采用原來的排程政策，即FIFO或者Round Robin。

    樓梯算法能避免程序饑餓現象，高優先級的程序會最終和低優先級的程序競争，使得低優先級程序最終獲得執行機會。對于互動式應用，當進入睡眠狀态時，與它同等優先級的其他程序将一步一步地走下樓梯，進入低優先級程序隊列。當該互動式程序再次喚醒後，它還留在高處的樓梯台階上，進而能更快地被排程器選中，加速了響應時間。

    樓梯算法的優點：從實作角度看，SD基本上還是沿用了O(1)的整體架構，隻是删除了O(1)排程器中動态修改優先級的複雜代碼；還淘汰了expire數組，進而簡化了代碼。它最重要的意義在于證明了完全公平這個思想的可行性。

    （2）RSDL（Rotating Staircase Deadline Scheduler）

    RSDL也是由Con Kolivas開發的，它是對SD算法的改進。核心的思想還是“完全公平”。沒有複雜的動态優先級調整政策。RSDL重新引入了expire數組。它為每一個優先級都配置設定了一個 “組時間配額”，記為Tg；同一優先級的每個程序都擁有同樣的"優先級時間配額"，用Tp表示。當程序用完了自身的Tp時，就下降到下一優先級程序組中。這個過程和SD相同，在RSDL中這個過程叫做minor rotation（次輪詢）。請注意Tp不等于程序的時間片，而是小于程序的時間片。下圖表示了minor rotation。程序從priority1的隊列中一步一步下到priority140之後回到priority2的隊列中，這個過程如下圖左邊所示，然後從priority 2開始再次一步一步下樓，到底後再次反彈到priority3隊列中，如下圖所示。

圖2 RSDL的次輪詢過程

    在SD算法中，處于樓梯底部的低優先級程序必須等待所有的高優先級程序執行完才能獲得CPU。是以低優先級程序的等待時間無法确定。RSDL中，當高優先級程序組用完了它們的Tg(即組時間配額)時，無論該組中是否還有程序Tp尚未用完，所有屬于該組的程序都被強制降低到下一優先級程序組中。這樣低優先級任務就可以在一個可以預計的未來得到排程。進而改善了排程的公平性。這就是RSDL中Deadline代表的含義。

    程序用完了自己的時間片time_slice時（下圖中T2），将放入expire數組指向的對應初始優先級隊列中(priority 1)。

圖3 時間片用完時的處理

    當active數組為空，或者所有的程序都降低到最低優先級時就會觸發主輪詢major rotation。Major rotation交換active數組和expire數組，所有程序都恢複到初始狀态，再一次從新開始minor rotation的過程。

    RSDL對互動式程序的支援：和SD同樣的道理，互動式程序在睡眠時間時，它所有的競争者都因為minor rotation而降到了低優先級程序隊列中。當它重新進入RUNNING狀态時，就獲得了相對較高的優先級，進而能被迅速響應。

    （3）完全公平的排程器CFS

    CFS是最終被核心采納的排程器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤程序的睡眠時間，也不再企圖區分互動式程序。它将所有的程序都統一對待，這就是公平的含義。CFS的算法和實作都相當簡單，衆多的測試表明其性能也非常優越。按照作者Ingo Molnar的說法（參考Documentation/scheduler/sched-design-CFS.txt），CFS百分之八十的工作可以用一句話概括：CFS在真實的硬體上模拟了完全理想的多任務處理器。在真空的硬體上，同一時刻我們隻能運作單個程序，是以當一個程序占用CPU時，其它程序就必須等待，這就産生了不公平。但是在“完全理想的多任務處理器 “下，每個程序都能同時獲得CPU的執行時間，即并行地每個程序占1/nr_running的時間。例如當系統中有兩個程序時，CPU的計算時間被分成兩份，每個程序獲得50%。假設runqueue中有n個程序，目前程序運作了10ms。在“完全理想的多任務處理器”中，10ms應該平分給n個程序(不考慮各個程序的nice值)，是以目前程序應得的時間是(10/n)ms，但是它卻運作了10ms。是以CFS将懲罰目前程序，使其它程序能夠在下次排程時盡可能取代目前程序。最終實作所有程序的公平排程。

    與之前的Linux排程器不同，CFS沒有将任務維護在連結清單式的運作隊列中，它抛棄了active/expire數組，而是對每個CPU維護一個以時間為順序的紅黑樹。該樹方法能夠良好運作的原因在于：

    * 紅黑樹可以始終保持平衡，這意味着樹上沒有路徑比任何其他路徑長兩倍以上。

    * 由于紅黑樹是二叉樹，查找操作的時間複雜度為O(log n)。但是除了最左側查找以外，很難執行其他查找，并且最左側的節點指針始終被緩存。

    * 對于大多數操作（插入、删除、查找等），紅黑樹的執行時間為O(log n)，而以前的排程程式通過具有固定優先級的優先級數組使用 O(1)。O(log n) 行為具有可測量的延遲，但是對于較大的任務數無關緊要。Molnar在嘗試這種樹方法時，首先對這一點進行了測試。

    * 紅黑樹可通過内部存儲實作，即不需要使用外部配置設定即可對資料結構進行維護。

    要實作平衡，CFS使用“虛拟運作時”表示某個任務的時間量。任務的虛拟運作時越小，意味着任務被允許通路伺服器的時間越短，其對處理器的需求越高。CFS還包含睡眠公平概念以便確定那些目前沒有運作的任務（例如，等待 I/O）在其最終需要時獲得相當份額的處理器。

    1）CFS如何實作pick next

    下圖是一個紅黑樹的例子。

圖4 一個紅黑樹示例

    所有可運作的任務通過不斷地插入操作最終都存儲在以時間為順序的紅黑樹中（由 sched_entity 對象表示），對處理器需求最多的任務（最低虛拟運作時）存儲在樹的左側，處理器需求最少的任務（最高虛拟運作時）存儲在樹的右側。 為了公平，CFS排程器會選擇紅黑樹最左邊的葉子節點作為下一個将獲得cpu的任務。這樣，樹左側的程序就被給予時間運作了。

    2）tick中斷

    在CFS中，tick中斷首先更新排程資訊。然後調整目前程序在紅黑樹中的位置。調整完成後如果發現目前程序不再是最左邊的葉子，就标記need_resched标志，中斷傳回時就會調用scheduler()完成程序切換。否則目前程序繼續占用CPU。從這裡可以看到 CFS抛棄了傳統的時間片概念。Tick中斷隻需更新紅黑樹，以前的所有排程器都在tick中斷中遞減時間片，當時間片或者配額被用完時才觸發優先級調整并重新排程。

    3）紅黑樹鍵值計算

    了解CFS的關鍵就是了解紅黑樹鍵值的計算方法。該鍵值由三個因子計算而得：一是程序已經占用的CPU時間；二是目前程序的nice值；三是目前的cpu負載。程序已經占用的CPU時間對鍵值的影響最大，其實很大程度上我們在了解CFS時可以簡單地認為鍵值就等于程序已占用的 CPU時間。是以該值越大，鍵值越大，進而使得目前程序向紅黑樹的右側移動。另外CFS規定，nice值為1的程序比nice值為0的程序多獲得10%的 CPU時間。在計算鍵值時也考慮到這個因素，是以nice值越大，鍵值也越大。

    CFS為每個程序都維護兩個重要變量：fair_clock和wait_runtime。這裡我們将為每個程序維護的變量稱為程序級變量，為每個CPU維護的稱作CPU級變量，為每個runqueue維護的稱為runqueue級變量。程序插入紅黑樹的鍵值即為fair_clock – wait_runtime。其中fair_clock從其字面含義上講就是一個程序應獲得的CPU時間，即等于程序已占用的CPU時間除以目前 runqueue中的程序總數；wait_runtime是程序的等待時間。它們的內插補點代表了一個程序的公平程度。該值越大，代表目前程序相對于其它程序越不公平。對于互動式任務，wait_runtime長時間得不到更新，是以它能擁有更高的紅黑樹鍵值，更靠近紅黑樹的左邊。進而得到快速響應。

    紅黑樹是平衡樹，排程器每次總最左邊讀出一個葉子節點，該讀取操作的時間複雜度是O(LgN)。

    4）排程器管理器

    為了支援實時程序，CFS提供了排程器子產品管理器。各種不同的排程器算法都可以作為一個子產品注冊到該管理器中。不同的程序可以選擇使用不同的排程器子產品。2.6.23中，CFS實作了兩個排程算法，CFS算法子產品和實時排程子產品。對應實時程序，将使用實時排程子產品。對應普通程序則使用CFS算法。CFS 排程子產品（在 kernel/sched_fair.c 中實作）用于以下排程政策：SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。對于 SCHED_RR 和 SCHED_FIFO 政策，将使用實時排程子產品（該子產品在 kernel/sched_rt.c 中實作）。

    5）CFS組排程

    CFS組排程（在 2.6.24 核心中引入）是另一種為排程帶來公平性的方式，尤其是在處理産生很多其他任務的任務時。 假設一個産生了很多任務的伺服器要并行化進入的連接配接（HTTP 伺服器的典型架構）。不是所有任務都會被統一公平對待， CFS 引入了組來處理這種行為。産生任務的伺服器程序在整個組中（在一個層次結構中）共享它們的虛拟運作時，而單個任務維持其自己獨立的虛拟運作時。這樣單個任務會收到與組大緻相同的排程時間。您會發現 /proc 接口用于管理程序層次結構，讓您對組的形成方式有完全的控制。使用此配置，您可以跨使用者、跨程序或其變體配置設定公平性。

    考慮一個兩使用者示例，使用者 A 和使用者 B 在一台機器上運作作業。使用者 A 隻有兩個作業正在運作，而使用者 B 正在運作 48 個作業。組排程使 CFS 能夠對使用者 A 和使用者 B 進行公平排程，而不是對系統中運作的 50 個作業進行公平排程。每個使用者各擁有 50% 的 CPU 使用。使用者 B 使用自己 50% 的 CPU 配置設定運作他的 48 個作業，而不會占用屬于使用者 A 的另外 50% 的 CPU 配置設定。

    4、Linux排程器的主要資料結構

    （1）程序描述符：struct task_struct

    下面代碼剖析使用的核心版本為2.6.32.45。CFS去掉了struct prio_array，并引入排程實體（scheduling entity）和排程類 （scheduling classes），分别由struct sched_entity 和 struct sched_class 定義。是以，task_struct結構（在./linux/include/linux/sched.h中）包含關于 sched_entity 和 sched_class。如下：

[cpp] view plain copy print ?

1. struct task_struct {  
2.     volatile long state;      
3.     void *stack;  
4.     atomic_t usage;  
5.     unsigned int flags;   
6.     unsigned int ptrace;  
7.     int prio, static_prio, normal_prio;  
8.     unsigned int rt_priority;  
9.     const struct sched_class *sched_class;  
10.     struct sched_entity se;  
11.     struct sched_rt_entity rt;  
12. };  

struct task_struct {
	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	void *stack;
	atomic_t usage;
	unsigned int flags;	/* per process flags, defined below */
	unsigned int ptrace;

	/* ...... */

	int prio, static_prio, normal_prio;
	unsigned int rt_priority;
	const struct sched_class *sched_class;
	struct sched_entity se;
	struct sched_rt_entity rt;
	/* ...... */
};
           

    程序排程的完整資料結構層次如下圖：

圖5 程序排程的資料結構層次

    各種結構的關系如上圖所示。樹的根通過 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 引用。通用排程器最後為此任務提供處理器。

    （2）排程實體：struct sched_entity

    該結構在./linux/include/linux/sched.h中，表示一個可排程實體（程序，程序組，等等）。它包含了完整的排程資訊，用于實作對單個任務或任務組的排程。排程實體可能與程序沒有關聯。

[cpp] view plain copy print ?

1. struct sched_entity {  
2.     struct load_weight  load;         
3.     struct rb_node      run_node;     
4.     struct list_head    group_node;  
5.     unsigned int        on_rq;  
6.     u64         exec_start;  
7.     u64         sum_exec_runtime;  
8.     u64         vruntime;          
9.     u64         prev_sum_exec_runtime;  
10.     u64         last_wakeup;  
11.     u64         avg_overlap;  
12.     u64         nr_migrations;  
13.     u64         start_runtime;  
14.     u64         avg_wakeup;  
15.     u64         avg_running;  
16. #ifdef CONFIG_SCHEDSTATS   
17.     u64         wait_start;  
18.     u64         wait_max;  
19.     u64         wait_count;  
20.     u64         wait_sum;  
21.     u64         iowait_count;  
22.     u64         iowait_sum;  
23.     u64         sleep_start;  
24.     u64         sleep_max;  
25.     s64         sum_sleep_runtime;  
26.     u64         block_start;  
27.     u64         block_max;  
28.     u64         exec_max;  
29.     u64         slice_max;  
30.     u64         nr_migrations_cold;  
31.     u64         nr_failed_migrations_affine;  
32.     u64         nr_failed_migrations_running;  
33.     u64         nr_failed_migrations_hot;  
34.     u64         nr_forced_migrations;  
35.     u64         nr_wakeups;  
36.     u64         nr_wakeups_sync;  
37.     u64         nr_wakeups_migrate;  
38.     u64         nr_wakeups_local;  
39.     u64         nr_wakeups_remote;  
40.     u64         nr_wakeups_affine;  
41.     u64         nr_wakeups_affine_attempts;  
42.     u64         nr_wakeups_passive;  
43.     u64         nr_wakeups_idle;  
44. #endif   
45. #ifdef CONFIG_FAIR_GROUP_SCHED   
46.     struct sched_entity *parent;  
47.     struct cfs_rq       *cfs_rq;  
48.     struct cfs_rq       *my_q;  
49. #endif   
50. };  

struct sched_entity {
	struct load_weight	load;		/* 用于負載平衡 */
	struct rb_node		run_node;	/* 對應的紅黑樹結點 */
	struct list_head	group_node;
	unsigned int		on_rq;

	u64			exec_start;
	u64			sum_exec_runtime;
	u64			vruntime;	     /* 虛拟運作時 */
	u64			prev_sum_exec_runtime;

	u64			last_wakeup;
	u64			avg_overlap;

	u64			nr_migrations;

	u64			start_runtime;
	u64			avg_wakeup;

	u64			avg_running;

#ifdef CONFIG_SCHEDSTATS
	u64			wait_start;
	u64			wait_max;
	u64			wait_count;
	u64			wait_sum;
	u64			iowait_count;
	u64			iowait_sum;

	u64			sleep_start;
	u64			sleep_max;
	s64			sum_sleep_runtime;

	u64			block_start;
	u64			block_max;
	u64			exec_max;
	u64			slice_max;

	u64			nr_migrations_cold;
	u64			nr_failed_migrations_affine;
	u64			nr_failed_migrations_running;
	u64			nr_failed_migrations_hot;
	u64			nr_forced_migrations;

	u64			nr_wakeups;
	u64			nr_wakeups_sync;
	u64			nr_wakeups_migrate;
	u64			nr_wakeups_local;
	u64			nr_wakeups_remote;
	u64			nr_wakeups_affine;
	u64			nr_wakeups_affine_attempts;
	u64			nr_wakeups_passive;
	u64			nr_wakeups_idle;
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
	struct sched_entity	*parent;
	/* rq on which this entity is (to be) queued: */
	struct cfs_rq		*cfs_rq;
	/* rq "owned" by this entity/group: */
	struct cfs_rq		*my_q;
#endif
};
           

    這裡包括負載權重load、對應的紅黑樹結點run_node、虛拟運作時vruntime（表示程序的運作時間，并作為紅黑樹的索引）、開始執行時間、最後喚醒時間、各種統計資料、用于組排程的CFS運作隊列資訊cfs_rq，等等。

    （3）排程類：struct sched_class

    該排程類也在sched.h中，是對排程器操作的面向對象抽象，協助核心排程程式的各種工作。排程類是排程器管理器的核心，每種排程算法子產品需要實作struct sched_class建議的一組函數。

[cpp] view plain copy print ?

1. struct sched_class {  
2.     const struct sched_class *next;  
3.     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup,  
4.                   bool head);  
5.     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);  
6.     void (*yield_task) (struct rq *rq);  
7.     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);  
8.     struct task_struct * (*pick_next_task) (struct rq *rq);  
9.     void (*put_prev_task) (struct rq *rq, struct task_struct *p);  
10. #ifdef CONFIG_SMP   
11.     int  (*select_task_rq)(struct rq *rq, struct task_struct *p,  
12.                    int sd_flag, int flags);  
13.     unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,  
14.             struct rq *busiest, unsigned long max_load_move,  
15.             struct sched_domain *sd, enum cpu_idle_type idle,  
16.             int *all_pinned, int *this_best_prio);  
17.     int (*move_one_task) (struct rq *this_rq, int this_cpu,  
18.                   struct rq *busiest, struct sched_domain *sd,  
19.                   enum cpu_idle_type idle);  
20.     void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);  
21.     void (*post_schedule) (struct rq *this_rq);  
22.     void (*task_waking) (struct rq *this_rq, struct task_struct *task);  
23.     void (*task_woken) (struct rq *this_rq, struct task_struct *task);  
24.     void (*set_cpus_allowed)(struct task_struct *p,  
25.                  const struct cpumask *newmask);  
26.     void (*rq_online)(struct rq *rq);  
27.     void (*rq_offline)(struct rq *rq);  
28. #endif   
29.     void (*set_curr_task) (struct rq *rq);  
30.     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);  
31.     void (*task_fork) (struct task_struct *p);  
32.     void (*switched_from) (struct rq *this_rq, struct task_struct *task,  
33.                    int running);  
34.     void (*switched_to) (struct rq *this_rq, struct task_struct *task,  
35.                  int running);  
36.     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,  
37.                  int oldprio, int running);  
38.     unsigned int (*get_rr_interval) (struct rq *rq,  
39.                      struct task_struct *task);  
40. #ifdef CONFIG_FAIR_GROUP_SCHED   
41.     void (*task_move_group) (struct task_struct *p, int on_rq);  
42. #endif   
43. };  

struct sched_class {
	const struct sched_class *next;

	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup,
			      bool head);
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
	void (*yield_task) (struct rq *rq);

	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

	struct task_struct * (*pick_next_task) (struct rq *rq);
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

#ifdef CONFIG_SMP
	int  (*select_task_rq)(struct rq *rq, struct task_struct *p,
			       int sd_flag, int flags);

	unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
			struct rq *busiest, unsigned long max_load_move,
			struct sched_domain *sd, enum cpu_idle_type idle,
			int *all_pinned, int *this_best_prio);

	int (*move_one_task) (struct rq *this_rq, int this_cpu,
			      struct rq *busiest, struct sched_domain *sd,
			      enum cpu_idle_type idle);
	void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
	void (*post_schedule) (struct rq *this_rq);
	void (*task_waking) (struct rq *this_rq, struct task_struct *task);
	void (*task_woken) (struct rq *this_rq, struct task_struct *task);

	void (*set_cpus_allowed)(struct task_struct *p,
				 const struct cpumask *newmask);

	void (*rq_online)(struct rq *rq);
	void (*rq_offline)(struct rq *rq);
#endif

	void (*set_curr_task) (struct rq *rq);
	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
	void (*task_fork) (struct task_struct *p);

	void (*switched_from) (struct rq *this_rq, struct task_struct *task,
			       int running);
	void (*switched_to) (struct rq *this_rq, struct task_struct *task,
			     int running);
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
			     int oldprio, int running);

	unsigned int (*get_rr_interval) (struct rq *rq,
					 struct task_struct *task);

#ifdef CONFIG_FAIR_GROUP_SCHED
	void (*task_move_group) (struct task_struct *p, int on_rq);
#endif
};
           

    看一下其中的主要函數：

    * enqueue_task：當某個任務進入可運作狀态時，該函數将得到調用。它将排程實體（程序）放入紅黑樹中，并對 nr_running 變量加 1。從前面“Linux程序管理”的分析中可知，程序建立的最後會調用該函數。

    * dequeue_task：當某個任務退出可運作狀态時調用該函數，它将從紅黑樹中去掉對應的排程實體，并從 nr_running 變量中減 1。

    * yield_task：在 compat_yield sysctl 關閉的情況下，該函數實際上執行先出隊後入隊；在這種情況下，它将排程實體放在紅黑樹的最右端。

    * check_preempt_curr：該函數将檢查目前運作的任務是否被搶占。在實際搶占正在運作的任務之前，CFS 排程程式子產品将執行公平性測試。這将驅動喚醒式（wakeup）搶占。

    * pick_next_task：該函數選擇接下來要運作的最合适的程序。

    * load_balance：每個排程程式子產品實作兩個函數，load_balance_start() 和 load_balance_next()，使用這兩個函數實作一個疊代器，在子產品的 load_balance 例程中調用。核心排程程式使用這種方法實作由排程子產品管理的程序的負載平衡。

    * set_curr_task：當任務修改其排程類或修改其任務組時，将調用這個函數。

    * task_tick：該函數通常調用自 time tick 函數；它可能引起程序切換。這将驅動運作時（running）搶占。

    排程類的引入是接口和實作分離的設計典範，你可以實作不同的排程算法（例如普通程序和實時程序的排程算法就不一樣），但由于有統一的接口，使得排程政策被子產品化，一個Linux排程程式可以有多個不同的排程政策。排程類顯著增強了核心排程程式的可擴充性。每個任務都屬于一個排程類，這決定了任務将如何排程。 排程類定義一個通用函數集，函數集定義排程器的行為。例如，每個排程器提供一種方式，添加要排程的任務、調出要運作的下一個任務、提供給排程器等等。每個排程器類都在一對一連接配接的清單中彼此相連，使類可以疊代（例如， 要啟用給定處理器的禁用）。注意，将任務函數加入隊列或脫離隊列隻需從特定排程結構中加入或移除任務。 核心函數 pick_next_task 選擇要執行的下一個任務（取決于排程類的具體政策）。排程類的圖形視圖如下：

圖6 排程類圖形視圖

    這裡sched_rt.c, sched_fair.c, sched_idletask.c等（都在kernel/目錄下）就是不同的排程算法實作。不要忘了排程類是任務結構本身的一部分（參見task_struct）。這一點簡化了任務的操作，無論其排程類如何。因為程序描述符中有sched_class引用，這樣就可以直接通過程序描述符來調用排程類中的各種操作。在排程類中，随着排程域的增加，其功能也在增加。 這些域允許您出于負載平衡和隔離的目的将一個或多個處理器按層次關系分組。 一個或多個處理器能夠共享排程政策（并在其之間保持負載平衡），或實作獨立的排程政策。

    不過Linux排程程式本身還沒有被子產品化，這是一個可以改進的地方。例如對Pluggable CPU排程程式架構，在核心編譯時可以選擇預設排程程式，在啟動時通過向核心傳遞參數也可以選擇其他的CPU排程程式。

    （4）可運作隊列：struct rq

    排程程式每次在程序發生切換時，都要從可運作隊列中選取一個最佳的程序來運作。Linux核心使用rq資料結構（以前的核心中該結構為runqueue）表示一個可運作隊列資訊（也就是就緒隊列），每個CPU都有且隻有一個這樣的結構。該結構在kernel/sched.c中，不僅描述了每個處理器中處于可運作狀态（TASK_RUNNING），而且還描述了該處理器的排程資訊。如下：

[cpp] view plain copy print ?

1. struct rq {  
2.     spinlock_t lock;  
3.     unsigned long nr_running;  
4.     #define CPU_LOAD_IDX_MAX 5   
5.     unsigned long cpu_load[CPU_LOAD_IDX_MAX];  
6. #ifdef CONFIG_NO_HZ   
7.     unsigned long last_tick_seen;  
8.     unsigned char in_nohz_recently;  
9. #endif   
10.     struct load_weight load;  
11.     unsigned long nr_load_updates;  
12.     u64 nr_switches;  
13.     struct cfs_rq cfs;  
14.     struct rt_rq rt;  
15. #ifdef CONFIG_FAIR_GROUP_SCHED   
16.     struct list_head leaf_cfs_rq_list;  
17. #endif   
18. #ifdef CONFIG_RT_GROUP_SCHED   
19.     struct list_head leaf_rt_rq_list;  
20. #endif   
21.     unsigned long nr_uninterruptible;  
22.     struct task_struct *curr, *idle;  
23.     unsigned long next_balance;  
24.     struct mm_struct *prev_mm;  
25.     u64 clock;  
26.     u64 clock_task;  
27.     atomic_t nr_iowait;  
28. #ifdef CONFIG_SMP   
29.     struct root_domain *rd;  
30.     struct sched_domain *sd;  
31.     unsigned long cpu_power;  
32.     unsigned char idle_at_tick;  
33.     int post_schedule;  
34.     int active_balance;  
35.     int push_cpu;  
36.     int cpu;  
37.     int online;  
38.     unsigned long avg_load_per_task;  
39.     struct task_struct *migration_thread;  
40.     struct list_head migration_queue;  
41.     u64 rt_avg;  
42.     u64 age_stamp;  
43.     u64 idle_stamp;  
44.     u64 avg_idle;  
45. #endif   
46. #ifdef CONFIG_IRQ_TIME_ACCOUNTING   
47.     u64 prev_irq_time;  
48. #endif   
49.     unsigned long calc_load_update;  
50.     long calc_load_active;  
51. #ifdef CONFIG_SCHED_HRTICK   
52. #ifdef CONFIG_SMP   
53.     int hrtick_csd_pending;  
54.     struct call_single_data hrtick_csd;  
55. #endif   
56.     struct hrtimer hrtick_timer;  
57. #endif   
58. #ifdef CONFIG_SCHEDSTATS   
59.     struct sched_info rq_sched_info;  
60.     unsigned long long rq_cpu_time;  
61.     unsigned int yld_count;  
62.     unsigned int sched_switch;  
63.     unsigned int sched_count;  
64.     unsigned int sched_goidle;  
65.     unsigned int ttwu_count;  
66.     unsigned int ttwu_local;  
67.     unsigned int bkl_count;  
68. #endif   
69. };  

struct rq {
	/* runqueue lock: */
	spinlock_t lock;

	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	unsigned long nr_running;
	#define CPU_LOAD_IDX_MAX 5
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
#ifdef CONFIG_NO_HZ
	unsigned long last_tick_seen;
	unsigned char in_nohz_recently;
#endif
	/* capture load from *all* tasks on this cpu: */
	struct load_weight load;
	unsigned long nr_load_updates;
	u64 nr_switches;

	struct cfs_rq cfs;
	struct rt_rq rt;

#ifdef CONFIG_FAIR_GROUP_SCHED
	/* list of leaf cfs_rq on this cpu: */
	struct list_head leaf_cfs_rq_list;
#endif
#ifdef CONFIG_RT_GROUP_SCHED
	struct list_head leaf_rt_rq_list;
#endif

	/*
	 * This is part of a global counter where only the total sum
	 * over all CPUs matters. A task can increase this counter on
	 * one CPU and if it got migrated afterwards it may decrease
	 * it on another CPU. Always updated under the runqueue lock:
	 */
	unsigned long nr_uninterruptible;

	struct task_struct *curr, *idle;
	unsigned long next_balance;
	struct mm_struct *prev_mm;

	u64 clock;
	u64 clock_task;

	atomic_t nr_iowait;

#ifdef CONFIG_SMP
	struct root_domain *rd;
	struct sched_domain *sd;

	unsigned long cpu_power;

	unsigned char idle_at_tick;
	/* For active balancing */
	int post_schedule;
	int active_balance;
	int push_cpu;
	/* cpu of this runqueue: */
	int cpu;
	int online;

	unsigned long avg_load_per_task;

	struct task_struct *migration_thread;
	struct list_head migration_queue;

	u64 rt_avg;
	u64 age_stamp;
	u64 idle_stamp;
	u64 avg_idle;
#endif

#ifdef CONFIG_IRQ_TIME_ACCOUNTING
	u64 prev_irq_time;
#endif

	/* calc_load related fields */
	unsigned long calc_load_update;
	long calc_load_active;

#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
	int hrtick_csd_pending;
	struct call_single_data hrtick_csd;
#endif
	struct hrtimer hrtick_timer;
#endif

#ifdef CONFIG_SCHEDSTATS
	/* latency stats */
	struct sched_info rq_sched_info;
	unsigned long long rq_cpu_time;
	/* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */

	/* sys_sched_yield() stats */
	unsigned int yld_count;

	/* schedule() stats */
	unsigned int sched_switch;
	unsigned int sched_count;
	unsigned int sched_goidle;

	/* try_to_wake_up() stats */
	unsigned int ttwu_count;
	unsigned int ttwu_local;

	/* BKL stats */
	unsigned int bkl_count;
#endif
};
           

    rq結構是主要的（每個CPU上的）運作隊列資料結構。其加鎖的規則是：在那些想鎖住多個運作隊列的地方（例如負載均衡或者線程遷移代碼），鎖的擷取操作必須按運作隊列的升序排序。rq中的部分核心成員含義如下：

    spinlock_t lock：保護程序連結清單的自旋鎖。

    unsigned long nr_running：目前處理器的運作隊列中程序數量。

    unsigned long cpu_load[CPU_LOAD_IDX_MAX]：用以表示處理器的負載，在每個處理器的rq中都會有對應到該處理器的cpu_load參數配置，在每次處理器觸發scheduler tick時，都會呼叫函數update_cpu_load_active,進行cpu_load的更新。在系統初始化的時候會呼叫函數sched_init把rq的cpu_load array初始化為0。了解他的更新方式最好的方式是通過函數update_cpu_load,公式如下：

    cpu_load[0]會直接等待rq中load.weight的值。

    cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2

    cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4

    cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8

    cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16

    呼叫函數this_cpu_load時，所傳回的cpu load值是cpu_load[0]。而在進行cpu blance或migration時，就會呼叫函數source_load target_load取得對該處理器cpu_load index值，來進行計算。

    struct load_weight load：負載權重，即load->weight值。會是目前所執行的schedule entity的load->weight的總和，也就是說rq的load->weight越高，說明所負責的程序單元load->weight總和越高，表示處理器所負荷的執行單元也越重。

    unsigned long nr_load_updates：在每次scheduler tick中呼叫update_cpu_load時，這個值就增加一，可以用來回報目前cpu load更新的次數。

    u64 nr_switches：CPU執行程序切換的次數。用來累加處理器進行context switch的次數，會在函數schedule呼叫時進行累加，并可以通過函數nr_context_switches統計目前所有處理器總共的context switch次數，或是可以透過檢視檔案/proc/stat中的ctxt位得知目前整個系統觸發context switch的次數。

    struct cfs_rq cfs：用于公平排程的CFS運作隊列。

    struct rt_rq rt：用于實時程序排程的運作隊列。

    struct list_head leaf_cfs_rq_list：目前CPU上葉子cfs_rq的清單。

    unsigned long nr_uninterruptible：之前在運作隊列中而現在處于重度睡眠狀态的程序總數。

    task_t *curr：指向本地CPU目前正在運作的程序的程序描述符，即current。

    task_t *idle：指向本地CPU上的idle程序描述符的指針。

    unsigned long next_balance：基于處理器的jiffies值，用以記錄下次進行處理器balancing的時間點。

    struct mm_struct *prev_mm：在程序進行切換時用來存放被替換程序記憶體描述符的位址。

    u64 clock：目前CPU的時鐘值。

    int cpu：本運作隊列對應的CPU

    最後是排程的一個些統計資訊，包括sys_sched_yield()、schedule()、try_to_wake_up()的統計資訊。注意現在rq結構中已經沒有active/expire數組了，是以現在rq結構并不直接維護程序隊列，對CFS程序隊列由紅黑樹來維護（對實時排程則仍使用組連結清單），并且以時間為順序。rq結構中的cfs結構有指向紅黑樹的根結點，由此可以通路到紅黑樹。

    （5）CFS運作隊列：struct cfs_rq

    該結構在kernel/sched.c中，是用于CFS排程的運作隊列。對于每個運作隊列資訊，都提供了一個cfs_rq結構來儲存相關紅黑樹的資訊。

[cpp] view plain copy print ?

1. struct cfs_rq {  
2.     struct load_weight load;    
3.     unsigned long nr_running;    
4.     u64 exec_clock;  
5.     u64 min_vruntime;    
6.     struct rb_root tasks_timeline;    
7.     struct rb_node *rb_leftmost;      
8.     struct list_head tasks;  
9.     struct list_head *balance_iterator;  
10.     struct sched_entity *curr, *next, *last;  
11.     unsigned int nr_spread_over;  
12. #ifdef CONFIG_FAIR_GROUP_SCHED   
13.     struct rq *rq;    
14.     struct list_head leaf_cfs_rq_list;  
15.     struct task_group *tg;    
16. #ifdef CONFIG_SMP   
17.     unsigned long task_weight;  
18.     unsigned long h_load;  
19.     unsigned long shares;  
20.     unsigned long rq_weight;  
21. #endif   
22. #endif   
23. };  

struct cfs_rq {
	struct load_weight load;  /* 運作負載 */
	unsigned long nr_running;  /* 運作程序個數 */

	u64 exec_clock;
	u64 min_vruntime;  /* 儲存的最小運作時間 */

	struct rb_root tasks_timeline;  /* 運作隊列樹根 */
	struct rb_node *rb_leftmost;    /* 儲存的紅黑樹最左邊的節點，這個為最小運作時間的節點，
                                           當程序選擇下一個來運作時，直接選擇這個 */

	struct list_head tasks;
	struct list_head *balance_iterator;

	/*
	 * 'curr'指針指向本cfs_rq上目前正在運作的程序，如果本cfs_rq上沒有正在運作的程序，則指向NULL
	 */
	struct sched_entity *curr, *next, *last;

	unsigned int nr_spread_over;

#ifdef CONFIG_FAIR_GROUP_SCHED
	struct rq *rq;	/* 本cfs_rq關聯的運作隊列 */

	/* 葉子cfs_rqs是那些層次中最底層的可排程實體，它們持有程序。非葉子lrqs持有其他更高層的可調用實體（例如使用者，容器等）
	 * leaf_cfs_rq_list用來把一個CPU上的葉子cfs_rq清單串結成一個清單，這個清單被用在負載平衡中
	 */
	struct list_head leaf_cfs_rq_list;
	struct task_group *tg;	/* 擁有本運作隊列的組 */

#ifdef CONFIG_SMP
	/*
	 * 由程序貢獻的load.weight部分
	 */
	unsigned long task_weight;

	/*
	 *   h_load = weight * f(tg)
	 * 其中f(tq)表示配置設定給組的疊代權重值
	 */
	unsigned long h_load;

	/*
	 * this cpu's part of tg->shares
	 */
	unsigned long shares;

	/*
	 * load.weight at the time we set shares
	 */
	unsigned long rq_weight;
#endif
#endif
};
           

    其中有紅黑樹的根結點、指向目前隊列上正在運作程序的curr，用于負載平衡的葉子隊列leaf_cfs_rq_list，貢獻的負載權重值task_weight等。

    （6）紅黑樹結點：struct rb_node, struct rb_root

[cpp] view plain copy print ?

1. struct rb_node  
2. {  
3.     unsigned long  rb_parent_color;  
4. #define RB_RED      0   
5. #define RB_BLACK    1   
6.     struct rb_node *rb_right;  
7.     struct rb_node *rb_left;  
8. } __attribute__((aligned(sizeof(long))));  
9. struct rb_root  
10. {  
11.     struct rb_node *rb_node;  
12. };  

struct rb_node
{
	unsigned long  rb_parent_color;
#define	RB_RED		0
#define	RB_BLACK	1
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
	struct rb_node *rb_node;
};
           

    rb_node和rb_root的定義在./linux/include/linux/rbtree.h中，其中rb_root表示紅黑樹的根結點。紅黑樹的實作在./linux/lib/rbtree.c中，包括插入、删除、旋轉、周遊等操作。

    還有很多其他的資料結構，如排程域sche_domain（在include/linux/sched.h中）、根域root_domain（在kernel/sched.c中）、任務組task_group（在kernel/sched.c中）等，這裡不一一介紹了。

     我們可以從設計層面來總結Linux程序排程一些設計思想：

     把程序抽象成程序描述符task_struct：包含程序所必需的資料，如狀态資訊、排程資訊、優先級資訊、記憶體頁資訊等。

     把需要排程的東西抽象成排程實體sched_entity：排程實體可以是程序、程序組、使用者等。這裡包含負載權重值、對應紅黑樹結點、虛拟運作時vruntime等。

    把排程政策（算法）抽象成排程類sched_class：包含一組通用的排程操作接口，将接口和實作分離。你可以根據這組接口實作不同的排程算法，使得一個Linux排程程式可以有多個不同的排程政策。

     把排程的組織抽象成可運作隊列rq：包含自旋鎖、程序數量、用于公平排程的CFS資訊結構、目前正在運作的程序描述符等。實際的程序隊列用紅黑樹來維護（通過CFS資訊結構來通路）。

    把CFS排程的運作隊列資訊抽象成cfs_rq：包含紅黑樹的根結點、正在運作的程序指針、用于負載平衡的葉子隊列等