1. CFS进程入队和出队

完全公平调度器CFS中有两个函数可用来增删队列的成员:enqueue_task_fair和dequeue_task_fair分别用来向CFS就绪队列中添加或者删除进程

2 enqueue_task_fair入队操作

2.1 enque_task_fair函数

向就绪队列中放置新进程的工作由函数enqueue_task_fair函数完成, 该函数定义在kernel/sched/fair.c, line 5442, 其函数原型如下

该函数将task_struct *p所指向的进程插入到rq所在的就绪队列中, 除了指向所述的就绪队列rq和task_struct的指针外, 该函数还有另外一个参数wakeup. 这使得可以指定入队的进程是否最近才被唤醒并转换为运行状态(此时需指定wakeup = 1), 还是此前就是可运行的(那么wakeup = 0).

static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)

enqueue_task_fair的执行流程如下

• 如果通过struct sched_entity的on_rq成员判断进程已经在就绪队列上, 则无事可做.
• 否则, 具体的工作委托给enqueue_entity完成, 其中内核会借机用update_curr更新统计量

在enqueue_entity内部如果需要会调用__enqueue_entity将进程插入到CFS红黑树中合适的结点

2.2 enque_task_fair完全函数

/*
 * The enqueue_task method is called before nr_running is
 * increased. Here we update the fair scheduling stats and
 * then put the task into the rbtree:
 */
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;

    for_each_sched_entity(se) {
        if (se->on_rq)
            break;
        cfs_rq = cfs_rq_of(se);
        enqueue_entity(cfs_rq, se, flags);

        /*
         * end eva luation on encountering a throttled cfs_rq
         *
         * note: in the case of encountering a throttled cfs_rq we will
         * post the final h_nr_running increment below.
        */
        if (cfs_rq_throttled(cfs_rq))
            break;
        cfs_rq->h_nr_running++;

        flags = ENQUEUE_WAKEUP;
    }

    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        cfs_rq->h_nr_running++;

        if (cfs_rq_throttled(cfs_rq))
            break;

        update_load_avg(se, 1);
        update_cfs_shares(cfs_rq);
    }

    if (!se)
        add_nr_running(rq, 1);

    hrtick_update(rq);
}

2.3 for_each_sched_entity

首先内核查找到待天机进程p所在的调度实体信息, 然后通过for_each_sched_entity循环所有调度实体,

//  enqueue_task_fair函数
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;

    for_each_sched_entity(se)
    {
    /*  ......  */
    }
}

linux对组调度的支持可以通过CONFIG_FAIR_GROUP_SCHED来启用, 在启用和不启用的条件下, 内核对很多函数的实现也会因条件而异, 这点对for_each_sched_entity函数尤为明显, 参见启用CONFIG_FAIR_GROUP_SCHED和不启用CONFIG_FAIR_GROUP_SCHED

• 如果通过struct sched_entity的on_rq成员判断进程已经在就绪队列上, 则无事可做.
• 否则, 具体的工作委托给enqueue_entity完成, 其中内核会借机用update_curr更新统计量.

//  enqueue_task_fair函数
{
        /*  如果当前进程已经在就绪队列上  */
        if (se->on_rq)
            break;

        /*  获取到当前进程所在的cfs_rq就绪队列  */
        cfs_rq = cfs_rq_of(se);
        /*  内核委托enqueue_entity完成真正的插入工作  */
        enqueue_entity(cfs_rq, se, flags);
}

2.4 enqueue_entity插入进程

enqueue_entity完成了进程真正的入队操作, 其具体流程如下所示

• 更新一些统计统计量, update_curr, update_cfs_shares等
• 如果进程此前是在睡眠状态, 则调用place_entity中首先会调整进程的虚拟运行时间
• 最后如果进程最近在运行, 其虚拟运行时间仍然有效, 那么则直接用__enqueue_entity加入到红黑树

首先如果进程最近正在运行, 其虚拟时间时间仍然有效, 那么(除非它当前在执行中)它可以直接用__enqueue_entity插入到红黑树, 该函数徐娅萍处理一些红黑树的机制, 这可以依靠内核的标准实现, 参见__enqueue_entity函数, kernel/sched/fair.c, line483

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    /*
     * Update the normalized vruntime before updating min_vruntime
     * through calling 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);
    enqueue_entity_load_avg(cfs_rq, se);
    account_entity_enqueue(cfs_rq, se);
    update_cfs_shares(cfs_rq);

    /*  如果当前进行之前在睡眠刚被唤醒  */
    i