汀的知识碎片

3.3 调度时机

28 min read

3.4 调度时机

前面我们讲述的过程全部是进程何时进入任务队列，此时新进程还没有真正被调度。触发调度器开始真正调度，选择进程并上 CPU 开始运行的时机包括定时调度节拍，以及其它进程阻塞时主动让出两种。

3.4.1 调度节拍

在 Linux 中有一套时钟节拍机制。计算机系统随着时钟节拍需要周期性地做很多事情，例如刷新屏幕、数据落盘、进程调度等。Linux 每隔固定周期会发出 timer interrupt (IRQ 0)，HZ 是用来定义每一秒有多少次 timer interrupts。

通过查看 Linux 下的 /boot/config-xx 文件可以找到当前系统的 HZ 频率。具体命令可以使用：

# cat /boot/config-`uname -r` | grep 'CONFIG_HZ='
CONFIG_HZ=1000

如上的输出表示当前系统的时钟节拍是每秒 1000 次，也就是每隔 1 ms 执行一次。

对于任务调度器来说，定时器驱动的调度节拍是一个很重要的调度时机。时钟节拍最终会调用调度类的 task_tick 方法完成调度相关的工作。会在这里判断是否需要调度下一个任务来抢占当前 CPU 核。也会触发多核之间任务队列的负载均衡。保证不让忙的核忙死，闲的核闲死。调度节拍的核心入口是 scheduler_tick。

// file: kernel/sched/fair.c
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
  u64 vruntime = cfs_rq->min_vruntime;
  ...
  // 调整醒来后进程的 vruntime
  if (entity_is_long_sleeper(se))
    se->vruntime = vruntime;
  else
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}
// file: kernel/sched/core.c
void scheduler_tick(void) {
  int cpu = smp_processor_id();
  struct rq *rq = cpu_rq(cpu);
  struct task_struct *curr = rq->curr;
  // 1.将每个进程执行过的时间累计起来
  // 2.判断是否需要调度下一个任务
  curr->sched_class->task_tick(rq, curr, 0);
  // 3.触发负载均衡
  rq->idle_balance = idle_cpu(cpu);
  trigger_load_balance(rq);
}

在 scheduler_tick 中执行的 curr→sched_class→task_tick 这个函数在完全公平调度器中的具体实现是 kernel/sched/fair.c 下的 task_tick_fair。这个函数主要是调用 entity_tick 来完成工作。

在调度节拍中会定时将每个进程所执行过的时间都换算成 vruntime，并累计起来。也会定时判断当前进程是否已经执行了足够长的时间了，如果是的话需要再选择另一个 vruntime 较小的任务来运行。接下来我们分别来看下这两个逻辑。

vruntime 计算

完全公平调度器是基于 vruntime 来维持公平的。如果所有进程真的完全公平就好办了，vruntime 可以直接用在 cpu 上运行的真实时间。但是在实践中可能确实有进程需要多分配一点运行时间。Linux 采用的做法是根据优先级按不同比例进行 CPU 的分配。

具体的做法就是将 100-139 之间的优先级转变为 nice 值，也就是我们平时 top 命令结果中看到的 ni 这一列。nice 范围为 -20（最高权重）到 19（最低权重）。每个 nice 值都有不同的分配比例。在时间片的分配上，按照 nice 值进行分配。nice 越低，所分配到的时间片就越多。nice 越高，能分到的时间片就会少很多。每一种优先级通过 sched_prio_to_weight 数组定义了一个分配比例。

比如对于 nice 为 0 的任务来说，它的权重是 1024。对于 nice 为 -5 的任务，它的权重是 3121。是的，nice 越低，任务运行 CPU 所占的权重就越高。值得注意的是这个权重仅仅是一个分配比例，而不再是具体的时间。假如有三个就绪进程 A、B、C。其权重分别是 a、b、c。那么 A 进程获得到实际的时间比例是 a/(a+b+c)。

现在有很多人都把 nice 理解成了优先级，这是不太恰当的。优先级强调的是抢占，高优先级比低优先级有优先获得 CPU 的权利。而用户进程中的 nice 值强调的是获取到 CPU 运行时间的比例。在完全公平调度器中，将 nice 理解成权重比理解成优先级更合适一点。

// file:kernel/sched/fair.c
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
  // 更新当前任务的各种时间信息
  update_curr(cfs_rq);
  ...
  if (cfs_rq->nr_running > 1)
    // 检查是否需要抢占当前任务
    check_preempt_tick(cfs_rq, curr);
}
// file:kernel/sched/core.c
const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

