2.9.5 公平调度类的处理器负载均衡

1．处理器拓扑

目前多处理器系统有两种体系结构。

（1）非一致内存访问（Non-Uniform Memory Access, NUMA）：指内存被划分成多个内存节点的多处理器系统，访问一个内存节点花费的时间取决于处理器和内存节点的距离。每个处理器有一个本地内存节点，处理器访问本地内存节点的速度比访问其他内存节点的速度快。

（2）对称多处理器（Symmetric Multi-Processor, SMP）：即一致内存访问（Uniform Memory Access, UMA），所有处理器访问内存花费的时间是相同的。每个处理器的地位是平等的，仅在内核初始化的时候不平等：“0号处理器作为引导处理器负责初始化内核，其他处理器等待内核初始化完成。”

在实际应用中可以采用混合体系结构，在NUMA节点内部使用SMP体系结构。

处理器内部的拓扑如下。

（1）核（core）：一个处理器包含多个核，每个核有独立的一级缓存，所有核共享二级缓存。

（2）硬件线程：也称为逻辑处理器或者虚拟处理器，一个处理器或者核包含多个硬件线程，硬件线程共享一级缓存和二级缓存。MIPS处理器的叫法是同步多线程（Simultaneous Multi-Threading, SMT），英特尔对它的叫法是超线程。

当一个进程在不同的处理器拓扑层次上迁移的时候，付出的代价是不同的。

（1）如果从同一个核的一个硬件线程迁移到另一个硬件线程，进程在一级缓存和二级缓存中的数据可以继续使用。

（2）如果从同一个处理器的一个核迁移到另一个核，进程在源核的一级缓存中的数据失效，在二级缓存中的数据可以继续使用。

（3）如果从同一个NUMA节点的一个处理器迁移到另一个处理器，进程在源处理器的一级缓存和二级缓存中的数据失效。

（4）如果从一个NUMA节点迁移到另一个NUMA节点，进程在源处理器的一级缓存和二级缓存中的数据失效，并且访问内存可能变慢。

可以看出，处理器拓扑层次越高，迁移进程付出的代价越大。

2．调度域和调度组

软件看到的处理器是最底层的处理器。

（1）如果处理器支持硬件线程，那么最底层的处理器是硬件线程。

（2）如果处理器不支持硬件线程，支持多核，那么最底层的处理器是核。

（3）如果处理器不支持多核和硬件线程，那么最底层的处理器是物理处理器。

本书中的描述基于“处理器支持多核和硬件线程”这个假设。

内核按照处理器拓扑层次划分调度域层次，每个调度域包含多个调度组，调度组和调度域的关系如下。

（1）每个调度组的处理器集合是调度域的处理器集合的子集。

（2）所有调度组的处理器集合的并集是调度域的处理器集合。

（3）不同调度组的处理器集合没有交集。

如果我们把硬件线程、核、物理处理器和NUMA节点都理解为对应层次的处理器，那么可以认为：调度域对应更高层次的一个处理器，调度组对应本层次的一个处理器。一个硬件线程调度域对应一个核，每个调度组对应核的一个硬件线程；一个核调度域对应一个物理处理器，每个调度组对应物理处理器的一个核；一个处理器调度域对应一个NUMA节点，每个调度组对应NUMA节点的一个处理器。

每个处理器有一个基本的调度域，它是硬件线程调度域，向上依次是核调度域、处理器调度域和NUMA节点调度域。

举例说明：假设系统只有一个处理器，处理器包含两个核，每个核包含两个硬件线程，软件看到的处理器是硬件线程，即处理器0～3，调度域层次树如图2.42所示。

图2.42 调度域层次树

（1）两个硬件线程调度域：一个硬件线程调度域包含处理器0～1，分为两个调度组，调度组1包含处理器0，调度组2包含处理器1；另一个硬件线程调度域包含处理器2～3，分为两个调度组，调度组1包含处理器2，调度组2包含处理器3。

（2）一个核调度域包含处理器0～3，分为两个调度组，调度组1包含处理器0～1，调度组2包含处理器2～3。

考虑到NUMA节点之间的距离不同，把NUMA节点调度域划分为多个层次，算法是：把节点0到其他节点之间的距离按从小到大排序，去掉重复的数值，如果有n个距离值，记为数组d[n]，那么划分n个层次，层次i（0 <= i < n）的标准是节点之间的距离小于或等于d[i]。

算法假设：节点0到节点j的距离在任意节点i到节点j的距离之中是最大的。

举例说明1：假设系统划分为3个NUMA节点，节点编号是0～2，节点0到节点1的距离是100，节点0到结节2的距离是200，那么划分2个NUMA节点调度域层次。

（1）层次0的标准是节点之间的距离小于或等于100。

（2）层次1的标准是节点之间的距离小于或等于200。

举例说明2：以举例说明1作为基础，每个NUMA节点包含2个处理器，每个处理器包含2个核，每个核包含2个硬件线程，总共24个硬件线程，软件看到的处理器是最底层的硬件线程，即24个处理器。硬件线程0和1看到的调度域层次树如图2.43所示。

