1. 前言

本文主要基于 Linux Kernel 2.6.26 的源代码，分析该 Linux 内核版本的进程模型及其调度器 (Completely Fair Scheduler) 的算法。

Linux Kernel 2.6.26 源代码下载地址：

2. 什么是进程

既然是要分析操作系统的进程模型及其调度算法，那么首先肯定得清楚到底什么是进程。

上对于进程的解释如下：

In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.

进程是正在执行的计算机程序的一个实例，它包含了程序的代码及其当前的活动。根据操作系统的不同，一个进程可能由多个并行执行的指令执行线程组成。

百闻不如一见，在 Windows 系统中只要打开任务管理器即可看到当前正在运行的进程的一些基本信息：

在 Linux 系统中可以用 ps 指令来查看当前正在运行的进程的一些基本信息：

以上便是我们在使用操作系统中对于进程最直接的认识了。那么接下来就一起深入到 Linux Kernel 2.6.26 源代码中，去看看进程是怎么被定义以及调度的。

3. 进程的组织

Linux 内核通过 task_struct 结构体来描述进程，它包含了一个进程的所有信息。

该结构体被定义在 include/linux/sched.h 文件中，下文将分析该结构体中的几个关键成员。

3.1. 进程标识符 (PID)

3.1.1. PID 的数据类型

进程标识符是用来唯一地标识一个进程的一个数值，可以将进程标识符类似地理解为现实生活中我们每个人的身份证号。进程标识符可以看成就是进程的身份证号，用来唯一地标识每一个进程。

PID 在 task_struct 中的定义为：

pid_t pid;

其中 pid_t 是一个由 typedef 定义的数据类型，它被定义于 include/linux/types.h 文件中：

typedef __kernel_pid_t      pid_t;

继续寻找 __kernel_pid_t 的定义，发现它在 include/asm-x86/posix_types_32.h 等多个文件中均有如下的定义：

typedef int     __kernel_pid_t;

可以发现，pid_t 实际上就是 int 类型。

至于为什么要用 typedef 定义而不直接使用 int ，猜想应该是为了将 Linux 内核移植到不同的平台时便于修改。

因为不同的平台上可能对于 PID 的数据类型有不同的要求，例如有的平台上可能需要使用 short 或者是 long 等来作为 pid_t 的数据类型，这时就只要为该平台单独写一个 .h 头文件，用 typedef 定义 pid_t 的数据类型即可。

3.1.2. PID 的取值范围

在 include/linux/threads.h 中定义了 PID 的最大值：

#define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)

可以看出，当 CONFIG_BASE_SMALL 的值等于 0 时，PID_MAX_DEFAULT 的值为 0x8000，即十进制下的 32768。

PID 的取值范围即：0 ~ 32767 (PID_MAX_DEFAULT - 1)

说明系统中的进程数最大为 32768 个，这对于大多数的桌面操作系统已经足够了，基本上不会出现同时运行这么多进程的情况。

然而，在一些服务器的操作系统中，可能需要同时运行大量的进程，这时候 Linux 也提供了相应的兼容性支持，在 64 位操作系统中，可以通过向 /proc/sys/kernel/pid_max 文件中直接写入需要的最大 PID 值来提高系统同时运行的进程数，最大能将 PID 最大值修改为 \(2^{22}\) ，大约是400,0000。

3.2. 进程状态

3.2.1. 进程状态的分析

进程状态在 task_struct 中的定义为：

volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */

state 成员的可能取值如下：(定义于 include/linux/sched.h 文件中)

#define TASK_RUNNING        0#define TASK_INTERRUPTIBLE  1#define TASK_UNINTERRUPTIBLE    2#define __TASK_STOPPED      4#define __TASK_TRACED       8/* in tsk->exit_state */#define EXIT_ZOMBIE     16#define EXIT_DEAD       32/* in tsk->state again */#define TASK_DEAD       64#define TASK_WAKEKILL       128

系统当前正在运行的每个进程的状态必定是以上所列举的进程状态中的一种。

下面就以上所列举的进程状态逐个分析：

• TASK_RUNNING

  位于这个状态下的进程是可运行的。

  即该进程当前要么就是正在运行，要么就是处于运行队列中，正在等待运行。

• TASK_INTERRUPTIBLE

  该状态表示进程被阻塞，处于睡眠状态。

  当进程等待的某些条件被满足了之后，内核会将该进程的状态设置为 TASK_RUNNING。

  同时，如果进程接收到某个信号，也能被立即唤醒，并进入可运行的状态。

