在當(dāng)今的計(jì)算機(jī)領(lǐng)域，多核CPU早已成為主流配置。從早期的單核處理器到如今的 8 核、16 核甚至更多核心的CPU，硬件性能得到了極大提升。這種多核架構(gòu)為計(jì)算機(jī)系統(tǒng)帶來了強(qiáng)大的并行處理能力，使得多個(gè)任務(wù)可以同時(shí)高效運(yùn)行。然而，多核 CPU 的性能優(yōu)勢(shì)并非能自動(dòng)實(shí)現(xiàn)，如何充分利用這些核心資源，讓各個(gè)進(jìn)程在不同核心上合理分配與運(yùn)行，成為了操作系統(tǒng)必須解決的關(guān)鍵問題。

在眾多操作系統(tǒng)中，Linux 以其開源、穩(wěn)定和高效等特點(diǎn)，被廣泛應(yīng)用于服務(wù)器、嵌入式設(shè)備以及超級(jí)計(jì)算機(jī)等領(lǐng)域。而 Linux 內(nèi)核進(jìn)程 CPU 負(fù)載均衡機(jī)制，就是其充分發(fā)揮多核 CPU 性能的核心技術(shù)之一。這一機(jī)制就像是一位智能的調(diào)度大師，時(shí)刻監(jiān)控著系統(tǒng)中各個(gè)進(jìn)程的運(yùn)行狀態(tài)以及各個(gè) CPU 核心的負(fù)載情況，然后巧妙地將進(jìn)程分配到最合適的 CPU 核心上運(yùn)行，確保系統(tǒng)資源得到充分利用，避免出現(xiàn)某些核心忙得不可開交，而另一些核心卻閑置無事的尷尬局面。

接下來，就讓我們一起深入探索 Linux 內(nèi)核進(jìn)程 CPU 負(fù)載均衡機(jī)制，揭開它神秘的面紗，了解它是如何在幕后默默工作，為我們帶來高效穩(wěn)定的系統(tǒng)體驗(yàn)的。

一、CPU負(fù)載均衡機(jī)制

1.1什么是 CPU 負(fù)載

在深入探討 Linux 內(nèi)核進(jìn)程 CPU 負(fù)載均衡機(jī)制之前，我們先來明確一個(gè)關(guān)鍵概念 ——CPU 負(fù)載。CPU 負(fù)載常常容易與 CPU 使用率、利用率混淆 ，這里我們來詳細(xì)區(qū)分一下。CPU 利用率是指 CPU 處于忙碌狀態(tài)的時(shí)間占總時(shí)間的比例。比如在 1000ms 的時(shí)間窗口內(nèi)，如果 CPU 執(zhí)行任務(wù)的時(shí)間為 500ms，處于空閑（idle）狀態(tài)的時(shí)間也是 500ms，那么該時(shí)間段內(nèi) CPU 的利用率就是 50%。在 CPU 利用率未達(dá)到 100% 時(shí)，利用率與負(fù)載大致相等。

但當(dāng) CPU 利用率達(dá)到 100% 時(shí)，利用率就無法準(zhǔn)確反映 CPU 負(fù)載狀況了。因?yàn)榇藭r(shí)不同 CPU 上的運(yùn)行隊(duì)列（runqueue）中等待執(zhí)行的任務(wù)數(shù)目可能不同，直觀來說，runqueue 中掛著 10 個(gè)任務(wù)的 CPU，其負(fù)載明顯要比掛著 5 個(gè)任務(wù)的 CPU 更重。

早期，CPU 負(fù)載是用 runqueue 深度來描述的，也就是運(yùn)行隊(duì)列中等待執(zhí)行的任務(wù)數(shù)量。不過這種方式比較粗略，例如 CPU A 和 CPU B 上都掛了 1 個(gè)任務(wù)，但 A 上的任務(wù)是重載任務(wù)，B 上的是經(jīng)常處于睡眠（sleep）狀態(tài)的輕載任務(wù)，僅依據(jù) runqueue 深度來判斷 CPU 負(fù)載就不準(zhǔn)確了。

現(xiàn)代調(diào)度器通常使用 CPU runqueue 上所有任務(wù)負(fù)載之和來表示 CPU 負(fù)載 ，這樣一來，對(duì) CPU 負(fù)載的跟蹤就轉(zhuǎn)變?yōu)閷?duì)任務(wù)負(fù)載的跟蹤。在 3.8 版本的 Linux 內(nèi)核中，引入了 PELT（per entity load tracking）算法，該算法能夠跟蹤每一個(gè)調(diào)度實(shí)體（sched entity）的負(fù)載，將負(fù)載跟蹤算法從基于每個(gè) CPU（per-CPU）進(jìn)化到基于每個(gè)調(diào)度實(shí)體（per-entity）。PELT 算法不僅能知曉 CPU 的負(fù)載情況，還能明確負(fù)載來自哪個(gè)調(diào)度實(shí)體，從而實(shí)現(xiàn)更精準(zhǔn)的負(fù)載均衡。

1.2何為均衡

明確了 CPU 負(fù)載的概念后，我們?cè)賮碚務(wù)?“均衡”。負(fù)載均衡并非簡(jiǎn)單地將系統(tǒng)的總負(fù)載平均分配到各個(gè) CPU 上。實(shí)際上，我們必須充分考慮系統(tǒng)中各個(gè) CPU 的算力，使每個(gè) CPU 所承擔(dān)的負(fù)載與其算力相匹配。例如，在一個(gè)擁有 6 個(gè)小核和 2 個(gè)大核的系統(tǒng)中，假設(shè)系統(tǒng)總負(fù)載為 800，如果簡(jiǎn)單地給每個(gè) CPU 分配 100 的負(fù)載，這其實(shí)是不均衡的，因?yàn)榇蠛?CPU 能夠提供更強(qiáng)的計(jì)算能力。

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

在考慮 CFS（Completely Fair Scheduler，完全公平調(diào)度器）任務(wù)的均衡時(shí)，還需要把 CPU 用于執(zhí)行實(shí)時(shí)任務(wù)（RT，Real - Time）和中斷請(qǐng)求（irq）的算力去掉，使用該 CPU 可用于 CFS 的算力 。所以，CFS 任務(wù)均衡中使用的 CPU 算力是一個(gè)不斷變化的值，需要經(jīng)常更新。為了便于對(duì)比 CPU 算力和任務(wù)負(fù)載，我們采用歸一化的方式，將系統(tǒng)中處理能力最強(qiáng)且運(yùn)行在最高頻率的 CPU 算力設(shè)定為 1024，其他 CPU 的算力則根據(jù)其微架構(gòu)和運(yùn)行頻率進(jìn)行相應(yīng)調(diào)整。

