從源碼到實踐：徹底剖析 Linux 進程負載均衡機制

在當今的計算機領域，多核 CPU 早已成爲主流配置。從早期的單核處理器到如今的 8 核、16 核甚至更多核心的 CPU，硬件性能得到了極大提升。這種多核架構爲計算機系統帶來了強大的並行處理能力，使得多個任務可以同時高效運行。然而，多核 CPU 的性能優勢並非能自動實現，如何充分利用這些核心資源，讓各個進程在不同核心上合理分配與運行，成爲了操作系統必須解決的關鍵問題。

在衆多操作系統中，Linux 以其開源、穩定和高效等特點，被廣泛應用於服務器、嵌入式設備以及超級計算機等領域。而 Linux 內核進程 CPU 負載均衡機制，就是其充分發揮多核 CPU 性能的核心技術之一。這一機制就像是一位智能的調度大師，時刻監控着系統中各個進程的運行狀態以及各個 CPU 核心的負載情況，然後巧妙地將進程分配到最合適的 CPU 核心上運行，確保系統資源得到充分利用，避免出現某些核心忙得不可開交，而另一些核心卻閒置無事的尷尬局面。

接下來，就讓我們一起深入探索 Linux 內核進程 CPU 負載均衡機制，揭開它神祕的面紗，瞭解它是如何在幕後默默工作，爲我們帶來高效穩定的系統體驗的。

一、CPU 負載均衡機制

1.1 什麼是 CPU 負載

在深入探討 Linux 內核進程 CPU 負載均衡機制之前，我們先來明確一個關鍵概念 ——CPU 負載。CPU 負載常常容易與 CPU 使用率、利用率混淆 ，這裏我們來詳細區分一下。CPU 利用率是指 CPU 處於忙碌狀態的時間佔總時間的比例。比如在 1000ms 的時間窗口內，如果 CPU 執行任務的時間爲 500ms，處於空閒（idle）狀態的時間也是 500ms，那麼該時間段內 CPU 的利用率就是 50%。在 CPU 利用率未達到 100% 時，利用率與負載大致相等。

但當 CPU 利用率達到 100% 時，利用率就無法準確反映 CPU 負載狀況了。因爲此時不同 CPU 上的運行隊列（runqueue）中等待執行的任務數目可能不同，直觀來說，runqueue 中掛着 10 個任務的 CPU，其負載明顯要比掛着 5 個任務的 CPU 更重。

早期，CPU 負載是用 runqueue 深度來描述的，也就是運行隊列中等待執行的任務數量。不過這種方式比較粗略，例如 CPU A 和 CPU B 上都掛了 1 個任務，但 A 上的任務是重載任務，B 上的是經常處於睡眠（sleep）狀態的輕載任務，僅依據 runqueue 深度來判斷 CPU 負載就不準確了。

現代調度器通常使用 CPU runqueue 上所有任務負載之和來表示 CPU 負載 ，這樣一來，對 CPU 負載的跟蹤就轉變爲對任務負載的跟蹤。在 3.8 版本的 Linux 內核中，引入了 PELT（per entity load tracking）算法，該算法能夠跟蹤每一個調度實體（sched entity）的負載，將負載跟蹤算法從基於每個 CPU（per-CPU）進化到基於每個調度實體（per-entity）。PELT 算法不僅能知曉 CPU 的負載情況，還能明確負載來自哪個調度實體，從而實現更精準的負載均衡。

1.2 何爲均衡

明確了 CPU 負載的概念後，我們再來談談 “均衡”。負載均衡並非簡單地將系統的總負載平均分配到各個 CPU 上。實際上，我們必須充分考慮系統中各個 CPU 的算力，使每個 CPU 所承擔的負載與其算力相匹配。例如，在一個擁有 6 個小核和 2 個大核的系統中，假設系統總負載爲 800，如果簡單地給每個 CPU 分配 100 的負載，這其實是不均衡的，因爲大核 CPU 能夠提供更強的計算能力。

那麼，什麼是 CPU 算力（capacity）呢？算力是用來描述 CPU 能夠提供的計算能力。在相同頻率下，微架構爲 A77 的 CPU 算力顯然大於 A57 的 CPU。如果 CPU 的微架構相同，那麼最大頻率爲 2.2GHz 的 CPU 算力肯定大於最大頻率爲 1.1GHz 的 CPU。通常，確定了微架構和最大頻率，一個 CPU 的算力就基本確定了。雖然 Cpufreq 系統會根據當前的 CPU 利用率來調節 CPU 的運行頻率，但這並不會改變 CPU 的算力，只有當 CPU 的最大運行頻率發生變化時（比如觸發溫控，限制了 CPU 的最大頻率），CPU 的算力纔會隨之改變。

在考慮 CFS（Completely Fair Scheduler，完全公平調度器）任務的均衡時，還需要把 CPU 用於執行實時任務（RT，Real - Time）和中斷請求（irq）的算力去掉，使用該 CPU 可用於 CFS 的算力 。所以，CFS 任務均衡中使用的 CPU 算力是一個不斷變化的值，需要經常更新。爲了便於對比 CPU 算力和任務負載，我們採用歸一化的方式，將系統中處理能力最強且運行在最高頻率的 CPU 算力設定爲 1024，其他 CPU 的算力則根據其微架構和運行頻率進行相應調整。

