六、task group時間片

6.1. 時間片分配

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

sched_slice的主要路徑如下：

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

如下圖4，假設tg嵌套2層，且在當前CPU上各層gse從tg那里分得的權重都是1024，且假設直接通過任務個數(shù)來計算周期，5個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的權重通過 cpu.shares 文件進行配置，然后各個cpu上的gse從 cpu.shares 配置的權重中按其上的grq的權重比例分配權重。gse的權重不再和nice值掛鉤。

6.2. 運行時間傳導

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

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

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

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

七、task group的PELT負載

7.1. 計算負載使用的timeline

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

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

7.2. 負載定義與計算

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。

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

7.2. 1. tse負載

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

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

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

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

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

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

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

7.2.2. cfs_rq的負載

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

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

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

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

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

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

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

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

7.2.3. gse 負載

對比著tse來講解gse:

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

(2) gse的runnable負載與tse是不同的。tse的 runnable_sum是任務 running+runnable 狀態(tài)的幾何級數(shù)累加值然后scale up后的值。而gse是其當前層級下所有層級的tse的個數(shù)之和乘以時間幾何級數(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 來源不同，因此也算的上是一個差異點，tse->weight來源于其優(yōu)先級，而gse來源于其從tg中分得的配額。

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

7.2. 4. grq 負載

grq的負載和cfs_rq的負載在更新上沒有什么不同。grq會比cfs_rq多了一個負載傳導更新過程，放到下面講解。

7.2.5. tg的負載

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

調(diào)用路徑：

7.3. 負載傳導

負載傳導是使能CFS組調(diào)度后才有的概念。當tg層次結構上插入或刪除一個tse的時候，整個層次結構的負載都變化了，因此需要逐層向上層進行傳導。

7.3.1. 負載傳導觸發(fā)條件

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

在 add_tg_cfs_propagate() 中標記需要進行負載傳導：

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

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

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

7.3.2. 負載傳導過程

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

load負載傳導函數(shù)和標記需要進行傳導的函數(shù)是同一個，為 add_tg_cfs_propagate(), 其調(diào)用路徑如下：

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

可見gse的util負載在傳導時直接取的是其grq上的util負載。然后通過更新上層 grq 的 util_avg 向上層傳導。

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

可見gse的runnable負載在傳導時也是直接取的是其grq上的runnable負載。然后通過更新上層 grq 的 runnable_avg 向上層傳導。

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

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

對load負載的標記和傳導都是這個函數(shù):

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

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

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

對比可見，runnable負載和util負載的傳導方向是由grq-->gse，分別通過runnable_avg/util_avg進行傳導，gse直接取grq的值。而load負載的傳導方向是由gse-->grq進行傳導，且是通過load_sum進行傳導的。

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

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

圖5:

注: 這只是在tg的層次結構中添加/刪除任務時的負載的傳導更新路徑，隨著時間的流逝，即使沒有添加/移除任務，gse/grq的負載也會更新，因為普通的負載更新函數(shù) __update_load_avg_se()/update_cfs_rq_load_avg() 并沒有區(qū)分是tse還是gse，是cfs_rq還是grq。

7.4. 層次負載

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

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

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

在計算最底層tse的h_load的時候，我們就使用如下公式：

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機制和負載均衡邏輯中使用。比如遷移類型為load的負載均衡中，要遷移多少load_avg可以使負載達到均衡，使用的就是task_h_load()，見 detach_tasks()。

八、總結

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

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