有了任務(wù)負(fù)載和 CPU 算力，看似就能完成負(fù)載均衡工作了，但實(shí)際情況更為復(fù)雜。當(dāng)負(fù)載不均衡時(shí)，任務(wù)需要在 CPU 之間遷移，而不同形態(tài)的遷移會(huì)產(chǎn)生不同的開銷。比如，一個(gè)任務(wù)在小核集群內(nèi)的 CPU 之間遷移，其性能開銷肯定小于從小核集群的 CPU 遷移到大核集群的開銷。因此，為了更有效地執(zhí)行負(fù)載均衡，調(diào)度域（scheduling domain）和調(diào)度組（scheduling group）的概念被引入。調(diào)度域是一組 CPU 的集合，這些 CPU 在拓?fù)浣Y(jié)構(gòu)、性能等方面具有相似性；調(diào)度組則是在調(diào)度域內(nèi)，根據(jù)更細(xì)粒度的規(guī)則劃分的 CPU 集合。通過合理劃分調(diào)度域和調(diào)度組，可以更精準(zhǔn)地控制任務(wù)在 CPU 之間的遷移，降低遷移開銷，實(shí)現(xiàn)更高效的負(fù)載均衡。

1.3何為負(fù)載

「負(fù)載」可不等同于 CPU 占用率，它衡量的是已經(jīng) ready，但在一段時(shí)間內(nèi)得不到執(zhí)行機(jī)會(huì)的任務(wù)數(shù)量。如果把CPU 比做車道的話，當(dāng)有車輛排隊(duì)等著進(jìn)入這個(gè)車道，那負(fù)載就大于 1，反之則小于 1，它體現(xiàn)的其實(shí)是一種擁塞程度。

在 Linux 系統(tǒng)中，使用 "top" 或者 "w" 命令可以看到最近 1 分鐘、5 分鐘和 15 分鐘的平均負(fù)載（沒有做歸一化處理，需要自己除以 CPU 的數(shù)目）。借助不同統(tǒng)計(jì)時(shí)段的平均負(fù)載值，還可以觀察出負(fù)載變化的趨勢(shì)。

一般認(rèn)為，負(fù)載值大于 0.7 就應(yīng)該引起注意，但對(duì)于 Linux 系統(tǒng)來說，情況可能有所不同，因?yàn)?Linux 中統(tǒng)計(jì)的負(fù)載值，除了處于就緒態(tài)的任務(wù)，還包括了處于 uninterruptible 狀態(tài)、等待 I/O 的任務(wù)。

for_each_possible_cpu(cpu)
    nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
avenrun[n] = avenrun[0]exp_n + nr_active(1 - exp_n)

所以確切地說它不僅是 CPU load，而是 system load。如果因?yàn)?uninterruptible 的任務(wù)較多造成負(fù)載值看起來偏高，實(shí)際的系統(tǒng)在使用上也不見得就會(huì)出現(xiàn)明顯的卡頓。

負(fù)載均衡有兩種方式：pull, push

• pull拉：負(fù)載輕的CPU，從負(fù)載繁重的CPU pull tasks來運(yùn)行。這應(yīng)該是主要的方式，因?yàn)椴粦?yīng)該讓負(fù)載本身就繁重的CPU執(zhí)行負(fù)載均衡任務(wù)。相應(yīng)的為load balance。
• push推：負(fù)載重的CPU，向負(fù)載輕的CPU，推送tasks由其幫忙執(zhí)行。相應(yīng)的為active balance。

但是遷移是有代價(jià)的。在同一個(gè)物理CPU的兩個(gè)logical core之間遷移，因?yàn)楣蚕韈ache，代價(jià)相對(duì)較小。如果是在兩個(gè)物理CPU之間遷移，代價(jià)就會(huì)增大。更進(jìn)一步，對(duì)于NUMA系統(tǒng)，在不同node之間的遷移將帶來更大的損失；這其實(shí)形成了一個(gè)調(diào)度上的約束，在Linux中被實(shí)現(xiàn)為"sched domain"，并以hierarchy的形式組織。處于同一內(nèi)層domain的，遷移可以更頻繁地進(jìn)行，越往外層，遷移則應(yīng)盡可能地避免。

1.4負(fù)載均衡的作用

負(fù)載均衡在 Linux 系統(tǒng)中起著至關(guān)重要的作用，對(duì)系統(tǒng)性能和穩(wěn)定性有著顯著的提升。如果沒有有效的負(fù)載均衡機(jī)制，當(dāng)系統(tǒng)中某個(gè) CPU 核心的負(fù)載過高，而其他核心卻閑置時(shí)，就會(huì)導(dǎo)致整個(gè)系統(tǒng)性能下降。高負(fù)載的核心可能會(huì)因?yàn)槿蝿?wù)過多而出現(xiàn)響應(yīng)變慢、處理延遲等問題，嚴(yán)重時(shí)甚至可能導(dǎo)致系統(tǒng)崩潰。

例如，在一個(gè) Web 服務(wù)器中，如果所有的 HTTP 請(qǐng)求處理任務(wù)都集中在某一個(gè) CPU 核心上，隨著請(qǐng)求量的增加，這個(gè)核心很快就會(huì)不堪重負(fù)，服務(wù)器的響應(yīng)時(shí)間會(huì)大幅延長(zhǎng)，用戶訪問網(wǎng)站時(shí)會(huì)感覺到明顯的卡頓，甚至無法訪問。

而通過負(fù)載均衡機(jī)制，將這些任務(wù)均勻地分配到各個(gè) CPU 核心上，每個(gè)核心都能充分發(fā)揮其計(jì)算能力，共同承擔(dān)系統(tǒng)的工作負(fù)載。這樣不僅可以避免單個(gè)核心過度勞累，還能大大提高系統(tǒng)的整體處理能力和響應(yīng)速度。以剛才的 Web 服務(wù)器為例，負(fù)載均衡機(jī)制會(huì)將 HTTP 請(qǐng)求合理地分發(fā)到多個(gè) CPU 核心上進(jìn)行處理，每個(gè)核心都能高效地處理一部分請(qǐng)求，服務(wù)器就能快速響應(yīng)用戶的訪問，提升用戶體驗(yàn)。

負(fù)載均衡還有助于提高系統(tǒng)資源的利用率。在多核 CPU 系統(tǒng)中，每個(gè)核心都是寶貴的資源。通過負(fù)載均衡，能夠確保這些資源得到充分利用，避免出現(xiàn)資源閑置浪費(fèi)的情況。當(dāng)一個(gè) CPU 核心的負(fù)載過高時(shí)，負(fù)載均衡機(jī)制會(huì)將部分任務(wù)遷移到其他相對(duì)空閑的核心上，使得整個(gè)系統(tǒng)的資源分配更加合理，從而提高系統(tǒng)的整體運(yùn)行效率。這就好比一個(gè)工廠里有多個(gè)工人（CPU 核心），如果所有的工作都交給一個(gè)工人做，其他工人卻閑著沒事干，那顯然是對(duì)人力資源的浪費(fèi)。而通過合理的任務(wù)分配（負(fù)載均衡），讓每個(gè)工人都能承擔(dān)適量的工作，就能充分發(fā)揮整個(gè)工廠的生產(chǎn)能力。

1.5為何均衡

