本文基于linux-5.4.24分析，由于涉及較多代碼的講解，建議結(jié)合源碼閱讀。另外，瀏覽本文前，建議先閱讀公眾號的負(fù)載均衡系列文章第一篇：CFS任務(wù)的負(fù)載均衡（框架篇）。當(dāng)然，部分已經(jīng)提及的基本概念，在本文中也會進(jìn)行簡單回顧。

一、任務(wù)放置場景

1. 什么是任務(wù)放置（task placement）

linux內(nèi)核為每個CPU都配置一個cpu runqueue，用以維護(hù)當(dāng)前CPU需要運行的所有線程，調(diào)度器會按一定的規(guī)則從runqueue中獲取某個線程來執(zhí)行。如果一個線程正掛在某個CPU的runqueue上，此時它處于就緒狀態(tài)，尚未得到cpu資源，調(diào)度器會適時地通過負(fù)載均衡（load balance）來調(diào)整任務(wù)的分布；當(dāng)它從runqueue中取出并開始執(zhí)行時，便處于運行狀態(tài)，若該狀態(tài)下的任務(wù)負(fù)載不是當(dāng)前CPU所能承受的，那么調(diào)度器會將其標(biāo)記為misfit task，周期性地觸發(fā)主動遷移（active upmigration），將misfit task布置到更高算力的CPU。

上面提到的場景，都是線程已經(jīng)被分配到某個具體的CPU并且具備有效的負(fù)載。如果一個任務(wù)線程還未被放置到任何一個CPU上，即處于阻塞狀態(tài)，又或者它是剛創(chuàng)建、剛開始執(zhí)行的，此時調(diào)度器又是何如做均衡分布的呢？這便是今天我們要花點篇幅來介紹的任務(wù)放置場景。

內(nèi)核中，task placement場景發(fā)生在以下三種情況：

（1）進(jìn)程通過fork創(chuàng)建子進(jìn)程；

（2）進(jìn)程通過sched_exec開始執(zhí)行；

（3）阻塞的進(jìn)程被喚醒。

2. 調(diào)度域（sched domain）及其標(biāo)志位（sd flag）

如果你正在使用智能手機(jī)閱讀本文，那你或許知道，目前的手機(jī)設(shè)備往往具備架構(gòu)不同的8個CPU core。我們?nèi)匀灰?小核+4大核的處理器結(jié)構(gòu)為例進(jìn)行說明。4個小核（cpu0-3）組成一個little cluster，另外4個大核（cpu4-7）組成big cluster，每個cluster的CPU架構(gòu)相同，它們之間使用同一個調(diào)頻策略，并且頻率調(diào)節(jié)保持一致。大核相對小核而言，具備更高的算力，但也會帶來更多的能量損耗。

對于多處理器均衡（multiprocessor balancing）而言，sched domain是極為重要的概念。內(nèi)核中以結(jié)構(gòu)體struct sched_domain對其進(jìn)行定義，將CPU core從下往上按層級劃分，對系統(tǒng)所有CPU core進(jìn)行管理，本系列文章第一篇已進(jìn)行過較為詳細(xì)的描述。little cluster和big cluster各自組成底層的MC domain，包含各自cluster的4個CPU core，頂層的DIE domian則覆蓋系統(tǒng)中所有的CPU core。

內(nèi)核調(diào)度器依賴sched domain進(jìn)行均衡，為了方便地對各種均衡狀態(tài)進(jìn)行識別，內(nèi)核定義了一組sched domain flag，用來標(biāo)識當(dāng)前sched domain具備的均衡屬性。表中，我們可以看到task placement場景常見的三種情況對應(yīng)的flag。

在構(gòu)建CPU拓?fù)浣Y(jié)構(gòu)時，會為各個sched domain配置初始的標(biāo)識位，如果是異構(gòu)系統(tǒng)，會設(shè)置SD_BALANCE_WAKE：

3. task placement均衡代碼框架

linux內(nèi)核的調(diào)度框架是高度抽象、模塊化的，所有的線程都擁有各自所屬的調(diào)度類（sched class），比如大家所熟知的實時線程屬于rt_sched_class，CFS線程屬于fair_sched_class，不同的調(diào)度類采用不同的調(diào)度策略。上面提到的task placement的三種場景，最終的函數(shù)入口都是core.c中定義的select_task_rq()方法，之后會跳轉(zhuǎn)至調(diào)度類自己的具體實現(xiàn)。本文以CFS調(diào)度類為分析對象，因為該調(diào)度類的線程在整個系統(tǒng)中占據(jù)較大的比重。有興趣的朋友可以了解下其它調(diào)度類的select_task_rq()實現(xiàn)。