• TASK_UNINTERRUPTIBLE

  该状态与 TASK_INTERRUPTIBLE 状态类似，也表示进程被阻塞，处于睡眠状态。

  当进程等待的某些条件被满足了之后，内核也会将该进程的状态设置为 TASK_RUNNING。

  但是，处于这个状态下的进程不能在接收到某个信号之后立即被唤醒。这时该状态与 TASK_INTERRUPTIBLE 状态唯一的区别。

• __TASK_STOPPED

  该状态表示进程被停止执行。

  当进程接收到 SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU 等信号时将进入该状态。

• __TASK_TRACED

  该状态表示当前进程正在被另一个进程所监视。

  例如当某进程被 debugger 等程序所调试时，该进程就处于 __TASK_TRACED 状态。

• EXIT_ZOMBIE

  该状态表示进程的执行被终止，但是它的父进程还没有使用 wait() 等系统调用来获知它的终止信息。

  当进程处于该状态的时候几乎不占用任何系统资源，仅仅只是在进程的列表中保留了一个位置。正如它的名字所描述的那样，就像是进程列表中的 zombie (僵尸)。

• EXIT_DEAD

  该状态是一个进程的最终状态，该状态的持续时间相当短暂，因为在这个状态下的进程接下来立即会被释放。

• TASK_DEAD

  该状态与进程状态的变迁有关。

• TASK_WAKEKILL

  该状态与进程状态的变迁有关。

3.2.2. 进程状态的转换

这里引用一张来自于《Linux Kernel Development 3rd Edition》书中的进程状态转换流程图来说明进程状态之间是如何转换的：

3.3. 进程调度实体 (sched_entity)

task_struct 中定义了进程调度器在执行调度操作时实际操作的对象 sched_entity ，即进程调度实体。

下文在描述 CFS 调度器的时候将涉及到进程调度实体。

至于为什么不在调度的时候直接操作 task_struct 而是操作进程调度实体 sched_entity ，应该是为了避免调度器频繁地操作 task_struct ，从而降低调度器设计的复杂度。

那么接下来就来看看进程调度实体 sched_entity 是怎么定义的：

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;   //进程所使用的 CPU 总时间    u64         vruntime;   //虚拟运行时间    u64         prev_sum_exec_runtime;    u64         last_wakeup;    u64         avg_overlap;#ifdef CONFIG_SCHEDSTATS    u64         wait_start;    u64         wait_max;    u64         wait_count;    u64         wait_sum;    u64         sleep_start;    u64         sleep_max;    s64         sum_sleep_runtime;    u64         block_start;    u64         block_max;    u64         exec_max;    u64         slice_max;    u64         nr_migrations;    u64         nr_migrations_cold;    u64         nr_failed_migrations_affine;    u64         nr_failed_migrations_running;    u64         nr_failed_migrations_hot;    u64         nr_forced_migrations;    u64         nr_forced2_migrations;    u64         nr_wakeups;    u64         nr_wakeups_sync;    u64         nr_wakeups_migrate;    u64         nr_wakeups_local;    u64         nr_wakeups_remote;    u64         nr_wakeups_affine;    u64         nr_wakeups_affine_attempts;    u64         nr_wakeups_passive;    u64         nr_wakeups_idle;#endif#ifdef CONFIG_FAIR_GROUP_SCHED    struct sched_entity *parent;    /* rq on which this entity is (to be) queued: */    struct cfs_rq       *cfs_rq;    /* rq "owned" by this entity/group: */    struct cfs_rq       *my_q;#endif};

可以看到在 sched_entity 中定义了进程调度时所需的各项参数，包括 CFS 调度器最重要的虚拟运行时间 vruntime 也被定义于进程调度实体之中。

4. 进程的调度

4.1. CFS 调度器简介

CFS 调度器全程为 Completely Fair Scheduler，翻译成中文即完全公平调度器。它是从 Linux Kernel 2.6.23 之后开始采用的进程调度器。

CFS 调度器试图通过软件的方式去模拟出一个理想的，精确的，多任务的 CPU (ideal, precise, multitasking CPU)。

那么什么是理想的，精确的，多任务的 CPU 呢？

其实就是一个可以同时运行并执行多个进程的 CPU，并且它给每隔进程分配等量的处理器功率（不是时间）。

例如，当只有一个进程运行的时候，它将会拥有处理器 100% 的功率。

