Archive:

LKD 读书笔记 Part 2

jwnhy Feb 25, 2022

LKD Chapter 3 进程调度

I/O 密集与计算密集

进程分为 I/O 密集与计算密集。

  I/O 密集 计算密集
时间片 短 长
主任务 处理 I/O 计算
中断 密集 几乎没有
例子 文本编辑 MATLAB

进程优先级

Linux 中进程优先级分为两个值 nice 值与 rtprio 值。 前者决定了普通进程的优先级，越大的 nice 代表进程优先级越低（对其他进程越 nice）。 后者决定了实时进程的优先级，越大的 rtprio 代表进程优先级越高。

nice 的取值范围是 -20～+19，rtprio 的取值范围是 0～99。

两者分开调度，实时进程总有比普通进程高的优先级。

查看实时优先级

ps -eo state, uid, pid, ppid, rtprio, time, comm

时间片

与一般操作系统不同，Linux 不直接对进程分配时间片，而是使用 CFS 确保进程运行时间的占用比例。 而 nice 值则是他们的占用比例的权重。 例如，有一个文本编辑器和一个视频编码器在同时运行，有着相同的 nice 值。 那么他们各自占用 50% 的处理器，而文本编辑器只需要在需要的时候才会响应，因此在 CFS 看来， 它总是未完全使用自己的时间，因此总是会优先响应它，而视频编码器也可以在文本编辑器未运行的时候充分利用 CPU 资源。

传统 UNIX 分配的缺点

传统 UNIX 分配的方式也是通过 nice 值决定进程优先级以及时间片的大小，但它有下面的缺点。

  1. 每一个 nice 值对应的绝对时间片难以确定。 例如，有两个进程分别有 0 和 +20 的 nice 值，那么他们分配的时间是 100 ms 和 5 ms。 但如果是同时有两个进程有 0 的 nice 值，那么他们分配的时间就会变成 100 ms 和 100 ms。 相似的，如果同时有两个进程有 +20 的 nice 值，那么他们分配的时间就会变成 5 ms 和 5 ms。 前者导致响应时间长，后者导致频繁的上下文切换。

  2. nice 值之间的差值不一致，nice 值为 0 和 1 的进程分配的时间片可能是 100 ms 和 95 ms。 相差无几，但 nice 值为 18 和 19 的可能是 10 ms 和 5 ms ，相差一倍。

  3. 时间片必须是时钟的整数倍。

  4. 对于刚唤醒进程的处理，系统常常会使得刚唤醒的进程有更高的优先级，即使它们的时间片已经用光。 这对交互式程序的体验有好处，但无疑影响了公平性。

CFS 调度

一个理想的调度算法，在不考虑上下文切换的开销的情况下，会希望所有任务在很小的 $\epsilon$ 时间内都运行一遍。 当然这在现实是不可能做到的，因为存在上下文开销。但是 CFS 会尝试接近这个理想模型，CFS 设置了一个 targeted latency。 也就是上面说的 $\epsilon$，当存在 $n$ 个任务时，每个任务所占用的时间是 $\frac{\epsilon}{n}$。值得注意的是， 如果 $n\rightarrow \infty$，会导致上下文切换的次数趋于无穷。因此 CFS 设置了一个最小粒度，默认为 1 ms。 而 nice 值在 CFS 算法中被用来计算每个任务应当占用的时间权重，CFS 会不断试图接近理想的分配方案， 它总是选择已经占用最少的任务进行执行。

与这个问题十分类似。

CFS 调度实现

CFS 算法分为下面几个部分。

  • 时间统计
  • 进程选择
  • 调度器入口
  • 休眠与唤醒

时间统计

调度对象结构体

CFS 并没有时间片的概念，但它仍然需要记录每个进程运行的时间来确保它们只运行公平的时间。 CFS 在 <linux/sched.h> 中引入了 struct sched_entity

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; // accounting the current running time
  u64 prev_sum_exec_runtime;
  u64 last_wakeup;
  u64 avg_overlap;
  u64 nr_migrations;
  u64 start_runtime;
  u64 avg_wakeup;
  /* many stat variables elided, enabled only if CONFIG_SCHEDSTATS is set */
}

该结构体直接嵌入 task_struct 中，成员名为 se。

vruntime

