一文讀懂 CPU 負載均衡實現

在《一文讀懂 | 進程怎麼綁定 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 個步驟：

這是 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 結構各個字段的作用：

我們接着分析一下 sched_group 結構，其定義如下：

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

下面介紹一下 sched_group 結構各個字段的作用：

它們之間的關係如下圖所示：

（圖 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 間的負載均衡處理。

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

猜你喜歡