[[398959]]

本文轉載自微信公眾號「人人都是極客」，作者布道師Peter。轉載本文請聯系人人都是極客公眾號。

調度的發展歷史

• O(n) 調度器是在內核2.4以及更早期版本采用的算法，其調度算法非常簡單和直接，就緒隊列是個全局列表，從就緒隊列中查找下一個最佳任務，由于每次在尋找下一個任務時需要遍歷系統中所有的任務(全局列表)，因此被稱為 O(n) 調度器(時間復雜度)。
• 內核2.6采用了O(1) 調度器，讓每個CPU維護一個自己的就緒隊列，從而減少了鎖的競爭。就緒隊列由兩個優先級數組組成，分別是active優先級數組和expired優先級數組。每個優先級數組包含140個優先級隊列，也就是每個優先級對應一個隊列，其中前100個對應實時進程，后40個對應普通進程。如下圖所示：

這樣設計的好處，調度器選擇下一個被調度任務就變得高效和簡單多了，只需要在active優先級數組中選擇優先級高，并且隊列中有可運行的任務即可。這里使用位圖來定義該隊列中是否有可運行的任務，如果有，則位圖中相應的位就會被置1。這樣選擇下一個被調用任務的時間就變成了查詢位圖的操作。

• 但上面的算法有個問題，一個高優先級多線程的應用會比低優先級單線程的應用獲得更多的資源，這就會導致一個調度周期內，低優先級的應用可能一直無法響應，直到高優先級應用結束。CFS調度器就是站在一視同仁的角度解決了這個問題，保證在一個調度周期內每個任務都有執行的機會，執行時間的長短，取決于任務的權重。下面詳細看下CFS調度器是如何動態調整任務的運行時間，達到公平調度的。

實際運行時間

CFS是Completely Fair Scheduler簡稱，即完全公平調度器。CFS調度器和以往的調度器不同之處在于沒有時間片的概念，而是公平分配cpu使用的時間。例如：2個相同優先級的進程在一個cpu上運行，那么每個進程都將會分配50%的cpu運行時間。這就是要實現的公平。

但現實中，必然是有的進程優先級高，有的進程優先級低。CFS調度器引入權重的概念，用權重代表進程的優先級，各個進程按照權重的比例分配cpu的時間。比如：2個進程A和B。A的權重是1024，B的權重是2048。那么A獲得cpu的時間比例是1024/(1024+2048) = 33.3%。B進程獲得的cpu時間比例是2048/(1024+2048)=66.7%。

在引入權重之后，分配給進程的時間計算公式如下：

實際運行時間 = 調度周期 * 進程權重 / 所有進程權重之和

CFS調度器用nice值表示優先級，取值范圍是[-20, 19]，nice和權重是一一對應的關系。數值越小代表優先級越大，同時也意味著權重值越大，nice值和權重之間的轉換關系：

const int sched_prio_to_weight[40] = { 
 /* -20 */     88761,     71755,     56483,     46273,     36291, 
 /* -15 */     29154,     23254,     18705,     14949,     11916, 
 /* -10 */      9548,      7620,      6100,      4904,      3906, 
 /*  -5 */      3121,      2501,      1991,      1586,      1277, 
 /*   0 */      1024,       820,       655,       526,       423, 
 /*   5 */       335,       272,       215,       172,       137, 
 /*  10 */       110,        87,        70,        56,        45, 
 /*  15 */        36,        29,        23,        18,        15, 
};  

數組值計算公式是：weight = 1024 / 1.25nice。

公式中的1.25取值依據是：進程每降低一個nice值，將多獲得10% cpu的時間。公式中以1024權重為基準值計算得來，1024權重對應nice值為0，其權重被稱為NICE_0_LOAD。默認情況下，大部分進程的權重基本都是NICE_0_LOAD。

虛擬運行時間

根據上面的理解，這里看個例子。假如一個CPU的調度周期是6ms，進程A和B的權重分別是1024和820(nice值分別是0和1)，那么進程A獲得的運行時間是6x1024/(1024+820)=3.3ms，進程B獲得的執行時間是6x820/(1024+820)=2.7ms。進程A的cpu使用比例是3.3/6x100%=55%，進程B的cpu使用比例是2.7/6x100%=45%。(符合上面說的“進程每降低一個nice值，將多獲得10% CPU的時間”)