当有两个进程同时运行的时候，每个进程都将会拥有处理器 50% 的功率。

当有四个进程同时运行的时候，每个进程将拥有处理器 25% 的功率。

按照这种规则，平均分配每个进程所获得的处理器功率，如下图所示：

显然，要模拟出这样理想的 CPU 是不可能的。因为在实际的系统运行过程中，可能出现的情况是相当复杂的。

所以 CFS 调度器只能试图去尽量地减少系统进程调度中不公平情况的产生。

CFS 调度器的基本原理是这样的：

1. 设定一个调度周期 (sched_latency_ns)，目的是让每个进程在这个周期内至少有机会运行一次；
2. 然后根据进程的数量，各个进程平均分配这个调度周期内的 CPU 使用权。这时由于各个进程的优先级 (即 nice 值不同)，分割调度周期的时候需要加权分配；
3. 每个进程的累计运行时间保存在自己的 vruntime 字段内，哪个进程的 vruntime 最小就能获得运行的权利。

综合来看，CFS 调度器的核心思想其实就是：根据各个进程的权重合理地分配运行时间。当分配给某个进程的时间失去平衡的时候，应该给失去平衡的进程分配时间，让其运行。

那么具体 CFS 调度器是如何实现进程调度的呢？接下来我们深入 Linux 内核源代码探究一下。

4.2. 深入了解 CFS 调度器

4.2.1. 虚拟运行时间 vruntime

CFS 调度器已经不再使用时间片了，CFS 调度器通过 vruntime (即进程的虚拟运行时间) 来衡量哪个进程是最值得被调度的。

CFS 调度器的就绪队列其实就是一棵以 vruntime 为键值的红黑树， vruntime 越小的进程就越靠近整棵红黑树的最左端。因此，调度器只需要每次都选择位于红黑树最左端的那个进程即可，因为该进程的 vruntime 最小，即该进程最值得运行。

接下来我们就深入到代码中，看看 vruntime 这个参数是如何被计算出来的。

首先，计时器每隔一个周期就会产生一个 tick 中断，在中断产生之后会调用 scheduler_tick() 函数来处理中断，该函数被定义于 kernel/sched.c 中：

void scheduler_tick(void){    int cpu = smp_processor_id();    struct rq *rq = cpu_rq(cpu);    struct task_struct *curr = rq->curr;    sched_clock_tick();    spin_lock(&rq->lock);    update_rq_clock(rq);    //更新运行队列维护的时钟    update_cpu_load(rq);    //更新运行队列维护的 CPU 负载    curr->sched_class->task_tick(rq, curr, 0);  //触发调度器，Look at this line    spin_unlock(&rq->lock);#ifdef CONFIG_SMP    rq->idle_at_tick = idle_cpu(cpu);    trigger_load_balance(rq, cpu);#endif}

代码中的 task_tick() 函数是用来完成周期性调度工作的，所以这里我们重点分析该函数。

在 CFS 调度器中它对应于 kernel/sched_fair.c 文件中的 task_tick_fair() 函数：

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);    //Look at this line    }}

可以看到，该函数循环对当前所有的 sched_entity 调度实体都执行了 entity_tick() 函数。

那么接下来就继续查看 entity_tick() 函数的源代码，看看这个函数对调度实体做了些什么操作。

