Linux 内核调度器源码解析：从调度入口到挑选下一个进程

在Linux内核中，调度器（scheduler）扮演着至关重要的角色，决定了哪个进程将获得CPU的执行时间。本文将深入剖析内核中调度器的代码实现，从入口函数开始，一步步分析如何选择下一个要执行的进程。让我们一同揭开这个内核之谜。

调度器入口

Linux调度器入口函数定义在kernel/sched/core.c中：

asmlinkage __visible void __sched schedule(void)
{
    // 获取当前任务结构体的指针
    struct task_struct *tsk = current;

    // 将任务提交到调度工作队列中
    sched_submit_work(tsk);

    // 进入调度循环，直到没有需要被调度的任务
    do {
        // 禁用抢占
        preempt_disable();
        // 调用实际的调度函数 __schedule，并传入调度策略参数 SM_NONE
        __schedule(SM_NONE);
        // 启用抢占，但不进行重新调度
        sched_preempt_enable_no_resched();
    } while (need_resched()); // 循环直到没有需要重新调度的任务

    // 更新工作队列中的任务状态
    sched_update_worker(tsk);
}
EXPORT_SYMBOL(schedule);

调度器的入口函数是schedule，首先获取当前任务结构体的指针，然后将任务提交到调度工作队列中，接着进入一个循环，该循环会禁用抢占，调用实际的调度函数__schedule，并在循环结束后启用抢占。循环会一直执行，直到没有需要重新调度的任务为止。最后，函数会更新工作队列中任务的状态。函数最后export导出schedule函数以供其他部分使用。

static void __sched __schedule(bool preempt)
{
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct rq *rq;

    prev = current;
    rq = this_rq();
    switch_count = &prev->nivcsw;

    // 获取下一个要运行的进程
    next = pick_next_task(rq);

    // 切换到下一个进程
    context_switch(rq, prev, next, switch_count);

    // 如果需要抢占，启用抢占
    if (preempt)
        need_resched();
}

} 这里，__schedule函数负责实际的调度操作。首先，它获取了当前任务结构体的指针（prev）、运行队列（rq）以及切换计数器（switch_count）。然后，通过调用pick_next_task函数，它选择下一个要运行的进程（next）。最后，通过context_switch函数，它进行进程切换，将CPU控制权移交给下一个进程。

具体如何挑选下一个需要运行的进程，就要扒开pick_next_task函数。

pick_next_task

/*
 * 选择下一个要运行的任务。
 */
static inline struct task_struct *
__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
    const struct sched_class *class; // 定义调度类指针
    struct task_struct *p; // 定义任务结构体指针

    // 优化：如果前一个任务是公平调度类中的任务，且运行队列中的任务数与CFS队列中的任务数相等，
    // 则可以直接选择下一个公平类任务，因为其他调度类的任务无法抢占CPU。
    if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
               rq->nr_running == rq->cfs.h_nr_running)) {

        p = pick_next_task_fair(rq, prev, rf); // 选择下一个公平调度类任务
        if (unlikely(p == RETRY_TASK)) // 如果选择任务失败，需要重新尝试
            goto restart;

        if (!p) {
            put_prev_task(rq, prev);
            p = pick_next_task_idle(rq); // 如果没有可运行任务，则选择下一个空转调度类任务
        }

        return p;
    }

restart:
    put_prev_task_balance(rq, prev, rf); // 将前一个任务放回队列，进行重新平衡

    // 遍历所有调度类
    for_each_class(class) {
        p = class->pick_next_task(rq); // 选择下一个任务
        if (p)
            return p;
    }

    BUG(); // 如果没有可运行任务，引发BUG。空转类应该始终有可运行的任务。
}

这段代码是用于选择下一个要运行的任务的函数。首先，它检查是否可以优化选择下一个任务，如果前一个任务是公平调度类中的任务，并且运行队列中的任务数与CFS队列中的任务数相等，就可以直接选择下一个公平调度类任务。如果选择任务失败，会重新尝试，然后如果没有可运行任务，将选择下一个空转调度类任务。如果不满足优化条件，将会重新平衡队列，然后遍历所有的调度类，选择下一个任务。如果没有可运行任务，将引发BUG，因为空转类应该始终有可运行的任务。

struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
  struct cfs_rq *cfs_rq = &rq->cfs; // 获取CFS队列
  struct sched_entity *se; // 定义调度实体指针
  struct task_struct *p; // 定义任务结构体指针
  int new_tasks;

again:
  // 如果没有可运行的公平调度任务，跳转到idle标签
  if (!sched_fair_runnable(rq))
    goto idle;

