Process

Linux进程

进程状态

进程创建

进程创建可以通过3个函数

  • fork：拷贝当前进程，创建出一个子进程。
  • vfork：类似fork，但不复制父进程的页表项。但由于copy on write技术的出现，这个函数的相对于fork的优势越来越小。
  • clone：最基本的函数，根据各种标志位指定父子进程需要共享的资源，比如虚拟内存。共享虚拟内存的话就是常说的线程。

实际上，fork和vfork的实现都是调用的clone，并指定特定的标志指定父子进程需要共享的资源。

clone函数的核心是do_fork函数，该函数执行流程如下。

其中，copy_process函数为进程创建一个内核栈、thread_info结构和task_struct结构，根据传递给clone的参数，拷贝对应的资源。CamScanner 02-08-2023 15.22_2

创建新程序

问题来了，这三个函数只能拷贝父进程，运行的代码都是一样的，那怎么创建别的程序呢？

execve()函数可以读取其他可执行文件，并加载到内存运行。此外，还有execve()的封装函数execlp(), execle(),execv(),execvp()，exec()。我们称为exec函数族。

那么创建新进程的就只需要调用fork/vfork/clone之后再调用exec函数即可。

Shell上调用其他命令就是这样实现的。

  • 首先使用fork创建出一个子进程，然后子进程调用exec执行其他进程。
  • 如果有重定向号>则在exec前关闭标准输出，打开新文件的描述符。

Copy On Write

Copy On Write顾名思义仅在写的时候才会复制出一个副本，也是属于懒加载的技术。

fork之后再exec的频率是很高的，复制的页表项相当于白白复制了，所以之前vfork就比fork要高效。

但出现了copy on write技术后，页表项仅仅在需要修改时才会复制，vfork就和fork一样了，基本上很少用了。

Linux的线程

Linux下的进程和线程没有本质区别，都是由task_struct描述，由clone产生，本质只是是否共享内存。通过下面这句即可创建线程。

clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0)

进程结束

根据创建进程的过程不难发现，新进程都会有一个父进程。子进程需要结束时，首先做一些能做的操作，但自己总不能回收自己吧，就留下一些资源等待父进程调用wait回收。

Linux的第一个进程就是init进程，其他进程都是其后代，在一定情况下负责后代的回收。

一般来说，进程结束发生在调用exit()时候，既可能是程序手动调用，也可能是隐形式地被添加这个调用。（C语言编译器在main()的返回点后面放置调用exit()的代码）。也能是接受到无法处理且无法忽略的信号，被动终止。

不管怎么终结，都会调用do_exit()。之后，它占有的内存就只有内核栈，thread_info和task_struct了。

然后父进程调用wait()，就完成了子进程的回收。

过程

  • 子进程终止，调用do_exit().
  • 父进程调用wait()，挂起自己，并等待自己的一个子进程的状态改变。

可能出现的问题

孤儿进程

孤儿（orphan）进程是指父进程先退出但自己还未退出的子进程

如果父进程先退出，未wait子进程，子进程do_exit()会查找新的父进程。如果现场组内没有其他进程，则该回收任务交由init进程执行，其pid为1。init进程例行调用wait()检查子进程。

僵尸进程

僵尸（zombie）进程是已经退出但未经过wait的子进程。

unix提供了一种机制可以保证只要父进程想知道子进程结束时的状态信息。

这种机制就是: 在do_exit释放大部分资源后，仍然为其保留一定的信息(内核栈，thread_info和task_struct)。直到父进程通过wait / waitpid来取时才释放。 但这样就导致了问题，如果进程不调用wait / waitpid的话， 那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程. 此即为僵尸进程的危害，应当避免。

可以通过以下方式解决

  • kill父进程，使子进程成为孤儿进程。
  • 父进程重写信号处理函数，接收到信号就wait子进程。
  • fork两次，中间的进程直接退出。孙子进程成为孤儿进程。

进程调度

核心概念

调度实体

为了简化调度器模型，内核单独抽象出了一个概念叫“调度实体”，用来封装调度对象， struct task_struct 与调度实体相关的字段包括：

/* file: include/linux/sched.h */
struct task_struct {
    /* 调度实体，调度器的调度对象，该字段用于 CFS */
    struct sched_entity se;
    /* 该字段用于 RT 调度器 */
    struct sched_rt_entity rt;
#ifdef CONFIG_CGROUP_SCHED
    struct task_group *sched_task_group;
#endif
    /* 该字段用于 DL 调度器 */
    struct sched_dl_entity dl;
}

三个表示调度实体的字段 se, rt, dl 分别用于不同的调度策略。

调度类

Linux 在 2.6 版本中引入了“调度类（Sched Class）”的概念，意在将调度逻辑模块化，内核通过 struct sched_class 抽象出了调度类的通用行为。这个结构体基本都是函数声明，这对于有 OO 编程经验的同学而言是很熟悉的： struct sched_class 实际上定义了一个接口（Interface），而各个调度类来负责具体的实现。

