linux排程器的一般原理請參閱《linux程序排程淺析》。
之前的排程器
cfs之前的linux排程器一般使用使用者設定的靜态優先級，加上對于程序互動性的判斷來生成動态優先級，再根據動态優先級決定程序被排程的順序，以及排程後可以運作的時間片。
反過來，随着程序的運作，核心可能發現其互動性發生改變，進而調整其動态優先級（獎勵睡眠多的互動式程序、懲罰睡眠少的批處理程序）。
cfs原理
cfs定義了一種新的模型，它給cfs_rq（cfs的run queue）中的每一個程序安排一個虛拟時鐘，vruntime。
如果一個程序得以執行，随着時間的增長（也就是一個個tick的到來），其vruntime将不斷增大。沒有得到執行的程序vruntime不變。
而排程器總是選擇vruntime跑得最慢的那個程序來執行。這就是所謂的“完全公平”。
為了差別不同優先級的程序，優先級高的程序vruntime增長得慢，以至于它可能得到更多的運作機會。
如下圖所示（注意，圖中的tick、load、vruntime隻是個示意）：
vruntime标準化
随着系統的不斷運作，程序的vruntime不斷增長。如果溢出了怎麼辦呢？
cfs給cfs_rq也設定了一個vruntime（cfs_rq->min_vruntime），這個時鐘有兩個特性：1)單調遞增；2)如果滿足第1點，讓它等于cfs_rq中最小的虛拟時鐘。（cfs_rq->min_vruntime一般情況下總是等于隊列中最小的vruntime，不過下面會提到程序睡眠喚醒的情況，這時新喚醒的程序的vruntime可能小于cfs_rq->min_vruntime。而cfs_rq->min_vruntime并不會是以而減小，依然保持單調遞增。）
選擇程序時，總是以程序的vruntime與cfs_rq->min_vruntime之差來作為判斷依據的。而這個內插補點基本上是不可能溢出的。這個內插補點被稱作normalized vruntime（标準化的虛拟時鐘）。
有了這個normalized vruntime，在程序enqueue/dequeue、或者是在cfs_rq間遷移、等情況下，程序的vruntime就有了統一的描述。
當程序dequeue時，其vruntime -= cfs_rq->min_vruntime。而當它再次enqueue時，vruntime += cfs_rq->min_vruntime（注意，兩個cfs_rq可能不是同一個）。
處理睡眠程序
linux的排程器一直認為，應該對互動式程序（也就是睡眠多的程序）給予獎勵。這個在cfs裡面是怎麼表現的呢？
差別于其他的情況，如果程序因為睡眠而dequeue，這時vruntime繼續保持原值，并不做normalize。那麼，等它被喚醒的時候，vruntime仍舊是一個較小的值，相當于得到了獎勵。
但是，如果隻是簡單的不做normalize，睡眠程序由于得不到運作，其虛拟時鐘不增長，那麼一個程序就可以在漫長的睡眠之後，進行報複性的滿載運作。這顯然是不合理的。
是以，程序在被喚醒之後，需要對其vruntime進行修正。vruntime=max(vruntime, cfs_rq->min_vruntime - thresh)。
即，分兩種情況：
1、如果程序隻是短暫睡眠，其vruntime > cfs_rq->min_vruntime - thresh，則vruntime保持原樣；
2、長時間睡眠，其vruntime <= cfs_rq->min_vruntime - thresh，則vruntime修改為cfs_rq->min_vruntime - thresh。
這裡的thresh可以認為等于一個排程延遲。
排程延遲
那麼，什麼是排程延遲呢？
cfs的原理是選擇vruntime最小的那個程序來運作。而如果cfs_rq中有兩個旗鼓相當的程序呢？可能導緻每個tick都會觸發一次switch。（a程序運作一個tick之後，vruntime超過b程序，于是switch到b程序；而b程序運作一個tick之後，vruntime又超過a程序，于是又switch到a程序；如此反複……）
這樣做雖然很公平，但是無疑帶來了很大的排程開銷，是不可接受的。
于是cfs為權衡公平性與性能，引入了排程延遲的概念。有人将排程延遲定義為：保證cfs_rq中的每個程序至少運作一次的時間間隔。但是我覺得這并不準确，因為cfs并不提供“至少運作一次”這樣的保證。在我看來，排程延遲就是提供一個延遲，使得cfs并不是每個tick都去檢查是否需要re-schedule，而是要延遲到一定程度再re-schedule。
對于不同的程序，當它在執行的時候，這個re-schedule的延遲是不一樣的。如果把排程延遲視作一個時間片，那麼cfs_rq中的每個程序将以其優先級為權重，瓜分這個時間片。程序分得的時間片大小跟其優先級是成正比的，也就是說，優先級高的程序能夠執行更多的時間，然後才會被re-schedule。
在cfs_rq穩定的情況下（也就是沒有程序enqueue/dequeue、也沒有程序修改優先級、等），因為vruntime的增長率也是跟程序的優先級成正比的，是以随着程序按優先級權重瓜分排程延遲，這些程序在各自用完一個時間片之後vruntime将得到同等的增長，并且在一個排程延遲内，每個程序都将被執行一次（這也就是為什麼排程延遲會被定義為“保證每個程序至少運作一次”）。
但是當cfs_rq發生變化，情況就有所不同。随着不斷有程序enqueue/dequeue、或者改變優先級，正在執行的程序的時間片是随時在變化的。如果某一時刻，cfs發現正在執行的程序用完了它的時間片，就會re-schedule；或者當正在執行的程序的vruntime與cfs_rq中最小的vruntime之差大于它的時間片時，也會re-schedule。
對應到前面讨論的睡眠喚醒，長時間睡眠的程序在被喚醒之後，vruntime修改為cfs_rq->min_vruntime減去一個排程延遲。那麼這個被喚醒的程序很有可能會将正在執行的程序搶占掉。被喚醒的程序很可能優先得到執行，并且一開始會得到更多的cpu時間，以使其vruntime追趕上其他程序。但是之後它便不能再得到這樣的優待，因為對于vruntime相同的程序來說，能分得多少cpu時間決定于它的優先級，而優先級并不因為睡眠喚醒而改變。
通常，排程延遲是一個固定的值，比如20ms。而如果cfs_rq中的程序過多，每個程序就會分得很小的時間片，這也可能頻繁的觸發排程。于是，這種情況下排程延遲會按cfs_rq中的程序數線性擴充。（注意，如這裡所描述的，排程延遲其實是一個跟cfs_rq相對應的概念。不同的cfs_rq程序數可能不同，則它們的排程延遲也不相同。）
load balance
在cfs之前，程序的優先級通常用nice、priority這樣的單詞來表示。而在cfs中則通常使用load（負載）這個詞。程序有程序的load、cfs_rq有cfs_rq的load。
一開始感覺這個“load”用得很奇怪，不過後來慢慢有了些體會：nice、priority是站在程序的角度，描述了其自身的優先級；而load則是站在cfs_rq的角度，描述了程序給cfs_rq帶來的負載。
對于程序的load，一方面它隐含了程序的優先級。程序的load越高，vruntime也就跑得越慢，為了增長同等的vruntime所獲得的執行時間也就越多；另一方面，程序的load也展現了它給cfs_rq施加的負載。對于load越高的程序，為了給它增長同等的vruntime，需要花費越多的cpu時間。
而cfs_rq的load則展現了cfs_rq中的程序給它施加的總的負載。cfs_rq中的程序越多、程序的優先級越高，增長同等的cfs_rq->min_vruntime所花費的時間就越多。
再來說說load_balance，也就是負載均衡。詳見：《linux核心smp負載均衡淺析》。
其目的把需要做的事情均勻配置設定到系統中的每個cpu上。假設所有cfs_rq中的程序的load之和為m，cpu個數為n，在負載均衡的情況下，對于一個load為a的程序來說，它将分得a*n/m的cpu時間。
load_balance是怎麼做的呢？顧名思義，它所要做的事情就是将程序的load均勻分布在每一個cpu所對應的cfs_rq中（通過在cfs_rq之間遷移一些程序來實作）。
那麼為什麼load均勻分布在每個cfs_rq中就能實作負載均衡呢？
繼續前面的例子，其實隻要每個cfs_rq的load都等于m/n，無論這個load為a的程序處于哪個cfs_rq中，它分得的cpu時間都是a*n/m。
組排程
關于組排程，詳見：《linux組排程淺析》。簡單來說，引入組排程是為了實作做一件事的一組程序與做另一件事的另一組程序的隔離。每件“事情”各自有自己的權重，而不管它需要使用多少程序來完成。
在cfs中，task_group和程序是同等對待的，task_group的優先級也由使用者來控制（通過cgroup檔案cpu.shares）。
實作上，task_group和程序都被抽象成schedule_entity（排程實體，以下簡稱se），上面說到的vruntime、load、等這些東西都被封裝在se裡面。
而task_group除了有se之外，還有cfs_rq。屬于這個task_group的程序就被裝在它的cfs_rq中（“組”不僅是一個被排程的實體，也是一個容器）。
組排程引入以後，一系列task_group的cfs_rq組成了一個樹型結構。樹根是cpu所對應的cfs_rq（也就是root group的cfs_rq）、樹的中間節點是各個task_group的cfs_rq、葉子節點是各個程序。
在一個task_group的兩頭，是兩個不同的世界，就像《盜夢空間》裡不同層次的夢境一樣。
以group-1為例，它所對應的se被加入到父組（cpu_rq）的cfs_rq中，接受排程。這個se有自己的load（由對應的cpu.shares檔案來配置），不管group-1下面有多少個程序，這個load都是這個值。父組看不到、也不關心group-1下的程序。父組隻會根據這個se的load和它執行的時間來更新其vruntime。
當group-1被排程器選中後，會繼續選擇其下面的task-11或task-12來執行。這裡又是一套獨立的體系，task-11與task-12的vruntime、load、等這些東西隻影響它們在group-1的cfs_rq中的排程情況。
樹型結構中的每一個cfs_rq都是獨立完成自己的排程邏輯。不過，從cpu配額上看，task_group的配額會被其子孫層層瓜分。
例如上圖中的task-11，它所在的group-1對應se的load是8，而group-1下兩個程序的load是9和3，task-11占其中的3/4。于是，在group-1所對應的cfs_rq内部看，task-11的load是9，而從全局來看，task-11的load是8*3/4=6。
而task_group下的程序的時間片也是這樣層層瓜分而來的，比如說group-1的cfs_rq下隻有兩個程序，計算得來的排程延遲是20ms。但是task-11并非占其中的3/4（15ms）。因為group-1的se的load占總額的8/(8+3+5)=1/2，是以task-11的load占總額的1/2*3/4=3/8，時間片是20ms*3/8=7.5ms。
這樣的瓜分有可能使得task_group裡面的程序分得很小的時間片，進而導緻頻繁re-schedule。不過好在這并不影響task_group外面的其他程序，并且也可以盡量讓task_group裡面的程序在每個排程延遲内都執行一次。
cfs曾經有過時間片不層層瓜分的實作，比如上圖中的task-11，時間片算出來是15ms就是15ms，不用再瓜分了。這樣做的好處是不會有頻繁的re-schedule。但是task_group裡的程序可能會很久才被執行一次。
瓜分與不瓜分兩種方案的示例如下（還是繼續上圖的例子，深藍色代表task-11、淺藍色是task-12，空白是其他程序）：
兩種方案好像很難說清孰優孰劣，貌似cfs也在這兩種方案間糾結了好幾次。
在程序用完其時間片之前，有可能它所在的task_group的se先用完了時間片，而被其父組re-schedule掉。這種情況下，當這個task_group的se再一次被其父組選中時，上次得到執行、且尚未用完時間片的那個程序将繼續運作，直到它用完時間片。（cfs_rq->last會記錄下這個尚未用完時間片的程序。）
組排程與load balance
在smp情況下，按cpu的個數，一個task_group擁有多個se及其對應的cfs_rq。屬于這個task_group的程序可能出現在這些不同的cfs_rq之中（意味着這些程序運作在不同cpu上）。這些cfs_rq可能存在load不均的情況。
為了解決這個問題，大緻有兩種方法：
1、在load_balance的時候，為每一個task_group都執行一遍load_balance邏輯，使得每個task_group内部都趨于load均衡；
2、load_balance隻針對root group。然後如果task_group内部的load不均，則load高的那個cfs_rq所對應的se的load得到提升，進而使得這個cfs_rq分得更多時間、或者引發root group的load_balance；
第一種方法貌似更完美，但是代價更大。不過其實它并非真正完美，比如task_group下隻有兩個running狀态的程序，一個load很高、一個load很低，那麼無論如何也沒法在這個task_group内做到balance。并且，在對一個task_group進行load_balance的時候，并不知道其他task_group imbalance的情況，是以全局的balance也很難做到。
是以核心選擇了方法二。下面再仔細分析下：
方法二有兩個要素：
1、針對task_group内部的load不均，修正task_group在不同cpu上的se的load；
task_group在每個cpu上的se的load是以其對應cfs_rq的load為權重，瓜分cpu.shares而得來。
如圖，group-1在cpu-0上的cfs_rq的load為5+5=10，在cpu-1上的cfs_rq的load為5，而設group-1的cpu.shares為9，則cpu-0上的se的load為：9*10/(10+5)=6。
2、因為task_group内部的load不均可能引起task_group對應各個cpu上的se的load不均，進而引起父組的load不均，繼而引起root group的load_balance，是以load_balance在做程序遷移的時候，需要考慮task_group内的程序；
在觸發程序遷移的時候，對于cpu上的每個task_group的cfs_rq都會試圖進行一定量的程序遷移。
如圖，load_balance之前兩個cpu的load是不均的（6+8 > 3+5）。而load_balance之後，通過遷移group-1下的task-12，使得兩個cpu的load均衡（3+8 = 6+5）。
task_group下的程序遷移，并不會影響程序所分得的load。比如task-12，在它被遷移之前，它所在的cfs_rq所對應的se的load是6，而它在這個cfs_rq中能分得一半的load，全局來看，load是3；遷移之後，task-12同樣分得6*5/(5+5)=3的load。類似的，在task-12遷移前後，task-11和task-13所能分得的load也是相同的。