Linux当中的完全公平调度CFS

之前一篇文章讲了linux当中的调度，今天来一篇讲讲linux当中最普遍的完全公平调度。
如前文所述，某种调度，最核心的就是其调度类了，完全公平调度类的结构如下：

const struct sched_class fair_sched_class = {
    .next            = &idle_sched_class,// 它下来就是idle了
    .enqueue_task        = enqueue_task_fair,// 队列操作，每一个调度类，操作涉rq当中的一个子队列
    .dequeue_task        = dequeue_task_fair,
    .yield_task        = yield_task_fair,
    .yield_to_task        = yield_to_task_fair,

    .check_preempt_curr    = check_preempt_wakeup,

    .pick_next_task        = __pick_next_task_fair,
    .put_prev_task        = put_prev_task_fair,
    .set_next_task = set_next_task_fair,
...
    .task_tick        = task_tick_fair,
    .task_fork        = task_fork_fair,

    .prio_changed        = prio_changed_fair,
    .switched_from        = switched_from_fair,
    .switched_to        = switched_to_fair,

    .get_rr_interval    = get_rr_interval_fair,

    .update_curr        = update_curr_fair,
..
};

cfs对应的调度子队列的结构为：

struct cfs_rq {
    struct load_weight    load;
    unsigned long        runnable_weight;
    unsigned int        nr_running;
    unsigned int        h_nr_running; /* SCHED_{NORMAL,BATCH,IDLE} */
    unsigned int        idle_h_nr_running; /* SCHED_IDLE */

    u64            exec_clock;
    u64            min_vruntime;// 内核会不断递增
    /*仅包含两个结构rb_root和 rb_leftmost*/
    struct rb_root_cached    tasks_timeline;
    /**/

    /*
     * 'curr' points to currently running entity on this cfs_rq.
     * It is set to NULL otherwise (i.e when none are currently running).
     */
    struct sched_entity    *curr;
    struct sched_entity    *next;
    struct sched_entity    *last;
    struct sched_entity    *skip;
...
};

整个队列的管理关键在于变量rb_root_cached，它的结构如下：

struct rb_root_cached {
    struct rb_root rb_root;//红黑树根节点
    struct rb_node *rb_leftmost;// 红黑树当中最左节点
};

这两个成员就把整个cfs队列当中的所有可以调度的进程管理好了，每次取最小，直接拿出rb_leftmost即可
完全公平调度依赖于虚拟时钟，用这个度量进程在这个体系当中得到的CPU时间。它在计算一个进程的运行时间的时候，会把实际运行的时间除以各个进程的优先级，这样，优先级高的进程明明花费了相同的时间，但是除以优先级之后，反而虚拟时间较少，这样，排序就靠前，下次就极有可能被调度了。