六、task group時(shí)間片

6.1. 時(shí)間片分配

若使能CFS組調(diào)度會(huì)從上到下逐層通過權(quán)重比例來分配上層分得的時(shí)間片，分配函數(shù)是sched_slice()。但是從上到下不便于遍歷，因此改為從下到上進(jìn)行遍歷，畢竟 ABC 和 CBA 是相等的。

sched_slice的主要路徑如下：

在tick中斷中，若發(fā)現(xiàn)se此次運(yùn)行時(shí)間已經(jīng)超過了其分得的時(shí)間片，就觸發(fā)搶占，以便讓其讓出CPU。

如下圖4，假設(shè)tg嵌套2層，且在當(dāng)前CPU上各層gse從tg那里分得的權(quán)重都是1024，且假設(shè)直接通過任務(wù)個(gè)數(shù)來計(jì)算周期，5個(gè)tse，period 就是 3 * 5 = 15ms那么：

tse1 獲得 1024/(1024+1024) * 15 = 7.5ms;

tse2 獲得 [1024/(1024+1024+1024)] * {[1024/(1024+1024)] * 15 }= 2.5ms

tse4 獲得 [1024/(1024+1024)] * {[1024/(1024+1024+1024)] * [1024/(1024+1024)] * 15} = 1.25ms

圖4:

注：tg1和tg2的權(quán)重通過 cpu.shares 文件進(jìn)行配置，然后各個(gè)cpu上的gse從 cpu.shares 配置的權(quán)重中按其上的grq的權(quán)重比例分配權(quán)重。gse的權(quán)重不再和nice值掛鉤。

6.2. 運(yùn)行時(shí)間傳導(dǎo)

pick_next_task_fair() 會(huì)優(yōu)先pick虛擬時(shí)間最小的se。gse的虛擬時(shí)間是怎么更新的呢。虛擬時(shí)間是在 update_curr()中進(jìn)行更新，然后通過 for_each_sched_entity 向上逐層遍歷更新gse的虛擬時(shí)間。若tse運(yùn)行5ms，則其父級(jí)各gse都運(yùn)行5ms，然后各層級(jí)根據(jù)自己的權(quán)重更新虛擬時(shí)間。

主要調(diào)用路徑：

在選擇下一個(gè)任務(wù)出來運(yùn)行時(shí)逐層級(jí)選擇虛擬時(shí)間最小的se，若選到gse就從其grq上繼續(xù)選，直到選到tse。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??

七、task group的PELT負(fù)載

7.1. 計(jì)算負(fù)載使用的timeline

計(jì)算負(fù)載使用的timeline和計(jì)算虛擬時(shí)間使用的timeline不同。計(jì)算虛擬時(shí)間時(shí)使用的timeline是 rq->clock_task, 這個(gè)是運(yùn)行多長(zhǎng)時(shí)間就是多長(zhǎng)時(shí)間。而計(jì)算負(fù)載使用的timeline是rq->clock_pelt，它是根據(jù)CPU的算力和當(dāng)前頻點(diǎn)scale后的，在CPU進(jìn)idle是會(huì)同步到rq->clock_task上。因此PELT計(jì)算出來的負(fù)載可以直接使用，而不用像WALT計(jì)算出來的負(fù)載那樣還需要scale。更新rq->clock_pelt這個(gè)timeline的函數(shù)是 update_rq_clock_pelt()

最終計(jì)算的 delta= delta * (capacity_cpu / capacity_max(1024)) * (cur_cpu_freq / max_cpu_freq) 也就是將當(dāng)前cpu在當(dāng)前頻點(diǎn)上運(yùn)行得到的delta時(shí)間值，縮放到最大性能CPU的最大頻點(diǎn)上對(duì)應(yīng)的delta時(shí)間值。然后累加到 clock_pelt 上。比如在小核上1GHz下跑了5ms，可能只等效于在超大核上運(yùn)行1ms，因此在不同Cluster的CPU核上跑相同的時(shí)間，負(fù)載增加量是不一樣的。

7.2. 負(fù)載定義與計(jì)算

load_avg 定義為：load_avg = runnable% * scale_load_down(load)。

runnable_avg 定義為：runnable_avg = runnable% * SCHED_CAPACITY_SCALE。

util_avg 定義為：util_avg = running% * SCHED_CAPACITY_SCALE。

