CFS 原理

CFS(Completely Fair Scheduler), 也即是完全公平調(diào)度器。

CFS 的產(chǎn)生就是為了在真實(shí)的硬件上模擬“理想的多任務(wù)處理器”，使每個(gè)進(jìn)程都能夠公平的獲得 CPU。

CFS 調(diào)度器沒(méi)有時(shí)間片的概念，CFS 的理念就是讓每個(gè)進(jìn)程擁有相同的使用 CPU 的時(shí)間。比如有 n 個(gè)可運(yùn)行的進(jìn)程，那么每個(gè)進(jìn)程將能獲取的處理時(shí)間為 1/n。

在 CFS 調(diào)度器中引用權(quán)重來(lái)代表進(jìn)程的優(yōu)先級(jí)。各個(gè)進(jìn)程按照權(quán)重的比例來(lái)分配使用 CPU 的時(shí)間。比如2個(gè)進(jìn)程 A 和 B， A 的權(quán)重為 100， B 的權(quán)重為200，那么 A 獲得的 CPU 的時(shí)間為 100/(100+200) = 33%, B 進(jìn)程獲得的CPU 的時(shí)間為 200/(100+200) = 67%。

在引入權(quán)重之后，在一個(gè)調(diào)度周期中分配給進(jìn)程的運(yùn)行時(shí)間計(jì)算公式如下：

實(shí)際運(yùn)行時(shí)間 = 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和

可以看到，權(quán)重越大，分到的運(yùn)行時(shí)間越多。

• 調(diào)度周期：在某個(gè)時(shí)間長(zhǎng)度可以保證運(yùn)行隊(duì)列中的每個(gè)進(jìn)程至少運(yùn)行一次，我們把這個(gè)時(shí)間長(zhǎng)度稱為調(diào)度周期。也稱為調(diào)度延遲，因?yàn)橐粋€(gè)進(jìn)程等待被調(diào)度的延遲時(shí)間是一個(gè)調(diào)度周期。
• 調(diào)度最小粒度：為了防止進(jìn)程切換太頻繁，進(jìn)程被調(diào)度后應(yīng)該至少運(yùn)行一小段時(shí)間，我們把這個(gè)時(shí)間長(zhǎng)度稱為調(diào)度最小粒度。

調(diào)度周期的默認(rèn)值是20毫秒，調(diào)度最小粒度的默認(rèn)值是4毫秒，如下所示，兩者的單位都是納秒。

//默認(rèn)調(diào)度周期 20ms
unsigned int sysctl_sched_latency = 20000000ULL;
//默認(rèn)調(diào)度最小粒度 4ms
unsigned int sysctl_sched_min_granularity = 4000000ULL;
// 默認(rèn)一個(gè)調(diào)度周期內(nèi)的進(jìn)程數(shù)：sysctl_sched_latency / sysctl_sched_min_granularity
static unsigned int sched_nr_latency = 5;

如果運(yùn)行隊(duì)列中的進(jìn)程數(shù)量太多，導(dǎo)致把調(diào)度周期 sysctl_sched_latency 平分給進(jìn)程時(shí)的時(shí)間片小于調(diào)度最小粒度，那么調(diào)度周期取 “調(diào)度最小粒度 × 進(jìn)程數(shù)量”。

CFS 調(diào)度器中使用 nice 值(取值范圍為[-20 ~ 19])作為進(jìn)程獲取處理器運(yùn)行比的權(quán)重：nice 值越高(優(yōu)先級(jí)越低)的進(jìn)程獲得的 CPU使用的權(quán)重越低。

在用戶態(tài)進(jìn)程的優(yōu)先級(jí) nice 值與 CFS 調(diào)度器中的權(quán)重又有什么關(guān)系?

在內(nèi)核中通過(guò) prio_to_weight 數(shù)組進(jìn)行 nice 值和權(quán)重的轉(zhuǎn)換。

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 和權(quán)重的對(duì)應(yīng)值可知，nice 值為 0 的權(quán)重為 1024(默認(rèn)權(quán)重)， nice 值為1的權(quán)重為 820，nice 值為 15 的權(quán)重值為 36，nice 值為19的權(quán)重值為 15。

