Linux内核中的CPU负载均衡机制是通过任务调度器来实现的。任务调度器负责将进程和线程分配到不同的CPU核心上执行，以实现负载均衡，Linux内核使用了一种叫做"完全公平调度"（Completely Fair Scheduler, CFS）的调度算法来实现任务的均衡分配，CFS将系统中所有可运行的任务都看作是一个红黑树，并按照每个任务占用CPU时间的比例进行排序。

当有新的任务需要被调度时，CFS会选择红黑树中最左边的节点作为下一个要执行的任务。这样可以保证每个任务在整个系统中被公平地分配CPU时间片。此外，CFS还考虑了不同CPU核心之间的负载差异，尽可能将新任务分配给相对空闲的核心。

一、什么是负载均衡

1.1什么是CPU负载（load）

CPU load是一个很容易和CPU usage混淆的概念。CPU usage是CPU忙闲的比例，例如在一个周期为1000ms的窗口中观察CPU的情况，如果500ms的时间在执行任务，500ms的时间处于idle状态，那么在这个窗口中CPU的usage是50%。CPU usage是一个直观的概念，所见即所得，然而它不能用来对比。例如一个任务在小核300MHz频率下执行1000ms，看到CPU usage是100%，同样的任务，在大核3GHz下的执行50ms，CPU usage是5%。这种场景下，同样的任务，load是一样的，但是CPU usage差别很大。CPU 利用率（utility）是另外一个容易混淆的概念。Utility和usage的共同点都是考虑了running time，区别是Utility进行了归一化，即把running time归一化到了系统中最大算力（超大核最高频率）上的执行时间。为了能和CPU capacity进行运算，utility还归一化到了1024。

CPU load和utility一样，都进行了归一化，但是概念还是不同的。Utility是一个和busy time（运行时间）相关的量，在CPU利用率没有达到100%的时候，利用率基本上等于负载，利用率高的时候负载也大，一旦当CPU利用率达到了100%的时候，利用率其实是无法给出CPU负载的状况，因为大家的利用率都是100%，利用率相等，但是并不意味着CPUs的负载也是相等的，因为这时候不同CPU上runqueue中等待执行的任务数目不同，直觉上runque上挂着10任务的CPU承压比挂着5个任务的CPU的负载要更重一些。因此，早期的CPU负载是使用runqueue深度来描述的。

显然，仅仅使用runqueue深度来表示CPU负载是一个很粗略的概念，我们可以举一个简单的例子：当前CPU A和CPU B上都挂了1个任务，但是A上挂的任务是一个重载任务，而B上挂的是一个经常sleep的轻载任务，那么仅仅从runqueue深度来描述CPU负载就有失偏颇了。因此，现代调度器往往使用CPU runqueue上task load之和来表示CPU load。这样，对CPU负载的跟踪就变成了对任务负载的跟踪。

3.8版本的linux内核引入了PELT算法来跟踪每一个sched entity的负载，把负载跟踪的算法从per-CPU进化到per-entity。PELT算法不但能知道CPU的负载，而且知道负载来自哪一个调度实体，从而可以更精准的进行负载均衡。

1.2什么是均衡

对于负载均衡而言，并不是把整个系统的负载平均的分配到系统中的各个CPU上。实际上，我们还是必须要考虑系统中各个CPU的算力，让CPU获得和其算力匹配的负载。

例如在一个6个小核+2个大核的系统中，整个系统如果有800的负载，那么每个CPU上分配100的负载其实是不均衡的，因为大核CPU可以提供更强的算力。

什么是CPU算力（capacity），所谓算力就是描述CPU的能够提供的计算能力。在同样的频率下，一个微架构是A77的CPU显然算力要大于A57的CPU。

如果CPU的微架构都是一样的，那么一个最大频率是2.2GHz的CPU算力肯定是大于最大频率是1.1GHz的CPU。因此，确定了微架构和最大频率，一个CPU的算力就基本确定了。struct rq数据结构中有两个和算力相关的成员：

Cpufreq系统会根据当前的CPU util来调节CPU当前的运行频率，也许触发温控，限制了该CPU的最大频率，但这并不能改变cpu_capacity_orig。本文主要描述CFS任务的均衡（RT的均衡不考虑负载，是在另外的维度），因此均衡需要考虑的CPU算力是cpu_capacity，这个算力需要把CPU用于执行rt、dl、irq的算力以及温控损失的算力去掉，即该CPU可用于CFS任务的算力。

