Linux是一個(gè)通用操作系統(tǒng)的內(nèi)核，她的目標(biāo)是星辰大海，上到網(wǎng)絡(luò)服務(wù)器，下至嵌入式設(shè)備都能運(yùn)行良好。做一款好的linux進(jìn)程調(diào)度器是一項(xiàng)非常具有挑戰(zhàn)性的任務(wù)，因?yàn)樵O(shè)計(jì)約束太多了：

• 它必須是公平的

• 快速響應(yīng)

• 系統(tǒng)的throughput要高

• 功耗要小

3.8版本之前的內(nèi)核CFS調(diào)度器在計(jì)算CPU load的時(shí)候采用的是跟蹤每個(gè)運(yùn)行隊(duì)列上的負(fù)載（per-rq load tracking）。這種粗略的負(fù)載跟蹤算法顯然無法為調(diào)度算法提供足夠的支撐。為了完美的滿足上面的所有需求，Linux調(diào)度器在3.8版中引入了PELT（Per-entity load tracking）算法。本文將為您分析PELT的設(shè)計(jì)概念和具體的實(shí)現(xiàn)。

本文出現(xiàn)的內(nèi)核代碼來自Linux5.4.28，如果有興趣，讀者可以配合代碼閱讀本文。

一、為何需要per-entity load tracking？

完美的調(diào)度算法需要一個(gè)能夠預(yù)知未來的水晶球：只有當(dāng)內(nèi)核準(zhǔn)確地推測(cè)出每個(gè)進(jìn)程對(duì)系統(tǒng)的需求，它才能最佳地完成調(diào)度任務(wù)。進(jìn)程對(duì)CPU的需求包括兩個(gè)方面：

• 任務(wù)的利用率（task utility）

• 任務(wù)的負(fù)載（task load）

跟蹤任務(wù)的utility主要是為任務(wù)尋找合適算力的CPU。例如在手機(jī)平臺(tái)上4個(gè)大核+4個(gè)小核的結(jié)構(gòu)，一個(gè)任務(wù)本身邏輯復(fù)雜，需要有很長的執(zhí)行時(shí)間，那么隨著任務(wù)的運(yùn)行，內(nèi)核發(fā)現(xiàn)其utility越來越大，那么可以根據(jù)utility選擇提升其所在CPU的頻率，輸出更大的算力，或者將其遷移到算力更強(qiáng)的大核CPU上執(zhí)行。Task load主要用于負(fù)載均衡算法，即讓系統(tǒng)中的每一個(gè)CPU承擔(dān)和它的算力匹配的負(fù)載。

3.8版本之前的內(nèi)核CFS調(diào)度器在負(fù)載跟蹤算法上比較粗糙，采用的是跟蹤每個(gè)運(yùn)行隊(duì)列上的負(fù)載（per-rq load tracking）。它并沒有跟蹤每一個(gè)任務(wù)的負(fù)載和利用率，只是關(guān)注整體CPU的負(fù)載。對(duì)于per-rq的負(fù)載跟蹤方法，調(diào)度器可以了解到每個(gè)運(yùn)行隊(duì)列對(duì)整個(gè)系統(tǒng)負(fù)載的貢獻(xiàn)。這樣的統(tǒng)計(jì)信息可以幫助調(diào)度器平衡runqueue上的負(fù)載，但從整個(gè)系統(tǒng)的角度看，我們并不知道當(dāng)前CPU上的負(fù)載來自哪些任務(wù)，每個(gè)任務(wù)施加多少負(fù)載，當(dāng)前CPU的算力是否支撐runqueue上的所有任務(wù)，是否需要提頻或者遷核來解決當(dāng)前CPU上負(fù)載。因此，為了更好的進(jìn)行負(fù)載均衡和CPU算力調(diào)整，調(diào)度器需要PELT算法來指引方向。

二、PELT算法的基本方法

