一、前言

我們描述CFS任務(wù)負(fù)載均衡的系列文章一共三篇，第一篇是框架部分，第二篇描述了taskplacement的邏輯過程，第三篇是負(fù)載均衡的情景分析，包括tick balance、nohz idle balance和new idle balance。之前已經(jīng)有OPPO的小伙伴關(guān)于task placement做了講解，為了更精細(xì)的講解代碼邏輯，我們這次增加了代碼分析部分。本文作為第二篇任務(wù)放置的附篇，深入講解task placement的代碼流程。本文出現(xiàn)的內(nèi)核代碼來自Linux5.10.61，為了減少篇幅，我們對(duì)引用的代碼進(jìn)行了刪減（例如去掉了NUMA的代碼，畢竟手機(jī)平臺(tái)上我們暫時(shí)不關(guān)注這個(gè)特性），如果有興趣，讀者可以配合完整的源代碼代碼閱讀本文。

二、能量模型框架及其相關(guān)數(shù)據(jù)結(jié)構(gòu)


1. 概述
在嵌入式平臺(tái)上，為了控制功耗，很多硬件模塊被設(shè)計(jì)成可以運(yùn)行在多種頻率下工作（配合對(duì)應(yīng)的電壓，形成不同的performance level），這種硬件的驅(qū)動(dòng)模塊可以感知到在不同performancelevel下的能耗。系統(tǒng)中的某些模塊可能會(huì)希望能感知到硬件能耗從而做出不同的判決。能量模型框架（EnergyModel (EM) framework）是一個(gè)通用的接口模塊，該接口連接了支持不同perf level的驅(qū)動(dòng)模塊和系統(tǒng)中的其他想要感知能量消耗的模塊。
一個(gè)典型的例子就是CPU調(diào)度器和CPU驅(qū)動(dòng)模塊，調(diào)度器希望能夠感知底層CPU能量的消耗，從而做出更優(yōu)的選核策略。對(duì)于CPU設(shè)備，各個(gè)cluster有各自獨(dú)立的調(diào)頻機(jī)制，cluster內(nèi)的CPU統(tǒng)一工作在一個(gè)頻率下。因此每個(gè)cluster就會(huì)形成一個(gè)性能域（performance domain）。調(diào)度器通過EM framework接口可以獲取CPU在各個(gè)performance level的能量消耗。在了解了能量模型的基本概念之后，我們一起來看看和調(diào)度器相關(guān)的EM數(shù)據(jù)結(jié)構(gòu)。

2. struct root_domain
最初引入root domain的概念是因?yàn)閞t調(diào)度的問題。對(duì)于cfs task，我們只要保證每一個(gè)cpu runqueue上的公平就OK了（load balancer也會(huì)盡量cpu之間的公平），不需要嚴(yán)格保證全局公平。但是對(duì)于rt task就不行了，我們必須保證從全局范圍看，優(yōu)先級(jí)最高的任務(wù)最優(yōu)先得到調(diào)度。然而這樣會(huì)引入擴(kuò)展性問題：隨著cpu core數(shù)據(jù)增大，維持全局的rt調(diào)度策略有些困難，這樣的情況下，我們把CPU分成一個(gè)個(gè)的區(qū)域，每一個(gè)區(qū)域?qū)?yīng)一個(gè)root domain。對(duì)于rt調(diào)度，我們不需要維持全局，只要保證一個(gè)root domain中，最高優(yōu)先級(jí)的rt任務(wù)最優(yōu)先得到調(diào)度即可。
當(dāng)然，后來更多的成員增加到這個(gè)數(shù)據(jù)結(jié)構(gòu)中（例如本文要描述的performancedomain），豐富了它的含義。在手機(jī)平臺(tái)上，我們只有一個(gè)root domain，有點(diǎn)類似整個(gè)系統(tǒng)的味道了。本文只描述和負(fù)載均衡相關(guān)的成員，具體如下：