因此，CFS任务均衡中使用的CPU算力（cpu_capacity成员）其实一个不断变化的值，需要经常更新（参考update_cpu_capacity函数）。为了让CPU算力和utility可以对比，实际上我们采用了归一化的方式，即系统中处理能力最强的CPU运行在最高频率的算力是1024，其他的CPU算力根据微架构和最大运行频率相应的进行调整。

有了各个任务负载，将runqueue中的任务负载累加起来就可以得到CPU负载，配合系统中各个CPU的算力，看起来我们就可以完成负载均衡的工作，然而事情没有那么简单，当负载不均衡的时候，任务需要在CPU之间迁移，不同形态的迁移会有不同的开销。

例如一个任务在小核cluster上的CPU之间的迁移所带来的性能开销一定是小于任务从小核cluster的CPU迁移到大核cluster的开销。因此，为了更好的执行负载均衡，我们需要构建和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调度域（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成一个调度组。

调度域: 上述结构中有3个调度域

D0，整个系统，包括所有CPU组成一个调度域，D0调度域仅有一个，其包括两个调度组，即两个NUMA结点。

D1，两个NUMA结点分别独立组成一个调度域，D1域的调度组是每个CPU上的物理core，即每个D1拥有4个调度组。

D2，每个物理core构成最小的调度域，D2域的组是每个超线程。

struct sched_domain {
	/*Sched domain会形成层级结构，parent和child建立了不同层级结构的父子关系。
  对于base domain而言，其child等于NULL，对于top domain而言，其parent等于NULL */
	struct sched_domain __rcu *parent;	/* top domain must be null terminated */
	struct sched_domain __rcu *child;	/* bottom domain must be null terminated */
 /* 一个调度域中有若干个调度组，这些调度组形成一个环形链表，groups成员就是链表头*/
	struct sched_group *groups;	/* the balancing groups of the domain */
 /* 做均衡也是需要开销的，我们不可能时刻去检查调度域的均衡状态，
  这两个参数定义了检查该sched domain均衡状态的时间间隔范围 */
	unsigned long min_interval;	/* Minimum balance interval ms */
	unsigned long max_interval;	/* Maximum balance interval ms */
  /* 正常情况下，balance_interval定义了均衡的时间间隔，如果cpu繁忙，
   那么均衡要时间间隔长一些，即时间间隔定义为busy_factor x balance_interval */
	unsigned int busy_factor;	/* less balancing by factor if busy */
 /* 调度域内的不均衡状态达到了一定的程度之后就开始进行负载均衡的操作。
  imbalance_pct这个成员定义了判定不均衡的门限 */
	unsigned int imbalance_pct;	/* No balance until over watermark */
  /* 这个成员应该是和nr_balance_failed配合控制负载均衡过程的迁移力度。
  当nr_balance_failed大于cache_nice_tries的时候，负载均衡会变得更加激进。*/
	unsigned int cache_nice_tries;	/* Leave cache hot tasks for # tries */
	/* 每个cpu都有其对应LLC sched domain，而LLC SD记录对应cpu的idle状态得到该domain中busy cpu的个数*/
	int nohz_idle;			/* NOHZ IDLE status */
	int flags;			/* 调度域标志* */
	int level;     /* 该sched domain在整个调度域层级结构中的level*/

	/* 上次进行balance的时间点，ast_balance加上这个计算得到的均衡时间间隔就是下一次均衡的时间点*/
	unsigned long last_balance;	/* init to jiffies. units in jiffies */
	unsigned int balance_interval;	/* 定义了该sched domain均衡的基础时间间隔. */
	unsigned int nr_balance_failed; /*本sched domain中进行负载均衡失败的次数 */

	/* 在该domain上进行newidle balance的最大时间长度 */
	u64 max_newidle_lb_cost;
	unsigned long last_decay_max_lb_cost;

	u64 avg_scan_cost;		/* 平均扫描成本 */
 /* 负载均衡的统计信息 */
#ifdef CONFIG_SCHEDSTATS
	/* load_balance() stats */
	unsigned int lb_count[CPU_MAX_IDLE_TYPES];
	unsigned int lb_failed[CPU_MAX_IDLE_TYPES];
	unsigned int lb_balanced[CPU_MAX_IDLE_TYPES];
	unsigned int lb_imbalance[CPU_MAX_IDLE_TYPES];
	unsigned int lb_gained[CPU_MAX_IDLE_TYPES];
	unsigned int lb_hot_gained[CPU_MAX_IDLE_TYPES];
	unsigned int lb_nobusyg[CPU_MAX_IDLE_TYPES];
	unsigned int lb_nobusyq[CPU_MAX_IDLE_TYPES];

	/* Active load balancing */
	unsigned int alb_count;
	unsigned int alb_failed;
	unsigned int alb_pushed;

