调度策略

在 Linux 里面，进程大概可以分成两种。

一种称为实时进程，也就是需要尽快执行返回结果的那种。另一种是普通进程，大部分的进程其实都是这种。

优先级其实就是一个数值，对于实时进程，优先级的范围是 0～99；对于普通进程，优先级的范围是 100～139。数值越小，优先级越高。

从这里可以看出，所有的实时进程都比普通进程优先级要高。

/****** task_struct 进程调度相关 ******/
// 是否在运行队列上
int        on_rq;
// 优先级
int        prio;
int        static_prio;
int        normal_prio;
unsigned int      rt_priority;
// 调度器类，封装了调度策略的执行逻辑
const struct sched_class  *sched_class;
// 调度实体
struct sched_entity    se; // 完全公平算法调度实体
struct sched_rt_entity    rt; // 实时调度实体
struct sched_dl_entity    dl; // Deadline 调度实体
// 调度策略
unsigned int      policy;
// 可以使用哪些CPU
int        nr_cpus_allowed;
cpumask_t      cpus_allowed;
struct sched_info    sched_info;


// 调度策略定义
#define SCHED_NORMAL    0
#define SCHED_FIFO    1  // 先来先服务
#define SCHED_RR    2
#define SCHED_BATCH    3
#define SCHED_IDLE    5
#define SCHED_DEADLINE    6

// 完全公平算法调度实体
struct sched_entity {
  struct load_weight    load;
  struct rb_node      run_node;
  struct list_head    group_node;
  unsigned int      on_rq;
  u64        exec_start;
  u64        sum_exec_runtime;
  u64        vruntime;
  u64        prev_sum_exec_runtime;
  u64        nr_migrations;
  struct sched_statistics    statistics;
  ......
};

实时进程的调度策略：SCHED_FIFO, SCHED_RR, SCHED_DEADLINE。

SCHED_FIFO 先来先服务，高优先级的进程可以抢占低优先级的进程，而相同优先级的进程，我们遵循先来先得。

SCHED_RR 轮流调度算法，采用时间片，相同优先级的任务当用完时间片会被放到队列尾部，以保证公平性，而高优先级的任务也是可以抢占低优先级的任务。

SCHED_DEADLINE，是按照任务的 deadline 进行调度的。当产生一个调度点的时候，DL 调度器总是选择其 deadline 距离当前时间点最近的那个任务，并调度它执行。

普通进程的调度策略：SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE。

SCHED_NORMAL 是普通的进程。

SCHED_BATCH 是后台进程，几乎不需要和前端进行交互。

SCHED_IDLE 是特别空闲的时候才跑的进程。

 

sched_class 有几种实现：

stop_sched_class 优先级最高的任务会使用这种策略，会中断所有其他线程，且不会被其他任务打断；

dl_sched_class 对应上面的 deadline 调度策略；

rt_sched_class 对应 RR 算法或者 FIFO 算法的调度策略，具体调度策略由进程的 task_struct->policy 指定；

fair_sched_class 普通进程的调度策略；

idle_sched_class 空闲进程的调度策略。

每个 CPU 都有自己的 struct rq 结构，用于描述在此 CPU 上所运行的所有进程，包括一个实时进程队列 rt_rq 和一个 CFS 运行队列 cfs_rq在。

调度时，调度器首先会先去实时进程队列找是否有实时进程需要运行，如果没有才会去 CFS 运行队列找是否有进程需要运行。

struct rq {
  /* runqueue lock: */
  raw_spinlock_t lock;
  unsigned int nr_running;
  unsigned long cpu_load[CPU_LOAD_IDX_MAX];
  ......
  struct load_weight load;
  unsigned long nr_load_updates;
  u64 nr_switches;


  struct cfs_rq cfs;
  struct rt_rq rt;
  struct dl_rq dl;
  ......
  struct task_struct *curr, *idle, *stop;
  ......
};


/* CFS-related fields in a runqueue */
struct cfs_rq {
  struct load_weight load;
  unsigned int nr_running, h_nr_running;

  u64 exec_clock;
  u64 min_vruntime;
#ifndef CONFIG_64BIT
  u64 min_vruntime_copy;
#endif
  struct rb_root tasks_timeline; // 指向红黑树的根节点
  struct rb_node *rb_leftmost; // 指向最左面的节点

  struct sched_entity *curr, *next, *last, *skip;
  ......
};

调度类的定义如下：

struct sched_class {
  const struct sched_class *next; // 指向下一个调度类
  
  // 向就绪队列中添加一个进程，当某个进程进入可运行状态时，调用这个函数
  void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
  // 将一个进程从就绪队列中删除
  void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
  void (*yield_task) (struct rq *rq);
  bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

  void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

  // 选择接下来要运行的进程
  struct task_struct * (*pick_next_task) (struct rq *rq,
            struct task_struct *prev,
            struct rq_flags *rf);
  // 用另一个进程代替当前运行的进程
  void (*put_prev_task) (struct rq *rq, struct task_struct *p);