這些負(fù)載值保存在struct sched_avg結(jié)構(gòu)中，此結(jié)構(gòu)內(nèi)嵌到se和cfs_rq結(jié)構(gòu)中。此外，struct sched_avg中還引入了load_sum、runnable_sum、util_sum成員來輔助計(jì)算。不同實(shí)體(tse/gse/grq/cfs_rq)的負(fù)載只是其runnable% 多么想運(yùn)行，和 running% 運(yùn)行了多少的表現(xiàn)形式不同。這兩個(gè)因數(shù)只對(duì)tse取值是[0,1]的，對(duì)其它實(shí)體則超出了這個(gè)范圍。

7.2. 1. tse負(fù)載

下面看一下tse負(fù)載計(jì)算公式，為了加深印象，舉一個(gè)跑死循環(huán)的例子。計(jì)算函數(shù)見 update_load_avg --> __update_load_avg_se().

load_avg: 等于 weight * load_sum / divider, 其中 weight = sched_prio_to_weight[prio-100]。由于 load_sum 是任務(wù) running+runnable 狀態(tài)的幾何級(jí)數(shù)，divider 近似為幾何級(jí)數(shù)最大值，因此一個(gè)死循環(huán)任務(wù)的 load_avg 接近于其權(quán)重。

runnable_avg: 等于 runnable_sum / divider。由于 runnable_sum 是任務(wù) running+runnable 狀態(tài)的幾何級(jí)數(shù)然后scale up后的值，divider 近似為幾何級(jí)數(shù)最大值，因此一個(gè)死循環(huán)任務(wù)的 runnable_avg 接近于 SCHED_CAPACITY_SCALE。

util_avg: 等于 util_sum / divider。由于 util_sum 是任務(wù) running 狀態(tài)的幾何級(jí)數(shù)然后scale up后的值，divider 近似為幾何級(jí)數(shù)最大值，因此一個(gè)死循環(huán)任務(wù)的 util_avg 接近于 SCHED_CAPACITY_SCALE。

load_sum: 是對(duì)任務(wù)是單純的 running+runnable 狀態(tài)的幾何級(jí)數(shù)累加值。對(duì)于一個(gè)死循環(huán)，此值趨近于 LOAD_AVG_MAX 。

runnable_sum: 是對(duì)任務(wù) running+runnable 狀態(tài)的幾何級(jí)數(shù)累加值然后scale up后的值。對(duì)于一個(gè)死循環(huán)，此值趨近于 LOAD_AVG_MAX * SCHED_CAPACITY_SCALE 。

util_sum: 是對(duì)任務(wù) running 狀態(tài)的幾何級(jí)數(shù)累加值然后scale up后的值。對(duì)于一個(gè)獨(dú)占某個(gè)核的死循環(huán)，此值趨近于 LOAD_AVG_MAX * SCHED_CAPACITY_SCALE，若不能獨(dú)占，會(huì)比此值小。

7.2.2. cfs_rq的負(fù)載

下面看一下cfs_rq負(fù)載計(jì)算公式，為了加深印象，舉一個(gè)跑死循環(huán)的例子。計(jì)算函數(shù)見 update_load_avg --> update_cfs_rq_load_avg --> __update_load_avg_cfs_rq()。

load_avg: 直接等于 load_sum / divider。cfs_rq 跑滿(跑一個(gè)死循環(huán)或多個(gè)死循環(huán))，趨近于cfs_rq的權(quán)重，cfs_rq的權(quán)重也就是其上掛的所有調(diào)度實(shí)體的權(quán)重之和，即Sum(sched_prio_to_weight[prio-100]) 。

runnable_avg: 等于 runnable_sum / divider。cfs_rq 跑滿(跑一個(gè)死循環(huán)或多個(gè)死循環(huán))，趨近于cfs_rq上任務(wù)個(gè)數(shù)乘以 SCHED_CAPACITY_SCALE。

util_avg: 等于 util_sum / divider。cfs_rq 跑滿(跑一個(gè)死循環(huán)或多個(gè)死循環(huán))，趨近于 SCHED_CAPACITY_SCALE。

load_sum: cfs_rq 的 weight，也就是本層級(jí)下所有se的權(quán)重之和乘以非idle狀態(tài)下的幾何級(jí)數(shù)。注意是本層級(jí)，下面講解層次負(fù)載h_load時(shí)有用到。