	/* SD_BALANCE_EXEC stats */
	unsigned int sbe_count;
	unsigned int sbe_balanced;
	unsigned int sbe_pushed;

	/* SD_BALANCE_FORK stats */
	unsigned int sbf_count;
	unsigned int sbf_balanced;
	unsigned int sbf_pushed;

	/* try_to_wake_up() stats */
	unsigned int ttwu_wake_remote;
	unsigned int ttwu_move_affine;
	unsigned int ttwu_move_balance;
#endif
#ifdef CONFIG_SCHED_DEBUG
	char *name;
#endif
	union {
		void *private;		/* used during construction */
		struct rcu_head rcu;	/* used during destruction */
	};
  /* 为了降低锁竞争，Sched domain是per-CPU的, 该sched domain中的busy cpu的个数,  
      该sched domain中是否有idle的cpu*/
	struct sched_domain_shared *shared;
  /* span_weight说明该sched domain中CPU的个数 */
	unsigned int span_weight;
	/*
	 * Span of all CPUs in this domain.
	 *
	 * NOTE: this field is variable length. (Allocated dynamically
	 * by attaching extra space to the end of the structure,
	 * depending on how many CPUs the kernel has booted up with)
	 */
  /* span等于该sched domain中所有CPU core形成的cpu mask */
	unsigned long span[];
};

调度域并不是一个平层结构，而是根据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。内核中struct sched_group来描述调度组，其主要的成员如下：

上面的描述过于枯燥，我们后面会使用一个具体的例子来描述负载如何在各个level的sched domain上进行均衡的，不过在此之前，我们先看看负载均衡的整体软件架构。

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中的第一个）。

如上流程图，实际上内核的负载均衡有以下几种：

一种是busy cpu的periodic balancer： 这种周期性负载均衡用于CFS任务的busy cpu上的负载均衡，是在时钟中断 scheduler_tick 中，找到该 domain 中最繁忙的 sched group 和 CPU runqueue，将其上的任务 pull 到本 CPU，以便让系统的负载处于均衡的状态。

一种是ilde cpu的NOHZ load balance： 当其他的 CPU 已经进入 idle，本 CPU 任务太重，需要通过 IPI 将其他 idle 的 CPU 唤醒来进行负载均衡。

如果没有dynamic tick特性，那么其实不需要进行nohz idle load balance，因为tick会唤醒处于idle的cpu，从而周期性tick就可以覆盖这个场景。

一种是ilde cpu的New idle load balance： 本 CPU 上没有任务执行，当前cfs runque中没有runnable，马上要进入 idle 状态的时候，调度器在pick next的时候，看看其他 CPU 是否需要帮忙，来从 busy cpu 上 pull 任务，让整个系统的负载处于均衡状态。

由于idle状态的CPU通常处于tickless/nohz模式，所以需要向它发送IPI（核间中断）来唤醒（“kick”），这也是为什么实现此过程的函数被命名为"nohz_balancer_kick"。

作为idle的CPU收到IPI后，将在softirq上下文中（类型为"SCHED_SOFTIRQ"）执行负载均衡，其对应的处理函数是在初始化时就注册好了的。

__init void init_sched_fair_class(void)
{
#ifdef CONFIG_SMP
	open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);

#ifdef CONFIG_NO_HZ_COMMON
	nohz.next_balance = jiffies;
	nohz.next_blocked = jiffies;
	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
#endif
#endif /* SMP */

这段最重要的是在内核中注册了一个软中断来做负载均衡run_rebalance_domains

static __latent_entropy void run_rebalance_domains(struct softirq_action *h)
{
	struct rq *this_rq = this_rq();
 /* 1. 如果当前运行队列有idle_balance值，即如果是idle，则选择CPU_IDLE类型，
      如果不是idle，则选择CPU_NOT_IDLE类型。 */
	enum cpu_idle_type idle = this_rq->idle_balance ?
						CPU_IDLE : CPU_NOT_IDLE;

	/*
	 * If this CPU has a pending nohz_balance_kick, then do the
	 * balancing on behalf of the other idle CPUs whose ticks are
	 * stopped. Do nohz_idle_balance *before* rebalance_domains to
	 * give the idle CPUs a chance to load balance. Else we may
	 * load balance only within the local sched_domain hierarchy
	 * and abort nohz_idle_balance altogether if we pull some load.
	 */
  /* 尝试idle cpu请求的 nohz， 并在通过 IPI 唤醒 nohz 空闲 cpu 时在 cpu 的运行队列中请求唤*/
	if (nohz_idle_balance(this_rq, idle))
		return;

	/* normal load balance */
	update_blocked_averages(this_rq->cpu);
  /* 开始负载均衡，从这里可以知道负载均衡是在一个domain 内的cpu来做的 */
	rebalance_domains(this_rq, idle);
}