這里需要澄清一下overload和overutilized這兩個(gè)概念，對(duì)于一個(gè)CPU而言，其處于overload狀態(tài)則說明其runqueue上有大于等于2個(gè)任務(wù)，或者雖然只有一個(gè)任務(wù)，但是是misfit task。對(duì)于一個(gè)CPU而言，其處于overutilized狀態(tài)說明：該cpu的utility超過其capacity（缺省預(yù)留20%的算力，另外，這里的capacity是用于cfs任務(wù)的算力）。在單個(gè)cpu overload/overutilized基礎(chǔ)上，我們定義root domain（即整個(gè)系統(tǒng)）的overload和overutilized。對(duì)于root domain，overload表示至少有一個(gè)cpu處于overload狀態(tài)。overutilized表示至少有一個(gè)cpu處于overutilized狀態(tài)。overutilized狀態(tài)非常重要，它決定了調(diào)度器是否啟用EAS，只有在系統(tǒng)沒有overutilized的情況下，EAS才會(huì)生效。Overload和newidlebalance的頻次控制相關(guān)，當(dāng)系統(tǒng)在overload的情況下，newidle balance才會(huì)啟動(dòng)進(jìn)行均衡。
在CPU拓?fù)涑跏蓟臅r(shí)候，通過build_perf_domains函數(shù)創(chuàng)建各個(gè)perf domain，形成root domain的perf domain鏈表。

3. struct perf_domain
Struct perf_comain表示一個(gè)CPU性能域，perf_comain和cpufreq policy是一一對(duì)應(yīng)的，對(duì)于一個(gè)4+3+1結(jié)構(gòu)的平臺(tái)，每一個(gè)性能域都是由perf_domain抽象，因此系統(tǒng)共計(jì)3個(gè)perf domain，形成鏈表，鏈表頭在root domain。Perf_domain的各個(gè)成員如下：

4. struct em_perf_domain
在EM framework中，我們使用em_perf_domain來抽象一個(gè)performance domain：

5. struct em_perf_state
每個(gè)性能域都有若干個(gè)perf level，每一個(gè)perf level對(duì)應(yīng)能耗是不同的，我們用struct em_perf_state來表示一個(gè)perf level下的能耗信息：

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

三、能量計(jì)算概述

我們都知道一個(gè)基本的能量計(jì)算公式，如下：

對(duì)于CPU而言，我們要計(jì)算其能量需要進(jìn)一步細(xì)化公式（省略了CPU處于idle狀態(tài)的能耗）：

在內(nèi)核中，EM中記錄了CPU各個(gè)頻點(diǎn)的功率，而運(yùn)行時(shí)間是通過cpu utility來呈現(xiàn)的。有一個(gè)不太方便的地方就是CPU utility是歸一化到1024的一個(gè)值，失去了在某個(gè)頻點(diǎn)的運(yùn)行時(shí)間長(zhǎng)度的信息，不過沒有關(guān)系，我們可以轉(zhuǎn)換：CPU在該頻點(diǎn)運(yùn)行時(shí)間 =? cpu utility / cpu currentcapacityCPU在某個(gè)perf state的算力如下：

不考慮idle state的功耗，Cpu在某個(gè)perfstate的能量估計(jì)如下：

把公式（1）帶入公式（2）可以得到：

上面公式的第一項(xiàng)是一個(gè)常量，保存在em_perf_state的cost成員中。由于每個(gè)perf domain中的微架構(gòu)都是一樣的，因此scale_cpu是一樣的，那么cost也是一樣的，通過提取公因式我們可以得到整個(gè)perf domain的能耗公式：

四、Task placement概述

1. 喚醒場(chǎng)景的Task placement
一個(gè)線程進(jìn)入阻塞狀態(tài)后，異步事件或者其他線程會(huì)調(diào)用try_to_wake_up函數(shù)喚醒該線程，這時(shí)候會(huì)引發(fā)一次喚醒場(chǎng)景的taskplacement，在手機(jī)平臺(tái)上任務(wù)放置大概的選核思路如下：（1）如果使能了EAS，那么優(yōu)先采用EAS選核。當(dāng)然，只有在輕載（系統(tǒng)沒有overutilized）才會(huì)啟用EAS，重載下（只要有一個(gè)cpu處于over utilized狀態(tài)）還是使用傳統(tǒng)內(nèi)核算法
（2）Wake affine場(chǎng)景下的Non-EAS選核。所謂Wake affine就是選擇靠近waker所在的cpu（具體靠近的含義是waker所在CPU的LLC domain范圍），當(dāng)然也有可能靠近prev cpu？在this cpu和prev cpu中選定一個(gè)目標(biāo)CPU之后，走快速路徑，在目標(biāo)cpu的LLCdomain選擇一個(gè)空閑的CPU。
（3）Non-wake affine場(chǎng)景下的Non-EAS選核。走快速路徑，在prev cpu的LLC domain選擇一個(gè)空閑的CPU。
一般而言Non-wake affine場(chǎng)景下的Non-EAS選核是要走慢速路徑的，但是在手機(jī)平臺(tái)，所有的各個(gè)level的sched domain都沒有設(shè)定SD_BALANCE_WAKE的標(biāo)記，因此我們無法確定wakeup均衡的范圍，因此走快速路徑。