作為OS的心跳，只要不是NO_HZ的CPU，tick都會(huì)如約而至，這為判斷是否需要均衡提供了一個(gè)絕佳的時(shí)機(jī)。不過，如果在每次tick時(shí)鐘中斷都去做一次balance，那開銷太大了，所以balance的觸發(fā)是有一個(gè)周期要求的。當(dāng)tick到來的時(shí)候，在scheduler_tick函數(shù)中會(huì)調(diào)用trigger_load_balance來觸發(fā)周期性負(fù)載均衡，相關(guān)的代碼如下：

void scheduler_tick(void)
{
...
#ifdef CONFIG_SMP
	rq->idle_balance = idle_cpu(cpu);
	trigger_load_balance(rq);
#endif
}

void trigger_load_balance(struct rq *rq)
{
	/*
	 * Don't need to rebalance while attached to NULL domain or
	 * runqueue CPU is not active
	 */
	if (unlikely(on_null_domain(rq) || !cpu_active(cpu_of(rq))))
		return;
	/* 觸發(fā)periodic balance */
	if (time_after_eq(jiffies, rq->next_balance))
		raise_softirq(SCHED_SOFTIRQ);
  /* -觸發(fā)nohz idle balance */
	nohz_balancer_kick(rq);
}

進(jìn)行調(diào)度和均衡本身也是需要消耗CPU的資源，因此比較適合交給idle的CPU來完成，idle_cpu被選中的這個(gè)idle CPU被叫做"idle load balancer"。

系統(tǒng)中有多個(gè)idle的cpu，如何選擇執(zhí)行nohz idle balance的那個(gè)CPU呢？

如果不考慮功耗，那么就從所有idle cpu中選擇一個(gè)就可以了，但是在異構(gòu)的系統(tǒng)中，我們應(yīng)該要考慮的更多，如果idle cpu中有大核也有小核，是選擇大核還是選擇小核？大核CPU雖然算力強(qiáng)，但是功耗高。如果選擇小核，雖然能省功耗，但是提供的算力是否足夠。標(biāo)準(zhǔn)內(nèi)核選擇的最簡(jiǎn)單的算法：隨便選擇一個(gè)idle cpu（也就是idle cpu mask中的第一個(gè)）。

1.6如何均衡

要實(shí)現(xiàn)多核系統(tǒng)的負(fù)載均衡，主要依靠 task 在不同 CPU 之間的遷移（migration），也就是將一個(gè) task 從負(fù)載較重的 CPU 上轉(zhuǎn)移到負(fù)載相對(duì)較輕的 CPU 上去執(zhí)行。從 CPU 的 runqueue 上取下來的這個(gè)動(dòng)作，稱為 "pull"，放到另一個(gè) CPU 的 runqueue 上去，則稱之為 "push"。

但是遷移是有代價(jià)的，而且這個(gè)遷移的代價(jià)還不一樣。AMP 系統(tǒng)里每個(gè) CPU 的 capacity 可能不同，而 SMP 系統(tǒng)里看起來每個(gè) CPU 都是一樣的，按理好像應(yīng)該視作一個(gè)數(shù)組，拉通來調(diào)度。但現(xiàn)實(shí)是：現(xiàn)代 SMP 的拓?fù)浣Y(jié)構(gòu)，決定了 CPU 之間的 cache 共享是不同的，cache 共享越多，遷移的“阻力”越小，反之就越大。

在同一個(gè)物理 core 的兩個(gè) logical CPU 之間遷移，因?yàn)楣蚕?L1 和 L2 cache，阻力相對(duì)較小。對(duì)于NUMA系統(tǒng)，如果是在同一 node 中的兩個(gè)物理 core 之間遷移，共享的是 L3 cache 和內(nèi)存，損失就會(huì)增大（AMD 的 Zen 系列芯片存在同一 node 的物理 core 不共享 L3 的情況）。更進(jìn)一步，在不同 node 之間的遷移將付出更大的代價(jià)。

就像一個(gè)人換工作的時(shí)候，往往會(huì)優(yōu)先考慮同一個(gè)公司的內(nèi)部職位，因?yàn)橹皇寝D(zhuǎn)崗的話，公司內(nèi)的各種環(huán)境都是熟悉的。再是考慮同一個(gè)城市的其他公司，因?yàn)椴挥冒峒衣??？赡茏詈蟛攀强紤]其他城市/國(guó)家的，畢竟 relocate 牽扯的事情還是蠻多的。

二、CPU負(fù)載均衡機(jī)制原理

2.1相關(guān)數(shù)據(jù)結(jié)構(gòu)與關(guān)鍵函數(shù)

在 Linux 內(nèi)核進(jìn)程 CPU 負(fù)載均衡機(jī)制中，有一些關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)和函數(shù)起著至關(guān)重要的作用。

runqueue 隊(duì)列是其中一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)。在多處理器系統(tǒng)中，每個(gè) CPU 都擁有自己的 runqueue 隊(duì)列 ，這個(gè)隊(duì)列就像是一個(gè)任務(wù)等待執(zhí)行的 “候診室”，里面存放著處于運(yùn)行狀態(tài)（run）的進(jìn)程鏈表。當(dāng)一個(gè)進(jìn)程準(zhǔn)備好運(yùn)行時(shí)，它就會(huì)被加入到某個(gè) CPU 的 runqueue 隊(duì)列中。例如，當(dāng)我們?cè)谙到y(tǒng)中啟動(dòng)一個(gè)新的應(yīng)用程序時(shí)，該程序?qū)?yīng)的進(jìn)程就會(huì)被添加到某個(gè) CPU 的 runqueue 隊(duì)列里，等待 CPU 的調(diào)度執(zhí)行。

調(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是和原來的CPU在不同的cluster中，性能會(huì)受影響（因?yàn)闀?huì)cache會(huì)變冷）。但是對(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)。為了解決這些問題，linux內(nèi)核引入了sched_domain的概念。

調(diào)度組： 調(diào)度組是組成調(diào)度域的基本單位，在最小的調(diào)度域中一個(gè)cpu core是一個(gè)調(diào)度組，在最大的調(diào)度域中，一個(gè)NUMA結(jié)點(diǎn)內(nèi)的所有cpu core成一個(gè)調(diào)度組。

sched_domain（調(diào)度域）也是一個(gè)核心數(shù)據(jù)結(jié)構(gòu)。為了適應(yīng)多種多處理器模型，Linux 引入了調(diào)度域及組的概念。一個(gè)調(diào)度域可以包含其他的調(diào)度域或者多個(gè)組 ，它是一組 CPU 的集合，這些 CPU 在拓?fù)浣Y(jié)構(gòu)、性能等方面具有相似性。通過調(diào)度域，內(nèi)核能夠更好地管理和協(xié)調(diào)不同 CPU 之間的負(fù)載均衡。