runnable_sum: cfs_rq上所有層級(jí)的runnable+running 狀態(tài)任務(wù)個(gè)數(shù)和乘以非idle狀態(tài)下的幾何級(jí)數(shù)，然后再乘以 SCHED_CAPACITY_SCALE 后的值。見 __update_load_avg_cfs_rq().

util_sum: cfs_rq 上所有任務(wù) running 狀態(tài)下的幾何級(jí)數(shù)之和再乘以 SCHED_CAPACITY_SCALE 后的值。

load_avg、runnable_avg、util_avg分別從權(quán)重(優(yōu)先級(jí))、任務(wù)個(gè)數(shù)、CPU時(shí)間片占用三個(gè)維度來描述CPU的負(fù)載。

7.2.3. gse 負(fù)載

對(duì)比著tse來講解gse:

(1) gse會(huì)和tse走一樣的負(fù)載更新流程(逐層向上更新，就會(huì)更新到gse)。

(2) gse的runnable負(fù)載與tse是不同的。tse的 runnable_sum是任務(wù) running+runnable 狀態(tài)的幾何級(jí)數(shù)累加值然后scale up后的值。而gse是其當(dāng)前層級(jí)下所有層級(jí)的tse的個(gè)數(shù)之和乘以時(shí)間幾何級(jí)數(shù)然后scale up后的值，見 __update_load_avg_se() 函數(shù) runnable 參數(shù)的差異。

(3) gse 和tse的 load_avg 雖然都等于 se->weight * load_sum/divider, 見 ___update_load_avg() 的參數(shù)差異。但是weight 來源不同，因此也算的上是一個(gè)差異點(diǎn)，tse->weight來源于其優(yōu)先級(jí)，而gse來源于其從tg中分得的配額。

(4) gse會(huì)比tse多出了一個(gè)負(fù)載傳導(dǎo)更新過程，放到下面講解(若不使能CFS組調(diào)度，只有一層，沒有tg的層次結(jié)構(gòu)，因此不需要傳導(dǎo)，只需要更新到cfs_rq上即可)。

7.2. 4. grq 負(fù)載

grq的負(fù)載和cfs_rq的負(fù)載在更新上沒有什么不同。grq會(huì)比cfs_rq多了一個(gè)負(fù)載傳導(dǎo)更新過程，放到下面講解。

7.2.5. tg的負(fù)載

tg只有一個(gè)load負(fù)載，就是tg->load_avg，取值為\Sum tg->cfs_rq[]->avg.load_avg，也即tg所有CPU上的grq的 load_avg 之和。tg負(fù)載更新是在update_tg_load_avg()中實(shí)現(xiàn)的，主要用于給gse[]分配權(quán)重。

調(diào)用路徑：

7.3. 負(fù)載傳導(dǎo)

負(fù)載傳導(dǎo)是使能CFS組調(diào)度后才有的概念。當(dāng)tg層次結(jié)構(gòu)上插入或刪除一個(gè)tse的時(shí)候，整個(gè)層次結(jié)構(gòu)的負(fù)載都變化了，因此需要逐層向上層進(jìn)行傳導(dǎo)。

7.3.1. 負(fù)載傳導(dǎo)觸發(fā)條件

是否需要進(jìn)行負(fù)載傳導(dǎo)是通過struct cfs_rq 的 propagate 成員進(jìn)行標(biāo)記。grq上增加/刪除的tse時(shí)會(huì)觸發(fā)負(fù)載傳導(dǎo)過程。tse的負(fù)載load_sum值會(huì)記錄在 struct cfs_rq 的 prop_runnable_sum 成員上，然后逐層向上傳導(dǎo)。其它負(fù)載(runnable_、util_)則會(huì)通過tse-->grq-->gse-->grq...逐層向上層傳導(dǎo)。

在 add_tg_cfs_propagate() 中標(biāo)記需要進(jìn)行負(fù)載傳導(dǎo)：

此函數(shù)調(diào)用路徑：