我们来看下 vruntime 的具体计算过程。前面我们看到了在调度节拍中调用了 update_curr。这个函数会将进程的一些运行的信息汇总收集起来，其中就包括 vruntime。

在当前进程的 exec_start 存储的是它开始执行时的时间，用当前时间 now 减去这个值得到的就是当前进程现在运行了多长时间，其计算结果为 delta_exec。通过 calc_delta_fair 将实际运行时间转化为 vruntime。

在 calc_delta_fair 先判断当前进程的权重是不是 nice 为 0 的进程所对应的权重。在 sched_prio_to_weight 中定义了每个 nice 值对应的 weight，其中 nice 0 对应的是 1024。这里的 NICE_0_LOAD 就是 1024，之所以单独定义是为了加速计算。

如果当前进程的 se→load.weight 和 NICE_0_LOAD 相等的话，就可以直接返回实际运行时间了。也就是说，如果我们的进程使用的是默认的 nice 值 0 的话，那么 vruntime 就是等于实际的运行时间。如果 nice 不为 0，就调用 __calc_delta 将实际的运行时间进行缩放。

使用 nice 命令可以修改进程调度实体中的 load.weight。

__calc_delta 该函数是下面数学公式的一个实现，会根据进程的 weight 对实际运行时间进行缩放。其缩放所用的算法如下：

vruntime = (实际运行时间 * ((NICE_0_LOAD * 2^32) / weight)) >> 32

如果 nice 值比较低，那同样的实际运行时间算出来的 vruntime 就会偏小，这样它就会在调度中获得更多的 CPU。如果 nice 值比较高，那它算出来的 vruntime 就会比实际运行时间偏大。这样它就会在调度的过程中让其它的进程先运行。__calc_delta 函数为了追求极致的性能，实现上比较复杂一些，源码就不给大家展示了。

判断是否需要抢占调度

调度节拍也会调用 check_preempt_tick 来判断是否有其它进程需要来抢占当前任务。在这个函数中分两种情况。

  • 情况一：当前进程实际运行的时间比根据调度周期算出的期望的运行时间长了，需要让出 CPU
  • 情况二：当前进程的 vruntime 已经比红黑树中最左侧（vruntime 最小）的任务大不少了

在这两种情况中当前进程都需要让出 CPU，让下一个进程来运行。我们来看下源码：

// file:kernel/sched/fair.c
static void update_curr(struct cfs_rq *cfs_rq)
{
  delta_exec = now - curr->exec_start;
  curr->vruntime += calc_delta_fair(delta_exec, curr);
  ...
}
// file:kernel/sched/fair.c
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
  if (unlikely(se->load.weight != NICE_0_LOAD))
    delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
  return delta;
}

情况二比较好理解，当前进程的 vruntime 比其它等待运行的所有进程都大的超过一定幅度的时候就该让出 CPU。情况一稍微有点小复杂。这是专门为了解决 O(1) 调度器时代调度延迟不可控的问题核心手段。

CFS 摒弃了按优先级固定计算时间片的思路。根据当前系统的情况动态地计算调度周期。在一个调度周期这么长的时间内，就绪的任务都会被执行一次。具体思想就为先根据当前系统的负载情况计算出一个调度周期来。完全公平调度器并不会真正按这个周期来调度。它的作用是用来计算每个在 CPU 上的任务应该运行的时间。避免当前任务运行过长而导致后面排队的任务延迟过高。

// file:kernel/sched/fair.c
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
  // 情况1:当前进程实际运行的比预期长了
  ideal_runtime = sched_slice(cfs_rq, curr);
  delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
  if (delta_exec > ideal_runtime) {
    resched_curr(rq_of(cfs_rq));
    ...
    return;
  }
  // 避免当前进程运行的太短了
  if (delta_exec < sysctl_sched_min_granularity)
    return;
  // 情况2:当前进程的 vruntime 已经比其它进程大不少了
  se = __pick_first_entity(cfs_rq);
  delta = curr->vruntime - se->vruntime;
  
  if (delta > ideal_runtime)
    resched_curr(rq_of(cfs_rq));
}
// file:kernel/sched/fair.c
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
  // 先计算一个调度周期出来
  u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
  // 暂时不考虑组调度,此处的循环只会执行一次
  for_each_sched_entity(se) {
    // 获取整个运行队列 cfs_rq 的总权重
    cfs_rq = cfs_rq_of(se);
    load = &cfs_rq->load;
    ...
    // 调用函数获得 se 在整个队列中的权重比例分配时间
    slice = __calc_delta(slice, se->load.weight, load);
  }
  return slice;
}