例如，在一個(gè)具有多個(gè) CPU 核心的系統(tǒng)中，可能會(huì)根據(jù) CPU 的性能和拓?fù)潢P(guān)系，將某些核心劃分為一個(gè)調(diào)度域，這樣在進(jìn)行負(fù)載均衡時(shí)，可以優(yōu)先在這個(gè)調(diào)度域內(nèi)進(jìn)行任務(wù)的遷移和分配，減少跨調(diào)度域遷移帶來的開銷。

調(diào)度域的數(shù)據(jù)結(jié)構(gòu)定義如下：

struct sched_domain {
    struct sched_domain *parent; // 指向父調(diào)度域
    struct sched_group *groups;  // 該調(diào)度域所包含的組
    cpumask_t span; 
    unsigned long min_interval; // 最小時(shí)間間隔，用于檢查負(fù)載均衡操作時(shí)機(jī)
    unsigned long max_interval; 
    unsigned int busy_factor;   // 忙碌時(shí)負(fù)載均衡時(shí)間間隔乘數(shù)
    unsigned int imbalance_pct; 
    unsigned long long cache_hot_time;
    unsigned int cache_nice_tries;
    unsigned int per_cpu_gain;
    int flags;
    unsigned long last_balance;
    unsigned int balance_interval;  // 負(fù)載均衡進(jìn)行的時(shí)間間隔
    unsigned int nr_balance_failed; // 負(fù)載均衡遷移進(jìn)程失敗的次數(shù)
};

調(diào)度域并不是一個(gè)平層結(jié)構(gòu)，而是根據(jù)CPU拓?fù)湫纬蓪蛹?jí)結(jié)構(gòu)。相對(duì)應(yīng)的，負(fù)載均衡也不是一蹴而就的，而是會(huì)在多個(gè)sched domain中展開（例如從base domain開始，一直到頂層sched domain，逐個(gè)domain進(jìn)行均衡）。

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

• Parent和child：Sched domain會(huì)形成層級(jí)結(jié)構(gòu)，parent和child建立了不同層級(jí)結(jié)構(gòu)的父子關(guān)系。對(duì)于base domain而言，其child等于NULL，對(duì)于top domain而言，其parent等于NULL。
• groups：一個(gè)調(diào)度域中有若干個(gè)調(diào)度組，這些調(diào)度組形成一個(gè)環(huán)形鏈表，groups成員就是鏈表頭。
• min_interval和max_interval：做均衡也是需要開銷的，我們不可能時(shí)刻去檢查調(diào)度域的均衡狀態(tài)，這兩個(gè)參數(shù)定義了檢查該sched domain均衡狀態(tài)的時(shí)間間隔范圍。
• busy_factor：正常情況下，balance_interval定義了均衡的時(shí)間間隔，如果cpu繁忙，那么均衡要時(shí)間間隔長(zhǎng)一些，即時(shí)間間隔定義為busy_factor x balance_interval。
• imbalance_pct：調(diào)度域內(nèi)的不均衡狀態(tài)達(dá)到了一定的程度之后就開始進(jìn)行負(fù)載均衡的操作。imbalance_pct這個(gè)成員定義了判定不均衡的門限。
• cache_nice_tries：這個(gè)成員應(yīng)該是和nr_balance_failed配合控制負(fù)載均衡過程的遷移力度。當(dāng)nr_balance_failed大于cache_nice_tries的時(shí)候，負(fù)載均衡會(huì)變得更加激進(jìn)。
• nohz_idle：每個(gè)cpu都有其對(duì)應(yīng)的LLC sched domain，而LLC SD記錄對(duì)應(yīng)cpu的idle狀態(tài)（是否tick被停掉），進(jìn)一步得到該domain中busy cpu的個(gè)數(shù)，體現(xiàn)在（sd->shared->nr_busy_cpus）。
• flags：調(diào)度域標(biāo)志，下面有表格詳細(xì)描述。
• level：該sched domain在整個(gè)調(diào)度域?qū)蛹?jí)結(jié)構(gòu)中的level。Base sched domain的level等于0，向上依次加一。
• last_balance：上次進(jìn)行balance的時(shí)間點(diǎn)。通過基礎(chǔ)均衡時(shí)間間隔（）和當(dāng)前sd的狀態(tài)可以計(jì)算最終的均衡間隔時(shí)間（get_sd_balance_interval），last_balance加上這個(gè)計(jì)算得到的均衡時(shí)間間隔就是下一次均衡的時(shí)間點(diǎn)。
• balance_interval：定義了該sched domain均衡的基礎(chǔ)時(shí)間間隔
• nr_balance_failed：本sched domain中進(jìn)行負(fù)載均衡失敗的次數(shù)。當(dāng)失敗次數(shù)大于cache_nice_tries的時(shí)候，我們考慮遷移cache hot的任務(wù)，進(jìn)行更激進(jìn)的均衡操作。
• max_newidle_lb_cost：在該domain上進(jìn)行newidle balance的最大時(shí)間長(zhǎng)度（即newidle balance的開銷）。最小值是sysctl_sched_migration_cost。
• next_decay_max_lb_cost：max_newidle_lb_cost會(huì)記錄最近在該sched domain上進(jìn)行newidle balance的最大時(shí)間長(zhǎng)度，這個(gè)max cost不是一成不變的，它有一個(gè)衰減過程，每秒衰減1%，這個(gè)成員就是用來控制衰減的。
• avg_scan_cost：平均掃描成本

調(diào)度域并不是一個(gè)平層結(jié)構(gòu)，而是根據(jù)CPU拓?fù)湫纬蓪蛹?jí)結(jié)構(gòu)。相對(duì)應(yīng)的，負(fù)載均衡也不是一蹴而就的，而是會(huì)在多個(gè)sched domain中展開（例如從base domain開始，一直到頂層sched domain，逐個(gè)domain進(jìn)行均衡）。具體如何進(jìn)行均衡（自底向上還是自頂向下，在哪些domain中進(jìn)行均衡）是和均衡類型和各個(gè)sched domain設(shè)置的flag相關(guān)，具體細(xì)節(jié)后面會(huì)描述。

在指定調(diào)度域內(nèi)進(jìn)行均衡的時(shí)候不考慮系統(tǒng)中其他調(diào)度域的CPU負(fù)載情況，只考慮該調(diào)度域內(nèi)的sched group之間的負(fù)載是否均衡。對(duì)于base doamin，其所屬的sched group中只有一個(gè)cpu，對(duì)于更高level的sched domain，其所屬的sched group中可能會(huì)有多個(gè)cpu core。

與之相關(guān)的是 sched_group（調(diào)度組），一個(gè)組通常包含一個(gè)或者多個(gè) CPU 。組的數(shù)據(jù)結(jié)構(gòu)通過cpumask_t來表示該組所包含的 CPU，還通過next指針將多個(gè)sched_group串到調(diào)度域的鏈表上面。其數(shù)據(jù)結(jié)構(gòu)定義如下：

struct sched_group {
    struct sched_group *next; // 用于將sched_group串到調(diào)度域鏈表
    cpumask_t cpumask; // 表示該group所包含的cpu
    unsigned long cpu_power; // 通常是cpu的個(gè)數(shù)
};