通過上一章，我們了解到PELT算法把負(fù)載跟蹤算法從per rq推進(jìn)到per-entity的層次，從而讓調(diào)度器有了做更精細(xì)控制的前提。這里per-entity中的“entity”指的是調(diào)度實(shí)體（scheduling entity），其實(shí)就是一個(gè)進(jìn)程或者control group中的一組進(jìn)程。為了做到Per-entity的負(fù)載跟蹤，時(shí)間被分成了1024us的序列，在每一個(gè)1024us的周期中，一個(gè)entity對(duì)系統(tǒng)負(fù)載的貢獻(xiàn)可以根據(jù)該實(shí)體處于runnable狀態(tài)（正在CPU上運(yùn)行或者等待cpu調(diào)度運(yùn)行）的時(shí)間進(jìn)行計(jì)算。任務(wù)在1024us的周期窗口內(nèi)的負(fù)載其實(shí)就是瞬時(shí)負(fù)載。如果在該周期內(nèi)，runnable的時(shí)間是t，那么該任務(wù)的瞬時(shí)負(fù)載應(yīng)該和（t/1024）有正比的關(guān)系。類似的概念，任務(wù)的瞬時(shí)利用率應(yīng)該通過1024us的周期窗口內(nèi)的執(zhí)行時(shí)間（不包括runqueue上的等待時(shí)間）比率來計(jì)算。

當(dāng)然，不同優(yōu)先級(jí)的任務(wù)對(duì)系統(tǒng)施加的負(fù)載也不同（畢竟在cfs調(diào)度算法中，高優(yōu)先級(jí)的任務(wù)在一個(gè)調(diào)度周期中會(huì)有更多的執(zhí)行時(shí)間），因此計(jì)算任務(wù)負(fù)載也需要考慮任務(wù)優(yōu)先級(jí)，這里引入一個(gè)負(fù)載權(quán)重（load weight）的概念。在PELT算法中，瞬時(shí)負(fù)載Li等于：

Li = load weight ?x （t/1024）

利用率和負(fù)載不一樣，它和任務(wù)優(yōu)先級(jí)無關(guān)，不過為了能夠和CPU算力進(jìn)行運(yùn)算，任務(wù)的瞬時(shí)利用率Ui使用下面的公式計(jì)算：

Ui = Max CPU capacity??x （t/1024）

在手機(jī)環(huán)境中，大核最高頻上的算力定義為最高算力，即1024。

任務(wù)的瞬時(shí)負(fù)載和瞬時(shí)利用率都是一個(gè)快速變化的計(jì)算量，但是它們并不適合直接調(diào)整調(diào)度算法，因?yàn)檎{(diào)度器期望的是一段時(shí)間內(nèi)保持平穩(wěn)而不是疲于奔命。例如，在遷移算法中，在上一個(gè)1024us窗口中，是滿窗運(yùn)行，瞬時(shí)利用率是1024，立刻將任務(wù)遷移到大核，下一個(gè)窗口，任務(wù)有3/4時(shí)間在阻塞狀態(tài)，利用率急速下降，調(diào)度器會(huì)將其遷移到小核上執(zhí)行。從這個(gè)例子可以看出，用瞬時(shí)量來推動(dòng)調(diào)度器的算法不適合，任務(wù)會(huì)不斷在大核小核之間跳來跳去，遷移的開銷會(huì)急劇加大。為此，我們需要對(duì)瞬時(shí)負(fù)載進(jìn)行滑動(dòng)平均的計(jì)算，得到平均負(fù)載。一個(gè)調(diào)度實(shí)體的平均負(fù)載可以表示為：

L = L0 + L1*y + L2*y2 + L3*y3 + ...

Li表示在周期pi中的瞬時(shí)負(fù)載，對(duì)于過去的負(fù)載我們?cè)谟?jì)算的時(shí)候需要乘一個(gè)衰減因子y。在目前的內(nèi)核代碼中，y是確定值：y ^32等于0.5。這樣選定的y值，一個(gè)調(diào)度實(shí)體的負(fù)荷貢獻(xiàn)經(jīng)過32個(gè)窗口（1024us）后，對(duì)當(dāng)前時(shí)間的的符合貢獻(xiàn)值會(huì)衰減一半。

