1 概述

CFS的代码在kernel/sched_fair.c中实现，其中最重要的为这四个部分：
时间记账
进程选择
调度器入口
睡眠与唤醒

2 时间记账

调度器需要对进程的运行时间进行记账，这样才可以得知进程的运行时间，从而在当前运行的进程时间片减少为0时，调度其他时间片不为0的进程进行抢占。

2.1 调度器实体结构

在Linux中，CFS使用调度器实体结构（在<linux/sched.h>中定义）来追踪进程进行记账，这个结构体被命名为se，然后作为成员变量嵌入到进程描述符task_struct中。下面是调度器实体结构对应的头文件代码：

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;
    u64         nr_migrations;
#ifdef CONFIG_SCHEDSTATS
    struct sched_statistics statistics;
#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
};

2.2 虚拟实时

在Linux内核中，CFS通过虚拟实时来实现，调度器实体结构中使用进行vruntime表示。vruntime中存放了进程的虚拟运行时间（指进程运行的时间和），同时vruntime的计算经过了所有进程的标准化计算（加权计算）。所谓的标准化计算就是i通过nice值的处理器权重映射完成虚拟运行时间的计算。
在进程调度的策略中提到，在进行进程选择时CFS会统计两个重要的概念：实际运行时间和理想运行时间。通过这两个之比来选择下一个执行的进程。而在实际中，linux 的CFS使用虚拟实时来实现这一统计，通过时间记账功能记录一个进程已经执行的时间和还应该运行的时间。该功能由定义在kernel/sched_fair.c文件中的update_curr()函数实现，需要注意的是这个函数由系统定时器周期性调用，因此vruntime可以准确的测量进程的运行时间。
该函数计算当前进程的执行时间，然后将这个时间存放在delta_exec
然后将执行时间传递给__update_curr()，该函数负责使用当前可运行进程总数对运行时间进行加权运算，然后将权重值和当前运行进程的&&vruntime**相加。下面是两个函数的具体实现。

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;

    /*
     * 获得最后一次修改负载后当前任务所占用的运行总时间 (this cannot
     * overflow on 32 bits):
     */
    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(struct cfs_rq *cfs_rq, struct sched_entity *curr,
          unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;

    schedstat_set(curr->statistics.exec_max,
              max((u64)delta_exec, curr->statistics.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);

    curr->vruntime += delta_exec_weighted;
    update_min_vruntime(cfs_rq);
}

3 进程选择

在进程调度策略中提到过，在CFS中进程选择是通过实际运行时间和理想运行时间的比较得出的。但是在具体实现中，只使用了vruntime来选择下一个执行的进程，CFS的调度器会选择vruntime最小的进程来进行执行。

3.1 查找

在CFS中为了更快的寻找到具有最小vruntime的进程，其使用了红黑树对可运行进程进行组织。根据红黑树的原理，具有最小的vruntime的进程必定在红黑树的最左叶子节点。所以仅仅需要遍历就可以找到下一个执行的进程。该功能定义在kernel/sched_fair.c的pick_next_entity()函数中。需要注意的是，可执行进程红黑树中没有最左子节点（为空时），表示没有可以运行的进程，但是CFS调度器不会等待，而是调度一个空进程idle来进行运行。

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct sched_entity *se = __pick_next_entity(cfs_rq);
    struct sched_entity *left = se;

    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

    /*
     * Prefer last buddy, try to return the CPU to a preempted task.
     */
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;

    clear_buddies(cfs_rq, se);

    return se;
}

3.2 添加可执行进程

向可执行进程红黑树中添加进程时，CFS的实现采用了缓存的方法，当新加入的进程时最左子节点时，那么取代已经缓存的当前最左子节点，否则当前缓存的最左叶子节点不变，通过这种方法可以有效减少最左叶子节点的遍历。该功能定义在kernel/sched_fair.c的enqueue_entity()函数中。但是该函数只是更新时间和一些统计数据，具体插入工作则由__enqueue_entity函数完成。

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    /*
     * Update the normalized vruntime before updating min_vruntime
     * through callig update_curr().
     */
    if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
        se->vruntime += cfs_rq->min_vruntime;

    /*
     * Update run-time statistics of the 'current'.
     */
    update_curr(cfs_rq);
    account_entity_enqueue(cfs_rq, se);

    if (flags & ENQUEUE_WAKEUP) {
        place_entity(cfs_rq, se, 0);
        enqueue_sleeper(cfs_rq, se);
    }

    update_stats_enqueue(cfs_rq, se);
    check_spread(cfs_rq, se);
    if (se != cfs_rq->curr)
        __enqueue_entity(cfs_rq, se);
}