例如：假設(shè)調(diào)度周期為12ms，2個(gè)相同nice的進(jìn)程其權(quán)重也相同，那么2個(gè)進(jìn)程各自的運(yùn)行時(shí)間為 6ms。

假設(shè)進(jìn)程 A 和 B 的 nice 值分別為0、1，那么權(quán)重也就分別為 1024、820。因此，A 實(shí)際運(yùn)行時(shí)間為 12 * 1024/(1024+820)= 6.66ms ，B 實(shí)際運(yùn)行時(shí)間為 12 * 820/(1024+820)= 5.34ms。

從結(jié)果來(lái)看，2個(gè)進(jìn)程運(yùn)行時(shí)間時(shí)不一樣的。由于A的權(quán)重高，優(yōu)先級(jí)大，會(huì)出現(xiàn) A 一直被調(diào)度，而 B 最后被調(diào)度，這就失去了公平性，所以 CFS 的存在就是為了解決 這種不公平性。

因此為了讓每個(gè)進(jìn)程完全公平調(diào)度，因此就引入了一個(gè) vruntime (虛擬運(yùn)行時(shí)間，virtual runtime)的概念, 每個(gè)調(diào)度實(shí)體都有一個(gè) vruntime，該vruntime 根據(jù)調(diào)度實(shí)體的調(diào)度而不停的累加，CFS 根據(jù) vruntime 的大小來(lái)選擇調(diào)度實(shí)體。

調(diào)度實(shí)體的結(jié)構(gòu)如下：

struct sched_entity {
struct load_weight load; // 調(diào)度實(shí)體的負(fù)載權(quán)重值
struct rb_node run_node; //用于添加到CFS運(yùn)行隊(duì)列的紅黑樹(shù)中的節(jié)點(diǎn)
unsigned int on_rq;//用于表示是否在運(yùn)行隊(duì)列中
u64 exec_start;//當(dāng)前調(diào)度實(shí)體的開(kāi)始運(yùn)行時(shí)間
u64 sum_exec_runtime;//調(diào)度實(shí)體執(zhí)行的總時(shí)間
/*

虛擬運(yùn)行時(shí)間，在時(shí)間中斷或者任務(wù)狀態(tài)發(fā)生改變時(shí)會(huì)更新

其會(huì)不停的增長(zhǎng)，增長(zhǎng)速度與load權(quán)重成反比，load越高，增長(zhǎng)速度越慢，就越可能處于紅黑樹(shù)最左邊被調(diào)度

每次時(shí)鐘中斷都會(huì)修改其值。注意其值為單調(diào)遞增，在每個(gè)調(diào)度器的時(shí)鐘中斷時(shí)當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間都會(huì)累加。

單純的說(shuō)就是進(jìn)程們都在比誰(shuí)的vruntime最小，最小的將被調(diào)度

*/
u64 vruntime;//虛擬運(yùn)行時(shí)間，這個(gè)時(shí)間用于在CFS運(yùn)行隊(duì)列中排隊(duì)
u64 prev_sum_exec_runtime;//上一個(gè)調(diào)度實(shí)體運(yùn)行的總時(shí)間
...
#ifdef CONFIG_FAIR_GROUP_SCHED
struct sched_entity *parent; //指向調(diào)度實(shí)體的父對(duì)象
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq; //指向調(diào)度實(shí)體歸屬的CFS隊(duì)列，也就是需要入列的CFS隊(duì)列
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;//指向歸屬于當(dāng)前調(diào)度實(shí)體的CFS隊(duì)列
#endif
};

虛擬時(shí)間和實(shí)際時(shí)間的關(guān)系如下：

虛擬運(yùn)行時(shí)間 = 實(shí)際運(yùn)行時(shí)間 *(NICE_0_LOAD / 進(jìn)程權(quán)重)

其中，NICE_0_LOAD 是 nice為0時(shí)的權(quán)重(默認(rèn))，也即是 1024。也就是說(shuō)，nice 值為0的進(jìn)程實(shí)際運(yùn)行時(shí)間和虛擬運(yùn)行時(shí)間相同。