Linux 总共实现了5种调度类，按照优先级有高到底排序依次为：

  1. stop_sched_class Stop 是特殊的调度类，内核使用该调度类来停止 CPU. 该调度类用来强行停止CPU 上的其他任务，由于该调度类的优先级最高，因此一旦生效就将抢占任何当前正在运行的任务，并且在运行过程中自己不会被抢占。

    该调度类只有在SMP架构的系统中存在，内核使用该调度类来完成负载均衡与CPU热插拔等工作。

  2. dl_sched_class 有些任务必须在指定时间窗口内完成。例如视频的编码与解码，CPU 必须以特定频率完成对应的数据处理；

    这类任务是优先级最高的用户任务，CPU 应该首先满足。

    Deadline 调度类用来调度这类任务，dl 便是单词 Deadline 的缩写，因此该调度类的优先级仅仅低于 Stop 调度类。

  3. rt_sched_class 实时任务（Real-time Task）对响应时间要求更高，例如编辑器软件，它可能由于等待用户输入长期处于睡眠之中，但一旦用户有输入动作，我们就期望编辑器能够立马响应，而不是等系统完成其它任务之后才开始反应，这一点对用户体验十分重要。

    RT 调度类用来调度这类任务，该调度类的优先级低于 DL.

  4. fair_sched_class Fair 调度类用来调度绝大多数用户任务，CFS 实现的就是这种调度类，其核心逻辑是根据任务的优先级公平地分配 CPU 时间。我们会在后续章节中详细讨论 CFS 的实现细节。

  5. idle_sched_class 与 Stop 类似，Idle 调度类也是仅供内核使用的特殊调度类，其优先级最低，只有在没有任何用户任务时才会用到。内核会为每个 CPU 绑定一个内核线程（kthread）来完成该任务，该线程会在队列无事可做的情况下启动该任务，并将 CPU 的功耗降到最低。

我们说调度类有优先级，具体怎么体现呢？

每一个CPU的rq在选择下一个进程来运行，要调用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;

    for_each_class(class) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
    }

    /* The idle class should always have a runnable task: */
    BUG();
}

从上述代码不难发现，对调度类的遍历通过宏 for_each_class 完成。而该宏展开的之后，各调度类的顺序就是我们上述提到的优先级。每一个调度类都实现了pick_next_task，用于选择下一个调度的进程。先便利高优先级的调度类，如果有进程可调度，则直接返回。

在相同优先级调度类中可能管理多个进程的调度，因此调度类有会对应的调度策略。

调度策略

  1. Stop 调度类 Stop 调度类中只有一个任务可供执行，不需要定义任何调度策略。
  2. DL （Deadline）调度类 DL 只实现了一种调度策略：SCHED_DEADLINE, 用来调度优先级最高的用户任务。
  3. RT （Real-Time） RT 提供了两种调度策略：SCHED_FIFO 与 SCHED_RR,对于使用 SCHED_FIFO 的任务，其会一直运行到主动放弃CPU; 而对于 SCHED_RR 的任务，如果多个任务的优先级相同，则大家会按照一定的时间配额来交替运行，即使一个任务一直处于可运行状态，在使用完自己的时间切片之后也会被抢占，然后被放入队列的尾巴等待下次机会。
  4. Fair CFS 实现了三种调度策略：
    • SCHED_NORMAL: 被用于绝大多数用户进程
    • SCHED_BATCH: 适用于没有用户交互行为的后台进程，用户对该类进程的响应时间要求不高，但对吞吐量要求较高，因此调度器会在完成所有 SCHED_NORMAL 的任务之后让该类任务不受打扰地跑上一段时间，这样能够最大限度地利用缓存。
    • SCHED_IDLE: 这类调度策略被用于系统中优先级最低的任务，只有在没有任何其他任务可运行时，调度器才会将运行该类任务。
  5. Idle 同 Stop 一样，Idle 调度类也没有实现调度策略，注意不要将这类调度类与 CFS 中的 SCHED_IDLE 混淆。

每个进程在创建时都会指定一个调度策略，从而自动归结到某个调度类下。

调度策略的定义如下：

#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6

可以通过 /proc/<pid>/sched 中的内容来查看进程的调度策略，例如

epoch@Ubuntu:~ $ cat /proc/130/sched | grep policy
policy                                       :                    0

运行队列

运行队列（run queue）rq 是系统可运行任务的容器，调度器的很多工作都是围绕着 rq 来进行的，调度类 struct sched_class 所申明的函数中，绝大多数函数都与 rq 相关。在系统中，每个 CPU 都有一个自己的 rq, 这样可以避免多个 CPU 访问同一个 rq 时产生的并发问题，提升调度器效率。

/* file: kernel/sched/sched.h */
struct rq {
    unsigned int nr_running;