static voidentity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued){    /*     * Update run-time statistics of the 'current'.     */    update_curr(cfs_rq);    //更新当前运行队列的运行时间统计值，其实主要就是更新各个进程的 vruntime 值，Look at this line#ifdef CONFIG_SCHED_HRTICK    /*     * queued ticks are scheduled to match the slice, so don't bother     * validating it and just reschedule.     */    if (queued) {        resched_task(rq_of(cfs_rq)->curr);        return;    }    /*     * don't let the period tick interfere with the hrtick preemption     */    if (!sched_feat(DOUBLE_TICK) &&            hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))        return;#endif    if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))        check_preempt_tick(cfs_rq, curr);}

可以看到，entity_tick() 主要是调用了 update_curr() 函数来更新当前运行队列的运行时间统计值，其实主要就是更新各个进程的 vruntime 值。

所以继续分析 update_curr() 函数：

static void update_curr(struct cfs_rq *cfs_rq){    struct sched_entity *curr = cfs_rq->curr;    u64 now = rq_of(cfs_rq)->clock;    unsigned long delta_exec;    if (unlikely(!curr))        return;    /*     * Get the amount of time the current task was running     * since the last time we changed load (this cannot     * overflow on 32 bits):     */    delta_exec = (unsigned long)(now - curr->exec_start);   //获取了最后一次更新负载之后当前进程所使用的 CPU 总时间    __update_curr(cfs_rq, curr, delta_exec);    //调用__update_curr()来更新 vruntime    curr->exec_start = now;    if (entity_is_task(curr)) {        struct task_struct *curtask = task_of(curr);        cpuacct_charge(curtask, delta_exec);    }}

在 update_curr() 函数中，首先获取了最后一次更新负载之后当前进程所使用的 CPU 总时间（即 delta_exec ），并将其转递给 __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;   //当前进程的执行时间加上delta_exec，即sum_exec_runtime = sum_exec_runtime + delta_exec    schedstat_add(cfs_rq, exec_clock, delta_exec);    delta_exec_weighted = delta_exec;    if (unlikely(curr->load.weight != NICE_0_LOAD)) {        delta_exec_weighted = calc_delta_fair(delta_exec_weighted,                            &curr->load);   //计算 vruntime    }    curr->vruntime += delta_exec_weighted;  //vruntime = vruntime + delta_exec_weighted}

分析代码之后可以发现，真正计算 vruntime 的其实就是 calc_delta_fair() 函数：

static inline unsigned longcalc_delta_fair(unsigned long delta_exec, struct load_weight *lw){    return calc_delta_mine(delta_exec, NICE_0_LOAD, lw);}

之后发现 calc_delta_fair() 函数其实又调用了 calc_delta_mine() 函数：

static unsigned longcalc_delta_mine(unsigned long delta_exec, unsigned long weight,        struct load_weight *lw){    u64 tmp;    if (!lw->inv_weight) {        if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))            lw->inv_weight = 1;        else            lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2)                / (lw->weight+1);    }    tmp = (u64)delta_exec * weight;    /*     * Check whether we'd overflow the 64-bit multiplication:     */    if (unlikely(tmp > WMULT_CONST))        tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,            WMULT_SHIFT/2);    else        tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);    return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);}

到这里，综合前文的代码可以整理分析出，一个调度周期的 \(vruntime = \frac{delta\_exec * NICE\_0\_LOAD}{Weight}\)

4.2.2. 下一个调度进程的选择

前文所述的 scheduler_tick() 函数只对进程的虚拟运行时间 vruntime 进行了更新并重新进行了排序，供调度器来使用。那么，真正的调度算法是在哪里实现的呢？

其实，主调度器被定义在 kernel/sched.c 文件中，由 schedule() 函数实现。该函数源代码如下所示：