虛擬運(yùn)行時(shí)間一方面跟進(jìn)程運(yùn)行時(shí)間有關(guān)，另一方面跟進(jìn)程優(yōu)先級(jí)有關(guān)。

進(jìn)程權(quán)重越大, 運(yùn)行同樣的實(shí)際時(shí)間, vruntime 增長(zhǎng)的越慢。

一個(gè)進(jìn)程在一個(gè)調(diào)度周期內(nèi)的虛擬運(yùn)行時(shí)間大小為:

vruntime = 進(jìn)程在一個(gè)調(diào)度周期內(nèi)的實(shí)際運(yùn)行時(shí)間 * 1024 / 進(jìn)程權(quán)重= (調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程總權(quán)重) * 1024 / 進(jìn)程權(quán)重= 調(diào)度周期 * 1024 / 所有進(jìn)程總權(quán)重。

可以看到, 一個(gè)進(jìn)程在一個(gè)調(diào)度周期內(nèi)的 vruntime 值大小是不和該進(jìn)程自己的權(quán)重相關(guān)的, 所以所有進(jìn)程的 vruntime 值大小都是一樣的。

接著上述的例子，通過(guò)虛擬運(yùn)行時(shí)間公式可得：

A 虛擬運(yùn)行時(shí)間為 6.66 * (1024/1024) = 6.66ms,

B 虛擬運(yùn)行時(shí)間為 5.34* (1024/820) = 6.66ms,

在一個(gè)調(diào)度周期過(guò)程中，各個(gè)調(diào)度實(shí)體的 vruntime 都是累加的過(guò)程，保證了在一個(gè)調(diào)度周期結(jié)束后，每個(gè)調(diào)度實(shí)體的 vruntime 值大小都是一樣的。

由于權(quán)重越高，應(yīng)該優(yōu)先的得到運(yùn)行，因此 CFS 采用虛擬運(yùn)行時(shí)間越小，越先調(diào)度。

當(dāng)權(quán)重越高的進(jìn)程隨著調(diào)度的次數(shù)多，其 vruntime 的累加也就越多。當(dāng)其 vruntime 的累加大于其他低優(yōu)先級(jí)進(jìn)程的 vruntime 時(shí)，低優(yōu)先級(jí)的進(jìn)程得以調(diào)度。這就保證了每個(gè)進(jìn)程都可以調(diào)度而不會(huì)出現(xiàn)高優(yōu)先級(jí)的一直得到調(diào)度，而優(yōu)先級(jí)低的進(jìn)程得不到調(diào)度而產(chǎn)生饑餓。

一言以蔽之：在CFS中，不管權(quán)重高低，根據(jù) vruntime 大小比較，大家都輪著使用 CPU。

當(dāng)然，根據(jù)一個(gè)調(diào)度周期中分配給進(jìn)程的實(shí)際運(yùn)行時(shí)間計(jì)算公式可知，在一個(gè)調(diào)度周期內(nèi)，雖然大家都輪著使用 CPU，但是實(shí)際運(yùn)行時(shí)間的多少和權(quán)重也是有關(guān)的，權(quán)重越高，總的實(shí)際運(yùn)行的時(shí)間也就越多。在一個(gè)調(diào)度周期結(jié)束后，各個(gè)調(diào)度實(shí)體的 vruntime 最終還是相等的。

那么在 CFS 中 vruntime 是怎么使用的呢?

CFS 中的就緒隊(duì)列是一棵以 vruntime 為鍵值的紅黑樹(shù)，虛擬時(shí)間越小的進(jìn)程越靠近整個(gè)紅黑樹(shù)的最左端。因此，調(diào)度器每次選擇位于紅黑樹(shù)最左端的那個(gè)進(jìn)程，該進(jìn)程的 vruntime 最小，也就最應(yīng)該優(yōu)先調(diào)度。

實(shí)際獲取最左葉子節(jié)點(diǎn)時(shí)并不會(huì)遍歷樹(shù)，而是 vruntime 最小的節(jié)點(diǎn)已經(jīng)緩存在了 rb_leftmost 字段中了，因此 CFS 很快可以獲取 vruntime 最小的節(jié)點(diǎn)。