2. Fork和exec場(chǎng)景的Taskplacement
對(duì)fork后新任務(wù)的喚醒，內(nèi)核不是用try_to_wake_up來處理，而是用了wake_up_new_task。這個(gè)函數(shù)會(huì)調(diào)用fork類型的選核函數(shù)完成任務(wù)放置。當(dāng)新任務(wù)調(diào)用exec類函數(shù)開啟自己新的旅程之后，內(nèi)核會(huì)調(diào)用sched_exec啟動(dòng)一次exec類型的placement。這兩種類型的placement選核思路類似：（1）對(duì)于fork場(chǎng)景，找到最高level且支持SD_BALANCE_FORK的sched domain（即找到fork均衡的范圍），走慢速路徑來進(jìn)行選核（2）對(duì)于exec場(chǎng)景，找到最高level且支持SD_BALANCE_EXEC的sched domain（即找到exec均衡的范圍），走慢速路徑來進(jìn)行選核

五、select_task_rq_fair函數(shù)代碼分析

無論哪種類型的task placement，最終都是調(diào)用select_task_rq_fair函數(shù)完成邏輯，只是傳遞參數(shù)不同。該函數(shù)的邏輯分成三個(gè)段落：第一段是EAS的bypass路徑，第二段是選擇scheddomain的邏輯（快速路徑的的sched domain不需要選擇，固定為為L(zhǎng)LC domain），第三段是CPU的選擇。我們先看第一段邏輯，它是喚醒類型的EAS處理，如下：

A、對(duì)喚醒路徑（通過try_to_wake_up進(jìn)入該函數(shù)）進(jìn)行特別的處理，主要包括兩部分內(nèi)容，一是對(duì)wake affine的處理（B和E），另外一個(gè)是EAS的選核。由此可見，EAS只用于wakeup，fork和exec均衡固定走傳統(tǒng)選核算法。
B、更新current task（waker）的wakee信息，關(guān)于wake affine后面會(huì)詳細(xì)描述。
C、find_energy_efficient_cpu是EAS的主選核路徑，使用EAS選核需要滿足兩個(gè)條件：?jiǎn)拘崖窂角襡nable了energy aware scheduler特性。具體EAS的選核邏輯后面會(huì)詳細(xì)描述
D、EAS選中了適合的CPU就直接返回。如果EAS選核不成功，那么恢復(fù)缺省cpu為prev cpu，走傳統(tǒng)選核路徑。
E、判斷本次喚醒是否想要wake affine（即wakee task靠近waker所在的cpu）。第二段尋找sched domain的代碼如下：

A、從當(dāng)前cpu（waker所在的cpu）所在的base sched domain，自下而上，尋找合適的sched domain，從而確定任務(wù)放置的范圍。
B、對(duì)于wake affine場(chǎng)景，我們需要找到一個(gè)符合要求的sched domain，它必須要滿足：（1）該sched domain支持wake affine，（2）該sched domain包括了prevcpu和當(dāng)前cpu。找到這樣的sched domain之后，我們需要調(diào)用wake_affine快速的在當(dāng)前cpu和prev cpu中選中其一，作為后續(xù)選核快速路徑的輸入（sd==NULL確保走快速路徑）。
C、目前手機(jī)平臺(tái)上，DIE domain和MC domain都沒有設(shè)定SD_BALANCE_WAKE，因此在喚醒場(chǎng)景，我們無法找到sched domain，從而走入快速路徑。對(duì)于SD_BALANCE_FORK和SD_BALANCE_EXEC場(chǎng)景，DIE domain和MC domain都設(shè)置了對(duì)應(yīng)的flag，因此遍歷搜索到了DIE domain，后續(xù)會(huì)走入慢速路徑。
如果不需要EAS選核，或者EAS沒有選擇到合適的CPU，那么就需要走快速或者慢速路徑的選核了，具體走那條路主要是第二段代碼邏輯中是否找到了適合的sched domain。第三段代碼邏輯如下：

A、慢速選核路徑，需要在選定的sched domain中尋找最空閑的group，然后在最空閑的group中選擇最空閑的cpu。然后繼續(xù)在下層sched domain重復(fù)上面的過程，最終選擇一個(gè)空閑CPU并把任務(wù)p放置在這個(gè)最空閑的CPU上。
B、快速選核路徑，主要是在LLC domain中選擇距離new_cpu比較近的空閑CPU。對(duì)于wakeaffine，這里的new_cpu就是wake_affine選定的target cpu，對(duì)于其他場(chǎng)景new_cpu就是prev cpu。

