Linux内核设计与实现(三)一一进程调度

发表于 | 阅读次数

多任务

  • 抢占式多任务

  • 非抢占式多任务

进程状态

我们可以用 ps 命令来看计算机运行的进程状态

偷懒用的macOS。。懒得开虚拟机了因为属性显示的差不多的

…
算了到时候补图吧，发现还是有很多不同的地方的

  • F：表示进程旗标，标识进程所拥有的权限，当我切换到root的时候为4表示拥有root权限，为1仅有fork()权限

  • R：表示进程当前的状态

    R：当前正在运行(RUNNING)
    S：睡眠(SLEEP)
    D：不可中断
    T：停止(STOP)
    Z：僵尸进程(ZOMBIE)

  • UID：拥有该进程用户的用户ID

  • PID：进程号

  • PPID：该进程父进程的进程好

  • C：CPU是用百分比

  • PRI：优先级

  • NI：nice值

  • ADDR/SZ/WCHAN：都与内存有关

  • TTY：登陆者的终端，和远程登陆脱不开干系

  • TIME：占用CPU时间

  • CMD：造成此进程的命令

Linux的进程调度

I/O消耗型进程

进程的大部分时间用来提交I/O请求或者是等待I/O请求

处理器消耗型进程

把时间大多用在执行代码上

进程优先级

NICE值

-20 ~ +19，默认为0

越大的NICE值意味着更低的优先级。

实时优先级

0 ~ 99

越高的实时优先级意味着进程优先级越高

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。

CFS调度算法

前面我们提到Linux是一个抢占式的系统，并且CFS分配的不是时间片，而是由NICE值决定的CPU使用比。

值得注意的是，反而CPU使用比低的新进程会立刻投入运行，CPU使用比高的新进程会延迟运行。这是为什么呢?

正如它的名字一样，因为它是追求完全公平的，CFS的出发点基于一个非常简单的概念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中每个进程将能获得1/n的处理器时间

就是说每个进程真正使用cpu的时间是一样的，包括I/O消耗型和处理器消耗型，以达到真正的公平，这就解释了刚才的问题，CPU使用比低的占用时间会不可避免的少于占用比高的进程，那我们只好让这个进程具有抢占能力，一就绪就可以抢占，这样子“看起来CPU使用比高了”（其实没变）“看起来CPU占用时间也和其他进程一样多了”（其实不多）

进程调度的时机

  • 进程状态转换时刻：进程终止、进程睡眠；

  • 当前进程的”时间片”用完；

  • 主动让出处理器，用户调用sleep()或者内核调用schedule()；

  • 从中断，系统调用或异常返回时

CFS调度算法实现

首先我们要明白我们为什么需要这个算法，这个算法是用来解决什么问题的。

我们在进程调度中遇到的要解决四个问题：


时间记账

所有的调度器都必须对进程运行时间做记账

调度器实体结构

每个进程task_struct中都有一个struct sched_entity se成员，这就是调度器的实体结构，进程调度算法实际上就是管理所有进程的这个se

linux/sched.h 的 struct_sched_entity 中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
truct task_struct {
    volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
    void *stack;
    atomic_t usage;
    unsigned int flags;    /* per process flags, defined below */
    unsigned int ptrace;
    int lock_depth;        /* BKL lock depth */
#ifdef CONFIG_SMP
#ifdef __ARCH_WANT_UNLOCKED_CTXSW
    int oncpu;
#endif
#endif
    int prio, static_prio, normal_prio;
    unsigned int rt_priority;
    const struct sched_class *sched_class;
    struct sched_entity se; //进程调度实体
    struct sched_rt_entity rt;
    …
}
虚拟实时
vruntime

vruntime 变量存放进程的虚拟运行时间，这个时间是通过优先级和系统负载等加权过的时间，而非物理时钟时间。所以这个时间与时间片即节拍器无关。

每个进程的调度实体se都保存着本进程的虚拟运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
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;
…
}

而进程相关的调度方法如下：

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
31
32
33
static const struct sched_class fair_sched_class = {
    .next            = &idle_sched_class,
    .enqueue_task        = enqueue_task_fair,
    .dequeue_task        = dequeue_task_fair,
    .yield_task        = yield_task_fair,
    .check_preempt_curr    = check_preempt_wakeup,
    .pick_next_task        = pick_next_task_fair,
    .put_prev_task        = put_prev_task_fair,
#ifdef CONFIG_SMP
    .select_task_rq        = select_task_rq_fair,
    .rq_online        = rq_online_fair,
    .rq_offline        = rq_offline_fair,
    .task_waking        = task_waking_fair,
#endif
    .set_curr_task = set_curr_task_fair,
    .task_tick        = task_tick_fair,
    .task_fork        = task_fork_fair,
    .prio_changed        = prio_changed_fair,
    .switched_to        = switched_to_fair,
    .get_rr_interval    = get_rr_interval_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
    .task_move_group    = task_move_group_fair,
#endif
};
vruntime更新

