我們描述負(fù)載均衡的系列文章一共三篇，第一篇是框架部分，即本文，主要描述了負(fù)載均衡相關(guān)的原理、場(chǎng)景和框架。后面的兩篇是對(duì)均衡代碼的情景分析，通過(guò)對(duì)load balance、task placement和active upmigration幾個(gè)典型的負(fù)載均衡來(lái)呈現(xiàn)其實(shí)現(xiàn)細(xì)節(jié)，稍后發(fā)布，敬請(qǐng)期待。

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

一、什么是負(fù)載均衡

1、什么是CPU負(fù)載（load）

CPU負(fù)載是一個(gè)很容易和CPU利用率（utility）混淆的概念。CPU利用率是CPU忙閑的比例，例如在一個(gè)周期為1000ms的窗口中觀察CPU的情況，如果500ms的時(shí)間在執(zhí)行任務(wù)，500ms的時(shí)間處于idle狀態(tài)，那么在這個(gè)窗口中CPU的利用率是50%。

在CPU利用率沒(méi)有達(dá)到100%的時(shí)候，利用率基本上等于負(fù)載，一旦當(dāng)CPU利用率達(dá)到了100%的時(shí)候，利用率其實(shí)是無(wú)法給出CPU負(fù)載的狀況，因?yàn)榇蠹业睦寐识际?00%，利用率相等，但是并不意味著CPUs的負(fù)載也是相等的，因?yàn)檫@時(shí)候不同CPU上runqueue中等待執(zhí)行的任務(wù)數(shù)目不同，直覺(jué)上runque上掛著10任務(wù)的CPU承壓比掛著5個(gè)任務(wù)的CPU的負(fù)載要更重一些。因此，早期的CPU負(fù)載是使用runqueue深度來(lái)描述的。

顯然，僅僅使用runqueue深度來(lái)表示CPU負(fù)載是一個(gè)很粗略的概念，我們可以舉一個(gè)簡(jiǎn)單的例子：當(dāng)前CPU A和CPU B上都掛了1個(gè)任務(wù)，但是A上掛的任務(wù)是一個(gè)重載任務(wù)，而B(niǎo)上掛的是一個(gè)經(jīng)常sleep的輕載任務(wù)，那么僅僅從runqueue深度來(lái)描述CPU負(fù)載就有失偏頗了。因此，現(xiàn)代調(diào)度器往往使用CPU runqueue上task load之和來(lái)表示CPU load。這樣，對(duì)CPU負(fù)載的跟蹤就變成了對(duì)任務(wù)負(fù)載的跟蹤。

3.8版本的linux內(nèi)核引入了PELT算法來(lái)跟蹤每一個(gè)sched entity的負(fù)載，把負(fù)載跟蹤的算法從per-CPU進(jìn)化到per-entity。PELT算法不但能知道CPU的負(fù)載，而且知道負(fù)載來(lái)自哪一個(gè)調(diào)度實(shí)體，從而可以更精準(zhǔn)的進(jìn)行負(fù)載均衡。

2、什么是均衡

對(duì)于負(fù)載均衡而言，并不是把整個(gè)系統(tǒng)的負(fù)載平均的分配到系統(tǒng)中的各個(gè)CPU上。實(shí)際上，我們還是必須要考慮系統(tǒng)中各個(gè)CPU的算力，讓CPU獲得和其算力匹配的負(fù)載。例如在一個(gè)6個(gè)小核+2個(gè)大核的系統(tǒng)中，整個(gè)系統(tǒng)如果有800的負(fù)載，那么每個(gè)CPU上分配100的負(fù)載其實(shí)是不均衡的，因?yàn)榇蠛薈PU可以提供更強(qiáng)的算力。

什么是CPU算力（capacity），所謂算力就是描述CPU的能夠提供的計(jì)算能力。在同樣的頻率下，一個(gè)微架構(gòu)是A77的CPU顯然算力要大于A57的CPU。如果CPU的微架構(gòu)都是一樣的，那么一個(gè)最大頻率是2.2GHz的CPU算力肯定是大于最大頻率是1.1GHz的CPU。因此，確定了微架構(gòu)和最大頻率，一個(gè)CPU的算力就基本確定了。Cpufreq系統(tǒng)會(huì)根據(jù)當(dāng)前的CPU util來(lái)調(diào)節(jié)CPU當(dāng)前的運(yùn)行頻率，但這并不能改變CPU算力。只有當(dāng)CPU最大運(yùn)行頻率發(fā)生變化的時(shí)候（例如觸發(fā)溫控，限制了該CPU的最大頻率），CPU的算力才會(huì)隨之變化。