通過上面的公式可以看出：

（1）調(diào)度實(shí)體對(duì)系統(tǒng)負(fù)荷的貢獻(xiàn)值是一個(gè)序列之和組成

（2）最近的負(fù)荷值擁有最大的權(quán)重

（3）過去的負(fù)荷也會(huì)被累計(jì)，但是是以遞減的方式來影響負(fù)載計(jì)算。

使用這樣序列的好處是計(jì)算簡單，我們不需要使用數(shù)組來記錄過去的負(fù)荷貢獻(xiàn)，只要把上次的總負(fù)荷的貢獻(xiàn)值乘以y再加上新的L0負(fù)荷值就OK了。利用率的計(jì)算也是類似的，不再贅述。

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

三、內(nèi)核調(diào)度器基本知識(shí)

為了能夠講清楚PELT算法，我們本章需要科普一點(diǎn)基本的CFS的基礎(chǔ)知識(shí)。

1、調(diào)度實(shí)體

內(nèi)核用struct sched_entity抽象一個(gè)調(diào)度實(shí)體結(jié)構(gòu)：

所有的成員都很直觀，除了runnable_weight。Task se的load weight和runnable weight是相等的，但是對(duì)于group se這兩個(gè)值是不同的，具體有什么區(qū)別這個(gè)我們后文會(huì)詳述。

2、Cfs任務(wù)的運(yùn)行隊(duì)列

內(nèi)核用struct cfs_rq抽象一個(gè)管理調(diào)度實(shí)體的cfs任務(wù)運(yùn)行隊(duì)列：

Cfs rq有一個(gè)成員load保存了掛入該runqueue的調(diào)度實(shí)體load weight之和。為何要匯總這個(gè)load weight值？主要有兩個(gè)運(yùn)算需要，一個(gè)是在計(jì)算具體調(diào)度實(shí)體需要分配的時(shí)間片的時(shí)候：

Se Time slice = sched period ?x ?se load weight / cfs rq load weight

此外，在計(jì)算cfs rq的負(fù)載的時(shí)候，我們也需要load weight之和，下面會(huì)詳細(xì)描述。