时钟中断产生时，会依次调用tick_periodic()-> update_process_times()->scheduler_tick()来更新vruntime

1
2
3
4
5
6
7
8
9
10
void scheduler_tick(void)
{
…
    raw_spin_lock(&rq->lock);
    update_rq_clock(rq);
    update_cpu_load(rq);
    curr->sched_class->task_tick(rq, curr, 0); //执行调度器tick，更新进程vruntime
    raw_spin_unlock(&rq->lock);
…
}

task_tick_fair ()调用entity_tick()如下：

1
2
3
4
5
6
7
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    update_curr(cfs_rq);
…
    if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
        check_preempt_tick(cfs_rq, curr); //检查当前进程是否需要调度
}

这里分析两个重要函数update_curr()和check_preempt_tick()

update_curr():

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
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;
// delta_exec获得最后一次修改后，当前进程所运行的实际时间
    delta_exec = (unsigned long)(now - curr->exec_start);
    if (!delta_exec)
        return;
    __update_curr(cfs_rq, curr, delta_exec);
    curr->exec_start = now; //运行时间已保存，更新起始执行时间
    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);
        trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
        cpuacct_charge(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }
}

主要关心__update_curr()函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
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);//对delta_exec加权
    curr->vruntime += delta_exec_weighted;//累计入vruntime
    update_min_vruntime(cfs_rq); //更新cfs_rq最小vruntime(保存所有进程中的最小vruntime)
}

然后看calc_delta_fair()加权函数如何实现：

1
2
3
4
5
6
7
8
9
10
11
/*
 * delta /= w
 */
static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
    return delta;
}

若当前进程nice为0，直接返回实际运行时间，其他所有nice值的加权都是以0nice值为参考增加或减少的。

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
/*
 * delta *= weight / lw
 */
static unsigned long
calc_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);
}

当nice!=0时，实际是按公式delta *= weight / lw来计算的weight=1024是nice0的权重，lw是当前进程的权重，该lw和nice值的换算后面介绍，上面函数的lw计算公式没弄明白，总之这个函数就是把实际运行时间加权为进程调度里的虚拟运行时间，从而更新vruntime。

vruntime更新

更新完vruntime之后，会检查是否需要进程调度

继续看 entity_tick()

1
2
3
4
5
6
7
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    update_curr(cfs_rq);
…
    if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
        check_preempt_tick(cfs_rq, curr); //检查当前进程是否需要调度
}

更新完cfs_rq之后，会检查当前进程是否已经用完自己的“时间片”

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
31
32
33
34
35
36
37
38
39
/*
 * Preempt the current task with a newly woken task if needed:
 */
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    ideal_runtime = sched_slice(cfs_rq, curr);//ideal_runtime是理论上的处理器运行时间片    
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;//该进程本轮调度累计运行时间
    if (delta_exec > ideal_runtime) {// 假如实际运行超过调度器分配的时间，就标记调度标志
        resched_task(rq_of(cfs_rq)->curr);
        /*
         * The current task ran long enough, ensure it doesn't get
         * re-elected due to buddy favours.
         */
        clear_buddies(cfs_rq, curr);
        return;
    }
    /*
     * Ensure that a task that missed wakeup preemption by a
     * narrow margin doesn't have to wait for a full slice.
     * This also mitigates buddy induced latencies under load.
     */
    if (!sched_feat(WAKEUP_PREEMPT))
        return;
    if (delta_exec < sysctl_sched_min_granularity)
        return;
    if (cfs_rq->nr_running > 1) {
        struct sched_entity *se = __pick_next_entity(cfs_rq);
        s64 delta = curr->vruntime - se->vruntime;
        if (delta > ideal_runtime)
            resched_task(rq_of(cfs_rq)->curr);
    }
}

当该进程运行时间超过实际分配的“时间片”，就标记调度标志resched_task(rq_of(cfs_rq)->curr);，否则本进程继续执行。中断退出，调度函数schedule()会检查此标记，以选取新的进程来抢占当前进程。

进程选择

挑选下一个任务

首先总结一下就是：