六、EAS選核

find_energy_efficient_cpu函數(shù)用來為被喚醒的任務(wù)找到一個(gè)能效比最高的目標(biāo)CPU。主要搜索的步驟如下：1、在每一個(gè)cluster（performancedomain）中找到空閑算力最多的cpu作為備選2、從備選cpu中通過能量模型找到消耗能量最小的cpu。
這個(gè)算法思路也比較簡(jiǎn)單，在一個(gè)cluster中，選擇一個(gè)空閑算力最大cpu放置任務(wù)會(huì)讓schedutil governor請(qǐng)求較低的CPU頻率，從而消耗較低的能量。在實(shí)際中，從能量的角度看，把小任務(wù)擠壓到一個(gè)CPU core上可以有助于讓其他CPU core進(jìn)入更深的idle狀態(tài)，但是這樣會(huì)讓cluster進(jìn)入idle的機(jī)會(huì)大大降低。因此，實(shí)際上從能量模型上，我們并不能說明這樣的小任務(wù)擠壓的策略是好的還是壞的。因此，find_energy_efficient_cpu函數(shù)還是選擇把任務(wù)擠壓在一個(gè)cluster內(nèi)，然后在選中的cluster之中，盡量把任務(wù)散布到各個(gè)cpu上。這樣的策略對(duì)延遲而言肯定是好事情。這種策略也和“只有異構(gòu)系統(tǒng)中的EAS才能帶來的能量節(jié)省”是一致的。這也是為什么我們只在SD_ASYM_CPUCAPACITY的系統(tǒng)中打開EAS的原因。
在fork場(chǎng)景，被fork出來的任務(wù)到底放置在哪個(gè)CPU并不采用EAS算法，因?yàn)樗恢雷约旱膗til數(shù)據(jù)，也不太能夠預(yù)測(cè)出能量的消耗。因此，對(duì)fork出來的任務(wù)仍然使用慢速路徑（find_idlest_cpu函數(shù)）找到最空閑的group/cpu并將其放置在該cpu上執(zhí)行，在有些用戶場(chǎng)景下，這種方法可能是恰好命中能效比最高的CPU，但未必總是如此。另一種可能的方法是先將新fork出來的任務(wù)放置在特定類型的cpu（例如小核），或者嘗試從父任務(wù)推斷它們的util_avg，但是這種placement策略也可能損害其他用戶場(chǎng)景。在沒有找到其他更好的方法之前，我們?nèi)匀徊捎脗鹘y(tǒng)的慢速路徑的方式來選核。Exec場(chǎng)景和fork場(chǎng)景類似，不再贅述。
Overutilized主要用來切換EAS調(diào)度器還是傳統(tǒng)調(diào)度器。如果系統(tǒng)處于overutilized的狀態(tài)，那么不再執(zhí)行EAS的task placement的邏輯，如下：

EAS的選核邏輯是先確定一個(gè)sched domain，然后從sched domain中選擇一個(gè)能效比高的CPU，具體選擇sched domain的方式如下：

從最低level的，并且包括不同算力CPU的domain開始向上搜索，直到該domain覆蓋了this cpu和prevcpu為止。對(duì)于手機(jī)平臺(tái)就是Die domain。之所以要求包括異構(gòu)CPU的domain是因?yàn)橥瑯?gòu)的cpu不需要EAS，不會(huì)有功耗的節(jié)省。

因?yàn)楹竺嫘枰蝿?wù)p的utility參與計(jì)算（估計(jì)調(diào)頻點(diǎn)和能耗），而該任務(wù)在被喚醒之前應(yīng)該已經(jīng)阻塞了一段時(shí)間，它的utility還停留在阻塞前那一點(diǎn)，因此這里需要進(jìn)行負(fù)載更新：

sync_entity_load_avg函數(shù)用來更新該任務(wù)的sched avg，sync表示同步到其掛入的cfs rq的最近的負(fù)載更新時(shí)間點(diǎn)（而不是當(dāng)前時(shí)間點(diǎn)）。如果任務(wù)的utility等于0那么通過能量模型對(duì)其進(jìn)行運(yùn)算是沒有意義的，所以直接退出。

EAS最核心的代碼如下：

