《Linux内核设计与实现》阅读笔记：(第四章)进程调度

发表于 | 分类于 | 阅读次数:
字数统计: 3,073 | 阅读时长 ≈ 11

进程调度是操作系统的核心功能，本篇继续追随《Linux内核设计与实现》的脚步，摸清Linux进程调度的原理。

多任务

调度程序主要负责决定三件事：

  • 执行哪个进程；
  • 什么时候执行；
  • 执行多长时间；

最大限度利用处理器时间原则：只要有可执行的进程，那么总会有进程正在执行。

多任务系统分类：

  • 非抢占式多任务：除非进程自己停止运行，否则就会一直执行；
  • 抢占式多任务：由电镀程序决定什么时候停止一个进程的运行，以便其它进程得到执行的机会，被抢占之前能狗运行的时间是预先设置好的，这个时间称为“时间片”；

绝大多数系统(包括Linux)是抢占式多任务系统。

Linux进程调度简介

Linux采用的调度算法是在不断演进的。2.5版本采用的是一种O(1)的调度程序，2.6.23用完全公平调度算法(CFS)替换了O(1)调度算法，发展历史如下：

(注：图片出自陈向群《操作系统原理》公开课)

策略

I/O消耗型和处理器消耗型进程

进程按执行过程划分可以用一张图表示：

进程划分

(注：图片出自陈向群《操作系统原理》公开课)

对于处理器密集型进程，调度策略往往是尽量降低它们的调度频率，延长运行时间；

调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速(响应时间短)和最大系统利用率(高吞吐量)；

Linux更倾向于优先调度I/O密集型进程，但并未忽视处理器密集型进程；

进程优先级

Linux采用两种不同的优先级范围：

  • nice值

nice是代表静态优先级的数值，范围从-20到+19，默认值为0。越大的nice值意味更低的优先级，在Linux系统中nice值代表时间片的比例；

  • 实时优先级

默认情况下它的变化范围是从0到99(包括0和99)，越高的实时优先级数值意味着进程优先级越高，实时进程的优先级高于普通进程；

时间片

Linux的CFS调度器没有直接分配时间片到进程，它将处理器的使用比划分给了进程，所以处理器时间其实和系统负载密切相关；

Linux中使用新的CFS调度器后，抢占时机取决于新的可运行程序消耗了多少处理器使用比，如果消耗的使用比比当前进程小，则新进程立刻投入运行抢占当前进程，否则推迟运行；

Linux调度算法

直接看看Linux的调度算法吧。

调度器类

Linux scheduler是modular的，这样允许不同算法调度不同类型的进程。每一个scheduler class有一个优先级，the base scheduler code定义在kernel/sched.c，这个基础代码按照优先级来迭代每一个scheduler class；

CFS是为普通进程注册的scheduler class，定义在kernel/sched_fair.c；

传统Unix系统调度器的改造

Linux的CFS对时间片分配方式进行了根本性重新设计，摒弃时间片而是分配给进程一个处理器使用比重，通过这种方式CFS确保了进程调度中能有恒定的公平性但切换速率可变；

公平调度

CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片；

任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比；

Linux调度实现

CFS四部分：

  • Time Accounting
  • Process Selection
  • The Scheduler Entry Point
  • Sleeping and Waking Up

Time Accounting

在大多数Unix系统中，所有进程调度器给每一个进程分配一个时间片，用来计算处理器运行的时间，每经过一次系统的始终周期，时间片的值就相应减少，当为0时CPU被时间片没有为0的进程抢占；

  1. The Scheduler Entity Structure

CFS不在有时间片的概念(我觉得主要表现在结构体没有时间片变量吧)，使用sched_entity结构体来持续记录进程运行时间(to keep track of process accounting)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct sched_entity {
    struct load_weight  load;       /* for load-balancing */
    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;
    ...
};

此结构作为一个成员变量se嵌入进程描述符中。

  1. The Virtual Runtime

vruntime保存了进程的虚拟运行时间，这是实际花费的运行时间按处于runnable状态的进程的权重计算出来的。它的作用：“CFS uses vruntime to account for how long a process has run and thus how much longer it ought to run.” 毕竟，如果拥有理想的处理器，就不需要vruntime，因为优先级相同的所有进程的虚拟运行时都是相同的。

vruntime的更新需要update_curr函数，具体可以看kernel/sched_fair.c文件下的update_curr()实现。

Process Selection

当CFS需要选择下一个运行进程时，它会挑选一个具有最小vruntime的进程。CFS使用红黑树(红黑树在本站的某篇中已经解读过)来组织可运行进程队列(the list of runnable processes)。

  1. 挑选下一个任务

就是在红黑树中查找最左节点，实现这一过程的函数是__pick_next_entity()；

红黑树最左节点缓存在rb_leftmost中，不需要__pick_next_entity函数在红黑树中搜索；

没有最左节点就代表没有节点，那么这个时候表示没有可运行的进程，CFS调度idle任务；

  1. 向树中加入进程

这一步的主要工作是将进程插入红黑树，并且缓存最左节点；

时机：在进程变为可运行状态(被唤醒)活着通过fork()调用第一次创建进程时，主要是enqueue_entity函数实现；

缓存最左节点时，采用leftmost标志位来判断插入的节点是否是最左，一旦转向右分支，则置为0，表示它不会是最左节点，如果leftmost一直为1，那么可以更新缓存；

  1. 从树中删除进程