其中紅黑樹(shù)的結(jié)構(gòu)如下:

CFS 調(diào)度時(shí)機(jī)

與 CFS 相關(guān)的有如下幾個(gè)過(guò)程：

• 創(chuàng)建新進(jìn)程: 創(chuàng)建新進(jìn)程時(shí), 需要設(shè)置新進(jìn)程的 vruntime 值以及將新進(jìn)程加入紅黑樹(shù)中. 并判斷是否需要搶占當(dāng)前進(jìn)程。
• 進(jìn)程的調(diào)度: 進(jìn)程調(diào)度時(shí), 需要把當(dāng)前進(jìn)程加入紅黑樹(shù)中, 還要從紅黑樹(shù)中挑選出下一個(gè)要運(yùn)行的進(jìn)程。
• 進(jìn)程喚醒: 喚醒進(jìn)程時(shí), 需要調(diào)整睡眠進(jìn)程的 vruntime 值, 并且將睡眠進(jìn)程加入紅黑樹(shù)中. 并判斷是否需要搶占當(dāng)前進(jìn)程。
• 時(shí)鐘周期中斷: 在時(shí)鐘中斷周期函數(shù)中, 需要更新當(dāng)前運(yùn)行進(jìn)程的 vruntime 值, 并判斷是否需要搶占當(dāng)前進(jìn)程。

創(chuàng)建新進(jìn)程

創(chuàng)建新進(jìn)程的系統(tǒng)調(diào)用 fork, vfork, clone. 這三個(gè)系統(tǒng)調(diào)用最終都是調(diào)用do_fork() 函數(shù).在 do_fork() 函數(shù)中, 主要就是設(shè)置新進(jìn)程的 vruntime 值, 將新進(jìn)程加入到紅黑樹(shù)中, 判斷新進(jìn)程是否可以搶占當(dāng)前進(jìn)程.

do_fork
--> wake_up_new_task
--> task_new_fair //設(shè)置新進(jìn)程的vruntime值,并將其加入就緒隊(duì)列中
--> check_preempt_curr //檢查新進(jìn)程是否可以搶占當(dāng)前進(jìn)程

task_new_fair 實(shí)現(xiàn)如下：

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); //更新當(dāng)前進(jìn)程的vruntime值
place_entity(cfs_rq, se, 1); //設(shè)置新進(jìn)程的vruntime值, 1表示是新進(jìn)程
/* 'curr' will be NULL if the child belongs to a different group */
//sysctl_sched_child_runs_first值表示是否設(shè)置了讓子進(jìn)程先運(yùn)行
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); //當(dāng)子進(jìn)程的vruntime值大于父進(jìn)程的vruntime時(shí), 交換兩個(gè)進(jìn)程的vruntime值
}
enqueue_task_fair(rq, p, 0);//將新任務(wù)加入到就緒隊(duì)列中
//設(shè)置TIF_NEED_RESCHED標(biāo)志值，該標(biāo)記標(biāo)志進(jìn)程是否需要重新調(diào)度，如果設(shè)置了，就會(huì)發(fā)生調(diào)度
resched_task(rq->curr);
}

該函數(shù)給新進(jìn)程設(shè)置一個(gè)新的 vruntime，然后加入到就緒隊(duì)列中，等待調(diào)度。