有了任務負載和 CPU 算力，看似就能完成負載均衡工作了，但實際情況更爲複雜。當負載不均衡時，任務需要在 CPU 之間遷移，而不同形態的遷移會產生不同的開銷。比如，一個任務在小核集羣內的 CPU 之間遷移，其性能開銷肯定小於從小核集羣的 CPU 遷移到大核集羣的開銷。因此，爲了更有效地執行負載均衡，調度域（scheduling domain）和調度組（scheduling group）的概念被引入。調度域是一組 CPU 的集合，這些 CPU 在拓撲結構、性能等方面具有相似性；調度組則是在調度域內，根據更細粒度的規則劃分的 CPU 集合。通過合理劃分調度域和調度組，可以更精準地控制任務在 CPU 之間的遷移，降低遷移開銷，實現更高效的負載均衡。

1.3 何爲負載

「負載」可不等同於 CPU 佔用率，它衡量的是已經 ready，但在一段時間內得不到執行機會的任務數量。如果把 CPU 比做車道的話，當有車輛排隊等着進入這個車道，那負載就大於 1，反之則小於 1，它體現的其實是一種擁塞程度。

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

一般認爲，負載值大於 0.7 就應該引起注意，但對於 Linux 系統來說，情況可能有所不同，因爲 Linux 中統計的負載值，除了處於就緒態的任務，還包括了處於 uninterruptible 狀態、等待 I/O 的任務。

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。如果因爲 uninterruptible 的任務較多造成負載值看起來偏高，實際的系統在使用上也不見得就會出現明顯的卡頓。

負載均衡有兩種方式：pull, push

• pull 拉：負載輕的 CPU，從負載繁重的 CPU pull tasks 來運行。這應該是主要的方式，因爲不應該讓負載本身就繁重的 CPU 執行負載均衡任務。相應的爲 load balance。

• push 推：負載重的 CPU，向負載輕的 CPU，推送 tasks 由其幫忙執行。相應的爲 active balance。

但是遷移是有代價的。在同一個物理 CPU 的兩個 logical core 之間遷移，因爲共享 cache，代價相對較小。如果是在兩個物理 CPU 之間遷移，代價就會增大。更進一步，對於 NUMA 系統，在不同 node 之間的遷移將帶來更大的損失；這其實形成了一個調度上的約束，在 Linux 中被實現爲 "sched domain"，並以 hierarchy 的形式組織。處於同一內層 domain 的，遷移可以更頻繁地進行，越往外層，遷移則應儘可能地避免。

1.4 負載均衡的作用

負載均衡在 Linux 系統中起着至關重要的作用，對系統性能和穩定性有着顯著的提升。如果沒有有效的負載均衡機制，當系統中某個 CPU 核心的負載過高，而其他核心卻閒置時，就會導致整個系統性能下降。高負載的核心可能會因爲任務過多而出現響應變慢、處理延遲等問題，嚴重時甚至可能導致系統崩潰。

例如，在一個 Web 服務器中，如果所有的 HTTP 請求處理任務都集中在某一個 CPU 核心上，隨着請求量的增加，這個核心很快就會不堪重負，服務器的響應時間會大幅延長，用戶訪問網站時會感覺到明顯的卡頓，甚至無法訪問。

而通過負載均衡機制，將這些任務均勻地分配到各個 CPU 核心上，每個核心都能充分發揮其計算能力，共同承擔系統的工作負載。這樣不僅可以避免單個核心過度勞累，還能大大提高系統的整體處理能力和響應速度。以剛纔的 Web 服務器爲例，負載均衡機制會將 HTTP 請求合理地分發到多個 CPU 核心上進行處理，每個核心都能高效地處理一部分請求，服務器就能快速響應用戶的訪問，提升用戶體驗。

負載均衡還有助於提高系統資源的利用率。在多核 CPU 系統中，每個核心都是寶貴的資源。通過負載均衡，能夠確保這些資源得到充分利用，避免出現資源閒置浪費的情況。當一個 CPU 核心的負載過高時，負載均衡機制會將部分任務遷移到其他相對空閒的核心上，使得整個系統的資源分配更加合理，從而提高系統的整體運行效率。這就好比一個工廠裏有多個工人（CPU 核心），如果所有的工作都交給一個工人做，其他工人卻閒着沒事幹，那顯然是對人力資源的浪費。而通過合理的任務分配（負載均衡），讓每個工人都能承擔適量的工作，就能充分發揮整個工廠的生產能力。

1.5 爲何均衡

作爲 OS 的心跳，只要不是 NO_HZ 的 CPU，tick 都會如約而至，這爲判斷是否需要均衡提供了一個絕佳的時機。不過，如果在每次 tick 時鐘中斷都去做一次 balance，那開銷太大了，所以 balance 的觸發是有一個週期要求的。當 tick 到來的時候，在 scheduler_tick 函數中會調用 trigger_load_balance 來觸發週期性負載均衡，相關的代碼如下：

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;
	/* 觸發periodic balance */
	if (time_after_eq(jiffies, rq->next_balance))
		raise_softirq(SCHED_SOFTIRQ);
  /* -觸發nohz idle balance */
	nohz_balancer_kick(rq);
}

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