1.挑选下一个任务 pick_next_entity() 树中最左侧的叶子节点
2.向树中加入进程 enqueue_entity()
3.向树中删除进程 dequeue_entity()

CFS选择具有最小vruntime值的进程作为下一个可执行进程，CFS用红黑树来组织调度实体，而键值就是vruntime。那么CFS只要查找选择最左叶子节点作为下一个可执行进程即可。实际上CFS缓存了最左叶子，可以直接选取left_most叶子。

上面代码跟踪到timer tick中断退出，若“ideal_runtime”已经用完，就会调用schedule()函数选中新进程并且完成切换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
asmlinkage void __sched schedule(void)
{
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        if (unlikely(signal_pending_state(prev->state, prev)))
            prev->state = TASK_RUNNING;
        else
            deactivate_task(rq, prev, 1);//如果状态已经不可运行，将其移除运行队列
        switch_count = &prev->nvcsw;
    }
    pre_schedule(rq, prev);
    if (unlikely(!rq->nr_running))
        idle_balance(cpu, rq);
    put_prev_task(rq, prev); //处理上一个进程
    next = pick_next_task(rq);//选出下一个进程
…
    context_switch(rq, prev, next); /* unlocks the rq *///完成进程切换
…
}

如果进程状态已经不是可运行，那么会将该进程移出可运行队列，如果继续可运行

put_prev_task()会依次调用put_prev_task_fair()->put_prev_entity()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    /*
     * If still on the runqueue then deactivate_task()
     * was not called and update_curr() has to be done:
     */
    if (prev->on_rq)
        update_curr(cfs_rq);
    check_spread(cfs_rq, prev);
    if (prev->on_rq) {
        update_stats_wait_start(cfs_rq, prev);
        /* Put 'current' back into the tree. */
        __enqueue_entity(cfs_rq, prev);
    }
    cfs_rq->curr = NULL;
}

__enqueue_entity(cfs_rq, prev) 将上一个进程重新插入红黑树(注意，当前运行进程是不在红黑树中的)

pick_next_task()会依次调用pick_next_task_fair()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 (!cfs_rq->nr_running)
        return NULL;
    do {
        se = pick_next_entity(cfs_rq);//选出下一个可执行进程
        set_next_entity(cfs_rq, se); //把选中的进程(left_most叶子)从红黑树移除，更新红黑树
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);
    p = task_of(se);
    hrtick_start_fair(rq, p);
    return p;
}

set_next_entity()函数会调用__dequeue_entity(cfs_rq, se)把选中的下一个进程即最左叶子移出红黑树。

最后context_switch()完成进程的切换。

更新rbtree的时机

  • 上一个进程执行完ideal_time，还可继续执行时，会插入红黑树

  • 下一个进程被选中移出rbtree红黑树时

  • 新建进程

  • 进程由睡眠态被激活，变为可运行态时

  • 调整优先级时也会更新rbtree

向树中加入进程

新建进程会做一系列复杂的工作，这里我们只关心与红黑树有关部分

Linux使用fork，clone或者vfork等系统调用创建进程，最终都会到do_fork函数实现，如果没有设 CLONE_STOPPED，do_fork会执行两个与红黑树相关的函数: copy_process()和wake_up_new_task()，也是我们在上一篇进程创建里面有学习到的。

①.copy_process()->sched_fork()->task_fork()
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
31
32
33
34
35
36
37
38
39
40
41
42
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;//以cfs的最小vruntime为基准
    /*
     * The 'current' period is already promised to the current tasks,
     * however the extra weight of the new task will slow them down a
     * little, place the new task so that it fits in the slot that
     * stays open at the end.
     */
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);// 加上一个调度周期内的"时间片"
    /* sleeps up to a single latency don't count. */
    if (!initial && sched_feat(FAIR_SLEEPERS)) {
        unsigned long thresh = sysctl_sched_latency;
        /*
         * Convert the sleeper threshold into virtual time.
         * SCHED_IDLE is a special sub-class. We care about
         * fairness only relative to other SCHED_IDLE tasks,
         * all of which have the same weight.
         */
        if (sched_feat(NORMALIZED_SLEEPER) && (!entity_is_task(se) ||
                 task_of(se)->policy != SCHED_IDLE))
            thresh = calc_delta_fair(thresh, se);
        /*
         * Halve their sleep time's effect, to allow
         * for a gentler effect of sleepers:
         */
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;
        vruntime -= thresh;
    }
    /* ensure we never gain time by being placed backwards. */
    vruntime = max_vruntime(se->vruntime, vruntime);
    se->vruntime = vruntime;
}
②. 调用wake_up_new_task函数
1
2
3
4
5
6
7
8
9
void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
…
    rq = task_rq_lock(p, &flags);
    update_rq_clock(rq);
    activate_task(rq, p, 0);//激活当前进程，添加入红黑树