#ifdef CONFIG_FAIR_GROUP_SCHED
  // 如果没有前一个任务，或者前一个任务不属于公平调度类，跳转到simple标签
  if (!prev || prev->sched_class != &fair_sched_class)
    goto simple;

  do {
    struct sched_entity *curr = cfs_rq->curr;

    // 如果当前任务存在
    if (curr) {
      // 如果当前任务在队列上，则更新其运行时间
      if (curr->on_rq)
        update_curr(cfs_rq);
      else
        curr = NULL;

      // 如果CFS队列的运行时间不正常，跳转到idle标签
      if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
        cfs_rq = &rq->cfs;

        // 如果没有可运行任务，跳转到idle标签
        if (!cfs_rq->nr_running)
          goto idle;

        goto simple;
      }
    }

    // 选择下一个调度实体，并切换到相应的CFS队列
    se = pick_next_entity(cfs_rq, curr);
    cfs_rq = group_cfs_rq(se);
  } while (cfs_rq);

  // 获取与选定实体关联的任务结构体
  p = task_of(se);

  // 如果前一个任务不等于选定任务，进行任务切换
  if (prev != p) {
    struct sched_entity *pse = &prev->se;

    while (!(cfs_rq = is_same_group(se, pse))) {
      int se_depth = se->depth;
      int pse_depth = pse->depth;

      if (se_depth <= pse_depth) {
        put_prev_entity(cfs_rq_of(pse), pse);
        pse = parent_entity(pse);
      }
      if (se_depth >= pse_depth) {
        set_next_entity(cfs_rq_of(se), se);
        se = parent_entity(se);
      }
    }

    put_prev_entity(cfs_rq, pse);
    set_next_entity(cfs_rq, se);
  }

  goto done;
simple:
#endif
  // 如果有前一个任务，将其放回队列
  if (prev)
    put_prev_task(rq, prev);

  do {
    // 选择下一个调度实体，并切换到相应的CFS队列
    se = pick_next_entity(cfs_rq, NULL);
    set_next_entity(cfs_rq, se);
    cfs_rq = group_cfs_rq(se);
  } while (cfs_rq);

  // 获取与选定实体关联的任务结构体
  p = task_of(se);

done: __maybe_unused;

#ifdef CONFIG_SMP
  // 将下一个正在运行的任务移动到队列的前面
  list_move(&p->se.group_node, &rq->cfs_tasks);
#endif

  // 如果启用高精度定时器，开始高精度定时
  if (hrtick_enabled_fair(rq))
    hrtick_start_fair(rq, p);

  // 更新不适合运行的任务状态
  update_misfit_status(p, rq);

  return p;

idle:
  // 如果没有rf标志，返回NULL
  if (!rf)
    return NULL;

  // 尝试进行新的空闲平衡操作
  new_tasks = newidle_balance(rq, rf);

  // 如果新的平衡操作失败，返回RETRY_TASK标志
  if (new_tasks < 0)
    return RETRY_TASK;

  // 如果有新的可运行任务，回到again标签重新选择
  if (new_tasks > 0)
    goto again;

  // 如果队列即将变为空闲状态，检查是否需要更新时钟pelt的lost_idle_time
  update_idle_rq_clock_pelt(rq);

  return NULL;
}

这个函数用于选择下一个要在公平调度类中运行的任务。函数中包含了条件判断和循环，以确保选择最适合的任务。

/*
 * 选择下一个调度实体，考虑以下因素，按照顺序：
 * 1) 在进程/任务组之间保持公平性
 * 2) 选择“下一个”进程，因为某个进程确实希望运行
 * 3) 选择“上一个”进程，以提高缓存局部性
 * 4) 如果其他任务可用，则不运行“跳过”的进程
 */
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
  struct sched_entity *left = __pick_first_entity(cfs_rq);  // 获取最左边的实体
  struct sched_entity *se;

  /*
   * 如果 curr 被设置，我们必须查看它是否位于树中最左边的实体的左侧，
   * 前提是树中确实有实体存在。
   */
  if (!left || (curr && entity_before(curr, left)))
    left = curr;

  se = left; /* 理想情况下，我们运行最左边的实体 */

  /*
   * 避免运行跳过的实体，如果可以不运行其他实体而不会太不公平。
   */
  if (cfs_rq->skip && cfs_rq->skip == se) {
    struct sched_entity *second;

    if (se == curr) {
      second = __pick_first_entity(cfs_rq);  // 获取最左边的实体
    } else {
      second = __pick_next_entity(se);  // 获取下一个实体
      if (!second || (curr && entity_before(curr, second)))
        second = curr;
    }

    if (second && wakeup_preempt_entity(second, left) < 1)
      se = second;
  }

  if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
    /*
     * 有人确实希望运行这个实体。如果不不公平，就运行它。
     */
    se = cfs_rq->next;
  } else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
    /*
     * 更倾向于运行最后一个实体，尝试将 CPU 返回到一个被抢占的任务。
     */
    se = cfs_rq->last;
  }

  return se;
}

if (se == curr) {
  second = __pick_first_entity(cfs_rq);  // 获取最左边的实体
} else {
  second = __pick_next_entity(se);  // 获取下一个实体
  if (!second || (curr && entity_before(curr, second)))
    second = curr;
}

if (second && wakeup_preempt_entity(second, left) < 1)
  se = second;

return se; } 函数pick_next_entity的作用是选择下一个要运行的调度实体，它根据一系列因素来决定选择哪个实体，以确保公平性、满足任务需求，并尽量提高缓存局部性。

总结

通过深入分析Linux内核调度器的代码实现，我们了解了调度器的入口函数和选择下一个执行进程的过程。这个过程是内核多任务处理的核心，确保了系统资源的合理分配。深入理解调度器的工作原理将有助于我们更好地优化系统性能，提高响应速度。