CFS組調(diào)度
注：本文縮寫說明
一、CFS組調(diào)度簡介
1.1. 存在的原因
總結(jié)來說是希望不同分組的任務(wù)在高負(fù)載下能分配可控比例的CPU資源。為什么會(huì)有這個(gè)需求呢，比如多用戶計(jì)算機(jī)系統(tǒng)每個(gè)用戶的所有任務(wù)劃分到一個(gè)分組中，A用戶90個(gè)相同任務(wù)，而B用戶只有10個(gè)相同任務(wù)，在CPU完全跑滿的情況下，那么A用戶將占90%的CPU時(shí)間，而B用戶只占到了10%的CPU時(shí)間，這對(duì)B用戶顯然是不公平的。再或者同一個(gè)用戶，既想-j64快速編譯，又不想被編譯任務(wù)影響使用體驗(yàn)，也可將編譯任務(wù)設(shè)置到對(duì)應(yīng)分組中，限制其CPU資源。
1.2. 手機(jī)設(shè)備上的分組狀態(tài)
/dev/cpuctl 目錄使用struct task_group root_task_group 表示。其下的每一層級(jí)的子目錄都抽象為一個(gè)task_group結(jié)構(gòu)。有幾個(gè)需要注意的點(diǎn)：
根組下的cpu.shares 文件默認(rèn)值是1024，而且不支持設(shè)置。根組的負(fù)載也不會(huì)更新。
根組也是一個(gè)task group，根組下的任務(wù)也是被分過組的，不會(huì)再屬于其它組。
內(nèi)核線程默認(rèn)在根組下，其直接從根cfs_rq上分配時(shí)間片，有非常大的優(yōu)勢，若是其一直跑，那在trace上看就幾乎就是”一直跑”，比如常見的kswapd內(nèi)核線程。
默認(rèn)cpu.shares配置下，若全是nice=0的任務(wù)，且只考慮單核的情況下，根組下的每個(gè)任務(wù)在完全滿載情況下能得到的時(shí)間片等于其它分組下所有任務(wù)能分配到的時(shí)間片的總和。
注意：task和task group都是通過權(quán)重來分配時(shí)間片的，但是task的權(quán)重來自其優(yōu)先級(jí)，而task group的權(quán)重則來自與其cgroup目錄下cpu.shares文件設(shè)置的值。使能組調(diào)度后，看任務(wù)分得的時(shí)間片，就不能單看其prio對(duì)應(yīng)的權(quán)重了，還要看其task group分得的權(quán)重和本group中其它任務(wù)的運(yùn)行情況。
二、任務(wù)的task group分組
CFS組調(diào)度功能主要是通過對(duì)任務(wù)進(jìn)行分組體現(xiàn)出來的，一個(gè)分組由一個(gè)struct task_group來表示。
2.1. 如何設(shè)置分組
task group分組配置接口由cpu cgroup子系統(tǒng)通過cgroup目錄層次結(jié)構(gòu)導(dǎo)出到用戶空間。
如何從task group中移除一個(gè)任務(wù)呢，沒有辦法直接移除的，在cgroup語義下，一個(gè)任務(wù)某一時(shí)刻必須屬于一個(gè)task group，只有通過將其echo到其它分組中才能將其從當(dāng)前分組中移除。
2.2. Android中如何設(shè)置分組
Process.java中向其它模塊提供 setProcessGroup(int pid, int group) 將pid進(jìn)程設(shè)置進(jìn)group參數(shù)指定的分組中，供其它模塊進(jìn)行調(diào)用設(shè)置。比如OomAdjuster.java 中將任務(wù)切前/后臺(tái)分別調(diào)用傳參group=THREAD_GROUP_TOP_APP/THREAD_GROUP_BACKGROUND。
libprocessgroup 中提供了一個(gè)名為 task_profiles.json 的配置文件，它里面 AggregateProfiles 聚合屬性字段配置了上層設(shè)置下來后的對(duì)應(yīng)的行為。比如 THREAD_GROUP_TOP_APP 對(duì)應(yīng)的聚合屬性為 SCHED_SP_TOP_APP，其中的MaxPerformance屬性對(duì)應(yīng)的行為就是加入到cpu top-app分組。
”MaxPerformance”屬性的配置可讀性非常強(qiáng)，可以看出是加入到cpu子系統(tǒng)的top-app分組中。
2.3. Android中設(shè)置為TOP-APP分組，對(duì)cgroup設(shè)置了什么
因?yàn)橛卸鄠€(gè)cgroup子系統(tǒng)，除了我們正在講的CFS組調(diào)度依附的cpu cgroup子系統(tǒng)外，還有cpuset cgroup子系統(tǒng)(限制任務(wù)可運(yùn)行的CPU和可使用的內(nèi)存節(jié)點(diǎn))，blkio cgroup子系統(tǒng)(限制進(jìn)程的塊設(shè)備io)，freezer cgroup子系統(tǒng)(提供進(jìn)程凍結(jié)功能)等。上層配置分組下來可能不只切一個(gè)cgroup，具體切了哪些子系統(tǒng)體現(xiàn)在集合屬性 AggregateProfiles 的數(shù)組成員上，比如上例中另外兩個(gè)屬性對(duì)應(yīng)的行為分別是加入blkio子系統(tǒng)的根組和將任務(wù)的timer_slack_ns(一個(gè)平衡hrtimer定時(shí)喚醒及時(shí)性與功耗的參數(shù))設(shè)置為50000ns。
2.4. 服務(wù)啟動(dòng)后就放在指定分組
在啟動(dòng)服務(wù)的時(shí)候使用 task_profiles進(jìn)行配置，舉例。
三、內(nèi)核實(shí)現(xiàn)概述
上面我們討論了對(duì)task group分組的配置，本節(jié)開始將進(jìn)入到內(nèi)核中，了解其實(shí)現(xiàn)。
3.1. 相關(guān)功能依賴關(guān)系
內(nèi)核相關(guān)CONFIG_*依賴如下：
圖1:
CGROUP提供cgroup目錄層次結(jié)構(gòu)的功能；CGROUP_SCHED提供cpu cgroup目錄層次結(jié)構(gòu)（如 /dev/cpuctl/top-app），并為每個(gè)cpu cgroup目錄提供task group的概念；FAIR_GROUP_SCHED基于cpu cgroup提供的task group提供CFS任務(wù)組調(diào)度功能。圖1中灰色的虛線框圖是Android手機(jī)內(nèi)核中默認(rèn)不使能的。
3.2. task group數(shù)據(jù)結(jié)構(gòu)框圖
如下圖2所示，展示了一個(gè)task group在內(nèi)核中維護(hù)的主要數(shù)據(jù)結(jié)構(gòu)的框圖，對(duì)照著圖下面概念更容易理解：
由于不能確定一個(gè)分組內(nèi)的任務(wù)跑在哪個(gè)CPU上，因此一個(gè)task group在每個(gè)CPU上都維護(hù)了一個(gè)group cfs_rq，由于task group也要參與調(diào)度(要先選中task group才能選中其group cfs_rq上的任務(wù)) ，因此在每個(gè)CPU上也都維護(hù)了一個(gè)group se。
task se的my_q成員為NULL，而group se的my_q成員指向其對(duì)應(yīng)的group cfs_rq，其分組在本CPU上的就緒任務(wù)就掛在這個(gè)group cfs_rq上。
task group可以嵌套，由 parent/siblings/children 成員構(gòu)成一個(gè)倒立樹狀層次結(jié)構(gòu)，根task group的parent指向NULL。
所有CPU的根cfs_rq屬于root task group。
圖2:
注：畫圖比較麻煩，此圖是借鑒蝸窩的。
四、相關(guān)結(jié)構(gòu)體
4.1. struct task_group
一個(gè) struct task_group 就表示一個(gè)cpu cgroup分組。在使能FAIR_GROUP_SCHED的情況下，一個(gè) struct task_group 就表示CFS組調(diào)度中的一個(gè)任務(wù)組。
css: 該task group對(duì)應(yīng)的cgroup狀態(tài)信息，通過它依附到cgroup目錄層次結(jié)構(gòu)中。
se: ?group se，是個(gè)數(shù)組指針，數(shù)組大小為CPU的個(gè)數(shù)。因?yàn)橐粋€(gè)task group中有多個(gè)任務(wù)，且可以跑在所有CPU上，因此需要每個(gè)CPU上都要有本task group的一個(gè) se。
cfs_rq: ?group se的cfs_rq, 是本task group的在各個(gè)CPU上的cfs_rq，也是個(gè)數(shù)組指針，數(shù)組大小為CPU的個(gè)數(shù)。當(dāng)本task group的任務(wù)就緒后就掛在這個(gè)cfs_rq上。它在各個(gè)CPU上對(duì)應(yīng)的指針和task group在各個(gè)CPU上的se->my_q具有相同指向，見 init_tg_cfs_entry().
shares: ?task group的權(quán)重，默認(rèn)為scale_up(1024)。和task se的權(quán)重類似，值越大task group能獲取的CPU時(shí)間片就越多。但是和task 不同的是，task group 在每個(gè)CPU上都有一個(gè)group se，因此需要按照一定規(guī)則分配給各CPU上的group se, 下面會(huì)講解分配規(guī)則。
load_avg: 此task group的負(fù)載，而且只是一個(gè)load_avg 變量(不像se和cfs_rq是一個(gè)結(jié)構(gòu))，下面會(huì)對(duì)其進(jìn)行講解。注意它不是per-cpu的，此task group的任務(wù)在各個(gè)CPU上進(jìn)行更新時(shí)都會(huì)更新它，因此需要注意對(duì)性能的影響。
parent/siblings/children: 構(gòu)成task group的層次結(jié)構(gòu)。
內(nèi)核中有個(gè)全局變量 struct task_group root_task_group, 表示根組。其cfs_rq[]就是各個(gè)cpu的cfs_rq, 其se[]都為NULL。其權(quán)重不允許被設(shè)置，見 sched_group_set_shares()。負(fù)載也不會(huì)被更新，見 update_tg_load_avg()。
系統(tǒng)中的所有task group 結(jié)構(gòu)都會(huì)被添加到task_groups鏈表上，在CFS帶寬控制時(shí)使用。
初學(xué)者可能會(huì)混淆組調(diào)度和調(diào)度組這兩個(gè)概念，以及 struct task_group 與struct sched_group 的區(qū)別。組調(diào)度對(duì)應(yīng)struct task_group，用來描述一組任務(wù)，主要用于util uclamp(對(duì)一組任務(wù)的算力需求進(jìn)行鉗制)和CPU資源使用限制，也是本文中要講解的內(nèi)容。調(diào)度組對(duì)應(yīng) struct sched_group，是CPU拓?fù)浣Y(jié)構(gòu)sched_domain中的概念，用來描述一個(gè)CPU(MC層級(jí))/Cluster(DIE層級(jí))的屬性，主要用于選核和負(fù)載均衡。
4.2. struct sched_entity
一個(gè)sched_entity 既可以表示一個(gè)task se, 又可以表示一個(gè)group se。下面主要介紹使能組調(diào)度后新增的一些成員。
load: 表示se的權(quán)重，對(duì)于gse, 新建時(shí)初始化為NICE_0_LOAD, 見init_tg_cfs_entry()。
depth: ?表示task group的嵌套深度，根組下的se的深度為0，每嵌套深一層就加1。比如/dev/cpuctl目錄下有個(gè)tg1目錄，tg1目錄下又有一個(gè)tg2目錄，tg1對(duì)應(yīng)的group se的深度為0，tg1下的task se的深度是1，tg2下的task se的深度是2。更新位置見 init_tg_cfs_entry()/attach_entity_cfs_rq()。
parent: 指向父se節(jié)點(diǎn), 父子se節(jié)點(diǎn)都是對(duì)應(yīng)同一cpu的。根組下任務(wù)的指向?yàn)镹ULL。
cfs_rq: 該se掛載到的cfs_rq。對(duì)于根組下的任務(wù)指向rq的cfs_rq，非根組的任務(wù)指向其parent->my_rq，見init_tg_cfs_entry()。
my_q: 該se的cfs_rq, 只有g(shù)roup se才有cfs_rq，task se的為NULL，entity_is_task()宏通過這個(gè)成員來判斷是task se還是group se。
runnable_weight: 緩存 gse->my_q->h_nr_running 的值，在計(jì)算gse的runnable負(fù)載時(shí)使用。
avg: se的負(fù)載，對(duì)于tse會(huì)初始化為其權(quán)重(創(chuàng)建時(shí)假設(shè)其負(fù)載很高)，而gse則會(huì)初始化為0，見init_entity_runnable_average()。task se的和group se的有一定區(qū)別，下面第五章會(huì)進(jìn)行講解。
4.3. struct cfs_rq
struct cfs_rq 既可以表示per-cpu的CFS就緒隊(duì)列，又可以用來表示gse的my_q隊(duì)列。下面列出對(duì)組調(diào)度比較關(guān)鍵的一些成員進(jìn)行講解。
load: 表示cfs_rq的權(quán)重，無論是根cfs_rq還是grq，這里的權(quán)重都等于其隊(duì)列上掛的所有任務(wù)的權(quán)重之和。
nr_running: 當(dāng)前層級(jí)下 task se 和 group se的個(gè)數(shù)和。
h_nr_running: 當(dāng)前層級(jí)以及所有子層級(jí)下task se的個(gè)數(shù)和，不包括group se。
avg: cfs_rq的負(fù)載。下面將對(duì)比task se、group se、cfs_rq講解負(fù)載。
removed: 當(dāng)一個(gè)任務(wù)退出或者喚醒后遷移到到其他cpu上的時(shí)候，原來CPU的cfs rq上需要移除該任務(wù)帶來的負(fù)載。這個(gè)移除動(dòng)作會(huì)先把移除的負(fù)載記錄在這個(gè)removed成員中，在下次調(diào)用update_cfs_rq_load_avg()更新cfs_rq負(fù)載時(shí)再移除。nr表示要移除的se的個(gè)數(shù)，*_avg則表示要移除的各類負(fù)載之和。
tg_load_avg_contrib: 是對(duì) grq->avg.load_avg 的一個(gè)緩存，表示當(dāng)前grq的load負(fù)載對(duì)tg的貢獻(xiàn)值。用于在更新 tg->load_avg 的同時(shí)降低對(duì) tg->load_avg 的訪問次數(shù)。在計(jì)算gse從tg分得的權(quán)重配額時(shí)的近似算法中也有用到，見 calc_group_shares()/update_tg_load_avg()。
propagate: 標(biāo)記是否有負(fù)載需要向上層傳播。下面7.3節(jié)會(huì)進(jìn)行講解。
prop_runnable_sum: 在負(fù)載沿著task group層級(jí)結(jié)構(gòu)向上層傳播的時(shí)候，表示要上傳的tse/gse的load_sum值。
h_load: 層次負(fù)載hierarchy load，表示本層cfs_rq的load_avg對(duì)CPU的load_avg的貢獻(xiàn)值，主要在負(fù)載均衡路徑中使用。下面會(huì)對(duì)其進(jìn)行講解。
last_h_load_update: 表示上一次更新h_load的時(shí)間點(diǎn)(單位jiffies)。
h_load_next: 指向子gse，為了獲取任務(wù)的hierarchy load（task_h_load函數(shù)），需要從頂層cfs向下，依次更新各個(gè)level的cfs rq的h_load。因此，這里的h_load_next就是為了形成一個(gè)從頂層cfs rq到底層cfs rq的cfs rq--se--cfs rq--se的關(guān)系鏈。
rq: 使能組調(diào)度后才加的這個(gè)成員，若沒有使能組調(diào)度的話，cfs_rq就是rq的一個(gè)成員，使用 container_of進(jìn)行路由，使能組調(diào)度后，增加了一個(gè)rq成員進(jìn)行cfs_rq到rq的路由。
on_list/leaf_cfs_rq_list: 嘗試將葉cfs_rq串聯(lián)起來，在CFS負(fù)載均衡和帶寬控制相關(guān)邏輯中使用。
tg: 該cfs_rq隸屬的task group。
五、task group權(quán)重
task group的權(quán)重使用struct task_group 的 shares 成員來表示，默認(rèn)值是scale_load(1024)?？梢酝ㄟ^cgroup目錄下的cpu.shares文件進(jìn)行讀寫，echo weight > cpu.shares 就是將task group權(quán)重配置為weight，保存到shares 成員變量中的值是scale_load(weight)。root_task_group不支持設(shè)置權(quán)重。
不同task group的權(quán)重大小表示系統(tǒng)CPU跑滿后，哪個(gè)task group組可以跑多一些，哪個(gè)task group組要跑的少一些。
5.1. gse的權(quán)重
task group在每個(gè)CPU上都有一個(gè)group se，那么就需要將task group的權(quán)重 tg->shares 按照一定的規(guī)則分配到各個(gè)gse上。規(guī)則就是公式(1)：
* ? ? ? ? ? ? ? ? ? ? tg->weight * grq->load.weight
* ? ge->load.weight = ? ----------------------------------------- ? ? ? ? ? ? ?(1)
* ? ? ? ? ? ? ? ? ? ? ? \Sum grq->load.weight
其中 tg->weight 就是tg->shares, grq->load.weight 表示tg在各個(gè)CPU上的grq的權(quán)重。也就是每個(gè)gse根據(jù)其cfs_rq的權(quán)重比例來分配tg的權(quán)重。cfs_rq的權(quán)重等于其上掛載的任務(wù)的權(quán)重之和。假設(shè)tg的權(quán)重是1024，系統(tǒng)中只有2個(gè)CPU，因此有兩個(gè)gse, 若其grq上任務(wù)狀態(tài)如下如下圖3，則gse[0]分得的權(quán)重為 1024 * (1024+2048+3072)/(1024+2048+3072+1024+1024) = 768；gse[1]分得的權(quán)重為 1024 * (1024+1024)/(1024+2048+3072+1024+1024) = 256。
圖3:
gse的權(quán)重更新函數(shù)為 update_cfs_group()，下面看其具體實(shí)現(xiàn):
tg的權(quán)重向gse[X]的分配動(dòng)作是在 calc_group_shares() 中完成的。
公式(1)中使用到 \Sum grq->load.weight，也就是說一個(gè)gse權(quán)重的更新需要訪問各個(gè)CPU上的grq，鎖競爭代價(jià)比較高，因此進(jìn)行了一系列的近似計(jì)算。
首先進(jìn)行替換：
* ? grq->load.weight --> grq->avg.load_avg ? ? ? ? ? ? ? ? ? ? ? ? (2)
然后得到：
* ? ? ? ? ? ? ? ? ? ? tg->weight * grq->avg.load_avg
* ? ge->load.weight = ? ?---------------------------------------- ? ? ? ? ? ? (3)
* ? ? ? ? ? ? ? ? ? ? ? ? ? ? tg->load_avg
*
* Where: tg->load_avg ~= \Sum grq->avg.load_avg
由于cfs_rq->avg.load_avg = cfs_rq->avg.load_sum/divider。而 cfs_rq->avg.load_sum 等于 cfs_rq->load.weight 乘以非idle狀態(tài)下的幾何級(jí)數(shù)。這個(gè)近似是在tg的每個(gè)CPU上的grq的非idle狀態(tài)的時(shí)間級(jí)數(shù)是相同的前提下才嚴(yán)格相等的。也就是說tg的任務(wù)在各個(gè)CPU上的運(yùn)行狀態(tài)越一致，越接近這個(gè)近似值。
task group 空閑的情況下，啟動(dòng)一個(gè)任務(wù)。grq->avg.load_avg 需要時(shí)間來建立，在建立時(shí)間這種特殊情況下公式1簡化為：
* ? ? ? ? ? ? ? ? ? ? tg->weight * grq->load.weight
* ? ge->load.weight = ? ?--------------------------------------- ? = ? tg->weight ? (4)
* ? ? ? ? ? ? ? ? ? ? ? ? grp->load.weight
相當(dāng)于一個(gè)單核系統(tǒng)下的狀態(tài)了。為了讓公式(3)在這種特殊情況下更貼近與公式(4)，又做了一次近似，得到：
* ? ? ? ? ? ? ? ? ? ? ? ? ? ? tg->weight * grq->load.weight
* ? ge->load.weight = ? ? -------------------------------------------------------------------- ? ? ? ? (5)
* ? ? ? ? ? ? ? ? ? ? ?tg->load_avg - grq->avg.load_avg + grq->load.weight
但是因?yàn)間rq上沒有任務(wù)時(shí)，grq->load.weight 可以下降到 0，導(dǎo)致除以零，需要使用 grq->avg.load_avg作為它的下限，然后給出：
* ? ? ? ? ? ? ? ? ? ? tg->weight * grq->load.weight
* ? ge->load.weight = ? ?------------------------------------------ ? (6)
* ? ? ? ? ? ? ? ? ? ? ? ? ? ? tg_load_avg'
*
* 其中:
* ? tg_load_avg' = tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg)
max(grq->load.weight, grq->avg.load_avg) 一般都是取grq->load.weight，因?yàn)橹挥術(shù)rq上一直有任務(wù)running+runnable才會(huì)趨近于grq->load.weight。
calc_group_shares() 函數(shù)是通過公式(6)近似計(jì)算各個(gè)gse分得的權(quán)重：
由于tg中的每個(gè)任務(wù)都對(duì)gse的權(quán)重有貢獻(xiàn)，因此grq上任務(wù)個(gè)數(shù)變更時(shí)都要更新gse的權(quán)重，近似過程中使用到了se的負(fù)載，在entity_tick()中也進(jìn)行了一次更新。調(diào)用路徑：
5.2. gse上每個(gè)tse分到的權(quán)重
任務(wù)組中的任務(wù)也是按其權(quán)重比例分配gse的權(quán)重。如上圖2中g(shù)se[0]的grq上掛的3個(gè)任務(wù)，tse1分得的權(quán)重就是768*1024/(1024+2048+3072)=128, tse2分得的權(quán)重就是768*2048/(1024+2048+3072)=256, tse3分得的權(quán)重就是768*3072/(1024+2048+3072)=384。
在tg中的任務(wù)分配tg分得的時(shí)間片的時(shí)候，會(huì)使用到這個(gè)按比例分得的權(quán)重。分組嵌套的越深，能按比例分得的權(quán)重就越小，由此可見，在高負(fù)載時(shí)task group中的任務(wù)是不利于分配時(shí)間片的。
六、task group時(shí)間片
6.1. 時(shí)間片分配
若使能CFS組調(diào)度會(huì)從上到下逐層通過權(quán)重比例來分配上層分得的時(shí)間片，分配函數(shù)是sched_slice()。但是從上到下不便于遍歷，因此改為從下到上進(jìn)行遍歷，畢竟 A*B*C 和 C*B*A 是相等的。
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。
七、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)行多長時(shí)間就是多長時(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ì)在某些場景下出現(xiàn)前臺(tái)任務(wù)被后臺(tái)任務(wù)卡住的情況，對(duì)于普適性配置，最新的一些Android版本中將各個(gè)分組的 cpu.shares 都設(shè)置為1024以追求CPU資源在各組之間的公平。
九、參考
1.內(nèi)核源碼(https://www.kernel.org/)和Android源碼(https://source.android.com/docs/setup/download/downloading)
2.內(nèi)核文檔Documentation/admin-guide/cgroup-v1
3.CFS調(diào)度器（3）-組調(diào)度: http://www.wowotech.net/process_management/449.html
4.PELT算法淺析: http://www.wowotech.net/process_management/pelt.html