这里暂时先不考虑nohz相关的函数，从rebalance_domains开始入手

static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
{
	int continue_balancing = 1;
	int cpu = rq->cpu;
	int busy = idle != CPU_IDLE && !sched_idle_cpu(cpu);
	unsigned long interval;
	struct sched_domain *sd;
	/* 我们必须再次进行重新平衡的最早时间 */
	unsigned long next_balance = jiffies + 60*HZ;
	int update_next_balance = 0;
	int need_serialize, need_decay = 0;
	u64 max_cost = 0;

	rcu_read_lock();
	for_each_domain(cpu, sd) {   /* 遍历到顶级调度域 */
		/*
		 * Decay the newidle max times here because this is a regular
		 * visit to all the domains.
		 */
		need_decay = update_newidle_cost(sd, 0);
		max_cost += sd->max_newidle_lb_cost;

		/*没有设置continue_balancing（初始值=1），则根据need_decay值设置则跳过，否则退出循环*/
		if (!continue_balancing) {
			if (need_decay)
				continue;
			break;
		}
	 /* 找出调度域的平衡周期 (jiffies) */
		interval = get_sd_balance_interval(sd, busy);
	 /*  当收到来自所有 CPU 的 numa 平衡请求时，将获取锁用于串行处理。如果失败，请跳过它 */
		need_serialize = sd->flags & SD_SERIALIZE;
		if (need_serialize) {
			if (!spin_trylock(&balancing))
				goto out;
		}
	  /* 如果当前时间超过遍历域的均衡周期，则进行负载均衡 */
		if (time_after_eq(jiffies, sd->last_balance + interval)) {
			if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
				/*
				 * The LBF_DST_PINNED logic could have changed
				 * env->dst_cpu, so we can't know our idle
				 * state even if we migrated tasks. Update it.
				 */
				idle = idle_cpu(cpu) ? CPU_IDLE : CPU_NOT_IDLE;
				busy = idle != CPU_IDLE && !sched_idle_cpu(cpu);
			}
	    /* 更新时间间隔 */
			sd->last_balance = jiffies;
			interval = get_sd_balance_interval(sd, busy);
		}
		if (need_serialize)
			spin_unlock(&balancing);
out:
	  /* next_balance更新每个域的last_balance +区间值中的最小值 */
		if (time_after(next_balance, sd->last_balance + interval)) {
			next_balance = sd->last_balance + interval;
			update_next_balance = 1;
		}
	}
  /* 如果设置了 need_decay，则更新 max_idle_balance_cost */
	if (need_decay) {
		/*
		 * Ensure the rq-wide value also decays but keep it at a
		 * reasonable floor to avoid funnies with rq->avg_idle.
		 */
		rq->max_idle_balance_cost =
			max((u64)sysctl_sched_migration_cost, max_cost);
	}
	rcu_read_unlock();

	/* 将运行队列的 next_balance 设置为更新的最小 next_balance
	 */

	if (likely(update_next_balance))
		rq->next_balance = next_balance;

}

该函数流程如下：

当一个CPU上进行负载均衡的时候，总是从base domain开始，检查其所属的sched group之间的负载均衡情况，如果有不均衡的情况，那么会在该CPU所属的cluster之间进行迁移，以维护cluster内各个CPU任务的负载均衡。

所以rebalance_domains职责是寻找需要被balance的sched domain，然后通过"find_busiest_group"找到该domain中最繁忙的sched group，进而通过"find_busiest_queue"在这个最繁忙的group中挑选最繁忙的CPU runqueue，被选中的CPU就成为任务迁移的src。

那接下来从这个队列中选择哪些任务来迁移呢？这就是"detach_tasks"函数要完成的事了，判断的依据主要是task load的大小，优先选择load重的任务

被选中迁移的任务从其所在的runqueue中移除（对应"deactive_task"函数），并被打上"TASK_ON_RQ_MIGRATING"的标记，开始向着作为dst的CPU runqueue进发（对应"active_task"函数）。

这里有一个例外，设置了CPU affinity，和所在CPU进行了绑定（俗称被"pin"住）的任务不能被迁移（就像被pin住的内存page不能被swap到磁盘上一样），对此进行判断的函数是"can_migrate_task"。

无论是单核还是多核，只要是多任务系统，就需要调度，但调度对多核系统显得尤为关键，因为如果调度不当，就无法充分发挥多核的潜力。

