1. 說明
1> linux內(nèi)核關(guān)于task調(diào)度這塊是比較復(fù)雜的，流程也比較長，要從源碼一一講清楚很容易看暈
2> 本篇文章主要是講清楚cfs公平調(diào)度算法如何將task在時鐘中斷驅(qū)動下切換調(diào)度，所以與此無關(guān)的代碼一律略過
3> 本篇只講最簡單的task調(diào)度，略過組調(diào)度，組調(diào)度在下一篇《極簡組調(diào)度-CGroup如何限制cpu》中講解
4> 本篇源碼來自CentOS7.6的3.10.0-957.el7內(nèi)核
?
2. 極簡task調(diào)度核心思想
1> linux采用cfs公平調(diào)度算法，其用vruntime記錄task運行的cpu時長，每次用重新調(diào)度時，總是選擇vruntime最小的task進(jìn)行調(diào)度
2> 所有Ready狀態(tài)的task會分配到不同cpu的rq隊列上，等待調(diào)度運行
3> 時鐘中斷中，++當(dāng)前task運行時間vruntime，并檢測當(dāng)前task運行時間是否超過一個時間片，或者其vruntime比當(dāng)前cpu rq隊列中最小的vruntime task大一個時間片，則設(shè)置resched標(biāo)記(但并不立馬進(jìn)行task切換，因為此時仍在中斷上下文中)
4> 所有中斷返回后（當(dāng)然也包括時鐘中斷），都會jump到ret_from_intr，這里會檢查resched標(biāo)記，如果置位，則調(diào)用schedule()選擇vruntime最小的task進(jìn)行調(diào)度
?
3. 極簡task調(diào)度相關(guān)數(shù)據(jù)結(jié)構(gòu)
3.1 名詞解釋
| ? |
全稱
|
說明
|
| se | schedule entity | 調(diào)度實例，可以是一個task，也可以是一個group（當(dāng)使用組調(diào)度時），linux支持組調(diào)度后，將調(diào)度實例從原來的task，抽象為se |
| rq | run queue | cpu的運行隊列，每個cpu一個，處于Ready狀態(tài)的se掛在對應(yīng)的cpu運行隊列上后，才會被選擇投入運行? |
| cfs_rq | cfs rq | 公平調(diào)度運行隊列，因為一般進(jìn)程都是用cfs調(diào)度算法，一般進(jìn)程的se都是掛在rq.cfs_rq上的 |
| vruntime | virtual runtime | se的一個重要成員，記錄調(diào)度實例的cpu運行時長，schedule時，cfs調(diào)度每次都選取vruntime最小的se投入運行，這就是cfs調(diào)度算法的核心原理 |
?
?
3.2 數(shù)據(jù)結(jié)構(gòu)
struct sched_entity { unsigned int on_rq; // se是否在rq上，不在的話即使task是Ready狀態(tài)也不會投入運行的 u64 vruntime; // cpu運行時長，cfs調(diào)度算法總是選擇該值最小的se投入運行 }; struct task { struct sched_entity se; // 調(diào)度實例 }; struct rq { struct cfs_rq cfs; // 所有要調(diào)度的se都掛在cfs rq中 struct task_struct* curr; // 當(dāng)前cpu上運行的task }; struct cfs_rq { struct rb_root tasks_timeline; // 以vruntime為key，se為value的紅黑樹根節(jié)點，schedule時，cfs調(diào)度算法每次從這里挑選vruntime最小的se投入運行 struct rb_node* rb_leftmost; // tasks_timeline紅黑樹最左的葉子節(jié)點，即vruntime最小的se，直接取這個節(jié)點以加快速度 sched_entity* curr; // cfs_rq中當(dāng)前正在運行的se struct rq* rq; /* cpu runqueue to which this cfs_rq is attached */ unsigned int nr_running; // cfs_rq隊列上有多少個se };
?
3.3 數(shù)據(jù)結(jié)構(gòu)關(guān)系
?
2.3 極簡task調(diào)度code
2.3.1 時鐘中斷
1> task調(diào)度的發(fā)動機時鐘中斷觸發(fā)后，會在smp_apic_timer_interrupt()中處理，經(jīng)過層層調(diào)用，最終會到entity_tick()
entity_tick() { update_curr(); // 如果當(dāng)前cfs_rq上的se大于1，則檢查是否要重新調(diào)度 if (cfs_rq->nr_running > 1) check_preempt_tick(cfs_rq, curr); }
2> update_curr()主要是++當(dāng)前task se的vruntime（當(dāng)然這里還對組調(diào)度進(jìn)行了處理，這里不講組調(diào)度，先略過）
void update_curr(struct cfs_rq* cfs_rq) { struct sched_entity* curr = cfs_rq->curr; curr->vruntime += delta_exec; // 增加se的運行時間 }
?3>?check_preempt_tick()判定當(dāng)前運行的時間大于sched_slice時，即超過了時間片，或者其vruntime比當(dāng)前cpu rq隊列中最小的vruntime task大一個時間片，就會標(biāo)記resched，然后等中斷返回后會調(diào)用schedule()進(jìn)行task切換
void check_preempt_tick() { // 如果運行時間大于sched_slice，則resched if (delta_exec > ideal_runtime) resched_task(rq_of(cfs_rq)->curr); // 如果比最小vruntime大一個sched_slice，則resched se = __pick_first_entity(cfs_rq); // 選擇cfs.rb_leftmost的se，即vruntime最小的se delta = curr->vruntime - se->vruntime; if (delta > ideal_runtime) resched_task(rq_of(cfs_rq)->curr); }
?4>?resched_curr()非常簡單，就是設(shè)置一個resched標(biāo)記位TIF_NEED_RESCHED
void resched_curr(struct rq* rq) { struct task_struct* curr = rq->curr; set_tsk_thread_flag(curr, TIF_NEED_RESCHED); }
?
2.3.2 schedule
1> 時鐘中斷返回后，會jump到ret_from_intr(有興趣可以去分析這段匯編)，如果resched標(biāo)記被置位，就會調(diào)用schedule()進(jìn)行調(diào)度
void schedule() { prev = rq->curr; put_prev_task_fair(rq, prev); // 對當(dāng)前task進(jìn)行處理，如果該task屬于一個group，還要對組調(diào)度進(jìn)行處理，這里不展開 // 選擇下一個task并切換運行 next = pick_next_task(rq); // 選擇一個vruntime最小的task進(jìn)行調(diào)度 context_switch(rq, prev, next); }
2>?pick_next_task() → pick_next_task_fair() → pick_next_entity() → __pick_first_entity()，__pick_first_entity()選擇vruntime最小的cfs_rq->rb_leftmost節(jié)點se進(jìn)行調(diào)度文章來源：http://www.zghlxwxcb.cn/news/detail-413453.html
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = cfs_rq->rb_leftmost; return rb_entry(left, struct sched_entity, run_node); }
?文章來源地址http://www.zghlxwxcb.cn/news/detail-413453.html
?
到了這里，關(guān)于極簡cfs公平調(diào)度算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