A、計(jì)算本performance domain的基礎(chǔ)能量消耗，即未放置任務(wù)p的能耗（base_energy_pd）。同時(shí)這里會(huì)累計(jì)各個(gè)pd的能耗（base_energy），也就是整個(gè)cpu系統(tǒng)消耗的能量。
B、遍歷該pd的各個(gè)cpu，計(jì)算各個(gè)cpu的剩余算力。這里的剩余算力是這樣計(jì)算的：獲取該cpu用于cfs task的算力（即原始算力去掉rt irq等消耗的算力），減去該cpu的util（即cfs task的總的utility）。這里的cpu util是把任務(wù)p放置在該cpu的預(yù)估utility（cpu_util_next）。
C、本身EAS就是在系統(tǒng)沒有overutilized的情況下才啟用的，如果任務(wù)p放置該CPU導(dǎo)致該cpu進(jìn)入overutilized，那么就跳過該CPU。當(dāng)然，這里的cpu util是經(jīng)過uclamp修正之后的util。上面步驟B中是估計(jì)cpu的空閑算力，需要真實(shí)的util，所以沒有經(jīng)過uclamp修正。
D、Prev cpu永遠(yuǎn)是備選對(duì)象，因此這里計(jì)算任務(wù)p放置在prev cpu上帶來的增量，方便后續(xù)進(jìn)行對(duì)比選核
E、尋找該perf domain中，空閑算力最大的那個(gè)CPU，這個(gè)cpu也是備選對(duì)象之一。
F、對(duì)比各個(gè)perf domain中選擇的最佳CPU（剩余空閑算力最大）的能耗，選擇一個(gè)最小的CPU，賦值給best_energy_cpu。
在EAS選核最后，選出的best_energy_cpu還要和prev cpu進(jìn)行PK，畢竟prevcpu有可能帶來潛在的性能收益（提高cache命中率），只有當(dāng)best_energy_cpu相對(duì)prev cpu能耗收益大于CPU總耗能的1/16，才選擇best_energy_cpu，否則還是運(yùn)行在prev cpu上。

七、能量計(jì)算

compute_energy函數(shù)原型如下：

該函數(shù)主要用來計(jì)算當(dāng)任務(wù)p放置到dst_cpu的時(shí)候，pd所在的perf domain會(huì)消耗多少能量。任務(wù)p放置到dst cpu的時(shí)候，這會(huì)影響pd所在的perfdomain中各個(gè)CPU的utility，進(jìn)而會(huì)驅(qū)動(dòng)cpufreq進(jìn)行頻率調(diào)整。計(jì)算能量的時(shí)候，我們必須預(yù)測(cè)可能的調(diào)頻，并通過這些utility可以估計(jì)該perf domain的能耗（任務(wù)放置在dst cpu之后）。詳細(xì)的代碼邏輯如下：

A、遍歷perf domain上的cpu，通過cpu_util_next計(jì)算任務(wù)p放置在dst cpu之后，各個(gè)cpu上的cfs任務(wù)的utility
B、在步驟A中僅僅得到了cfs任務(wù)的utility，通過schedutil_cpu_util得到該cpu的utility（累計(jì)rt、dl、irq等的util）并累計(jì)起來。這里的util是用來計(jì)算能量的，因此返回的util要等于真實(shí)CPU busy time，不需要uclamp的處理。遍歷perf domain上的所有CPU就得到其上的util總和，用于能量計(jì)算。
C、計(jì)算該CPU的調(diào)頻util。這里是調(diào)頻需要的util，需要進(jìn)行utility clamp處理。D、找到該perf domain中最大的cpuutil。
E、調(diào)用em_cpu_energy函數(shù)進(jìn)行該perf domain的耗能估計(jì)。Max_util用來估計(jì)該perf domain潛在運(yùn)行的頻點(diǎn)，sum_util表示該perf domain的總運(yùn)行時(shí)間。具體的運(yùn)算非常簡(jiǎn)單，在第三章已經(jīng)給出，不再贅述。

八、Wake affine

task_struct中有三個(gè)成員用來記錄被喚醒線程（wakee）的信息，如下：

每次waker喚醒wakee的時(shí)候都會(huì)調(diào)用record_wakee來更新上面的成員，具體代碼如下：