check_preempt_curr(rq, p, WF_FORK);//确认是否需要抢占
    …
}

更新时钟，激活新建的进程activate_task()会调用

1
2
3
4
5
6
7
8
9
static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup, bool head)
{
    if (wakeup)
        p->se.start_runtime = p->se.sum_exec_runtime;
    sched_info_queued(p);
    p->sched_class->enqueue_task(rq, p, wakeup, head);
    p->se.on_rq = 1;
}

将新建的进程加入rbtree

从树中删除一个进程

和加入进程类似，调用函数不同

调度器入口

schedule()–调用–> pick_next_task()[实际上是调用pick_next_entity()也就是调用__pick_next_entity()] 从最高优先级的调度中，选择高优先级进程

改变进程优先级，如何调整rbtree

Linux中改变进程优先级会调用底层的set_user_nice()

1
2
3
4
5
6
7
8
9
10
void set_user_nice(struct task_struct *p, long nice)
{
…
    dequeue_task(rq, p, 0); //把进程从红黑树中取出
…
    p->static_prio = NICE_TO_PRIO(nice);//将nice(-20~19)值映射到100~139,0~99是实时进程优先级
    set_load_weight(p);
…
    enqueue_task(rq, p, 0, false);
}

set_user_nice把进程从红黑树取出，调整优先级(nice值对应权重)，再重新加入红黑树.

set_load_weight()函数是设置nice值对应的权重，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void set_load_weight(struct task_struct *p)
{
    if (task_has_rt_policy(p)) {
        p->se.load.weight = 0;
        p->se.load.inv_weight = WMULT_CONST;
        return;
    }
    /*
     * SCHED_IDLE tasks get minimal weight:
     */
    if (p->policy == SCHED_IDLE) {
        p->se.load.weight = WEIGHT_IDLEPRIO;
        p->se.load.inv_weight = WMULT_IDLEPRIO;
        return;
    }
    p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
    p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

数组prio_to_weight[]是将nice值(-20~19)转化为以nici 0(1024)值为基准的加权值,根据内核注释每一个nice差值，权重相差10%，即在负载一定的条件下，每增加或减少一个nice值，获得的CPU时间相应增加或减少10%

1
2
3
4
5
6
7
8
9
10
static const int prio_to_weight[40] = {
 /* -20 */ 88761, 71755, 56483, 46273, 36291,
 /* -15 */ 29154, 23254, 18705, 14949, 11916,
 /* -10 */ 9548, 7620, 6100, 4904, 3906,
 /* -5 */ 3121, 2501, 1991, 1586, 1277,
 /* 0 */ 1024, 820, 655, 526, 423,
 /* 5 */ 335, 272, 215, 172, 137,
 /* 10 */ 110, 87, 70, 56, 45,
 /* 15 */ 36, 29, 23, 18, 15,
};

calc_delta_mine()函数用到这个数组加权值，这个转化过程 大概是为了防止相乘之后越界,再一个就是用移位来近似代替除法，暂时不太明白

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
 *
 * In cases where the weight does not change often, we can use the
 * precalculated inverse to speed up arithmetics by turning divisions
 * into multiplications:
 */
static const u32 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,
};

睡眠和唤醒

睡眠

睡眠的常见原因是因为文件I/O

唤醒进程

调用try_to_wake_up()->activate_task()->enqueue_task_fair()->enqueue_entity()

注意enqueue_entity 函数调用place_entity对进程vruntime做补偿计算，再次考察place_entity(cfs_rq, se, 0)

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
31
32
33
34
35
36
37
38
39
40
41
42
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;//以cfs的最小vruntime为基准
    /*
     * The 'current' period is already promised to the current tasks,
     * however the extra weight of the new task will slow them down a
     * little, place the new task so that it fits in the slot that
     * stays open at the end.
     */
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);//一个调度周期内的"时间片"
    /* sleeps up to a single latency don't count. */
    if (!initial && sched_feat(FAIR_SLEEPERS)) {
        unsigned long thresh = sysctl_sched_latency;
        /*
         * Convert the sleeper threshold into virtual time.
         * SCHED_IDLE is a special sub-class. We care about
         * fairness only relative to other SCHED_IDLE tasks,
         * all of which have the same weight.
         */
        if (sched_feat(NORMALIZED_SLEEPER) && (!entity_is_task(se) ||
                 task_of(se)->policy != SCHED_IDLE))
            thresh = calc_delta_fair(thresh, se);
        /*
         * Halve their sleep time's effect, to allow
         * for a gentler effect of sleepers:
         */
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;
        vruntime -= thresh;//对于睡眠进程唤醒，给予vruntime补偿
    }
    /* ensure we never gain time by being placed backwards. */
    vruntime = max_vruntime(se->vruntime, vruntime);//避免通过睡眠来获得运行时间
    se->vruntime = vruntime;
}

