深入理解Linux内核进程CPU负载均衡机制（上）

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个调度域

1. D0，整个系统，包括所有CPU组成一个调度域，D0调度域仅有一个，其包括两个调度组，即两个NUMA结点。
   
2. D1，两个NUMA结点分别独立组成一个调度域，D1域的调度组是每个CPU上的物理core，即每个D1拥有4个调度组。
   
3. 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 的，所以这两种模型并没有绝对的优劣之分。