基于多核的调度，大致有两种模型，一种是只有一个任务队列（single queue），即当有一个任务需要执行时，选择一个空闲的 CPU 来承接。

这种调度方法可谓简单明了，但既然共享一个队列，那往往免不了需要上锁。此外，现代 CPU 可是使用了 cache 的，一个任务一会儿在这个 CPU 上运行，一会儿又在那个 CPU 上运行，每新到一处，cache 往往都是“冷”的，执行效率必然大打折扣。

就像一个项目，交给 A 来做，A 刚花两天时间熟悉了下项目背景，隔一个星期因为 A 有其他事情，任务又转给 B 做，B 又需要花时间来重新熟悉项目。

所以啊，任务既然交给了 A，就让它一直做嘛，各管各的，一竿子到底。从 OS 调度的角度，就是采用每个 CPU 有一个任务队列的模型（multiple queues）。

共享减少了，cache affinity（俗称 "cpu affinity"）也建立起来了，但新的问题也随之出现了。

假设有 4 个任务（P1, P2, P3 和 P4），每个任务所需耗费的时间都差不多，分给 2 个 CPU 来执行，那刚刚好。那如果这 4 个任务所需耗费的时间差异很大呢，或者只有 3 个任务需要执行呢，该怎么分配？

multiple queues 模式跟现在企业的任务分配模式比较类似，其所面临的问题，也是作为调度者的项目经理经常需要面对的问题。项目交给 A 做以后，A 突然有其他更重要的任务要处理，正好这个时候 B 手头没事，那是不是应该让 B 来帮忙？

O(1) 和 CFS 调用算法使用的都是 multiple queues 模型, 而 Brain Fuck Schedule（简称BFS）使用的则是 single queue 模型。在某些场景下（比如 CPU 数目较少时），BFS 的性能表现是要超过 CFS 的，所以这两种模型并没有绝对的优劣之分。

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 牵扯的事情还是蛮多的。

【文章福利】小编推荐自己的Linux内核技术交流群:【865977150】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！

二、负载均衡的软件架构

负载均衡的整体软件结构图如下：

负载均衡模块主要分两个软件层次：核心负载均衡模块和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架构以及通信路径来进行的。

三、如何做负载均衡

3.1一个CPU拓扑示例

我们以一个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。

3.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算力之和

3.3其他需要考虑的事项

之所以要进行负载均衡主要是为了系统整体的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处于较低的频率运行，功耗会比方案一更低。

四、负载均衡场景分析

4.1整体的场景描述

在linux内核中，为了让任务均衡的分布在系统的所有CPU上，我们主要考虑下面三个场景：

（1）负载均衡（load balance）。通过搬移cpu runqueue上的任务，让各个CPU上的负载匹配CPU算力。

（2）任务放置（task placement）。当阻塞的任务被唤醒的时候，确定该任务应该放置在那个CPU上执行

（3）主动均衡（active upmigration）。当一个低算力CPU的runqueue中出现misfit task的时候，如果该任务持续执行，那么负载均衡无能为力，因为它只负责迁移runnable状态的任务。这种场景下，active upmigration可以把当前正在运行的misfit task向上迁移到算力更高的CPU上去。

4.2Task placement

任务放置主要发生在：

（1）唤醒一个新fork的线程

（2）Exec一个线程的时候

（3）唤醒一个阻塞的进程

在上面的三个场景中都会调用select_task_rq来为task选择一个适合的CPU core。

4.3Load balance

Load balance主要有三种：

（1）在tick中触发load balance。我们称之tick load balance或者periodic load balance。具体的代码执行路径是：

（2）调度器在pick next的时候，当前cfs runque中没有runnable，只能执行idle线程，让CPU进入idle状态。我们称之new idle load balance。具体的代码执行路径是：

（3）其他的cpu已经进入idle，本CPU任务太重，需要通过ipi将其idle的cpu唤醒来进行负载均衡。我们称之nohz idle load banlance，具体的代码执行路径是：

如果没有dynamic tick特性，那么其实不需要进行nohz idle load balance，因为tick会唤醒处于idle的cpu，从而周期性tick就可以覆盖这个场景。

4.4Active upmigration

主动迁移是Load balance的一种特殊场景。在负载均衡中，只要运用适当的同步机制（持有一个或者多个rq lock），runnable的任务可以在各个CPU runqueue之间移动，然而running的任务是例外，它不挂在CPU runqueue中，load balance无法覆盖。为了能够迁移running状态的任务，内核提供了Active upmigration的方法（利用stop machine调度类）。这个feature原生内核没有提供，故不再详述。