/*
 * Enqueue an entity into the rb-tree:
 */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    s64 key = entity_key(cfs_rq, se);
    int leftmost = 1;

    /*
     * Find the right place in the rbtree:
     */
    while (*link) {//遍历查找合适的插入位置
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        /*
         * We dont care about collisions. Nodes with
         * the same key stay together.
         */
        if (key < entity_key(cfs_rq, entry)) {//当插入键值小于当前节点的键值时
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = 0;
        }
    }

    /*
     * Maintain a cache of leftmost tree entries (it is frequently
     * used):
     */
    if (leftmost)//对最常用的最左叶子节点进行缓存
        cfs_rq->rb_leftmost = &se->run_node;

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

3.3 删除不可执行的进程

当然还有一个删除节点的函数，这个功能在进程阻塞时，负责将代表可执行进程的节点移出红黑树。该功能定义在kernel/sched_fair.c的dequeue_entity()函数中，当然和插入一样该函数完成的也只是一些统计工作，具体删除是由__dequeue_entity()函数完成的。

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    u64 min_vruntime;

    /*
     * Update run-time statistics of the 'current'.
     */
    update_curr(cfs_rq);

    update_stats_dequeue(cfs_rq, se);
    if (flags & DEQUEUE_SLEEP) {
#ifdef CONFIG_SCHEDSTATS
        if (entity_is_task(se)) {
            struct task_struct *tsk = task_of(se);

            if (tsk->state & TASK_INTERRUPTIBLE)
                se->statistics.sleep_start = rq_of(cfs_rq)->clock;
            if (tsk->state & TASK_UNINTERRUPTIBLE)
                se->statistics.block_start = rq_of(cfs_rq)->clock;
        }
#endif
    }

    clear_buddies(cfs_rq, se);

    if (se != cfs_rq->curr)
        __dequeue_entity(cfs_rq, se);
    account_entity_dequeue(cfs_rq, se);

    min_vruntime = cfs_rq->min_vruntime;
    update_min_vruntime(cfs_rq);

    /*
     * Normalize the entity after updating the min_vruntime because the
     * update can refer to the ->curr item and we need to reflect this
     * movement in our normalized position.
     */
    if (!(flags & DEQUEUE_SLEEP))
        se->vruntime -= min_vruntime;
}

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    if (cfs_rq->rb_leftmost == &se->run_node) {
        struct rb_node *next_node;

        next_node = rb_next(&se->run_node);
        cfs_rq->rb_leftmost = next_node;
    }

    rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

4 调度器入口

进程调度其的主要入口函数为Schedule()，其定义在kernel/sched.c中。这个函数时内核其他部分调用进程调度器的入口。Schedule()函数首先找到一个最高优先级的调度类（该调度类有自己的可执行队列），然后Schedule函数再由这个调度类将下一个进行运行的进程告知Schedule函数。Schedule函数最重要的工作由pick_next_task()函数来完成，该函数会以优先级为次序，从高到低检查每一个调度类，并且从最高优先级的调度类中选择最高优先级的进程。

/*
 * schedule() is the main scheduler function.
 */