  // 用于修改调度策略
  void (*set_curr_task) (struct rq *rq);
  // 每次周期性时钟到的时候，这个函数被调用，可能触发调度
  void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
  void (*task_fork) (struct task_struct *p);
  void (*task_dead) (struct task_struct *p);

  void (*switched_from) (struct rq *this_rq, struct task_struct *task);
  void (*switched_to) (struct rq *this_rq, struct task_struct *task);
  void (*prio_changed) (struct rq *this_rq, struct task_struct *task, int oldprio);
  unsigned int (*get_rr_interval) (struct rq *rq,
           struct task_struct *task);
  void (*update_curr) (struct rq *rq)
}

 

调度类分为下面这几种：

extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

它们其实是放在一个链表上的。这里我们以调度最常见的操作，取下一个任务为例，来解析一下。

可以看到，这里面有一个 for_each_class 循环，沿着上面的顺序，依次调用每个调度类的方法。

这就说明，调度的时候是从优先级最高的调度类到优先级低的调度类，依次执行。而对于每种调度类，有自己的实现，例如，CFS 就有 fair_sched_class。

/*
 * Pick up the highest-prio 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;
  ......
  for_each_class(class) {
    p = class->pick_next_task(rq, prev, rf);
    if (p) {
      if (unlikely(p == RETRY_TASK))
        goto again;
      return p;
    }
  }
}


const struct sched_class fair_sched_class = {
  .next      = &idle_sched_class,
  .enqueue_task    = enqueue_task_fair,
  .dequeue_task    = dequeue_task_fair,
  .yield_task    = yield_task_fair,
  .yield_to_task    = yield_to_task_fair,
  .check_preempt_curr  = check_preempt_wakeup,
  .pick_next_task    = pick_next_task_fair,
  .put_prev_task    = put_prev_task_fair,
  .set_curr_task          = set_curr_task_fair,
  .task_tick    = task_tick_fair,
  .task_fork    = task_fork_fair,
  .prio_changed    = prio_changed_fair,
  .switched_from    = switched_from_fair,
  .switched_to    = switched_to_fair,
  .get_rr_interval  = get_rr_interval_fair,
  .update_curr    = update_curr_fair,
};

对于同样的 pick_next_task 选取下一个要运行的任务这个动作，不同的调度类有自己的实现。

fair_sched_class 的实现是 pick_next_task_fair，rt_sched_class 的实现是 pick_next_task_rt。

我们会发现这两个函数是操作不同的队列，pick_next_task_rt 操作的是 rt_rq，pick_next_task_fair 操作的是 cfs_rq。

static struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
  struct task_struct *p;
  struct rt_rq *rt_rq = &rq->rt;
  ......
}


static 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;
  struct sched_entity *se;
  struct task_struct *p;
  ......
}

这样整个运行的场景就串起来了，在每个 CPU 上都有一个队列 rq，这个队列里面包含多个子队列，例如 rt_rq 和 cfs_rq，不同的队列有不同的实现方式，cfs_rq 就是用红黑树实现的。当有一天，某个 CPU 需要找下一个任务执行的时候，会按照优先级依次调用调度类，不同的调度类操作不同的队列。当然 rt_sched_class 先被调用，它会在 rt_rq 上找下一个任务，只有找不到的时候，才轮到 fair_sched_class 被调用，它会在 cfs_rq 上找下一个任务。这样保证了实时任务的优先级永远大于普通任务。

我们重点看下 fair_sched_class 对于 pick_next_task 的实现 pick_next_task_fair，获取下一个进程。

调用路径如下：pick_next_task_fair->pick_next_entity->__pick_first_entity。

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
  struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);

  if (!left)
    return NULL;

  return rb_entry(left, struct sched_entity, run_node);
}

主动调度

举例：从 Tap 网络设备等待一个读取。Tap 网络设备是虚拟机使用的网络设备。当没有数据到来的时候，它也需要等待，所以也会选择把 CPU 让给其他进程。

static ssize_t tap_do_read(struct tap_queue *q,
         struct iov_iter *to,
         int noblock, struct sk_buff *skb)
{
  ......
  while (1) {
    if (!noblock)
      prepare_to_wait(sk_sleep(&q->sk), &wait,
          TASK_INTERRUPTIBLE);
    ......
    /* Nothing to read, let's sleep */
    schedule();
  }
  ......
}

schedule 函数的调用过程

