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

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

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

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

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

在CPU利用率沒有達到100%的時候，利用率基本上等于負(fù)載，一旦當(dāng)CPU利用率達到了100%的時候，利用率其實是無法給出CPU負(fù)載的狀況，因為大家的利用率都是100%，利用率相等，但是并不意味著CPUs的負(fù)載也是相等的，因為這時候不同CPU上runqueue中等待執(zhí)行的任務(wù)數(shù)目不同，直覺上runque上掛著10任務(wù)的CPU承壓比掛著5個任務(wù)的CPU的負(fù)載要更重一些。因此，早期的CPU負(fù)載是使用runqueue深度來描述的。

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

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

2、什么是均衡

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

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

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

有了任務(wù)負(fù)載就可以得到CPU負(fù)載，配合系統(tǒng)中各個CPU的算力，看起來我們就可以完成負(fù)載均衡的工作，然而事情沒有那么簡單，當(dāng)負(fù)載不均衡的時候，任務(wù)需要在CPU之間遷移，不同形態(tài)的遷移會有不同的開銷。例如一個任務(wù)在小核cluster上的CPU之間的遷移所帶來的性能開銷一定是小于任務(wù)從小核cluster的CPU遷移到大核cluster的開銷。因此，為了更好的執(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很忙，我們把之前運行在該CPU上的一個任務(wù)遷移到新的CPU上的時候，如果遷移到新的CPU是和原來的CPU在不同的cluster中，性能會受影響（因為會cache flush）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們以一個4小核+4大核的處理器來描述CPU的domain和group：

在上面的結(jié)構(gòu)中，sched domain是分成兩個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。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2、其他需要考慮的事項

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

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

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

（1）全部放到一個CPU上；

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

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

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

1、整體的場景描述

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

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

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

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

2、Task placement

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

（1）喚醒一個新fork的線程；

（2）Exec一個線程的時候；

（3）喚醒一個阻塞的進程。

在上面的三個場景中都會調(diào)用select_task_rq來為task選擇一個適合的CPU core。

3、Load balance

Load balance主要有三種：

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

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

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

如果沒有dynamic tick特性，那么其實不需要進行idle load balance，因為tick會喚醒處于idle的cpu，從而周期性tick就可以覆蓋這個場景。

4、Active upmigration

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