asmlinkage void __sched schedule(void){    struct task_struct *prev, *next;    unsigned long *switch_count;    struct rq *rq;    int cpu;    /* 为节省篇幅，部分代码未列出 */    if (unlikely(!rq->nr_running))        idle_balance(cpu, rq);    prev->sched_class->put_prev_task(rq, prev);    next = pick_next_task(rq, prev);    //挑选下一个要被运行的进程    if (likely(prev != next)) {        sched_info_switch(prev, next);        rq->nr_switches++;        rq->curr = next;        ++*switch_count;        context_switch(rq, prev, next); /* unlocks the rq */        /*         * the context switch might have flipped the stack from under         * us, hence refresh the local variables.         */        cpu = smp_processor_id();        rq = cpu_rq(cpu);    } else        spin_unlock_irq(&rq->lock);    /* 为节省篇幅，部分代码未列出 */}

可以看到，其实挑选下一个要被调度执行的进程是由 pick_next_task() 函数，在 pick_next_task() 函数中将会进一步调用调度类的pick_next_task，而在 CFS 调度器中就是由 pick_next_task_fair() 函数来实现了，该函数源代码如下：

static struct task_struct *pick_next_task_fair(struct rq *rq){    struct task_struct *p;    struct cfs_rq *cfs_rq = &rq->cfs;    struct sched_entity *se;    if (unlikely(!cfs_rq->nr_running))        return NULL;    do {        se = pick_next_entity(cfs_rq);  //选择下一个进程调度实体        cfs_rq = group_cfs_rq(se);    } while (cfs_rq);    p = task_of(se);    hrtick_start_fair(rq, p);    return p;}

这里是调用了 pick_next_entity() 函数来选择下一个进程调度的实体，那么进一步分析可知，pick_next_entity() 其实是调用了 __pick_next_entity() 函数：

static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq){    return cfs_rq->rb_leftmost; //返回红黑树最左端子节点}static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq){    return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);}

可以看出，其实就是挑选了红黑树最左端的子节点作为下一个调度执行的进程，即挑选当前 vruntime 最小的进程作为下一个调度执行的进程。

接下来只要做好进程的上下文 (Context) 切换即可实现进程的切换，具体有关进程的上下文是如何切换的不在本文的讨论范围之内。

4.3. 有关 CFS 调度器的几个问题

4.3.1. 新进程的初始 vruntime 值是多少

?新进程的初始 vruntime 值？可能你的第一反应会觉得它是 0。

但是转念一想，如果新进程的初始 vruntime 值被设置成 0 了之后，那么在相当长的一段时间内，新进程都将拥有使用 CPU 的权利，因为它的 vruntime 比其他老进程小很多。这样的话其他的老进程就会进入"饥饿"状态，这显然是不合理的，如果是这样的话也就做不到 CFS 调度器所追求的尽量公平了。

所以其实 CFS 调度器是这样给新进程分配 vruntime 初始值的：每个运行队列中都由一个 min_vruntime 字段，记录着该运行队列中的所有进程的 vruntime 的最小值。新进程的初始 vruntime 值就以它所在的运行队列的 min_vruntime 为基础来设置，确保与老进程保持一个合理的差距范围。

这样就能既让新进程得到一定的执行时间，又不会导致老进程进入"饥饿"状态。

4.3.2. 休眠的进程 vruntime 是一直保持不变的吗

这个问题其实跟上一个问题是类似的。

如果休眠状态下进程的 vruntime 是一直保持不变的话，那么在该进程休眠的时候，其他进程一直在运行，其他进程的 vruntime 就会比休眠状态下的进程大很多。

这时候，如果休眠状态下的进程被唤醒了之后，它的 vruntime 会比其他一直在运行的进程小很多。进而就会出现跟上一个问题一样的情况，刚被唤醒的进程将在很长的一段时间之内，拥有 CPU 的使用权利，导致其他进程出现"饥饿"的情况。

所以 CFS 调度器会在休眠的进程被唤醒的时候重新设置其 vruntime 的值，以 min_vruntime 的值为基础，减去调度周期的一半作为其 vruntime 值。

4.3.3. 红黑树？

红黑树 (Red–black tree) 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构。

在 CFS 调度器中将 sched_entity 存储在以时间为顺序的红黑树中，vruntime 最低的进程存储在树的左侧，vruntime 最高的进程存储在树的右侧。 为了公平，调度器每次都会选取红黑树最左端的节点调度以便保持公平性。这样，整颗红黑树最左侧的进程就被给予时间运行了，树的内容从右侧迁移到左侧以保持公平。

同时，红黑树的时间复杂度为 O(log n)，可以快速高效地执行插入或是删除操作。

一棵红黑树的示意图如下所示：

5. 对操作系统进程模型的看法

进程是操作系统的重要组成部分，我们在日常使用各种操作系统进行着各项工作的时候都离不开进程。虽然我们在使用计算机的时候可能并不容易察觉到进程的存在以及操作系统在这背后对进程的优化以及调度做了多大的努力。

但是深入操作系统内核之后可以看到，其实看起清楚地看到操作系统对于进程的优化以及调度算法所付出的巨大努力，光光与调度有关的代码行数可能都已经上千行了。所有的努力都是为了能让当前系统所有的进程更高效地运行，能更好地完成人们交给计算机的任务。归结起来，就是尽量地追求效率与公平。

然而，要同时照顾到效率与公平显然是不太可能的。更何况当前操作系统被设计的越来越复杂，所要经历的应用场景越来越多，从计算机到现在越来越多的移动设备再到未来更多的物联网设备。

在我看来，操作系统对于进程的调度算法整体而言并不存在最优的解。但是可以做到对于每个应用场景尽量地实现最优化。

PS，前文提到的 PID 最大值，在运行着 Linux 4.15.13-1-ARCH 内核的 Archlinux 系统中已经被提高到了 49152，看来对于同时运行的进程数有了越来越高的要求：(上边的窗口为 Linux 2.6.32 内核的 CentOS 6，下边的窗口为 Linux 4.15.13 内核的 Archlinux)

6. 参考资料

6. Robert Love,《Linux Kernel Development》,3rd edition