check_preempt_curr 在 CFS 中 對(duì)應(yīng)的為 check_preempt_wakeup 函數(shù)，其實(shí)現(xiàn)如下：

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 為進(jìn)程調(diào)度粒度
gran = sysctl_sched_wakeup_granularity; // 10 ms
if (unlikely(se->load.weight != NICE_0_LOAD))
gran = calc_delta_fair(gran, &se->load); //計(jì)算調(diào)度粒度
/*

調(diào)度粒度的設(shè)置, 是為了防止這么一個(gè)情況: 新進(jìn)程的vruntime值只比當(dāng)前進(jìn)程的vruntime小一點(diǎn)點(diǎn)， 如果此時(shí)發(fā)生重新調(diào)度，則新進(jìn)程只運(yùn)行一點(diǎn)點(diǎn)時(shí)間后，其vruntime值就會(huì)大于前面被搶占的進(jìn)程的vruntime值， 這樣又會(huì)發(fā)生搶占,所以這樣的情況下，系統(tǒng)會(huì)發(fā)生頻繁的切換。故, 只有當(dāng)新進(jìn)程的vruntime值比當(dāng)前進(jìn)程的vruntime值小于調(diào)度粒度之外，才發(fā)生搶占。

所以，當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間se->vruntime 比 下一個(gè)進(jìn)程 pse->vruntime 大于一個(gè)調(diào)度粒度，說(shuō)明當(dāng)前進(jìn)程應(yīng)該被搶占，應(yīng)該切換出去讓別vruntime小的進(jìn)程進(jìn)行運(yùn)行，因此給當(dāng)前進(jìn)程設(shè)置是一個(gè)重新調(diào)度標(biāo)記TIF_NEED_RESCHED，當(dāng)某個(gè)時(shí)機(jī)根據(jù)該標(biāo)記進(jìn)行調(diào)用schedule(),這時(shí)會(huì)重新選擇一個(gè)進(jìn)程進(jìn)行切換。

*/
if (pse->vruntime + gran < se->vruntime)
resched_task(curr);
}

該功能就是根據(jù)調(diào)度粒度，判斷是否需要設(shè)置被搶占標(biāo)記，若需要，這調(diào)用resched_task 把當(dāng)前進(jìn)程設(shè)置成被搶占標(biāo)記TIF_NEED_RESCHED，該標(biāo)記說(shuō)明當(dāng)前進(jìn)程運(yùn)行的時(shí)間夠多的了，應(yīng)該切換出去，讓出 CPU 讓讓別的進(jìn)程運(yùn)行。

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;
//設(shè)置被被搶占標(biāo)記
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);
}

設(shè)置完TIF_NEED_RESCHED 不代表當(dāng)前進(jìn)程立馬就切換出去了，而是等待一定時(shí)機(jī)，然后會(huì)根據(jù)TIF_NEED_RESCHED 標(biāo)記調(diào)用schedule()進(jìn)行調(diào)度切換。

進(jìn)程的調(diào)度

進(jìn)程調(diào)度的主要入口點(diǎn)是 schedule 函數(shù)，它正是內(nèi)核其他部分用于調(diào)用進(jìn)程調(diào)度器的入口：選擇哪個(gè)進(jìn)程可以運(yùn)行，何時(shí)投入運(yùn)行。

schedule 通常要和一個(gè)具體的調(diào)度類相關(guān)聯(lián)，也即是，它會(huì)找到最高優(yōu)先級(jí)的調(diào)度類，然后從就緒隊(duì)列中選擇下一個(gè)該運(yùn)行的進(jìn)程。

當(dāng)調(diào)用 schedule() 進(jìn)行任務(wù)切換的時(shí)候，調(diào)度器調(diào)用 pick_next_task 函數(shù)選擇下一個(gè)將要執(zhí)行的任務(wù)，這是相對(duì)默認(rèn) nice 值進(jìn)程的進(jìn)程而言的。

asmlinkage void __sched schedule(void)
{
/*prev 表示調(diào)度之前的進(jìn)程, next 表示調(diào)度之后的進(jìn)程 */
struct task_struct *prev, *next;
long *switch_count;
struct rq *rq;
int cpu;
need_resched:
preempt_disable(); //關(guān)閉內(nèi)核搶占
cpu = smp_processor_id(); //獲取所在的cpu
rq = cpu_rq(cpu); //獲取cpu對(duì)應(yīng)的運(yùn)行隊(duì)列
rcu_qsctr_inc(cpu);
prev = rq->curr; /*讓prev 成為當(dāng)前進(jìn)程 */
switch_count = &prev->nivcsw;
/釋放全局內(nèi)核鎖，并開(kāi)this_cpu 的中斷/
release_kernel_lock(prev);
need_resched_nonpreemptible:
__update_rq_clock(rq); //更新運(yùn)行隊(duì)列的時(shí)鐘值
...
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
// 對(duì)應(yīng)到CFS,則為 put_prev_task_fair
prev->sched_class->put_prev_task(rq, prev); //通知調(diào)度器類當(dāng)前運(yùn)行進(jìn)程要被另一個(gè)進(jìn)程取代
/*pick_next_task以優(yōu)先級(jí)從高到底依次檢查每個(gè)調(diào)度類，從最高優(yōu)先級(jí)的調(diào)度類中選擇最高優(yōu)先級(jí)的進(jìn)程作為
下一個(gè)應(yīng)執(zhí)行進(jìn)程(若其余都睡眠，則只有當(dāng)前進(jìn)程可運(yùn)行，就跳過(guò)下面了)*/
next = pick_next_task(rq, prev); //選擇需要進(jìn)行切換的task
...
}