图2.43 包含NUMA节点的调度域层次树

3．负载均衡算法

（1）计算公平运行队列的平均负载。

把运行历史划分成近似1毫秒的片段，每个片段称为一个周期，为了方便执行移位操作，把一个周期定义为1024微秒。

一个周期的加权负载：load = 周期长度 × 处理器频率 × 公平运行队列的权重。

公平运行队列的加权负载总和：load_sum = load +（y × load_sum），其中y是衰减系数，y32=0.5。

把公式展开以后如下所示：

加权时间总和：time_sum = 周期长度 + (y × time_sum)。

加权平均负载：load_avg = load_sum / time_sum。

（2）计算处理器负载。

基于上面的公平运行队列的加权平均负载，计算5种处理器负载，计算公式如下：

其中i的取值是0～4, load_avg是根任务组的公平运行队列的加权平均负载。

5种负载的区别是，历史负载和当前负载的比例不同，i越大，历史负载占的比例越大，处理器负载曲线越平滑。在处理器不空闲、即将空闲和空闲等不同情况下实现负载均衡时，使用不同的处理器负载。

4．代码实现

（1）计算公平运行队列的平均负载：在以下情况下，从进程到根任务组计算每层公平运行队列的平均负载。

❑ 周期性地计算（函数task_tick_fair）。

❑ 进程加入公平运行队列（函数enqueue_task_fair）。

❑ 进程退出公平运行队列（函数dequeue_task_fair）。

公平运行队列中描述负载总和与平均负载的成员如下：

    kernel/sched/sched.h
    struct cfs_rq {
          …
          u64 runnable_load_sum;
          unsigned long runnable_load_avg;
          …
    };

如图2.44所示，如果当前正在执行的进程属于公平调度类，那么周期调度函数scheduler_tick()将调用公平调度类的task_tick方法，从当前进程到根任务组，计算每层公平运行队列的平均负载。

图2.44 周期性地计算公平运行队列的平均负载

函数___update_load_avg计算公平运行队列的平均负载，其代码如下：

    kernel/sched/fair.c
    1   static __always_inline int
    2   ___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
    3          unsigned long weight, int running, struct cfs_rq *cfs_rq)
    4   {
    5   u64 delta;
    6
    7   delta = now - sa->last_update_time;
    8   /*
    9    * 这应该只会在时间倒流时发生，
    10   * 不幸的是，在初始化调度时钟，换用TSC（time stamp counter）的过程中确实也会发生
    11   */
    12  if ((s64)delta < 0) {
    13       sa->last_update_time = now;
    14       return 0;
    15  }
    16
    17  delta >>= 10;
    18  if (! delta)
    19       return 0;
    20
    21  sa->last_update_time += delta << 10;
    22
    23  if (! accumulate_sum(delta, cpu, sa, weight, running, cfs_rq))
    24       return 0;
    25
    26  sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
    27  if (cfs_rq) {
    28       cfs_rq->runnable_load_avg =
    29             div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
    30  }
    31  sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
    32
    33  return 1;
    34  }

第7行代码，计算上一次计算平均负载到现在的时间间隔。

第17行代码，把时间间隔从纳秒转换成微秒。为了快速计算，不是除以1000，而是右移10位，相当于除以1024，因为移位操作比除法操作快。1024纳秒接近1微秒。

第21行代码，记录计算平均负载的时间。

第23行代码，调用函数accumulate_sum来计算负载总和。如果时间间隔至少包含一个完整周期，那么函数accumulate_sum返回真。

第27～30行代码，如果经过至少一个完整周期，那么计算负载平均值，把加权负载总和除以加权时间总和，加权时间总和总是取345个周期的加权时间总和，是一个常量。

函数accumulate_sum负责计算负载总和，其代码如下：

    kernel/sched/fair.c
    1   static __always_inline u32
    2   accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
    3          unsigned long weight, int running, struct cfs_rq *cfs_rq)
    4   {
    5    unsigned long scale_freq, scale_cpu;
    6    u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
    7    u64 periods;
    8
    9    scale_freq = arch_scale_freq_capacity(NULL, cpu);
    10   scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
    11
    12   delta += sa->period_contrib;
    13   periods = delta / 1024;
    14
    15   /*
    16    * 第1步：如果经过至少一个周期，那么衰减旧的负载总和
    17    */
    18   if (periods) {
    19        sa->load_sum = decay_load(sa->load_sum, periods);
    20        if (cfs_rq) {
    21              cfs_rq->runnable_load_sum =
    22                   decay_load(cfs_rq->runnable_load_sum, periods);
    23        }
    24        sa->util_sum = decay_load((u64)(sa->util_sum), periods);
    25
    26        /*
    27         * 第2步
    28         */
    29        delta %= 1024;
    30        contrib = __accumulate_pelt_segments(periods,
    31                   1024 - sa->period_contrib, delta);
    32   }
    33   sa->period_contrib = delta;
    34
    35   contrib = cap_scale(contrib, scale_freq);
    36   if (weight) {
    37        sa->load_sum += weight * contrib;
    38        if (cfs_rq)
    39              cfs_rq->runnable_load_sum += weight * contrib;
    40    }
    41    if (running)
    42         sa->util_sum += contrib * scale_cpu;
    43
    44    return periods;
    45   }

