Linux Kernel: Process Scheduling

struct runqueue {
    // runqueue 维护的所有 running 进程的个数, 是 active 和 expired 之和.
    // 这个值反应了当前 cpu 的负载程度
    unsigned long nr_running;
    /* curr 即 current, idle 即 swapper */
    task_t *curr, *idle;
    /* 最主要的数据结构: runqueue 中所有的进程被分为两类: active 与
     * expired, active 是指时间片尚没有耗尽的进程, expired 是指本次
     * roundrobin 过程中时间片已经耗尽的进程, scheduler 只会从 active
     * 中寻找 candidate, 参考 process */
    prio_array_t *active, *expired, arrays[2];
    /* 指示是否需要将当前 runqueue 的 task 转换到其它 cpu */
    int active_balance;
}

struct task_struct {
    volatile long state;

    /* dynamic priority */
    int prio
    /* static priority */
    int static_prio;

    /* 和 runqueue 有关 */
    struct list_head run_list;
    prio_array_t *array;

    // 平均睡眠时间, 和 time slice 大小及 interactive process 的判定有关,
    // 需要注意的是 sleep_avg 是指 1s 之内处于 sleeping 的时间, 但它的统
    // 计方法并不是严格意义上的平均, 只是一种近似的方法
    unsigned long sleep_avg;
    // timestamp 是记录 task 与计算 sleep_avg 相关的时间戳
    // 1. 被 schedule in 或 out 的时间 (schedule)
    // 2. 被唤醒的时间 (try_to_wake_up)
    unsigned long long timestamp, last_ran;
    int activated;

    /* scheduler: SCHED_FIFO, SCHED_RR 或 SCHED_NORMAL */
    unsigned long policy;

    /* CPU mask */
    cpumask_t cpus_allowed;

    /* 当前进程剩余的时间片 */
    unsigned int time_slice
    unsigned int first_time_slice;

    /* 实时优先级(policy 需要是 FIFO 或 RR) */
    unsigned long rt_priority;
};

try_to_wake_up:
  activate_task()
    recalc_task_prio()
      sleep_time = now - p->timestamp;
      if (sleep_time > NS_MAX_SLEEP_AVG):
        sleep_time = NS_MAX_SLEEP_AVG;
      p->sleep_avg += sleep_time;
      if (p->sleep_avg > NS_MAX_SLEEP_AVG):
        p->sleep_avg = NS_MAX_SLEEP_AVG;
      p->prio = effective_prio(p);
    __activate_task(p, rq);
      enqueue_task(p, rq->active);
  // 抢占
  if (TASK_PREEMPTS_CURR(p, rq)):
    resched_task(rq->curr);

schedule:
  prev = current;
  rq = this_rq();
  // schedule 只会从 active 中取进程
  array = rq->active;
  if (!array->nr_active):
    // Switch the active and expired arrays.
    rq->active = rq->expired;
    rq->expired = array;
    array = rq->active;
  // 这三行代码可以常数时间内选择 active 中一个动态优先级最高的链表, 所以
  // 称为 O(1) schedule
  idx = sched_find_first_bit(array->bitmap);
  queue = array->queue + idx;
  next = list_entry(queue->next, task_t, run_list);
  if (!rt_task(next):
    // 对于 conventional task, 直接移动到 active 队尾, 在这一点上
    // SCHED_FIFO 及 SCHED_RR 与它不同: 对于 rt_task, 只有主动 yield 才会
    // 导致它被放在队尾, 被抢占并不会将它放在队尾
    array = next->array;
    dequeue_task(next, array);
    enqueue_task(next, array);

  // sleep_avg 相关
  //
  // task_struct->timestamp 是指 task 最近一次被调度的时间 (schedule in
  // 或 out), 所以 run_time 是 prev 本次运行的时间
  run_time = now - prev->timestamp;
  prev->sleep_avg -= run_time;
  prev->timestamp = next->timestamp = now;
  // switch !
  prepare_arch_switch(rq, next);
  prev = context_switch(rq, prev, next);

set_user_nice:
  if (rt_task(p)):
    // 对于 rt_task, static_prio 也会被 nice 修改, 因为计算 time_slice
    // 进需要用到.
    p->static_prio = NICE_TO_PRIO(nice);
    goto out;

  array = p->array;
  if (array):
    dequeue_task(p, array);

  old_prio = p->prio;
  new_prio = NICE_TO_PRIO(nice);
  delta = new_prio - old_prio;
  p->static_prio = NICE_TO_PRIO(nice);
  p->prio += delta;

  if (array):
    enqueue_task(p, array);
    // 如果要提高某个 task 的优先级, 或者要降低当前 task 的优先级, 则通过
    // resched_task 调用 scheduler, 实现 task 的抢占
    if (delta < 0 || (delta > 0 && task_running(rq, p))):
      resched_task(rq->curr);

sys_sched_yield:
  runqueue_t *rq = this_rq_lock();
  prio_array_t *array = current->array;
  prio_array_t *target = rq->expired;
  // 对于 rt_task 来说, yield 并不会将 task 移动到 expired, 而仅仅是移动
  // 到 active 的队尾
  if (rt_task(current)):
    target = rq->active;

  // 对于 rt_task 来说, 通过 dequeue_task 和 enqueue_task 将 task 移动到
  // active 队尾, 对于 conventional task 来说, 将 task 从 active 移动到
  // expired.
  // 但看起来 task 的 time_slice 并没有通过 task_timeslice 进入补充, 所以
  // 它将被 schedule 时还会使用旧的 time_slice?
  dequeue_task(current, array);
  enqueue_task(current, target);

  schedule();

fork:
  sched_fork(p)
    p->state = TASK_RUNNING;
    p->array = NULL;
    // 父子进程的 time_slice 都变为父进程的一半
    p->time_slice = (current->time_slice + 1) >> 1;
    current->time_slice >>= 1;
  wake_up_new_task(p)
    // 计算动态优先级, 对于 conventional process, prio 由 static_prio 和
    // sleep_avg 决定, 对于 real time process, prio 不会再被修改, 直接使
    // 用 parent fork 出来的 prio
    p->prio = effective_prio(p);
    if (!(clone_flags & CLONE_VM)):
      // CLONE_VM 没有置位, 先调度子进程执行, 因为有可能子进程会直接调用
      // exec. 通过让子进程先执行 exec, 可以避免父进程写内存时导致的 COW,
      // 如果 CLONE_VM 置位, 则不会发生 COW, 优先让父进程执行
      p->prio = current->prio;
      list_add_tail(&p->run_list, &current->run_list);
      p->array = current->array;
      // "让子进程先执行"是通过两点做到的:
      //
      // 1. 通过 list_add_tail (而不是通常的 enqueue_task) 将 p 添加到
      // active 链表中, 但位于 current 之前
      //
      // 2. set_need_resched 会使 current 进程返回到 user mode 前发生
      // schedule, 由于 p 上一步已经在链表中 current 之前, 所以它极有可能
      // 在 schedule 被选中, 但即使没有选中 p, 也可以保证 p 肯定在
      // current 之前被调度
      set_need_resched();
    else:
      enqueue_task(p, rq->active);
      rq->nr_running++;