在負(fù)載均衡的時(shí)候，我們需要根據(jù)各個(gè)root cfs rq上的負(fù)載進(jìn)行均衡，然而各個(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（因?yàn)閠ask se的load weight是其level上的load weight，并不能體現(xiàn)到root cfs rq上）。所以，我們?cè)诟鱾€(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 ?group se 在上一層cfs負(fù)載中的占比

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

Task se的h_load = task se的load avg ?x ?cfs rq的h_load / cfs rq的load avg

3、任務(wù)組（task group）

內(nèi)核用struct task_group來抽象屬于同一個(gè)control group的一組任務(wù)（需要內(nèi)核支持組調(diào)度，具體細(xì)節(jié)可參考其他文章）：

在上面的task group成員中，load_avg稍顯突兀。雖然task group作為一個(gè)調(diào)度實(shí)體來競(jìng)爭CPU資源，但是task group是一組task se或者group se（task group可以嵌套）的集合，不可能在一個(gè)CPU上進(jìn)行調(diào)度，因此task group的調(diào)度實(shí)際上在各個(gè)CPU上都會(huì)發(fā)生，因此其load weight（即share成員）需要按照一定的算法分配給各個(gè)CPU上的group se，因此這里需要跟蹤整個(gè)task group的load avg以及該task group在各個(gè)CPU上的load avg。

4、基本組件

和調(diào)度器相關(guān)的基本組件如下：

這是當(dāng)系統(tǒng)不支持組調(diào)度時(shí)候的形態(tài)，每個(gè)任務(wù)都內(nèi)嵌一個(gè)sched_entity，我們稱之task se，每個(gè)CPU runqueue上都內(nèi)嵌調(diào)度類自己的runqueue，對(duì)于cfs調(diào)度類而言就是cfs rq。Cfs rq有一個(gè)紅黑樹，每個(gè)處于runnable狀態(tài)的任務(wù)（se）都是按照vruntime的值掛入其所屬的cfs rq。當(dāng)進(jìn)入阻塞狀態(tài)的時(shí)候，任務(wù)會(huì)被掛入wait queue，但是從PELT的角度來看，該任務(wù)仍然掛在cfs rq上，該task se的負(fù)載（blocked load）仍然會(huì)累計(jì)到cfs rq的負(fù)載（如上圖虛線所示），不過既然該task se進(jìn)入阻塞狀態(tài)，那么就會(huì)按照PELT算法的規(guī)則衰減，計(jì)入其上次掛入的cfs rq。

5、構(gòu)建大廈

當(dāng)系統(tǒng)支持組調(diào)度的時(shí)候，cfs rq---se這個(gè)基本組件會(huì)形成層級(jí)結(jié)構(gòu)，如下圖所示：

一組任務(wù)（task group）作為一個(gè)整體進(jìn)行調(diào)度的時(shí)候，那么它也就是一個(gè)sched entity了，也就是說task group對(duì)應(yīng)一個(gè)se。這句話對(duì)UP是成立的，然而，在SMP的情況下，系統(tǒng)有多個(gè)CPU，任務(wù)組中的任務(wù)可能遍布到各個(gè)CPU上去，因此實(shí)際上，task group對(duì)應(yīng)的是一組se，我們稱之group se。由于task group中可能包含一個(gè)task group，因此task group也是形成層級(jí)關(guān)系，頂層是一個(gè)虛擬的root task group，該task group沒有對(duì)應(yīng)的group se（都頂層了，不需要掛入其他cfs rq），因而其對(duì)應(yīng)的cfs rq內(nèi)嵌在cpu runqueue中。

Group se需要管理若干個(gè)sched se（可能是task se，也可能是其下的group se），因此group se需要一個(gè)對(duì)應(yīng)的cfs rq。對(duì)于一個(gè)group se，它有兩個(gè)關(guān)聯(lián)的cfs rq，一個(gè)是該group se所掛入的cfs rq：

另外一個(gè)是該group se所屬的cfs rq：

四、關(guān)于負(fù)載權(quán)重（load weight）和負(fù)載

1、load weight

PELT算法中定義了一個(gè)struct load_weight的數(shù)據(jù)結(jié)構(gòu)來表示調(diào)度實(shí)體的負(fù)載權(quán)重：

這個(gè)數(shù)據(jù)結(jié)構(gòu)中的weight成員就是負(fù)載權(quán)重值。inv_weight沒有實(shí)際的意義，主要是為了快速運(yùn)算的。struct load_weight可以嵌入到se或者cfs rq中，分別表示se/cfs rq的權(quán)重負(fù)載。Cfs rq的load weight等于掛入隊(duì)列所有se的load weight之和。有了這些信息，我們可以快速計(jì)算出一個(gè)se的時(shí)間片信息（這個(gè)公式非常重要，讓我們?cè)僦貜?fù)一次）：

Sched slice=sched period x se的權(quán)重/cfs rq的權(quán)重

CFS調(diào)度算法的核心就是在target latency（sched period）時(shí)間內(nèi)，保證CPU資源是按照se的權(quán)重來分配的。映射到virtual runtime的世界中，cfs rq上的所有se是完全公平的。

2、平均負(fù)載

內(nèi)核用struct sched_avg來抽象一個(gè)se或者cfs rq的平均負(fù)載：

說是平均負(fù)載，但是實(shí)際上這個(gè)數(shù)據(jù)結(jié)構(gòu)包括了負(fù)載和利用率信息，主要是*_avg成員，其他的成員是中間計(jì)算變量。

3、如何確定se的load weight？

