上帝視角：多核系統的負載均衡

我們知道爲了 CPU 之間減少 “干擾”，每個 CPU 上都有一個任務隊列。運行的過程種可能會出現有的 CPU 很忙，有的 CPU 很閒，如下圖所示：

爲了避免這個問題的出現，Linux 內核實現了 CPU 可運行進程隊列之間的負載均衡。

因爲負載均衡是在多個核上的均衡，所以在講解負載均衡之前，我們先看下多核的架構。

將 task 從負載較重的 CPU 上轉移到負載相對較輕的 CPU 上執行，這個過程就是負載均衡的過程。

多核架構

這裏以 Arm64 的 NUMA(Non Uniform Memory Access) 架構爲例，看下多核架構的組成。

從圖中可以看出，這是非一致性內存訪問。每個 CPU 訪問 local memory，速度更快，延遲更小。因爲 Interconnect 模塊的存在，整體的內存會構成一個內存池，所以 CPU 也能訪問 remote memory，但是相對 local memory 來說速度更慢，延遲更大。

我們知道一個多核心的 SOC 片上系統，內部結構是很複雜的。內核採用 CPU 拓撲結構來描述一個 SOC 的架構，使用調度域和調度組來描述 CPU 之間的層次關係。

CPU 拓撲

每一個 CPU 都會維護這麼一個結構體實例，用來描述 CPU 拓撲。

struct cpu_topology {
 int thread_id;
 int core_id;
 int cluster_id;
 cpumask_t thread_sibling;
 cpumask_t core_sibling;
};

thread_id: 從 mpidr_el1 寄存器中獲取
core_id：從 mpidr_el1 寄存器中獲取
cluster_id：從 mpidr_el1 寄存器中獲取
thread_sibling：當前 CPU 的兄弟 thread。
core_sibling：當前 CPU 的兄弟 Core，即在同一個 Cluster 中的 CPU。

可以通過 /sys/devices/system/cpu/cpuX/topology 查看 cpu topology 的信息。

cpu_topology 結構體是通過函數 parse_dt_topology() 解析 DTS 中的信息建立的:

kernel_init() -> kernel_init_freeable() -> smp_prepare_cpus() -> init_cpu_topology() -> parse_dt_topology()

static int __init parse_dt_topology(void)
{
 struct device_node *cn, *map;
 int ret = 0;
 int cpu;

 cn = of_find_node_by_path("/cpus");          ------(1)
 if (!cn) {
  pr_err("No CPU information found in DT\n");
  return 0;
 }

 /*
  * When topology is provided cpu-map is essentially a root
  * cluster with restricted subnodes.
  */
 map = of_get_child_by_name(cn, "cpu-map");   ------(2)
 if (!map)
  goto out;

 ret = parse_cluster(map, 0);                 ------(3)
 if (ret != 0)
  goto out_map;

 topology_normalize_cpu_scale();

 /*
  * Check that all cores are in the topology; the SMP code will
  * only mark cores described in the DT as possible.
  */
 for_each_possible_cpu(cpu)
  if (cpu_topology[cpu].cluster_id == -1)
   ret = -EINVAL;

out_map:
 of_node_put(map);
out:
 of_node_put(cn);
 return ret;
}

找到 dts 中 cpu topology 的根節點 "/cpus"
找到 "cpu-map" 節點
解析 "cpu-map" 中的 cluster

以 i.mx8qm 爲例，topology 爲：”4_A53 + 2_A72”，dts 中定義如下：

# imx8qm.dtsi