系統中有多個 idle 的 cpu，如何選擇執行 nohz idle balance 的那個 CPU 呢？

如果不考慮功耗，那麼就從所有 idle cpu 中選擇一個就可以了，但是在異構的系統中，我們應該要考慮的更多，如果 idle cpu 中有大核也有小核，是選擇大核還是選擇小核？大核 CPU 雖然算力強，但是功耗高。如果選擇小核，雖然能省功耗，但是提供的算力是否足夠。標準內核選擇的最簡單的算法：隨便選擇一個 idle cpu（也就是 idle cpu mask 中的第一個）。

1.6 如何均衡

要實現多核系統的負載均衡，主要依靠 task 在不同 CPU 之間的遷移（migration），也就是將一個 task 從負載較重的 CPU 上轉移到負載相對較輕的 CPU 上去執行。從 CPU 的 runqueue 上取下來的這個動作，稱爲 "pull"，放到另一個 CPU 的 runqueue 上去，則稱之爲 "push"。

但是遷移是有代價的，而且這個遷移的代價還不一樣。AMP 系統裏每個 CPU 的 capacity 可能不同，而 SMP 系統裏看起來每個 CPU 都是一樣的，按理好像應該視作一個數組，拉通來調度。但現實是：現代 SMP 的拓撲結構，決定了 CPU 之間的 cache 共享是不同的，cache 共享越多，遷移的 “阻力” 越小，反之就越大。

在同一個物理 core 的兩個 logical CPU 之間遷移，因爲共享 L1 和 L2 cache，阻力相對較小。對於 NUMA 系統，如果是在同一 node 中的兩個物理 core 之間遷移，共享的是 L3 cache 和內存，損失就會增大（AMD 的 Zen 系列芯片存在同一 node 的物理 core 不共享 L3 的情況）。更進一步，在不同 node 之間的遷移將付出更大的代價。

就像一個人換工作的時候，往往會優先考慮同一個公司的內部職位，因爲只是轉崗的話，公司內的各種環境都是熟悉的。再是考慮同一個城市的其他公司，因爲不用搬家嘛。可能最後纔是考慮其他城市 / 國家的，畢竟 relocate 牽扯的事情還是蠻多的。

二、CPU 負載均衡機制原理

2.1 相關數據結構與關鍵函數

在 Linux 內核進程 CPU 負載均衡機制中，有一些關鍵的數據結構和函數起着至關重要的作用。

runqueue 隊列是其中一個重要的數據結構。在多處理器系統中，每個 CPU 都擁有自己的 runqueue 隊列 ，這個隊列就像是一個任務等待執行的 “候診室”，裏面存放着處於運行狀態（run）的進程鏈表。當一個進程準備好運行時，它就會被加入到某個 CPU 的 runqueue 隊列中。例如，當我們在系統中啓動一個新的應用程序時，該程序對應的進程就會被添加到某個 CPU 的 runqueue 隊列裏，等待 CPU 的調度執行。

調度域（sched domain）和調度組（sched group）

負載均衡的複雜性主要和複雜的系統拓撲有關。由於當前 CPU 很忙，我們把之前運行在該 CPU 上的一個任務遷移到新的 CPU 上的時候，如果遷移到新的 CPU 是和原來的 CPU 在不同的 cluster 中，性能會受影響（因爲會 cache 會變冷）。但是對於超線程架構，cpu 共享 cache，這時候超線程之間的任務遷移將不會有特別明顯的性能影響。

NUMA 上任務遷移的影響又不同，我們應該儘量避免不同 NUMA node 之間的任務遷移，除非 NUMA node 之間的均衡達到非常嚴重的程度。總之，一個好的負載均衡算法必須適配各種 cpu 拓撲結構。爲了解決這些問題，linux 內核引入了 sched_domain 的概念。

調度組： 調度組是組成調度域的基本單位，在最小的調度域中一個 cpu core 是一個調度組，在最大的調度域中，一個 NUMA 結點內的所有 cpu core 成一個調度組。

sched_domain（調度域）也是一個核心數據結構。爲了適應多種多處理器模型，Linux 引入了調度域及組的概念。一個調度域可以包含其他的調度域或者多個組 ，它是一組 CPU 的集合，這些 CPU 在拓撲結構、性能等方面具有相似性。通過調度域，內核能夠更好地管理和協調不同 CPU 之間的負載均衡。

例如，在一個具有多個 CPU 核心的系統中，可能會根據 CPU 的性能和拓撲關係，將某些核心劃分爲一個調度域，這樣在進行負載均衡時，可以優先在這個調度域內進行任務的遷移和分配，減少跨調度域遷移帶來的開銷。

調度域的數據結構定義如下：

struct sched_domain {
    struct sched_domain *parent; // 指向父調度域
    struct sched_group *groups;  // 該調度域所包含的組
    cpumask_t span; 
    unsigned long min_interval; // 最小時間間隔，用於檢查負載均衡操作時機
    unsigned long max_interval; 
    unsigned int busy_factor;   // 忙碌時負載均衡時間間隔乘數
    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;  // 負載均衡進行的時間間隔
    unsigned int nr_balance_failed; // 負載均衡遷移進程失敗的次數
};