由上可見，當(dāng)從非CSF調(diào)度類變?yōu)镃FS調(diào)度類、移到當(dāng)前tg中來、新建的任務(wù)開始掛到cfs_rq上、遷移到當(dāng)前CPU都會(huì)觸發(fā)負(fù)載傳導(dǎo)過程，此時(shí)會(huì)向整個(gè)層次結(jié)構(gòu)中傳導(dǎo)添加這個(gè)任務(wù)帶來的負(fù)載。當(dāng)任務(wù)從當(dāng)前CPU遷移走、變?yōu)榉荂FS調(diào)度類、從tg遷移走，此時(shí)會(huì)向整個(gè)層次結(jié)構(gòu)中傳導(dǎo)移除這個(gè)任務(wù)降低的負(fù)載。

注意，任務(wù)休眠時(shí)并沒有將其負(fù)載移除，只是休眠期間其負(fù)載不增加了，隨時(shí)間衰減。

7.3.2. 負(fù)載傳導(dǎo)過程

負(fù)載傳導(dǎo)過程體現(xiàn)在逐層更新負(fù)載的過程中。如下，負(fù)載更新函數(shù)update_load_avg() 在主要路徑下，每層都會(huì)進(jìn)行調(diào)用：

load負(fù)載傳導(dǎo)函數(shù)和標(biāo)記需要進(jìn)行傳導(dǎo)的函數(shù)是同一個(gè)，為 add_tg_cfs_propagate(), 其調(diào)用路徑如下：

7.3.2.1. update_tg_cfs_util() 更新gse和grq的util_* 負(fù)載，并負(fù)責(zé)將負(fù)載傳遞給上層。

可見gse的util負(fù)載在傳導(dǎo)時(shí)直接取的是其grq上的util負(fù)載。然后通過更新上層 grq 的 util_avg 向上層傳導(dǎo)。

7.3.2.2. update_tg_cfs_runnable() 更新gse和grq的runnable_*負(fù)載，并負(fù)責(zé)將負(fù)載傳遞給上層。

可見gse的runnable負(fù)載在傳導(dǎo)時(shí)也是直接取的是其grq上的runnable負(fù)載。然后通過更新上層 grq 的 runnable_avg 向上層傳導(dǎo)。

7.3.2.3. update_tg_cfs_load() 更新gse和grq的load_*負(fù)載，并負(fù)責(zé)將負(fù)載傳遞給上層。

load負(fù)載比較特殊，負(fù)載傳導(dǎo)時(shí)并不是直接取自grq的load負(fù)載，而是在向grq添加/刪除任務(wù)時(shí)就記錄了tse 的load_sum值，然后在 add_tg_cfs_propagate() 中逐層向上傳導(dǎo)，傳導(dǎo)位置調(diào)用路徑：

對(duì)load負(fù)載的標(biāo)記和傳導(dǎo)都是這個(gè)函數(shù):

load負(fù)載更新函數(shù)：

刪除任務(wù)就是將grq上的se的平均load_sum賦值給gse。添加任務(wù)是將gse的load_sum直接加上delta值。

load_avg和普通tse計(jì)算方式一樣，為load_sum*se_weight(gse)/divider。

對(duì)比可見，runnable負(fù)載和util負(fù)載的傳導(dǎo)方向是由grq-->gse，分別通過runnable_avg/util_avg進(jìn)行傳導(dǎo)，gse直接取grq的值。而load負(fù)載的傳導(dǎo)方向是由gse-->grq進(jìn)行傳導(dǎo)，且是通過load_sum進(jìn)行傳導(dǎo)的。

load負(fù)載傳導(dǎo)賦值方式上為什么和runnable負(fù)載和util負(fù)載有差異，可能和其統(tǒng)計(jì)算法有關(guān)。對(duì)于runnable_avg，gse計(jì)算的是當(dāng)前層級(jí)下所有層級(jí)上tse的個(gè)數(shù)和乘以runnable狀態(tài)時(shí)間級(jí)數(shù)的比值，底層增加一個(gè)tse對(duì)上層相當(dāng)于tse個(gè)數(shù)增加了一個(gè)；對(duì)于util_avg，gse計(jì)算的是其下所有tse的running狀態(tài)幾何級(jí)數(shù)和與時(shí)間級(jí)數(shù)的比值，底層增加一個(gè)tse對(duì)上層就相當(dāng)于增加了tse的running狀態(tài)的幾何級(jí)數(shù)；而 load_avg 和se的權(quán)重有關(guān)，gse和tse的權(quán)重來源不同，前者來自從tg->shares中分得的配額，而后者來源于優(yōu)先級(jí)，不能直接相加減。而load_sum對(duì)于se來說是一個(gè)單純的runnable狀態(tài)的時(shí)間級(jí)數(shù)，不涉及權(quán)重，因此tse和gse都可以使用它。