    u64 nr_switches;

    /*
     * runqueue 采用的模块化的实现方式，各个不同的 Scheduling Class 都有自己的
     runqueue 实现。不同的 runqueue 的数据结构保存在如下属性之中
    */
    struct cfs_rq cfs; /* CFS runqueue 的实现 */
    struct rt_rq rt;   /* RT runqueue 的实现 */
    struct dl_rq dl;   /* Deadline runqueue 的实现 */

    struct task_struct __rcu *curr; /* 当前 runqueue 中正在运行的进程 */
    struct task_struct *idle;       /* Idle 调度类的任务 */
    struct task_struct *stop;       /* Stop 调度类的任务 */
    struct mm_struct *prev_mm;

    atomic_t nr_iowait;

#ifdef CONFIG_SMP
    struct root_domain *rd;
    struct sched_domain __rcu *sd;

    unsigned long cpu_capacity;
    unsigned long cpu_capacity_orig;
#endif /* CONFIG_SMP */

#ifdef CONFIG_SCHEDSTATS
    /* latency stats */
    struct sched_info rq_sched_info;
    unsigned long long rq_cpu_time;
    /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */

    /* sys_sched_yield() stats */
    unsigned int yld_count;

    /* schedule() stats */
    unsigned int sched_count;
    unsigned int sched_goidle;
#endif
};

此处删除了该结构体的大多数字段，仅仅保留了一些主要的字段一探究竟，这些字段涉及如下几个方面：

  1. 具体调度类的运行队列。不同的调度类选择下一个任务的逻辑是不同的，因此不同的调度类会有不同的调度队列实现方式，例如字段 struct cfs_rq cfs 就是 CFS 的调度队列

  2. 当前正在运行的进程，以及 stop 与 idle 这种特殊任务

  3. 如果是 SMP 架构，则 rq 中还会包含调度域的字段，调度器使用调度域中的信息来做负载均衡

  4. 一些统计信息

进程优先级

每一个调度类都实现了pick_next_task，用于选择下一个调度的进程。而该函数选择的依据，跟进程的优先级密不可分。

在Linux下，用户能通过系统调用设置优先级，分别是nice与sched_setscheduler，其中nice仅仅设置优先级，而sched_setscheduler还能改普通进程为实时进程。

站在用户的角度，用户只能接触到一类优先级，取值为[-20, 19]。

而站在内核的角度，能看到三种优先级，都在task_struct中。

/* file: include/linux/sched.h */
struct task_struct {
    int prio; //动态优先级
    int static_prio; //静态优先级
    int normal_prio; //将三种优先级归一化，否则无法比较优先级。
    unsigned int rt_priority; // 实时优先级
	....
}

  • static_prio: 静态优先级。当用户通过 nice 与 sched_setscheduler 两个系统调用修改优先级时，改变的就是该字段。前文提到 nice 值的范围是[-20, 19], 而实时优先级的有效范围是[1, 99], 二者的重叠部分如何处理呢？内核在处理 nice 时会加上120, 完成 nice 值与静态优先级之间的转换。新进程创建时该值从父进程继承，静态优先级在进程执行过程中是不会改变的，而当其值发生改变的时候，其他相关优先级也需要重新计算（例如动态优先级）。

  • rt_priority：实时优先级。可通过系统调用chrt修改，有效范围是 [1, 99], 数字越大优先级越高，用于实时调度，所以当数值是0时表示该进程是普通进程。

  • prio: 动态优先级。为了调优IO密集和计算密集进程，动态优先级是在静态优先级动态调整而来，可调整的范围是+-5，可通过函数 effective_prio() 得到，具体实现如下。在$O(1)$调度器使用，CFS替代了$O(1)$调度器，在CFS中并为使用。

    static int effective_prio(struct task_struct *p) {
    p->normal_prio = normal_prio(p);
    /* 判断是否为实时优先级：如果 p.prio 的值小于 100(MAX_RT_PRIO的值), 则返回 1, 否则返回 0*/
    if (!rt_prio(p->prio))
        return p->normal_prio;
    return p->prio;
}

  • normal_prio: 归一化优先级。 我们使用了不同的方式来刻画同一个概念，那么势必会带来管理上的麻烦，所谓归一化，就是设计一种转换方式，将这些不同的方法统一到同一种方法上去，从而简化问题的模型。内核设计了一种归一化算法，将所有的优先级统一到 [-1, 139] 这个区间上，并且数字越小优先级越大，该优先级就叫做归一化优先级。转换算法如下

    static inline int __normal_prio(struct task_struct *p) {
    return p->static_prio;
}

