//默認(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)一個調(diào)度周期內(nèi)的進(jìn)程數(shù)：sysctl_sched_latency / sysctl_sched_min_granularity
static unsigned int sched_nr_latency = 5;

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,
};

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

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

do_fork
--> wake_up_new_task
--> task_new_fair //設(shè)置新進(jìn)程的vruntime值,并將其加入就緒隊列中
--> check_preempt_curr //檢查新進(jìn)程是否可以搶占當(dāng)前進(jì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)程先運行
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時, 交換兩個進(jìn)程的vruntime值
}
enqueue_task_fair(rq, p, 0);//將新任務(wù)加入到就緒隊列中
//設(shè)置TIF_NEED_RESCHED標(biāo)志值，該標(biāo)記標(biāo)志進(jìn)程是否需要重新調(diào)度，如果設(shè)置了，就會發(fā)生調(diào)度
resched_task(rq->curr);
}

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); //計算調(diào)度粒度
/*

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

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);
}

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對應(yīng)的運行隊列
rcu_qsctr_inc(cpu);
prev = rq->curr; /*讓prev 成為當(dāng)前進(jìn)程 */
switch_count = &prev->nivcsw;
/釋放全局內(nèi)核鎖，并開this_cpu 的中斷/
release_kernel_lock(prev);
need_resched_nonpreemptible:
__update_rq_clock(rq); //更新運行隊列的時鐘值
...
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
// 對應(yīng)到CFS,則為 put_prev_task_fair
prev->sched_class->put_prev_task(rq, prev); //通知調(diào)度器類當(dāng)前運行進(jìn)程要被另一個進(jìn)程取代
/*pick_next_task以優(yōu)先級從高到底依次檢查每個調(diào)度類，從最高優(yōu)先級的調(diào)度類中選擇最高優(yōu)先級的進(jìn)程作為
下一個應(yīng)執(zhí)行進(jìn)程(若其余都睡眠，則只有當(dāng)前進(jìn)程可運行，就跳過下面了)*/
next = pick_next_task(rq, prev); //選擇需要進(jìn)行切換的task
...
}

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

cfs_rq：可運行隊列對象。
curr：當(dāng)前進(jìn)程調(diào)度實體。
delta_exec：實際運行的時間。
__update_curr() 函數(shù)主要完成以下幾個工作：
更新進(jìn)程調(diào)度實體的總實際運行時間。
根據(jù)進(jìn)程調(diào)度實體的權(quán)重值，計算其使用的虛擬運行時間。
把計算虛擬運行時間的結(jié)果添加到進(jìn)程調(diào)度實體的 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)程總實際運行的時間
curr->sum_exec_runtime += delta_exec;
// 更新cfs_rq的實際執(zhí)行時間cfs_rq->exec_clock
schedstat_add(cfs_rq, exec_clock, delta_exec);
//根據(jù)實際運行時間計算虛擬運行時間并累加到當(dāng)前進(jìn)程的虛擬運行時間
delta_exec_weighted = delta_exec;
//// 根據(jù)實際運行時間計算其使用的虛擬運行時間
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)程的虛擬運行時間
/*
? 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只能單調(diào)遞增，
所以，如果當(dāng)前進(jìn)程vruntime比min_vruntime小，是不會更新min_vruntime的。
那么min_vruntime的作用的是什么呢?試想一下如果一個進(jìn)程睡眠了很長時間，則它的vruntime非常小，
一旦它被喚醒，將持續(xù)占用CPU，很容易引發(fā)進(jìn)程饑餓。
CFS調(diào)度器會根據(jù)min_vruntime設(shè)置一個合適的vruntime值給被喚醒的進(jìn)程，
既要保證它能優(yōu)先被調(diào)度，又要保證其他進(jìn)程也能得到合理調(diào)度。
*/
cfs_rq->min_vruntime =
max_vruntime(cfs_rq->min_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; // 紅黑樹根節(jié)點
struct rb_node *parent = NULL;
struct sched_entity *entry;
s64 key = entity_key(cfs_rq, se);// 當(dāng)前進(jìn)程調(diào)度實體的虛擬運行時間
int leftmost = 1;
/*
? Find the right place in the rbtree:
*/
while (*link) { // 把當(dāng)前調(diào)度實體插入到運行隊列的紅黑樹中
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) //緩存最左葉子節(jié)點
cfs_rq->rb_leftmost = &se->run_node;
rb_link_node(&se->run_node, parent, link);
//把節(jié)點插入到紅黑樹中
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

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:
*/
/選擇時并不是想象中的直接按照調(diào)度器的優(yōu)先級對所有調(diào)度器類進(jìn)行遍歷，而是假設(shè)下一個運行的進(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;
}
}

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_entity
---> __pick_next_entity 從就緒隊列中選取一個最合適的調(diào)度實體(虛擬時間最小的調(diào)度實體)
---> set_next_entity 把選中的進(jìn)程從紅黑樹中移除，并更新紅黑樹

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

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

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