CPU：一核有難，八核圍觀

在《一文讀懂 | 進(jìn)程怎么綁定 CPU》這篇文章中介紹過，在 Linux 內(nèi)核中會(huì)為每個(gè) CPU 創(chuàng)建一個(gè)可運(yùn)行進(jìn)程隊(duì)列，由于每個(gè) CPU 都擁有一個(gè)可運(yùn)行進(jìn)程隊(duì)列，那么就有可能會(huì)出現(xiàn)每個(gè)可運(yùn)行進(jìn)程隊(duì)列之間的進(jìn)程數(shù)不一樣的問題，這就是所謂的 負(fù)載不均衡 問題，如下圖所示：

（圖1）

最極端的情況是，一個(gè) CPU 的可運(yùn)行進(jìn)程隊(duì)列擁有非常多的進(jìn)程，而其他 CPU 的可運(yùn)行進(jìn)程隊(duì)列為空，這就是著名的 一核有難，多核圍觀，如下圖：

（圖2）

為了避免這個(gè)問題的出現(xiàn)，Linux 內(nèi)核實(shí)現(xiàn)了 CPU 可運(yùn)行進(jìn)程隊(duì)列之間的負(fù)載均衡。接下來，我們將會(huì)介紹 CPU 間的負(fù)載均衡的實(shí)現(xiàn)原理。

本文使用的內(nèi)核版本為：Linux-2.6.23

CPU 間負(fù)載均衡原理

CPU 間負(fù)載不均衡的根本原因就是，CPU 的可運(yùn)行進(jìn)程隊(duì)列中的進(jìn)程數(shù)量不均衡導(dǎo)致的。所以，要解決 CPU 間負(fù)載不均衡的方法就是：將最繁忙的 CPU 可運(yùn)行進(jìn)程隊(duì)列的一些進(jìn)程遷移到其他比較空閑的 CPU 中，從而達(dá)到 CPU 間負(fù)載均衡的目的。

當(dāng)然，在 2.6.0 版本的內(nèi)核的確是這樣實(shí)現(xiàn)的，我們可以看看其實(shí)現(xiàn)代碼：

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 運(yùn)行隊(duì)列
    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. 從最繁忙運(yùn)行隊(duì)列中取得一個(gè)進(jìn)程
    tmp = list_entry(curr, task_t, run_list);
    ...

    // 3. 把進(jìn)程從最繁忙的可運(yùn)行隊(duì)列中遷移到當(dāng)前可運(yùn)行隊(duì)列中
    pull_task(busiest, array, tmp, this_rq, this_cpu);
    ...
}

load_balance 函數(shù)主要用于解決 CPU 間負(fù)載均衡問題，其主要完成以下 3 個(gè)步驟：

• 從所有 CPU 的可運(yùn)行隊(duì)列中找到最繁忙的可運(yùn)行隊(duì)列。
• 從最繁忙可運(yùn)行隊(duì)列中取得一個(gè)進(jìn)程。
• 把進(jìn)程從最繁忙的可運(yùn)行隊(duì)列中遷移到當(dāng)前可運(yùn)行隊(duì)列中。

這是 2.6.0 版本的解決方案，但這個(gè)方案并不是最優(yōu)的，因?yàn)楝F(xiàn)代 CPU 架構(gòu)是非常復(fù)雜的，比如一個(gè)物理 CPU 有多個(gè)核心（多核），而每個(gè)核心又可以通過超線程（Hyper-Threading）來實(shí)現(xiàn)多個(gè)邏輯 CPU，如下圖所示：

（圖3）

如上圖所示，一個(gè)物理 CPU 中擁有 4 個(gè)核心，而每個(gè)核心又擁有 2 個(gè)超線程。在 Linux 內(nèi)核中，會(huì)為每個(gè)超線程定義一個(gè)可運(yùn)行進(jìn)程隊(duì)列，所以 Linux 內(nèi)核會(huì)為上面的 CPU 定義 8 個(gè)可運(yùn)行進(jìn)程隊(duì)列。

現(xiàn)在問題來了，在上面的 CPU 架構(gòu)中，不同的可運(yùn)行隊(duì)列之間的進(jìn)程遷移代價(jià)是不一樣的。因?yàn)橥粋€(gè)核心的不同超線程共用了所有的緩存，所以同一個(gè)核心不同超線程間的進(jìn)程遷移代價(jià)是最小的。

而同一個(gè)物理 CPU 不同核心間也會(huì)共用某些緩存，所以不同核心間的進(jìn)程遷移的代價(jià)會(huì)比同一核心不同超線程間的進(jìn)程遷移稍大。由于現(xiàn)在很多主板都支持安裝多個(gè)物理 CPU，而不同物理 CPU 間基本不會(huì)共用緩存，所以不同物理 CPU 間的進(jìn)程遷移代價(jià)最大。如下圖所示（圖中的 L1、L2 和 L3 分別指一級(jí)、二級(jí)和三級(jí)緩存）：