調度域並不是一個平層結構，而是根據 CPU 拓撲形成層級結構。相對應的，負載均衡也不是一蹴而就的，而是會在多個 sched domain 中展開（例如從 base domain 開始，一直到頂層 sched domain，逐個 domain 進行均衡）。

內核中 struct sched_domain 來描述調度域，其主要的成員如下：

• Parent 和 child：Sched domain 會形成層級結構，parent 和 child 建立了不同層級結構的父子關係。對於 base domain 而言，其 child 等於 NULL，對於 top domain 而言，其 parent 等於 NULL。

• groups：一個調度域中有若干個調度組，這些調度組形成一個環形鏈表，groups 成員就是鏈表頭。

• min_interval 和 max_interval：做均衡也是需要開銷的，我們不可能時刻去檢查調度域的均衡狀態，這兩個參數定義了檢查該 sched domain 均衡狀態的時間間隔範圍。

• busy_factor：正常情況下，balance_interval 定義了均衡的時間間隔，如果 cpu 繁忙，那麼均衡要時間間隔長一些，即時間間隔定義爲 busy_factor x balance_interval。

• imbalance_pct：調度域內的不均衡狀態達到了一定的程度之後就開始進行負載均衡的操作。imbalance_pct 這個成員定義了判定不均衡的門限。

• cache_nice_tries：這個成員應該是和 nr_balance_failed 配合控制負載均衡過程的遷移力度。當 nr_balance_failed 大於 cache_nice_tries 的時候，負載均衡會變得更加激進。

• nohz_idle：每個 cpu 都有其對應的 LLC sched domain，而 LLC SD 記錄對應 cpu 的 idle 狀態（是否 tick 被停掉），進一步得到該 domain 中 busy cpu 的個數，體現在（sd->shared->nr_busy_cpus）。

• flags：調度域標誌，下面有表格詳細描述。

• level：該 sched domain 在整個調度域層級結構中的 level。Base sched domain 的 level 等於 0，向上依次加一。

• last_balance：上次進行 balance 的時間點。通過基礎均衡時間間隔（）和當前 sd 的狀態可以計算最終的均衡間隔時間（get_sd_balance_interval），last_balance 加上這個計算得到的均衡時間間隔就是下一次均衡的時間點。

• balance_interval：定義了該 sched domain 均衡的基礎時間間隔

• nr_balance_failed：本 sched domain 中進行負載均衡失敗的次數。當失敗次數大於 cache_nice_tries 的時候，我們考慮遷移 cache hot 的任務，進行更激進的均衡操作。

• max_newidle_lb_cost：在該 domain 上進行 newidle balance 的最大時間長度（即 newidle balance 的開銷）。最小值是 sysctl_sched_migration_cost。

• next_decay_max_lb_cost：max_newidle_lb_cost 會記錄最近在該 sched domain 上進行 newidle balance 的最大時間長度，這個 max cost 不是一成不變的，它有一個衰減過程，每秒衰減 1%，這個成員就是用來控制衰減的。

• avg_scan_cost：平均掃描成本

調度域並不是一個平層結構，而是根據 CPU 拓撲形成層級結構。相對應的，負載均衡也不是一蹴而就的，而是會在多個 sched domain 中展開（例如從 base domain 開始，一直到頂層 sched domain，逐個 domain 進行均衡）。具體如何進行均衡（自底向上還是自頂向下，在哪些 domain 中進行均衡）是和均衡類型和各個 sched domain 設置的 flag 相關，具體細節後面會描述。

在指定調度域內進行均衡的時候不考慮系統中其他調度域的 CPU 負載情況，只考慮該調度域內的 sched group 之間的負載是否均衡。對於 base doamin，其所屬的 sched group 中只有一個 cpu，對於更高 level 的 sched domain，其所屬的 sched group 中可能會有多個 cpu core。

與之相關的是 sched_group（調度組），一個組通常包含一個或者多個 CPU 。組的數據結構通過 cpumask_t 來表示該組所包含的 CPU，還通過 next 指針將多個 sched_group 串到調度域的鏈表上面。其數據結構定義如下：

struct sched_group {
    struct sched_group *next; // 用於將sched_group串到調度域鏈表
    cpumask_t cpumask; // 表示該group所包含的cpu
    unsigned long cpu_power; // 通常是cpu的個數
};

在函數方面，load_balance 函數是實現負載均衡的關鍵函數之一。當系統檢測到 CPU 負載不均衡時，就會調用 load_balance 函數。它的主要工作是尋找最繁忙的 CPU 組中的最繁忙的 CPU ，然後將其進程遷移一部分到其他相對空閒的 CPU 上。例如，在一個四核系統中，如果發現 CPU0 的負載過高，而 CPU1、CPU2 和 CPU3 相對空閒，load_balance 函數就會嘗試從 CPU0 的 runqueue 隊列中挑選一些進程，遷移到 CPU1、CPU2 或 CPU3 的 runqueue 隊列中，以實現負載的均衡。

