Linux内核之fair调度

今天主要来讲一下Linux的fair调度器，通常Linux下有dl, rt, cfs, idle四种调度器，其中，dl（deadline）调度器优先级最高，然后是RT(real time)调度器, 继而是CFS调度器,  最后才是idle调度。 fair调度器的初始化是在main.c的start_kernel中调用sched_init完成，程序栈为：

start_kernel
    sched_init    // 主要是一些带宽控制相关的
       init_sched_fair_class

但我们知道，其实，fair真正管用的是fair.c内部的结构体struct sched_class fair_sched_class, 本篇不讲sched_init函数的实现内容，只简单说明fair_sched_class结构体。如下是fair_sched_class的结构成员，

const struct sched_class fair_sched_class = {
    .next         = &idle_sched_class,     // 下一个调度器是idle调度器（链表按照优先级顺序排列）
    .enqueue_task      = enqueue_task_fair, // 将一个task加入到cfs_rq
    .dequeue_task      = dequeue_task_fair, // 将一个task从cfs_rq删除

    .yield_task        = yield_task_fair,   // 当前指定rq的task放弃CPU执行
    .yield_to_task     = yield_to_task_fair, // 当前rq的task放弃执行，并设置下次切换的task
    .check_preempt_curr    = check_preempt_wakeup, // 检查指定task是否可以抢占当前task

    .pick_next_task = pick_next_task_fair, // 切换task, 当前task加入到cfs_rq队列，取新的task设置成current

    .put_prev_task      = put_prev_task_fair, // 将当前task加入cfs_rq队列
    .set_curr_task      = set_curr_task_fair, // 设置task为当前task

    .task_tick        = task_tick_fair,   // 一个tick到来，会调用该函数，用于检查是否需要调度
    .task_fork        = task_fork_fair,   // 新创建一个task，需要调用这个分配虚拟时钟

    .prio_changed        = prio_changed_fair,  // 改变优先级
    .switched_from        = switched_from_fair, //进程改变调度器时使用
    .switched_to        = switched_to_fair, // 进程改变调度器时使用

    .update_curr        = update_curr_fair, // 更新当前task链上的虚拟时钟相关
}

在开始讲结构体之前，有几个基本概念应该了解：一，一个核上只有一个run queue(rq)， 一个rq下面可能有一个或者多个cfs_rq；二、所有的task都是用entity来表示（调度实体）；三、所有的调度实体（entity）都是挂接到红黑树上进行管理，即运行队列是一棵红黑树；四，一个运行队列下面挂可能是一个task entity，也可能是一个group entity。

首先，当应用程序创建一个进程（fork）的时候，会调用task_fork和对应调度器进行关联，这里是fair的task_fork，

点击(此处)折叠或打开

.task_fork    = task_fork_fair,
                        update_curr   // 更新当前task的虚拟时钟
                        place_entity  // 根据当前cfs_rq队列情况，计算出新task最佳虚拟时钟

然后，一个新的task创建，这时候，需要将新的task加入到cfs_rq队列，才能参与调度，即ready状态，调用如下，
点击(此处)折叠或打开

.enqueue_task   = enqueue_task_fair,
                       enqueue_entity
                           update_curr      // 更新entity的虚拟时钟
                           __enqueue_entity // 将新的entity加入到红黑树
                       on_rq = 1;           // on_rq设置为1

此后，该task就已经加入了调度。如果此后，该task需要休眠或者等待IO，则调用dequeue从运行队列上取下来，
点击(此处)折叠或打开

.dequeue_task  = dequeue_task_fair,
                      dequeue_entity
                          update_curr // 更新entity的虚拟时钟
                          clear_buddies // 清理buddy，buddy用于选择最佳task使用，是为了给有贡献的任务做补偿使用的，这里因为要休眠了， 所以清楚掉这个标记
                         __dequeue_entity // 从红黑树上取下当前task
                         on_rq = 0;     // 将on_rq 设置成0