第9行代码，获取处理器频率。

第12行代码，把时间间隔加上period_contrib, period_contrib是上次计算平均负载时最后一个不完整周期走过的时间。

第13行代码，把时间间隔除以周期长度得到周期数量n，一个周期是1024微秒，约1毫秒。

第18行代码，如果经过至少一个完整周期，处理如下。

❑ 第20～23行代码，针对公平运行队列，把旧的负载总和乘以衰减系数的n次幂。

❑ 第29行代码，当前周期可能没结束，算出已经经历的时间长度。

❑ 第30行和第31行代码，调用函数__accumulate_pelt_segments来计算自从上次计算负载总和到现在这段时间的负载增量。

第33行代码，记录当前周期已经经历的时间长度。

第35行代码，把负载增量乘以处理器频率。

第38行和第39行代码，针对公平运行队列，把负载增量乘以权重，然后把负载增量加到负载总和。

函数__accumulate_pelt_segments负责计算自从上次计算负载总和到现在这段时间的负载增量，有3个参数：d1是上次计算负载总和的时候最后一个周期的剩余部分，periods是完整周期的数量，d3是当前周期已经经历的时间长度。

    kernel/sched/fair.c
    1   static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
    2   {
    3    u32 c1, c2, c3 = d3; /* y^0 == 1 */
    4
    5    /*
    6     * c1 = d1 y^p
    7     */
    8    c1 = decay_load((u64)d1, periods);
    9
    10   /*
    11    *          p-1
    12    * c2 = 1024 \Sum y^n
    13    *          n=1
    14    *
    15    *             inf       inf
    16    *    = 1024 ( \Sum y^n - \Sum y^n - y^0 )
    17    *              n=0      n=p
    18    */
    19   c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
    20
    21   return c1 + c2 + c3;
    22  }

第3行代码，计算当前周期已经经历的时间长度的负载增量。

第8行代码，计算上次计算负载总和的时候最后一个周期的剩余部分的负载增量。

第19行代码，计算periods个完整周期的负载增量。

第21行代码，把3部分负载增量相加。

（2）计算处理器负载。运行队列中描述处理器负载的成员如下：

    kernel/sched/sched.h
    struct rq {
          …
          #define CPU_LOAD_IDX_MAX 5
          unsigned long cpu_load[CPU_LOAD_IDX_MAX];
          …
    };

如图2.45所示，周期调度函数scheduler_tick()调用函数cpu_load_update_active()，计算处理器负载。

图2.45 周期性地计算处理器负载

函数cpu_load_update负责以根任务组的公平运行队列的平均负载值为基础计算处理器负载，参数this_load是公平运行队列的平均负载值，其代码如下：

    kernel/sched/fair.c
    static void cpu_load_update(struct rq *this_rq, unsigned long this_load,
                        unsigned long pending_updates)
    {
          …
          this_rq->cpu_load[0] = this_load;
          for (i = 1, scale = 2; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
              unsigned long old_load, new_load;
              old_load = this_rq->cpu_load[i];
              new_load = this_load;
              if (new_load > old_load)
                    new_load += scale - 1;
              this_rq->cpu_load[i] = (old_load * (scale - 1) + new_load) >> i;
          }
          …
    }

（3）负载均衡。调度器在以下情况下会执行处理器负载均衡。

1）周期性地主动负载均衡，时间间隔是1分钟。

2）除空闲线程外没有其他可运行的进程，处理器即将空闲。

如图2.46所示，周期调度函数scheduler_tick()判断有没有到达执行负载均衡的时间点，如果到达，触发调度软中断。调度软中断从处理器的基本调度域到顶层调度域执行负载均衡，在每层调度域，函数load_balance负责执行负载均衡。

图2.46 周期性地负载均衡

1）判断当前处理器是否应该执行负载均衡。这3种情况允许当前处理器执行负载均衡：当前处理器即将空闲，或是第一个调度组的第一个空闲处理器，或是第一个调度组的第一个处理器。

2）找出最忙的调度组。

3）从最忙的调度组中找出最忙的处理器。

4）从最忙的处理器中迁移若干个进程到当前处理器。

5）如果负载均衡失败，即没有迁移一个进程，那么为最忙处理器设置主动负载均衡标志，记录当前处理器作为迁移目标，向最忙处理器的停机工作队列添加一个工作，工作函数是active_load_balance_cpu_stop，唤醒最忙处理器的迁移线程。迁移线程将会从从停机工作队列取出工作，执行主动的负载均衡。

找出最忙的调度组