vruntime 指当前进程运行的时间经过 nice 值作为权重标准化之后的值。 更新它的函数是定义在 <linux/sched_fair.c> 中的 update_curr(struct cfs_rq *cfs_rq)。 它的步骤如下。

  • 获取当前时间

    u64 now = rq_of(cfs_rq)->clock;

  • 计算差值

    delta_exec = (unsigned long) (now - curr -> exec_start);

  • 更新 vruntime

    __update_curr(cfs_rq, curr, delta_exec);

  • 更新开始时间

    curr->exec_start = now;

具体加权求值的方式在 __update_curr 中。

static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
unsigned long delta_exec)
{
  unsigned long delta_exec_weighted;

  schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));

  curr->sum_exec_runtime += delta_exec;
  schedstat_add(cfs_rq, exec_clock, delta_exec);
  delta_exec_weighted = calc_delta_fair(delta_exec, curr);

  curr->vruntime += delta_exec_weighted;
  update_min_vruntime(cfs_rq);
}

进程选择

之前讨论过，在一个理想的多任务系统中，每个进程的 vruntime 都应该是一样的。 CFS 做不到这一点，因此它采用了一种很简单的方法。

每次挑选 vruntime 最小的进程。

红黑树

CFS 使用红黑树 rbtree 来管理可运行的进程列表，能够快速的寻找到 vruntime 最小的进程。

进程选择的代码如下，值得注意的是，Linux 并没有真的遍历整颗树，而是缓存了最左节点。

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
  struct rb_node *left = cfs_rq->rb_leftmost;
  if (!left)
    return NULL;
  return rb_entry(left, struct sched_entity, run_node);
}
向树中添加节点

每一次有进程被唤醒/创建时，都会向红黑树中添加进程并且缓存最左节点。

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
  /*
  * Update the normalized vruntime before updating min_vruntime
  * through callig update_curr().
  */
  // 如果是刚创建的进程，将当前最小的 `vruntime` 加上
  if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
    se->vruntime += cfs_rq->min_vruntime;

  /*
  * Update run-time statistics of the ‘current’.
  */
  update_curr(cfs_rq);
  account_entity_enqueue(cfs_rq, se);

  if (flags & ENQUEUE_WAKEUP) {
    place_entity(cfs_rq, se, 0);
    enqueue_sleeper(cfs_rq, se);
  }

  update_stats_enqueue(cfs_rq, se);
  check_spread(cfs_rq, se);
  if (se != cfs_rq->curr)
    __enqueue_entity(cfs_rq, se);
}

真正向树中添加节点的是 __enqueue_entity 函数。

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
  struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
  struct rb_node *parent = NULL;
  struct sched_entity *entry;
  s64 key = entity_key(cfs_rq, se);
  int leftmost = 1;
  /*
  * Find the right place in the rbtree:
  */
  while (*link) {
    parent = *link;
    entry = rb_entry(parent, struct sched_entity, run_node);
    /*
    * We dont care about collisions. Nodes with
    * the same key stay together.
    */
    if (key < entity_key(cfs_rq, entry)) {
      link = &parent->rb_left;
    } else {
      link = &parent->rb_right;
    leftmost = 0;
    }
  }

  /*
  * Maintain a cache of leftmost tree entries (it is frequently
  * used):
  */

  if (leftmost)
    cfs_rq->rb_leftmost = &se->run_node;

  // rbtree function to maintain its properties
  rb_link_node(&se->run_node, parent, link);
  rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}
向树中移除节点

向红黑树中移除节点也类似，注意到它会先更新 curr 的时间统计数据再进行移除。

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
{
  /*
  * Update run-time statistics of the ‘current’.
  */
  update_curr(cfs_rq);

  update_stats_dequeue(cfs_rq, se);
  clear_buddies(cfs_rq, se);
  if (se != cfs_rq->curr)
    __dequeue_entity(cfs_rq, se);
  account_entity_dequeue(cfs_rq, se);
  update_min_vruntime(cfs_rq);

  /*
  * Normalize the entity after updating the min_vruntime because the
  * update can refer to the ->curr item and we need to reflect this
  * movement in our normalized position.
  */
  if (!sleep)
    se->vruntime -= cfs_rq->min_vruntime;
}

移除节点时，我们只需要注意移除的是否是我们缓存的节点，然后使用 rbtree 的接口即可。

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
  if (cfs_rq->rb_leftmost == &se->run_node) {
    struct rb_node *next_node;
    next_node = rb_next(&se->run_node);
    cfs_rq->rb_leftmost = next_node;
  }
  rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}
调度器入口