asmlinkage __visible void __sched schedule(void)
{
  struct task_struct *tsk = current;


  sched_submit_work(tsk);
  do {
    preempt_disable();
    __schedule(false);
    sched_preempt_enable_no_resched();
  } while (need_resched());
}


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

  // 1. 在当前的 CPU 上取出任务队列 rq
  cpu = smp_processor_id();
  rq = cpu_rq(cpu);
  prev = rq->curr;
  ......
  // 2. 获取下一个任务，即继任
  next = pick_next_task(rq, prev, &rf);
  clear_tsk_need_resched(prev);
  clear_preempt_need_resched();
  ......
  // 3. 当选出的继任者和前任不同，就要进行上下文切换，继任者进程正式进入运行
  if (likely(prev != next)) {
    rq->nr_switches++;
    rq->curr = next;
    ++*switch_count;
    ......
    rq = context_switch(rq, prev, next, &rf);
    ......
}

 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;
  /*
   * Optimization: we know that if all tasks are in the fair class we can call that function directly, 
   * but only if the @prev task wasn't of a higher scheduling class, 
   * because otherwise those loose the opportunity to pull in more work from other CPUs.
   */
  if (likely((prev->sched_class == &idle_sched_class ||
        prev->sched_class == &fair_sched_class) &&
       rq->nr_running == rq->cfs.h_nr_running)) {
    p = fair_sched_class.pick_next_task(rq, prev, rf);
    if (unlikely(p == RETRY_TASK))
      goto again;
    /* Assumes fair_sched_class->next == idle_sched_class */
    if (unlikely(!p))
      p = idle_sched_class.pick_next_task(rq, prev, rf);
    return p;
  }
again:
  for_each_class(class) {
    p = class->pick_next_task(rq, prev, rf);
    if (p) {
      if (unlikely(p == RETRY_TASK))
        goto again;
      return p;
    }
  }
}

again 就是依次调用调度类。但是这里有了一个优化，因为大部分进程是普通进程，所以大部分情况下会调用上面的逻辑，调用的就是 fair_sched_class.pick_next_task。

根据 fair_sched_class 的定义，它调用的是 pick_next_task_fair。

static 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;
  struct sched_entity *se;
  struct task_struct *p;
  int new_tasks;

对于 CFS 调度类，取出相应的队列 cfs_rq，这就是那棵红黑树。

    struct sched_entity *curr = cfs_rq->curr;
    if (curr) {
      if (curr->on_rq)
        update_curr(cfs_rq);
      else
        curr = NULL;
        ......
    }
    se = pick_next_entity(cfs_rq, curr);

取出当前正在运行的任务 curr，如果依然是可运行的状态，也即处于进程就绪状态，则调用 update_curr 更新 vruntime。

update_curr 会根据实际运行时间算出 vruntime 来。

接着，pick_next_entity 从红黑树里面，取最左边的一个节点。

  // 得到下一个调度实体对应的 task_struct
  p = task_of(se);

  // 如果发现继任和前任不一样，这就说明有一个更需要运行的进程了，就需要更新红黑树了。
  if (prev != p) {
    struct sched_entity *pse = &prev->se;
    ......
    // 前面前任的 vruntime 更新过了，put_prev_entity 放回红黑树，会找到相应的位置
    put_prev_entity(cfs_rq, pse);
    // 将继任者设为当前任务
    set_next_entity(cfs_rq, se);
  }

  return p

进程上下文切换

上下文切换主要干两件事情，一是切换进程空间，也即虚拟内存；二是切换寄存器和 CPU 上下文。

/*
 * context_switch - switch to the new MM and the new thread's register state.
 */
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
         struct task_struct *next, struct rq_flags *rf)
{
  struct mm_struct *mm, *oldmm;
  ......
  mm = next->mm;
  oldmm = prev->active_mm;
  ......
  switch_mm_irqs_off(oldmm, mm, next);
  ......
  /* Here we just switch the register state and the stack. */
  switch_to(prev, next, prev);
  barrier();
  return finish_task_switch(prev);
}

switch_to 是寄存器和栈的切换，它调用到了 __switch_to_asm。这是一段汇编代码，主要用于栈的切换。

// 32 位操作系统
/*
 * %eax: prev task
 * %edx: next task
 */
ENTRY(__switch_to_asm)
  ......
  /* switch stack */
  movl  %esp, TASK_threadsp(%eax)
  movl  TASK_threadsp(%edx), %esp
  ......
  jmp  __switch_to
END(__switch_to_asm)


// 64 位操作系统
/*
 * %rdi: prev task
 * %rsi: next task
 */
ENTRY(__switch_to_asm)
  ......
  /* switch stack */
  movq  %rsp, TASK_threadsp(%rdi)
  movq  TASK_threadsp(%rsi), %rsp
  ......
  jmp  __switch_to
END(__switch_to_asm)

最终，都返回了 __switch_to 这个函数。这个函数对于 32 位和 64 位操作系统虽然有不同的实现，但里面做的事情是差不多的。所以这里仅仅列出 64 位操作系统做的事情。

__visible __notrace_funcgraph struct task_struct *
__switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
  struct thread_struct *prev = &prev_p->thread;
  struct thread_struct *next = &next_p->thread;
  ......
  int cpu = smp_processor_id();
  struct tss_struct *tss = &per_cpu(cpu_tss, cpu);
  ......
  load_TLS(next, cpu);
  ......
  this_cpu_write(current_task, next_p);


  /* Reload esp0 and ss1.  This changes current_thread_info(). */
  load_sp0(tss, next);
  ......
  return prev_p;
}

所谓的进程切换，就是将某个进程的 thread_struct 里面的寄存器的值，写入到 CPU 的 TR 指向的 tss_struct，对于 CPU 来讲，这就算是完成了切换。

例如 __switch_to 中的 load_sp0，就是将下一个进程的 thread_struct 的 sp0 的值加载到 tss_struct 里面去。