很明顯，2個進程的實際執行時間是不相等的，但是CFS想保證每個進程運行時間相等。因此CFS引入了虛擬時間的概念，也就是說上面的2.7ms和3.3ms經過一個公式的轉換可以得到一樣的值，這個轉換后的值稱作虛擬時間。這樣的話，CFS只需要保證每個進程運行的虛擬時間是相等的即可。虛擬時間vriture_runtime和實際時間(wall time)轉換公式如下：

虛擬運行時間 = 實際運行時間 * NICE_0_LOAD / 進程權重 = (調度周期 * 進程權重 / 所有進程權重之和) * NICE_0_LOAD / 進程權重 = 調度周期 * 1024 / 所有進程總權重

從公式可以看出，在一個調度周期里，所有進程的虛擬運行時間是相同的。所以在進程調度時，只需要找到虛擬運行時間最小的進程調度運行即可。

為了能夠快速找到虛擬運行時間最小的進程，Linux 內核使用紅黑樹來保存可運行的進程。CFS跟蹤調度實體sched_entity的虛擬運行時間vruntime，將sched_entity通過enqueue_entity()和dequeue_entity()來進行紅黑樹的出隊入隊，vruntime少的調度實體sched_entity排列到紅黑樹的左邊。

如上圖所示，紅黑樹的左節點比父節點小，而右節點比父節點大。所以查找最小節點時，只需要獲取紅黑樹的最左節點即可。

相關步驟如下：

• 每個sched_latency周期內，根據各個任務的權重值，可以計算出運行時間runtime;
• 運行時間runtime可以轉換成虛擬運行時間vruntime;
• 根據虛擬運行時間的大小，插入到CFS紅黑樹中，虛擬運行時間少的調度實體放置到左邊;
• 在下一次任務調度的時候，選擇虛擬運行時間少的調度實體來運行(pick_next_task從就緒隊列中選擇最適合運行的調度實體，即虛擬時間最小的調度實體);

CFS 數據結構

task_struct: 任務描述符，包含很多進程相關的信息，例如，優先級、進程狀態以及調度實體等。

struct task_struct { 
    ... 
    struct sched_entity se; 
    ... 
} 

cfs_rq：跟蹤就緒隊列信息以及管理就緒態調度實體，并維護一棵按照虛擬時間排序的紅黑樹。tasks_timeline->rb_root是紅黑樹的根，tasks_timeline->rb_leftmost指向紅黑樹中最左邊的調度實體，即虛擬時間最小的調度實體。

struct cfs_rq { 
  ... 
  struct rb_root_cached tasks_timeline 
  ... 
}; 

sched_entity：可被內核調度的實體。每個就緒態的調度實體sched_entity包含插入紅黑樹中使用的節點rb_node，同時vruntime成員記錄已經運行的虛擬時間。

struct sched_entity { 
  ... 
  struct rb_node    run_node;       
  ... 
  u64          vruntime;               
  ... 
}; 

這些數據結構的關系如下圖所示：

CFS 算法實現

1.時鐘中斷 scheduler_tick 更新虛擬運行時間，檢查是否需要搶占。

更新運行時的各類統計信息，比如vruntime， 運行時間、負載值、權重值等。

檢查是否需要搶占，主要是比較運行時間是否耗盡，以及vruntime的差值是否大于運行時間等。

2.任務出隊入隊

當任務進入可運行狀態時，用 enqueue_task_fair 將調度實體放入到紅黑樹中，完成入隊操作;當任務退出可運行狀態時，用 dequeue_task_fair 將調度實體從紅黑樹中移除，完成出隊操作;隊操作。

調用 __enqueue_entity 函數后，就可以把進程調度實體插入到運行隊列的紅黑樹中。同時會把紅黑樹最左端的節點緩存到運行隊列的 rb_leftmost 字段中，用于快速獲取下一個可運行的進程。

從 cfs_rq 中獲取下一個可運行的任務

每當進程任務切換的時候，也就是schedule函數執行時，調度器都需要選擇下一個將要執行的任務。在CFS調度器中，是通過 pick_next_task_fair 函數完成的，其本質是從就緒隊列中選擇最適合運行的調度實體(虛擬時間最小的調度實體)。