注意：entity的on_rq成员，只有在enqueue和dequeue的时候才会改变。而Linux总体有running, ready和sleep三种大的状态。一、当执行enqueue函数加入到cfs_rq红黑树上的时候（on_rq会同步设置为1），为ready状态，此后，task可参与调度；二、当task获取到运行权限的时候， 则要将task从红黑树上取下来，保存到current当中，但on_rq的值保持不变即on_rq = 1，此时为running状态（因为每次找最合适的task的时候总是从cfs_rq红黑树的最左边开始）；三、当进程需要休眠或者等待IO的时候，则需要调用dequeue函数从红黑树上取下来，并且同步设置为on_rq = 0， 此时为sleep/io状态。四、调度器总是以在红黑树链表上的虚拟时钟最小的task来运行，当这个最小虚拟时钟的task在运行过程中，会在每个tick到来的时候，根据优先级，来增加它的虚拟时钟值，当前他的虚拟时钟值大于红黑树里面的其他最小虚拟时钟值task的时候，就会发生task切换。

有时候，task在运行过程中， 只需要短暂放弃CPU，而不需要休眠，则调用，

点击(此处)折叠或打开

.yield_task    = yield_task_fair,
                      clear_buddies
                      update_curr
                      set_skip_buddy   // 设置cfs_rq的skip值为当前task，表示下次调度的时候，不参与调度

有时候，task在运行的过程中， 需要短暂将CPU让给指定程序，
点击(此处)折叠或打开

.yield_to_task  = yield_to_task_fair,
                      set_next_buddy  // 将指定task设置成cfs_rq的next值，表示下次调度优先考虑分配
                      yield_task_fair // 将当前task设置成skip值，下次不参与调度

由于系统在运行过程中，可能会出现从一个调度器切换到另一个调度器的情况（cfs->idle），意味着当前调度器里面没有任务需要运行，则需要调用put_prev_task，将对应task释放到它对应调度器的运行链表上面，则，
点击(此处)折叠或打开

.put_prev_task = put_prev_task_fair,
                     put_prev_entity //其实就是将当前task相关联的entity都加入到对应cfs_rq的红黑树

由于系统上次刚运行完idle或者其他调度器的task，现在需要切换到cfs调度器，那么就需要调用set_curr_task设置当前调度器的task为curr，
点击(此处)折叠或打开

.set_curr_task = set_curr_task_fair,
                      set_next_entity // 将指定task设置成cfs_rq的curr值，进行调度运行

注： put_prev_entity函数 会将entity加入到红黑树，并把cfs_rq->curr 设置成NULL, set_next_entiry会将entity从红黑树中移除，并把cfs_rq->curr设置成当前这个entity。

static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /* 'current' is not kept within the tree. */
    if (se->on_rq) {
        __dequeue_entity(cfs_rq, se); // 加入红黑树
    }

    cfs_rq->curr = se; // 设置当前cfs_rq的curr值
    se->prev_sum_exec_runtime = se->sum_exec_runtime;
}

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    if (prev->on_rq)
        update_curr(cfs_rq);

    if (prev->on_rq) {
         __enqueue_entity(cfs_rq, prev); // 移除红黑树
    }
    cfs_rq->curr = NULL;
}

当一个时钟到达后，会调用task_tick去管理自己的task，判断是否需要切换task，
点击(此处)折叠或打开

.task_tick      = task_tick_fair,
                      entity_tick
                         update_curr
                         check_preempt_tick // 如果在红黑树中有虚拟时钟更小的task，则设置当前task需要reschedule

判断一个task是否可以抢占当前task，
点击(此处)折叠或打开

.check_preempt_curr = check_preempt_wakeup, // 主要是设置cfs_rq的next和last值，让下次调度优先选择这个task
                      put_prev_task
                      pick_next_entity
                      set_next_entity

当一个进程schedule的时候，切换task的时候，调用如下，
点击(此处)折叠或打开

schedule
    __schedule
        pick_next_task  // 调用调度器的pick_next_task切换进程。
           fair_sched_class.pick_next_task（...）
        return;

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) { //这里的顺序是dl->rt->cfs->idle
        p = class->pick_next_task(rq, prev, rf);
        if (p) {
            if (unlikely(p == RETRY_TASK))
                goto again;
            return p;
        }
    }
}

fair的pick_next_task，这里会详细讲解该函数， 实现如下，
点击(此处)折叠或打开

static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    struct task_struct *p;
    int new_tasks;

again:
    if (!cfs_rq->nr_running)  // 如果cfs_rq的红黑树上没有程序，即没有ready的task，则跳转到idle
        goto idle;