在選擇下一個(gè)進(jìn)程前，先調(diào)用 put_prev_task (對(duì)應(yīng)到 CFS 為put_prev_task_fair)，計(jì)算下當(dāng)前進(jìn)程的運(yùn)行時(shí)間，根據(jù)當(dāng)前運(yùn)行時(shí)間計(jì)算出虛擬運(yùn)行時(shí)間，并累加到 vruntime，然后把當(dāng)前進(jìn)程根據(jù) vruntime 重新加入到就緒隊(duì)列紅黑樹(shù)中，等待下一次被調(diào)度。

put_prev_task_fair
--> put_prev_entity
--> update_curr
--> __update_curr //更新當(dāng)前調(diào)度實(shí)體的實(shí)際運(yùn)行時(shí)間和虛擬運(yùn)行時(shí)間
--> __enqueue_entity //把當(dāng)前調(diào)度實(shí)體重新加入到就緒隊(duì)列紅黑樹(shù)中等待下一次調(diào)度
/*

cfs_rq：可運(yùn)行隊(duì)列對(duì)象。
curr：當(dāng)前進(jìn)程調(diào)度實(shí)體。
delta_exec：實(shí)際運(yùn)行的時(shí)間。
__update_curr() 函數(shù)主要完成以下幾個(gè)工作：
更新進(jìn)程調(diào)度實(shí)體的總實(shí)際運(yùn)行時(shí)間。
根據(jù)進(jìn)程調(diào)度實(shí)體的權(quán)重值，計(jì)算其使用的虛擬運(yùn)行時(shí)間。
把計(jì)算虛擬運(yùn)行時(shí)間的結(jié)果添加到進(jìn)程調(diào)度實(shí)體的 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));
//// 增加當(dāng)前進(jìn)程總實(shí)際運(yùn)行的時(shí)間
curr->sum_exec_runtime += delta_exec;
// 更新cfs_rq的實(shí)際執(zhí)行時(shí)間cfs_rq->exec_clock
schedstat_add(cfs_rq, exec_clock, delta_exec);
//根據(jù)實(shí)際運(yùn)行時(shí)間計(jì)算虛擬運(yùn)行時(shí)間并累加到當(dāng)前進(jìn)程的虛擬運(yùn)行時(shí)間
delta_exec_weighted = delta_exec;
//// 根據(jù)實(shí)際運(yùn)行時(shí)間計(jì)算其使用的虛擬運(yùn)行時(shí)間
if (unlikely(curr->load.weight != NICE_0_LOAD)) {
delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
&curr->load);
}
curr->vruntime += delta_exec_weighted; // 更新進(jìn)程的虛擬運(yùn)行時(shí)間
/*
? 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運(yùn)行隊(duì)列上vruntime最小值，但是實(shí)際上min_vruntime只能單調(diào)遞增，
所以，如果當(dāng)前進(jìn)程vruntime比min_vruntime小，是不會(huì)更新min_vruntime的。
那么min_vruntime的作用的是什么呢?試想一下如果一個(gè)進(jìn)程睡眠了很長(zhǎng)時(shí)間，則它的vruntime非常小，
一旦它被喚醒，將持續(xù)占用CPU，很容易引發(fā)進(jìn)程饑餓。
CFS調(diào)度器會(huì)根據(jù)min_vruntime設(shè)置一個(gè)合適的vruntime值給被喚醒的進(jìn)程，
既要保證它能優(yōu)先被調(diào)度，又要保證其他進(jìn)程也能得到合理調(diào)度。
*/
cfs_rq->min_vruntime =
max_vruntime(cfs_rq->min_vruntime, vruntime);
}