此外，本文主要描述CFS任務(wù)的均衡（RT的均衡不考慮負(fù)載，是在另外的維度），因此在考慮CPU算力的時(shí)候，需要把CPU用于執(zhí)行rt和irq的算力去掉，使用該CPU可用于CFS的算力。因此，CFS任務(wù)均衡中使用的CPU算力其實(shí)一個(gè)不斷變化的值，需要經(jīng)常更新。為了讓CPU算力和任務(wù)負(fù)載可以對(duì)比，實(shí)際上我們采用了歸一化的方式，即系統(tǒng)中處理能力最強(qiáng)的CPU運(yùn)行在最高頻率的算力是1024，其他的CPU算力根據(jù)微架構(gòu)和運(yùn)行頻率響應(yīng)的調(diào)整其算力。

有了任務(wù)負(fù)載就可以得到CPU負(fù)載，配合系統(tǒng)中各個(gè)CPU的算力，看起來(lái)我們就可以完成負(fù)載均衡的工作，然而事情沒(méi)有那么簡(jiǎn)單，當(dāng)負(fù)載不均衡的時(shí)候，任務(wù)需要在CPU之間遷移，不同形態(tài)的遷移會(huì)有不同的開(kāi)銷。例如一個(gè)任務(wù)在小核cluster上的CPU之間的遷移所帶來(lái)的性能開(kāi)銷一定是小于任務(wù)從小核cluster的CPU遷移到大核cluster的開(kāi)銷。因此，為了更好的執(zhí)行負(fù)載均衡，我們需要構(gòu)建和CPU拓?fù)湎嚓P(guān)的數(shù)據(jù)結(jié)構(gòu)，也就是調(diào)度域和調(diào)度組的概念。

3、調(diào)度域（sched domain）和調(diào)度組（sched group）

負(fù)載均衡的復(fù)雜性主要和復(fù)雜的系統(tǒng)拓?fù)溆嘘P(guān)。由于當(dāng)前CPU很忙，我們把之前運(yùn)行在該CPU上的一個(gè)任務(wù)遷移到新的CPU上的時(shí)候，如果遷移到新的CPU是和原來(lái)的CPU在不同的cluster中，性能會(huì)受影響（因?yàn)闀?huì)cache flush）。

但是對(duì)于超線程架構(gòu)，cpu共享cache，這時(shí)候超線程之間的任務(wù)遷移將不會(huì)有特別明顯的性能影響。NUMA上任務(wù)遷移的影響又不同，我們應(yīng)該盡量避免不同NUMA node之間的任務(wù)遷移，除非NUMA node之間的均衡達(dá)到非常嚴(yán)重的程度。

總之，一個(gè)好的負(fù)載均衡算法必須適配各種cpu拓?fù)浣Y(jié)構(gòu)。為了解決這些問(wèn)題，linux內(nèi)核引入了sched_domain的概念。

內(nèi)核中struct sched_domain來(lái)描述調(diào)度域，其主要的成員如下：

一旦形成了調(diào)度域，那么負(fù)載均衡就被限制在了該調(diào)度域內(nèi)，在該調(diào)度域內(nèi)進(jìn)行均衡的時(shí)候不考慮系統(tǒng)中其他調(diào)度域的CPU負(fù)載情況，只考慮該調(diào)度域內(nèi)的sched group之間的負(fù)載是否均衡。對(duì)于base domain，其所屬的sched group中只有一個(gè)cpu，對(duì)于更高level的sched domain，其所屬的sched group中可能會(huì)有多個(gè)cpu core。內(nèi)核中struct sched_group來(lái)描述調(diào)度組，其主要的成員如下：

上面的描述過(guò)于枯燥，我們后面會(huì)使用一個(gè)具體的例子來(lái)描述負(fù)載如何在各個(gè)level的sched domain上進(jìn)行均衡的，不過(guò)在此之前，我們先看看負(fù)載均衡的整體軟件架構(gòu)。