#ifdef CONFIG_FAIR_GROUP_SCHED
    if (prev->sched_class != &fair_sched_class)  // 如果当前进程不是cfs调度器，就用simple的通用调度切换方法
        goto simple;

    // 这个do while主要是找到最应该被调度的entity，即找到下一个task实体， 这里是存在多个cfs_rq的情况。
    do {
        struct sched_entity *curr = cfs_rq->curr;

        if (curr) {
            if (curr->on_rq) // 如果当前cfs_rq的task在队列上，更新虚拟时钟
                update_curr(cfs_rq);
            else
                curr = NULL;

            // 返回true,表示当前cfs已经超出运行时间，不能再进行组内调度，应该全局选择
            if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
                cfs_rq = &rq->cfs;

                if (!cfs_rq->nr_running)
                    goto idle;

                goto simple;
            }
        }
        // 从cfs_rq获取虚拟时钟最小或者最应该参与调度的task
        se = pick_next_entity(cfs_rq, curr);
        cfs_rq = group_cfs_rq(se);// 如果是调度组，会继续while，非调度组的group_cfs_rq返回NULL
    } while (cfs_rq);

    p = task_of(se); // 这里的se就是上面组调度里面，找到的最合适参与调度的task
    if (prev != p) { // 这个prev != p里面，主要是更新prev和p相关的组（cfs_cq）内成员的虚拟时钟
        struct sched_entity *pse = &prev->se;

        while (!(cfs_rq = is_same_group(se, pse))) {
            int se_depth = se->depth;
            int pse_depth = pse->depth;

            if (se_depth <= pse_depth) { // 表明pre所在的调度组 深度更深，需要更新prev所在的组的虚拟时钟
                put_prev_entity(cfs_rq_of(pse), pse);
                pse = parent_entity(pse);
            }
            if (se_depth >= pse_depth) { // 表明curr所在的调度组更深，需要将curr所在调度组一连串设置成对应cfs_rq的curr
                set_next_entity(cfs_rq_of(se), se);
                se = parent_entity(se);
            }
        }

        put_prev_entity(cfs_rq, pse);
        set_next_entity(cfs_rq, se);
    }

    goto done;
simple:
#endif
    // put_prev_task会将prev task释放到对应调度器的红黑树队列里面
    put_prev_task(rq, prev);

    do {
        se = pick_next_entity(cfs_rq, NULL); // 从cfs_rq中选择一个task
        set_next_entity(cfs_rq, se);  // 将该task设置成curr，参与调度
        cfs_rq = group_cfs_rq(se);   // 如果当前Curr为调度组，继续找该调度组里面的成员
    } while (cfs_rq);

    p = task_of(se);

done: __maybe_unused;
    if (hrtick_enabled(rq))
        hrtick_start_fair(rq, p);

    return p;

idle:
    new_tasks = idle_balance(rq, rf);
    if (new_tasks < 0)
        return RETRY_TASK;

    if (new_tasks > 0)
        goto again;

    return NULL;
}

pick_next_entity的函数为选择最佳task的关键算法，实现如下，

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;

    // left是红黑树里面，拥有最小虚拟时钟的task，如果left为NULL或者curr的虚拟时钟比当前最小的left还要小，那么left就设置成curr，即curr还可以继续获得CPU，不进行任务切换
    if (!left || (curr && entity_before(curr, left)))
        left = curr;

    se = left; // 这个se不是指向curr进程,就是指向红黑树的最小虚拟时钟进程

    // 发现se指向的task被设置成不参与调度（skip）
    if (cfs_rq->skip == se) {
        struct sched_entity *second;

        if (se == curr) { // 如果这个不参与调度的task就是当前进程,那么就取红黑树的第一个实体
            second = __pick_first_entity(cfs_rq);
        } else { // 这个不参与调度的task不是curr进程，那说明这个task是红黑树的最小虚拟时钟task，因此，需要从红黑树中找到一个次小的虚拟时钟task
            second = __pick_next_entity(se);
            // 判断这个次小task是否能抢占curr，如果不能，second就还是变为curr
            if (!second || (curr && entity_before(curr, second)))
                second = curr;
        }

        // 判读这个新的task是否能抢占left，如果能，se就为它,这里的对比条件并没有最开始的严格，这里允许一个最小调度差值。
        if (second && wakeup_preempt_entity(second, left) < 1)
            se = second;
    }

    // 发现设置了last值，则优先调度last指向的task
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;

    // 发现设置了last值，则优先调度last指向的task
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

    // 清除task的next或last值，以免下次调度的时候，又把last和next加入判断，导致不公平
    clear_buddies(cfs_rq, se);

    return se;
}

wakeup_preempt_entity用于比较是否可以被抢占的函数，实现如下，