對(duì)于task se而言，load weight是明確的，該值是和se的nice value有對(duì)應(yīng)關(guān)系，但是對(duì)于group se，load weight怎么設(shè)定？這是和task group相關(guān)的，當(dāng)用戶空間創(chuàng)建任務(wù)組的時(shí)候，在其目錄下有一個(gè)share屬性文件，用戶空間通過該值可以配置該task group在分享CPU資源時(shí)候的權(quán)重值。根據(jù)上面的描述，我們知道一個(gè)task group對(duì)應(yīng)的group se是若干個(gè)（CPU個(gè)數(shù)），那么這個(gè)share值應(yīng)該是分配到各個(gè)group se中去，即task group se的load weight之和應(yīng)該等于share值。平均分配肯定不合適，task group對(duì)應(yīng)的各個(gè)cfs rq所掛入的具體任務(wù)情況各不相同，具體怎么分配？直覺上來說應(yīng)該和其所屬cfs rq掛入的調(diào)度實(shí)體權(quán)重相關(guān)，calc_group_shares給出了具體的計(jì)算方法，其基本的思想是：

這里的grq就是任務(wù)組的group cfs rq，通過求和運(yùn)算可以得到該任務(wù)組所有cfs rq的權(quán)重之和。而一個(gè)group se的權(quán)重應(yīng)該是按照其所屬group cfs rq的權(quán)重在該任務(wù)組cfs rq權(quán)重和的占比有關(guān)。當(dāng)然，由于運(yùn)算量大，實(shí)際代碼中做了一些變換，把load weight變成了load avg，具體就不描述了，大家可以自行閱讀。

4、Se和cfs rq的平均負(fù)載

根據(jù)上文的計(jì)算公式，Task se的平均負(fù)載和利用率計(jì)算是非常直觀的：有了load weight，有了明確的任務(wù)狀態(tài)信息，計(jì)算幾何級(jí)數(shù)即可。然而，對(duì)于group se而言，任務(wù)狀態(tài)不是那么直觀，它是這么定義的：只要其下層層級(jí)結(jié)構(gòu)中有一個(gè)處于running狀態(tài)，那么該group se就是running狀態(tài)（cfs rq->curr == se）。只要其下層層級(jí)結(jié)構(gòu)中有一個(gè)處于runnable狀態(tài)，那么該group se就是runnable狀態(tài)（se->on_rq表示該狀態(tài)）。定義清楚group se狀態(tài)之后，group se的load avg計(jì)算和task se是一毛一樣的。

下面我們看看cfs runqueue的負(fù)載計(jì)算：

CFS runqueue也內(nèi)嵌一個(gè)load avg數(shù)據(jù)結(jié)構(gòu)，用來表示cfs rq的負(fù)載信息。CFS runqueue定義為其下sched entity的負(fù)載之和。這里的負(fù)載有兩部分，一部分是blocked load，另外一部分是runnable load。我們用一個(gè)簡單的例子來描述：Cfs rq上掛著B和C兩個(gè)se，還有一個(gè)se A進(jìn)入阻塞狀態(tài)。當(dāng)在se B的tick中更新cfs rq負(fù)載的時(shí)候，這時(shí)候需要重新計(jì)算A B C三個(gè)se的負(fù)載，然后求和就可以得到cfs rq的負(fù)載。當(dāng)然，這樣的算法很丑陋，當(dāng)cfs rq下面有太多的sched se的時(shí)候，更新cfs rq的計(jì)算量將非常的大。內(nèi)核采用的算法比較簡單，首先衰減上一次cfs rq的load（A B C三個(gè)se的負(fù)載同時(shí)衰減），然后累加新的A和B的負(fù)載。因?yàn)閏fs rq的load weight等于A的load weight加上B的load weight，所以cfs rq的load avg計(jì)算和sched entity的load avg計(jì)算的基本邏輯是一樣的。具體可以參考__update_load_avg_se（更新se負(fù)載）和__update_load_avg_cfs_rq（更新cfs rq負(fù)載）的代碼實(shí)現(xiàn)。

5、Runnable weight和Runnable load

