負載均衡的系列文章共分爲三篇，第一篇爲框架篇，描述負載均衡的相關原理、場景和框架。本篇作爲該系列文章第二篇，主要通過對任務放置場景（task placement）的均衡分佈進行分析，以便加深讀者對內核調度器實現任務均衡分佈的理解。

本文基於linux-5.4.24分析，由於涉及較多代碼的講解，建議結合源碼閱讀。另外，瀏覽本文前，建議先閱讀公衆號的負載均衡系列文章第一篇：CFS任務的負載均衡（框架篇）。當然，部分已經提及的基本概念，在本文中也會進行簡單回顧。

一、任務放置場景

1. 什麼是任務放置（task placement）

linux內核爲每個CPU都配置一個cpu runqueue，用以維護當前CPU需要運行的所有線程，調度器會按一定的規則從runqueue中獲取某個線程來執行。如果一個線程正掛在某個CPU的runqueue上，此時它處於就緒狀態，尚未得到cpu資源，調度器會適時地通過負載均衡（load balance）來調整任務的分佈；當它從runqueue中取出並開始執行時，便處於運行狀態，若該狀態下的任務負載不是當前CPU所能承受的，那麼調度器會將其標記爲misfit task，週期性地觸發主動遷移（active upmigration），將misfit task佈置到更高算力的CPU。

上面提到的場景，都是線程已經被分配到某個具體的CPU並且具備有效的負載。如果一個任務線程還未被放置到任何一個CPU上，即處於阻塞狀態，又或者它是剛創建、剛開始執行的，此時調度器又是何如做均衡分佈的呢？這便是今天我們要花點篇幅來介紹的任務放置場景。

內核中，task placement場景發生在以下三種情況：

2. 調度域（sched domain）及其標誌位（sd flag）

如果你正在使用智能手機閱讀本文，那你或許知道，目前的手機設備往往具備架構不同的8個CPU core。我們仍然以4小核+4大核的處理器結構爲例進行說明。4個小核（cpu0-3）組成一個little cluster，另外4個大核（cpu4-7）組成big cluster，每個cluster的CPU架構相同，它們之間使用同一個調頻策略，並且頻率調節保持一致。大核相對小核而言，具備更高的算力，但也會帶來更多的能量損耗。

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

內核調度器依賴sched domain進行均衡，爲了方便地對各種均衡狀態進行識別，內核定義了一組sched domain flag，用來標識當前sched domain具備的均衡屬性。表中，我們可以看到task placement場景常見的三種情況對應的flag。

在構建CPU拓撲結構時，會爲各個sched domain配置初始的標識位，如果是異構系統，會設置SD_BALANCE_WAKE：

3. task placement均衡代碼框架

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

4. select_task_rq_fair()方法

CFS調度類的線程進行task placement時，會通過core.c的select_task_rq()方法跳轉至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參數：傳入sched domain標識位，目前一共有三種：SD_BALANCE_WAKE、SD_BALANCE_FORK、SD_BALANCE_EXEC，分別對應task placement的三種情形。調度器只會在設置有相應標識位的sched domain中進行CPU的選擇。

wake_flags參數：特地爲SD_BALANCE_WAKE提供的喚醒標識位，一共有三種類型：

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

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

find_energy_efficient_cpu()

find_idlest_cpu()

select_idle_sibling()

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

（1） find_energy_efficient_cpu()，即 EAS選核路徑。 當傳入參數sd_flag爲SD_BALANCE_WAKE，並且系統配置key值sched_energy_present（即考慮性能和功耗的均衡），調度器就會進入EAS選核路徑進行CPU的查找。這裏涉及到內核中Energy Aware Scheduling（EAS）機制，我們稍後將在第三節中詳細描述。總之，EAS路徑在保證任務能正常運行的前提下，爲任務選取使系統整體能耗最小的CPU。通常情況下，EAS總是能如願找到符合要求的CPU，但如果當前平臺不是異構系統，或者系統中存在超載（Over-utilization）的CPU，EAS就直接返回-1，不能在這次調度中大展拳腳。

當EAS不能在這次調度中發揮作用時，分支的走向取決於該任務是否爲wake affine類型的任務，這裏讓我們先來簡單瞭解下該類型的任務。

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

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

（2） find_idlest_cpu()，即 慢速路徑。 有兩種常見的情況會進入慢速路徑：傳入參數sd_flag爲SD_BALANCE_WAKE，且EAS沒有使能或者返回-1時，如果該任務不是wake affine類型，就會進入慢速路徑；傳入參數sd_flag爲SD_BALANCE_FORK、SD_BALANCE_EXEC時，由於此時的任務負載是不可信任的，無法預測其對系統能耗的影響，也會進入慢速路徑。慢速路徑使用find_idlest_cpu()方法找到系統中最空閒的CPU，作爲放置任務的CPU並返回。基本的搜索流程是：