在函數(shù)方面，load_balance函數(shù)是實(shí)現(xiàn)負(fù)載均衡的關(guān)鍵函數(shù)之一。當(dāng)系統(tǒng)檢測(cè)到 CPU 負(fù)載不均衡時(shí)，就會(huì)調(diào)用load_balance函數(shù)。它的主要工作是尋找最繁忙的 CPU 組中的最繁忙的 CPU ，然后將其進(jìn)程遷移一部分到其他相對(duì)空閑的 CPU 上。例如，在一個(gè)四核系統(tǒng)中，如果發(fā)現(xiàn) CPU0 的負(fù)載過高，而 CPU1、CPU2 和 CPU3 相對(duì)空閑，load_balance函數(shù)就會(huì)嘗試從 CPU0 的 runqueue 隊(duì)列中挑選一些進(jìn)程，遷移到 CPU1、CPU2 或 CPU3 的 runqueue 隊(duì)列中，以實(shí)現(xiàn)負(fù)載的均衡。

rebalance_tick函數(shù)也在負(fù)載均衡中扮演著重要角色。每經(jīng)過一次時(shí)鐘中斷，scheduler_tick函數(shù)就會(huì)調(diào)用rebalance_tick函數(shù) 。rebalance_tick函數(shù)會(huì)從最底層的調(diào)度域開始，一直到最上層的調(diào)度域進(jìn)行檢查，對(duì)于每個(gè)調(diào)度域，它會(huì)查看是否到了調(diào)用load_balance函數(shù)的時(shí)間。如果到了合適的時(shí)間，就會(huì)觸發(fā)負(fù)載均衡操作。同時(shí)，它還會(huì)根據(jù)當(dāng)前 CPU 的 idle 狀態(tài)和sched_domain的參數(shù)來確定調(diào)用load_balance的時(shí)間間隔。

當(dāng) CPU 處于空閑狀態(tài)時(shí)，會(huì)以較高的頻率調(diào)用load_balance（可能 1、2 個(gè)時(shí)鐘節(jié)拍） ，以便盡快將其他 CPU 上的任務(wù)遷移過來，充分利用空閑的 CPU 資源；而當(dāng) CPU 處于忙碌狀態(tài)時(shí)，則會(huì)以較低的頻率調(diào)用load_balance（可能 10 - 100ms ），避免過度頻繁的負(fù)載均衡操作影響系統(tǒng)性能。

2.3任務(wù)調(diào)度算法（以 CFS 為例）

在 Linux 內(nèi)核中，任務(wù)調(diào)度算法是實(shí)現(xiàn) CPU 負(fù)載均衡的核心部分，其中完全公平調(diào)度（CFS，Completely Fair Scheduler）算法被廣泛應(yīng)用于普通進(jìn)程的調(diào)度。

CFS 算法的核心思想是將任務(wù)看作紅黑樹節(jié)點(diǎn)進(jìn)行排序和調(diào)度 ，以實(shí)現(xiàn)公平的 CPU 資源分配。在 CFS 中，每個(gè)進(jìn)程都有一個(gè)虛擬運(yùn)行時(shí)間（vruntime）的概念，這個(gè)虛擬運(yùn)行時(shí)間是衡量進(jìn)程已經(jīng)獲得的 CPU 服務(wù)量的指標(biāo)。當(dāng)新創(chuàng)建一個(gè)任務(wù)時(shí)，會(huì)賦予其初始的 vruntime 值 ；隨著程序的執(zhí)行，vruntime 會(huì)不斷累加。

對(duì)于等待更長(zhǎng)時(shí)間未被執(zhí)行過的輕載任務(wù)來說，其 vruntime 值會(huì)相對(duì)較低，這樣的任務(wù)會(huì)被放置于紅黑樹的左側(cè)位置，以便盡快得到 CPU 的服務(wù)機(jī)會(huì)。這就好比在一場(chǎng)比賽中，那些等待起跑時(shí)間較長(zhǎng)的選手（任務(wù)），會(huì)被安排在更有利的起跑位置（紅黑樹左側(cè)），從而更有可能先起跑（先獲得 CPU 執(zhí)行時(shí)間）。

CFS 調(diào)度器選取待運(yùn)行的下一個(gè)進(jìn)程時(shí)，會(huì)選擇具有最小 vruntime 的任務(wù) ，因?yàn)檫@個(gè)任務(wù)的虛擬運(yùn)行時(shí)間最短，也就意味著它獲得的 CPU 時(shí)間最少，最需要被調(diào)度執(zhí)行。而紅黑樹這種數(shù)據(jù)結(jié)構(gòu)的特性使得每次插入、刪除操作都能保持在 O (log n) 的時(shí)間復(fù)雜度 ，從而保證了在大量進(jìn)程存在的情況下，依然能高效地查找和調(diào)度具有最小 vruntime 的任務(wù)。例如，在一個(gè)擁有 1000 個(gè)進(jìn)程的系統(tǒng)中，CFS 調(diào)度器通過紅黑樹能夠快速地找到 vruntime 最小的進(jìn)程，將其調(diào)度到 CPU 上執(zhí)行，而不會(huì)因?yàn)檫M(jìn)程數(shù)量的增加導(dǎo)致調(diào)度效率大幅下降。

在考慮 CPU 核心負(fù)載差異分配任務(wù)方面，CFS 算法會(huì)綜合多個(gè)因素。首先，它會(huì)關(guān)注每個(gè) CPU 核心的負(fù)載情況，盡量將任務(wù)分配到負(fù)載較輕的核心上。如果某個(gè) CPU 核心的 runqueue 隊(duì)列中任務(wù)過多，負(fù)載較重，CFS 調(diào)度器會(huì)嘗試將新的任務(wù)分配到其他負(fù)載相對(duì)較輕的核心上，以避免某個(gè)核心過度繁忙。其次，CFS 算法還會(huì)考慮進(jìn)程的特性，比如進(jìn)程的優(yōu)先級(jí)（通過 nice 值體現(xiàn)） 。較高的 nice 值（較低的優(yōu)先級(jí)）進(jìn)程會(huì)獲得更低的處理器使用權(quán)重 ，在分配任務(wù)時(shí)，會(huì)相對(duì)優(yōu)先調(diào)度 nice 值較低（優(yōu)先級(jí)較高）的進(jìn)程，以保證系統(tǒng)中重要任務(wù)能夠及時(shí)得到執(zhí)行。

2.4負(fù)載均衡的觸發(fā)時(shí)機(jī)

負(fù)載均衡的觸發(fā)時(shí)機(jī)對(duì)于保證系統(tǒng)性能至關(guān)重要，Linux 內(nèi)核主要通過以下兩種情況來觸發(fā)負(fù)載均衡。

（1)當(dāng)某個(gè) CPU 的 runqueue 為空時(shí)