A、每隔一秒對(duì)wakee_flips進(jìn)行衰減。如果一個(gè)線程能夠經(jīng)常的喚醒不同的其他線程，那么該線程的wakee_flips會(huì)保持在一個(gè)較高的值。相反，如果僅僅是偶爾喚醒一次其他線程，和某個(gè)固定的線程有喚醒關(guān)系，那么這里的wakee_flips應(yīng)該會(huì)趨向0B、如果上次喚醒的不是p，那么要切換wakee，并累加wakee翻轉(zhuǎn)次數(shù)Waker喚醒wakee的場(chǎng)景中，有兩種placement思路：一種是聚合的思路，即讓waker和wakee盡量的close，從而提高cache hit。另外一種思考是分散，即讓load盡量平均分配在多個(gè)cpu上。不同的喚醒模型使用不同的放置策略。我們來看看下面兩種簡(jiǎn)單的喚醒模型：（1）在1：N模型中，一個(gè)server會(huì)不斷的喚醒多個(gè)不同的client（2）1：1模型，線程A和線程B不斷的喚醒對(duì)方在1：N模型中，如果N是一個(gè)較大的數(shù)值，那么讓waker和wakee盡量的close會(huì)導(dǎo)致負(fù)荷的極度不平均，這會(huì)waker所在的sched domain會(huì)承擔(dān)太多的task，從而引起性能下降。在1：1模型中，讓waker和wakee盡量的close不存在這樣的問題，同時(shí)還能提高性能。當(dāng)時(shí)，實(shí)際的程序中，喚醒關(guān)系可能沒有那么簡(jiǎn)單，一個(gè)wakee可能是另外一個(gè)關(guān)系中的waker，交互可能是M：N的形式。考慮這樣一個(gè)場(chǎng)景：waker把wakee拉近，而wakee自身的wakeeflips比較大，那么更多的線程也會(huì)拉近waker所在的scheddomain，從而進(jìn)一步加劇CPU資源的競(jìng)爭(zhēng)。因此waker和wakee的wakee flips的數(shù)值都不能太大，太大的時(shí)候應(yīng)該禁止wake affine。內(nèi)核中通過wake_wide來判斷是否使能wake affine：

A、這里的場(chǎng)景是current task喚醒任務(wù)p的場(chǎng)景，master是current喚醒不同線程的次數(shù)，slave是被喚醒的任務(wù)p喚醒不同線程的次數(shù)。
B、Wake affine場(chǎng)景下任務(wù)放置要走快速路徑，即在LLC上選擇空閑的CPU。sd_llc_size是LLCdomain上CPU的個(gè)數(shù)。Wake affine本質(zhì)上是把wakee線程們拉到waker所在的LLCdomain，如果超過了LLC domain的cpu個(gè)數(shù)，那么必然有任務(wù)需要等待，這也就失去了wake affine提升性能的初衷。對(duì)于手機(jī)平臺(tái)，llc domain是MC domain。
C、一般而言，執(zhí)行更多喚醒動(dòng)作（并且喚醒不同task）的任務(wù)是master，因此這里根據(jù)翻轉(zhuǎn)次數(shù)來交換master和slave，確保master的翻轉(zhuǎn)次數(shù)大于slave。
D、Slave和master的wakee_flips如果比較小，那么啟動(dòng)wake affine，否則disable wake affine，走正常選核邏輯。這里的or邏輯是存疑的，因?yàn)閙aster和slave其一的wakee_flips比較小就會(huì)wake affine，這會(huì)使得任務(wù)太容易在LLC domain堆積了。在1：N模型中（例如手機(jī)轉(zhuǎn)屏的時(shí)候，一個(gè)線程會(huì)喚醒非常非常多的線程來處理configChange消息），master的wakee_flips巨大無比，slave的wakee_flips非常小，如果仍然wake affine是不合理的。
如果判斷需要進(jìn)行wake affine，那么我們需要在waking cpu和該任務(wù)的prev cpu中選擇一個(gè)CPU，后續(xù)在該CPU的LLC domain上進(jìn)行wakeaffine。選擇waking cpu還是prev cpu的邏輯是在wake_affine中實(shí)現(xiàn)：

A、這里根據(jù)this_cpu（即wakingCPU）和prev cpu的idle狀態(tài)來選擇，哪個(gè)cpu處于idle狀態(tài)，那么就選擇那個(gè)cpu。如果都idle，那么優(yōu)先prev cpu。thiscpu有一個(gè)特殊情況：在sync wakeup的場(chǎng)景下，thiscpu上如果有唯一的running task（也就是waker了），那么優(yōu)先this cpu，畢竟waker很快就阻塞了。另外，當(dāng)this cpu處于idle狀態(tài)的時(shí)候（中斷喚醒），我們也不能盲目選擇它，畢竟在中斷大量下發(fā)的情況下，有些平臺(tái)會(huì)把硬件中斷信號(hào)只送到this cpu所在的節(jié)點(diǎn)，這會(huì)導(dǎo)致 this cpu所在的節(jié)點(diǎn)非常繁忙。
B、當(dāng)根據(jù)idle狀態(tài)無法完成選核的時(shí)候，我們會(huì)比拼this cpu和prev cpu上的負(fù)載。當(dāng)然，在計(jì)算this cpu和prev cpu負(fù)載的時(shí)候要考慮任務(wù)p的遷移。當(dāng)this cpu的負(fù)載小于prevcpu的負(fù)載的時(shí)候選擇this cpu。否則，選擇prevcpu。