二、負(fù)載均衡的軟件架構(gòu)

負(fù)載均衡的整體軟件結(jié)構(gòu)圖如下：

負(fù)載均衡模塊主要分兩個(gè)軟件層次：核心負(fù)載均衡模塊和class-specific均衡模塊。內(nèi)核對(duì)不同的類型的任務(wù)有不同的均衡策略，普通的CFS（complete fair schedule）任務(wù)和RT、Deadline任務(wù)處理方式是不同的，由于篇幅原因，本文主要討論CFS任務(wù)的負(fù)載均衡。

為了更好的進(jìn)行CFS任務(wù)的均衡，系統(tǒng)需要跟蹤任務(wù)負(fù)載和CPU負(fù)載。跟蹤任務(wù)負(fù)載是主要有兩個(gè)原因：

（1）判斷該任務(wù)是否適合當(dāng)前CPU算力。

（2）如果判定需要均衡，那么需要在CPU之間遷移多少的任務(wù)才能達(dá)到平衡？有了任務(wù)負(fù)載跟蹤模塊，這個(gè)問(wèn)題就比較好回答了。

對(duì)CPU負(fù)載的跟蹤不僅要考慮每一個(gè)CPU的負(fù)載，還要匯聚cluster上所有負(fù)載，方便計(jì)算cluster之間負(fù)載的不均衡狀況。

為了更好的進(jìn)行高效的均衡，我們還需要構(gòu)建調(diào)度域的層級(jí)結(jié)構(gòu)（sched domain hierarchy），圖中顯示的是二級(jí)結(jié)構(gòu)。手機(jī)場(chǎng)景多半是二級(jí)結(jié)構(gòu)，支持NUMA的服務(wù)器場(chǎng)景可能會(huì)形成更復(fù)雜的結(jié)構(gòu)。通過(guò)DTS和CPU topo子系統(tǒng)，我們可以構(gòu)建sched domain層級(jí)結(jié)構(gòu)，用于具體的均衡算法。

有了上面描述的基礎(chǔ)設(shè)施，那么什么時(shí)候進(jìn)行負(fù)載均衡呢？這主要和調(diào)度事件相關(guān)，當(dāng)發(fā)生任務(wù)喚醒、任務(wù)創(chuàng)建、tick到來(lái)等調(diào)度事件的時(shí)候，我們可以檢查當(dāng)前系統(tǒng)的不均衡情況，并酌情進(jìn)行任務(wù)遷移，以便讓系統(tǒng)負(fù)載處于平衡狀態(tài)。

三、如何做負(fù)載均衡

1、一個(gè)CPU拓?fù)涫纠?/p>

我們以一個(gè)4小核+4大核的處理器來(lái)描述CPU的domain和group：

在上面的結(jié)構(gòu)中，sched domain是分成兩個(gè)level，base domain稱為MC domain（multi core domain），頂層的domain稱為DIE domain。頂層的DIE domain覆蓋了系統(tǒng)中所有的CPU，小核cluster的MC domain包括所有小核cluster中的cpu，同理，大核cluster的MC domain包括所有大核cluster中的cpu。

對(duì)于小核MC domain而言，其所屬的sched group有四個(gè)，cpu0、1、2、3分別形成一個(gè)sched group，形成了MC domain的sched group環(huán)形鏈表。

不同CPU的MC domain的環(huán)形鏈表首元素（即sched domain中的groups成員指向的那個(gè)sched group）是不同的，對(duì)于cpu0的MC domain，其groups環(huán)形鏈表的順序是0-1-2-3，對(duì)于cpu1的MC domain，其groups環(huán)形鏈表的順序是1-2-3-0，以此類推。大核MC domain也是類似，這里不再贅述。

對(duì)于非base domain而言，其sched group有多個(gè)cpu，覆蓋其child domain的所有cpu。例如上面圖例中的DIE domain，它有兩個(gè)child domain，分別是大核domain和小核domian，因此，DIE domain的groups環(huán)形鏈表有兩個(gè)元素，分別是小核group和大核group。

不同CPU的DIE domain的環(huán)形鏈表首元素（即鏈表頭）是不同的，對(duì)于cpu0的DIE domain，其groups環(huán)形鏈表的順序是（0,1,2,3）--（4,5,6,7），對(duì)于cpu6的MC domain，其groups環(huán)形鏈表的順序是（4,5,6,7）--（0,1,2,3），以此類推。