函数 __sched_period 的作用就是在计算这个调度周期。如果当前核的运行队列上进程数不多的话，那就使用一个固定的调度周期。该周期是由 sysctl_sched_latency 内核参数来决定的。假如等待运行进程数量过多，那就给每个进程保证一个最小运行时间片，这个最小时间片由 sched_min_granularity_ns 参数来决定。有 N 个进程等待，那就 N * sysctl_sched_min_granularity 为一个调度周期。保证所有的进程都能快速得到处理一小段时间。调度周期计算源码如下：

// file:kernel/sched/fair.c
static u64 __sched_period(unsigned long nr_running)
{
  if (unlikely(nr_running > sched_nr_latency))
    return nr_running * sysctl_sched_min_granularity;
  else
    return sysctl_sched_latency;
}

在我手头的服务器上，sysctl_sched_latency 的值是 24ms。意味着在绝大部分情况下，每隔 24ms，就开启新一轮的调度。也就是说进程的调度延迟不会超过 24ms。如果就绪任务太多的时候，就给每个进程一段长为 sched_min_granularity 的时间。在我手头的一台机器上它设置的值是 3ms。目的是保证一个进程被执行的时候，最少可以运行这么久。

# sysctl -a | grep sched_
kernel.sched_latency_ns = 24000000
kernel.sched_min_granularity_ns = 3000000

因为调度周期是计算出来的，所以相比 2.5 时代的 O(1) 调度器比较可控，周期可控，那进程的调度延迟也就最大不会超过一个调度周期。

如果需要重新调度的话，就调用 resched_curr 来触发重新调度。

这里所谓的触发仅仅只是给当前运行的任务设置了一个 TIF_NEED_RESCHED 标记而已。通过 set_tsk_need_resched 来完成的 。真正的调度我们在 5.4.2 节讲述。

//file:kernel/sched/core.c
void resched_curr(struct rq *rq)
{
  struct task_struct *curr = rq->curr;
  int cpu;
  cpu = cpu_of(rq);
  ...
  set_tsk_need_resched(curr);
  ...
}
//file:include/linux/sched.h
static inline void set_tsk_need_resched(struct task_struct *tsk)
{
  set_tsk_thread_flag(tsk, TIF_NEED_RESCHED);
}

负载均衡

前面我们讨论的都是基于一个 CPU 核上的任务队列来讨论完全公平调度器的调度的。现代的服务器通常都是几十核上百核都很常见。每个核上都会存在一个任务队列。那会不会存在一种情况，有的核上的就绪任务已经堆到处理不过来了，有的核却很闲？

这种情况是完全有可能出现的，所有负载均衡模块存在的目的就是为了解决这种问题的。在讨论负载均衡之前，我们需要先讨论一下 Linux 中的调度域的概念。在上面我们介绍了主流的服务器中的 CPU 大概是如下图这种格式的。

CPU 拓扑示例

下图展示了一个由两颗 CPU 组成的服务器，每颗 CPU 上各有两个物理核，并且开启了超线程，将一个物理核当成了两个逻辑核来用。现实中的服务器 CPU 架构核数比这个要多得多，这个图只是为了简化来方便说明问题。

在这个服务器的所有的物理核之间进行任务迁移的话，由于共享 Cache 和访问内存的情况的不同，所以迁移带来的缓存性能损失是不太一样的，分成以下三种情况。

  • 逻辑核 0 和逻辑核 4：同属同一个物理核心，所有的 Cache 都是复用的。所以它们之间如果进行任务迁移的话，几乎是没太大的缓存损伤的。
  • 逻辑核 0 和逻辑核 1：虽然 L1/L2 是不同的，但是仍然共享同一个 L3，虽然缓存有损伤，但是损伤还不算太大。
  • 逻辑核 0 和逻辑核 2：所有的 CPU 缓存都无法复用，而且由于跨 Node 访问内存的情况存在，性能的损伤最大。

为了表示服务器上的这种 CPU 的逻辑结构，内核定义了调度域 sched_domain 内核对象。系统在启动的时候会根据 CPU 的物理结构来创建调度域。调度域是分级的，越是下层的调度域中的核，但共享缓存的特性越好。越上层的调度域，包含的核越多，但他们之间缓存共享的就差一些。

一个初始化后的调度域的树大概如下。分成了三级调度域。

// file:include/linux/sched/topology.h
struct sched_domain {
  struct sched_domain __rcu *parent;  
  struct sched_domain __rcu *child; 
  struct sched_group *groups; 
}
 
struct sched_group {
  ...
  unsigned long   cpumask[0];
};