struct sched_avg數(shù)據(jù)結(jié)構(gòu)中有負(fù)載（load_sum/load_avg）和運(yùn)行負(fù)載（runnable_load_sum/runnable_load_avg），這兩個(gè)有什么不同呢？在回答這個(gè)問題之前，我們先思考這樣的問題：一個(gè)任務(wù)進(jìn)入阻塞態(tài)后，它是否還對(duì)CPU的負(fù)載施加影響？從前文的PELT算法來看，即便任務(wù)從cpu runqueue摘下，但是該任務(wù)的負(fù)載依然存在，還是按照PELT規(guī)則進(jìn)行衰減，并計(jì)算入它阻塞前所在的CPU runqueue中（這種負(fù)載稱為blocked load）。因此，load_sum/load_avg在計(jì)算的時(shí)候是包括了這些blocked load。負(fù)載均衡的時(shí)候，我們需要在各個(gè)CPU runqueue之間均衡負(fù)載（runnable load），如果不支持組調(diào)度，那么其實(shí)也OK，因?yàn)槲覀兺ㄟ^se->on_rq知道其狀態(tài)，通過累計(jì)CPU上所有se->on_rq==1的se負(fù)載可以了解各個(gè)CPU上的runnable load并進(jìn)行均衡。然而，當(dāng)系統(tǒng)支持cgroup的時(shí)候，上述算法失效了，對(duì)于一個(gè)group se而言，只要其下有一個(gè)se是處于runnable，那么group se->on_rq==1。這樣，在負(fù)載均衡的時(shí)候，cpu runqueue的負(fù)載重計(jì)入了太多的blocked load，從而無法有效的執(zhí)行負(fù)載均衡。

為了解決這個(gè)問題，我們引入了runnable weight的概念，對(duì)于task se而言，runnable weight等于load weight，對(duì)于group se而言，runnable weight不等于load weight，而是通過下面的公式計(jì)算：

通過這樣的方法，在group se內(nèi)嵌的load avg中，我們實(shí)際上可以得到兩個(gè)負(fù)載，一個(gè)是全負(fù)載（包括blocked load），另外一個(gè)是runnable load。

五、如何計(jì)算/更新load avg？

1、概述

內(nèi)核構(gòu)建了負(fù)載的PELT層級(jí)結(jié)構(gòu)之后，還需要日常性的維護(hù)這個(gè)PELT大廈上各個(gè)cfs rq和se節(jié)點(diǎn)上的load avg，以便讓任務(wù)負(fù)載、CPU負(fù)載能夠及時(shí)更新。update_load_avg函數(shù)用來更新CFS任務(wù)及其cfs rq的負(fù)載。具體的更新的時(shí)間點(diǎn)總是和調(diào)度事件相關(guān)，例如一個(gè)任務(wù)阻塞的時(shí)候，把之前處于running狀態(tài)的時(shí)間增加的負(fù)載更新到系統(tǒng)中。而在任務(wù)被喚醒的時(shí)候，需要根據(jù)其睡眠時(shí)間，對(duì)其負(fù)載進(jìn)行衰減。具體調(diào)用update_load_avg函數(shù)的時(shí)機(jī)包括：

在本章的后續(xù)小節(jié)中，我們選取幾個(gè)典型的場(chǎng)景具體分析負(fù)載更新的細(xì)節(jié)。

2、一個(gè)新建sched entity如何初始化load avg？

Load avg的初始化分成兩個(gè)階段，第一個(gè)階段在創(chuàng)建sched entity的時(shí)候（對(duì)于task se而言就是在fork的時(shí)候，對(duì)于group se而言，發(fā)生在創(chuàng)建cgroup的時(shí)候），調(diào)用init_entity_runnable_average函數(shù)完成初始化，第二個(gè)階段在喚醒這個(gè)新創(chuàng)建se的時(shí)候，可以參考post_init_entity_util_avg函數(shù)的實(shí)現(xiàn)。Group se不可能被喚醒，因此第二階段的se初始化僅僅適用于task se。