該函數(shù)的功能如下:

• 更新進(jìn)程調(diào)度實(shí)體的總實(shí)際運(yùn)行時(shí)間。
• 根據(jù)進(jìn)程調(diào)度實(shí)體的權(quán)重值，計(jì)算其虛擬運(yùn)行時(shí)間。
• 把計(jì)算虛擬運(yùn)行時(shí)間的結(jié)果添加到進(jìn)程調(diào)度實(shí)體的 vruntime 字段。

將調(diào)度實(shí)體加入紅黑樹(shù)中

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; // 紅黑樹(shù)根節(jié)點(diǎn)
struct rb_node *parent = NULL;
struct sched_entity *entry;
s64 key = entity_key(cfs_rq, se);// 當(dāng)前進(jìn)程調(diào)度實(shí)體的虛擬運(yùn)行時(shí)間
int leftmost = 1;
/*
? Find the right place in the rbtree:
*/
while (*link) { // 把當(dāng)前調(diào)度實(shí)體插入到運(yùn)行隊(duì)列的紅黑樹(shù)中
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)) { // 比較虛擬運(yùn)行時(shí)間
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = 0;
}
}
/*
? Maintain a cache of leftmost tree entries (it is frequently
? used):
*/
if (leftmost) //緩存最左葉子節(jié)點(diǎn)
cfs_rq->rb_leftmost = &se->run_node;
rb_link_node(&se->run_node, parent, link);
//把節(jié)點(diǎn)插入到紅黑樹(shù)中
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

__enqueue_entity() 函數(shù)的主要工作如下：

1. 獲取運(yùn)行隊(duì)列紅黑樹(shù)的根節(jié)點(diǎn)。
2. 獲取當(dāng)前進(jìn)程調(diào)度實(shí)體的虛擬運(yùn)行時(shí)間。
3. 把當(dāng)前進(jìn)程調(diào)度實(shí)體添加到紅黑樹(shù)中。
4. 緩存紅黑樹(shù)最左端節(jié)點(diǎn)。
5. 對(duì)紅黑樹(shù)進(jìn)行平衡操作。

獲取下一個(gè)合適的調(diào)度實(shí)體

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:
*/
/選擇時(shí)并不是想象中的直接按照調(diào)度器的優(yōu)先級(jí)對(duì)所有調(diào)度器類進(jìn)行遍歷，而是假設(shè)下一個(gè)運(yùn)行的進(jìn)程屬于 cfs 調(diào)度器類，畢竟，系統(tǒng)中絕大多數(shù)的進(jìn)程都是由 cfs 調(diào)度器進(jìn)行管理，這樣做可以從整體上提高執(zhí)行效率./
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 中會(huì)遍歷所有的調(diào)度類，然后從就緒隊(duì)列中選取一個(gè)最合適的調(diào)度實(shí)體進(jìn)行調(diào)度。

對(duì)于完全公平調(diào)度算法(CFS)，會(huì)調(diào)用fair_sched_class.pick_next_task() 函數(shù)，從 fair_sched_class 中可知，也即是調(diào)用 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 調(diào)用過(guò)程如下：

pick_next_task_fair
---> pick_next_entity
---> __pick_next_entity 從就緒隊(duì)列中選取一個(gè)最合適的調(diào)度實(shí)體(虛擬時(shí)間最小的調(diào)度實(shí)體)
---> set_next_entity 把選中的進(jìn)程從紅黑樹(shù)中移除，并更新紅黑樹(shù)

從 schedule 調(diào)用可知，其在選擇下一個(gè)運(yùn)行任務(wù)前，先計(jì)算當(dāng)前進(jìn)程(待切換出去的進(jìn)程)的時(shí)間運(yùn)行時(shí)間，然后根據(jù)實(shí)際運(yùn)行時(shí)間計(jì)算虛擬運(yùn)行時(shí)間，在根據(jù)虛擬運(yùn)行時(shí)間把當(dāng)前進(jìn)程加入到就緒隊(duì)列中的紅黑樹(shù)中等待下一次調(diào)度。