為了減少鎖的競(jìng)爭(zhēng)，每一個(gè)cpu都有自己的MC domain、DIE domain以及sched group，并且形成了sched domain之間的層級(jí)結(jié)構(gòu)，sched group的環(huán)形鏈表結(jié)構(gòu)。

2、負(fù)載均衡的基本過(guò)程

負(fù)載均衡不是一個(gè)全局CPU之間的均衡，實(shí)際上那樣做也不現(xiàn)實(shí)，當(dāng)系統(tǒng)的CPU數(shù)量較大的時(shí)候，很難一次性的完成所有CPU之間的均衡，這也是提出sched domain的原因之一。

當(dāng)一個(gè)CPU上進(jìn)行負(fù)載均衡的時(shí)候，我們總是從base domain開(kāi)始（對(duì)于上面的例子，base domain就是MC domain），檢查其所屬sched group之間（即各個(gè)cpu之間）的負(fù)載均衡情況，如果有不均衡情況，那么會(huì)在該cpu所屬cluster之間進(jìn)行遷移，以便維護(hù)cluster內(nèi)各個(gè)cpu core的任務(wù)負(fù)載均衡。有了各個(gè)CPU上的負(fù)載統(tǒng)計(jì)以及CPU的算力信息，我們很容易知道MC domain上的不均衡情況。

為了讓算法更加簡(jiǎn)單，Linux內(nèi)核的負(fù)載均衡算法只允許CPU拉任務(wù)，這樣，MC domain的均衡大致需要下面幾個(gè)步驟：

（1）找到MC domain中最繁忙的sched group；

（2）找到最繁忙sched group中最繁忙的CPU（對(duì)于MC domain而言，這一步不存在，畢竟其sched group只有一個(gè)cpu）；

（3）從選中的那個(gè)繁忙的cpu上拉取任務(wù)，具體拉取多少的任務(wù)到本CPU runqueue上是和不均衡的程度相關(guān)，越是不均衡，拉取的任務(wù)越多。

完成MC domain均衡之后，繼續(xù)沿著sched domain層級(jí)結(jié)構(gòu)向上檢查，進(jìn)入DIE domain，在這個(gè)level的domain上，我們?nèi)匀粰z查其所屬sched group之間（即各個(gè)cluster之間）的負(fù)載均衡情況，如果有不均衡的情況，那么會(huì)進(jìn)行inter-cluster的任務(wù)遷移。基本方法和MC domain類似，只不過(guò)在計(jì)算均衡的時(shí)候，DIE domain不再考慮單個(gè)CPU的負(fù)載和算力，它考慮的是：

（1）該sched group的負(fù)載，即sched group中所有CPU負(fù)載之和；

（2）該sched group的算力，即sched group中所有CPU算力之和；

2、其他需要考慮的事項(xiàng)

之所以要進(jìn)行負(fù)載均衡主要是為了系統(tǒng)整體的throughput，避免出現(xiàn)一核有難，七核圍觀的狀況。然而，進(jìn)行負(fù)載均衡本身需要額外的算力開(kāi)銷，為了降低開(kāi)銷，我們?yōu)椴煌琹evel的sched domain定義了時(shí)間間隔，不能太密集的進(jìn)行負(fù)載均衡。之外，我們還定義了不均衡的門限值，也就是說(shuō)domain的group之間如果有較小的不均衡，我們也是可以允許的，超過(guò)了門限值才發(fā)起負(fù)載均衡的操作。很顯然，越高level的sched domain其不均衡的threashhold越高，越高level的均衡會(huì)帶來(lái)更大的性能開(kāi)銷。

在引入異構(gòu)計(jì)算系統(tǒng)之后，任務(wù)在placement的時(shí)候可以有所選擇。如果負(fù)載比較輕，或者該任務(wù)對(duì)延遲要求不高，我們可以放置在小核CPU執(zhí)行，如果負(fù)載比較重或者該該任務(wù)和用戶體驗(yàn)相關(guān)，那么我們傾向于讓它在算力更高的CPU上執(zhí)行。為了應(yīng)對(duì)這種狀況，內(nèi)核引入了misfit task的概念。一旦任務(wù)被標(biāo)記了misfit task，那么負(fù)載均衡算法要考慮及時(shí)的將該任務(wù)進(jìn)行upmigration，從而讓重載任務(wù)盡快完成，或者提升該任務(wù)的執(zhí)行速度，從而提升用戶體驗(yàn)。