rebalance_tick 函數也在負載均衡中扮演着重要角色。每經過一次時鐘中斷，scheduler_tick 函數就會調用 rebalance_tick 函數 。rebalance_tick 函數會從最底層的調度域開始，一直到最上層的調度域進行檢查，對於每個調度域，它會查看是否到了調用 load_balance 函數的時間。如果到了合適的時間，就會觸發負載均衡操作。同時，它還會根據當前 CPU 的 idle 狀態和 sched_domain 的參數來確定調用 load_balance 的時間間隔。

當 CPU 處於空閒狀態時，會以較高的頻率調用 load_balance（可能 1、2 個時鐘節拍） ，以便儘快將其他 CPU 上的任務遷移過來，充分利用空閒的 CPU 資源；而當 CPU 處於忙碌狀態時，則會以較低的頻率調用 load_balance（可能 10 - 100ms ），避免過度頻繁的負載均衡操作影響系統性能。

2.3 任務調度算法（以 CFS 爲例）

在 Linux 內核中，任務調度算法是實現 CPU 負載均衡的核心部分，其中完全公平調度（CFS，Completely Fair Scheduler）算法被廣泛應用於普通進程的調度。

CFS 算法的核心思想是將任務看作紅黑樹節點進行排序和調度 ，以實現公平的 CPU 資源分配。在 CFS 中，每個進程都有一個虛擬運行時間（vruntime）的概念，這個虛擬運行時間是衡量進程已經獲得的 CPU 服務量的指標。當新創建一個任務時，會賦予其初始的 vruntime 值 ；隨着程序的執行，vruntime 會不斷累加。

對於等待更長時間未被執行過的輕載任務來說，其 vruntime 值會相對較低，這樣的任務會被放置於紅黑樹的左側位置，以便儘快得到 CPU 的服務機會。這就好比在一場比賽中，那些等待起跑時間較長的選手（任務），會被安排在更有利的起跑位置（紅黑樹左側），從而更有可能先起跑（先獲得 CPU 執行時間）。

CFS 調度器選取待運行的下一個進程時，會選擇具有最小 vruntime 的任務 ，因爲這個任務的虛擬運行時間最短，也就意味着它獲得的 CPU 時間最少，最需要被調度執行。而紅黑樹這種數據結構的特性使得每次插入、刪除操作都能保持在 O (log n) 的時間複雜度 ，從而保證了在大量進程存在的情況下，依然能高效地查找和調度具有最小 vruntime 的任務。例如，在一個擁有 1000 個進程的系統中，CFS 調度器通過紅黑樹能夠快速地找到 vruntime 最小的進程，將其調度到 CPU 上執行，而不會因爲進程數量的增加導致調度效率大幅下降。

在考慮 CPU 核心負載差異分配任務方面，CFS 算法會綜合多個因素。首先，它會關注每個 CPU 核心的負載情況，儘量將任務分配到負載較輕的核心上。如果某個 CPU 核心的 runqueue 隊列中任務過多，負載較重，CFS 調度器會嘗試將新的任務分配到其他負載相對較輕的核心上，以避免某個核心過度繁忙。其次，CFS 算法還會考慮進程的特性，比如進程的優先級（通過 nice 值體現） 。較高的 nice 值（較低的優先級）進程會獲得更低的處理器使用權重 ，在分配任務時，會相對優先調度 nice 值較低（優先級較高）的進程，以保證系統中重要任務能夠及時得到執行。

2.3 負載均衡的觸發時機

負載均衡的觸發時機對於保證系統性能至關重要，Linux 內核主要通過以下兩種情況來觸發負載均衡。

（1) 當某個 CPU 的 runqueue 爲空時

當某個 CPU 的 runqueue 隊列中一個可運行進程都沒有時，就說明這個 CPU 處於空閒狀態，無事可做。這時，爲了充分利用 CPU 資源，系統會從其他 CPU 的 runqueue 中獲取任務 。例如，在一個雙核系統中，假設 CPU0 上的 runqueue 隊列中有多個可運行進程，而 CPU1 的 runqueue 隊列爲空。

那麼，CPU1 就會調用 load_balance 函數，發現在 CPU0 上還有許多進程等待運行，於是它會從 CPU0 上的可運行進程裏找到優先級最高的進程，將其拿到自己的 runqueue 裏開始執行。這樣，原本空閒的 CPU1 就可以利用起來，分擔系統的工作負載，提高系統的整體處理能力。

(2) 週期性檢查

每經過一個時鐘節拍，內核會調用 scheduler_tick 函數 ，這個函數會執行許多重要的任務，例如減少當前正在執行的進程的時間片，以確保每個進程都能公平地獲得 CPU 時間。在 scheduler_tick 函數的結尾處，則會調用 rebalance_tick 函數 ，rebalance_tick 函數決定了以什麼樣的頻率執行負載均衡。

具體來說，rebalance_tick 函數會從當前 CPU 所屬的調度域開始，依次遍歷各個更高級的調度域。對於每個調度域，它會檢查是否滿足調用 load_balance 函數的條件。這裏的條件主要基於時間間隔和負載情況。每個調度域都有一個 balance_interval 參數 ，表示負載均衡進行的時間間隔。同時，還會根據當前 CPU 的 idle 狀態來調整這個時間間隔。