當(dāng)某個(gè) CPU 的 runqueue 隊(duì)列中一個(gè)可運(yùn)行進(jìn)程都沒有時(shí)，就說明這個(gè) CPU 處于空閑狀態(tài)，無事可做。這時(shí)，為了充分利用 CPU 資源，系統(tǒng)會(huì)從其他 CPU 的 runqueue 中獲取任務(wù) 。例如，在一個(gè)雙核系統(tǒng)中，假設(shè) CPU0 上的 runqueue 隊(duì)列中有多個(gè)可運(yùn)行進(jìn)程，而 CPU1 的 runqueue 隊(duì)列為空。

那么，CPU1 就會(huì)調(diào)用load_balance函數(shù)，發(fā)現(xiàn)在 CPU0 上還有許多進(jìn)程等待運(yùn)行，于是它會(huì)從 CPU0 上的可運(yùn)行進(jìn)程里找到優(yōu)先級(jí)最高的進(jìn)程，將其拿到自己的 runqueue 里開始執(zhí)行。這樣，原本空閑的 CPU1 就可以利用起來，分擔(dān)系統(tǒng)的工作負(fù)載，提高系統(tǒng)的整體處理能力。

(2)周期性檢查

每經(jīng)過一個(gè)時(shí)鐘節(jié)拍，內(nèi)核會(huì)調(diào)用scheduler_tick函數(shù) ，這個(gè)函數(shù)會(huì)執(zhí)行許多重要的任務(wù)，例如減少當(dāng)前正在執(zhí)行的進(jìn)程的時(shí)間片，以確保每個(gè)進(jìn)程都能公平地獲得 CPU 時(shí)間。在scheduler_tick函數(shù)的結(jié)尾處，則會(huì)調(diào)用rebalance_tick函數(shù) ，rebalance_tick函數(shù)決定了以什么樣的頻率執(zhí)行負(fù)載均衡。

具體來說，rebalance_tick函數(shù)會(huì)從當(dāng)前 CPU 所屬的調(diào)度域開始，依次遍歷各個(gè)更高級(jí)的調(diào)度域。對(duì)于每個(gè)調(diào)度域，它會(huì)檢查是否滿足調(diào)用load_balance函數(shù)的條件。這里的條件主要基于時(shí)間間隔和負(fù)載情況。每個(gè)調(diào)度域都有一個(gè)balance_interval參數(shù) ，表示負(fù)載均衡進(jìn)行的時(shí)間間隔。同時(shí)，還會(huì)根據(jù)當(dāng)前 CPU 的 idle 狀態(tài)來調(diào)整這個(gè)時(shí)間間隔。

當(dāng) idle 標(biāo)志位是SCHED_IDLE時(shí)，表示當(dāng)前 CPU 處理器空閑 ，此時(shí)會(huì)以很高的頻率來調(diào)用load_balance（通常是 1、2 個(gè)時(shí)鐘節(jié)拍） ，因?yàn)榭臻e的 CPU 需要盡快獲取任務(wù)來執(zhí)行，避免資源浪費(fèi)；反之，表示當(dāng)前 CPU 并不空閑，會(huì)以很低的頻率調(diào)用load_balance（一般是 10 - 100ms ），因?yàn)樵?CPU 忙碌時(shí)，頻繁進(jìn)行負(fù)載均衡操作可能會(huì)增加系統(tǒng)開銷，影響系統(tǒng)性能。

例如，假設(shè)一個(gè)調(diào)度域的balance_interval設(shè)置為 50ms ，當(dāng) CPU 處于忙碌狀態(tài)時(shí)，rebalance_tick函數(shù)會(huì)每隔 50ms 檢查一次是否需要進(jìn)行負(fù)載均衡。如果當(dāng)前時(shí)間戳與上次執(zhí)行負(fù)載均衡的時(shí)間戳之差大于等于 50ms ，并且經(jīng)過一系列的負(fù)載檢查和判斷，發(fā)現(xiàn)存在負(fù)載不均衡的情況，就會(huì)調(diào)用load_balance函數(shù)進(jìn)行負(fù)載均衡操作，將任務(wù)從負(fù)載重的 CPU 遷移到負(fù)載輕的 CPU 上，以實(shí)現(xiàn)系統(tǒng)負(fù)載的均衡。

三、負(fù)載均衡的軟件架構(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)需要跟蹤C(jī)FS任務(wù)負(fù)載、各個(gè)sched group的負(fù)載及其CPU算力（可用于CFS任務(wù)運(yùn)算的CPU算力）。跟蹤任務(wù)負(fù)載是主要有兩個(gè)原因：

1. 判斷該任務(wù)是否適合當(dāng)前CPU算力
2. 如果判定需要均衡，那么需要在CPU之間遷移多少的任務(wù)才能達(dá)到平衡？有了任務(wù)負(fù)載跟蹤模塊，這個(gè)問題就比較好回答了。

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

在手機(jī)平臺(tái)上，負(fù)載均衡會(huì)進(jìn)行兩個(gè)level：MC domain的均衡和DIE domain的均衡。在MC domain上，我們會(huì)對(duì)跟蹤每個(gè)CPU負(fù)載狀態(tài)（sched group只有一個(gè)CPU）并及時(shí)更新其算力，使得每個(gè)CPU上有其匹配的負(fù)載。在DIE domain上，我們會(huì)跟蹤cluster上所有負(fù)載（每個(gè)cluster對(duì)應(yīng)一個(gè)sched group）以及cluster的總算力，然后計(jì)算cluster之間負(fù)載的不均衡狀況，通過inter-cluster遷移讓整個(gè)DIE domain進(jìn)入負(fù)載均衡狀態(tài)。

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

首先需要了解下CPU核心之間的數(shù)據(jù)流通信原理，這樣就能大概知道CPU中的Core之間的進(jìn)程遷移之間的開銷：

由于NUMA是以層次關(guān)系呈現(xiàn)，因此在執(zhí)行進(jìn)程的負(fù)載均衡也會(huì)呈現(xiàn)不同的成本開銷。進(jìn)程在同一個(gè)物理Core上的邏輯Core之前遷移開銷最?。?/span>

如果在不同的物理Core之間遷移,如果每個(gè)物理Core擁有私有的L1 Cache,共享L2 Cache,進(jìn)程遷移后就無法使用原來的L1 Cache，進(jìn)程遷移到新的Core上缺失L1 Cache數(shù)據(jù)，這就需要進(jìn)程的狀態(tài)數(shù)據(jù)需要在CPU Core之間進(jìn)行通信獲取這些數(shù)據(jù)，根據(jù)上圖CPU的通信模式可以了解，成本代價(jià)是蠻大的。

內(nèi)核采用調(diào)度域解決現(xiàn)代多CPU多核的問題，調(diào)度域是具有相同屬性和調(diào)度策略的處理器集合，任務(wù)進(jìn)程可以在它們內(nèi)部按照某種策略進(jìn)行調(diào)度遷移。