static inline int normal_prio(struct task_struct *p) {
    int prio;

    if (task_has_dl_policy(p))
        /* MAX_DL_PRIO为0, 因此Deadline的优先级永远为-1 */
        prio = MAX_DL_PRIO - 1;
    else if (task_has_rt_policy(p))
        /* MAX_RT_PRIO为100, 而rt_priority的范围是[1,99]且数字越大对应的优先级越高，下面的算法实现了优先级反转，高优先级将对应小的数字。
         */
        prio = MAX_RT_PRIO - 1 - p->rt_priority;
    else
        /* 对于普通进程，直接返回静态优先级static_prio */
        prio = __normal_prio(p);
    return prio;
}

CFS

为什么引入有CFS？

传统的处理是将nice值映射到时间片，比如[ -20 … 0 … 19 ]的普通进程其缺省时间片为[800ms … 100ms … 5ms]。

传统基于优先级和时间片的算法有几点问题

  • 问题1：nice值映射到处理器绝对时间，进程切换无法最优化进行。
  • 问题2：即使相对nice值相同，运行时间差距也可能很大。
  • 问题3：由于是映射到时间片，所以时间片是定时器周期的整数倍。
  • 问题4：为了交互进程，可能需要临时提高交互进程优先级，打破了公平规则。

分别举例说明一下1、2、3。

问题1

问题1：nice值映射到处理器绝对时间，公平性难以把握。

假设现在存在两个活跃进程，nice值分别为0和19，时间片分别是100ms和5ms。即105ms一个周期，进行两次上下文切换。

但如果是两个nice值为19的进程，时间片就是5ms和5ms，10ms内进行两次上下文切换。

通常来说，我们希望后台进程优先级低，交互进程优先级高，后台能够获得更长的运行时间，交互进程能够尽快响应用户操作。

这样分配的话，会导致交互进程分配较长的时间片，交互进程大部分时间在阻塞，后台进程时间片短，后台进程也无法充分运行。

问题2

问题2：即使相对nice值相同，运行时间差距也可能很大。

假设现在存在两个活跃进程，nice值分别为0和1，时间片分别是100ms和95ms。差距不大。

但对于nice值为18和19的进程，时间片为10ms和5ms。前者是后者两倍运行时间。

问题3

由于nice值到时间片的绝对映射，所以时间片一定是定时器周期的整数倍。

假设定时器周期为1ms，则时间片差距至少为1ms。

思路

公平性

CFS，completely fair scheduler，即完全公平调度器。顾名思义，公平是CFS的核心。

理想情况下，公平就是CPU的时间均分给每一个进程，如果时间为T，共N个进程在运行，那么每一个进程的时间就是$\frac{T}{N}$。但现实是，系统无法知道T的具体值，而N也总是动态变化。前的调度逻辑都是基于时间片，绝对的公平几乎不可能实现。

CFS不再使用时间片，它的核心逻辑是以进程当前的实际运行时间为度量单位，记为runtime, 调度器每次调度时都选择runtime最小的进程。

优先级与权重

实际上，进程之间存在着优先级的差异，上面提到的runtime的完全公平是不符合实际需求的。所以引入优先级的概念，这个优先级就是我们常说的nice值。优先级越高，获得运行时间的比例也就应该越高，也就是这个进程的权重越高。

为了实现优先级的需求，但又保留公平性处理逻辑的简洁。CFS的做法是，调度仍然是选择运行时间最小的那个进程，不过这个时间是虚拟时间。在物理时间相同的情况下，进程的权重越高，它的虚拟时间流逝的就越快。

这样，调度就只需要选择虚拟时间vruntime最小的进程进行调度。进程运行时，将真实时间经过权重的放缩之后计算到虚拟时间。

公平性、优先级与权重

我们从公平角度来说，希望每一个进程都在CPU上运行相同的时间，但考虑到不同进程是有优先级的，比如说一个编辑器进程，我们希望他能够立刻响应，而一个跑深度学习的进程，我们倒是希望能够在后台运行，没有快速响应，慢几分钟几秒钟到是无所谓。这两种进程同时运行时，我们希望让编辑器进程优先响应，即编辑器进程优先级更高。

CFS的公平性本质上是对CPU时间的公平分配，而优先级的加入并没有改变这一点，优先级本质上是为了区分不同进程的重要性，只要调度器能够根据每个进程的重要性的比例来分配时间，那么它就依然是公平的。例如我们有三个进程 A, B, C, 其中B与C的重要性相等，而A的重要性是他们的两倍，那么在公平的分配策略下，三个进程得到的CPU时间比例应该是：

  • A: 50%
  • B: 25%
  • C: 25%

假设系统已经运行了100ms, 三个任务均分了该时间片：

  • A: 33.3ms, 实际比例1/3, 期望比例为1/2, 差值为：1/6
  • B: 33.3ms, 实际比例1/3, 期望比例为1/4, 差值为：1/12
  • C: 33.3ms, 实际比例1/3, 期望比例为1/4, 差值为：1/12