（圖4）

為了解決進(jìn)程遷移成本的問題，新版本的 Linux 內(nèi)核引入了 調(diào)度域 和 調(diào)度組。

調(diào)度域與調(diào)度組

從前面的分析可知，根據(jù) CPU 的物理架構(gòu)可以劃分為：不同的物理 CPU、相同 CPU 不同的核心、相同核心不同的超線程等，如下圖所示：

（圖5）

在 Linux 內(nèi)核中，把這個(gè)層級(jí)成為 調(diào)度域。從前面的分析可知，越下層的調(diào)度域共用的緩存就越多，所以在進(jìn)程遷移時(shí)，優(yōu)先從底層的調(diào)度域開始進(jìn)行。

由于內(nèi)核為每個(gè)超線程定義一個(gè)可運(yùn)行隊(duì)列，所以圖 3 中的 CPU 擁有 8 個(gè)可運(yùn)行隊(duì)列。而根據(jù)不同的調(diào)度域，可以把這 8 個(gè)可運(yùn)行隊(duì)列劃分為不同的 調(diào)度組，如下圖所示：

（圖6）

如上圖所示，由于每個(gè)超線程都擁有一個(gè)可運(yùn)行隊(duì)列，所以圖 3 的 CPU 擁有 8 個(gè)可運(yùn)行隊(duì)列，而這些可運(yùn)行隊(duì)列可以根據(jù)不同的核心來劃分為 4 個(gè)調(diào)度組，而這 4 個(gè)調(diào)度組可以根據(jù)不同的物理 CPU 來劃分成 1 個(gè)調(diào)度組。

由于越底層的調(diào)度域共用的緩存越多，所以對(duì) CPU 可運(yùn)行隊(duì)列進(jìn)行負(fù)載均衡時(shí)，優(yōu)先從底層調(diào)度域開始。比如把 Thread0 可運(yùn)行隊(duì)列的進(jìn)程遷移到 Thread1 可運(yùn)行隊(duì)列的代價(jià)要比遷移到 Thread2 可運(yùn)行隊(duì)列的小，這是由于 Thread0 與 Thread1 屬于同一個(gè)核心，同一個(gè)核心共用所有的 CPU 緩存。

在 Linux 內(nèi)核中，調(diào)度域使用 sched_domain 結(jié)構(gòu)表示，而調(diào)度組使用 sched_group 結(jié)構(gòu)表示。我們來看看 sched_domain 結(jié)構(gòu)的定義：

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 結(jié)構(gòu)各個(gè)字段的作用：

• parent：由于調(diào)度域是分層的，上層調(diào)度域是下層的調(diào)度域的父親，所以這個(gè)字段指向的是當(dāng)前調(diào)度域的上層調(diào)度域。
• child：如上所述，這個(gè)字段用來指向當(dāng)前調(diào)度域的下層調(diào)度域。
• groups：每個(gè)調(diào)度域都擁有一批調(diào)度組，所以這個(gè)字段指向的是屬于當(dāng)前調(diào)度域的調(diào)度組列表。
• span：這個(gè)字段主要用來標(biāo)記屬于當(dāng)前調(diào)度域的 CPU 列表（每個(gè)位表示一個(gè) CPU）。

我們接著分析一下 sched_group 結(jié)構(gòu)，其定義如下：

struct sched_group {
    struct sched_group *next;
    cpumask_t           cpumask;
    ...
};

下面介紹一下 sched_group 結(jié)構(gòu)各個(gè)字段的作用：

• next：指向?qū)儆谕粋€(gè)調(diào)度域的下一個(gè)調(diào)度組。
• cpumask：用于標(biāo)記屬于當(dāng)前調(diào)度組的 CPU 列表（每個(gè)位表示一個(gè) CPU）。

它們之間的關(guān)系如下圖所示：

（圖7）

CPU 間負(fù)載均衡實(shí)現(xiàn)

要實(shí)現(xiàn) CPU 間的負(fù)載均衡，只需要將最繁忙的可運(yùn)行隊(duì)列中的一部分進(jìn)程遷移到空閑的可運(yùn)行隊(duì)列中即可。但由于 CPU 緩存的原因，對(duì)使用不同的 CPU 緩存的可運(yùn)行隊(duì)列之間進(jìn)行進(jìn)程遷移，將會(huì)導(dǎo)致緩存丟失，從而導(dǎo)致性能損耗。所以，Linux 內(nèi)核會(huì)優(yōu)先對(duì)使用相同 CPU 緩存的可運(yùn)行隊(duì)列之間進(jìn)行進(jìn)程遷移。