其次，從就緒隊(duì)列的紅黑樹(shù)中選擇虛擬運(yùn)行時(shí)間最小的任務(wù)作為即將運(yùn)行的任務(wù)。

進(jìn)程喚醒

進(jìn)程的默認(rèn)喚醒函數(shù)是 try_to_wake_up(), 該函數(shù)主要是調(diào)整睡眠進(jìn)程的 vruntime值, 以及把睡眠進(jìn)程加入紅黑樹(shù)中, 并判斷是否可以發(fā)生搶占。

調(diào)用關(guān)系如下：

try_to_wake_up
--> activate_task
--> enqueue_task
--> check_preempt_curr

時(shí)鐘周期中斷

周期性調(diào)度器是基于 scheduler_tick 函數(shù)實(shí)現(xiàn)。系統(tǒng)都是以tick(節(jié)拍)來(lái)執(zhí)行各種調(diào)度與統(tǒng)計(jì)，節(jié)拍可以通過(guò) CONFIG_HZ 宏來(lái)控制。內(nèi)核會(huì)以 1/HZ ms 為周期來(lái)執(zhí)行周期性調(diào)度，這也是 CFS 實(shí)現(xiàn)的關(guān)鍵。CFS調(diào)度類會(huì)根據(jù)這個(gè)節(jié)拍來(lái)對(duì)所有進(jìn)程進(jìn)行記賬。每個(gè) CPU 都會(huì)擁有自己的周期性調(diào)度器。周期性調(diào)度器可以把當(dāng)前進(jìn)程設(shè)置為 need resched 狀態(tài)，等待合適的時(shí)機(jī)當(dāng)前的進(jìn)程就會(huì)被重新調(diào)度。

時(shí)鐘周期中斷函數(shù)的調(diào)用過(guò)程:

tick_periodic
--> update_process_times
--> scheduler_tick
--> task_tick_fair
-->entity_tick
--> update_curr
--> check_preempt_tick

在 CFS 中，scheduler_tick 會(huì)調(diào)用 具體實(shí)現(xiàn) task_tick_fair，在task_tick_fair 中會(huì)從當(dāng)前進(jìn)程開(kāi)始獲取每個(gè)調(diào)度實(shí)體，對(duì)每個(gè)調(diào)度實(shí)體進(jìn)行調(diào)用 entity_tick，在 entity_tick 中更新調(diào)度實(shí)體的實(shí)際運(yùn)行時(shí)間和虛擬運(yùn)行時(shí)間，同時(shí)檢查是否需要重新調(diào)度。

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
unsigned long ideal_runtime, delta_exec;
// ideal_runtime 為一個(gè)調(diào)度周期內(nèi)理想的運(yùn)行時(shí)間，也即是為 調(diào)度周期 * 進(jìn)程權(quán)重 / 所有進(jìn)程權(quán)重之和
ideal_runtime = sched_slice(cfs_rq, curr);
// sum_exec_runtime 指進(jìn)程總共執(zhí)行的實(shí)際時(shí)間;
// prev_sum_exec_runtime 指上次該進(jìn)程被調(diào)度時(shí)已經(jīng)占用的實(shí)際時(shí)間。
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
// delta_exec 這次調(diào)度占用實(shí)際時(shí)間，如果大于 ideal_runtime，則應(yīng)該被搶占了
if (delta_exec > ideal_runtime)
resched_task(rq_of(cfs_rq)->curr);
}
若當(dāng)前進(jìn)程運(yùn)行的時(shí)間超過(guò)時(shí)間限制，

則把當(dāng)前進(jìn)程設(shè)置為 被搶占重新調(diào)度標(biāo)記 TIF_NEED_RESCHED，待一定時(shí)機(jī)后會(huì)根據(jù) TIF_NEED_RESCHED 標(biāo)記調(diào)用 schedule() 進(jìn)行調(diào)度切換。關(guān)于“一定的時(shí)機(jī)”，后續(xù)文章進(jìn)行分析。