4. select_task_rq_fair()方法

CFS調(diào)度類的線程進(jìn)行task placement時，會通過core.c的select_task_rq()方法跳轉(zhuǎn)至select_task_rq_fair()，該方法聲明如下：

static int select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)

sd_flag參數(shù)：傳入sched domain標(biāo)識位，目前一共有三種：SD_BALANCE_WAKE、SD_BALANCE_FORK、SD_BALANCE_EXEC，分別對應(yīng)task placement的三種情形。調(diào)度器只會在設(shè)置有相應(yīng)標(biāo)識位的sched domain中進(jìn)行CPU的選擇。

wake_flags參數(shù)：特地為SD_BALANCE_WAKE提供的喚醒標(biāo)識位，一共有三種類型：

select_task_rq_fair()內(nèi)僅對WF_SYNC進(jìn)行處理，若傳入該標(biāo)識位，說明喚醒線程waker在被喚醒線程wakee喚醒后，將進(jìn)入阻塞狀態(tài)，調(diào)度器會傾向于將wakee放置到waker所在的CPU。這種場景使用相當(dāng)頻繁，比如用戶空間兩個進(jìn)程進(jìn)行非異步binder通信，Server端喚醒一個binder線程處理事務(wù)時，調(diào)用的接口如下：

select_task_rq_fair()中涉及到三個重要的選核函數(shù)：

????find_energy_efficient_cpu()

????find_idlest_cpu()

????select_idle_sibling()

它們分別代表任務(wù)放置過程中的三條路徑。task placement的各個場景，根據(jù)不同條件，最終都會進(jìn)入其中某一條路徑，得到任務(wù)放置CPU并結(jié)束此次的task placement過程?，F(xiàn)在讓我們來理一理這三條路徑的常見進(jìn)入條件以及基本的CPU選擇考量：

（1）find_energy_efficient_cpu()，即EAS選核路徑。當(dāng)傳入?yún)?shù)sd_flag為SD_BALANCE_WAKE，并且系統(tǒng)配置key值sched_energy_present（即考慮性能和功耗的均衡），調(diào)度器就會進(jìn)入EAS選核路徑進(jìn)行CPU的查找。這里涉及到內(nèi)核中Energy Aware Scheduling（EAS）機(jī)制，我們稍后將在第三節(jié)中詳細(xì)描述。總之，EAS路徑在保證任務(wù)能正常運行的前提下，為任務(wù)選取使系統(tǒng)整體能耗最小的CPU。通常情況下，EAS總是能如愿找到符合要求的CPU，但如果當(dāng)前平臺不是異構(gòu)系統(tǒng)，或者系統(tǒng)中存在超載（Over-utilization）的CPU，EAS就直接返回-1，不能在這次調(diào)度中大展拳腳。

當(dāng)EAS不能在這次調(diào)度中發(fā)揮作用時，分支的走向取決于該任務(wù)是否為wake affine類型的任務(wù)，這里讓我們先來簡單了解下該類型的任務(wù)。

用戶場景有時會出現(xiàn)一個主任務(wù)（waker）喚醒多個子任務(wù)（wakee）的情況，如果我們將其作為wake affine類型處理，將wakee打包在臨近的CPU上（如喚醒CPU、上次執(zhí)行的CPU、共享cache的CPU），即可以提高cache命中率，改善性能，又能避免喚醒其它可能正處于idle狀態(tài)的CPU，節(jié)省功耗。看起來這樣的處理似乎非常完美，可惜的是，往往有些wakee對調(diào)度延遲非常敏感，如果將它們打包在一塊，CPU上的任務(wù)就變得“擁擠”，調(diào)度延遲就會急劇上升，這樣的場景下，所謂的cache命中率、功耗，一切的誘惑都變得索然無味。

對于wake affine類型的判斷，內(nèi)核主要通過wake_wide()和wake_cap()的實現(xiàn)，從wakee的數(shù)量以及臨近CPU算力是否滿足任務(wù)需求這兩個維度進(jìn)行考量。

（2）find_idlest_cpu()，即慢速路徑。有兩種常見的情況會進(jìn)入慢速路徑：傳入?yún)?shù)sd_flag為SD_BALANCE_WAKE，且EAS沒有使能或者返回-1時，如果該任務(wù)不是wake affine類型，就會進(jìn)入慢速路徑；傳入?yún)?shù)sd_flag為SD_BALANCE_FORK、SD_BALANCE_EXEC時，由于此時的任務(wù)負(fù)載是不可信任的，無法預(yù)測其對系統(tǒng)能耗的影響，也會進(jìn)入慢速路徑。慢速路徑使用find_idlest_cpu()方法找到系統(tǒng)中最空閑的CPU，作為放置任務(wù)的CPU并返回?；镜乃阉髁鞒淌牵?/p>