當 idle 標誌位是 SCHED_IDLE 時，表示當前 CPU 處理器空閒 ，此時會以很高的頻率來調用 load_balance（通常是 1、2 個時鐘節拍） ，因爲空閒的 CPU 需要儘快獲取任務來執行，避免資源浪費；反之，表示當前 CPU 並不空閒，會以很低的頻率調用 load_balance（一般是 10 - 100ms ），因爲在 CPU 忙碌時，頻繁進行負載均衡操作可能會增加系統開銷，影響系統性能。

例如，假設一個調度域的 balance_interval 設置爲 50ms ，當 CPU 處於忙碌狀態時，rebalance_tick 函數會每隔 50ms 檢查一次是否需要進行負載均衡。如果當前時間戳與上次執行負載均衡的時間戳之差大於等於 50ms ，並且經過一系列的負載檢查和判斷，發現存在負載不均衡的情況，就會調用 load_balance 函數進行負載均衡操作，將任務從負載重的 CPU 遷移到負載輕的 CPU 上，以實現系統負載的均衡。

三、負載均衡的軟件架構

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

爲了更好的進行 CFS 任務的均衡，系統需要跟蹤 CFS 任務負載、各個 sched group 的負載及其 CPU 算力（可用於 CFS 任務運算的 CPU 算力）。跟蹤任務負載是主要有兩個原因：

1. 判斷該任務是否適合當前 CPU 算力

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

爲了更好的進行高效的均衡，我們還需要構建調度域的層級結構（sched domain hierarchy），圖中顯示的是二級結構（這裏給的是邏輯結構，實際內核中的各個 level 的 sched domain 是 per cpu 的）。手機場景多半是二級結構，支持 NUMA 的服務器場景可能會形成更復雜的結構。通過 DTS 和 CPU topo 子系統，我們可以構建 sched domain 層級結構，用於具體的均衡算法。

在手機平臺上，負載均衡會進行兩個 level：MC domain 的均衡和 DIE domain 的均衡。在 MC domain 上，我們會對跟蹤每個 CPU 負載狀態（sched group 只有一個 CPU）並及時更新其算力，使得每個 CPU 上有其匹配的負載。在 DIE domain 上，我們會跟蹤 cluster 上所有負載（每個 cluster 對應一個 sched group）以及 cluster 的總算力，然後計算 cluster 之間負載的不均衡狀況，通過 inter-cluster 遷移讓整個 DIE domain 進入負載均衡狀態。

有了上面描述的基礎設施，那麼什麼時候進行負載均衡呢？這主要和調度事件相關，當發生任務喚醒、任務創建、tick 到來等調度事件的時候，我們可以檢查當前系統的不均衡情況，並酌情進行任務遷移，以便讓系統負載處於平衡狀態。

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

由於 NUMA 是以層次關係呈現，因此在執行進程的負載均衡也會呈現不同的成本開銷。進程在同一個物理 Core 上的邏輯 Core 之前遷移開銷最小；

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

內核採用調度域解決現代多 CPU 多核的問題，調度域是具有相同屬性和調度策略的處理器集合，任務進程可以在它們內部按照某種策略進行調度遷移。

進程在多 CPU 的負載均衡也是針對調度域的，調度域根據超線程、多核、SMP、NUMA 等系統架構劃分爲不同的等級，不同的等級架構通過指針鏈接在一起，從而形成樹狀結構；在進程的負載均衡過程中，從樹的葉子節點往上遍歷，直到所有的域中的負載都是平衡的。目前內核進程調度按照如下的原則進行, 這些原則都是按照 cpu 架構以及通信路徑來進行的。

四、CPU 負載均衡機制實現方式

4.1 如何做負載均衡

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

在上面的結構中，sched domain 是分成兩個 level，base domain 稱爲 MC domain（multi core domain），頂層的 domain 稱爲 DIE domain。頂層的 DIE domain 覆蓋了系統中所有的 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 環形鏈表。不同 CPU 的 MC domain 的環形鏈表首元素（即 sched domain 中的 groups 成員指向的那個 sched group）是不同的，對於 cpu0 的 MC domain，其 groups 環形鏈表的順序是 0-1-2-3，對於 cpu1 的 MC domain，其 groups 環形鏈表的順序是 1-2-3-0，以此類推。大核 MC domain 也是類似，這裏不再贅述。

對於非 base domain 而言，其 sched group 有多個 cpu，覆蓋其 child domain 的所有 cpu。例如上面圖例中的 DIE domain，它有兩個 child domain，分別是大核 domain 和小核 domian，因此，DIE domain 的 groups 環形鏈表有兩個元素，分別是小核 group 和大核 group。不同 CPU 的 DIE domain 的環形鏈表首元素（即鏈表頭）是不同的，對於 cpu0 的 DIE domain，其 groups 環形鏈表的順序是（0,1,2,3）--（4,5,6,7），對於 cpu6 的 MC domain，其 groups 環形鏈表的順序是（4,5,6,7）--（0,1,2,3），以此類推。