九、快速選核路徑

快速選核路徑的入口是select_idle_sibling函數(shù)，在這個(gè)函數(shù)的開始是一些快速選擇cpu的邏輯，即不需要掃描整個(gè)LLC domain的CPU，找idle的cpu，而是直接選擇某個(gè)具體的cpu，具體如下：

A、在異構(gòu)系統(tǒng)中，我們后面的代碼邏輯需要使用該任務(wù)的utility，看看是否能夠適合CPU的算力，因此，這里需要進(jìn)行一個(gè)負(fù)載更新動(dòng)作，主要是衰減阻塞這段時(shí)間的負(fù)載。
B、如果之前選定的target cpu是idlecpu或者雖然沒有idle，但是runqueue中都是SCHED_IDLE的任務(wù)，而且該CPU的算力能夠承載該被喚醒的任務(wù)，這時(shí)候，直接返回target cpu即可。Wake affine的場(chǎng)景下，target cpu是通過wake_affine函數(shù)尋找的target cpu，其他場(chǎng)景下，target CPU其實(shí)等于prev CPU。第二段代碼如下：

A、如果prev cpu是idle狀態(tài)（包括runqueue上僅SCHED_IDLE的任務(wù)），并且prev cpu算力能承接該任務(wù)的utili，同時(shí)prev和target cpu在一個(gè)LLCdomain，那么優(yōu)選prev cpuB、當(dāng)waker是一個(gè)per cpu的kthread線程的時(shí)候，在wakee的prevcpu也是this cpu的時(shí)候，允許把wakee拉到waker所在的cpu，這是為了解決XFS性能問題而引入的提交。這時(shí)候kthread很快就會(huì)阻塞（類似sync wakeup），wakee也不會(huì)在runqueue上等太久。第三段代碼如下：

我們假設(shè)有這樣的一個(gè)場(chǎng)景，任務(wù)A和任務(wù)B互相喚醒，如果沒有這段代碼，選核如下：（1）任務(wù)A（在CPU0上）喚醒任務(wù)B并將其放置在CPU1（2）任務(wù)B（在CPU1上）喚醒任務(wù)A并將其放置在CPU2（3）任務(wù)A（在CPU2上）喚醒任務(wù)B并將其放置在CPU3（4）......這樣的選核讓任務(wù)A和任務(wù)B相互拉扯，均勻的使用LLCdomain中的各個(gè)CPU。這會(huì)導(dǎo)致任務(wù)的util平均散布在各個(gè)CPU上，從而導(dǎo)致CPU util比較小，處于比較低的頻率，影響性能。有了上面的這段代碼邏輯，任務(wù)A和任務(wù)B的喚醒過程如下：（1）任務(wù)A（在CPU0上）喚醒任務(wù)B并將其放置在CPU1（2）任務(wù)B（在CPU1上）喚醒任務(wù)A并將其放置在CPU0（3）......至此，快速選擇CPU的場(chǎng)景結(jié)束了，后續(xù)代碼是在LLC domain上選擇合適CPU的過程。對(duì)于異構(gòu)平臺(tái)（例如手機(jī)），我們更喜歡idle CPU，這時(shí)候我們擴(kuò)大搜尋范圍，從LLC擴(kuò)大到sd_asym_cpucapacity（DIE domain），代碼如下：

通過select_idle_capacity我們?cè)贒IE domain尋找第一個(gè)能夠承載該任務(wù)的idle cpu，如果雖然找到idle cpu，但是cpu capacity不足，這種情況下，我們返回算力最大的CPU即可。如果找不到idle cpu，那么選擇之前選擇的target cpu。對(duì)于同構(gòu)平臺(tái)，我們需要通過掃描llc domain尋找最空閑CPU，代碼邏輯如下（刪去了SMT代碼）：

select_idle_cpu邏輯比較簡(jiǎn)單，就是從LLC domain中找到第一個(gè)idle的cpu。為了防止不必要的scan開銷，在掃描之前需要對(duì)比該cpu rq的平均idle時(shí)間和掃描開銷，如果掃描開銷相對(duì)于平均idle時(shí)間太大，那么就不再進(jìn)行掃描。

十、慢速選核路徑