進(jìn)程在多CPU的負(fù)載均衡也是針對(duì)調(diào)度域的，調(diào)度域根據(jù)超線程、多核、SMP、NUMA等系統(tǒng)架構(gòu)劃分為不同的等級(jí)，不同的等級(jí)架構(gòu)通過指針鏈接在一起，從而形成樹狀結(jié)構(gòu)；在進(jìn)程的負(fù)載均衡過程中，從樹的葉子節(jié)點(diǎn)往上遍歷，直到所有的域中的負(fù)載都是平衡的。目前內(nèi)核進(jìn)程調(diào)度按照如下的原則進(jìn)行,這些原則都是按照cpu架構(gòu)以及通信路徑來進(jìn)行的。

四、CPU負(fù)載均衡機(jī)制實(shí)現(xiàn)方式

4.1如何做負(fù)載均衡

我們以一個(gè)4小核+4大核的處理器來描述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 domain之間的層級(jí)結(jié)構(gòu)。在MC domain，其所屬cpu形成sched group的環(huán)形鏈表結(jié)構(gòu)，各個(gè)cpu對(duì)應(yīng)的MC domain的groups成員指向環(huán)形鏈表中的自己的cpu group。在DIE domain，cluster形成sched group的環(huán)形鏈表結(jié)構(gòu)，各個(gè)cpu對(duì)應(yīng)的DIE domain的groups成員指向環(huán)形鏈表中的自己的cluster group。

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

負(fù)載均衡不是一個(gè)全局CPU之間的均衡，實(shí)際上那樣做也不現(xiàn)實(shí)，當(dāng)系統(tǒng)的CPU數(shù)量較大的時(shí)候，很難一次性的完成所有CPU之間的均衡，這也是提出sched domain的原因之一。我們以周期性均衡為例來描述負(fù)載均衡的基本過程。當(dāng)一個(gè)CPU上進(jìn)行周期性負(fù)載均衡的時(shí)候，我們總是從base domain開始（對(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ù)遷移?；痉椒ê蚆C domain類似，只不過在計(jì)算均衡的時(shí)候，DIE domain不再考慮單個(gè)CPU的負(fù)載和算力，它考慮的是：

1. 該sched group的負(fù)載，即sched group中所有CPU負(fù)載之和
2. 該sched group的算力，即sched group中所有CPU算力之和

4.3線程的負(fù)載均衡

在 Linux 內(nèi)核進(jìn)程 CPU 負(fù)載均衡機(jī)制中，線程的負(fù)載均衡是確保系統(tǒng)高效運(yùn)行的關(guān)鍵環(huán)節(jié)，它主要針對(duì)實(shí)時(shí)（RT，Real - Time）任務(wù)和普通任務(wù)采取不同的策略。

⑴RT 任務(wù)

RT 任務(wù)對(duì)時(shí)間的要求極為嚴(yán)格，需要確保能夠及時(shí)響應(yīng)和執(zhí)行。在 Linux 系統(tǒng)中，對(duì)于 RT 任務(wù)的負(fù)載均衡，采用了一種高效的分配方式，即把 n 個(gè)優(yōu)先級(jí)最高的 RT 任務(wù)自動(dòng)分配到 n 個(gè)核上 。這是因?yàn)?RT 任務(wù)的實(shí)時(shí)性要求決定了它們需要盡快得到 CPU 的執(zhí)行機(jī)會(huì)，將這些高優(yōu)先級(jí)的 RT 任務(wù)分散到多個(gè)核心上，可以避免任務(wù)之間的競(jìng)爭(zhēng)和延遲，確保每個(gè)任務(wù)都能在最短的時(shí)間內(nèi)得到處理。

在實(shí)際實(shí)現(xiàn)過程中，主要通過pull_rt_task和push_rt_task這兩個(gè)函數(shù)來完成任務(wù)的遷移操作 。當(dāng)系統(tǒng)中出現(xiàn)新的高優(yōu)先級(jí) RT 任務(wù)時(shí)，會(huì)調(diào)用push_rt_task函數(shù)，將任務(wù)推送到相對(duì)空閑的 CPU 核心上，以確保任務(wù)能夠及時(shí)執(zhí)行；而當(dāng)某個(gè) CPU 核心上的 RT 任務(wù)執(zhí)行完畢，或者負(fù)載過高需要調(diào)整時(shí)，則會(huì)調(diào)用pull_rt_task函數(shù)，從其他核心上拉取合適的 RT 任務(wù)到當(dāng)前核心，從而實(shí)現(xiàn)負(fù)載的均衡。這種基于任務(wù)優(yōu)先級(jí)的分配方式，能夠充分利用多核 CPU 的并行處理能力，保證 RT 任務(wù)的實(shí)時(shí)性需求，使得系統(tǒng)在處理對(duì)時(shí)間敏感的任務(wù)時(shí)，能夠保持高效穩(wěn)定的運(yùn)行狀態(tài)。

⑵普通任務(wù)

普通任務(wù)的負(fù)載均衡則主要通過周期性負(fù)載均衡、idle 時(shí)負(fù)載均衡以及 fork 和 exec 時(shí)負(fù)載均衡這幾種方式來實(shí)現(xiàn)。

周期性負(fù)載均衡是在時(shí)鐘 tick 到來時(shí)進(jìn)行的 。每當(dāng)時(shí)鐘 tick 發(fā)生，系統(tǒng)就會(huì)檢查各個(gè)核的負(fù)載情況，優(yōu)先讓空閑核工作。如果發(fā)現(xiàn)某個(gè)核處于空閑狀態(tài)，而其他核負(fù)載較重，就會(huì)從負(fù)載重的核中pull任務(wù)到空閑核，或者將空閑核的任務(wù)push給負(fù)載較輕的核 。例如，在一個(gè)四核系統(tǒng)中，假設(shè) CPU0 和 CPU1 負(fù)載較高，而 CPU2 和 CPU3 處于空閑狀態(tài)。當(dāng)時(shí)鐘 tick 到來時(shí)，系統(tǒng)會(huì)檢測(cè)到這種負(fù)載不均衡的情況，然后從 CPU0 和 CPU1 的 runqueue 隊(duì)列中挑選一些普通任務(wù)，遷移到 CPU2 和 CPU3 上執(zhí)行，這樣就能讓各個(gè)核都能參與到任務(wù)處理中，避免出現(xiàn)部分核過度忙碌，而部分核閑置的情況，從而實(shí)現(xiàn)系統(tǒng)負(fù)載的均衡。

idle 時(shí)負(fù)載均衡是當(dāng)某個(gè)核進(jìn)入 idle 狀態(tài)時(shí)觸發(fā)的 。當(dāng)一個(gè)核進(jìn)入 idle 狀態(tài)，說明它當(dāng)前沒有可執(zhí)行的任務(wù)，處于空閑狀態(tài)。此時(shí)，這個(gè)核會(huì)主動(dòng)去檢查其他核的負(fù)載情況，如果發(fā)現(xiàn)其他核有任務(wù)在運(yùn)行，就會(huì)主動(dòng)從其他核pull任務(wù)過來執(zhí)行 。例如，在一個(gè)八核系統(tǒng)中，假設(shè) CPU5 進(jìn)入 idle 狀態(tài)，它會(huì)查看其他七個(gè)核的 runqueue 隊(duì)列，發(fā)現(xiàn) CPU3 上有較多的普通任務(wù)在等待執(zhí)行，那么 CPU5 就會(huì)從 CPU3 的 runqueue 隊(duì)列中選取一些任務(wù)，將其遷移到自己的隊(duì)列中并開始執(zhí)行，這樣可以充分利用空閑的 CPU 資源，提高系統(tǒng)的整體處理能力。