cpus: cpus {
        #address-cells = <2>;
        #size-cells = <0>;

        A53_0: cpu@0 {
                device_type = "cpu";
                compatible = "arm,cortex-a53", "arm,armv8";
                reg = <0x0 0x0>;
                clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
                enable-method = "psci";
                next-level-cache = <&A53_L2>;
                operating-points-v2 = <&a53_opp_table>;
                #cooling-cells = <2>;
        };

        A53_1: cpu@1 {
                device_type = "cpu";
                compatible = "arm,cortex-a53", "arm,armv8";
                reg = <0x0 0x1>;
                clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
                enable-method = "psci";
                next-level-cache = <&A53_L2>;
                operating-points-v2 = <&a53_opp_table>;
                #cooling-cells = <2>;
        };

        A53_2: cpu@2 {
                device_type = "cpu";
                compatible = "arm,cortex-a53", "arm,armv8";
                reg = <0x0 0x2>;
                clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
                enable-method = "psci";
                next-level-cache = <&A53_L2>;
                operating-points-v2 = <&a53_opp_table>;
                #cooling-cells = <2>;
        };

        A53_3: cpu@3 {
                device_type = "cpu";
                compatible = "arm,cortex-a53", "arm,armv8";
                reg = <0x0 0x3>;
                clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
                enable-method = "psci";
                next-level-cache = <&A53_L2>;
                operating-points-v2 = <&a53_opp_table>;
                #cooling-cells = <2>;
        };

        A72_0: cpu@100 {
                device_type = "cpu";
                compatible = "arm,cortex-a72", "arm,armv8";
                reg = <0x0 0x100>;
                clocks = <&clk IMX_SC_R_A72 IMX_SC_PM_CLK_CPU>;
                enable-method = "psci";
                next-level-cache = <&A72_L2>;
                operating-points-v2 = <&a72_opp_table>;
                #cooling-cells = <2>;
        };

        A72_1: cpu@101 {
                device_type = "cpu";
                compatible = "arm,cortex-a72", "arm,armv8";
                reg = <0x0 0x101>;
                clocks = <&clk IMX_SC_R_A72 IMX_SC_PM_CLK_CPU>;
                enable-method = "psci";
                next-level-cache = <&A72_L2>;
                operating-points-v2 = <&a72_opp_table>;
                #cooling-cells = <2>;
        };

        A53_L2: l2-cache0 {
                compatible = "cache";
        };

        A72_L2: l2-cache1 {
                compatible = "cache";
        };
  
        cpu-map {
                cluster0 {
                        core0 {
                                cpu = <&A53_0>;
                        };
                        core1 {
                                cpu = <&A53_1>;
                        };
                        core2 {
                                cpu = <&A53_2>;
                        };
                        core3 {
                                cpu = <&A53_3>;
                        };
                };

                cluster1 {
                        core0 {
                                cpu = <&A72_0>;
                        };
                        core1 {
                                cpu = <&A72_1>;
                        };
                };
        };
};

經過 parse_dt_topology()，update_siblings_masks() 解析後得到 cpu_topology 的值爲：

CPU0: cluster_id = 0, core_id = 0

CPU1: cluster_id = 0, core_id = 1

CPU2: cluster_id = 0, core_id = 2

CPU3: cluster_id = 0, core_id = 3

CPU4: cluster_id = 1, core_id = 0

CPU5: cluster_id = 1, core_id = 1

調度域和調度組

在 Linux 內核中，調度域使用 sched_domain 結構表示，調度組使用 sched_group 結構表示。

調度域 sched_domain

struct sched_domain {
    struct sched_domain *parent;   
    struct sched_domain *child;     
    struct sched_group  *groups;     
    unsigned long min_interval;
    unsigned long max_interval; 
    ...
};

parent：由於調度域是分層的，上層調度域是下層的調度域的父親，所以這個字段指向的是當前調度域的上層調度域。
child：如上所述，這個字段用來指向當前調度域的下層調度域。
groups：每個調度域都擁有一批調度組，所以這個字段指向的是屬於當前調度域的調度組列表。
min_interval/max_interval：做均衡也是需要開銷的，不能時刻去檢查調度域的均衡狀態，這兩個參數定義了檢查該 sched domain 均衡狀態的時間間隔的範圍

sched_domain 是分成兩個 level，base domain 稱爲 MC domain（multi core domain），頂層 domain 稱爲 DIE domain。

調度組 sched_group

struct sched_group {
    struct sched_group *next;
    unsigned int group_weight;
    ...
    struct sched_group_capacity *sgc;
    unsigned long cpumask[0];
};