爲了減少鎖的競爭，每一個 cpu 都有自己的 MC domain 和 DIE domain，並且形成了 sched domain 之間的層級結構。在 MC domain，其所屬 cpu 形成 sched group 的環形鏈表結構，各個 cpu 對應的 MC domain 的 groups 成員指向環形鏈表中的自己的 cpu group。在 DIE domain，cluster 形成 sched group 的環形鏈表結構，各個 cpu 對應的 DIE domain 的 groups 成員指向環形鏈表中的自己的 cluster group。

4.2 負載均衡的基本過程

負載均衡不是一個全局 CPU 之間的均衡，實際上那樣做也不現實，當系統的 CPU 數量較大的時候，很難一次性的完成所有 CPU 之間的均衡，這也是提出 sched domain 的原因之一。我們以週期性均衡爲例來描述負載均衡的基本過程。當一個 CPU 上進行週期性負載均衡的時候，我們總是從 base domain 開始（對於上面的例子，base domain 就是 MC domain），檢查其所屬 sched group 之間（即各個 cpu 之間）的負載均衡情況，如果有不均衡情況，那麼會在該 cpu 所屬 cluster 之間進行遷移，以便維護 cluster 內各個 cpu core 的任務負載均衡。

有了各個 CPU 上的負載統計以及 CPU 的算力信息，我們很容易知道 MC domain 上的不均衡情況。爲了讓算法更加簡單，Linux 內核的負載均衡算法只允許 CPU 拉任務，這樣，MC domain 的均衡大致需要下面幾個步驟：

1. 找到 MC domain 中最繁忙的 sched group

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

3. 從選中的那個繁忙的 cpu 上拉取任務，具體拉取多少的任務到本 CPU runqueue 上是和不均衡的程度相關，越是不均衡，拉取的任務越多。

完成 MC domain 均衡之後，繼續沿着 sched domain 層級結構向上檢查，進入 DIE domain，在這個 level 的 domain 上，我們仍然檢查其所屬 sched group 之間（即各個 cluster 之間）的負載均衡情況，如果有不均衡的情況，那麼會進行 inter-cluster 的任務遷移。基本方法和 MC domain 類似，只不過在計算均衡的時候，DIE domain 不再考慮單個 CPU 的負載和算力，它考慮的是：

1. 該 sched group 的負載，即 sched group 中所有 CPU 負載之和

2. 該 sched group 的算力，即 sched group 中所有 CPU 算力之和

4.3 線程的負載均衡

在 Linux 內核進程 CPU 負載均衡機制中，線程的負載均衡是確保系統高效運行的關鍵環節，它主要針對實時（RT，Real - Time）任務和普通任務採取不同的策略。

⑴RT 任務

RT 任務對時間的要求極爲嚴格，需要確保能夠及時響應和執行。在 Linux 系統中，對於 RT 任務的負載均衡，採用了一種高效的分配方式，即把 n 個優先級最高的 RT 任務自動分配到 n 個核上 。這是因爲 RT 任務的實時性要求決定了它們需要儘快得到 CPU 的執行機會，將這些高優先級的 RT 任務分散到多個核心上，可以避免任務之間的競爭和延遲，確保每個任務都能在最短的時間內得到處理。

在實際實現過程中，主要通過 pull_rt_task 和 push_rt_task 這兩個函數來完成任務的遷移操作 。當系統中出現新的高優先級 RT 任務時，會調用 push_rt_task 函數，將任務推送到相對空閒的 CPU 核心上，以確保任務能夠及時執行；而當某個 CPU 核心上的 RT 任務執行完畢，或者負載過高需要調整時，則會調用 pull_rt_task 函數，從其他核心上拉取合適的 RT 任務到當前核心，從而實現負載的均衡。這種基於任務優先級的分配方式，能夠充分利用多核 CPU 的並行處理能力，保證 RT 任務的實時性需求，使得系統在處理對時間敏感的任務時，能夠保持高效穩定的運行狀態。

⑵普通任務

普通任務的負載均衡則主要通過週期性負載均衡、idle 時負載均衡以及 fork 和 exec 時負載均衡這幾種方式來實現。

週期性負載均衡是在時鐘 tick 到來時進行的 。每當時鐘 tick 發生，系統就會檢查各個核的負載情況，優先讓空閒核工作。如果發現某個核處於空閒狀態，而其他核負載較重，就會從負載重的核中 pull 任務到空閒核，或者將空閒核的任務 push 給負載較輕的核 。例如，在一個四核系統中，假設 CPU0 和 CPU1 負載較高，而 CPU2 和 CPU3 處於空閒狀態。當時鍾 tick 到來時，系統會檢測到這種負載不均衡的情況，然後從 CPU0 和 CPU1 的 runqueue 隊列中挑選一些普通任務，遷移到 CPU2 和 CPU3 上執行，這樣就能讓各個核都能參與到任務處理中，避免出現部分核過度忙碌，而部分核閒置的情況，從而實現系統負載的均衡。