此时A的比例差值最大，说明A所分配到的时间比例偏少，调度器应该选择A作为下一个任务来执行。整个过程略显复杂，需要每个任务都记录下自己的时间比例与权重比例，而CPU还需要计算出每一个进程的差值，选取插值最大的，有没有一种方式，让CPU看来，每一个进程运行的时间都相同，这样满足公平性且编码逻辑更加简洁，而进程运行的实际时间却具有权重之分？有， 那就是虚拟时间vruntime。

因此，逻辑就清晰了。CPU保证每个进程运行的逻辑时间相等，以保证公平性；将虚拟时间与物理时间按照权重进行一定的换算，以保证优先级的机制。

虚拟时间vruntime

计算运行的虚拟时间

权重和优先级有一定映射关系，公式如下
$$
weight = \frac{1024}{1.25^{nice}}
$$

nice是之前提到的用户能够设置的静态优先级，当nice=0时，任务权重weight为1024，而1024作为权重的一个基准，内核中用宏NICE_0_LOAD表示，其他所有的权重都是在该基准上伸缩得来。

因此，计算虚拟时间vruntime就很简单了，公式如下
$$
vruntime = \frac{wall_time * NICE_0_LOAD}{weight}
$$
其中wall_time代表物理时间（墙上时间，钟一般是挂在墙上的嘛）。

为了避免浮点运算，程序先进行放大后再缩小，代码为vruntime = (wall_time * ((NICE_0_LOAD * 2^32) / weight)) >> 32。而其中$\frac{2^{32}}{weight}$被称为inv_weight，由于频繁使用，因此以打表缓存的形式存在。
$$
inv_weight = \frac{2^{32}}{weight}
$$

const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

具体实现的计算函数是__calc_delta(delta, NICE_0_LOAD, &se->load)。delta即墙上时间，&se->load即权重。

接下来我们再来看一下系统如何更新任务的vruntime以及其他的时间信息的，完成该任务的是函数 update_curr():

/* file: kernel/sched/fair.c */
static void update_curr(struct cfs_rq *cfs_rq) {
	struct sched_entity *curr = cfs_rq->curr;
    /* 获取当前时间 */
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;

    if (unlikely(!curr))
    return;

    /* 本次更新vruntime与上次更新vruntime之间的时间差，即任务本次的运行时间，该值为墙上时间
    */
    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))
    return;

    /* 记录这次更新的时间 */
    curr->exec_start = now;

    /* 更新总的运行时间 */
    curr->sum_exec_runtime += delta_exec;

    /* 更新vruntime, 通过函数calc_delta_fair计算出墙上时间delta_exec对应的虚拟时间
    */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    /* 更新队列的 min_vruntime */
    update_min_vruntime(cfs_rq);

    /* 下面的逻辑可以暂时不管 */
    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);

        trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
        cgroup_account_cputime(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }

    account_cfs_rq_runtime(cfs_rq, delta_exec);
}

任务的vruntime就靠函数 update_curr 来维护，系统在很多情况下都会调用该方法，包括任务在入队、出队时，调度中断函数也会周期性地调用该方法，以确保任务的各种时间信息随时都是最新的状态。

调整睡眠的进程和新进程的vruntime

除了为运行的任务计算vruntime之外，调度器还需要调整新创建的任务及久睡方醒的任务的vruntime, 否则他们的vruntime将远远落后于一直在执行的任务，从而导致长久的霸占CPU. 该任务通过函数 place_entity 完成

该函数总是为目标任务加上一定的vruntime, 因此事实上是一个“惩罚函数”。

/* file: kernel/sched/fair.c */
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                    int initial) {
    /* 以队列的min_vruntime为基础进行调整 */
    u64 vruntime = cfs_rq->min_vruntime;

    /* 对新创建的进程（initial=1）适当的惩罚，为其加上一定的 vruntime,
    * 函数sched_vslice将任务在一个调度周期内应当分配到的墙上时间换算成虚拟时间，调度周期会在下一节介绍
    */
    if (initial && sched_feat(START_DEBIT))
    	vruntime += sched_vslice(cfs_rq, se);

    if (!initial) {
    /* 如果进程睡眠了很久，那么其 vruntime 可能远远小于队列中其他任务的vruntime,
        * 我们也需要对其vruntime
        * 进行惩罚，但进程被唤醒（initial=0）说明它所等待的事件已经得到了满足，需要马上干活，所以这里减去一定的vruntime作为补偿。*/
    	unsigned long thresh = sysctl_sched_latency;

        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;

        vruntime -= thresh;
    }

    /* 确保不要因为 vruntime -=thresh 导致 se.vruntime 的值越来越小了 */
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}
如何选择下一个进程