首先確定放置的target domain（從waker的base domain向上，找到最底層配置相應(yīng)sd_flag的domain），然后從target domain中找到負(fù)載最小的調(diào)度組，進(jìn)而在調(diào)度組中找到負(fù)載最小的CPU。

這種選核方式對于剛創(chuàng)建的任務(wù)來說，算是一種相對穩(wěn)妥的做法，開發(fā)者也指出，或許可以將新創(chuàng)建的任務(wù)放置到特殊類型的CPU上，或者通過它的父進(jìn)程來推斷它的負(fù)載走向，但這些啟發(fā)式的方法也有可能在一些使用場景下造成其他問題。

（3）select_idle_sibling()，即快速路徑。傳入?yún)?shù)sd_flag為SD_BALANCE_WAKE，但EAS又無法發(fā)揮作用時，若該任務(wù)為wake affine類型任務(wù)，調(diào)度器就會進(jìn)入快速路徑來選取放置的CPU，該路徑在CPU的選擇上，主要考慮共享cache且idle的CPU。在滿足條件的情況下，優(yōu)先選擇任務(wù)上一次運行的CPU（prev cpu），hot cache的CPU是wake affine類型任務(wù)所青睞的。其次是喚醒任務(wù)的CPU（wake cpu），即waker所在的CPU。當(dāng)該次喚醒為sync喚醒時（傳入?yún)?shù)wake_flags為WF_SYNC），對wake cpu的idle狀態(tài)判定將會放寬，比如waker為wake cpu唯一的任務(wù)，由于sync喚醒下的waker很快就進(jìn)入阻塞狀態(tài)，也可當(dāng)做idle處理。

如果prev cpu或者wake cpu無法滿足條件，那么調(diào)度器會嘗試從它們的LLC domain中去搜索idle的CPU。

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

二、Energy Aware Scheduling（EAS）

系統(tǒng)中的Energy Aware Scheduling（EAS）機(jī)制被使能時，調(diào)度器就會在CFS任務(wù)由阻塞狀態(tài)喚醒的時候，使用find_energy_efficient_cpu()為任務(wù)選擇合適的放置CPU。

1. 什么是Energy Model（EM）

在了解什么是EAS之前，我們先學(xué)習(xí)下EM。EM的設(shè)計使用比較簡單，因為我們要避免在task placement時，由于算法過于復(fù)雜導(dǎo)致調(diào)度延遲變高。理解EM的一個重點是理解性能域（performance domain）。與sched domain相同，內(nèi)核也有相應(yīng)的結(jié)構(gòu)體struct perf_domain來定義性能域。相同微架構(gòu)的CPU會歸屬到同一個perf domain，4大核+4小核的CPU拓?fù)湫畔⑷缦拢?/p>

little cluster的4個CPU core組成一個perf domain，big cluster則組成另外一個。相同perf domian內(nèi)的所有CPU core一起進(jìn)行調(diào)頻，保持著相同的頻率。CPU使用的頻點是分級的，各級別的頻點與capacity值、power值是一一映射的關(guān)系，例如：小核的4個cpu，最大capacity都是512，與之對應(yīng)的最高頻點為1G Hz，那么500M Hz的頻點對應(yīng)的capacity就是256。為了將這些信息有效的組織起來，內(nèi)核又為EM增加兩個新的結(jié)構(gòu)體，用于存儲這些信息，它們都能夠從perf domain中獲取。

2. 什么是EAS

異構(gòu)CPU拓?fù)浼軜?gòu)（比如Arm big.LITTLE架構(gòu)），存在高性能的cluster和低功耗的cluster，它們的算力（capacity）之間存在差異，這讓調(diào)度器在喚醒場景下進(jìn)行task placement變得更加復(fù)雜，我們希望在不影響整體系統(tǒng)吞吐量的同時，盡可能地節(jié)省能量，因此，EAS應(yīng)運而生。它的設(shè)計令調(diào)度器在做CPU選擇時，增加能量評估的維度，它的運作依賴于Energy Model（EM）。

EAS對能量（energy）和功率（power）的定義與傳統(tǒng)意義并無差別，energy是類似電源設(shè)備上的電池這樣的資源，單位是焦耳，power則是每秒的能量損耗值，單位是瓦特。

EAS在非異構(gòu)系統(tǒng)下，或者系統(tǒng)中存在超載CPU時不會使能，調(diào)度器對于CPU超載的判定是比較嚴(yán)格的，當(dāng)root domain中存在CPU負(fù)載達(dá)到該CPU算力的80%以上時，就認(rèn)為是超載。