在第一階段初始化的時(shí)候，sched_avg對(duì)象的各個(gè)成員初始化為0是常規(guī)操作，不過task se的load avg（以及runnable load avg）初始化為最大負(fù)載值，即初始化為se的load weight。隨著任務(wù)的運(yùn)行，其load avg會(huì)慢慢逼近其真實(shí)的負(fù)載情況。對(duì)于group se而言，其load avg等于0，表示沒有任何se附著在該group se上。

一個(gè)新建任務(wù)的util avg設(shè)置為0是不合適的，其設(shè)定值應(yīng)該和該task se掛入的cfs隊(duì)列的負(fù)載狀況以及CPU算力相關(guān)，但是在創(chuàng)建task se的時(shí)候，我們根本不知道它會(huì)掛入哪一個(gè)cfs rq，因此在喚醒一個(gè)新創(chuàng)建的任務(wù)的時(shí)候，我們會(huì)進(jìn)行第二階段的初始化。具體新建任務(wù)的util avg的初始化公式如下：

完成了新建task se的負(fù)載和利用率的初始化之后，我們還會(huì)調(diào)用attach_entity_cfs_rq函數(shù)把這個(gè)task se掛入cfs---se的層級(jí)結(jié)構(gòu)。雖然這里僅僅是給PELT大廈增加一個(gè)task se節(jié)點(diǎn)，但是整個(gè)PELT hierarchy都需要感知到這個(gè)新增的se帶來的負(fù)載和利用率的變化。因此，除了把該task se的load avg加到cfs的load avg中，還需要把這個(gè)新增的負(fù)載沿著cfs---se的層級(jí)結(jié)構(gòu)向上傳播。類似的，這個(gè)新增負(fù)載也需要加入到task group中。

3、負(fù)載/利用率的傳播

當(dāng)一個(gè)新的task se加入cfs---se的層級(jí)結(jié)構(gòu)（也稱為PELT hierarchy）的時(shí)候，task se的負(fù)載（也包括util，后續(xù)用負(fù)載指代load和utility）會(huì)累計(jì)到各個(gè)level的group se，直到頂層的cfs rq。此外，當(dāng)任務(wù)從一個(gè)CPU遷移到另外的CPU上或者任務(wù)從一個(gè)cgroup移動(dòng)到另外的cgroup的時(shí)候，PELT hierarchy發(fā)生變化，都會(huì)引起負(fù)載的傳播過程。我們下面用新建se加入PELT hierarchy來描述具體的負(fù)載傳播細(xì)節(jié)：

attach_entity_cfs_rq的執(zhí)行過程如下：

（1）確定task se的負(fù)載，如果需要的話可以執(zhí)行更新動(dòng)作。后續(xù)需要把這個(gè)新增se負(fù)載在整個(gè)PELT層級(jí)結(jié)構(gòu)中向上傳播。

（2）找到該task se所掛入的cfs rq，把task se的負(fù)載更新到cfs rq。記錄需要向上傳播的負(fù)載（add_tg_cfs_propagate）

（3）把task se的負(fù)載更新到其所屬的task group（update_tg_load_avg）

（4）至此底層level的負(fù)載更新完成，現(xiàn)在要進(jìn)入上一層進(jìn)行負(fù)載更新。首先要更新group se的負(fù)載

（5）更新group se的負(fù)載，同時(shí)記錄要向上傳播的負(fù)載，即把level 0 cfs rq的prop_runnable_sum傳遞到level 1 cfs rq的prop_runnable_sum。

（6）由于task se的加入，level 0的cfs rq的負(fù)載和level 1的group se的負(fù)載也已經(jīng)有了偏差，這里需要更新。通過update_tg_cfs_util函數(shù)讓group se的utility和其所屬的group cfs rq保持同步。通過update_tg_cfs_runnable函數(shù)讓group se的負(fù)載和其所屬的group cfs rq保持同步。

（7）更新level 1 task group的負(fù)載。然后不斷重復(fù)上面的過程，直到頂層cfs rq。

4、在tick中更新load avg

主要的代碼路徑在entity_tick函數(shù)中：