首先確定放置的target domain（從waker的base domain向上，找到最底層配置相應sd_flag的domain），然後從target domain中找到負載最小的調度組，進而在調度組中找到負載最小的CPU。

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

（3） select_idle_sibling()，即 快速路徑。 傳入參數sd_flag爲SD_BALANCE_WAKE，但EAS又無法發揮作用時，若該任務爲wake affine類型任務，調度器就會進入快速路徑來選取放置的CPU，該路徑在CPU的選擇上，主要考慮共享cache且idle的CPU。在滿足條件的情況下，優先選擇任務上一次運行的CPU（prev cpu），hot cache的CPU是wake affine類型任務所青睞的。其次是喚醒任務的CPU（wake cpu），即waker所在的CPU。當該次喚醒爲sync喚醒時（傳入參數wake_flags爲WF_SYNC），對wake cpu的idle狀態判定將會放寬，比如waker爲wake cpu唯一的任務，由於sync喚醒下的waker很快就進入阻塞狀態，也可當做idle處理。

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

二、Energy Aware Scheduling（EAS）

系統中的Energy Aware Scheduling（EAS）機制被使能時，調度器就會在CFS任務由阻塞狀態喚醒的時候，使用find_energy_efficient_cpu()爲任務選擇合適的放置CPU。

1. 什麼是Energy Model（EM）

在瞭解什麼是EAS之前，我們先學習下EM。EM的設計使用比較簡單，因爲我們要避免在task placement時，由於算法過於複雜導致調度延遲變高。理解EM的一個重點是理解性能域（performance domain）。與sched domain相同，內核也有相應的結構體struct perf_domain來定義性能域。相同微架構的CPU會歸屬到同一個perf domain，4大核+4小核的CPU拓撲信息如下：

little cluster的4個CPU core組成一個perf domain，big cluster則組成另外一個。相同perf domian內的所有CPU core一起進行調頻，保持着相同的頻率。CPU使用的頻點是分級的，各級別的頻點與capacity值、power值是一一映射的關係，例如：小核的4個cpu，最大capacity都是512，與之對應的最高頻點爲1G Hz，那麼500M Hz的頻點對應的capacity就是256。爲了將這些信息有效的組織起來，內核又爲EM增加兩個新的結構體，用於存儲這些信息，它們都能夠從perf domain中獲取。

2. 什麼是EAS

異構CPU拓撲架構（比如Arm big.LITTLE架構），存在高性能的cluster和低功耗的cluster，它們的算力（capacity）之間存在差異，這讓調度器在喚醒場景下進行task placement變得更加複雜，我們希望在不影響整體系統吞吐量的同時，儘可能地節省能量，因此，EAS應運而生。它的設計令調度器在做CPU選擇時，增加能量評估的維度，它的運作依賴於Energy Model（EM）。

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

EAS在非異構系統下，或者系統中存在超載CPU時不會使能，調度器對於CPU超載的判定是比較嚴格的，當root domain中存在CPU負載達到該CPU算力的80%以上時，就認爲是超載。

3. EM是如何估算energy的

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

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

max_util參數：perf domain各個CPU中的最高負載。

sum_util參數：perf domain中所有CPU的總負載。

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

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

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

4. EAS task placement

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

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

（2）遍歷各個perf domain，找到該domain下擁有最大空餘算力的CPU以及prev cpu，作爲備選放置CPU；

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

（4）通過比較得到令energy變化最小的備選CPU，即將任務放置到該CPU上，能得到最小的domain energy，如果相對於將任務放置到prev cpu，此次的選擇能節省6%以上的能量，則該CPU爲目標CPU。

選擇perf domain中擁有最大空餘算力的CPU作爲備選CPU，是因爲這樣可以避免某個CPU負載特別高，導致整個cluster的頻點往上提。並且顧及到hot cache的prev cpu有利於提高任務運行效率，EAS對於prev cpu還是難以割捨的，除非節能可以達到6%以上。

另外，從上面的邏輯中也可以看出爲何超載情況下EAS是不使能的。我們假定little cluster中cpu3存在超載的情況，那麼無論你將任務放置到哪個CPU上，little cluster總是維持最高頻點，對於同個perf domain下擁有最大空餘算力的CPU來說，這樣預估的energy是不公平的，與EAS的設計相違背，EAS希望能通過放置任務改變cluster的頻點來降低功耗。

三、總結

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

我們可以看到，目前task placement過程中的一些啓發式算法還存在缺陷，也能看到開發者對此的不斷思考和創新，隨着內核版本的不斷更新迭代，未來的調度算法一定會出現更多有意思的特性。

參考資料

[1] linux-5.4.24 source code

[2] linux-5.4.24/Documentation/power/ energy-model.rst

[3] linux-5.4.24/Documentation/scheduler/ sched-energy.rst

[4] https://lwn.net/Articles/728942/

Linux 內核黑科技 | 技術文章 | 精選教程