其中最底层的三级调度域表达的是共享所有 CPU 高速的核的情况。负载均衡就是尽量在下层的调度域中进行调度，实在没有办法再往上层调度，最坏的情况就是到根调度域中进行跨物理 CPU 进行任务的迁移，这样的代价也最大。

负载均衡也是在调度节拍中定时发起的。在 scheduler_tick 中调用 trigger_load_balance 来触发。在 trigger_load_balance 中是通过和网络手法包类似，触发一个软中断来让 ksoftirqd 线程来处理真正的负载均衡过程。

完全公平调度器在系统初始化的时候就为 SCHED_SOFTIRQ 这种类型的软中断设置好了处理函数为 run_rebalance_domains。

ksoftirqd 在收到软中断后，调用 run_rebalance_domains 开始执行，会调用到 rebalance_domains。

// file:kernel/sched/fair.c
void trigger_load_balance(struct rq *rq)
{
  if (time_after_eq(jiffies, rq->next_balance))
    raise_softirq(SCHED_SOFTIRQ);
  nohz_balancer_kick(rq);
}
// file:kernel/sched/fair.c
__init void init_sched_fair_class(void)
{
  ...
  open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
}
// file:kernel/sched/fair.c
static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
{
  ...
  for_each_domain(cpu, sd) {
    ...
    // 计算出当前调度域负载均衡的时间间隔,这里会考虑 CPU 是否繁忙以及调度域的时间间隔区间
    interval = get_sd_balance_interval(sd, idle != CPU_IDLE);
    // 如果当前时间已经超过负载均衡的时间间隔,则触发负载均衡操作
    if (time_after_eq(jiffies, sd->last_balance + interval)) {
      if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
        ...
      }
    }
  }
}

rebalance_domains 函数的核心是一个循环。这个循环是从最底层开始遍历每一层调度域。优先尝试在最底层调度域实现负载均衡，然后再往二级调度域、根调度域上开始迁移尝试。

// file:kernel/sched/fair.c
static int load_balance(int this_cpu, struct rq *this_rq,
      struct sched_domain *sd, enum cpu_idle_type idle,
      int *continue_balancing)
{
  ...
  // 判断当前 CPU 是否可以从其它 CPU 拉点任务过来
  if (!should_we_balance(&env)) {
    *continue_balancing = 0;
    goto out_balanced;
  }
  // 通过对各个调度组的负载、利用率来确定哪个调度组最忙
  group = find_busiest_group(&env);
  // 在最忙的调度组中找出最忙的运行队列
  busiest = find_busiest_queue(&env, group);
  // 迁移一下
  if (busiest->nr_running > 1) {
    // 从源队列拉取任务
    cur_ld_moved = detach_tasks(&env);
    // 加入到目标 CPU 的任务队列上
    attach_tasks(&env);
    ...
  }
}

至于具体的 load_balance 过程就比较简单了。先是判断当前 CPU 是否有余力多处理一些任务。如果有的话根据当前调度域中的调度组（CPU 核列表）来计算一下看哪个调度组最忙，接着看哪个运行队列最忙。找到后，从源队列中拉取任务放到自己的任务队列上就可以了。

其中从源队列中拉取任务是调用 detach_tasks 函数实现的。这里要注意的是并不是说源队列中任务比较多就可以随便拉出来。有一些情况下是不可以被拉出的。比如说通过使用 taskset 命令，或者是在程序中调用 sched_setaffinity 为进程设置了调度亲和性，那很有可能这个进程是无法被拉出的。

// file:kernel/sched/fair.c
static int detach_tasks(struct lb_env *env)
{
  struct task_struct *p;
  while (!list_empty(tasks)) {
    // 获取队列中的一个任务
    p = list_last_entry(tasks, struct task_struct, se.group_node);
    // 判断当前任务是否能迁移到当前 cpu 上
    if (!can_migrate_task(p, env))
      goto next;
    ...
    detach_task(p, env);
  }
}

在 detach_tasks 中调用 can_migrate_task 判断所遍历到的任务是否能够被拉出到当前的 CPU 上。判断是在 can_migrate_task 中处理的。

在 can_migrate_task 其中一个判断就是进程的 CPU 亲和性。这个亲和性是存在 task_struct 下的 cpus_ptr、cpus_mask 中的。在后面的小节中我们再看 taskset 命令是如何为进程设置亲和性的。

3.4.2 真正的调度

前面我们看到在调度节拍中只是根据判断来决定是否需要抢占当前任务。而真正开始选择并运行任务队列中的下一个进程的核心入口是 schedule 函数。在内核中除了调度节拍外，其它进程如果主动放弃 CPU 的话也会触发 schedule 调度。

