2.8.3 数据结构

内核引入了调度域（ sched_domain ）与调度组（ sched_group ）这两种数据结构来组织CPU, 调度域用来表示CPU物理拓扑结构中的层级关系，而调度组是负载均衡的基本单元。一个调度域包含多个调度组，系统做负载均衡时，首先需要保证的就是一个调度域中所有调度组的负载平衡，再考虑跨域的负载平衡。

2.8.3.1. 调度域 - sched_domain

sched_domain 是内核在2.6版时引入的数据结构，调度器使用调度域来组织管理CPU, 进而完成负载均衡。系统会根据CPU 的物理拓扑结构创建调度域，每个调度域都覆盖了一组CPU, 属于同一个调度域的所有CPU具有相同的调度策略与属性，所有的调度域最终形成一颗树形（Tree）结构，该结构的层级关系与CPU的物理拓扑结构相对应。例如前文提到的4核8线程的CPU，内核最终创建的调度域示意图如下：

图一：调度域

其中 Domain 0 表示 Core 0 的调度域，也是内核中最底层的调度域（被称为Base Domain），包含了 Core 0 的两个超线程（分别是CPU 0与CPU 4）；4 个Core 的调度域又构成了一个上层调度域（图中的Root Domain）。

CPU的超线程分组可以通过命令 lscpu -p 进行查看。目录 /sys/devices/system/cpu 中包含了更详细的CPU信息。

上图的CPU结构相对比较简单，因此总共只形成了两级调度域，在更复杂的系统中调度域的层级将更加复杂。不过不管调度域有多少层级，隶属于同一个调度域内的CPU总是比同级但跨域的CPU更具“亲和性”，也就是说在同一个调度域中的CPU之间迁移任务比跨域迁移的代价更小。例如上图中，将任务从CPU 0迁移到CPU 4的代价就比迁移到CPU 1要小。

调度域的数据结构定义如下：

/* file: include/linux/sched/topology.h */

struct sched_domain {
  /* These fields must be setup */
  /* 父节点 */
  struct sched_domain __rcu *parent; /* top domain must be null terminated */
  /* 子节点 */
  struct sched_domain __rcu *child; /* bottom domain must be null terminated */
  /* 本调度域中的调度组，各个调度组形成一个链表，下一节将对调度组做详细介绍 */
  struct sched_group *groups; /* the balancing groups of the domain */
  /* 检查负载均衡的最小时间间隔，过于频繁的检查会造成系统产生额外开销 */
  unsigned long min_interval; /* Minimum balance interval ms */
  /* 检查负载均衡的最大时间间隔，太长时间不检查容易导致负载偏差太大 */
  unsigned long max_interval; /* Maximum balance interval ms */
  /* 反映CPU繁忙程度的参数，系统会根据运行情况动态调整负载均衡的时间间隔，该间隔时间记录在字段balance_interval中
     但如果CPU很繁忙，那么时间间隔就适当延长一些，即busy_factor*balance_interval
   */
  unsigned int busy_factor; /* less balancing by factor if busy */
  /* 调度域内的不均衡状态达到了一定的程度之后就开始进行负载均衡的操作。
     imbalance_pct这个成员定义了判定不均衡的阈值 */
  unsigned int imbalance_pct;    /* No balance until over watermark */
  unsigned int cache_nice_tries; /* Leave cache hot tasks for # tries */

  int nohz_idle; /* NOHZ IDLE status */
  int flags;     /* See SD_* */
  /* 该调度域在整个调度域层级结构中的level。Base调度域的level等于0，向上依次加一。
     可以理解为调度域在树中的高度
   */
  int level;

  /* Runtime fields. */
  /* 上次做负载均衡的时间点 */
  unsigned long last_balance; /* init to jiffies. units in jiffies */
  /* 该字段定义了均衡的时间间隔，会随着系统的运行而变化 */
  unsigned int balance_interval;  /* initialise to 1. units in ms. */
  unsigned int nr_balance_failed; /* initialise to 0 */

  /* idle_balance() stats */
  u64 max_newidle_lb_cost;
  unsigned long next_decay_max_lb_cost;

  u64 avg_scan_cost; /* select_idle_sibling */

  union {
    void *private;       /* used during construction */
    struct rcu_head rcu; /* used during destruction */
  };
  struct sched_domain_shared *shared;

  unsigned int span_weight;
  /*
   * A sched domain’s span means “balance process load among these CPUs”.
   *
   该字段用来描述当前sd覆盖了哪些CPU,父调度域的span应该是其所有子调度域的超集。
   * */
  unsigned long span[];
};

这里删除了一些不太重要的字段，包括调度域的名字及统计信息。总体来说，结构体 sched_domain 中包含了如下几类信息：

• 目标CPU, 通过span字段指定

• 负载均衡的配置信息，例如间隔时间区间，这类信息属于静态信息

• 负载均衡的运行时信息，例如负载均衡的实际间隔时间，统计字段等，这类信息属于动态信息

前面我们提到，负载均衡首先发生在单个调度域内，然后再考虑是否需要跨域。为了更好的达成这个目的，内核还引入了另一个概念来辅助完成这个任务，这就是调度组（sched_group）。

2.8.3.2. 调度组 - sched_group

通过前面的描述，可以发现调度域实际上是为负载均衡划定了一个界限，该界限本质上就是目标CPU的集合，也就是 sched_domain 中的 span 字段。然而当调度器在单个调度域内做负载均衡时，CPU并不是调度器的工作对象，内核引入了调度组（sched_group）来辅助该操作，调度组才是负载均衡的基本单位。

调度域包含了一个或多个调度组，字段 struct sched_group *groups; 指向的便是该调度域包含的调度组，多个调度组构成一个单向链表。在一颗调度域构成的树中，父调度域的每个子调度域都是一个调度组，而Base Domain中，一个CPU会对应一个调度组. 下图是前文4x8处理器附上调度组后的示意图：

图二：调度域与调度组

调度域内的负载均衡发生在调度组之间，例如上图中的 Root Domain 包含了4个调度组，那么只有当这些组之间的负载偏差超过一定阈值时，负载均衡才会发生，调度器会根据算法将任务从负载高的调度组向负载低的调度组迁移。一个调度组的负载是改组内所有CPU的负载之和。

调度组的结构体定义如下：

/* file: kernel/sched/sched.h */
struct sched_group {
  /* 指向下一个调度组，形成单向链表 */
  struct sched_group *next; /* Must be a circular list */
  /* 该调度组的引用计数 */
  atomic_t ref;

  unsigned int group_weight;
  /* 该调度组的算力信息 */
  struct sched_group_capacity *sgc;
  int asym_prefer_cpu; /* CPU of highest priority in group */

  /* 该调度组包含的CPU */
  unsigned long cpumask[];
};

当调度器做负载均衡时，除了考虑调度组的负载，还需要考虑算力，如果一个调度组的负载很低，但其本身也没什么剩余算力，那么向其迁移任务也是不合理的。算力就是组内所有CPU能够提供的计算能力的总和，每个调度组的算力保存在字段 sched_group_capacity 中。造成调度组算力不同的原因有很多，例如不同CPU设置的最高主频不同、大小核的区分等都会直接影响CPU的算力，另外我们这里讨论的是CFS的负载均衡，但CPU还会用来调度DL、RT这些任务，这也会消耗掉一部分算力。因此系统会充分考虑这些因素，然后计算出调度组的实际算力。