通过前文对于公平性的讨论，我们知道对于CFS所管理的任务而言，vruntime相等就是公平的，CFS的工作职责就是维持所有任务的vruntime尽可能相等。总结起来，CFS的工作原理如下：CFS为每个任务维护一个虚拟时间vruntime, 每次调度时都从runqueue中挑选vruntime最小的任务来执行，并将任务执行时所耗费的墙上时间根据任务的权重换算成虚拟时间累计起来；随着时间的消耗，当当前任务的vruntime数值不再是runqueue中最小的时，调度器将其放回runqueue, 重新选择下一个任务。

调度周期

从CFS的调度原理来考虑的话，CFS似乎不需要调度周期的概念，因为CFS并不是预先给任务分配时间片，而是根据大家当前的运行时间来判断谁应该是下一个该执行的任务，这样所有任务都随着时间的推进齐头并进。但为了用来调度延迟，CFS也需要引入调度周期。

什么是调度延迟呢？CFS不仅需要保证时间分配的公平，还要保证各个任务每隔一段时间就能够执行一次，一个任务在两次被调度到的时间间隔就是调度延迟。相反，调度器还需要保证任务在每次得到机会执行时，除了任务主动放弃CPU, 尽量不要太快地被踢出来，因为太频繁的上下文切换会导致系统的总体性能降低。所以 CFS 没有使用固定的时间长度作为调度周期，而是根据当前队列中的任务数量动态计算出调度周期的长度，该逻辑由函数 __sched_period 实现

/* file: kernel/sched/fair.c */
/* 参数 nr_running 表示当前 cfs_rq 中的任务总数 */
static u64 __sched_period(unsigned long nr_running) {
    /* sched_nr_latency: 8 */
    if (unlikely(nr_running > sched_nr_latency))
    	/* sysctl_sched_min_granularity: 0.75ms */
    	return nr_running * sysctl_sched_min_granularity;
    else
    	/* sysctl_sched_latency: 6ms*/
    	return sysctl_sched_latency;
}

当队列中所有的任务超过8个时，CFS的调度周期为任务总数乘以0.75ms，否则调度周期为固定的6ms, 这样可以保证任务的切换频率比较合理。

算出调度周期之后，系统还需要为任务计算其在一个调度周期内的时间配额，函数 sched_slice 用来实现该逻辑：

/* file: kernel/sched/fair.c */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    unsigned int nr_running = cfs_rq->nr_running;
    u64 slice;

    /* 调度周期 */
    slice = __sched_period(nr_running + !se->on_rq);

    /* 暂时不考虑组调度，此处的循环只会执行一次 */
    for_each_sched_entity(se) {
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        /* 整个运行队列 cfs_rq 的总权重 */
        load = &cfs_rq->load;

        /* se->load.weight为se的权重，调用函数__calc_delta得到slice*se->load.weight/load.weight,
            * 即根据 se 在整个队列中的权重比例分配时间 */
        slice = __calc_delta(slice, se->load.weight, load);
    }

    if (sched_feat(BASE_SLICE))
    	slice = max(slice, (u64)sysctl_sched_min_granularity);

    return slice;
}

当任务在当前调度周期内的耗时超过自己的配额时，调度器就会将其踢出去，换其他任务来执行，这个值的检查的频率是由调度节拍决定的。调度节拍中将会详细讨论该逻辑。

调度节拍

计算机系统随着时钟节拍需要周期性地做很多事情，例如刷新屏幕、数据落盘等，而进程调度是众多任务中最重要的之一。周期性调度也叫调度节拍，它的入口是函数 scheduler_tick(), 该函数最终会调用调度类的 task_tick() 方法完成操作：

/* file: kernel/sched/core.c */
void scheduler_tick(void) {
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;

    /* 调用当前任务的调度类的 task_tick 方法 */
    curr->sched_class->task_tick(rq, curr, 0);

    #ifdef CONFIG_SMP
    /* SMP 架构下触发负载均衡 */
    rq->idle_balance = idle_cpu(cpu);
    trigger_load_balance(rq);
    #endif
}

CFS 中实现 task_tick 方法的是函数 task_tick_fair:

/* file: kernel/sched/fair.c */
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) {
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    /* 在不考虑组调度的情况下，此处的循环只会迭代一次，处理的就是当前任务 */
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);
    }
}

实际的逻辑都在函数 entity_tick 中，删除无关代码及与组调度相关的逻辑，主要逻辑如下：

/* file: kernel/sched/fair.c */
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) {
    /* 首先更新当前任务及队列的各种时间信息，详见 vruntime 一节 */
    update_curr(cfs_rq);
    if (cfs_rq->nr_running > 1)
        /* 检查是否需要抢占当前任务 */
    	check_preempt_tick(cfs_rq, curr);	
}

该函数的主要任务有两个，一个是更新任务的各种时间信息；另一个是检查当前任务是否已经执行地足够久了，如果是的话就需要对其进行抢占，换其它任务来执行。关于抢占的概念将在下一节中介绍。

进程抢占