3. EM是如何估算energy的

由于EM將系統(tǒng)中所有CPU的各級capacity、frequence、power以便捷高效的方式組織起來，計算energy的工作就變得很簡單了。內(nèi)核中某個perf domian的energy可以通過em_pd_energy()獲得，它實際上是通過假定將任務(wù)放置到某個CPU上，引起perf domain各個CPU負(fù)載變化，來估算整體energy數(shù)值。令人值得慶幸的是，該方法的實現(xiàn)代碼中，有一半以上都是注釋語句。

static inline unsigned long em_pd_energy(struct em_perf_domain *pd, unsigned long max_util, unsigned long sum_util)

max_util參數(shù)：perf domain各個CPU中的最高負(fù)載。

sum_util參數(shù)：perf domain中所有CPU的總負(fù)載。

前面提到過，同個perf domian下的所有CPU使用相同的頻點，因此，cluster選擇哪個頻點，取決于擁有最大負(fù)載的CPU。EM首先會獲取當(dāng)前perf domain的最高頻點和最大算力，并將max_util映射到對應(yīng)的頻率上，找到超過該頻率的最低頻點及相應(yīng)的算力cs_capacity，畢竟我們要確保任務(wù)能夠正常執(zhí)行。

盡管我們知道EA可以很輕易的獲得該頻點的功率cs_power值，并且無論是cs_capacity還是cs_power，domain下所有CPU都是相同的，但是要獲得各個CPU的energy，我們還需要一個跟各個CPU運行時間相關(guān)的信息。由于CPU不是超載的（超載情況下EAS不會使能），它不會一直運行任務(wù)，我們需要忽略掉idle的部分，這一點可以通過CPU負(fù)載與算力的比值進(jìn)行估算。這是由于，負(fù)載體現(xiàn)了CPU執(zhí)行任務(wù)的窗口時間，當(dāng)整個窗口時間都在運行任務(wù)時，CPU的負(fù)載就達(dá)到其算力上限。

好了，現(xiàn)在需要的信息都齊全，只要將所有CPU的energy累加起來，就能得到整個perf domain的估計能量值。

4. EAS task placement

EAS在任務(wù)喚醒時，通過函數(shù)find_energy_efficient_cpu()為任務(wù)選擇合適的放置CPU，它的實現(xiàn)邏輯大致如下：

（1）通過em_pd_energy()計算取得各個perf domian未放置任務(wù)的基礎(chǔ)能量值；

（2）遍歷各個perf domain，找到該domain下?lián)碛凶畲罂沼嗨懔Φ腃PU以及prev cpu，作為備選放置CPU；

（3）通過em_pd_energy()計算取得將任務(wù)放置到備選CPU引起的perf domain的energy變化值；

（4）通過比較得到令energy變化最小的備選CPU，即將任務(wù)放置到該CPU上，能得到最小的domain energy，如果相對于將任務(wù)放置到prev cpu，此次的選擇能節(jié)省6%以上的能量，則該CPU為目標(biāo)CPU。

選擇perf domain中擁有最大空余算力的CPU作為備選CPU，是因為這樣可以避免某個CPU負(fù)載特別高，導(dǎo)致整個cluster的頻點往上提。并且顧及到hot cache的prev cpu有利于提高任務(wù)運行效率，EAS對于prev cpu還是難以割舍的，除非節(jié)能可以達(dá)到6%以上。

另外，從上面的邏輯中也可以看出為何超載情況下EAS是不使能的。我們假定little cluster中cpu3存在超載的情況，那么無論你將任務(wù)放置到哪個CPU上，little cluster總是維持最高頻點，對于同個perf domain下?lián)碛凶畲罂沼嗨懔Φ腃PU來說，這樣預(yù)估的energy是不公平的，與EAS的設(shè)計相違背，EAS希望能通過放置任務(wù)改變cluster的頻點來降低功耗。

三、總結(jié)

本文作為負(fù)載均衡系列文章的第二篇，主要對CFS任務(wù)的task placement做場景分析，描述調(diào)度器在此過程中的選擇實現(xiàn)和考量，由于篇幅和精力有限，很多具體的細(xì)節(jié)還沒能呈現(xiàn)清晰，特別是對快速路徑和慢速路徑這一塊的描述，希望有興趣的朋友可以自行閱讀源碼實現(xiàn)，共同學(xué)習(xí)交流。

我們可以看到，目前task placement過程中的一些啟發(fā)式算法還存在缺陷，也能看到開發(fā)者對此的不斷思考和創(chuàng)新，隨著內(nèi)核版本的不斷更新迭代，未來的調(diào)度算法一定會出現(xiàn)更多有意思的特性。

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