在tick中更新loadavg是一個(gè)層次遞進(jìn)的過程，從頁節(jié)點(diǎn)的task se開始向上，直到root cfs rq，每次都調(diào)用entity_tick來更新該層級(jí)的se以及cfs rq的load avg，這是通過函數(shù)update_load_avg完成的。更新完load avg之后，由于group cfs rq的狀態(tài)發(fā)生變化，需要重新計(jì)算group se的load weight（以及runnable weight），這是通過update_cfs_group函數(shù)完成的。

update_load_avg的主要執(zhí)行過程如下：

（1）更新本層級(jí)sched entity的load avg（__update_load_avg_se）

（2）更新該se掛入的cfs rq的load avg（update_cfs_rq_load_avg）

（3）如果是group se，并且cfs---se層級(jí)結(jié)構(gòu)有了調(diào)度實(shí)體的變化，那么需要處理向上傳播的負(fù)載。在tick場(chǎng)景中，不需要這個(gè)傳播過程。

（4）更新該層級(jí)task group的負(fù)載（update_tg_load_avg）。之所以計(jì)算task group的load avg，這個(gè)值后續(xù)會(huì)參與計(jì)算group se的load weight。

update_cfs_group的主要執(zhí)行過程如下：

（1）找到該group se所屬的cfs rq

（2）調(diào)用calc_group_shares計(jì)算該group se的load weight

（3）調(diào)用calc_group_runnable計(jì)算該group se的runnable weight

（4）調(diào)用reweight_entity重新設(shè)定該group se的load weight和runnable weight，并根據(jù)這些新的weight值更新group se所掛入的cfs rq。

5、在任務(wù)喚醒時(shí)更新load avg

和tick一樣，任務(wù)喚醒過程中更新load avg也是一個(gè)層次遞進(jìn)的過程，從頁節(jié)點(diǎn)的task se開始向上，直到root cfs rq。不過在遍歷中間節(jié)點(diǎn)（group se）的時(shí)候要判斷當(dāng)前的group se是否在runqueue上，如果沒有那么就調(diào)用enqueue_entity，否則不需要調(diào)用。具體代碼在enqueue_task_fair函數(shù)中：

（1）如果se->on_rq等于0，那么調(diào)用enqueue_entity進(jìn)行負(fù)載更新

（2）如果se->on_rq等于1，那么表示表示該group的子節(jié)點(diǎn)至少有一個(gè)runnable或者running狀態(tài)的se，這時(shí)候不需要entity入隊(duì)操作，直接調(diào)用update_load_avg和update_cfs_group完成負(fù)載更新（過程和tick中一致）

在enqueue_entity函數(shù)中，相關(guān)負(fù)載更新代碼如下：

和tick對(duì)比，這個(gè)場(chǎng)景下的update_load_avg多傳遞了一個(gè)DO_ATTACH的flag，當(dāng)一個(gè)任務(wù)被喚醒的時(shí)候發(fā)生了遷移，那么PELT層級(jí)結(jié)構(gòu)發(fā)生了變化，這時(shí)候需要負(fù)載的傳播過程。enqueue_runnable_load_avg函數(shù)用來更新cfs rq的runnable load weight和runnable load。account_entity_enqueue函數(shù)會(huì)更新cfs rq的load weight。

6、任務(wù)睡眠時(shí)更新load avg

這個(gè)場(chǎng)景涉及的主要函數(shù)是dequeue_task_fair，是enqueue_task_fair的逆過程，這里我們主要看dequeue_entity函數(shù)中和負(fù)載相關(guān)的代碼：

（1）更新本level的se及其掛入cfs rq的負(fù)載

（2）將該se的runnable load weight以及runnable load avg從cfs rq中減去。這里僅僅是減去了runnable load avg，并沒有把load avg從cfs rq中減去，這說明雖然任務(wù)阻塞了，但是仍然會(huì)對(duì)cfs rq的load avg有貢獻(xiàn)，只是隨著睡眠時(shí)間不斷衰減。

（3）將該se的load weight從cfs rq的load weight中減去

（4）更新group se的load weight以及runnable weight

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