對(duì)于load_avg的傳導(dǎo)舉個(gè)例子，如下圖5，假如ts2一直休眠，ts1和ts3是兩個(gè)死循環(huán)，那么gse1的grq1的load_avg將趨近于4096，而根cfs_rq的負(fù)載將趨近于2048，若此時(shí)要將ts3遷移走，若像計(jì)算runnable和util負(fù)載那樣直接想減，得到的delta值是-4096，那么根cfs_rq的load_avg將會(huì)是個(gè)負(fù)值(2048-4096<0)，這顯然是不合理的。若通過load_sum進(jìn)行傳導(dǎo)，它只是個(gè)時(shí)間級(jí)數(shù)，相減后根cfs_rq上只相當(dāng)于損失了50%的負(fù)載。

圖5:

注: 這只是在tg的層次結(jié)構(gòu)中添加/刪除任務(wù)時(shí)的負(fù)載的傳導(dǎo)更新路徑，隨著時(shí)間的流逝，即使沒有添加/移除任務(wù)，gse/grq的負(fù)載也會(huì)更新，因?yàn)槠胀ǖ呢?fù)載更新函數(shù) __update_load_avg_se()/update_cfs_rq_load_avg() 并沒有區(qū)分是tse還是gse，是cfs_rq還是grq。

7.4. 層次負(fù)載

在負(fù)載均衡的時(shí)候，需要遷移CPU上的負(fù)載以便達(dá)到均衡，為了達(dá)成這個(gè)目的，需要在CPU之間進(jìn)行任務(wù)遷移。然而各個(gè)task se的load avg并不能真實(shí)反映它對(duì)root cfs rq（即對(duì)該CPU）的負(fù)載貢獻(xiàn)，因?yàn)閠ask se/cfs rq總是在某個(gè)具體level上計(jì)算其load avg。比如grq的load_avg并不會(huì)等于其上掛的所有tse的load_avg的和，因?yàn)閞unnable的時(shí)間級(jí)數(shù)肯定是Sum(tse) > grq的(有runnable等待運(yùn)行的狀態(tài)存在)。

為了計(jì)算task對(duì)CPU的負(fù)載(h_load)，在各個(gè)cfs rq上引入了hierarchy load的概念，對(duì)于頂層cfs rq而言，其hierarchy load等于該cfs rq的load avg，隨著層級(jí)的遞進(jìn)，cfs rq的hierarchy load定義如下：

下一層的cfs rq的h_load = 上一層cfs rq的h_load x gse負(fù)載在上一層cfs負(fù)載中的占比

在計(jì)算最底層tse的h_load的時(shí)候，我們就使用如下公式：

tse的h_load = grq的h_load x tse的load avg / grq的load avg

獲取和更新task的h_load的函數(shù)如下：

更新grq的h_load的函數(shù)如下：

調(diào)用路徑：

可以看到，主要是喚醒wake_affine_weight機(jī)制和負(fù)載均衡邏輯中使用。比如遷移類型為load的負(fù)載均衡中，要遷移多少load_avg可以使負(fù)載達(dá)到均衡，使用的就是task_h_load()，見 detach_tasks()。

八、總結(jié)

本文介紹了CFS組調(diào)度功能引入的原因，配置方法，和一些實(shí)現(xiàn)細(xì)節(jié)。此功能可以在高負(fù)載下"軟限制"(相比與CFS帶寬控制)各分組任務(wù)對(duì)CPU資源的使用占比，以達(dá)到各組之間公平使用CPU資源的目的。在老版原生Android代碼中對(duì)后臺(tái)分組限制的較狠(甚是將 background/cpu.shares 設(shè)置到52)，將CPU資源重點(diǎn)向前臺(tái)分組進(jìn)行傾斜，但這個(gè)配置可能會(huì)在某些場(chǎng)景下出現(xiàn)前臺(tái)任務(wù)被后臺(tái)任務(wù)卡住的情況，對(duì)于普適性配置，最新的一些Android版本中將各個(gè)分組的 cpu.shares 都設(shè)置為1024以追求CPU資源在各組之間的公平。

原文作者：內(nèi)核工匠