next：指向屬於同一個調度域的下一個調度組。
group_weight：該調度組中有多少個 cpu。
sgc：該調度組的算力信息。
cpumask：用於標記屬於當前調度組的 CPU 列表（每個位表示一個 CPU）。

爲了減少鎖的競爭，每一個 CPU 都有自己的 MC domain、DIE domain 以及 sched_group，並且形成了 sched_domain 之間的層級結構，sched_group 的環形鏈表結構。CPU 對應的調度域和調度組可通過在設備模型文件 /proc/sys/kernel/sched_domain 裏查看。

具體的 sched_domain 的初始化代碼分析如下：

kernel_init() -> kernel_init_freeable() -> sched_init_smp() -> init_sched_domains(cpu_active_mask) -> build_sched_domains(doms_cur[0], NULL)

static int
build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
{
 enum s_alloc alloc_state;
 struct sched_domain *sd;
 struct s_data d;
 int i, ret = -ENOMEM;

 alloc_state = __visit_domain_allocation_hell(&d, cpu_map);    ------(1)
 if (alloc_state != sa_rootdomain)
  goto error;

 /* Set up domains for CPUs specified by the cpu_map: */
 for_each_cpu(i, cpu_map) {
  struct sched_domain_topology_level *tl;

  sd = NULL;
  for_each_sd_topology(tl) {
   sd = build_sched_domain(tl, cpu_map, attr, sd, i);        ------(2)
   if (tl == sched_domain_topology)
    *per_cpu_ptr(d.sd, i) = sd;
   if (tl->flags & SDTL_OVERLAP)
    sd->flags |= SD_OVERLAP;
  }
 }

 /* Build the groups for the domains */
 for_each_cpu(i, cpu_map) {
  for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
   sd->span_weight = cpumask_weight(sched_domain_span(sd));
   if (sd->flags & SD_OVERLAP) {
    if (build_overlap_sched_groups(sd, i))
     goto error;
   } else {
    if (build_sched_groups(sd, i))                          ------(3)
     goto error;
   }
  }
 }
  ......
 /* Attach the domains */
 rcu_read_lock();
 for_each_cpu(i, cpu_map) {
  int max_cpu = READ_ONCE(d.rd->max_cap_orig_cpu);
  int min_cpu = READ_ONCE(d.rd->min_cap_orig_cpu);

  sd = *per_cpu_ptr(d.sd, i);

  if ((max_cpu < 0) || (cpu_rq(i)->cpu_capacity_orig >
      cpu_rq(max_cpu)->cpu_capacity_orig))
   WRITE_ONCE(d.rd->max_cap_orig_cpu, i);

  if ((min_cpu < 0) || (cpu_rq(i)->cpu_capacity_orig <
      cpu_rq(min_cpu)->cpu_capacity_orig))
   WRITE_ONCE(d.rd->min_cap_orig_cpu, i);

  cpu_attach_domain(sd, d.rd, i);                            ------(4)
 }
 rcu_read_unlock();

 if (!cpumask_empty(cpu_map))
  update_asym_cpucapacity(cpumask_first(cpu_map));

 ret = 0;
error:
 __free_domain_allocs(&d, alloc_state, cpu_map);             ------(5)
 return ret;
}

在每個 tl 層次，給每個 CPU 分配 sd、sg、sgc 空間
遍歷 cpu_map 裏所有 CPU，創建與物理拓撲結構對應的多級調度域
遍歷 cpu_map 裏所有 CPU, 創建調度組
將每個 CPU 的 rq 與 rd(root_domain) 進行綁定
free 掉分配失敗或者分配成功多餘的內存

所以，可運行進程隊列與調度域和調度組的關係如下圖所示：

總結

這裏用一張圖來總結下 CPU 拓撲，調度域初始化的過程，如下所示：

根據已經生成的 CPU 拓撲，調度域和調度組，最終可以生成如下圖所示的關係圖。