idle 時負載均衡是當某個核進入 idle 狀態時觸發的 。當一個核進入 idle 狀態，說明它當前沒有可執行的任務，處於空閒狀態。此時，這個核會主動去檢查其他核的負載情況，如果發現其他核有任務在運行，就會主動從其他核 pull 任務過來執行 。例如，在一個八核系統中，假設 CPU5 進入 idle 狀態，它會查看其他七個核的 runqueue 隊列，發現 CPU3 上有較多的普通任務在等待執行，那麼 CPU5 就會從 CPU3 的 runqueue 隊列中選取一些任務，將其遷移到自己的隊列中並開始執行，這樣可以充分利用空閒的 CPU 資源，提高系統的整體處理能力。

fork 和 exec 時負載均衡則與新進程的創建和執行密切相關 。當系統執行 fork 操作創建一個新進程，或者通過 exec 函數族執行新的程序時，會把新創建的進程放到最閒的核上去運行 。這是因爲新進程在啓動階段可能需要進行一些初始化操作，將其分配到最閒的核上，可以避免對其他正在忙碌執行任務的核造成額外的負擔，同時也能讓新進程儘快獲得 CPU 資源，順利完成初始化和後續的執行操作。例如，當我們在系統中啓動一個新的應用程序時，系統會根據各個核的負載情況，將這個新程序對應的進程分配到當前負載最輕的核上運行，確保新進程能夠高效啓動和運行。

4.4 中斷負載均衡

在 Linux 系統中，負載不僅來源於進程，中斷也是重要的負載來源之一。中斷分爲硬件中斷和軟中斷，它們在系統運行中起着不同但又緊密相關的作用。

硬件中斷通常是由外部設備（如網卡、硬盤、鍵盤等）引發的信號，用於通知 CPU 有需要立即處理的事件 。例如，當網卡接收到數據時，會產生一個硬件中斷，通知 CPU 有新的數據到達需要處理。硬件中斷的處理時間一般較短，在 Linux 2.6.34 版本之後，內核不再支持中斷嵌套 。

當硬件中斷髮生並完成數據接收等操作後，通常會調用軟中斷來進行後續的處理，比如處理 TCP/IP 包 。軟中斷可以嵌套，它主要負責處理那些可以稍微延遲處理的任務，是對硬件中斷未完成工作的一種推後執行機制。在 top 命令中，hi 表示硬中斷時間（isr，屏蔽中斷），si 表示軟中斷 。當網絡流量較大時，CPU 花在硬中斷和軟中斷上的時間會比較多，此時就需要進行中斷的負載均衡，以確保系統的高效運行。

在新網卡多隊列的情況下，實現中斷負載均衡可以通過設置中斷親和性來完成 。例如，在一個 4 核的系統中，如果網卡有 4 個隊列，每個隊列都可以單獨產生中斷，並且硬件支持負載均衡 。那麼可以將一個隊列綁定到一個核上，通過將每個中斷號分別設置 affinity，綁定到指定 CPU，就能讓所有 CPU 都參與到網卡發送包服務中 。

比如，通過查看 / proc/interrupts 文件找到與網卡相關的中斷號，然後使用命令 sudo sh -c “echo 3> /proc/irq/124/smp_affinity”，就可以將中斷號爲 124 的中斷綁定到 CPU3 上 。這樣，當網卡的不同隊列產生中斷時，就會被分配到不同的 CPU 核心上進行處理，避免了所有中斷都集中在一個核心上，從而實現了中斷的負載均衡，提高了系統處理網絡數據的能力。

然而，有些網卡只有一個隊列，這種情況下，單個核拋出的軟中斷只能在這個核上運行，導致一個隊列拋出的軟中斷（如 TCP/IP 層處理）只能在這一個核執行，其他核會處於空閒狀態，無法充分利用多核 CPU 的優勢。爲了解決這個問題，Google 推出了 RPS（Receive Packet Steering）補丁 。RPS 補丁的原理是由單一 CPU 核響應硬件中斷，然後將大量網絡接收包通過多核間中斷方式分發給其他空閒核 。

例如，在一個單核網卡隊列收包的系統中，默認情況下收包操作只在 CPU0 上執行。通過設置 RPS，如 echo 3 > /sys/class/net/eth0/queues/rx-0/rps_cpus，可以將收包操作均衡到 CPU0 和 CPU1 上 。這樣，當大量網絡數據包到達時，原本只能由一個核處理的任務，現在可以由多個核共同處理，大大提高了系統處理網絡數據的效率，實現了軟中斷的負載均衡，充分發揮了多核 CPU 的性能優勢。

4.5 其他需要考慮的事項

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

在引入異構計算系統之後，任務在 placement 的時候可以有所選擇。如果負載比較輕，或者該任務對延遲要求不高，我們可以放置在小核 CPU 執行，如果負載比較重或者該該任務和用戶體驗相關，那麼我們傾向於讓它在算力更高的 CPU 上執行。爲了應對這種狀況，內核引入了 misfit task 的概念。一旦任務被標記了 misfit task，那麼負載均衡算法要考慮及時的將該任務進行 upmigration，從而讓重載任務儘快完成，或者提升該任務的執行速度，從而提升用戶體驗。

除了性能，負載均衡也會帶來功耗的收益。例如系統有 4 個 CPU，共計 8 個進入執行態的任務（負載相同）。這些任務在 4 個 CPU 上的排布有兩種選擇：

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

• （2）每個 CPU runqueue 掛 2 個任務

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vIhKGhIRGRBiSIGpalZeHA