1. 概覽
和快速路徑不同，慢速路徑在一個(gè)指定的sched domain開始，層層遞進(jìn)，不斷搜索最空閑的group，然后在這個(gè)group中搜索最不忙的CPU，直到basedomain。這樣的結(jié)果就是在各個(gè)level的scheddomain上都達(dá)到了均衡的效果。慢速路徑的入口是find_idlest_cpu，其函數(shù)原型是：

該函數(shù)的參數(shù)以及返回值解釋如下：

我們分兩段來解析find_idlest_cpu的邏輯。第一段代碼流程如下：

A、如果任務(wù)p由于affinity的原因無法在sd指定的sched domain中運(yùn)行，那么直接選擇prev_cpuB、由于后續(xù)需要進(jìn)行cpu util的比拼，不同的選核會(huì)導(dǎo)致任務(wù)p util從一個(gè)cpu移動(dòng)到另外的cpu，因此需要調(diào)用sync_entity_load_avg來更新任務(wù)p的負(fù)載。當(dāng)然，新fork出來的任務(wù)沒有必要更新，使用初始負(fù)載即可第二段代碼流程如下：

A、Task placement也是均衡中的一個(gè)環(huán)節(jié)，而均衡是一個(gè)層層遞進(jìn)的過程：從指定的sched domain為起點(diǎn)，遍歷其child sched domain，直到base domain。
B、首先在參數(shù)sd中指定的domain中調(diào)用find_idlest_group函數(shù)找到最空閑的sched group，如果local group最閑，那么直接進(jìn)入下一級(jí)的child domain繼續(xù)搜尋。
C、在找到的最空閑的sched group中調(diào)用find_idlest_group_cpu函數(shù)尋找最空閑的CPU，如果不需要切換CPU，那么進(jìn)入下一級(jí)的child domain繼續(xù)搜尋。D、如果需要切換CPU，那么尋找該CPU對(duì)應(yīng)的下一級(jí)child domain，繼續(xù)進(jìn)行搜尋，直到base domain。

2. 尋找最空閑組
find_idlest_group的代碼邏輯主要分成兩個(gè)部分：第一部分是更新各個(gè)group上的負(fù)載并記錄non-local中最空閑的group和localgroup（總是備選）。第二部分是idlest group和localgroup的比拼。我們先看第一段代碼：

A、任務(wù)至少要能在該group中的一個(gè)cpu上運(yùn)行，否則就不考慮該groupB、判斷是否是local group。我們區(qū)別對(duì)待local group和non-local group，對(duì)于non-local group要找到最空閑的group。
C、更新該group上的負(fù)載信息。這里和load_balance中更新group負(fù)載的概念是一樣的，有興趣的可以看看內(nèi)核工匠之前發(fā)布的load_balance詳解的文章。不再贅述。
D、尋找最空閑的idlest group。
至此，我們已經(jīng)拿到了兩個(gè)group的統(tǒng)計(jì)信息：local group和non-group中idlest group。那么下一級(jí)進(jìn)入那個(gè)group對(duì)應(yīng)的domain就需要在這兩個(gè)group中比拼，有些選擇是顯而易見的，例如當(dāng)idlest group不存在或者雖然idlest group存在，但是local group更空閑，這時(shí)候選擇local group，可以使得該level的sched domain更加均衡。而當(dāng)local group不存在，或者idlest group比local group更空閑，這時(shí)候選擇idlest group。比較困難的場(chǎng)景是當(dāng)idlest group和local group空閑程度差不多（group_type相對(duì)），這又分成集中情況：（1）group_overloaded或者group_fully_busy的情況下，對(duì)比group的平均負(fù)載，選擇平均負(fù)載輕的（2）group_misfit_task情況下，選擇算力大的group（3）group_has_spare情況下，看哪個(gè)group中的idle cpu數(shù)量多

3. 尋找最空閑CPU
find_idlest_group_cpu的基本邏輯過程如下：（1）如果group內(nèi)只有一個(gè)cpu（base domain），那么直接返回該cpu（2）如果group內(nèi)有多個(gè)cpu，那么需要遍歷進(jìn)行比拼（3）如果一個(gè)cpu上只有SCHED_IDLE類型的任務(wù)，那么直接返回該cpu。（4）如果有處于idle狀態(tài)的cpu，那么選擇退出延時(shí)最小的那個(gè)idle cpu（即睡眠最淺的）。如果有多個(gè)cpu處于同等深度的idle狀態(tài)，那么選擇最近那個(gè)進(jìn)入idle的cpu（cache的狀態(tài)會(huì)好一些）（5）如果所有的cpu都忙碌中，那么選擇cpuload最小的那個(gè)。

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