在《一文讀懂 | 進程怎么綁定 CPU》這篇文章中介紹過，在 Linux 內核中會為每個 CPU 創建一個可運行進程隊列，由于每個 CPU 都擁有一個可運行進程隊列，那么就有可能會出現每個可運行進程隊列之間的進程數不一樣的問題，這就是所謂的 負載不均衡 問題，如下圖所示：
（圖1）
最極端的情況是，一個 CPU 的可運行進程隊列擁有非常多的進程，而其他 CPU 的可運行進程隊列為空，這就是著名的 一核有難，多核圍觀，如下圖：
（圖2）
為了避免這個問題的出現，Linux 內核實現了 CPU 可運行進程隊列之間的負載均衡。接下來，我們將會介紹 CPU 間的負載均衡的實現原理。
本文使用的內核版本為：Linux-2.6.23
CPU 間負載均衡原理
CPU 間負載不均衡的根本原因就是，CPU 的可運行進程隊列中的進程數量不均衡導致的。所以，要解決 CPU 間負載不均衡的方法就是：將最繁忙的 CPU 可運行進程隊列的一些進程遷移到其他比較空閑的 CPU 中，從而達到 CPU 間負載均衡的目的。
當然，在 2.6.0 版本的內核的確是這樣實現的，我們可以看看其實現代碼：
static void
load_balance(runqueue_t *this_rq, int idle, cpumask_t cpumask)
{
int imbalance, idx, this_cpu = smp_processor_id();
runqueue_t *busiest;
prio_array_t *array;
struct list_head *head, *curr;
task_t *tmp;
// 1. 找到最繁忙的 CPU 運行隊列
busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance, cpumask);
if (!busiest)
goto out;
...
head = array->queue + idx;
curr = head->prev;
skip_queue:
// 2. 從最繁忙運行隊列中取得一個進程
tmp = list_entry(curr, task_t, run_list);
...
// 3. 把進程從最繁忙的可運行隊列中遷移到當前可運行隊列中
pull_task(busiest, array, tmp, this_rq, this_cpu);
...
}
load_balance 函數主要用于解決 CPU 間負載均衡問題，其主要完成以下 3 個步驟：
從所有 CPU 的可運行隊列中找到最繁忙的可運行隊列。 從最繁忙可運行隊列中取得一個進程。 把進程從最繁忙的可運行隊列中遷移到當前可運行隊列中。
這是 2.6.0 版本的解決方案，但這個方案并不是最優的，因為現代 CPU 架構是非常復雜的，比如一個物理 CPU 有多個核心（多核），而每個核心又可以通過超線程（Hyper-Threading）來實現多個邏輯 CPU，如下圖所示：
（圖3）
如上圖所示，一個物理 CPU 中擁有 4 個核心，而每個核心又擁有 2 個超線程。在 Linux 內核中，會為每個超線程定義一個可運行進程隊列，所以 Linux 內核會為上面的 CPU 定義 8 個可運行進程隊列。
現在問題來了，在上面的 CPU 架構中，不同的可運行隊列之間的進程遷移代價是不一樣的。因為同一個核心的不同超線程共用了所有的緩存，所以同一個核心不同超線程間的進程遷移代價是最小的。
而同一個物理 CPU 不同核心間也會共用某些緩存，所以不同核心間的進程遷移的代價會比同一核心不同超線程間的進程遷移稍大。由于現在很多主板都支持安裝多個物理 CPU，而不同物理 CPU 間基本不會共用緩存，所以不同物理 CPU 間的進程遷移代價最大。如下圖所示（圖中的 L1、L2 和 L3 分別指一級、二級和三級緩存）：
（圖4）
為了解決進程遷移成本的問題，新版本的 Linux 內核引入了 調度域 和 調度組。
調度域與調度組
從前面的分析可知，根據 CPU 的物理架構可以劃分為：不同的物理 CPU、相同 CPU 不同的核心、相同核心不同的超線程等，如下圖所示：
（圖5）
在 Linux 內核中，把這個層級成為 調度域。從前面的分析可知，越下層的調度域共用的緩存就越多，所以在進程遷移時，優先從底層的調度域開始進行。
由于內核為每個超線程定義一個可運行隊列，所以圖 3 中的 CPU 擁有 8 個可運行隊列。而根據不同的調度域，可以把這 8 個可運行隊列劃分為不同的 調度組，如下圖所示：
（圖6）
如上圖所示，由于每個超線程都擁有一個可運行隊列，所以圖 3 的 CPU 擁有 8 個可運行隊列，而這些可運行隊列可以根據不同的核心來劃分為 4 個調度組，而這 4 個調度組可以根據不同的物理 CPU 來劃分成 1 個調度組。
由于越底層的調度域共用的緩存越多，所以對 CPU 可運行隊列進行負載均衡時，優先從底層調度域開始。比如把 Thread0 可運行隊列的進程遷移到 Thread1 可運行隊列的代價要比遷移到 Thread2 可運行隊列的小，這是由于 Thread0 與 Thread1 屬于同一個核心，同一個核心共用所有的 CPU 緩存。
在 Linux 內核中，調度域使用 sched_domain 結構表示，而調度組使用 sched_group 結構表示。我們來看看 sched_domain 結構的定義：
struct sched_domain {
struct sched_domain *parent; /* top domain must be null terminated */
struct sched_domain *child; /* bottom domain must be null terminated */
struct sched_group *groups; /* the balancing groups of the domain */
cpumask_t span; /* span of all CPUs in this domain */
...
};
下面介紹一下 sched_domain 結構各個字段的作用：
parent：由于調度域是分層的，上層調度域是下層的調度域的父親，所以這個字段指向的是當前調度域的上層調度域。child：如上所述，這個字段用來指向當前調度域的下層調度域。groups：每個調度域都擁有一批調度組，所以這個字段指向的是屬于當前調度域的調度組列表。span：這個字段主要用來標記屬于當前調度域的 CPU 列表（每個位表示一個 CPU）。
我們接著分析一下 sched_group 結構，其定義如下：
struct sched_group {
struct sched_group *next;
cpumask_t cpumask;
...
};
下面介紹一下 sched_group 結構各個字段的作用：
next：指向屬于同一個調度域的下一個調度組。cpumask：用于標記屬于當前調度組的 CPU 列表（每個位表示一個 CPU）。
它們之間的關系如下圖所示：
（圖7）
CPU 間負載均衡實現
要實現 CPU 間的負載均衡，只需要將最繁忙的可運行隊列中的一部分進程遷移到空閑的可運行隊列中即可。但由于 CPU 緩存的原因，對使用不同的 CPU 緩存的可運行隊列之間進行進程遷移，將會導致緩存丟失，從而導致性能損耗。所以，Linux 內核會優先對使用相同 CPU 緩存的可運行隊列之間進行進程遷移。
1. CPU 間負載均衡觸發時機
當 CPU 的負載不均衡時，內核就需要對 CPU 進行負載均衡。負載均衡的觸發時機比較多，如進程被創建、進程被喚醒、進程休眠和時鐘中斷等，這里我們介紹一下在時鐘中斷時怎么進行 CPU 間的負載均衡。
在 Linux 內核中是通過 rq 結構來描述一個可運行進程隊列的，它有個名為 sd 的字段用于指向其所屬的 調度域 層級的最底層，如下所示：
struct rq {
...
struct sched_domain *sd;
...
}
它與調度域和調度組的關系如下圖所示：
（圖8）
在時鐘中斷下半部處理中，會通過調用 run_rebalance_domains 函數來對 CPU 進行負載均衡處理，而 run_rebalance_domains 接著會通過調用 rebalance_domains 函數來完成負載均衡的工作，其實現如下：
static inline void
rebalance_domains(int cpu, enum cpu_idle_type idle)
{
int balance = 1;
struct rq *rq = cpu_rq(cpu);
unsigned long interval;
struct sched_domain *sd;
unsigned long next_balance = jiffies + 60*HZ;
int update_next_balance = 0;
// 遍歷可運行隊列的調度組層級 (從最底層開始)
for_each_domain(cpu, sd) {
...
// 由于對 CPU 進行負載均衡可能會導致 CPU 緩存丟失
// 所以對 CPU 進行負載均衡不能太頻繁, 必須隔一段時間才能進行
// 這里就是判斷上次進行負載均衡與這次的間隔是否已經達到合適的時間
// 如果時間間隔已經達到一段時間, 那么就調用 load_balance 函數進行負載均衡
if (time_after_eq(jiffies, sd->last_balance + interval)) {
if (load_balance(cpu, rq, sd, idle, &balance)) {
idle = CPU_NOT_IDLE;
}
sd->last_balance = jiffies;
}
...
}
...
}
由于每個 CPU（超線程）都有一個可運行隊列，而 rebalance_domains 函數的工作就是獲取當前 CPU （超線程）的可運行隊列，然后從最底層開始遍歷其調度域層級（由于越底層的調度域，進行進程遷移的代價越小）。
由于對 CPU 進行負載均衡可能會導致 CPU 緩存丟失，所以對 CPU 進行負載均衡不能太頻繁（需要隔一段時間才能進行）。那么在對 CPU 進行負載均衡前，就需要判斷上次進行負載均衡與這次的時間間隔是否合理。如果時間間隔合理, 那么就調用 load_balance 函數對調度域進行負載均衡。
load_balance 函數實現如下：
static int
load_balance(int this_cpu, struct rq *this_rq, struct sched_domain *sd,
enum cpu_idle_type idle, int *balance)
{
...
redo:
// 1. 從調度域中找到一個最繁忙的調度組
group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
&cpus, balance);
...
// 2. 從最繁忙的調度組中找到一個最繁忙的運行隊列
busiest = find_busiest_queue(group, idle, imbalance, &cpus);
...
if (busiest->nr_running > 1) {
...
// 3. 從最繁忙的運行隊列中遷移一些任務到當前任務隊列
ld_moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle,
&all_pinned);
...
}
...
return 0;
}
load_balance 函數主要完成 3 個工作：
從 調度域中找到一個最繁忙的調度組。從最繁忙的 調度組中找到一個最繁忙的可運行隊列。從最繁忙的 可運行隊列中遷移一些任務到當前可運行隊列。
這樣就完成了 CPU 間的負載均衡處理。