static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
    s64 gran, vdiff = curr->vruntime - se->vruntime;

    if (vdiff <= 0)  // curr的虚拟时钟值明显比se小，直接返回，可以抢占
        return -1;

    gran = wakeup_gran(se); // 计算curr的最小抢占期限粒度
    if (vdiff > gran) // 如果当前curr的虚拟时钟比se的虚拟时钟多超过最小抢占粒度的时间值，那么直接返回不支持抢占
        return 1;

    return 0; // 返回支持抢占
}

schedule函数大概实现如下，
点击(此处)折叠或打开

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

    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr; // 获取当前进程
    .....
    update_rq_clock(rq); //更新rq的时钟

    // 如果prev是不可运行的, 并且内核态不被抢占,说明该task是主动schedule的
    if (!preempt && prev->state) {
        // 如果当前进程有非阻塞等待信号，并且它的状态是TASK_INTERRUPTIBLE
        if (unlikely(signal_pending_state(prev->state, prev))) {
            prev->state = TASK_RUNNING;// 留着rq中，下次调度的时候，会处理自己的信号
        } else { // 否则需要将prev进程从就绪队列中删除
            deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);
            prev->on_rq = 0;

            if (prev->in_iowait) {
                atomic_inc(&rq->nr_iowait);
                delayacct_blkio_start();
            }

            if (prev->flags & PF_WQ_WORKER) { // 告诉工作队列唤醒相关
                struct task_struct *to_wakeup;

                to_wakeup = wq_worker_sleeping(prev);
                if (to_wakeup)
                    try_to_wake_up_local(to_wakeup, &rf);
            }
        }
        switch_count = &prev->nvcsw;
    }

    next = pick_next_task(rq, prev, &rf); // 挑选一个优先级最高的任务排进队列
    clear_tsk_need_resched(prev);
    clear_preempt_need_resched();

    if (likely(prev != next)) {
        rq->nr_switches++;
        rq->curr = next;

        ++*switch_count; // 进程切换次数更新
        rq = context_switch(rq, prev, next, &rf); // bsp相关的上下文切换，包含映射表和寄存器
    } else { // 如果是同一个进程不需要切换
        rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
        rq_unlock_irq(rq, &rf);
    }
}

context_switch函数实现如下，

static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
     struct task_struct *next, struct rq_flags *rf)
{
    struct mm_struct *mm, *oldmm;

    prepare_task_switch(rq, prev, next);

    mm = next->mm;
    oldmm = prev->active_mm;

    arch_start_context_switch(prev);

    if (!mm) { //内核线程是没有mm，内核task和应用进程的mm共享，因此内核线程延用上一个task的mm
        next->active_mm = oldmm;
        mmgrab(oldmm);
        enter_lazy_tlb(oldmm, next);
    } else
        switch_mm_irqs_off(oldmm, mm, next);

    if (!prev->mm) {
        prev->active_mm = NULL;
        rq->prev_mm = oldmm;
    }

    rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

    prepare_lock_switch(rq, next, rf);

    switch_to(prev, next, prev); // 体系结构切换，主要是寄存器切换
    barrier();

    return finish_task_switch(prev);
}

const struct sched_class fair_sched_class = {
.enqueue_task    = enqueue_task_fair,
                       enqueue_entity
                           update_curr
                           __enqueue_entity

.dequeue_task    = dequeue_task_fair,
                      dequeue_entity
                          update_curr
                          clear_buddies
                         __dequeue_entity

.yield_task    = yield_task_fair,
                      clear_buddies
                      update_curr
                      set_skip_buddy

.yield_to_task    = yield_to_task_fair,
                        set_next_buddy
                        yield_task_fair

.check_preempt_curr = check_preempt_wakeup,
                           set_next_buddy
                           update_curr
                           set_next_buddy

.pick_next_task  = pick_next_task_fair,
                       put_prev_task
                       pick_next_entity
                       set_next_entity

.put_prev_task    = put_prev_task_fair,
                        put_prev_entity

.set_curr_task = set_curr_task_fair,
                      set_next_entity

.task_tick      = task_tick_fair,
                      entity_tick
                         update_curr
                         check_preempt_tick

.task_fork      = task_fork_fair,
                      place_entity
}

check_cfs_rq_runtime 检查 cfs_rq的是否没有可运行时间，true表示无运行时间，false表示还可以继续使用。
throttle_cfs_rq throttle对应的cfs_rq。