CFS 原理
CFS（Completely Fair Scheduler）, 也即是完全公平排程器。
CFS 的産生就是為了在真實的硬體上模拟“理想的多任務處理器”，使每個程序都能夠公平的獲得 CPU。
CFS 排程器沒有時間片的概念，CFS 的理念就是讓每個程序擁有相同的使用 CPU 的時間。比如有 n 個可運作的程序，那麼每個程序将能擷取的處理時間為 1/n。
在 CFS 排程器中引用權重來代表程序的優先級。各個程序按照權重的比例來配置設定使用 CPU 的時間。比如2個程序 A 和 B， A 的權重為 100， B 的權重為200，那麼 A 獲得的 CPU 的時間為 100/(100+200) = 33%, B 程序獲得的CPU 的時間為 200/(100+200) = 67%。
在引入權重之後，在一個排程周期中配置設定給程序的運作時間計算公式如下：
實際運作時間 = 排程周期 * 程序權重 / 所有程序權重之和
可以看到，權重越大，分到的運作時間越多。
排程周期：在某個時間長度可以保證運作隊列中的每個程序至少運作一次，我們把這個時間長度稱為排程周期。也稱為排程延遲，因為一個程序等待被排程的延遲時間是一個排程周期。
排程最小粒度：為了防止程序切換太頻繁，程序被排程後應該至少運作一小段時間，我們把這個時間長度稱為排程最小粒度。
排程周期的預設值是20毫秒，排程最小粒度的預設值是4毫秒，如下所示，兩者的機關都是納秒。
//預設排程周期 20ms
unsigned int sysctl_sched_latency = 20000000ULL;
//預設排程最小粒度 4ms
unsigned int sysctl_sched_min_granularity = 4000000ULL;
// 預設一個排程周期内的程序數：sysctl_sched_latency / sysctl_sched_min_granularity
static unsigned int sched_nr_latency = 5;
如果運作隊列中的程序數量太多，導緻把排程周期 sysctl_sched_latency 平分給程序時的時間片小于排程最小粒度，那麼排程周期取 “排程最小粒度 × 程序數量”。
CFS 排程器中使用 nice 值（取值範圍為[-20 ~ 19]）作為程序擷取處理器運作比的權重：nice 值越高（優先級越低）的程序獲得的 CPU使用的權重越低。
在使用者态程序的優先級 nice 值與 CFS 排程器中的權重又有什麼關系？
在核心中通過 prio_to_weight 數組進行 nice 值和權重的轉換。
static const int 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,
};
從 nice 和權重的對應值可知，nice 值為 0 的權重為 1024（預設權重）， nice 值為1的權重為 820，nice 值為 15 的權重值為 36，nice 值為19的權重值為 15。
例如：假設排程周期為12ms，2個相同nice的程序其權重也相同，那麼2個程序各自的運作時間為 6ms。
假設程序 A 和 B 的 nice 值分别為0、1，那麼權重也就分别為 1024、820。是以，
A 實際運作時間為 12 * 1024/(1024+820)= 6.66ms ，
B 實際運作時間為 12 * 820/(1024+820)= 5.34ms。
從結果來看，2個程序運作時間時不一樣的。由于A的權重高，優先級大，會出現 A 一直被排程，而 B 最後被排程，這就失去了公平性，是以 CFS 的存在就是為了解決 這種不公平性。
是以為了讓每個程序完全公平排程，是以就引入了一個 vruntime （虛拟運作時間，virtual runtime）的概念, 每個排程實體都有一個 vruntime，該vruntime 根據排程實體的排程而不停的累加，CFS 根據 vruntime 的大小來選擇排程實體。
排程實體的結構如下：
struct sched_entity {
struct load_weight load; // 排程實體的負載權重值
struct rb_node run_node; //用于添加到CFS運作隊列的紅黑樹中的節點
unsigned int on_rq;//用于表示是否在運作隊列中
u64 exec_start;//目前排程實體的開始運作時間
u64 sum_exec_runtime;//排程實體執行的總時間
/*
虛拟運作時間，在時間中斷或者任務狀态發生改變時會更新
其會不停的增長，增長速度與load權重成反比，load越高，增長速度越慢，就越可能處于紅黑樹最左邊被排程
每次時鐘中斷都會修改其值。注意其值為單調遞增，在每個排程器的時鐘中斷時目前程序的虛拟運作時間都會累加。
單純的說就是程序們都在比誰的vruntime最小，最小的将被排程
*/
u64 vruntime;//虛拟運作時間，這個時間用于在CFS運作隊列中排隊
u64 prev_sum_exec_runtime;//上一個排程實體運作的總時間
...
#ifdef CONFIG_FAIR_GROUP_SCHED
struct sched_entity *parent; //指向排程實體的父對象
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq; //指向排程實體歸屬的CFS隊列，也就是需要入列的CFS隊列
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;//指向歸屬于目前排程實體的CFS隊列
#endif
};
虛拟時間和實際時間的關系如下：
虛拟運作時間 = 實際運作時間 *（NICE_0_LOAD / 程序權重）
其中，NICE_0_LOAD 是 nice為0時的權重（預設），也即是 1024。也就是說，nice 值為0的程序實際運作時間和虛拟運作時間相同。
虛拟運作時間一方面跟程序運作時間有關，另一方面跟程序優先級有關。
程序權重越大, 運作同樣的實際時間, vruntime 增長的越慢。
一個程序在一個排程周期内的虛拟運作時間大小為:
vruntime = 程序在一個排程周期内的實際運作時間 * 1024 / 程序權重
= (排程周期 * 程序權重 / 所有程序總權重) * 1024 / 程序權重
= 排程周期 * 1024 / 所有程序總權重
可以看到, 一個程序在一個排程周期内的 vruntime 值大小是不和該程序自己的權重相關的, 是以所有程序的 vruntime 值大小都是一樣的。
接着上述的例子，通過虛拟運作時間公式可得：
A 虛拟運作時間為 6.66 * (1024/1024) = 6.66ms,
B 虛拟運作時間為 5.34* (1024/820) = 6.66ms,
在一個排程周期過程中，各個排程實體的 vruntime 都是累加的過程，保證了在一個排程周期結束後，每個排程實體的 vruntime 值大小都是一樣的。
由于權重越高，應該優先的得到運作，是以 CFS 采用虛拟運作時間越小，越先排程。
當權重越高的程序随着排程的次數多，其 vruntime 的累加也就越多。當其 vruntime 的累加大于其他低優先級程序的 vruntime 時，低優先級的程序得以排程。這就保證了每個程序都可以排程而不會出現高優先級的一直得到排程，而優先級低的程序得不到排程而産生饑餓。
一言以蔽之：在CFS中，不管權重高低，根據 vruntime 大小比較，大家都輪着使用 CPU。
當然，根據一個排程周期中配置設定給程序的實際運作時間計算公式可知，在一個排程周期内，雖然大家都輪着使用 CPU，但是實際運作時間的多少和權重也是有關的，權重越高，總的實際運作的時間也就越多。在一個排程周期結束後，各個排程實體的 vruntime 最終還是相等的。
那麼在 CFS 中 vruntime 是怎麼使用的呢？
CFS 中的就緒隊列是一棵以 vruntime 為鍵值的紅黑樹，虛拟時間越小的程序越靠近整個紅黑樹的最左端。是以，排程器每次選擇位于紅黑樹最左端的那個程序，該程序的 vruntime 最小，也就最應該優先排程。
實際擷取最左葉子節點時并不會周遊樹，而是 vruntime 最小的節點已經緩存在了 rb_leftmost 字段中了，是以 CFS 很快可以擷取 vruntime 最小的節點。
其中紅黑樹的結構如下:
CFS 排程時機
與 CFS 相關的有如下幾個過程：
- 建立新程序: 建立新程序時, 需要設定新程序的 vruntime 值以及将新程序加入紅黑樹中. 并判斷是否需要搶占目前程序。
- 程序的排程: 程序排程時, 需要把目前程序加入紅黑樹中, 還要從紅黑樹中挑選出下一個要運作的程序。
- 程序喚醒: 喚醒程序時, 需要調整睡眠程序的 vruntime 值, 并且将睡眠程序加入紅黑樹中. 并判斷是否需要搶占目前程序。
- 時鐘周期中斷: 在時鐘中斷周期函數中, 需要更新目前運作程序的 vruntime 值, 并判斷是否需要搶占目前程序。
建立新程序
建立新程序的系統調用 fork, vfork, clone. 這三個系統調用最終都是調用do_fork() 函數.在 do_fork() 函數中, 主要就是設定新程序的 vruntime 值, 将新程序加入到紅黑樹中, 判斷新程序是否可以搶占目前程序.
do_fork
--> wake_up_new_task
--> task_new_fair //設定新程序的vruntime值,并将其加入就緒隊列中
--> check_preempt_curr //檢查新程序是否可以搶占目前程序
task_new_fair 實作如下：
static void task_new_fair(struct rq *rq, struct task_struct *p)
{
struct cfs_rq *cfs_rq = task_cfs_rq(p);
struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
int this_cpu = smp_processor_id();
sched_info_queued(p);
update_curr(cfs_rq); //更新目前程序的vruntime值
place_entity(cfs_rq, se, 1); //設定新程序的vruntime值, 1表示是新程序
/* 'curr' will be NULL if the child belongs to a different group */
//sysctl_sched_child_runs_first值表示是否設定了讓子程序先運作
if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
curr && curr->vruntime < se->vruntime) {
/*
* Upon rescheduling, sched_class::put_prev_task() will place
* 'current' within the tree based on its new key value.
*/
swap(curr->vruntime, se->vruntime); //當子程序的vruntime值大于父程序的vruntime時, 交換兩個程序的vruntime值
}
enqueue_task_fair(rq, p, 0);//将新任務加入到就緒隊列中
//設定TIF_NEED_RESCHED标志值，該标記标志程序是否需要重新排程，如果設定了，就會發生排程
resched_task(rq->curr);
}
該函數給新程序設定一個新的 vruntime，然後加入到就緒隊列中，等待排程。
check_preempt_curr 在 CFS 中 對應的為 check_preempt_wakeup 函數，其實作如下：
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
{
struct task_struct *curr = rq->curr;
struct cfs_rq *cfs_rq = task_cfs_rq(curr);
struct sched_entity *se = &curr->se, *pse = &p->se;
unsigned long gran;
...
// gran 為程序排程粒度
gran = sysctl_sched_wakeup_granularity; // 10 ms
if (unlikely(se->load.weight != NICE_0_LOAD))
gran = calc_delta_fair(gran, &se->load); //計算排程粒度
/*
排程粒度的設定, 是為了防止這麼一個情況: 新程序的vruntime值隻比目前程序的vruntime小一點點, 如果此時發生重新排程,
則新程序隻運作一點點時間後, 其vruntime值就會大于前面被搶占的程序的vruntime值, 這樣又會發生搶占,
是以這樣的情況下, 系統會發生頻繁的切換.故, 隻有當新程序的vruntime值比目前程序的vruntime值小于排程粒度之外,
才發生搶占.
是以，目前程序的虛拟運作時間se->vruntime 比 下一個程序 pse->vruntime 大于一個排程粒度，說明目前程序應該被搶占，
應該切換出去讓别vruntime小的程序進行運作，是以給目前程序設定是一個重新排程标記TIF_NEED_RESCHED，
當某個時機根據該标記進行調用schedule(),這時會重新選擇一個程序進行切換
*/
if (pse->vruntime + gran < se->vruntime)
resched_task(curr);
}
該功能就是根據排程粒度，判斷是否需要設定被搶占标記，若需要，這調用
resched_task 把目前程序設定成被搶占标記TIF_NEED_RESCHED，該标記說明目前程序運作的時間夠多的了，應該切換出去，讓出 CPU 讓讓别的程序運作。
static void resched_task(struct task_struct *p)
{
int cpu;
assert_spin_locked(&task_rq(p)->lock);
if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
return;
//設定被被搶占标記
set_tsk_thread_flag(p, TIF_NEED_RESCHED);
cpu = task_cpu(p);
if (cpu == smp_processor_id())
return;
/* NEED_RESCHED must be visible before we test polling */
smp_mb();
if (!tsk_is_polling(p))
smp_send_reschedule(cpu);
}
設定完TIF_NEED_RESCHED 不代表目前程序立馬就切換出去了，而是等待一定時機，然後會根據TIF_NEED_RESCHED 标記調用schedule()進行排程切換。
程序的排程
程序排程的主要入口點是 schedule 函數，它正是核心其他部分用于調用程序排程器的入口：選擇哪個程序可以運作，何時投入運作。
schedule 通常要和一個具體的排程類相關聯，也即是，它會找到最高優先級的排程類，然後從就緒隊列中選擇下一個該運作的程序。
當調用 schedule() 進行任務切換的時候，排程器調用 pick_next_task 函數選擇下一個将要執行的任務，這是相對預設 nice 值程序的程序而言的。
asmlinkage void __sched schedule(void)
{
/*prev 表示排程之前的程序, next 表示排程之後的程序 */
struct task_struct *prev, *next;
long *switch_count;
struct rq *rq;
int cpu;
need_resched:
preempt_disable(); //關閉核心搶占
cpu = smp_processor_id(); //擷取所在的cpu
rq = cpu_rq(cpu); //擷取cpu對應的運作隊列
rcu_qsctr_inc(cpu);
prev = rq->curr; /*讓prev 成為目前程序 */
switch_count = &prev->nivcsw;
/*釋放全局核心鎖，并開this_cpu 的中斷*/
release_kernel_lock(prev);
need_resched_nonpreemptible:
__update_rq_clock(rq); //更新運作隊列的時鐘值
...
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
// 對應到CFS,則為 put_prev_task_fair
prev->sched_class->put_prev_task(rq, prev); //通知排程器類目前運作程序要被另一個程序取代
/*pick_next_task以優先級從高到底依次檢查每個排程類，從最高優先級的排程類中選擇最高優先級的程序作為
下一個應執行程序（若其餘都睡眠，則隻有目前程序可運作，就跳過下面了）*/
next = pick_next_task(rq, prev); //選擇需要進行切換的task
...
}
在選擇下一個程序前，先調用 put_prev_task （對應到 CFS 為put_prev_task_fair），計算下目前程序的運作時間，根據目前運作時間計算出虛拟運作時間，并累加到 vruntime，然後把目前程序根據 vruntime 重新加入到就緒隊列紅黑樹中，等待下一次被排程。
put_prev_task_fair
--> put_prev_entity
--> update_curr
--> __update_curr //更新目前排程實體的實際運作時間和虛拟運作時間
--> __enqueue_entity //把目前排程實體重新加入到就緒隊列紅黑樹中等待下一次排程
/*
cfs_rq：可運作隊列對象。
curr：目前程序排程實體。
delta_exec：實際運作的時間。
__update_curr() 函數主要完成以下幾個工作：
更新程序排程實體的總實際運作時間。
根據程序排程實體的權重值，計算其使用的虛拟運作時間。
把計算虛拟運作時間的結果添加到程序排程實體的 vruntime 字段。
*/
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
unsigned long delta_exec)
{
unsigned long delta_exec_weighted;
u64 vruntime;
schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
//// 增加目前程序總實際運作的時間
curr->sum_exec_runtime += delta_exec;
// 更新cfs_rq的實際執行時間cfs_rq->exec_clock
schedstat_add(cfs_rq, exec_clock, delta_exec);
//根據實際運作時間計算虛拟運作時間并累加到目前程序的虛拟運作時間
delta_exec_weighted = delta_exec;
//// 根據實際運作時間計算其使用的虛拟運作時間
if (unlikely(curr->load.weight != NICE_0_LOAD)) {
delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
&curr->load);
}
curr->vruntime += delta_exec_weighted; // 更新程序的虛拟運作時間
/*
* maintain cfs_rq->min_vruntime to be a monotonic increasing
* value tracking the leftmost vruntime in the tree.
*/
if (first_fair(cfs_rq)) {
vruntime = min_vruntime(curr->vruntime,
__pick_next_entity(cfs_rq)->vruntime);
} else
vruntime = curr->vruntime;
/*min_vruntime記錄CFS運作隊列上vruntime最小值，但是實際上min_vruntime隻能單調遞增，
是以，如果目前程序vruntime比min_vruntime小，是不會更新min_vruntime的。
那麼min_vruntime的作用的是什麼呢？試想一下如果一個程序睡眠了很長時間，則它的vruntime非常小，
一旦它被喚醒，将持續占用CPU，很容易引發程序饑餓。
CFS排程器會根據min_vruntime設定一個合适的vruntime值給被喚醒的程序，
既要保證它能優先被排程，又要保證其他程序也能得到合理排程。
*/
cfs_rq->min_vruntime =
max_vruntime(cfs_rq->min_vruntime, vruntime);
}
該函數的功能如下:
- 更新程序排程實體的總實際運作時間。
- 根據程序排程實體的權重值，計算其虛拟運作時間。
- 把計算虛拟運作時間的結果添加到程序排程實體的 vruntime 字段。
将排程實體加入紅黑樹中
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; // 紅黑樹根節點
struct rb_node *parent = NULL;
struct sched_entity *entry;
s64 key = entity_key(cfs_rq, se);// 目前程序排程實體的虛拟運作時間
int leftmost = 1;
/*
* Find the right place in the rbtree:
*/
while (*link) { // 把目前排程實體插入到運作隊列的紅黑樹中
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
/*
* We dont care about collisions. Nodes with
* the same key stay together.
*/
if (key < entity_key(cfs_rq, entry)) { // 比較虛拟運作時間
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = 0;
}
}
/*
* Maintain a cache of leftmost tree entries (it is frequently
* used):
*/
if (leftmost) //緩存最左葉子節點
cfs_rq->rb_leftmost = &se->run_node;
rb_link_node(&se->run_node, parent, link);
//把節點插入到紅黑樹中
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}
__enqueue_entity() 函數的主要工作如下：
- 擷取運作隊列紅黑樹的根節點。
- 擷取目前程序排程實體的虛拟運作時間。
- 把目前程序排程實體添加到紅黑樹中。
- 緩存紅黑樹最左端節點。
- 對紅黑樹進行平衡操作。
擷取下一個合适的排程實體
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
const struct sched_class *class;
struct task_struct *p;
/*
* Optimization: we know that if all tasks are in
* the fair class we can call that function directly:
*/
/*選擇時并不是想象中的直接按照排程器的優先級對所有排程器類進行周遊，而是假設下一個運作的程序屬于 cfs 排程器類，畢竟，系統中絕大多數的程序都是由 cfs 排程器進行管理，這樣做可以從整體上提高執行效率.*/
if (likely(rq->nr_running == rq->cfs.nr_running)) {
p = fair_sched_class.pick_next_task(rq);
if (likely(p))
return p;
}
class = sched_class_highest; // #define sched_class_highest (&rt_sched_class)
for ( ; ; ) {
p = class->pick_next_task(rq);
if (p)
return p;
/*
* Will never be NULL as the idle class always
* returns a non-NULL p:
*/
class = class->next;
}
}
在 pick_next_task 中會周遊所有的排程類，然後從就緒隊列中選取一個最合适的排程實體進行排程。
對于完全公平排程算法（CFS），會調用 fair_sched_class.pick_next_task() 函數，從 fair_sched_class 中可知，也即是調用 pick_next_task_fair。
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.load_balance = load_balance_fair,
.move_one_task = move_one_task_fair,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_new = task_new_fair,
};
pick_next_task_fair 調用過程如下：
pick_next_task_fair
---> pick_next_entity
---> __pick_next_entity 從就緒隊列中選取一個最合适的排程實體(虛拟時間最小的排程實體)
---> set_next_entity 把選中的程序從紅黑樹中移除，并更新紅黑樹
從 schedule 調用可知，其在選擇下一個運作任務前，先計算目前程序（待切換出去的程序）的時間運作時間，然後根據實際運作時間計算虛拟運作時間，在根據虛拟運作時間把目前程序加入到就緒隊列中的紅黑樹中等待下一次排程。
其次，從就緒隊列的紅黑樹中選擇虛拟運作時間最小的任務作為即将運作的任務。
程序喚醒
程序的預設喚醒函數是 try_to_wake_up(), 該函數主要是調整睡眠程序的 vruntime值, 以及把睡眠程序加入紅黑樹中, 并判斷是否可以發生搶占。
調用關系如下：
try_to_wake_up
--> activate_task
--> enqueue_task
--> check_preempt_curr
時鐘周期中斷
周期性排程器是基于 scheduler_tick 函數實作。系統都是以tick（節拍）來執行各種排程與統計，節拍可以通過 CONFIG_HZ 宏來控制。核心會以 1/HZ ms 為周期來執行周期性排程，這也是 CFS 實作的關鍵。CFS排程類會根據這個節拍來對所有程序進行記賬。每個 CPU 都會擁有自己的周期性排程器。周期性排程器可以把目前程序設定為 need resched 狀态，等待合适的時機目前的程序就會被重新排程。
時鐘周期中斷函數的調用過程:
tick_periodic
--> update_process_times
--> scheduler_tick
--> task_tick_fair
-->entity_tick
--> update_curr
--> check_preempt_tick
在 CFS 中，scheduler_tick 會調用 具體實作 task_tick_fair，在task_tick_fair 中會從目前程序開始擷取每個排程實體，對每個排程實體進行調用 entity_tick，在 entity_tick 中更新排程實體的實際運作時間和虛拟運作時間，同時檢查是否需要重新排程。
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
unsigned long ideal_runtime, delta_exec;
// ideal_runtime 為一個排程周期内理想的運作時間，也即是為 排程周期 * 程序權重 / 所有程序權重之和
ideal_runtime = sched_slice(cfs_rq, curr);
// sum_exec_runtime 指程序總共執行的實際時間;
// prev_sum_exec_runtime 指上次該程序被排程時已經占用的實際時間。
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
// delta_exec 這次排程占用實際時間，如果大于 ideal_runtime，則應該被搶占了
if (delta_exec > ideal_runtime)
resched_task(rq_of(cfs_rq)->curr);
}
若目前程序運作的時間超過時間限制，則把目前程序設定為 被搶占重新排程标記 TIF_NEED_RESCHED，待一定時機後會根據 TIF_NEED_RESCHED 标記調用 schedule() 進行排程切換。關于“一定的時機”，後續文章進行分析。
![Linux程序管理之終止[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)