所谓抢占，就是停止当前正在执行的任务，换另一个任务来执行。导致这种情况发生的原因很多，例如当前任务已经运行了太长时间，需要让出CPU; 用户修改了任务优先级，导致当前任务应该被换下；或者优先级更高的任务被唤醒，需要立刻开始运行。但当这种情况发生时，调度器并不会真的立刻切换任务，而是调用 resched_curr() 函数为当前任务设置一个叫着 TIF_NEED_RESCHED 的标记位，该函数的主要逻辑如下

/* file: kernel/sched/core.c */
void resched_curr(struct rq *rq) {
    struct task_struct *curr = rq->curr;
    int cpu;

    lockdep_assert_held(&rq->lock);

    /* 如果当前任务已经设置了 TIF_NEED_RESCHED 标记位，则返回 */
    if (test_tsk_need_resched(curr))
    return;

    cpu = cpu_of(rq);

    if (cpu == smp_processor_id()) {
        /* 设置标记位 */
        set_tsk_need_resched(curr);
        set_preempt_need_resched();
        return;
	}
}

TIF_NEED_RESCHED 位被设置之后，调度器在下一次调度发生时就会进行真正的调度，将任务换下，进行上下文切换，运行新任务。具体的调度入口和调度时机在后文讨论。

调用resched_curr()的地方非常多，这里主要介绍两个典型场景：

  1. 调度节拍中检测到任务运行时间耗尽
  2. 任务状态切换为可运行时，判断是否可以调用，例如创建新进程、任务苏醒。
运行时间耗尽

前面提到每个调度周期内都有一定的时间配额，当任务耗尽了该时间片之后就需要让出CPU, 以便给其它任务提供运行的机会。在调度节拍一节中，提到 entity_tick 最后调用了check_preempt_tick，后者就是检查时间是否耗尽的函数，实现如下。

/* file: kernel/sched/fair.c */
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) {
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;

    /* 计算出当前任务在一个调度周期内的时间配额 */
    ideal_runtime = sched_slice(cfs_rq, curr);
    /* 计算出当前任务已经运行了多长时间 */
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    if (delta_exec > ideal_runtime) {
        /* 如果运行时长已经超过了任务自己的时间配额，则对任务进行抢占 */
        resched_curr(rq_of(cfs_rq));
        return;
    }

    /* 避免任务抢占发生得太过频繁 */
    if (delta_exec < sysctl_sched_min_granularity)
    	return;

    /* 从cfs_fq中挑出vruntime最小的任务，即红黑树中最左子节点；并计算出当前任务与该任务的vruntime的差值
    */
    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;

    /* 如果当前任务的vruntime依然小于红黑树中所有任务的vruntime, 则不发生抢占 */
    if (delta < 0)
    	return;

    /* 如果已经多除了相当部分，则可以抢占当前任务了 */
    if (delta > ideal_runtime)
    	resched_curr(rq_of(cfs_rq));
}

可以看到最后一行，情况符合的话，就会调用resched_curr。

创建新任务

新任务创建后可能需要立即运行，就可能会调用到resched_curr函数。创建完毕后，在wake_up_new_task检查是否需要调用resched_curr。

调度入口

调度入口就是真正执行调度的地方，由schedule()执行，保留核心代码，实现如下

/* file: kernel/sched/core.c */
asmlinkage __visible void __sched schedule(void) {
    struct task_struct *tsk = current;

    do {
        preempt_disable();
        /* 调用函数 __schedule 来做具体的工作 */
        __schedule(false);
        sched_preempt_enable_no_resched();
        /* need_resched用来判断当前任务是否应该被抢占，此时的当前任务就是函数__schedule最新选择的任务，如果是的话那么继续调用函数__schedule以便调用下一个合适的任务。*/
    } while (need_resched());
}

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

    /* 获取到当前CPU序号，进而获取到其runqueue */
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    /* rq->curr 是当前正在执行的任务 */
    prev = rq->curr;

    prev_state = prev->state;
    if (!preempt && prev_state) {
        if (signal_pending_state(prev_state, prev)) {
            prev->state = TASK_RUNNING;
        } else {
            /* preempt 如果为false,
                则说明此次调度不是由于任务抢占导致的，那么导致调度发生的原因就是任务主动要求让出CPU,
                对于由于IO事件进入睡眠的任务而言，需要先将其从运行队列中踢出去。该函数最终会调用调度类（sched_class）的
                dequeue_task 方法完成具体工作。*/
            deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
        }
    }

    /* 从队列中选择下一个任务，该函数最终会调用调度类（sched_class的函数pick_next_task方法。对于CFS而言，就是选择vruntime最小的任务
    */
    next = pick_next_task(rq, prev, &rf);
    /* 清除 prev 任务的TIF_NEED_RESCHED标记，因为此时它已经被抢占了 */
    clear_tsk_need_resched(prev);

    if (likely(prev != next)) {
        /* 完成上下文切换，CPU将开始执行刚刚挑出来的任务next了 */
        rq = context_switch(rq, prev, next, &rf);
    }
}