在上面的結構中，頂層的 DIE domain 覆蓋了系統中所有的 CPU，4 個 A53 是 Cluster 0，共享 L2 cache，兩外 2 個 A72 是 Cluster 1，共享 L2 cache。那麼每個 Cluster 可以認爲是一個 MC 調度域，左邊的 MC 調度域中有 4 個調度組，右邊的 MC 調度域中有 2 個調度組，每個調度組中只有 1 個 CPU。整個 SOC 可以認爲是高一級別的 DIE 調度域，其中有兩個調度組，Cluster 0 屬於一個調度組，Cluster 1 屬於另一個調度組。跨 Cluster 的負載均衡是需要清除 L2 cache 的，開銷是很大的，因此 SOC 級別的 DIE 調度域進行負載均衡的開銷比 MC 調度域更大一些。

到目前爲止，我們已經將內核的調度域構建起來了，CFS 可以利用 sched_domain 來完成多核間的負載均衡了。

何時做負載均衡？

CFS 任務的負載均衡器有兩種：

一種是針對 busy CPU 的 periodic balancer，用於進程在 busy CPU 上的均衡
一種是針對 idle CPU 的 idle balancer，用於把 busy CPU 上的進程均衡到 idle CPU 上來。

periodic balancer：週期性負載均衡是在時鐘中斷 scheduler_tick 中，找到該 domain 中最繁忙的 sched group 和 CPU runqueue，將其上的任務 pull 到本 CPU，以便讓系統的負載處於均衡的狀態。

nohz idle balancer：當其他的 CPU 已經進入 idle，本 CPU 任務太重，需要通過 IPI 將其他 idle 的 CPU 喚醒來進行負載均衡。

new idle balancer：本 CPU 上沒有任務執行，馬上要進入 idle 狀態的時候，看看其他 CPU 是否需要幫忙，來從 busy cpu 上 pull 任務，讓整個系統的負載處於均衡狀態。

負載均衡的基本過程

當一個 CPU 上進行負載均衡的時候，總是從 base domain 開始，檢查其所屬 sched group 之間的負載均衡情況，如果有不均衡情況，那麼會在該 CPU 所屬 Cluster 之間進行遷移，以便維護 Cluster 內各個 CPU 的任務負載均衡。

load_balance 是處理負載均衡的核心函數，它的處理單元是一個調度域，其中會包含對調度組的處理。

static int load_balance(int this_cpu, struct rq *this_rq,
                        struct sched_domain *sd, enum cpu_idle_type idle,
                        int *continue_balancing)
{
        ......
redo:
        if (!should_we_balance(&env)) {
                *continue_balancing = 0;
                goto out_balanced;
        }

        group = find_busiest_group(&env);           ------(1)
        if (!group) {
                schedstat_inc(sd->lb_nobusyg[idle]);
                goto out_balanced;
        }

        busiest = find_busiest_queue(&env, group);  ------(2)
        if (!busiest) {
                schedstat_inc(sd->lb_nobusyq[idle]);
                goto out_balanced;
        }

        BUG_ON(busiest == env.dst_rq);

        schedstat_add(sd->lb_imbalance[idle], env.imbalance);

        env.src_cpu = busiest->cpu;
        env.src_rq = busiest;

        ld_moved = 0;
        if (busiest->nr_running > 1) {
                env.flags |= LBF_ALL_PINNED;
                env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);

more_balance:
                rq_lock_irqsave(busiest, &rf);
                update_rq_clock(busiest);
                
                cur_ld_moved = detach_tasks(&env);  ------(3)

                rq_unlock(busiest, &rf);

                if (cur_ld_moved) {
                        attach_tasks(&env);         ------(4)
                        ld_moved += cur_ld_moved;
                }

                local_irq_restore(rf.flags);

                if (env.flags & LBF_NEED_BREAK) {
                        env.flags &= ~LBF_NEED_BREAK;
                        goto more_balance;
                }
                ......
        }
        ......
out:
        return ld_moved;
}

找到該 domain 中最繁忙的 sched group
在這個最繁忙的 group 中挑選最繁忙的 CPU runqueue, 作爲 src
從這個隊列中選擇任務來遷移，然後把被選中的任務從其所在的 runqueue 中移除
從最繁忙的 CPU runqueue 中 pull 一些任務到當前可運行隊列 dst

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