schedule() 调度函数设计比较简单，它找到具有最高优先级且非空的调度器类，然后问它下一个应该执行的进程。

具体过程定义在 pick_next_task() 中，值得注意的是，由于大部分时候 Linux 执行的都是普通任务。 因此如果所有的进程都是普通进程，则直接调用 CFS 调度。 后面的 for 循环找出第一个有可运行进程 non-NULL 的进程类。

/*
* Pick up the highest-prio task:
*/
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
  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:
  */
  if (likely(rq->nr_running == rq->cfs.nr_running)) {
    p = fair_sched_class.pick_next_task(rq);
    if (likely(p))
    return p;
  }
  class = sched_class_highest;
  for ( ; ; ) {
    p = class->pick_next_task(rq);
    if (p)
    return p;
    /*
    * Will never be NULL as the idle class always
    * returns a non-NULL p:
    */
    class = class->next;
  }
}

休眠与唤醒

image.png

休眠

休眠在内核中有点复杂，因为可能发生竞争，既进入休眠时，条件恰好为真，导致出现无限休眠。 因此推荐的内核休眠方式如下

/* ‘q’ is the wait queue we wish to sleep on */
DEFINE_WAIT(wait);

add_wait_queue(q, &wait);
while (!condition) { /* condition is the event that we are waiting for */
  prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
  if (signal_pending(current))
    /* handle signal */
    schedule();
}
finish_wait(&q, &wait);

  1. 创建休眠项 DEFINE_WAIT()

  2. 添加到休眠队列中 add_wait_queue()，由别处调用该队列的 wake_up() 唤醒。

  3. 调用 prepare_to_wait 设置进程状态为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTABLE。

  4. 如果为 TASK_INTERRUPTIBLE，接收到信号处理完信号接着休眠。

  5. 当进程苏醒，查看条件是否为真，否阶接着睡。

  6. 如果条件为真，调用 finish_wait 结束休眠。

fs/notify/inotify/inotify_user.c 中的 inotify_read() 是这个模式的一个例子。

唤醒

唤醒通过 wake_up() 函数实现，其唤醒给定队列中的所有进程。 调用 try_to_wake_up() 将进程状态设置为 TASK_RUNNING。 调用 enqueue_task() 将进程加入红黑树，并且如果唤醒进程的优先级较高需要重新调度，则设置 need_resched 。

抢占与上下文切换

上下文切换

上下文切换由 kernel/sched.c 中的 context_switch() 函数实现，并由 schedule 调用，分为下面两步。

  • 调用 <asm/mmu_context.h> 中的 switch_mm() 切换虚拟地址映射。
  • 调用 <asm/system.h> 中的 switch_to() 切换处理器状态，包括栈指针，处理器寄存器等其他架构相关状态。

抢占

内核必须知道何时调用 schedule() 进行进程切换，因为如果像协程一样依赖用户程序主动调用，会导致 用户进程有能力一直运行下去。

内核提供了 need_resched 来标志是否需要进行重新调度。有两个函数会设置这个标记。

  • scheduler_tick() 当一个进程应该被抢占时。
  • try_to_wake_up() 当一个优先级高于当前进程的进程被唤醒时。
函数 功能
set_tsk_need_resched 设置标记
clear_tsk_need_resched 清除标记
need_resched 返回标记
用户抢占

用户抢占发生在内核态返回用户态时。当内核即将返回用户空间时，这时是一个安全状态。 内核既可以继续运行当前进程，也可以选一个新进程运行。因此内核会检查 need_resched 来决定是否 调用 schedule() 函数进行调度。

以下两种情况会发生用户抢占。

  1. 当内核从 系统调用 返回用户态时。
  2. 当内核从 中断处理 返回用户态时。
内核抢占

不同于其他 Unix 内核，Linux 内核支持内核抢占。

为了能够安全的进行内核抢占，首先引入了 preempt_count。 其会记录当前进程持有锁的数量，每次取得锁 preempt_count++，每次释放锁 preempt_count--。 当 need_resched = true && preempt_count == 0 时，可以安全的进行抢占。

内核抢占也可以通过显式调用 schedule() 函数实现。一般来说，内核抢占可以发生在下面这些情况下。

  1. 当一个中断处理函数退出，返回内核态时。
  2. 当内核代码变成可抢占的，即释放锁时。
  3. 当一个内核进程显式调用 schedule()。
  4. 当一个内核进程阻塞时，其会导致调用 schedule()。

相关系统调用

image.png