其中next = pick_next_task(rq, prev, &rf);就是前文提到的全局的pick_next_task，根据优先级遍历所有的调度类。

函数 schedule() 最后调用 context_switch() 完成上下文切换，至此，整个调度工作就完成了！

接下来讨论调度的时机，即什么时候调用schedule()。

调度时机

用户抢占

在以下情况会检查TIF_NEED_RESCHED标志位，

  • 从系统调用返回用户空间时
  • 从中断处理程序返回用户空间时

检查到了则会调用schedule，进行任务调度。

内核抢占

在以下情况可能发生内核抢占，检测到TIF_NEED_RESCHED标志位，或者显式调用

  • 中断处理程序正在执行，且返回内核空间之前
  • 内核代码再一次具有可抢占性的时候
  • 内核代码显示调用schedule()
  • 内核中的任务阻塞（同样导致调用schedule）

前面提到，周期性调度会按照调度节拍检查当前任务是否超时，而该周期性调度程序是由中断实现的，返回时即会检查TIF_NEED_RESCHED标志位。

重新调度

所谓抢占，就是停止当前正在执行的任务，换另一个任务来执行。导致这种情况发生的原因很多，例如当前任务已经运行了太长时间，需要让出CPU; 用户修改了任务优先级，导致当前任务应该被换下；或者优先级更高的任务被唤醒，需要立刻开始运行。但当这种情况发生时，调度器并不会真的立刻切换任务，而是调用 resched_curr() 函数为当前任务设置一个叫着 TIF_NEED_RESCHED 的标记位，等下一个调度节拍来执行实际的调度。

上下文切换

调度函数 schedule() 最后调用 context_switch() 完成上下文切换，context_switch()完成两项基本的工作

  • 进程地址空间切换：声明在<sam/mmu_context.h>中的switch_mm：切换大部分虚拟内存。由于虚拟内存与MMU有关，具体的工作细节取决于处理器，主要包括
    • 加载页表：即修改页表基址寄存器成新的task_struct->mm_struct->pgd。
    • 刷新TLB（有些体系会优化这个步骤，用到才刷新）
    • 向MMU提供信息…
  • 处理器状态切换：声明在<asm/system.h>中的swtich_to：保存、恢复内核栈信息（用户栈在上一步已经被切换）和PC、SP等寄存器信息，还有其他任何于体系结构相关的信息。

由于与具体体系关系紧密，因此上下文切换代码通常使用汇编语言编写。

内核的mm_struct指向NULL。

进程组、组调度

为什么要有进程组的概念呢？考虑如下情况，一个系统有100个进程，CFS会保证每个进程都获得1%的CPU时间，但实际上系统中的这100个进程可能隶属于两个用户A与B, 其中用户A拥有10个进程，用户B拥有90个进程，这种实现造成的结果是用户A只获得了10%的CPU时间，而用户B获得了90%的时间。如果用户B了解CFS的调度原理，那么他可以肆无忌惮地fork出更多的进程以攫取更多的CPU时间。可见CFS在进程层面上的公平，却导致了系统在用户层面上的不公平，甚至是漏洞。对于这种情况，一种更合理的策略是系统首先保证每个用户获得相同的时间，然后再对隶属于同一个用户的所有进程公平地分配该用户的时间。

将该概念进一步抽象，我们就得到了进程组的概念。进程组的引入实际上是增加了一个调度层级，调度器首先完成进程组的时间分配，再处理组内进程之间的时间分配，前文提到的用户分组只是进程组的一个特例。

负载均衡

一个CPU有很多核心嘛，为了效率肯定需要做负载均衡的，每一个核心都需要做负载记账，当核心之间的负载不均衡时，需要进行任务迁徙，这个过程就是负载均衡。当然负载均衡需要考虑很多问题，比如这个CPU是什么架构是SMP还是NUMA，不同核心处理能力不同，迁移时vruntime又怎么处理等等。

抽象层面

Linux为了更方便地扩展，抽象出了很多概念。举几个例子

调度类：每一个调度类都需要实现调度的通用函数，即对调度相关的函数声明进行实现。这其实就是一种面向对象的思想。

调度实体：进程就是一种调度实体，线程也是。在Linux下的进程和线程都是task_struct表示，区别只是是否共享虚拟地址空间。这其实是一种抽象，而Linux的task_struct就是一种可调度的实体）。

调度组：进程组的引入实际上是增加了一个调度层级，调度器首先完成进程组的时间分配，再处理组内进程之间的时间分配，前文提到的用户分组只是进程组的一个特例。

参考资料

TODO

  • 调度域
  • 调度实体
  • 负载记账
  • 负载均衡
Linux
Process
https://messenger1th.github.io/2024/07/24/Linux/Process/
作者
Epoch
发布于
2024年7月24日
许可协议