fork 和 exec 時(shí)負(fù)載均衡則與新進(jìn)程的創(chuàng)建和執(zhí)行密切相關(guān) 。當(dāng)系統(tǒng)執(zhí)行 fork 操作創(chuàng)建一個(gè)新進(jìn)程，或者通過 exec 函數(shù)族執(zhí)行新的程序時(shí)，會(huì)把新創(chuàng)建的進(jìn)程放到最閑的核上去運(yùn)行 。這是因?yàn)樾逻M(jìn)程在啟動(dòng)階段可能需要進(jìn)行一些初始化操作，將其分配到最閑的核上，可以避免對(duì)其他正在忙碌執(zhí)行任務(wù)的核造成額外的負(fù)擔(dān)，同時(shí)也能讓新進(jìn)程盡快獲得 CPU 資源，順利完成初始化和后續(xù)的執(zhí)行操作。例如，當(dāng)我們?cè)谙到y(tǒng)中啟動(dòng)一個(gè)新的應(yīng)用程序時(shí)，系統(tǒng)會(huì)根據(jù)各個(gè)核的負(fù)載情況，將這個(gè)新程序?qū)?yīng)的進(jìn)程分配到當(dāng)前負(fù)載最輕的核上運(yùn)行，確保新進(jìn)程能夠高效啟動(dòng)和運(yùn)行。

4.4中斷負(fù)載均衡

在 Linux 系統(tǒng)中，負(fù)載不僅來源于進(jìn)程，中斷也是重要的負(fù)載來源之一。中斷分為硬件中斷和軟中斷，它們?cè)谙到y(tǒng)運(yùn)行中起著不同但又緊密相關(guān)的作用。

硬件中斷通常是由外部設(shè)備（如網(wǎng)卡、硬盤、鍵盤等）引發(fā)的信號(hào)，用于通知 CPU 有需要立即處理的事件 。例如，當(dāng)網(wǎng)卡接收到數(shù)據(jù)時(shí)，會(huì)產(chǎn)生一個(gè)硬件中斷，通知 CPU 有新的數(shù)據(jù)到達(dá)需要處理。硬件中斷的處理時(shí)間一般較短，在 Linux 2.6.34 版本之后，內(nèi)核不再支持中斷嵌套 。

當(dāng)硬件中斷發(fā)生并完成數(shù)據(jù)接收等操作后，通常會(huì)調(diào)用軟中斷來進(jìn)行后續(xù)的處理，比如處理 TCP/IP 包 。軟中斷可以嵌套，它主要負(fù)責(zé)處理那些可以稍微延遲處理的任務(wù)，是對(duì)硬件中斷未完成工作的一種推后執(zhí)行機(jī)制。在top命令中，hi表示硬中斷時(shí)間（isr，屏蔽中斷），si表示軟中斷 。當(dāng)網(wǎng)絡(luò)流量較大時(shí)，CPU 花在硬中斷和軟中斷上的時(shí)間會(huì)比較多，此時(shí)就需要進(jìn)行中斷的負(fù)載均衡，以確保系統(tǒng)的高效運(yùn)行。

在新網(wǎng)卡多隊(duì)列的情況下，實(shí)現(xiàn)中斷負(fù)載均衡可以通過設(shè)置中斷親和性來完成 。例如，在一個(gè) 4 核的系統(tǒng)中，如果網(wǎng)卡有 4 個(gè)隊(duì)列，每個(gè)隊(duì)列都可以單獨(dú)產(chǎn)生中斷，并且硬件支持負(fù)載均衡 。那么可以將一個(gè)隊(duì)列綁定到一個(gè)核上，通過將每個(gè)中斷號(hào)分別設(shè)置 affinity，綁定到指定 CPU，就能讓所有 CPU 都參與到網(wǎng)卡發(fā)送包服務(wù)中 。

比如，通過查看/proc/interrupts文件找到與網(wǎng)卡相關(guān)的中斷號(hào)，然后使用命令sudo sh -c “echo 3 > /proc/irq/124/smp_affinity”，就可以將中斷號(hào)為 124 的中斷綁定到 CPU3 上 。這樣，當(dāng)網(wǎng)卡的不同隊(duì)列產(chǎn)生中斷時(shí)，就會(huì)被分配到不同的 CPU 核心上進(jìn)行處理，避免了所有中斷都集中在一個(gè)核心上，從而實(shí)現(xiàn)了中斷的負(fù)載均衡，提高了系統(tǒng)處理網(wǎng)絡(luò)數(shù)據(jù)的能力。

然而，有些網(wǎng)卡只有一個(gè)隊(duì)列，這種情況下，單個(gè)核拋出的軟中斷只能在這個(gè)核上運(yùn)行，導(dǎo)致一個(gè)隊(duì)列拋出的軟中斷（如 TCP/IP 層處理）只能在這一個(gè)核執(zhí)行，其他核會(huì)處于空閑狀態(tài)，無法充分利用多核 CPU 的優(yōu)勢(shì)。為了解決這個(gè)問題，Google 推出了 RPS（Receive Packet Steering）補(bǔ)丁 。RPS 補(bǔ)丁的原理是由單一 CPU 核響應(yīng)硬件中斷，然后將大量網(wǎng)絡(luò)接收包通過多核間中斷方式分發(fā)給其他空閑核 。

例如，在一個(gè)單核網(wǎng)卡隊(duì)列收包的系統(tǒng)中，默認(rèn)情況下收包操作只在 CPU0 上執(zhí)行。通過設(shè)置 RPS，如echo 3 > /sys/class/net/eth0/queues/rx-0/rps_cpus，可以將收包操作均衡到 CPU0 和 CPU1 上 。這樣，當(dāng)大量網(wǎng)絡(luò)數(shù)據(jù)包到達(dá)時(shí)，原本只能由一個(gè)核處理的任務(wù)，現(xiàn)在可以由多個(gè)核共同處理，大大提高了系統(tǒng)處理網(wǎng)絡(luò)數(shù)據(jù)的效率，實(shí)現(xiàn)了軟中斷的負(fù)載均衡，充分發(fā)揮了多核 CPU 的性能優(yōu)勢(shì)。

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

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

在引入異構(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ì)帶來功耗的收益。例如系統(tǒng)有4個(gè)CPU，共計(jì)8個(gè)進(jìn)入執(zhí)行態(tài)的任務(wù)（負(fù)載相同）。這些任務(wù)在4個(gè)CPU上的排布有兩種選擇：

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

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

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