除了性能，負(fù)載均衡也會(huì)帶來(lái)功耗的收益。例如系統(tǒng)有4個(gè)CPU，共計(jì)8個(gè)進(jìn)入執(zhí)行態(tài)的任務(wù)。這些任務(wù)在4個(gè)CPU上的排布有兩種選擇：

（1）全部放到一個(gè)CPU上；

（2）每個(gè)CPU runqueue掛2個(gè)任務(wù)。

負(fù)載均衡算法會(huì)讓任務(wù)均布，從而帶來(lái)功耗的收益。雖然方案一中有三個(gè)CPU是處于idle狀態(tài)的，但是那個(gè)繁忙CPU運(yùn)行在更高的頻率上。而方案二中，由于任務(wù)均布，CPU處于較低的頻率運(yùn)行，功耗會(huì)比方案一更低。

四、負(fù)載均衡場(chǎng)景分析

1、整體的場(chǎng)景描述

在linux內(nèi)核中，為了讓任務(wù)均衡的分布在系統(tǒng)的所有CPU上，我們主要考慮下面三個(gè)場(chǎng)景：

（1）負(fù)載均衡（load balance）。通過(guò)搬移cpu runqueue上的任務(wù)，讓各個(gè)CPU上的負(fù)載匹配CPU算力。

（2）任務(wù)放置（task placement）。當(dāng)阻塞的任務(wù)被喚醒的時(shí)候，確定該任務(wù)應(yīng)該放置在那個(gè)CPU上執(zhí)行。

（3）主動(dòng)均衡（active upmigration）。當(dāng)一個(gè)低算力CPU的runqueue中出現(xiàn)misfit task的時(shí)候，如果該任務(wù)持續(xù)執(zhí)行，那么負(fù)載均衡無(wú)能為力，因?yàn)樗回?fù)責(zé)遷移runnable狀態(tài)的任務(wù)。這種場(chǎng)景下，active upmigration可以把當(dāng)前正在運(yùn)行的misfit task向上遷移到算力更高的CPU上去。

2、Task placement

任務(wù)放置主要發(fā)生在：

（1）喚醒一個(gè)新fork的線程；

（2）Exec一個(gè)線程的時(shí)候；

（3）喚醒一個(gè)阻塞的進(jìn)程。

在上面的三個(gè)場(chǎng)景中都會(huì)調(diào)用select_task_rq來(lái)為task選擇一個(gè)適合的CPU core。

3、Load balance

Load balance主要有三種：

（1）在tick中觸發(fā)load balance。我們稱之tick load balance或者periodic load balance。具體的代碼執(zhí)行路徑是：

（2）調(diào)度器在pick next的時(shí)候，當(dāng)前cfs runque中沒(méi)有runnable，只能執(zhí)行idle線程，讓CPU進(jìn)入idle狀態(tài)。我們稱之new idle load balance。具體的代碼執(zhí)行路徑是：

（3）其他的cpu已經(jīng)進(jìn)入idle，本CPU任務(wù)太重，需要通過(guò)ipi將其idle的cpu喚醒來(lái)進(jìn)行負(fù)載均衡。我們稱之idle load banlance，具體的代碼執(zhí)行路徑是：

如果沒(méi)有dynamic tick特性，那么其實(shí)不需要進(jìn)行idle load balance，因?yàn)閠ick會(huì)喚醒處于idle的cpu，從而周期性tick就可以覆蓋這個(gè)場(chǎng)景。

4、Active upmigration

主動(dòng)遷移是Load balance的一種特殊場(chǎng)景。在負(fù)載均衡中，只要運(yùn)用適當(dāng)?shù)耐綑C(jī)制（持有一個(gè)或者多個(gè)rq lock），runnable的任務(wù)可以在各個(gè)CPU runqueue之間移動(dòng)，然而running的任務(wù)是例外，它不掛在CPU runqueue中，load balance無(wú)法覆蓋。為了能夠遷移running狀態(tài)的任務(wù)，內(nèi)核提供了Active upmigration的方法（利用stop machine調(diào)度類）。