在《深入理解Linux网络》第3.3节中我们提到过，在同步阻塞网络编程模型下，如果 socket 上没有收到数据，或者收到不够多，则调用 sk_wait_data 把当前进程阻塞掉，让出 CPU 并调度运行队列中的其它进程进行。如果某一个进程发生了这样的阻塞。sk_wait_data 依次会调用 sk_wait_event、schedule_timeout，然后到达调度的核心函数 schedule。

我们来看看 schedule 函数的的核心实现 __schedule。在这个函数中把当前 CPU 的任务队列取了出来，接着获取下一个待运行的任务，再执行上下文切换到新进程上来运行。接下来我们分两个小节单独来看下。

// file: kernel/sched/fair.c
int can_migrate_task(struct task_struct *p, struct lb_env *env)
{
  ...
  if (!cpumask_test_cpu(env->dst_cpu, p->cpus_ptr)) {
    ...
  }
}
// file: kernel/sched/core.c
static void __sched notrace __schedule(unsigned int sched_mode)
{
  ......
  // 取出当前 CPU 及其任务队列
  cpu = smp_processor_id();
  rq = cpu_rq(cpu);
  // 1 获取下一个待执行任务
  next = pick_next_task(rq);
  // 2 执行上下文切换到新进程上
  context_switch(rq, prev, next);
  ......
}

获取下一个待执行任务

是如何获取下一个待执行任务的呢？我们来看下 pick_next_task 的实现。

因为大部分都是普通进程，所以大概率会执行到 pick_next_task_fair 函数中。该函数其实就是从当前任务队列的红黑树节点将运行虚拟时间最小的节点（最左侧的节点）选出来而已。

在调用 pick_next_entity 后，下一个待运行的调度实体进程就被选出来了。这里的调度实体有可能是实际的进程，也有可能是和 CPU cgroup 相关的调度组，我们将会在第八章中讲到容器中进程的调度过程再次讲到这里。

// file: kernel/sched/core.c
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
  if(...){
    p = pick_next_task_fair(rq, prev, rf);
    ...
  }
  ...
}
// file: kernel/sched/fair.c
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
  // 获取完全公平调取器
  struct cfs_rq *cfs_rq = &rq->cfs;
  // 从完全公平调取器红黑树中选择一个调度实体
  se = pick_next_entity(cfs_rq);
  ...
}

执行上下文切换到新进程上

假设我们已经选出来待运行的新进程以后，接着就需要执行进程上下文切换，把新进程的运行状态给切换上来。

当前进程上下文切换完成的时候，CPU上已经加载了新进程的地址空间、栈、寄存器等都收拾好了，新进程终于可以得以运行了！

3.5 任务切换开销实测

进程是操作系统的伟大发明，对应用程序屏蔽了CPU调度、内存管理等硬件细节，抽象出一个进程的概念，让应用程序专心于实现自己的业务逻辑。但是进程为用户带来方便的同时，也引入了一些额外的开销。如下图，在进程运行中间的时间里，虽然CPU也在忙于干活，但是却没有完成任何的用户工作，这就是进程机制带来的额外开销。

在3.4节我们介绍进程调度的时候，讲到了选出来待运行的新进程以后，接着就需要执行进程上下文切换，把新进程的运行状态给切换上来。这个上下文切换的主要函数是 context_switch。我们通过它可以看到进程上下文切换都干了啥。

// file: kernel/sched/core.c
static inline void
context_switch(struct rq *rq, struct task_struct *prev,
               struct task_struct *next)
{
  prepare_task_switch(rq, prev, next);
  ......
    
  // 执行地址空间切换
  switch_mm_irqs_off(prev->active_mm, next->mm, next);
  // 执行栈和寄存器切换
  switch_to(prev, next, prev);
  ......
}
// file: kernel/sched/core.c
static inline void
context_switch(struct rq *rq, struct task_struct *prev,
               struct task_struct *next)
{
  prepare_task_switch(rq, prev, next);
  ......
    
  // 执行地址空间切换
  switch_mm_irqs_off(prev->active_mm, next->mm, next);
  // 执行栈和寄存器切换
  switch_to(prev, next, prev);
  ......
}

图片引用

以下图片在本节中用于辅助说明（原文页码标注）：

  • [Image 511 on Page 112]
  • [Image 512 on Page 112]
  • [Image 519 on Page 113]
  • [Image 524 on Page 114]
  • [Image 529 on Page 115]
  • [Image 534 on Page 116]
  • [Image 542 on Page 118]