在讨論了采用CFS排程算法的動機和内部邏輯以後，可以适當探索CFS的部分具體實作。相關代碼位于檔案kernel/sched_fair.c當中。可以檢視其中四個組成部分。
·時間記賬
·程序選擇
·排程器入口
·睡眠和喚醒
1.5.1 時間記賬：
排程器要為每個程序做時間記賬，在多數的Unix系統當中，配置設定一個時間片給每一個程序。程序的節拍周期随着系統的節拍不斷減少。一個程序的時間片被減少到0時，他就會被另一個尚未被減到零的時間片程序搶占。
1.排程器的實體結構
CFS維護程序運作的時間記賬，確定程序在給予他的處理器時間内運作。排程器的實體結構（定義在
struct sched_eneity
{
struct load_weigt load;
struct eb_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_operlap;
u64 nr_migrations;
u64 start_runtime;
u64 avg_wakeup;
//這裡省略了很多統計變量，隻有在設定了CONFIG_SCHEDSTATS時才啟用這些變量
}
排程器的實體結構作為一個名為se的成員變量，潛入在程序描述符 struct task_struct 内。
2.虛拟實時
vruntime變量存放程序的虛拟運作時間，CFS使用vruntime變量來記錄一個程式到底運作了多長時間以及他還應該運作多久。
定義在kernel/sched_fair.c檔案中的update_cuurr()函數實作了記賬的功能。
static void update_surr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr =cfs_rq->curr;
u64 now = rq_of(cfs_rq)->clock;
unsigned long delta_exec;
if(unlikely(!curr))
/*獲得從最後一次修改後目前任務所占用的運作總時間*/
delta_exec =(unsignd long)(now -cur->exec_start);
if(!delta_exec)
return ;
_update_curr(cfs_rq,curr,delta_exec);
curr->exec_start = now;
if(entity_is_task(curr))
{
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask,delta_exec,curr->vruntime);
cpuacct_charge(curtask,delta_exec);
account_group_exec_runtime(curtask,delta_exec);
}
}
update_curr()計算了目前程序的執行時間，并且将其存放在變量delta_exec中，然後它又将運作時間傳遞給了__update_curr(),由後者根據目前可運作程序總數對運作時間進行權重計算。最終将上述的權重值與目前運作程序的vruntime相加。
static inline void
__update_cur(struct cfs_rq *cfs_rq,struct sched_entity *curr,unsigned long delta_exec)
{
unsigned long delta_exec_weighted;
sched_set(curr->exec_max,max((u64)delta_exec,curr->exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq,exec_clock,delta_exec);
delta_exec_weight = calc_delta_fair(delta_exec,curr);
curr->vruntime += delta_exec_weighted;
update_min_vruntime(cfs_rq);
}
update_curr()是有系統定時器調用的，無論是在程序處于可執行狀态，還是被堵塞處于不可執行的狀态。都可以準确的測量。
1.5.2程序選擇
加入存在一個完美的多任務處理器，那麼所有可執行程序的vruntime的值将是一樣的。但是事實是不存在理想的情況。在需要選擇下一個程序的時候，CFS會選擇一個vruntime最小的程序。這個就是CFS排程算法的核心。那麼具體如何實作選擇最小的程序呢？
CFS使用紅黑樹來組織可運作程序的隊列，紅黑樹被稱為rbtree.rbtree是一種以樹節點形式存在的資料，每個資料會對應一個鍵值。通過鍵值可以快速搜尋節點上的資料。但是，通過鍵值搜尋到對應節點的速度與整個數的節點規模呈現指數比的關系。
在沒有你的世界裡，愛你，葉铮