当initial=1时，新建进程vruntime=cfs最小vruntime值+时间片，放入红黑树最右端。

当initial=0时，表示唤醒进程，vruntime要减去一个thresh.这个thresh由调度周期sysctl_sched_latency加权得到虚拟时间，这样做可以对睡眠进程做一个补偿，唤醒时会得到一个较小的vruntime, 使它可以尽快抢占CPU(可以快速响应I/O消耗型进程)。

注意注释/ ensure we never gain time by being placed backwards. /

这个设计是为了给睡眠较长时间的进程做时间补偿的，既使其可以快速抢占，又避免因太小的vruntime值而长期占用CPU。但有些进程只是短时间睡眠，这样唤醒时自身vruntime还是大于min_vruntime的，为了不让进程通过睡眠获得额外运行时间补偿，最后vruntime取计算出的补偿时间和进程本身的vruntime较大者。从这可以看出，虽然CFS不再区分I/O消耗型，CPU消耗型进程，但是CFS模型对IO消耗型天然的提供了快速的响应

CFS调度算法总结

对“完全公平”的认识

  • 不再区分进程类型，所有进程公平对待

  • 对I/O消耗型进程，仍然会提供快速响应(对睡眠进程做时间补偿)

  • 优先级高的进程，获得CPU时间更多(vruntime增长的更慢)

并且CFS的“完全公平”，并不是说所有进程绝对的平等，占用CPU时间完全相同，而是体现在vruntime数值上，所有进程都用虚拟时间来度量，总是让vruntime最小的进程抢占，这样看起来是完全公平的，但实际上vruntime的更新，增长速度，不同进程是不尽一样的。

CFS的思想

  • Linux采用的是完全公平调度算法（CFS）（还有实时调度算法SCHED_FIFO和SCHED_RR，按优先级执行，一般不会被抢占。直到实时进程执行完，才会执行普通进程，但是并不常用。）

  • Linux的进程调度并未使用直接均分时间片的方式，而是对优先级进行了改进，采用了两种不同的优先级范围，一种是nice值，范围是-20到+19，越大的nice值意味着更低的优先级，低nice值的进程会获得更多的处理器时间（按比例获得），第二种范围是实时优先级，其值是可配置的，默认情况下它的变化范围是从0到99，与nice值意义相反，越高的实时优先级数值意味着进程优先级越高，任何实时进程的优先级都高于普通进程

    PS：nice值还会不断对old优先级进行更改，当然也可以设置nice的值，nice值给负值必须要用root

  • nice值不是优先级，但会影响优先级 PRI(new)=PRI(old)+nice

  • 时间片过长会导致人机交互欠佳，而时间片过短会导致大量的处理器时间浪费在进程的切换上，而且I/O消耗型进程和处理器消耗型进程之间的处理器时间的不公平之处也显现出来了

  • CFS并没有直接分配时间片到进程，而是将处理器的使用比划分给了进程，这个比例还会受到nice值的影响

  • CFS的做法是允许每个进程运行一段时间，循环轮转，选择运行最少的进程作为写一个运行进程，所以根据nice值的含义-占用处理器的百分比，来根据系统中全部可运行进程总数来根据所占比例的“时间片”运行

  • Linux设计总是想分配给N个进程每个进程同样多的处理器运行时间，当N趋于无穷大的时候，按理说是可以分配给无限小的时间周期，但是这么做会很糟糕，我们也无法分配无限小的时间周期，虽然越小的时间周期可以带来更好的交互性，但还是带来不可接受的切换消耗，所以引入了一个目标延迟，来模拟无限小调度周期的近似值，现在假设目标延迟就是20ms，用它除以所有当前可以运行的进程数目就可以得到每个进程获得的时间片长度，当进程数无限大时候，每个进程分配的时间就趋于无限小，很好，进程切换又爆炸了，那么如果把最小值设为为1ms呢，进程数目再多我也保证每个进程在被强占之前获得1ms的运行时间，那么这个1ms就被称为最小粒度

参考

Linux进程调度CFS算法实现分析