删除动作发生在进程阻塞(不可运行态)或终止；

删除具体由__dequeue_entity()完成，它直接借用了红黑树的rb_erase()来完成所有删除工作；

更新rb_leftmost，如果删除了最左节点，还要调用rb_next()按顺序遍历；

The Scheduler Entry Point

前面提到了“the base scheduler code定义在kernel/sched.c，这个基础代码按照优先级来迭代每一个scheduler class”，进程调度的入口函数schedule()就定义在文件kernel/sched.c，
而在schedule()里发生的唯一重要的部分就是调用pick_next_task()(该函数也定义在文件kernel/sched.c中)；

一个调度类对应一个调度算法，设立涉及两个最高优先级：最高优先级调度类以及最高优先级进程；

pick_next_task()要做的事是按照优先级从高到低，依次轮询调度类，每个调度类又维护着自己的运行队列，于是又查找运行队列里优先级最高的进程；

CFS是普通进程的调度类，而系统中运行的绝大多数进程都是普通进程，所以一开始可以判断所有运行进程的数量是否等于CFS对应的可运行进程数，如果是就直接通过CFS查询最高优先级的线程并选择执行之；

有了上面的基本结论，那么pick_next_task()的代码就不难理解了，这里直接放出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * 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;
        }
}

轮询各调度类的pick_next_task()封装出总的pick_next_task()，likely(rq->nr_running == rq->cfs.nr_running)中，rq结构体存储了CPU的调度信息，每个CPU都分配了一个rq。所以rq->nr_running可以求出所有该CPU被调度运行的进程，rq->cfs.nr_running求出cfs算法的运行队列有多少可运行的线程；

Sleeping and Waking Up

这一小节的内容符合本人对睡眠唤醒的理解，所以不赘述，一图以蔽之：

睡眠唤醒

抢占和上下文切换

上下文切换时机：当一个新的进程被选出来准备投入运行，schedule()就会调用context_switch()负责处理上下文切换；

context_switch()完成两项基本工作：

  • 调用switch_mm()，切换虚拟内存映射；
  • 调用switch_to()，负责从上一个进程的处理器状态切换到新进程的处理器状态，包括保存和恢复(栈信息、寄存器信息以及其它)；

抢占时机：和schedule()的调用有关，内核需要知道什么时候调用它。need_resched是一个标志位，scheduler_tick()和try_to_wake_up()都会设置这个标志，内核检查该标志位，确认是否被设置来判断是不是要调用schedule()；

每个进程都包含一个need_resched标志，2.6版本以后，它被移到thread_info结构体里；

用户抢占

用户抢占发生在内核返回用户空间，need_resched被设置，调度器(scheduler)被调用的时候；

总的来说，用户抢占发生在如下情况：

  • 从内核返回用户空间时；
  • 从中断处理程序返回用户空间时；

在这两种情况下，都会检查need_resched标志；

内核抢占

只要重新调度是安全的，内核就可以在任何时候抢占正在执行的任务；

安全与否取决于是否持有锁，锁是非抢占区域的标志；

如何实现锁？在thread_info引入preempt_count计数器，初始为0，每当使用锁的时候数值加1，释放的时候数值减1， 进程持有的所有锁都被释放了，那么preempt_count会重新置为0，释放锁的代码会检查need_resched是否被设置；

内核抢占发生在如下情况：

  • 中断处理程序正在执行，且返回内核空间之前；
  • 内核代码再次变得可抢占式的，(When kernel code becomes preemptible again)；
  • 内核进程(task)显示调用schedule()；
  • 如果内核进程(task)被阻塞(结果就是调用schedule())；

实时调度策略

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR，而普通的非实时的调度策略是SCHED_NORMAL；

实时调度策略不受CFS调度器的管理，CFS调度在sched_fair.c中，实时调度在sched_rt.c中。

  • SCHED_FIFO：

优先级比SCHED_NORMAL高；

一旦被调度就一直执行，直到阻塞或显式释放处理器为止；

除非有更高级的进程才能抢占SCHED_FIFO进程；

多个同级SCHED_FIFO进程可以轮流执行，但只有它们原意让出处理器时才会退出；

  • SCHED_RR：

SCHED_RR可以理解为带有时间片的SCHED_FIFO；

当SCHED_RR时间片耗尽的时候，同一优先级的其它实时进程被轮流调度；

对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但是低优先级进程绝对不能抢占SCHED_RR，即使后者时间片耗尽；

软实时：内核调度进程，尽力使进程在它的限定时间到来前运行，但不保证满足；相反，硬实时保证在一定条件下，可以满足任何调度的要求；

补充

很多资料会出现SCHED_OTHER调度策略，实际上它就是SCHED_NORMAL，对于普通进程有这三种：

  • SCHED_NORMAL：CFS对应的策略；
  • SCHED_BATCH：与SCHED_NORMAL策略一样，但针对吞吐量优化；
  • SCHED_IDLE：优先级最低，系统空闲才跑；

小结

通过此篇笔记，本人对Linux进程调度有了大致的理解，了解了其内部的运作机制。

参考

《Linux内核设计与实现(第三版)》

《Linux Kernel Development, 3rd Edition》

陈向群《操作系统原理》公开课