1. CPU 間負(fù)載均衡觸發(fā)時(shí)機(jī)

當(dāng) CPU 的負(fù)載不均衡時(shí)，內(nèi)核就需要對(duì) CPU 進(jìn)行負(fù)載均衡。負(fù)載均衡的觸發(fā)時(shí)機(jī)比較多，如進(jìn)程被創(chuàng)建、進(jìn)程被喚醒、進(jìn)程休眠和時(shí)鐘中斷等，這里我們介紹一下在時(shí)鐘中斷時(shí)怎么進(jìn)行 CPU 間的負(fù)載均衡。

在 Linux 內(nèi)核中是通過 rq 結(jié)構(gòu)來描述一個(gè)可運(yùn)行進(jìn)程隊(duì)列的，它有個(gè)名為 sd 的字段用于指向其所屬的 調(diào)度域 層級(jí)的最底層，如下所示：

struct rq {
    ...
    struct sched_domain *sd;
    ...
}

它與調(diào)度域和調(diào)度組的關(guān)系如下圖所示：

（圖8）

在時(shí)鐘中斷下半部處理中，會(huì)通過調(diào)用 run_rebalance_domains 函數(shù)來對(duì) CPU 進(jìn)行負(fù)載均衡處理，而 run_rebalance_domains 接著會(huì)通過調(diào)用 rebalance_domains 函數(shù)來完成負(fù)載均衡的工作，其實(shí)現(xiàn)如下：

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;

    // 遍歷可運(yùn)行隊(duì)列的調(diào)度組層級(jí) (從最底層開始)
    for_each_domain(cpu, sd) {
        ...
        // 由于對(duì) CPU 進(jìn)行負(fù)載均衡可能會(huì)導(dǎo)致 CPU 緩存丟失
        // 所以對(duì) CPU 進(jìn)行負(fù)載均衡不能太頻繁, 必須隔一段時(shí)間才能進(jìn)行
        // 這里就是判斷上次進(jìn)行負(fù)載均衡與這次的間隔是否已經(jīng)達(dá)到合適的時(shí)間
        // 如果時(shí)間間隔已經(jīng)達(dá)到一段時(shí)間, 那么就調(diào)用 load_balance 函數(shù)進(jìn)行負(fù)載均衡
        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;
        }
        ...
    }
    ...
}

由于每個(gè) CPU（超線程）都有一個(gè)可運(yùn)行隊(duì)列，而 rebalance_domains 函數(shù)的工作就是獲取當(dāng)前 CPU （超線程）的可運(yùn)行隊(duì)列，然后從最底層開始遍歷其調(diào)度域?qū)蛹?jí)（由于越底層的調(diào)度域，進(jìn)行進(jìn)程遷移的代價(jià)越?。?。

由于對(duì) CPU 進(jìn)行負(fù)載均衡可能會(huì)導(dǎo)致 CPU 緩存丟失，所以對(duì) CPU 進(jìn)行負(fù)載均衡不能太頻繁（需要隔一段時(shí)間才能進(jìn)行）。那么在對(duì) CPU 進(jìn)行負(fù)載均衡前，就需要判斷上次進(jìn)行負(fù)載均衡與這次的時(shí)間間隔是否合理。如果時(shí)間間隔合理, 那么就調(diào)用 load_balance 函數(shù)對(duì)調(diào)度域進(jìn)行負(fù)載均衡。

load_balance 函數(shù)實(shí)現(xiàn)如下：

static int
load_balance(int this_cpu, struct rq *this_rq, struct sched_domain *sd,
             enum cpu_idle_type idle, int *balance)
{
    ...

redo:
    // 1. 從調(diào)度域中找到一個(gè)最繁忙的調(diào)度組
    group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
                               &cpus, balance);
    ...

    // 2. 從最繁忙的調(diào)度組中找到一個(gè)最繁忙的運(yùn)行隊(duì)列
    busiest = find_busiest_queue(group, idle, imbalance, &cpus);
    ...

    if (busiest->nr_running > 1) {
        ...
        // 3. 從最繁忙的運(yùn)行隊(duì)列中遷移一些任務(wù)到當(dāng)前任務(wù)隊(duì)列
        ld_moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle,
                              &all_pinned);
        ...
    }
    ...
    return 0;
}

load_balance 函數(shù)主要完成 3 個(gè)工作：

• 從 調(diào)度域 中找到一個(gè)最繁忙的 調(diào)度組。
• 從最繁忙的 調(diào)度組 中找到一個(gè)最繁忙的 可運(yùn)行隊(duì)列。
• 從最繁忙的 可運(yùn)行隊(duì)列 中遷移一些任務(wù)到當(dāng)前 可運(yùn)行隊(duì)列。

這樣就完成了 CPU 間的負(fù)載均衡處理。