asmlinkage void __sched schedule(void)
{
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct rq *rq;
    int cpu;

need_resched:
    preempt_disable();
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    rcu_note_context_switch(cpu);
    prev = rq->curr;
    switch_count = &prev->nivcsw;

    release_kernel_lock(prev);
need_resched_nonpreemptible:

    schedule_debug(prev);

    if (sched_feat(HRTICK))
        hrtick_clear(rq);

    raw_spin_lock_irq(&rq->lock);
    clear_tsk_need_resched(prev);

    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        if (unlikely(signal_pending_state(prev->state, prev)))
            prev->state = TASK_RUNNING;
        else
            deactivate_task(rq, prev, DEQUEUE_SLEEP);
        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);

    if (likely(prev != next)) {
        sched_info_switch(prev, next);
        perf_event_task_sched_out(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
        raw_spin_unlock_irq(&rq->lock);

    post_schedule(rq);

    if (unlikely(reacquire_kernel_lock(current) < 0)) {
        prev = rq->curr;
        switch_count = &prev->nivcsw;
        goto need_resched_nonpreemptible;
    }

    preempt_enable_no_resched();
    if (need_resched())
        goto need_resched;
}

/*
 * 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;
    }
}

5 睡眠与唤醒

当进程被阻塞时会处于一个不可执行的状态，这个状态也被称为睡眠状态，调度程序不能够选择一个处于睡眠状态的进程执行，进程在等待一些事件的发生时就会处于这个状态。而唤醒则是处于睡眠状态的进程等待的事件发生，那么进程就会处于可执行状态，其会被亦儒道可执行红黑树中。

5.1 等待队列

睡眠的进程都会存放在等待队列中，内核使用wake_queue_head_t来代表等待队列。等待队列有两种实现方式，分别为DECLARE_WAITQUEUE()静态创建和init_waitqueue_head()动态创建。 在阻塞时进程会把自己放入等待队列并设置自己为不可执行状态，当阻塞的事件发生时，队列上的进程会唤醒。
进程加入等待队列有以下步骤：

1. 调用宏DEFINE_WAIT()创建一个等待队列；
2. 调用add_wait_queue()把自己加入到队列中。进程会在等待的条件唤醒，所以需要在其他地方撰写相应的唤醒条件代码，当等待的事件发生时，可以执行wake_up()操作；
3. 调用prepare_to_wait()方法将进程状态设置为TASK_INTERRUPTIBLE或者TASK_UNINTERRUPTIBLE。当循环遍历时，该函数还可以把进程加回到等待队列；
4. 状态为TASK_INTERRUPTIBLE的进程可以被信号唤醒。这个唤醒为伪唤醒，因为进程等待的事件并未发生；
5. 进程被唤醒时，检查等待的事件是否发生。发生则退出休眠，不发生则循环调用Schedule()函数；
6. 等待的事件发生时，进程会将自己设置为TASK_RUNNING然后调用finish_wait()方法推出等待队列；

需要注意的是，当进程休眠前其所等待的事件发生时，进程就不会进入休眠状态。
函数inotify_read()函数是等待队列的一个典型用法，其负责从通知文件描述符中读取信息，该函数在fs/notify/inotify/inotify_user.c中实现。

static ssize_t inotify_read(struct file *file, char __user *buf,
                size_t count, loff_t *pos)
{
    struct fsnotify_group *group;
    struct fsnotify_event *kevent;
    char __user *start;
    int ret;
    DEFINE_WAIT(wait);

    start = buf;
    group = file->private_data;

    while (1) {
        prepare_to_wait(&group->notification_waitq, &wait, TASK_INTERRUPTIBLE);

        mutex_lock(&group->notification_mutex);
        kevent = get_one_event(group, count);
        mutex_unlock(&group->notification_mutex);

        if (kevent) {
            ret = PTR_ERR(kevent);
            if (IS_ERR(kevent))
                break;
            ret = copy_event_to_user(group, kevent, buf);
            fsnotify_put_event(kevent);
            if (ret < 0)
                break;
            buf += ret;
            count -= ret;
            continue;
        }

        ret = -EAGAIN;
        if (file->f_flags & O_NONBLOCK)
            break;
        ret = -EINTR;
        if (signal_pending(current))
            break;

        if (start != buf)
            break;

        schedule();
    }

    finish_wait(&group->notification_waitq, &wait);
    if (start != buf && ret != -EFAULT)
        ret = buf - start;
    return ret;
}

5.2 唤醒

唤醒操作在前面也提到过是通过wake_up()函数完成的，其会唤醒制定的等待队列上的所有进程。在wake_up()函数中函数如下：
首先，调用了try_to_wake_up()去将进程状态设置为TASK_RUNNING状态；
其次，调用enqueue_task()函数将进程放入可执行红黑树中；
最后，若被唤醒的进程优先级高于当前正在执行的进程，设置need_resched()标志；

这是个人在阅读《Linux内核设计与实现》时候的一点心得，里面加入了一些自己关于操作系统的理解，对自己的现有的知识进行梳理，如有错误敬请指正。